基于矩阵填充问题的五轮零知识身份认证方案

doi:10.11959/j.issn.1000-436x.2021212

通信学报 ›› 2021, Vol. 42 ›› Issue (11): 79-86.doi: 10.11959/j.issn.1000-436x.2021212

基于矩阵填充问题的五轮零知识身份认证方案

王后珍¹^,², 蔡鑫伟¹, 郭岩¹, 张焕国¹

¹ 武汉大学国家网络安全学院，湖北武汉 430072
² 密码科学技术国家重点实验室，北京 100878

修回日期:2021-10-31 出版日期:2021-11-25 发布日期:2021-11-01
作者简介:王后珍（1981− ），男，湖北恩施人，博士，武汉大学讲师，主要研究方向为信息安全、抗量子密码、量子计算等
蔡鑫伟（1998− ），男，湖北武汉人，武汉大学硕士生，主要研究方向为信息安全、应用密码学等
郭岩（1998− ），男，河北邢台人，武汉大学硕士生，主要研究方向为信息安全、应用密码学等
张焕国（1945− ），男，湖北武汉人，博士，武汉大学教授，主要研究方向为信息安全、密码学、可信计算等
基金资助:
“十三五”国家密码发展基金资助项目(MMJJ201701304);国家自然科学基金资助项目(61332019);国家重点研发计划基金资助项目(2018YFC1604000)

5-pass zero-knowledge identity authentication scheme based on matrix completion problem

Houzhen WANG¹^,², Xinwei CAI¹, Yan GUO¹, Huanguo ZHANG¹

¹ School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, China
² State Key Laboratory of Cryptology, Beijing 100878, China

Revised:2021-10-31 Online:2021-11-25 Published:2021-11-01
Supported by:
The National Cryptography Development Fund of China(MMJJ201701304);The National Natural Science Foundation of China(61332019);The National Key Research and Development Program of China(2018YFC1604000)

摘要/Abstract

摘要：

针对现存绝大多数身份认证协议容易遭受量子计算攻击及实现效率低的缺陷，基于矩阵填充（MC）问题构造了一种安全高效的五轮零知识身份认证方案。由于MC问题是NP完全的，所提方案具有很好的抗量子计算攻击潜力。相较于目前已有类似方案，所提方案通过增加单轮交互将欺骗概率由2/3降至1/2，同时兼具容易实现、密钥尺寸小等优点。此外，采用Fiat-Shamir密码转换技术还可将所提五轮零知识认证协议转换为高效的具有抗量子计算攻击潜力的数字签名方案。

关键词: 抗量子计算密码, 身份认证, 零知识证明, 矩阵填充问题

Abstract:

To solve the problem that most identity authentication schemes are vulnerable to quantum-computing attacks and low efficiency, a new 5-pass zero-knowledge identity authentication scheme was designed based on the matrix completion problem (MCP).Since the MCP is NP-complete, the proposed scheme has the potential to avoid quantum-computing attacks.Compared with the existing similar protocols, the proposed scheme reduced the fraud probability from 2/3 to 1/2 by adding a single round of interaction, and had the advantages of easy implementation and small key size.Moreover, based on the proposed zero-knowledge authentication scheme and Fiat-Shamir standard transformation method, a secure and efficient digital signature algorithm against quantum-computing can be obtained.

Key words: post-quantum cryptography, identity authentication, zero-knowledge proof, matrix completion problem

中图分类号:

TP3-0

王后珍, 蔡鑫伟, 郭岩, 张焕国. 基于矩阵填充问题的五轮零知识身份认证方案[J]. 通信学报, 2021, 42(11): 79-86.

Houzhen WANG, Xinwei CAI, Yan GUO, Huanguo ZHANG. 5-pass zero-knowledge identity authentication scheme based on matrix completion problem[J]. Journal on Communications, 2021, 42(11): 79-86.

图/表 3

图1

表1

参数比较"

参数	PKP^[13]	PPP^[16]	SC^[17]	MC(三轮)^[19]	MC(五轮)
矩阵维数	16 × 34	101 × 117	64 × 2 048	11 × 11	11 × 11
有限域	$F_{251}$	$F_{2}$	$F_{257}$	$F_{65521}$	$F_{65521}$
通信次数	5	5	5	3	5
轮次	20	35	20	35	20
欺骗成功概率	$\frac{1}{2}$	$\frac{2}{3}$	$\frac{1}{2}$	$\frac{2}{3}$	$\frac{1}{2}$
系统参数/kbit	4.6	28.5	1 048	0.7	0.7
公钥尺寸/bit	272	11 918	512	432	432
私钥尺寸/bit	128	117	2 048	144	144
通信开销/bit	665	1 040	33 216	4 449	7 257
时间复杂度	2 ⁶⁰	2 ⁷⁴	2 ¹⁰⁰	2 ⁸⁸	2 ⁸⁸

表1

表2

参考文献 32

