Microsoft Word doc

Size: px

Start display at page:

Download "Microsoft Word - 141506.doc"

硕禹跃冯
9 years ago
Views:

1 第 37 卷第 8 期电子与信息学报 Vol.37 No 年 8 月 Journal of Electronics & Information Technology ug. 015 一种新型基于环上带误差学习问题的认证密钥交换方案杨孝鹏马文平张成丽 ( 西安电子科技大学综合业务网及关键技术国家重点实验室西安 ) 摘要 : 利用格上判定带误差学习问题 (Ring-DLWE) 困难假设该文基于 Peikert 的调和技术构造认证密钥交换方案在标准模型下该方案是 CK 模型中可证明安全的并达到弱前向安全性 (wpfs) 与现有的基于 LWE 的密钥交换方案相比该方案使用平衡的密钥提取函数因而保护共享会话密钥同时因其基于格中困难问题所以能抵抗量子攻击关键词 : 密码学 ; 格 ; 认证密钥交换 ;CK 模型 ; 环上判定带误差学习问题 (Ring-DLWE) 中图分类号 :TP309 文献标识码 : 文章编号 : (015) DOI: /JEIT New uthenticated Key Exchange Scheme ased on Ring Learning with Errors Problem Yang Xiao-peng Ma Wen-ping Zhang Cheng-li (State Key Laboratory of Integrated Service Networks Xidian University Xi an China) bstract: Using the hard assumption of Ring-Decision Learning With Errors (Ring-DLWE) in the lattice a new uthenticated Key Exchange (KE) scheme is proposed which is based on the Peikert s reconciliation technique. Under the standard model the proposed scheme is provably secure in the CK model which is additionally achieves weak Perfect Forward Secrecy (wpfs). Compared with the current Key Exchange (KE) schemes based on the LWE the proposed scheme not only protects the shared session key with balanced key derivation function but also resists quantum attacks because of the hard assumption on lattice problem. Key words: Cryptography; Lattice; uthenticated Key Exchange (KE); CK model; Ring-Decision Learning With Errors (Ring-DLWE) 1 引言认证密钥交换是密码学中的基本原型它不仅允许通信双方协商出共享密钥而且为双方提供认证每个通信方拥有一对静态公私钥其中静态公钥由可信第三方颁发在协议执行过程中每个通信方首先生成自己的短暂公私钥再计算会话状态最后利用密钥提取函数计算共享密钥近年来基于格的密码体制因其具有较高的渐进效率可并行计算抗量子攻击等优点迅速成 [1 1] 为密码学研究新热点并取得了一系列成果其中基于带误差学习 (Learning With Errors LWE) 问题的困难性在建立秘密共享方案方面应用广 [6 1] 泛文献 [6] 基于 LWE 提出了认证密钥交换协收到改回网络优先出版国家自然科学基金 ( ) 高等学校博士学科点专项科研基金 ( ) 高等学校创新引智计划项目 (08038) 十二五国家密码发展基金 (MMJJ ) 和华为技术有限公司合作项目 (Y ) 资助课题通信作者 : 杨孝鹏 [email protected] 议并证明协议是强安全的文献 [7] 指出文献 [6] 的协议难以抵抗不知道任何秘密信息的外部攻击者实施的假冒攻击文献 [8] 提出基于 LWE 的秘密共享方案该方案借助符号函数来降噪但符号函数泄露了密钥的一些信息文献 [9] 提出基于 LWE 的认证密钥交换方案并构造了特征函数和符号函数为了使符号函数输出分布与均匀分布不可区分要求模数很大针对现有文献的不足该文基于环上带误差学习问题 (RLWE) 问题 [10] 提出新的认证密钥交换方案使用较小的模数并利用平衡密钥提取器所以不会泄露共享密钥的信息而且所有计算可以采用分圆域上快速傅里叶变换 (FFT) [10] 加速预备知识.1 符号说明用和分别表示复数集实数集整数集和有理数集对于 x 定义 [ x ] = x + 1/ 对于 q 1 定义 q = / q 一个 k n k n 维格表示为 Λ = L( ) = { c : c }

Peikert 的调和技术构造认证密钥交换方案在标准模型下该方案是 CK 模型中可证明安全的并达到弱前向安全性 (wpfs) 与现有的基于 LWE 的密钥交换方案相比该方案使用平衡的密钥提取函数因而保护共享会话密钥同时因其基于格

