A Designated-Verifier SNARG with One Group Element and tau + o(tau) Bits

–

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

Generic Group ModelProof Size Lower BoundsSnarks

A designated-verifier SNARG lets a prover convince one particular verifier, holding a secret verification state, that a circuit is satisfiable — with a proof far shorter than the witness. In the generic group model the source brings the proof down to a single group element plus a number of bits proportional to the soundness level, and with a random oracle down to \(695\) bits for \(2^{-80}\) soundness at \(128\)-bit security, roughly half the best pairing-based SNARG. Two sources of slack in that count are identified and not removed. Fix both and the additive term should fall to about \(340\) bits — which is the source’s numbered Conjecture 1.3.

View PDF · LaTeX source · Formal statement — not yet formalized

The model (the source’s Definitions 3.2 and 3.4). Shoup’s generic group model: the oracle holds a random bijection from a label space to \((\mathbb{Z}_{p'},+)\), all parties get the label of \(1\), and the oracle adds two labels. A dv-SNARG for a relation \(R\) is \((\mathsf{Setup}, \mathsf{P}, \mathsf{V})\) with oracle access, where \(\mathsf{Setup}(1^n)\) outputs a CRS and a secret verification state, \(\mathsf{P}\) outputs a proof of length \(\ell\), and \(\mathsf{V}\) outputs a bit; completeness and adaptive soundness are as usual, soundness quantified over provers making at most \(t\) oracle queries, and succinctness asks \(|\mathsf{pf}| = o(|w|)\).

Conjecture (the source’s Conjecture 1.3, verbatim). Let \(\mathbb{G} = \mathbb{G}_\lambda\) be a generic group and \(\tau\) a soundness parameter. There exists a dv-SNARG for proving the satisfiability of a Boolean circuit of size \(s\) with soundness error \(2^{-\tau + \log\log\lambda} + O(t^2/2^\lambda)\) against \(t\)-query adversaries, proof size \(1\) \(\mathbb{G}\)-element and \(\tau + o(\tau)\) additional bits, and CRS size \(O(\tau s)\) \(\mathbb{G}\)-elements.

What the source’s own theorems give. Theorem 1.1: soundness \(2^{-\tau} + O(t^2 2^{-\lambda})\), proof one \(\mathbb{G}\)-element plus \(O(\tau)\) bits with a large hidden constant (\(56\tau\) bits if the CRS is allowed to be \(O(\tau s^2)\)), CRS \(O(\tau s)\). Theorem 1.2, additionally using a random oracle for collision resistance: proof one \(\mathbb{G}\)-element, one hash output and \(\lceil 2\tau\log p/(\log p - \Theta(1))\rceil\) bits, CRS \(O(\tau s \cdot \mathrm{poly}(p))\).

No random oracle. The conjecture lives in the generic group model alone, with a linear CRS. That is what separates it from both theorems: the better concrete bound buys its tighter malleability analysis with a random oracle, and the oracle-free theorem pays \(O(\tau)\) bits with a large constant.

The soundness term is unusual and is the source’s. The \(\log\log\lambda\) in the exponent is printed in the paper; the conjecture therefore allows a \(\log\lambda\) multiplicative loss over \(2^{-\tau}\), and a construction achieving \(2^{-\tau}\) exactly would be stronger than what is asked.

Sources

View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized

Open. The source decomposes the conjecture into two ingredients and leaves both open, presenting Conjecture 1.3 as what they would jointly buy.

Ingredient one: a tighter malleability analysis. The proof size is decided by how much malleability a generic-group adversary has against packed ElGamal, and the source says “we believe that our analysis is quite loose, and conjecture that an even a slightly simpler construction can achieve a better level of soundness”, giving an explicit candidate it conjectures reaches \(2^{-\tau}\) with one group element and about \(2\tau\) bits.

Ingredient two: a practical linear PCP with \(\mu \approx 1\). The source’s construction is insensitive to the number of LPCP queries but sensitive to the ratio \(\mu\) between the total bit-length of the answers and \(\tau\); its LPCPs have \(\mu \approx 2\), which is the \(2\tau\) term. LPCPs with \(\mu \approx 1\) follow from optimal \(\mathrm{MAXLIN}\) inapproximability, but have non-negligible completeness error and, the source judges, “seem practically infeasible”; eliminating that error via amortized-query-complexity PCPs and universal factor graphs looks practically infeasible too. The source leaves designing practical LPCPs with \(\mu \approx 1\) open.

Checked against the literature, 2026-08-25. No proof, refutation or improvement found. Targeted check, not an exhaustive sweep.

Why designated verification is the right frame. In every dv-SNARG the CRS can be reused indefinitely as long as the prover does not learn (too often) whether the verifier accepted a badly formed proof, which is good enough for long-lived prover–verifier relationships. The source’s schemes are not reusable in the strong sense where the prover sees every accept/reject decision, and achieving that is a separate open question it records.

Neighbouring open problems, not this one. The source lists two more: runtimes, where it conjectures separately (its Conjecture 3.11) that its LPCP is \(O(\lambda p^2 s)\)-bounded, which would let a random-walk concentration bound cut verification time to grow with \(s^{1/4}\); and full CRS reusability. Both are distinct statements.

What a reviewer should be suspicious of, in order. First, whether a claimed construction really avoids the random oracle — Theorem 1.2’s improvement is entirely the oracle’s doing, so an oracle-using scheme at \(\tau + o(\tau)\) bits does not settle this. Second, whether the CRS stays \(O(\tau s)\) group elements: the source can already reach \(56\tau\) bits by letting the CRS go quadratic. Third, the \(\log\log\lambda\) term, which a reader may take for a typo and inadvertently prove a stronger statement — worth reporting as such if so.