Perfectly Secret Encryption

ENCS4320 - Applied Cryptography

Dr. Ahmed I. A. Shawahna
Electrical and Computer Engineering Department
Birzeit University
 Presentation Outline

❖ Basic Probability

❖ Perfect Secrecy

❖ The One-Time Pad

❖ Crypto Requirements

❖ Crypto Taxonomy

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 2

 Discrete Probability
❖ Suppose that 𝒰 is a finite set, e.g., 𝒰 = 0, 1 𝑛

Definition: A probability distribution over 𝒰 is a function

Pr ∶ 𝒰 → [0, 1] such that ෍ Pr 𝑢 = 1
𝑢∈𝒰

 For example, 𝒰 = 0, 1 2 = 00, 01, 10, 11 is the set of all

possible outcomes
1 1 1

0.8 0.8 0.8

0.6 0.6 0.6

Pr 𝑢

0.4 0.4 0.4

0.2 0.2 0.2

0 0 0
00 01 10 11 00 01 10 11 00 01 10 11
Pr 00 = 1/4 Pr 00 = 1/4 Pr 00 =0
Pr 01 = 1/4 Pr 01 = 1/8 Pr 01 =1
Pr 10 = 1/4 Pr 10 = 1/2 Pr 10 =0
Pr 11 = 1/4 Pr 11 = 1/8 Pr 11 =0
Uniform distribution Point distribution
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 3
 Discrete Probability
❖ A subset 𝐸 ⊆ 𝒰 is called an event, and Pr 𝐸 = σe ∈ 𝐸 Pr 𝑒
𝒰
𝐸

❖ If each outcome is equally likely, then the probability of event

𝐸 ⊆ 𝒰 is
 Pr 𝐸 = # elements in 𝐸 / # elements in 𝒰
❖ For example, suppose we flip 2 coins, then 𝒰 = ℎℎ, ℎ𝑡, 𝑡ℎ, 𝑡𝑡
 Suppose 𝐸 = “at least one tail” = ℎ𝑡, 𝑡ℎ, 𝑡𝑡
 Then, Pr 𝐸 = 3/4
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 4
 Exercise - Discrete Probability
Suppose 𝒰 = 0, 1 8 , and 𝐸 = 𝑥 ∈ 𝒰 ∣ 𝑥 = 11xx xxxx , i.e., 𝐸 ⊂ 𝒰.
With the uniform distribution over 𝒰, what is Pr 𝐸 ?

Solution:
Pr 𝐸 = Pr 1100 0000 + Pr[1100 0001] + ⋯ + Pr 1111 1111
= 26 / 28
= 1/22
= 1/4

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 5

 Discrete Probability - Complement
ത
❖ If 𝐸 is an event, the complement of 𝐸 is 𝒰 ∖ 𝐸 and denoted 𝐸;
i.e., 𝐸ത is the event that 𝐸 does not occur
 Fact: Pr 𝐸ത = 1 − Pr 𝐸
❖ Often, it’s easier to compute Pr 𝐸 = 1 − Pr 𝐸ത

❖ Again, suppose we flip 2 coins, then 𝒰 = ℎℎ, ℎ𝑡, 𝑡ℎ, 𝑡𝑡

 Suppose 𝐸 = “at least one tail” = ℎ𝑡, 𝑡ℎ, 𝑡𝑡
 Complement of 𝐸 is “no tails” = ℎℎ
❖ Then,
 Pr 𝐸 = 1 − Pr 𝐸ത = 1 − 1/4 = 3/4

❖ We make use of this trick often!

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 6

 Disjunction and Union Bound
❖ If 𝐸1 and 𝐸2 are events, then 𝐸1 ∪ 𝐸2 denotes the disjunction
of 𝐸1 and 𝐸2 ; that is, 𝐸1 ∪ 𝐸2 is the event that either 𝐸1 or 𝐸2
occurs
 By definition, Pr 𝐸1 ∪ 𝐸2 ≥ Pr 𝐸1 and Pr 𝐸1 ∪ 𝐸2 ≥ Pr 𝐸2

𝒰
𝐸1
𝐸2

❖ Union bound: For events 𝐸1 and 𝐸2 in 𝒰:

 Pr 𝐸1 ∪ 𝐸2 ≤ Pr 𝐸1 + Pr 𝐸2
 Repeated application of the union bound for any events 𝐸1 , …,
