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

arXiv:2401.03807 · ACM Symposium on Theory of Computing (STOC)

Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs

Thomas Debris-Alazard, Pouria Fallahpour, Damien Stehlé

Published Jun 10, 2024• 13 citations
arXivHTMLPDF

Abstract

The Learning With Errors (LWE) problem asks to find ‍s from an input of the form (A, b = As+e) ∈ (ℤ/qℤ)m × n × (ℤ/qℤ)m, for a vector ‍e that has small-magnitude entries. In this work, we do not focus on solving ‍LWE but on the task of sampling instances. As these are extremely sparse in their range, it may seem plausible that the only way to proceed is to first create ‍s and ‍e and then set ‍b = As+e. In particular, such an instance sampler knows the solution. This raises the question whether it is possible to obliviously sample (A, As+e), namely, without knowing the underlying ‍s. A variant of the assumption that oblivious ‍LWE sampling is hard has been used in a series of works to analyze the security of candidate constructions of Succinct Non-interactive Arguments of Knowledge (SNARKs). As the assumption is related to ‍LWE, these SNARKs have been conjectured to be secure in the presence of quantum adversaries.

DOI
10.1145/3618260.3649766

Related papers

Candidate Obfuscation via Oblivious LWE Sampling.

Hoeteck Wee, Daniel Wichs

We present a new, simple candidate construction of indistinguishability obfuscation (iO). Our scheme is inspired by lattices and learning-with-errors (LWE) techniques, but we are unable to prove security under a standard assumption. Instead, we formulate a new falsifiable assumption under which the scheme is secure. Furthermore, the scheme plausibly achieves post-quantum security.

•Jan 1, 2020•15 citations

Verifiable quantum advantage in extremely low depth

Alexandru Gheorghiu

We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., $\mathsf{QNC}^0[\log\log]$ circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., $\mathsf{QAC}^0$ circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. (2025) to very low depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption used by Arabadjieva et al. (2025), we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.

quant-pharXiv:2609.01448•Sep 2, 2026•3 citations

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•5 citations

Learning with Correlated Errors: A New Lattice Hard Problem with Worst-Case Reductions and Public-Key Encryption

Kishore K

We introduce Learning with Correlated Errors (LCE), a new lattice-based computationalhardness assumption in which observed samples carry noise generated by a low-rank linearcorrelation structure. Formally, given samples (A, b = As + Ce0 + e1 mod q), whereC ∈ Zm×rq is a publicly known correlation matrix and e0, e1 are short Gaussian vectors, thetask is to recover the secret s.Unlike LWE, the noise in LCE is globally correlated: up to r independent root noise sourcesdrive m observations simultaneously. Unlike the recent hybrid sparse-small assumptions ofGhosal et al. [GJL+25], LCE preserves a lattice structure that enables a reduction from theLearning with Errors (LWE) problem, thereby inheriting its worst-case hardness guarantees.We prove: (1) Worst-case hardness via reduction: We give a polynomial-timereduction from Decision-LWE to Decision-LCE, establishing that LCE is at least as hardas LWE and thereby inheriting its worst-case lattice hardness guarantees. (2) Search-to-Decision reduction: Search-LCE and Decision-LCE are polynomial-time equivalent (viaan explicit n-hybrid argument). (3) Cryptographic construction: an IND-CPA-securepublic-key encryption scheme from Decision-LCE. (4) Quantum resistance: by composingour reduction with Regev’s quantum reduction, we show that LCE resists known quantumattacks, with quantum lattice sieving requiring an estimated 20.265n quantum gates (matchingthe estimated cost for standard LWE).LCE provides a new, independently motivated hardness foundation for post-quantumcryptography and adds meaningful assumption diversity beyond LWE and LPN.

•Mar 11, 2026•0 citations

A Note on Obfuscation-Based Attacks on Private-Coin Evasive LWE

Tzu-Hsiang Huang, Wei-Hsiang Hung, Shota Yamada

The evasive learning with errors (evasive LWE) assumption is a new assumption recently introduced by Wee [Wee22] and Tsabary [Tsa22] independently, as a significant strengthening of the standard LWE assumption. While the assumption is known to imply various strong primitives including witness encryption [Tsa22, VWW22], the assumption in the most general case (i.e., the private coin variant) is considered quite implausible due to the obfuscation based attack mentioned in [Wee22]. This obfuscation based attack is then later formalized by Vaikuntanathan, Wee, and Wichs [VWW22]. In this note, we revisit their attack and show that the attack actually does not work by showing a concrete counterexample. While various attacks against private-coin evasive LWE are now known, the attack of [VWW22] is the only one that applies in the setting where the sampler is oblivious to the LWE secret, which we call the S-oblivious regime. Therefore, our refutation closes the only known avenue for attacking the assumption in the S-oblivious regime. To complement the above refutation of this attack, we also present a variant of the counterexample assuming the existence of instance-hiding witness encryption. However, our sampler is not S-oblivious, and thus we do not fully recover the attack considered in [VWW22]. Taken together, these results indicate that the security of private-coin evasive LWE in the S-oblivious regime remains open.

IACR Communications in Cryptology•Jan 8, 2026•3 citations

Augmented Learning with Errors: The Untapped Potential of the Error Term.

Rachid El Bansarkhani, Özgür Dagdelen, Johannes A Buchmann

