笔记分享|浙大暑期密码学课程：可证明安全基础

本篇笔记是张秉晟老师在浙江大学的暑期Crypto School的课证明安全基础课程的整理，可前往以下b站链接或点击下列视频观看完整课程。

浙大暑期Crypto课程-Provable Security Basics（ 上）

https://www.bilibili.com/video/BV1im4y1a7UH/?spm_id_from=333.999.0.0&vd_source=15b7926a3a203446fa868f18be9bc87e

浙大暑期Crypto课程-Provable Security Basics（ 下）

https://www.bilibili.com/video/BV1DX4y1p78V/?spm_id_from=333.788&vd_source=15b7926a3a203446fa868f18be9bc87e 

本次课程由浙江大学的张秉晟老师带来，主要讲解密码学中的可证明安全理论基础。

现代密码学在20世纪70年代末得到发展，密码学可以用于保证机密性，完整性和认证，并广泛用于多个现代密码学原语中，如零知识证明，全同态加密等。

可证明安全主要分为以下三个步骤，首先确定威胁模型，其次构造方案，最后给出一个正式的安全性证明。

公钥加密始于1976年Diffie和Hellman的论文，并提出了DH密钥交换/协商，当然DH密钥协商的安全性并非完全建立在离散对数上，RSA的安全性也不完全建立在factoring上。

在这里我们要讲述的是Textbook RSA是不安全的，一般而言，需要对消息进行padding才可以使用相应的RSA方案。

接下来介绍了单向函数，在单向函数中，多项式时间的敌手没法快速地找到单向函数输出所对应的原像，以下是单向函数的定义和安全性博弈(Game)。

假设f(x)是一个单向函数，但是f(m)和f(m||r)都不是关于m的承诺方案，因为commitment需要保证hiding和binding，可能该输出会泄露m中的部分比特信息，但如果f是一个随机预言机(random oracle)，那么f(m||r)是一个承诺。

以下是离散对数的定义，在离散对数中，给定一个生成元g和一个群元素g^x，敌手无法在多项式时间内求解x。

以下PPT介绍的是基于DH的密钥协商协议，分为初始化阶段，密钥生成阶段和生成会话密钥阶段。

我们在证明DHKE安全性之前，需要确定DHKE在哪个假设之下是安全的，我们需要先确定安全性和假设，然后使用规约的方式来证明DHKE可以在多项式时间内被规约到特定假设，若该假设是困难的，则说明被证明的密码方案很难被攻破，就具有安全性。

首先我们需要先定义安全目标，在协议/算法执行过程中，敌手是谁，敌手的攻击能力和确定敌手的攻击目标。

以下是关于密钥恢复(Key Recovery)算法的安全性的安全定义和安全模型。

下图主要介绍了如何将DH密钥协商协议的安全性规约到特定的困难问题，最简单的方式是将DH密钥协商协议的安全性规约到离散对数问题，但是目前并不知道怎么样将密钥协商协议的安全性进行规约。

所以我们需要引入计算性的DH问题，简记为CDH，下图介绍了CDH的敌手攻击能力和对应的博弈。

离散对数(DL)和CDH的关系如下图所示，当CDH是困难的，那么DL是困难的，同时如果DL问题是困难的，CDH问题在某些条件下才是困难的，我们将采用该定理来实现安全性的规约。

规约其实就是假设某个问题是困难的，那么能够规约到该问题的原问题也是困难的，CDH和DL问题也是这样的关系，下图描述了他们之间的关系。 

敌手无法获得密钥k，密钥协商只实现这种安全性是不够的，还需要敌手无法获得关于k的任何信息。

这种性质常见的典型体现是一次一密，即每次使用一个新的随机密钥k，对m进行异或操作，给定密文c和随机值，敌手很难在多项式时间内判断哪个是随机值，哪个是密文。

该定义对应了不可区分安全，即敌手在多项式时间内无法确定特定数据，哪个是随机选取的，哪个是正确生成的，如下图所示。

下图定义了不可区分（IND）的模型，同时为后续证明DH在DDH上实现IND安全先行进行了描述。

然后下图定义了决定性DH问题，简记为DDH，该问题相对于CDH而言，在安全性证明规约中更通用，下图是DDH问题的敌手攻击能力和博弈描述。

张老师最后给出了详细的推导和证明过程，详情请见视频。