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

Houzhen WANG; Xinwei CAI; Yan GUO; Huanguo ZHANG

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

您当前的位置：

首页 >

文章列表页 >

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

Papers | 更新时间：2024-06-05

- 5-pass zero-knowledge identity authentication scheme based on matrix completion problem
- Journal on Communications Vol. 42, Issue 11, Pages: 79-86(2021)
- 作者机构：
  
  1. 武汉大学国家网络安全学院，湖北武汉 430072
  2. 密码科学技术国家重点实验室，北京 100878
- 作者简介：
- 基金信息：
  
  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)
- DOI：10.11959/j.issn.1000-436x.2021212
  CLC： TP3-0
- Online First：2021-11，
  
  Published：25 November 2021
- 稿件说明：
移动端阅览
Houzhen WANG, Xinwei CAI, Yan GUO, et al. 5-pass zero-knowledge identity authentication scheme based on matrix completion problem[J]. Journal on Communications, 2021, 42(11): 79-86.
DOI：

Houzhen WANG, Xinwei CAI, Yan GUO, et al. 5-pass zero-knowledge identity authentication scheme based on matrix completion problem[J]. Journal on Communications, 2021, 42(11): 79-86. DOI： 10.11959/j.issn.1000-436x.2021212.

摘要

针对现存绝大多数身份认证协议容易遭受量子计算攻击及实现效率低的缺陷，基于矩阵填充（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.

关键词

Keywords

references

GOLDWASSER S , MICALI S , RACKOFF C . The knowledge complexity of interactive proof systems [J ] . SIAM Journal on Computing , 1989 , 18 ( 1 ): 186 - 208 .

FEIGE U , FIAT A , SHAMIR A . Zero-knowledge proofs of identity [J ] . Journal of Cryptology , 1988 , 1 ( 2 ): 77 - 94 .

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 .

SCHNORR C P . Efficient signature generation by smart cards [J ] . Journal of Cryptology , 1991 , 4 ( 3 ): 161 - 174 .

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 .

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 .

STERN J , . A new identification scheme based on syndrome decoding [C ] // Advances in Cryptology — CRYPTO’ 93 . Berlin:Springer , 1994 : 13 - 21 .

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 .

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 .

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 .

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 .

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 .

SHAMIR A , . An efficient identification scheme based on permuted kernels (extended abstract) [C ] // Advances in Cryptology — CRYPTO’ 89 Proceedings . Berlin:Springer , 1989 : 606 - 609 .

CHEN K F , . A new identification algorithm [C ] // Cryptography:Policy and Algorithms . Berlin:Springer , 1996 : 244 - 249 .

STERN J , . Designing identification schemes with keys of short size [C ] // Advances in Cryptology — CRYPTO ’94 . Berlin:Springer , 1994 : 164 - 173 .

POINTCHEVAL D , . A new identification scheme based on the perceptrons problem [C ] // Advances in Cryptology — EUROCRYPT ’95 . Berlin:Springer , 1995 : 319 - 328 .

CAYREL P L , LINDNER R , RÜCKERT M , et al . Improved zero-knowledge identification with lattices [C ] // Provable Security . Berlin:Springer , 2010 : 1 - 17 .

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 .

王后珍 , 郭岩 , 张焕国 . 基于矩阵填充问题的高效零知识身份认证方案 [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 .

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 .

GABIDULIN E M . Theory of codes with maximum rank distance(translation) [J ] . Problems of Information Transmission , 1985 , 21 ( 1 ): 1 - 12 .

HARM D . On the equivalence between low-rank matrix completion and tensor rank [J ] . Linear and Multilinear Algebra , 2018 , 66 ( 4 ): 645 - 667 .

PEETERS R . Orthogonal representations over finite fields and the chromatic number of graphs [J ] . Combinatorica , 1996 , 16 ( 3 ): 417 - 431 .

CRAVO G . Matrix completion problems [J ] . Linear Algebra and Its Applications , 2009 , 430 ( 8/9 ): 2511 - 2540 .

COPPERSMITH D , STERN J , VAUDENAY S . Attacks on the birational permutation signature schemes [C ] // Advances in Cryptology —CRYPTO’ 93 . Berlin:Springer , 1993 : 435 - 443 .

COURTOIS N T , . The security of hidden field equations (HFE) [C ] // Topics in Cryptology — CT-RSA 2001 . Berlin:Springer , 2001 : 266 - 281 .

KIPNIS A , SHAMIR A . Cryptanalysis of the HFE public key cryptosystem by relinearization [C ] // Advances in Cryptology — CRYPTO’ 99 . Berlin:Springer , 1999 : 19 - 30 .

GOUBIN L , COURTOIS N T . Cryptanalysis of the TTM cryptosystem [C ] // Advances in Cryptology — ASIACRYPT 2000 . Berlin:Springer , 2000 : 44 - 57 .

COURTOIS N T . The security of cryptographic primitives based on multivariate algebraic problems:MQ,MinRank,IP,HFE [D ] . Paris:Paris 6 University . 2001 .

FAUGERE J C,LEVY-DIT-VEHELF,PERRETL , . Cryptanalysis of minrank [C ] // Advances in Cryptology-CRYPTO’08 . Berlin:Springer , 2008 : 280 - 296 .

张海波 , 黄宏武 , 刘开健 , 等 . 车联网中可证安全的匿名可追溯快速组认证协议 [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 .

田苗苗 , 陈静 , 仲红 . 格上基于身份的增量签名方案 [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 .

Views

1192

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Privacy-preserving authentication scheme for electricity trading in V2G network using anonymous credential and blockchain

Distributed anonymous authentication scheme based on the blockchain in VANET

Privacy protection scheme based on fair blind signature and hierarchical encryption for consortium blockchain

New entity authentication and access control scheme in satellite communication network

Authentication scheme for multi-cloud environment based on smart card

Related Author

HUANG Rong

HU Baiji

LI Yuancheng

Kaiping CUI

Xia FENG

Qingqing XIE

Liangmin WANG

Zhihong LI

Related Institution

Institute of Information and Communication, China Electric Power Research Institute Co., Ltd.

School of Control and Computer Engineering, North China Electric Power University

School of Computer Science and Communication Engineering, Jiangsu University

School of Automotive and Traffic Engineering, Jiangsu University

School of Cyber Science and Engineering, Southeast University

AI问答

⁰