# 「Cryptography-MIT6875」: Lecture 2

Science wins either way.

Topics:

- How to circumvent Shannon’s lower bound: the computational adversary
- Definition of computational security
- The definition of pseudorandom generators(PRG)

# Recap

In the previous blog, we define __two equivalent definitions of security__, Perfect Secrecy and Perfect Indistinguishability, with the setting of an arbitrary computationally unbounded adversary.

- Perfect Secrecy: A posteriori = A priori

For all $m, c$: $\operatorname{Pr}[\mathcal{M}=m\mid \operatorname{E}(\mathcal{K,M)}=c] = \operatorname{Pr}[\mathcal{M}=m]$ - Perfect Indistinguishability:

For all $m_0, m_1, c$: $\operatorname{Pr}[ \operatorname{E}(\mathcal{K,m_0)}=c] = \operatorname{Pr}[\operatorname{E}(\mathcal{K,m_1)}=c]$

Although the definitions above are equivalent, sometime one is **more convenient** to work with than the other.

We mentioned that the perfect secrecy is achievable using one-time pad. However, the __keys are as long as messages in one-time pad.__

Worse still, in Shannon’s theorem, **for any perfectly secure scheme**, __the key space must be larger than or equal to the message space__, i.e. $\mathcal{|K|\ge|M|}$.

This is known as Shannon’s conundrum.

Therefore, the gist of this blog is **how we can overcome Shannon’s conundrum**.

# Computational Security

Before that, I’ll introduce two mathematical definitions to instantiate Perfect Indistinguishability.

## Perfect Indistinguishability

As mentioned in the previous blog, Perfect Indistinguishability is substantially a formalization of the Turing test.

There are two worlds, world 0 and world 1. The two worlds both sample the key $k$ from the key space $\mathcal{K}$, and the world 0 uses $k$ to encrypt $m$ while world 1 uses $k$ to encrypt $m’$.

The adversary called EVE is a **distinguisher** that __gets the $c$ and tries to guess which world she’s in.__

**Perfect Indistinguishability:**

There are two mathematical definitions to instantiate Perfect Indistinguishability.

*The First Def: *

The probability that EVE think __she is in World 0__ is the same.

*The Second Def: *

The probability of __EVE guessing correctly which world__ she is in is exactly half.

## Key Idea: Computationally Bounded Adversaries

Now, back to the question of how to overcome Shannon’s conundrum.

The key idea is we relax the adversary to an arbitrary **computationally bounded adversary**.

## Computational Indistinguishability (take 1)

In order to define the computationally bounded adversary (or, Computational Indistinguishability), I’ll introduce the **axiom of modern crypto** that __Feasible Computation = Probabilistic Polynomial-time.__

### The Axiom of Modern Crypto: p.p.t

Feasible Computation = Probabilistic polynomial-time

**p.p.t.**is the abbreviation for**Probabilistic Polynomial-time**- It’s a polynomial in a security parameter n (in next subsection).

So, in the scenario of Secure Communication mentioned above, **Alice and Bob** are __fixed__ p.p.t. algorithms while **Eve** is __any__ p.p.t. algorithm.

### Toy Definition with p.p.t.

Let’s attempt to define Computational Indistinguishability with p.p.t..

There are two worlds again, world 0 and world 1.The **only difference** from the unbounded case is that t__he adversary is a p.p.t. distinguisher.__

Write it as a mathematical definition.

*Toy Def: *

### Not Feasible

However, it’s still subject to Shannon’s impossibility which means the __key space must be larger than or equal to the message space__ for any scheme s.t. the Toy Def.

Prove it by **contradiction** same with the proof of Shannon’s Theorem.

**Proof:**

Assume the contradiction that the __key is n bits__ and the __message is n+1 bits__, i.e. $\mathcal{|K|<|M|}$.

If we pick any $c\in \mathcal{C}$ and decrypt $c$ with all distinct keys, there are at most $|\mathcal{K}|$ possible messages.

The__possible message space is the blue part__in the left ellipse which the size is at most $|\mathcal{K}|$ and less than $\mathcal{|M|}$.Assume $m_0$ is inside the possible message space (inside the blue part) while $m_1$ is outside the possible message space.

Consider Eve that picks a random key k and

- output 0 if $\mathrm{D}(k,c)=m_0$ (w.p $\ge 1/2^n$)

It’s possible because $m_0$ is inside the blue part. - output 1 if $\mathrm{D}(k,c)=m_1$ (w.p $=0$)

