Cryptography Reference
In-Depth Information
Traceability of the Chor-Fiat-Naor and Boneh-Naor Schemes
Following a similar argumentation to the case of the linear length multiuser
encryption scheme, we will prove in this section that Chor-Fiat-Naor and
Boneh-Naor schemes are black box traitor tracing schemes against resettable
decoders. The tracer will query the decoder with special tracing ciphertexts
defined separately for both of the schemes. After each query the tracer resets
the adversary and continues querying new tracing ciphertexts. Resetting plays
a crucial role in the tracing strategy as the pirate decoder might be capable of
distinguishing the “abnormal” ciphertexts by observing the history of previous
transmissions.
We note that a decoder with su
cient success probability would be re-
quired to use a sequence of ` secret keys each one selected from the column of
the code. The purpose of the special tracing ciphertexts is to expose the secret
keys used and effectively reconstruct the “pirate codeword” that corresponds
to the pattern of keys that are manifested in the adversarial decoder.
We next provide the special tracing ciphertexts that will be used as queries
by the tracer for both schemes:
• Chor-Fiat-Naor Scheme: The tracer T
CFN
queries the special tracing ci-
phertext Transmit
i,
CFN[
F
]
(ek,m), for (i,j) ∈{0,1,...,q}×{1,...,`}, ran-
domizes the first i rows of the share encrypted in the j-th column. Let
r
1
,...,r
`
be the random strings of the same length with m that satisfy
m = r
1
⊕...⊕r
`
. We define Transmit
i,
CFN[
F
]
(ek,m) as:
2
3
E
k
1
(r
1
)
E
k
1
(r
2
) ...
E
k
1
(R
1
) ...
E
k
1
(r
`
)
4
5
E
k
2
(r
1
)
E
k
2
(r
2
) ...
E
k
2
(R
2
) ...
E
k
2
(r
`
)
. . . . .
E
k
i
(r
1
)
E
k
i
(r
2
) ...
E
k
i
(R
i
) ...
E
k
i
(r
`
)
E
k
i+1
(r
1
)
E
k
i+1
(r
2
) ...
E
k
i+1
(r
j
) ...
E
k
i+1
(r
`
)
.
.
(3.4)
.
.
.
.
.
E
k
q
(r
1
)
E
k
q
(r
2
) ...
E
k
q
(r
j
) ...
E
k
q
(r
`
)
where R
1
,R
2
,...,R
i
is a set of random strings of length equal to the length
of the shares r
1
,...,r
`
.
• Boneh-Naor Scheme: The tracer T
BN
queries the special tracing ciphertext
Transmit
i,j
BN[
F
]
(ek,m), for (i,j) ∈{0,1,...,q}×{1,...,`}, substitutes the
first i encryptions with random strings for each type of transmission based
on the choice of j. We define Transmit
i,j
BN[
F
]
(ek,m) as:
hj,
E
k
1
(R
1
),
E
k
2
(R
2
),...,
E
k
i
(R
i
),E
k
i+1
(m),...,
E
k
q
(m)i
(3.5)
where R
1
,R
2
,...,R
i
is a set of random strings of length similar to the
share m.
