Top

Published in:

2020 | OriginalPaper | Chapter

Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs

Authors : Alex Lombardi, Vinod Vaikuntanathan

Published in: Advances in Cryptology – CRYPTO 2020

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The Fiat-Shamir transform is a methodology for compiling a (public-coin) interactive proof system for a language L into a non-interactive argument system for L. Proving security of the Fiat-Shamir transform in the standard model, especially in the context of succinct arguments, is largely an unsolved problem. The work of Canetti et al. (STOC 2019) proved the security of the Fiat-Shamir transform applied to the Goldwasser-Kalai-Rothblum (STOC 2008) succinct interactive proof system under a very strong “optimal learning with errors” assumption. Achieving a similar result under standard assumptions remains an important open question.

In this work, we consider the problem of compiling a different succinct interactive proof system: Pietrzak’s proof system (ITCS 2019) for the iterated squaring problem. We construct a hash function family (with evaluation time roughly \(2^{\lambda ^{\epsilon }}\)) that guarantees the soundness of Fiat-Shamir for this protocol assuming the sub-exponential (\(2^{-n^{1-\epsilon }}\))-hardness of the n-dimensional learning with errors problem. (The latter follows from the worst-case \(2^{n^{1-\epsilon }}\) hardness of lattice problems.) More generally, we extend the “bad-challenge function” methodology of Canetti et al. for proving the soundness of Fiat-Shamir to a class of protocols whose bad-challenge functions are not efficiently computable.

As a corollary (following Choudhuri et al., ePrint 2019 and Ephraim et al., EUROCRYPT 2020), we construct hard-on-average problems in the complexity class \(\mathbf {CLS}\subset \mathbf {PPAD}\) under the \(2^{\lambda ^\epsilon }\)-hardness of the repeated squaring problem and the \(2^{-n^{1-\epsilon }}\)-hardness of the learning with errors problem. Under the additional assumption that the repeated squaring problem is “inherently sequential”, we also obtain a Verifiable Delay Function (Boneh et al., EUROCRYPT 2018) in the standard model. Finally, we give additional PPAD-hardness and VDF instantiations demonstrating a broader tradeoff between the strength of the repeated squaring assumption and the strength of the lattice assumption.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter The Measure-and-Reprogram Technique 2.0: Multi-round Fiat-Shamir and More

next chapter Delegation with Updatable Unambiguous Proofs and PPAD-Hardness

[BBBF18] explicitly suggested this.

The two works [Pie18, Wes19] consider qualitatively different interactive argument systems. In this work, we focus on the [Pie18] protocol since (1) it has unconditional soundness and therefore is more conducive to provable Fiat-Shamir compilation, and (2) it is more closely related to \(\mathbf {PPAD}\)-hardness.

Our protocol differs very slightly from the formulation in [CHK+19b], but the difference is irrelevant to the reduction.

The prover can cheat on a pair \((\alpha , \beta )\) if and only if there exists a third message \(\gamma \) such that \((x, \alpha , \beta , \gamma )\) is accepted by the verifier.

To obtain adaptive soundness, we modify the protocol to set \(\beta = h(x, \alpha )\) and instead consider the function \(f(x, \alpha ) = \beta ^*(x, \alpha )\).

The only current known Fiat-Shamir instantiation for the [GKR08] protocol utilizes a compact correlation intractable hash family (in the sense that the hash evaluation time is independent of the time to compute the correlation function/relation) which we only know how to build from an optimal security assumption [CCH+19].

For this overview, we ignore the details of working over the group \(\mathbb {QR}_N\subset \mathbb {Z}_N^\times \) and the corresponding technical challenges.

To guarantee this property, r is selected from a range smaller than either of the prime factors of N.

See [JOP14] for a detailed discussion of the state-of-the-art on discrete logarithm algorithms.

We are not aware of prior work considering this particular time-probability trade-off, but the necessary smooth number bounds appear in [CEP83, Gra08]. Quite curiously, [CCRR18] considers the \(\mathrm {poly}(\lambda )\)-time variant of this algorithm to give evidence against the optimal hardness of computing discrete logarithms over \(\mathbb {Z}_p^\times \). That was bad for them, but for us, the non-optimal hardness is a feature!.

This second variant allows for an invocation of correlation intractability against uniform adversaries in the security proof.

Crucially, we must also bound the number of calls that can be made to the oracle to be at most \(\mathrm {poly}\log (\lambda )\) to get a meaningful result.

Albrecht, M., Bai, S., Fouque, P.-A., Kirchner, P., Stehlé, D., Wen, W.: Faster enumeration-based lattice reduction: root Hermite factor \(k^{1/(2k)}\) in time \(k^{k/8+o(k)}\). In: CRYPTO (2020)

Adleman, L.: A subexponential algorithm for the discrete logarithm problem with applications to cryptography. In: 20th Annual Symposium on Foundations of Computer Science (SFCS 1979), pp. 55–60. IEEE (1979)

Aggarwal, D., Dadush, D., Regev, O., Stephens-Davidowitz, N.: Solving the shortest vector problem in 2n time using discrete gaussian sampling. In: STOC 2015, pp. 733–742 (2015)

Ananth, P., Jain, A., Lin, H., Matt, C., Sahai, A.: Indistinguishability obfuscation without multilinear maps: new paradigms via low degree weak pseudorandomness and security amplification. In: CRYPTO (2019)

Abbot, T., Kane, D., Valiant, P.: On algorithms for nash equilibria. Unpublished Manuscript 1 (2004). http://web.mit.edu/tabbott/Public/final.pdf

Barak, B.: How to go beyond the black-box simulation barrier. In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 106–115. IEEE (2001)

Boneh, D., Bonneau, J., Bünz, B., Fisch, B.: Verifiable delay functions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 757–788. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_25. (EUROCRYPT 2018)CrossRef

Bartusek, J., Bronfman, L., Holmgren, J., Ma, F., Rothblum, R.D.: On the (in)security of Kilian-based SNARGs. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019. LNCS, vol. 11892, pp. 522–551. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36033-7_20CrossRefMATH

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

Brakerski, Z., Döttling, N., Garg, S., Malavolta, G.: Candidate iO from homomorphic encryption schemes. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 79–109. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_4CrossRef

Badrinarayanan, S., Fernando, R., Jain, A., Khurana, D., Sahai, A.: Statistical ZAP arguments. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 642–667. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_22CrossRef

Bitansky, N., Gerichter, I.: On the cryptographic hardness of local search. In: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2020)

Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_1. Journal version appears in JACM 2012CrossRef

Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: STOC 2013, pp. 575–584. ACM (2013)

Bai, S., Laarhoven, T., Stehlé, D.: Tuple lattice sieving. LMS J. Comput. Math. 19(A), 146–162 (2016)MathSciNetCrossRef

Blum, M.: How to prove a theorem so no one else can claim it. In: Proceedings of the International Congress of Mathematicians, vol. 1, pp. 2. Citeseer (1986)

Barak, B., Lindell, Y., Vadhan, S.: Lower bounds for non-black-box zero knowledge. J. Comput. Syst. Sci. 72(2), 321–391 (2006)MathSciNetCrossRef

Bitansky, N., Paneth, O., Rosen, A.: On the cryptographic hardness of finding a nash equilibrium. In: FOCS 2015. IEEE (2015)

Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and communications security, pp. 62–73. ACM (1993)

Canetti, R., Chen, Y., Holmgren, J., Lombardi, A., Rothblum, G.N., Rothblum, R.D.: Fiat-Shamir from simpler assumptions. IACR Cryptol. ePrint Arch. 2018, 1004 (2018)MATH

Canetti, R., et al.: Fiat-Shamir: from practice to theory. In: STOC 2019. ACM (2019). Merge of [CCH\(^+\)18] and [CLW18]

Canetti, R., Chen, Y., Reyzin, L.: On the correlation intractability of obfuscated pseudorandom functions. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 389–415. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49096-9_17CrossRefMATH

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

Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player nash equilibria. J. ACM (JACM) 56(3), 1–57 (2009)MathSciNetCrossRef

Canfield, E.R., Erdös, P., Pomerance, C.: On a problem of oppenheim concerning “factorisatio numerorum”. J. Number Theory 17(1), 1–28 (1983)MathSciNetCrossRef

Canetti, R., Goldreich, O., Goldwasser, S., Micali, S.: Resettable zero-knowledge. In: STOC 2000, pp. 235–244 (2000)

Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM (JACM) 51(4), 557–594 (2004)MathSciNetCrossRef

Choudhuri, A.R., Hubáček, P., Kamath, C., Pietrzak, K., Rosen, A., Rothblum, G.N.: Finding a nash equilibrium is no easier than breaking Fiat-Shamir. In: STOC 2019 (2019)

Choudhuri, A.R., Hubácek, P., Kamath, C., Pietrzak, K., Rosen, A., Rothblum, G.N.: PPAD-hardness via iterated squaring modulo a composite. Cryptology ePrint Archive, Report 2019/667, 2019 (2019)

Canetti, R., Lombardi, A., Wichs, D.: Fiat-shamir: from practice to theory, part II (non-interactive zero knowledge and correlation intractability from circular-secure FHE). IACR Cryptol. ePrint Arch. 2018, 1248 (2018)

De Feo, L., Masson, S., Petit, C., Sanso, A.: Verifiable delay functions from supersingular isogenies and pairings. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11921, pp. 248–277. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34578-5_10CrossRef

Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a nash equilibrium. SIAM J. Comput. 39(1), 195–259 (2009)MathSciNetCrossRef

Dixon, J.D.: Asymptotically fast factorization of integers. Math. Comput. 36(153), 255–260 (1981)MathSciNetCrossRef

Dwork, C., Naor, M., Reingold, O., Stockmeyer, L.: Magic functions. In: FOCS (1999)

Daskalakis, C., Papadimitriou, C.: Continuous local search. In: SODA 2011, pp. 790–804. SIAM (2011)

Ephraim, N., Freitag, C., Komargodski, I., Pass, R.: Continuous verifiable delay functions. In: EUROCRYPT 2020 (2019)

