Paper 2020/427

Improving the Performance of the Picnic Signature Scheme

Daniel Kales and Greg Zaverucha

Abstract

Picnic is a digital signature algorithm designed to provide security against attacks by quantum computers. The design uses only symmetric-key primitives, and is an efficient instantiation of the MPC-in-the-head paradigm. In this work, we explore the Picnic design in great detail. We investigate and benchmark different parameter choices and show that there exist better parameter choices than those in the current specification. We also present improvements to the MPC protocol that shorten signatures and reduce signing time. The proposed MPC changes tailor the protocol to the circuit of interest in Picnic, but may also be of independent interest. Taken together, these changes give a new instantiation of Picnic that signs messages 7.9 to 13.9 times faster, and verifies signatures 4.5 to 5.5 times faster than the existing ``Picnic2'' design, while having nearly the same signature sizes.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
post-quantum cryptographydigital signaturesefficient implementationzero-knowledgeMPC-in-the-head
Contact author(s)
gregz @ microsoft com
daniel kales @ iaik tugraz at
History
2020-05-05: revised
2020-04-15: received
See all versions
Short URL
https://ia.cr/2020/427
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/427,
      author = {Daniel Kales and Greg Zaverucha},
      title = {Improving the Performance of the Picnic Signature Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2020/427},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/427}},
      url = {https://eprint.iacr.org/2020/427}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.