## Public-Key Identification Schemes Based on
Multivariate Quadratic Polynomials

**Koichi Sakumoto, Taizo Shirai, and Harunaga Hiwatari**

*Sony Corporation, Japan*
**Abstract.**
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 paper,
we propose 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. Our schemes do *not*
rely on the
IP problem, and they consist of an identification protocol which is zeroknowledge
argument of knowledge for the MQ problem. For a practical
parameter choice, the efficiency of our 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, our scheme can achieve the security under active attack with
some additional cost.

**Keywords:**
identification scheme, zero knowledge, MQ problem.