格上基于密文标准语言的可证明安全两轮口令认证密钥交换协议

doi:10.12263/DZXB.20210517

电子学报 ›› 2022, Vol. 50 ›› Issue (5): 1140-1149.DOI: 10.12263/DZXB.20210517

格上基于密文标准语言的可证明安全两轮口令认证密钥交换协议

尹安琪¹, 曲彤洲¹, 郭渊博¹, 汪定², 陈琳¹, 李勇飞¹

^1.信息工程大学电子技术学院, 河南郑州 450001
^2.南开大学网络空间安全学院, 天津 300350

收稿日期:2021-04-21 修回日期:2021-09-26 出版日期:2022-05-25 发布日期:2022-05-16
通讯作者: 郭渊博
作者简介:尹安琪　女，1995年生于山东临沂.现为信息工程大学电子技术学院博士研究生.主要研究方向为格密码理论及格上的口令认证密钥交换协议.
曲彤洲　男，1994年生于辽宁铁岭.现为信息工程大学电子技术学院博士研究生.主要研究方向为粗粒度可重构密码逻辑阵列和密码计算.E-mail: qutongzhou@outlook.com
郭渊博　男，1975年生于陕西周至.现为信息工程大学电子技术学院教授、博士生导师.主要研究方向为网络防御、数据挖掘、机器学习和人工智能安全等.E-mail: guo_yuanbo@126.com
汪定　男，1985年生于湖北十堰.现为南开大学网络空间安全学院教授、博士生导师.主要研究方向为公钥密码学、系统安全、人工智能等.E-mail: wangding@nankai.edu.cn
陈琳　女，1975年生于河南开封.现为信息工程大学电子技术学院副教授.主要研究方向为安全专用芯片设计.E-mail: chenlin916@163.com
李勇飞　男，1998年生于河南郑州，现为信息工程大学电子技术学院硕士研究生，主要研究方向为网络安全知识图谱.E-mail: leekgfly@foxmail.com
基金资助:
国家自然科学基金(61501515);信息保障技术重点实验室开放基金(KJ-15-108)

Provably Secure Two-Round PAKE Based on Ciphertext Standard Language over Lattices

YIN An-qi¹, QU Tong-zhou¹, GUO Yuan-bo¹, WANG Ding², CHEN Lin¹, LI Yong-fei¹

^1.College of Electronic Technology，Information Engineering University，Zhengzhou，Henan 450001，China
^2.College of Cyber Science，Nankai University，Tianjin 300350，China

Received:2021-04-21 Revised:2021-09-26 Online:2022-05-25 Published:2022-05-16
Contact: GUO Yuan-bo

摘要/Abstract

摘要：

降低口令认证密钥交换（Password-based Authenticated Key Exchange，PAKE）协议的通信轮次和安全性假设是格上PAKE协议的重要优化方向.平滑投射哈希函数（Smooth Projective Hash Function，SPHF）是构造PAKE协议的重要数学工具，但现有的基于格的SPHF多不能在超多项式模数下应用.为此，本文提出了两种格上基于密文标准语言的SPHFs，在不增加通信开销和存储开销的前提下解决了上述问题.基于上述SPHFs,本文提出了一种基于格的可证明安全的两轮PAKE协议，该协议可以抵抗量子攻击,在不需要零知识证明和随机预言机的前提下，降低了协议通信轮次和安全性假设；本文还基于更加准确的标准安全模型对所提出的协议进行了严格的安全性证明.实验证明，本文提出的协议具有更优的通信轮次复杂度、计算开销、安全性假设和实际安全性.

关键词: 口令, 密钥交换, 平滑投射哈希函数, 可证明安全, 格, 抗量子

Abstract:

Reducing the communication round complexity and security assumptions are important directions of password-based authenticated key exchange(PAKE) protocol over lattices. Smooth projective Hash function(SPHF) is an important mathematical tool for constructing PAKE. But most of the existing lattice-based SPHFs cannot be applied under hyperpolynomial modulus. This paper proposes two SPHFs based on the standard language of ciphertext over lattices, which solves the above problem without increasing communication and storage overhead. Based on the proposed SPHFs, this paper proposes a provably secure two-round PAKE protocol over lattices, which can resist quantum attacks and reduce the communication round complexity and the security assumptions without random oracle and zero-knowledge proof. And this paper also provides a strict security proof for the proposed protocol based on a more accurate security model. Experiment results show that the protocol proposed has better communication round complexity, computational overhead, security assumptions and actual security.

