Cryptography

CS 555
Week 1:
• Course Overview & What is Cryptography
• Historical Ciphers (& How to Break Them)
• Perfect Secrecy
• Computational Security

Readings: Katz and Lindell Chapter 1-2 + Appendix A.3 (background)

Spring 2021 1
Course Resources
Instructor: Jeremiah Blocki
Office Hours: Thursdays from 2-4PM

TA: Mohammad Hassan Ameri

Office Hours: TBD

Course Web Page: Slides, homeworks and schedule

[Link]

2
Technology
• Brightspace
• Syllabus (You are responsible for reading and understanding course policies)
• Recorded Lectures
• Quizzes
• Gradescope
• Submit homework assignments
• View Graded Assignments and Exams
• Piazza
• Course Discussion Board
• Announcements/Questions
• Preferred method of communication

3
Grades
• Course Participation: 5%
• Homework: 35%
• Midterm Exam: 20%
• Final Exam: 25%
• Online Quizzes: 15%

Collaboration is permitted on homework assignments, but you completely

understand your solutions and you must write the solutions entirely in your
own words.

No collaboration on quizzes/exams

4
Expected Background
• Basic Probability Theory
• Algorithms and Complexity
• Most security proofs involve reductions
• General Mathematical Maturity
• Quantifiers/Predicate Logic
• Understand what is (is not) a proper definition
• Know how to write a proof

5
Course Goals
• Understand the mathematics underlying cryptographic algorithms
and protocols
• Understand the power (and limitations) of common cryptographic
tools
• Understand the formal approach to security in modern cryptography

6
Topic 1: Course Overview &
What is Cryptography

7
What is Cryptography?
“the art of writing or solving codes” – Concise Oxford English Dictionary

8
What is Cryptography?
“the art of writing or solving codes” – Concise Oxford English Dictionary

“The study of mathematical techniques for securing

digital information, systems and distributed
computation against adversarial attacks.”
-- Intro to Modern Cryptography
Late 20th century
Art Science

9
 What is Cryptography?

• Precise Mathematical
Security Definitions
• Experience
• Specific Algorithmic
• Intuition
Assumptions
• Creativity
• Formal Security
Reductions/Proofs

10
What Does It Mean to “Secure Information”
• Confidentiality (Security/Privacy)
• Only intended recipient can see the communication

11
 What Does It Mean to “Secure Information”
• Confidentiality (Security/Privacy)
• Only intended recipient can see the communication
• Integrity (Authenticity)
• The message was actually sent by the alleged sender

I love you We need to

Alice… - Bob break up -Bob Alice
Bob 12
Two Attacker Models
• Passive Attacker (Eve)
• Attacker can eavesdrop
• Protection Requires?
• Confidentiality

• Active Attacker (Mallory)

• Has full control over communication channel
• Protection Requires?
• Confidentiality & Integrity

13
Steganography vs Cryptography
• Steganography
• Goal: Hide existence of a message
• Invisible Ink, Tattoo Underneath Hair, …

• Assumption: Method is secret

14
Steganography vs Cryptography
• Steganography
• Goal: Hide existence of a message
• Invisible Ink, Tattoo Underneath Hair, …
• Assumption: Method is secret
• Cryptography
• Goal: Hide the meaning of a message
• Depends only on secrecy of a (short) key
• Kerckhoff’s Principle: Cipher method should
not be required to be secret.

15
Symmetric Key Encryption
• What cryptography has historically been all about (Pre 1970)
• Two parties (sender and receiver) share secret key

• Sender uses key to encrypt (“scramble”) the message before

transmission
• Receiver uses the key to decrypt (“unscramble”) and recover the
original message

16
Encryption: Basic Terminology
• Plaintext
• The original message m
• Plaintext Space (Message Space)
• The set ℳ of all possible plaintext messages
′
• Example 1: ℳ = 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑘𝑘 ′ ,′ 𝑟𝑟𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑡𝑡 ′ , ′ℎ𝑜𝑜𝑜𝑜𝑜𝑜 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝
• Example 2: ℳ = 0,1 𝑛𝑛 --- all n-bit messages
• Ciphertext c ∈ 𝒞𝒞
• An encrypted (“scrambled”) message c ∈ 𝒞𝒞 (ciphertext space)
• Key/Keyspace k ∈ 𝒦𝒦

17
Private Key Encryption Syntax
• Message Space: ℳ
Typically picks k ∈ 𝒦𝒦
• Key Space: 𝒦𝒦 uniformly at random
• Three Algorithms Π = Gen, Enc, Dec
• Gen(𝑅𝑅) (Key-generation algorithm)
• Input: Random Bits R Trusted Parties (e.g., Alice and Bob)
• Output: Secret key k ∈ 𝒦𝒦 must run Gen in advance to obtain
• Enck(𝑚𝑚) (Encryption algorithm) secret k.
• Input: Secret key k ∈ 𝒦𝒦 and message m ∈ ℳ
• Output: ciphertext c
• Deck(𝑐𝑐) (Decryption algorithm)
• Input: Secret key k ∈ 𝒦𝒦 and a ciphertex c Assumption: Adversary does not get
• Output: a plaintext message m ∈ ℳ to see output of Gen

• Invariant: Deck(Enck(m))=m

18
Example: Shift Cipher
• Key Space: 𝒦𝒦={0,1,…,25}
• Message Space: ℳ={a,b,c,…,z}*
• Right Shift Operation
• RS1(a) = b
• RS1(b) = c
• ...
• RS1(z) = ?
• RSi+1(a)=RSi(b)

19
Shift Cipher
• Key Space: 𝒦𝒦={0,1,…,25}
• Message Space: ℳ={a,b,c,…,z}*
• Right Shift Operation
• RS1(a) = b
• RS1(b) = c
• ...
• RS1(z) = a
• RSi+1(a)=RSi(b)
• Enck(𝑚𝑚1 ∘ ⋯ ∘ 𝑚𝑚𝑛𝑛 ) = 𝑅𝑅𝑅𝑅𝑘𝑘 𝑚𝑚1 ∘ ⋯ ∘ 𝑅𝑅𝑅𝑅𝑘𝑘 𝑚𝑚𝑛𝑛
• Each letter in plaintext message m = 𝑚𝑚1 ∘ ⋯ ∘ 𝑚𝑚𝑛𝑛 is right shifted k times RSk
• Question: what is ciphertext space 𝒞𝒞?

