Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2510.08725

Post-Quantum Security of Block Cipher Constructions

Gorjan Alagic, Chen Bai, Christian Majenz, Kaiyan Shi

Published Oct 9, 2025• 0 citations
arXivHTMLPDF

Abstract

Block ciphers are versatile cryptographic ingredients that are used in a wide range of applications ranging from secure Internet communications to disk encryption. While post-quantum security of public-key cryptography has received significant attention, the case of symmetric-key cryptography (and block ciphers in particular) remains a largely unexplored topic. In this work, we set the foundations for a theory of post-quantum security for block ciphers and associated constructions. Leveraging our new techniques, we provide the first post-quantum security proofs for the key-length extension scheme FX, the tweakable block ciphers LRW and XEX, and most block cipher encryption and authentication modes. Our techniques can be used for security proofs in both the plain model and the quantum ideal cipher model. Our work takes significant initial steps in establishing a rigorous understanding of the post-quantum security of practical symmetric-key cryptography.

DOI
10.48550/arxiv.2510.08725

Related papers

A Review of Block Ciphers and Its Post-Quantum Considerations

R Chethana, Jayavrinda Vrindavanam V, Subarna Roy +1 more

Recent advances in cryptography aim to address threats posed by quantum computers. However, these advances have focused disproportionately on asymmetric schemes, while symmetric primitives like block ciphers have received less attention. The common assumption is that doubling block cipher key sizes provides adequate quantum resistance, but this oversimplifies the challenge. This paper provides a systematic examination of block cipher security in the quantum computing era. The paper first establishes a formal framework for understanding block cipher security, covering their mathematical foundations and essential security properties. Building on this foundation, we examine how quantum computing fundamentally challenges these security assumptions, going beyond the simple impact on key lengths. Our review of recent research reveals that quantum attacks can exploit structural vulnerabilities in block ciphers and their modes of operation, requiring more comprehensive defenses than key length adjustments alone. We analyze emerging approaches in quantum-resistant design and identify critical areas requiring further research to ensure block cipher security in a post-quantum world.

IEEE Access•Jan 1, 2025•8 citations

New Era of Security analysis in Cryptography: Post Quantum Cryptography

Pagalla Bhavani Shankar, P. L. N. Prakash Kumar, Nazini Mahammad +1 more

In today’s world more and more electronic devices are connected through the channel “internet”. To secure these devices, designers rely on cryptographic standards that provide encryption, authentication and data-integrity. However, future advances in quantum computing threaten the security of these standards as they are predicted to break the underlying hard mathematical problems. It is therefore of the utmost importance to find new standards that are safe against quantum computers. The design and analysis of such quantum-safe algorithms is studied in the field of many post-quantum encryption schemes are subject to decryption failures. This means that even after a proper execution of the algorithm, there is a (very small) chance that the message or key is not transmitted correctly. It simply led like that decryption failures lead to a new attack vector in which failing cipher texts are assembled and used to reconstruct the secret key. To secure the connected devices and data the method of Post Quantum Cryptography will plays a vital role. Post Quantum Cryptography improves the security proof bound on decryption failure attacks.

Routledge eBooks•May 18, 2023•0 citations

Provably Quantum-Secure Tweakable Block Ciphers

Akinori Hosoyamada, Tetsu Iwata

Recent results on quantum cryptanalysis show that some symmetric key schemes can be broken in polynomial time even if they are proven to be secure in the classical setting. Liskov, Rivest, and Wagner showed that secure tweakable block ciphers can be constructed from secure block ciphers in the classical setting. However, Kaplan et al. showed that their scheme can be broken by polynomial time quantum superposition attacks, even if underlying block ciphers are quantum-secure. Since then, it remains open if there exists a mode of block ciphers to build quantum-secure tweakable block ciphers. This paper settles the problem in the reduction-based provable security paradigm. We show the first design of quantum-secure tweakable block ciphers based on quantum-secure block ciphers, and present a provable security bound. Our construction is simple, and when instantiated with a quantum-secure n-bit block cipher, it is secure against attacks that query arbitrary quantum superpositions of plaintexts and tweaks up to O(2n/6) quantum queries. Our security proofs use the compressed oracle technique introduced by Zhandry. More precisely, we use an alternative formalization of the technique introduced by Hosoyamada and Iwata.

IACR Transactions on Symmetric Cryptology•Mar 19, 2021•17 citations

A Survey on the Quantum Security of Block Cipher-Based Cryptography

S.E. Bootsma, M. De Vries

