Cryptography Reference
In-Depth Information
• KeyDist
BF
`
: On input 1
n
, it uses Gen(1
k
) to produce a description of
a multiplicative group G a generator g ∈G of prime order q where q is a
k-bit prime. It also samples elements a
0
,...,a
`
∈ Z
q
−{0} uniformly at
random. The tuple ha
0
,...,a
`
i constitutes the tracing key tk, whereas the
public-key contains the tuple
H = hh
0
=
df
g
a
0
,h
1
=
df
g
a
1
,...,h
`
=
df
g
a
`
i
It, further, computes a code Γ = {γ
1
,...,γ
n
} that contains n tuples of
Z
q
as follows: first it defines a (n−`) ×n matrix M so that the j-th row
of M equals h1,2
j−1
,...,n
j−1
i. Now let β
1
,...,β
`
be a basis of the right
of the matrix B. i.e. γ
j
= hβ
j
,...,β
j
i. We have the following equation:
2
3
1
1
1
...
1
4
5
1
2
3
...
n
2
3
...
β
1
β2 β
3
... β
`
...
1
2
2
2
3
2
... n
2
4
5
= 0
×
(3.1)
. . .
1
n−`−2
2
n−`−2
3
n−`−2
... n
n−`−2
1
n−`−1
2
n−`−1
3
n−`−1
... n
n−`−2
.
.
Hence, Γ contains n codewords of each length `, we note that using La-
grange interpolation we can directly construct the j-th codeword in Γ.
The secret key sk
j
is computed as a vector δ = b
j
· γ
j
with b
j
=
a
0
(
P
i=1
a
i
γ
i
)
−1
for j = 1,...,n. The encryption key ek is set to the
pair hH,Γi
• Transmit
BF
`
: Given a message m ∈ hgi and the encryption key ek =
hH,Γi, the encryption of the message is calculated similarly to ElGamal
encryption as follows:
hh
0
·m,h
1
,...,h
`
i
where r is sampled randomly from Z
q
−{0}. Standard variations such as
hH(h
0
) ⊕m,h
1
,...,h
`
i where H is a k-bit long hash function and m ∈
{0,1}
k
are also possible (but will not be analyzed here).
• Receive
BF
`
: Having access to the public key ek = hH,Γi and given the
key material sk
j
that is the vector δ = b
j
·γ
j
, on input a transmission of
the form:
hA
0
,A
1
,...,A
`
i
it outputs the result of the following computation:
A
0
(A
δ
1
...A
δ
`
)
−1
1
Recall that the right kernel of a matrix B is the set {γ | B·γ = 0}.
