证明: 令n 为安全参数.方案的其他参数设定确保算法SampleD和ExBasis在本方案中可以正确的执行.具体的,因为PKG知道格Λ⊥q(A) 的陷门基,从而PKG可以生成更大维数的格Λ⊥q(AID) 的陷门基.即密钥提取算法可以正确的运行.另一方面,签名v 是算法SampleD的输出,从而该签名以极大概率可以被验证算法接受.□

3.5.2.1　安全性证明

定理3.3 假如存在敌手A 能够以概率∈攻破方案在静态选择消息和选择身份攻击下的不可伪造性,其中敌手可以执行q1 次密钥提取询问和q2 次签名询问,则可以构造一个挑战者C 以概率解决一个SIS 问题实例,其中l 为消息的长度.

证明: 假设挑战者收到一个SIS问题的实例

其中,挑战者希望得到一个小向量v 满足

敌手首先输出挑战身份ID* =(id*[1],··· ,id*[k])设ID*的汉明重量为k*.令

其中

系统建立:C 执行A 得到q2 个消息μ(1),··· ,μ(q2) .接下来C 计算P 为所有比特串p ∈{0,1}≤k 的集合,其中p 为不是所有μ(j) 前缀的最小的比特串.由文献[45],这样的集合可以在多项式时间内计算得到并且p 的个数至多为lq2.

接下来,C 从P 中随机的选择一个p,并设p 的汉明重量为t,p 的长度为|p|.则挑战者生成公钥A,Ai,Bi 如下:

1.A=A0.

2.由[39],生成k - k* 个均匀随机矩阵及对应格 的陷门基 对i = 1,2,··· ,k* 并且,其他矩阵

3.由[39]产生|p|-t 个陷门格及其陷门基 .如果p[j]=0,令Bj = .如果p[j]=1,令Bj = .

4.随机选择一个非零小向量e ∈,满足计算y= (modq).C 发送公钥(A,Ai,Bj,y)给敌手,其中i ≤k,j ≤l.挑战者维护两个列表用来分别存储提取询问和签名询问的答案.

提取询问: 对一个新鲜的消息ID ID* ,必存在一个位置t0 满足id[t0] = 1 并且id*[t0] = 0,否则终止游戏并宣布失败.挑战者C 如密钥提取算法中所示生成身份ID 对应的矩阵AID .于是

作为身份ID 的密钥.

秘密地发送TID 作为本次询问的回复并将该回复存入列表L1.(在此过程中如果ID已经被询问过,则应返回与列表中相同的答案.)

签名询问: 给定消息μ(i) = (μ[1],μ[2],··· ,μ[l]) 和身份ID ,C 根据μ[i] = 0 或μ[i]=1 选择矩阵Bi.挑战者C 记

其中μ[j1]=μ[j2]=···=μ[jl*]=1.

分以下两种情形讨论:(www.daowen.com)

一、ID ID* 由于挑战者知道格Λ⊥q(AID)的陷门基,从而他可以为消息μ(i) 生成身份ID 的签名v.最后,挑战者存储(v,μ(i),ID)到列表L2.

二、ID =ID*.

首先比特串p 不是消息μ(i) = (μ[1],μ[2],··· ,μ[l]) 的前缀.不失一般性,我们假设p[t1] = p[t2] = ··· = p[tp*] = 1,于是以概率存在一个位置t′ 满足t′ ＜|p|,t′ ti,i = 1,2,··· ,p* 并且μ[t′] = 1 .(若不然,终止游戏并宣布失败.) 于是挑战者掌握了格Λ⊥q(Bt′)的陷门基,从而挑战者可以生成身份ID*对消息μ(i)的签名v:

当所有询问结束,敌手A 以概率∈输出挑战身份ID*对消息μ*的签名v*.于是有

成立,其中k*and l*分别是身份信息和消息的汉明重量.

如果比特串p 不是消息μ*的前缀,A 终止,否则C 可以解决SIS问题实例:

挑战者根据矩阵AID*μ* 和矩阵 间的关系,将其他的矩阵级联到矩阵AID*μ* 并得到新的矩阵.接下来,挑战者相应的将(k-k*)+(l-l*)个m 维零向量添加到签名向量v*得到一个新的向量v,满足=y(modq).

由于挑战者知道满足y= (modq)的向量e,从而

成立.若ev,则挑战者得到一个SIS问题的解.由[38],ev 将以极大概率成立.

我们来分析挑战者的优势,挑战者可以完美的模拟上述游戏,只要:

1.在密钥提取询问阶段存在一个位置t 满足id[t]=1 并且id*[t]=0.

2.在签名询问阶段存在一个位置t′满足t′ ＜|p|,t′ ti,i=1,2,··· ,p*并且μ[t′]=1.

注意到方案中的身份信息是一个安全hash函数的输出,从而在身份信息中0和1的分布是均衡的.于是密钥提取阶段以极大概率存在位置t.

另一方面,由简单的概率计算知位置t′存在的概率为以下说明概率是可忽略的.不失一般性,假设p 是集合P 中长度最短的比特串,从而比特串p||0 和p||1也不是任何μ(i) 的前缀.即,如果p 是比特串p′ 的前缀,则p′ 不是任何μ(j) 的前缀.长度为l 的比特串p′ 的个数有2l-|p| .由于集合P 中至多有lq2 个比特串而p 是其中最短的比特串,从而有lq22l-|p| ≤2l 成立,即|p| ≥log2 lq2 .因此集合P 中的任意比特串的长度依然满足|p| ≥log2 lq2 .从而概率是可忽略的.又因为游戏中比特串p 均匀随机选取的,从而p 是消息μ* 的前缀的概率为 从而挑战者可以以概率来求解SIS问题.

□

3.5.2.2　效率分析

将我们的方案与R¨ucurt的无分层的IBS方案比较[61],本方案在公钥尺寸、签名尺寸和计算消耗上均存在优势.表3.2 给出了两者在空间效率上的比较,其中k*和l*分别是身份信息和消息的汉明重量.直观起见可以作如下合理的假设:k/2=k*,l/2=l*.表3.3给出了两个方案在计算消耗上的效率比较,其中psf 和sa 分别代表原像抽样函数和陷门抽样函数的计算代价,而sam 和sav 分别代表按照相应的高斯分别抽取一个随机矩阵和抽取一个随机向量的计算代价.

表3.2　空间效率比较

表3.3　计算效率比较

注: 我们需要指出的是,本文方案无法提供IBS的分层结构,这是因为我们的的新型矩阵赋值原则无法保证在分层结构下i层身份ID 和i+1层身份(ID||0)被赋值的矩阵是不同的.