Revisiting Post-quantum Fiat-Shamir

Qipeng Liu; Mark Zhandry

doi:10.1007/978-3-030-26951-7_12

Revisiting Post-quantum Fiat-Shamir

Qipeng Liu, Mark Zhandry

Computer Science

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

49 Scopus citations

Abstract

The Fiat-Shamir transformation is a useful approach to building non-interactive arguments (of knowledge) in the random oracle model. Unfortunately, existing proof techniques are incapable of proving the security of Fiat-Shamir in the quantum setting. The problem stems from (1) the difficulty of quantum rewinding, and (2) the inability of current techniques to adaptively program random oracles in the quantum setting. In this work, we show how to overcome the limitations above in many settings. In particular, we give mild conditions under which Fiat-Shamir is secure in the quantum setting. As an application, we show that existing lattice signatures based on Fiat-Shamir are secure without any modifications.

Original language	English (US)
Title of host publication	Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings
Editors	Alexandra Boldyreva, Daniele Micciancio
Publisher	Springer Verlag
Pages	326-355
Number of pages	30
ISBN (Print)	9783030269500
DOIs	https://doi.org/10.1007/978-3-030-26951-7_12
State	Published - 2019
Event	39th Annual International Cryptology Conference, CRYPTO 2019 - Santa Barbara, United States Duration: Aug 18 2019 → Aug 22 2019

Publication series

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

Conference

Conference	39th Annual International Cryptology Conference, CRYPTO 2019
Country/Territory	United States
City	Santa Barbara
Period	8/18/19 → 8/22/19

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-26951-7_12

Cite this

Liu, Q., & Zhandry, M. (2019). Revisiting Post-quantum Fiat-Shamir. In A. Boldyreva, & D. Micciancio (Eds.), Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings (pp. 326-355). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11693 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-26951-7_12

Liu, Qipeng ; Zhandry, Mark. / Revisiting Post-quantum Fiat-Shamir. Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings. editor / Alexandra Boldyreva ; Daniele Micciancio. Springer Verlag, 2019. pp. 326-355 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{bdc2fe5c900441d2ba8d9e0d47a1971b,

title = "Revisiting Post-quantum Fiat-Shamir",

abstract = "The Fiat-Shamir transformation is a useful approach to building non-interactive arguments (of knowledge) in the random oracle model. Unfortunately, existing proof techniques are incapable of proving the security of Fiat-Shamir in the quantum setting. The problem stems from (1) the difficulty of quantum rewinding, and (2) the inability of current techniques to adaptively program random oracles in the quantum setting. In this work, we show how to overcome the limitations above in many settings. In particular, we give mild conditions under which Fiat-Shamir is secure in the quantum setting. As an application, we show that existing lattice signatures based on Fiat-Shamir are secure without any modifications.",

author = "Qipeng Liu and Mark Zhandry",

note = "Publisher Copyright: {\textcopyright} 2019, International Association for Cryptologic Research.; 39th Annual International Cryptology Conference, CRYPTO 2019 ; Conference date: 18-08-2019 Through 22-08-2019",

year = "2019",

doi = "10.1007/978-3-030-26951-7_12",

language = "English (US)",

isbn = "9783030269500",

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

publisher = "Springer Verlag",

pages = "326--355",

editor = "Alexandra Boldyreva and Daniele Micciancio",

booktitle = "Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings",

address = "Germany",

}

Liu, Q & Zhandry, M 2019, Revisiting Post-quantum Fiat-Shamir. in A Boldyreva & D Micciancio (eds), Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11693 LNCS, Springer Verlag, pp. 326-355, 39th Annual International Cryptology Conference, CRYPTO 2019, Santa Barbara, United States, 8/18/19. https://doi.org/10.1007/978-3-030-26951-7_12

Revisiting Post-quantum Fiat-Shamir. / Liu, Qipeng; Zhandry, Mark.
Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings. ed. / Alexandra Boldyreva; Daniele Micciancio. Springer Verlag, 2019. p. 326-355 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11693 LNCS).

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

TY - GEN

T1 - Revisiting Post-quantum Fiat-Shamir

AU - Liu, Qipeng

AU - Zhandry, Mark

PY - 2019

Y1 - 2019

N2 - The Fiat-Shamir transformation is a useful approach to building non-interactive arguments (of knowledge) in the random oracle model. Unfortunately, existing proof techniques are incapable of proving the security of Fiat-Shamir in the quantum setting. The problem stems from (1) the difficulty of quantum rewinding, and (2) the inability of current techniques to adaptively program random oracles in the quantum setting. In this work, we show how to overcome the limitations above in many settings. In particular, we give mild conditions under which Fiat-Shamir is secure in the quantum setting. As an application, we show that existing lattice signatures based on Fiat-Shamir are secure without any modifications.

AB - The Fiat-Shamir transformation is a useful approach to building non-interactive arguments (of knowledge) in the random oracle model. Unfortunately, existing proof techniques are incapable of proving the security of Fiat-Shamir in the quantum setting. The problem stems from (1) the difficulty of quantum rewinding, and (2) the inability of current techniques to adaptively program random oracles in the quantum setting. In this work, we show how to overcome the limitations above in many settings. In particular, we give mild conditions under which Fiat-Shamir is secure in the quantum setting. As an application, we show that existing lattice signatures based on Fiat-Shamir are secure without any modifications.

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

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

U2 - 10.1007/978-3-030-26951-7_12

DO - 10.1007/978-3-030-26951-7_12

M3 - Conference contribution

AN - SCOPUS:85071513525

SN - 9783030269500

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

SP - 326

EP - 355

BT - Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings

A2 - Boldyreva, Alexandra

A2 - Micciancio, Daniele

PB - Springer Verlag

T2 - 39th Annual International Cryptology Conference, CRYPTO 2019

Y2 - 18 August 2019 through 22 August 2019

ER -

Liu Q, Zhandry M. Revisiting Post-quantum Fiat-Shamir. In Boldyreva A, Micciancio D, editors, Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings. Springer Verlag. 2019. p. 326-355. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-26951-7_12

Revisiting Post-quantum Fiat-Shamir

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this