Cryptography Reference
In-Depth Information
multiuser encryption scheme. Let htk,ek,sk
1
,...,sk
n
i be distributed ac-
cording to KeyDist
F
which employs a q-ary fingerprinting code. We have
tk = (W,ik) ← CodeGen
`
(1
n
), and ek = {k
i,j
}
(i,j)∈[q]×[`]
so that the pri-
vate 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
BN[
F
]
(Transmit
BN[
F
]
(ek,m),sk
u
) = m] = 1
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 ciphertext; i.e. for each j = 1,...,`
there is a i ∈ {1,2,...,q} so that decryption of
E
k
i,j
(m) is available to that
particular user with index u, which implies the the correct calculation of the
plaintext m.
It is possible to define a variation of the Boneh-Naor scheme to support
an q-ary multiuser encryption scheme where the transmission of the message
vector M = hm
1
,...,m
q
i will be computed as follows:
hl,
E
k
1,l
(m
1
),
E
k
2,l
(m
2
),...,
E
k
q,l
(m
q
)i
Another variant of the Boneh-Naor scheme can utilize stateful transmis-
sion, where a state σ ∈ States is an integer from the set {1,...,`} and is
updated as σ = (σ mod `) + 1 after each transmission. The state σ plays the
role of l in the transmission that is sampled randomly from the set {1,...,`}.
The proof of correctness and the proof of security (which we will see later
in this section) of these variants of the Boneh-Naor scheme is no essentially
different compared to the standard version.
The Kiayias-Yung Scheme
This scheme is an binary scheme that involves a q-ary fingerprinting code
F
with a length `. It is similar to the Chor-Fiat-Naor scheme but as we will see
later its tracing operation applies to a much wider class of pirate decoders. As
before we will assume that the plaintext space is endowed with an additive
group structure, i.e., we will assume that there is a binary operation ⊕ that
allows the addition of plaintexts and satisfies the usual group properties, i.e.,
it is associative, there is a neutral element (zero) and any element has an
inverse with respect to addition within the group.
• Transmit
KY [
F
]
: Given a vector input M = hm
0
,m
1
i and the encryption
key ek = {k
i,j
}
(i,j)∈[q]×[`]
, it first samples l ← {1,...,`}, b ← {0,1} and
sets the parameter s = 0 (this parameter is only used when tracing).
It, then, transmits the encryption of the message M with ek by using a
symmetric encryption scheme (
E
,
D
) as follows:
