Lecture 1 – Introduction to cryptography

TEK4500
30.08.2023
Håkon Jacobsen
hakon.jacobsen@its.uio.no
What is cryptography?

Alice Internet
Bob

Adversary

2
What is cryptography?

Alice
Bob

Adversary

3
What is cryptography?

Alice
Bob

Adversary
Security goals:

• Data privacy: adversary should not be able to read message M

4
What is cryptography?

Alice
Bob

M M'

Adversary
Security goals:

• Data privacy: adversary should not be able to read message M

• Data integrity: adversary should not be able to modify message M
• Data authenticity: message M really originated from Alice

5
Ideal solution: secure channels

But how to build?

Alice
Bob

Adversary
Security goals:

• Data privacy: adversary should not be able to read message M 

• Data integrity: adversary should not be able to modify message M 
• Data authenticity: message M really originated from Alice 

6
Creating secure channels: encryption schemes

Alice
Bob
K K
C
M ℰ 𝒟

M/⊥
Adversary

𝓔 : encryption algorithm (public) K : encryption / decryption key (secret)

𝓓 : decryption algorithm (public)

7
Creating secure channels: encryption schemes

Alice
Bob
Ke Kd
C
M ℰ 𝒟

M/⊥
Adversary

𝓔 : encryption algorithm (public) Ke : encryption key (public)

𝓓 : decryption algorithm (public) Kd : decryption key (secret)

8
Basic goals of cryptography

Message integrity /
Message privacy
authentication

Message authentication
Symmetric keys Symmetric encryption
codes (MAC)

Asymmetric encryption
Asymmetric keys Digital signatures
(public-key encryption)

9
Basic goals of cryptography

Message integrity /
Message privacy
authentication

Message authentication
Symmetric keys Symmetric encryption
codes (MAC)

Asymmetric encryption
Asymmetric keys Digital signatures
(public-key encryption)

10
Some notation
• ∈ − "element in" • ∀ − "for all"
4
• 3 ∈ {1,2,3,4,5} • "∀𝑋 ∈ 0,1 … " = "for all bitstrings of length 4…"
• 7 ∉ {1,2,3,4,5}
• ∃ − "there exists"
𝑛 •
• 0,1 − set of all bitstrings of length 𝑛 "∃𝑋 ∈ {0,1,2, … } such that 𝑋 > 13"
3
• 011 ∈ 0,1
• 011 ∉ 0,1 5 • 𝒳 × 𝒴 − set of pairs (𝑋, 𝑌) with 𝑋 ∈ 𝒳 and 𝑌 ∈ 𝒴
• 𝐹 ∶ 𝒳 × 𝒴 → 𝒵 function taking two inputs 𝑋 ∈ 𝒳,
∗ 𝑌 ∈ 𝒴 and producing single output 𝑍 ∈ 𝒵
• 0,1 − set of all bitstrings of finite length
∗
• 1, 1001, 10, 10001101000001 ∈ 0,1
• 𝑋 ← 5 − "assign value 5 to 𝑋"
• 1𝑛 or 0𝑛 – string of 𝑛 "ones" (or "zeros")
$
• 15 = 11111 • 𝑋 ← 𝒳 − "assign 𝑋 a random value from set 𝒳"
• 03 = 000

• 𝐹 ∶ 𝒳 → 𝒴 − function from set 𝒳 to set 𝒴 …independent, and

5 3
• 𝐹 ∶ 0,1 → 0,1 uniformly distributed…
• 𝐺 ∶ 𝐴, 𝐵, 𝐶, 𝐷 → 0,1,2, …
11
Symmetric encryption – syntax
Π = ℰ, 𝒟 Examples:

𝒦 = 0,1 128 ℳ = 0,1 ∗ 𝒞 = 0,1 ∗

ℰ ∶𝒦×ℳ →𝒞
ℰ 𝐾, 𝑀 = ℰ𝐾 𝑀 = 𝐶 𝒦 = 0,1 128 ℳ = 𝐴, 𝐵, … , 𝑍 𝒞 = 𝐴, 𝐵, … , 𝑍
𝒦 = 0,1 128 ℳ = YES, NO 𝒞 = 0,1 ∗
𝒟: 𝒦 × 𝒞 → ℳ
𝒟 𝐾, 𝐶 = 𝒟𝐾 𝐶 = 𝑀 𝒦 = 1, … , 𝑝 ℳ = 𝐴, 𝐵, … , 𝑍 𝒞 = 0,1 ∗