After 20 years, someone finally solved this MIT puzzle (2019)

Feige, U., Lapidot, D., Shamir, A.: Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput. 29(1), 1–28 (1999)MathSciNetCrossRef

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_12CrossRef

Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS 2013 (2013)

Goldwasser, S., Kalai, Y.T.: On the (in)security of the Fiat-Shamir paradigm. In: FOCS 2003, pp. 102–113. IEEE (2003)

Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: STOC 2008, pp. 113–122. ACM (2008)

Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. In: STOC 1985, pp. 291–304. ACM (1985)

Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM (JACM) 38(3), 690–728 (1991)MathSciNetCrossRef

Garg, S., Pandey, O., Srinivasan, A.: Revisiting the cryptographic hardness of finding a nash equilibrium. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 579–604. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_20CrossRef

Granville, A.: Smooth numbers: computational number theory and beyond. Algorithm. Number Theory Lattices Number Fields Curves Cryptograph. 44, 267–323 (2008)MathSciNetMATH

Holmgren, J., Lombardi, A.: Cryptographic hashing from strong one-way functions. In: FOCS 2018 (2018)

Hubáček , P., Yogev, E.: Hardness of continuous local search: query complexity and cryptographic lower bounds. In: SODA 2017, pp. 1352–1371. SIAM (2017)

Jain, A., Jin, Z.: Statistical zap arguments from quasi-polynomial LWE. In: EUROCRYPT 2020 (2019)

Jain, A., Lin, H., Matt, C., Sahai, A.: How to leverage hardness of constant-degree expanding polynomials over \(\mathbb{R}\) to build \(i\cal{O}\). In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 251–281. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17653-2_9CrossRef

Jain, A., Lin, H., Sahai, A.: Simplifying constructions and assumptions for \(i\cal{O}\). Cryptology ePrint Archive, Report 2019/1252 (2019)

Joux, A., Odlyzko, A., Pierrot, C.: The past, evolving present, and future of the discrete logarithm. In: Koç, Ç.K. (ed.) Open Problems in Mathematics and Computational Science, pp. 5–36. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10683-0_2CrossRefMATH

Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: STOC 1983, pp. 193–206 (1983)

Kirchner, P., Fouque, P.-A.: Time-memory trade-off for lattice enumeration in a ball. IACR Cryptol. ePrint Arch. 2016, 222 (2016)

Kalai, Y.T., Paneth, O., Yang, L.: How to delegate computations publicly. In: STOC 2019, pp. 1115–1124 (2019)

Kalai, Y., Paneth, O., Yang, L.: PPAD-hardness and delegation with unambiguous and updatable proofs. In: CRYPTO 2020 (2020)

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

Lund, C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic methods for interactive proof systems. J. ACM 39(4), 859–868 (1992)MathSciNetCrossRef

Lenstra, A.K., Lenstra Jr., H.W., Manasse, M.S., Pollard, J.M.: The number field sieve. In: STOC 1990, pp. 564–572 (1990)

Lombardi, A., Vaikuntanathan, V.: Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs. IACR Cryptology ePrint Archive, Report 2020/772 (2020). https://eprint.iacr.org/2020/772

Lombardi, A., Vaikuntanathan, V., Wichs, D.: 2-message publicly verifiable WI from (subexponential) LWE. Cryptology ePrint Archive, Report 2019/808 (2019)

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

Naor, M.: On cryptographic assumptions and challenges. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 96–109. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_6CrossRef

Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48(3), 498–532 (1994)MathSciNetCrossRef

Peikert, C.: A decade of lattice cryptography. Found. Trends Theor. Comput. Sci. 10(4), 283–424 (2016)MathSciNetCrossRef

Pietrzak, K.: Simple verifiable delay functions. In: ITCS 2019 (2018)

Pomerance, C.: Fast, rigorous factorization and discrete logarithm algorithms. In: Discrete Algorithms and Complexity, pp. 119–143. Elsevier (1987)

Peikert, C., Regev, O., Stephens-Davidowitz, N.: Pseudorandomness of ring-LWE for any ring and modulus. In: STOC 2017, pp. 461–473. ACM (2017)

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

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

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM (JACM) 56(6), 34 (2009)MathSciNetCrossRef

Description of the LCS35 time capsule crypto-puzzle (1999)

Reingold, O., Rothblum, G.N., Rothblum, R.D.: Constant-round interactive proofs for delegating computation. SIAM J. Comput. STOC16-255 (2016)

Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release crypto (1996)

Schnorr, C.P.: Efficient identification and signatures for smart cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_22CrossRef

Valiant, P.: Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 1–18. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_1CrossRefMATH

Wesolowski, B.: Efficient verifiable delay functions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 379–407. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_13CrossRef

Title: Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs
Authors: Alex Lombardi
Vinod Vaikuntanathan
Publisher: Springer International Publishing
Book: Advances in Cryptology – CRYPTO 2020
Print ISBN: 978-3-030-56876-4

Electronic ISBN: 978-3-030-56877-1

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-56877-1_22

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner