公钥密码算法可证明安全理论：第三讲

4 安全规约基础

4.1 预备知识

4.1.1 计算问题 Computing Problem

def 用数学原语（mathematical primitive）定义的计算问题表示特定问题和答案的数学对象，其具有无限数目的实例 - 解决方案对 $(x, y)$

• 使用算法（algorithms）解决计算问题

• 查找 $y$ 的计算开销随着 $x$ 长度的增加而增加

• 计算问题 = 计算性问题 + 判定性问题

4.1.2 计算 / 搜索性问题 Computational Problem

def 在计算性问题中，问题实例 $x$ 的解决方案 $y$ 来自一个大的解空间，譬如$2^{|x|}$
e.g. CDHP：实例 $x =(g, g^a,g^b) ∈G$; 解决方案 $y=g^{ab} ∈G$

4.1.3 判定性问题 Decisional Problem

def 在判定性问题中， 问题实例 x 的解 y 来自集合 {0, 1}，只有两个答案：

• 如果 y = 1，则实例 x 称为 true 实例

• 如果 y = 0，则实例 x 称为 false 实例
  e.g. DDHP

1. 正直语言 Formal Language

def 包含所有 true 实例的集合称为正直语言 $L$，判定性问题转化为判断 $x∈ L$ 是否成立

4.1.4 决定性算法 Deterministic Algorithms

def 给定一个问题实例 x 作为输入，始终返回解决方案 y 作为正确的结果

4.1.5 概率性算法 Probabilistic Algorithms

def 给定一个问题实例 x 作为输入，有一定可能给出正确的结果

• 比决定性算法更高效

• $(t, ϵ)$：

  • $t$：时间差，要求为概率多项式时间 PPT
  • $ϵ$：概率 / 优势

1. 为什么要求为概率多项式时间 PPT？

若为指数时间，则攻破了方案还未攻破困难问题，即方案的安全性较困难问题弱了很多

2. $\epsilon$ 什么时候是优势，什么时候是概率？

• 对计算性问题，$ϵ$ 是成功概率（success probability）

• 对判定性问题，$ϵ$ 是解决问题的优势（advantage）

4.1.6 算法的分类

所有对象（构造方案、中断方案、解决问题和程序规约）都是为了提出算法。在密码学中，算法可以分为：

• 方案算法：用于构建密码系统（方案）

• 攻击算法：用于打破一个方案

• 求解算法：用于解决一个困难问题

• 规约算法：用于描述安全规约

4.1.7 多项式与指数

def 令 f (λ) 是关于正数 λ 的函数，有：

• 多项式（Polynomial）：存在 $c, k > 0$ 使得 $f (λ) ≤ c·λ^k$

  • 多项式时间：理解为多项式速度，$f(λ)$ 增加的速度取决于 $λ$ 的长度

• 指数（Exponential）：存在 $c > 0$ 使得 $2^{c·λ}≤f (λ)$ （变量在方幂上）
  e.g. $2^{160}$ 不是指数时间，$2^λ$ 是指数时间

4.1.8 不可忽略 Non-Negligible/Noticeable

def $1−negl(λ)$ ：如果对于任何整数 $k_1∈Z$，存在另一个整数 $k_2∈Z$，对 $λ> k_2$ ，函数 $negl(λ)<1/λ^{k_1}$，则函数 $1−negl(λ)$ 在 $λ$ 中是不可忽略的

4.2 困难问题

4.2.1 计算性困难问题

def 假设由安全参数 λ 生成一个计算性问题，给定一个问题实例并将其作为输入，在多项式时间内找到该问题实例正确解的概率是 λ 的可忽略函数 $ϵ(λ)$

$$Pr⁡[A(x) = y] ≤ ϵ(λ)$$

• 对手 $A$ 运行概率算法

• 对手在多项式时间内中止

• $ϵ(λ)$ 是 $λ$ 中的可忽略函数

• 问题实例 $x$ 的长度为 $λ$

4.2.2 判定性困难问题

def 假设由安全参数 λ 生成一个判定性问题，给定一个目标为 Z 的问题实例作为输入，在多项式时间内输出正确猜测的优势是 λ 的可忽略函数 $ϵ(λ)$

