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.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 scienceDec 1, 20251 citation

Public-Key Encryption Schemes with Auxiliary Inputs

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

Lecture notes in computer scienceJan 1, 2010199 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).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 AccessJan 1, 20217 citations

The Learning Stabilizers with Noise Problem

Alexander Poremba, Yihui Quek, Peter W. Shor

Random classical codes have good error correcting properties, and yet they are notoriously hard to decode in practice. Despite many decades of extensive study, the fastest known algorithms still run in exponential time. The Learning Parity with Noise (LPN) problem, which can be seen as the task of decoding a random linear code in the presence of noise, has thus emerged as a prominent hardness assumption with numerous applications in both cryptography and learning theory. Is there a natural quantum analog of the LPN problem? In this work, we introduce the Learning Stabilizers with Noise (LSN) problem, the task of decoding a random stabilizer code in the presence of local depolarizing noise. We give both polynomial-time and exponential-time quantum algorithms for solving LSN in various depolarizing noise regimes, ranging from extremely low noise, to low constant noise rates, and even higher noise rates up to a threshold. Next, we provide concrete evidence that LSN is hard. First, we show that LSN includes LPN as a special case, which suggests that it is at least as hard as its classical counterpart. Second, we prove worst-case to average-case reductions for variants of LSN. We then ask: what is the computational complexity of solving LSN? Because the task features quantum inputs, its complexity cannot be characterized by traditional complexity classes. Instead, we show that the LSN problem lies in a recently introduced (distributional and oracle) unitary synthesis class. Finally, we identify several applications of our LSN assumption, ranging from the construction of quantum bit commitment schemes to the computational limitations of learning from quantum data.Random classical codes have good error correcting properties, and yet they are notoriously hard to decode in practice. Despite many decades of extensive study, the fastest known algorithms still run in exponential time. The Learning Parity with Noise (LPN) problem, which can be seen as the task of decoding a random linear code in the presence of noise, has thus emerged as a prominent hardness assumption with numerous applications in both cryptography and learning theory. Is there a natural quantum analog of the LPN problem? In this work, we introduce the Learning Stabilizers with Noise (LSN) problem, the task of decoding a random stabilizer code in the presence of local depolarizing noise. We give both polynomial-time and exponential-time quantum algorithms for solving LSN in various depolarizing noise regimes, ranging from extremely low noise, to low constant noise rates, and even higher noise rates up to a threshold. Next, we provide concrete evidence that LSN is hard. First, we show that LSN includes LPN as a special case, which suggests that it is at least as hard as its classical counterpart. Second, we prove worst-case to average-case reductions for variants of LSN. We then ask: what is the computational complexity of solving LSN? Because the task features quantum inputs, its complexity cannot be characterized by traditional complexity classes. Instead, we show that the LSN problem lies in a recently introduced (distributional and oracle) unitary synthesis class. Finally, we identify several applications of our LSN assumption, ranging from the construction of quantum bit commitment schemes to the computational limitations of learning from quantum data.

arXiv:2410.18953Leibniz international proceedings in informaticsOct 24, 20242 citations

\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.