Cryptography Reference
In-Depth Information
Section 9 of [
149
]): just remove the component
e
of the ciphertext and set the encapsulated
key to be
K
kdf
(
g
1
,h
k
). An alternative KEM (with even shorter ciphertext) was proposed
by Kurosawa and Desmedt [
323
]. Their idea was to set
K
=
c
k
d
αk
for
=
kdf
(
v
) where
v
=
(
g
1
,g
2
). The security again
follows from Lemma
23.2.8
: informally, querying the decryption oracle on badly formed
(
u
1
,u
2
) gives no information about the key
K
.
α
=
H
(
u
1
,u
2
). The KEM ciphertext is therefore just (
u
1
,u
2
)
=
Exercise 23.2.10
Write down a formal description of the Cramer-Shoup KEM.
Exercise 23.2.11
Show that an adversary against the Cramer-Shoup scheme who knows
any pair (
z
1
,z
2
) such that
h
g
z
1
g
z
2
=
can decrypt valid ciphertexts.
2
Exercise
23.2.12
Suppose
an
adversary
against
the
Cramer-Shoup
scheme
knows
x
1
,x
2
,y
1
,y
2
. Show how the adversary can win the OWE-CCA security game.
Exercise 23.2.13
Suppose the checks that
u
1
,u
2
∈
G
are omitted in the Cramer-Shoup
1) is a small prime (say
l<
2
10
). Suppose
the Decrypt algorithm uses the method of Exercise
23.2.5
. Show how to determine, using
a decryption oracle,
z
1
(mod
l
) and
z
2
(mod
l
). Show that if
p
⊂ F
p
where
l
cryptosystem. Suppose
G
|
(
p
−
1 has many such small
factors
l
then one could recover the values
z
1
and
z
2
in the private key of the Cramer-Shoup
scheme.
−
Cramer and Shoup [
148
] have shown how the above cryptosystem fits into a general
framework for constructing secure encryption schemes using “universal hash proof sys-
tems”. We do not have space to present this topic.
23.3 Other encryption functionalities
There are many variants of public key encryption (such as threshold decryption, server-aided
decryption, etc.). In this section we briefly sketch two important variants: homomorphic
encryption and identity-based encryption.
23.3.1 Homomorphic encryption
Let
c
1
,...,
c
k
be ciphertexts that are encryptions under some public key of messages
m
1
,...,
m
k
. The goal of homomorphic encryption is for any user to be able to efficiently
compute a ciphertext that encrypts
F
(
m
1
,...,
m
k
) for any function
F
, given only a descrip-
tion of the function
F
and the ciphertexts
c
1
,...,
c
k
. An encryption scheme that has this
property is called
fully homomorphic
.
Homomorphic encryption schemes allow third parties to perform computations on
encrypted data. A common additional security requirement is that the resulting cipher-
texts do not reveal to a user with the private key what computation was performed (except
its result). A typical application of homomorphic encryption is voting: if users encrypt
