Lecture 9: Public-Key Encryption and Digital Signatures

• Slides
• Playlist (length: 1:20:13)

Asymmetric Encryption

(True/False) Asymmetric encryption is the same as symmetric, except a user has two private keys instead of one

False. One key is private but the other is publically known

One-Way Functions

Is the one-time pad (with an unknown-key) a one-way function?

No. Given some y=OTP(k, x), an attacker can learn k in a single query and subsequently learn x

Public Key Encryption and Semantic Security

What is the main difference between the IND-CPA and Semantic Security games we've seen in class?

Instead of a query phase, the adversary is simply given the public key

El-Gamal Encryption Scheme

(True/False) In El-Gamal encryption, the exponent r must be random

True. It must be random because if an attacker could predict it, they could decrypt a ciphertext

El Gamal Padding

(True/False) The padding scheme presented only works if the message size is less than or equal to the number of plaintext bits

False. It’s stricly less than.

Hybrid Encryption

(True/False) Hybrid encryption works by using symmetric encryption to encrypt a message, and encrypting the symmetric key with asymmetric encryption.

True.

El Gamal Security + Asynchronous Encryption

(True/False) El Gamal is secure if the Discrete Log problem holds

False. El Gamal relies on a slightly stronger assumption described in this lecture clip (called Computational Diffie Hellman)

El Gamal Intuition

Which two cryptographic techniques/protocols is El Gamal built on?

The one-time pad and Diffie Hellman key exchange

Digital Signatures

If Verify(PK, m, Sign(SK, m)) always outputted 1, a digital signature scheme would still satisfy correctness. Which other property would fail? How?

Security would fail as it’s now trivial to find a forgery (literally anything will work)

RSA Signature Scheme

(True/False) The modulus n must be a prime number

False. By construction, N is a composite number made up of two primes

RSA Signature Scheme Security

In order for the RSA signature scheme to be secure, it is sufficient for the modulus n to be kept secret

False. n is public - the factorization of n must be kept secret.