Improved Identification Protocol Based on the MQ Problem
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E98-A No.6 pp.1255-1265
- Publication Date
- 2015/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E98.A.1255
- Type of Manuscript
- PAPER
- Category
- Cryptography and Information Security
Authors
Fábio S. MONTEIRO
Diretoria de Comunicacões e Tecnologia da Informacão da Marinha
Denise H. GOYA
Universidade Federal do ABC
Routo TERADA
Universidade de São Paulo
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Fábio S. MONTEIRO, Denise H. GOYA, Routo TERADA, "Improved Identification Protocol Based on the MQ Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E98-A, no. 6, pp. 1255-1265, June 2015, doi: 10.1587/transfun.E98.A.1255.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.1255/_p
Copy
@ARTICLE{e98-a_6_1255,
author={Fábio S. MONTEIRO, Denise H. GOYA, Routo TERADA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Improved Identification Protocol Based on the MQ Problem},
year={2015},
volume={E98-A},
number={6},
pages={1255-1265},
abstract={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.},
keywords={},
doi={10.1587/transfun.E98.A.1255},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Improved Identification Protocol Based on the MQ Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1255
EP - 1265
AU - Fábio S. MONTEIRO
AU - Denise H. GOYA
AU - Routo TERADA
PY - 2015
DO - 10.1587/transfun.E98.A.1255
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2015
AB - 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.
ER -
English
