浙大暑期密码学课程|可证明安全基础
视频地址：浙大暑期Crypto课程-Provable Security Basics（ 上）、浙大暑期Crypto课程-Provable Security Basics（ 下）
本次课程由浙江大学的张秉晟老师带来，主要讲解密码学中的可证明安全理论基础。
现代密码学在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可以在多项式时间内被规约到特定假设，若该假设是困难的，则说明被证明的密码方案很难被攻破，就具有安全性。
下图主要介绍了如何将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问题的敌手攻击能力和博弈描述。
张老师最后给出了详细的推导和证明过程，详情请见视频。