Correctness requirement: Possible privacy security goals:

∀𝐾 ∈ 𝒦, ∀𝑀 ∈ ℳ: - Hard to recover 𝑀 from 𝐶

- Hard to recover 𝐾 from 𝐶
- Hard to learn one bit of 𝑀 from 𝐶
𝒟 𝐾, ℰ 𝐾, 𝑀 =𝑀 - Hard to learn parity of 𝑀 from 𝐶
-…

12
Historical encryption algorithms
Ceasar cipher

a b c d e f g h i j k l m n o p q r s t u v w x y z

a b c d e f g h i j k l m n o p q r s t u v w x y z a

in the far distance a helicopter skimmed down between

the roofs, hovered for an instant like a bluebottle,
and darted away again with a curving flight. It was
the police patrol, snooping into people's windows

lq wkh idu glvwdqfh d kholfrswhu vnlpphg grzq ehwzhhq

wkh urriv, kryhuhg iru dq lqvwdqw olnh d eoxherwwoh,
dqg gduwhg dzdb djdlq zlwk d fxuylqj ioljkw. Lw zdv
wkh srolfh sdwuro, vqrrslqj lqwr shrsoh'v zlqgrzv

14
Ceasar cipher (ROT-13)

a b c d e f g h i j k l m n o p q r s t u v w x y z

a b c d e f g h i j k l m n o p q r s t u v w x y z

in the far distance a helicopter skimmed down between

the roofs, hovered for an instant like a bluebottle,
and darted away again with a curving flight. It was
the police patrol, snooping into people's windows

va gur sne qvfgnapr n uryvpbcgre fxvzzrq qbja orgjrra

gur ebbsf, ubirerq sbe na vafgnag yvxr n oyhrobggyr,
naq qnegrq njnl ntnva jvgu n pheivat syvtug. Vg jnf
gur cbyvpr cngeby, fabbcvat vagb crbcyr'f jvaqbjf

15
Ceasar cipher
• a↔0
• b↔1
• c↔2
• d↔3
• e↔4
𝐶 ← 𝑀 + 3 (mod 26)

• z ↔ 25

16
Modular arithmetic

−4 −3 −2 −1 0 1 2 3 4 5 6 7 8 9 10 11

17
Modular arithmetic
14 13
5 4
12
15 3
6

16 7 2 11
20

8
17 1
10
−4 −3 −2 −1 0 19
9
18

18
Modular arithmetic
14 13
5 4
−4 12
15 3
6
−3

16 7 −2 2 11
20
−1
8
17 1
10
0 19
9
18

19
Modular arithmetic
14 13
5 4 1+3=4

−4 12 5 + 8 = 13 ≡ 4 mod 9
15 3
6
−3 5 ⋅ 4 = 20 ≡ 2 mod 9

−2 mod 9 2 − 5 = −3 ≡ 6 mod 9
16 7 2 11
20
210 = 1024 ≡ 7 mod 9
−1
8
17 1
10 158 mod 9 = 153 + 𝑟 ≡ 𝑟 mod 9
0 19
𝑟<9
9
18
9 → 18 → 27 → 36 → ⋯ → 𝟏𝟓𝟑 → 162
20
Ceasar cipher
• a↔0
• b↔1
• c↔2
• d↔3
• e↔4
𝐶 ← 𝑀 + 3 (mod 26)

• z ↔ 25

21
ROT-13
• a↔0
• b↔1
• c↔2
• d↔3
• e↔4
𝐶 ← 𝑀 + 13 (mod 26)
𝑀 ← 𝐶 − 13 (mod 26)
⁞
𝒦 = {13}
• z ↔ 25
ℰ ∶𝒦×ℳ →𝒞 ℳ = {0,1,2, … , 25}
𝒟 ∶𝒦×𝒞 →ℳ 𝒞 = {0,1,2, … , 25}

22
ROT-K
• a↔0
• b↔1
• c↔2
• d↔3
• e↔4
𝐶 ← 𝑀 + 𝐾 (mod 26)
𝑀 ← 𝐶 − 𝐾 (mod 26)
⁞
𝒦 = {0,1,2, … , 25}
• z ↔ 25
ℰ ∶𝒦×ℳ →𝒞 ℳ = {0,1,2, … , 25}
𝒟 ∶𝒦×𝒞 →ℳ 𝒞 = {0,1,2, … , 25}