Abstract. The Learning with Errors (LWE) problem has gained a lot of attention in recent years leading to a series of new cryptographic applications. Specifically, it states that it is hard to distinguish random linear equations disguised by some small error from truly random ones. Interestingly, cryptographic primitives based on LWE often do not exploit the full potential of the error term beside of its importance for security. To this end, we introduce a novel LWE-close assumption, namely Augmented Learning with Errors (A-LWE), which allows to hide auxiliary data injected into the error term by a technique that we call message embedding. In particular, it enables existing cryptosystems to strongly increase the message throughput per ciphertext. We show that A-LWE is for certain instantiations at least as hard as the LWE problem. This inherently leads to new cryptographic constructions providing high data load encryption and customized security properties as required, for instance, in economic environments such as stock markets resp. for financial transactions. The security of those constructions basically stems from the hardness to solve the A-LWE problem. As an application we introduce (among others) the first lattice-based replayable chosen-ciphertext secure encryption scheme from A-LWE.

•Jan 1, 2014•1 citation
The Learning With Errors (LWE) problem asks to find ‍s from an input of the form (A, b = As+e) ∈ (ℤ/qℤ)m × n × (ℤ/qℤ)m, for a vector ‍e that has small-magnitude entries. In this work, we do not focus on solving ‍LWE but on the task of sampling instances. As these are extremely sparse in their range, it may seem plausible that the only way to proceed is to first create ‍s and ‍e and then set ‍b = As+e. In particular, such an instance sampler knows the solution. This raises the question whether it is possible to obliviously sample (A, As+e), namely, without knowing the underlying ‍s. A variant of the assumption that oblivious ‍LWE sampling is hard has been used in a series of works to analyze the security of candidate constructions of Succinct Non-interactive Arguments of Knowledge (SNARKs). As the assumption is related to ‍LWE, these SNARKs have been conjectured to be secure in the presence of quantum adversaries.
We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., QNC0[log⁡log⁡]\mathsf{QNC}^0[\log\log]QNC0[loglog] circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., QAC0\mathsf{QAC}^0QAC0 circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. (2025) to very low depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption used by Arabadjieva et al. (2025), we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
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.
We introduce Learning with Correlated Errors (LCE), a new lattice-based computationalhardness assumption in which observed samples carry noise generated by a low-rank linearcorrelation structure. Formally, given samples (A, b = As + Ce0 + e1 mod q), whereC ∈ Zm×rq is a publicly known correlation matrix and e0, e1 are short Gaussian vectors, thetask is to recover the secret s.Unlike LWE, the noise in LCE is globally correlated: up to r independent root noise sourcesdrive m observations simultaneously. Unlike the recent hybrid sparse-small assumptions ofGhosal et al. [GJL+25], LCE preserves a lattice structure that enables a reduction from theLearning with Errors (LWE) problem, thereby inheriting its worst-case hardness guarantees.We prove: (1) Worst-case hardness via reduction: We give a polynomial-timereduction from Decision-LWE to Decision-LCE, establishing that LCE is at least as hardas LWE and thereby inheriting its worst-case lattice hardness guarantees. (2) Search-to-Decision reduction: Search-LCE and Decision-LCE are polynomial-time equivalent (viaan explicit n-hybrid argument). (3) Cryptographic construction: an IND-CPA-securepublic-key encryption scheme from Decision-LCE. (4) Quantum resistance: by composingour reduction with Regev’s quantum reduction, we show that LCE resists known quantumattacks, with quantum lattice sieving requiring an estimated 20.265n quantum gates (matchingthe estimated cost for standard LWE).LCE provides a new, independently motivated hardness foundation for post-quantumcryptography and adds meaningful assumption diversity beyond LWE and LPN.
The evasive learning with errors (evasive LWE) assumption is a new assumption recently introduced by Wee [Wee22] and Tsabary [Tsa22] independently, as a significant strengthening of the standard LWE assumption. While the assumption is known to imply various strong primitives including witness encryption [Tsa22, VWW22], the assumption in the most general case (i.e., the private coin variant) is considered quite implausible due to the obfuscation based attack mentioned in [Wee22]. This obfuscation based attack is then later formalized by Vaikuntanathan, Wee, and Wichs [VWW22]. In this note, we revisit their attack and show that the attack actually does not work by showing a concrete counterexample. While various attacks against private-coin evasive LWE are now known, the attack of [VWW22] is the only one that applies in the setting where the sampler is oblivious to the LWE secret, which we call the S-oblivious regime. Therefore, our refutation closes the only known avenue for attacking the assumption in the S-oblivious regime. To complement the above refutation of this attack, we also present a variant of the counterexample assuming the existence of instance-hiding witness encryption. However, our sampler is not S-oblivious, and thus we do not fully recover the attack considered in [VWW22]. Taken together, these results indicate that the security of private-coin evasive LWE in the S-oblivious regime remains open.
Abstract. The Learning with Errors (LWE) problem has gained a lot of attention in recent years leading to a series of new cryptographic applications. Specifically, it states that it is hard to distinguish random linear equations disguised by some small error from truly random ones. Interestingly, cryptographic primitives based on LWE often do not exploit the full potential of the error term beside of its importance for security. To this end, we introduce a novel LWE-close assumption, namely Augmented Learning with Errors (A-LWE), which allows to hide auxiliary data injected into the error term by a technique that we call message embedding. In particular, it enables existing cryptosystems to strongly increase the message throughput per ciphertext. We show that A-LWE is for certain instantiations at least as hard as the LWE problem. This inherently leads to new cryptographic constructions providing high data load encryption and customized security properties as required, for instance, in economic environments such as stock markets resp. for financial transactions. The security of those constructions basically stems from the hardness to solve the A-LWE problem. As an application we introduce (among others) the first lattice-based replayable chosen-ciphertext secure encryption scheme from A-LWE.