𝐸𝑘 gives Pr ∪𝑘𝑖=1 𝐸𝑖 ≤ σ𝑘𝑖=1 Pr 𝐸𝑖
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 7
 Conjunction and Independence
❖ If 𝐸1 and 𝐸2 are events, then 𝐸1 ⋂ 𝐸2 denotes their
conjunction; i.e., 𝐸1 ⋂ 𝐸2 is the event that both 𝐸1 and 𝐸2
occur
 By definition, Pr 𝐸1 ⋂ 𝐸2 ≤ Pr 𝐸1 and Pr 𝐸1 ⋂ 𝐸2 ≤ Pr 𝐸2

𝒰
𝐸1
𝐸2

❖ Events 𝐸1 and 𝐸2 are said to be independent if

 Pr 𝐸1 ⋂ 𝐸2 = Pr 𝐸1 ⋅ Pr 𝐸2

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 8

 Conditional Probability
❖ The conditional probability of 𝐸1
given 𝐸2 , denoted Pr 𝐸1 | 𝐸2 ,
represents the probability that event 𝒰
𝐸1 occurs, given that event 𝐸2 has
occurred, is defined as 𝐵 𝐶
𝐴
Pr 𝐸1 ⋂ 𝐸2
 Pr 𝐸1 | 𝐸2 ≝
Pr 𝐸2
Pr 𝐴 ∣ 𝐵 > Pr 𝐴
as long as Pr 𝐸2 ≠ 0 (If Pr 𝐸2 = 0 then
Pr 𝐴 ∣ 𝐶 = 0
Pr 𝐸1 | 𝐸2 is undefined)

❖ It follows immediately from the definition that

 Pr 𝐸1 ⋂ 𝐸2 = Pr 𝐸1 | 𝐸2 ⋅ Pr 𝐸2
 Pr 𝐸2 ⋂ 𝐸1 = Pr 𝐸2 | 𝐸1 ⋅ Pr 𝐸1
 But, Pr 𝐸1 ⋂ 𝐸2 = Pr 𝐸2 ⋂ 𝐸1 !!
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 9
 Law of Total Probability
❖ Bayes’ Theorem:
Pr 𝐸1 ⋂ 𝐸2 Pr 𝐸2 ⋂ 𝐸1 Pr 𝐸2 | 𝐸1 ⋅ Pr 𝐸1
 Pr 𝐸1 | 𝐸2 = = =
Pr 𝐸2 Pr 𝐸2 Pr 𝐸2

❖ Let 𝐸1 , …, 𝐸𝑛 be disjoint events, so that Pr 𝐸𝑖 ⋂ 𝐸𝑗 = 0 for

all 𝑖 ≠ 𝑗. That is, at most one of the 𝐸𝑖 occur. Assume
further that Pr 𝐸𝑖 > 0 for all 𝑖. Then for any event 𝐹
 Pr 𝐹 = Pr 𝐹 | 𝐸1 ⋅ Pr 𝐸1 +
𝐸1 𝒰
Pr 𝐹 | 𝐸2 ⋅ Pr 𝐸2 + 𝐸3
… +
Pr 𝐹 | 𝐸𝑛 ⋅ Pr 𝐸𝑛
𝐸2 𝐸𝑛
𝑛

= ෍ Pr 𝐹 | 𝐸𝑖 ⋅ Pr 𝐸𝑖
𝑖=1
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 10
 Random Numbers
❖ Random numbers used to generate keys
 E.g., independent, unbiased (i.e., uniform) bits for symmetric keys
❖ Random numbers used for nonces (used only-once values)
 Sometimes a sequence is OK
 But sometimes nonces must be random
❖ Random numbers also used in simulations, statistics, etc.
 Such numbers need to be “statistically” random
❖ Two distinct and not necessarily compatible requirements for a
sequence of random numbers are:
 Randomness (irreproducible)
 Unpredictability

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 11

 Random Numbers
❖ Cryptographic random numbers must be statistically
random and unpredictable
❖ Suppose server generates symmetric keys …
 Alice: KA
 Bob: KB
 Charlie: KC
 Dave: KD

