Known and conjectured succinct arguments in the ROM
Known and conjectured succinct arguments in the ROM
The ROM supports several well-known constructions of succinct arguments that can be heuristically instantiated via lightweight cryptographic hash functions, are plausibly post-quantum secure [CMS19], and have led to realizations that are useful in practice. These constructions include the Fiat–Shamir transformation [FS86], which applies to public-coin interactive proofs (IPs); the Micali transformation [Mic00], which applies to probabilistically checkable proofs (PCPs); and the BCS transformation [BCS16], which applies to public-coin interactive oracle proofs (IOPs).
Alessandro Chiesa, Peter Manohar, and Nicholas Spooner. "Succinct Arguments in the Quantum Random Oracle Model". In: Proceedings of the 1 7th Theory of Cryptography Conference. TCC '19. Available as Cryptology ePrint Archive, Report 2019 / 834.2019, pp. 1-29. Amos Fiat and Adi Shamir. "How to prove yourself: practical solutions to identification and signature problems". In: Proceedings of the 6th Annual International Cryptology Conference. CRYPTO '86. 1986, pp. 186-194. Silvio Micali. “Computationally Sound Proofs”. In: SIAM Journal on Computing 30.4 (2000). Preliminary version appeared in FOCS ’94., pp. 1253–1298. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. “Interactive Oracle Proofs”. In: Proceedings of the 14th Theory of Cryptography Conference. TCC ’16-B. 2016, pp. 31–60.
Fiat-Shamir transformation.
While useful in general, the Fiat-Shamir transformation is not useful specifically for achieving small argument size for 3SAT, because:
this transformation does not compress prover-to-verifier communication compared to the given public-coin IP; public-coin IPs with small prover-to-verifier communication for 3 SAT are unlikely [GH98].
Oded Goldreich and Johan Håstad. “On the complexity of interactive proofs with bounded communication”. In: Information Processing Letters 67.4 (1998), pp. 205–214.
Micali transformation.
The basic construction.
Start with the PCP Theorem [AS98; ALMSS98], a PCP for 3 SAT with proof length over the alphabet , query complexity , verifier randomness , and soundness error . By repeating the verifier times (and being careful with using randomness), one obtains a PCP for 3 SAT with the same proof length over the same alphabet , query complexity , verifier randomness , and soundness error . If we use this latter PCP in the Micali transformation, we obtain a SNARG with argument size , prover queries , and verifier queries
Sanjeev Arora and Shmuel Safra. “Probabilistic checking of proofs: a new characterization of NP”. In: Journal of the ACM 45.1 (1998). Preliminary version in FOCS ’92., pp. 70–122. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. “Proof verification and the hardness of approximation problems”. In: Journal of the ACM 45.3 (1998). Preliminary version in FOCS ’92., pp. 501–555.
An improved construction.
One can achieve better argument size by leveraging the fact that in the Micali transformation it is better, for argument size, to reduce the soundness error by increasing the alphabet size of the PCP rather increasing the number of queries of the PCP. Intuitively this is because one alphabet symbol of more bits can be authenticated via one Merkle path (as opposed to authenticating multiple bits in different locations via different Merkle paths). The state-of-the-art construction in this direction is due to Dinur, Harsha, and Kindler [DHK15], a PCP for 3SAT with proof length over an alphabet of size , query complexity (polyloglogn), verifier randomness , and soundness error poly . To achieve a soundness error of , now we need to repeat the verifier only times. If we use this latter PCP in the Micali transformation, we obtain a SNARG with an improved argument size of polyloglog polyloglog , prover queries poly , and verifier queries polyloglog .
Irit Dinur, Prahladh Harsha, and Guy Kindler. “Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition”. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing. STOC ’15. 2015, pp. 267–276.
An approach based on a conjecture.
The best conjectured parameters for constant-query PCPs with small soundness error are captured by the Sliding Scale Conjecture [BGLR93], which in one setting of parameters states that there exists a PCP for 3 SAT with proof length over an alphabet of size poly , query complexity , verifier randomness , and soundness error poly . Then, to achieve a soundness error of , we repeat the verifier times. If we use this latter PCP in the Micali transformation, we obtain a SNARG with an argument size of , prover queries poly , and verifier queries .
M. Bellare, S. Goldwasser, C. Lund, and A. Russell. “Efficient Probabilistically Checkable Proofs and Applications to Approximations”. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing. STOC 93. 1993, pp. 294–304.
BCS transformation.
The BCS transformation yields essentially the same argument size as the Micali transformation, except that the starting point is not a PCP, rather, a generalization thereof known as a public-coin IOP. While there are several settings of parameters achievable via IOPs and not known to be achievable by PCPs, we are not aware of any known improvements of IOPs over PCPs solely for argument size. (The main advantage of IOPs over PCPs in the literature is proof length, but argument size only depends logarithmically on it.)