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

Lecture notes in computer science

On Quantum Ciphertext Indistinguishability, Recoverability, and OAEP

Juliane Krämer, Patrick Struck

Published Jan 1, 2022• 2 citations
Publisher
DOI
10.1007/978-3-031-17234-2_14

Related papers

History-Recoverability Post-Quantum Security (HR-PQS)

Trinity Labo

This paper introduces History-Recoverability Post-Quantum Security (HR-PQS), a lightweight theoretical framework for post-quantum security based on the principle of unrecoverable history. Rather than treating the quantum threat as merely a problem of replacing vulnerable cryptographic algorithms, HR-PQS reformulates post-quantum security as a question of whether future quantum-capable adversaries can reconstruct meaningful past histories from stored ciphertexts, keys, logs, backups, certificates, metadata, and operational residues. The central claim is that post-quantum cryptography is necessary but not sufficient. Even when quantum-resistant algorithms are deployed, long-lived information may remain vulnerable through archived ciphertexts, residual key material, metadata leakage, certificate chains, traffic patterns, and backup recovery paths. HR-PQS therefore shifts the security objective from simple decryption failure to semantic history-unrecoverability. The framework unifies existing security practices such as post-quantum cryptography, perfect forward secrecy, ratcheting, secure key erasure, re-encryption, envelope encryption, metadata hiding, and cryptographic agility under a single operational principle: history pruning. In this view, key rotation is not merely a lifecycle procedure, but a mechanism for cutting future reconstruction paths from past encrypted histories. Mathematically, HR-PQS models a future quantum adversary as a relational observer with access to quantum computation, classical computation, internal information, stored ciphertexts, backups, and metadata. Security is defined through a history-recoverability functional combining mutual information leakage, semantic recovery advantage, collapse risk, and operational cost. The paper further introduces a semantic recovery game and a history-recoverability distance for measuring whether an adversary can reconstruct useful domain-specific features of past information, such as financial transaction graphs, medical diagnosis patterns, communication networks, or enterprise activity timelines. The theory is inspired by TrinityLabo's Recoverable Reality Principle and Relational Recoverable Reality Principle, but reverses their role for cryptographic security: in physical theory, good compression should remain recoverable; in security theory, attacker-side reconstruction must remain impossible. HR-PQS is not proposed as a new cryptographic primitive or replacement protocol. Instead, it is a lightweight upper-level theory for organizing existing and emerging post-quantum security practices around the deeper requirement of protecting the past from future reconstruction. In short: not merely quantum-resistant encryption, but unrecoverable history.

•May 10, 2026•0 citations

Quantum Indistinguishability for Public Key Encryption

Tommaso Gagliardoni, Juliane Krämer, Patrick Struck

Lecture notes in computer science•Jan 1, 2021•15 citations

Computational Indistinguishability between Quantum States and Its Cryptographic Application

亮周 河内, Akinori Kawachi

•Jan 1, 2005•0 citations

Quantum Indistinguishability for Public Key Encryption

Tommaso Gagliardoni, Juliane Krämer, Patrick Struck

In this work we study the quantum security of public key encryption schemes (PKE). Boneh and Zhandry (CRYPTO'13) initiated this research area for PKE and symmetric key encryption (SKE), albeit restricted to a classical indistinguishability phase. Gagliardoni et al. (CRYPTO'16) advanced the study of quantum security by giving, for SKE, the first definition with a quantum indistinguishability phase. For PKE, on the other hand, no notion of quantum security with a quantum indistinguishability phase exists. Our main result is a novel quantum security notion (qIND-qCPA) for PKE with a quantum indistinguishability phase, which closes the aforementioned gap. We show a distinguishing attack against code-based schemes and against LWE-based schemes with certain parameters. We also show that the canonical hybrid PKE-SKE encryption construction is qIND-qCPA-secure, even if the underlying PKE scheme by itself is not. Finally, we classify quantum-resistant PKE schemes based on the applicability of our security notion. Our core idea follows the approach of Gagliardoni et al. by using so-called type-2 operators for encrypting the challenge message. At first glance, type-2 operators appear unnatural for PKE, as the canonical way of building them requires both the secret and the public key. However, we identify a class of PKE schemes - which we call recoverable - and show that for this class type-2 operators require merely the public key. Moreover, recoverable schemes allow to realise type-2 operators even if they suffer from decryption failures, which in general thwarts the reversibility mandated by type-2 operators. Our work reveals that many real-world quantum-resistant PKE schemes, including most NIST PQC candidates and the canonical hybrid construction, are indeed recoverable.

arXiv:2003.00578•Mar 1, 2020•3 citations

Computational Indistinguishability Between Quantum States and Its Cryptographic Application

Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura +1 more

Lecture notes in computer science•Jan 1, 2005•47 citations

An Indistinguishably Secure Function Encryption Scheme

