Cryptography Reference
In-Depth Information
b
(
f
−
i
(
f
i
(
r
))) =
σ
. Indistin-
guishability of encryptions can be easily proved using the fact that
b
is
a hard-core of
f
i
. We comment that the above scheme is quite waste-
ful in bandwidth; however, the paradigm underlying its construction
(i.e., applying the trapdoor permutation to a randomized version of the
plaintext rather than to the actual plaintext ) is valuable in practice.
A more ecient construction of a public-key encryption scheme, which
uses the same key-generation algorithm, follows. To encrypt an
-bit
long string
x
(using the encryption-key
i
), the encryption algorithm
uniformly selects
r
trapdoor
t
of
f
i
). Clearly, (
σ
⊕
b
(
r
))
⊕
b
(
f
−
i
(
r
))
and produces the ciphertext (
f
i
(
r
)
,x ⊕ y
). To decrypt the cipher-
text (
u, v
) (using the decryption-key
t
), the decryption algorithm first
recovers
r
=
f
−
i
(
u
) (using the trapdoor
t
of
f
i
), and then obtains
v ⊕ b
(
r
)
· b
(
f
i
(
r
))
···b
(
f
−
i
(
r
)). Note the similarity to the construction
in Theorem 3.3, and the fact that the proof can be extended to estab-
lish the computational indistinguishability of (
b
(
r
)
∈
D
i
, computes
y
←
b
(
r
)
·
b
(
f
i
(
r
))
···
b
(
f
−
1
i
(
r
))
,f
i
(
r
))
and (
r
,f
i
(
r
)), for random and independent
r ∈ D
i
and
r
∈{
0
,
1
}
···
.
Indistinguishability of encryptions follows, and thus the aforementioned
scheme is secure.
Concrete implementations of the aforementioned public-key
encryption schemes:
For the first scheme, we are going to use the
RSA scheme (112) as a trapdoor permutation (rather than using it
directly as an encryption scheme).
4
The RSA scheme has an instance-
generating algorithm that randomly selects two primes,
p
and
q
,com-
putes their product
N
=
p
·
q
, and selects at random a pair of integers
1(mod
φ
(
N
)), where
φ
(
N
)
de
=(
p
(
e, d
) such that
e
1).
(The “plain RSA” operations are raising to power
e
or
d
modulo
N
.)
We construct a public-key encryption scheme as follows: The key-
generation algorithm is identical to the instance-generator algorithm of
RSA, and the encryption-key is set to (
N,e
) (resp., the decryption-key
is set to (
N,d
)), just as in “plain RSA”. To encrypt
a single bit
σ
(using
·
d
≡
−
1)
·
(
q
−
4
Recall that RSA itself is not semantically secure, because it employs a deterministic
encryption algorithm. The scheme presented here can be viewed as a “randomized version”
of RSA.
