Cryptography Reference
In-Depth Information
either 0 or 1 under a certain public key
3
then a trusted third party can compute a ciphertext
that is an encryption of the sum of all the users' votes, and then this ciphertext can be
decrypted to give the total number of votes. If the user with the private key never sees the
individual votes then they cannot determine how an individual user voted. A general survey
on homomorphic encryption that gives some references for applications is Fontaine and
Galand [
191
].
For many applications it is sufficient to consider encryption schemes that only allow
a user to compute
F
(
m
1
,...,
m
k
) for certain specific functions (for example, addition in
the voting application). In this section we focus on the case where
F
(
m
1
,
m
2
) is a group
operation.
Definition 23.3.1
Let
G
be a group (written multiplicatively). A public key encryption
scheme with message space
G
and ciphertext space
C
is said to be
homomorphic
for the
group
G
if there is some efficiently computable binary operation
on
C
such that, for all
m
1
,
m
2
∈
G
,if
c
1
is an encryption of
m
1
and
c
2
is an encryption of
m
2
(both with respect
to the same public key) then
c
1
c
2
is an encryption of
m
1
m
2
.
Exercise
23.3.2
shows that one cannot have CCA security when using homomorphic
encryption. Hence, the usual security requirement of a homomorphic encryption scheme is
that it should have IND-CPA security.
Exercise 23.3.2
Show that a homomorphic encryption scheme does not have IND-CCA
security.
Exercise 23.3.3
Let
G
=
g
where
g
is an element of order
r
in a group. Let
c
1
=
(
g
k
1
,
m
1
h
k
1
) and
c
2
=
(
g
k
2
,
m
2
h
k
2
) be classic textbook Elgamal
(
c
1
,
1
,
c
1
,
2
)
=
(
c
2
,
1
,
c
2
,
2
)
=
encryptions of
m
1
,
m
2
∈
(
c
1
,
1
c
2
,
1
,
c
1
,
2
c
2
,
2
). Show that
c
1
c
2
is an
encryption of
m
1
m
2
and hence that classic textbook Elgamal encryption is homomorphic
for the group
G
.
G
. Define
c
1
c
2
=
l
2
= {
l
. Note that
G
is a group under addition modulo 2
Exercise 23.3.4
Let
G
= F
0
,
1
}
⊕
≤
≤
2let
c
i
=
=
(
g
k
i
,
m
i
⊕
H
(
h
k
i
))
(equivalently, under exclusive-or
). For 1
i
(
c
i,
1
,
c
i,
2
)
be semi-textbook Elgamal encryptions of messages
m
i
∈
G
. Consider the operation
c
1
c
2
=
c
2
,
2
). Show that semi-textbook Elgamal is not homomorphic with
respect to this operation.
(
c
1
,
1
c
2
,
1
,
c
1
,
2
⊕
Exercise 23.3.5
A variant of Elgamal encryption that is homomorphic with respect to
addition is to encrypt
m
as (
c
1
=
g
k
,
c
2
=
g
m
h
k
). Prove that if (
c
i,
1
,
c
i,
2
) are ciphertexts
encrypting messages
m
i
for
i
m
2
.Givea
decryption algorithm for this system and explain why it is only practical when the messages
m
are small integers. Hence, show that this scheme does not strictly satisfy Definition
23.3.1
when the order of
g
is large.
4
=
1
,
2 then (
c
1
,
1
c
2
,
1
,
c
1
,
2
c
2
,
2
) encrypts
m
1
+
3
It is necessary for users to prove that their vote lies in
{
0
,
1
}
.
4
The order of
g
must be large for the scheme to have IND-CPA security.
