For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2015/06/01
Online ISSN: 1745-1337
Type of Manuscript: PAPER
Category: Cryptography and Information Security
Multivariate Quadratic problem, zero-knowledge identification protocol, finite field,
Full Text: PDF>>
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.