Cryptography Reference
In-Depth Information
Consequently, an adversary who is given a ciphertext can always use the recipient's
public key (which is publicly known) and perform a brute-force attack to find the
plaintext message. If we assume a computationally unbound adversary, then this
attack is always successful (at least if we assume the plaintext message to represent
some reasonable or meaningful message).
Referring to Section 1.2.2, we must specify the adversary's capabilities and
the task he or she is required to solve in order to be successful before we can
meaningfully discuss the security properties of an asymmetric encryption system.
•
With regard to the first point (i.e., the adversary's capabilities), one usually
assumes an adversary who is polynomially bound with respect to his or her
computing power (or some other resources, such as available memory or
time).
•
With regard to the second point (i.e., the task he or she is required to solve in
order to be successful), there are several possibilities, and these possibilities
lead to different notions of security (as addressed later).
In Section 10.1, we introduced and distinguished between ciphertext-only,
known-plaintext, (adaptive) chosen-plaintext, and (adaptive) chosen-ciphertext at-
tacks. Again, ciphertext-only and known-plaintext attacks are very important and
certainly the types of attacks one wants to protect against. Because the encryption
key is public in an asymmetric encryption system, (adaptive) chosen-plaintext at-
tacks are always possible and trivial to perform (just take the public key and encrypt
arbitrary plaintext messages with it). This is not the case with (adaptive) chosen-
ciphertext attacks. Because the private key is kept secret, it may not be possible for
an adversary to decrypt a ciphertext of his or her choice (unless he or she has ac-
cess to a decryption device or oracle).
1
Consequently, protection against (adaptive)
chosen-ciphertext attacks is important for asymmetric encryption systems, and the
design of systems that are resistant against these types of attacks is an important and
timely research area.
Taking all of these considerations into account, there are several notions of
security for an asymmetric encryption system. The most commonly used notion can
be described as “semantic security against adaptive chosen-ciphertext attacks.” We
already know what an adaptive chosen-ciphertext attack is (the term was originally
introduced in [1]), so it remains to be seen what “semantic security” means. The
term
semantic security
was introduced and formalized in the context of probabilis-
tic encryption in [2] (see Section 14.3.1 for a brief overview and discussion of
1
Remember that an oracle is an efficient (i.e., PPT) algorithm that takes an arbitrary input and that is
able to generate a correct output. The algorithm itself is not known, and hence the oracle must be
considered a black box.
