nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Verifiable Delay Functions

verfasst von : Dan Boneh, Joseph Bonneau, Benedikt Bünz, Ben Fisch

Erschienen in: Advances in Cryptology – CRYPTO 2018

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

We study the problem of building a verifiable delay function (VDF). A \(\text {VDF}\)requires a specified number of sequential steps to evaluate, yet produces a unique output that can be efficiently and publicly verified. \(\text {VDF}\)s have many applications in decentralized systems, including public randomness beacons, leader election in consensus protocols, and proofs of replication. We formalize the requirements for \(\text {VDF}\)s and present new candidate constructions that are the first to achieve an exponential gap between evaluation and verification time.

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 Provable Security of (Tweakable) Block Ciphers Based on Substitution-Permutation Networks

Nächstes Kapitel Proofs of Work From Worst-Case Assumptions

A randomness extractor can then be applied to the output to map it to a uniform distribution.

The difficulty in proving indifferentiability arises because the distinguisher can query the VDF/RO construction and the RO itself separately, therefore the simulator must be able to simulate queries to the random oracle H given only access to the Random Delay Oracle. Indifferentiability doesn’t require the simulator to respond in exactly the same time, but it is still required to be efficient. This becomes an issue if the delay t is superpolynomial.

If square roots are iterated on a value x without an interleaved permutation then there is a shortcut to the iterated computation that first computes \(v = (\frac{p+1}{4})^\ell \mod p\) and then the single exponentiation \(x^v\).

http://www.ouah.org/ogay/sha2/.

