PaperlayerView exact revision on arXiv

Source-linked AI summary

Witness Encryption via Prime-Order Generic Groups

Isaac M Hair, Amit Sahai

arXiv:2609.18275v2cs.CR

TL;DR

Existing witness-encryption schemes were not known to be unconditionally secure in the prime-order generic-group model or related plausible algebraic ideal models. This paper constructs witness encryption in that model, establishes correctness and false-statement security guarantees, and proves a first superconstant-factor hardness result for homogeneous MinRank.

  • Problem

    Existing witness-encryption schemes were not known to be unconditionally secure in the prime-order generic-group model or related plausible algebraic ideal models.

    Source: §1 · p. 1

  • Method

    The paper constructs witness encryption for NP in the classical prime-order generic-group model, where group operations are accessed through an oracle and there are no pairing or multilinear operations.

    Source: §1 · p. 1, §1.1 · p. 2

  • Results

    Theorem 1.1 gives witness-correctness and false-statement distinguishing-advantage guarantees against classical adversaries making the specified number of group-oracle queries.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    The construction also yields the first superconstant-factor NP-hardness of approximation result for bounded-factor MinRank, including standard homogeneous MinRank.

    Source: §1.1 · p. 2

    Concrete instantiations require an additional assumption of false-statement security against classical nonuniform probabilistic polynomial-time adversaries, and the stated definitions omit corruption of honestly generated keys.

    Source: §1.2 · p. 3

Abstract

from arXiv · show

For every constant $c > 0$, we unconditionally construct witness encryption for NP in the classical generic cyclic group model with the following properties. For SAT instances of size $n$, encryption runs in time poly$(n)$, and any satisfying assignment can be used to decrypt in poly$(n)$ time with correctness error $2^{-n}$. If no satisfying assignment exists, every generic adversary making at most $n^{(\log n)^c}$ group queries has distinguishing advantage at most $n^{-(\log n)^c}$. Along the way, we give the first superconstant-factor NP-hardness of approximation result for homogeneous MinRank under randomized polynomial-time reductions. We obtain a gap of $(\log n)^c$ for any prescribed constant $c>0$, even when YES instances are required to have a rank-one matrix of the form $\mathbf u\mathbf v^T$ where $\mathbf v$ is a 0/1 vector. The main results of this paper were discovered by Codex / ChatGPT 6 Astra Ultra using harness components from the UCLA Moonshot Harness Project, in response to a general strategy for witness encryption suggested by the authors. See the end of the introduction for a discussion.

1 Introduction

The paper constructs witness encryption in the classical prime-order generic-group model and connects its security to a new MinRank hardness gap. It also derives cryptographic applications and situates the construction among prior witness-encryption and MinRank approaches.

1.3 Witness Encryption and Ideal Groups

  • Prior witness-encryption candidates exist, but the supplied discussion says none were known to be unconditionally secure in the prime-order generic-group model; the earlier generic-group route relied on an unproven minimum-distance hardness conjecture.The paper’s security proof follows a random-encoding approach to generic-group lower bounds.Source: §1 · p. 1, §1.3 · pp. 4–5

1 Introduction

  • The construction uses a matrix space where witnesses identify rank-one matrices with small integer right factors, while false statements force every nonzero matrix to have high rank.The rank-one structure supports polynomial-time decryption; high rank makes algebraic equalities testable by generic adversaries unlikely.Source: §1 · p. 1

1.1 Our Results

  • Valid witnesses decrypt correctly with probability at least 1 − 2^-n, while false statements resist classical generic adversaries making at most n^(log n)^c queries with advantage at most n^−(log n)^c.The construction runs in polynomial time for every fixed c > 0.Source: §1.1 · p. 2
  • For every fixed c > 0, randomized polynomial-time reductions establish a (log m)^c MinRank gap with rank-one YES matrices uvT whose right factor v is Boolean.In NO instances, every nonzero matrix has rank at least (log m)^c.Source: §1.1 · p. 2

