In Asiacrypt 2001, Courtois proposed the first three-pass zero-knowledge identification (ID) scheme based on the MinRank problem. However, in a single round of Courtois' ID scheme, the cheating probability, i.e., the success probability of the cheating prover, is 2/3 which is larger than half. Although Courtois also proposed a variant scheme which is claimed to have half cheating probability, its security is not formally proven and it requires another hardness assumption on a specific one-way function and that verifier always generates challenges according to a specific non-uniform distribution. In this paper, we propose the first three-pass zero-knowledge ID scheme based on the MinRank problem with the cheating probability of exactly half for each round, even with only two-bit challenge space, without any additional assumption. Our proposed ID scheme requires fewer rounds and less total average communications costs compared to Curtois' under the same security level against impersonation.
翻译:在2001年亚历山哥里,Courtois基于MinRank问题提出了前三通零知识识别(ID)计划。然而,在单轮Courtois的识别(ID)计划中,欺骗概率(即作弊证明人的成功概率)为2/3,大于一半。虽然Courtois还提出了一个替代计划,声称该计划有一半作弊概率,但其安全没有得到正式证明,它要求对特定的单行功能另作硬性假设,而核查者总是根据特定的非统一分布产生挑战。在本文中,我们提出了基于MinRank问题的前三通零知识识别计划,每轮的欺骗概率完全为一半,即使只有两位挑战空间,而没有任何额外的假设。我们提议的识别计划要求比Curtois在防止冒险的同一安全级别下减少回合,降低通信总平均费用。