Cryptography Reference
In-Depth Information
Note that we could have gotten rid of the randomization (in the encryp-
tion process) if we had allowed the encryption algorithm to be history-
dependent (e.g., use a counter in the role of
r
). This can be done pro-
vided that either only one party uses the key for encryption (and main-
tains a counter) or that all parties that encrypt, using the same key,
coordinate their actions (i.e., maintain a joint state (e.g., counter)).
Indeed, when using a private-key encryption scheme, a common situa-
tion is that the same key is only used for communication between two
specific parties, which update a joint counter during their communi-
cation. Furthermore, if the encryption scheme is used for fifo com-
munication between the parties and both parties can reliably maintain
the counter value, then there is no need (for the sender) to send the
counter value. (The resulting scheme is related to “stream ciphers” that
arecommonlyusedinpractice.)
We comment that the use of a counter (or any other state) in the
encryption process is not reasonable in the case of public-key encryp-
tion schemes, because it is incompatible with the canonical usage of
such schemes (i.e., allowing all parties to send encrypted messages to
the “owner of the encryption-key” without engaging in any type of fur-
ther coordination or communication). Furthermore, as discussed before,
probabilistic encryption is essential for a secure public-key encryption
scheme
even in the case of encrypting a single message
(unlike in the
case of private-key schemes). Following Goldwasser and Micali (80), we
now demonstrate the use of
probabilistic encryption
in the construction
of a public-key encryption scheme.
Public-key encryption scheme based on trapdoor permuta-
tions:
We present two constructions that employ a collection of trap-
door permutations, as defined in Definition 2.3. Let
D
i
}
i
be
such a collection, and let
b
be a corresponding hard-core predicate. The
key generation algorithm consists of selecting a permutation
f
i
along
with a corresponding trapdoor
t
, and outputting (
i, t
) as the key-pair.
To encrypt a (
single
)bit
σ
(using the encryption-key
i
), the encryp-
tion algorithm uniformly selects
r
{
f
i
:
D
i
→
∈
D
i
, and produces the ciphertext
(
f
i
(
r
)
,σ
b
(
r
)). To decrypt the ciphertext (
y, τ
) (using the decryption-
key
t
), the decryption algorithm computes
τ
⊕
b
(
f
−
1
⊕
(
y
)) (using the
i
