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

Naor-Yung Transform for IND-CCA Probing Security with Lattice Instantiations

Katharina Boudgoust, Laurent Imbert A, Loïc Masure, Laz Panard

Published Mar 5, 2026• 0 citations
OpenAlex

Abstract

In this work, we propose novel security notions for encryption schemes that combine the power of a typical black-box adversary with additional side-channel access to sensitive algorithms (key generation and decryption). We then extend the Naor-Yung (NY) transform to this setting, enabling generic upgrades from IND-CPA to IND-CCA security under probing attacks. We instantiate this framework with the IND-CPA scheme Rutile and its IND-CCA counterpart Topaz, two lattice-based encryption schemes inspired by Kyber but redesigned with probing security and masking-friendliness in mind. By replacing Kyber’s masking-unfriendly components (centered binomial distributions and the FO-transform) with sum-of-uniforms sampling and the NY-transform, we achieve better side-channel resistance by design, resulting in a practical, provably secure encryption scheme that resists both theoretical and side-channel attacks in the probing model.

Related papers

URDP: General Framework for Direct CCA2 Security from any Lattice-Based PKE Scheme

Roohallah Rastaghi

Design efficient lattice-based cryptosystem secure against adaptive chosen ciphertext attack (IND-CCA2) is a challenge problem. To the date, full CCA2-security of all proposed lattice-based PKE schemes achieved by using a generic transformations such as either strongly unforgeable one-time signature schemes (SU-OT-SS), or a message authentication code (MAC) and weak form of commitment. The drawback of these schemes is that encryption requires "separate encryption". Therefore, the resulting encryption scheme is not sufficiently efficient to be used in practice and it is inappropriate for many applications such as small ubiquitous computing devices with limited resources such as smart cards, active RFID tags, wireless sensor networks and other embedded devices. In this work, for the first time, we introduce an efficient universal random data padding (URDP) scheme, and show how it can be used to construct a "direct" CCA2-secure encryption scheme from "any" worst-case hardness problems in (ideal) lattice in the standard model, resolving a problem that has remained open till date. This novel approach is a "black-box" construction and leads to the elimination of separate encryption, as it avoids using general transformation from CPA-secure scheme to a CCA2-secure one. IND-CCA2 security of this scheme can be tightly reduced in the standard model to the assumption that the underlying primitive is an one-way trapdoor function.

arXiv:1302.6352•Feb 26, 2013•0 citations

Disjoint Simulatability and Security Reduction of a Class of Lattice-Based Schemes

Baosheng Huang, Guoqing Zhou, Lin Wang +4 more

Security is the primary consideration for cryptographic algorithms. For key encapsulation mechanisms, it is generally required to satisfy indistinguishability under chosen ciphertext attacks(IND-CCA) in the quantum random oracle model(QROM). The approach of constructing IND-CCA-secure key encapsulation mechanisms from public-key encryption schemes that satisfy disjoint simulatability (DS) is tight. However, existing work on DS either does not consider decryption error rates or requires stronger security properties from the underlying schemes. In this work, we presents a DS-based reduction method that accounts for decryption errors without relying on IND-CPA and this method is applicable to most scenarios of lattice-based encryption schemes including LWE-baced and NTRU-based deterministic public key encryption(DPKE). This work can enhance confidence in the security of lattice-based encryption algorithms in the post-quantum era.

International Conference on Electronics and Communication, Network and Computer Technology (ECNCT)•Jul 1, 2026•0 citations

Novel efficient lattice-based IBE schemes with CPK for fog computing

Yanfeng Shi, Shuo Qiu, Jiqiang Liu +1 more

The data security of fog computing is a key problem for the Internet of things. Identity-based encryption (IBE) from lattices is extremely suitable for fog computing. It is able to not only simplify certificate management, but also resist quantum attacks. In this paper, firstly, we construct a novel efficient lattice-based IBE scheme with Combined Public Key (CPK) technique by keeping from consumptive trapdoor generation algorithm and preimage sampling algorithm, which is required by the existing lattice-based IBE schemes based on learning with errors (LWE). In addition, its key storage cost is lower and it is IND-ID-CPA secure in the random oracle model. Furthermore, based on this, an enhanced lattice-based IBE scheme with IND-ID-CCA security is developed by employing strong one-time signature. Our schemes only need O(n3/log n) additions of vectors, while the existing schemes need at least O(n3) of additions and multiplications in Setup and Extract phase.

Mathematical Biosciences & Engineering•Jan 1, 2020•2 citations

CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM

Joppe W. Bos, Léo Ducas, Eike Kiltz +6 more

Rapid advances in quantum computing, together with the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digitalsignature, encryption, and key-establishment protocols, have created significant interest in post-quantum cryptographic schemes. This paper introduces Kyber (part of CRYSTALS - Cryptographic Suite for Algebraic Lattices - a package submitted to NIST post-quantum standardization effort in November 2017), a portfolio of post-quantum cryptographic primitives built around a key-encapsulation mechanism (KEM), based on hardness assumptions over module lattices. Our KEM is most naturally seen as a successor to the NEWHOPE KEM (Usenix 2016). In particular, the key and ciphertext sizes of our new construction are about half the size, the KEM offers CCA instead of only passive security, the security is based on a more general (and flexible) lattice problem, and our optimized implementation results in essentially the same running time as the aforementioned scheme. We first introduce a CPA-secure public-key encryption scheme, apply a variant of the Fujisaki-Okamoto transform to create a CCA-secure KEM, and eventually construct, in a black-box manner, CCA-secure encryption, key exchange, and authenticated-key-exchange schemes. The security of our primitives is based on the hardness of Module-LWE in the classical and quantum random oracle models, and our concrete parameters conservatively target more than 128 bits of postquantum security.

IEEE European Symposium on Security and Privacy•Apr 1, 2018•1,342 citations

New IND-CPA-D Attacks on BFV and BGV

Hyeongmin Choe, Min-Sik Kang, Damien Stehlé

