Cryptography Reference
In-Depth Information
E
k
1
(r
1
)
E
k
1
(r
2
) ...
E
k
1
(m
0
1
−
P
i6=l
r
i
) ...
E
k
1
(r
`
)
2
3
E
k
2
(r
1
)
E
k
2
(r
2
) ...
E
k
2
(m
0
2
−
P
i6=l
r
i
) ...
E
k
2
(r
`
)
.
4
5
.
.
.
.
.
E
k
q
(r
1
)
E
k
q
(r
2
) ...
E
k
q
(m
0
q
−
P
i6=l
r
i
) ...
E
k
q
(r
`
)
where r
1
,...,r
l−1
,r
l+1
,...,r
`
are drawn randomly from the plaintext
space, m
0
1
= ... = m
0
s
= m
1−b
and m
0
s+1
= ... = m
0
q
= m
b
. Given
that s = 0, observe that the encryption operation entirely ignores message
m
1−b
(nevertheless m
1−b
is also a valid message to transmit and receive).
The usefulness of the parameter s will become evident when tracing.
• Receive
KY [
F
]
: Given the key-material k
u
= hk
w
1
,k
w
2
,...,k
w
`
i for some
u ∈ [n] and a transmission of the form:
2
4
3
5
c
1
c
1
... c
1
c
2
c
2
... c
2
. . . .
c
q
c
q
... c
q
it returns
D
k
w
1
(c
w
1
) ⊕
D
k
w
2
(c
w
2
) ⊕...⊕
D
k
w
`
(c
`
w
`
).
Theorem 3.6. The multiuser encryption scheme
ME
KY [
F
]
satisfies the cor-
rectness property described in Definition
3.1
.
nary multiuser encryption scheme. Let htk,ek,sk
1
,...,sk
n
i be distributed
according to KeyDist
q
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 private
key for any user-index u ∈ [n] is defined as sk
u
= hk
w
1
,k
w
2
,...,k
w
`
i where
w
u
= hw
1
,w
2
,...,w
`
i∈W.
We will now prove that for any vector of input M = hm
1
,m
2
i and any
user-index u ∈ [n] it holds that
Prob[Receive
KY [
F
]
(Transmit
KY [
F
]
(ek,M),sk
u
) ∈{m
0
,m
1
}] = 1
Provided that r
1
,...,r
`
,m
1
,m
2
are all elements of m, the resulting trans-
mission would be distributed as Transmit
KY [
F
]
(ek,m) consisting of an q×`
matrix as described above. Let l ∈ {1,...,`} be the special column index
sampled for the transmission, s ∈{0,1,...,q} the switching point for m
0
to
m
1
(normally s = 0) and b ∈{0,1}. Observe that the Receive algorithm on
input sk
u
= hk
w
1
,k
w
2
,...,k
w
`
i is capable of decrypting exactly one cipher-
text from each column, i.e. for any i = 1,...,` there is a j ∈{1,2,...,q} so
that the user will obtain the values r
i
for i 6= l and the value m−
P
i6=l
r
i
where m is either m
0
or m
1
. By adding all these values the user u will obtain
m. This implies that the correctness requirement is satisfied.
