CRYPTOGRAPHY (COMP3357)

Ravi Ramanathan

TA: Chengru Zhang

Department of Computer Science, HKU

Lecture 4 - Computational Security. Pseudo-random Generators.

Email: ravi at cs dot hku dot hk

 Semantic Security

We've seen that by Shannon's theorem, the only way to achieve perfect secrecy is to have keys

that are as long as messages.

This is quite impractical. We'd like to encrypt a document (say several MB) using a key of few hundred bits.

To do this, we consider weaker, more practical adversaries, that are computationally bounded.

These adversaries perform attacks using real computers with practical limits on time and memory.

Also, we ask that encryption and decryption be themselves efficient algorithms, rather than arbitrary ones.
 Security Parameter n

We consider security parameter n (an integer) chosen by the honest parties beforehand.

n will correspond to the length of the key, typically n = 128.

The security parameter n is assumed to also be known to the adversary.

By efficient algorithms, we will refer to algorithms whose running time is polynomial in n .

Also, since we want to use short keys, we will allow schemes in which the adversaries succeed

with neglibly small probability.

 Probabilistic Polynomial Time Adversaries

An algorithm 𝒜 runs in polynomial time if there exists a polynomial p such that for every

input x ∈ {0,1}* the computation of 𝒜(x) terminates within at most p ( | x | ) steps.

Here | x | denotes the length of the string x .

We write the security parameter in unary as 1n so that we can view the algorithm as

running in time polynomial in its input size.

A probabilistic (randomized) algorithm is one that has access to a source of randomness that yields

unbiased random and independent bits.

A randomized algorithm is considered to give more power to adversary than a deterministic one.
 Probabilistic Polynomial Time Adversaries

The adversary is said to be efficient or Probabilistic Polynomial Time (PPT) if it is using a

randomized (probabilistic) algorithm running in time polynomial in n .

A PPT adversary is a probabilistic algorithm that can only perform a polynomial amount of
operations and has access to a polynomial number of random bits.

By the Extended Church-Turing thesis, all ‘reasonable’ models of computation are polynomially
equivalent, so the notion of PPT adversary is justified, independent of the resources available
to the attacker.
 Redefining Private Key Encryption

Definition. A private-key encryption scheme is a tuple of probabilistic polynomial-time algorithms

(Gen, Enc, Dec) such that:

1. The key-generation algorithm Gen takes as input 1n and outputs a key k, i.e., k ← Gen(1n) .

We assume wlog that any key k output by Gen(1n) satisfies | k | ≥ n .

2. The encryption algorithm Enc takes as input a key k and a plaintext message m ∈ {0,1}*,

and outputs a ciphertext c, i.e. c ← Enck(m) .

3. The decryption algorithm Dec takes as input a key k and a ciphertext c, and outputs a
message m or error ⊥ . We write m := Deck(c) when Dec does not return an error.
 Adversarial Indistinguishability Experiment PrivKeav
𝒜,Π(n) :

We now define Computational (aka Semantic or EAV) Security against a single ciphertext-only attack.

Adversarial Indistinguishability Experiment PrivKeav

𝒜,Π(n) :

1. The adversary 𝒜 is given input 1n and outputs a pair of messages m0, m1 with | m0 | = | m1 | .

2. A key k is generated by running Gen (1n) and a uniform bit b ∈ {0,1} is chosen.
Challenge ciphertext c ← Enck (mb) is computed and given to 𝒜 .

3. Adversary 𝒜 outputs a bit b′ ∈ {0,1} .

4. The adversary 𝒜 succeeds and the output of the experiment is defined to be 1 if b = b′

and 0 otherwise, i.e., we set PrivKeav(n) = 1 if adversary succeeds in guessing the bit.
𝒜,Π

S. Goldwasser and S. Micali. Probabilistic Encryption. Journal of Computer and System Sciences, 28(2): 270-299 (1984).
 Adversarial Indistinguishability Experiment PrivKeav
