Reference & Analysis#

《Introduction to Modern Cryptography》

Introduction-to-modern-cryptography/现代密码学简介.pdf

Contest#

期中#

Cheatsheet#

需要证明的部分我会用🙈标出来

期中all in one paper#

*Intro of Crypto#

关于 Cryptography

kryptós /kryp.tós/ → /krypˈtos/ → /kripˈtos/ 表示 “hidden, secret”

把很多”不断加深的概念放在这里”

观念变化#

• Gen,Enc,Dec不可泄露->可泄露
  • August Kerchoff 1884 密码系统只依赖密钥，方法可以公开
  • “攻击者不能获取额外信息”（关注某些位，长度这些额外信息）
• 从Shannon和Perfect认为攻击者无限强，后来都认为$\mathcal A$是PPT的
  • 不要求绝对均匀
• 从知识先于零知识到零知识脱离于知识
  • Zero-Knowledge Proof, ZKP，陈述某种陈述的正确性，不泄漏任何陈述本身信息
  • 协议中重要作用
• 传统密码学
  • 天才cracked game
  • Caesar Cipher (Gen无随机性)
  • Substitution Cipher 改成随机排列，那么我们引入

凯撒密码和变形

原则#

• 可用性
  • $\mathbb P[\mathrm{Dec}(\mathrm{Enc}(x))=x]=1$
• 正确性
• 安全性

对我们关注的Provable Security

• Precise Definition of Security
• Mathematic Assumpation
• Security Proof——Reduction

Crypto Principles#

基础款加密系统定义

$\{\mathrm{Gen,Enc,Dec,M,K}\}$

• $\mathrm{GEN}(srand)=sk$ (randomized from K)
• $\mathrm {ENC}(sk,M)=C$ (R/D)
• $\mathrm{DECO}(sk,C)=D$ (deterministic)

Secure Multi-Party Computation#

计算一个关于秘密输入 $x_1, \dots, x_n$ 的函数 $f$ 。在计算 $f(x_1, \dots, x_n)$ 时，各方希望在不泄露任何额外信息的情况下完成计算，包括各方的秘密输入。针对 f 的 MPC 协议 $\pi$ 具有以下属性：

• 正确性 (Correctness)：执行协议 $\pi$ 后，所有参与方都能得出 $f(x_1, \dots, x_n)$ 的值。
• .完美的、诚实但好奇的 t -串通安全性 (t-security)：设 $[n]$ 表示参与方集合 $\{1, \dots, n\}$ ， $t$ 表示串通的对手方数量。

对于所有大小为 t 的集合 $S \subseteq [n]$ ，存在一个模拟器 $\text{Sim}$ ，使得对于所有 $x_1, \dots, x_n$ ：

$\text{View}_S(\pi(x_1, \dots, x_n)) \equiv \text{Sim}(x_S, f(x_1, \dots, x_n))$

其中，$\text{View}_S(\pi(x_1, \dots, x_n))$表示参与方 $i$ $\in$ $S$ 在协议执行期间的可观测状态。

非诚勿扰的例子（？）

两个人出示0/1状态，如何设计协议使得两个人在诚信情况下仅能获取是否同为1的结果（舔狗如何保护自己）

设计表格

	A	B
1	01	10
0	10	01

然后按照 sa|1|sb 的方式连接成环

容易发现，只有11的情况是有长度为3的1连续段的

Shannon/Perfect Privacy#

介绍香农/完美安全互化，并陈述其局限性。本质是基于纯随机的等价概率分布的生成。

Shannon vs Perfect#

两个形式

Shannon $\forall t,c,\mathbb P_{m\leftarrow D}[m=t]=\mathbb P_{m\leftarrow D,sk\leftarrow \mathrm{Gen}}[m=t\mid \mathrm{Enc}(sk,m)=c]$

Perfect $\forall m_1,m_2,\mathbb P_{sk\leftarrow \mathrm{Gen}}[\mathrm{Enc}(sk,m1)=c]=\mathbb P_{sk\leftarrow \mathrm{Gen}}[\mathrm{Enc}(sk,m2)=c]]$