23
Attacking ROT-K

𝑲 𝑴
0 va gur sne qvfgnapr n uryvpbcgre …
𝒦 = 26
1 uz ftq rmd puefmzoq m tqxuoabfqd …
2 ty esp qlc otdelynp l spwtnzaepc …
3 sx dro pkb nscdkxmo k rovsmyzdob …

𝐶 = va gur sne qvfgnapr n uryvpbcgre …

⋮

12 jo uif gbs ejtubodf b ifmjdpqufs …

13 in the far distance a helicopter …
14 hm sgd ezq chrszmbd z gdkhbnosdq …
Conclusion: key space must be large enough!

25 wb hvs tof rwghobqs o vszwqcdhsf …

24
Substitution cipher

a b c d e f g h i j k l m n o p q r s t u v w x y z

a b c d e f g h i j k l m n o p q r s t u v w x y z

25
Substitution cipher

a b c d e f g h i j k l m n o p q r s t u v w x y z

a b c d e f g h i j k l m n o p q r s t u v w x y z

26
Substitution cipher 𝒦 = 26! ≈ 1026 ≈ 288

a b c d e f g h i j k l m n o p q r s t u v w x y z

↕ ↕ ↕ ↕ … ↕

s x d y w q f m j k o i l g z b e n t u c p a r v h

in the far distance a helicopter skimmed down between the roofs,

hovered for an instant like a bluebottle, and darted away again
with a curving flight. It was the police patrol, snooping into
people's windows

jg umw qsn yjtusgdw s mwijdzbuwn tojllwy yzag xwuawwg umw nzzqt,

mzpwnwy qzn sg jgtusgu ijow s xicwxzuuiw, sgy ysnuwy sasv sfsjg
ajum s dcnpjgf qijfmu. ju ast umw bzijdw bsunzi, tgzzbjgf jguz
bwzbiw't ajgyzat

27
Attacking the substitution cipher
jg umw qsn yjtusgdw s mwijdzbuwn
tojllwy yzag xwuawwg umw nzzqt,
𝒦 = 26! ≈ 1026 ≈ 288 mzpwnwy qzn sg jgtusgu ijow s
xicwxzuuiw, sgy ysnuwy sasv sfsjg
ajum s dcnpjgf qijfmu. ju ast umw
bzijdw bsunzi, tgzzbjgf jguz
English letter frequency
bwzbiw't ajgyzat

28
Attacking the substitution cipher
jg ume qsn yjtusgde s meijdzbuen
tojlley yzag xeuaeeg ume nzzqt,
𝒦 = 26! ≈ 1026 ≈ 288 mzpeney qzn sg jgtusgu ijoe s
xicexzuuie, sgy ysnuey sasv sfsjg
ajum s dcnpjgf qijfmu. ju ast ume
bzijde bsunzi, tgzzbjgf jguz
English letter frequency
bezbie't ajgyzat


29
Attacking the substitution cipher
jg tme qsn yjttsgde s meijdzbten
tojlley yzag xetaeeg tme nzzqt,
𝒦 = 26! ≈ 1026 ≈ 288 mzpeney qzn sg jgttsgt ijoe s
xicexzttie, sgy ysntey sasv sfsjg
ajtm s dcnpjgf qijfmt. jt ast tme
bzijde bstnzi, tgzzbjgf jgtz
English letter frequency
bezbie't ajgyzat