𝒜,Π(n) :

Note that in the experiment PrivKeav

𝒜,Π(n), adversary only sees the single challenge ciphertext,

and does not have any other interaction with sender or receiver.

Challenger A
m0 , m 1 2 M
R
b {0, 1}
R
k K
R
c E(k, mb ) c

b̂ 2 {0, 1}

Figure 2.5: Attack Game 2.4

Theorem 2.10. For every cipher E and every adversary A, we have

S. Goldwasser and S. Micali. Probabilistic Encryption. Journal

SSadv[A, E] = · SSadv⇤ [A,
of2Computer and
E].System Sciences, 28(2): 270-299 (1984).
(2.10)
Proof. This is just a simple calculation. Let p0 be the probability that the adversary outputs 1 in
 Computational Indistinguishability or EAV-security

Definition. A private-key encryption scheme Π = (Gen, Enc, Dec) has indistinguishable encryptions

in the presence of an eavesdropper, or is EAV-secure, or is semantically secure, if for all

probabilistic polynomial-time adversaries 𝒜 there is a negligible function ϵ such that for all n,

1
Pr [PrivKeav
𝒜,Π (n) = 1 ] 2 + ϵ(n) .
≤

Here, the probability is taken over the randomness used by 𝒜 and the randomness used in the
experiment for choosing k, and b, as well as any randomness used by Enc .

S. Goldwasser and S. Micali. Probabilistic Encryption. Journal of Computer and System Sciences, 28(2): 270-299 (1984).
 Negligible Success Probability: Negligible Functions

Definition. A function f : ℕ → ℝ is polynomially bounded if there exist constants c, d ∈ ℝ+

such that for all positive integers n, we have | f (n) | ≤ n c + d .

A negligible function is one that is asymptotically smaller than any inverse polynomial function.

Definition. A function f : ℕ → ℝ≥0 is negligible if for every positive polynomial p there is

1
an N such that for all integers n > N it holds that f (n) < ,
p(n)
1
i.e. ∀p, ∃N s.t. f(n) < for n > N
p(n)
 Negligible Functions

Equivalently, function f : ℕ → ℝ≥0 is negligible if for all constants c there exists an N such that
for all n > N it holds that f (n) < n −c . We denote a negligible function by ϵ(n) .

1/4 1/3
Typical negligible functions: f(n) = 2−n, 2− n
, e −n , n 42−cn, 2−c′ n , 2−c′′n , n −log2 n .

Example. Suppose f (n) = 2−n .

We can calculate N such that f (n) < n −8 for all n > N .

Setting 2−n < n −8 and taking logs (base 2) on both sides

we get n > 8 log2 n . This gives N = 44.

 Negligible Functions

Equivalently, a function f : ℕ → ℝ≥0 is negligible if and only if for all c > 0, we have

lim f (n) ⋅ n c = 0.
n→∞

−100 1
Some examples of non-negligible functions include n , .
100n 4 + n 2 log n
1
2n
for odd n
Example. Suppose we have a function defined as g(n) := 1
for even n
n8

1
This function g(n) is not negligible since there is no N for which g(n) < for all n > N .
n 9

1/3
Q1. Find N such that (a) f1(n) = 2−n , (b) f2(n) = n −log2 n are smaller than n −3 for all n > N .
A1. (a) N ≈ 133194, (b) N = 8.
 Closure Properties of Negligible Functions

Fact. If f1(n) and f2(n) are negligible functions, then the following hold:

1. The function f3(n) = f1(n) + f2(n) is a negligible function,

2. For any positive polynomial p, the function f4(n) = p(n) ⋅ f1(n) is negligible.

−n 1/3
Example. We have seen that 2 and n −log2 n are negligible functions.
1/3
From the theorem it follows that 2−n + n −log2 n is negligible and also
1/3
n 4 ⋅ 2−n is negligible.

Q2. Verify these by finding N such that each of the above functions is smaller than n −4 for all n > N .
 Solving for Parameters Exercise

