Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
On ELFs, Deterministic Encryption, and Correlated-Input Security Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

Efficient Verifiable Delay Functions

verfasst von : Benjamin Wesolowski

Erschienen in: Advances in Cryptology – EUROCRYPT 2019

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We construct a verifiable delay function (VDF). A VDF is a function whose evaluation requires running a given number of sequential steps, yet the result can be efficiently verified. They have applications in decentralised systems, such as the generation of trustworthy public randomness in a trustless environment, or resource-efficient blockchains. To construct our VDF, we actually build a trapdoor VDF. A trapdoor VDF is essentially a VDF which can be evaluated efficiently by parties who know a secret (the trapdoor). By setting up this scheme in a way that the trapdoor is unknown (not even by the party running the setup, so that there is no need for a trusted setup environment), we obtain a simple VDF. Our construction is based on groups of unknown order such as an RSA group, or the class group of an imaginary quadratic field. The output of our construction is very short (the result and the proof of correctness are each a single element of the group), and the verification of correctness is very efficient.

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 A Modular Treatment of Blind Signatures from Identification Schemes
Nächstes Kapitel Quantum Lightning Never Strikes the Same State Twice
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
The paper [4] was developed independently of the present work, yet we adopt their terminology for verifiable delay functions, for the sake of uniformity.
 
2
i.e., \(C(\mathcal A,g) = O(f(\mathrm {len}(g)))\) for a polynomial f, with \(\mathrm {len}(g)\) the binary length of g.
 
3
In this game, the output of \(\mathcal A\) is another algorithm \(\mathcal B\). When we say that \(\mathcal A\) is limited to q queries, we limit the total number of queries by \(\mathcal A\) and \(\mathcal B\) combined. In other words, if \(\mathcal A\) did \(x \le q\) queries, then its output \(\mathcal B\) is limited to \(q-x\) queries.
 
4
Note that this constant factor does not affect the chances of \(\mathcal C\) to win the \((\delta ,{t})\)-time-lock game, since it concerns only the running time of \(\mathcal C\) itself and not of the algorithm output by \(\mathcal C(G)\).
 
5
In this game, the output of \(\mathcal A\) is another algorithm \(\mathcal B\). When we say that \(\mathcal A\) is limited to q queries, we limit the total number of queries by \(\mathcal A\) and \(\mathcal B\) combined. In other words, if \(\mathcal A\) did \(x \le q\) queries, then its output \(\mathcal B\) is limited to \(q-x\) queries.
 
6
A message does not travel directly from Alice (or Bob) to Judy, since Judy is only communicating with the (mis)informant. What is measured here is the sum of the delay between Alice and the (mis)informant and the delay between the (mis)informant and Judy. There is no constraint on the location of the (mis)informant, but we assume a triangular inequality: he could be close to Alice and Bob, in which case his communications with Judy suffer a delay, or he could be close to Judy, in which case his interactions with Alice and Bob are delayed.
 
Literatur
1.
Bellare, M., Goldwasser, S.: Encapsulated key escrow. Technical report (1996)
2.
Bellare, M., Goldwasser, S.: Verifiable partial key escrow. In: Proceedings of the 4th ACM Conference on Computer and Communications Security, CCS 1997, pp. 78–91. ACM, New York, NY, USA (1997)
3.
Biehl, I., Buchmann, J., Hamdy, S., Meyer, A.: A signature scheme based on the intractability of computing roots. Des. Codes Crypt. 25(3), 223–236 (2002)MathSciNetCrossRef
4.
5.
6.
7.
8.
Buchmann, J., Hamdy, S.: A survey on IQ cryptography. In: Proceedings of Public Key Cryptography and Computational Number Theory, pp. 1–15 (2001)
9.
Buchmann, J., Williams, H.C.: A key-exchange system based on imaginary quadratic fields. J. Cryptol. 1(2), 107–118 (1988)MathSciNetCrossRef
10.
11.
12.
Drake, J.: Ethereum 2.0 randomness. August 2018 Workshop at Stanford Hosted by the Ethereum Foundation and the Stanford Center for Blockchain Research (2018)
13.
14.
Hafner, J.L., McCurley, K.S.: A rigorous subexponential algorithm for computation of class groups. J. Am. Math. Soc. 2(4), 837–850 (1989)MathSciNetCrossRef
15.
Lenstra, A.K., Wesolowski, B.: Trustworthy public randomness with sloth, unicorn and trx. Int. J. Appl. Cryptol. 3, 330–343 (2016)MathSciNetCrossRef
16.
Pietrzak, K.: Simple verifiable delay functions. In: Blum, A. (ed.), 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, San Diego, California, USA, 10–12 January 2019, pp. 60:1–60:15 (2019)
17.
18.
Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release crypto. Technical report (1996)
19.
20.
Metadaten
Titel
Efficient Verifiable Delay Functions
verfasst von
Benjamin Wesolowski
Copyright-Jahr
2019
Buch
Advances in Cryptology – EUROCRYPT 2019

Print ISBN: 978-3-030-17658-7

Electronic ISBN: 978-3-030-17659-4

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-3-030-17659-4_13

Premium Partner

    Bildnachweise