1.2 Cryptographic Implications

  • In the classical prime-order generic-group model, the paper derives small-key IND-CPA public-key encryption assuming one-way functions, adaptive key-policy ABE assuming LWE, and flexible broadcast encryption and registered ABE assuming LWE.It also gives policy-selectively secure registered ABE for polynomial-size circuit policies.Source: §1.2 · p. 3
  • Under additional concrete-instantiation security and LWE assumptions, the paper obtains standard-model indexed positional witness encryption, broadcast-and-trace, and noninteractive batch arguments for NP.For the first two schemes, ciphertext length is N^ε poly(λ, |C|, |µ|, log N) or N^ε poly(λ, |µ|, log N), respectively; the recipient set is excluded from the latter bound.Source: §1.2 · pp. 3–4

1.4 MinRank and Coding-Theoretic Hardness

  • The MinRank construction modifies a moment-matrix approach with weights, obtaining logarithmic-power rank gaps at polynomial output size, including over growing prime fields.The cited prior construction already used bounded-degree assignment-bit products and Boolean rank-one factors; the new weights aim to grow the gap without increasing assignment degree with input size.Source: §1.4 · p. 5

2 Preliminaries

The preliminaries define witness encryption and specify the paper’s prime-order generic-group setting. They also explain how the NP relation is represented as a SAT circuit for the construction.

2 Preliminaries

  • Witness encryption requires correctness for valid witnesses and indistinguishability on false statements, with no security requirement on true statements.The definition takes a polynomial-time decidable, polynomially balanced relation and ciphertexts for a bit message.Source: §2 · pp. 6–7
  • It suffices to construct witness encryption for Boolean circuit SAT: an NP verifier can be compiled into a circuit while preserving witnesses, and padding sets the effective size to n = max{2, λ, |φ|}.For a fixed NP relation, the circuit size is polynomial in the original statement and witness bounds.Source: §2 · p. 7
  • The generic-group oracle returns encodings for group addition or subtraction, but cannot multiply two encoded group elements; adversaries may use unbounded local computation, with oracle calls charged to their query budget.The encoding is fresh and random, and advice may depend on the statement but not on the encoding or hidden encryption coins.Source: §2 · p. 7

3 Witness Encryption

Section 3 derives witness encryption from a bounded-factor MinRank reduction: satisfying assignments yield matrix factors, while unsatisfiability enforces a rank lower bound. Under the stated rank-growth conditions, the scheme achieves exponentially small correctness error and quantitative security against classical generic adversaries.

3 Witness Encryption

  • 2^-n correctness error and n^-R/8 distinguishing advantage hold against classical generic adversaries making at most n^R/8 queries, when R→∞ and R log n=o(m).The guarantee applies to false statements.Source: §3 · p. 8, §3.3 · p. 11

3.1 Parameters and Algorithms

  • The reduction supplies a public matrix-space basis, while a satisfying assignment gives factors used in decryption to test membership in a short list of scalar multiples.The basis need not be included in the ciphertext.Source: §3.1 · pp. 8–9
  • Bounded sampling has failure probability at most 2^-n-2, and conditioned on success the sampled distributions are exact.Source: §3.1 · p. 9

3.2 Correctness

  • For zero ciphertexts, Booleanity ensures the tested list contains Z; for one ciphertexts, the probability that Z enters the list is at most (B + 1)/p.The proof combines this bound with sampling failure to establish correctness.Source: §3.2 · p. 9

3.3 Adaptive Generic Security

  • A symbolic simulator fixes the adversary’s adaptive forms and bounds collisions, coupling the real experiments even when decisions depend on label bit patterns.The proof bounds collisions between distinct affine forms on the fixed symbolic list.Source: §3.3 · pp. 10–11
  • For arbitrary-string inputs, rejecting unassigned operands and charging guessed valid encodings adds O(Q/p); invalid-input handling supplies no free validity oracle.The abort outcome has equal probability for both messages and contributes no distinguishing advantage.Source: §3.3 · p. 11

4 Warm-Up: A Logarithmic Gap for Bounded-Factor MinRank

This warm-up part gives a polynomial-time construction reducing SAT to bounded-factor MinRank, with satisfying assignments yielding rank-one matrices with Boolean right factors and nonzero low-rank solutions implying satisfiability. It describes an iterative way to compute the constructed space and establishes a NO-case rank bound of Ω(log m).

