### CIS 5371 Cryptography

```CIS 5371 Cryptography
3b. Pseudorandomness.
Based on: Jonathan Katz and Yehuda Lindell Introduction to Modern Cryptography
1
Pseudorandomness
An introduction
• A distribution D is pseudorandom if no PPT
distinguisher can detect if it a string sampled
according to D or chosen uniformly at random.
• This is formalized by requiring that every PPT
algorithm outputs 1 with almost the same
probability when given a truly random string
as when given a pseudorandom string.
2
Pseudorandomness
An introduction
• A pseudorandom generator is a
deterministic algorithm that given a short
truly random seed of length n will stretch
it to into a longer string of length ()
that is pseudorandom.
3
Existence of pseudorandom
generators
• We cannot prove that pseudorandom
generators exist!
• We believe that such generators can be
constructed from one-way functions.
• There are some long-standing problems
that have no efficient solution and it is
believed that they are unsolvable in
polynomial time.
4
Pseudorandom generators
informal definition
• A distribution D is pseudorandom if no PPT
distinguisher can detect if it is given a string
sampled according to D or a string chosen
uniformly at random.
• This can be formalized by requiring that a PPT
distinguisher D outputs 1 with almost the
same probability when given a truly random
string and when given a pseudorandom string.
5
Pseudorandomness
Definition
Let (∙) be a polynomial and  a deterministic
polynomial-time algorithm that on input any
{0,1} will output string of length ().  is
a pseudorandom generator if:
•   >
• ∀ PPT distinguishers D, ∃  negl function with:
| Pr   = 1 − Pr    = 1 ≤ negl(n)
where  is uniform random string of length   ,
is uniform random of length  and the probabilities
are taken over the coins used by  and the choices
of , .
6
A secure fixed length
encryption scheme

ℎ
7
A secure fixed length encryption
Protocol 
Let  be a pseudorandom generator with expansion
factor . Define a private-key encryption scheme
for messages of length  as follows
• Gen: on input 1 choose   {0,1} uniformly at
random and output  as key.
• Enc: on input a key   {0,1} and a message
m{0,1}() output the ciphertext
≔G  .
• Dec: on input a key   {0,1} and a ciphertext
c{0,1}() output the plaintext
≔G  .
8
A secure fixed length encryption
Theorem
If  be a pseudorandom generator then
protocol  is a fixed-length private-key
encryption scheme that has
indistinguishable encryptions in the
presence of an eavesdropper.
9
A secure fixed length encryption
Reduction
(Distinguisher D)
1

choose a random bit
compute  : = w 
1 if  ′ =
0 if  ′ 
0 , 1

Suppose that A
succeeds with
probability ()
′
10
A secure fixed length encryption
Proof
1
2
Let   = Pr[PrivK eav (, )  = 1] − .
Then,
•
when  is uniform random we have
Pr   = 1 = Pr[PrivK
•
eav
(, )  = 1] =
1
.
2
when  = () we have
Pr   = 1 = Pr
=1 =
Pr[PrivK eav (, )  = 1] =
1
+
2
().
11
A secure fixed length encryption
Proof
Therefore when  is chosen uniformly in {0,1}
|Pr   = 1 − Pr[

:
= 1]| = () .
12
Variable output length
pseudorandom generators
A deterministic polynomial-time algorithm  is a
variable output-length pseudorandom generator if:
1. Let  be a string and  > 0 an integer. Then
, 1 outputs a string of length .
2. For all , , ′ with  < ′ , the string  , 1 is a
′
prefix of  , 1 .
Define   ≝  , 1(||) .
Then for every polynomial it holds that  , 1 is a
pseudorandom generator with expansion factor .
13
Stream ciphers
• We can easily modify the earlier construction
for the encryption scheme  for variable
output length PRG.
• In this case,
•  ≔ G , 1    .
•  ≔ G , 1||   .
14
Discussion
• We use the term
• stream cipher
for the PR stream generator,
• not the encryption algorithm.
• There are a number of practical
constructions of stream ciphers that are
extraordinarily fast, such as the stream
cipher RC4.
15
Discussion
• The WEP encryption protocol for 802.11
used RC4 and was broken.
• But since then it is fixed---and the standard
updated.
• If RC4 has to be used the first 1024 bits or
16
Discussion
• From a security point of view it is
advocated to use block cipher constructions
for constructing secure encryption
schemes.
• This disadvantage is that this approach is
less efficient when compared to using a
dedicated stream cipher.
17
Multi-message eavesdropping
mult
experiment PrivK
(,)()
1. The adversary  is given input 1 and outputs a pair
of vectors of messages 10 , … , 0 and 11 , … , 1
witℎ |0 = 1 | for all .
2. A key  is generated runnng  1 and a random bit
∈ 0,1 is chosen. For all  the ciphertext    En
is computed and the vector of ciphertexts 1 , … ,
is given to .
3. . outputs a bit  ′ .
4. The output of the experiment i 1 if  =  ′ and 0 otherwise.
18
Definition
A private-key encryption scheme =(Gen,Enc,Dec)
that has indistinguishable multiple encryptions in
the presence of an eavesdropper satisfies:
 PPT Adversary ,  a negligible function negl:
Pr[PrivK
mult
(, )  = 1] ≤
1
2
+ negl  ,
where the probability is taken over the random
coins of , and the experiment.
19
Indistinguishable single encryptions vs
indistinguishable multi encryptions
• The secure fixed length encryption Protocol 
presented earlier is deterministic and cannot
be used as a construction for a
indistinguishable multi encryptions.
• To see why, we use the experiment PrivK mult
for the pair of vector messages (0 , 0 ) and
0 , 1 .
20
Secure multiple encryptions
using a stream cipher
• Synchronized mode
• Communicating parties use a different
part of the stream cipher output to
encrypt a message.
• Useful for parties communicating in the
same session.
• Communicating parties must maintain
state between encryptions.
21
Secure multiple encryptions
using a stream cipher
Unsynchronized mode
 Encryptions are carried out independently
of one another.
 Communicating parties are not required to
maintain state between encryptions.
   ≔ ,  ,   
where the initial vector   {0,1} is
chosen at random.
22
Security against ChosenPlaintext Attack (CPA)
 We now consider a more powerful
encryptions of some specific plaintext
messages, as well as eavesdrop.
23
The CPA indistinguishability
experiment PrivK cpa (,)()
1.
A key  is generated runnng Gen 1 .
2.
.and outputs a pair of messages 0 , 1 of equal length.
3. A random bit
0,1 is chosen and a ciphertext
c  En  is computed and given to .
outputs a bit  ′ .
5. The output of the experiment i 1 if  =  ′ and 0 otherwise.
24
Indistinguishable encryptions under CPA
Definition
A private-key encryption scheme  = Gen, Enc, Dec
has indistinguishable encryptions under CPA if
∀ PPT adversaries , ∃ a negl function such that,
Pr[PrivKcpa
, 
= 1] ≤
1
2
+ negl  ,
where the probability is taken over the coins of A
and those of the experiment.
25
CPA security for multiple encryptions
 As for single encryption, extend the
experiment to PrivK cpa in which the adversary
outputs a pair of vectors of plaintext.
 Any private-key encryption scheme that has
indistinguishable encryptions under CPA also
has indistinguishable multiple encryptions
under CPA
26
```