2 第 8 期杨孝鹏等 : 一种新型基于环上带误差学习问题的认证密钥交换方案 1985 π 是格的基高斯函数为 ρr ( ) exp x x = r 其中 x H={ x: xi= xm i i m} 格的陪集 Λ+ c 上 ρr ( x) 的离散高斯概率分布为 D Λ + c r ( x) = ρ ( Λ+ c ) x Λ + c 对于正整数 m ζ m 是本原 m 阶单位根 K = ( ζ m ) 表示 m 次分圆域 R = [ ζ m ] 表示 m j m 1 次分圆环 { ζ : gcd( jm ) = 1} 是 R 的幂基 P 设 m j= 0 τ 是 K 的自同构 R 的解码基为 d = τ( P ) 设 p 为奇素数记 g = (1 ζ ) 设 R 为可换环 R 上 pm ij 离散傅里叶变换 DFT m 为矩阵 ( ω m) ( i j) ( m m) 中国剩余变换 CRT m 为 DFT m 的亚矩阵阶为 m [ ϕ( m)]. 格上亚高斯变量 p 定义 1 [10] 对于 δ > 0 t 若满足 πtx δ +π r t 则称上随机变量 E[exp( )] exp( ) X 是标准偏差为 r 的 δ - 亚高斯变量由马尔科夫不等式得 : t 0 有 Pr X t exp δ π t / r (1) [ ] ( ) 事实 1 [10] 若 X 1 是 δ1 - 亚高斯变量标准偏差为 r 1 X 是 δ - 亚高斯变量标准偏差为 r X 1 与 X 相互独立则 X1 + X是 ( δ1 + δ) - 亚高斯变量标准偏差为 r + r 1 引理 1 [10] 设 g e是 δ - 亚高斯变量标准偏差为 m r e Q( ζ m ) 则对于 e e ( ζ m ) 用 R 的每个解码基表示时系数均是 δ - 亚高斯变量标准偏差为 r e 引理 [10] 设 e χ 其中 χ = [ ϕ r ] ϕ r = ( m / g) D r 则 g e 是 δ - 亚高斯变量标准偏差为 m r + π rad( m)/ m 且 g e m r + r ( rad( m)/ m) n 以至少 1 n 的概率成立.3 代数整数环上格的抽样设 a K 用 R 的解码基表示为 a = ( m / g) da 代数整数环上格的高斯抽样简述如下 :(1) t ϕ( m) σ ζ = CRT ; () 从空间 ( 0 ) m t= 利用典范嵌入计算 { } H 上的连续高斯分布中抽样 σ () a 左乘 CRT m 计算 a = CRT m σ( a) ; (3) 计算 a = ( m / g) da ; (4) 对 a 的解码基的每个系数凑整为最近整数输出 [ a ].4 困难问题定义 [410] 对于 s R q K 上的分布 χ 随机均匀选取 a e 是服从 χ 的噪声计算 b = R q a s + e modqr 记 ( ab= a s+ e modr) q 的分布为 s χ 以不可忽略的概率区分 s χ 与 R q (K m / qr ) 上的均匀分布问题就是判定 Ring-LWE 问题记作 RDLWE q χ 引理 3 [4] n 设 α = ω( log n) 向量 x 分布 χ α 与分布 χ α + x 统计距离至多为 x / α.5 安全模型安全模型定义请参见文献 [13].6 调和技术调和函数定义请参见文献 [11] 引理 4 [11] 对于偶数模 q 若 x q 是随机均匀的则 [ x ] 是随机均匀的引理 5 [11] 对于偶数模 q 若 w = x + emodq v q e E 则 rec( w x ) = [ x] = rec( x x ) 引理 6 [11] 对于奇数模 q 若 x q 是随机均匀的 x dbl( x) q 给定 x 条件下 [ x ] 的分布是一致分布 3 方案 3.1 方案描述设 R q = q[ X]/( Φm( X)) q 为奇素数且满足 q 1modm αq ω( log n) 抽样 s e χ 将 s 作为静态私钥计算静态公钥 P = a s + e R q 抽样 s e χ 将 s 作为静态私钥计算静态公钥 P = a s + e R q 方案如图 1 所示 r f χ r f χ x = a r + f x y = a r + f e χ d = g P s + e d = dbl( d) k = [ d] v = d f χ y v v w = g s P y = y + a k 1 rec( w v ) = k SK = [] c 1 w = g ( y a k) r rec( w v )=SK c = g x r + f c = dbl( c) 擦掉除 (SK w ) 外的擦掉除 (SK c) 外的所有状态信息 v = c 所有状态信息图 1 基于 Ring-LWE 的认证密钥交换方案

= (1 ζ ) 设 R 为可换环 R 上 pm ij 离散傅里叶变换 DFT m 为矩阵 ( ω m) ( i j) ( m m) 中国剩余变换 CRT m 为 DFT m 的亚矩阵阶为 m [ ϕ( m)].

3 1986 电子与信息学报第 37 卷 3. 正确性引理 7 假设 g si g r i 令 e 1 = g ( s e s e) e R e 1 R 为在 d dbl( d) 中选取的随机元对于 μ > 0 若能恢复 k 的真实值则要求 q π r ( + n) + μ 8 () 进一步在恢复 k 的真实值条件下 SK = SK 以至少 n(1 exp(3 δ π μ )) 的概率成立证明因为 w1 = d + g ( s e + s e) e R q 由引理可知 g e 和 g e 都是 δ - 亚高斯变量标准偏差为 m r 其中 r = ( r + π 1/ rad( m)/ m) 因为 g si g r i 由引理 1 可知 g e s 和 g e s 的解码基的每个系数都是 δ - 亚高斯变量标准偏差为 r 由引理 1 可知 e 的解码基的每个系数都是 δ - 亚高斯变量标准偏差为 r n 另外 e 1 的解码基的每个系数都是 0 - 亚高斯变量标准偏差为 π 由事实 1 可知 e1 + e 1 的解码基的每个系数都是 3δ - 亚高斯变量标准偏差为 [ r ( λ + n) +π 1/ /] 此时 e1 + e 1 的解码基的每个系数落在区间 [ q/4 q/4) 上由引理 5 可知能恢复 k 的真实值由式 (1) 得出式 () e1 + e 1 的解码基的每个系数以至少 1 exp(3 δ π μ ) 的概率落在区间 [ q/4 q/4) 上由引理 5 得以至少 n(1 exp(3 δ π μ )) 的概率恢复出 k 的真实值同理可证在恢复 k 的真实值条件下 SK = SK 以至少 n(1 exp(3δ π μ )) 的概率成立证毕 3.3 参数选取由引理 7 可知只需取 q = O ( n ) 为保证 α q 1/4 ω( log n) 设 r = ( n/ log ( n)) ω( log n) 3.4 效率比较方案效率由计算复杂度和通信复杂度组成计算复杂度主要考虑向量乘法和抽样通信复杂度考虑发送比特总数表 1 对现有的基于 Ring-LWE 的密钥交换方案做比较 ( 密钥为 n bit) 4 安全分析 1/ 定理 1 设 n 是安全参数 α < (log n/ n) q = 1modm 是一个多项式有界的素数且 αq ω( log n) 若 RDLWE q χ 是困难问题则上述方案在标准模型下是带 wfs 的 SK 安全的证明在下述证明中设 sid 表示测试会话标示符表示敌手 Suc 表示敌手赢得游戏根据测试会话是否有匹配会话分为以下两种情形进行分析 : 情形 1 sid 有匹配会话并且可以得到 sid 的静态私钥这部分证明要利用混合游戏 G 1x 记 dv( G1 x ) 表示赢得游戏 G 1x 的优势其中 x = G 10 这个游戏是敌手和协议之间的真实交互按照模型规定的能力向模拟器 S 发出询问并得到相应的回答特别地当向一个未完成的会话发出 Test 询问时 S 选取 b R {01} 若 b = 0 则 S 返回一个随机密钥给否则 S 返回 sid 的真实密钥给 G 11 这个游戏和 G 10 基本相同下述情况除外 : S 抽取 r f χ 计算 y = a r + f 选取 k {01} n R 计算 y = y + a k 选取 r R Rq 计算 v = dbl( r) c = g x r + f 依据协议规范地计算 cv SK 并发送 ( y v v ) 给因为 y 的分布与一致分布计算不可区分所以猜测出 y = y + a k 的概率可忽略因为 y = a ( r + k) + f 由引理 3 可知 r + k 的分布统计接近 χ 则 G 11 中的 y 的分布统计接近 G 10 中的 y 的分布构造一个规约 R 1 它的两对输入为 ( ay ) 和 ( b r ) R Rq Rq 设 v = dbl( c ) 输出 1 ( ap = s b y v k ) 若 R 1 的输入取自 e 0 χ 则 R 1 的输出和 G 10 的输出相同否则 R 1 的输出和 G 11 输出相同由引理 6 可知这两对输入计算不可区分若 RDLWE q χ 是困难问题则 dv G dv G negl( n) (3) ( 11 ) ( 10 ) 表 1 基于 Ring-LWE 的密钥交换方案的性能比较 ( 密钥为 n bit) 方案认证 q 的尺寸困难假设安全模型计算复杂度 ROM 发送比特总数文献 [8] n 4 Ideal-SIVP 9 On ( ) n O( ) n + n log q 文献 [9] Ideal-SIVP ω(log n) 9 On ( ) R n O( ) n + n log q 本文 On ( ) Ideal-SIVP 5 On ( ) CK n 1 O ( + ) n + n log q

)) 的概率成立证明因为 w1 = d + g ( s e + s e) e R q 由引理可知 g e 和 g e 都是 δ - 亚高斯变量标准偏差为 m r 其中 r = ( r + π 1/ rad( m)/ m) 因为 g si g r i 由引理 1 可知 g e s 和 g e s 的解码基的每个系数都是 δ

4 第 8 期杨孝鹏等 : 一种新型基于环上带误差学习问题的认证密钥交换方案 1987 G 1 这个游戏和 G 11 基本相同下述情况除外 : S 选取 P R Rq 计算 w1 = g s P 选取 k R R q 设置 rec( w1 v) = k 依据协议规范地计算 w 和 SK 因为 P 的分布与一致分布计算不可区分则由引理 6 可知给定 v 条件下 k 是一致分布的且 dv G dv G negl( n) (4) ( 1 ) ( 11 ) G 13 这个游戏和 G 1 基本相同下述情况除外 : S 选取 y R Rq k {01} n R 计算 y = y + a k 选取 c R R q 计算 cv v 选取 SK {01} n R 并设置 [ c ] = SK 发送 ( y v v) 给 G 1 中 SK 替换为 G 13 中的随机值设 ( u1 v 1) 和 ( u v ) 是两个 Ring-LWE 挑战组构造求解 Ring-LWE 问题的区分器 D D 设置 s = u 1 x = u y = v 1 选取 k {01} n R 计算 y = y + a k 设置 c = v 依据协议规范计算 csk v 另外 D 选取 SK {01} n R 设置 [ c ] = SK 发送 ( y v v ) 给若 RDLWE q χ 是困难问题则 ( 13 ) ( 1 ) dv G dv G negl( n) (5) G 14 这个游戏和 G 13 基本相同下述情况除外 : S 选取 x R Rq 设置 SK {01} n R 作为共享密钥在 G 14 中 SK 是均匀随机的给定 w 条件下 rec( w v ) 的输出分布统计接近均匀分布 G 13 与 G 14 计算不可区分且有 ( 14 ) ( 13 ) dv G dv G negl( n) (6) 在 G 14 中会话状态完全随机化则敌手不能通过 Test 问询获得任何优势结合式 (3) 式 (6) 可知的优势是可忽略的量情形 sid 没有匹配会话且可以得到 sid 的静态私钥这部分证明要利用混合游戏 G x G 0 这个游戏与情形 1 中游戏 G 10 相同 G 1 这个游戏和 G 0 基本相同下述情况除外 : S 抽取 r f χ 计算 x = a r + f 抽取 r f χ 计算 y = a r + f 选取 k {01} n R 计算 y = y + a k 选取 r R Rq 计算 v = dbl( r ) 并发送 ( y v v ) 给类似分析 G 11 与 G 10 的不可区分性可以得到 dv G dv G negl( n) (7) ( 1 ) ( 0 ) G 这个游戏和 G 1 基本相同下述情况除外 : S 用 P R R q 替换 G 1 中的 P 类似分析 G 1 与的不可区分性可以得到 G 11 ( ) ( 1) dv G dv G negl( n) (8) G 3 这个游戏和 G 基本相同下述情况除外 : S 抽取 r f χ 计算 x = a r + f 选取 P R Rq 计算 w1 = g s P 依据协议规范地计算 SK 类似分析 G 13 与 G 1 的不可区分性可以得到 ( 3 ) ( ) dv G dv G negl( n) (9) G 4 这个游戏和 G 3 基本相同下述情况除外 : S 抽取 r f χ 计算 z 1 = a r + f 计算 x= z1 + f= a r + ( f + f ) 计算 c = g x r +f 依据协议规范地计算 csk v y 由引理 3 可知不能区分 G 4 与 G 3 则有 ( 4 ) ( 3 ) dv G dv G negl( n) (10) G 5 这个游戏和 G 4 基本相同下述情况除外 : n S 选取 v R {01} 依据协议规范地计算 SK 因为在 v 随机均匀条件下 SK 的分布是一致分布由引理 5 可知猜测成功的优势可忽略则有 ( 5 ) ( 4 ) dv G dv G negl( n) (11) G 6 这个游戏和 G 5 基本相同下述情况除外 : S 选取 z1 R R q 在 G 6 中会话密钥完全随机化则敌手不能通过 Test 问询获得任何优势结合式 (7) 式 (11) 可知的优势是可忽略的量证毕 5 结束语本文利用 Ring-DLWE 困难假设基于调和技术构造出一种新型认证密钥交换方案相对于现有的基于 LWE 的认证密钥交换方案来说本文使用较小的模数并利用平衡函数提取共享密钥下一步工作可以考虑基于 LWE 构造强安全的认证密钥交换方案参考文献 [1] Gentry C Peikert C and Vaikuntanathan V. Trapdoor for hard lattices and new cryptographic constructions[c]. Proceedings of the 40th nnual CM Symposium on Theory of Computing Victoria C Canada 008: [] Regev O. On lattices learning with errors random linear codes and cryptography[j]. Journal of the CM 009 DOI: / [3] Peikert C. Public-key cryptosystems for the worst-case shortest vector problem[c]. Proceedings of the 41th nnual CM Symposium on Theory of Computing ethesda MD US 009: [4] Lyubashevsky V Peikert C and Regev O. On ideal lattices and learning with errors over rings[c]. Proceedings of the 9th nnual International Conference on the Theory and pplications of Cryptographic Techniques Riviera France 010: 1-3.

