Cryptology ePrint Archive: Report 2019/490

On sigma protocols with helper for MQ and PKP, fishy signature schemes and more

Ward Beullens

Abstract: This work presents 2 sigma protocols with helper to prove knowledge of:

-A solution to a system of quadratic polynomials

-A solution to an instance of the Permuted Kernel Problem

We then remove the helper from the protocol with a "cut-and-choose" protocol and we apply the Fiat-Shamir transform to obtain signature schemes with security proof in the QROM. We show that the resulting signature schemes, which we call the "MUltivarite quaDratic FIat-SHamir" scheme (MUDFISH) and the "ShUffled Solution to Homogeneous linear SYstem FIat-SHamir" scheme (SUSHSYFISH), are more efficient than existing signatures based on the MQ problem and the Permuted Kernel Problem. We also leverage the ZK-proof for PKP to improve the efficiency of Stern-like Zero Knowledge proofs for lattice statements.

Category / Keywords: public-key cryptography / zero knowledge, Post-Quantum digital signatures, Multivariate cryptography, Permuted Kernel Problem, Silly acronyms

Date: received 13 May 2019

Contact author: ward beullens at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20190520:093529 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]