You are looking at a specific version 20190701:091436 of this paper. See the latest version.

Paper 2019/699

Quantum security of the Fiat-Shamir transform of commit and open protocols

André Chailloux

Abstract

Applying the Fiat-Shamir transform on identification schemes is one of the main ways of constructing signature schemes. While the classical security of this transformation is well understood, it is only very recently that generic results for the quantum case has been proposed [DFMS19,LZ19]. In this paper, we show that if we start from a commit-and-open identification scheme, where the prover first commits to several strings and then as a second message opens a subset of them depending on the verifier's message, then the Fiat-Shamir transform is quantum secure, for a suitable choice of commitment scheme. Unlike previous generic results, our transformation doesn't require to reprogram the random function H used in the Fiat-Shamir transform and we actually only require a quantum one-wayness property. Our techniques can in some cases lead to a much tighter security reduction. To illustrate this, we apply our techniques to identifications schemes at the core of the MQDSS signature scheme, the Picnic scheme (both present in the round 2 of the post quantum NIST competition) and the Stern signature scheme. For all these schemes, we show that our technique can be applied with essentially tight results.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
quantum Fiat-Shamir transformsignature schemescommit and open identifications schemes
Contact author(s)
andre chailloux @ inria fr
History
2021-03-16: last of 3 revisions
2019-06-13: received
See all versions
Short URL
https://ia.cr/2019/699
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.