Key words: password, key exchange, SPHF(Smooth Projective Hash Function), provably secure, lattice, post-quantum

中图分类号:

TN918.1

尹安琪, 曲彤洲, 郭渊博, 汪定, 陈琳, 李勇飞. 格上基于密文标准语言的可证明安全两轮口令认证密钥交换协议[J]. 电子学报, 2022, 50(5): 1140-1149.

YIN An-qi, QU Tong-zhou, GUO Yuan-bo, WANG Ding, CHEN Lin, LI Yong-fei. Provably Secure Two-Round PAKE Based on Ciphertext Standard Language over Lattices[J]. Acta Electronica Sinica, 2022, 50(5): 1140-1149.

图/表 5

表1 符号定义

符号	含义
n	安全参数
［ A \| B ］/［ A \|\| B ］	矩阵 A 和 B 的横/纵向级联
negl（.）	可忽略函数
q	LWE困难问题模数
Ham（.， .）	汉明距离函数
A^T	矩阵 A 的转置矩阵
←/ $← r$	取样/随机取样
\|D\|	集合D的大小
d（.， .）	距离函数（欧式距离）
\|\| x \|\|	向量 x 的欧几里得范数
$⊥$	非法标识
「a⌉/⌊a」	大于/小于a的最小/最大整数
「a」	与a最接近的整数
〈.， .〉	内积运算

表1 符号定义

符号	含义
n	安全参数
［ A \| B ］/［ A \|\| B ］	矩阵 A 和 B 的横/纵向级联
negl（.）	可忽略函数
q	LWE困难问题模数
Ham（.， .）	汉明距离函数
A^T	矩阵 A 的转置矩阵
←/ $← r$	取样/随机取样
\|D\|	集合D的大小
d（.， .）	距离函数（欧式距离）
\|\| x \|\|	向量 x 的欧几里得范数
$⊥$	非法标识
「a⌉/⌊a」	大于/小于a的最小/最大整数
「a」	与a最接近的整数
〈.， .〉	内积运算

图1 舍入函数波形图

表2 密码原语执行时间

操作	执行时间	操作	执行时间
MP.Enc	0.310152048399	MP.SPHF	0.00109302669866
Reg.Enc	0.0433926372716	Reg.SPHF	0.00593389340693
KV.Enc	0.873595026517	KV.SPHF	0.444697060174
SPKE.Enc	13.985888249	SPKE.SPHF	0.00112316393037
GPV.Enc	0.1392346325	GPV.SPHF	0.0097478549383

表3 协议效率对比

协议名称	客户端	服务器端
Z-PAKE^［1］	13.9870245578	13.987024017
B-PAKE^［11］	14.6049738586	14.6049722413
L-PAKE-1^［14］	0.316085944235	0.0444856664001
L-PAKE-2^［10］	0.311245077527	0.311245077527
K-PAKE-1^［9］	1.02864704845	1.02864758728
本文方案	0.299152334473	1.16812224452

表4 通信与存储开销对比

协议名称		Z-PAKE^［1］	B-PAKE^［11］	L-PAKE-1^［14］	L-PAKE-2^［10］	K-PAKE-1^［9］	本文方案
通信复杂度		O（2（4m - 2n₁+ kn₁）logq + k）	O（（8m + 2kn - 4n₁）logq）	O（2（m + kn）logq）	O（2（m + kn）logq）	O（（3mn + 2kn）logq + k）	O（（（mn + 1）+ k（n + 1））logq）
通信开销		1001600	1394688	940032	940032	59769984	20055552
存储复杂度	客户	O（（2mn + k（m + 2n₁） + 8m - 3n₁ + n₂ + 1）logq + 5k）	O（（2mn + k（m + 2n）+ 9m + 3n - 4n₁）logq + k）	O（（mn + k（m + 2n）+ 2m + 3n + 1）logq + 3k）	O（（mn + k（m + 2n）+ 3m + 2n）logq + 3k）	O（（mn（3k + 2n + 6）+ n （2k + 1））logq + 5k）	O（（mn + 2m + 2n + 1 +（m + n + 1）k）logq + 3k）
存储复杂度	服务器	O（（2mn + k（m + 2n₁） + 8m - 3n₁ + n₂ + 1）logq + 5k）	O（（2mn + k（m + 2n）+ 9m + 3n - 4n₁）logq + k）	O（（mn + k（m + 2n）+ 3m + 3n + 1）logq + 3k）	O（（mn + k（m + 2n）+ 3m + 2n）logq + 3k）	O（（mn（3k + 2n + 6）+ n （2k + 1））logq + 5k）	O（（mn（2k+2n+4） + 3n + 1 +（n + 1）k）logq + 3k）
存储开销	客户	50157184	50633088	30440844	30514560	17734832768	30046092
存储开销	服务器	50157184	50633088	30517644	30514560	17734832768	15178541964

