5-pass zero-knowledge identity authentication scheme based on matrix completion problem - Houzhen WANG; Xinwei CAI; Yan GUO; Huanguo ZHANG (Tongxin xuebao)
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.