基于矩阵填充问题的高效零知识身份认证方案
Efficient Zero-Knowledge Identification Based on Matrix Completion Problem
- 武汉大学学报（理学版）
- 作者机构：
1.空天信息安全与可信计算教育部重点实验室，武汉大学 国家网络安全学院， 湖北 武汉 430072
2.密码科学技术国家重点实验室，北京100878
- 作者简介：
王后珍，男，讲师，现从事应用密码学以及量子密码研究。E-mail：whz@whu.edu.cn
- 基金信息：国家重点研发计划项目(2018YFC1604000);“十三五”国家密码发展基金(MMJJ201701304);国家自然科学基金重点项目(61332019)
DOI：10.14188/j.1671-8836.2020.0230
中图分类号： TP309纸质出版日期：2021-04-24，
收稿日期：2020-09-23，
扫 描 看 全 文
引用本文
王后珍,郭岩,张焕国.基于矩阵填充问题的高效零知识身份认证方案[J].武汉大学学报（理学版）,2021,67(2):111-117.
WANG Houzhen,GUO Yan,ZHANG Huanguo.Efficient Zero-Knowledge Identification Based on Matrix Completion Problem [J].J Wuhan Univ （Nat Sci Ed）,2021,67(2):111-117.
王后珍,郭岩,张焕国.基于矩阵填充问题的高效零知识身份认证方案[J].武汉大学学报（理学版）,2021,67(2):111-117. DOI：10.14188/j.1671-8836.2020.0230.
WANG Houzhen,GUO Yan,ZHANG Huanguo.Efficient Zero-Knowledge Identification Based on Matrix Completion Problem [J].J Wuhan Univ （Nat Sci Ed）,2021,67(2):111-117. DOI：10.14188/j.1671-8836.2020.0230(Ch).
摘要
针对目前大多数身份认证密码协议容易遭受量子计算机攻击且实现效率较低的问题，基于矩阵填充问题设计了一种新型零知识身份认证协议。与现有类似方案相比，本文的方案具有密钥尺寸小、易于实现等特点。矩阵填充问题属于NPC（non-deterministic polynomial complete）问题，本文提出的协议具有抗量子计算攻击潜力。利用本文方案并采用Fiat-Shamir标准转换方法，可得到一种安全高效的抗量子计算数字签名算法。
Abstract
Since most of the current authentication cryptographic protocols are vulnerable to quantum computer attacks and have low implementation efficiency, we present a novel zero-knowledge authentication protocol based on the matrix completion problem in this paper. Compared with the existing similar schemes, our scheme has a smaller key size and is easier to implement. Besides, the matrix completion belongs to the NPC（non-deterministic polynomial complete） problem, so the protocol proposed in this paper has the potential to resist quantum computing attacks. Last but not least, a secure and efficient post-quantum digital signature can be obtained by employing the Fiat-Shamir method.
关键词
身份认证协议矩阵填充问题零知识证明NPC问题
Keywords
authentication protocolmatrix completion problemzero-knowledge proofNPC（non-deterministic polynomial complete） problem
references
GOLDWASSER S， MICALI S， RACKOFF C. The knowledge complexity of interactive proof systems ［J］. SIAM Journal on Computing， 1989， 18（1）：186-208. DOI：10.1137/0218012http://dx.doi.org/10.1137/0218012.
FEIGE U， FIAT A， SHAMIR A. Zero-knowledge proofs of identity ［J］. Journal of Cryptology， 1988， 1（2）：77-94. DOI：10.1007/bf02351717http://dx.doi.org/10.1007/bf02351717.
GUILLOU L C， QUISQUATER J J. A “paradoxical” indentity-based signature scheme resulting from zero-knowledge［C］//Advances in Cryptology—CRYPTO’ 88. New York： Springer， 1990：216-231. DOI：10.1007/0-387-34799-2_16http://dx.doi.org/10.1007/0-387-34799-2_16.
SCHNORR C P. Efficient signature generation by smart cards［J］. Journal of Cryptology， 1991， 4（3）：161-174. DOI：10.1007/bf00196725http://dx.doi.org/10.1007/bf00196725.
SHOR P W. Algorithms for quantum computation： Discrete logarithms and factoring［C］// Proceedings 35th Annual Symposium on Foundations of Computer Science. New York：IEEE，1994：124-134. DOI：10.1109/SFCS.1994.365700http://dx.doi.org/10.1109/SFCS.1994.365700.
ALAGIC G， ALPERIN-SHERIFF J， APON D， et al. Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process［EB/OL］.［2019-01-01］.https：//www.trustwrx.com/wp-content/uploads/2019/04/NIST-Post-Quantum-Cryptography.pdfhttps://www.trustwrx.com/wp-content/uploads/2019/04/NIST-Post-Quantum-Cryptography.pdf. DOI：10.6028/NIST.IR.8240http://dx.doi.org/10.6028/NIST.IR.8240.
STERN J. A new identification scheme based on syndrome decoding ［C］//Annual International Cryptology Conference. Berlin：Springer， 1993：13-21. DOI：10.1007/3-540-48329-2_2http://dx.doi.org/10.1007/3-540-48329-2_2.
GABORIT P， GIRAULT M. Lightweight code-based identification and signature ［C］// 2007 IEEE International Symposium on Information Theory. New York： IEEE， 2007：191-195. DOI：10.1109/ISIT.2007.4557225http://dx.doi.org/10.1109/ISIT.2007.4557225.
AGUILAR C， GABORIT P， SCHREK J. A new zero-knowledge code based identification scheme with reduced communication［C］//2011 IEEE Information Theory Workshop. New York：IEEE，2011：648-652. DOI： 10.1109/ITW.2011.6089577http://dx.doi.org/10.1109/ITW.2011.6089577.
CAYREL P L， ALAOUI S M， Hoffmann G，et al. An improved threshold ring signature scheme based on error correcting codes ［C］// International Workshop on the Arithmetic of Finite Fields. Berlin：Springer， 2012：45-63.DOI：10.1007/978-3-642-31662-3_4http://dx.doi.org/10.1007/978-3-642-31662-3_4.
COURTOIS N T. Efficient zero-knowledge authentication based on a linear algebra problem MinRank［C］// International Conference on the Theory and Application of Cryptology and Information Security. Berlin： Springer， 2001：402-421. DOI：10.1007/3-540-45682-1_24http://dx.doi.org/10.1007/3-540-45682-1_24.
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. DOI：10.1007/978-3-642-22792-9_40http://dx.doi.org/10.1007/978-3-642-22792-9_40.
SHAMIR A. An efficient identification scheme based on permuted kernels ［C］//Conference on the Theory and Application of Cryptology. Berlin：Springer， 1989：606-609.DOI：10.1007/0-387-34805-0_54http://dx.doi.org/10.1007/0-387-34805-0_54.
CHEN K F. A new identification algorithm［C］//Cryptography Policy and Algorithms Conference. Berlin：Springer，1995：244-249.DOI： 10.1007/BFb0032363http://dx.doi.org/10.1007/BFb0032363.
STERN J. Designing identification schemes with keys of short size ［C］// Annual International Cryptology Conference. Berlin： Springer， 1994：164-173.DOI：10.1007/3-540-48658-5_18http://dx.doi.org/10.1007/3-540-48658-5_18.
POINTCHEVAL D. A new identification scheme based on the perceptrons problem ［C］//International Conference on the Theory and Applications of Cryptographic Techniques. Berlin：Springer，1995：319-328.DOI：10.1007/3-540-49264-X_26http://dx.doi.org/10.1007/3-540-49264-X_26.
CAYREL P L， LINDNER R， RÜCKERT M， et al. Improved zero-knowledge identification with lattices ［J］. Tatra Mountains Mathematical Publications， 2012， 53（1）： 33-63. DOI：10.2478/v10127-012-0038-4http://dx.doi.org/10.2478/v10127-012-0038-4.
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. DOI：10.1007/978-3-030-26948-7_6http://dx.doi.org/10.1007/978-3-030-26948-7_6.
GOLDREICH O， OREN Y. Definitions and properties of zero-knowledge proof systems ［J］. Journal of Cryptology，1994， 7（1）：1-32. DOI：10.1007/BF00195207http://dx.doi.org/10.1007/BF00195207.
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. DOI：10.1006/jcss.1998.1608http://dx.doi.org/10.1006/jcss.1998.1608.
GABIDULIN E M. Theory of codes with maximum rank distance［J］. Problems of Information Transmission，1985，21（1）：1-12.
DERKSEN H. On the equivalence between low-rank matrix completion and tensor rank ［J］. Linear and Multilinear Algebra， 2018，66（4）：645–667.DOI：10.1080/03081087.2017.1315044http://dx.doi.org/10.1080/03081087.2017.1315044.
PEETERS R. Orthogonal representations over finite fields and the chromatic number of graphs ［J］. Combinatorica，1996， 16（3）：417-431. DOI：10.1007/BF01261326http://dx.doi.org/10.1007/BF01261326.
CRAVO G. Matrix completion problems ［J］. Linear Algebra and Its Applications， 2009，430（8-9）：2511-2540.DOI： 10.1016/j.laa.2008.12.029http://dx.doi.org/10.1016/j.laa.2008.12.029.
COPPERSMITH D， STERN J， VAUDENAY S. Attacks on the birational permutation signature schemes ［C］//Annual International Cryptology Conference. Berlin：Springer， 1993：435-443. DOI：10.1007/3-540-48329-2_37http://dx.doi.org/10.1007/3-540-48329-2_37.
COURTOIS N T. The security of hidden field equations （HFE） ［C］//Cryptographers' Track at the RSA Conference. Berlin：Springer， 2001：266-281.DOI：10.1007/3-540-45353-9_20http://dx.doi.org/10.1007/3-540-45353-9_20.
SHAMIR A， KIPNIS A. Cryptanalysis of the HFE public key cryptosystem by Relinearization ［C］//Advances in Cryptology — Crypto’99. Berlin：Springer，1999：19-30.DOI：10.1007/3-540-48405-1_2http://dx.doi.org/10.1007/3-540-48405-1_2.
COURTOIS N. The Security of Cryptographic Primitives Based on Multivariate Algebraic Problems： MQ， MinRank， IP， HFE ［D］. Paris ：Université ParisⅥ，2001.
GOUBIN L， COURTOIS N T. Cryptanalysis of the TTM cryptosystem［C］//International Conference on the Theory and Application of Cryptology and Information Security. Berlin：Springer，2000：44-57. DOI：10.1007/3-540-44448-3_4http://dx.doi.org/10.1007/3-540-44448-3_4.
FAUGÈRE J C， LEVY-DIT-VEHEL F， PERRET L. Cryptanalysis of MinRank［C］//Annual International Cryptology Conference. Berlin：Springer， 2008：280-296.DOI：10.1007/978-3-540-85174-5_16http://dx.doi.org/10.1007/978-3-540-85174-5_16.
FIAT A， SHAMIR A. How to prove yourself： Practical solutions to identification and signature problems［C］//Advances in Cryptology — CRYPTO’ 86. Berlin： Springer， 1986：186-194. DOI：10.1007/3-540-47721-7_12http://dx.doi.org/10.1007/3-540-47721-7_12.
0
浏览量
32
下载量
1
CSCD
关联资源
相关文章
相关作者
相关机构