计算 cv v 选取 SK {01} n R 并设置 [ c ] = SK 发送 ( y v v) 给 G 1 中 SK 替换为 G 13 中的随机值设 ( u1 v 1) 和 ( u v ) 是两个 Ring-LWE 挑战组构造求解 Ring-LWE 问题的区分器 D D 设置 s = u 1 x = u y = v 1 选取 k {01}

5 1988 电子与信息学报第 37 卷 [5] enny David C and Peikert C. Fast cryptographic primitives and circular-secure encryption based on hard learning problems[c]. Proceedings of the 9th nnual International Cryptology Conference Santa arbara C US 009: [6] Fujioka Suzuki K Xagawa K et al.. Practical and post-quantum authenticated key exchange from one-way secure key encapsulation mechanism[c]. Proceedings of the 8th CM Symposium on Information Computer and Communication Security Hangzhou China 013: [7] 胡学先魏江宏叶茂等. 对一个强安全的认证密钥交换协议的分析 [J]. 电子与信息学报 (9): Hu Xue-xian Wei Jiang-hong Ye Mao et al.. Cryptanalysis of a strongly secure authenticated key exchange protocol[j]. Journal of Electronics & Information Technology (9): [8] Ding Jin-tai. simple provably secure key exchange scheme based on the learning with errors problems[ol] [9] Zhang Jiang Zhang Zhen-feng Ding Jin-tai et al.. uthenticated key exchange from ideal lattices[ol] [10] Lyubashevsky V Peikert C and Regev O. toolkit for ring-lwe cryptography[c]. Proceedings of the 3nd nnual International Conference on the Theory and pplications of Cryptographic Techniques thens Greece 013: [11] Peikert C. Lattice cryptography for the Internet[C]. Proceedings of the 6th International Workshop Post-Quantum Cryptography Waterloo Canada 014: [1] Peikert C. n efficient and parallel gaussian sampler for lattices[c]. Proceedings of the 30th nnual International Cryptology Conference Santa arbara C US 010: [13] Canetti R and Krawczyk H. nalysis of key-exchange protocols and their use for building secure channels[c]. Proceedings of the 0th nnual International Conference on the Theory and pplications of Cryptographic Techniques Innsbruck ustria 001: 杨孝鹏 : 男 1986 年生博士生研究方向为格密码. 马文平 : 男 1965 年生博士教授博士生导师研究方向为通信理论纠错码和信息安全等. 张成丽 : 女 1985 年生博士生研究方向为格密码.

. Practical and post-quantum authenticated key exchange from one-way secure key encapsulation mechanism[c].

说明为了反映教运行的基本状态, 为校和院制定相关政策和进行教建设与改革提供据依据, 校从程资源 ( 开类别开量规模 ) 教师结构程考核等维度, 对 2015 年春季期教运行基

说明为了反映教运行的基本状态, 为校和院制定相关政策和进行教建设与改革提供据依据, 校从程资源 ( 开类别开量规模 ) 教师结构程考核等维度, 对 2015 年春季期教运行基内部资料东北师范大教运行基本状态据报告 2015 年春季期教务处 2015 年 10 月 27 日说明为了反映教运行的基本状态, 为校和院制定相关政策和进行教建设与改革提供据依据, 校从程资源 ( 开类别开量规模 ) 教师结构程考核等维度,