Paper 2019/490

Sigma protocols for MQ, PKP and SIS, and fishy signature schemes

Ward Beullens

Abstract

This work presents sigma protocols to prove knowledge of: -a solution to a system of quadratic polynomials, -a solution to an instance of the Permuted Kernel Problem and -a witness for a variety of lattice statements (including SIS). Our sigma protocols have soundness error 1/q', where q' is any number bounded by the size of the underlying finite field. This is much better than existing proofs, which have soundness error 2/3 or (q'+1)/2q'. The prover and verifier time of our proofs are O(q'). We achieve this by first constructing so-called sigma protocols with helper, which are sigma protocols where the prover and the verifier are assisted by a trusted third party, and then eliminating the helper from the proof with a "cut-and-choose" protocol. 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 "MUltivariate 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. Our proof system can be used to improve the efficiency of applications relying on (generalizations of) Stern's protocol. We show that the proof size of our SIS proof is smaller than that of Stern's protocol by an order of magnitude and that our proof is more efficient than existing post-quantum secure SIS proofs.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
zero knowledgePost-Quantum digital signaturesMultivariate cryptographyPermuted Kernel ProblemSilly acronyms
Contact author(s)
ward beullens @ esat kuleuven be
History
2020-02-21: last of 3 revisions
2019-05-20: received
See all versions
Short URL
https://ia.cr/2019/490
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/490,
      author = {Ward Beullens},
      title = {Sigma protocols for MQ, PKP and SIS, and fishy signature schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2019/490},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/490}},
      url = {https://eprint.iacr.org/2019/490}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.