❖ But Alice, Bob, and Charlie don’t like Dave

❖ Alice, Bob, and Charlie working together must not be able to
determine KD

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 12

 Random Number Generators (RNGs)

RNG

True RNG Cryptographically

Pseudorandom NG
Secure PRNG

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 13

 True Random Number Generators (TRNGs)
❖ Based on physical random processes:
 Delays between network events, hard-disk access
times, keystrokes or mouse movements made by
the users, thermal/shot noise, or radioactive decay

❖ However, high-entropy data is not necessarily

uniform. Thus, post-processing is needed to obtain
(nearly) independent and uniform key stream ki:
 Pr(ki = 0) = Pr(ki = 1) = 50%

❖ Entropy is a measure of unpredictability

❖ Output can neither be predicted nor be
reproduced
❖ True “randomness” hard to define
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 14
 Exercise - TRNGs Post-Processing
Imagine that a processor generates high-entropy data containing
a sequence of biased bits, where 1 occurs with probability p and
0 occurs with probability (1 − p). Thousands of such bits have
lots of entropy, but are not close to uniform. How can we obtain a
uniformly distributed output from the initial high-entropy pool?
Solution:
We can obtain a uniform sequence of bits by taking the original bits
in pairs: if we see a 1 followed by a 0 then we output 0, and if we
see a 0 followed by a 1 then we output 1. (If we see two 0s or two
1s in a row we output nothing, and simply move on to the next
pair.) The probability that any pair results in a 0 is p · (1 − p), which
is exactly equal to the probability that any pair results in a 1. (Note
that we do not even need to know the value of p !)

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 15

 Pseudorandom Number Generator (PRNG)
❖ Generate sequences from initial seed value
❖ Typically, output stream has good statistical properties
❖ However, output can be predicted and can be reproduced
❖ Often computed in a recursive way:
s0 = seed
si+1 = F(si, si-1, si-2 , …, si-t)

❖ Example, rand() function in the standard C library <stdlib.h>:

s0 = 12345
si+1 = (1103515245 * si + 12345) mod 231

❖ Most PRNGs have bad cryptographic properties!

 Using them in cryptographic settings can have disastrous consequences
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 16
 Cryptanalyzing a Simple PRNG
❖ Assume: Simple PRNG:
 Unknown A, B and s0 as Linear Congruential Generator
key s0 = seed
 Size of A, B and si to be si+1 = (A * si + B) mod m
100 bit

❖ Solving:
Request 300 bit of output, i.e., s1, s2 and s3
s2 = (A * s1 + B) mod m
s3 = (A * s2 + B) mod m
… directly reveals A and B. All si can be computed easily!
❖ Bad cryptographic properties due to the linearity of most PRNGs
 Bottom line: “The use of pseudo-random processes to generate
secret quantities can result in pseudo-security”
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 17
 Cryptographically Secure PRNG (CSPRNG)
❖ Special PRNG with additional property:
 Output must be unpredictable
❖ More precisely: Given n consecutive bits of output si, the
following output bits sn+1 cannot be predicted (in polynomial
time)
❖ Needed in cryptography, in particular for stream ciphers
❖ Remark: There are almost no other applications that need
unpredictability, whereas many, many (technical) systems
need PRNGs

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 18

 Random Variables
❖ A random variable X is a function 𝒳 ∶ 𝒰 → 𝒱

𝒰 𝒱
❖ Example: 00000 0
𝒰 𝒱 00001 1
00010 𝒳 2
𝒳 ∶ 0,1 5 → {0,1, 2, … , 10}
⋮ ⋮
def
𝒳 𝑥 = 𝑥0 + 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 11111 10

Pr 𝑋 = 0 = 1/32
Pr 𝑋 = 1 = 5/32
Uniform distribution on 𝒰
5
Pr 𝑋 = 2 = / 32 = 10/32 but not on 𝒱!
⋮ 2
Pr 𝑋 = 10 = 0
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 19
 Deterministic and Randomized Algorithms
Inputs Outputs
❖ Deterministic algorithm:
𝑦 ← 𝐴(𝑥)
𝑥
𝐴(𝑥)