n 1/3(log2 n)
2/3
Q1. The best classical factoring algorithm requires a running time of about 2 clock cycles
to factor an n-bit number. Consider an attacker who has access to a 4GHz computer.
Estimate the size of the numbers that the attacker cannot factor for the next 100 years.

A1. We know that 4GHz = 4 × 109 clock-cycles per second.

100years = 100 × 365 × 24 × 60 × 60 = 3.1536 × 109 seconds.

Let us find n for which the n-bit number can be factored within the next 100 years:

n 1/3(log2 n)
2/3
2 ≤ 3.1536 × 109 × 4 × 109 = 126144 × 1014

n 1/3 (log2 n)
2/3
≤ log2 126144 + 14 log2 10 = 16.945 + 46.507 = 63.452

n (log2 n) ≤ 255464.11
2
 Solving for Parameters Exercise

n 1/3(log2 n)
2/3
Q1. The best classical factoring algorithm requires a running time of about 2 clock cycles
to factor an n-bit number. Consider an attacker who has access to a 4GHz computer.
Estimate the size of the numbers that the attacker cannot factor for the next 100 years.

loge n
A1. Continued. Let x = loge n . Then n = e x, log2 n =
loge 2

n (log2 n) ≤ 255464.11
2

x 2e x ≤ 255464.11 × (loge 2) = 122738.5

2

A formal solution can be obtained using Lambert's W function.

x ≤ 7.649 ⟹ n ≤ 2098.5

For n > 2099, attacker cannot factor the n-bit number in 100 years.
 Solving for Parameters Exercise

n 1/3(log2 n)
2/3
Q1. The best classical factoring algorithm requires a running time of about 2 clock cycles
to factor an n-bit number. Consider an attacker who has access to a 4GHz computer.
Estimate the size of the numbers that the attacker cannot factor for the next 100 years.

A1. Continued. n (log2 n) ≤ 255464.11

2

A formal solution can be obtained using Lambert's W function.

1
n 1/2 log2 n 1/2 ≤ 255464.11 = 252.72
2
Let loge n 1/2 = x ⟹ n = e 2x xe x ≤ 252.72 × loge 2 = 175.17

Lambert's W function (aka Product Log function) is the inverse function of f (W ) = We w .

x ≤ W(175.17) = 3.8244 ⟹ n ≤ 2098.1
For n > 2099, attacker cannot factor the n-bit number in 100 years.
 Parity Prediction

Q2. Let Π = (Enc, Dec) be a cipher defined over (𝒦, ℳ, 𝒞) with ℳ = {0,1}l .

For m ∈ ℳ, we define 𝚙𝚊𝚛𝚒𝚝𝚢(m) to be 1 if the number of 1′s in m is odd, and 0, otherwise.

Suppose that for Π, there exists an efficient (PPT) adversary ℬ that could predict 𝚙𝚊𝚛𝚒𝚝𝚢(m)

with probability 1 upon observing a ciphertext.

Is Π semantically secure? Prove your answer.

A2. To be discussed in class.

 Permutation Cipher

Q3. Consider the following permutation cipher Π = (Enc, Dec) defined over (𝒦, ℳ, 𝒞) where

𝒞 = ℳ = {0,1}l and 𝒦 is the set of all l! permutations of the set {0,1,…, l} .

For a key k ∈ 𝒦 and message m ∈ ℳ define Enck(m) to be the result of permuting the bits of m

using the permutation k, that is, Enck(m) = m[k(0)]…m[k(l − 1)] .

Is the permutation cipher Π semantically secure? Prove your answer.

A3. To be discussed in class.

 Pseudorandomness

An important ingredient in constructing computationally secure encryption schemes is

the notion of pseudorandom numbers.

Firstly, we recognize that randomness is the property, not of a particular bit string, but of

a distribution of bit strings.

We'll say that a distribution D on {0,1}l is pseudorandom if the experiment in which a bit

