Cryptography Reference
In-Depth Information
primes, each congruent to 3 modulo 4). The resulting secure public-key
encryption scheme, depicted in Figure 5.3, has eciency comparable to
that of (plain) RSA. We comment that special properties of modular
squaring were only used (in Figure 5.3) to speed-up the computation
of
f
−
i
(i.e., rather than iteratively extracting modular square roots
times, we extracted the modular 2
-th root).
5.3
Beyond eavesdropping security
Our treatment so far has referred only to a “passive” attack in which
the adversary merely eavesdrops on the line over which ciphertext s
are being sent. Stronger types of attacks, culminating in the so-called
Chosen Ciphertext Attack, may be possible in various applications.
Specifically, in some settings it is feasible for the adversary to make
the sender encrypt a message of the adversary's choice, and in some
settings the adversary may even make the receiver decrypt a cipher-
text of the adversary's choice. This gives rise to
chosen plaintext attacks
and to
chosen ciphertext attacks
, respectively, which are not covered by
the security definitions considered in previous sections. In this section
we briefly discuss such “active” attacks, focusing on chosen ciphertext
attacks (of the stronger type known as “a posteriori” or “CCA2”).
Loosely speaking, in a chosen ciphertext attack, the adversary may
obtain the decryptions of ciphertext s of its choice, and is deemed suc-
cessful if it learns something regarding the plaintext that corresponds
to some different ciphertext (see (89; 19) and (67, Sec. 5.4.4)). That is,
the adversary is given oracle access to the decryption function corre-
sponding to the decryption-key in use (and, in the case of private-key
schemes, it is also given oracle access to the corresponding encryption
function). The adversary is allowed to query the decryption oracle on
any ciphertext except for the “test ciphertext ” (i.e., the very ciphertext
for which it tries to learn something about the corresponding plain-
text). It may also make queries that do not correspond to legitimate
ciphertext s, and the answer will be accordingly (i.e., a special “failure”
symbol). Furthermore, the adversary may effect the selection of the test
ciphertext (by specifying a distribution from which the corresponding
plaintext is to be drawn).