Ping Zhang, Yamin Li, Muhua Liu

In this work, we first design a function encryption scheme by using key encapsulation. We combine public key encryption with symmetric encryption to implement the idea of key encapsulation. In the key encapsulation, we use a key to turn a message (plaintext) into a ciphertext by symmetric encryption, and then we use public key encryption to turn this key into another ciphertext. In the design of function encryption scheme, we use the public key encryption system, symmetric encryption system, noninteractive proof system, indistinguishable obfuscator, and commitment scheme. Finally, we prove the indistinguishable security of our function encryption scheme.

Security and Communication Networks•Nov 5, 2019•1 citation
This paper introduces History-Recoverability Post-Quantum Security (HR-PQS), a lightweight theoretical framework for post-quantum security based on the principle of unrecoverable history. Rather than treating the quantum threat as merely a problem of replacing vulnerable cryptographic algorithms, HR-PQS reformulates post-quantum security as a question of whether future quantum-capable adversaries can reconstruct meaningful past histories from stored ciphertexts, keys, logs, backups, certificates, metadata, and operational residues. The central claim is that post-quantum cryptography is necessary but not sufficient. Even when quantum-resistant algorithms are deployed, long-lived information may remain vulnerable through archived ciphertexts, residual key material, metadata leakage, certificate chains, traffic patterns, and backup recovery paths. HR-PQS therefore shifts the security objective from simple decryption failure to semantic history-unrecoverability. The framework unifies existing security practices such as post-quantum cryptography, perfect forward secrecy, ratcheting, secure key erasure, re-encryption, envelope encryption, metadata hiding, and cryptographic agility under a single operational principle: history pruning. In this view, key rotation is not merely a lifecycle procedure, but a mechanism for cutting future reconstruction paths from past encrypted histories. Mathematically, HR-PQS models a future quantum adversary as a relational observer with access to quantum computation, classical computation, internal information, stored ciphertexts, backups, and metadata. Security is defined through a history-recoverability functional combining mutual information leakage, semantic recovery advantage, collapse risk, and operational cost. The paper further introduces a semantic recovery game and a history-recoverability distance for measuring whether an adversary can reconstruct useful domain-specific features of past information, such as financial transaction graphs, medical diagnosis patterns, communication networks, or enterprise activity timelines. The theory is inspired by TrinityLabo's Recoverable Reality Principle and Relational Recoverable Reality Principle, but reverses their role for cryptographic security: in physical theory, good compression should remain recoverable; in security theory, attacker-side reconstruction must remain impossible. HR-PQS is not proposed as a new cryptographic primitive or replacement protocol. Instead, it is a lightweight upper-level theory for organizing existing and emerging post-quantum security practices around the deeper requirement of protecting the past from future reconstruction. In short: not merely quantum-resistant encryption, but unrecoverable history.
In this work we study the quantum security of public key encryption schemes (PKE). Boneh and Zhandry (CRYPTO'13) initiated this research area for PKE and symmetric key encryption (SKE), albeit restricted to a classical indistinguishability phase. Gagliardoni et al. (CRYPTO'16) advanced the study of quantum security by giving, for SKE, the first definition with a quantum indistinguishability phase. For PKE, on the other hand, no notion of quantum security with a quantum indistinguishability phase exists. Our main result is a novel quantum security notion (qIND-qCPA) for PKE with a quantum indistinguishability phase, which closes the aforementioned gap. We show a distinguishing attack against code-based schemes and against LWE-based schemes with certain parameters. We also show that the canonical hybrid PKE-SKE encryption construction is qIND-qCPA-secure, even if the underlying PKE scheme by itself is not. Finally, we classify quantum-resistant PKE schemes based on the applicability of our security notion. Our core idea follows the approach of Gagliardoni et al. by using so-called type-2 operators for encrypting the challenge message. At first glance, type-2 operators appear unnatural for PKE, as the canonical way of building them requires both the secret and the public key. However, we identify a class of PKE schemes - which we call recoverable - and show that for this class type-2 operators require merely the public key. Moreover, recoverable schemes allow to realise type-2 operators even if they suffer from decryption failures, which in general thwarts the reversibility mandated by type-2 operators. Our work reveals that many real-world quantum-resistant PKE schemes, including most NIST PQC candidates and the canonical hybrid construction, are indeed recoverable.
In this work, we first design a function encryption scheme by using key encapsulation. We combine public key encryption with symmetric encryption to implement the idea of key encapsulation. In the key encapsulation, we use a key to turn a message (plaintext) into a ciphertext by symmetric encryption, and then we use public key encryption to turn this key into another ciphertext. In the design of function encryption scheme, we use the public key encryption system, symmetric encryption system, noninteractive proof system, indistinguishable obfuscator, and commitment scheme. Finally, we prove the indistinguishable security of our function encryption scheme.