30
Attacking the substitution cipher
jg tme qan yjttagde a meijdzbten
tojlley yzag xetaeeg tme nzzqt,
𝒦 = 26! ≈ 1026 ≈ 288 mzpeney qzn ag jgttagt ijoe a
xicexzttie, agy yantey aaav afajg
ajtm a dcnpjgf qijfmt. jt aat tme
bzijde batnzi, tgzzbjgf jgtz
English letter frequency
bezbie't ajgyzat

 

 
31
Attacking the substitution cipher
ig tme qan yittagde a meiidzbten
toilley yzag xetaeeg tme nzzqt,
𝒦 = 26! ≈ 1026 ≈ 288 mzpeney qzn ag igttagt iioe a
xicexzttie, agy yantey aaav afaig
aitm a dcnpigf qiifmt. it aat tme
bziide batnzi, tgzzbigf igtz
English letter frequency
bezbie't aigyzat

  

  
32
Attacking the substitution cipher
ig tme qan yittagde a meiidobten
toilley yoag xetaeeg tme nooqt,
𝒦 = 26! ≈ 1026 ≈ 288 mopeney qon ag igttagt iioe a
xicexottie, agy yantey aaav afaig
aitm a dcnpigf qiifmt. it aat tme
boiide batnoi, tgoobigf igto
English letter frequency
beobie't aigyoat

   

 
33
Attacking the substitution cipher
in tme qan yittande a meiidobten
toilley yoan xetaeen tme nooqt,
𝒦 = 26! ≈ 1026 ≈ 288 mopeney qon an inttant iioe a
xicexottie, any yantey aaav afain
aitm a dcnpinf qiifmt. it aat tme
boiide batnoi, tnoobinf into
English letter frequency
beobie't ainyoat

   

 
34
Attacking the substitution cipher
in tme qan yistande a meiidobten
soilley yoan xetaeen tme nooqs,
𝒦 = 26! ≈ 1026 ≈ 288 mopeney qon an instant iioe a
xicexottie, any yantey aaav afain
aitm a dcnpinf qiifmt. it aas tme
boiide batnoi, tnoobinf into
English letter frequency
beobie's ainyoas

    

  
35
Attacking the substitution cipher
in the qan distande a heiidobter
soilled down xetween the rooqs,
𝒦 = 26! ≈ 1026 ≈ 288 hopered qor an instant iioe a
xicexottie, and danted awav afain
with a dcrpinf qiifht. it was tme
boiide batroi, tnoobinf into
English letter frequency
beobie's windows

       

      
36
Conclusions

• Key space must be large enough

• Ciphertext should not reveal letter frequency of the message

• Is this enough?

37
Historical approach to crypto development

build → break → fix → break → fix → break → fix ... secure?

38
Modern approach

• Trying to make cryptography more a science than an art

• Focus on formal definitions of security (and insecurity)

• Clearly stated assumptions

• Analysis supported by mathematical proofs

• ... but old fashioned cryptanalysis continues to be very important!

39
The one-time-pad (OTP)
𝑛
𝒦 = 0,1
ℳ = 0,1 𝑛

𝒞 = 0,1 𝑛

ℰ 𝐾, 𝑀 = 𝐾 ⊕ 𝑀 𝒟 𝐾, 𝐶 = 𝐾 ⊕ 𝐶

0101100100 𝑀 1011101001 𝐶
⊕ 1110001101 𝐾 ⊕ 1110001101 𝐾
−−−−−−−− − −−−−−−−− −
= 1011101001 𝐶 = 0101100100 𝑀

Is the one-time pad secure?

40
(One-time) perfect privacy

1–p𝐫𝐢𝐯
𝐄𝐱𝐩Σ 𝐴 World 0 World 1
𝑏
$ Input 𝑀: Input 𝑀:
1. 𝑏 ← 0,1 return Σ. Enc 𝐾, 𝑀 return Σ. Enc 𝐾, $
$
2. 𝐾 ← Σ. KeyGen
3. 𝑀←𝐴
$
4. 𝑅 ← 0,1 𝑀
5. 𝐶0 ← Σ. Enc 𝐾, 𝑀
6. 𝐶1 ← Σ. Enc 𝐾, 𝑅 I’m in World 𝒃′
7. 𝑏′ ← 𝐴 𝐶𝑏
?
8. 𝐫𝐞𝐭𝐮𝐫𝐧 𝑏 ′ = 𝑏

Definition: An encryption scheme Σ has (one-time) perfect privacy

if for any adversary 𝐴:
1
Pr 𝑏′ = 𝑏 =
2

41
The one-time-pad (OTP) – security

Theorem (Shannon 1949): The one-time pad encryption scheme has one-time perfect privacy

World 0 World 1
𝐏𝐫𝐨𝐛 𝑲 𝑴
Input 𝑀: Input 𝑀:
Proof: Need to show: Pr 𝑏 ′ = 𝑏 = 1/2 1/8 000 101 return 𝐾 ⊕ 𝑀 return 𝐾 ⊕ $
𝑏

1/8 001 100

