Traitor Tracing - Encryption for Digital Content - page 109

• KeyDist L : Given 1 n it produces a set of keys {k 1 ,...,k n }⊆ K, sk i is set
to be the key k i for i = 1,...,n, and sets ek = hk 1 ,...,k n i. The tracing
key tk is empty.
• Transmit L : Given a message m ∈ M and the encryption key ek =
hk 1 ,...,k n i, it transmits the encryption of the message m with ek by
employing the encryption scheme ( E , D ) as follows:

h E k 1 (m),..., E k n (m)i

• Receive L : Given the key sk i = k i for some i ∈ [n] and a transmission of
the form hc 1 ,...,c n i, it returns D k i (c i ).

Theorem 3.3. A linear length multiuser encryption scheme ME L satisfies cor-
rectness (cf. Definition 3.1 ) i.e., we assume that for all k,m ∈ K,M it holds
D k ( E k (m)) = m. It is, further, CCA-1 ε-insecure in the sense of Definition 3.2
with ε ≤ 2n·ε p where the underlying encryption scheme ( E , D ) is ε p -insecure
in the sense of Definition 2.5 .

Proof. Theorem 3.3 : Regarding correctness, for user i ∈ [n], the input of the
receive function is some c such that c ← Transmit(ek,m) as well as k i . It
follows that i-th user will be able to apply the key k i to the i-th component
of the ciphertext c to recover the plaintext m correctly always. Therefore
correctness follows easily.
The security proof is a simpler form of the proof we provided in the proof
of Theorem 2.8 . We will make the argument clear in here once more so that
it will be ready for future reference. Let us start writing the original game
Exp 0 = Exp ME A (1 n ) explicitly in Figure 3.2 :

TransmitOracle(m) ReceiveOracle(c,u)

retrieve ek; retrieve sk u ;

c ← Transmit(ek,m); return Receive(c,sk u );

return c;
Experiment Exp 0 (1 n )
(∅,{k i } i∈[n] ,k 1 ,...,k n ) ←KeyDist(1 n );
ek = {k i } i∈[n] ; sk i = k i for i = 1,...,n
aux ←A TransmitOracle(·),ReceiveOracle(·) (1 n )
m 0 ,m 1 ←M; b ←{0,1}
c = h E k 1 (m 1 ),..., E k n (m 1 )i← Transmit(ek,m 1 )
b 0 ←A(aux,m b ,c)
return 1 if and only if b = b 0

Fig. 3.2. The initial security game Exp 0 .

Experiment Exp 1 . This experiment, for v = 0,...,n, is identical to Exp 0 ,
with a slight modification in its encryption on line 4. Let an experiment of