20
Example: Shift Cipher (Multiple Characters)
• Key Space: 𝒦𝒦={0,1,…,25}
• Message Space: ℳ={a,b,c,…,z}*
Enck(𝑚𝑚1 ∘ ⋯ ∘ 𝑚𝑚𝑛𝑛 ) = 𝑅𝑅𝑅𝑅𝑘𝑘 𝑚𝑚1 ∘ ⋯ ∘ 𝑅𝑅𝑅𝑅𝑘𝑘 𝑚𝑚𝑛𝑛
Deck(𝑐𝑐1 ∘ ⋯ ∘ 𝑐𝑐𝑛𝑛 ) = 𝐿𝐿𝑆𝑆𝑘𝑘 𝑐𝑐1 ∘ ⋯ ∘ 𝐿𝐿𝑆𝑆𝑘𝑘 𝑐𝑐𝑛𝑛

• Note:
Deck Enck 𝑚𝑚1 ∘ ⋯ ∘ 𝑚𝑚𝑛𝑛 = 𝑚𝑚1 ∘ ⋯ ∘ 𝑚𝑚𝑛𝑛
since
𝐿𝐿𝐿𝐿𝑘𝑘 𝑅𝑅𝑅𝑅𝑘𝑘 𝑚𝑚𝑖𝑖 = 𝑚𝑚𝑖𝑖

21
Topic 2: Historical Ciphers (&
How to Break Them)

26
Cryptography History
• 2500+ years
• Ongoing battle Formalization of
• Codemakers and codebreakers Modern Crypto
(1976+)

Shannon Entropy/Perfect Secrecy

Caesar Shift Cipher (50 BC)
(~1950)
1970s

Cipher Machines (1900s)

Frequency Analysis
Public Key Crypto/RSA
27
 Who Uses Cryptography
• Traditionally: Militias
• Modern Times: Everyone!

Caesar Shift Cipher (50 BC) Revolutionary War

Modern Crypto

28
Caesar Cipher
Three shall be the number of thy shifting and the
number of thy shifting shall be three. Four shalt
thou not shift, neither shift thou two, excepting
that thou then proceed to three. Five is right
out…..

Caesar adopted the shift cipher with secret key k=3

29
Caesar Cipher (Example)

BEGINTHEATTACKNOW

EHJLQWKHDWWDFNQRZ

Caesar adopted the shift cipher with secret key k=3

30
Caesar Cipher (Example)

BEGINTHEATTACKNOW

EHJLQWKHDWWDFNQRZ

Immediate Issue: anyone who knows method can decrypt

(since k=3 is fixed)

31
Modern Application: Avoid Spoilers (ROT13)

32
Modern Application: Avoid Spoilers (ROT13)

33
Shift Cipher: Brute Force Attack
• Ciphertext: “lwxrw ztn sd ndj iwxcz xh gxvwi?”
• k=1  m = “mxysx auo te oek jxyda yi hywxj?”
• k=2  m=“nyzty bvp uf pfl kyzeb zj izxyk?”
• k=3  m=“ozauz cwq vg qgm lzafc ak jayzl?”
• k=4  m = “pabva dxr wh rhn mabgd bl kbzam?”
• k=5  m=“qbcwb eys xi sio nbche cm lcabn?”
• k=6  m=“rcdxc fzt yj tjp ocdif dn mdbco?”

34
Shift Cipher: Brute Force Attack
• Ciphertext: “lwxrw ztn sd ndj iwxcz xh gxvwi?”
•…
• k=7  m=“sdeyd gau zk ukq pdejg eo necdp?”
• k=8  m=“tefze hbv al vlr qefkh fp ofdeq?”
• k=9  m = “ufgaf icw bm wms rfgli gq pgefr?”
• k=10  m=“vghbg jdx cn xnt sghmj hr qhfgs?”
• k=11 m= “which key do you think is right?”
• k=12 m= “xijdi lfz ep zpv uijol jt sjhiu?”

35
Sufficient Key Space Principle
“Any secure encryption scheme must have a key space
that is sufficiently large to make an exhaustive search
attack infeasible.”

36
Sufficient Key Space Principle
“Any secure encryption scheme must have a key space
that is sufficiently large to make an exhaustive search
attack infeasible.”

Question 1: How big is big enough? Complicated question….

Question 2: If the key space is large is the encryption scheme

necessarily secure?

37
Substitution Cipher
• Secret key K is permutation of the alphabet
• Example:
• A B C D E F G H I J K L M N OP Q R S T U V W X Y Z
• X E U A D N B K V M R O C Q F S Y H W G L Z I J P T

• Encryption: apply permutation K to each letter in message

• TELLHIMABOUTME  GDOOKVCXEFLGCD

• Decryption: reverse the permutation

38
Substitution Cipher
• Secret key K is a permutation of the alphabet
• Example:
• A B C D E F G H I J K L M N OP Q R S T U V W X Y Z
• X E U A D N B K V M R O C Q F S Y H W G L Z I J P T

• Question: What is the size of the keyspace 𝒦𝒦?

𝒦𝒦 = 26! ≈ 288

39
40
 Frequency Analysis
• Observation 1: If e is mapped to d then every appearance of e in the plaintext results in the appearance of a
d in the ciphertext

• Observation 2: Some letters occur much more frequently in English.

• Observation 3: Texts consisting of a few sentences tend to have a distribution close to average.

Step 1: Find letter in ciphertext that occurs with

frequency > 11%. This letter is probably e…

41
Vigenère Cipher
• Generalizes Shift Cipher
• K=k1,…,kt
• EncK(m)
• Shift first letter right k1 times
• Shift second letter right k2 times
• …
• Shift tth letter right kt times
• Shift t+1st letter right k1 times
• …
• Question: Size of key-space?
• Answer: 26t (brute force may not be useful)

42
Vigenère Cipher
• Still vulnerable to frequency analysis
• Good guess: Select K=k1,…,kt to maximize number of e’s in resulting
ciphertext
• See Katz and Lindell 1.3 for even more sophisticated heuristics.

• Attack works when the initial message m is sufficiently long

• Vigenère is “perfectly secret” if the message m is at most t letters

long.

43
Conclusions
• Designing secure ciphers is hard

• Vigenère remained “unbroken” for a long time

• Complex schemes are not secure

• All historical ciphers have fallen

44
Homework 1 Released
• Due: Thursday, February 4th at 11:59 PM on Gradescope (2 weeks)

• Solutions should be typeset (preferably in Latex)

• You may collaborate with classmates, but you must write up your own
solution and you must understand this solution

• Ask clarification questions on Piazza or during office hours

45
Topic 3: Perfect Secrecy +
One-Time-Pads

