本文将翻译Fuchun Guo老师所编写的Introduction to Security Reduction一书，本书主要讲述密码学协议是如何构造一个安全性证明的。

Introduction to Security Reduction

https://doi.org/10.1007/978-3-319-93049-7

Preface

安全还原（原文是security reduction，也可以说是安全性降低）是证明公钥密码学安全性的一种非常流行的方法。粗略地说，通过安全还原，我们可以证明破解一个方案就像解决一个数学难题一样困难。然而，如何利用对手的自适应攻击来编制正确的安全还原是相当复杂的。原因在于，并不存在适用于所有建议方案的通用安全还原。

密码学研究论文中给出的安全还原通常很难被初学者完全理解。为了帮助初学者，一些密码学教科书用较简单的例子说明了如何正确编制安全还原程序。不过，研究论文和以往教科书中提到的安全还原通常是针对特定方案的。不同方案的安全还原不同，导致初学者无所适从。我们需要一本系统介绍如何为密码系统（而非特定方案）正确编写安全还原程序的书籍。有鉴于此，我们编写了这本书，希望能帮助读者了解如何正确编写安全还原程序。

本书的内容，尤其是安全裁减的基础，是基于我们的理解和经验。读者可能会发现，书中对概念的解释与其他资料略有不同，因为我们添加了一些 “佐料”，以帮助读者理解这些概念。例如，在安全还原中，对手不是黑盒对手，而是拥有无限制计算能力的恶意对手。我们原以为本书能在一年内完成，但我们低估了它的难度。我们花了四年多的时间才完成本书的写作。肯定还有一些错误尚未发现。欢迎大家提出意见和建议。

Acknowledgements

Pass!

Guide to This Book

在公钥密码学中，构建可证明安全的密码系统的第一步是明确其密码学概念，并正式定义算法及其相应的安全模型。密码学概念有助于读者理解算法的定义，而安全模型对于衡量所提方案的强度至关重要。方案构建和安全证明都需要相应的密码学基础知识。有鉴于此，我们按照图 1.1 所示的可证明安全方案的工作过程来安排本书的章节。

图1.1：构建可证明安全的公钥加密方案的步骤

公钥密码学中有两种流行的安全证明方法，即基于博弈的证明和基于模拟的证明。前者又可分为两类，即安全还原和博弈跳转。本书只涉及安全还原，它首先假设存在一个能破解所提方案的对手。在有安全还原的安全证明中，具体的安全还原取决于相应的密码系统、方案和基础难题。目前还没有通用的方法来为所有方案编制安全还原。本书介绍了三种特定密码系统的安全还原：数字签名、公钥加密和基于身份的加密。本书给出的所有示例和方案都是在有或没有双线性映射的循环群上构建的。
各章内容概述如下。第 2 章简要回顾了密码学概念、算法和安全模型。如果读者熟悉定义，可以跳过本章。第 3 章介绍了基于群的密码学基础：我们介绍了有限域、循环群、双线性配对和哈希函数。我们的介绍主要集中在高效可计算运算和群表示。我们尽量减少对分组密码学初步知识的描述。第 4 章是本书最重要的一章。在这一章中，我们对安全还原的基本概念进行了分类和解释，并总结了如何对数字签名和加密进行全面的安全还原编程。在有必要举例说明概念时，我们以基于组的密码学为例。本书其余各章专门介绍一些选定方案的安全证明，以帮助读者理解如何正确编程安全还原。每个选定方案的安全证明都对应一种有用的还原技术。
关于符号。本书倾向于使用以下符号。相同的符号在不同的应用中可能有不同的含义。

For mathematical primitives:

$q,p$ ：素数
$F_{q^n}$ ：有限域，有限域的阶表示为pⁿ（p是素数、n是正整数）
$k$ ：扩展域 $F_{(q^n)^k}$ 的嵌入度，嵌入度（embedding degree）指的是将有限域F的元素扩展到更大扩域中的最小次数。换句话说，它是将F的元素映射到一个具有更高次数的扩域中所需的最小扩展次数。
$Z_p$ ：整数集合 $\{0,1,2,...,p-1\}$
$Z_p^*$ ：整数集合 $\{1,2,...,p-1\}$
$H$ ：一个一般群
$G$ ：一个素阶循环群，其中群的阶（元素个数）为一个素数p。
$u,v$ ：域或群中的一般元素
$g,h$ ：循环群中的所有元素
$w,x,y,z$ ：一个整数集合中的整数，例如 $Z_p$
$e$ ：一个双线性映射（是一种从两个向量空间到一个标量域的映射）

For scheme constructions:

$\lambda$ ：一个安全参数
$(G,g,p)$ ：一个具有素数阶 p 的一般循环群 G，其中 g 是 G 的一个生成元。
$|p|$ ：在二进制表示中，数值 p 的比特长度。
$|g|$ ：在二进制表示中，群元素 g 的比特长度。
$|G|$ ：群 G 中群元素的数量。
$PG=(G,G_T,g,p,e)$ ：一个配对群，由两个具有相同素数阶数 p 的群 $G$ 和 $G_t$ 组成，其中 G 的生成元为 g，并且具有一个双线性映射 $e:G\times F\rarr G_T$ 。
$\{0,1\}^*$ ：任意长度所有可能的二进制序列
$\{0,1\}^n$ ：n比特长度的所有可能的二进制序列
$\alpha, \beta, \gamma$ ： $Z_p$ 中的随机整数作为密钥
$g,h,u,v$ ：群元素
$r,s$ ： $Z_p$ 中的随机数字
$n$ ：与相应情景相关联的一个一般正数。
$i,j$ ：索引
$m$ ：明文
$\sigma_m=(\sigma_1,\sigma_2,..,\sigma_n)$ ：m的签名，其中 $\sigma_i$ 表示第i个元素
$CT=(C_1,C_2,...,C_n)$ ：密文 $C_i$
$(pk,sk)$ ：一对密钥，其中pk表示公钥，sk表示私钥。
$d_{ID}$ ：在基于身份的加密中，与身份ID相关联的私钥。

For hard problems:

$I$ ：一个数学困难问题的实例。
$Z$ ：在一个决策性困难问题的实例中将要判断的目标，其中Z可以是一个真元素或者一个假元素。
$g,h,u,v$ ：群元素。
$a,b,c$ ：问题实例 $I$ 中从 $Z_p$ 中随机选择且未知的指数。
$F(x),f(x),g(x)$ ：在 $Z_p[x]$ 中的（随机）多项式，即多项式中的所有系数都是从 $Z_p$ 中随机选择的。
$F_i,G_i,f_i,a_i$ ：多项式中xi的系数。
$n,k,l$ ：与相应情景相关联的一般正整数。

For security models and security proofs:

$\mathcal{A}$ ：攻击者（adversary）
$\mathcal{C}$ ：挑战者（challenger）
$\mathcal{B}$ ：模拟器（simulator）
$\varepsilon$ ：打破方案或解决困难问题的优势（advantage）
$t$ ：打破方案所需的时间成本（time cost）
$q$ ：与底层困难问题相关的数字
$q_s$ ：签名查询的数量（signature queries）
$q_k$ ：身份基础密码学中私钥查询的数量（private-key queries）
$q_d$ ：解密查询的数量（decryption queries）
$q_H$ ：随机预言机的哈希查询数量（hash queries to random oracles）
$c,coin$ ：从{0,1}中随机选择的比特位
$w,x,y,z$ ：模拟器从Zp中选择的秘密和随机数
$T_s$ ：安全性约简的时间成本（time cost of security reduction）

研究学生须知。安全还原需要非常棘手的分析。即使你能理解别人的安全还原，但要为自己的方案编制一个正确的安全还原，可能仍有难度。中国有句传统谚语

Seeing\ once\ is\ better\ than\ hearing\ 100\ times\ ,\\ but\ doing\ once\ is\ better\ than\ seeing\ 100\ times

