格上无证书代理重签名

范 祯, 欧海文, 裴 焘

1.中船重工集团公司第七二二研究所, 武汉430079

2.北京电子科技学院, 北京 100071

1 引言

1998 年Blaze、Bleumer 和Strauss 初次提出了代理重签名的概念[1].代理重签名中代理者 P 扮演了转换两个不同签名者对相同消息签名的角色, 即代理者P 在知道代理密钥的情况下可以将受托者B 对某一个消息的签名转换成委托者A 对该消息的签名, 并使得代理者P 对该消息的签名和委托者A 对该消息的签名是不可区分的, 但与受托者B 对该消息的签名是可区分的.代理重签名在数字版权管理、证书管理和构造跨域操作系统等方面有很好的应用前景.例如, 如今国家正在采用电子护照, 也就是在传统的护照文件中存储若干数目的数字签名, 假设用户C 拥有自己国家E (相当于受托者) 的良好身份签名SigE,当C 去另一个国家F (相当于委托者) 时, 边防警察(相当于代理者) 首先检查SigE 是否为真, 如果是真的, 那么可以将 SigE 转换成国家 F 对用户 C 的良好公民身份的签名 SigF, 通过边防局的公钥即可验证该用户是否通过边防警察的验收.2005 年Ateniese 和Honenberger[2]给出了代理重签名更具体的定义,并给出了具体的代理重签名方案.现有的代理重签名方案大多是基于公钥密码体制提出的, 通常公钥密码系统可以分为三类: 基于证书、基于身份和基于无证书, 其中基于证书的公钥密码系统需要可信中心CA对用户的公钥进行认证, 并且需要管理系统来管理用户的公钥信息, 如果用户过多, 那么很明显存在证书的管理问题.1984 年Shamir 首次提出基于身份的公钥密码体制[3], 该体制中用户的私钥通过密钥生成中心KGC 来产生, 公钥可以通过用户身份信息ID 生成, 解决了基于证书的证书管理问题, 但是如果 KGC被攻击或者在传送密钥的途中被攻击, 那么显然又存在密钥托管问题.2003 年Al-Riyami 和Paterson 首次提出无证书公钥的概念[4].无证书公钥密码方案利用KGC 与用户共同生成私钥的方式, 解决了基于身份的数字签名方案中存在的密钥托管问题.2005 年Huang 提出一个无证书签名方案[5], 并给出在随机预言机模型下无证书签名体制的安全模型, 2007 年又针对两种攻击者类型对该安全模型进行改进, 提出更完善的安全模型[6].

由于现在还没有发现多项式时间量子算法能够破解格上的困难问题, 所以目前认为格密码能够抵抗量子攻击.基于格理论设计的公钥密码方案除了抗量子攻击之外, 还有一些其他的优势: ①运算简单.因为格是离散加法交换群的子群, 格上的代数运算通常都是矩阵的加法或者矩阵和向量之间乘法之类的线性运算, 所以相比双线性对复杂的代数运算, 效率较高且运算更简单; 而且特殊的格比如循环格[7]、理想格[8]等具有一般格所不具有的特殊结构, 能够更好的提升密码方案的效率或者减少密钥存储空间; ②安全程度高.文献[9]已证明了格上困难问题在随机实例下的困难程度等价于最坏实例下的困难程度, 所以格上密码方案的安全性可以归约到格上最坏情况下的某些困难问题.2012 年 Lyubashevsky 提出随机预言机下高效的格上无陷门的签名方案[10], 其安全性基于小整数解问题(small integer solution problem, SIS) 问题, 利用了无抽样技术, 使得效率更高.在该签名的基础上, 2015 年 Tian M 等提出格上无证书签名方案[11], 相比其他同类型方案密钥尺寸更小、效率更高; 同年还构造了一个基于身份的双向代理重签名方案[12], 但是该方案的代理重密钥需要委托者和受托者的私钥才能生成.

本文对文献[11]的无证书方案中的密钥尺寸进行改进, 并对文献 [12]的代理重签名方案中基于身份和代理密钥生成的不足进行改进, 提出格上无证书代理重签名方案, 该方案相比已有的方案效率较高且密钥尺寸较小.

2 基础知识

本节将介绍基于格的公钥密码方案常用的一些相关的格基础知识, 包括格的定义、SIS 问题、格上的离散高斯分布、陷门和无抽样技术.

2.1 格

在几何学中, 格是 n 维空间中一组有着周期排列结构点的集合; 在代数学中, 格是集合 Rn的一个子群.

定义 1(格) 设 b1,b2,··· ,bm是 Rn上 m 个线性无关的向量, 则 b1,b2,··· ,bm的所有整系数倍的线性组合构成的集合称为格, 记作:

任意一组可以生成格的线性无关向量都可以称为该格的基, 例如, 在上述定义中 b1,b2,··· ,bm为格的一组基.另一方面, 如果一个 n 行 m 列的矩阵 B =(b1,b2,··· ,bm) 是一组格基, 那么可以将该格定义为Λ = L(B) = {Bx|x ∈Zm}.显而易见, 任意格的基都存在且不唯一, 例如当矩阵 B 是一组格基时, 则该格必定至少还存在另一个基矩阵−B.

定义 2(q-模格) 两种特殊的模 q 整数格:

2.2 SIS问题

格上的困难问题有很多种, 但这里主要介绍以下几个问题.

定义 3(SISq,n,m,β) 设 q 是一个整数, 矩阵β 是一个正实数, 找到一个非零向量 e ∈是 Ax=0 mod q 的解, 其中 ||e|| ≤ β.

定义 4(ISISq,n,m,β) 给定正整数参数m、n、非零实数β, 矩阵均匀随机选取, 以及任意均匀随机向量找到非零向量 v, 满足 Av ≡u(modq), 并且其范数 ||v||≤ β.

SIS 和ISIS 问题的困难程度是一样的.

2.3 格上的离散高斯分布

定义 5(统计距离) 某个集合Ω 上的两个分布X,Y 之间的统计距离被定义为:

若X,Y 的统计距离是可忽略的, 那么我们就说这两个变量是统计接近的, 即两个统计分布是不可区分的.

定义 6在线性空间 Rn中, 以向量 c ∈Rn为中心, 方差参数是s>0 的 n 维高斯函数为

其中 ∀x ∈ Rn.

定义 7假设 Λ ∈Rn为一个格, 在线性空间 Rn中, 以向量 c ∈Rn为中心, 实参数为 s > 0, 可以定义 n 维格 Λ 的离散高斯分布为

其中 ∀x ∈ Λ, ρs,c(Λ)= ∑x∈A ρs,c(x).

2.4 格上的陷门

公钥密码体制可以归结为设计一个陷门单向函数.单向函数是正向容易计算, 反向计算不可行的函数; 而在知道某些信息的情况下, 单向函数的反向计算是容易的函数则称为陷门单向函数.函数 f(x) =Ax(modq) 是一个单向函数 (其中因为该函数的原像不唯一, 所以求解原像较为困难.而基于SIS 问题的困难性, 当规定原像x 是范数较小的向量时, 可以将其看作一个陷门单向函数.

文献[13]中给出该陷门的生成算法TrapGen 和原像取样算法SamplePre 见算法1 和算法2.

利用上述生成算法得到的陷门可以通过调用以下算法得到上述单向函数的范数较小的原像, 具体算法如算法2.

利用原像取样算法可以得到小矩阵的算法如算法3.

2.5 无抽样技术

文献 [10]设计的签名方案中没有用到上述的原像抽样算法进行签名, 而是基于随机预言机利用无抽样技术设计了一种无陷门签名的方案.因为无抽样技术效率较高, 所以现在已有的较多格上高效率的签名方案都是利用该技术来设计的.

引理1[9]Rm上的离散高斯分布上, 有

其中 σ >0, x ∈Rm.

由文献[10]中可得, 在上述引理的基础上, 其中c ∈Zm, a 是实数, 可以得出以下结论:

3 格上无证书代理重签名

3.1 格上无证书代理重签名方案

(1) 系统初始化

①输入安全参数n, 运行TrapGen(n,m,q), 输出中一个服从随机均匀分布的矩阵A 和格Λ⊥(A) 的一组基

②选取两个哈希函数

③公共参数param={A,H1,H2}, 主私钥是sk=B.

(2) 部分密钥提取

假设KGC 要生成身份为ID 的用户的部分密钥值, 具体步骤如下:

①计算F =H1(ID);

②KGC 运行算法SampleMat(A,B,s,F), 输出矩阵DID∈Zm×k, 然后将DID发送给该用户, 其中

③DID为该用户的部分密钥, 并将其发送给该用户.

(3) 密钥生成

对于需要生成密钥的用户(身份为ID), 密钥生成的步骤如下:

①从{−d,··· ,0,··· ,d}m×k中选择一个服从随机均匀分布的矩阵CID, 将矩阵CID设置为该用户的秘密值, 其中

③该用户的公钥为(A,TID=T), 私钥为SID=S.

(4) 代理重密钥的生成

假设委托者 I 的身份是 IDI, 受托者 M 的身份是 IDM, 那么这两个用户的公钥分别表示为 (A,TIDI)和(A,TIDM), 私钥分别表示为SIDI和SIDM.那么该代理重密钥的生成步骤如下:

①受托者M 从Zm×k中选择的一个服从随机均匀分布的矩阵R;

②受托者M 利用他的私钥SIDM和矩阵R 计算代理重密钥KM→I=SIDM+R;

③受托者M 将矩阵R 秘密分享给委托者I, 将代理重密钥KM→I通过秘密信道发送给代理签名者P;

④委托者I 利用自己的私钥SIDI和矩阵R 计算KI→M= SIDI+R, 然后将KI→M通过秘密信道发送给代理签名者P;

(5) 签名

假设需要对消息 µ 进行签名, 签名者的身份是 ID, 则签名者的公钥是 (A,TID), 私钥是 SID.那么该签名者对消息µ 的签名步骤如下:

②计算c=H2(Ay,µ);

③计算zID=SIDc+y;

(6) 代理重签名

代理签名者P 利用受托者M 的对消息µ 的签名sig=(zIDM,c) 和代理重密钥进行以下步骤:

①代理签名者P 首先验证受托者M 的签名sig=(zIDM,c), 验证步骤见下述(7), 如果验证通过, 则继续进行②, 否则停止;

②代理签名者P 利用sig=(zIDM,c), KI→M和KM→I计算

③代理者P 代替委托者I 对消息µ 的签名为sig=(zIDI,c).

(7) 验证

假设需要验证身份为ID 用户的签名sig=(zID,c), 那么验证者V 进行验证的步骤如下:

②利用该签名用户的公钥(A,TID), 计算c′=H2(AzID−(H1(ID)+TID)c,µ);

③判断(c′=c), 如果相等, 则验证通过; 否则验证不通过, 输出“Reject”.

3.2 方案分析

3.2.1 正确性分析

由于该代理重签名的验证用户 ID 对消息 µ 的签名时, 需要满足的两点分别是 c =分析如下:

(1) 关于第一点的正确性分析分为以下两点:

①当签名为身份为ID 的用户的直接签名时, 因为

所以 H2(Ay,µ)=H2(AzID− (H1(ID)+TID)c,µ).

②当签名为代理者P 利用代理签名密钥和受托者M 对消息µ 的签名得到委托者I 的签名时,

紧接着类似①的正确性分析, 可以验证AzIDI−(H1(IDI)+TIDI)c=Ay, 因此可得

(2) 关于第二点的正确性分析如下.

因为zID= SIDc+y, 其中y 服从分布, 由拒绝采样算法[10]和离散高斯分布的性质可以知道, 以概率输出的SIDc+y 满足的分布与分布统计上接近(且统计距离为2−ω(logm)/M, 其中 M ≈ e), 所以由引理1 可知, 签名 zID以 1 − 2−m的概率满足

综上所述, 该代理重签名方案是正确的.

3.2.2 安全性分析

一般情况下, 无证书签名方案的安全性通常需要从两方面证明, 一方面需要证明签名方案对外部攻击(第一类攻击) 是安全的, 此时的敌手仅仅能替换用户的公钥, 而不能够得到任意用户的部分密钥值; 另一方面需要证明签名方案对内部 KGC 的攻击 (第二类攻击) 是安全的, 此时的敌手仅仅能获得 KGC 的私钥, 而不能替换用户的公钥.接下来针对这两类敌手攻击对上述签名无证书代理重签名方案进行安全性的证明.

第一类攻击:

命题 1假设哈希函数可以被看作是随机预言机, 且小整数解问题 SISq,n,m,β是困难的 (其中 β =那么该无证书代理重签名方案中任一用户ID 对任意消息µ 的签名, 如果被第一类攻击的敌手 A 在多项式时间内成功伪造, 则存在一个算法以不可忽略的概率破解 SISq,n,m,β问题.也就是说, 在随机预言机模型和 SISq,n,m,β问题难解的情况下, 该无证书签名方案对第一类攻击在选择消息攻击下是存在不可伪造的.

证明:这里利用第一类攻击敌手A 和挑战者C 两者之间进行的一个游戏来证明该签名方案是不可伪造的.假设敌手A 能够在多项式时间内以不可忽略的概率伪造签名, 那么挑战者C 可以利用敌手A 伪造的签名以不可忽略的概率解决SIS 问题.

挑战者C 首先建立四个列表, 第一个列表T1存储的分别是(用户身份ID, F =H1(ID), 部分密钥值D, 秘密值C, 公钥P, 私钥S), 第二个列表T2存储的分别是(消息µ, 随机值y ←, c=H1(Ay,µ)),第三个列表T3存储的分别是(用户身份ID, 消息µ, 签名sig=(c,z)), 第四个列表T4存储的分别是(委托者身份IDI, 受托者身份IDM, 代理重密钥KI→M, 代理重密钥KM→I).当系统初始化已经进行后, 挑战者C 可以调用创建用户的算法l: 输入系统的公共参数param、主私钥B 和用户的身份ID 后, 首先查询列表 T1, 如果表中存在身份 ID, 则退出; 否则, 在和 {−d,··· ,0,··· ,d} 中分别随机抽取 F 和秘密值 C, 调用算法 SampleMat(A,B,s,F) 得到部分密钥值 D, 再分别计算公钥 P = AC mod q ∈和私钥 S =C+D, 最后将 (ID,F,D,C,P,S) 存入列表T1后退出.

敌手A和挑战者C进行游戏的步骤如下:

(1) 系统建立

挑战者 C 首先选择安全参数 n, 素数 q ≥3, m ≥5n log q, 运行算法 TrapGen (1n), 输出一个服从随机均匀分布的矩阵 A 和格 Λ⊥(A) 的一组基其中

(2) 询问(敌手A 根据自己的需求对挑战者C 进行以下询问)

①哈希询问

a.H1询问: 敌手 A 向挑战者 C 发送 IDi, 希望得到对应的哈希值 Fi= H1(IDi).C 首先查询列表T1, 如果列表中已经存在该用户, 则发送对应的Fi给A; 否则C 调用算法l, 输入用户的身份IDi, 当算法运行完成后, C 查询列表 T1, 将 IDi对应的 Fi直接发送给 A.

b.H2询问: 敌手 A 向挑战者 C 发送消息 µi, 希望得到对应的哈希值.C 首先查询列表 T2, 如果列表中已经存在该消息 µi, 那么直接发送对应的 ci给 A; 否则在 {c:c ∈{−1,0,1}κ,||c||1≤ κ} 中随机抽取ci发送给A, 再随机选择y ←, 最后再将(µi,yi,ci) 存入列表T2.

②部分密钥提取询问

敌手A 向挑战者C 发送IDi, 希望能够得到该用户的部分密钥值Di.C 首先查询列表T1, 如果列表中已经存在该用户, 那么直接发送对应的部分密钥值 Di给 A; 否则 C 调用算法 l, 输入用户的身份 IDi,当算法运行完成后, C 查询列表T1, 将IDi对应的部分密钥值Di直接发送给A.

③用户密钥提取询问

由于第一类敌手可替换用户公钥, 所以敌手A 可以进行如下两种密钥提取询问.

a.不替换用户公钥

敌手A 向挑战者C 发送IDi, 希望得到该用户的公私钥(Pi,Si).C 首先查询列表T1, 如果列表中已经存在该用户, 那么发送对应公私钥 (Pi,Si) 给 A; 否则 C 调用算法 l, 输入身份 IDi后, l 运行完成后, C查询列表 T1, 将 IDi对应的公私钥 (Pi,Si) 发送给 A.

b.替换用户公钥

敌手 A 向挑战者 C 发送 (IDi,Pi,Ci), 希望得到该用户的的私钥 (其中 Pi和 Ci分别是 A 替换该用户的公钥和秘密值).C 首先查询列表T1, 然后分情况进行以下几种操作:

i.如果列表T1中存在IDi, 并且对应的公钥等于Pi, 那么C 直接将该用户对应的私钥Si发送给A;

ii.如果列表T1中存在该用户IDi, 但是该用户的公钥不等于Pi, 那么C 利用表T1中的部分密钥值Di, 重新计算私钥Si= Ci+Di, 然后将T1中 IDi对应的秘密值和私钥分别修改为 Ci和 Si, 同时将Si发送给A.

iii.如果列表 T1中不存在 IDi, C 在中随机抽取 Fi, 调用算法 SampleMat(A,B,σ,Fi) 得到部分密钥值Di, 再计算私钥 Si=Ci+Di, 最后将(IDi,Fi,Di,Ci,Pi,Si) 存入列表 T1, 同时将私钥Si发送给A.

④代理重密钥询问

敌手A 向挑战者C 发送(IDi,IDj).C 查询列表T4将对应的代理重密钥发送给A.

⑤签名询问

敌手 A 向挑战者 C 发送 (IDi,µi), 希望得到该用户对消息 µi的签名.C 首先查询列表 T3, 如果列表中已经存在该用户对消息µi的签名, 则将对应的签名sigi发送给A; 否则C 调用算法l (因为如果T1中已经存在该用户, 那么算法l 将直接退出), 输入IDi, 当该算法运行完成后, C 查询列表T1和T2, 利用T1中用户IDi所对应的 Si和T2中消息µi所对应的(yi,ci), 计算zi=Sici+yi, 最后将(IDi,µi,(ci,zi))存入列表 T3, 同时将 (ci,zi) 发送给 A.

⑥重签名询问

敌手 A 向挑战者 C 发送 (IDi,IDj,µj,sigj= (zj,cj)), 希望 C 利用用户 IDj对消息 µj的签名sigj= (zj,cj) 得到用户 IDi对该消息的签名.挑战者C 首先对 sigj= (zj,cj) 签名进行验证, 若通过则对(IDi,µj) 进行签名询问的过程, 将结果返回给A; 否则终止询问.

(3) 伪造

当上述询问进行完成后, 敌手A 根据已有的经验输出任一用户的身份ID∗和公钥P∗(ID∗在上述密钥询问中没有询问过), 能够在多项式时间内伪造该用户 ID∗对任意消息 µ∗的签名sig∗= (z∗,c∗) (这里的消息 µ∗可以被认为在前边的H2询问中已经询问过了), 并且使得验证算法Verify 以不可忽略的概率输出为 “Accept”.

此时挑战者 C 得到用户 ID∗对消息µ∗的伪造签名后, 根据一般分叉引理[10]可知, 当挑战者 C 重新选取消息µ∗所对应的H2询问值时, 敌手A 还可以以不可忽略的概率伪造出用户ID∗对消息µ∗的签名另一个签名 sig′=(z′,c′), 使得

又因为H1(ID∗)=ABID∗, TID∗=ACID∗(其中BID∗是用户ID∗的部分密钥值, CID∗是用户ID∗的秘密值) 所以

第二类攻击

命题 2假设哈希函数可以被看作是随机预言机, 且小整数解问题 SISq,n,m,β是困难的 (其中 β =那么该无证书代理重签名方案中任一用户ID 对任意消息µ 的签名, 如果被第二类攻击的敌手 A 在多项式时间内成功伪造, 则存在一个算法以不可忽略的概率破解 SISq,n,m,β问题.也就是说, 在随机预言机模型和 SISq,n,m,β问题难解的情况下, 该无证书签名方案对第二类攻击在选择消息攻击下是存在不可伪造的.

证明:类似于命题1 的证明, 依然利用敌手A (第二类攻击) 和挑战者C 两者之间进行的一个游戏来证明该签名方案是不可伪造的.假设敌手A 能够在多项式时间内以不可忽略的概率伪造签名, 那么挑战者C 可以利用敌手A 伪造的签名以不可忽略的概率解决SIS 问题.

敌手 A 首先对挑战者 C 进行相应的询问, 但是与命题 1 不同的是第二类攻击者是可以知道系统中用的主私钥而不能替换用户的公钥.当A 相应的询问进行完成后, A 根据已有的经验输出任一用户的身份 ID∗(ID∗在上述密钥询问中没有询问过能够在多项式时间内伪造该用户 ID∗对任意消息 µ∗的签名sig∗=(z∗,c∗), 并且使得验证算法以不可忽略的概率输出为 “Accept”.

此时挑战者 C 得到用户 ID∗对消息 µ∗的签名后, 根据一般分叉引理[10]可知, 当挑战者 C 重新选取消息µ∗所对应的H2询问值时, 敌手A 还可以以不可忽略的概率伪造出用户ID∗对消息µ∗的另一个签名 sig′=(z′,c′), 使得

又因为 H1(ID∗)=ABID∗, TID∗=ACID∗(其中 BID∗是用户 ID∗的部分密钥值, CID∗是用户 ID∗的秘密值) 所以

3.2.3 效率分析

文献[14]提出了一个格上无证书加密方案, 文献[11,15,16]分别提出了格上无证书的签名方案, 将本文的无证书签名方案与它们进行对比得出表1.其中 TSamM,TSamP,TBas,TTrap,TRand,TExt,THash,Tmul,分别是算法 SampleMat、SamplePar、BasicDel、TrapGen、RandBasis、ExtBasis、Hash 函数和数乘运算所需要的时间.

表1 中显示本文和文献 [11]中的无证书签名方案的公钥、私钥和签名长度相同, 只是 m 值的取值范围不同, 本文中 m>5n log q, 文献[11]中5n log q >64+n log q/(2d+1) 和文献 [15,16]中的无证书签名方案相比, 公钥、私钥和签名尺寸都有所减小(由于m>k).文献[14]是无证书公钥加密方案, 相比之下本文的公钥长度有所减少, 但是私钥长度相对更大.本文采用了无抽样技术, 具有较高的效率.

表1 一些无证书签名方案的比较Table 1 Comparison of some certificateless signature schemes

又本文代理重签名方案是基于无证书, 防止密钥托管问题.改进后的代理重密钥生成能够抵抗中间人攻击, 仅仅需要矩阵之间的加运算, 代理重签名需要矩阵和向量之间的乘法运算以及向量之间的加减运算,运算复杂度较低.表2 将新方案与已有的方案在安全性、代理重签名密钥和签名尺寸作对比, 从而得出新方案相比已有的两种代理重签名方案在效率不变的情况下安全性方面更好一些.

表2 一些代理重签名方案的比较Table 2 Comparison of some proxy re-signature schemes

4 结语

我们首先改进了文献[11]中的无证书签名方案, 使得密钥长度有所减小, 然后在此基础上对文献[12]中的格上基于身份的代理重签名方案中两个不足之处进行改进, 提出了第一个格上的无证书代理重签名方案, 新方案具有更好的安全性和较好的运行效率.但是该代理重签名方不能够抵抗受托者和代理者的合谋攻击, 下一步应该研究抵抗合谋攻击的代理重签名方案.