Suppose 𝐴 submits 𝑴 = 𝟏𝟏𝟎 and receives 𝑪 = 𝟏𝟎𝟏
1/8 010 111
I’m in World 𝒃′

Pr 𝑪 = 𝟏𝟎𝟏 𝑏 = 0 = Pr 𝑲 = 𝟎𝟏𝟏 = 1/8 1/8 011 110

1/8 100 001
Pr 𝑪 = 𝟏𝟎𝟏 𝑏 = 1 = 1/8
1/8 101 000
Pr 𝑪 = 𝟏𝟎𝟏 = 1/8
1/8 110 011
1/8 111 010

Probability that 𝐴 sees 𝑪 = 𝟏𝟎𝟏 is independent of which world it's in! ⟹ 𝑪 contains no information about 𝑏

⟹ Pr 𝑏 ′ = 𝑏 = 1/2
42
One-time pad – perfect?

• One-time pad has perfect privacy…for one message

• What happens if you use the same key for two messages?
• 𝐶1 ⊕ 𝐶2 = 𝐾 ⊕ 𝑀1 ⊕ 𝐾 ⊕ 𝑀2 = 𝑀1 ⊕ 𝑀2

• Key is as long as the message

• Key management becomes very difficult Theorem: No encryption scheme can have
• Sort of defeats the purpose perfect 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?

43
Wanted: security definition for symmetric encryption

• One-time perfect privacy:

′
1
Pr 𝑏 = 𝑏 =
2

• Security holds for any adversary (no limit on resource usage)

• Very strict requirements:

• Keys need to be as long as message…want keys to be short
• Key can only be used for one message…want to encrypt many messages

44
Modern cryptography – idea

computational
• One-time perfect privacy:

′
1
Pr 𝑏 = 𝑏 = ± 𝜀
2
resource bounded

• Security holds for any adversary (no limit on resource usage)

• Very strict requirements:

• Keys need to be as long as message…want keys to be short 
• Key can only be used for one message…want to encrypt many messages 

45
Outline of course

Message integrity /
Message privacy
authentication

Message authentication
Symmetric keys Symmetric encryption
codes (MAC)

Asymmetric encryption
Asymmetric keys (a.k.a. public-key Digital signatures
encryption)

46
Outline of course

Message integrity /
Message privacy
authentication

Message authentication
Symmetric keys Symmetric encryption
codes (MAC) Part I

Asymmetric encryption
Asymmetric keys (a.k.a. public-key Digital signatures
encryption)

47
Outline of course

Message integrity /
Message privacy
authentication

Message authentication
Symmetric keys Symmetric encryption
codes (MAC)

Asymmetric encryption
Asymmetric keys (a.k.a. public-key Digital signatures Part II
encryption)

48
Much more to cryptography
I know it
Password? Welcome!

• Zero-knowledge proofs

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

• Multi-party computation

• Blockchain

49
The security pyramid

IN 5280 – Security by design

User IN 5540 – Privacy by design

Secure IN 5290 – Ethical hacking

systems
TEK 5510 – Security in operating systems and software

Communication TEK 5520 – Cyber security of industrial systems

protocols

TEK 4500 – Introduction to cryptography

Cryptographic mechanisms TEK 5550 – Advanced topics in cryptograpy

50
 Discrete probability
the bare minimum

More details: https://en.wikibooks.org/wiki/High_School_Mathematics_Extensions/Discrete_Probability

Discrete probability
• 𝒰 − a finite set (e.g. 𝒰 = 0,1 𝑛 )

Definition: A probability distribution over 𝒰 is a function Pr ∶ 𝒰 → [0,1] such that

Pr 𝑋 = 1
𝑋∈𝒰

𝒰 = 0,1 2 = 00, 01, 10, 11

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 52

Discrete probability

• A subset 𝐴 ⊆ 𝒰 is called an event and Pr 𝐴 = 𝑥∈A Pr 𝑥

𝒰
𝐴
• The complement of 𝐴 is 𝒰 ∖ 𝐴 and denoted 𝐴
• Fact: Pr 𝐴 = 1 − Pr 𝐴

8
• Example: 𝒰 = 0,1

𝐴 = 𝑥 ∈ 𝒰 ∣ 𝑥 = 11xx xxxx ⊂ 𝒰
With the uniform distribution over 𝒰, what is Pr 𝐴 ?