This is reasonable if the evaluator has an NVIDIA Titan V GPU, which can compute up to \(10^{14}\) pipelined arithmetic operations per second (https://www.nvidia.com/en-us/titan/titan-v/).

RANDAO: A DAO working as RNG of Ethereum. Technical report (2016)

Filecoin: A decentralized storage network. Protocol Labs (2017). https://filecoin.io/filecoin.pdf

Proof of replication. Protocol Labs (2017). https://filecoin.io/proof-of-replication.pdf

Threshold relay. Dfinity (2017). https://dfinity.org/pdfs/viewer.html?file=../library/threshold-relay-blockchain-stanford.pdf

Albrecht, M., Grassi, L., Rechberger, C., Roy, A., Tiessen, T.: MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 191–219. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_7CrossRef

Armknecht, F., Barman, L., Bohli, J.-M., Karame, G.O.: Mirror: enabling proofs of data replication and retrievability in the cloud. In: USENIX Security Symposium, pp. 1051–1068 (2016)

Aura, T., Nikander, P., Leiwo, J.: DOS-resistant authentication with client puzzles. In: Christianson, B., Malcolm, J.A., Crispo, B., Roe, M. (eds.) Security Protocols 2000. LNCS, vol. 2133, pp. 170–177. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44810-1_22CrossRef

Baktir, S., Savas, E.: Highly-parallel montgomery multiplication for multi-core general-purpose microprocessors. In: Gelenbe, E., Lent, R. (eds.) Computer and Information Sciences III, pp. 467–476. Springer, London (2013). https://doi.org/10.1007/978-1-4471-4594-3_48CrossRef

Ben-Sasson, E., et al. Zerocash: decentralized anonymous payments from Bitcoin. In: IEEE Symposium on Security and Privacy (2014)

10.

Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: SNARKs for C: verifying program executions succinctly and in zero knowledge. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 90–108. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_6CrossRefMATH

11.

Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Scalable zero knowledge via cycles of elliptic curves. Algorithmica 79, 1102–1160 (2014)MathSciNetCrossRef

12.

Bentov, I., Gabizon, A., Zuckerman, D.: Bitcoin beacon. arXiv preprint arXiv:1605.04559 (2016)

13.

Bentov, I., Pass, R., Shi, E.: Snow white: provably secure proofs of stake. IACR Cryptology ePrint Archive, 2016 (2016)

14.

Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKs and proof-carrying data. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 111–120. ACM (2013)

15.

Bitansky, N., Goldwasser, S., Jain, A., Paneth, O., Vaikuntanathan, V., Waters, B.: Time-lock puzzles from randomized encodings. In: ACM Conference on Innovations in Theoretical Computer Science (2016)

16.

Boneh, D., Naor, M.: Timed commitments. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 236–254. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44598-6_15CrossRef

17.

Bonneau, J., Clark, J., Goldfeder, S.: On bitcoin as a public randomness source (2015). https://eprint.iacr.org/2015/1015.pdf

18.

Bonneau, J., Xu, R.: Scrambling for lightweight censorship resistance. In: Christianson, B., Crispo, B., Malcolm, J., Stajano, F. (eds.) Security Protocols 2011. LNCS, vol. 7114, pp. 296–302. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25867-1_28CrossRef

19.

Cohen, B., Pietrzak, K.: Simple proofs of sequential work. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 451–467. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_15CrossRef

20.

Buchmann, J., Williams, H.C.: A key-exchange system based on imaginary quadratic fields. J. Cryptol. 1(2), 107–118 (1988)MathSciNetCrossRef

21.

Cai, J., Lipton, R.J., Sedgewick, R., Yao, A.C.: Towards uncheatable benchmarks. In: Structure in Complexity Theory (1993)

22.

Cai, J.-Y., Nerurkar, A., Wu, M.-Y.: The design of uncheatable benchmarks using complexity theory (1997)

23.

Cascudo, I., David, B.: Scrape: scalable randomness attested by public entities. Cryptology ePrint Archive, Report 2017/216 (2017). http://eprint.iacr.org/2017/216

24.

Clark, J., Hengartner, U.: On the use of financial data as a random beacon. In: Usenix EVT/WOTE (2010)

25.

Codenottia, B., Datta, B.N., Datta, K., Leoncini, M.: Parallel algorithms for certain matrix computations. Theor. Comput. Sci. 180, 287–308 (1997)MathSciNetCrossRef

26.

Cohen, B.: Proofs of space and time. In: Blockchain Protocol Analysis and Security Engineering (2017). https://cyber.stanford.edu/sites/default/files/bramcohen.pdf

27.

Dai, W.: B-money. Consulted 1, 2012 (1998)

28.

David, B., Gaži, P., Kiayias, A., Russell, A.: Ouroboros Praos: an adaptively-secure, semi-synchronous proof-of-stake blockchain. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 66–98. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_3CrossRef

29.

Dean, D., Stubblefield, A.: Using client puzzles to protect TLS. In: USENIX Security Symposium, vol. 42 (2001)

30.

Douceur, J.R.: The Sybil attack. In: Druschel, P., Kaashoek, F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol. 2429, pp. 251–260. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45748-8_24CrossRef

31.

Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139–147. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-48071-4_10CrossRef

32.

Dziembowski, S., Faust, S., Kolmogorov, V., Pietrzak, K.: Proofs of space. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 585–605. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_29CrossRef

33.

Mathieu, É.: Mémoire sur l’étude des fonctions de plusieurs quantités sur la manière de les former et sur les substitutions qui les laissent invariables. J. Math. Pures Appl. 6(2), 241–323 (1861)MathSciNet

34.

Garay, J., Kiayias, A., Leonardos, N.: The Bitcoin backbone protocol: analysis and applications. Cryptology ePrint Archive # 2014/765 (2014)

35.

Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626–645. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_37CrossRef

36.

Goldschlag, D.M., Stubblebine, S.G.: Publicly verifiable lotteries: applications of delaying functions. In: Hirchfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 214–226. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055485CrossRef

37.

Guralnick, R.M., Müller, P.: Exceptional polynomials of affine type. J. Algebra 194(2), 429–454 (1997)MathSciNetCrossRef

38.

Hou, X.-d.: Permutation polynomials over finite fieldsa survey of recent advances. Finite Fields Appl. 32, 82–119 (2015)

39.

Jerschow, Y.I., Mauve, M.: Non-parallelizable and non-interactive client puzzles from modular square roots. In: Availability, Reliability and Security (ARES) (2011)

40.

Alwen, J., Blocki, J., Pietrzak, K.: Depth-robust graphs and their cumulative memory complexity. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 3–32. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_1CrossRef

41.

Juels, A., Kaliski Jr., B.S.: PORs: proofs of retrievability for large files. In: Proceedings of the 14th ACM Conference on Computer and Communications Security, pp. 584–597. ACM (2007)

42.

Jules, A., Brainard, J.: Client-puzzles: a cryptographic defense against connection depletion. In: Proceedings of Network and Distributed System Security Symposium (NDSS 1999), pp. 151–165 (1999)

43.

Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: a provably secure proof-of-stake blockchain protocol. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 357–388. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_12CrossRef

44.

King, S., Nadal, S.: Peercoin–secure & sustainable cryptocoin, August 2012. https://peercoin.net/whitepaper

45.

Kogan, D., Manohar, N., Boneh, D.: T/key: second-factor authentication from secure hash chains. In: ACM Conference on Computer and Communications Security (2017)

46.

Lenstra, A.K., Wesolowski, B.: A random zoo: sloth, unicorn, and trx. IACR Cryptology ePrint Archive, 2015 (2015)

47.

Lidl, R., Mullen, G.L., Turnwald, G.: Dickson Polynomials, vol. 65. Chapman & Hall/CRC, Boca Raton (1993)MATH

48.

Lipmaa, H.: Secure accumulators from euclidean rings without trusted setup. In: Bao, F., Samarati, P., Zhou, J. (eds.) ACNS 2012. LNCS, vol. 7341, pp. 224–240. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31284-7_14CrossRef

49.

Mahmoody, M., Moran, T., Vadhan, S.: Publicly verifiable proofs of sequential work. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science. ACM (2013)

50.

Maurer, U., Renner, R., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_2CrossRef

51.

Micali, S.: CS proofs. In: 1994 Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 436–453. IEEE (1994)

52.

Micali, S.: Algorand: the efficient and democratic ledger. arXiv preprint arXiv:1607.01341 (2016)

53.

Miller, A., Juels, A., Shi, E., Parno, B., Katz, J.: Permacoin: repurposing bitcoin work for data preservation. In: 2014 IEEE Symposium on Security and Privacy (SP), pp. 475–490. IEEE (2014)

54.

Moran, T., Naor, M., Segev, G.: An optimally fair coin toss. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 1–18. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00457-5_1CrossRef

55.

Morris, R., Thompson, K.: Password security: a case history. Commun. ACM 22(11), 594–597 (1979)CrossRef

56.

Müller, P.: A weil-bound free proof of Schur’s conjecture. Finite Fields Appl. 3(1), 25–32 (1997)MathSciNetCrossRef

57.

Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008)

