Improved Identification Protocol Based on the MQ Problem

Fábio S. MONTEIRO  Denise H. GOYA  Routo TERADA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E98-A   No.6   pp.1255-1265
Publication Date: 2015/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E98.A.1255
Type of Manuscript: PAPER
Category: Cryptography and Information Security
Multivariate Quadratic problem,  zero-knowledge identification protocol,  finite field,  

Full Text: PDF>>
Buy this Article

The MQ problem, which consists of solving a system of multivariate quadratic polynomials over a finite field, has attracted the attention of researchers for the development of public-key cryptosystems because (1) it is NP-complete, (2) there is no known polynomial-time algorithm for its solution, even in the quantum computational model, and (3) it enables cryptographic primitives of practical interest. In 2011, Sakumoto, Shirai and Hiwatari presented two new zero-knowledge identification protocols based exclusively on the MQ problem. The 3-pass identification protocol of Sakumoto et al. has impersonation probability 2/3. In this paper, we propose an improvement that reduces the impersonation probability to 1/2. The result is a protocol that reduces the total computation time, the total communication needed and requires a smaller number of rounds for the same security level. We also present a new extension that achieves an additional communication reduction with the use of some smaller hash commitments, but maintaining the same security level.