[1]	GOLDWASSER S , MICALI S , RACKOFF C . The knowledge complexity of interactive proof systems[J]. SIAM Journal on Computing, 1989,18(1): 186-208.
[2]	FEIGE U , FIAT A , SHAMIR A . Zero-knowledge proofs of identity[J]. Journal of Cryptology, 1988,1(2): 77-94.
[3]	GUILLOU L C , QUISQUATER J J . A “paradoxical” indentity-based signature scheme resulting from zero-knowledge[C]// Advances in Cryptology — CRYPTO’ 88. Berlin:Springer, 1990: 216-231.
[4]	SCHNORR C P . Efficient signature generation by smart cards[J]. Journal of Cryptology, 1991,4(3): 161-174.
[5]	SHOR P W , . Algorithms for quantum computation:discrete logarithms and factoring[C]// Proceedings of the 35th Annual Symposium on Foundations of Computer Science. Piscataway:IEEE Press, 1994: 124-134.
[6]	ALAGIC G , ALPERIN-SHERIFF J , APON D ,et al. Status report on the first round of the nist post-quantum cryptography standardization process[R]. 2019.
[7]	STERN J , . A new identification scheme based on syndrome decoding[C]// Advances in Cryptology — CRYPTO’ 93. Berlin:Springer, 1994: 13-21.
[8]	GABORIT P , GIRAULT M . Lightweight code-based identification and signature[C]// Proceedings of 2007 IEEE International Symposium on Information Theory. Piscataway:IEEE Press, 2007: 191-195.
[9]	AGUILAR C , GABORIT P , SCHREK J . A new zero-knowledge code based identification scheme with reduced communication[C]// Proceedings of 2011 IEEE Information Theory Workshop. Piscataway:IEEE Press, 2011: 648-652.
[10]	CAYREL P L , EL Y A S M , HOFFMANN G ,et al. An improved threshold ring signature scheme based on error correcting codes[C]// Arithmetic of Finite Fields. Berlin:Springer, 2012: 45-63.
[11]	COURTOIS N T , . Efficient zero-knowledge authentication based on a linear algebra problem MinRank[C]// Advances in Cryptology —ASIACRYPT 2001. Berlin:Springer, 2001: 402-421.
[12]	SAKUMOTO K , SHIRAI T , HIWATARI H . Public-key identification schemes based on multivariate quadratic polynomials[C]// Advances in Cryptology – CRYPTO 2011. Berlin:Springer, 2011: 706-723.
[13]	SHAMIR A , . An efficient identification scheme based on permuted kernels (extended abstract)[C]// Advances in Cryptology — CRYPTO’ 89 Proceedings. Berlin:Springer, 1989: 606-609.
[14]	CHEN K F , . A new identification algorithm[C]// Cryptography:Policy and Algorithms. Berlin:Springer, 1996: 244-249.
[15]	STERN J , . Designing identification schemes with keys of short size[C]// Advances in Cryptology — CRYPTO ’94. Berlin:Springer, 1994: 164-173.
[16]	POINTCHEVAL D , . A new identification scheme based on the perceptrons problem[C]// Advances in Cryptology — EUROCRYPT ’95. Berlin:Springer, 1995: 319-328.
[17]	CAYREL P L , LINDNER R , RüCKERT M ,et al. Improved zero-knowledge identification with lattices[C]// Provable Security. Berlin:Springer, 2010: 1-17.
[18]	YANG R P , AU M H , ZHANG Z F ,et al. Efficient lattice-based zero-knowledge arguments with standard soundness:construction and applications[C]// Advances in Cryptology – CRYPTO 2019. Cham:Springer International Publishing, 2019: 147-175.
[19]	王后珍, 郭岩, 张焕国 . 基于矩阵填充问题的高效零知识身份认证方案[J]. 武汉大学学报(理学版), 2021,67(2): 111-117.
	WANG H Z , GUO Y , ZHANG H G . Efficient zero-knowledge identification based on matrix completion problem[J]. Journal of Wuhan University (Natural Science Edition), 2021,67(2): 111-117.