"百闻不如一见，百见不如一做"。
为了更好地利用本书，你可以在阅读本书给出的安全证明（看）之前，根据第 4 章的知识尝试证明（做）书中提供的方案。这样，你就能更清楚地了解哪个部分对你来说最难，以及如何正确编程安全还原。读者可以访问作者的主页，查找本书的补充资源。

Notions, Definitions, and Models

在本章中，我们简要回顾了数字签名、公钥加密和基于身份的加密的重要知识，包括密码学概念、算法和安全模型。为了方便演示，我们将数字签名和公钥加密的传统密钥生成算法分为系统参数生成算法和密钥生成算法，其中系统参数可以由所有用户共享。本书中的每个密码系统由四个算法组成。

Digital Signatures

数字签名是密码学中的一种基本工具，被广泛应用于身份验证和不可否认性。以身份验证为例。假设一方，比如Alice，希望说服其他所有方，证明一条消息m是由她发布的。为此，Alice生成一个公钥/私钥对(pk,sk)，并将公钥pk发布给所有的验证者。为了在消息m上生成一个签名 $\sigma _m$ ，她使用她的私钥sk对m进行数字签名。收到 $(m,\sigma _m)$ 的任何已知pk的接收方可以验证签名 $\sigma _m$ ，并确认消息m的来源。

数字签名方案包括以下四个算法：

**SysGen: ** 系统参数生成算法以安全参数 $\lambda$ 作为输入，并返回系统参数 $SP$

**KeyGen: ** 密钥生成算法以系统参数 $SP$ 作为输入，并返回公钥/私钥对 $(sk,pk)$

**Sign: ** 签名算法以消息空间中的消息 $m$ 、私钥 $sk$ 和系统参数 $SP$ 作为输入，并返回用 $\sigma _m$ 表示的消息 $m$ 的签名。

**Verify: ** 验证算法以消息-签名对 $(m, \sigma_m)$ 、公钥 $pk$ 和系统参数 $SP$ 作为输入。如果 $\sigma_m$ 是使用私钥 $sk$ 对 $m$ 进行签名的有效签名，则返回“接受”；否则，返回“拒绝”

正确性：对于任意的 $(pk, sk, m, σ_m)$ ，如果 $σ_m$ 是使用私钥 $sk$ 对 $m$ 进行签名的有效签名，则在 $(m, σ_m, pk)$ 上运行的验证算法将返回“接受”。

安全性：在没有私钥 $sk$ 的情况下，任何概率多项式时间(PPT)的对手很难伪造一个能通过签名验证的新消息 $m$ 的有效签名 $σ_m$ 。

在数字签名的安全模型中，安全性通过一个由挑战者和对手玩的游戏来建模。在他们之间的互动过程中，挑战者生成一个签名方案，而对手则试图破解这个方案。也就是说，挑战者首先生成一个密钥对 $(pk, sk)$ ，将公钥 $pk$ 发送给对手，而保留私钥。然后，对手可以对由自己选择的任何消息进行适应性查询。最后，对手返回一个未被查询过的新消息的伪造签名。这种安全概念被称为存在性不可伪造性。

存在性不可伪造性（EU-CMA）的安全模型可以描述如下：

设置阶段：令 $SP$ 为系统参数。挑战者运行密钥生成算法以生成密钥对 $(pk, sk)$ ，并将 $pk$ 发送给对手。挑战者保留 $sk$ 以响应对手的签名查询。

查询阶段：对手根据自己的选择进行消息的签名查询。对于消息 $m_i$ 的签名查询，挑战者运行签名算法计算 $σ_{m_i}$ ，并将其发送给对手。

伪造阶段：对手返回一个在某个消息 $m^*$ 上的伪造签名 $σ_{m^∗}$ 并且在游戏中获胜，如果：

$σ_{m^∗}$ 是消息 $m^∗$ 的有效签名。
在查询阶段，没有对消息 $m^*$ 进行签名查询。

获胜游戏的优势 $ε$ 是返回有效伪造签名的概率。

