Sponsor
Joseph Jaeger and Stefano Tessaro were partially supported by NSF grants CNS-1930117 (CAREER), CNS-1926324, CNS-2026774, a Sloan Research Fellowship, and a JP Morgan Faculty Award. Joseph Jaeger’s work done while at the University of Washington. Fang Song thanks Robin Kothari for helpful discussion on the element distinctness problem. Fang Song was supported by NSF grants CCF-2041841, CCF-2042414, and CCF-2054758 (CAREER).
Published In
Lecture Notes in Computer Science
Document Type
Pre-Print
Publication Date
11-4-2022
Subjects
Quantum Algorithms --Testing
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 with inherently longer keys or develop key-length extension techniques to amplify the security of a blockcipher to use longer keys.
We consider the latter approach and revisit the FX and double encryption constructions. Classically, FX was proven to be a secure key-length extension technique, while double encryption fails to be 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 a partially-quantum model, where the attacker has quantum access to the ideal primitive, but only classical access to FX. This is a natural model and also the strongest possible, since effective quantum attacks against FX exist in the fully-quantum model when quantum access is granted to both oracles. We provide two results for FX in this model. The first establishes the security of FX against non-adaptive attackers. The second establishes security against general adaptive attackers for 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. An extension to perfectly lazily sampling a quantum random permutation, which would help resolve the adaptive security of standard FX, is an important but challenging open question. We introduce techniques for partially-quantum proofs without relying on analyzing the classical and quantum oracles separately, which is common in existing work. This may be of broader interest.
For double encryption, we show that it amplifies strong pseudorandom permutation security in the fully-quantum model, strengthening a known result in the weaker sense of key-recovery security. This is done by adapting a technique of Tessaro and Thiruvengadam (TCC ’18) to reduce the security to the difficulty of solving the list disjointness problem and then showing its hardness via a chain of reductions to the known quantum difficulty of the element distinctness problem.
Locate the Document
DOI
10.1007/978-3-030-90459-3_8
Persistent Identifier
https://archives.pdx.edu/ds/psu/37214
Citation Details
Published as: Jaeger, J., Song, F., & Tessaro, S. (2021, November). Quantum key-length extension. In Theory of Cryptography Conference (pp. 209-239). Springer, Cham.
Description
This is the author’s version of a work. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document.