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

Candidate Obfuscation via Oblivious LWE Sampling.

Hoeteck Wee, Daniel Wichs

Published Jan 1, 2020• 15 citations
OpenAlex

Abstract

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.

Related papers

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

Thomas Debris-Alazard, Pouria Fallahpour, Damien Stehlé

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.

arXiv:2401.03807•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•13 citations

Factoring and Pairings Are Not Necessary for IO: Circular-Secure LWE Suffices

Zvika Brakerski, Nico Döttling, Sanjam Garg +1 more

We construct indistinguishability obfuscation (iO) solely under circular-security properties of encryption schemes based on the Learning with Errors (LWE) problem. Circular-security assumptions were used before to construct (non-leveled) fully-homomorphic encryption (FHE), but our assumption is stronger and requires circular randomness-leakage-resilience. In contrast with prior works, this assumption can be conjectured to be post-quantum secure; yielding the first provably secure iO construction that is (plausibly) post-quantum secure. Our work follows the high-level outline of the recent work of Gay and Pass [STOC 2021], who showed a way to remove the heuristic step from the homomorphic-encryption based iO approach of Brakerski, Döttling, Garg, and Malavolta [EUROCRYPT 2020]. They thus obtain a construction proved secure under circular security assumption of natural homomorphic encryption schemes - specifically, they use homomorphic encryption schemes based on LWE and DCR, respectively. In this work we show how to remove the DCR assumption and remain with a scheme based on the circular security of LWE alone. Along the way we relax some of the requirements in the Gay-Pass blueprint and thus obtain a scheme that is secure under a different assumption. Specifically, we do not require security in the presence of a key-cycle, but rather only in the presence of a key-randomness cycle. An additional contribution of our work is to point out a problem in one of the building blocks used by many iO candidates, including all existing provable post-quantum candidates. Namely, in the transformation from exponentially-efficient iO (XiO) from Lin, Pass, Seth and Telang [PKC 2016]. We show why their transformation inherently falls short of achieving the desired goal, and then rectify this situation by showing that shallow XiO (i.e. one where the obfuscator is depth-bounded) does translate to iO using LWE.

Leibniz international proceedings in informatics•Jan 1, 2022•30 citations

Indistinguishability Obfuscation of Null Quantum Circuits and Applications

James Bartusek, Giulio Malavolta

We study the notion of indistinguishability obfuscation for null quantum circuits (quantum null-iO). We present a construction assuming: - The quantum hardness of learning with errors (LWE). - Post-quantum indistinguishability obfuscation for classical circuits. - A notion of ''dual-mode'' classical verification of quantum computation (CVQC). We give evidence that our notion of dual-mode CVQC exists by proposing a scheme that is secure assuming LWE in the quantum random oracle model (QROM). Then we show how quantum null-iO enables a series of new cryptographic primitives that, prior to our work, were unknown to exist even making heuristic assumptions. Among others, we obtain the first witness encryption scheme for QMA, the first publicly verifiable non-interactive zero-knowledge (NIZK) scheme for QMA, and the first attribute-based encryption (ABE) scheme for BQP.

arXiv:2106.06094•Leibniz international proceedings in informatics•Jun 11, 2021•18 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

Novel Smooth Hash Proof Systems Based on Lattices

Qiqi Lai, Bo Yang, Yong Hong Yu +2 more

As a basic and important primitive, hash proof system can be used to construct many cryptographic schemes and protocols. Therefore, it is significant to instantiate more efficient hash proof systems from various assumptions. Although there are many hash proof systems based on various classical assumptions, only a handful of efficient hash proof systems are known based on post-quantum assumptions. In this paper, we present several new hash proof systems based on the standard learning with errors (LWE) problem, which is at least as hard as standard worst-case lattice problems. Comparing with other existing constructions based on lattices, our main advantages are 2-fold: much simpler and more efficient. And our constructions can be easily extended to be identity-based ones and updatable ones. Throughout the paper, our main idea is to base hash proof systems on a new subset indistinguishability problem related to LWE, and employ the property of smooth parameter of q-ary orthogonal lattices to ensure smoothness.

The Computer Journal•Dec 6, 2017•5 citations

On the Design and Improvement of Lattice-based Cryptosystems

Rachid El Bansarkhani

Digital signatures and encryption schemes constitute arguably an integral part of cryptographic schemes with the goal to meet the security needs of present and future private and business applications. However, almost all public key cryptosystems applied in practice are put at risk due to its vulnerability to quantum attacks as a result of Shor's quantum algorithm. The magnitude of economic and social impact is tremendous inherently asking for alternatives replacing classical schemes in case large-scale quantum computers are built. Lattice-based cryptography emerged as a powerful candidate attracting lots of attention not only due to its conjectured resistance against quantum attacks, but also because of its unique security guarantee to provide worst-case hardness of average-case instances. Hence, the requirement of imposing further assumptions on the hardness of randomly chosen instances disappears, resulting in more efficient instantiations of cryptographic schemes. The best known lattice attack algorithms run in exponential time. In this thesis we contribute to a smooth transition into a world with practically efficient lattice-based cryptographic schemes. This is indeed accomplished by designing new algorithms and cryptographic schemes as well as improving existing ones. Our contributions are threefold. First, we construct new encryption schemes that fully exploit the error term in LWE instances. To this end, we introduce a novel computational problem that we call Augmented LWE (A-LWE), differing from the original LWE problem only in the way the error term is produced. In fact, we embed arbitrary data into the error term without changing the target distributions. Following this, we prove that A-LWE instances are indistinguishable from LWE samples. This allows to build powerful encryption schemes on top of the A-LWE problem that are simple in its representations and efficient in practice while encrypting huge amounts of data realizing message expansion factors close to 1. This improves, to our knowledge, upon all existing encryption schemes. Due to the versatility of the error term, we further add various security features such as CCA and RCCA security or even plug lattice-based signatures into parts of the error term, thus providing an additional mechanism to authenticate encrypted data. Based on the methodology to embed arbitrary data into the error term while keeping the target distributions, we realize a novel CDT-like discrete Gaussian sampler that beats the best known samplers such as Knuth-Yao or the standard CDT sampler in terms of running time. At run time the table size amounting to 44 elements is constant for every discrete Gaussian parameter and the total space requirements are exactly as large as for the standard CDT sampler. Further results include a very efficient inversion algorithm for ring elements in special classes of cyclotomic rings. In fact, by use of the NTT it is possible to efficiently check for invertibility and deduce a representation of the corresponding unit group. Moreover, we generalize the LWE inversion algorithm for the trapdoor candidate of Micciancio and Peikert from power of two moduli to arbitrary composed integers using a different approach. In the second part of this thesis, we present an efficient trapdoor construction for ideal lattices and an associated description of the GPV signature scheme. Furthermore, we improve the signing step using a different representation of the involved perturbation matrix leading to enhanced memory usage and running times. Subsequently, we introduce an advanced compression algorithm for GPV signatures, which previously suffered from huge signature sizes as a result of the construction or due to the requirement of the security proof. We circumvent this problem by introducing the notion of public and secret randomness for signatures. In particular, we generate the public portion of a signature from a short uniform random seed without violating the previous conditions. This concept is subsequently transferred to the multi-signer setting which increases the efficiency of the compression scheme in presence of multiple signers. Finally in this part, we propose the first lattice-based sequential aggregate signature scheme that enables a group of signers to sequentially generate an aggregate signature of reduced storage size such that the verifier is still able to check that each signer indeed signed a message. This approach is realized based on lattice-based trapdoor functions and has many application areas such as wireless sensor networks. In the final part of this thesis, we extend the theoretical foundations of lattices and propose new representations of lattice problems by use of Cauchy integrals. Considering lattice points as simple poles of some complex functions allows to operate on lattice points via Cauchy integrals and its generalizations. For instance, we can deduce for the one-dimensional and two-dimensional case simple expressions for the number of lattice points inside a domain using trigonometric or elliptic functions.

