Lune

CRYPTO2021Top-tier venue

Counterexamples to New Circular Security Assumptions Underlying iO

Samuel B. Hopkins, Aayush Jain, Huijia Lin

Abstract

We study several strengthening of classical circular security assumptions which were recently introduced in four new lattice-based constructions of indistinguishability obfuscation: Brakerski-Döttling-Garg-Malavolta (Eurocrypt 2020), Gay-Pass (STOC 2021), Brakerski-Döttling-Garg-Malavolta (Eprint 2020) and Wee-Wichs (Eprint 2020).

We provide explicit counterexamples to the 22-circular shielded randomness leakage assumption w.r.t. the Gentry-Sahai-Waters fully homomorphic encryption scheme proposed by Gay-Pass, and the homomorphic pseudorandom LWE samples conjecture proposed by Wee-Wichs. Our work suggests a separation between classical circular security of the kind underlying un-levelled fully-homomorphic encryption from the strengthened versions underlying recent iO constructions, showing that they are not (yet) on the same footing. Our counterexamples exploit the flexibility to choose specific implementations of circuits, which is explicitly allowed in the Gay-Pass assumption and unspecified in the Wee-Wichs assumption. Their indistinguishabilty obfuscation schemes are still unbroken. Our work shows that the assumptions, at least, need refinement. In particular, generic leakage-resilient circular security assumptions are delicate, and their security is sensitive to the specific structure of the leakages involved.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

2 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices cites Indistinguishability obfuscation from circular security
  • Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices cites Indistinguishability obfuscation from well-founded assumptions
  • Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices cites Candidate Obfuscation via Oblivious LWE Sampling
  • Indistinguishability obfuscation from well-founded assumptions cites Candidate iO from Homomorphic Encryption Schemes
  • Indistinguishability obfuscation from well-founded assumptions cites Indistinguishability Obfuscation Without Maps: Attacks and Fixes for Noisy Linear FE
  • Candidate Obfuscation via Oblivious LWE Sampling cites Indistinguishability obfuscation from circular security
  • Candidate Obfuscation via Oblivious LWE Sampling cites Indistinguishability obfuscation from well-founded assumptions
  • Candidate Obfuscation via Oblivious LWE Sampling cites Candidate iO from Homomorphic Encryption Schemes
  • Candidate Obfuscation via Oblivious LWE Sampling cites Indistinguishability Obfuscation Without Maps: Attacks and Fixes for Noisy Linear FE
  • Watermarking PRFs Against Quantum Adversaries cites Indistinguishability obfuscation from circular security
  • Watermarking PRFs Against Quantum Adversaries cites Candidate Obfuscation via Oblivious LWE Sampling
  • Watermarking PRFs Against Quantum Adversaries cites Indistinguishability Obfuscation Without Maps: Attacks and Fixes for Noisy Linear FE
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Attribute-Based Encryption for Circuits of Unbounded Depth from LatticesYao-Ching Hsieh, Huijia Lin, Ji LuoFOCS 2023 · 38 citations
  2. Watermarking PRFs Against Quantum AdversariesFuyuki Kitagawa, Ryo NishimakiEUROCRYPT 2022 · 9 citations

Builds on6

  1. Indistinguishability obfuscation from well-founded assumptionsAayush Jain, Huijia Lin, Amit SahaiSTOC 2021 · 223 citations
  2. Indistinguishability obfuscation from circular securityRomain Gay, Rafael PassSTOC 2021 · 78 citations
  3. Candidate Obfuscation via Oblivious LWE SamplingHoeteck Wee, Daniel WichsEUROCRYPT 2021 · 78 citations
  4. Candidate iO from Homomorphic Encryption SchemesZvika Brakerski, Nico Döttling, Sanjam Garg, Giulio MalavoltaEUROCRYPT 2020 · 60 citations
  5. Indistinguishability Obfuscation Without Maps: Attacks and Fixes for Noisy Linear FEShweta Agrawal, Alice Pellet-MaryEUROCRYPT 2020 · 51 citations

Related papers

  1. Indistinguishability Obfuscation from LPN over Fp\mathbb {F}_p, DLIN, and PRGs in NC0Aayush Jain, Huijia Lin, Amit SahaiEUROCRYPT 2022 · 102 citations
  2. Lattice-Based Obfuscation from NTRU and Equivocal LWEValerio Cini, Russell W. F. Lai, Ivy K. Y. WooCRYPTO 2025 · 3 citations
  3. Fully Homomorphic Encryption with Chosen-Ciphertext Security from LWERupeng Yang, Zuoxia Yu, Willy SusiloCRYPTO 2025 · 5 citations
  4. Lattice-Based Post-quantum iO from Circular Security with Random Opening AssumptionYao-Ching Hsieh, Aayush Jain, Huijia LinCRYPTO 2025 · 9 citations
  5. Pseudorandom Obfuscation and ApplicationsPedro Branco, Nico Döttling, Abhishek Jain, Giulio Malavolta et al.CRYPTO 2025 · 6 citations
Dusk over the sea between two cliffs drawn in fine vertical lines