Theorem

上述定义等价🙈

Hint:全概率展开

有一个推论

Shannon’s theorem

假设$|M|=|K|=|C|$，则我们有完美安全等价于$k$概率均匀分布,$\mathrm{Enc}(k,m)=c$，对于给定的$m,c$,$k$是唯一的

One Time pad#

显然有$\mathbb P_{sk}[sk\oplus m=c]=\mathbb P_{sk}[sk=m\oplus c]$,这里出一个问题，长密钥保护短内容

OTP是Shannon-secure的

Theorem

香农安全必定有$|K|\geqslant |M|$🙈

Hint:从映射不完全性出发

One-way function#

Turing machine 假设

$\mathcal M$是一个图灵机，$T(\mathcal M)$表示$\forall \mathbf x\in \{0,1\}^*$ ，$\mathcal M$会在$T(|x|)$内停下

$\mathcal A$adversary ,其满足PPT(随机性多项式时间)，即攻击力有限

最后强调一下，$n$是数据量规模，不是数据个数，大数的贡献是位数

• Worst one-way function

  • easy to compute $\exist \mathcal M(P),\forall x\in\{0,1\}^*,\mathcal M(x)=f(x)$
  • hard to invert, 不存在 $\mathcal A$, $\mathbb P[A(f(x))=t\mid f(x)=f(t)]=1$

• strong one-way function(默认均指这个)

  • $\forall \mathcal A^r,\mathbb P_{x,r}[A(f(x))=t\mid f(x)=f(t)]\leqslant \mathtt {negl}(n)$

• *weak one-way function(其实不管，比较复杂，OWF是一个family)

  • $\forall \mathcal A^r,\mathbb P_{x,r}[A(f(x))=t\mid f(x)=f(t)]\leqslant 1-\frac{1}{\mathrm{poly}}$

eg

设$\mathcal P_n$ 表示 $\mathcal P \cap [2^{n-1},2^{n}-1]$即二进制为$n$位的素数集合

$f:\mathcal P_n\times \mathcal P_n\to \{0,1\}^{2n}$为一个OWF

由素数定理$\pi(n)\approx\frac{n}{\ln n}$

$|\mathcal P_n|=\pi (2^n)\approx\frac{2^n}{n}$

$$\begin{align*} \forall \mathcal A^r,\mathbb P_{x,r}[\mathcal A(f(x))=t\mid f(x)=f(t)]&=\mathbb P_{(p,q)\xleftarrow{\$}\mathcal P_n\times \mathcal P_n}[\mathcal A (z)=(p',q')\mid p'q'=pq=z]\ \\&=\mathbb P_{(p,q)\xleftarrow{\$}\mathcal P_n\times \mathcal P_n}[\mathcal A (z)=pq]=\mathtt {negl}(n) \end{align*}$$

也即大数分解的概率

这里张聪上课说错了，不能直接用素数密度定理直接说明这个OWF性质

换一个

$g:\mathcal \{0,1\}^n \times \{0,1\}^n\to \{0,1\}^{2n}:g(x,y)=xy$

这个显然就不是strong OWF

我们取$\mathcal P_n\times \mathcal P_n\subseteq \{0,1\}^n\times \{0,1\}^n$，这部分选取概率为

$\mathbb P[(x,y)\in \mathcal P_n\times \mathcal P_n]=\frac{|\mathcal P_n|^2}{2^{2n}}\approx\frac{1}{4n^2}$

则

$$\mathbb P_{(p,q)\xleftarrow{\$}\{0,1\}^n\times \{0,1\}^n}[\mathcal A (z)=(p',q')\mid p'q'=pq=z]\leqslant 1-\frac{1}{4n^2}$$

这里我跳步了

hc

给定一个函数 $f$ ，若存在一个函数 $\text{hc} : \{0,1\}^* \rightarrow \{0,1\}$ 满足以下条件，则称 \text{hc} 是 f 的hard-core predict：

• 可计算性：

  $$\text{hc}$$

  可以在多项式时间内计算。

• 难以预测性：对于任意概率多项式时间算法

  $$\mathcal A$$

  ，存在一个可忽略函数

  $$\text{negl}(n)$$

  ，使得

$$\mathbb P_{x \leftarrow {0,1}^n} \left[ \mathcal A(1^n, f(x)) = \text{hc}(x) \right] \leq \frac{1}{2} + \text{negl}(n)$$

PRG#

stream password

魔改OTP

$$\begin{align*}\mathrm{Gen}(1^n)&\to seed \overset{\$}{\leftarrow} \{0,1\}^n\\\mathrm{Enc}(seed,m)&\to sk\oplus m\\\mathrm{Dec}(seed,c)&\to sk\oplus c\end{align*}$$

这里需要一个混淆seed和sk的东西

引入一个补充概念

EAV-secure/Semantic Security

$$\forall \mathcal A^r,i,\mathbb P[\mathcal A(1^n,\mathrm{Enc}(sk,m))=m_i]\leqslant \frac{1}{2}+\mathtt {negl}(n)$$

实质上就是我们不能够通过对于加密结果的分析获取对于数据任意字段的信息

简单描述下PRG基于的游戏过程

一句话就是A无法依赖ch给出的加密范式，区分自己提供的(也就是任意的)密文加密后的结果

给予一些额外的数学原理我们右

EVA-another definition

$\pi = (\mathrm{Enc},\mathrm{Dec})$ os EVA iff:

$$\forall \mathcal A^r,f:\{0,1\}^n\to \{0,1\},\mathcal D,\exist \mathcal A' \\\left|\mathbb P[\mathcal A(1^n,\mathrm{Enc}(sk,m))=f(m)]-\mathcal A'(1^n)=f(m)\right|\leqslant \mathtt {negl}(n)$$

依赖上述过程我们可以给出PRG的标准定义

PRG def

设 $G:1^n\to 1^{l(n)}$ ，则其为一个伪随机生成器的充要条件为(这里我为了一致性，懒得区分这里的$\mathcal D$和$\mathcal A$了，假设你乐意可以自行区分)

$$\forall \mathcal A^r:\{0,1\}^{l(n)}\xrightarrow{PPT} \{0,1\},\left|\Pr_{s \leftarrow \{0,1\}^n, r \leftarrow G(s)}[\mathcal A(r)=1]-\Pr_{r \xleftarrow{\$}\{0,1\}^{l(n)}}[\mathcal A(r)=1]\right| \leq \mathtt{negl}(n)$$

这里有一个外包任务，我们可以依赖EVA-secure的游戏形式构造reduction

在PRG中，我们往这个有些一半丢均匀分布，一般丢$G(x)$生成的分布，$\mathcal A'$的优势可忽略

PRG chain(hybrid argument)#

这里我们先给出尽量严谨的论述

PRG可扩展定理

假设$G:\{0,1\}^n\to \{0,1\}^{n+1}$，则我们可以对任意$\mathrm{poly}(n)$生成$\hat G :\{0,1\}^n\to \{0,1\}^{\mathrm{poly(n)}}$

这里我不知道为什么老师要取$\mathrm {poly}(n)=2n$，也不知道有什么特殊性，注意这里千万不要认为这个迭代过程可以无限，换句话这个迭代过程的次数关于$n$为常数

上述证明称为 hybrid argument 这里不做解释 (P282)

Multi-message-secure#

容易发现我们之前构造的流密码，缩短了sk但是还是只能一次一密，我们可以利用异或的可逆性构造冲撞，获取额外信息，考虑下面的游戏

当我们提供来选择的消息为阵列时，情况有所不同

下面给出了一种方案

在这个意义上，我们泄露了一部分$sk'$,达成了安全性

IND-CPA#

IND-CPA:indistinguishabable chosen-plaintext-attacks

从这个出发

• Initial Phase

然后执行多轮

这记为Phase1

• challaenge Phase(注意这种二择一的只有一次)