❖ Randomized algorithm:
$ 𝐴(𝑥)
𝑦 ← 𝐴(𝑥, 𝑟) where 𝑟 ← 0,1 𝑛 𝑥
𝐴(𝑥′)
$
𝑦 ← 𝐴(𝑥′) 𝑥′

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 20

 Exercise - Probability Distribution
Consider the shift cipher, with the following distribution over ℳ:
Pr 𝑀 = "kim" = 0.5,
Pr 𝑀 = "ann" = 0.2, and
Pr 𝑀 = "boo" = 0.3
1) What is the probability that the ciphertext is "DQQ"?
2) What is the probability that "ann" was encrypted, given
that we observe ciphertext "DQQ"?

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 21

 Exercise - Probability Distribution
Solution:
1) The only way the ciphertext "DQQ“ can occur is if 𝑀 = "ann" and
𝐾 = 3, or 𝑀 = "boo" and 𝐾 = 2. By independence of 𝑀 and 𝐾, we
have
Pr 𝑀 = "ann" ⋂ 𝐾 = 3 = Pr 𝑀 = "ann" ⋅ Pr 𝐾 = 3
= 0.2 ⋅ 1/26
Similarly,

Pr 𝑀 = "boo" ⋂ 𝐾 = 2 = Pr 𝑀 = "boo" ⋅ Pr 𝐾 = 2
= 0.3 ⋅ 1/26
Therefore,

Pr 𝐶 = "DQQ" = Pr 𝑀 = "ann" ⋂ 𝐾 = 3 + Pr 𝑀 = "boo" ⋂ 𝐾 = 2

= 0.2 ⋅ 1/26 + 0.3 ⋅ 1/26 = 0.5 ⋅ 1/26 = 1/52
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 22
 Exercise - Probability Distribution
Solution:
2) Using Bayes’ Theorem, we have

Pr 𝑀 = "ann" | 𝐶 = "DQQ"
Pr 𝐶 = "DQQ" | 𝑀 = "ann" ⋅ Pr 𝑀 = "ann"
=
Pr 𝐶 = "DQQ"
Pr 𝐶 = "DQQ" | 𝑀 = "ann" ⋅ 0.2
=
1/52

Note that, Pr 𝐶 = "DQQ" | 𝑀 = "ann" = 1/26, since if 𝑀 = "ann"

then the only way 𝐶 = "DQQ" can occur is if 𝐾 = 3 (which occurs
with probability 1/26). We conclude that
(1/26) ⋅ 0.2
Pr 𝑀 = "ann" | 𝐶 = "DQQ" = = 0.4
1/52
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 23
 Symmetric Key Cryptography - Review
❖ An encryption scheme is defined by:
 The key-generation algorithm (Gen): a probabilistic algorithm that
outputs a key 𝑘, 𝑘 ∈ 𝒦, chosen according to some distribution.
𝒦 is the set of all possible keys that can be output by Gen

 The encryption algorithm (Enc): encrypt message 𝑚, 𝑚 ∈ ℳ,

using the key 𝑘
Enc ∶ 𝒦 × ℳ → 𝒞 , Enc(𝑘, 𝑚) = Enck (𝑚) = 𝑐
where, 𝒞 denote the set of all possible ciphertexts that can be
output by Enck (𝑚)

 The decryption algorithm (Dec): decrypt ciphertext 𝑐, 𝑐 ∈ 𝒞, using

the key 𝑘
Dec ∶ 𝒦 × 𝒞 → ℳ, Dec(𝑘, 𝑐) = Deck (𝑐) = 𝑚

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 24

 Presentation Outline

❖ Basic Probability

❖ Perfect Secrecy

❖ The One-Time Pad

❖ Crypto Requirements

❖ Crypto Taxonomy

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 25

 Perfectly Secret

Definition: An encryption scheme (Gen, Enc, Dec) with

message space ℳ is perfectly secret if for every probability
distribution for 𝑀, every message 𝑚 ∈ ℳ, and every
ciphertext 𝑐 ∈ 𝒞 for which Pr 𝐶 = 𝑐 > 0:
Pr 𝑀 = 𝑚 | 𝐶 = 𝑐 = Pr 𝑀 = 𝑚

❖ For an encryption scheme to be perfectly secret, the

ciphertext should have no effect on the adversary’s knowledge
regarding the actual plaintext that was sent
 In other words, the ciphertext reveals nothing about the
underlying plaintext

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 26

 Exercise - Perfectly Secret
Show that the shift cipher is not perfectly secret when used with
the message space ℳ consisting of all two-letter plaintexts

Solution:
The probability distribution over ℳ, for every message 𝑚 ∈ ℳ, is
Pr 𝑀 = 𝑚 = 1/ 26 2
Consider the message is “hi“ and the ciphertext is “XX” (i.e., 𝑚 =
"hi" and 𝑐 = "XX"). Then, clearly Pr 𝑀 = "hi" | 𝐶 = "XX" = 0, as
there is no way that “XX” can ever result from the encryption of
“hi“ (In the shift cipher, the relative shift between characters is
preserved). Therefore,
Pr 𝑀 = "hi" | 𝐶 = "XX" ≠ Pr 𝑀 = "hi"
2 # the scheme is not
0 ≠ 1/ 26
perfectly secret
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 27
 Perfectly Secret

LEMMA: An encryption scheme Σ = (Gen, Enc, Dec)

with message space ℳ is perfectly secret if and only if
Pr Enc𝐾 (𝑚) = 𝑐 = Pr Enc𝐾 (𝑚′ ) = 𝑐
for every two messages 𝑚, 𝑚′ ∈ ℳ, and every ciphertext
$
𝑐 ∈ 𝒞, with probability taken over the random choice 𝐾 ← 𝒦
and the random coins used by Enc() (if any)

❖ For an encryption scheme to be perfectly secret, the

distribution of the ciphertext must not depend on the plaintext
 In other words, the distribution of the ciphertext when 𝑚 is
encrypted should be identical to the distribution of the ciphertext
when 𝑚′ is encrypted

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 28

 Exercise

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 29

 Perfect (Adversarial) Indistinguishability

Definition: An encryption scheme

𝐄𝐱𝐩Per−Indist
Σ 𝐴
Σ = (Gen, Enc, Dec) with message
space ℳ is perfectly indistinguishable Σ = (Gen, Enc, Dec)
if for every adversary 𝐴 it holds that 𝐴: an adversary, a stateful
Per−Indist 1 algorithm
Pr 𝐄𝐱𝐩Σ, 𝐴 = 1 = Pr 𝑏′ = 𝑏 = ----------------------------------
2 𝑏
$
1. 𝑏 ← 0, 1
❖ An encryption scheme is perfectly 2. 𝑘 ← Σ. Gen()
indistinguishable if no adversary 𝐴 can 3. 𝑚0 ← 𝐴, 𝑚1 ← 𝐴
succeed with probability better than 1/2 4. 𝑐 ← Σ. Enc 𝑘, 𝑚𝑏
5. 𝑏′ ← 𝐴 𝑐
LEMMA: An encryption scheme Σ ?
is perfectly secret if and only if it is 6. 𝐫𝐞𝐭𝐮𝐫𝐧 𝑏′ = 𝑏
perfectly indistinguishable

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 30

 Exercise - Perfectly Secret
Show that the Vigenère cipher is not perfectly indistinguishable,
at least for certain parameters (e.g., for the message space of
two-letter strings and the upper bound of the period is 2)
Solution:
Let Σ denote the Vigenère cipher for the message space of two-
letter strings, and where the period is chosen uniformly in {1, 2},
and adversary 𝐴 does:
1. Output 𝑚0 = "aa" and 𝑚1 = "ab"
2. Upon receiving the challenge ciphertext c = 𝑐0 𝑐1 , do the following:
if 𝑐0 = 𝑐1 output 0; else output 1
Pr 𝐄𝐱𝐩Per−Indist
Σ, 𝐴 =1
= Pr 𝐄𝐱𝐩Per−Indist
Σ, 𝐴 = 1 | 𝑏 = 0 ⋅ Pr 𝑏 = 0
+ Pr 𝐄𝐱𝐩Per−Indist
Σ, 𝐴 = 1 | 𝑏 = 1 ⋅ Pr 𝑏 = 1
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 31
 Exercise - Perfectly Secret
Pr 𝐄𝐱𝐩Per−Indist
Σ, 𝐴 =1
= Pr 𝐴 outputs 0 | 𝑏 = 0 ⋅ 1/2 + Pr 𝐴 outputs 1 | 𝑏 = 1 ⋅ 1/2
When 𝑏 = 0 (so 𝑚0 = "aa" is encrypted) then 𝑐0 = 𝑐1 (i.e.,
𝐴 outputs 0) if either (1) a key of period 1 is chosen, or (2) a key of
period 2 is chosen and both characters of the key are equal
1 1 1 27
Pr 𝐴 outputs 0 | 𝑏 = 0 = + ⋅ ⋅1=
2 2 26 52
When 𝑏 = 1 (so 𝑚1 = "ab" is encrypted) then 𝑐0 = 𝑐1 (i.e.,
𝐴 outputs 0) only if a key of period 2 is chosen and the first character
of the key is one more than the second character of the key
1 1 51
Pr 𝐴 outputs 1 | 𝑏 = 1 = 1 − Pr 𝐴 outputs 0 | 𝑏 = 1 = 1 − ⋅ ⋅1=
2 26 52
Plugging into the main Equation, then gives
1 27 51 1 # the scheme is not
Pr 𝐄𝐱𝐩Per−Indist
Σ, 𝐴 =1 = ⋅ + = 0.75 >
2 52 52 2 perfectly indistinguishable
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 32
 Presentation Outline

❖ Basic Probability

❖ Perfect Secrecy

❖ The One-Time Pad

❖ Crypto Requirements

❖ Crypto Taxonomy

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 33

 One-Time Pad
❖ A perfectly secret encryption scheme proposed in 1917
❖ Encryption: 𝒦×ℳ →𝒞
𝐶 ←𝑀𝐾
 Enck(m1 ··· mL) = c1 ··· cL , where ci = mi  ki

❖ Decryption: 𝒦×𝒞 →ℳ
𝑀←𝐶𝐾
 Deck(c1 ··· cL) = m1 ··· mL , where mi = ci  ki

Where, ⊕ denote the bitwise exclusive-or (XOR) operation,

and Deck(Enck(m)) = k  k  m = m
𝑛 𝑛 𝑛
𝒦 = 0,1 ℳ = 0,1 𝒞 = 0,1
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 34
 One-Time Pad: Encryption

e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111

❖ Encryption: Plaintext  Key = Ciphertext

h e i l h i t l e r
Plaintext: 001 000 010 100 001 010 111 100 000 101
Key: 111 101 110 101 111 100 000 101 110 000
Ciphertext: 110 101 100 001 110 110 111 001 110 101

s r l h s s t h s r

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 35

 One-Time Pad: Decryption

e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111

❖ Decryption: Ciphertext  Key = Plaintext

s r l h s s t h s r
Ciphertext: 110 101 100 001 110 110 111 001 110 101
Key: 111 101 110 101 111 100 000 101 110 000
Plaintext: 001 000 010 100 001 010 111 100 000 101

h e i l h i t l e r

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 36

 One-Time Pad: Decryption

e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111

❖ Double agent claims sender used following “key”

s r l h s s t h s r
Ciphertext: 110 101 100 001 110 110 111 001 110 101
Key: 101 111 000 101 111 100 000 101 110 000
Plaintext: 011 010 100 100 001 010 111 100 000 101

k i l l h i t l e r

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 37

 One-Time Pad: Decryption

e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111

❖ Or sender is captured and claims the key is…

s r l h s s t h s r
Ciphertext: 110 101 100 001 110 110 111 001 110 101
Key: 111 101 000 011 101 110 001 011 101 101
Plaintext: 001 000 100 010 011 000 110 010 011 000

h e l i k e s i k e

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 38

 Exercise – OTP Encryption
What is the ciphertext that results when the plaintext 0x012345
(written in hex) is encrypted using the one-time pad with key
0xFFEEDD?

Solution:
Encryption: Plaintext  Key = Ciphertext
0 1 2 3 4 5
Plaintext: 0000 0001 0010 0011 0100 0101
Key: 1111 1111 1110 1110 1101 1101
Ciphertext: 1111 1110 1100 1101 1001 1000

F E C D 9 8
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 39
 One-Time Pad – Security

Theorem: The one-time pad encryption scheme has one-time

perfect privacy

❖ From adversary's POV, the ciphertext is uniformly distributed

