2011 | OriginalPaper | Buchkapitel
Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials
verfasst von : Koichi Sakumoto, Taizo Shirai, Harunaga Hiwatari
Erschienen in: Advances in Cryptology – CRYPTO 2011
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 zero-knowledge 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.