格上无陷门的基于证书盲签名

陈江山

（1.闽南师范大学数据科学与统计重点实验室,福建漳州 363000；2.闽南师范大学数学与统计学院,福建漳州 363000）

随着信息社会的发展，个人隐私保护问题日益尖锐.在日常的电子商务活动中充斥着各种不愿泄露自身信息的情况.盲签名技术则提供了其中一种.如：签名的持有人希望获得签名人的一份签名，但同时不愿意泄露这份签名所对应的信息.在这种情况下，便可以采用盲签名技术.盲签名技术是电子商务的重要应用技术之一.盲签名技术由Chaum[1]提出，签名人对盲化过的消息进行签名，签名持有人取得签名后对其进行去盲化，从而得到一份真实有效的签名.盲签名技术的应用较为广泛，比如：电子银行、电子投票、不经意传输等.

应用的广泛使得盲签名技术的研究从未间断[2-6].特别是在不同的密码体制和密码应用场景中[7-12].然而，这些盲签名方案均基于传统的代数数论困难问题之上.在后量子时代中，传统的基于代数数论困难问题的密码技术受到了严重的安全威胁.因此，越来越多的密码学者研究可以不受量子算法威胁的密码技术[13-16].而且，我国也已然开始了对后量子密码算法的征集，并纳入我国商密标准算法.

在后量子密码的研究中，基于格的密码(也称格基密码)是其中一个重要研究方向.目前，大部分的后量子密码算法，均是格基密码[17-24].然而，多数的格基密码的效率都因为陷门技术问题大大下降，从而难以实用化.

2012年,Lyubashevsky[25]提出了一个拒绝采样的格上无陷门签名方案.该方案在格基密码的实用化道路上迈出了第一步.在Lyubashevsky工作的基础上，构造一个格上无陷门的基于证书盲签名方案.该盲签名方案与Lyubashevsky的工作一样拒绝采样，从而避免了使用格上的陷门技术.同时，该方案具备了必要的无条件盲性和不可加一伪造性.方案所需的存储空间较小，通信量也较小.由于方案使用无陷门技术，故而方案的计算复杂度也较小.

1 预备知识

1.1 格的基础知识

定义1(格) 由矩阵B∈Rn×m产生的格L可定义如下：

其中，B是一个由m个线性无关的n维向量{b1,b2,…,bm}组成的矩阵.

定义2（l2-SISq,n,m,β问题）给定整数q和实数β，以及随机矩阵，计算得到一个向量z∈Zm{0}，使得Az=0(mod q)和‖z‖≤β.

其中，当β≥时，以上困难问题有解.

1.2 拒绝采样技术

这里，回顾Lyubashevsky的拒绝采样技术.

1.3 基于证书盲签名方案的一般性定义

基于证书的盲签名方案一般由以下几个算法组成：

Setup算法输入安全参数，输出系统的公共参数，证书机构的主公钥和主密钥.

UserKeyGen算法输入系统的公共参数和用户的身份，输出用户的公钥和私钥.

CertGen算法输入系统的公共参数和证书机构的主密钥，以及用户的身份和公钥，输出用户的证书.

BlindSign协议输入系统的公共参数，待签消息，签名人的身份、私钥和证书，输出签名.

Verify 算法输入系统的公共参数，消息签名对，证书机构的主公钥，签名人的身份和公钥，输出1 或0.其中:1表示签名有效，0表示签名无效.

1.4 盲签名方案的安全性

盲签名方案的安全性一般用无条件盲性和不可加一伪造性来刻画.

无条件盲性：给定两个盲化的消息签名对，随机选择其中一个进行去盲化处理.对于这个去盲化后的消息签名对，任意的多项式时间算法（签名人或区分器）能够区分正确的优势是可忽略的，则称这个盲签名方案满足无条件盲性.

不可加一伪造性：盲签名方案的不可加一伪造性可以通过一个游戏模型证明.该游戏由挑战者和攻击者交互进行.挑战者初始化系统后，将系统公共参数和公钥发送给攻击者，并提供询问谕言机.如Hash询问谕言机、私钥提取询问谕言机、盲签名询问谕言机等等.攻击者可以适应性选择询问，除了被攻击目标的私钥.攻击者获得l个被攻击目标的对应盲签名之后，若能输出l+1个被攻击目标的可验证有效的盲签名，则攻击者赢得游戏.若任意的攻击者在多项式时间内赢得游戏的概率是可忽略的，则称该盲签名方案满足不可加一伪造性.

2 格上无陷门的基于证书盲签名方案

2.1 构造的方案

格上无陷门的基于证书盲签名方案的构造具体如下：

2.2 正确性

签名的正确性可以由以下的等式容易验证.

2.3 安全性分析

1)无条件盲性.由签名方案的ΒlindSign算法的盲化步骤和去盲步骤可知，用于盲化和去盲的盲化因子x和h'均是均匀随机选择的.而且，签名人所收到的h''是经过盲化处理的，签名人无法从h''中获得任何信息.因此，假定从和中随机选取一个进行去盲化处理.对于签名人（或区分器）而言，由于未获得任何有效信息，因而签名人只能通过抛硬币决定输出b'.那么，签名人输出一个b'满足b'=b的优势是可忽略的.所以，该基于证书盲签名方案满足无条件盲性.

2)不可加一伪造性.在游戏过程中，若攻击者赢得游戏的优势是不可忽略的，则挑战者可以利用攻击者的能力输出一个Lyubashevsky 方案的有效伪造.挑战者向攻击者提供询问谕言机，同时向Lyubashevsky 方案请求询问.挑战者收到攻击者的询问后，若该询问所相关的信息与Lyubashevsky 方案无关，则挑战者自己建立询问谕言机并进行回答；否则，挑战者将攻击者的询问加以处理并转以询问Lyubashevsky方案，得到回复后，再处理成攻击者所需的回复并以此回复攻击者.当攻击者进行了l个被攻击目标的对应盲签名询问之后，输出l+1个被攻击目标的可验证有效的消息签名对.那么，其中至少由一个消息签名对不属于询问谕言机回复的签名结果.由此，挑战者可以对该消息签名对进行必要的处理，然后将它作为Lyubashevsky方案的伪造输出.

由Lyubashevsky方案的不可伪造性可知，攻击者在多项式时间内赢得游戏的概率是可忽略的.所以，该基于证书盲签名方案满足不可加一伪造性.

2.4 效率分析

该基于证书盲签名方案的构造采用了Lyubashevsky[25]的拒绝采样技术，从而大大降低了整体的计算复杂度.方案在存储开销方面，参照文献[25]的参数说明及实例，本方案的参数设置如下，见表1.

表1 方案的参数设置Tab.1 Parameters for our scheme

3 结论

Lyubashevsky 构建了一个无陷门的签名方案，采用拒绝采样技术，从而使得格基签名在趋于实用化道路上迈出了一步.在Lyubashevsky 工作的基础上构建了一个基于证书的盲签名方案.该方案同样采用拒绝采样技术，未使用陷门技术.从而，使得方案的计算复杂度大大下降.而且，方案满足无条件盲性和不可加一伪造性.方案基本满足一些电子商务的需求.