Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials (following Sakumoto, Shirai and Hiwatari)

A problem of solving a system of multivariate quadratic polynomials over a finite field, which is called an MQ problem, is a promising problem in cryptography. A number of studies have been conducted on designing public-key schemes using the MQ problem, which are known as multivariate public-key cryptography (MPKC). However, the security of the existing schemes in MPKC relies not only on the MQ problem but also on an Isomorphism of Polynomials (IP) problem. In this talk, we present public-key identification schemes based on the conjectured intractability of the MQ problem under the assumption of the existence of a non-interactive commitment scheme. The schemes (due to Sakumoto, Shirai and Hiwatari) do not rely on the IP problem, and they consist of an identification protocol which is zero-knowledge argument of knowledge for the MQ problem. For a practical parameter choice, the efficiency of these schemes is highly comparable to that of identification schemes based on another problem including Permuted Kernels, Syndrome Decoding, Constrained Linear Equations, and Permuted Perceptrons. Furthermore, even if the protocol is repeated in parallel, the schemes can achieve the security under active attack with some additional cost.