2022/05/06 by Bagus Santoso, Santoso, Bagus, Yasuhiko Ikematsu +5 · 1 citation
Computer Science · #Coding theory and cryptography #Cryptographic Implementations and Security #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2205.03255
openalex publication_date 2022/05/06 · openalex created_date 2022/05/11 · openalex updated_date 2026/07/28
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.