参考文献 21

1	ZHANG J, YU Y. Two-round PAKE from approximate SPH and instantiations from lattices[C]//TAKAGI T. Advances in Cryptology-ASIACRYPT 2017. Cham, Germany: Springer, 2017: 37-67.
2	KATZ J, VAIKUNTANATHAN V. Round-optimal password-based authenticated key exchange[C]//ISHAI Y. Theory of Cryptography Conference. Berlin: Springer, 2011: 293-310.
3	KATZ J, OSTROVSKY R, YUNG M. Efficient password-authenticated key exchange using human-memorable passwords[C]//PFITZMANN B. International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer, 2001: 475-494.
4	JIANG S, GONG G. Password based key exchange with mutual authentication[C]//HANDSCHUH H. International Workshop on Selected Areas in Cryptography. Berlin, Germany: Springer, 2004: 267-279.
5	GROCE A, KATZ J. A new framework for efficient password-based authenticated key exchange[C]//AL-SHAER E S. Proceedings of the 17th ACM Conference on Computer and Communications Security. Chicago, USA: ACM, 2010: 516-525.
6	REGEV O. On lattices, learning with errors, random linear codes, and cryptography[J]. Proceedings of the Annual ACM Symposium on Theory of Computing, 2009, 56(6): 84-93.
7	ATENIESE G, FELICI G, MANCINI L V, et al. Hacking smart machines with smarter ones: how to extract meaningful data from machine learning classifiers[J]. International Journal of Security & Networks, 2015, 10(3): 137-150.
8	BALUJA S, FISCHER I. Learning to attack: adversarial transformation networks[C]//MCILRAITH S. Thirty-Second AAAI Conference on Artificial Intelligence. California, USA: AAAI Press, 2018: 2687-2695.
9	KATZ J, VAIKUNTANATHAN V. Smooth projective hashing and password-based authenticated key exchange from lattices[C]//MITSURU M. International Conference on the Theory and Application of Cryptology and Information Security. Berlin, Germany: Springer, 2009: 636-
652
10	LI Z, WANG D. Achieving one-round password-based authenticated key exchange over lattices[J]. IEEE Transactions on Services Computing, 2019, 2019(8): 1-14.
11	BENHAMOUDA F, BLAZY O, LÉO D, et al. Hash proof systems over lattices revisited[C]//ABDALLA M. IACR International Workshop on Public Key Cryptography. Cham, Germany: Springer, 2018: 644-674.
12	GENNARO R, LINDELL Y. A framework for password-based authenticated key exchange[J]. ACM Transactions on Information & System Security, 2006, 9(2): 181-234.
13	YIN A, GUO Y, SONG Y, et al. Two-round password-based authenticated key exchange from lattices[J]. Wireless Communications and Mobile Computing, 2020, 2020(17): 1-13.
14	LI Z, WANG D. Two-round PAKE protocol over lattices without NIZK[C]//GUO F. International Conference on Information Security and Cryptology. Cham, Germany: Springer, 2018: 138-159.
15	ZHANG J, YU Y, FAN S, et al. Improved lattice-based CCA2-secure PKE in the standard model[J]. Science China Information Sciences, 2020, 63(8): 22-28.
16	于金霞, 廉欢欢, 汤永利, 等. 格上基于口令的三方认证密钥交换协议[J]. 通信学报, 2018, 39(11): 91-101.
	YU Jin-xia, LIAN Huan-huan, TANG Yong-li, et al. Password-based three-party authenticated key exchange protocol from lattices[J]. Journal on Communications, 2018, 39(11): 91-101. (in Chinese)
