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

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

Abstract

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

CLC Number:

TP3-0

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.

Figures/Tables 3

参数	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 ⁸⁸

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

方案	问题	时间/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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 32

Related Articles 15

Metrics

Recommended 0

[1]	Xia FENG, Kaiping CUI, Qingqing XIE, Liangmin WANG. Distributed anonymous authentication scheme based on the blockchain in VANET [J]. Journal on Communications, 2022, 43(9): 134-147.
[2]	Xuewang ZHANG, Zhihong LI, Jinzhao LIN. Privacy protection scheme based on fair blind signature and hierarchical encryption for consortium blockchain [J]. Journal on Communications, 2022, 43(8): 131-141.
[3]	Bin LI, Xiaojie CHEN, Feng FENG, Qinglei ZHOU. FPGA multi-unit parallel optimization and implementation of post-quantum cryptography CRYSTALS-Kyber [J]. Journal on Communications, 2022, 43(2): 196-207.
[4]	Liehuang ZHU,Long WANG,Jiasheng LI,Chuan ZHANG,Weihua YUAN. New entity authentication and access control scheme in satellite communication network [J]. Journal on Communications, 2018, 39(6): 73-80.
[5]	Sen ZHAO,Qingqing GAN,Xiaoming WANG,Fang YU. Authentication scheme for multi-cloud environment based on smart card [J]. Journal on Communications, 2018, 39(4): 131-138.
[6]	Wei-guo SHEN,Wei WANG. Keystroke features recognition based on stable linear discriminant analysis [J]. Journal on Communications, 2017, 38(Z2): 26-29.
[7]	Ying-di DONG,Jin-ye PENG,Xiao-bo ZHANG,Zhen-long ZHANG. Quantum identity authentication scheme based on measurement-device-independent quantum key distribution protocol [J]. Journal on Communications, 2016, 37(2): 152-157.
[8]	. Authentication method in SWIM based on improved Diameter/EAP-MD5 [J]. Journal on Communications, 2014, 35(8): 1-7.
[9]	Zhi-jun WU,Ting ZHAO,Jin LEI. Authentication method in SWIM based on improved Diameter/EAP-MD5 [J]. Journal on Communications, 2014, 35(8): 1-7.
[10]	. Rational analysis of authentication protocols based on NGUYEN L H scheme [J]. Journal on Communications, 2013, 34(8): 3-26.
[11]	Xing-hua LI,Ling-juan DENG,Yuan ZHANG,Jian-feng MA. Rational analysis of authentication protocols based on NGUYEN L H scheme [J]. Journal on Communications, 2013, 34(8): 18-26.
[12]	. Secure anonymous authentication scheme based on elliptic curve and zero-knowledge proof in VANET [J]. Journal on Communications, 2013, 34(5): 6-61.
[13]	Chun-sheng GU. Breaking the HFEM public key scheme [J]. Journal on Communications, 2013, 34(3): 85-89.
[14]	Zhen-peng LIU,Feng-long WU,Kai-yu SHANG,Wen-lei CHAI,Xiao WANG. Mutual authentication scheme based on the TPM cloud computing platform [J]. Journal on Communications, 2012, 33(Z2): 20-24.
[15]	Xin LIU,Qiu-liang XU. Unclonable dynamic k-times anonymous authentication [J]. Journal on Communications, 2012, 33(7): 75-89.