论文标题
基于缩小性问题的三通识别方案，一半作弊概率
Three-Pass Identification Scheme Based on MinRank Problem with Half Cheating Probability
论文作者
论文摘要
在2001年的Asiacrypt中，Courois提出了基于Minrank问题的第一个三通零知识识别（ID）方案。但是，在一轮Courtois的ID计划中，作弊概率，即作弊供奉献的成功概率是2/3，大于一半。尽管Courtois还提出了一种变体方案，该方案据称具有一半的作弊概率，但其安全性并未得到正式证明，并且需要在特定的单向功能上进行另一个硬度假设，并且验证者始终根据特定的非均匀分布产生挑战。在本文中，我们根据微小的问题提出了第一个三通零知识ID方案，即使只有两个位挑战空间，每个回合的作弊概率也完全是一半，而没有任何其他假设。与Curtois相比，我们提出的ID计划需要更少的回合和平均通信成本，而在相同的安全水平下进行了与模拟相同的安全水平。
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.