46
Principles of Modern Cryptography
• Need formal definitions of “security”
If you don’t understand what you want to achieve, how can you possibly know
when (or if) you have achieved it?

• Attempt 1: Impossible/infeasible for attacker to recover secret key K

• Enck(m) = m
• Attempt 2: Impossible for attacker to recover entire plaintext from ciphertext?
• Ok to decrypt 90% of message?
• Attempt 3: Impossible for attacker to figure out any particular character of the
plaintext from the ciphertext?
• [Too Weak] Does employee make more than $100,000 per year?
• [Too Strong] Lucky guess? Prior Information? (e.g., letters always begin “Dear ….”)

47
Principles of Modern Cryptography
• Need formal definitions of “security”
If you don’t understand what you want to achieve, how can you possibly know
when (or if) you have achieved it?

• Final Attempt: Regardless of information an attacker already has, a ciphertext

should leak no additional information about the underlying plaintext.
• This is the “right” approach
• Still need to formalize mathematically

• Security definition includes goal and threat-model

48
Principles of Modern Cryptography
• Proofs of Security are critical
• Iron-clad guarantee that attacker will not succeed (relative to
definition/assumptions)
• Experience: intuition is often misleading in cryptography
• An “intuitively secure” scheme may actually be badly broken.

• Before deploying in the real world

• Consider definition/assumptions in security definition
• Does the threat model capture the attackers true abilities?

49
Perfect Secrecy Intuition
• Regardless of information an attacker already has, a
ciphertext should leak no additional information
about the underlying plaintext.

• We will formalize this intuition

• And show how to achieve it

50
Private Key Encryption Syntax
• Message Space: ℳ
Typically picks k ∈ 𝒦𝒦
• Key Space: 𝒦𝒦 uniformly at random
• Three Algorithms Π = Gen, Enc, Dec
• Gen(𝑅𝑅) (Key-generation algorithm)
• Input: Random Bits R Trusted Parties (e.g., Alice and Bob)
• Output: Secret key k ∈ 𝒦𝒦. must run Gen in advance to obtain
• Enck(𝑚𝑚) (Encryption algorithm) secret k.
• Input: Secret key k ∈ 𝒦𝒦 and message m ∈ ℳ
• Output: ciphertext c
• Deck(𝑐𝑐) (Decryption algorithm)
• Input: Secret key k ∈ 𝒦𝒦 and a ciphertex c Assumption: Adversary does not get
• Output: a plaintext message m ∈ ℳ to see output of Gen

• Invariant: Deck(Enck(m))=m

51
An Example
• Enemy knows that Caesar likes to fight in the rain and it is raining
today
Pr 𝑚𝑚 = 𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤 = 0.3
Pr 𝑚𝑚 = 𝑎𝑎𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 = 0.7
• Suppose that Caesar sends c=EncK(m) to generals and that the
attacker intercepts the ciphertext c and calculates
Pr 𝑚𝑚 = 𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤 |c=EncK(m) = 0.2
Pr 𝑚𝑚 = 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 |c=EncK(m) = 0.8

• Did the attacker learn anything useful?

52
Perfect Secrecy
Definition 1: An encryption scheme Π = Gen, Enc, Dec with message space ℳ
is perfectly secret if for every probability distribution 𝒟𝒟 over ℳ, every message
m ∈ ℳ and every ciphertext c ∈ 𝒞𝒞 for which Pr 𝐶𝐶 = 𝑐𝑐 > 0:
Pr 𝑀𝑀 = 𝑚𝑚|𝐶𝐶 = 𝑐𝑐 = Pr 𝑀𝑀 = 𝑚𝑚 .
(where 𝑀𝑀 ← 𝒟𝒟, 𝐾𝐾 = 𝐺𝐺𝐺𝐺𝐺𝐺(𝑅𝑅) and 𝐶𝐶 = EncK 𝑀𝑀 )

Definition 2: For every m, m′ ∈ ℳ and c ∈ 𝒞𝒞

Pr EncK 𝑚𝑚 = 𝑐𝑐 = Pr EncK 𝑚𝑚′ = 𝑐𝑐 .
(where the probabilities are taken over the randomness of Gen and Enc)

Lemma 2.4: The above definitions are equivalent.

53
Perfect Secrecy
Definition 1: An encryption scheme Π = Gen, Enc, Dec with message space ℳ
is perfectly secret if for every probability distribution 𝒟𝒟 over ℳ, every message
m ∈ ℳ and every ciphertext c ∈ 𝒞𝒞 for which Pr 𝐶𝐶 = 𝑐𝑐 > 0:
Pr 𝑀𝑀 = 𝑚𝑚|𝐶𝐶 = 𝑐𝑐 = Pr 𝑀𝑀 = 𝑚𝑚 .
(where 𝑀𝑀 ← 𝒟𝒟, 𝐾𝐾 = 𝐺𝐺𝐺𝐺𝐺𝐺(𝑅𝑅) and 𝐶𝐶 = EncK 𝑀𝑀 )

Definition 2: For every m, m′ ∈ ℳ and c ∈ 𝒞𝒞

Pr EncK 𝑚𝑚 = 𝑐𝑐 = Pr EncK 𝑚𝑚′ = 𝑐𝑐 .
(where the probabilities are taken over the randomness of Gen and Enc)

Lemma 2.4: The above definitions are equivalent.

Definition 1 is more compelling as a security definition (attacker gains no information).
Easier to prove an encryption scheme satisfied definition 2. 54
Proof (Def 1  Def 2):
Suppose first that (Gen,Enc,Dec) does not satisfy definition 2. Then there exists m, m′ ∈ ℳ
and c ∈ 𝒞𝒞 such that
Pr EncK 𝑚𝑚 = 𝑐𝑐 ≠ Pr EncK 𝑚𝑚′ = 𝑐𝑐 (1).

We will now prove that definition 1 does not hold. Define 𝒟𝒟 such that
1
Pr[M=m]=Pr[M=mʹ]=
2
Assume for the sake of contradiction that Definition 1 were satisfied then we would have
1
Pr 𝑀𝑀 = 𝑚𝑚|𝐶𝐶 = 𝑐𝑐 = Pr 𝑀𝑀 = 𝑚𝑚 = , and
2
1
Pr 𝑀𝑀 = 𝑚𝑚′|𝐶𝐶 = 𝑐𝑐 = Pr 𝑀𝑀 = 𝑚𝑚′ =
2
which implies
𝑃𝑃𝑃𝑃 𝑀𝑀 = 𝑚𝑚|𝐶𝐶 = 𝑐𝑐 = 𝑃𝑃𝑃𝑃 𝑀𝑀 = 𝑚𝑚𝑚|𝐶𝐶 = 𝑐𝑐 (∗)
55
Proof (Def 1  Def 2):
Suppose first that (Gen,Enc,Dec) does not satisfy definition 2. Then there
exists m, m′ ∈ ℳ and c ∈ 𝒞𝒞 such that
Pr EncK 𝑚𝑚 = 𝑐𝑐 ≠ Pr EncK 𝑚𝑚′ = 𝑐𝑐 (1).

