Lecture 5: Introduction to Cryptography

• Slides
• Playlist (length: 59:44)

Intro to Cryptography

(True/False) Cryptography only reasons about defending against known attacks

False. Cryptography mathematically models any attacker strategy and can provide guarantees against attacks we don’t even know about

(True/False) One difference between symmetric and asymmetric key cryptography is that in the former one key is held by both parties, while in the latter both parties have different keys

True.

Kerckhoff’s Principle/Security Through Obscurity

What are three reasons cryptographic schemes should be public? Which part of a cryptosystem must be kept private?

1) If your secrets are leaked, it’s a lot easier to change a key than an entire algorithm 2) Public algorithms can be tested and improved by others 3) The algorithm should be usable by different people under different threat models.

The key

Intro to Symmetric Encryption Schemes

Why do we allow the ciphertext to leak the length of the message in our definition of confidentiality?

Because requiring the length to be hidden would hinder use cases by either making it impossible to encrypt large messages or expensive to encrypt small ones.

Defining Security for Symmetric Encryption

What did our original idea of security fail to account for?

Partial information leakage

Security Games and IND-CPA

What is the adversary's goal in the IND-CPA game?

To distinguish the encryption of two messages of their choosing.

IND-CPA Examples

Is Enc(K, M) = 3*K +2*M, IND-CPA secure?

No. Similar to a previous example, encrypting a message of 0 and dividing by 3 completely reveals the key

IND-CPA Intuition

If we modify IND-CPA such that the messages sent in the challenge phase can't be queried during either of the query phases, which type of undesirable encryption scheme will now be considered IND-CPA?

Deterministic schemes

OTP

Consider a variant of IND-CPA, IND-CPA', where an attack can only make one query before submitting their challenge and no queries after. Is the OTP IND-CPA' secure?

No, the adversary can learn the secret key in one step by querying 0.