Answer: Pr 𝐴 = Pr 1100 0000 + Pr[1100 0001] + ⋯ + Pr 1111 1111

= 26 ⋅ 1/ 28
= 1/22
= 1/4

53
Union bound and independence

• Union bound: For events 𝐴 and 𝐵 in 𝒰: 𝒰

𝐴
Pr 𝐴 ∪ 𝐵 ≤ Pr 𝐴 + Pr 𝐵 𝐵

• Events 𝐴 and 𝐵 are independent if Pr 𝐴 and 𝐵 = Pr 𝐴 ⋅ Pr 𝐵

54
Law of total probability

• Conditional probability

Pr 𝐴 ∣ 𝐵 > Pr 𝐴
Pr 𝑋 𝑌
def
=
Pr 𝑋 and 𝑌 𝐵 𝐶
Pr 𝑌 Pr 𝐴 ∣ 𝐶 = 0
𝐴

• Law of total probability

𝐸1
𝐸3
Pr 𝐴 ∣ 𝐸1 ⋅ Pr 𝐸1
+ Pr 𝐴 ∣ 𝐸2 ⋅ Pr 𝐸2
Pr 𝐴 =
⋮
𝐸2 𝐸𝑛
+Pr 𝐴 ∣ 𝐸𝑛 ⋅ Pr 𝐸𝑛

55
Random variables
A random variable 𝑋 is a function 𝑋 ∶ 𝒰 → 𝒱

Example: 𝒰 𝒱
00000
𝒰 𝒱 00
5 2 00001
𝑋 ∶ 0,1 → 0,1 00010 01
def
𝑋 𝑠 = msb2 𝑠 𝑋 10
⋮

11
11111

def 23
Pr[𝑋 = 11] = Pr 𝑠 = 11xxx = = 1/4
𝑠∈𝒰 25

Depends on the probability Uniform distribution on 𝒰

distribution on 𝒰

56
Random variables
A random variable 𝑋 is a function 𝑋 ∶ 𝒰 → 𝒱

Example: 𝒰 𝒱
00000 0
𝒰 𝒱 1
5 00001
𝑋 ∶ 0,1 → [0,1, 2, … , 10] 2
00010 𝑋 3
def 4
𝑋 𝑠 = 𝑠1 + 𝑠2 + 𝑠3 + 𝑠4 + 𝑠5 ⋮
⋮

11111 10

Pr 𝑋 = 0 = 1/32

Pr 𝑋 = 1 = 5/32
5
Pr 𝑋 = 2 = / 32 = 10/32 Uniform distribution on 𝒰
2
but not on 𝒱!

Pr 𝑋 = 10 = 0

57
Random variables
A random variable 𝑋 is a function 𝑋 ∶ 𝒰 → 𝒱

Example: 𝒱
0 1/32 1/32
𝒰 𝒱 𝒰 𝒱 1 5/32 1/32

𝑋 ∶ 0,1 5 → [0,1, 2, … , 10] 5 2 10/32 1/32

𝑈 ∶ 0,1 → [0,1, 2, … , 10]
𝑋
3 10/32 1/32
𝑈
def 4 5/32 1/32
𝑋 𝑠 = 𝑠1 + 𝑠2 + 𝑠3 + 𝑠4 + 𝑠5
⋮

10 0 1/32

Pr 𝑋 = 0 = 1/32

Pr 𝑋 = 1 = 5/32
5
Pr 𝑋 = 2 = / 32 = 10/32 Uniform distribution on 𝒰
2
but not on 𝒱! Uniform distribution on 𝒱
i.e. 𝑈 is a uniform random variable (on 𝒱)
Pr 𝑋 = 10 = 0

58
Randomized algorithms
Inputs Outputs

• Deterministic algorithm:
𝑦 ← 𝐴(𝑥) 𝑥
𝐴(𝑥)

• Randomized algorithm:
$
𝑛
𝑦 ← 𝐴(𝑥; 𝑟) where 𝑟 ← 0,1
$
𝑦 ← 𝐴(𝑥) 𝐴(𝑥)
𝑥
𝐴(𝑥′)
• Example: 𝑥′
$
𝐴 𝑋; 𝐾 = Enc 𝐾, 𝑋 𝑌 ← 𝐴(𝑋)
59
Next week

• Block ciphers

• Pseudorandom functions and pseuorandom permutations

• AES

• NOTE: different room!

60