Source-linked AI summary
Indistinguishability Obfuscation from Well-Founded Assumptions
Aayush Jain, Huijia Lin, Amit Sahai
TL;DR
Prior iO constructions relied on assumptions created specifically for iO and faced uncertainty after several were broken. This paper constructs iO from subexponential hardness of SXDH, LWE, LPN over fields, and an NC^0 Boolean PRG, proving subexponentially secure iO for all polynomial-size circuits.
Problem
Earlier iO constructions relied on new assumptions proposed specifically for their security, several of which were broken, leaving uncertainty about iO's security foundation.
Method
The paper leverages LPN over fields and an NC^0 PRG to construct the structured-seed PRG used in an iO construction.
Results
Subexponentially secure indistinguishability obfuscation for all polynomial-size circuits exists under subexponential hardness of four stated assumptions.
Takeaways & Limitations
The construction places iO on assumptions with long histories in complexity, coding, number theory, and cryptography.
Takeaways & Limitations
The theorem requires subexponential security of the four assumptions and sufficiently large polynomial parameters in the security parameter.
Abstract
from arXiv · showhide
In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove: Let $τ\in (0,\infty), δ\in (0,1), ε\in (0,1)$ be arbitrary constants. Assume sub-exponential security of the following assumptions, where $λ$ is a security parameter, and the parameters $\ell,k,n$ below are large enough polynomials in $λ$: - The SXDH assumption on asymmetric bilinear groups of a prime order $p = O(2^λ)$, - The LWE assumption over $\mathbb{Z}_{p}$ with subexponential modulus-to-noise ratio $2^{k^ε}$, where $k$ is the dimension of the LWE secret, - The LPN assumption over $\mathbb{Z}_p$ with polynomially many LPN samples and error rate $1/\ell^δ$, where $\ell$ is the dimension of the LPN secret, - The existence of a Boolean PRG in $\mathsf{NC}^0$ with stretch $n^{1+τ}$, Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists.
1 Introduction
The paper addresses the fragile foundation of prior iO constructions by building iO from subexponential hardness of four well-founded assumptions. Its central innovation uses LPN over fields to construct the structured-seed PRG needed for iO.
- Motivation: Prior iO constructions relied on new assumptions introduced specifically for their security, several of which were later broken by cryptanalysis.The surviving assumptions were based on computational problems different from well-studied problems, creating uncertainty about iO security.
- Main theorem: The paper proves that subexponentially secure indistinguishability obfuscation for all polynomial-size circuits exists.This is the paper's principal theorem-level outcome.
- Main theorem: The construction assumes subexponential security of SXDH, LWE, LPN over fields, and a Boolean PRG in NC^0.The parameters include prime order p = O(2^λ), LWE modulus-to-noise ratio 2^(k^ε), LPN error rate 1/ℓ^δ, and PRG stretch n^(1+τ).
- Assumptions: The assumptions have long research histories and were introduced for basic cryptographic primitives and goals unrelated to iO.The paper uses this history to motivate their characterization as well-founded assumptions.
- Prior framework: Previous work reduced iO to LWE, SXDH, an NC^0 PRG, and a structured-seed PRG with polynomial stretch and special efficiency properties.The structured-seed PRG exposes a public seed while requiring degree-2 computation in the private seed.
- Our ideas: The key innovation is leveraging LPN over fields to build the structured-seed PRG from an ordinary NC^0 PRG.The construction uses sparse LPN errors and preprocessing to correct erroneous outputs while preserving the required computation structure.
2 Preliminaries
The preliminaries define the indistinguishability framework, iO, and LPN over large fields, while introducing notation and a leakage-simulation theorem used in the security proofs.
- Polynomial representations: The paper represents NC^0 PRGs by constant-degree multilinear or field polynomials because each output depends on only a constant number of input bits.For degree d, the conversion process takes O(nd) time, hence polynomial time in the NC^0 setting.
- Security notions: The paper defines indistinguishability through computational bounds T and distinguishing advantage γ, including subexponential security for T(λ) = 2^(λ^c).The definitions distinguish ordinary, subexponential, and negligible-advantage indistinguishability.
- Indistinguishability obfuscation: An indistinguishability obfuscator is a uniform PPT algorithm that preserves indistinguishability between same-size, functionally equivalent polynomial-size circuits.The definition also includes completeness.
- LPN over fields: LPN over fields uses a distribution that outputs zero with probability 1 − r and a random field element with probability r.The paper sets ℓ as a sufficiently large polynomial, r = ℓ^−δ, and the sample count n = ℓ^c for c > 1.
- Proof tool: The leakage lemma replaces a distribution (X, W) with (X, h(X, U)) so that leakage circuits of size s cannot distinguish them beyond ε.The simulator h has size s′ = O(s^2ℓ^(ε−2)).
3 Definition of Structured-Seed PRG
A structured-seed PRG separates public and private seed components and evaluates its output with controlled complexity in the public seed and degree in the private seed.
- Syntax: An sPRG samples an index, jointly generates public and private seeds, and evaluates them to produce an m-bit output.The combined seed length is n · poly(λ), and Eval(I, sd) outputs a string in {0, 1}^m.
- Stretch: An sPRG has polynomial stretch when its stretch parameter satisfies τ > 1, while the seed length may include a fixed polynomial factor in λ.The parameter n is viewed as an arbitrarily large polynomial in λ, so the sPRG expands in length.
- Security: The sPRG security condition requires its output distributions to be (T(λ), γ(λ))-pseudorandom.The security definition is expressed through computational indistinguishability.
- Complexity and degree: An sPRG has complexity C in the public seed and degree d in the private seed when its processing algorithm lies in C and its output is represented by degree-d polynomials in the private seed.The polynomial coefficients are generated from the public seed by the specified processing algorithm.
- Relation to standard PRGs: The definition generalizes standard PRGs by allowing a public and private seed and a nonuniform seed distribution.The standard uniform-seed PRG is recovered when the public seed is empty and the private seed is uniform.
4 Construction of Structured Seed PRG
The construction builds a structured-seed PRG whose evaluation has degree 2 in the private seed while preserving polynomial stretch and pseudorandomness under LPN and an NC^0 PRG assumption. It resolves sparse LPN errors by compressing and obliviously expanding corrections, with security established through hybrid arguments.
- Security and parameters: The resulting sPRG has polynomial stretch, degree 2 in the private seed, and constant public-seed degree, and is pseudorandom under the LPN and PRG assumptions.The construction is subexponentially pseudorandom when both assumptions resist 2^λ^ν-time adversaries.
- Construction overview: The sPRG evaluates an NC^0 PRG on an LPN-hidden seed while restricting private-seed degree to 2 and public-seed computation to constant degree.The preprocessing converts the PRG seed into public and private components using LPN samples over Z_p.
- Error correction: Sparse LPN noise creates only a small set of bad outputs because the PRG evaluation has constant locality.The construction bounds the number of bad outputs by T = mr log n and zeroizes the output when this bound is exceeded.
- Error correction: Storing the full correction vector would destroy expansion, while correcting only bad outputs would reveal LPN-noise locations and jeopardize security.These two failed approaches expose the tension between expansion and security.
- Error correction: The final construction compresses the correction vector and expands it obliviously by randomly assigning bad outputs to buckets.This avoids depending on the locations of bad outputs while retaining degree-2 private-seed computation.
- Security and parameters: Security follows through hybrids combining LPN hiding, PRG pseudorandomness, and simulation of the one-bit flag leakage.The hybrid sequence bounds the distinguishing advantage and concludes the proposition by contradiction.
5 Bootstrapping to Indistinguishability Obfuscation
The section bootstraps weak functional encryption into public-key, collusion-resistant functional encryption for polynomial-size circuits, then transforms it into indistinguishability obfuscation. The construction derives perturbation-resilient generators from structured-seed PRGs and combines them with SXDH, LWE, and NC^0 PRG assumptions.
- From perturbation-resilient generators to weak FE for NC^0: Perturbation-resilient generators, SXDH, LWE, and NC^0 PRGs yield weak secret-key FE for NC^0 circuits with one-key security and sublinear ciphertexts.The ciphertext size is linear in input length and sublinear in circuit size.
- Bootstrapping FE: Known transformations lift weak FE for NC^0 to full FE for polynomial-size circuits, strengthen security, and convert secret-key FE into public-key FE.The resulting public-key scheme becomes adaptively collusion resistant, while encryption time becomes polynomial in the security parameter and input length.
- FE to IO transformation: The FE-to-iO transformation converts public-key FE with weakly selective subexponential security and sublinear encryption time into subexponentially secure iO.The transformation applies to polynomial-size circuits.
- Main result: Under subexponential hardness of LWE, SXDH, and an NC^0 Boolean PRG, subexponentially secure indistinguishability obfuscation for all polynomial-size circuits exists.The theorem also states that polynomial security suffices for collusion-resistant, adaptive, compact public-key FE for all circuits.
- From structured-seed PRG to perturbation-resilient generator: A structured-seed PRG yields a perturbation-resilient generator with slightly reduced stretch and security loss 2γ + O(1/λ).The generator outputs remain indistinguishable under addition of adversarially chosen small integer perturbations.
A Partially Hiding Functional Encryption
The section defines partially hiding functional encryption through algorithms for public-parameter generation, setup, encryption, key generation, and decryption. It specifies correctness and simulation or indistinguishability security, with ordinary functional encryption as a special case.
- Concept and scope: PHFE associates secret keys with binary functions f(x,y), revealing f(x,y), x, and f while hiding the private input y.Functional encryption is obtained when there is no public input.
- Parameters: The functionality and message spaces are indexed by security parameter λ and length parameter n.The maximum function size and ciphertext sizes are defined relative to these parameters.
- Syntax: A PHFE scheme consists of PPGen, Setup, Enc, KeyGen, and Dec algorithms running in polynomial time.Encryption outputs a ciphertext together with the public input x; decryption returns a value in Z or ⊥.
- Correctness: Correctness requires every honestly generated ciphertext and function key to decrypt to the prescribed function value for all valid inputs.The definition quantifies over every security parameter, length polynomial, input pair, and function.
- Security: Simulation security compares real encryptions and keys against a simulator given only the permitted function outputs, while IND security compares encryptions of two messages.Both definitions support weakly selective security with bounded ciphertext and key queries.
B Recap of constant-depth functional encryption
The construction builds one-key secret-key FE for NC^0 functions from LWE-based homomorphic encryption, perturbation-resilient generators, and PHFE from SXDH. It achieves sublinear ciphertext growth in circuit size while retaining linear dependence on input length.
- Function representation: NC^0 functions are represented by constant-degree multilinear polynomials with coefficients in {1,-1}, enabling arithmetic evaluation of their outputs.The construction evaluates a polynomial G with constant complexity and degree two in the private seed.
- LWE ingredient: LWE encryption of Boolean strings has the form (A, b = sA + 2e + x) over Z_p and supports homomorphic evaluation of constant-degree polynomials.The modulus-to-noise ratio is chosen within the subexponential LWE regime.
- Perturbation-resilient generator: A perturbation-resilient generator supplies public and private seeds and produces polynomial-magnitude integer outputs that tolerate bounded perturbations.Its seed length is n·poly(λ, log B), and its output lies in a polynomially bounded integer range.
- PHFE integration: PHFE based on SXDH hides the private input while allowing evaluation of the constructed arithmetic function using public and private inputs.The decryption procedure recovers a noisy function value and then reveals its value modulo 2.
- Compactness: The ciphertext size is poly(λ,l)m^(1−ε), giving sublinear dependence on the NC^0 output or circuit size and linear dependence on input length.This follows from the linear efficiency of PHFE and the generator seed length m^(1/τ).