IND-CPA-D security is an extension of IND-CPA security introduced in the context of Fully Homomorphic Encryption (FHE). It captures the situation where the computation result is known to the adversary; it is in particular necessary for FHE with threshold decryption. This work presents three new attacks in this situation on the BFV and BGV FHE schemes, when their parameters are instantiated with heuristic assumptions commonly used to enable correctness. We first extend the bootstrapping failure attacks from Cheon et al. [CCS'24] on the DM/CGGI and CKKS schemes, to both BFV and BGV. We focus on BGV when instantiated with the so-called powerful-basis representation of ring elements. The second attack relies on skewing the ciphertext noise in BFV, making it outpace the heuristic noise bounds for plaintext-ciphertext multiplications. This is achieved by crafting plaintexts, for which the noise bounds do not hold. The third and last attack focuses on outpacing the noise growth in BFV ciphertext-ciphertext multiplications. For this purpose, we skew the mask part of the ciphertext by selecting a random encryption of zero, whose addition yields a ciphertext with a sufficiently large mask norm. While the first two attacks successfully recover the secret key, the last attack instead breaks the IND-CPA-D indistinguishability game. We report experiments on all these attacks, based on the HElib and OpenFHE libraries, respectively, for BGV and BFV. Notably, the second attack implemented in OpenFHE fully recovers the secret key in a few minutes to a few hours, depending on the parameters.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 12, 2026•0 citations

Enhancing Post-Quantum KEMs: A Secure and Efficient Transformation

Sai Charan Reddy Nevuri

This paper proposes a new generic Encrypt-thenMAC (EtM) transformation for constructing IND-CCA secure Key Encapsulation Mechanisms (KEMs) in the post-quantum setting. The transformation builds on a public-key encryption scheme satisfying one-wayness under plaintext-checking attacks (OW-PCA) and an existentially unforgeable MAC, and formally achieves tight IND-CCA security in the random oracle model via a rigorous security reduction. Unlike the widely used FujisakiOkamoto (FO) transformation, our approach eliminates the need for ciphertext re-encryption during decapsulation-a major source of computational overhead and side-channel vulnerability in lattice-based implementations. We instantiate the transformation using the ML-KEM (FIPS 203) subroutine, yielding the ML-KEM-EtM variant. Experimental results show that ML-KEMEtM reduces decapsulation cycle counts by$72-79 {\%}$across security levels, with only a modest increase in encapsulation cost$(1.8-7.3 {\%})$and ciphertext size$(1.0-2.1 {\%})$. The scheme thus offers a practical and efficient a lternative to F O-based KEMs, especially in performance-critical scenarios such as post-quantum TLS handshakes, where decapsulation efficiency is paramount.

International Symposium on Digital Forensics and Security (ISDFS)•Mar 19, 2026•0 citations
In this work, we propose novel security notions for encryption schemes that combine the power of a typical black-box adversary with additional side-channel access to sensitive algorithms (key generation and decryption). We then extend the Naor-Yung (NY) transform to this setting, enabling generic upgrades from IND-CPA to IND-CCA security under probing attacks. We instantiate this framework with the IND-CPA scheme Rutile and its IND-CCA counterpart Topaz, two lattice-based encryption schemes inspired by Kyber but redesigned with probing security and masking-friendliness in mind. By replacing Kyber’s masking-unfriendly components (centered binomial distributions and the FO-transform) with sum-of-uniforms sampling and the NY-transform, we achieve better side-channel resistance by design, resulting in a practical, provably secure encryption scheme that resists both theoretical and side-channel attacks in the probing model.
Design efficient lattice-based cryptosystem secure against adaptive chosen ciphertext attack (IND-CCA2) is a challenge problem. To the date, full CCA2-security of all proposed lattice-based PKE schemes achieved by using a generic transformations such as either strongly unforgeable one-time signature schemes (SU-OT-SS), or a message authentication code (MAC) and weak form of commitment. The drawback of these schemes is that encryption requires "separate encryption". Therefore, the resulting encryption scheme is not sufficiently efficient to be used in practice and it is inappropriate for many applications such as small ubiquitous computing devices with limited resources such as smart cards, active RFID tags, wireless sensor networks and other embedded devices. In this work, for the first time, we introduce an efficient universal random data padding (URDP) scheme, and show how it can be used to construct a "direct" CCA2-secure encryption scheme from "any" worst-case hardness problems in (ideal) lattice in the standard model, resolving a problem that has remained open till date. This novel approach is a "black-box" construction and leads to the elimination of separate encryption, as it avoids using general transformation from CPA-secure scheme to a CCA2-secure one. IND-CCA2 security of this scheme can be tightly reduced in the standard model to the assumption that the underlying primitive is an one-way trapdoor function.
Security is the primary consideration for cryptographic algorithms. For key encapsulation mechanisms, it is generally required to satisfy indistinguishability under chosen ciphertext attacks(IND-CCA) in the quantum random oracle model(QROM). The approach of constructing IND-CCA-secure key encapsulation mechanisms from public-key encryption schemes that satisfy disjoint simulatability (DS) is tight. However, existing work on DS either does not consider decryption error rates or requires stronger security properties from the underlying schemes. In this work, we presents a DS-based reduction method that accounts for decryption errors without relying on IND-CPA and this method is applicable to most scenarios of lattice-based encryption schemes including LWE-baced and NTRU-based deterministic public key encryption(DPKE). This work can enhance confidence in the security of lattice-based encryption algorithms in the post-quantum era.
The data security of fog computing is a key problem for the Internet of things. Identity-based encryption (IBE) from lattices is extremely suitable for fog computing. It is able to not only simplify certificate management, but also resist quantum attacks. In this paper, firstly, we construct a novel efficient lattice-based IBE scheme with Combined Public Key (CPK) technique by keeping from consumptive trapdoor generation algorithm and preimage sampling algorithm, which is required by the existing lattice-based IBE schemes based on learning with errors (LWE). In addition, its key storage cost is lower and it is IND-ID-CPA secure in the random oracle model. Furthermore, based on this, an enhanced lattice-based IBE scheme with IND-ID-CCA security is developed by employing strong one-time signature. Our schemes only need O(n3/log n) additions of vectors, while the existing schemes need at least O(n3) of additions and multiplications in Setup and Extract phase.
Rapid advances in quantum computing, together with the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digitalsignature, encryption, and key-establishment protocols, have created significant interest in post-quantum cryptographic schemes. This paper introduces Kyber (part of CRYSTALS - Cryptographic Suite for Algebraic Lattices - a package submitted to NIST post-quantum standardization effort in November 2017), a portfolio of post-quantum cryptographic primitives built around a key-encapsulation mechanism (KEM), based on hardness assumptions over module lattices. Our KEM is most naturally seen as a successor to the NEWHOPE KEM (Usenix 2016). In particular, the key and ciphertext sizes of our new construction are about half the size, the KEM offers CCA instead of only passive security, the security is based on a more general (and flexible) lattice problem, and our optimized implementation results in essentially the same running time as the aforementioned scheme. We first introduce a CPA-secure public-key encryption scheme, apply a variant of the Fujisaki-Okamoto transform to create a CCA-secure KEM, and eventually construct, in a black-box manner, CCA-secure encryption, key exchange, and authenticated-key-exchange schemes. The security of our primitives is based on the hardness of Module-LWE in the classical and quantum random oracle models, and our concrete parameters conservatively target more than 128 bits of postquantum security.
IND-CPA-D security is an extension of IND-CPA security introduced in the context of Fully Homomorphic Encryption (FHE). It captures the situation where the computation result is known to the adversary; it is in particular necessary for FHE with threshold decryption. This work presents three new attacks in this situation on the BFV and BGV FHE schemes, when their parameters are instantiated with heuristic assumptions commonly used to enable correctness. We first extend the bootstrapping failure attacks from Cheon et al. [CCS'24] on the DM/CGGI and CKKS schemes, to both BFV and BGV. We focus on BGV when instantiated with the so-called powerful-basis representation of ring elements. The second attack relies on skewing the ciphertext noise in BFV, making it outpace the heuristic noise bounds for plaintext-ciphertext multiplications. This is achieved by crafting plaintexts, for which the noise bounds do not hold. The third and last attack focuses on outpacing the noise growth in BFV ciphertext-ciphertext multiplications. For this purpose, we skew the mask part of the ciphertext by selecting a random encryption of zero, whose addition yields a ciphertext with a sufficiently large mask norm. While the first two attacks successfully recover the secret key, the last attack instead breaks the IND-CPA-D indistinguishability game. We report experiments on all these attacks, based on the HElib and OpenFHE libraries, respectively, for BGV and BFV. Notably, the second attack implemented in OpenFHE fully recovers the secret key in a few minutes to a few hours, depending on the parameters.
This paper proposes a new generic Encrypt-thenMAC (EtM) transformation for constructing IND-CCA secure Key Encapsulation Mechanisms (KEMs) in the post-quantum setting. The transformation builds on a public-key encryption scheme satisfying one-wayness under plaintext-checking attacks (OW-PCA) and an existentially unforgeable MAC, and formally achieves tight IND-CCA security in the random oracle model via a rigorous security reduction. Unlike the widely used FujisakiOkamoto (FO) transformation, our approach eliminates the need for ciphertext re-encryption during decapsulation-a major source of computational overhead and side-channel vulnerability in lattice-based implementations. We instantiate the transformation using the ML-KEM (FIPS 203) subroutine, yielding the ML-KEM-EtM variant. Experimental results show that ML-KEMEtM reduces decapsulation cycle counts by72−79%72-79 {\%}72−79%across security levels, with only a modest increase in encapsulation cost(1.8−7.3%)(1.8-7.3 {\%})(1.8−7.3%)and ciphertext size(1.0−2.1%)(1.0-2.1 {\%})(1.0−2.1%). The scheme thus offers a practical and efficient a lternative to F O-based KEMs, especially in performance-critical scenarios such as post-quantum TLS handshakes, where decapsulation efficiency is paramount.