Short-lived Zero-Knowledge Proofs and Signatures

Arasu Arun; Joseph Bonneau; Jeremy Clark

doi:10.1007/978-3-031-22969-5_17

Short-lived Zero-Knowledge Proofs and Signatures

Arasu Arun, Joseph Bonneau, Jeremy Clark

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We introduce the short-lived proof, a non-interactive proof of knowledge with a novel feature: after a specified period of time, the proof is no longer convincing. This time-delayed loss of soundness happens “naturally” without further involvement from the prover or any third party. We propose definitions for short-lived proofs as well as the special case of short-lived signatures. We show several practical constructions built using verifiable delay functions (VDFs). The key idea in our approach is to allow any party to forge any proof by executing a large sequential computation. Some constructions achieve a stronger property called reusable forgeability in which one sequential computation allows forging an arbitrary number of proofs of different statements. We also introduces two novel types of VDFs, re-randomizable VDFs and zero-knowledge VDFs, which may be of independent interest. Our constructions for short-lived Σ -protocols and signatures are practically efficient for provers and verifiers, adding a few hundred bytes of overhead and tens to hundreds of milliseconds of proving/verification time.

Original language	English (US)
Title of host publication	Advances in Cryptology – ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, 2022, Proceedings
Editors	Shweta Agrawal, Dongdai Lin
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	487-516
Number of pages	30
ISBN (Print)	9783031229688
DOIs	https://doi.org/10.1007/978-3-031-22969-5_17
State	Published - 2022
Event	28th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2022 - Taipei, Taiwan, Province of China Duration: Dec 5 2022 → Dec 9 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13793 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	28th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2022
Country/Territory	Taiwan, Province of China
City	Taipei
Period	12/5/22 → 12/9/22

Keywords

Signatures
Time-based crypto
VDFs
Zero-knowledge proofs

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-22969-5_17

Cite this

Arun, A., Bonneau, J., & Clark, J. (2022). Short-lived Zero-Knowledge Proofs and Signatures. In S. Agrawal, & D. Lin (Eds.), Advances in Cryptology – ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, 2022, Proceedings (pp. 487-516). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13793 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-22969-5_17

Short-lived Zero-Knowledge Proofs and Signatures. / Arun, Arasu; Bonneau, Joseph; Clark, Jeremy.
Advances in Cryptology – ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, 2022, Proceedings. ed. / Shweta Agrawal; Dongdai Lin. Springer Science and Business Media Deutschland GmbH, 2022. p. 487-516 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13793 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Arun, A, Bonneau, J & Clark, J 2022, Short-lived Zero-Knowledge Proofs and Signatures. in S Agrawal & D Lin (eds), Advances in Cryptology – ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13793 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 487-516, 28th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2022, Taipei, Taiwan, Province of China, 12/5/22. https://doi.org/10.1007/978-3-031-22969-5_17

Arun A, Bonneau J, Clark J. Short-lived Zero-Knowledge Proofs and Signatures. In Agrawal S, Lin D, editors, Advances in Cryptology – ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 487-516. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-22969-5_17

Arun, Arasu ; Bonneau, Joseph ; Clark, Jeremy. / Short-lived Zero-Knowledge Proofs and Signatures. Advances in Cryptology – ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, 2022, Proceedings. editor / Shweta Agrawal ; Dongdai Lin. Springer Science and Business Media Deutschland GmbH, 2022. pp. 487-516 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2a61b423183e4d3f9a069b3b09cd2e44,

title = "Short-lived Zero-Knowledge Proofs and Signatures",

abstract = "We introduce the short-lived proof, a non-interactive proof of knowledge with a novel feature: after a specified period of time, the proof is no longer convincing. This time-delayed loss of soundness happens “naturally” without further involvement from the prover or any third party. We propose definitions for short-lived proofs as well as the special case of short-lived signatures. We show several practical constructions built using verifiable delay functions (VDFs). The key idea in our approach is to allow any party to forge any proof by executing a large sequential computation. Some constructions achieve a stronger property called reusable forgeability in which one sequential computation allows forging an arbitrary number of proofs of different statements. We also introduces two novel types of VDFs, re-randomizable VDFs and zero-knowledge VDFs, which may be of independent interest. Our constructions for short-lived Σ -protocols and signatures are practically efficient for provers and verifiers, adding a few hundred bytes of overhead and tens to hundreds of milliseconds of proving/verification time.",

keywords = "Signatures, Time-based crypto, VDFs, Zero-knowledge proofs",

author = "Arasu Arun and Joseph Bonneau and Jeremy Clark",

note = "Publisher Copyright: {\textcopyright} 2022, International Association for Cryptologic Research.; 28th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2022 ; Conference date: 05-12-2022 Through 09-12-2022",

year = "2022",

doi = "10.1007/978-3-031-22969-5_17",

language = "English (US)",

isbn = "9783031229688",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "487--516",

editor = "Shweta Agrawal and Dongdai Lin",

booktitle = "Advances in Cryptology – ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, 2022, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Short-lived Zero-Knowledge Proofs and Signatures

AU - Arun, Arasu

AU - Bonneau, Joseph

AU - Clark, Jeremy

PY - 2022

Y1 - 2022

N2 - We introduce the short-lived proof, a non-interactive proof of knowledge with a novel feature: after a specified period of time, the proof is no longer convincing. This time-delayed loss of soundness happens “naturally” without further involvement from the prover or any third party. We propose definitions for short-lived proofs as well as the special case of short-lived signatures. We show several practical constructions built using verifiable delay functions (VDFs). The key idea in our approach is to allow any party to forge any proof by executing a large sequential computation. Some constructions achieve a stronger property called reusable forgeability in which one sequential computation allows forging an arbitrary number of proofs of different statements. We also introduces two novel types of VDFs, re-randomizable VDFs and zero-knowledge VDFs, which may be of independent interest. Our constructions for short-lived Σ -protocols and signatures are practically efficient for provers and verifiers, adding a few hundred bytes of overhead and tens to hundreds of milliseconds of proving/verification time.

AB - We introduce the short-lived proof, a non-interactive proof of knowledge with a novel feature: after a specified period of time, the proof is no longer convincing. This time-delayed loss of soundness happens “naturally” without further involvement from the prover or any third party. We propose definitions for short-lived proofs as well as the special case of short-lived signatures. We show several practical constructions built using verifiable delay functions (VDFs). The key idea in our approach is to allow any party to forge any proof by executing a large sequential computation. Some constructions achieve a stronger property called reusable forgeability in which one sequential computation allows forging an arbitrary number of proofs of different statements. We also introduces two novel types of VDFs, re-randomizable VDFs and zero-knowledge VDFs, which may be of independent interest. Our constructions for short-lived Σ -protocols and signatures are practically efficient for provers and verifiers, adding a few hundred bytes of overhead and tens to hundreds of milliseconds of proving/verification time.

KW - Signatures

KW - Time-based crypto

KW - VDFs

KW - Zero-knowledge proofs

UR - http://www.scopus.com/inward/record.url?scp=85149642598&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85149642598&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-22969-5_17

DO - 10.1007/978-3-031-22969-5_17

M3 - Conference contribution

AN - SCOPUS:85149642598

SN - 9783031229688

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 487

EP - 516

BT - Advances in Cryptology – ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, 2022, Proceedings

A2 - Agrawal, Shweta

A2 - Lin, Dongdai

PB - Springer Science and Business Media Deutschland GmbH

T2 - 28th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2022

Y2 - 5 December 2022 through 9 December 2022

ER -