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

Cybersecurity

Lattice-based, LWE-leakage model for Gaussian and uniform secret and its application in decentralization

Xiaokang Dai, Jingwei Chen, Wenyuan Wu, Yong Feng

Published Nov 26, 2025• 0 citations
Publisher

Abstract

Abstract In the case of standard LWE samples $$({\textbf {A}},{\textbf {b = sA + e}})$$ ( A , b = sA + e ) , $${\textbf {A}}$$ A is typically uniformly over $$\mathbb {Z}_q^{n \times m}$$ Z q n × m . Under the $$\textsf {DLWE}$$ DLWE assumption, the conditional distribution of $${\textbf {s}}|({\textbf {A}}, {\textbf {b}})$$ s | ( A , b ) and $${\textbf {s}}$$ s is expected to be consistent. However, in the case where an adversary chooses $${\textbf {A}}$$ A adaptively, the disparity between the two entities may be larger. In this work, our primary focus is on the quantification of the Average Conditional Min-Entropy $$\tilde{H}_\infty ({\textbf {s}}|{\textbf {sA + e}})$$ H ~ ∞ ( s | sA + e ) of $${\textbf {s}}$$ s , where $${\textbf {A}}$$ A is chosen by the adversary. Brakerski and Döttling answered the question in one case: they proved that when $${\textbf {s}}$$ s is uniformly chosen from $$\mathbb {Z}_q^n$$ Z q n , it holds that $$\tilde{H}_\infty ({\textbf {s}}|{\textbf {sA + e}}) \varpropto \rho _\sigma (\varLambda _q({\textbf {A}}))$$ H ~ ∞ ( s | sA + e ) ∝ ρ σ ( Λ q ( A

DOI
10.1186/s42400-025-00439-5

Related papers

Leaky LWE: Learning with Errors with Semi-Adaptive Secret- and Error-Leakage

Russell W. F. Lai, Monisha Swarnakar, Ivy K. Y. Woo

The Learning with Errors (LWE) problem asks to distinguish noisy samples s^T A + e^T mod q from uniformly random values given the random matrix A. In this work, we show that a variant called Leaky LWE, where the distinguisher receives additionally noisy leakages (s^T, e^T) L + f^T of the LWE secret s and error e for low-norm matrix L chosen adaptively by the distinguisher after seeing A, is not easier than the standard LWE of the same dimensions up to polynomial losses in the noise level and the modulus. More generally, we show that the Leaky LWE problem is hard even if the public matrix A is structured and/or hinted and if the non-leaky parts of the secret and error do not follow Gaussian distributions, as long as the corresponding LWE problem without leakage is hard. Our reduction from LWE to Leaky LWE unifies and extends prior results on the Error-Leakage LWE problem [Döttling-Kolonelos-Lai-Lin-Malavolta-Rahimi, EUROCRYPT'23], where L only acts on the error e and the Hint-MLWE problem [Kim-Lee-Seo-Song, CRYPTO'23], where L is restricted to concatenations of random Gaussian scalar matrices not controlled by the distinguisher. Previously, the Hint-MLWE and Error-Leakage LWE assumptions were used as computational replacements of the statistical noise flooding technique in security proofs which led to improved parameters in lattice-based cryptographic constructions such as zero-knowledge proofs, threshold signatures and registration-based encryption. We provide lemmas which abstract out such computational arguments based on Leaky LWE.

IACR Communications in Cryptology•Oct 6, 2025•4 citations

On the Hardness of Module Learning with Errors with Short Distributions

Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois +1 more

The Module Learning With Errors ( $$\text {M-LWE}$$ ) problem is a core computational assumption of lattice-based cryptography which offers an interesting trade-off between guaranteed security and concrete efficiency. The problem is parameterized by a secret distribution as well as an error distribution. There is a gap between the choices of those distributions for theoretical hardness results (standard formulation of $$\text {M-LWE}$$ , i.e., uniform secret modulo q and Gaussian error) and practical schemes (small bounded secret and error). In this work, we make progress toward narrowing this gap. More precisely, we prove that $$\text {M-LWE}$$ with uniform $$\eta $$ -bounded secret for any $$1 \le \eta \ll q$$ and Gaussian error, in both its search and decision variants, is at least as hard as the standard formulation of $$\text {M-LWE}$$ , provided that the module rank d is at least logarithmic in the ring degree n. We also prove that the search version of $$\text {M-LWE}$$ with large uniform secret and uniform $$\eta $$ -bounded error is at least as hard as the standard $$\text {M-LWE}$$ problem, if the number of samples m is close to the module rank d and with further restrictions on $$\eta $$ . The latter result can be extended to provide the hardness of search $$\text {M-LWE}$$ with uniform $$\eta $$ -bounded secret and error under specific parameter conditions. Overall, the results apply to all cyclotomic fields, but most of the intermediate results are proven in more general number fields.

Journal of Cryptology•Nov 30, 2022•36 citations

Provably Secure LWE Encryption with Smallish Uniform Noise and Secret

Daniel Cabarcas, Florian Göpfert, Patrick Weiden

Abstract. In this paper we propose the first provably secure public key encryption scheme based on the Learning with Errors (LWE) problem, in which secrets and errors are sampled uniformly at random from a relatively small set rather than from the commonly used discrete Gaussian distribution. Using a uniform distribution, instead of a Gaussian, has the potential of improving computational efficiency a great deal due to its simplicity, thus making the scheme attractive for use in practice. At the same time our scheme features the strong security guarantee of being based on the hardness of worst-case lattice problems. After presenting the construction of our scheme we prove its security and propose asymptotic parameters. Finally, we compare our scheme on several measures to one of the most efficient LWE-based encryption schemes with Gaussian noise. We show that the expected efficiency improvement is debunked, due to the large blow-up of the parameter sets involved.

•Jan 1, 2014•2 citations

Gaussian Sampling Precision and Information Leakage in Lattice Cryptography.

Markku-Juhani Olavi Saarinen

•Jan 1, 2015•11 citations

Lattice-Based Post Quantum Cryptography Using Variations of Learning with Error (LWE)

Parth D. Shah, Priteshkumar Prajapati, Dhaval Patel

Communications in computer and information science•Jan 1, 2025•3 citations

Multi-distribution bi-deniable inner product encryption based on Decision-LWE

Hangchao Ding, Huayun Tang, Jia Chen +1 more

Bi-deniable Encryption scheme means that when the sender and the receiver are coerced, the coercer can obtain fake plaintext, random numbers, and secret keys. It’s a solution strategy in the case of information leakage. Compared with traditional encryption, deniable encryption can provide secret communications in situations of coercion in the Post-Quantum era. Compared with sender-deniable encryption and receiver-deniable encryption, bi-deniable encryption can achieve secret communications in the situation that both sender and receiver are coerced by the coercer. So, we propose to design a bi-deniable encryption scheme under the multi-distribution model. In our bi-deniable encryption scheme, we construct a bi-deniable encryption scheme based on the assumption of Decision-Learning With Errors (DLWE) under the multi-distribution model. Firstly, the principle of Inner Product Predicate Encryption (IPPE) is applied in our scheme. Secondly, we apply the framework of Bi-Translucent Set (BTS), combined with inner product predicate encryption. Thirdly, we construct a series of probabilistic polynomial time algorithms, which apply linear transformation between different lattice structures, and Regev dual encryption. Fourthly, the statistical indistinguishability between the sampling algorithm with discrete Gaussian sampling algorithm, and the computational indistinguishability between LWE’s ciphertext samples with uniform samples, the property of indistinguishability is applied in theorem proving, which obtain Indistinguishability under Chosen Plaintext Attacks (IND-CPA) security and the property of bi-deniability. Given the value range of the Gaussian parameter and security parameter in our scheme, the correctness of the bi-deniable encryption scheme is guaranteed. We also give the security proof of IND-CPA and bi-deniability’s property by a series of games. The ‘Inner-Product Bi-Translucent Set’ Bi-Deniable Encryption scheme under the multi-distribution model is based on Decision-LWE assumption, and can avoid quantum-resistant attacks. The bi-deniable encryption scheme is firstly constructed by the inner product with the Decision-LWE assumption, which can provide better properties of security and deniability.

Journal of High Speed Networks•Mar 8, 2024•0 citations
Abstract In the case of standard LWE samples (A,b = sA + e)({\textbf {A}},{\textbf {b = sA + e}})(A,b = sA + e) ( A , b = sA + e ) , A{\textbf {A}}A A is typically uniformly over Zqn×m\mathbb {Z}_q^{n \times m}Zqn×m​ Z q n × m . Under the DLWE\textsf {DLWE}DLWE DLWE assumption, the conditional distribution of s∣(A,b){\textbf {s}}|({\textbf {A}}, {\textbf {b}})s∣(A,b) s | ( A , b ) and s{\textbf {s}}s s is expected to be consistent. However, in the case where an adversary chooses A{\textbf {A}}A A adaptively, the disparity between the two entities may be larger. In this work, our primary focus is on the quantification of the Average Conditional Min-Entropy H~∞(s∣sA + e)\tilde{H}_\infty ({\textbf {s}}|{\textbf {sA + e}})H~∞​(s∣sA + e) H ~ ∞ ( s | sA + e ) of s{\textbf {s}}s s , where A{\textbf {A}}A A is chosen by the adversary. Brakerski and Döttling answered the question in one case: they proved that when s{\textbf {s}}s s is uniformly chosen from Zqn\mathbb {Z}_q^nZqn​ Z q n , it holds that H~∞(s∣sA + e)∝ρσ(Λq(A))\tilde{H}_\infty ({\textbf {s}}|{\textbf {sA + e}}) \varpropto \rho _\sigma (\varLambda _q({\textbf {A}}))H~∞​(s∣sA + e)∝ρσ​(Λq​(A)) H ~ ∞ ( s | sA + e ) ∝ ρ σ ( Λ q ( A
The Learning with Errors (LWE) problem asks to distinguish noisy samples s^T A + e^T mod q from uniformly random values given the random matrix A. In this work, we show that a variant called Leaky LWE, where the distinguisher receives additionally noisy leakages (s^T, e^T) L + f^T of the LWE secret s and error e for low-norm matrix L chosen adaptively by the distinguisher after seeing A, is not easier than the standard LWE of the same dimensions up to polynomial losses in the noise level and the modulus. More generally, we show that the Leaky LWE problem is hard even if the public matrix A is structured and/or hinted and if the non-leaky parts of the secret and error do not follow Gaussian distributions, as long as the corresponding LWE problem without leakage is hard. Our reduction from LWE to Leaky LWE unifies and extends prior results on the Error-Leakage LWE problem [Döttling-Kolonelos-Lai-Lin-Malavolta-Rahimi, EUROCRYPT'23], where L only acts on the error e and the Hint-MLWE problem [Kim-Lee-Seo-Song, CRYPTO'23], where L is restricted to concatenations of random Gaussian scalar matrices not controlled by the distinguisher. Previously, the Hint-MLWE and Error-Leakage LWE assumptions were used as computational replacements of the statistical noise flooding technique in security proofs which led to improved parameters in lattice-based cryptographic constructions such as zero-knowledge proofs, threshold signatures and registration-based encryption. We provide lemmas which abstract out such computational arguments based on Leaky LWE.
The Module Learning With Errors ( M-LWE\text {M-LWE}M-LWE ) problem is a core computational assumption of lattice-based cryptography which offers an interesting trade-off between guaranteed security and concrete efficiency. The problem is parameterized by a secret distribution as well as an error distribution. There is a gap between the choices of those distributions for theoretical hardness results (standard formulation of M-LWE\text {M-LWE}M-LWE , i.e., uniform secret modulo q and Gaussian error) and practical schemes (small bounded secret and error). In this work, we make progress toward narrowing this gap. More precisely, we prove that M-LWE\text {M-LWE}M-LWE with uniform η\eta η -bounded secret for any 1≤η≪q1 \le \eta \ll q1≤η≪q and Gaussian error, in both its search and decision variants, is at least as hard as the standard formulation of M-LWE\text {M-LWE}M-LWE , provided that the module rank d is at least logarithmic in the ring degree n. We also prove that the search version of M-LWE\text {M-LWE}M-LWE with large uniform secret and uniform η\eta η -bounded error is at least as hard as the standard M-LWE\text {M-LWE}M-LWE problem, if the number of samples m is close to the module rank d and with further restrictions on η\eta η . The latter result can be extended to provide the hardness of search M-LWE\text {M-LWE}M-LWE with uniform η\eta η -bounded secret and error under specific parameter conditions. Overall, the results apply to all cyclotomic fields, but most of the intermediate results are proven in more general number fields.
Abstract. In this paper we propose the first provably secure public key encryption scheme based on the Learning with Errors (LWE) problem, in which secrets and errors are sampled uniformly at random from a relatively small set rather than from the commonly used discrete Gaussian distribution. Using a uniform distribution, instead of a Gaussian, has the potential of improving computational efficiency a great deal due to its simplicity, thus making the scheme attractive for use in practice. At the same time our scheme features the strong security guarantee of being based on the hardness of worst-case lattice problems. After presenting the construction of our scheme we prove its security and propose asymptotic parameters. Finally, we compare our scheme on several measures to one of the most efficient LWE-based encryption schemes with Gaussian noise. We show that the expected efficiency improvement is debunked, due to the large blow-up of the parameter sets involved.
Bi-deniable Encryption scheme means that when the sender and the receiver are coerced, the coercer can obtain fake plaintext, random numbers, and secret keys. It’s a solution strategy in the case of information leakage. Compared with traditional encryption, deniable encryption can provide secret communications in situations of coercion in the Post-Quantum era. Compared with sender-deniable encryption and receiver-deniable encryption, bi-deniable encryption can achieve secret communications in the situation that both sender and receiver are coerced by the coercer. So, we propose to design a bi-deniable encryption scheme under the multi-distribution model. In our bi-deniable encryption scheme, we construct a bi-deniable encryption scheme based on the assumption of Decision-Learning With Errors (DLWE) under the multi-distribution model. Firstly, the principle of Inner Product Predicate Encryption (IPPE) is applied in our scheme. Secondly, we apply the framework of Bi-Translucent Set (BTS), combined with inner product predicate encryption. Thirdly, we construct a series of probabilistic polynomial time algorithms, which apply linear transformation between different lattice structures, and Regev dual encryption. Fourthly, the statistical indistinguishability between the sampling algorithm with discrete Gaussian sampling algorithm, and the computational indistinguishability between LWE’s ciphertext samples with uniform samples, the property of indistinguishability is applied in theorem proving, which obtain Indistinguishability under Chosen Plaintext Attacks (IND-CPA) security and the property of bi-deniability. Given the value range of the Gaussian parameter and security parameter in our scheme, the correctness of the bi-deniable encryption scheme is guaranteed. We also give the security proof of IND-CPA and bi-deniability’s property by a series of games. The ‘Inner-Product Bi-Translucent Set’ Bi-Deniable Encryption scheme under the multi-distribution model is based on Decision-LWE assumption, and can avoid quantum-resistant attacks. The bi-deniable encryption scheme is firstly constructed by the inner product with the Decision-LWE assumption, which can provide better properties of security and deniability.