1
Define 𝒟𝒟 such that Pr[M=m]=Pr[M=mʹ]=
2

Bayes Rule (1)

Pr 𝐶𝐶 = 𝑐𝑐 |𝑀𝑀 = 𝑚𝑚 Pr[M=m]
Pr 𝑀𝑀 = 𝑚𝑚|EncK 𝑀𝑀 = 𝑐𝑐 =
Pr[C=c]
1 Pr EncK 𝑚𝑚 = 𝑐𝑐
= (2)
2 Pr[C=c]
56
Proof (Def 1  Def 2):
Suppose first that (Gen,Enc,Dec) does not satisfy definition 2. Then there
exists m, m′ ∈ ℳ and c ∈ 𝒞𝒞 such that
Pr EncK 𝑚𝑚 = 𝑐𝑐 ≠ Pr EncK 𝑚𝑚′ = 𝑐𝑐 (1).

1
Define 𝒟𝒟 such that Pr[M=m]=Pr[M=mʹ]=
2

Bayes Rule (2)

Pr 𝐶𝐶 = 𝑐𝑐 |𝑀𝑀 = 𝑚𝑚′ Pr[M=mʹ]
Pr 𝑀𝑀 = 𝑚𝑚′|EncK 𝑀𝑀 = 𝑐𝑐 =
Pr[C=c]
1 Pr EncK 𝑚𝑚′ = 𝑐𝑐
= (3)
2 Pr[C=c]
57
Proof (Def 1  Def 2):
Suppose first that (Gen,Enc,Dec) does not satisfy definition 2. Then there
exists m, m′ ∈ ℳ and c ∈ 𝒞𝒞 such that
Pr EncK 𝑚𝑚 = 𝑐𝑐 ≠ Pr EncK 𝑚𝑚′ = 𝑐𝑐 (1).

1
Define 𝒟𝒟 such that Pr[M=m]=Pr[M=mʹ]=
2

Combining equations (2) and (3), Bayes Rule implies that

1 Pr EncK 𝑚𝑚𝑚 = 𝑐𝑐
Pr 𝑀𝑀 = 𝑚𝑚′|EncK 𝑀𝑀 = 𝑐𝑐 =
2 Pr[C=c]
1 Pr EncK 𝑚𝑚 = 𝑐𝑐
≠ = Pr 𝑀𝑀 = 𝑚𝑚|EncK 𝑀𝑀 = 𝑐𝑐 (∗∗)
2 Pr[C=c]
58
Proof (Def 1  Def 2):
Thus, Bayes Rule implies that
1 Pr EncK 𝑚𝑚𝑚 = 𝑐𝑐
Pr 𝑀𝑀 = 𝑚𝑚′|EncK 𝑀𝑀 = 𝑐𝑐 =
2 Pr[C=c]
1 Pr EncK 𝑚𝑚 = 𝑐𝑐
≠ = Pr 𝑀𝑀 = 𝑚𝑚|EncK 𝑀𝑀 = 𝑐𝑐 (∗∗)
2 Pr[C=c]

We previously showed that definition 2 implies

Pr 𝑀𝑀 = 𝑚𝑚|𝐶𝐶 = 𝑐𝑐 = Pr 𝑀𝑀 = 𝑚𝑚𝑚|𝐶𝐶 = 𝑐𝑐 (∗)

Contradiction!
(Still need to prove Def 2  Def 1 --- See textbook for details)
59
 Proof (Def 2  Def 1):
Assume that Definition 2 holds then for all messages m,m’ and ciphertexts we have
Pr EncK 𝑚𝑚 = 𝑐𝑐 = Pr EncK 𝑚𝑚′ = 𝑐𝑐

Now to show that Definition 1 holds we fix any distribution D and any message m
and ciphertext c for which Pr 𝐶𝐶 = 𝑐𝑐 > 0
(when C = EncK 𝑀𝑀 for a randomly sampled message M from D)

We need to prove that Pr 𝑀𝑀 = 𝑚𝑚|𝐶𝐶 = 𝑐𝑐 = Pr 𝑀𝑀 = 𝑚𝑚

Observation 1: If Pr 𝑀𝑀 = 𝑚𝑚 = 0 then Pr 𝑀𝑀 = 𝑚𝑚|𝐶𝐶 = 𝑐𝑐 = 0 = Pr 𝑀𝑀 = 𝑚𝑚

60
 Proof (Def 2  Def 1):
We need to prove that Pr 𝑀𝑀 = 𝑚𝑚|𝐶𝐶 = 𝑐𝑐 = Pr 𝑀𝑀 = 𝑚𝑚
Observation 1: If Pr 𝑀𝑀 = 𝑚𝑚 = 0 then Pr 𝑀𝑀 = 𝑚𝑚|𝐶𝐶 = 𝑐𝑐 = 0 = Pr 𝑀𝑀 = 𝑚𝑚

Otherwise, define pc ≔ Pr 𝐶𝐶 = 𝑐𝑐 |𝑀𝑀 = 𝑚𝑚 and notice that

Pr 𝐶𝐶 = 𝑐𝑐 |𝑀𝑀 = 𝑚𝑚 = Pr EncK 𝑀𝑀 = 𝑐𝑐|𝑀𝑀 = 𝑚𝑚 = Pr EncK 𝑚𝑚 = 𝑐𝑐 (1)

For any other message m’ we have
Pr EncK 𝑚𝑚𝑚 = 𝑐𝑐 = Pr EncK 𝑚𝑚 = 𝑐𝑐 = Pr 𝐶𝐶 = 𝑐𝑐 |𝑀𝑀 = 𝑚𝑚 = pc
Def 1 Eq 1 Definition

61
Proof (Def 2  Def 1):

Pr 𝐶𝐶 = 𝑐𝑐 |𝑀𝑀 = 𝑚𝑚 Pr[𝑀𝑀 = 𝑚𝑚]

Pr 𝑀𝑀 = 𝑚𝑚|𝐶𝐶 = 𝑐𝑐 = (Bayes Theorem)
Pr[𝐶𝐶 = 𝑐𝑐]

Pr 𝐶𝐶 = 𝑐𝑐 |𝑀𝑀 = 𝑚𝑚 Pr[𝑀𝑀 = 𝑚𝑚]

=
∑𝑚𝑚′ Pr[𝑀𝑀 = 𝑚𝑚′ ]Pr[𝐶𝐶 = 𝑐𝑐|𝑀𝑀 = 𝑚𝑚𝑚]

pc Pr[𝑀𝑀 = 𝑚𝑚] Pr[𝑀𝑀 = 𝑚𝑚]

= =
∑𝑚𝑚′ Pr[𝑀𝑀 = 𝑚𝑚 ]pc ∑𝑚𝑚′ Pr[𝑀𝑀 = 𝑚𝑚′ ]
′

Pr[𝑀𝑀 = 𝑚𝑚] This is what we wanted to prove

= = Pr 𝑀𝑀 = 𝑚𝑚
1
QED 62
Another Equivalent Definition (Game)
m0, m1

c Random bit b
b’ K  Gen(.)
c = EncK(mb)

′
1
∀ Pr 𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺 𝑏𝑏 = 𝑏𝑏 =
2
63
 Another Equivalent Definition (Game)
m0, m1
𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹, 𝑙𝑙𝑙𝑙𝑙𝑙 Π = 𝐺𝐺𝐺𝐺𝐺𝐺, 𝐸𝐸𝐸𝐸𝐸𝐸, 𝐷𝐷𝐷𝐷𝐷𝐷 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑡𝑡𝑡𝑡𝑡 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠, and let A
denote an eavesdropping attacker. c Random bit b
𝐶𝐶𝐶𝐶𝐶𝐶𝐶𝐶 𝑡𝑡𝑡𝑡𝑡 𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔
b’ K = Gen(.)
𝑡𝑡𝑡𝑡𝑡 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 𝑎𝑎𝑎𝑎𝑎𝑎
𝑒𝑒𝑒𝑒𝑒𝑒
𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑎𝑎 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣 𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝐴𝐴,Π 𝑎𝑎𝑎𝑎 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 c = Enc (m )
K b
𝑒𝑒𝑒𝑒𝑒𝑒 1 if 𝑏𝑏 = 𝑏𝑏 ′ (𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑖𝑖𝑖𝑖 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐)
𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝐴𝐴,Π =�
0 otherwise(𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑖𝑖𝑖𝑖 𝑛𝑛𝑛𝑛𝑛𝑛 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐)

Π ℎ𝑎𝑎𝑎𝑎 𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 𝑖𝑖𝑖𝑖 𝑡𝑡𝑡𝑡𝑡 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑜𝑜𝑜𝑜

𝑎𝑎𝑎𝑎 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 𝑖𝑖𝑖𝑖 𝑓𝑓𝑓𝑓𝑓𝑓 𝑎𝑎𝑎𝑎𝑎𝑎 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝐴𝐴 𝑤𝑤𝑤𝑤 ℎ𝑎𝑎𝑎𝑎𝑎𝑎
𝑒𝑒𝑒𝑒𝑒𝑒
Pr 𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝐴𝐴,Π = 1 =
1
′
1
∀ Pr 2 𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺 𝑏𝑏 = 𝑏𝑏 =
2
64
 Another Equivalent Definition (Game)
m0, m1

c Random bit b
b’ K  Gen(.)
c = EncK(mb)

Suppose we have m,m’,c’ s.t. Pr[EncK(m)= c’] > Pr[EncK(m’)=c’] then the adversary
can win the game w.p > ½. How?

What else do we need to establish to prove that the definitions are equivalent?

65
One Time Pad [Vernam 1917]
Enc𝐾𝐾 𝑚𝑚 = 𝐾𝐾⨁𝑚𝑚 Dec𝐾𝐾 𝑐𝑐 = 𝐾𝐾⨁𝑐𝑐

𝐄𝐄𝐄𝐄𝐄𝐄𝐄𝐄𝐄𝐄𝐄𝐄𝐄𝐄 = 𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏⨁0011 = ???

Theorem: The one-time pad encryption scheme is perfectly secret

The following calculation holds for any c, m

Pr[EncK(m)=c] = Pr[𝐾𝐾⨁m =c] = Pr[K=c⨁m] = 1� 𝒦𝒦 .
Thus, for any m, m’, c we have
Pr[EncK(m)=c]=1� 𝒦𝒦 =Pr[EncK(m’)=c].

66
One Time Pad [Vernam 1917]
Enc𝐾𝐾 𝑚𝑚 = 𝐾𝐾⨁𝑚𝑚 Dec𝐾𝐾 𝑐𝑐 = 𝐾𝐾⨁𝑐𝑐

𝐄𝐄𝐄𝐄𝐄𝐄𝐄𝐄𝐄𝐄𝐄𝐄𝐄𝐄 = 𝟏𝟏𝟏𝟏𝟏𝟏𝟏𝟏⨁0011 = ???

67
One Time Pad

68
One Time Pad

69
Perfect Secrecy Limitations
Theorem: If (Gen,Enc,Dec) is a perfectly secret encryption
scheme then
𝒦𝒦 ≥ ℳ

70
 One Time Pad Limitations
• The key is as long as the message
• How to exchange long messages?
• Need to exchange/secure lots of one-time pads!
• OTPs can only be used once
• As the name suggests
• VENONA project (US + UK)
• Decrypt ciphertexts sent by Soviet Union which were mistakenly encrypted
with portions of the same one-time pad over several decades

𝑐𝑐⨁𝑐𝑐 ′ = 𝑚𝑚⨁𝑘𝑘 ⨁ 𝑚𝑚′ ⨁𝑘𝑘 = 𝑚𝑚⨁𝑚𝑚𝑚

71
VENONA project

72
Shannon’s Theorem
Theorem: Let (Gen,Enc,Dec) be an encryption scheme
with 𝒦𝒦 = ℳ = 𝒞𝒞 . Then the scheme is perfectly
secret if and only if:
1. Every key k ∈ 𝒦𝒦 is chosen with (equal) probability
1
� 𝒦𝒦 by the algorithm Gen, and
2. For every m ∈ ℳ and every c ∈ 𝒞𝒞 there exists a
unique key k ∈ 𝒦𝒦 such that Enck(m)=c.

73
An Important Remark on Randomness
• In our analysis we have made (and will
continue to make) a key assumption:
• We have access to true “randomness”
to generate a secret key K
Example: K = one time pad
• Independent Random Bits
• Unbiased Coin flips
• Radioactive decay?

74
 In Practice
• Hard to flip thousands/millions of coins

• Mouse-movements/keys
• Uniform bits?
• Independent bits?

• Use Randomness Extractors

• As long as input has high entropy, we can extract (almost)
uniform/independent bits
• Hot research topic in theory
75
 In Practice
• Hard to flip thousands/millions of coins

• Mouse-movements/keys

• Customized Randomness Chip?

76
Caveat: Don’t do this!
• Rand() in C stdlib.h is no good for cryptographic
applications

• Source of many real

world flaws

77
Perfect Secrecy
• What capabilities do we assume the attacker has?
• Eavesdropping (Passive Adversary)
• That’s it!
• Implicit Assumption: No ability to tamper with messages!
Remark on One-Time Pads: If attacker has the ability to tamper with the
ciphertext then s/he can easily flip the last bit of the message. How?
Answer: Flip the last bit of the intercepted ciphertext 𝑐𝑐 = 𝐾𝐾⨁𝑚𝑚 to obtain
𝑐𝑐 ′ = 𝑐𝑐⨁00 … 01
Dec𝐾𝐾 𝑐𝑐′ = 𝐾𝐾⨁𝑐𝑐 ′ = 𝐾𝐾⨁𝑐𝑐 ⨁00 … 01 = 𝑚𝑚⨁00 … 01

78
 Week 1: Topic 4:
Computational Security

81
What if we want to send a longer message?
K1,K2,K3
K1,K2,K3

Enc𝐾𝐾1 "𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴, 𝐼𝐼 𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤 𝑡𝑡𝑡𝑡𝑡𝑡𝑡 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑓𝑓𝑓𝑓𝑓𝑓 𝑦𝑦𝑦𝑦𝑦𝑦𝑦

Enc𝐾𝐾2 "𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅 𝑎𝑎𝑎𝑎𝑎𝑎 𝑟𝑟𝑟𝑟𝑟𝑟, … . "

Enc𝐾𝐾3 "𝐼𝐼 𝑎𝑎𝑎𝑎 𝑜𝑜𝑜𝑜𝑜𝑜 𝑜𝑜𝑜𝑜 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠, 𝑏𝑏𝑏𝑏𝑏𝑏 𝑡𝑡𝑡𝑡𝑡 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 𝑤𝑤𝑤𝑤𝑤𝑤 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎

83
What if we want to send many messages?
K1,K2,K3
K1,K2,K3

Enc𝐾𝐾1 "𝑊𝑊𝑊𝑊𝑊𝑊𝑊𝑊𝑊 𝑢𝑢𝑢𝑢, 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴? "

Enc𝐾𝐾2 "𝑁𝑁𝑁𝑁𝑁𝑁 𝑡𝑡𝑡𝑡𝑡𝑡 𝑚𝑚𝑚𝑚𝑚𝑚𝑚, 𝑦𝑦𝑦𝑦𝑦𝑦? "

Enc𝐾𝐾3 "𝐽𝐽𝐽𝐽𝐽𝐽𝐽𝐽 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑜𝑜𝑜𝑜𝑜𝑜𝑜

84
Can we save their relationship?
K1,K2,K3 K1,K2,K3

Enc𝐾𝐾1 "𝑊𝑊𝑊𝑊𝑊𝑊𝑊𝑊𝑊 𝑢𝑢𝑢𝑢, 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴? "

Enc𝐾𝐾2 "𝑁𝑁𝑁𝑁𝑁𝑁 𝑡𝑡𝑡𝑡𝑡𝑡 𝑚𝑚𝑚𝑚𝑚𝑚𝑚, 𝑦𝑦𝑦𝑦𝑦𝑦? "

Enc𝐾𝐾3 "𝐽𝐽𝐽𝐽𝐽𝐽𝐽𝐽 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑜𝑜𝑜𝑜𝑜𝑜𝑜

85
Perfect Secrecy vs Computational Security
• Perfect Secrecy is Information Theoretic
• Guarantee is independent of attacker resources

• Computational Security
• Security against computationally bounded attacker
• An attacker with infinite resources might break security
• Attacker might succeed with very small probability
• Example: Lucky guess reveals secret key
• Very Small Probability: 2−100 , 2−1000 , …

86
Current Goal
• Define computational security in presence of eavesdropper who
intercepts a single (long) message
If you don’t understand what you want to achieve, how can you possibly know
when (or if) you have achieved it?
• Show how to build a symmetric encryption scheme with
computational security in the presence of an eavesdropper.
• Define computational security against an active attacker who might
modify the message
• Define computational security for multiple messages in presence of
an eavesdropper
87
Concrete Security
“A scheme is (t,ε)-secure if every adversary running for time
at most t succeeds in breaking the scheme with probability
at most ε”
• Example: t = 260 CPU cycles
• 9 years on a 4GHz processor
• < 1 minute on fastest supercomputer (in parallel)
• Full formal definition needs to specify “break”
• Important Metric in Practice
• Caveat 1: difficult to provide/prove such precise statements
• Caveat 2: hardware improves over time

88
Asymptotic Approach to Security
A scheme is secure if every probabilistic polynomial
time (ppt) adversary “succeeds” with negligible
probability.
• Two Key Concepts
• Polynomial time algorithm
• Negligible Function

Definition: A function 𝑓𝑓: ℕ ⟶ ℝ≥0 is negligible if for every positive

polynomial p there is an integer N>0 such that for all n > N we have
1
𝑓𝑓(𝑛𝑛) <
𝑝𝑝(𝑛𝑛)
89
Asymptotic Approach to Security
Definition: A function 𝑓𝑓: ℕ ⟶ ℝ≥0 is negligible if for every positive
polynomial 𝑝𝑝 . > 0 there is an integer N>0 such that for all n > N we
have
1
𝑓𝑓(𝑛𝑛) <
𝑝𝑝(𝑛𝑛)

Intuition: If we choose the security parameter n to be sufficiently large

then we can make the adversaries success probability very small
(negligibly small).

90
Asymptotic Approach to Security
Definition: A function 𝑓𝑓: ℕ ⟶ ℝ≥0 is negligible if for every positive polynomial p there is an integer
N>0 such that for all n > N we have
1
𝑓𝑓(𝑛𝑛) <
𝑝𝑝(𝑛𝑛)

Which functions below are negligible?

• 𝑓𝑓 𝑛𝑛 = 2−𝑛𝑛
• 𝑓𝑓 𝑛𝑛 = 𝑛𝑛−5
• 𝑓𝑓 𝑛𝑛 = 2−1000 1000𝑛𝑛1000
• 𝑓𝑓 𝑛𝑛 = 2100 2− 𝑛𝑛

• 𝑓𝑓 𝑛𝑛 = 2− log 𝑛𝑛
• 𝑓𝑓 𝑛𝑛 = 𝑛𝑛− log 𝑛𝑛

91
Asymptotic Approach to Security
Definition: A function 𝑓𝑓: ℕ ⟶ ℝ≥0 is negligible if for every positive polynomial p there is an integer
N>0 such that for all n > N we have
1
𝑓𝑓(𝑛𝑛) <
𝑝𝑝(𝑛𝑛)

Which functions below are negligible?

• 𝑓𝑓 𝑛𝑛 = 2−𝑛𝑛
• 𝑓𝑓 𝑛𝑛 = 𝑛𝑛−5
• 𝑓𝑓 𝑛𝑛 = 2−1000 1000𝑛𝑛1000
• 𝑓𝑓 𝑛𝑛 = 2100 2− 𝑛𝑛

• 𝑓𝑓 𝑛𝑛 = 2− log 𝑛𝑛
• 𝑓𝑓 𝑛𝑛 = 𝑛𝑛− log 𝑛𝑛

92
Asymptotic Approach to Security
Definition: An (randomized) algorithm A runs in polynomial time if
there exists a polynomial p(.) such that for every n-bit input x, A(x)
terminates in at most p(n) steps in expectation.

Intuition: If an algorithm A does not run in polynomial time then, for

sufficiently large n, it will quickly become impractical for any attacker to
run the algorithm A.

93
Asymptotic Approach to Security
A scheme is secure if every probabilistic polynomial
time (ppt) adversary “succeeds” with negligible
probability.

• General Attack 1: Test all possible secret keys k′ ∈ 𝒦𝒦

• Doesn’t run in polynomial time, since 𝒦𝒦 = 2𝑛𝑛
• General Attack 2: Select random key k ′ ∈ 𝒦𝒦, check if it is
correct (otherwise output ⊥ for “fail”).
• Only successful with negligible probability 2−𝑛𝑛
94
Advantages of Asymptotic Approach
• Closure
• If subroutine B runs in polynomial time and algorithm A makes poly(n) queries to the
subroutine B then A also runs in polynomial time.
• If f and g are negligible functions then h(n) = f(n)+g(n) is a negligible function
• If p(.) is a positive polynomial, and f(.) is a negligible function then the function
g(n)=f(n)p(n) is also negligible.
• Church-Turing Thesis: “reasonable” model of computations are all
polynomially equivalent.
• Implication: No need to worry about different models of computation
(circuits, random access machines, etc…)
• Disadvantage: Limited guidance on how big to make security parameter n
in practice.

95
Note: Asymptotic vs Concrete Security
• Theory of Cryptography: Often follows Asymptotic Approach
• Course Textbook (Katz-Lindell) follows the asymptotic approach
• Applied Cryptography: Concrete Security Analysis is more useful
• This Course: We will consider both approaches

96
Private Key Encryption Syntax (Revisited)
• Message Space: ℳ
• Key Space: 𝒦𝒦
• Three Algorithms
• Gen(𝟏𝟏𝒏𝒏 ; 𝑅𝑅) (Key-generation algorithm)
• Input: 1n (security parameter in unary) + Random Bits R, Trusted Parties (e.g., Alice and Bob)
• Output: Secret key k ∈ 𝒦𝒦 Requirement: all three
Typically picks algorithms
k ∈ 𝒦𝒦 run
must run Gen in advance to obtain
• Enck(𝑚𝑚; 𝑹𝑹) (Encryption algorithm) in probabilistic
uniformlypolynomial
at random time
secret k.
• Input: Secret key k ∈ 𝒦𝒦 and message m ∈ ℳ + Random Bits R,
• Output: ciphertext c
• Deck(𝑐𝑐) (Decryption algorithm)
• Input: Secret key k ∈ 𝒦𝒦 and a ciphertex c
• Output: a plaintext message m ∈ ℳ or ⊥ (𝒊𝒊. 𝒆𝒆“Fail”) Quick Comment on Notation:
K = Gen(𝟏𝟏𝒏𝒏 ; 𝑅𝑅) vs.
K ← Gen(𝟏𝟏𝒏𝒏 )
• Invariant: Deck(Enck(m))=m

97
Private Key Encryption Syntax (Revisited)
• Message Space: ℳ
• Key Space: 𝒦𝒦
• Three Algorithms
• Gen(𝟏𝟏𝒏𝒏 ; 𝑅𝑅) (Key-generation algorithm)
• Input: 1n (security parameter in unary) + Random Bits R, Trusted Parties (e.g., Alice and Bob)
• Output: Secret key k ∈ 𝒦𝒦 Requirement: all three
Typically picks algorithms
k ∈ 𝒦𝒦 run
must run Gen in advance to obtain
• Enck(𝑚𝑚; 𝑹𝑹) (Encryption algorithm) in probabilistic
uniformlypolynomial
at random time
secret k.
• Input: Secret key k ∈ 𝒦𝒦 and message m ∈ ℳ + Random Bits R,
• Output: ciphertext c
• Deck(𝑐𝑐) (Decryption algorithm)
• Input: Secret key k ∈ 𝒦𝒦 and a ciphertex c
• Output: a plaintext message m ∈ ℳ or ⊥ (𝒊𝒊. 𝒆𝒆“Fail”) Quick Comment on Notation:
K = Gen(𝟏𝟏𝒏𝒏 ; 𝑅𝑅) vs.
K ← Gen(𝟏𝟏𝒏𝒏 )
• Invariant: Deck(Enck(m))=m

98
 Adversarial Indistinguishability Experiment
m0, m1

c Random bit b
b’ K  Gen(1n)
c  EncK(mb)

𝑝𝑝𝑝𝑝𝑝𝑝 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓

′
1
∀ ∃𝜇𝜇 Pr 𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺 𝑏𝑏 = 𝑏𝑏 ≤ + 𝜇𝜇 (𝑛𝑛)
2
99
 Adversarial Indistinguishability Experiment
m0,𝑙𝑙𝑙𝑙𝑙𝑙
𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹, m1 Π = 𝐺𝐺𝐺𝐺𝐺𝐺, 𝐸𝐸𝐸𝐸𝐸𝐸, 𝐷𝐷𝐷𝐷𝐷𝐷 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑡𝑡𝑡𝑡𝑡 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠,
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 𝑡𝑡𝑡𝑡𝑡 𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔 𝑡𝑡𝑡𝑡𝑡 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 𝑎𝑎𝑎𝑎𝑎𝑎
Random bit b
c
𝑒𝑒𝑒𝑒𝑒𝑒
𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑎𝑎 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣 𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝐴𝐴,Π 1 𝑎𝑎𝑎𝑎 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓
n
b’ K = Gen(1 n)

