浙江大学暑期密码学课程|可证明安全性基础

浙江大学暑期密码学课程|可证明安全性基础

视频地址：浙江大学暑期密码课程-可证明安全基础（第1部分）、浙江大学暑期密码课程-可证明安全基础（第2部分）

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

前言

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

现代密码学于 20 世纪 70 年代末发展起来。密码学可以用来保证机密性、完整性和真实性，并广泛应用于多种现代密码学原语，如零知识证明、全同态加密等。

证明安全

可证明安全性主要分为以下三个步骤：

• 首先确定威胁模型
• 第二个结构图
• 最后给出正式的安全证明

公钥加密始于1976年Diffie和Hellman的论文，提出了DH密钥交换/协商。当然，DH密钥协商的安全性并不完全基于离散对数，RSA的安全性也不完全基于因式分解（大数分解问题）。

教科书RSA

我们这里要说的是教科书RSA是不安全的。一般来说，消息需要进行padding才可以使用相应的RSA方案。

• 填充：与对称加密算法DES和AES一样，RSA算法也是一种分组密码算法（block cipheralgorithm），总是对固定长度的块进行操作，即需要用消息，但与AES等不同的是，块长度与密钥长度相关。
• 更多参考：RSA非对称加解密算法填充方法（Padding）

单向功能

接下来，我们介绍了单向功能。在单向函数中，多项式时间对手无法快速找到与单向函数的输出相对应的原始图像。以下是单向函数和安全博弈（Game）的定义。

假设 \(f(x)\) 是单向函数，但 \(f(m)\) 和 \(f(m) || r)\) 不是 m 的承诺解决方案，因为承诺需要保证隐藏和绑定。输出可能会泄漏 m 中的一些位信息，但如果 f 是随机预言 ，则 \(f(m||r)\) 是一个承诺。

DH 密钥协商

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

以下ppt引入了基于DH的关键协议协议，该协议分为初始化阶段，密钥生成阶段和生成会话键 关键阶段。

安全证明

在证明DHKE的安全性之前，我们需要确定DHKE在哪些假设下是安全的。我们需要先确定安全性和假设，然后利用规则来证明DHKE可以在多项式时间内还原为特定的假设。如果假设是困难的，就意味着经过验证的密码方案很难被破解，并且具有安全性。

• 首先，我们需要定义安全目标。在协议/算法执行过程中，谁是对手、对手的攻击能力并确定对手的攻击目标。
  • 对手是：第三者
  • 对手攻击能力：只能查看，数据无法修改
  • 对手攻击目标：获得\(k=g^{st}\)

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

调节理论

下图主要介绍如何针对具体难题降低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相比，这个问题在安全证明协议中更为普遍。下图展示了对手的攻击能力和博弈描述。

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