# 「Cryptography-Dan」:Stream Cipher 3

Stream Cipher的第三篇文章。

# Negligible and non-negligible

In practice: $\epsilon$ is a scalar and

• $\epsilon$ non-neg: $\epsilon \geq 1/2^{30}$ (likely to happen over 1GB of data)
• $\epsilon$ negligible: $\epsilon \leq 1/2^{80}$ (won’t happen over life of key)

In theory: $\epsilon$ is a function $\varepsilon: Z^{\geq 0} \rightarrow R^{\geq 0}$ and

• $\epsilon$ non-neg: $\exists d: \epsilon(\lambda)\geq 1/\lambda^d$ ($\epsilon \geq 1/\text{poly}$, for many $\lambda$ )
• $\epsilon$ negligible: $\forall d, \lambda \geq \lambda_{d}: \varepsilon(\lambda) \leq 1 / \lambda^{d}$ ( $\epsilon \leq 1/\text{poly}$, for large $\lambda$ )

[0]（理论中，这个还不太理解，待补充。）

# PRG Security Defs

Let $G:K\longrightarrow \{0,1\}^n$ be a PRG.

Goal: define what it means that

[ $k\stackrel{R}{\longleftarrow} \mathcal{K}$ , output G(k) ] is “indistinguishable” from [ $r\stackrel{R}{\longleftarrow} \{0,1\}^n$ , output r] .

【使得PGR的输出和真随机是不可区分的】（ $\stackrel{R}{\longleftarrow}$ 的意思是在均匀分布中随机取）

## Statistical Tests

Statistical test on ${0,1}^n$ ：有一个算法A，$x\in{0,1}^n$ ,A(x) 根据算法定义输出”0”或”1”.

Example：

1. A(x)=1 if $| \#0(x)-\#1(x)|\leq 10\cdot\sqrt{n}$

【期望串中0、1的数目差不多，这样look random】

2. A(x)=1 if $|\#00(x)-\frac{n}{4}\leq10\cdot\sqrt{n}$

【期望Pr(00)=1/4 ,串中00出现的概率为1/4，认为是look random】

3. A(x)=1if max-run-of-0(x) < 10·log(n)

【期望串中0的最大游程不要超过规定值】

Let G: $k \rightarrow \{0,1\}^n$ be a PRG and A a stat. test on ${0,1}^n$

【G是一个PRG，A是一个对01串的统计测试】

Define: the advantage of statisticaltest A relative to PRG G Adv$_\text{PRG}[A,G]$

$\text{Adv}_\text{PRG}[A,G]=|Pr[A(G(k))=1]-Pr[A(r)=1]|\in[0,1]$ , $k\stackrel{R}{\longleftarrow} \mathcal{K}, r\stackrel{R}{\longleftarrow}\{0,1\}^n$

【定义：Adv$_\text{PRG}[A,G]$ 为统计测试A对于PRG G的优势为统计测试以PRG作为输入输出为1的概率 减去 统计测试以truly random string 作为输入输出为1的概率】

In cryptography, an adversary’s advantage is a measure of how successfully it can attack a cryptographic algorithm, by distinguishing it from an idealized version of that type of algorithm.Note that in this context, the “adversary” is itself an algorithm and not a person. A cryptographic algorithm is considered secure if no adversary has a non-negligible advantage, subject to specified bounds on the adversary’s computational resources (see concrete security).

e.g.1 : A(x) = 0，统计测试A对PRG的任何输出都输出0，则Adv[A,G] = 0.

e.g.2 :

G: $k \rightarrow {0,1}^n$ satisfies msb(G(k))=1 for 2/3 of keys in K.

Define statistical test A(x) as : if[ msb(x)=1 ] output “1” else output “0”

【PRG G(k)的2/3的输出的最高有效位是1，定义统计测试A(x),输入的最高有效位为1输出1，否则输出0】

msb: most significant bit,最高有效位。

## Secure PRGs: crypto definition

Def: We say that G: $k \rightarrow {0,1}^n$ is secure PRG

if $\forall$ “eff” stat. tests A : Adv$_\text{PRG}$ [A,G] is “negligible”.

### Easy fact: a secure PRG is unpredictable

suppose A is an efficient algorithm s.t. $\text{Pr}_{k\stackrel{R}{\longleftarrow}\mathcal{K}}[A(G(k))|_{1,...,i}=G(k)|_{i+1}]>\frac{1}{2} + \epsilon$ for non-negligible $\epsilon$ .

【 算法A是一个有效的预测算法， $\text{Pr}_{k\stackrel{R}{\longleftarrow}\mathcal{K}}[A(G(k))|_{1,...,i}=G(k)|_{i+1}]>\frac{1}{2} + \epsilon$ , $\epsilon$ 是不可忽略的值，即A能以大于1/2的概率推测下一位。】

Define statistical test B as: B(x)=1 if $A(x|_{1,...,i})=x_{i+1}$ , else B(x)=0.

【定义一个统计测试B，如果预测算法A预测下一位正确输出1，否则输出0】

• $r\stackrel{R}{\longleftarrow}\{0,1\}^n$ : Pr[B(r) = 1] = 1/2
• $k\stackrel{R}{\longleftarrow}\{0,1\}^n$ : Pr[B(G(k)) = 1] = 1/2+ $\epsilon$
• Adv$_\text{PRG}$[B,G] = |Pr[B(r)=1] - Pr[B(G(k))=1] | > $\epsilon$

Adversary 能以 $\epsilon$ 的优势区分PRG和random，因此PRG 不安全。

### Thm(Yao’82): an unpredictable PRG is secure

G: $k \rightarrow {0,1}^n$ be PRG

“Thm“ : if $\forall i \in$ {0,…, n-1} PRG G is unpredictable at pos. i then G is a secure PRG.

【定理：如果在任何位置PRG都是不可预测的，那么PRG就是安全的】

Proof：

• A: 预测算法： $\forall i \quad\text{Pr}_{k\stackrel{R}{\longleftarrow}\mathcal{K}}[A(G(k))|_{1,...,i}=G(k)|_{i+1}]=\frac{1}{2}$
• B:统计测试： B(x)=1 if $A(x|_{1,...,i})=x_{i+1}$ , else B(x)=0.
• Adv$_\text{PRG}$[B,G] = |Pr[B(r)=1] - Pr[B(G(k))=1] | = 0

If next-bit predictors cannot distinguish G from random then no statistial test can!

【next-bit predictor指用预测算法的统计测试】

e.g.

Let G: $k \rightarrow {0,1}^n$ be PRG such that from the last n/2 bits of G(k) it is easy to compute the first n/2 bits.

Is G predictable for som i $\in$ {0, …, n-1} ?

: Yes.当n=2时，可以预测出第一位。

## More generally: computationally indistinguishable

Let P1 and P2 be two distributions over ${0,1}^n$

Def : We say that P1 and P2 are computationally indistinguishable (denoted $P_1\approx_p P_2$)

If $\forall$ “eff” stat. tests A $\left|\text{Pr}_{x\leftarrow_{P_1}}[A(x)=1]-\text{Pr}_{x\leftarrow_{P_2}}[A(x)=1]\right|<\text{negligible}$ .

【P1,P2都是01串上的两个分布，且对任意的有效统计测试满足上式，则认为P1和P2两个分布在计算上不可区分，记做$P_1\approx_p P_2$】

# Semantic Security

What is a secure cipher?

attacker abilities: obtains one ciphertext(唯密文攻击)

Possible security requirements：

1. attacker cannot recover secret key.

attacker不能恢复密钥。

E(k,m)=m直接输出明文，这个算法满足条件，但显然不安全。

2. attacker cannot recover all of plaintext.

attacker对所有的明文都不可恢复。

E(k, m0||m1) = m0||k $\oplus$ m1,该算法泄漏了一半的明文，不安全。

3. Shannon’s idea: CT should reveal no “info” about PT.

## Recall Shannon‘s perfect secrecy

A cipher $(E,D)$ over $\mathcal{(K,M,C)}$ has perfect security if $\forall m_0,m_1 \in \mathcal{M}\ (|m_0|=|m_1|) \quad \text{and} \quad \forall c\in \mathcal{C}$

$$Pr[E(k,m_0)=c]=Pr[E(k,m_1)=c] \qquad \text{where} \ k\overset{R}{\longleftarrow}\mathcal{K}$$

Let (E,D) be a cipher over (K,M,C)

• 上图中的定义就是perfect security的定义，密钥加密m0和m1的分布完全相同。

引入上文中的computationally indistinguishable（计算不可区分）的概率放宽条件，得到下面的定义。

• 密钥加密m0和m1的分布计算上不可区分。

## Semantic Security for OTP

### attack game

Attack Game[3]: For a given cipher $\mathcal{E}$ = (E, D), deﬁned over (K, M , C), and for a given adversary $\mathcal{A}$ , we deﬁne two experiments, Experiment 0 and Experiment 1. For b = 0, 1, we deﬁne

【定义一个adversary $\mathcal{A}$，两个实验也对应两个challenger，实验定义如下】

