The exam will cover Chapters 1 and 2 from the text. Specifically:
• Private Key Encryption
◦ Definition of a priv. Key encryption system (e.g., three algorithms, KeyGen, Enc, Dec)
◦ Definition of correctness
◦ EAV security
▪ How do we model it? Game with oracle and adversary and PrivK experiment
◦ CPAsecurity
▪ How do we model it?
▪ How does it come up in real life?
▪ What is an important requirement for CPA security? (e.g., need randomized ciphertexts)
◦ Be able to show certain given ciphers are insecure in either EAV or CPA model (or both) ▪ Note that EAV < CPA, so if something isn't EAV secure, it automatically isn't CPA
secure but the opposite is not necessarily true
◦ Know how: Shift Cipher, mono-alphabetic cipher, Vigenere cipher, and OTP all work
◦ Exhaustive search (2.2.1) – be able to do computations here to argue about “practical”
security
◦ Know that OTP is perfectly secure. Know that, to be perfectly secure, it is necessary, but
not sufficient, that the key-size is as large as the message.
◦ Know Kerchkoff's principle (Principle 3 in text)
• PRG (aka Stream Cipher)
◦ Definition and how do we prove something is or is not a PRG (distinguisher model)
◦ Be able to show certain candidate PRG's are not real PRGs
▪ Explain, derive a distinguisher, and work out the probabilities.
◦ How do you turn a PRG into an EAV secure encryption protocol?
• PRF and PRP
◦ Definition and how do we prove something is or is not a PRF
◦ Be able to show something is not a PRF
◦ How can they be used in encryption?
◦ Know Feistel Network construction (just know how one round works, and then it's copy-
paste!) See Figure 2.14.
• Modes of Operation
◦ Be able to recreate ECB and CBC and CTR modes. These will not necessarily be given to you but you may be asked to draw or describe how each work.
◦ Why is ECB insecure?
◦ Argue informally why CTR is secure?
◦ Know what happens when you flip a bit in the ciphertext of CTR mode vs. CBC mode.
◦ Why is the IV important?
• Problems/Things to look at (at a minimum!):
◦ Exercise: 2.1, 2.7 (Just argue CPA > EAV; note that CTO = EAV and ignore KPA), 2.11,
2.18 (show not PRF), 2.19 (show not PRF), 2.20, 2.35( show 4,5 are not PRFs ), 2.39 ( part
2)
◦ Example 2.1, 2.2, Section 2.9
◦ All HW problems