In this paper, we show under which strengthened conditions the Fiat-Shamir proof system is still post-quantum secure. Namely, we show that if we require the sigma-protocol to have computational zero-knowledge and perfect special soundness, then Fiat-Shamir is a zero-knowledge simulation-sound proof system (but not a proof of knowledge!). Furthermore, we show that Fiat-Shamir leads to a post-quantum secure strongly unforgeable signature scheme when additionally assuming a "dual-mode hard instance generator" for generating key pairs.
Finally, we study the extractability (proof of knowledge) property of Fiat-Shamir. While we have no proof of the extractability itself, we show that if we can prove extractability, then other desired properties such as simulation-sound extractability (i.e., non-malleability), and strongly unforgeable signatures follow.
Category / Keywords: public-key cryptography / quantum cryptography, zero knowledge, digital signatures Date: received 9 May 2017 Contact author: unruh at ut ee Available format(s): PDF | BibTeX Citation Version: 20170509:124145 (All versions of this report) Short URL: ia.cr/2017/398 Discussion forum: Show discussion | Start new discussion