Revisiting Post-Quantum Fiat-Shamir

Qipeng Liu; Mark Zhandry

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2019/262

Revisiting Post-Quantum Fiat-Shamir

Qipeng Liu and Mark Zhandry

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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Keywords: quantum Fiat-Shamir signature SIS
Contact author(s): qipengl @ cs princeton edu
History: 2019-03-06: received
Short URL: https://ia.cr/2019/262
License: CC BY

BibTeX

@misc{cryptoeprint:2019/262,
      author = {Qipeng Liu and Mark Zhandry},
      title = {Revisiting Post-Quantum Fiat-Shamir},
      howpublished = {Cryptology ePrint Archive, Paper 2019/262},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/262}},
      url = {https://eprint.iacr.org/2019/262}
}