Revisiting Post-quantum Fiat-Shamir

Qipeng Liu, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 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 languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings
EditorsAlexandra Boldyreva, Daniele Micciancio
PublisherSpringer Verlag
Pages326-355
Number of pages30
ISBN (Print)9783030269500
DOIs
StatePublished - Jan 1 2019
Event39th Annual International Cryptology Conference, CRYPTO 2019 - Santa Barbara, United States
Duration: Aug 18 2019Aug 22 2019

Publication series

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

Conference

Conference39th Annual International Cryptology Conference, CRYPTO 2019
CountryUnited States
CitySanta Barbara
Period8/18/198/22/19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Revisiting Post-quantum Fiat-Shamir'. Together they form a unique fingerprint.

  • 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