Instructor: Daniele Micciancio (UCSD)

Public Key Encryption

We begin by reviewing the formal definition of public key encryption. The reader is assumed to already know this material from an introductory cryptography course. But reviewing these definitions and establishing some basic relations between them is a good way to introduce a number of notational convetions, and to set the tone for the rest of this course, as this is the type of activity we will be mostly concerned with.

Cryptographic protocols and their properties will be presented with a style similar to the following definition, using a number of notational conventions that we are about to describe.

A Public Key Encryption (PKE) scheme is defined by three efficient algorithms (KeyGen,Enc,Dec) where

KeyGen(t) is a probabilistic key generation algorithm that, on input a security parameter t, outputs a pair of keys (pk,sk)

Enc(pk,msg) is a probabilistic encryption algorithm that on input a public key pk and a message msg, outputs a ciphertext ct

Dec(sk,ct) is a (typically deterministic) decryption algorithm that on input a secret key sk and ciphertext ct, outputs a message msg.

The algorithms should satisfy the following correctness condition:
Pr{ Dec(sk,Enc(pk,m)) = m | (pk,sk) ← KeyGen(t) } ≡ 1

Notation and Conventions

Unless stated otherwise, all algorithms are assumed to receive (often implicitly) as their first input a security parameter t. Probabilistic algorithms also receive as an implicit input some randomness r, which is assumed to be chosen uniformly at random from the set of all binary strings of appropriate length. When we want to explicitly refer to the randomness used by a probabilistic algorith we write P(x;r), with the randomness r separated from the regular inputs by a semicolon. The operation of sampling a value using a probabilistic algorithm is written as y ⟵ P(x), and we write y ⟵ A for the operation of sampling y uniformly at random from a set A. When P is a deterministic algorithm, we may also write y = P(x) to emphaized that y is uniquely determined by x.

Unless stated otherwise, all regular inputs to the algorithms are assumed to be bitstrings of some fixed length {0, 1}^ℓ(t) which may depend on the security parameter t. Notice that, for any fixed value of t, this turns all the algorithms defining an encryption scheme into finite functions

KeyGen: R → PK × SK
Enc: PK × M × R → C
Dec: SK × C → M

for appropriate (and implicitly defined) finite sets R (the randomness space), SK (the secret key space), PK (the public key space), M (the message space), and C (the ciphertext space). We say that an algorithm is efficient if it runs in time polynomial in the security parameter t. In particular, efficient algorithms necessarily take as inputs bitstrings of length ℓ(t)=t^O(1) polynomial in the security parameter.

We use common set builder notation to describe probability distributions, the result of running probabilistic algorithms, or events in a probability space. For example, we write {z|x ← X; y ← Y; z ← P(x, y)} or {x ← X; y ← Y : P(x, y)} for the probability distribution obtained by sampling x and y independently according to distributions X and Y, and running (a possibly probabilistic) algorithm P on (x, y). This may also be abbreviated as P(X, Y) when the meaning is clear from the context.

For any predicate P (or randomized function/algorithm taking values in {0, 1},) we write {P(x)|x ⟵ X} for the event (over the probability space defined by the randomness of X and P) that P(x) is satisfied (or P(x)=1) when x is selected according to distribution X. For any two functions f(t) and g(t) (of the security parameter t), we write f(t)≡g(t) if the absolute difference is at most |f(t)−g(t)| ≤ ε(t) for some negligible function ε(t)=t^−ω(1).

Security against chosen plaintext attack (CPA security)

There are two common formulations of security of PKE against passive (chosen plaintext) attacks.

