Cryptography Reference
In-Depth Information
Exercise 24.2.21
Consider the following public key cryptosystem related to Rabin: a user's
public key is a product
N
pq
where
p
and
q
are primes congruent to 3 modulo 4. To
encrypt a message 1
<
m
<N
to the user compute and send
=
m
2
1)
2
c
1
=
c
2
=
+
(mod
N
)
and
(
m
(mod
N
)
.
Show that if
x
2
y
2
1)
2
1)
2
≡
(mod
N
) and (
x
+
≡
(
y
+
(mod
N
) then
x
≡
y
(mod
N
).
Hence, show that decryption is well-defined.
Show that this cryptosystem does not have OWE security under a passive attack.
24.3 Homomorphic encryption
Homomorphic encryption was defined in Section
23.3.1
. We first remark that the textbook
RSA scheme is homomorphic for multiplication modulo
N
:if
c
1
≡
m
1
(mod
N
) and
c
2
≡
m
2
(
m
1
m
2
)
e
(mod
N
). Indeed, this property is behind the CCA attack
on textbook RSA encryption. Padding schemes can destroy this homomorphic feature.
(mod
N
) then
c
1
c
2
≡
Exercise 24.3.1
Show that textbook Rabin encryption is not homomorphic for multiplica-
tion when using any of the redundancy schemes of Section
24.2.1
.
We now give a scheme that is homomorphic for addition, and that allows a much larger
range of values for the message compared with the scheme in Exercise
23.3.5
.
Example 24.3.2
(Paillier [
424
]) Let
N
=
pq
be a user's public key. To encrypt a message
to the user choose a random integer 1
<u<N
(note that, with overwhelming
probability,
u
∈ Z
/N
Z
m
)
∗
) and compute the ciphertext
∈
(
Z
/N
Z
N
m
)
u
N
(mod
N
2
)
.
=
+
c
(1
To decrypt compute
c
λ
(
N
)
λ
(
N
)
N
m
(mod
N
2
)
≡
1
+
and hence determine
m
(mod
N
). (This requires multiplication by
λ
(
N
)
−
1
(mod
N
)).
The homomorphic property is: if
c
1
and
c
2
are ciphertexts encrypting
m
1
and
m
2
,
respectively, then
m
2
))(
u
1
u
2
)
N
(mod
N
2
)
c
1
c
2
≡
(1
+
N
(
m
1
+
encrypts
m
1
+
m
2
(mod
N
).
Exercise 24.3.3
Verify the calculations in Example
24.3.2
.
As always, one cannot obtain CCA secure encryption using a homomorphic scheme.
Hence, one is only interested in passive attacks. To check whether or not a Paillier ciphertext
c
corresponds to a specific message
m
is precisely solving the following computational
problem.