**定义2.1.0.1（EU-CMA）**在 EU-CMA 安全模型中，如果不存在能够在时间 $t$ 内进行 $q_s$ 次签名查询后以优势 $ε$ 赢得上述游戏的对手，则签名方案被称为 $(t,q_s,ε)-$ 安全。

更强的数字签名安全模型定义如下。

**定义2.1.0.1（SU-CMA）**在针对强存在性不可伪造性的选择消息攻击（SU-CMA）的安全模型中，如果不存在能够在时间 $t$ 内进行 $q_s$ 次签名查询后以优势 $ε$ 赢得上述游戏的对手，则签名方案被称为 $(t,qs,ε)-$ 安全。在这种情况下，伪造的签名可以是任意消息，只要它与所有查询的签名都不相同。

在（标准）数字签名的定义中，私钥 $sk$ 在签名生成期间不需要更新。我们将这种签名称为无状态签名（stateless signature）。相反，如果在生成每个签名之前需要更新私钥 sk，则称之为有状态签名（stateful signature）。本书将在第6.3节和第6.5节介绍有状态签名方案。

Public-Key Encryption

公钥加密是公钥密码体系中的另一个重要工具，已经证明了许多有用的应用，如数据机密性、密钥交换、遗忘传输等。以数据机密性为例，假设一方（称为Bob）希望将敏感消息 m 发送给另一方（称为Alice），尽管他们没有共享任何秘密密钥。Alice首先生成一个公钥/私钥对（pk, sk），并将她的公钥 pk 公开给所有发送者。使用 pk，Bob可以将敏感消息 m 加密，并将得到的密文发送给Alice。Alice可以使用私钥 sk 解密密文，并获取消息 m。

公钥加密方案包括以下四个算法。

SysGen：系统参数生成算法以安全参数 $\lambda$ 作为输入，返回系统参数SP。

KeyGen：密钥生成算法以系统参数 $SP$ 作为输入，返回公钥/私钥对 $(pk,sk)$ 。

Encrypt：加密算法以来自其消息空间的消息 $m$ 、公钥 $pk$ 和系统参数 $SP$ 作为输入，返回密文 $CT = E[SP,pk,m]$ 。

Decrypt：解密算法以密文 $CT$ 、私钥 $sk$ 和系统参数 $SP$ 作为输入，返回消息 $m$ 或输出 $⊥$ 表示失败。

正确性：对于任意的 $(SP,pk,sk,m,CT)$ ，如果 $CT = E[SP,pk,m]$ 是使用公钥 $pk$ 对消息 $m$ 进行加密得到的密文，则使用私钥 $sk$ 对 $CT$ 进行解密将返回原始消息 $m$ 。

安全性：在没有私钥 $sk$ 的情况下，对于任何概率多项式时间（PPT）的对手来说，从给定的密文 $CT = E[SP,pk,m]$ 中提取消息m是困难的。

公钥加密的不可区分性安全性通过由挑战者和对手进行的一场游戏来建模。挑战者生成加密方案，而对手试图破解该方案。开始时，挑战者生成一个密钥对 $(pk,sk)$ ，将公钥 $pk$ 发送给对手，并保留私钥 $sk$ 。对手从相同消息空间中输出两个不同的消息 $m_0,m_1$ 作为挑战。挑战者在 $\{m_0,m_1\}$ 中随机选择一条消息 $m_c$ ，生成一个挑战密文 $CT^∗$ 。如果允许进行解密查询，对手可以对由对手自己自适应选择的任意密文进行解密查询，但不允许对 $CT^∗$ 进行解密查询。最后，对手输出对挑战密文 $CT^∗$ 中所选择的消息 $m_c$ 的猜测。

形式化地，针对选择密文攻击的不可区分性安全（IND-CCA）模型可以描述如下：

设置：令 $SP$ 为系统参数。挑战者运行密钥生成算法以生成密钥对 $(pk,sk)$ ，并将 $pk$ 发送给对手。挑战者保留 $sk$ 以回应对手的解密查询。

第一阶段：对手可以在由对手自己自适应选择的密文上进行解密查询。对于对密文 $CT_i$ 的解密查询，挑战者运行解密算法，然后将解密结果发送给对手。