Intistinguishability under chosen plaintext attack (IND-CPA). For any PKΕ E = (KeyGen,Enc,Dec) and adversarial algorithm A = (A0,A1) define the following experiment/event
ExpINDCPA[E,A] = { b = b' | (pk,sk) ⟵ KeyGen();
                             (msg[0], msg[1], z) ⟵ A0(pk);
                             b  ⟵ {0,1};
                             ct ⟵ Enc(pk,msg[b]);
                             b' ⟵ A1(z,ct) }
The advantage of adversary A against the scheme is defined as AdvINDCPA[A,E] = (2 Pr{ExpINDCPA[E,A]} - 1). The scheme E is IND-CPΑ secure if any efficient (probabilistic polynomial time) adversary A has negligible advantage AdvIndCPA[A,E] ≡ 0.

Informally, the above definition says that no adversary can efficiently tell the difference between the encryption of any two messages m₀, m₁. The messages are adversarially chosen to model the fact that security should hold for any message distribution. The difficulty of distinguishing between two messages (as opposed to recover a full message from a corresponding ciphertext) captures the fact that the adversary should not even be able to obtain partial information about an encrypted message without knowning the secret key.

Another common security definition employs the so-called simulation paradigm, which informally states that anything that an adversary can efficiently compute from a ciphertext, can also be computed without the ciphertext. In other words, the ciphertext does not help.

Semantic Security under chosen plaintext attack (SIM-CPA) Α public key encryption scheme E=(KeyGen,Enc,Dec) is semantically secure if for any PPT adversary A there is a PPT simulator S such that for any PPT sampling algorithm M, the probability distributions
X = { A(pk,z,c) | (pk,sk) ⟵ KeyGen(t); (msg,z) ⟵ M(pk); ct ⟵ Enc(pk,msg) }
 Y = { S(pk,z)   | (pk,sk) ⟵ KeyGen(t); (msg,z) ⟵ M(pk) }
are computationally indistinguishable, that is for any PPT predicate D (the distinguisher) we have Pr{D(X)} ≡ Pr{D(Y)}

One may consider several varians of the above definition:

Restrict the adversary A to produce a single output bit. It is easy to see that in this case X and Y are indistinguishable if and only if Pr{X}≡Pr{Y}.
Change the order of quantification to "For every adversary A and distinguisher D, there is a simulator S such that for any message distribution M, ...". This allows the simulator S to depend on the distinguisher.
Restrict A(pk,z,c)=(pk,z,c) to a dummy adversary that computes the identity function.

A natural question to ask is: what is the relation between these definitions? Are these different variants of SIM-CPA security equivalent? Are IND-CPA and SIM-CPA equivalent? Does one imply the other?

If they are not equivalent, one may also ask: which one is the "right" or "best" definition? This is not a well defined question, as it is not clear what is meant by "right" or "best". Right for what? Best for what? The answer to this question is likely to depend on our goals/application. But proving that the definitions are equivalent would certainly increase our confidence in the fact that any one of them is a good definitional choice.

SIM-CPΑ security implies IND-CPΑ security

Claim 1: If (KeyGen,Enc,Dec) is SIM-CPA secure, then it is also IND-CPA Secure.

Proof: Let (KeyGen,Enc,Dec) be a SIM-CPA secure public key encryption scheme, and let (A0,A1) be an adversary against its IND-CPA security. We need to prove that AdvINDCPA(A0,A1) ≡ 0. For any bit b ∈ {0, 1}, let

Out[b] = { (pk,sk) ⟵ KeyGen(t); 
           (m[0],m[1],z) ⟵ A0(pk); 
           c ⟵ Enc(pk,m[b])
         : A1(z,c)}

be the output of the adversary in the indistinguishability experiment for a fixed value of the bit b. We need to bound the advantage

AdvINDCPA = 2 Pr{Out[b] = b | b ⟵ {0,1} } - 1 
          = Pr{Out[1]} - Pr{Out[0]}

Define the following adversary and message distributions in the simulation experiment:

A(pk,z,c) = A1(z,c).
M0(pk) = { (m[0],m[1],z) ⟵ A0(pk): (m[0],z) }
M1(pk) = { (m[0],m[1],z) ⟵ A0(pk): (m[1],z) }

By the SIM-CPA security definition, there is a simulator S such that for any message distribution M, the distributions X,Y produced by A and S are indistinguishable. Since A and S output a single bit, this is the same as requiring Pr{X} ≡ Pr{Y}. Let X0,Y0,X1,Y1 the distributions in the SIM-CPΑ definition when the message distribution is set to M=M0 or M=M1, and notice that

X0 = Out[0]
X1 = Out[1]
Y0 = Y1

It follows that

AdvINDCPA = |Pr{Out[1]} - Pr{Out[0]}| = |Pr{X1} - Pr{X0}|
           ≤ |Pr{X1} - Pr{Y1}| + |Pr{Y1} - Pr{Y0}| + |Pr{Y0} - Pr{X0}| ≤ 2ε

qed

IND-CPΑ security implies SIM-CPΑ security

Claim 2: If (KeyGen,Enc,Dec) is IND-CPA secure, then it is also SIM-CPA Secure.

Proof: Assume (KeyGen,Enc,Dec) is IND-CPA secure, and let A be an adversary against the SIM-CPA security definition. Consider a simulator

S(pk,z) = A(pk,z,Enc(pk,0))

that simply runs the attacker A on the encryption of a fixed message m = 0. We need to show that this is a good simulator, i.e., for any message distribution M and distinguisher D, the probability distributions X,Y defined in the semantic security experiment satisfy |Pr{D(X)}-Pr{D(Y)}| ≤ ε. Consider the following IND-CPA adversary (A0,A1):

A0(pk) =  {(m,0,(z,pk)) | (m,z) ⟵ M(pk)}
 A1((z,pk),c) = D(A(pk,z,c))

It is easy to check that X = Out[0] and Y = Out[1]. So, by IND-CPA security, Pr{X} ≡ Pr{Y}.

qed

Exercises

Consider the other definitional variants of SIM-CPA security where
- A outputs only a bit, or
- The order of quantifiers is changed to ∀A.∀D.∃S.∀M..., or
- A(pk,z,c)=(pk,z,c) is fixed to the "dummy" adversary

and show that they are all equivalent to each other and to IND-CPA/SIM-CPΑ.