1 = �1 if 𝑏𝑏 = 𝑏𝑏𝑏
𝑒𝑒𝑒𝑒𝑒𝑒 n
𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝐴𝐴,Π c = EncK(mb)
0 otherwise
𝑝𝑝𝑝𝑝𝑝𝑝 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 𝑖𝑖𝑖𝑖𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛
Π ℎ𝑎𝑎𝑎𝑎 𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 𝑡𝑡𝑡𝑡𝑡 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑜𝑜𝑜𝑜
𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓
𝑎𝑎𝑎𝑎 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 𝑖𝑖𝑖𝑖 𝑓𝑓𝑓𝑓𝑓𝑓 𝑎𝑎𝑎𝑎𝑎𝑎 𝑃𝑃𝑃𝑃𝑃𝑃 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝐴𝐴, 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 𝑎𝑎
negligible function 𝜇𝜇(. ) such that
𝑒𝑒𝑒𝑒𝑒𝑒
Pr[𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝐴𝐴,Π = 1] ≤ + 𝜇𝜇(𝑛𝑛)
1
1 ′
∀ Pr 𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺 𝑏𝑏 = 𝑏𝑏 ≤ + 𝜇𝜇(𝑛𝑛)
2

2
100
 EAV-Secure
m0, m1

c Random bit b
b’ K  Gen(1n)
c  EncK(mb)

𝑝𝑝𝑝𝑝𝑝𝑝 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓

′
1
∀ ∃𝜇𝜇 Pr 𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺 𝑏𝑏 = 𝑏𝑏 ≤ + 𝜇𝜇 (𝑛𝑛)
2
101
 𝑡𝑡 𝑛𝑛 , 𝜀𝜀 𝑛𝑛 -EAV-Secure (Concrete Version)
m0, m1

c Random bit b
b’ K  Gen(1n)
c = EncK(mb)

𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 𝑖𝑖𝑖𝑖 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡 𝑎𝑎𝑎𝑎 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 𝑡𝑡(𝑛𝑛) 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓

(same for all attackers)

′
1
∀ Pr 𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺𝐺 𝑏𝑏 = 𝑏𝑏 ≤ + 𝜀𝜀(𝑛𝑛)
2
103
Aside: Message and Ciphertext Length
• In the previous game we typically require that |m0|=|m1|. Why?

• It is impossible to support arbitrary length messages while hiding all

information about plaintext length

• Limitation: When could message length be sensitive?

• Numeric data (5 figure vs 6 figure salary)
• Database Searches: number of records returned can reveal information about
the query
• Compressed Data: Short compressed string indicates that original plaintext
has a lot of redundancy (e.g., CRIME attack on session cookies in HTTPS)
104
Implications of Indistinguishability ith bit of message
Theorem 3.10: Let (Gen, Enc, Dec) be a fixed-length private key
encryption scheme for message of length ℓ that satisfies
indistinguishability (prior definition) then for all PPT attackers A and
any i ≤ ℓ we have
𝑛𝑛 𝑖𝑖
1
Pr 𝐴𝐴 1 , Enc𝐾𝐾 𝑚𝑚 = 𝑚𝑚 ≤ + negl(𝑛𝑛)
2
Where the randomness is taken over K ← Gen 1𝑛𝑛 , uniform m ∈
0,1 ℓ and the randomness of Enc and A.

Remark: A bit weaker than saying eavesdropping attacker obtains ``no

additional” information about message m.
105
 Semantic Security
Definition 3.12: Let Π = Gen, Enc, Dec be a fixed-length private key encryption
scheme for message of length ℓ. We say that the scheme is semantically secure
if for all PPT attackers A there exists a PPT algorithm A’ such that for any PPT
algorithm Sample all any polynomial time computable functions f and h we have
|Pr 𝐴𝐴 1𝑛𝑛 , Enc𝐾𝐾 𝑚𝑚 , ℎ(𝑚𝑚) = 𝑓𝑓(𝑚𝑚)

106
 A’ doesn’t even get to see an
Example:
Semantic
h(m) Security
background
f(m)might
knowledge the
= 1 ifhave
m > about
100,000;
encryption of m! Just the length
attacker m. of m!
f(m) = 0 otherwise .
Definition 3.12: Let Π = Gen, Enc, Dec be a fixed-length private key encryption
scheme for message of length ℓ. We say that the scheme is semantically secure
if for all PPT attackers A there exists a PPT algorithm A’ such that for any PPT
algorithm Sample all any polynomial time computable functions f and h we have
|Pr 𝐴𝐴 1𝑛𝑛 , Enc𝐾𝐾 𝑚𝑚 , ℎ(𝑚𝑚) = 𝑓𝑓(𝑚𝑚)

107
 Semantic Security
Definition 3.12: Let Π = Gen, Enc, Dec be a fixed-length private key encryption
scheme for message of length ℓ. We say that the scheme is semantically secure if for
all PPT attackers A there exists a PPT algorithm A’ such that for any PPT algorithm
Sample all any polynomial time computable functions f and h we have
|Pr 𝐴𝐴 1𝑛𝑛 , Enc𝐾𝐾 𝑚𝑚 , ℎ(𝑚𝑚) = 𝑓𝑓(𝑚𝑚)

108
 Another Interpretation of Semantic Security
• World 2: Perfect Secrecy (Attacker doesn’t even see ciphertext).
• For all attackers A’ (even unbounded) with background knowledge h(m) we have
Pr 𝐴𝐴𝐴 1𝑛𝑛 , 𝑚𝑚 , ℎ(𝑚𝑚) = 𝑓𝑓(𝑚𝑚) = Pr 𝑓𝑓(𝑚𝑚)| ℎ 𝑚𝑚 , 𝑚𝑚

• World 1: Attacker is PPT and sees ciphertext

• Best World 1 attacker does no better than World 2 attacker
• Pr 𝐴𝐴 1𝑛𝑛 , Enc𝐾𝐾 𝑚𝑚 , ℎ(𝑚𝑚) = 𝑓𝑓(𝑚𝑚) − Pr 𝐴𝐴𝐴 1𝑛𝑛 , 𝑚𝑚 , ℎ(𝑚𝑚) = 𝑓𝑓(𝑚𝑚) ≤
negl(𝑛𝑛)

• What is probability over?

109