[20]	BUSS J F , FRANDSEN G S , SHALLIT J O . The computational complexity of some problems of linear algebra[J]. Journal of Computer and System Sciences, 1999,58(3): 572-596.
[21]	GABIDULIN E M . Theory of codes with maximum rank distance(translation)[J]. Problems of Information Transmission, 1985,21(1): 1-12.
[22]	HARM D . On the equivalence between low-rank matrix completion and tensor rank[J]. Linear and Multilinear Algebra, 2018,66(4): 645-667.
[23]	PEETERS R . Orthogonal representations over finite fields and the chromatic number of graphs[J]. Combinatorica, 1996,16(3): 417-431.
[24]	CRAVO G . Matrix completion problems[J]. Linear Algebra and Its Applications, 2009,430(8/9): 2511-2540.
[25]	COPPERSMITH D , STERN J , VAUDENAY S . Attacks on the birational permutation signature schemes[C]// Advances in Cryptology —CRYPTO’ 93. Berlin:Springer, 1993: 435-443.
[26]	COURTOIS N T , . The security of hidden field equations (HFE)[C]// Topics in Cryptology — CT-RSA 2001. Berlin:Springer, 2001: 266-281.
[27]	KIPNIS A , SHAMIR A . Cryptanalysis of the HFE public key cryptosystem by relinearization[C]// Advances in Cryptology — CRYPTO’ 99. Berlin:Springer, 1999: 19-30.
[28]	GOUBIN L , COURTOIS N T . Cryptanalysis of the TTM cryptosystem[C]// Advances in Cryptology — ASIACRYPT 2000. Berlin:Springer, 2000: 44-57.
[29]	COURTOIS N T . The security of cryptographic primitives based on multivariate algebraic problems:MQ,MinRank,IP,HFE[D]. Paris:Paris 6 University. 2001.
[30]	FAUGERE J C,LEVY-DIT-VEHELF,PERRETL , . Cryptanalysis of minrank[C]// Advances in Cryptology-CRYPTO’08. Berlin:Springer, 2008: 280-296.
[31]	张海波, 黄宏武, 刘开健 ,等. 车联网中可证安全的匿名可追溯快速组认证协议[J]. 通信学报, 2021,42(6): 213-225.
	ZHANG H B , HUANG H W , LIU K J ,et al. Verifiably secure fast group authentication protocol with anonymous traceability for Internet of vehicles[J]. Journal on Communications, 2021,42(6): 213-225.
[32]	田苗苗, 陈静, 仲红 . 格上基于身份的增量签名方案[J]. 通信学报, 2021,42(1): 108-117.
	TIAN M M , CHEN J , ZHONG H . Identity-based incremental signature scheme from lattices[J]. Journal on Communications, 2021,42(1): 108-117.

方案	问题	时间/ms
GQ方案^[3]	IFP	2
Schnorr方案^[4]	DLP	3.1
Stern方案^[7]	SDP	29.3
文献[19]方案	MCP	5.8
本文方案	MCP	4.6
注：实验环境为Intel i5-5200U 2.2 GHZ/4 GB。

基于矩阵填充问题的五轮零知识身份认证方案

5-pass zero-knowledge identity authentication scheme based on matrix completion problem

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 32

相关文章 15

Metrics

推荐阅读 0

[1]	冯霞, 崔凯平, 谢晴晴, 王良民. VANET中基于区块链的分布式匿名认证方案[J]. 通信学报, 2022, 43(9): 134-147.
[2]	张学旺, 黎志鸿, 林金朝. 基于公平盲签名和分级加密的联盟链隐私保护方案[J]. 通信学报, 2022, 43(8): 131-141.
[3]	唐飞, 包佳立, 黄永洪, 黄东, 王惠莅. 基于属性的多授权中心身份认证方案[J]. 通信学报, 2021, 42(3): 220-228.
[4]	朱智强,林韧昊,胡翠云. 基于数字证书的openstack身份认证协议[J]. 通信学报, 2019, 40(2): 188-196.
[5]	祝烈煌,王龙,李嘉盛,张川,原卫华. 卫星通信网中一种新的实体认证与访问控制方案[J]. 通信学报, 2018, 39(6): 73-80.
[6]	赵森,甘庆晴,王晓明,余芳. 多云环境下基于智能卡的认证方案[J]. 通信学报, 2018, 39(4): 131-138.
[7]	张佳乐,赵彦超,陈兵,胡峰,朱琨. 边缘计算数据安全与隐私保护研究综述[J]. 通信学报, 2018, 39(3): 1-21.
[8]	沈伟国,王巍. 基于顽健线性判别分析的击键特征识别方法[J]. 通信学报, 2017, 38(Z2): 26-29.
[9]	董颖娣,彭进业,张晓博,张振龙. 基于测量设备无关协议的量子身份认证方案[J]. 通信学报, 2016, 37(2): 152-157.
[10]	吴志军,赵婷,雷缙. 基于改进的Diameter/EAP-MD5的SWIM认证方法[J]. 通信学报, 2014, 35(8): 1-7.
[11]	吴志军，赵婷，雷缙. 基于改进的diameter/EAP-MD5的SWIM认证方法[J]. 通信学报, 2014, 35(8): 1-7.
[12]	吕洁1, 2，陈萍1, 2，王文清3，张扬1, 2，张蓓1, 2. 基于联盟身份认证和CALIS联合认证的图书馆资源访问方案[J]. 通信学报, 2013, 34(Z2): 14-73.
[13]	吕洁,陈萍,王文清,张扬,张蓓. 基于联盟身份认证和CALIS联合认证的图书馆资源访问方案[J]. 通信学报, 2013, 34(Z2): 69-73.
[14]	何文才,杜敏,陈志伟,刘培鹤,韩妍妍. 分布式文件交互系统节点身份认证方案[J]. 通信学报, 2013, 34(Z1): 14-20.
[15]	何文才1,2，杜敏1,2，陈志伟1,2，刘培鹤1，韩妍妍1. 分布式文件交互系统节点身份认证方案[J]. 通信学报, 2013, 34(Z1): 3-20.