Cryptology ePrint Archive: Report 2016/1168

Generic Zero-Knowledge and Multivariate Quadratic Systems

Alan Szepieniec and Bart Preneel

Abstract: Zero-knowledge proofs are a core building block for a broad range of cryptographic protocols. This paper introduces a generic zero-knowledge proof system capable of proving the correct computation of any circuit. Our protocol draws on recent advancements in multiparty computation and its security relies only on the underlying commitment scheme. Furthermore, we optimize this protocol for use with multivariate quadratic systems of polynomials, leading to provably secure signatures from multivariate quadratic systems, with keys that scale linearly and signatures that scale quadratically with the security parameter.

Category / Keywords: public-key cryptography / zero-knowledge proof, post-quantum, signature, multivariate quadratic, provable security, multi-party computation

Date: received 20 Dec 2016, withdrawn 17 Jan 2017

Contact author: alan szepieniec at esat kuleuven be

Available format(s): (-- withdrawn --)

Version: 20170117:111609 (All versions of this report)

Short URL: ia.cr/2016/1168

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]