Paper 2018/452

Time-space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2

Panjin Kim, Daewan Han, and Kyung Chul Jeong

Abstract

Performance of cryptanalytic quantum search algorithms is mainly inferred from query complexity which hides overhead induced by an implementation. To shed light on quantitative complexity analysis removing hidden factors, we provide a framework for estimating time-space complexity, with carefully accounting for characteristics of target cryptographic functions. Processor and circuit parallelization methods are taken into account, resulting in the time-space trade-off curves in terms of depth and qubit. The method guides howto rank different circuit designs in order of their efficiency. The framework is applied to representative cryptosystems NIST referred to as a guideline for security parameters, reassessing the security strengths of AES and SHA-2.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Quantum Information Processing
DOI
10.1007/s11128-018-2107-3
Keywords
Quantum circuitGroverParallelizationResource estimatesAESSHA-2
Contact author(s)
jeongkc @ nsr re kr
History
2018-11-01: revised
2018-05-21: received
See all versions
Short URL
https://ia.cr/2018/452
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/452,
      author = {Panjin Kim and Daewan Han and Kyung Chul Jeong},
      title = {Time-space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2},
      howpublished = {Cryptology ePrint Archive, Paper 2018/452},
      year = {2018},
      doi = {10.1007/s11128-018-2107-3},
      note = {\url{https://eprint.iacr.org/2018/452}},
      url = {https://eprint.iacr.org/2018/452}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.