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

Cryptography with Auxiliary Input and Trapdoor from Constant-Noise LPN

Yu Yu, Jiang Zhang

Published Jan 1, 2016• 46 citations
Publisher
DOI
10.1007/978-3-662-53018-4_9

Related papers

IND-CCA Secure Cryptography Based on a Variant of the LPN Problem

Nico Döttling, Jörn Müller‐Quade, Anderson C. A. Nascimento

Lecture notes in computer science•Jan 1, 2012•51 citations

Simple Chosen-Ciphertext Security from Low-Noise LPN

Eike Kiltz, Daniel Masny, Krzysztof Pietrzak

Lecture notes in computer science•Jan 1, 2014•50 citations

Efficient Pseudorandom Correlation Generators from Ring-LPN

Elette Boyle, Geoffroy Couteau, Niv Gilboa +3 more

Lecture notes in computer science•Jan 1, 2020•127 citations

Slightly Sublinear Trapdoor Hash Functions and PIR from Low-Noise LPN

Damiano Abram, Giulio Malavolta, Lawrence Roy

Trapdoor hash functions (TDHs) are compressing hash functions, with an additional trapdoor functionality: Given an encoding key for a function f, a hash on x together with a (small) input encoding allow one to recover f(x). TDHs are a versatile tool and a useful building block for more complex cryptographic protocols. In this work, we propose the first TDH construction assuming the (quasi-polynomial) hardness of the LPN problem with noise rate $$\varepsilon = O(\log ^{1+\beta } n / n)$$ for $$\beta >0$$ , i.e., in the so-called low-noise regime. The construction achieves $$2^{\varTheta (\log ^{1-\beta } \lambda )}$$ compression factor. As an application, we obtain private-information retrieval (PIR) with communication complexity $$L / 2^{\varTheta (\log ^{1-\beta } L)}$$ , for a database of size L. This is the first PIR scheme with non-trivial communication complexity (asymptotically smaller than L) from any code-based assumption.

Lecture notes in computer science•Dec 1, 2025•2 citations

Public-Key Encryption Schemes with Auxiliary Inputs

Yevgeniy Dodis, Shafi Goldwasser, Yael Tauman Kalai +2 more

Lecture notes in computer science•Jan 1, 2010•197 citations

Chosen-Ciphertext Secure Key Encapsulation Mechanism in the Standard Model

Shengfeng Xu, Xiangxue Li

Key Encapsulation Mechanism (KEM) is a foundational cryptography primitive, which can provide secure symmetric cryptographic key material for transmission by using public key algorithms. Until now, many Chosen-Ciphertext (IND-CCA) secure KEM schemes are constructed from Chosen-Plaintext (IND-CPA) or One-Way (OW-CPA) secure PKE via the generic Fujisaki-Okamoto (FO) transformations (TCC 2017). However, the security relies on the Random Oracle Model (ROM). To the best of our knowledge, there are no IND-CCA secure KEM schemes based on Learning Parity with Noise (LPN) assumption that can against post quantum attacks in the standard model. In this work, we propose the first direct construction of LPN-based KEM, which is secure in the standard model. In particular, we use double-trapdoor technique to answer adversary’s decryption queries correctly and a Target Collision Resistant (TCR) hash function to check the validity of the ciphertext. The encapsulated key is determined by a special LPN problem (with no random oracle required). The scheme is IND-CCA secure against post-quantum attacks under the low-noise LPN assumptions by a series of games and the security reduction is tight. Compared with previous schemes on 128-bit security level, our CCA-secure scheme only holds 50.78MB public keys, 62.50MB secret keys and 4.54KB ciphertexts, which is more efficient than the schemes of Döttlinget al.(ASIACRYPT 2012), Kiltzet al.(PKC 2014) and Yuet al.(CRYPTO 2016) ((7.27GB, 7.24GB, 7.03KB), (80.89MB, 46.23MB, 6.80KB) and (70.95MB, 70.65MB, 86.50KB) respectively).

IEEE Access•Jan 1, 2021•8 citations
Trapdoor hash functions (TDHs) are compressing hash functions, with an additional trapdoor functionality: Given an encoding key for a function f, a hash on x together with a (small) input encoding allow one to recover f(x). TDHs are a versatile tool and a useful building block for more complex cryptographic protocols. In this work, we propose the first TDH construction assuming the (quasi-polynomial) hardness of the LPN problem with noise rate ε=O(log⁡1+βn/n)\varepsilon = O(\log ^{1+\beta } n / n)ε=O(log1+βn/n) for β>0\beta >0β>0 , i.e., in the so-called low-noise regime. The construction achieves 2Θ(log⁡1−βλ)2^{\varTheta (\log ^{1-\beta } \lambda )}2Θ(log1−βλ) compression factor. As an application, we obtain private-information retrieval (PIR) with communication complexity L/2Θ(log⁡1−βL)L / 2^{\varTheta (\log ^{1-\beta } L)}L/2Θ(log1−βL) , for a database of size L. This is the first PIR scheme with non-trivial communication complexity (asymptotically smaller than L) from any code-based assumption.
Key Encapsulation Mechanism (KEM) is a foundational cryptography primitive, which can provide secure symmetric cryptographic key material for transmission by using public key algorithms. Until now, many Chosen-Ciphertext (IND-CCA) secure KEM schemes are constructed from Chosen-Plaintext (IND-CPA) or One-Way (OW-CPA) secure PKE via the generic Fujisaki-Okamoto (FO) transformations (TCC 2017). However, the security relies on the Random Oracle Model (ROM). To the best of our knowledge, there are no IND-CCA secure KEM schemes based on Learning Parity with Noise (LPN) assumption that can against post quantum attacks in the standard model. In this work, we propose the first direct construction of LPN-based KEM, which is secure in the standard model. In particular, we use double-trapdoor technique to answer adversary’s decryption queries correctly and a Target Collision Resistant (TCR) hash function to check the validity of the ciphertext. The encapsulated key is determined by a special LPN problem (with no random oracle required). The scheme is IND-CCA secure against post-quantum attacks under the low-noise LPN assumptions by a series of games and the security reduction is tight. Compared with previous schemes on 128-bit security level, our CCA-secure scheme only holds 50.78MB public keys, 62.50MB secret keys and 4.54KB ciphertexts, which is more efficient than the schemes of Döttlinget al.(ASIACRYPT 2012), Kiltzet al.(PKC 2014) and Yuet al.(CRYPTO 2016) ((7.27GB, 7.24GB, 7.03KB), (80.89MB, 46.23MB, 6.80KB) and (70.95MB, 70.65MB, 86.50KB) respectively).