Cryptography Reference
In-Depth Information
user while ek is the encryption key. The tracing key tk is some auxiliary
information to be used for tracing that may be empty.
• Transmit. It is a probabilistic algorithm that given a vector of inputs
M = hm
1
,...,m
s
i∈ M
s
, it prepares an element c ∈ C. We will write the
following to denote the distribution of the output: c ← Transmit(ek,M)
• Receive. It is a deterministic algorithm that on input c sampled from
Transmit(ek,hm
1
,...,m
s
i) and a user-key sk
i
for some i ∈ [n] where
(tk,ek,sk
1
,...,sk
n
) ← KeyDist(1
n
), it either outputs m
i
for some i ∈
{1,...,s} or fails. Note that Receive can also be generalized to be a
probabilistic algorithm but we will not take advantage of this here.
We can consider a variant of the multiuser encryption scheme that is state-
ful where the algorithm Transmit is parameterized by a set of states denoted
by States. In a stateful multiuser encryption scheme, the Transmit algorithm
prepares an element c ∈ C as a function of the current state and updates the
state after each transmission. In this chapter, unless stated otherwise, we will
be discussing stateless multiuser encryption schemes.
The above determine the syntax of the algorithms that define a multiuser
encryption scheme
ME
. We expect from such a scheme to satisfy correctness
in the usual sense. In particular we require that:
Definition 3.1. Correctness. We say an s-ary multiuser encryption scheme
ME
is correct if for any n ∈ N, for any vector of messages M = hm
1
,...,m
s
i∈
M
s
and for any u ∈ [n], it holds that
Prob[Receive(Transmit(ek,M),sk
u
) ∈{m
1
,...,m
s
}] = 1
where (tk,ek,sk
1
,...,sk
n
) is distributed according to KeyDist(1
n
).
It is possible to use the multiuser encryption scheme as a key encapsu-
lation mechanism that is to transmit a cryptographic key similar to the use
of broadcast encryption schemes we discussed in the previous chapter. That
is something that enables the usage of the above scheme in a hybrid encryp-
tion mode. The figure
3.1
is the standard security game that captures the key
encapsulation we require from the multiuser encryption scheme.
Definition 3.2. We say an s-ary multiuser encryption scheme
ME
is CCA-1
ε-insecure if for any probabilistic polynomial time algorithm A, it holds that
Adv
ke
A
(1
n
) = Prob[Exp
ke
A
(1
n
) = 1] −
1
2
] ≤ ε
where the experiment Exp
kem
A
is defined as in figure
3.1
.
We note that ε in general is not supposed to be a function of n, i.e. the
security property should hold independently of the number of users present
in the recipient list. It is possible to define CPA version of the above security