It’s impossible. - output a random bit if neither holds. (w.p $=1/2$)

- output 0 if $\mathrm{D}(k,c)=m_0$ (w.p $\ge 1/2^n$)
Hence, the probability of

$\begin{array}{l}\text{There exist EVE and }m_0, m_1:\\ \operatorname{Pr}[k\leftarrow \mathcal{K}; b\leftarrow \{0,1\};c=E(k,m_b):\mathrm{EVE}(c)=b] = 1/2 + 1/2^n\end{array}$__EVE guessing correctly__which world she is in is more than half.

## Computational Indistinguishability (take 2)

For the purpose of circumventing the Shannon’s lower bound, I’ll introduce a new notion.

### Negligible Functions

Informally, **Negligible Functions** are functions that __grow slower than $1/p(n)$__ for any polynomial $p$.

**Definition of Negligible Functions: **

A **function** $\mu :\mathbb{N} \rightarrow \mathbb{R}$ is **negligible** if for __every polynomial function__ $p$, there exists an $n_0$ s.t.

for all $n>n_0$:

$$

\mu(n) < 1/p(n)

$$

The **key property** of negligible function is that events that occur with **negligible** probability __look to poly-time algorithms__ like they __never occur__.

Examples:

Is $\mu$ negligible ?

- $\mu(n)=1/n^{100}$ if $n$ is prime.

No, choose $p(n)=n^{200}$.- $\mu(n)=1/2^n$

Yes.

Let $\mu(n)$ be a __negligible__ function and $q(n)$ a __polynomial__ function.

Then $\mu(n)q(n)$ is **negligible** function. ( Run the event $q(n)$ times）

### Security Parameter: n

Security Parameter $n$ (sometimes $\lambda$) always appears in papers.

What the hell is it ?

**Security Parameter** is used to measure __how secure your system is.__

**Security Parameter** is sort of __an input__ to all these algorithms to instantiate them.

So __runtimes & success probabilities__ are measured as __a function of $n$.__

- We want
__honest parties__run in time (**fixed**) polynomial in $n$. - We want
__adversaries__run in time (**arbitrary**) polynomial in $n$, and should have**success probability**__negligible in $n$.__

### Definition

Now we can define Computational Indistinguishability __with p.p.t and negligible function.__

*Definition: *

Hence, the probability of __EVE guessing correctly__ which world she is in __is substantially half,__ which is half __plus a negligible function of security parameter.__

# Pseudorandom Generators (PRG)

In the section, I’ll introduce our first crypto tool: **Pseudorandom Generators** (PRG).

Before that, I want to ask a question. Can you take __10 random bits as input__ and **deterministically** generate __20 bits of randomness as output__ ?

No, you **cannot** generate randomness out of nothing.

Informally, Pseudo-random Generators are **deterministic** programs that __stretch a “ truly random” seed__ into a (much)

__longer sequence of “__

**seeming random**” bits.There are more questions after having the informal definition.

How to define “seeming random” ? Can such a G exist ?

## 3 Equiv. Definitions of PRG

For the first question that __how to define a strong pseudo-random number generator__, there are three equivalent definitions.

**Def 1 [Indistinguishability]**

“No polynomial-time algorithm can distinguish between the output of a PRG on a random seed vs. a truly random string.”

= “as good as” a truly random string for all practical purpose.

**Def 2 [Next-bit Unpredictability]**

“No polynomial-time algorithm can predict the (i+1)th bit of the output of a PRG given the first i bits, better than chance 1/2.”

**Def 3 [Incompressibility]**

“No polynomial-time algorithm can compress the output of the PRG into a shorter string”

All three definitions are equivalent!

In this blog, I’ll just elaborate[*详尽说明; explain] the first definition of indistinguishability.

The other two definitions and the proof will be elaborated in following blog.

## Def 1: Indistinguishability

**Def 1 [Indistinguishability]**

A **deterministic** polynomial-time computable function ${G}:\{0,1\}^n\rightarrow \{0,1\}^m$ is a PRG if:

- It is
**expanding**: $m>n$ and - for every
**p.p.t.**algorithm D (called a distinguisher or a statistical test) if there is a**negligible function**${\mu}$ such that: $$ |\operatorname{Pr}[D({G(U_n)})=1]-\operatorname{Pr}[D({U_m})=1]|={\mu(n)} $$ Notation: $U_n$(resp. $U_m$) denotes the random distribution on $n$-bit (resp. $m$-bit) strings; $m$ is shorthand for $m(n)$.

First of all, PRG is a __deterministic polynomial-time computable function__ which can __expand__ $n$ bits to $m$ bits. $m$ is shorthand for $m(n$) and $m>n$.

There are two worlds, world 1 and world 2.

**World 1** is the __pseudorandom world__ which __samples a truly random__ $n$-bit string from $U_n$ and __expands it__ to a $m$-bit string using PRG $G$, and output the expanded $m$-bit string as $y$.

**World 0** is the __truly random world__ which __sample a truly random__ $m$-bit string from $U_m$, and output the sampled $m$-bit string as $y$.

The adversary is a p.p.t **distinguisher** that __gets the $y$ and tries to tell which world she’s in.__

### Why good ?

Why is this a good definition ?

It’s good for all applications. As long as we can find truly random seeds, can replace true randomness by the __output of PRG(seed)__ in any (polynomial-time) application.

If the application behaves differently, then it __constitutes a (polynomial-time) statistical test__ between PRG(seed) and a truly random strings.

## PRG can Overcome Shannon’s Conundrum

PRG can overcome Shannon’s conundrum. That is, we can encrypt $n+1$ bits using an $n$-bit key.

### How to achieve it ?

The scheme consists of three algorithms.

- $Gen(1^n)$: generate a random n-bit key $k$
- $Enc(k,m)$ where $m$ is a $m(n)$-bit message:
- Expand $k$ into a $(n+1)$-bit pseudorandom string $k’=G(k)$
- One time pad with $k’$: $c = k’\oplus m$

- $Dec(k, c)$: output $G(k)\oplus c$

$G$ is a public and deterministic p.p.t. function, so Alice and Bob can both calculate the one-time pad key $k’=G(k)$.

**Correctness: **

$Dec(k,c)=G(k)\oplus c = G(k)\oplus G(k)\oplus m = m$

The correctness is easily proved.

The scheme is **under the assumption** that $G$ __is a pseudorandom generator.__

Hence, if there exists a PRG, we can move beyond Shannon’s.

### Security Analysis

The most important thing is to prove the scheme is **computational secure**.

Recall the definitions of computational indistinguishability and pseudorandom generator.

*Def of Computational Indistinguishability:*

*Def of PRG [Indistinguishability]:*

A **deterministic** polynomial-time computable function ${G}:\{0,1\}^n\rightarrow \{0,1\}^m$ is a PRG if:

The following proof is maybe your first **reduction**.

The scheme is under **the assumption** that $G$ __is a pseudorandom generator.__

Hence, the thing **we want to prove** is __if $G$ is a pseudorandom generator, then the scheme is computational secure.__

**Proof:**

We want to **prove the contradiction** for simplicity that __if the scheme doesn’t satisfy the computational indistinguishability, then the assumption doesn’t hold__, i.e. $G$ is not a PRG.

Suppose for contradiction that there is a p.p.t. $\operatorname{EVE}$, a polynomial function $p$ and $m_0, m_1$ s.t.

$\operatorname{Pr}[k\leftarrow \mathcal{K}; b\leftarrow \{0,1\};c=Enc(k,m_b):\mathrm{EVE}(c)=b] \ge 1/2 + p(n)$__Case 1:__If $\operatorname{EVE}$ is a**distinguisher for the scheme**, instantiate it.- $\rho = \operatorname{Pr}[k\leftarrow \{0,1\}^n; b\leftarrow \{0,1\};c=G(k)\oplus m_b:\mathrm{EVE}(c)=b] \ge 1/2 + p(n)$
- The probability of $\operatorname{EVE}$ guessing correctly which world she is in is
__more than half.__ - As a result, $\operatorname{EVE}$ is able to distinguish case 1.

__Case 2:__If EVE is a**distinguisher for one-time pad**, instantiate it.- $\rho' = \operatorname{Pr}[k'\leftarrow \{0,1\}^{n+1}; b\leftarrow \{0,1\};c=k'\oplus m_b:\mathrm{EVE}(c)=b] = 1/2 \;(+\mu(n))$
- The probability of $\operatorname{EVE}$ guessing correctly which world she is in is
__substantially half.__ - As a result, $\operatorname{EVE}$ cannot distinguish case 2.

Then we can construct

**a distinguisher $\operatorname{EVE’}$ for $G$**using distinguisher $\operatorname{EVE}$.- A
**distinguisher for PRG**is to get $y$ and try to tell__whether $y$ is from the pseudorandom world and the truly random world.__ __Construct $\operatorname{EVE}’$:__

Get as input a string $y$, run $\operatorname{EVE}(y\oplus m_b)$ for a random $b$, and let $\operatorname{EVE}$’s output be $b’$. Output “PRG” if $b=b’$ and “RANDOM” otherwise.- Run $\operatorname{EVE}(y\oplus m_b)$ for a random $b$
- Let $b’:=\operatorname{EVE}(y\oplus m_b)$
- $\operatorname{EVE}'(y)=\begin{cases} \text{PRG},& b=b'\\ \text{RANDOM},& \text{otherwise}\end{cases}$

- If $y$
__is from the pseudorandom world,__- $\operatorname{EVE}$ is trying to
__distinguish the Case 1__when running $\operatorname{EVE}(y\oplus m_b)$ for a random $b$. - The probability of $\operatorname{EVE}(y\oplus m_b)$
__guessing $b$ correctly, i.e. $b’=b$, is more than half.__ - $\operatorname{Pr}[\operatorname{EVE’}\text{ outputs PRG}\mid y\text{ is pseudorandom}]=\rho \ge 1/2 + 1/p(n)$

- $\operatorname{EVE}$ is trying to
- If $y$ is
__from the truly random world,__- $\operatorname{EVE}$ is trying to
__distinguish the Case 2__when running $\operatorname{EVE}(y\oplus m_b)$ for a random $b$. - The probability of $\operatorname{EVE}(y\oplus m_b)$
__guessing $b$ correctly, i.e. $b’=b$, is substantially half.__ - $\operatorname{Pr}[\operatorname{EVE’}\text{ outputs RANDOM}\mid y\text{ is random}]=\rho’ = 1/2$

- $\operatorname{EVE}$ is trying to

- A
Hence,

__the advantage of $\operatorname{EVE}’$ distinguishing for $G$ is__$\operatorname{Pr}[\operatorname{EVE'}\text{ outputs PRG}\mid y\text{ is pseudorandom}]-\operatorname{Pr}[\operatorname{EVE'}\text{ outputs RANDOM}\mid y\text{ is random}]\ge 1/p(n)$ , which proves $G$ is not a PRG.QED.

So far we have proven it that $G$ is not a PRG if the scheme is not (computational) secure which also means __the scheme is (computational) secure if there exists a PRG $G$.__

We make a **reduction** from __whether the scheme is (computational) secure to whether PRGs exist.__ It’s a simple but typical reduction. The reductions will be more intricate but the principle remains same.

### Two Questions to PRG

As a consequence, the proof of security comes back to PRGs.

There are two questions to PRGs

- Q1: Do PRGs exist ?
- Q2: How do we encrypt longer messages or many messages with a fixed key ?

The next subsection will answer the first question Q1 while Q2 will be answered in following blog.

## Q1: Do PRGs Exist ?

Do PRGs exist ?

If P=NP, PRGs do not exist.

I believe P$\ne$NP so I believe PRGs do exist.

There are two methodologies to construct PRGs, the practical methodology and the foundational mehodology.

Rigndael (AES) is designed by the practical methodology, but this course is more about the foundational methodology.

### The Practical Methodology

Start from a design framework.

A**practical truth**is appropriately chosen__functions composed appropriately many times look random.__For example, if you repeat the knot many and many times, then you will get a random line ball.Come up with a candidate construction.

e.g. the construction of Rijndael (AES) .Do extensive cryptanalysis.

### The Foundational Methodology

The maxim is reducing to simpler primitives.

Construct one-way function (OWF) from well-studied and average-case hard problems.

Then create the thriving world of cryptography based on OWF.

“Science wins either way” ——Silvio Micali

There is a PRG candidate from the average-case hardness of subset-sum.

**A PRG Candidate from the average-case hardness of Subset-sum:**

$G(a_1,\dots,a_n,x_1,\dots,x_n)=(a_1,\dots,a_n,\sum_{i=1}^n x_i a_i \mod{2^{n+1}})$

where $a_i$ are random $(n+1)$-bit numbers, and $x_i$ are random bits.

Nevertheless, there exists a better way to construct PRG.

**Beautiful Function: **

If $G$ is one-way function, then $G$ is a PRG.

If lattice problems are hard on the worst-case, $G$ is a PRG.

「Cryptography-MIT6875」: Lecture 2