You are looking at a specific version 20210503:204139 of this paper. See the latest version.

Paper 2021/579

Quantum Key-length Extension

Joseph Jaeger and Fang Song and Stefano Tessaro

Abstract

Should quantum computers become available, they will reduce the effective key length of basic secret-key primitives, such as blockciphers. To address this we will either need to use blockciphers which inherently have longer keys or use key-length extension techniques which employ a blockcipher to construct a more secure blockcipher that uses longer keys. We consider the latter approach -- in particular, analyzing the security of the FX and double encryption constructions. Classically, these constructs were considered as key-length extension techniques for DES. FX was proven to be a secure key-length extension technique, while double encryption was shown to be no more secure than single encryption due to a meet-in-the-middle attack. In this work we provide positive results, with concrete and tight bounds, for the security of both of these constructions against quantum attackers in ideal models. For FX, we consider security in the so-called "Q1 model," a natural model in which the attacker has quantum access to the ideal primitive, but only classic access to FX. We provide two partial results for FX in this model. The first establishes the security of FX against non-adaptive attackers. The second establishes security against fully adaptive attackers when considering a variant of FX using a random oracle in place of an ideal cipher. This result relies on the techniques of Zhandry (CRYPTO '19) for lazily sampling a quantum random oracle and are thus hard to extend to the true FX construction because it is currently unknown if a quantum random permutation can be lazily sampled. To the best of our knowledge, this result also is the first to introduce techniques to handle Q1 security in ideal models without analyzing the classical and quantum oracles separately, which may be of broader interest. For double encryption we apply a technique of Tessaro and Thiruvengadam (TCC '18) to establish that security reduces to the difficulty of solving the list disjointness problem, which we are able to reduce through a chain of results to the known quantum difficulty of the element distinctness problem.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
post-quantum cryptographyblock ciphersquantum random oracle modelconcrete securityprovable security
Contact author(s)
jsjaeger @ cs washington edu,tessaro @ cs washington edu,fang song @ pdx edu
History
2021-10-18: revised
2021-05-03: received
See all versions
Short URL
https://ia.cr/2021/579
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.