Cryptography Reference
In-Depth Information
while ek is the encryption key. The algorithm also produces a membership
test for a language L. The language L encodes all possible revocation
instructions for the encryption function.
• Encrypt. It is a probabilistic algorithm that on input m ∈M, a string ψ ∈
L and ek, it outputs a ciphertext c ∈ C. We write c ← Encrypt(ek,m,ψ)
to denote that c is sampled according to the distribution of the encryptions
of the plaintext m based on the revocation instruction ψ.
• Decrypt. It is a deterministic algorithm that on input c sampled from
Encrypt(ek,m,ψ) and a user-key sk
i
∈ K where (ek,sk
1
,...,sk
n
) ←
KeyGen(1
n
), it either outputs m or fails. Note that Decrypt can also be
generalized to be a probabilistic algorithm but we will not take advantage
of this here.
A broadcast encryption scheme
BE
can be in the public or symmetric key
setting by signifying that the encryption key ek is either public or secret
respectively. In case of public encryption this would enable any party to use
the broadcast encryption to distribute content to the receiver population. A
natural generalization of the above definition (which we will not consider in
this chapter) is to accept a vector of messages M = hm
1
,...,m
s
i ∈ M
s
so
that Decrypt either outputs m
i
for some i ∈ [s] or fails. We call such scheme
an s-ary broadcast encryption.
Regarding the language of revocation instructions we will require that it
contains at least the descriptions of some subsets R ⊆ [n]. The way a certain
subset R is described by a revocation instruction varies and there can even
be many different revocation instructions resulting in the same set of revoked
users R. Depending on the scheme it might be the case that any subset of
indices R can be encoded in L or there are only some specific subsets that are
included, e.g., all subsets up to a certain size.
Next we define the correctness properties that are required from a broad-
cast encryption scheme.
Definition 2.1. Correctness. We say an s-ary broadcast encryption scheme
is correct if for any ψ ∈ L that encodes a subset R ⊆ [n] and for all M =
hm
1
,...,m
s
i∈M
s
and for any u ∈ [n] \R, it holds that
Prob[Decrypt(Encrypt(ek,M,ψ),sk
u
) ∈{m
1
,...,m
s
}] = 1
where (ek,sk
1
,...,sk
n
) is distributed according to KeyGen(1
n
). Natu-
rally one may generalize the above definition to have decryption fail with some
small probability.
The correctness definition ensures that the Decrypt algorithm does not
fail as long as the index u is not removed from the list of enabled users.
E
ciency Parameters.
The e
ciency of a broadcast encryption scheme is evaluated according to the
following parameters.
