第1章 随机谕言机模型下的数字签名机制
本章主要介绍随机谕言机模型下的**数字签名机制，介绍相关签名机制[1-3]的算法定义及安全性证明方法。
1.1 算法定义及安全模型
本节将介绍签名机制的形式化定义及不可伪造性。
1.1.1 形式化定义
一个消息空间为的签名机制由、和等三个算法组成。
(1)密钥生成。
密钥生成算法的输入是安全参数，输出公私钥对，其中pk是公钥，sk是私钥。该算法可以表示为。
(2)签名。
签名算法输入一个明文和私钥sk，输出相应的签名。该算法可以表示为。
(3)验证。
验证算法输入签名、消息和公钥pk，若是关于消息的合法签名，则输出1；否则，输出0。该算法可以表示为。
一般情况下，算法和是概率性算法，即随机数将参与上述算法的运行，如随机性签名算法可以保证相同的明文消息，多次运行算法可以产生不同的签名值。
正确性要求对于任意的消息和公私钥对，有关系成立。特别地，在部分签名机制的算法定义中会包含一个初始化算法用于生成该签名机制所需的公共参数。
1.1.2 不可伪造性
设是一个消息空间为 的签名机制。适应性选择消息攻击下存在不可伪造性(existential unforgeability against chosen-message attacks，EUF-CMA)的游戏中挑战者和敌手间的消息交互过程如下所示。
(1)初始化。
挑战者输入安全参数，运行密钥生成算法，产生公钥pk和私钥sk，秘密保存sk的同时将pk发送给敌手。
(2)询问。
敌手自适应地选取任意消息进行签名询问，挑战者运行签名算法，生成相应的签名，并将其发送给敌手。
(3)伪造。
敌手输出关于消息的伪造签名，当满足下面两个条件时，敌手在该游戏中获胜。
①是关于消息的有效签名，即。
②询问阶段未对挑战消息进行签名生成询问。
敌手在上述游戏中获胜的优势定义为
定义1-1(签名机制的不可伪造性)对于任意的概率多项式时间敌手，若其在上述游戏中获胜的优势是可忽略的，则相应的签名机制在适应性选择消息攻击下具有不可伪造性。
上述安全性游戏的形式化描述如下所示。
其中，是签名询问谕言机；是记录敌手所提交的签名询问消息的相关列表。特别地，谕言机的应答过程如下所示。
在交互式实验中，敌手获胜的优势定义为
对于签名机制而言，上述游戏要求挑战消息不能在询问阶段出现，这个要求一定程度上限制了敌手的能力，使得不可伪造性的安全强度相对较低。为了进一步提升安全强度，本书将介绍签名机制的强不可伪造性定义，该性质的形式化描述如下所示：
其中，是签名询问谕言机；是记录敌手所提交的签名询问消息的相关列表。特别地，谕言机的应答过程如下所示。
在交互式实验 中，敌手 获胜的优势定义为
定义1-2(签名机制的强不可伪造性)对于任意的概率多项式时间敌手，若其在上述交互式实验中获胜的优势是可忽略的，则相应的签名机制在适应性选择消息攻击下具有强不可伪造性。
特别地，在强不可伪造性的定义中，允许敌手向挑战者提出关于挑战消息的签名生成询问，只要在伪造阶段敌手输出的伪造签名不是由挑战者生成的即可。对挑战消息的签名询问为敌手提供了额外帮助，增加了敌手伪造成功的概率，因此强不可伪造性的安全级别更高。
1.2 BLS数字签名机制
本节将介绍BLS签名机制，是由Boneh、Lynn和Shacham提出的一种签名机制[1]。
1.2.1 具体构造
(1)初始化。
(2)密钥产生。
(3)签名。其中
(4)验证。
签名的合法性验证是正确的，这是因为
1.2.2 安全性证明
假设1-1(计算性Diffie-Hellman(computational Diffie-Hellman，CDH)假设) 对于已知的元组 ，给定任意的随机元素，对于任意未知的指数，CDH问题的目标是计算。CDH假设意味着在多项式时间内敌手成功解决CDH问题的优势是可忽略的，其中概率来源于与在上的随机选取和算法的随机选择。
定理1-1 令哈希函数是一个随机谕言机。若群上的CDH假设成立，则上述BLS签名机制在适应性选择消息攻击下是不可伪造的。
安全性证明中，挑战者基于CDH问题的挑战元组为敌手构建一个BLS签名机制供敌手攻击，挑战者需要从敌手的伪造签名中得出CDH问题的解。由具体的签名形式可知，挑战者要想解决该问题只能将相应的已知参数与分别嵌入到和挑战消息所对应的哈希函数值中，那么敌手输出的关于挑战消息的伪造签名将包含CDH问题的有效解。因此，证明时需要将挑战消息的哈希值与已知参数建立联系，则哈希函数被视为随机谕言机。特别地，在上述操作中，对于挑战者而言如何获知敌手的挑战消息是证明成功的关键，因此挑战者需要在询问过程中适应性地猜测敌手的挑战消息。
证明 游戏开始之前，挑战者将收到CDH假设的挑战元组和相应的公开参数，目标是计算。挑战者与敌手间的游戏交互过程如下所示。
(1)系统设置。
令是一个随机谕言机。挑战者*先设置公钥，然后公开参数和给敌手。隐含地设置私钥，但挑战者并不掌握。
(2)询问。
该阶段敌手可适应性地进行多项式有界次的下述询问。在收到敌手所提交的相关询问之前，挑战者适应性地选取一个整数作为对挑战消息的猜测，其中是敌手对谕言机的询问总数(对于敌手而言，生成伪造签名时需使用挑战消息的哈希函数值，因此为了提高签名伪造成功的概率，敌手肯定会对挑战消息进行哈希询问，也就是提交谕言机询问)。此外，挑战者将维护一个初始为空的哈希列表来记录相应的询问和应答。
①谕言机询问。对于敌手所提交的关于消息的哈希询问，若哈希列表中存在关于的相应记录，则挑战者返回相应的给敌手；否则，挑战者随机选取，并设置：
*后，挑战者返回相应的给敌手，并添加相应的元组到哈希列表中。
②签名询问。对于敌手所提交的关于消息的签名询问，若，则挑战者终止并输出；否则，挑战者计算，并发送给敌手。特别地，敌手对消息进行签名询问之前已完成对的哈希询问，则哈希列表中存在相应的元组。由等式可知，是关于消息的一个有效签名。
(3)伪造。
敌手输出关于消息的伪造签名，其中，并且消息未在签名询问中出现。
若，则签名是关于消息的有效签名，那么有
*后，挑战者输出并将其作为CDH问题的有效解。
根据挑战者的设置，和都是中随机选取的，从敌手的角度而言，相关参数及哈希应答都是随机且*立的，因此模拟与真实攻击是不可区分的。对于挑战者而言，其成功的概率就是猜测出正确挑战消息的概率，因此，模拟成功的概率是。综上所述，在EUF-CMA安全模型中，若存在一个敌手能以不可忽略的优势攻破上述BLS签名机制的不可伪造性，则将构造一个挑战者以显而易见的优势解决CDH问题的困难性。
定理1-1证毕。
注解1-1由于上述BLS签名机制从次哈希询问中正确猜测出挑战消息的概率相对较低，故挑战者模拟成功的概率仅为，那么该如何提升模拟成功的概率？挑战者为了嵌入CDH困难问题，需猜测具体的挑战消息，导致模拟成功的概率降低。如果不进行挑战消息的猜测，且要保证敌手的伪造签名中包含CDH困难问题的解，那么挑战者对非挑战消息的哈希询问的应答也是，然而此时挑战者将无法应答敌手提出的对非挑战消息的签名询问，因为相应的有效签名包含了挑战者未知的，因此BLS签名机制的证明中挑战者必须猜测挑战消息。
1.3 改进的BLS数字签名机制
由原始BLS签名机制的证明过程可知，挑战消息的猜测影响了挑战者游戏模拟成功的概率。挑战者只有不再进行挑战消息的猜测才能提升模拟成功的概率。然而，一个消息既有可能是挑战消息，也有可能是签名询问消息。从敌手的角度出发，他期望在哈希询问中询问更多的挑战消息，但签名询问中的消息一定是非挑战的消息(在不可伪造性的定义中，签名询问中的消息，不能被用来做挑战消息)，因此通过为消息设置挑战和询问两个状态，使得每个消息既能出现在伪造阶段，也能出现在询问阶段，那么模拟者在安全性证明时只需猜测消息的相应状态，此时模拟成功的概率将升至1/2，即哈希询问的消息处于挑战状态，签名询问的消息处于询问状态。本节将介绍改进的BLS签名机制[2]，称该方案为BLS+签名机制。
1.3.1 具体构造
(1)初始化。
(2)密钥产生。
展开
