Intro 2

Q: What is a public-key encryption scheme?

A public-key encryption scheme E = (G,E,D) is a triple of efficient algorithms defined over (M,C).

G is a probabilistic key generation algorithm that outputs a public key pk and a secret key sk: (pk,sk) <- G()

E is a probabilistic encryption algorithm that takes pk and a message m in M and outputs a ciphertext c: c <- E(pk,m)

D is a deterministic decryption algorithm that takes sk and a ciphertext c in C and outputs either a message m in M or Reject: m <- D(sk,c)

Q: What is the correctness condition for a public-key encryption scheme?

For all messages m in M, D(sk, E(pk,m)) = m.

Q: Why might correctness be stated as holding with high probability rather than probability 1?

Some public-key schemes can have a negligible probability of decryption failure.

For schemes such as RSA, ElGamal, and many elliptic-curve schemes, correctness usually holds with probability 1.

For some lattice-based schemes, a valid ciphertext may decrypt incorrectly with negligible probability, so correctness may be stated as holding with probability 1 - epsilon, where epsilon is negligible.

Q: Why must the key generation algorithm G be probabilistic?

If G were deterministic and always produced the same key pair, then everyone running key generation would get the same public key and secret key.

So G must be probabilistic to produce fresh key pairs.

Q: Why must the encryption algorithm E be probabilistic?

If E were deterministic, an adversary given pk could compute E(pk,m0) and E(pk,m1) for chosen messages and compare them with the challenge ciphertext.

So encryption must be randomized so that the same message can encrypt to different ciphertexts.

Q: Why do message space, ciphertext space, and key space matter in public-key cryptography?

In public-key cryptography, the message space, ciphertext space, and key space may be algebraic objects rather than ordinary bitstrings.

So not every bitstring is automatically a valid message, key, or ciphertext, and sampling uniformly from these spaces may be non-trivial.

Q: Why can decryption output Reject in public-key encryption?

The ciphertext space C may contain values that do not correspond to valid encryptions.

So D(sk,c) may output a message if c is valid, or Reject if c is invalid.

Q: Define the semantic security game for public-key encryption.

1. Generate keys:    (pk,sk) <- G()

2. The adversary chooses two messages after seeing pk:    m0, m1 <- A(pk)

3. Sample a random bit:    b <- {0,1}

4. Encrypt the chosen message:    c <- E(pk,m_b)

5. The adversary receives pk and c and outputs a guess:    b_hat <- A(pk,c)

6. The adversary wins if:    b_hat = b

Advantage: Adv^SS_E(A) := |Pr[b_hat = b] - 1/2|

Q: Why does semantic security imply CPA security in the public-key setting?

In the public-key setting, the encryption algorithm is public and the encryption key pk is public.

So an adversary can perform encryptions of chosen messages by itself.

That gives the adversary CPA-like power, so semantic security implies CPA security.

Q: Show why deterministic public-key encryption is not semantically secure.

Suppose E is deterministic.

After choosing m0 and m1, the adversary receives c = E(pk,m_b).

Because pk is public, it computes E(pk,m0) and E(pk,m1).

It then compares those ciphertexts with c and learns whether b = 0 or b = 1.

So deterministic public-key encryption is not semantically secure.

Q: Why is public-key encryption usually not used for long messages?

Public-key encryption is typically much slower and less efficient than symmetric encryption, and it often causes large ciphertext expansion.

So in practice it is usually used to encrypt or encapsulate a short key, and symmetric encryption is used for the actual long message.

Q: What is hybrid encryption?

Hybrid encryption combines public-key and symmetric-key encryption.

It uses public-key cryptography to protect a short key, then uses symmetric encryption with that key to encrypt the actual message.

This gives the flexibility of public-key cryptography and the efficiency of symmetric-key cryptography.

Q: What components are used in the hybrid encryption construction?

The construction uses:

1. A trapdoor function scheme T = (G,F,I) over (X,Y)
2. A hash function H : X -> K
3. A symmetric cipher E_S = (E_S,D_S) over (K,M,C)

This produces a hybrid encryption scheme E = (G,E,D) over (M, Y x C).

Q: What is the key generation algorithm for the hybrid encryption scheme?

It is the same as the trapdoor function key generation algorithm.

Generate (pk,sk) <- G()

and use the resulting pk and sk for the hybrid scheme.

Q: Describe hybrid encryption.

To encrypt message m in M under public key pk:

1. Choose a random value:    x <- X

2. Apply the trapdoor function:    y <- F(pk,x)

3. Derive an encryption key:    k <- H(x)

4. Encrypt the message using the symmetric cipher:    c <- E_S(k,m)

5. Return the ciphertext:    (y,c)

Q: Describe hybrid decryption.

To decrypt ciphertext (y,c) using sk:

1. Invert the trapdoor function:    x <- I(sk,y)

2. Derive the encryption key:    k <- H(x)

3. Decrypt the symmetric ciphertext:    m <- D_S(k,c)

4. Return m

Q: Why is the hash function H needed in hybrid encryption?

The trapdoor-function value x lies in X, while the symmetric cipher requires a key in K.

So H maps H : X -> K

and derives a symmetric key k <- H(x).

Q: What assumptions are needed for the hybrid encryption scheme to be secure?

The hybrid scheme is secure if:

1. the trapdoor function is one-way secure, so the adversary cannot recover x from y = F(pk,x);

2. the symmetric encryption scheme is semantically secure.