•Jan 1, 2015•0 citations
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.
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 construct indistinguishability obfuscation (iO) solely under circular-security properties of encryption schemes based on the Learning with Errors (LWE) problem. Circular-security assumptions were used before to construct (non-leveled) fully-homomorphic encryption (FHE), but our assumption is stronger and requires circular randomness-leakage-resilience. In contrast with prior works, this assumption can be conjectured to be post-quantum secure; yielding the first provably secure iO construction that is (plausibly) post-quantum secure. Our work follows the high-level outline of the recent work of Gay and Pass [STOC 2021], who showed a way to remove the heuristic step from the homomorphic-encryption based iO approach of Brakerski, Döttling, Garg, and Malavolta [EUROCRYPT 2020]. They thus obtain a construction proved secure under circular security assumption of natural homomorphic encryption schemes - specifically, they use homomorphic encryption schemes based on LWE and DCR, respectively. In this work we show how to remove the DCR assumption and remain with a scheme based on the circular security of LWE alone. Along the way we relax some of the requirements in the Gay-Pass blueprint and thus obtain a scheme that is secure under a different assumption. Specifically, we do not require security in the presence of a key-cycle, but rather only in the presence of a key-randomness cycle. An additional contribution of our work is to point out a problem in one of the building blocks used by many iO candidates, including all existing provable post-quantum candidates. Namely, in the transformation from exponentially-efficient iO (XiO) from Lin, Pass, Seth and Telang [PKC 2016]. We show why their transformation inherently falls short of achieving the desired goal, and then rectify this situation by showing that shallow XiO (i.e. one where the obfuscator is depth-bounded) does translate to iO using LWE.
We study the notion of indistinguishability obfuscation for null quantum circuits (quantum null-iO). We present a construction assuming: - The quantum hardness of learning with errors (LWE). - Post-quantum indistinguishability obfuscation for classical circuits. - A notion of ''dual-mode'' classical verification of quantum computation (CVQC). We give evidence that our notion of dual-mode CVQC exists by proposing a scheme that is secure assuming LWE in the quantum random oracle model (QROM). Then we show how quantum null-iO enables a series of new cryptographic primitives that, prior to our work, were unknown to exist even making heuristic assumptions. Among others, we obtain the first witness encryption scheme for QMA, the first publicly verifiable non-interactive zero-knowledge (NIZK) scheme for QMA, and the first attribute-based encryption (ABE) scheme for BQP.
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.
As a basic and important primitive, hash proof system can be used to construct many cryptographic schemes and protocols. Therefore, it is significant to instantiate more efficient hash proof systems from various assumptions. Although there are many hash proof systems based on various classical assumptions, only a handful of efficient hash proof systems are known based on post-quantum assumptions. In this paper, we present several new hash proof systems based on the standard learning with errors (LWE) problem, which is at least as hard as standard worst-case lattice problems. Comparing with other existing constructions based on lattices, our main advantages are 2-fold: much simpler and more efficient. And our constructions can be easily extended to be identity-based ones and updatable ones. Throughout the paper, our main idea is to base hash proof systems on a new subset indistinguishability problem related to LWE, and employ the property of smooth parameter of q-ary orthogonal lattices to ensure smoothness.
Digital signatures and encryption schemes constitute arguably an integral part of cryptographic schemes with the goal to meet the security needs of present and future private and business applications. However, almost all public key cryptosystems applied in practice are put at risk due to its vulnerability to quantum attacks as a result of Shor's quantum algorithm. The magnitude of economic and social impact is tremendous inherently asking for alternatives replacing classical schemes in case large-scale quantum computers are built. Lattice-based cryptography emerged as a powerful candidate attracting lots of attention not only due to its conjectured resistance against quantum attacks, but also because of its unique security guarantee to provide worst-case hardness of average-case instances. Hence, the requirement of imposing further assumptions on the hardness of randomly chosen instances disappears, resulting in more efficient instantiations of cryptographic schemes. The best known lattice attack algorithms run in exponential time. In this thesis we contribute to a smooth transition into a world with practically efficient lattice-based cryptographic schemes. This is indeed accomplished by designing new algorithms and cryptographic schemes as well as improving existing ones. Our contributions are threefold. First, we construct new encryption schemes that fully exploit the error term in LWE instances. To this end, we introduce a novel computational problem that we call Augmented LWE (A-LWE), differing from the original LWE problem only in the way the error term is produced. In fact, we embed arbitrary data into the error term without changing the target distributions. Following this, we prove that A-LWE instances are indistinguishable from LWE samples. This allows to build powerful encryption schemes on top of the A-LWE problem that are simple in its representations and efficient in practice while encrypting huge amounts of data realizing message expansion factors close to 1. This improves, to our knowledge, upon all existing encryption schemes. Due to the versatility of the error term, we further add various security features such as CCA and RCCA security or even plug lattice-based signatures into parts of the error term, thus providing an additional mechanism to authenticate encrypted data. Based on the methodology to embed arbitrary data into the error term while keeping the target distributions, we realize a novel CDT-like discrete Gaussian sampler that beats the best known samplers such as Knuth-Yao or the standard CDT sampler in terms of running time. At run time the table size amounting to 44 elements is constant for every discrete Gaussian parameter and the total space requirements are exactly as large as for the standard CDT sampler. Further results include a very efficient inversion algorithm for ring elements in special classes of cyclotomic rings. In fact, by use of the NTT it is possible to efficiently check for invertibility and deduce a representation of the corresponding unit group. Moreover, we generalize the LWE inversion algorithm for the trapdoor candidate of Micciancio and Peikert from power of two moduli to arbitrary composed integers using a different approach. In the second part of this thesis, we present an efficient trapdoor construction for ideal lattices and an associated description of the GPV signature scheme. Furthermore, we improve the signing step using a different representation of the involved perturbation matrix leading to enhanced memory usage and running times. Subsequently, we introduce an advanced compression algorithm for GPV signatures, which previously suffered from huge signature sizes as a result of the construction or due to the requirement of the security proof. We circumvent this problem by introducing the notion of public and secret randomness for signatures. In particular, we generate the public portion of a signature from a short uniform random seed without violating the previous conditions. This concept is subsequently transferred to the multi-signer setting which increases the efficiency of the compression scheme in presence of multiple signers. Finally in this part, we propose the first lattice-based sequential aggregate signature scheme that enables a group of signers to sequentially generate an aggregate signature of reduced storage size such that the verifier is still able to check that each signer indeed signed a message. This approach is realized based on lattice-based trapdoor functions and has many application areas such as wireless sensor networks. In the final part of this thesis, we extend the theoretical foundations of lattices and propose new representations of lattice problems by use of Cauchy integrals. Considering lattice points as simple poles of some complex functions allows to operate on lattice points via Cauchy integrals and its generalizations. For instance, we can deduce for the one-dimensional and two-dimensional case simple expressions for the number of lattice points inside a domain using trigonometric or elliptic functions.