International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Revisiting Post-quantum Fiat-Shamir

Authors:
Qipeng Liu
Mark Zhandry
Download:
DOI: 10.1007/978-3-030-26951-7_12 (login may be required)
Search ePrint
Search Google
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.
Video from CRYPTO 2019
BibTeX
@article{crypto-2019-29891,
  title={Revisiting Post-quantum Fiat-Shamir},
  booktitle={Advances in Cryptology – CRYPTO 2019},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11693},
  pages={326-355},
  doi={10.1007/978-3-030-26951-7_12},
  author={Qipeng Liu and Mark Zhandry},
  year=2019
}