Linear-only vector encryption ⇒ Designated-verifier SNARG (lattice-based)

CRS model · BISW17

Statement

If linear-only vector encryption exists — a generalization of BCIOP13’s linear-only encryption in which the prover is constrained to evaluate a single linear function on all query vectors simultaneously, and which BISW17 conjecture variants of Regev encryption satisfy — compiling a linear PCP with it gives designated-verifier preprocessing SNARGs for $\mathbf{NP}$, plausibly post-quantum, with argument size quasilinear in $\lambda$. Together with new statistically sound linear PCPs over small fields, a further extension of the method gives the first SNARG, from any assumption, that is quasi-optimal in both succinctness and prover overhead, the latter polylogarithmic in $\lambda$ — BISW17.

Notes

• A lattice-based designated-verifier zk-SNARK from square span programs has proofs of 5 LWE encodings — GMNO18.
• Quasi-optimal SNARGs can also be built from linear multi-prover interactive proofs — BISW18.
• The scalar notion, over a field of super-polynomial size, compiles linear interactive proofs: Linear-only encryption ⇒ Designated-verifier SNARG — BCIOP13.