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

王后珍; 蔡鑫伟; 郭岩; 张焕国

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

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 基于矩阵填充问题的五轮零知识身份认证方案
- 5-pass zero-knowledge identity authentication scheme based on matrix completion problem
- 通信学报 2021年42卷第11期页码：79-86
- 作者机构：
  
  1. 武汉大学国家网络安全学院，湖北武汉 430072
  2. 密码科学技术国家重点实验室，北京 100878
- 作者简介：
  
  [ "王后珍（1981− ），男，湖北恩施人，博士，武汉大学讲师，主要研究方向为信息安全、抗量子密码、量子计算等" ]
  [ "蔡鑫伟（1998− ），男，湖北武汉人，武汉大学硕士生，主要研究方向为信息安全、应用密码学等" ]
  [ "郭岩（1998− ），男，河北邢台人，武汉大学硕士生，主要研究方向为信息安全、应用密码学等" ]
  [ "张焕国（1945− ），男，湖北武汉人，博士，武汉大学教授，主要研究方向为信息安全、密码学、可信计算等" ]
- 基金信息：
  
  “十三五”国家密码发展基金资助项目(MMJJ201701304);国家自然科学基金资助项目(61332019);国家重点研发计划基金资助项目(2018YFC1604000)
- DOI：10.11959/j.issn.1000-436x.2021212
  中图分类号： TP3-0
- 网络出版日期：2021-11，
  
  纸质出版日期：2021-11-25
- 稿件说明：
移动端阅览
王后珍, 蔡鑫伟, 郭岩, 等. 基于矩阵填充问题的五轮零知识身份认证方案[J]. 通信学报, 2021,42(11):79-86.

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.
王后珍, 蔡鑫伟, 郭岩, 等. 基于矩阵填充问题的五轮零知识身份认证方案[J]. 通信学报, 2021,42(11):79-86. DOI： 10.11959/j.issn.1000-436x.2021212.

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 .

浏览量

437

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

VANET中基于区块链的分布式匿名认证方案

基于公平盲签名和分级加密的联盟链隐私保护方案

卫星通信网中一种新的实体认证与访问控制方案

多云环境下基于智能卡的认证方案

基于顽健线性判别分析的击键特征识别方法