n 上 m 个线性无关的向量，格 Λ 定义为所有这些向量的整数线性组合构成的集合，即 
}，其中向量组 b 1 , b 2 ,…, b m 构成格 Λ 的一组基 B . 张彦华 胡予濮
(综合业务网理论与关键技术国家重点实验室(西安电子科技大学) 西安 710071) (yhzhangxidian@163.com)
摘 要： 可验证加密签名(verifiably encrypted signature, VES)能够有效地保证互联网上交易过程的公平性.VES的核心思想是：签名者利用仲裁者的公钥对自己所签发的一个普通数字签名进行加密，随后证明密文中确实包含一个普通签名，任何验证者都可以利用仲裁者的公钥来验证其真实性，但在没有签名者或仲裁者的帮助下无法从中提取出普通签名；当争议发生时，验证者可以要求仲裁者从可验证加密签名中恢复出签名者的普通签名.利用Agrawal等人在美密2010上给出的固定维数的格基委派技术、格上原像抽样算法和差错学习问题的非交互零知识证明，该文构造出一个新的格上可验证加密签名方案，并在随机预言机模型下严格证明了其安全性.与已有的可验证加密签名方案相比，该方案要求签名者根据仲裁者公钥生成签名者公私钥对，构造简单，公私钥和签名尺寸更短，效率更高，并且能够抵抗量子攻击.
关键词： 可验证加密签名(VES)；固定维数；格；随机预言机模型; 差错学习问题
互联网在线交易已逐渐成为日常生活中比较重要的商品交换方式，如何在分布式网络中保证交换过程的公平性是电子商务安全亟待解决的关键问题之一.1997年，Asokan等人 [1] 首次提出可验证加密签名(verifiably encrypted signature, VES)的概念.可验证加密签名能够有效地保证互联网上交易过程的公平性.一个可验证加密签名方案包含3个参与者：签名者(又称用户)、验证者和可信第三方(又称仲裁者).VES的核心思想是：签名者利用仲裁者的公钥对自己所签发的一个普通数字签名进行加密，随后证明密文中确实包含一个普通签名，任何验证者都可以利用仲裁者的公钥来验证其真实性，但在没有签名者或仲裁者的帮助下无法从中提取出普通签名；当争议发生时，验证者可以要求仲裁者从可验证加密签名中恢复出签名者的普通签名.
基于双线性Diffie-Hellman假设，Boneh等人 [2] 于2003年给出了第1个有效的非交互的VES方案.签名验证过程不需要零知识证明，而且方案在随机预言机模型下是可证明安全的.自此以后，VES引起了众多学者的广泛关注，很多基于标准数论假设的VES方案相继被提出 [3-7] .
近年来，基于格构造新型密码系统因具有较高的渐进效率、运算简单和抗量子攻击等特点，成为后量子时代密码领域的研究热点，并取得了一系列研究成果 [8-11] .2010年，Rückert等人 [12] 构造出第1个基于格的标准模型下的VES方案，然而该方案是静态化的.2011年，Wang等人 [13] 构造出第1个基于格的随机预言机模型下非静态化的VES方案，然而该方案不满足强不可伪造性.2014年，Kim等人 [14] 构造出一个高效的基于格的VES方案，该方案不再额外需要梅克尔树(Merkle trees)，但是签名者的公私钥尺寸和可验证加密签名的尺寸都明显较大.
本文增添仲裁者密钥生成阶段来生成仲裁者公私钥，并利用Agrawal等人 [15] 提出的固定维数的格基委派技术来生成签名者密钥，从而有效地减小签名者的公私钥尺寸；然后运用原像抽样算法和差错学习问题(learning with errors, LWE) 的非交互零知识证明构造出一个新的格上可验证加密签名方案，并在随机预言机模型下严格证明了其安全性.与已有的基于格的可验证加密签名方案相比，该方案构造简单，公私钥和签名尺寸更短，效率更高.
1.1 格
定义1. 设 b 1 , b 2 ,…, b m 是 n 上 m 个线性无关的向量，格 Λ 定义为所有这些向量的整数线性组合构成的集合，即 }，其中向量组 b 1 , b 2 ,…, b m 构成格 Λ 的一组基 B .
定义2. 设 q 是一个素数， A ∈ n × mq ， u ∈ nq ，则：
，
(1)
.
(2)
定义3. 对任意 s >0，定义以向量 c 为中心， s 为参数的格 Λ 上的离散高斯分布为：
，
(3)
其中 x ∈ Λ ， ρ s , c ( x )=exp(- π ‖ x - c ‖ 2 
s 2 ).
1.2 重要算法
引理1 [8] . 设 n 是正整数， q ≥2, m ≥2 n lb q ,对于除了至多2 q - n 的部分之外所有的 A ∈ n × mq 以及任意 
，向量 u = Ae mod q 的分布统计接近 nq 上的均匀分布，其中 e ∈ D m , s .
格上陷门抽样算法( TrapGen )、离散高斯抽样算法( SampGau )和原像抽样算法( SampPre )由如下2个引理给出.
引理2 [9] . 设 n 是正整数， q ≥2， m >5 n lb q ,存在概率多项式时间(probabilistic polynomial time, PPT)算法 TrapGen ( q , n )，输出 A ∈ n × mq 和 T A ∈ m × mq ，其中 A 在 n × mq 上是统计均匀的， T A 是格 
的陷门基，且满足
‖ T A ‖≤ O ( n lb q ),‖ 
‖ 
).
引理3 [8] . 设 n 是正整数，素数 q ≥2， m > n ，矩阵 A ∈ n × mq . T A ∈ m × mq 是格 的陷门基，高斯参数 s ≥‖ 
‖ 
).对于 c ∈ m 和 u ∈ nq ，有：
1) Pr [‖ x ‖> 
).
2) 存在PPT算法 SampGau ( A , T A , s , c )，输出一个统计接近 
的格向量 
).
3) 存在PPT算法 SampPre ( A , T A , u , s ),输出一个统计接近 
的格向量 
).
Gordon等人 [10] 提出了一个变形的格基陷门抽样算法( OrthoSamp )，由如下引理给出.
引理4 [10] . 设 n 是正整数，素数 q ≥2，正整数 m ≥ n +8 n lb q ，矩阵 B ∈ n × mq 的列向量的子集合构成 nq .存在PPT算法 OrthoSamp ( q , B )，输出矩阵 A ∈ n × mq 和 T A ∈ m × mq ，使得：
1) AB T =0 mod q ，其中 A 的秩为 n ，且在 n × mq 上是统计均匀的.
2) T A 是格 
的陷门基，即 AT A =0 mod q .
3) T A 的任一列向量 t i ∈ mq 统计接近 
，其中 
).
定义4. 对于矩阵 A ∈ m × m ，如果 A mod q 作为 
中的矩阵是可逆的，则称 A 是 q 可逆的.
定义5. 设 
，令 D m × m 表示按照( D m , σ R ) m 来抽取的并且在 m × m 上 q 可逆的矩阵分布.
Agrawal等人 [15] 提出的格基委派技术( BasisDel )能够生成固定维数的格基陷门，由如下引理给出.
引理5 [15] . 设 n 是正整数， q >2， m >2 n lb q ， T A ∈ 是格 的陷门基，可逆矩阵 R ∈ D m × m ，高斯参数 s ≥‖ ‖ 
m) 3 .存在 PPT 算法BasisDel( A , R , T A , s ),输出 B ∈ n × mq 和 T B ∈ m × mq ，其中 B = AR -1 mod q ， T B 是格 
的陷门基，且对于参数 s 的最小值满足‖ 
‖≤‖ ‖ 
.
引理5需要知道格 的陷门基 T A 和可逆矩阵 R 才能得到格 
的陷门基.然而，如引理6指出，在选取可逆矩阵 R 的情况下，不用知道格 的陷门基就可以得到格 的陷门基.该性质对方案的安全性证明特别重要.
引理6 [15] . 设 n 是正整数， q >2， m >2 n lb q ，矩阵 A ∈ n × mq 的列向量的子集合构成 nq .存在PPT算法 SampRwith ( A )，输出矩阵 B ∈ n × mq ， R ∈ m × mq 和 T B ∈ m × mq ，其中 B = AR -1 mod q ，其分布统计接近于 D m × m ，矩阵 T B ∈ m × mq 是格 
的陷门基，且满足‖ ‖ ).
1.3 格上困难问题
定义6. 小整数解问题(small integer solution, SIS).设 n 是正整数， q 为素数，给定随机矩阵 A ∈ n × mq 和实数 β = poly ( n )，找到非零向量 e ，使得 Ae =0 mod q 且‖ e ‖≤ β .
定义7. 非齐次小整数解问题(inhomogeneous small integer solution, ISIS).设 n 是正整数， q 为素数，给定矩阵 A ∈ n × mq 和向量 y ∈ nq ，实数 β = poly ( n )，找到非零向量 e ，使得 Ae = y mod q 且‖ e ‖≤ β .
引理7 [7] . 设 n 是正整数, m , β = poly ( n )，对于任意素数 
，平均情况下的SIS和ISIS问题的困难性与最差情况下的近似最短独立向量问题(shortest independent vector problem, SIVP)的困难性是相同的，其近似因子为 γ 1 = β × 
).
定义8. 差错学习问题(learning with errors, LWE).设 n 是正整数， q 为素数，对任意0< α <1，定义 ψ α 为期望值为0、标准差为 α 
的[0,1)上的正态分布，对应的 q 上的离散分布为 
.定义 
为 
nq × q 上的分布，其中 s ， u i ∈ nq 是随机选取的向量， x i ∈ q 依分布 独立随机选取.LWE问题是指给定 A s , χ 上多项式个样本量，找到向量 s ∈ nq .
引理8 [16] . 设 n 是正整数，素数 
α ，如果存在一个有效的量子算法解决LWE问题，那么就存在一个有效的量子算法解决最差情况下的近似SIVP问题，其近似因子为 
α ).
1.4 格上非交互零知识证明
2013年，Laguillaumie等人 [17] 给出了一个满足如下ISIS关系的非交互零知识证明协议，即
R ISIS ={( A , y , β ; x )∈ n × mq × nq × × m ;
Ax = y mod q ,‖ x ‖≤ β }.
(4)
利用LWE困难问题与ISIS困难问题的对偶性，Laguillaumie等人同时给出了满足如下LWE关系的一个有效的零知识证明协议，即
.
(5)
2.1 定 义
可验证加密签名由如下8个PPT算法构成.
1) 系统建立( Setup ).给定安全参数 λ ，输出系统公开参数 PP .
2) 仲裁者密钥生成( Adj - KeyGen ).给定公开参数 PP ，输出仲裁者公私钥对( APK , ASK ).
3) 签名者密钥生成( KeyGen ).给定公开参数 PP 、仲裁者公钥 APK ，输出签名者公私钥对( PK , SK ).
4) 普通签名生成( Sign ).给定公开参数 PP 、私钥 SK 和消息 M ，输出普通签名 σ .
5) 普通签名验证( Verify ).给定公开参数 PP 、公钥 PK 、签名 σ 和消息 M ，输出接受或拒绝.
6) 可验证加密签名生成( VES - Sign ).给定私钥 SK 、消息 M 和仲裁者公钥 APK ，输出可验证加密签名 ω .
7) 可验证加密签名验证( VES - Verify ).给定公钥 PK 、 APK 、签名 ω 和消息 M ，输出接受或拒绝.
8) 仲裁( Adj ).给定公钥 PK 、 APK 、仲裁者私钥 ASK 、可验证加密签名 ω 和消息 M ，输出普通签名 σ .
可验证加密签名方案的正确性需满足如下2点：
1) 运用 VES - Sign 算法生成的可验证加密签名 ω 必须能通过 VES - Verify 算法的验证；
2) 仲裁者运用 Adj 算法可以有效地从可验证加密签名 ω 中恢复出原始普通签名 σ ，且 σ 必能通过 Verify 算法的验证.
2.2 安全模型
可验证加密签名方案应满足强不可伪造性、强不透明性和可提取性3个安全属性.可通过攻击者与挑战者的交互游戏来定义其安全性.
定义9. 强不可伪造性.若不存在多项式有界的敌手A 1 能以不可忽略的优势赢得以下游戏，则称一个VES方案是强不可伪造的.
1) 系统建立.挑战者C 1 输入安全参数 λ ，运行 Setup ， Adj - KeyGen 和 KeyGen 算法生成VES方案的公开参数 PP 和所有公私钥对( APK ， ASK )，( PK ， SK )，并将( PP , APK , ASK , PK )发送给敌手A 1 .
2) 询问阶段.A 1 适应性地进行多项式次如下询问.
① 普通签名生成询问.C 1 运行 Sign 算法可获得任何消息 M 的普通签名 σ ，并返回给A 1 .
② 可验证加密签名生成询问.C 1 运行 VES - Sign 算法获得任何消息 M 的VES签名 ω ，并返回给A 1 .
3) 伪造阶段.最后，敌手A 1 输出一个消息 M * 及其VES签名 ω * .
敌手A 1 赢得上述游戏当且仅当：
1) ω * 是消息 M * 的一个合法VES；
2) ( M * , ω * )不是一个可验证加密签名生成的询问结果.
定义10. 强不透明性.若不存在多项式有界的敌手A 2 能以不可忽略的优势赢得以下游戏，则称一个VES方案是强不透明的.
1) 系统建立.挑战者C 2 输入安全参数 λ ，运行 Setup ， Adj - KeyGen 和 KeyGen 算法生成VES方案的公开参数 PP 和所有公私钥对( APK ， ASK )，( PK ， SK )，并将( PP , APK , PK )发送给敌手A 2 .
2) 询问阶段.A 2 适应性地进行多项式次如下询问.
① 普通签名生成询问.C 2 运行 Sign 算法可获得任何消息 M 的普通签名 σ ，并返回给A 2 .
② 可验证加密签名生成询问.C 2 运行 VES - Sign 算法可获得任何消息 M 的VES签名 ω ，并返回给A 2 .
③ 仲裁询问.C 2 运行 Adj 算法可获得消息 M 及其VES签名 ω 对应的普通签名 σ ，并返回给A 2 .
3) 伪造阶段.最后，敌手A 2 输出一个消息 M * 及其普通签名 σ * .
敌手A 2 赢得上述游戏当且仅当：
1) σ * 是消息 M * 的一个合法普通签名；
2) ( M * , σ * )不是一个仲裁询问结果.
定义11. 可提取性.若不存在多项式有界的敌手A 3 能以不可忽略的优势赢得以下游戏，则称一个VES方案是可提取的.
1) 系统建立.挑战者C 3 输入安全参数 λ ，运行 Setup 和 Adj - KeyGen 算法生成VES方案的公开参数 PP 和所有仲裁者公私钥对( APK ， ASK )，并将( PP ， APK )发送给敌手A 3 .
2) 询问阶段.A 3 适应性地进行多项式次如下询问.
仲裁询问：C 3 运行 Adj 算法可获得消息 M 及其VES签名 ω 对应的普通签名 σ ，并返回给A 3 .
3) 伪造阶段.最后，敌手A 3 输出一个消息 M * 及其VES签名 ω * ，对应的签名者的公钥为 PK * .
敌手A 3 赢得上述游戏当且仅当：
1) ω * 是消息 M * 的一个合法VES；
2) σ * = Adj ( PP , ASK , APK , PK * , ω * , M * )不是消息 M * 的一个合法普通签名.
3.1 方案构造
1) 系统建立.输入安全参数 n ，具体参数设置见3.2节.选取2个安全的抗碰撞Hash函数 H 1 :{0,1} * → D m × m ， H 2 :{0,1} * × m q → nq ；输出系统公开参数 PP =( n , m , q , s 1 , s 2 , s 3 , α , H 1 , H 2 ).
2) 仲裁者密钥生成.输入公开参数 PP ，运行算法 TrapGen ( q , n )生成随机矩阵 B ∈ n × mq 和格 
的陷门基 T B ∈ m × mq ，且‖ ‖ 
；输出仲裁者公私钥对( APK , ASK )=( B , T B ).
3) 签名者密钥生成.输入公开参数 PP 和仲裁者公钥 APK = B ；运行算法 OrthoSamp ( q , B )生成随机矩阵 A ∈ 
和格 
的陷门基 T A ∈ ，满足 AB T =0 mod q ；输出公私钥对( PK , SK )=( A , T A ).
4) 普通签名.输入公开参数 PP 、私钥 SK = T A 和消息 M ，签名者进行如下操作.
① 随机选取比特串 r ←{0,1} n 和向量 v ∈ mq .
② 运行算法 SampPre ( A , T A , H 2 ( M ‖ r ‖ v ), s 1 )，生成向量 d ∈ m .
③ 输出普通签名 σ =( M , r , v , d ).
5) 普通签名验证.输入签名者公钥 PK = A 和签名 σ =( M , r , v , d )；如果‖ d ‖ 
‖ r ‖ v )，则接受 σ 为签名者对给定消息 M 的一个有效普通签名，否则,拒绝.
6) 可验证加密签名生成.输入公开参数 PP 、私钥 SK = T A 、仲裁者公钥 APK = B ∈ n × mq 和消息 M ，签名者进行如下操作.
① 选取随机比特串 r ←{0,1} n ,误差向量 
和随机向量 s ∈ mq .
② 令 R = H 1 ( M ‖ r )， B ′= BR -1 ∈ n × mq .
③ 计算 v = B ′ T s + x mod q ，并构造对 v 的一个有效非交互零知识证明 π .
④ 运行 SampPre ( A , T A , H 2 ( M ‖ r ‖ v )- AR T x , s 2 )生成向量 e ∈ m .
⑤ 输出可验证加密签名 ω =( M , r , v , π , e ).
7) 可验证加密签名验证.输入签名者公钥 PK = A 、仲裁者公钥 APK = B ∈ n × mq 和签名 ω =( M , r , v , π , e )；首先验证非交互零知识证明 π 的有效性，计算 R = H 1 ( M ‖ r )，如果 π 是有效的， AB T =0 mod q ，‖ e ‖ 
‖ r ‖ v ) mod q ，则接受 ω 为签名者对消息 M 的一个有效的可验证加密签名；否则,拒绝.
8) 仲裁.输入签名者公钥 PK = A ，仲裁者私钥 ASK = T B 和签名 ω =( M , r , v , π , e )，仲裁者进行如下操作.
① 计算 R = H 1 ( M ‖ r ).
② 运行算法 BasisDel ( B , R , T B , s 3 )生成随机矩阵 B ′= BR -1 ∈ n × mq 和 
的陷门基 T B ′ ∈ m × mq .
③ 利用 T B ′ 从 v = B ′ T s + x mod q 中解出( s , x ).
④ 计算 d = e + R T x ∈ mq .
⑤ 输出普通签名 σ =( M , r , v , d ).
3.2 参数设置
为保证仲裁过程中可以从 v 中有效解出( s , x )和系统的安全运行，给定安全参数为 n ，设置其他参数如下：
m = n +8 n 1+ δ ,
(6)
，
(7)
,
(8)
,
(9)
,
(10)
,
(11)
.
(12)
3.3 安全性证明
3.3.1 正确性
令 ω =( M , r , v , π , e )是可验证加密签名生成算法的一个输出，方案的正确性分析如下：
1) 由于签名者选取随机向量 s ，从而签名者可以构造出一个有效的非交互零知识证明 π .
2) 仲裁者计算 
,由于 T B ′ 和 x 的分量元素都比较小，向量 
的每一个分量都远小于 q ,从而 
，容易计算 
.
3) 容易计算 Aσ = A ( e + R T x )= Ae + AR T x = H 2 ( M ‖ r ‖ v ) mod q .
4) 在可验证加密签名验证算法中，我们有：
A ( e + R T v )= Ae + AR T v = Ae + AR T ( B ′ T s + x )=
Ae + A ( B ′ R ) T s + AR T x = Ae + AB T s + AR T x =
A ( e + R T x )= H 2 ( M ‖ r ‖ v ) mod q .
3.3.2 强不可伪造性
定理1. 如果存在敌手A 1 以不可忽略的优势 ε 1 攻破方案的强不可伪造性，则可构造算法B 1 以概率 ε 1 q H 2 求解ISIS问题，其中 q H 2 表示敌手可进行 H 2 询问的最大次数.
证明. 假设B 1 获得了一个ISIS问题实例( A ∈ n × mq , y ∈ nq , n , m , q , s )，要求B 1 通过模拟游戏利用A 1 求解出一个非零向量 e ，使得 Ae = y mod q 且 
.
模拟过程如下：
1) B 1 运行算法 OrthoSamp ( q , A )生成 
的陷门基 T B ∈ m × mq ， BA T =0 mod q ；令仲裁者公私钥对( APK , ASK )=( B , T B )，并将 A , B 和 T B 发送给A 1 ，B 1 随机选取 i * ∈{1,2,…, q H 2 }.B 1 维护2个列表 l 1 和 l 2 分别存储对 H 1 和 H 2 询问的应答.
2) 虽然B 1 没有对应于格 的陷门基，但是B 1 仍可以正确回答A 1 的询问，具体过程如下.
① H 1 ( M ‖ r ‖)询问.B 1 首先检查列表 l 1 中是否存在对该询问的应答，若存在，直接返回；否则，B 1 随机选取矩阵 R ∈ D m × m 并将( M , r , R )存储在列表 l 1 中，然后将 R 返回给A 1 .
② H 2 ( M ‖ r ‖ v )询问.B 1 首先进行 H 1 ( M ‖ r )询问并获得矩阵 R .如果此次询问恰好是第 i * 次询问，B 1 计算 h 2 = AR T v + y mod q ，并将( M , r , v , h 2 ,⊥)存储在列表 l 2 中，然后将 h 2 返回给A 1 ;如果不是第 i * 询问，B 1 计算 h 2 = A ( R T v + e ) mod q ，其中 e ∈ D m , s ，并将( M , r , v , h 2 , e )存储在列表 l 2 中，然后将 h 2 返回给A 1 .
③ 可验证加密签名询问.不失一般性，假设A 1 在进行可验证加密签名询问之前已进行过 H 1 和 H 2 询问.B 1 在列表 l 2 中找到( M , r , v , h 2 , e )，如果 e =⊥，则B 1 直接放弃模拟，否则，返回 e 作为签名应答.
3) 最终，A 1 输出一个伪造的可验证加密签名 ω * =( M * , r * , v * , π * , e * ).不失一般性，假设A 1 在输出伪造的可验证加密签名之前已经进行过 H 1 和 H 2 询问.B 1 在列表 l 2 中找到( M * , r * , v * , h , e )，如果 e ≠⊥，则B 1 直接放弃，否则，B 1 直接返回 e * 作为ISIS实例的应答.
由上可知， A ( R *T v *+ e *) mod q = H 2 ( M * ‖ r *‖ v *)= AR *T v *+ y mod q ，其中 R *= H 1 ( M * ‖ r *).从而可得 Ae *= y mod q ，‖ e *‖ 
.因而只要A 1 成功攻破上述方案的强不可伪造性，算法B 1 就可以以概率1 q H 2 求解ISIS问题，从而我们易知算法B 1 成功求解ISIS问题的概率为 ε 1 q H 2 .
证毕.
3.3.3 强不透明性
定理2. 如果存在敌手A 2 以不可忽略的优势 ε 2 攻破方案的强不透明性，则可构造算法B 2 以概率 ε 2 q H 1 求解LWE问题，其中 q H 1 表示敌手可进行 H 1 询问的最大次数.
证明. 假设B 2 获得了一组LWE问题实例( u i ∈ 
q )， i ∈{1,2,…, m }，要求B 2 通过模拟游戏利用A 2 求解出向量 s * ∈ nq .
模拟过程如下：
1) B 2 首先构造矩阵 B ′∈ n × mq ，其中第 i 列恰好是向量 u i ；构造向量 v ′∈ mq ，其中第 i 个分量元素恰好是 v i ；B 2 选取随机矩阵 R ′∈ D m × m ，然后运行算法 OrthoSamp ( q , B ′ R ′)生成随机矩阵 A ∈ n × mq 和 的陷门基 T A ∈ m × mq ， B ′ R ′ A T =0 mod q ；令仲裁者公钥 APK = B ′ R ′，签名者公私钥对( PK , SK )=( A , T A )，并将 APK ， PK 发送给敌手A 2 ，同时B 2 随机选取 i * ∈{1,2,…, q H 1 }.B维护3个列表 l 1 ， l 2 ， l 3 分别存储对 H 1 询问、 H 2 询问和可验证加密签名询问的应答.
2) 虽然B 2 没有对应于格 
的陷门基，但是B 2 仍可以正确回答敌手A 2 的询问，具体过程如下.
① H 1 ( M ‖ r ‖)询问.如果此次询问恰好是第 i * 次询问，B 2 将( M , r ,⊥, R ′)存储在列表 l 1 中并将 R ′返回给A 2 ；如果此次询问不是第 i * 次询问，B 2 运行算法 SampRwith ( B )生成可逆矩阵 R ∈ m × mq ， BR -1 ∈ n × mq 和 T BR -1 ∈ m × mq ，B 2 将( M , r , T BR -1 , R )存储在列表 l 1 中并将 R 返回给A 2 .
② H 2 ( M ‖ r ‖ v )询问.B 2 首先检查列表 l 2 中是否存在对该询问的应答，若存在，直接返回；否则，B 2 随机选取向量 h 2 ∈ nq 并将( M , r , v , h 2 )存储在列表 l 2 中，然后将 h 2 返回给A 2 .
③ 可验证加密签名询问.不失一般性，假设敌手A 2 在进行可验证加密签名询问之前已经进行过 H 1 和 H 2 询问.B 2 在列表 l 1 中找到( M , r , T BR -1 , R )，如果 T BR -1 ≠⊥，则B 2 按照算法步骤进行可验证加密签名生成，否则，令 v = v ′，B 2 利用陷门基 T A 运行算法 SampPre ( A , T A , H 2 ( M ‖ r ‖ v )- AR ′ T x , s 2 )生成向量 e ,并构造对 v 的一个有效非交互零知识证明 π .B 2 将( M , r , v , π , e )存储在列表 l 3 中，返回 e 作为签名应答.
④ 仲裁询问.不失一般性，假设A 2 在进行仲裁询问之前已经进行过 H 1 询问，当收到A 2 对可验证加密签名 ω =( M , r , v , π , e )的仲裁询问，B 2 在列表 l 1 中找到( M , r , T BR -1 , R )，如果 T BR -1 =⊥，则B 2 直接放弃;否则，B 2 利用 T BR -1 对 v =( BR -1 ) T s + x mod q 进行求解得 x ，并返回普通签名 σ =( M , r , v , d = e + R T x )给A 2 ，其中 R = H 1 ( M ‖ r ‖).
3) 最终，敌手A 2 输出一个有效的普通数字签名 σ * =( M * , r * , v * , d * ).在这里，假设 σ * 是A 2 从可验证加密签名询问结果中提取出来的.不失一般性，假设敌手A 2 在输出伪造的可验证加密签名之前已经进行过 H 1 询问、 H 2 询问和可验证加密签名询问.B 2 首先在列表 l 1 中找到( M * , r * , T BR -1 , R )，在列表 l 3 中找到( M * , r * , v , π , e );如果 T BR -1 ≠⊥，则B 2 直接放弃，否则，我们易知 v = v ′， R = R ′，B 2 利用 R 和 e 可以由向量 d * = e + R ′ T x 求得 x ，从而可以由 v ′= B ′ T s * + x mod q 求解出 s * .
因而只要A 2 成功攻破上述方案的强不透明性，算法B 2 就可以有效求解LWE问题，从而我们易知算法B 2 成功求解LWE问题的概率为 ε 2 q H 1 .
证毕.
3.3.4 可提取性
定理3. 上述可验证加密签名方案满足可提取性.
证明. 对于消息 M 的VES ω =( M , r , v , π , e )，我们证明如果该签名是有效的，那么总可以由 ω 提取出一个普通签名 σ =( M , r , v , d = e + R T x ).非交互零知识证明 π 可以有效确保 v =( BR -1 ) T s + x mod q 中的 x 是一个短向量.由仲裁过程可知，可以以极大概率从 v 中提取出 x ，从而可以构造出短向量 d = e + R T x .
由可验证加密签名验证过程可知，
H 2 ( M ‖ r ‖ v )= A ( e + R T v )=
A [ e + R T ( BR -1 ) T s + R T x ]=
A [ e + B T s + R T x ]= A ( e + R T x ).
因而只要可验证加密签名 ω 是有效的，那么 v 中肯定含有短向量 x ,使得
A ( e + R T x )= H 2 ( M ‖ r ‖ v ).
证毕.
3.4 效率比较
表1给出了该文方案与已有的基于格的可验证加密签名方案的比较结果.文献[13]的方案仅满足存在性不可伪造性，文献[14]的方案虽满足强不可伪造性(strong unfrogeability)，但签名者的公私钥和可验证加密签名尺寸都明显较大.该文方案虽然要求签名者公私钥对需根据仲裁者公钥生成，但是其构造简单，不仅满足强不可伪造性和强不透明性，而且签名者公私钥和可验证加密签名更短，效率更高，实用性更强.
Table 1 Efficiency Comparison of Schemes
表1 方案的效率对比
本文利用Agrawal等人提出的固定维数的格基委派技术，构造出一个新的格上可验证加密签名方案.在随机预言机模型下证明了方案的安全性是基于格上ISIS和LWE问题，保证了其在量子环境下的安全性.与已有的基于格的可验证加密签名方案相比，该方案构造简单，公私钥和签名尺寸更短，效率更高.
参考文献：
[1]Asokan N, Schunter M, Waidner M. Optimistic protocols for fair exchange[C] //Proc of the 4th ACM Conf on Information Security and Privacy. New York: ACM, 1997: 7-17
[2]Boneh D, Gentry C, Lynn B, et al.. Aggregate and verifiably encrypted signatures from bilinear maps[G] //LNCS 2656: Proc of Eurocrypt 2003. Berlin: Springer, 2003: 416-432
[3]Zhou Yousheng, Sun Yanbin, Qing Sihan, et al. An efficient id-based verifiably encrypted signature scheme[J]. Journal of Computer Research and Development, 2011, 48(8): 1350-1356 (in Chinese)(周由胜, 孙艳宾, 卿斯汉, 等. 一种高效的基于身份的可验证加密签名方案[J]. 计算机研究与发展, 2011, 48(8): 1350-1356)
[4]Shen Jian, Wang Jin, Zheng Yuhui, et al. A novel verifiably encrypted signature from weil pairing[C] //Proc of HumanCom and EMC 2013. Berlin: Springer, 2014: 603-607
[5]Calderon T, Meiklejohn S, Shacham H, et al. Rethinking verifiably encrypted signatures: A gap in functionality and potential solutions[G] //LNCS 8366: Proc of CT-RSA 2014. Berlin: Springer, 2014: 349-366
[6]Shim K A. On the security of verifiably encrypted signature schemes in a multi-user setting[J]. Annals of Telecommuni-cations, 2014, 69(11): 585-591
[7]Nishimaki R, Xagawa K. Verifiably encrypted signatures with short keys based on the decisional linear problem and obfuscation for encrypted VES[J]. Designs, Codes and Cryptography, 2015, 77(1): 61-98
[8]Gentry C, Peikert C, Vaikuntanathan V. How to use a short basis: Trapdoors for hard lattice and new cryptographic constructions[C] //Proc of the 40th Annual Symp on Theory of Computing. New York: ACM, 2008: 197-206
[9]Alwen J, Peikert C. Generating shorter bases for hard random lattices[J]. Theory of Computing Systems, 2011, 48(3): 535-553
[10]Gordon S D, Katz J, Vaikuntanathan V. A group signature scheme from lattice assumptions[G] //LNCS 6477: Proc of Asiacrypt 2010, Berlin: Springer, 2010: 395-412
[11]Nguyen P Q, Zhang J, Zhang Z F. Simpler efficient group signatures from lattices[G] //LNCS 9020: Proc of PKC 2015. Berlin: Springer, 2015: 401-426
[12]Rückert M, Schneider M, Schröoder D. Generic constructions for verifiably encrypted signatures without random oracles or NIZKs[G] //LNCS 6123: Proc of ACNS 2010. Berlin: Springer, 2010: 22-25
[13]Wang Fenghe, Hu Yupu, Wang Chunxiao. A verifiably encrypted signature scheme from lattice assumption[J]. Journal of Information and Computational Science, 2011, 8(8): 1431-1438
[14]Kim K S, Jeong I R. Efficient verifiably encrypted signatures from lattices[J]. International Journal of Information Security, 2014, 13(4): 305-314
[15]Agrawal S, Boneh D, Boyen X. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE[G] //LNCS 6223: Proc of Crypto 2010. Berlin: Springer, 2010: 98-115
[16]Regev O. On lattices, learning with errors, random linear codes, and cryptography[C] //Proc of the 37th Annual Symp on Theory of Computing. New York: ACM, 2005: 84-93
[17]Laguillaumie F, Langois A, Libert B, et al. Lattice-based group signature scheme with logarithmic signature size[G] //LNCS 6477: Proc of Asiacrypt 2013. Berlin: Springer, 2013: 41-61
Zhang Yanhua, born in 1989. PhD candidate in Xidian University. His research interests include public key cryptography based on lattice and provable security.
Hu Yupu, born in 1955. Professor and PhD supervisor. His main research interests include multilinear map, public key cryptography based on lattice, witness encryption and fully homomorphic encryption.
Zhang Yanhua and Hu Yupu
( State Key Laboratory of Integrated Service Networks ( Xidian University ), Xi ’ an 710071)
Abstract： Verifiably encrypted signatures (VES) can ensure the fairness of the Internet exchange process effectively. In a VES system, a signer can generate an ordinary signature on a given message using the secret key of the signer and then encrypt it under the public key of the adjudicator. A verifier should be able to verify that this encrypted signature is indeed an encryption of the ordinary signature of the signer, but the verifier cannot be able to extract the ordinary signature. The ordinary signature can only be recovered by the adjudicator from this encrypted signature. Using the technique of basis delegation in fixed dimension suggested by Agrawal et al in CPYPTO 2010, the lattice-based preimage sampling algorithm and a non-interactive zero-knowledge proof for the learning with errors (LWE) problem, this paper constructs a new verifiably encrypted signature scheme from lattices, and based on the hardness of the short integer solution (SIS) problem and the LWE problem, this proposed construction is provably strong unforgeable in the random oracle model. Compared with current verifiably encrypted signature schemes, this scheme needs that the public-private key pair of the signer should be generated according to the public key of the adjudicator, and this scheme can resist quantum attacks and enjoy simpler constructions, shorter public-private keys, smaller signature size and higher efficiency.
Key words： verifiably encrypted signature (VES); fixed dimension; lattice; random oracle model; the learning with errors
收稿日期： 2015-09-30；
修回日期： 2016-05-16
基金项目： 国家自然科学基金项目(61472309) This work was supported by the National Natural Science Foundation of China (61472309).
中图法分类号： TP309