Cryptography Reference
In-Depth Information
•
∈{
,
}
←
Enc
: On input a public key
n
and a message
m
0
1
, choose a random
x
QR
n
and compute the ciphertext:
(
c
,
d
)
:=
Enc
(
pk
,
m
)
=
(
BW
n
(
x
),
LSB
(
x
)
⊕
m
).
•
Dec
: On input a private key
(
p
,
q
)
and a ciphertext
(
c
,
d
)
, compute the message:
BW
−
1
n
m
:=
Dec
(
sk
,(
c
,
d
))
=
LSB
(
(
c
))
⊕
d
.
The fact that
LSB
is a hard-core predicate for the Blum-Williams family entails
that it gives a pseudo-random bit generator (as we have seen when constructing the
Blum-Blum-Shub PRG) when it acts on random seeds. As happens with the 'pseudo-
random one-time pad', if an adversary is able to distinguish encrypted messages
with non-negligible advantage given the ciphertext, then a PPT algorithm
can
be constructed that calls this adversary and outputs, with non-negligible advantage,
LSB
B
for a random
x
, which is a contradiction and shows that the scheme is CPA
secure. More concretely,
(
x
)
B
takes as input a public key
n
and
BW
n
(
x
)
and calls the
adversary
A
that generates two different messages
m
0
,
m
1
∈{
0
,
1
}
. Then
B
chooses
a random bit
b
←{
0
,
1
}
and submits to
A
the ciphertext
(
BW
n
(
x
),
g
⊕
m
b
)
, where
outputs a bit
b
and
g
is another randomly chosen bit.
A
B
guesses that
LSB
(
x
)
=
g
b
. Thus
b
,
precisely when
A
is successful, i.e., when
b
=
B
outputs
g
⊕
b
⊕
b
and the complement of
g
otherwise. The advantage of
this algorithm is the same as that of
i.e., it outputs
g
if
b
=
A
B
which is non-negligible by hypothesis, so
(
)
/
outputs
LSB
2, giving the required
contradiction. This is the idea of how to prove that the scheme is CPA secure and we
refer to [109, Theorem 10.28] for a detailed proof.
This scheme encrypts one bit at a time and hence is very inefficient for prac-
tical use. Moreover, the scheme is not CCA secure either. Indeed, given the chal-
lenge ciphertext
x
with probability non-negligibly greater than 1
whose corresponding unknown plaintext
m
is to be found, the
adversary submits to the decryption oracle the ciphertext
(
c
,
d
)
d
)
, where
d
=
1.
This ciphertext is distinct from the challenge ciphertext and the oracle returns the
corresponding plaintext
m
. Then the adversary knows that
c
(
c
,
d
⊕
=
BW
n
(
x
)
, where
d
=
m
. This reveals the least significant bit of
x
because then
LSB
LSB
(
x
)
⊕
(
x
)
=
m
⊕
d
and hence
m
is obtained as
m
m
⊕
d
⊕
m
⊕
1. However,
as in the case of RSA, we are going to see that an efficient scheme can be constructed
based on the Rabin functions and enjoying IND-CCA security in the random oracle
model, again under the assumption that factoring Blum integers is hard. This scheme,
introduced in 2001, is based in the OAEP construction and will be described next.
=
LSB
(
x
)
⊕
d
=
d
=
8.4.3.1 The Boneh-Rabin Encryption Scheme Rabin-SAEP
+
The encryption scheme Rabin-SAEP
+
, where the initials SAEP stand for “simple
OAEP” was introduced by Boneh in [34] together with a simpler scheme called
Rabin-SAEP and, as starting point, requires the following ingredients:
