Cryptography Reference
In-Depth Information
unary multiuser encryption scheme. Let htk,ek,sk
1
,...,sk
n
i be distributed
according to KeyDist
F
which employs a q-ary fingerprinting code
F
. We have
tk = (W,ik) ← CodeGen
`
(1
n
), and ek = {k
i,j
}
(i,j)∈[q]×[`]
so that the private
key for any user-index u ∈ [n] is defined as sk
u
= hk
w
1
,1
,k
w
2
,2
,...,k
w
`
,`
i
where w
u
= hw
1
,w
2
,...,w
`
i∈W.
We will now prove that for any m ∈M and any user-index u ∈ [n] it holds
that
Prob[Receive
CFN[
F
]
(Transmit
CFN[
F
]
(ek,m),sk
u
) = m] = 1
Provided that m = r
1
⊕...⊕r
`
holds for a set of strings r
1
,...,r
`
of the
same length with m, and the transmission is Transmit
CFN[
F
]
(ek,m) consist-
ing of an q×` matrix as described above. Observe that the Receive algorithm
on input sk
u
= hk
w
1
,1
,k
w
2
,2
,...,k
w
`
,`
i is capable of decrypting exactly one ci-
phertext from each column, i.e., for any j = 1,...,` there is a i ∈{1,2,...,q}
so that decryption of
E
k
i,j
(m
j
) is available to that particular user with index
u, which implies the availability of the share m
j
. The receiver then can apply
the ⊕ operation to all shares to calculate the plaintext m.
The Boneh-Naor Scheme
The mode of transmission in a unary multiuser encryption scheme that is
based on fingerprinting codes can be modified to support a shorter transmis-
sion overhead. The idea is to sample a column-index l ←{1,...,`} and trans-
mit h
E
k
1,l
(m),
E
k
2,l
(m),...,
E
k
q,l
(m)i. Such modification ensures the short ci-
phertext during the normal transmission. We define the multiuser encryption
scheme
ME
BN[
F
]
as follows:
• Transmit
BN[
F
]
: Given m and the encryption key ek = {k
i,j
}
(i,j)∈[q]×[`]
, it
first picks l ← {1,...,`} and it transmits the encryption of the message
M with ek by using a symmetric encryption scheme (
E
,
D
) as follows:
hl,
E
k
1,l
(m),
E
k
2,l
(m),...,
E
k
q,l
(m)i
• Receive
BN[
F
]
: Given the key-material sk
u
= hk
w
1
,1
,k
w
2
,2
,...,k
w
`
,`
i for
any u ∈ [n] and a transmission of the form:
hi,c
1
,c
2
,...,c
q
i
it returns
D
k
w
i
,i
(c
w
i
).
Theorem 3.5. The multiuser encryption scheme
ME
BN[
F
]
satisfies the cor-
rectness property described in Definition
3.1
assuming the correctness of the
underlying encryption (
E
,
D
) i.e., for all m,k ∈M,K :
D
k
(
E
k
(m)) = m.
