nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

On the (In)security of Kilian-Based SNARGs

verfasst von : James Bartusek, Liron Bronfman, Justin Holmgren, Fermi Ma, Ron D. Rothblum

Erschienen in: Theory of Cryptography

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The Fiat-Shamir transform is an incredibly powerful technique that uses a suitable hash function to reduce the interaction of general public-coin protocols. Unfortunately, there are known counterexamples showing that this methodology may not be sound (no matter what concrete hash function is used). Still, these counterexamples are somewhat unsatisfying, as the underlying protocols were specifically tailored to make Fiat-Shamir fail. This raises the question of whether this transform is sound when applied to natural protocols.

One of the most important protocols for which we would like to reduce interaction is Kilian’s four-message argument system for all of \(\mathsf {NP}\), based on collision resistant hash functions (\(\mathsf {CRHF}\)) and probabilistically checkable proofs (\(\mathsf {PCP}\)s). Indeed, an application of the Fiat-Shamir transform to Kilian’s protocol is at the heart of both theoretical results (e.g., Micali’s CS proofs) as well as leading practical approaches of highly efficient non-interactive proof-systems (e.g., \(\mathsf {SNARK}\)s and \(\mathsf {STARK}\)s).

In this work, we show significant obstacles to establishing soundness of (what we refer to as) the “Fiat-Shamir-Kilian-Micali” (\(\mathsf {FSKM}\)) protocol. More specifically:

We construct a (contrived) \(\mathsf {CRHF}\) for which \(\mathsf {FSKM}\) is unsound for a very large class of \(\mathsf {PCP}\)s and for any Fiat-Shamir hash function. The collision-resistance of our \(\mathsf {CRHF}\) relies on very strong but plausible cryptographic assumptions. The statement is “tight” in the following sense: any \(\mathsf {PCP}\) outside the scope of our result trivially implies a \(\mathsf {SNARK}\), eliminating the need for \(\mathsf {FSKM}\) in the first place.
Second, we consider a known extension of Kilian’s protocol to an interactive variant of \(\mathsf {PCP}\)s called probabilistically checkable interactive proofs (\(\mathsf {PCIP})\) (also known as interactive oracle proofs or \(\mathsf {IOP}\)s). We construct a particular (contrived) \(\mathsf {PCIP}\) for \(\mathsf {NP}\) for which the \(\mathsf {FSKM}\) protocol is unsound no matter what \(\mathsf {CRHF}\) and Fiat-Shamir hash function is used. This result is unconditional (i.e., does not rely on any cryptographic assumptions).

Put together, our results show that the soundness of \(\mathsf {FSKM}\) must rely on some special structure of both the \(\mathsf {CRHF}\) and \(\mathsf {PCP}\) that underlie Kilian’s protocol. We believe these negative results may cast light on how to securely instantiate the \(\mathsf {FSKM}\) protocol by a synergistic choice of the \(\mathsf {PCP}\), \(\mathsf {CRHF}\), and Fiat-Shamir hash function.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Linear-Size Constant-Query IOPs for Delegating Computation

Nächstes Kapitel Incrementally Verifiable Computation via Incremental PCPs

A succinct decommitment to the value \(\pi _{i_j}\) can be accomplished by having \(\mathcal {P}_{\mathsf {Kilian}}\) reveal the hash values of all vertices in the tree that are either on, or adjacent to, the path from \(\pi _{i_j}\) to the root in the Merkle tree.

\(\mathsf {PCIP}\)s are also called interactive oracle proofs \(\mathsf {IOP}\)s.

The work of [BCPR14] showed that if indistinguishability obfuscation exists, then \(\mathsf {SNARK}\)s where extraction holds with respect to arbitrary unbounded polynomial length auxiliary input do not exist. We therefore rely on a version of the [BCI+13] knowledge of exponent assumption which only requires extraction to hold with respect to auxiliary input from a “benign” distribution (e.g. a uniform distribution); a similar approach was taken in [CFH+15, FFG+16, Gro16, BCC+17]. We are able to rely on this relaxed version since the auxiliary input in our construction essentially just consists of the key for some arbitrary collision resistant hash function. We discuss this issue in further detail in the full version [BBH+19].

