1
Public-Key Encryption and Security Notions

Nuttapong ATTRAPADUNG and Takahiro MATSUDA

National Institute of Advanced Industrial Science and Technology (AIST), Tokyo, Japan

Public-key encryption (PKE) allows a sender to use a receiver's public key to encrypt a message under it and send it to the receiver, who possesses the corresponding secret key. There has been a tremendous amount of research on PKE since the first introduction of the concept by Diffie and Hellman (1976). One of the main goals would be to devise efficient PKE schemes that are provably secure in strong security notions using weak and reasonable computational assumptions. This chapter aims to provide some basic knowledge on PKE and its security notions and survey important results in this field.

We begin the chapter by centering around the security notion called indistinguishability against chosen-ciphertext attacks (IND-CCA), which is widely accepted as the de facto standard notion for PKE. In the first part, we study in detail the Cramer-Shoup (CS) PKE (Cramer and Shoup 1998), which is the first practical IND-CCA secure PKE under a reasonable assumption. This part may also serve as introductory material for a popular method to prove security, namely, using the game-based approach. In the second part, we provide a survey on specific and generic constructions for IND-CCA secure PKE. In the last part, we briefly cover some advanced recent research topics for PKE, such as tight security, key-dependent-message (KDM) security, and so on.

1.1. Basic definitions for PKE

1.1.1. Basic notation

For n ? , we define [n] := {1,..., n}. For a discrete finite set S, |S| denotes its size and x R S denotes choosing an element x uniformly at random from S. For strings x and y, |x| denotes the bit-length of x and x?y denotes their concatenation.

For a (probabilistic) algorithm or a function A, y R A(x) denotes assigning to y the output of A on input x, and if we need to specify a randomness r used in A, we denote y A(x; r) (in which case the computation of A is understood as deterministic on input x and r). If (·) denotes a function or an algorithm, then means that A has oracle access to (·), which upon given an input x returns (x) to A (but A cannot see the internal description/calculation of ). ? always denotes a security parameter. PPT stands for probabilistic polynomial time. A function f (?) is said to be negligible if f (?) tends to 0 faster than ?-c for any constant c > 0.

1.1.2. Public-key encryption

A PKE scheme consists of the three PPT algorithms (KG, Enc, Dec) with the following syntax:

where Dec is a deterministic algorithm, (pk, sk) is a public/secret key pair and c is a ciphertext of a plaintext m under pk. We typically allow Dec to output the special symbol ? (which is distinguished from any element of the plaintext space) indicating that c is invalid.

We say that a PKE scheme is correct if for all ? ? , (pk, sk) output by KG(1?), and m, we have Dec(sk, Enc(pk, m)) = m.

Historically, the concept of PKE was first introduced by the seminal work by Diffie and Hellman (1976), and the first feasible construction was proposed by Rivest et al. (1978) known as the RSA encryption scheme. Earlier proposed PKE systems such as RSA consider schemes with deterministic encryption algorithms (or, deterministic PKE, a.k.a. a trapdoor function [TDF]). Goldwasser and Micali (1982) were the first to treat PKE with a probabilistic encryption algorithm.

1.1.3. IND-CPA and IND-CCA security

Here, we review the two central basic security notions for PKE: indistinguishability against chosen-plaintext attacks (IND-CPA security) and IND-CCA security.

We first review their formal definitions. For a PKE scheme ? = (KG, Enc, Dec) and an adversary = (1, 2), consider the IND-CPA experiment and IND-CCA experiment as described in Figure 1.1. In both the experiments, st denotes an arbitrary internal state information passed from 1 to 2, and it is required that |m0| = |m1|. Furthermore, in the IND-CCA experiment, 2 is not allowed to submit the challenge ciphertext c* to the decryption oracle Dec(sk, ·).

DEFINITION 1.1.- We say that a PKE scheme ? is IND-CCA secure if for any PPT adversary , its IND-CCA advantage 1/2| is negligible. IND-CPA security of a PKE scheme is defined analogously using the IND-CPA experiment and IND-CPA advantage

Figure 1.1. The IND-CPA experiment (left) and the IND-CCA experiment (right) for PKE.(┼) It is required that |m0| = |m1|.(╬) 2 is disallowed to submit c* to Dec(sk, ·)

The names IND-CPA and IND-CCA, and more generally the notation combining the security goal (IND) and the attack model (CPA/CCA), were introduced by Bellare et al. (1998), and the notation has been frequently adopted for other types of security notions. IND-CPA security is the very first formal definition for PKE introduced by Goldwasser and Micali (1982). They also gave another formal definition of security for PKE called semantic security, using the notion of a simulator. (A security notion defined using a simulator is often called a simulation-based security definition.) Roughly speaking, semantic security captures the intuition that a ciphertext does not leak any partial information on the encrypted plaintext except for its length (against an adversary passively observing the ciphertext). This notion aimed at formalizing the computational variant of the security notion for an encryption scheme called perfect secrecy considered by Shannon (1949). Goldwasser and Micali (1982) showed that IND-CPA security and semantic security are equivalent. It is easy to see that IND-CPA security cannot be achieved by a PKE scheme of which the encryption algorithm is deterministic.

The notion of security against chosen-ciphertext attacks was first formalized by Naor and Yung (1990), whose definition captures the so-called IND-CCA1 security, where an adversary's decryption query after receiving the challenge ciphertext is not allowed. (This type of attack is also called a non-adaptive chosen-ciphertext attack.) Chosen-ciphertext attack that take into account an adversary's decryption queries after receiving the challenge ciphertext were first considered (Rackoff and Simon 1992). (This type of attack is called an adaptive chosen-ciphertext attack.) The formal definition of IND-CCA security we reviewed above is the one most widely used nowadays. IND-CCA security is sometimes called IND-CCA2 security to make it explicit that it takes care of adaptive chosen-ciphertext attacks.

In contrast to IND-CPA security, IND-CCA security captures security against "active" adversaries that have access to the decryption oracle. However, it might not be obvious from its definition why we should care about this security notion. The practical importance of IND-CCA security was first widely recognized by the famous attack on the PKE scheme PKCS#1v1.5 by Bleichenbacher (1998). His attack recovers a plaintext from a ciphertext by accessing an oracle that on input a ciphertext returns whether the queried ciphertext is in a valid form (according to the decryption algorithm). This attack is ineffective if a PKE scheme is IND-CCA secure. In response to Bleichenbacher's attack, PKCS#1 was updated and adopted the RSA-OAEP scheme (Bellare and Rogaway 1995) that was proven to be IND-CCA secure (in the random oracle model). Besides, IND-CCA security has been shown to imply many useful and important security notions for PKE (in terms of both practical and theoretical viewpoints), such as non-malleability (Dolev et al. 1991), as explained in the next section. Therefore, IND-CCA security is nowadays considered one of the golden standard security notions for PKE that should be achieved by ones used in practice.

1.1.4. Other basic security notions and relations

Here, we review two other basic security notions for PKE that are as basic as IND-CPA and IND-CCA security. (We do not give formal definitions, and thus interested readers are referred to the original or related papers.) We also describe some more security notions in section 1.4.

1.1.4.1. One-wayness

One-wayness is a security notion that captures the intuition that given a ciphertext c encrypting a randomly chosen plaintext m, one cannot entirely recover m. It might sound sufficiently strong as a security notion for PKE. When formalized, however, it does not guarantee that no partial information on m is leaked from c. Moreover, this security notion is not...