David Naccache - Workshop on Secure Implementation of Post-Quantum Cryptography in Israel

Thrifty Zero-Knowledge When Linear Programming Meets Cryptography

Simon Cogliani, Houda Ferradi, Rémi Géraud, and David Naccache

Abstract: We introduce “thrifty” zero-knowledge protocols, or TZK. These protocols are constructed by introducing a bias in the challenge send by the prover. This bias is chosen so as to maximize the security versus effort trade-off. We illustrate the benefits of this approach on several well-known zero-knowledge protocols.