The development of quantum computers represents an important advancement in computing, using quantum mechanics to address problems that were previously difficult to solve. This technological advancement poses a challenge for cryptographic systems. While some methods are known to be vulnerable, the impact of quantum computing on symmetric cryptography has received less research attention, largely because the common advice is to simply double the key size. This paper explores how quantum computing affects symmetric cryptography, focusing on block cipher-based cryptography. It surveys existing literature on the quantum resilience of symmetric cryptographic primitives based on block ciphers and their security in various scenarios. Not all symmetric cryptographic functionalities are quantum-secure, and their security depends on the specific adversary model being considered. We provide an overview of the research conducted and pinpoint areas where further investigation is needed.

IEEE Access•Jan 1, 2024•7 citations

Post‐Quantum Symmetric Cryptography

María Naya‐Plasencia

The scientific community is expending significant effort to anticipate the enormous consequences of the arrival of quantum computers in cryptography. The main quantum algorithms used in symmetric cryptanalysis so far have used mainly Grover's algorithm. There are two main models considered to classify quantum attacks on symmetric schemes: Q1 model and Q2 model. Besides the natural need for having bigger keys in the post-quantum world for an equivalent ideal security, the need also for bigger than usual internal states for avoiding internal quantum collisions seems like a good idea. As a future interesting field of work, new generic ways of extending the internal state size, as well as the key size, with a quantum security proof could be very useful for securely extending the use of current secure block ciphers to post-quantum applications.

Wiley eBooks•Dec 1, 2023•2 citations

Quantum resilient security proofs

Hélder Vieira de Freitas Maia Martins

Recent developments in quantum computers pose an imminent threat to cryptography since many widely used cryptographic schemes will no longer be secure. This worrisome scenario motivated a growing interest in the field of post-quantum cryptography, which aims to design cryptosystems that are postquantum secure, i.e. secure against quantum-capable adversaries. While finding post-quantum computational hardness assumptions is pivotal to achieve this goal, an issue that is often overlooked is provable security. In fact, to prove that the post-quantum computational hardness necessarily implies post-quantum security of the derived cryptosystem, the reduction argument that establishes this implication also needs to be post-quantum. As such, many new methods have been devised in the last few years to handle this adaptation to the quantum setting. In particular, the quantum analogue of the Random Oracle Model has garnered special interest, as it is the foundation of many cryptographic schemes, from public-key encryption to digital signatures. It is also very problematic and usually the main culprit of the failure of security proofs when transitioning to the quantum setting. This work offers a comprehensive exposition on the most influential techniques developed in the last decade to enable or facilitate the construction of security proofs in the Quantum Random Oracle Model (QROM). Each presented technique offers an unique purpose and a solution to a problem provoked by the QROM, and, as such, as a whole, this works allows for an understanding of the most common strategies to construct these type of security proofs. This is accomplished by presenting and analyzing the security proof of three cryptographic schemes set in this model, which underlines the central role these techniques take in provable quantum security.