• Phase2

最后猜$b'$

下面我们考虑说明IND-CPA与Multi-Msg-Secure 的关系

回顾Multi-Msg $\mathsf {Privk}^{\mathrm{mult}}_{\mathcal A,\mathrm{II}} (n)$

在本题中的IND-CPA范式实际上可以用更强形式表示 CPA2

CPA2→Multi-Msg S显然

每次都可以问$m_{i,0/1}$然后回答$\mathrm{Enc}(m_{i,b})$

换句话对这个CPA，其问题都形如

CPA2→CPA可以直接将二择一的问变成确定问，这个reduce是显然的

CPA→CPA2是构造一个hybrid argument

1个power怎么扩展

用CPA来勾连b=0到b=1

这里我感性的描述下这个Game set

Game0:

分别问，$(m_{10},m_{11}),\cdots(m_{i0},m_{i1})$，全部回答$b_i=0$

Game1:

分别问，$(m_{10},m_{11}),\cdots(m_{i0},m_{i1})$，除了第一个全部回答$b_i=0$

Game2:

分别问，$(m_{10},m_{11}),\cdots(m_{i0},m_{i1})$，除了前两个全部回答$b_i=0$

…

一句话，你最后是希望区分全0和全1

上面$Game_i$和$Game_{i+1}$本质上就是前缀的1多了一个一位，能利用CPA来分界搭桥（新引入的一位是challange phase），最后就能搭一个长桥

PRFs#

对于

我们有$|\mathcal F|=(2^n)^{2^n}$,这里我们希望能够随便选取一个$F_I$，但显然这个随机生成的代价太大，这里我们引入

PRFs

$\mathcal F_I$为一个被$I$索引的映射集合（题库），其是伪随机的当且仅当游戏成立

ch首先把$\mathcal F_I$给A

然后ch自己在$I$里面选一个sk,$b$随便定

然后A反复问$m_1$,ch根据$b$反复回答$F_{sk}(m_i)$或$y_i$

