Paper 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.