Witness Encryption via Prime-Order Generic Groups
arXiv:2609.18275v1 [cs.CR] 16 Sep 2026
Isaac M Hair ∗ UCSB, UCLA
Amit Sahai † UCLA
Abstract We unconditionally construct witness encryption for NP in the classical generic-group model, using an ordinary cyclic group of prime order. For SAT instances of size n, the encryption algorithm runs in time poly(n), and any satisfying assignment can be used to decrypt in Ω(1) poly(n) time with correctness error 2−n . If no satisfying assignment exists, then every generic adversary making at most nΘ(log n) group queries has distinguishing advantage at most n−Θ(log n) . Along the way, we prove the first superconstant-factor NP-hardness of approximation result for homogeneous MinRank under randomized polynomial-time reductions, achieving a logarithmic gap even when the rank-one witness has a Boolean right factor.
1
Introduction
Witness encryption allows a message to be encrypted to a mathematical statement. Anyone who knows a witness that the statement is true can decrypt. If the statement is false, the ciphertext must hide the message. Since its introduction by Garg, Gentry, Sahai, and Waters [GGSW13], witness encryption has provided a way to turn the existence of witnesses into cryptographic access control. We study this problem in the ordinary prime-order generic-group model. In this model, group elements have random encodings, and algorithms access the group law through an oracle. There is no pairing or multilinear operation. Barta, Ishai, Ostrovsky, and Wu [BIOW20] identified a route to witness encryption in this model based on an (as-of-yet unproven) conjecture on NP hardness of approximation for the minimum distance of code problem. Their approach raises a useful broader question: which NP hardness of approximation gaps lead to a witness encryption scheme that can simultaneously support efficient decryption and a generic security proof? Our answer uses matrix rank. The reduction produces a linear space of matrices with two properties. On a true statement, a witness identifies a rank-one matrix uv T , where v has small integer coordinates. On a false statement, every nonzero matrix in the space has large rank. The first property allows us to perform decryption in polynomial time, and the second makes the algebraic equalities that a generic adversary can test unlikely.
1.1
Our results
We use the standard witness-encryption requirement: correctness on true statements and indistinguishability on false statements. Security does not require hiding the message on a true statement from a party that lacks a witness. See Theorem 2.1 for a formal definition. Throughout, logarithms have base two. Theorem 1.1 (Witness encryption). There are polynomial-time witness-encryption algorithms for every NP relation in the classical prime-order generic-group model with the following guarantees. Let n = max{2, λ, |φ|}, where λ is the security parameter and φ is the encoded NP statement. Then: ∗ †
[email protected] [email protected]
1
1. Every valid witness decrypts correctly with probability at least 1 − 2−n
Ω(1)
.
2. On every false statement, every classical adversary making at most nΘ(log n) group-oracle queries has distinguishing advantage at most n−Θ(log n) . Each encryption uses a fresh random group encoding. Adversaries may perform arbitrary local computation, inspect encoding strings, and submit arbitrary strings to the oracle. Their advice is independent of the fresh encoding and the encryption randomness. The quantitative bound in Theorem 3.5 gives the tradeoff between query budget and distinguishing advantage. We also obtain a logarithmic hardness gap for a bounded-factor version of MinRank (which automatically implies the same hardness gap for standard MinRank). Given a basis of a linear space S ⊆ Fm×m , homogeneous MinRank asks for the minimum rank of a nonzero matrix in S. In p the bounded-factor promise problem, the YES case contains a nonzero rank-one matrix uv T , where u ∈ Fm p and the coordinates of v are integers in {0, . . . , B}, viewed in Fp , for a specified bound B < p. The NO case requires every nonzero matrix in S to have rank at least a specified threshold. We obtain a logarithmic gap even when B = 1, so the right factor is Boolean. Theorem 1.2 (Bounded-factor MinRank hardness, informal). For some f (m) = Θ(log m), it is NP-hard under randomized polynomial-time reductions to distinguish the following cases for a linear space S ⊆ Fm×m , given by a basis, over primes p = Θ(2m ): p 1. S contains a nonzero matrix uv T with v ∈ {0, 1}m . 2. Every nonzero matrix in S has rank at least f (m). See Theorem 3.1 for the formal reduction, which is deterministic for every sufficiently large supplied prime, and Theorem 4.4 for the randomized choice of prime. This also gives a logarithmic hardness gap for homogeneous MinRank without the bounded-factor requirement. Previous polynomial-time reductions gave only constant-factor NP-hardness [GRT26]; their larger gaps require superpolynomial reductions and stronger complexity assumptions.
1.2
Related work and mathematical ingredients
Witness encryption and ideal groups. The first construction of witness encryption used multilinear maps [GGSW13]; Gentry, Lewko, and Waters [GLW14] subsequently developed constructions from instance-independent assumptions. The closest generic-group precursor is Barta et al. [BIOW20], who connect witness-preserving approximation hardness over large fields to witness encryption. Their proposed NP-hardness condition concerns Hamming minimum distance with a gap larger than logarithmic, which is not known. We instead use a matrix rank gap and prove the encryption and collision arguments directly from that promise. Indistinguishability obfuscation also implies witness encryption: one obfuscates a circuit that outputs the message on valid witnesses and ⊥ otherwise [GGH+ 13]. On a false statement, the circuits for different messages compute the same constant function. Combining this implication with the constructions of Jain, Lin, and Sahai [JLS21, JLS22] gives witness encryption in the standard model from subexponential versions of well-studied assumptions. Ragavan, Vafa, and Vaikuntanathan [RVV24] subsequently construct indistinguishability obfuscation from subexponential versions of the decisional linear assumption on bilinear groups, large-field LPN, and binary sparse LPN. Other work relates witness encryption to proof systems. Faonio, Nielsen, and Venturi study predictable arguments of knowledge [FNV17]. Liu, Mazor, and Pass characterize witness encryption 2
through special-honest-verifier zero-knowledge arguments with logarithmic prover communication [LMP25]. Garg, Hajiabadi, Kolonelos, Kothapalli, and Policharla give a framework based on linearly verifiable SNARKs, with special-purpose applications [GHK+ 25]. Bartusek, Ishai, Jain, Ma, Sahai, and Zhandry use determinant and rank-deficiency structure in their affine determinant program framework for obfuscation and witness encryption [BIJ+ 20]. Choi and Vaudenay study extractable witness encryption for a promise version of multi-subset sum in a hidden-group-withhashing abstraction [CV22]; both the promise and the model differ from ours. Our security proof follows the random-encoding approach to generic-group lower bounds exemplified by Shoup [Sho97]. The model and the primitive matter when comparing such results. In particular, the generic-group identity-based encryption lower bound of Schul-Ganz and Segev [SGS21] does not by itself exclude witness encryption in the model considered here. As discussed by Barta et al. [BIOW20], the usual transformation from witness encryption to identity-based encryption uses the group in a non-black-box way. MinRank and coding-theoretic hardness. Bläser, Ikenmeyer, Lysikov, Pandey, and Schreyer establish NP-hardness of homogeneous rank-one MinRank through homogeneous quadratic feasibility [BIL+ 19]. Guruswami, Ren, and Tang [GRT26] prove stronger promise-rank hardness. For a source size M and rank threshold k, their constructions have size M O(log k) over fixed characteristictwo fields and M O(k) over arbitrary fixed finite fields. Their arbitrary-finite-field moment construction already has Boolean rank-one factors. The issue addressed here is the simultaneous attainment of polynomial output size, a logarithmic rank threshold, and a growing prime characteristic. Boolean completeness itself is an established feature of the moment-matrix approach. MinRank has several cryptographic formulations. Courtois uses an affine MinRank problem for authentication [Cou01]; Gaborit and Zémor study decoding and minimum distance for extensionfield-linear rank codes [GZ16]. Chatterjee, Mu, and Vasudevan construct public-key encryption from planted average-case binary MinRank, using matrix-valued inner products and rank-metric duality [CMV26]. Our construction uses a worst-case reduction to a homogeneous prime-field matrix space. Decryption tests a short interval of scalar exponents, and security uses the rank of every nonzero matrix in the space. As mentioned previously, Barta et al. [BIOW20] showed how to leverage sufficiently strong NP hardness of approximation for the minimum distance of code problem to build witness encryption. Austrin and Khot give a deterministic reduction for gap minimum distance [AK14]. Bhattiprolu, Guruswami, Lee, and Ren use tensor-code structure and rank-versus-weight estimates in their hardness results for sparse vectors [BGLR25]. The characteristic-two approach of Guruswami et al. also connects to the superposition-soundness methods of Khot and Saket [KS17]. All of these reductions only achieve a constant factor gap under polynomial time reductions. Algebraic sources of the reduction. We will use a geometric-evaluation argument that belongs to the same family of rank-preservation ideas used in explicit subspace designs and symbolic rank condensers [GK16, FSS14]. Here we will prove the fact we need directly: after eliminating leading terms, a determinant of geometrically sampled polynomials has a nonzero Vandermonde leading coefficient. A large supplied prime keeps the evaluation points distinct. We will combine this elementary fact with weighted bit-pair tables whose right factor remains Boolean. To efficiently construct the matrix space in our encryption algorithm, we will use tools related to the propagation of coefficient spaces in algebraic branching programs. Raz and Shpilka retain bases of such spaces in deterministic polynomial identity testing [RS05]. In our setting, the two transitions will be Boolean choices, and we will prove the needed closure properties directly.
3
For soundness, we will use Boolean interpolation to get selectors on the small coordinate space supplied by low rank. Our proof technique is related to the use of polynomial equation consequences in Nullstellensatz proof systems [BIK+ 96] and their dual description by designs [Bus98]; polynomial calculus provides a related dynamic proof system [CEI96]. Moment reconstruction provides additional context. Laurent and Mourrain relate flat extensions of moment matrices over arbitrary fields to quotient algebras and commuting multiplication operators [LM09]; Mourrain studies finite-rank Hankel operators and Prony-type reconstruction [Mou18]. In characteristic two, power sums appear as BCH syndromes, with shift-register reconstruction as developed by Massey [Mas69]. Moore determinants and linearized polynomials describe the corresponding Frobenius linear algebra [Moo96, WL13]. Feng–Rao-type arguments obtain rank lower bounds from a first nonzero syndrome and ordered products; see Matsumoto and Miura [MM00]. These uses of moments and rank are related to our proof, although we will not use any of the theorems as black boxes, and we do not need to explicitly reconstruct a low-rank matrix as a sum of points.
Acknowledgements and AI use methodology The human authors spent several months thinking about how to construct witness encryption in the generic group model making use of various NP reductions. We then began a search via Codex / ChatGPT 6 Astra Ultra using harness components from the UCLA Moonshot Harness Project [ZHC+ 26]. The human authors thought that NP hardness of MinRank could be helpful, and we suggested this approach to Codex. Codex responded that it did not see how to use MinRank directly, but that the variant of MinRank presented here (bounded-factor MinRank) could be proven NP-hard and used to build witness encryption. We then used Codex to significantly simplify the proof ideas it had suggested, and rewrote much of what it suggested. Of course, the human authors take full responsibility for this paper and all its contents. If any reader is aware of any references that should be cited, please contact us and we will update the manuscript. Remark 1.3. Using Codex, we were also able to show that bounded-factor MinRank is NP hard to approximate within a factor of (log n)c for any constant c > 1, which gives a witness encryption scheme with any desired quasipolynomial security, but we have not refined the proof sufficiently to incorporate this improvement into the present writeup. This research was supported in part by a Laude Moonshot seed award, a Simons Investigator Award, a DARPA expMath award, NSF grant 2333935, BSF grant 2022370, a Xerox Faculty Research Award, a Google Faculty Research Award, an Okawa Foundation Research Grant, and the Symantec Chair of Computer Science.
2
Preliminaries
Vectors are columns. For a prime p, we write Fp = Z/pZ; all matrix ranks and spans are over Fp , m unless stated otherwise. A Boolean vector in Fm p is the image of a vector in {0, 1} ; its Hamming weight wt(v) counts its nonzero coordinates. We regard these coordinates as the integers zero and one when bounding a decryption search. A basis of a matrix space always means a linearly independent basis.
4
Definition 2.1 (Witness encryption). Let R be a polynomial-time decidable, polynomially balanced relation, and let L = {φ : ∃w, (φ, w) ∈ R}. A witness encryption scheme for R consists of polynomial-time algorithms Enc and Dec [GGSW13, GLW14]. Encryption takes (1λ , φ, β), where β ∈ {0, 1}, and outputs a ciphertext C. Decryption takes (1λ , φ, w, C) and outputs a bit or ⊥. Writing n = max{2, λ, |φ|}, we require: 1. Correctness. There is a negligible function κ such that, for every λ, every (φ, w) ∈ R, and every β ∈ {0, 1}, h i Pr Dec(1λ , φ, w, Enc(1λ , φ, β)) = β ≥ 1 − κ(n). 2. False-statement security. For every probabilistic polynomial-time adversary A, there is a negligible function εA such that, for every λ and every φ ∈ / L, AdvA (λ, φ) = Pr[A(1λ , φ, Enc(1λ , φ, 0)) = 1] − Pr[A(1λ , φ, Enc(1λ , φ, 1)) = 1] ≤ εA (n). Probabilities are over the algorithms’ randomness, and the bounds are uniform over the statements and witnesses. No security requirement is imposed when φ ∈ L. In this paper, the algorithms use the generic-group oracle defined below, and the probabilities also range over its fresh random encoding. Decryption and the adversary use the group context included in the ciphertext. We prove a stronger quantitative guarantee for every classical adversary making at most a specified number of oracle queries, with no restriction on its local running time. The restrictions on advice are specified below. Statements and witnesses. It suffices to give witness encryption for Boolean circuit satisfiability. A polynomial-time NP verifier can be compiled into such a circuit, preserving witnesses, and every satisfying input extends to the gate values. We use φ for the resulting satisfiability statement. An independent security parameter is accommodated by padding the algebraic encoding to at least λ variables. The effective size is n = max{2, λ, |φ|}. For a fixed NP relation, the circuit size is polynomial in the original statement and witness bounds; this polynomial change preserves all asymptotic guarantees in Theorem 1.1. A fresh generic cyclic group. For each encryption and prime p, the model supplies a fresh, uniformly random injection σ : Fp −→ {0, 1}ℓ ,
ℓ = 2⌈log p⌉.
We write g a = σ(a), so g = σ(1). The group oracle takes two strings and an addition or subtraction instruction, and returns σ(a + b) or σ(a − b) on valid encodings σ(a), σ(b); it returns ⊥ if either operand is invalid. Equality is ordinary string equality. Known scalar multiples use O(log p) group operations. This is an ordinary generic group: no oracle multiplies two unknown exponents. A ciphertext includes access to its fresh group context, denoted Γ. The random encoding table is part of the oracle model. The algorithms transmit only polynomially many handles (encoding strings), not the table. An adversary may inspect strings and use arbitrary local computation; oracle calls, including calls on guessed strings, are charged to its query budget. Advice may depend on the statement but not on the fresh encoding or hidden encryption coins.
5
3
Witness encryption
We construct the scheme from the following matrix-space guarantee, which we prove in Section 4. Theorem 3.1 (Boolean-factor MinRank reduction). Given a satisfiability instance φ, choose a padding parameter N ≥ max{2, |φ|} large enough to hold its Boolean quadratic encoding, and put R = ⌊log N ⌋. For every prime p > max{2N , 2N R}, a deterministic algorithm running in poly(N, log p) time outputs an ordered basis M1 , . . . , Mk of a space S ⊆ Fm×m , with p 2R m = (N + 1)(2N R + 1) R
!
= O(N 4 log N ),
such that: 1. If φ is satisfiable, every satisfying witness efficiently yields a ∈ Fkp and u, v ∈ Fm p satisfying k X
aj Mj = uv T ̸= 0,
v ∈ {0, 1}m ,
wt(v) ≤ N + 1.
j=1
2. If φ is unsatisfiable, every nonzero matrix in S has rank at least R + 1. The matrix order m depends only on N and can be computed in polynomial time before choosing p. The scheme uses only this interface: an independent basis, a rank-one witness with a Boolean factor, and a rank lower bound on false statements.
3.1
Parameters and algorithms
Given (1λ , φ), put n = max{2, λ, |φ|} and form the Boolean quadratic encoding. Let N be the larger of n and the number of variables in that encoding, and pad with unused variables to reach N . Thus N = Θ(n). Compute the matrix order m supplied by Theorem 3.1, and put d = 1 + ⌊log N ⌋. Choose a prime p ∈ [2m , 2m+1 ). With R = d − 1, the displayed formula for m gives m > N and m > 2N R. Hence p ≥ 2m > max{2N , 2N R}, as required by the reduction. For this prime, compute the deterministic basis M1 , . . . , Mk from Theorem 3.1; in particular, k ≤ m2 . The basis is determined by the public input and p, so it need not be included in the ciphertext. We first describe the algorithms with exact sampling. The bounded-time implementation immediately below adds a common abort outcome. Encryption Enc(1λ , φ, β). Obtain a fresh group context Γ of order p and independently sample s ← Fm p ,
r ← {0, . . . , m − 1}m ,
η ← Fkp .
Output (
C = (p, Γ, g, X1 , . . . , Xm , Y1 , . . . , Yk ),
si
Xi = g ,
Yj =
T
g s Mj r , g ηj ,
Both messages use the same samplers, including the unused randomness.
6
β = 0, β = 1.
(1)
Decryption Dec(1λ , φ, w, C). Check the witness. For a valid witness, compute a, u, v as in Theorem 3.1, and form H=
m Y
Xiui ,
Z=
i=1
k Y
a
Yj j ,
B = (m − 1) wt(v).
j=1
Return zero if Z is one of 1, H, H 2 , . . . , H B , and return one otherwise. Compute this list by successive group operations. On the common abort outcome return zero; on an invalid witness or malformed input return ⊥. All steps are polynomial time. Scalar exponentiation costs O(log p) group operations, and B ≤ m(N + 1). The ciphertext has O(m + k) handles, each of O(log p) bits, and log p = O(m). This proves polynomial communication as well. Lemma 3.2 (Bounded sampling). The scheme has a bounded polynomial-time implementation with sampling failure probability δ = 2−Ω(m) . Conditioned on an accepted prime and successful sampling, the distributions in Equation (1) are exact. The failure event and public-prime distribution are the same for both messages. Proof. Test m2 independent uniform candidates from [2m , 2m+1 ) using a deterministic polynomialtime primality test [AKS04]. Prime density Ω(1/m) gives failure probability 2−Ω(m) . For each field or grid coordinate, sample a binary integer with the minimum sufficient bit length, reject if it is outside the desired range, and allow m attempts. Acceptance probability is at least one half, and a successful value is exactly uniform. There are polynomially many coordinates, so their total failure probability is also 2−Ω(m) . Use independent randomness for all coordinates and the same schedule for both messages. Conditional on success, the coordinates remain independent and uniform; any reweighting of the accepted prime is common to both messages. On any failure output a fixed abort symbol.
3.2
Correctness
Proposition 3.3 (Correctness). For every satisfying witness and either message, decryption fails with probability at most δ + m(N + 1) + 1 2−m = 2−Ω(m) . Proof. Fix an accepted prime p and condition on successful sampling. For an encryption of zero, Z=g
P
sT (
j
aj Mj )r
T
T
T
= g (s u)(v r) = H v r .
The integer v T r lies in [0, B], since v is Boolean. The tested list therefore contains Z, even if H = 1. For an encryption of one, a ̸= 0, because its matrix combination is nonzero. Hence aT η is T uniform in Fp and independent of H. The probability that Z = g a η lies in the tested list is at most (B + 1)/p; repeated powers only shorten the list. Averaging over the prime, adding sampling failure, and using p ≥ 2m proves the claim.
3.3
Rank bounds a single collision
The security proof starts with a finite-grid estimate. It uses independence of coordinates, not a polynomial identity testing theorem.
7
Lemma 3.4 (Bilinear collision bound). Let M ∈ Fm×m have rank ρ, and fix α ∈ Fm p p and c ∈ Fp . m m For independent s ← Fp and r ← {0, . . . , m − 1} , where m < p, Pr[c + sT (α + M r) = 0] ≤ m−ρ + p−1 . If M = 0 and (c, α) ̸= (0, 0), the bound improves to p−1 . Proof. Choose ρ independent columns of M and fix the coordinates of r outside those columns. At most one choice of the remaining coordinates can satisfy M r = −α. Since their grid values are distinct field elements, this event has probability at most m−ρ . Off that event, the expression is a nonconstant affine linear form in uniform s, so it vanishes with probability 1/p. The final assertion is the same affine-linear calculation.
3.4
Adaptive generic security
Theorem 3.5 (Quantitative generic security). Fix an unsatisfiable φ and any accepted prime p. Against a classical generic adversary making Q oracle queries, the distinguishing advantage of the scheme, conditional on successful sampling, is at most
O (Q + m + k)2 m−d + p−1
.
(2)
This holds with arbitrary local computation and arbitrary-string oracle inputs. Averaging over the prime and including the common abort outcome gives the same bound with p−1 replaced by 2−m . Proof. We couple both ciphertext distributions to one symbolic experiment. Introduce formal variables S1 , . . . , Sm and Z1 , . . . , Zk . Initially associate the generator, identity, and ciphertext handles with the formal affine linear expressions 1, 0, S1 , . . . , Sm , Z1 , . . . , Zk . Writing S = (S1 , . . . , Sm )T and Z = (Z1 , . . . , Zk )T , the simulator stores coefficient vectors of affine forms F = c + αT S + γ T Z. k Here c ∈ Fp , α ∈ Fm p , and γ ∈ Fp . Identical vectors use the same label; a new vector receives a fresh uniform label distinct from those already assigned. A group operation adds or subtracts coefficient vectors. There are at most H = m + k + Q + 2 such forms. First consider oracle inputs using already assigned labels. Fix the adversary’s coins and all labels of the symbolic simulation. This fixes its entire adaptive list of forms independently of s, r, η. We bound collisions on this fixed symbolic list, rather than condition a real transcript on having avoided earlier collisions. In the one distribution, substitute S = s and Z = η. The difference of distinct forms is a nonzero affine linear form in uniform (s, η), so it evaluates to zero with probability at most 1/p. In the zero distribution, the same difference evaluates to
c + sT (α + Mγ r),
Mγ =
X
γj Mj .
j
If γ = ̸ 0, independence of the basis makes Mγ ̸= 0, and unsatisfiability gives rank Mγ ≥ d. Theorem 3.4 bounds the collision probability by m−d + p−1 . If γ = 0, the nonzero affine-linear bound p−1 applies. 8
Until two distinct forms evaluate to the same exponent, either real experiment can use exactly the labels of the common simulator. Writing Adv for the distinguishing advantage, a union bound over the pairs in both experiments therefore gives Adv ≤
H 2
!
m−d + 2p−1
for inputs using known labels. This coupling accounts for full adaptivity and for decisions based on the bit patterns of labels. Now allow arbitrary-string inputs. Extend the simulator to reject any candidate operand that is not already assigned. Exclude each such rejected string from subsequent fresh labels. There are at most 2Q candidates. Until one is a valid unseen encoding, the remaining valid labels are exchangeable among unassigned, unexcluded strings. Since the ambient label space has size U = 2ℓ ≥ p2 , each new candidate is valid with conditional probability at most p . U − H − 2Q It suffices to consider Q + m + k ≤ p, since otherwise the claimed bound exceeds one. In this range the denominator is Ω(p2 ), and coupling both experiments adds O(Q/p), which is absorbed by Equation (2). Declaring either guessed operand valid to be a bad event also covers an oracle that returns a single undifferentiated invalid-input symbol. Arbitrary computation on strings provides no additional, uncharged validity oracle. All collision bounds hold for every accepted prime, with the exact conditional sampling distributions supplied by Theorem 3.2. The two messages have identical abort and public-prime distributions. The abort branch contributes zero distinguishing advantage, so averaging preserves the bound without an additive sampling-error term.
3.5
Putting the parameters together
Proof of Theorem 1.1. The reduction uses N = Θ(n), d = Θ(log n), and N ≤ m = N O(1) , while k ≤ m2 and p ≥ 2m . Consequently m−d = n−Θ(log n) ,
p−1 = 2−n
Ω(1)
.
For a sufficiently small positive constant in the exponent, choose Q∗ (n) = nΘ(log n) . Then (Q∗ (n) + m + k)2 m−d = n−Θ(log n) , and the p−1 term is smaller. This gives a function ε(n) = n−Θ(log n) satisfying the security claim. Correctness follows from Theorem 3.3 and m = nΩ(1) . The algorithms and communication are polynomial in n, by the matrix construction and the bounded sampling implementation. Finally, witness-preserving circuit encodings give the claim for every NP relation. The construction uses the two matrix promises in separate, concrete ways: bounded coordinates allow decryption to enumerate candidate exponents, and rank prevents a generic adversary from encountering useful accidental equalities. Stronger rank gaps or smaller encodings would improve the quantitative tradeoff through Equation (2) without changing the encryption algorithm.
9
4
A matrix space with Boolean rank-one witnesses
We prove Theorem 3.1 by constructing the matrix space used by the encryption scheme. The proof uses linear algebra over a field, elementary polynomials, and Boolean circuits. We begin with the rank-one case, then explain cancellation and the purpose of weighted tables. After choosing the weights, we prove soundness and give the exact-span algorithm. Throughout this section the prime is supplied to the reduction; the large-prime hypothesis will be used to keep certain powers of two and sample values distinct. We allow any integer rank threshold 1 ≤ R ≤ N in the construction, and take R = ⌊log N ⌋ when proving Theorem 3.1.
4.1
A table that contains one assignment
Write the input equations as b = (b1 , . . . , bN ) ∈ {0, 1}N ,
q1 (b) = · · · = qJ (b) = 0,
where every qs has degree at most two over Fp . For a Boolean circuit, an AND gate with input bits bi , bj and output bit bk gives bk − bi bj = 0. A NOT gate gives bk + bi − 1 = 0, and acceptance gives bout − 1 = 0. Consequently circuit satisfiability has this form with polynomial overhead; a satisfying circuit input determines all the gate bits efficiently. There are O(|φ|) variables and equations. Pad with unused bits to reach the chosen N ≥ max{2, |φ|}, as in Theorem 3.1. All assignments used to define our matrices will be Boolean. Set b0 = 1. This is an indexing convention, not an additional unknown bit. Define the column vector and its table of pairwise products by v(b) = (1, b1 , . . . , bN )T ,
M (b) = v(b)v(b)T .
Rows and columns of this table are indexed by 0, . . . , N . Thus M (b)ij = bi bj ,
M (b)00 = 1,
M (b)0i = M (b)ii = bi .
The first coordinate lets one table contain constants, individual bits, and products of two bits. It also ensures that M (b) is nonzero. An equation becomes a linear test of the table. q(b) = a0 +
N X
ai bi +
i=1
For a quadratic polynomial X
aij bi bj ,
1≤i≤j≤N
define the following linear function of a matrix M : Tq (M ) = a0 M00 +
N X i=1
ai M0i +
X
aij Mij .
(3)
i≤j
In particular, Tq (M (b)) = q(b). The AND equation above is tested by M0k − Mij . The equation is quadratic in the unknown bits, but its test is linear in the entries of the table.
10
Why a rank-one table is enough to recover bits. Every honest table M (b) is symmetric and has rank one. Conversely, the identities Mii = M0i nearly force a rank-one table to be honest. (N +1)×(N +1)
Lemma 4.1. Suppose M ∈ Fp Mii = M0i for 1 ≤ i ≤ N . Then
M = M00 v(b)v(b)T
is nonzero, is symmetric, has rank one, and satisfies
for some b ∈ {0, 1}N ,
M00 ̸= 0.
If every Tqs (M ) vanishes, this b satisfies the input equations. Proof. Every 2 × 2 minor of a rank-one matrix is zero. If M00 = 0, the minor using rows and 2 = 0. Thus M = M = 0. The minors using rows and columns i, j then give columns 0, i gives M0i 0i ii Mij2 = 0, making the whole matrix zero, a contradiction. We can therefore set bi = M0i /M00 . The minor using rows 0, i and columns 0, j gives Mij = M0i M0j /M00 . Now Mii = M0i says b2i = bi , whose only solutions in a field are zero and one. Finally Tqs (M ) = M00 qs (b). This settles the rank-one starting point. The challenge is to exclude ranks two through R as well.
4.2
Cancellation and selectors
A linear space must contain sums and scalar multiples of its matrices. We therefore have to understand expressions such as X
M=
λb ∈ Fp .
λb M (b),
b∈{0,1}N
In particular, passing an equation test means only that Tqs (M ) =
X
λb qs (b) = 0.
b
Several failures of an equation can cancel. The ideal weights would isolate assignments. Given h Boolean coordinates, write w = (w1 , . . . , wh ). For a particular point e = (e1 , . . . , eh ) ∈ {0, 1}h , define Ee (w) =
Y
wj
j:ej =1
Y
(1 − wj ).
(4)
j:ej =0
This polynomial equals one at e and zero at every other Boolean point. Its degree is h. For one bit, the two selectors are simply 1 − w and w. If we could use every selector on the original N bits as a weight, then applying the same table P test Tqs to the table b λb Ee (b)M (b) would give X
λb Ee (b)qs (b) = λe qs (e).
b
Requiring this weighted table to pass the test would therefore say λe qs (e) = 0. For an unsatisfiable system, some equation fails at each e, so every λe would be zero. No cancellation would survive. The difficulty is the number of selectors: there are 2N of them. We will use rank to make a smaller collection suffice. To explain how, we first need to put several weighted tables into one matrix. 11
4.3
Put the weighted tables on top of one another
Temporarily let H be any finite list of polynomials in the bits, called weights, including the constant polynomial 1. Write its members as h1 , h2 , . . .. For a single assignment, stack one table for each weight: h1 (b)v(b)v(b)T h1 (b)v(b) T A(b) = h2 (b)v(b)v(b) = h2 (b)v(b) v(b)T . (5) .. .. . . This is still a rank-one matrix: all its blocks have the same right factor v(b). It is nonzero because one block has weight 1. Take the span of these whole matrices: V = span{A(b) : b ∈ {0, 1}N }. An arbitrary A ∈ V has some expression A = b λb A(b). Its block belonging to a weight h is therefore X Bh = λb h(b)v(b)v(b)T . (6) P
b
The same coefficients λb occur in every block. Allowing each block to choose its own coefficients would be a different construction. Keep just those matrices whose every block passes every input equation: S = {A ∈ V : Tqs (Bh ) = 0 for all s ∈ {1, . . . , J}, h ∈ H}.
(7)
These are homogeneous linear constraints on matrix entries, so S is a linear space. Equivalently, its constraints say X λb h(b)qs (b) = 0. (8) b
If b is a satisfying assignment, A(b) passes every constraint and is a nonzero rank-one matrix in S. Thus the YES case already works, whatever additional weights we choose. What a relation between columns actually says. For example, suppose columns 0, 1, 2 of the whole stack satisfy column 2 = c column 0 + d column 1. Here c, d ∈ Fp are scalars. This is what we mean by a column relation: an equality between the indicated column vectors. It must hold in every row of every block. The row indexed by i in the block Bh says exactly X λb h(b)bi (b2 − c − db1 ) = 0. (9) b
Consequently, inside this particular sum, we can replace b2 by c + db1 without changing its value. This does not assert that b2 = c + db1 at every assignment. It asserts an equality between weighted sums, proved by expanding a matrix-column equality. If A has rank ρ, only ρ of its columns are needed to express all the others. The example shows why that might help: relations between columns can give replacement rules inside our tests.
12
4.4
Choose weights that work for every possible column space
For the threshold 1 ≤ R ≤ N fixed above, build weights from R linear combinations of the coordinates b0 , b1 , . . . , bN , remembering that b0 = 1. If these combinations are ℓ1 (b), . . . , ℓR (b), include all products ℓ1 (b)α1 · · · ℓR (b)αR ,
αj ∈ Z≥0 ,
α1 + · · · + αR ≤ R.
(10)
Thus we can take any polynomial of degree at most R in these R quantities as a weight, by linearly R listed monomials. To obtain this count, introduce a combining blocks. There are only 2R 4 ≤ R PR+1 P slack exponent αR+1 = R − R α j=1 j and count nonnegative solutions of j=1 αj = R: arrange R objects and R separators in a row. The numbers of objects before the first separator, between successive separators, and after the last give the R + 1 exponents. We use R combinations because a matrix of rank at most R has a column space of dimension at most R. We want our combinations to span that space. The choice must be made before seeing the matrix, so we include several lists of combinations. The next elementary lemma will ensure that one list works. A family of spanning combinations. Require the supplied prime to satisfy the bound below, and set p > max{2N , 2N R}, D = N R, S = {0, 1, . . . , 2D} ⊆ Fp . (11) The exponential lower bound on p is harmless for the reduction: the running time is polynomial in log p. Its purpose is to make the distinct integer powers 1, 2, 4, . . . , 2N remain distinct in the field. For each t ∈ S use the R forms ℓj,t (b) =
N X
(2j−1 t)i bi ,
1 ≤ j ≤ R.
(12)
i=0
As usual a zeroth power is one, including when t = 0. For example, the first two combinations, when R ≥ 2, are ℓ1,t (b) = 1 +
N X
ti bi ,
ℓ2,t (b) = 1 +
i=1
N X
(2t)i bi .
i=1
The same coefficients will be applied to matrix columns in the next lemma. We will use the elementary polynomial root bound: a nonzero polynomial of degree d over a field has at most d distinct roots. Lemma 4.2. Let c0 , . . . , cN be vectors over Fp spanning a space of dimension 1 ≤ ρ ≤ R. Define vector polynomials dj (T ) =
N X
(2j−1 T )i ci ,
1 ≤ j ≤ ρ.
i=0
There is a nonzero scalar polynomial ∆(T ) of degree at most N ρ ≤ D such that, whenever ∆(t) ̸= 0, the vectors d1 (t), . . . , dρ (t) are a basis of the given space. Proof. Choose coordinates on the ρ-dimensional space. The coordinates of i ci T i are ρ polynomials f1 (T ), . . . , fρ (T ), each of degree at most N . They are linearly independent. To see why, suppose P scalars r1 , . . . , rρ give j rj fj (T ) = 0. Comparing the coefficient of each T i says that the row vector (r1 , . . . , rρ ) times the coordinate vector of ci is zero. The ci span the whole coordinate space, so that row vector must be zero. P
13
Gaussian elimination on their coefficient vectors lets us replace these polynomials by invertible linear combinations with distinct degrees e1 < · · · < eρ . One way to do this is to select a polynomial of highest degree, cancel its leading coefficient in the others, and continue. Denote the resulting nonzero leading coefficients by a1 , . . . , aρ . Consider the matrix with entry fi (2j−1 T ) in row i, P column j, after this elimination. Its P determinant has degree at most i ei . The coefficient of T i ei is 1 2e1 ! ρ Y 1 2e2 ai det .. .. . . i=1 1 2eρ
(2e1 )2 · · · (2e1 )ρ−1 (2e2 )2 · · · (2e2 )ρ−1 . .. .. . . (2eρ )2 · · · (2eρ )ρ−1
The displayed matrix is invertible. Indeed, a nontrivial linear combination of its columns equal to zero would describe a nonzero polynomial of degree at most ρ − 1 vanishing at the ρ distinct points 2e1 , . . . , 2eρ . This is impossible. These points are distinct because ei ≤ N and p > 2N . Thus the determinant is a nonzero polynomial of degree at most N ρ. Undoing the invertible row operations changes it only by a nonzero constant. Take the original determinant as ∆(T ). Its nonvanishing says precisely that the dj (t) are independent. The complete weight list and the resulting size. For every t ∈ S and every exponent tuple α = (α1 , . . . , αR ) in (10), put the weight hα,t (b) =
R Y
ℓj,t (b)αj
(13)
j=1
in H. Keep repeated weights as separate blocks; this makes the description uniform and does not harm the proof. Construct A(b), V, and S as in (5)–(7). There are 2R K = (2N R + 1) R
!
blocks, so the matrices have m = (N + 1)K rows and N + 1 columns. Append m − (N + 1) zero columns to make them square. This does not change their rank. The right factor of an honest matrix is then (1, b1 , . . . , bN , 0, . . . , 0)T , a Boolean vector with at most N + 1 nonzero entries. Proposition 4.3. For the supplied prime in (11), the construction gives a matrix space S ⊆ Fm×m p with ! 2R m = (N + 1)(2N R + 1) . (14) R A satisfying assignment gives a nonzero rank-one matrix in S with the Boolean right factor just described. If the equations are unsatisfiable, every nonzero matrix in S has rank greater than R. An ordered basis of S is deterministically computable in time polynomial in N, J, m, log p. Given a satisfying assignment, the coordinates of its matrix in that basis are computable within the same bound. For R = ⌊log2 N ⌋, one has m = O(N 4 log N ), and every nonzero NO-case matrix has rank Ω(log m). We already proved the satisfying-assignment claim immediately after (7). The next subsection proves the rank lower bound; Section 4.6 gives the basis algorithm. 14
4.5
Why a nonzero low-rank matrix would yield a solution
Suppose, toward a contradiction, that the input equations are unsatisfiable but A ∈ S is nonzero and has rank 1 ≤ ρ ≤ R. Discard its appended zero columns. Choose an expression X
A=
λb A(b)
b∈{0,1}N
and keep these same coefficients throughout the proof. This expression need not be unique and we do not need to find it algorithmically. Let c0 , . . . , cN be the actual column vectors of this whole stack. Step 1: choose one useful list that also contains a nonzero block. Apply Lemma 4.2 to the columns ci , obtaining ∆(T ). Its nonvanishing will give a basis of the whole column space. We also want a nonzero block among the weights at the same value of t. Since A ̸= 0, some block entry is nonzero. Suppose it has weight index α, sample value t0 , and row and column indices i, j. Replace the sample value in that entry by a formal variable T : f (T ) =
X b
λb bi bj
!αs
R Y
N X
s=1
k=0
(2s−1 T )k bk
.
This polynomial is nonzero because f (t0 ) ̸= 0. Each factor inside parentheses has degree at most N , P and s αs ≤ R, so deg f ≤ N R = D. The product f (T )∆(T ) is therefore a nonzero polynomial of degree at most 2D. It cannot vanish at every one of the 2D + 1 distinct values in S. Fix a value t where the product is nonzero. At this value, 1. the first ρ column combinations in Lemma 4.2 form a basis of the entire column space of A; 2. at least one of the blocks with this value of t is nonzero. We will show that all these blocks are zero, obtaining a contradiction. From now on this t is fixed. Write ℓj = ℓj,t and ℓ(b) = (ℓ1 (b), . . . , ℓR (b)). Step 2: record exactly which replacements the columns permit. Suppose scalars P κ0 , . . . , κN ∈ Fp give a column relation κ0 c0 + · · · + κN cN = 0, and write k(b) = N i=0 κi bi . Let a(b) be any linear combination of b0 , . . . , bN , and let H be a polynomial of degree at most R in R variables. Expanding block rows as in (9) gives X
λb k(b)a(b)H(ℓ(b)) = 0,
deg H ≤ R,
(15)
b
Indeed the individual rows give a = bi ; linear combinations of rows give general a. Linear combinations of the monomial blocks give general H. Constants are allowed as a because b0 = 1. For any polynomial G of degree at most R + 1 in R variables, we also have X
λb k(b)G(ℓ(b)) = 0,
deg G ≤ R + 1.
(16)
b
For a nonconstant monomial in G, use one of its ℓj factors as a in (15); the remaining product has degree at most R. For a constant use a = 1. Adding these identities proves the claim. These two displayed equations are the replacement rules we need.
15
Step 3: express the columns using ρ coordinates. Choose ρ independent columns ci1 , . . . , ciρ from c0 , . . . , cN . They form a basis of the column space. Introduce formal variables y1 , . . . , yρ , one for each chosen column. For each i, record the coefficients expressing ci in this basis in a linear polynomial: ci =
ρ X
γij cij ,
Li (y) =
j=1
ρ X
γij yj ,
y = (y1 , . . . , yρ ).
j=1
For a chosen basis column its own coordinate is one and the others are zero, so Lij (y) = yj . For example, suppose ρ = 2, columns c0 , c2 form a basis, and c1 = 3c0 + 2c2 . Then L0 (y) = y1 ,
L2 (y) = y2 ,
L1 (y) = 3y1 + 2y2 .
These polynomials simply copy the coefficients of the column expressions. The choice in this example is illustrative: in general column zero may or may not be among the chosen columns. Next we need formulas for these chosen coordinates using the available weight forms. This will ensure that polynomials of degree at most R in the new coordinates are allowed as weights. The P first ρ combinations dj = i (2j−1 t)i ci are another basis, by our choice of t. Express each chosen actual column in that basis: cij =
ρ X
ujs ds ,
wj (b) =
s=1
ρ X
ujs ℓs (b),
w(b) = (w1 (b), . . . , wρ (b)).
s=1
Here yj is a formal variable used to write polynomials, whereas wj (b) is a specific field value for each assignment b. We evaluate polynomials in y at y = w(b) throughout the proof. Replacing every bi in the formula for wj (b) by the column ci gives exactly cij . It follows that the coefficients of bi − Li (w(b)) give a column relation. The rules in Step 2 therefore apply to each of these differences. The values wj (b) need not be Boolean. They are built from linear combinations of the weight forms, not by taking bits of b. Likewise, bi = Li (w(b)) need not hold pointwise. The equations in Step 2 say precisely where these replacements are valid. Step 4: justify replacements in a weighted quadratic. Let g(x0 , . . . , xN ) be any polynomial of degree at most two and let H be any polynomial of degree at most R in R variables. We claim X b
λb g(v(b))H(ℓ(b)) =
X
λb g L0 (w(b)), . . . , LN (w(b)) H(ℓ(b)).
(17)
b
The weight H(ℓ(b)) is the same on both sides. Only the inputs to g have been replaced. Constants in g remain constants. The occurrence of v(b) simply means that the zeroth input of g is evaluated at b0 = 1. Here is the proof, including the degree bounds. For a quadratic monomial, use the identity bi bj − Li (w(b))Lj (w(b)) = (bi − Li (w(b)))bj + Li (w(b))(bj − Lj (w(b))). Multiply by H(ℓ(b)) and sum with coefficients λb . Both terms vanish by (15): the other factor is a linear combination of the original bk , and deg H ≤ R. A linear monomial is treated with the same rule and a = 1; a constant needs no change. Adding these monomial identities proves (17). We will use weights that are polynomials in the new coordinates. Given F (y) of degree at most R, choose H so that H(ℓ(b)) = F (w(b)), by substituting the formulas defining wj . Since each wj is a linear combination of the ℓs , this H still has degree at most R. Equation (17) therefore allows us to replace g while keeping the multiplier F (w(b)) unchanged. 16
For an input equation, use the polynomial g(x0 , . . . , xN ) = qs (x1 , . . . , xN ), which simply ignores its zeroth argument. For a Boolean identity, use g = x2i − xi ; the original value is zero also when i = 0, because b0 = 1. Applying this replacement to these two kinds of polynomial gives, for every F with deg F ≤ R, X
λb qs L1 (w(b)), . . . , LN (w(b)) F (w(b)) = 0,
(18)
b
X
λb Li (w(b))2 − Li (w(b)) F (w(b)) = 0,
0 ≤ i ≤ N.
(19)
b
The first line uses the imposed equation tests; the second uses identities true at each original assignment. In particular, since Lij (y) = yj , the second line gives X
λb wj (b)2 − wj (b) F (w(b)) = 0,
deg F ≤ R.
(20)
b
This is the exact sense in which the new coordinates obey Boolean identities inside the weighted sums. We have not assumed that their individual values are bits. Step 5: use the selectors on just ρ coordinates. We can now use the selectors from Section 4.2, this time on the formal variables y1 , . . . , yρ . Before doing so we explain why these selectors can describe the sums, even though w(b) need not be Boolean. For any polynomial f (y) of degree at most R + 2, repeatedly replace every power yjk , k ≥ 2, by yjk−1 . Each change is a multiple of yj2 − yj , because yjk − yjk−1 = (yj2 − yj )yjk−2 . Including any other factors of the monomial, the multiplier has degree at most (R + 2) − 2 = R. P Equation (20) therefore shows that these changes preserve the sum b λb f (w(b)). Call the result fml . It is a multilinear polynomial: every variable has exponent at most one. It has the same values as f on {0, 1}ρ . Every multilinear polynomial equals the sum of its Boolean values times the corresponding selectors. In one variable this is a + cy = a(1 − y) + (a + c)y; applying this identity to one variable after another gives X fml (y) = f (e)Ee (y). e∈{0,1}ρ
Consequently, if we define the selector weights µe =
X
e ∈ {0, 1}ρ ,
λb Ee (w(b)),
b
then for every f of degree at most R + 2 we have X b
X
λb f (w(b)) =
µe f (e).
(21)
e∈{0,1}ρ
Thus the sums we need can be computed using only 2ρ field weights on a Boolean cube. This conclusion is about those sums; it is not a claim that the original coefficients λb have small support. Fix a cube point e ∈ {0, 1}ρ . It proposes the assignment (L1 (e), . . . , LN (e)). 17
This proposal must fail. Either some Li (e) is not a bit, so Li (e)2 − Li (e) ̸= 0, or all are bits and one of the input equations fails. Therefore some polynomial Q(y) from the list {Li (y)2 − Li (y) : 1 ≤ i ≤ N } ∪ {qs (L1 (y), . . . , LN (y)) : 1 ≤ s ≤ J} has Q(e) ̸= 0. Equations (18)–(19) apply with multiplier Ee , since deg Ee = ρ ≤ R. They give X
0=
λb Q(w(b))Ee (w(b)) = µe Q(e).
b
The second equality is (21), valid because deg(QEe ) ≤ ρ + 2 ≤ R + 2; the selector kills every other cube point. Since Q(e) ̸= 0, it follows that µe = 0. This holds for every e. Equation (21) now says X
λb f (w(b)) = 0
for every deg f ≤ R + 2.
(22)
b
Step 6: return to the entries of the matrix. An entry of any block at the fixed sample is P b λb bi bj H(ℓ(b)) for a weight monomial H of degree at most R. Equation (17) changes this to X
λb Li (w(b))Lj (w(b))H(ℓ(b)).
b
To apply (22), we must express the remaining factors ℓs (b) in terms of w(b) as well. For each such factor, make the replacement ℓs (b) =
N X
(2s−1 t)k bk
7−→
k=0
N X
(2s−1 t)k Lk (w(b)).
k=0
The difference is a linear combination of bk − Lk (w(b)), so its coefficients give a column relation. All the other factors, including ones already replaced, are polynomials in the original ℓs : each wj is a linear combination of those forms. The product of the other factors has degree at most 2 + (R − 1) = R + 1 in these forms. Equation (16) therefore justifies each replacement inside the sum. P After these replacements the entry has the form b λb f (w(b)), where f is a polynomial in ρ variables of degree at most R + 2. It is zero by (22). All the blocks at this sample are zero, contradicting Step 1. The rank lower bound is proved. Why we kept weights through degree R. The selectors above have degree ρ ≤ R, and multiplying by a quadratic uses degree at most R + 2. This is exactly what a degree-R weight times a bit pair supplies. This degree allowance lets the proof treat all columns, including column zero, in the same way. The proof applies whether or not column zero is one of the basis columns. The proof gives an explicit short list of candidate assignments. Given a nonzero matrix in S of rank ρ ≤ R, choose any basis from its actual columns and compute the polynomials Li as in Step 3. These polynomials depend only on that column basis. Enumerate the 2ρ tuples e and test each proposal (L1 (e), . . . , LN (e)) for Boolean entries and the input equations. At least one proposal must pass: if every proposal failed, the selector argument would again force the nonzero block to be zero. Thus the small coordinate space has a concrete purpose—it gives a short list containing a satisfying assignment. The sample and the weighted sums prove that the list works; constructing the list itself requires only the column basis. 18
4.6
Compute the space without listing all assignments
The definition of V used 2N matrices A(b). We now give an exact algorithm that keeps only a basis at each stage. The key is that setting one more bit to zero or one acts linearly on the full matrix encoding. During this algorithm, temporarily set the bits not yet assigned to zero. Suppose the next bit is bi , and we change it from zero to ε ∈ {0, 1}. At each sample, this changes a weight form by ℓj,t 7−→ ℓj,t + ε(2j−1 t)i . For example a square changes by ℓ2 7→ ℓ2 + 2cℓ + c2 for the appropriate constant c. In general, the binomial formula writes every updated weight of degree at most R as a linear combination of the old weights of degree at most R. This is why the list includes all lower degrees. In the left vector in (5), the coordinates are h(b)bk for all weights h and 0 ≤ k ≤ N . For k ̸= i, the bit bk does not change, so the updated coordinate is the same linear combination of the old coordinates h(b)bk . For k = i, its new value is ε times the updated weight, which is a linear combination of the coordinates h(b)b0 = h(b). Thus there is an explicit linear map Ui,ε on the left vector that performs this update for every current partial assignment. There is also a linear map Vi,ε on the right vector: it leaves other coordinates alone and replaces coordinate i by ε times coordinate zero. The whole matrix therefore updates by the linear map T A 7−→ Ui,ε AVi,ε .
Start from the one-dimensional span of the encoding with all bits zero. At step i, apply both maps, for ε = 0 and 1, to a basis of the current space. Keep a basis of the span of the resulting matrices, using Gaussian elimination on their lists of entries. Inductively this is exactly the span of all encodings of the first i bits, with the others temporarily zero: linear maps take a spanning set to a spanning set of its image. After N steps the space is exactly V. To make the output deterministic and ordered, fix the numerical order of samples, lexicographic order of exponent tuples, and row-by-row order of matrix entries. In every Gaussian elimination use the first available nonzero pivot in these orders and retain the resulting basis in pivot order. The basis size never exceeds the number m(N + 1) of entries in a rectangular matrix. Every transition and every elimination therefore takes polynomially many field operations in N and m. Intersecting with the constraints in (7) is another homogeneous linear system, giving an ordered basis of S. A satisfying assignment’s matrix is explicit, so its coordinates in that basis are found by one further linear solve. Appending zero columns requires no additional argument. All operations have bit complexity polynomial also in J and log p. Finally, ! 2R m = (N + 1)(2N R + 1) = O(N 2 R4R ). R For R = ⌊log2 N ⌋ we have 4R ≤ N 2 , hence m = O(N 4 log N ). It follows that log m = O(log N ), while the NO-case rank bound R + 1 is greater than log2 N . Thus that bound is Ω(log m), as claimed in Proposition 4.3.
4.7
Putting everything together
We now prove our theorem on NP hardness of approximation for MinRank.
19
Proof of Theorem 3.1. Encode the circuit by the Boolean quadratic equations of Section 4.1, and take R = ⌊log N ⌋. Proposition 4.3 supplies the matrix space, the ordered basis algorithm, and the rank gap. A satisfying witness determines the assignment b, hence the two factors of A(b) in (5). The linear solve in Section 4.6 gives its coefficients in the output basis. The padded right factor is Boolean with weight at most N + 1. Finally, (14) depends only on N and is polynomially bounded, so it can be computed before choosing the prime. This proves all the stated guarantees. Corollary 4.4 (Growing-prime hardness). For some f (m) = Θ(log m), it is NP-hard under randomized reductions to distinguish a matrix space containing a nonzero uv T with v ∈ {0, 1}m from one whose every nonzero matrix has rank at least f (m), over primes p = Θ(2m ). The reduction can be zero-error expected polynomial time, or bounded polynomial time with negligible error probability. Proof. Use N = Θ(|φ|) in Theorem 3.1, determine m, and sample a prime in [2m , 2m+1 ). Prime density in this interval is Ω(1/m), and primality is decidable in polynomial time [AKS04]. Thus repeated uniform sampling takes expected polynomial time and always outputs a valid prime. Capping the number of attempts at a sufficiently large polynomial gives negligible failure probability. The formula (14) gives m > N and m > 2N R, so all accepted primes satisfy p > max{2N , 2N R}. Finally, m = N O(1) and m ≥ N , so the gap R + 1 is Ω(log m). Choose f (2) = 2; on a truncated sampler’s failure, output the fixed valid NO instance spanF5 {I2 }, where I2 is the 2 × 2 identity matrix. This gives the bounded-time version. The Boolean factor meets any polynomial coordinate bound.
References [AK14]
Per Austrin and Subhash Khot. A simple deterministic reduction for the gap minimum distance of code problem. IEEE Transactions on Information Theory, 60(10):6636–6645, 2014. https://doi.org/10.1109/TIT.2014.2340869.
[AKS04]
Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Annals of Mathematics, 160(2):781–793, 2004. https://doi.org/10.4007/annals.2004.160.781.
[BGLR25] Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee, and Xuandi Ren. Inapproximability of finding sparse vectors in codes, subspaces, and lattices. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science, pages 1295–1303, 2025. https://doi.org/10.1109/FOCS63196.2025.00068. [BIJ+ 20]
James Bartusek, Yuval Ishai, Aayush Jain, Fermi Ma, Amit Sahai, and Mark Zhandry. Affine determinant programs: A framework for obfuscation and witness encryption. In 11th Innovations in Theoretical Computer Science Conference, volume 151 of Leibniz International Proceedings in Informatics, pages 82:1–82:39, 2020. https://doi.org/10.4230/LIPIcs.ITCS.2020.82.
[BIK+ 96]
Paul Beame, Russell Impagliazzo, Jan Krajíček, Toniann Pitassi, and Pavel Pudlák. Lower bounds on Hilbert’s Nullstellensatz and propositional proofs. Proceedings of the London Mathematical Society, 73(1):1–26, 1996. https://doi.org/10.1112/plms/s3-73.1.1.
[BIL+ 19]
Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, and Frank-Olaf Schreyer. Variety membership testing, algebraic natural proofs, and geometric complexity theory. arXiv:1911.02534, 2019. https://arxiv.org/abs/1911.02534. 20
[BIOW20] Ohad Barta, Yuval Ishai, Rafail Ostrovsky, and David J. Wu. On succinct arguments and witness encryption from groups. In Advances in Cryptology – CRYPTO 2020, pages 776–806, 2020. https://doi.org/10.1007/978-3-030-56784-2_26. [Bus98]
Samuel R. Buss. Lower bounds on Nullstellensatz proofs via designs. In Paul Beame and Samuel R. Buss, editors, Proof Complexity and Feasible Arithmetics, volume 39 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 59–71. American Mathematical Society, 1998. https://doi.org/10.1090/dimacs/039/04.
[CEI96]
Matthew Clegg, Jeffery Edmonds, and Russell Impagliazzo. Using the Groebner basis algorithm to find proofs of unsatisfiability. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, pages 174–183. ACM, 1996. https://doi.org/10.1145/237814.237860.
[CMV26]
Rohit Chatterjee, Changrui Mu, and Prashant Nalini Vasudevan. Public-key encryption from the MinRank problem. In Advances in Cryptology – EUROCRYPT 2026, volume 16544 of Lecture Notes in Computer Science, pages 449–480, 2026. https://doi.org/10.1007/978-3-032-25327-9_16.
[Cou01]
Nicolas T. Courtois. Efficient zero-knowledge authentication based on a linear algebra problem MinRank. In Advances in Cryptology – ASIACRYPT 2001, volume 2248 of Lecture Notes in Computer Science, pages 402–421, 2001. https://doi.org/10.1007/3-540-45682-1_24.
[CV22]
Gwangbae Choi and Serge Vaudenay. Towards witness encryption without multilinear maps: Extractable witness encryption for multi-subset sum instances with no small solution to the homogeneous problem. In Information Security and Cryptology – ICISC 2021, 2022. https://doi.org/10.1007/978-3-031-08896-4_2.
[FNV17]
Antonio Faonio, Jesper Buus Nielsen, and Daniele Venturi. Predictable arguments of knowledge. In Public-Key Cryptography – PKC 2017, volume 10174 of Lecture Notes in Computer Science, pages 121–150, 2017. https://doi.org/10.1007/978-3-662-54365-8_6.
[FSS14]
Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka. Hitting sets for multilinear read-once algebraic branching programs, in any order. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC ’14, pages 867–875. ACM, 2014. https://doi.org/10.1145/2591796.2591816.
[GGH+ 13] Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 40–49, 2013. https://doi.org/10.1109/FOCS.2013.13. [GGSW13] Sanjam Garg, Craig Gentry, Amit Sahai, and Brent Waters. Witness encryption and its applications. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pages 467–476, 2013. https://eprint.iacr.org/2013/258. [GHK+ 25] Sanjam Garg, Mohammad Hajiabadi, Dimitris Kolonelos, Abhiram Kothapalli, and Guru-Vamsi Policharla. A framework for witness encryption from linearly verifiable 21
SNARKs and applications. In Advances in Cryptology – CRYPTO 2025, pages 504–539, 2025. https://doi.org/10.1007/978-3-032-01881-6_16. [GK16]
Venkatesan Guruswami and Swastik Kopparty. Explicit subspace designs. Combinatorica, 36(2):161–185, 2016. https://doi.org/10.1007/s00493-014-3169-1.
[GLW14]
Craig Gentry, Allison Lewko, and Brent Waters. Witness encryption from instance independent assumptions. In Advances in Cryptology – CRYPTO 2014, pages 426–443, 2014. https://eprint.iacr.org/2014/273.
[GRT26]
Venkatesan Guruswami, Xuandi Ren, and Shaoxuan Tang. Strong inapproximability for a promise rank problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026), volume 392 of Leibniz International Proceedings in Informatics, pages 19:1–19:22, 2026. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2026.19.
[GZ16]
Philippe Gaborit and Gilles Zémor. On the hardness of the decoding and the minimum distance problems for rank codes. IEEE Transactions on Information Theory, 62(12):7245–7252, 2016. https://doi.org/10.1109/TIT.2016.2616127.
[JLS21]
Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 60–73, 2021. https://doi.org/10.1145/3406325.3451093.
[JLS22]
Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from LPN over Fp , DLIN, and PRGs in NC0 . In Advances in Cryptology – EUROCRYPT 2022, volume 13275 of Lecture Notes in Computer Science, pages 670–699, 2022. https://doi.org/10.1007/978-3-031-06944-4_23.
[KS17]
Subhash Khot and Rishi Saket. Hardness of coloring 2-colorable 12-uniform Ω(1) hypergraphs with 2(log n) colors. SIAM Journal on Computing, 46(1):235–271, 2017. https://doi.org/10.1137/15100240X.
[LM09]
Monique Laurent and Bernard Mourrain. A generalized flat extension theorem for moment matrices. Archiv der Mathematik, 93(1):87–98, 2009. https://doi.org/10.1007/s00013-009-0007-6.
[LMP25]
Yanyi Liu, Noam Mazor, and Rafael Pass. On witness encryption and laconic zero-knowledge arguments. In Advances in Cryptology – CRYPTO 2025, pages 429–461, 2025. https://eccc.weizmann.ac.il/report/2024/194/.
[Mas69]
James L. Massey. Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory, 15(1):122–127, 1969. https://doi.org/10.1109/TIT.1969.1054260.
[MM00]
Ryutaroh Matsumoto and Shinji Miura. On the Feng-Rao bound for the L-construction of algebraic geometry codes. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E83-A(5):923–926, 2000. https://rmatsumoto.org/repository/e83-a_5_923.pdf.
22
[Moo96]
Eliakim Hastings Moore. A two-fold generalization of Fermat’s theorem. Bulletin of the American Mathematical Society, 2(7):189–199, 1896. https://doi.org/10.1090/S0002-9904-1896-00337-2.
[Mou18]
Bernard Mourrain. Polynomial-exponential decomposition from moments. Foundations of Computational Mathematics, 18(6):1435–1492, 2018. https://doi.org/10.1007/s10208-017-9372-x.
[RS05]
Ran Raz and Amir Shpilka. Deterministic polynomial identity testing in non-commutative models. Computational Complexity, 14(1):1–19, 2005. https://doi.org/10.1007/s00037-005-0188-8.
[RVV24]
Seyoon Ragavan, Neekon Vafa, and Vinod Vaikuntanathan. Indistinguishability obfuscation from bilinear maps and LPN variants. In Theory of Cryptography – TCC 2024, volume 15367 of Lecture Notes in Computer Science, pages 3–36, 2024. https://doi.org/10.1007/978-3-031-78023-3_1.
[SGS21]
Gili Schul-Ganz and Gil Segev. Generic-group identity-based encryption: A tight impossibility result. In 2nd Conference on Information-Theoretic Cryptography, Leibniz International Proceedings in Informatics, 2021. https://doi.org/10.4230/LIPIcs.ITC.2021.26.
[Sho97]
Victor Shoup. Lower bounds for discrete logarithms and related problems. In Advances in Cryptology – EUROCRYPT 1997, pages 256–266, 1997. https://www.shoup.net/papers/dlbounds1.pdf.
[WL13]
Baofeng Wu and Zhuojun Liu. Linearized polynomials over finite fields revisited. Finite Fields and Their Applications, 22:79–100, 2013. https://doi.org/10.1016/j.ffa.2013.03.003.
[ZHC+ 26] Junyi Zhang, Xinjie He, Hyunsik Chae, Ethan Ji, Eric Jiang, Rushil Raghavan, Yiwen Kou, Alex Taylor, Kai-Wei Chang, Raghu Meka, Violet Peng, Amit Sahai, Terence Tao, and Wei Wang. Ucla moonshot harness, 2026.
23