$\mathbb P[b=b']=\frac{1}{2}+\mathtt{negl}(n)$

更形式化

IND-CPA 2 PRFs#

PRFs 2 IND-CPA#

对Reduction层面

ch给R $\mathcal F_I$，自己生成$sk$

R基于定义生成$\mathrm{Gen.Enc,Dec}$给A

A丢回去$m_1$,R顺带给出$r_1$,ch回答$str_1$

然后R→$(r_1,str_1\oplus m_1)$→A

…

来A发出一次灵魂challenge

给$m_0^*,m_1^*$，然后返回一个

$\mathrm{Enc}(m_d^*)$,猜测正确与否对应$b'=0/1$,再回去对照$b$

PRG 2 PRFs#

还是hybrid argument

相当于你需要从$[0,2^n)$全$0→[0,2^n)$全1

首先我们假定$G$是PRG

Game0G

Game1但是层1反

Game1但是层1,2反

…

这里一个问题是Game n-1这个间隔有$2^{n-1}$，是不能用hybrid argument

显然我们是求解具体一个$\mathcal O(q)$的发问，因此完善这部分即可

PRFs 2 PRG#

这个是显然的，一位一位即可

PRPs#

PRPs

$\mathcal P_I$为一个被$I$索引的映射集合（题库），其是伪随机的当且仅当游戏成立

ch首先把$\mathcal P_I$给A

然后ch自己在$I$里面选一个sk,$b$随便定

然后A反复问$(m_0,\mathcal P)$或者$(m_1,\mathcal P^{-1})$，然后A这边根据问题回答

$\mathbb P[b=b']=\frac{1}{2}+\mathtt{negl}(n)$

形式化定义如下

Cipher-Block-Chaining#

我们希望节省sk生成的开销

一个循环利用的想法应运而生

但显然这里$F$用到了异或可逆的性质，因此更一般的我们需要给出PRPs，实现$(r,P_k(m,r))\leftrightarrow m$

• CBC
• OFB
• CTR

MAC#

这部分我们暂时不看机密性，我们开始关注可信性

真实的数字签名没有sk

攻击者必须仿造$(m',\tau')$

unforgeability chosen message attack（UCMA）

UCMA模型的安全性通常与数字签名的存在性不可伪造性（Existential Unforgeability）相关联。如果一个数字签名方案在UCMA模型下是安全的，那么可以认为该方案具有EUF-CMA（Existential Unforgeability under Chosen Message Attacks）的安全性

整体思路是设计

$\mathbb P[A~wins]=\mathbb P[\mathrm{Verify(m^*,\tau^*)}=1]=\mathtt{negl}(n)$

注意$\mathcal A$这次开挂了，相当于本地可以一直跑，跑好了才找人

密码学作业#

第一次作业 One Time Pad & OWF & PRG#

这一节作业没有更新勘误，因此看个大概就行，懒得改成提交的版本

Question 1: A Flawed One-Time Pad#

Description

Consider a variant of the one-time pad with message space $\{0, 1\}^n$, where $n$ is an odd integer, and the secret key space is restricted to all $n$-bit strings with an even number of 1’s. Construct an efficient adversary that compromises perfect secrecy.

Answer:

Let the key set be denoted by $K$: $|K|=\sum _{i=0}^{n-1}\binom{n}{i}=2^{n-1}$

For any $m_1$ with an odd number of 1’s and any $m_2$ with an even number of 1’s, since $n$ is odd, we have

Similarly,

Thus, an adversary can determine the parity (odd or even) of the number of 1’s in the original message by examining the ciphertext $c$. This additional information compromises perfect secrecy.

Idea:

The original One-Time Pad encryption and decryption processes are defined as follows:

Under the condition that $sk$ is uniformly random, the probability of encrypting $m_1$ and $m_2$ to the same ciphertext $c$ is equal, i.e.,

However, the modification to the definition of $K$ leads to the issue where

Question 2: One Way Functions vs Pseudorandom Generators#

2.1#

Description

Let $G$ be a PRG that maps $n$ bits to $2n$ bits, prove that $G$ is a (strong) one-way function.

Solution:

The definition of a PRG is that for any algorithm $A$, the probability that $A$ can distinguish between the output of $G:\{0,1\}^n\to \{0,1\}^{l(n)}$ (in this problem, $l(n)=2n$) on a random input and a truly random string is negligible. Formally,

If $G$ is not a one-way function, there exists an efficient algorithm $\mathcal A$ that can invert $G$.

Idea:

Assume $G \in \text{PRG}[\{0,1\}^n \to \{0,1\}^{2n}]$ is not a one-way function, then there exists $\mathcal A_0$ such that

($G$ here is essentially the function $f$ in the definition).

In this scenario, consider

Then,

and

Thus,

Since $\frac{1}{\text{poly'}(n)} \neq \mathtt{negl}(n)$, this contradicts the initial assumption. Therefore, $G$ is a one-way function.

2.2#

Description

Given that $F$ is a one-way function, construct a function $G$ such that:

• $G$ is a one-way function.
• $G$ is not a pseudorandom generator (PRG).

Solution:

Directly provide the construction: Let

Construct

Here, $\text{concat}$ denotes the sequential concatenation of two binary sequences. In other words, $G$ appends a $1$ to the end of $F$‘s output.

Proof for OWF:

Since $F$ satisfies

If $G$ is not OWF, then there exists $\mathcal A_0:\{0,1\}^{l(n)+1}\to \{0,1\}^n,\text{poly}(\cdot)$ such that

Then we construct $\mathcal A'_0:{0,1}^{l(n)}\to {0,1}^{n} \mid \mathcal {A}'_0(r)=\mathcal A_0(\text{concat}(r,{\mathtt{1}}))$

$\mathcal A_0'$ satisfies

This contradicts the fact that $F$ is an OWF.

Proof for not PRG:

Construct

Then

Clearly, this contradicts the requirement for the PRG definition of being negligible.

In summary, the constructed $G$ is a One-Way Function but not a PRG.br