Paper 2018/008

Quantum Algorithms for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems

Yu-Ao Chen and Xiao-Shan Gao

Abstract

Decision of whether a Boolean equation system has a solution is an NPC problem and finding a solution is NP hard. In this paper, we present a quantum algorithm to decide whether a Boolean equation system F has a solution and compute one if F does have solutions with any given success probability. The complexity of the algorithm is polynomial in the size of F and the condition number of F. As a consequence, we have achieved exponential speedup for solving sparse Boolean equation systems if their condition numbers are small. We apply the quantum algorithm to the cryptanalysis of the stream cipher Trivum, the block cipher AES, the hash function SHA-3/Keccak, and the multivariate public key cryptosystems, and show that they are secure under quantum algebraic attack only if the condition numbers of the corresponding equation systems are large.

Note: The paper is on arXiv 1712.06239.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
quantum algorithmBoolean equation solvingquantum algebraic attac
Contact author(s)
xgao @ mmrc iss ac cn
History
2018-01-02: received
Short URL
https://ia.cr/2018/008
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/008,
      author = {Yu-Ao Chen and Xiao-Shan Gao},
      title = {Quantum Algorithms for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2018/008},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/008}},
      url = {https://eprint.iacr.org/2018/008}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.