•Dec 21, 2024•0 citations
Block ciphers are versatile cryptographic ingredients that are used in a wide range of applications ranging from secure Internet communications to disk encryption. While post-quantum security of public-key cryptography has received significant attention, the case of symmetric-key cryptography (and block ciphers in particular) remains a largely unexplored topic. In this work, we set the foundations for a theory of post-quantum security for block ciphers and associated constructions. Leveraging our new techniques, we provide the first post-quantum security proofs for the key-length extension scheme FX, the tweakable block ciphers LRW and XEX, and most block cipher encryption and authentication modes. Our techniques can be used for security proofs in both the plain model and the quantum ideal cipher model. Our work takes significant initial steps in establishing a rigorous understanding of the post-quantum security of practical symmetric-key cryptography.
Recent advances in cryptography aim to address threats posed by quantum computers. However, these advances have focused disproportionately on asymmetric schemes, while symmetric primitives like block ciphers have received less attention. The common assumption is that doubling block cipher key sizes provides adequate quantum resistance, but this oversimplifies the challenge. This paper provides a systematic examination of block cipher security in the quantum computing era. The paper first establishes a formal framework for understanding block cipher security, covering their mathematical foundations and essential security properties. Building on this foundation, we examine how quantum computing fundamentally challenges these security assumptions, going beyond the simple impact on key lengths. Our review of recent research reveals that quantum attacks can exploit structural vulnerabilities in block ciphers and their modes of operation, requiring more comprehensive defenses than key length adjustments alone. We analyze emerging approaches in quantum-resistant design and identify critical areas requiring further research to ensure block cipher security in a post-quantum world.
In today’s world more and more electronic devices are connected through the channel “internet”. To secure these devices, designers rely on cryptographic standards that provide encryption, authentication and data-integrity. However, future advances in quantum computing threaten the security of these standards as they are predicted to break the underlying hard mathematical problems. It is therefore of the utmost importance to find new standards that are safe against quantum computers. The design and analysis of such quantum-safe algorithms is studied in the field of many post-quantum encryption schemes are subject to decryption failures. This means that even after a proper execution of the algorithm, there is a (very small) chance that the message or key is not transmitted correctly. It simply led like that decryption failures lead to a new attack vector in which failing cipher texts are assembled and used to reconstruct the secret key. To secure the connected devices and data the method of Post Quantum Cryptography will plays a vital role. Post Quantum Cryptography improves the security proof bound on decryption failure attacks.
Recent results on quantum cryptanalysis show that some symmetric key schemes can be broken in polynomial time even if they are proven to be secure in the classical setting. Liskov, Rivest, and Wagner showed that secure tweakable block ciphers can be constructed from secure block ciphers in the classical setting. However, Kaplan et al. showed that their scheme can be broken by polynomial time quantum superposition attacks, even if underlying block ciphers are quantum-secure. Since then, it remains open if there exists a mode of block ciphers to build quantum-secure tweakable block ciphers. This paper settles the problem in the reduction-based provable security paradigm. We show the first design of quantum-secure tweakable block ciphers based on quantum-secure block ciphers, and present a provable security bound. Our construction is simple, and when instantiated with a quantum-secure n-bit block cipher, it is secure against attacks that query arbitrary quantum superpositions of plaintexts and tweaks up to O(2n/6) quantum queries. Our security proofs use the compressed oracle technique introduced by Zhandry. More precisely, we use an alternative formalization of the technique introduced by Hosoyamada and Iwata.
The development of quantum computers represents an important advancement in computing, using quantum mechanics to address problems that were previously difficult to solve. This technological advancement poses a challenge for cryptographic systems. While some methods are known to be vulnerable, the impact of quantum computing on symmetric cryptography has received less research attention, largely because the common advice is to simply double the key size. This paper explores how quantum computing affects symmetric cryptography, focusing on block cipher-based cryptography. It surveys existing literature on the quantum resilience of symmetric cryptographic primitives based on block ciphers and their security in various scenarios. Not all symmetric cryptographic functionalities are quantum-secure, and their security depends on the specific adversary model being considered. We provide an overview of the research conducted and pinpoint areas where further investigation is needed.
The scientific community is expending significant effort to anticipate the enormous consequences of the arrival of quantum computers in cryptography. The main quantum algorithms used in symmetric cryptanalysis so far have used mainly Grover's algorithm. There are two main models considered to classify quantum attacks on symmetric schemes: Q1 model and Q2 model. Besides the natural need for having bigger keys in the post-quantum world for an equivalent ideal security, the need also for bigger than usual internal states for avoiding internal quantum collisions seems like a good idea. As a future interesting field of work, new generic ways of extending the internal state size, as well as the key size, with a quantum security proof could be very useful for securely extending the use of current secure block ciphers to post-quantum applications.
Recent developments in quantum computers pose an imminent threat to cryptography since many widely used cryptographic schemes will no longer be secure. This worrisome scenario motivated a growing interest in the field of post-quantum cryptography, which aims to design cryptosystems that are postquantum secure, i.e. secure against quantum-capable adversaries. While finding post-quantum computational hardness assumptions is pivotal to achieve this goal, an issue that is often overlooked is provable security. In fact, to prove that the post-quantum computational hardness necessarily implies post-quantum security of the derived cryptosystem, the reduction argument that establishes this implication also needs to be post-quantum. As such, many new methods have been devised in the last few years to handle this adaptation to the quantum setting. In particular, the quantum analogue of the Random Oracle Model has garnered special interest, as it is the foundation of many cryptographic schemes, from public-key encryption to digital signatures. It is also very problematic and usually the main culprit of the failure of security proofs when transitioning to the quantum setting. This work offers a comprehensive exposition on the most influential techniques developed in the last decade to enable or facilitate the construction of security proofs in the Quantum Random Oracle Model (QROM). Each presented technique offers an unique purpose and a solution to a problem provoked by the QROM, and, as such, as a whole, this works allows for an understanding of the most common strategies to construct these type of security proofs. This is accomplished by presenting and analyzing the security proof of three cryptographic schemes set in this model, which underlines the central role these techniques take in provable quantum security.