4 Warm-Up: A Logarithmic Gap for Bounded-Factor MinRank

  • YES instances yield a rank-one matrix with a Boolean right factor, while NO instances have no nonzero matrix below rank Ω(log m).For a SAT instance φ, the reduction constructs a matrix space in polynomial time with m = poly(|φ|); a satisfying assignment efficiently gives the rank-one witness, and unsatisfiability forces rank at least a fixed positive constant times log m.Source: §4 · p. 11, §4.4 · p. 16

4.1 Starting Point: A Table That Contains One Assignment

  • An assignment's pairwise-product table is nonzero, symmetric, and rank one, and its linear tests encode the quadratic equations.Conversely, the conditions Mii = M0i on a nonzero symmetric rank-one table force it to encode Boolean bits; if every equation test vanishes, those bits satisfy the input system.Source: §4.1 · p. 12

4.2 Cancellation and Selectors

  • Equation failures can cancel in linear combinations, so isolating every Boolean assignment would require 2^N selectors.Ideal selectors would make each weighted equation test isolate one assignment and prevent cancellation, but their exponential count motivates using rank to reduce the needed collection.Source: §4.2 · p. 13

4.3 Stacking the Weighted Tables

  • Stacking one table per weight preserves a shared assignment coefficient across blocks, while column relations can yield replacement rules within weighted sums.A satisfying assignment gives a nonzero rank-one matrix passing every block constraint; a matrix of rank ρ needs only ρ columns to express the others.Source: §4.3 · pp. 13–14

4.4 Choosing Weights That Work for Every Possible Column Space

  • Weights built from R linear combinations are chosen in advance so that one list spans the column space of any matrix of rank at most R.A spanning-combinations lemma guarantees a suitable sampled list; the construction uses degree-at-most-R polynomials in the combinations as weights.Source: §4.4 · pp. 14–15

4.5 Soundness: A Nonzero Low-Rank Matrix Yields a Solution

  • For a hypothetical nonzero NO-case matrix of rank at most R, the soundness argument selects a sample where the combinations span its column space and a weight block remains nonzero.It combines the spanning determinant with a polynomial for a nonzero block; their product has degree at most 2D and therefore cannot vanish at all 2D + 1 sample values.Source: §4.5 · p. 17
  • A nonzero matrix of rank ρ ≤ R forces all selector-weighted sums to vanish, contradicting the existence of a nonzero block and proving the soundness rank lower bound.The selector argument reduces the sums to 2^ρ Boolean-cube weights; it does not claim the original coefficients have small support.Source: §4.5 · pp. 19–20
  • A satisfying assignment can be recovered by enumerating 2^ρ candidates from a column basis of any nonzero matrix of rank ρ ≤ R and testing each candidate.At least one candidate is Boolean and satisfies the input equations; constructing the candidate list requires only the column basis.Source: §4.5 · p. 20

4.6 Computing the Space Without Listing All Assignments

  • The space is computed by updating a basis under both choices for each bit and retaining a basis after every step, so the algorithm avoids listing all assignments.Each transition and elimination uses polynomially many field operations; the constraint intersection and coordinate recovery also take polynomial time.Source: §4.6 · p. 21
  • R + 1 = Ω(log m) is the NO-case rank bound, with R = floor(log N), m = O(N^4 log N), and any prime p ≥ 2m satisfying the construction’s condition.These parameter choices establish the stated bound in Theorem 4.1.Source: §4.6 · p. 22

5 A Larger Gap for Bounded-Factor MinRank

The section develops a deterministic MinRank reduction with a logarithmic rank gap, where satisfying witnesses yield rank-one matrices with Boolean right factors and unsatisfiable instances have no nonzero matrix below the gap. Its final parameter choice gives a polynomial-time construction with NO-case rank bound $R \ge (\log m)^c$.

5 A Larger Gap for Bounded-Factor MinRank

  • For every constant c > 0, the reduction maps a SAT instance to a space whose nonzero matrices have rank at least (log m)^c if unsatisfiable, while satisfying witnesses yield rank-one matrices with a Boolean right factor.The matrix order m is polynomial in the SAT instance size; for any supplied prime p ≥ 2m, the reduction and witness conversion run in time polynomial in |φ| and log p, with an exponent that may depend on c.Source: §5 · p. 22, §5.1 · p. 22