58.

Park, S., Pietrzak, K., Kwon, A., Alwen, J., Fuchsbauer, G., Gai, P.: SpaceMint: a cryptocurrency based on proofs of space. Cryptology ePrint Archive, Report 2015/528 (2015). http://eprint.iacr.org/2015/528

59.

Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: IEEE Security and Privacy (2013)

60.

Pierrot, C., Wesolowski, B.: Malleability of the blockchains entropy. Cryptogr. Commun. 10, 211–233 (2016)MathSciNetCrossRef

61.

Pietrzak, K.: Unique proofs of sequential work from time-lock puzzles (2018). Manuscript

62.

Rabin, M.O.: Transaction protection by beacons. J. Comput. Syst. Sci. 27, 256–267 (1983)MathSciNetCrossRef

63.

Rivest, R.L., Shamir, A.: PayWord and MicroMint: two simple micropayment schemes. In: Lomas, M. (ed.) Security Protocols 1996. LNCS, vol. 1189, pp. 69–87. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-62494-5_6CrossRef

64.

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

65.

Syta, E., et al.: Scalable bias-resistant distributed randomness. In: 2017 IEEE Symposium on Security and Privacy (SP), pp. 444–460. IEEE (2017)

66.

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

67.

Van Oorschot,P.C., Wiener, M.J.: Parallel collision search with application to hash functions and discrete logarithms. In: ACM Conference on Computer and Communications Security (1994)

68.

Wahby, R.S., Setty, S.T., Ren, Z., Blumberg, A.J., Walfish, M.: Efficient RAM and control flow in verifiable outsourced computation. In: NDSS (2015)

Titel: Verifiable Delay Functions
verfasst von: Dan Boneh
Joseph Bonneau
Benedikt Bünz
Ben Fisch
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2018
Print ISBN: 978-3-319-96883-4

Electronic ISBN: 978-3-319-96884-1

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-96884-1_25

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"