17	GENTRY C, PEIKERT C, VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions[C]//LADNER R. Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. New York, USA: ACM, 2008: 197-206.
18	ALWEN J, PEIKERT C. Generating shorter bases for hard random lattices[J]. Theory of Computing Systems, 2011, 48(3): 535-553.
19	BELLARE M, POINTCHEVAL D, ROGAWAY P. Authenticated key exchange secure against dictionary attacks[C]//PRENEEL B. International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer, 2000: 139-155.
20	WANG D, CHENG H, WANG P, et al. Zipf's law in passwords[J]. IEEE Transactions on Information Forensics and Security, 2017, 12(11): 2776-2791.
21	WANG D, WANG P. On the implications of zipf's law in passwords[C]//ASKOXYLAKIS I. European Symposium on Research in Computer Security. Cham, Germany: Springer, 2016: 111-131.

[1]	吕明久, 马建朝, 韦旭, 陈文峰, 杨军, 马晓岩. 基于矩阵化原子范数的高频雷达距离-多普勒二维估计方法[J]. 电子学报, 2022, 50(5): 1150-1158.
[2]	杨曦, 张鑫, 郭浩远, 王楠楠, 高新波. 基于不变特征的多源遥感图像舰船目标检测算法[J]. 电子学报, 2022, 50(4): 887-899.
[3]	张凌明, 赵悦, 李鹏程, 刘洋, 高陈强. 基于局部注意力机制的三维牙齿模型分割网络[J]. 电子学报, 2022, 50(3): 681-690.
[4]	于建立, 樊亚东, 周蜜, 蔡力. 云—地闪电地面水平电场在不同回击速度和地电参数时的波形特性[J]. 电子学报, 2021, 49(8): 1633-1640.
[5]	刘镇, 吴立强, 韩益亮, 杨晓元, 柳曙光. 一种基于环上LWE的广义签密方案[J]. 电子学报, 2021, 49(7): 1314-1322.
[6]	李子臣, 谢婷, 张卷美. 基于RLWE问题的后量子口令认证密钥交换协议[J]. 电子学报, 2021, 49(2): 260-267.
[7]	周琮伟, 胡斌, 关杰. 一类传递置换群阶的下界估计与实例[J]. 电子学报, 2021, 49(12): 2366-2371.
[8]	史芳静, 樊养余, 王鑫圆, 高永胜. 基于相位调制器的光子射频自干扰消除系统[J]. 电子学报, 2021, 49(10): 1900-1907.
[9]	樊养余, 王武营, 刘曦春. 光载无线通信链路拉格朗日乘子线性度优化[J]. 电子学报, 2021, 49(10): 1927-1933.
[10]	吴立强, 韩益亮, 杨晓元, 张敏情, 杨凯. 基于理想格的鲁棒门限代理重加密方案[J]. 电子学报, 2020, 48(9): 1786-1794.
[11]	郭红伟, 朱策, 刘宇洋. 视频编码率失真优化技术研究综述[J]. 电子学报, 2020, 48(5): 1018-1029.
[12]	王金艳, 胡春, 牛当当, 李先贤. 基于IAPS的扩展规则局部搜索算法[J]. 电子学报, 2020, 48(5): 899-905.
[13]	史聪伟, 赵杰煜, 陈瑜. 利用网格卷积特征的三维形变目标分类[J]. 电子学报, 2020, 48(4): 648-653.
[14]	李大锦, 高文冉, 高俊杰. 基于kuwahara滤波的视频风格化框架[J]. 电子学报, 2020, 48(3): 538-544.
[15]	汪孙律, 杨秋松, 李明树. 一种针对格式文件的符号执行优化方法[J]. 电子学报, 2020, 48(12): 2417-2424.

格上基于密文标准语言的可证明安全两轮口令认证密钥交换协议

Provably Secure Two-Round PAKE Based on Ciphertext Standard Language over Lattices

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 21

相关文章 15

编辑推荐

Metrics