string is sampled from D is indistinguishable (by a polynomial-time algorithm) from the

experiment in which a uniform string of length l is sampled.

 Pseudorandomness

The uniform distribution on l-bit strings is the distribution Ul where Ul(x) = 2−l for all x ∈ {0,1}l .

Let Dn be a distribution over p(n)-bit strings.

Pseduorandomness is a property of a sequence of distributions {Dn} = {D1, D2, …}

Definition: Let {Dn} be a sequence of distributions over p(n)-bit strings. {Dn} is pseudorandom if

for every probabilistic, polynomial-time algorithm A, there is a negligible function ϵ such that

Prx←Dn[A(x) = 1] − Prx←Up(n)[A(x) = 1] ≤ ϵ(n) .

 Pseudorandomness

We may think of 𝒜 as executing statistical tests in polynomial time. The sequence of distributions

{Dn} is pseudorandom if it passes all efficient statistical tests, i.e., it is infeasible (beyond

probability ϵ(n) ) for any polynomial-time algorithm to distinguish whether the bit string is sampled

according to {Dn} or if it is given a uniform p(n) bit string.

Example. A(x) = 1 if the first bit of x is 1. A(x) = 1 if the parity of x is 1

Example A(x) = 1 if #0(x) − #1(x) ≤ 10 p(n), A(x) = 1 if max run of 0's in x is ≤ 2 log2 p(n) .

Tests for uniformity, consistency, frequency, compressability, Forward and backward Unpredictability.

Pseudorandomness is thus a computational relaxation of true randomness.

 Pseudorandom (number) generators (PRGs/PRNGs)
Note that getting true randomness is very difficult. As an example, one may collect lots of high-entropy

data, and apply some processing to smooth this out and get uniform random bits.

A Pseudorandom generator (PRG) is an efficient (poly-time), deterministic algorithm that expands

a short, uniform seed s into a longer, pseudorandom output G(s) where | G(s) | = p( | s | ) > | s | .

Seed s

Output G(s)
 Pseudorandom (number) generators (PRGs/PRNGs): Formal
Definition

Definition. Let p be a polynomial and let G be a deterministic polynomial-time algorithm such that

for any n and any input s ∈ {0,1}n, G(s) is a string of length p(n) .

We say that G is a pseudorandom generator if the following hold:

1. Expansion: For every n it holds that p(n) > n . We call p the expansion factor of G .

2. Pseudorandomness: For any PPT algorithm D, there is a negligible function ϵ such that

Prs←Un [D (G(s)) = 1] − Prr←Up(n) [D(r) = 1] ≤ ϵ(n)

where the first probability is over uniform choice of s ∈ {0,1}n and the randomness of D,

and the second is over uniform choice of r ∈ {0,1}p(n) and the randomness of D .
Pseudorandom (number) generators (PRGs/PRNGs): Points to
note

By definition, for a PRG G, no efficient attacker 𝒜 can distinguish whether it is given G(s)
(for uniform s of length n bits) or a uniform string y of length p(n) bits.
2n
Note however that G(s) itself is not uniform. The fraction of strings in the range of G is p(n) .
2
Many strings do not occur as outputs of G .

{0,1}n

Q . Suppose G(s) = s∥ ⊕i si . Is this G a PRG?

{0,1}p(n)

Q . Suppose G : {0,1}n → {0,1}2n satisfies msb(G(s)) = 1 for 2/3 fraction of the s in {0,1}n .
Is G a PRG?
 Pseudorandom Generator Exercise

Q . Suppose G : {0,1}s → {0,1}n is a secure PRG.

Check if the following are secure PRGs.

(a) G′(x) = G(x)[0,…, n − 2] i.e., G′(x) drops the final bit of G(x) .

(b) G′(x) = G(x)∥0.

(c) G′(x) = G(x) ⊕ 1n .

(d) G′(x) = reverse(G(x)) where reverse(x) reverses the bit string x .

(e) G′(x) = G(x)∥G(x) .

 Pseudorandom Generator Exercise

Q . Suppose G : {0,1}s → {0,1}n is a secure PRG.

Check if the following are secure PRGs.

(a) G′(x) = G(x)[0,…, n − 2] i.e., G′(x) drops the final bit of G(x) .

A(a) Yes. G′ is a secure PRG. One can construct a distinguisher for G given a distinguisher for G′ . Why?

(b) G′(x) = G(x)∥0.

A(b) No. G′ is NOT a secure PRG. A distinguisher for G′ can output not random when the last bit is not 0.

(c) G′(x) = G(x) ⊕ 1n .

A(c). Yes. G′ is a secure PRG. One can construct a distinguisher for G given a distinguisher for G′ .
 Pseudorandom Generator Exercise

Q . Suppose G : {0,1}s → {0,1}n is a secure PRG.

Check if the following are secure PRGs.

(d) G′(x) = reverse(G(x)) where reverse(x) reverses the bit string x .

A(d) Yes. G′ is a secure PRG. One can construct a distinguisher for G given a distinguisher for G′ .

(e) G′(x) = G(x)∥G(x) .

A(e) No. G′ is NOT a secure PRG.

A distinguisher for G′ can output not random when the first n bits does not equal the last n bits.

In each case, understand how to construct the distinguisher, and to calculate the distinguishing probability.
 Pseudorandom (number) generators (PRGs/PRNGs): Points to
note

Do secure PRGs exist?

In general, this is not known. If we could unconditionally prove that a particular PRG is secure,

we would have shown P ≠ NP .

But we can assume in practice that certain G are PRGs.

We know particular examples of deterministic functions G called stream ciphers for which

no efficient distinguishers are known.

We can also construct PRGs from weaker assumptions (that one-way functions exist)

which hold if, for instance certain problems like factoring are hard.
 Linear Congruential Generator

The Linear Congruential Generator is a simple Pseudo-Random Generator, that is in general

not cryptographically secure.

Parameters. m > 0 : the modulus, 0 < a < m : the multiplier,

0 ≤ c < m : the increment, and 0 ≤ X0 < m : the seed.

The Linear Congruential Generator generates a sequence of pseudo-random numbers {Xn} via :

Xn+1 = (aXn + c) mod m

The choice of constants a, c, and m is important:

m should be large, prime, e.g. 231 − 1
If c = 0 there are some good values of a, e.g. a = 75 = 16807

If the adversary knows parameters and one number, it can easily determine subsequent numbers.
 Blum Blum Shub Generator

The Blum Blum Shub Generator is a cryptographically secure pseudo-random bit generator.

Parameters. p, q : large prime numbers such that p ≡ q ≡ 3 (mod 4)

M = p × q, s : random number relatively prime to M .

The Blum Blum Shub generator generates a sequence of pseudo-random bits Bi via :

X0 = s 2 mod M, for i = 1 → ∞, Xi = (Xi−1) mod M, Bi = Xi mod 2.

2

Example. Say M = 192649 = 383 × 503,

s = 101355
Output Bi are the lsb of Xi .

Blum, L.; Blum, M.; Shub, M. (1986). "A Simple Unpredictable Pseudo-Random Number Generator"
SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM). 15 (2): 364–383.
 Pseudo One-Time Pad

Pseudo One-Time Pad is a private-key encryption scheme built upon any pseudorandom generator.

Pseudo One-Time Pad Construction. Let G be a pseudorandom generator with expansion

factor p . Define a private-key encryption scheme for messages of length p as:

Gen : Takes input 1n, outputs a uniform k ∈ {0,1}n as the key.

Enc : Takes as inputs key k ∈ {0,1}n and message m ∈ {0,1}p(n), outputs the ciphertext
c := G(k) ⊕ m .

Dec : Takes as inputs key k ∈ {0,1}n and ciphertext c ∈ {0,1}p(n), outputs the message
m : G(k) ⊕ c .

Check that the Pseudo OTP satisfies Correctness.