I have read about the Fiat-Shamir heuristic for making an interactive proof of knowledge into a non-interactive proof of knowledge. If I apply this to zero-knowledge proof of knowledge, it seems to me that I would destroy the simulator and therefore the zero-knowledgeness.

Does the Fiat-Shamir heuristic destroy zero-knowledgeness? If it does, it it possible to circumvent this?

Link to Fiat-Shamir heuristic.


In the random-oracle model, it has been shown that the Fiat-Shamir transform preserves the soundness and zero-knowledge of certain families of zero-knowledge (proof of knowledge) protocols (e.g., Sigma protocols) -- see [§5 in BR93,PS00,FKMV12]. Instantiating the random oracle with a concrete hash function is a much harder prospect, but there have been some recent works in this direction as well --- for example, the recent construction of NIZK from LWE relies on such an instantiation of the Fiat-Shamir transform [PS19].

P.S. Zero-knowledge is usually easy to show -- it is arguing soundness that usually causes problems in the non-interactive setting.

[BR93]: Bellare and Rogaway: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols [FKMV12]: Faust et al. On the Non-malleability of the Fiat-Shamir Transform
[PS00]: Pointcheval and Stern: Security Arguments for Digital Signatures and Blind Signatures
[PS19]: Peikert and Sheihan Non-Interactive Zero Knowledge for NP from (Plain) LWE.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.