over 𝒞 (𝐶 cannot give any information about 𝑀)
𝐏𝐫𝐨𝐛 𝑲 𝑪 = 𝑲 ⊕ 𝟏𝟎𝟏 𝐏𝐫𝐨𝐛 𝑲 𝑪 = 𝑲 ⊕ 𝟎𝟎𝟏
1/8 000 101 1/8 000 001
1/8 001 100 1/8 001 000
1/8 010 111 1/8 010 011
1/8 011 110 1/8 011 010
1/8 100 001 1/8 100 101
1/8 101 000 1/8 101 100
1/8 110 011 1/8 110 111
1/8 111 010 1/8 111 110
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 40
 Proof of OTP One-Time Perfect Privacy

Theorem: The one-time pad encryption scheme has one-time

perfect privacy

Need to show: Pr 𝑀 = 𝑚 | 𝐶 = 𝑐 = Pr 𝑀 = 𝑚 , where 𝑚, 𝑐 ∈ 0, 1 𝑛

Pr 𝐶 = 𝑐 | 𝑀 = 𝑚 ⋅ Pr 𝑀 = 𝑚 (Bayes’ Theorem)
Pr 𝑀 = 𝑚 | 𝐶 = 𝑐 =
Pr 𝐶 = 𝑐
Pr 𝐶 = 𝑐 | 𝑀 = 𝑚 = Pr Enc(𝐾, 𝑀) = 𝑐 | 𝑀 = 𝑚
1
= Pr 𝐾 ⊕ 𝑚 = 𝑐 = Pr 𝐾 = 𝑚 ⊕ 𝑐 =
2𝑛

Pr 𝐶 = 𝑐 = σ𝑚 ∈ 𝑀 Pr 𝐶 = 𝑐 | 𝑀 = 𝑚 ⋅ Pr 𝑀 = 𝑚 (Law of Total Probability)

1 1 1
= σ𝑚 ∈ 𝑀 ⋅ Pr 𝑀 = 𝑚 = ⋅ σ𝑚 ∈ 𝑀 Pr 𝑀 = 𝑚 =
2n 2n 2𝑛
1/2n ⋅ Pr 𝑀 = 𝑚
Pr 𝑀 = 𝑚 | 𝐶 = 𝑐 = = Pr 𝑀 = 𝑚
1/2n
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 41
 Proof of OTP One-Time Perfect Privacy

Theorem: The one-time pad encryption scheme has one-time

perfect privacy

Need to show: Pr Enc𝐾 (𝑚) = 𝑐 = Pr Enc𝐾 (𝑚′ ) = 𝑐 for any two

messages 𝑚, 𝑚′ ∈ ℳ, and any ciphertext 𝑐 ∈ 𝒞, where 𝑚, 𝑚′ , 𝑐 ∈ 0, 1 𝑛

Pr Enc𝐾 (𝑚) = 𝑐 = Pr 𝐾 ⊕ 𝑚 = 𝑐
1
= Pr 𝐾 = 𝑚 ⊕ 𝑐 = Pr 𝐾 = 𝑘1 =
2𝑛

Pr Enc𝐾 (𝑚′ ) = 𝑐 = Pr 𝐾 ⊕ 𝑚′ = 𝑐
1
= Pr 𝐾 = 𝑚′ ⊕ 𝑐 = Pr 𝐾 = 𝑘2 =
2𝑛

We conclude that the one-time pad is perfectly secret.

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 42
 Exercise - Perfectly Secret
Prove or refute: An encryption scheme with message space ℳ
is perfectly secret if and only if for every probability distribution
on ℳ and every 𝑐0 , 𝑐1 ∈ 𝒞, we have
Pr 𝐶 = 𝑐0 = Pr 𝐶 = 𝑐1

Solution:
This is not true. Consider modifying the one-time pad so encryption
appends a bit that is 0 with probability 1/4 and 1 with probability
3/4. This scheme will still be perfect secret, but ciphertexts ending
with 1 are more likely that ciphertexts ending with 0.

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 43

 One-Time Pad – Perfect?
❖ Provably secure…
 Ciphertext provides no info about plaintext
 All plaintexts are equally likely