The hash step H derives the symmetric key k from x.

Q: What are the main routes for attacking the hybrid encryption scheme?

An adversary could try to:

1. recover x from y by breaking the trapdoor function;

2. learn or guess the derived key k = H(x);

3. break the symmetric encryption and learn information about m from c without k.

Q: What is a Key Encapsulation Mechanism (KEM)?

A KEM is a triple of algorithms (G,E,D).

G is key generation: (pk,sk) <- G()

E is encapsulation: (k,c) <- E(pk)

where k is the symmetric key and c is the encapsulation of that key.

D is decapsulation: k <- D(sk,c)

or Reject if c is not valid.

Q: How is a KEM different from ordinary public-key encryption?

Ordinary public-key encryption takes a message m as input and encrypts it.

A KEM does not take a message as input. Instead, it generates a fresh symmetric key k and an encapsulation c: (k,c) <- E(pk)

The symmetric key can then be used by a separate symmetric encryption scheme.

Q: What is the KEM/DEM paradigm?

KEM/DEM splits hybrid encryption into two parts.

KEM: Uses public-key cryptography to generate and encapsulate a symmetric key.

DEM: Uses symmetric-key encryption to encrypt the actual data with that key.

This separates key transport from data encryption.

Q: Why are KEMs important in practice?

Practical public-key systems usually do not encrypt long messages directly.

Instead, they encapsulate a symmetric key and then use symmetric encryption for the actual data.

Q: Give the efficiency model for hybrid encryption.

Let alpha be the cost of encapsulating an n-bit key using E.

Let beta be the cost per bit of encryption using a symmetric encryption scheme.

If |m| > n, then the total cost of encrypting message m is alpha + beta * |m|

and the per-bit cost is alpha / |m| + beta

Q: Why does hybrid encryption become efficient for long messages?

The per-bit cost is alpha / |m| + beta.

As |m| grows, the term alpha / |m| becomes negligible, so the cost approaches beta, the cost of symmetric encryption per bit.

So for long messages, hybrid encryption has public-key functionality with near-symmetric efficiency.

Q: What is modular arithmetic?

Modular arithmetic is arithmetic where numbers wrap around after reaching a modulus.

Example: 9 + 6 = 15 and 15 ≡ 3 mod 12

So on a 12-hour clock, 6 hours after 9 o'clock is 3 o'clock.

Q: What does it mean for two integers to be congruent modulo m?

For modulus m >= 1, integers a and b are congruent modulo m, written a ≡ b mod m, if m divides their difference: m | (a - b).

Equivalently, there exists k in Z such that a - b = km.

Q: What is Z_n?

Z_n is the set {0,1,…,n-1}.

It represents the integers modulo n.

Numbers that are congruent modulo n are treated as the same element of Z_n.

Q: How are addition and multiplication defined in Z_n?

For a,b in Z_n:

Modular addition: a +_n b = (a + b) mod n

Modular multiplication: a x_n b = (a x b) mod n

Once the modulus is clear, the subscripts are usually dropped.

Q: Why does the representation of an element in Z_n not matter?

If two integers are congruent modulo n, they represent the same element of Z_n.

So calculations give the same result regardless of which representative is used.

For example modulo 13, 2, 15, 93, and -50 all represent the same element.

Q: Why is modular arithmetic useful in cryptography?

There are two main reasons.

1. Mathematical structure: It gives finite algebraic structures such as groups, rings, and fields, which have useful properties for cryptographic constructions.

2. Computational practicality: Computers cannot conveniently work with unbounded integers, so modular arithmetic keeps computations inside a finite range.

Q: What is closure in modular arithmetic?

Closure means that applying an operation to elements of a set gives another element of the same set.

In Z_n, if a,b are in Z_n, then both (a + b) mod n and (a * b) mod n are also in Z_n.

Q: What is number theory?

Number theory is the branch of mathematics that studies integers and arithmetic functions, including topics such as primes, divisibility, coprimality, and modular arithmetic.

Public-key cryptography relies heavily on number theory.

Q: What is a prime number?

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers.

Examples include 2, 3, 5, 7, 11, 13, …

Q: What is the Fundamental Theorem of Arithmetic?

Every integer greater than 1 can be represented uniquely as a product of prime numbers.

That is why prime numbers are the multiplicative building blocks of the integers.

Q: What does it mean for two integers to be coprime?

Integers a and b are coprime if they do not share any positive divisor other than 1.

Equivalently, gcd(a,b) = 1.

Q: Do two coprime numbers both have to be prime?

No.

Two numbers can be coprime even if neither is prime.

For example, 8 and 15 are both composite, but they are coprime because gcd(8,15) = 1.

Q: Define Euler’s totient function.

Euler’s totient function phi : N -> N maps n to the number of positive integers up to n that are coprime to n.

Formally, phi(n) := |{ k in N : 1 <= k <= n and gcd(k,n) = 1 }|

Q: What two properties of Euler’s totient function are used here?

1. If p is prime, then    phi(p) = p - 1

2. If a and b are coprime, then    phi(ab) = phi(a)phi(b)

Q: Why does hybrid encryption use a trapdoor function, a hash function, and a symmetric cipher together?

The trapdoor function protects the secret value x by publishing only y = F(pk,x).

The hash function derives a usable symmetric key k = H(x).

The symmetric cipher uses k to encrypt the actual message efficiently.

Together they give a public-key encryption scheme that is efficient for long messages.