Cryptography Reference
In-Depth Information
It, then, produces a collection of keys {k
i,j
}
(i,j)∈[q]×[`]
⊆ K which is also set
to be transmission key ek for the encryption. The user key sk
u
, for u ∈ [n],
is set to hk
w
1
,1
,k
w
2
,2
,...,k
w
`
,`
i where w
u
= hw
1
,w
2
,...,w
`
i ∈ W. The
pair (W,ik) is set to be the tracing key tk.
The following schemes are named due to their authors:
The Chor-Fiat-Naor Scheme
This scheme, as a unary scheme, is a non-trivial improvement on the ciphertext
length of the basic linear length multiuser encryption scheme. The idea is to
split the content m into ` shares m
1
,...,m
`
so that the content is the bit-wise
XOR of the m
j
's. We denote the XOR operation by ⊕ and we assume (M,⊕)
is an Abelian group, i.e., the operation ⊕ is associative, commutative, there
is an identity element, and there exists the inverse of all elements in M with
respect to ⊕. We note that these are trivially satisfied in case M = {0,1}
k
and ⊕ stands for the bit-wise exclusive-or operation.
The encryption procedure will be applied to each share m
j
, for j = 1,...,`,
that will be encrypted under q keys, namely k
i,j
for i = 1,...,q. More specif-
ically, we define the multiuser encryption scheme
ME
CFN[
F
]
as follows:
• Transmit
CFN[
F
]
: Given a message m and the transmission key ek =
{k
i,j
}
(i,j)∈[q]×[`]
, it selects r
1
,...,r
`
randomly as strings of the same length
with m such that m = r
1
⊕...⊕r
`
holds. The algorithm finally transmits
the encryption of the message m with ek by using a symmetric encryption
scheme (
E
,
D
) as follows:
2
4
3
5
E
k
1
(r
1
)
E
k
1
(r
2
) ...
E
k
1
(r
`
)
E
k
2
(r
1
)
E
k
2
(r
2
) ...
E
k
2
(r
`
)
.
. . .
E
k
q
(r
1
)
E
k
q
(r
2
) ...
E
k
q
(r
`
)
• Receive
CFN[
F
]
: Given the key-material sk
u
= hk
w
1
,1
,k
w
2
,2
,...,k
w
`
,`
i for
any u ∈ [n] and a transmission of the form:
2
3
c
1,1
c
1,2
... c
1,`
c
2,1
c
2,2
... c
2,`
. . . .
c
q,1
c
q,2
... c
q,`
4
5
it returns
D
k
w
1
,1
(c
w
1
,1
) ⊕
D
k
w
2
,2
(c
w
2
,2
) ...⊕
D
k
w
`
,`
(c
w
`
,`
).
We now discuss the correctnes of the above scheme:
Theorem 3.4. The multiuser encryption scheme
ME
CFN[
F
]
satisfies the cor-
rectness property described in Definition
3.1
assuming the correctness of the
underlying encryption (
E
,
D
) i.e., for all m,k ∈M,K :
D
k
(
E
k
(m)) = m.
