Cryptography Reference
In-Depth Information
(b)
In an
a-posteriori-chosen
ciphertext attack the attacker is given the target ciphertext
first, but its access to the oracle is restricted in that it is not allowed to make a query
equal to the target ciphertext.
In both cases, the adversary can make queries that do not correspond to a legitimate
ciphertext, and the answers will be accordingly (i.e., a special “failure” symbol).
Purpose of Attacks.
Again, the following is not claimed to be exhaustive:
1.
Standard
security
: the infeasibility of
obtaining information regarding the plaintext
.As
defined earlier, such information must be a function (or a randomized process) applied
to the bare plaintext and cannot depend on the encryption (or decryption) key.
2.
In contrast, the notion of
non-malleability
[64] refers to generating a string depending
on both the plaintext and the current encryption key. Specifically, one requires that it be
infeasible for an adversary, given a ciphertext, to produce a valid ciphertext for a related
plaintext. For example, given a ciphertext of a plaintext of the form 1
x
, it should be
infeasible to produce a ciphertext to the plaintext 0
x
.
With the exception of passive attacks on private-key schemes, non-malleability al-
ways implies security against attempts to obtain information on the plaintext. Secu-
rity and non-malleability are equivalent under a-posteriori-chosen ciphertext attack
(cf. [64, 16]). For a detailed discussion of the relationships among the various no-
tions of secure private-key and public-key encryptions, the reader is referred to [142]
and [16], respectively.
Some Known Constructions.
As in the basic case, the (strongly secure) private-key
encryption schemes can be constructed based on the existence of one-way functions,
whereas the (strongly secure) public-key encryption schemes are based on the existence
of trapdoor permutations.
Private-key schemes:
The private-key encryption scheme based on pseudoran-
dom functions (described earlier) is secure also against a-priori-chosen ciphertext
attacks.
3
It is easy to turn any passively secure private-key encryption scheme into a
scheme secure under (a posteriori) chosen ciphertext attacks by using a message-
authentication scheme
4
on top of the basic encryption.
Public-key schemes:
Public-key encryption schemes secure against a-priori-
chosen ciphertext attacks can be constructed assuming the existence of trap-
door permutations and utilizing non-interactive zero-knowledge proofs see
[176]. (Recall that the latter proof systems can be constructed under the former
assumption.)
3
Note that this scheme is not secure under an a-posteriori-chosen ciphertext attack: On input a ciphertext
(
r
,
x
⊕
f
s
(
r
)), we obtain
f
s
(
r
) by making the query (
r
,
y
), where
y
=
x
⊕
f
s
(
r
). (This query is answered with
x
such that
y
=
x
⊕
f
s
(
r
).)
4
See definition in Section B.2.
