Exploiting preprocessing for quantum search to break parameters for MQ cryptosystems

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper we re-examine quantum search applied to the Multivariate Quadratic (MQ) hardness problem over the finite field GF(2). This problem is key to the security of a number of proposed post-quantum public-key cryptosystems designed to be resistant against attacks from quantum computers and in this paper we give a warning of the dangers of extrapolating parameters based upon the efficiency of quantum search algorithms. Our methods demonstrate that by applying
preprocessing to the MQ problem, we can reduce the computational load on the quantum computer and, in a generalisation of multi-target search for single-targets, improve the efficiency of the basic quantum search oracle
for the MQ problem over GF(2). Our work builds upon the MQ oracle introduced by Westerbaan and Schwabe and improves it to the extent that it breaks all quantum-resistant security parameters for the Gui cryptosystem proposed by the original authors. Our results hold both in the logical gate model and when the algorithm is
fully costed in terms of the Clifford+T universal gate set.
Original languageEnglish
Title of host publicationArithmetic of Finite Fields - 7th International Workshop, WAIFI 2018, Revised Selected Papers.
PublisherWAIFI
Publication statusPublished - 16 Jun 2018

Fingerprint

Quantum computers
Cryptography
Hardness

Keywords

  • quantum search
  • cryptography
  • multivariate quadratic

Cite this

Pring, B. (2018). Exploiting preprocessing for quantum search to break parameters for MQ cryptosystems. In Arithmetic of Finite Fields - 7th International Workshop, WAIFI 2018, Revised Selected Papers. WAIFI.

Exploiting preprocessing for quantum search to break parameters for MQ cryptosystems. / Pring, Benjamin.

Arithmetic of Finite Fields - 7th International Workshop, WAIFI 2018, Revised Selected Papers.. WAIFI, 2018.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Pring, B 2018, Exploiting preprocessing for quantum search to break parameters for MQ cryptosystems. in Arithmetic of Finite Fields - 7th International Workshop, WAIFI 2018, Revised Selected Papers.. WAIFI.
Pring B. Exploiting preprocessing for quantum search to break parameters for MQ cryptosystems. In Arithmetic of Finite Fields - 7th International Workshop, WAIFI 2018, Revised Selected Papers.. WAIFI. 2018
Pring, Benjamin. / Exploiting preprocessing for quantum search to break parameters for MQ cryptosystems. Arithmetic of Finite Fields - 7th International Workshop, WAIFI 2018, Revised Selected Papers.. WAIFI, 2018.
@inproceedings{6d3566c1a7d748bfa6f4189ca28c6071,
title = "Exploiting preprocessing for quantum search to break parameters for MQ cryptosystems",
abstract = "In this paper we re-examine quantum search applied to the Multivariate Quadratic (MQ) hardness problem over the finite field GF(2). This problem is key to the security of a number of proposed post-quantum public-key cryptosystems designed to be resistant against attacks from quantum computers and in this paper we give a warning of the dangers of extrapolating parameters based upon the efficiency of quantum search algorithms. Our methods demonstrate that by applyingpreprocessing to the MQ problem, we can reduce the computational load on the quantum computer and, in a generalisation of multi-target search for single-targets, improve the efficiency of the basic quantum search oraclefor the MQ problem over GF(2). Our work builds upon the MQ oracle introduced by Westerbaan and Schwabe and improves it to the extent that it breaks all quantum-resistant security parameters for the Gui cryptosystem proposed by the original authors. Our results hold both in the logical gate model and when the algorithm isfully costed in terms of the Clifford+T universal gate set.",
keywords = "quantum search, cryptography, multivariate quadratic",
author = "Benjamin Pring",
year = "2018",
month = "6",
day = "16",
language = "English",
booktitle = "Arithmetic of Finite Fields - 7th International Workshop, WAIFI 2018, Revised Selected Papers.",
publisher = "WAIFI",

}

TY - GEN

T1 - Exploiting preprocessing for quantum search to break parameters for MQ cryptosystems

AU - Pring, Benjamin

PY - 2018/6/16

Y1 - 2018/6/16

N2 - In this paper we re-examine quantum search applied to the Multivariate Quadratic (MQ) hardness problem over the finite field GF(2). This problem is key to the security of a number of proposed post-quantum public-key cryptosystems designed to be resistant against attacks from quantum computers and in this paper we give a warning of the dangers of extrapolating parameters based upon the efficiency of quantum search algorithms. Our methods demonstrate that by applyingpreprocessing to the MQ problem, we can reduce the computational load on the quantum computer and, in a generalisation of multi-target search for single-targets, improve the efficiency of the basic quantum search oraclefor the MQ problem over GF(2). Our work builds upon the MQ oracle introduced by Westerbaan and Schwabe and improves it to the extent that it breaks all quantum-resistant security parameters for the Gui cryptosystem proposed by the original authors. Our results hold both in the logical gate model and when the algorithm isfully costed in terms of the Clifford+T universal gate set.

AB - In this paper we re-examine quantum search applied to the Multivariate Quadratic (MQ) hardness problem over the finite field GF(2). This problem is key to the security of a number of proposed post-quantum public-key cryptosystems designed to be resistant against attacks from quantum computers and in this paper we give a warning of the dangers of extrapolating parameters based upon the efficiency of quantum search algorithms. Our methods demonstrate that by applyingpreprocessing to the MQ problem, we can reduce the computational load on the quantum computer and, in a generalisation of multi-target search for single-targets, improve the efficiency of the basic quantum search oraclefor the MQ problem over GF(2). Our work builds upon the MQ oracle introduced by Westerbaan and Schwabe and improves it to the extent that it breaks all quantum-resistant security parameters for the Gui cryptosystem proposed by the original authors. Our results hold both in the logical gate model and when the algorithm isfully costed in terms of the Clifford+T universal gate set.

KW - quantum search

KW - cryptography

KW - multivariate quadratic

M3 - Conference contribution

BT - Arithmetic of Finite Fields - 7th International Workshop, WAIFI 2018, Revised Selected Papers.

PB - WAIFI

ER -