---
_id: '6528'
abstract:
- lang: eng
text: We construct a verifiable delay function (VDF) by showing how the Rivest-Shamir-Wagner
time-lock puzzle can be made publicly verifiable. Concretely, we give a statistically
sound public-coin protocol to prove that a tuple (N,x,T,y) satisfies y=x2T (mod
N) where the prover doesn’t know the factorization of N and its running time is
dominated by solving the puzzle, that is, compute x2T, which is conjectured to
require T sequential squarings. To get a VDF we make this protocol non-interactive
using the Fiat-Shamir heuristic.The motivation for this work comes from the Chia
blockchain design, which uses a VDF as akey ingredient. For typical parameters
(T≤2 40, N= 2048), our proofs are of size around 10K B, verification cost around
three RSA exponentiations and computing the proof is 8000 times faster than solving
the puzzle even without any parallelism.
alternative_title:
- LIPIcs
article_number: '60'
article_processing_charge: No
author:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Pietrzak KZ. Simple verifiable delay functions. In: 10th Innovations in
Theoretical Computer Science Conference. Vol 124. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2019. doi:10.4230/LIPICS.ITCS.2019.60'
apa: 'Pietrzak, K. Z. (2019). Simple verifiable delay functions. In 10th Innovations
in Theoretical Computer Science Conference (Vol. 124). San Diego, CA, United
States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2019.60'
chicago: Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” In 10th
Innovations in Theoretical Computer Science Conference, Vol. 124. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ITCS.2019.60.
ieee: K. Z. Pietrzak, “Simple verifiable delay functions,” in 10th Innovations
in Theoretical Computer Science Conference, San Diego, CA, United States,
2019, vol. 124.
ista: 'Pietrzak KZ. 2019. Simple verifiable delay functions. 10th Innovations in
Theoretical Computer Science Conference. ITCS 2019: Innovations in Theoretical
Computer Science, LIPIcs, vol. 124, 60.'
mla: Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” 10th Innovations
in Theoretical Computer Science Conference, vol. 124, 60, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.ITCS.2019.60.
short: K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science Conference,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
conference:
end_date: 2019-01-12
location: San Diego, CA, United States
name: 'ITCS 2019: Innovations in Theoretical Computer Science'
start_date: 2019-01-10
date_created: 2019-06-06T14:12:36Z
date_published: 2019-01-10T00:00:00Z
date_updated: 2021-01-12T08:07:53Z
day: '10'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.4230/LIPICS.ITCS.2019.60
ec_funded: 1
file:
- access_level: open_access
checksum: f0ae1bb161431d9db3dea5ace082bfb5
content_type: application/pdf
creator: dernst
date_created: 2019-06-06T14:22:04Z
date_updated: 2020-07-14T12:47:33Z
file_id: '6529'
file_name: 2019_LIPIcs_Pietrzak.pdf
file_size: 558770
relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: ' 124'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2018/627
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 10th Innovations in Theoretical Computer Science Conference
publication_identifier:
isbn:
- 978-3-95977-095-8
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Simple verifiable delay functions
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 124
year: '2019'
...