Experiment b:

• The adversary computes m0 , m1 ∈ M , of the same length, and sends them to the challenger.

• The challenger computes $k\stackrel{R}{\leftarrow}\mathcal{K}$, $c\stackrel{R}{\leftarrow}E(k,m_b)$, and sends c to the adversary.

• The adversary outputs a bit $\hat{b}\in$ { 0, 1 } .

【adversary收到c，猜测c是加密m0还是m1的，输出 $\hat{b}$ 】

for b=0,1 $W_b$ = [event that $\mathcal{A}$ output 1 in experiment b].

【定义事件 $W_b$ 为在实验EXP(b)中$\mathcal{A}$ 输出1】

Def： $\mathcal{A}$‘s semantic security advantage with respect to $\mathcal{E}$ as

$$\operatorname{Adv_{SS}}[\mathcal{A}, \mathcal{E}]:=\left|\operatorname{Pr}\left[W_{0}\right]-\operatorname{Pr}\left[W_{1}\right]\right|$$

【定义adversary $\mathcal{A}$ 对于cipher $\mathcal{E}$ 的语意安全优势为上式】

Note that in the above game, the events W0 and W1 are deﬁned with respect to the probability space determined by the random choice of k, the random choices made (if any) by the encryption algorithm, and the random choices made (if any) by the adversary. The value Advss[ A , E] is a number between 0 and 1.

### semantic security

Defsemantic security：A cipher $\mathcal{E}$ is semantially secure if for all efficient $\mathcal{A}$ , the value $\operatorname{Adv_{SS}}[\mathcal{A}, \mathcal{E}]$ is negligible.

### example 1

Suppose efficient A can always deduce LSB of PT from CT.

【假设算法A总能从CT中推断出PT的最低有效位】

adversary B对于cipher $\mathcal{E}$ 的优势是： $\operatorname{Adv_{SS}}[\mathcal{B}, \mathcal{E}]:=\left|\operatorname{Pr}\left[\text{EXP}(0)=1\right]-\operatorname{Pr}\left[\text{EXP}(1)=1\right]\right|=|0-1|=1$

### example 2: OTP

OTP虽然不实用，但是具备perfect security，下面来证明OTP也具有semantic security。

OTP的perfect security的性质是 $Pr[E(k,m_0)=c]=Pr[E(k,m_1)=c] \qquad \text{where} \ k\overset{R}{\longleftarrow}\mathcal{K}$ ，k和任意m异或都是均匀分布，因此上图中的 $\left\{\mathrm{E}\left(\mathrm{k}, \mathrm{m}_{0}\right)\right\} =\left\{\mathrm{E}\left(\mathrm{k}, \mathrm{m}_{1}\right)\right\}$ 是同分布。

For all A : $\operatorname{Adv}_{\operatorname{ss}}[A, \text { OTP }]=\mid \operatorname{Pr}\left[A\left(\mathbf{k} \oplus m_{0}\right)=1\right]-\operatorname{Pr}\left[A\left(\mathbf{k} \oplus m_{1}\right)=1\right]|=0$

## Stream Ciphers are semantically secure

Thm: Let G: $k \rightarrow {0,1}^n$ is a secure PRG $\Rightarrow$ stream cipher E derived from G is semantic secure.

### Proof: intuition

（上左上右下左下右：图1234，G(k):PRG 的输出， r: truly random string）

### Proof

Let A be a sem. sec. adversary.

for b = 0,1 Wb = [event that b’=1]

$\operatorname{Adv}_{\operatorname{SS}}[A,E]=|\text{Pr}[W_0]-\text{Pr}[W_1]|$

for b = 0,1 Rb = [event that b’=1]

$\operatorname{Adv}_{\operatorname{SS}}[A,OTP]=|\text{Pr}[R_0]-\text{Pr}[R_1]|=0$

1. 根据OTP的semantic security ，已经得到 $|\text{Pr}[R_0]-\text{Pr}[R_1]|=\operatorname{Adv}_{\operatorname{SS}}[A,OTP]=0$ ，所以Pr[R0]=Pr[R1]。

2. 因为G是secure PRG，所以 $\exists$ adversary B满足 $|\text{Pr}[W_b]-\text{Pr}[R_b]|=\operatorname{Adv}_{\operatorname{PRG}}[B,G]$ ,如下图：

# Summary

secure PRG 就是计算上无法区分G(k)的输出和truly random string。

semantic secure 就是从CT中无法得到PT的任何信息，在计算上无法区分任意m0和m1的加密结果。

# reference

1. Negligible, super-poly, and poly-bounded functions.(Book p28)