Note that Håstad’s \(\mathsf {PCP}\) only has constant soundness. Nevertheless, the attack can be generalized to the sequential repetition of Håstad’s \(\mathsf {PCP}\) as long as the sampler \(\mathcal {S}\) generates random query sets.

One would assume that a random choice of \(\mathsf {FS}\) hash function from the collection would produce a uniformly random string for the verifier. However, since we want to deal with arbitrary candidate \(\mathsf {FS}\) hash functions, we cannot assume that this is the case.

[ALM+98]

Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM (JACM) 45(3), 501–555 (1998)MathSciNetCrossRef

[Bar01]

Barak, B.: How to go beyond the black-box simulation barrier. In: FOCS (2001)

[BBB+18]

Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: Short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy, pp. 315–334. IEEE Computer Society Press, May 2018

[BBC+17]

Ben-Sasson, E., et al.: Computational integrity with a public random string from quasi-linear PCPs. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 551–579. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_19

[BBH+19]

Bartusek, J., Bronfman, L., Holmgren, J., Ma, F., Rothblum, R.D.: On the (in)security of kilian-basen snargs. Cryptology ePrint Archive, Report 2019/997 (2019. https://eprint.iacr.org/2018/997

[BBHR18a]

Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Fast reed-solomon interactive oracle proofs of proximity. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, 9–13 July 2018, pp. 14:1–14:17 (2018)

[BBHR18b]

Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Scalable, transparent, and post-quantum secure computational integrity. IACR Cryptology ePrint Archive 2018, 46 (2018)

[BCC+17]

Bitansky, N., et al.: The hunting of the SNARK. J. Cryptol. 30(4), 989–1066 (2017)MathSciNetCrossRef

[BCCT13]

Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKS and proof-carrying data. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th ACM STOC, pp. 111–120. ACM Press, June 2013

[BCI+13]

Bitansky, N., Chiesa, A., Ishai, Y., Paneth, O., Ostrovsky, R.: Succinct non-interactive arguments via linear interactive proofs. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 315–333. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_18CrossRef

[BCPR14]

Bitansky, N., Canetti, R., Paneth, O., Rosen, A:. On the existence of extractable one-way functions. In: Shmoys, D.B. (eds.) 46th ACM STOC, pp. 505–514. ACM Press, May/June 2014

[BCR+19]

Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., Ward, N.P.: Aurora: transparent succinct arguments for R1CS. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 103–128. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17653-2_4CrossRef

[BCS16]

Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 31–60. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53644-5_2CrossRef

[BG08]

Barak, B., Goldreich, O.: Universal arguments and their applications. SIAM J. Comput. 38(5), 1661–1694 (2008)MathSciNetCrossRef

[BGG17]

Bowe, S., Gabizon, A., Green, M.D.: A multi-party protocol for constructing the public parameters of the pinocchio zk-SNARK. Cryptology ePrint Archive, Report 2017/602 (2017). http://eprint.iacr.org/2017/602

[BGH+05]

Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Short PCPs verifiable in polylogarithmic time. In: 20th Annual IEEE Conference on Computational Complexity (CCC 2005), San Jose, CA, USA, 11–15 June 2005, pp. 120–134 (2005)

[BGH+06]

Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput. 36(4), 889–974 (2006)MathSciNetCrossRef

[BGM17]

Bowe, S., Gabizon, A., Miers, I.: Scalable multi-party computation for zk-SNARK parameters in the random beacon model. Cryptology ePrint Archive, Report 2017/1050 (2017). http://eprint.iacr.org/2017/1050

[BR94]

Bellare, M., Rogaway, P.: Entity authentication and key distribution. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 232–249. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2_21CrossRef

[CCH+19]

Canetti, R., et al.: Fiat-Shamir: from practice to theory (2019)

[CCRR18]

Canetti, R., Chen, Y., Reyzin, L., Rothblum, R.D.: Fiat-Shamir and correlation intractability from strong KDM-secure encryption. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 91–122. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_4CrossRef

[CFH+15]

Costello, C., et al.: Geppetto: versatile verifiable computation. In: 2015 IEEE Symposium on Security and Privacy, pp. 253–270. IEEE Computer Society Press, May 2015

[DR06]

Dinur, I., Reingold, O.: Assignment testers: towards a combinatorial proof of the PCP theorem. SIAM J. Comput. 36(4), 975–1024 (2006)MathSciNetCrossRef

[FFG+16]

Fiore, D., Fournet, C., Ghosh, E., Kohlweiss, M., Ohrimenko, O., Parno, B.: Hash first, argue later: adaptive verifiable computations on outsourced data. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 1304–1316. ACM Press, October 2016

[FS86]

Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12 CrossRef

[GK03]

Goldwasser, S., Kalai, Y.T.: On the (in)security of the Fiat-Shamir paradigm. In: 44th FOCS, pp. 102–115. IEEE Computer Society Press, October 2003

[Gro16]

Groth, J.: On the size of pairing-based non-interactive arguments. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 305–326. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_11CrossRef

[GW11]

Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Fortnow, L., Vadhan, S.P. (eds.) 43rd ACM STOC, pp. 99–108. ACM Press, June 2011

[Hås01]

Håstad, J.: Some optimal inapproximability results. J. ACM 48(4), 798–859 (2001)MathSciNetCrossRef

[HL18]

Holmgren, J., Lombardi, A.: Cryptographic hashing from strong one-way functions (or: one-way product functions and their applications). In: Thorup, M. (eds.) 59th FOCS, pp. 850–858. IEEE Computer Society Press, October 2018

[HR04]

Hsiao, C.-Y., Reyzin, L.: Finding collisions on a public road, or do secure hash functions need secret coins? In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 92–105. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_6CrossRef

[HW15a]

Hubacek, P., Wichs, D.: On the communication complexity of secure function evaluation with long output. In: Roughgarden, T. (eds.) ITCS 2015, pp. 163–172. ACM, January 2015

[HW15b]

Hub’avcek, P., Wichs, D.: On the communication complexity of secure function evaluation with long output. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, 11–13 January 2015, pp. 163–172 (2015)

[Kil88]

Kilian, J.: Founding cryptography on oblivious transfer. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, Illinois, USA, 2–4 May 1988, pp. 20–31 (1988)

[Kil92]

Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: 24th ACM STOC, pp. 723–732. ACM Press, May 1992

[KRR17]

Kalai, Y.T., Rothblum, G.N., Rothblum, R.D.: From obfuscation to the security of Fiat-Shamir for proofs. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 224–251. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_8CrossRef

[Mau05]

Maurer, U.: Abstract models of computation in cryptography. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 1–12. Springer, Heidelberg (2005). https://doi.org/10.1007/11586821_1CrossRefMATH

[Mic00]

Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253–1298 (2000)MathSciNetCrossRef

[Nec94]

Nechaev, V.I.: Complexity of a determinate algorithm for the discrete logarithm. Math. Notes 55(2), 165–172 (1994)MathSciNetCrossRef

[PS96]

Pointcheval, D., Stern, J.: Security proofs for signature schemes. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 387–398. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68339-9_33CrossRef

[PS19]

Peikert, C., Shiehian, S.: Noninteractive zero knowledge for NP from (plain) learning with errors. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 89–114. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_4CrossRef

[RRR16a]

Reingold, O., Rothblum, G.N., Rothblum, R.D.: Constant-round interactive proofs for delegating computation. In: Wichs, D., Mansour, Y. (eds.) 48th ACM STOC, pp. 49–62. ACM Press, June 2016

[RRR16b]

Reingold, O., Rothblum, G.N., Rothblum, R.D.: Constant-round interactive proofs for delegating computation. In: STOC, pp. 49–62. ACM (2016)

[Sho97]

Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-69053-0_18CrossRef

Titel: On the (In)security of Kilian-Based SNARGs
verfasst von: James Bartusek
Liron Bronfman
Justin Holmgren
Fermi Ma
Ron D. Rothblum
Verlag: Springer International Publishing
Buch: Theory of Cryptography
Print ISBN: 978-3-030-36032-0

Electronic ISBN: 978-3-030-36033-7

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-36033-7_20

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner