可证明安全初步（Provable Security Basics）

Speecher: Bingsheng Zhang

这一系列的课程，为了介绍一些基础，弥补一些上密码学课和看论文的Gap。

历史上的密码学是art，就像鲁班锁，看着很精妙，但是没有证明。

1970s以来，逐渐发展成Science。

定义和模型一直在改，但是方法论和安全性证明是一样的。

传统的应用：

机密性（加密）
完整性（MAC）
验证（签名）

现代的原语：

区块链
FHE
ZK
SMPC
ABE
functional encryption
indistinguishability obfuscation

现代密码学的核心准则：可证明安全。主要分为三步：

准确地定义威胁模型，即：什么是安全？
- “什么是安全”的正式模型和定义，比如敌手能做什么、不能做什么…
提出构造
- 算法、协议、scheme
写一个正式的proof（在这系列课程中，基本就是reduction）
- 在什么样的威胁模型下，如果某个假设成立，那么构造是安全的（除了极少数的，比如one-time-pad，都会有假设，即使one-time-pad，也会对随机性有假设）。
- 假设的说明要清晰、没有歧义。

最后我们会得到四个东西：

安全性定义
假设
协议
证明

可证明安全最后也可能不安全：你的假设可能被攻破、威胁模型可能和实际不同（就像你锁了门，但是没关窗）。

1976：DH密钥协商（HTTPS-TLS-DH），这一次我们将部分涉及DH的安全性。为什么DH是安全的？基于什么（假设）是怎么样安全的？

1977：RSA（比如用于电子护照的签名）。

我们以DH介绍可证明安全的初步。

Zhang：一般自己别造假设，follow一些经典假设就够了，否则，虽然也叫可证明安全，但是会被challenge，因为自己对密码学领域的理解并没有那么牛逼。但是，密码学界的一些新突破，比如Gentry（2009）的FHE，就假设了理想格，给了一个构造。但是分析这个假设就可以出三大密。

Textbook RSA 是不安全的

Textbook RSA：就是RSA在课本里呈现的形态，选个 $P, Q$ ，乘起来、再构造公钥私钥blabla。

Textbook RSA它并不是一个加密算法，而是一个带陷门的one-way permutation。

几年前，有人发现QQ浏览器用的Textbook RSA进行加密，于是写了一篇文章批判一番。

后期，很多学校课程都在说Textbook RSA在各种情况下是不安全的。那RSA怎么用呢？

比如说，加PKCS1.5的padding。RSA本身不是公钥加密算法，

我们给明文加padding，再做一个trapdoor one-way permutation，这就成了一个加密算法。

至于这个算法怎么安全，比如CPA/CCA安全，这就看具体的padding方法和proof。

Warm-up：单向函数(One-way function)

密码学中最基础的一个假设：假设单向函数存在。

实际上，我们不知道单向函数是不是真的存在。

（更事实上地，整个现代密码学的基础就基于假设）

函数 $\{0,1\}^n \rightarrow \{0,1\}^m$ 是单向的，如果有：

$\forall x, f(x)$ 是多项式时间可计算的。
难以反向：对于所有的概率多项式时间(probabilistic polynomial-time, PPT)算法 $\mathcal A$ ，有
$P[Invert_{\mathcal A, f}(n) = 1] < \epsilon(n)$
（换句话说，玩下面这个Game时，赢的概率可以忽略）

其中 $\epsilon$ 是一个negligible函数， $n$ 在此定义为安全参数。

其中， $Invert_{\mathcal A, f}(n)$ 是一个game，包含以下四步：

选择随机 $\leftarrow \{0,1\}^n$
计算 $y = f (x)$
获取 $\leftarrow \mathcal A(1^n, y)$ （给敌手 $y$ 和安全参数，让它选择 $x^{'}$ ）
当且仅当 $f (x^{'}) = y$ 时返回1（win）

关于game：

game有一个challenge（考官）和一个adversary（考生）。考官出一些题来考试(play game)，通过表现来判断考试是否通过。

为什么说game是考试呢？因为规定了能力（考生能看见什么不能看见什么）、时间（多项式时间）etc

注意一些细节：

$\mathcal A$ 不要求回答一个完全正确的 $x$ ，只要回答一个原像 $x^{'}$ 就OK。
$x$ 要在足够大的域里选（安全参数规定的域里选）。

一个等价的定义：

$P_{x \leftarrow \{0,1\}^n}[\mathcal{A}(1^n, f(x)) \in f^{-1}(f(x))]\leq \epsilon(n)$

但是绝大多数的game很难这么简洁地写，因为很多game的操作很复杂，在一行里写清楚可能性不大。

一些练习。假设 $f (x)$ 是一个安全的单向函数，那么

$f (m)$ 能不能做 $m$ 的一个one way commitment?

不能。它的问题是： $f (x)$ 是单向函数的话，要求 $\leftarrow \{0,1\}^n$ ，但是这里 $m$ 没说是uniformly random的。比如石头剪刀布，plaintext的选项只有三种可能性，我们不会拿 $m$ 做commitment，因为它就没有hiding的性质——试一试 $f (剪刀)$ 、 $f (石头)$ 、 $f (布)$ 就什么都知道了。

在微信对话框里如何在不引入可信第三方的情况下相互（公平地）玩石头剪刀布？这就要用到commitment。

$f (m ∣∣ r)$ 是不是 $m$ 的一个commitment？其中 $\leftarrow \{0,1\}^{256}$ 、 $m ∣∣ r$ 是concatenate操作。答案是否定的。根据前面game的定义，不能exactly找到 $x$ ，但是这个game没说不能精确找到其中的哪些位。

同样的scheme，你用不同的假设（比如把上述game中的one-way function 换成 random oracle），有的时候能做出来，有的时候做不出来。

离散对数问题（一般基于一个group generator $\mathcal G$ ）

这个 $\mathcal G$ ，你给它一个安全参数，它就生成一个群并返回。

但是在现实中不是这么用的。你自己生成一个security group，审稿人不一定认。现实中大家一般用公开的group，比如椭圆曲线。

设 $\mathcal G$ 是一个通用的、多项式时间的、群生成算法。那么向 $\mathcal G$ 传入安全参数 $1^n$ ，生成一个循环群 $\mathbb G$ （乘群），输出 $\mathbb G$ 的阶 $q$ ， $q$ 的位数是 $n$ ，一个生成元 $\in \mathbb G$ 。

离散对数假设 $DLog_{\mathcal{A,G}}(n)$ 如下：

生成 $(\mathbb G, q, g) \leftarrow \mathcal G(1^n)$
随机选取 $\leftarrow \mathcal G$ （这一步隐含这个群应该是efficiently samplable，当然不这么做也行，可以选取一个 $y$ ，返回 $g^y \leftarrow \mathcal G$ ）
采样 $\leftarrow \mathcal A(\mathbb G, q, g, h)$
当且仅当 $g^x = h$ 时返回1