  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.