5.1 Keeping More Products in Each Assignment Table

  • Keeping products of up to 2d bits in each assignment table and multiplying equations by up to 2d −2 bits preserves polynomial size for fixed d and supports a growing rank gap.Higher-degree Boolean assignment monomials in rank-one moment matrices also appear in Guruswami, Ren, and Tang; here fixed assignment degree is combined with weights to obtain the growing gap.Source: §5.1 · pp. 22–23

5.2 A Rank Bound from One-Bit Selectors

  • One-bit selectors split a rectangular Boolean table into smaller tables whose ranks add, yielding a rank bound that can produce any fixed logarithmic power with suitable fixed d.The lemma assumes the quadratic equations have no common Boolean zero and that the required equation and Boolean identities hold after multiplication by polynomials of the allowed degree.Source: §5.2 · pp. 23–24

5.3 Choosing the Weights

  • The weight construction preserves relations among collections of columns by using up to R² geometric forms, with extra relations needed after multiplication by up to d −1 bits.The weight count reflects the dimension bound for preserving these relations.Source: §5.3 · pp. 24–25

5.4 A Nonzero Low-Rank Matrix Gives a Contradiction

  • A nonzero low-rank matrix would yield a nonzero larger Boolean moment table whose rank is no greater, contradicting the rank bound for unsatisfiable equations.The larger table is used only in the soundness proof; the reduction does not construct it.Source: §5.4 · pp. 25, 27, 28

5.5 Computing the Space and Choosing the Gap

  • A deterministic basis algorithm computes the space and intersects it with the linear tests, while a satisfying assignment supplies the rank-one factors and a linear solve gives their basis coordinates.The described operations take time polynomial in N, J, m, and log p.Source: §5.5 · p. 28
  • Choosing d > 2c and padding by an amount depending only on c gives a polynomial-time construction with NO-case rank bound R ≥ (log m)^c, while m is computable before the prime is supplied.The NO-case rank bound is that of Theorem 5.1; the YES-case factor and witness conversion were established earlier.Source: §5.5 · p. 28

6 Putting It All Together

The paper chooses a prime and combines the MinRank reduction with the witness-encryption construction to obtain the stated security and correctness bounds. It then applies witness encryption in the generic-group model to several cryptographic constructions and gives a standard-model consequence under an additional group assumption.

Witness Encryption

  • The construction achieves distinguishing advantage at most n^-(log n)^c against adversaries making at most n^(log n)^c group queries, with correctness error at most 2^-n.Prime-sampling failure is at most 2^-n-2; the sampler tests polynomially many candidates in [2m, 2m+1).Source: §6 · p. 29

Randomized MinRank Hardness

  • The randomized reduction preserves NO instances and maps YES instances to YES instances except with probability at most 2^-n-2.On successful prime sampling, the YES and NO cases are those of the introductory theorem; forgetting the Boolean factor condition gives the same gap for homogeneous MinRank.Source: §6 · pp. 29–30

The Cryptographic Applications

  • Independent witness encryptions, fresh group contexts, a union bound, and bitwise hybrids extend the construction to encrypt polynomially many bits.The simulation argument lets reductions lazily assign random encodings to independent contexts and forward the challenge context when needed.Source: §6 · p. 30
  • The one-way-function construction of Garg et al. gives public-key encryption by encrypting under the statement that a published string lies in the generator's image.A uniform string lies in that image with probability at most 2^-λ, enabling the false-statement hybrid.Source: §6 · p. 30
  • The cited LWE-based constructions yield adaptive security and negligible correctness error, plus semi-static flexible broadcast encryption and policy-selective registered ABE under stated key-corruption restrictions.The latter constructions require ordinary, group-free auxiliary primitives inside their hash-function circuits and NP relations.Source: §6 · p. 30
  • Global correctness with negligible error supports null obfuscation and, through cutoff obfuscation, indexed witness-encryption, broadcast-and-trace, and somewhere-statistically sound batch arguments for NP.The batch-argument application uses an ordinary LWE assumption and polynomial security of the assumed instantiation.Source: §6 · pp. 31–32
Loading 2609.18275v2…