Cryptography Reference
In-Depth Information
Security
Here we will discuss security of the multiuser encryption schemes based on
fingerprinting codes:
Theorem 3.7. The Chor-Fiat-Naor and Kiayias-Yung multiuser encryption
schemes are CCA-1 ε-insecure in the sense of Definition
3.2
with ε ≤ 2q·ε
p
assuming the underlying encryption-decryption scheme (
E
,
D
) is ε
p
-insecure in
the sense of Definition
2.5
.
in the security proof of the linear length multiuser scheme. Here, it su
ces
to make the similar walking argument over a sequence of encryptions so that
we obtain q different experiments. More specifically, we define the experiment
Exp
1
, for v = 1,...,q, that is identical to Exp
0
with a slight modification in
its challenge transmission, and apply the similar arguments over the success
probabilities of winning these experiments. The transmission for experiment
Exp
1
is chosen as follows for each scheme:
• Chor-Fiat-Naor Scheme: The walking argument is over a single column,
without loss of generality, say the first column. In other terms, the first v
keys of the first column are over a random share while the remaining keys
encode the correct share. More specifically, the transmission challenge in
the security game (cf. Figure
3.1
) is replaced with:
2
4
3
5
E
k
1
(R
1
)
E
k
1
(r
2
) ...
E
k
1
(r
`
)
E
k
2
(R
2
)
E
k
2
(r
2
) ...
E
k
2
(r
`
)
. . .
E
k
v
(R
v
)
E
k
v
(r
2
) ...
E
k
v
(r
`
)
E
k
v+1
(r
1
)
E
k
v+1
(r
2
) ...
E
k
v+1
(r
`
)
.
.
.
.
.
E
k
q
(r
1
)
E
k
q
(r
2
) ...
E
k
q
(r
`
)
• Kiayias-Yung Scheme: Similar to the Chor-Fiat-Naor scheme the walking
argument is over a single column the one preceding the randomly selected
column l (allowing wraparound modulo `, i.e., when l = 1 then the last
column would be affected).
2
4
E
k
1
(m
0
1
−
P
i6=l
r
i
) ...
E
k
1
(r
`
)
3
5
E
k
1
(r
1
) ...
E
k
l−1
1
(R
1
)
E
k
2
(m
0
2
−
P
i6=l
r
i
) ...
E
k
2
(r
`
)
E
k
2
(r
1
) ...
E
k
l−1
2
(R
2
)
.
.
.
.
.
.
E
k
v
(m
0
v
−
P
i6=l
r
i
) ...
E
k
v
(r
`
)
E
k
v
(r
1
) ...
E
k
l−1
v
(R
v
)
v+1
(r
l−1
)
E
k
v+1
(m
0
v+1
−
P
i6=l
r
i
) ...
E
k
v+1
(r
`
)
E
k
v+1
(r
1
) ...
E
k
l−1
.
.
.
.
.
.
E
k
q
(m
0
q
−
P
i6=l
r
i
) ...
E
k
q
(r
`
)
E
k
q
(r
1
) ...
E
k
l−1
q
(r
l−1
)