挑战：对手从相同消息空间中自适应选择两个不同的消息 $m_0$ 、 $m_1$ 。挑战者随机选择一个比特 $c \in \{0,1\}$ ，然后计算一个挑战密文 $CT^∗ = E[SP,pk,m_c]$ ，并将其提供给对手。

第二阶段：挑战者以与第一阶段相同的方式回应解密查询，但限制不允许对 $CT^∗$ 进行解密查询。

猜测：对手输出一个对c的猜测c0，并且如果c0 = c，则对手赢得游戏。对手在赢得这个游戏中的优势ε定义为：

\varepsilon=2(Pr[c^{\prime}=c]-\frac{1}{2})

定义2.2.0.1（IND-CCA）：在IND-CCA安全模型下，如果不存在能够在时间t内进行 $q_d$ 个解密查询的对手能够以优势 $ε$ 赢得上述游戏，则公钥加密方案是 $(t,q_d,ε)$ -安全的。

一般情况下，我们认为IND-CCA模型是加密安全性的标准安全模型。还有一个较弱的不可区分性版本，即针对已知明文攻击的不可区分性（IND-CPA），也称为语义安全性，其定义如下。

定义2.2.0.2（IND-CPA）：在不可区分选择明文攻击（IND-CPA）的安全模型下，公钥加密方案是 $(t,ε)$ 安全的，如果该方案在IND-CCA安全模型中是 $(t,0,ε)$ 安全的，其中对手不被允许进行任何解密查询。

在安全模型的描述中，挑战者选择一个随机硬币来决定在挑战阶段要加密的消息。在本书中，我们用符号 $c ∈ \{0,1\}$ 或符号 $coin ∈ \{0,1\}$ 来表示随机硬币，如果c已经在难度假设中使用过。

Identity-Based Encryption

身份基加密（IBE）是由公钥加密的一个劣势所激发的，即每个公钥看起来都像是一个随机字符串，因此公钥加密需要一个证书系统。在IBE的概念中，有一个由私钥生成器（PKG）生成的主密钥对 $(mpk,msk)$ 。主公钥mpk被发布给所有用户，主秘钥msk由PKG保留。假设一方，比如Bob，想要向另一方，比如Alice，发送一条敏感消息。Bob只需使用主公钥mpk和Alice的身份ID（比如Alice的电子邮件地址）对消息进行加密。Alice使用她的私钥 $d_{ID}$ 对密文进行解密，该私钥由PKG使用身份ID和主秘钥msk计算得到。

IBE方案只需要所有加密者验证主公钥mpk的有效性。因此，他们不需要验证接收者的公钥，因为公钥就是接收者的身份信息。只有匹配身份信息的接收者才能从PKG获取其私钥并解密相应的密文。IBE允许Bob使用Alice的姓名作为身份来加密消息；然后Alice向PKG申请相应的私钥。在本书中，解密密钥在PKE中被称为秘密密钥；而在IBE中，解密密钥被称为私钥。

一个身份基加密方案包括以下四个算法。

设置：设置算法以安全参数λ作为输入。它返回一个主公钥/秘密钥对 $(mpk,msk)$ 。
密钥生成：密钥生成算法以身份ID和主密钥对 $(mpk,msk)$ 作为输入。它返回ID的私钥 $d_{ID}$ 。
加密：加密算法以来自其消息空间的消息m，身份ID和主公钥mpk作为输入。它返回一个密文 $CT = E[mpk,ID,m]$ 。
解密：解密算法以ID的密文CT，私钥 $d_{ID}$ 和主公钥mpk作为输入。它返回一个消息m或输出 $⊥$ 表示失败。

正确性：对于任何（mpk，msk，ID，dID，m，CT），如果CT = E[mpk，ID，m]是使用ID对消息m进行加密的密文，则使用私钥dID解密CT将返回消息m。

安全性：在没有私钥 $d_{ID}$ 的情况下，任何PPT对手很难从给定的密文 $CT = E[mpk,ID,m]$ 中提取消息。

身份基加密的不可区分性安全性是由挑战者和对手进行的一种游戏模型来建模的。挑战者生成一个IBE方案，而对手试图破解该方案。首先，挑战者生成一个主密钥对 $(mpk,msk)$ ，将主公钥mpk发送给对手，并保留主秘钥msk。对手输出两个不同的消息m0，m1和一个要挑战的身份 $ID^∗$ 。挑战者为 $ID^∗$ 从 $\{m0,m1\}$ 中随机选择一个消息生成一个挑战密文 $CT^∗$ 。在游戏过程中，对手可以自适应地对除了挑战身份之外的任何身份进行私钥查询，并可以对除了挑战密文之外的任何密文进行解密查询。特别地，对手可以对满足 $(ID = ID^∗,CT \ne CT^∗)$ 或 $(ID \ne ID^∗,CT = CT^∗)$ 的 $(ID,CT)$ 进行解密查询。最后，对手输出对于挑战密文 $CT^∗$ 中选择的消息的猜测。

对于选择密文攻击（IND-CCA）的不可区分性安全性模型可以描述如下。

设置：挑战者运行设置算法生成主密钥对（mpk，msk），并将mpk发送给对手。挑战者保留msk以回应对手的查询。

第一阶段：对手进行私钥查询和解密查询，其中身份和密文由对手自适应选择。

• 对于关于 $ID_i$ 的私钥查询，挑战者使用主密钥 $msk$ 在 $ID_i$ 上运行密钥生成算法，然后将 $d_{ID_i}$ 发送给对手。

• 对于关于 $(ID_i,CT_i)$ 的解密查询，挑战者使用私钥 $d_{ID_i}$ 运行解密算法，然后将解密结果发送给对手。

挑战：对手输出两个不同的消息 $m_0,m_1$ ，这两个消息来自相同的消息空间，并选择一个要进行挑战的标识符 $ID^∗$ 。其中 $m_0,m_1$ 和 $ID^∗$ 均由对手自己自适应地选择。在 Phase 1 中，我们要求没有查询过 $ID^∗$ 的私钥。挑战者随机选择一个 $c ∈ \{0,1\}$ ，然后计算一个挑战密文 $CT^∗ = E[mpk,ID^∗,m_c]$ ，并将该密文给予对手。

第二阶段：挑战者对私钥查询和解密查询的回应方式与 Phase 1 相同，但有以下限制：不允许对 $ID^∗$ 进行私钥查询，也不允许对 $(ID^∗,CT^∗)$ 进行解密查询。

Guess. 对手输出一个猜测 $c^{\prime}$ 关于 c，并在 $c^{\prime}$ = c 时赢得游戏。对手在赢得该游戏中的优势 ε 定义为：

\epsilon = 2 (Pr[c^{\prime}=c]-\frac{1}{2})

定义 2.3.0.1 (IND-ID-CCA)：如果不存在任何在时间 t 内通过进行 $q_k$ 次私钥查询和 $q_d$ 次解密查询来获得优势 $ε$ 的对手能够赢得上述游戏，则基于身份的加密方案在 IND-ID-CCA 安全模型中是 $(t,q_k,q_d,ε)$ -安全的。

存在两个更弱的安全模型，定义如下：定义 2.3.0.2 (IND-sID-CCA)：如果加密方案在 IND-ID-CCA 安全模型中是 $(t,q_k,q_d,ε)$ -安全的，但对手必须在设置阶段之前选择挑战身份 $ID^∗$ ，则基于身份的加密方案在选择性身份 (IND-sID-CCA) 安全模型中是 $(t,q_k,q_d,ε)$ 安全的。

在安全模型的阶段1和阶段2中，对手可以交替进行私钥查询和解密查询。对手在安全模型中总共进行的查询次数为 $q_k$ 和 $q_d$ ，但是对手可以自行适应性地决定阶段1中的私钥查询次数（记为 $q_1$ ）和解密查询次数（记为 $q_2$ ），只要满足 $q_1 ≤ q_k$ 和 $q_2 ≤ q_d$ 。