$$|Pr⁡[A(x)=True│x=true]-Pr⁡[[A(x)=True│x=false]|≤ϵ(λ)$$

• 对手 $A$ 运行概率算法

• 对手在多项式时间内中止

• $ϵ(λ)$ 是 $λ$ 中的可忽略函数

• 问题实例 $x$ 的长度为 $λ$

1. 困难问题和困难问题假设的区别？

打破方案意味着解决困难难题，因此方案在此困难问题假设下是安全的

4.2.3 强假设与弱假设

• 弱假设

  • def 又称标准假设，其安全级别仅与生成底层数学原语所输入的安全参数有关
  • 安全级别非常接近 DLP，攻破的时间成本高
  • 当且仅当几个条件成立时，计算问题才很难

• 强假设

  • def 其安全级别不仅与生成底层数学原语所输入的安全参数有关，还与其他参数有关，譬如每个问题实例的大小
  • 安全级别低于 DLP，攻破的时间成本低于弱假设
  • 当且仅当许多条件成立时，计算问题才很难

1. 什么样的方案安全性更好？

	更好	更差
困难问题假设	弱假设	强假设
安全模型	强模型	弱模型

4.2.4 计算性困难问题实例

设 $G$ 和 $G_τ$ 是 $e:G×G→G_τ$ 且 $G=<g>$ 的循环群

DP	实例
DL	$g, g^a∈G → a$
CDH	$g, g^a, g^b∈G → g^{ab}$
q-SDH	$g, g^x,g^{x^2},⋯, g^{x^q}∈G → (c,g^{1/(x+c)})$，其中 $c≠-x$
q-SDHI	$g, g^a,g^{a^2} ,⋯, g^{a^q} ∈G → g^{1/a}$
q-BDHI	$g, g^a,g^{a^2},⋯, g^{a^q}∈G → e(g,g)^{1/a}$
q-BDH	$g, g^a,g^{a^2},⋯, g^{a^q}, g^{a^{q+2}},⋯, g^{a^2q},h∈G → e(g,h)^{a^{q+1}}$
设 $G_1$ , $G_2$ 和 $G_τ$ 是 $e:G_1×G_2→G_τ$ , $G_1=<g_1>$ , $G_2=<g_2>$ 的循环群

DP	实例
co-CDH	$g_1, g_1^a,g_2,g_2^a,g_2^b∈G_1^2×G_2^3 → g_2^{ab}$
CBDH	$g_1,g_1^a,g_1^b,g_1^c,g_2,g_2^b,g_2^c∈G{_1^4}×G{_2^3}$ → $e(g_1, g_2)^{abc}$
JoC-sDBDH	$g_1,g_1^x,g_1^{x^2},⋯,g_1^{x^q},g_2,g_2^x ∈G_1^{q+2}×G_2^2$ → $(c,g_1^{1/(x+c)})$

4.2.5 判定性困难问题实例

4.3 安全级别

从攻击算法的角度，为达到 k-bit 安全性，有：

$$2^k=min\{t_1/ϵ_1 ,t_2/ϵ_2 ,⋯,t_l/ϵ_l \}$$

• 已知（known）安全级别：基于所有已知的攻击算法

• 确切（exact）安全级别：基于最佳攻击算法，通常是未知的，否则证明$NP ≠ P$ 是容易的

• 安全级别上限（upper bound）：基于比破坏方案更难的 DP

• 安全级别下限（lower bound）：基于安全规约采用的困难问题假设

4.4 一次一密 One-Time Pad

def 令 $E(m,r,R)$ 是由公共参数 $R$ 和秘密参数 $r$ 对给定消息 $m$ 的加密。如果对于来自同一明文空间的任意两个不同消息 $m_0$, $m_1$，在公共参数 $R$ 下，$CT$ 可以等概率地表示为由秘密参数 $r_0$ 对消息 $m_0$ 的加密，或者由秘密参数 $r_1$ 对消息 $m_1$ 的加密，即 $Pr[CT=E(m_0,r_0,R)]=Pr[CT=E(m_1,r_1,R)]$，那么密文 $E(m,r,R)$ 是一次一密

参考资料：

[1] 安全规约导论，郭富春