❖ OTP has perfect privacy … for one message
 What happens if you use the same (unknown) key for two messages?
 𝑐1 ⊕ 𝑐2 = 𝑘 ⊕ 𝑚1 ⊕ 𝑘 ⊕ 𝑚2 = 𝑚1 ⊕ 𝑚2
 The adversary can learn where the two messages differ
❖ Key is as long as the message Theorem: No encryption
scheme can have perfect
 Key management becomes very difficult secrecy if 𝒦 < ℳ
 What happens if it is shorter?
❖ Nothing special about XOR: ROT-K also has one-time perfect privacy
 Why doesn't this contradict what we saw earlier about ROT-K?
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 44
 Claude Shannon
❖ The founder of Information Theory
❖ 1949 paper: Comm. Thy. of Secrecy Systems
❖ Fundamental concepts
 Confusion ⎯ obscure relationship between plaintext and
ciphertext
 Diffusion ⎯ spread plaintext statistics through the
ciphertext
❖ Proved one-time pad is secure
❖ One-time pad is confusion-only

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 45

 Exercise – OTP Key Limitation
The following questions concern multiple encryptions of single-
character ASCII plaintexts with the one-time pad using the
same 8-bit key. You may assume that the plaintexts are either
(upper- or lower-case) English letters or the space character.
a) Say you see the ciphertexts 1011 0111 and 1110 0111. What can
you deduce about the plaintext characters these correspond to?
b) Say you see the three ciphertexts 0110 0110, 0011 0010, and
0010 0011. What can you deduce about the plaintext characters
these correspond to?

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 46

 Presentation Outline

❖ Basic Probability

❖ Perfect Secrecy

❖ The One-Time Pad

❖ Crypto Requirements

❖ Crypto Taxonomy

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 47

 Cryptography Requirements
❖ Wanted: security definition for symmetric encryption
1
 One-time perfect privacy: Pr 𝑏 ′ = 𝑏 =
2
 Security holds for any adversary (no limit on resource usage)
 Very strict requirements:
▪ Keys need to be as long as message
▪ Key can only be used for one message

❖ Modern cryptography – idea

1 ± 𝜀
 Computational privacy: Pr 𝑏 ′ = 𝑏 =
2
 Security holds for any recourse bounded adversary
 Very strict requirements:
▪ Want keys to be short
▪ Want to encrypt many messages using the same key
Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 48
 Presentation Outline

❖ Basic Probability

❖ Perfect Secrecy

❖ The One-Time Pad

❖ Crypto Requirements

❖ Crypto Taxonomy

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 49

 Taxonomy of Cryptography
❖ Symmetric Key
 Same key for encryption and decryption
 Two types: Stream ciphers and Block ciphers
❖ Public Key (or asymmetric crypto)
 Two keys, one for encryption (public), and one for
decryption (private)
 And digital signatures ⎯ nothing comparable in
symmetric key crypto
❖ Hash Algorithms
 Can be viewed as “one way” crypto

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 50

 Outline of Course

Message Integrity /
Message Privacy
Authentication

Symmetric Encryption Message Authentication

Symmetric Keys Part I
(private-key encryption) Codes (MAC)

Asymmetric Encryption
Asymmetric Keys Digital Signatures
(public-key encryption)

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 51

 Outline of Course

Message Integrity /
Message Privacy
Authentication

Symmetric Encryption Message Authentication

Symmetric Keys
(private-key encryption) Codes (MAC)

Asymmetric Encryption
Asymmetric Keys
(public-key encryption)
Digital Signatures Part II

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 52

 Much More to Cryptography
I know it
Password? Welcome!

❖ Zero-knowledge proofs

❖ Fully-homomorphic encryption
𝐸𝑛𝑐 𝐾, 𝑀1 + 𝑀2 = 𝐸𝑛𝑐 𝐾, 𝑀1 + 𝐸𝑛𝑐 𝐾, 𝑀2

❖ Multi-party computation

❖ Blockchain

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 53

 Slides Original Source
❖ Jonathan Katz and Yehuda Lindell, “Introduction to Modern
Cryptography,” Third Edition, 2021

❖ M. Stamp, “Information Security: Principles and Practice,”

John Wiley

❖ B. Forouzan, “Cryptography and Network Security,” McGraw-

Hill

Perfectly Secret Encryption ENCS4320 – Applied Cryptography © Ahmed Shawahna – slide 54