Picnic

A Family of Post-Quantum Secure Digital Signature Algorithms

The Picnic family of digital signature algorithms is designed to provide security against attacks by quantum computers, in addition to attacks by classical computers. The building blocks are a zero-knowledge proof system (with post-quantum security), and symmetric key primitives like hash functions and block ciphers, with well-understood post-quantum security. Picnic does not require number-theoretic, or structured hardness assumptions.

Publications

• Melissa Chase, David Derler, Steven Goldfeder, Claudio Orlandi, Sebastian Ramacher, Christian Rechberger, Daniel Slamanig, Greg Zaverucha. Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives. ACM CCS 2017 (see also ePrint 2017/279).

• The Picnic Signature Algorithm Specification, version 3.0, April 2020.

• The Picnic Signature Algorithm Design Document, version 2.2, April 2020.

• Itai Dinur, Daniel Kales, Angela Promitzer, Sebastian Ramacher, Christian Rechberger. Linear Equivalence of Block Ciphers with Partial Non-Linear Layers: Application to LowMC. Eurocrypt 2019 (see also ePrint Report 2018/772).

• Jonathan Katz, Vladimir Kolesnikov and Xiao Wang. Improved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures. ACM CCS 2018 (see also ePrint Report 2018/475).

• Daniel Kales, Sebastian Ramacher, Christian Rechberger, Roman Walch and Mario Werner. Efficient FPGA Implementations of LowMC and Picnic. CT-RSA2020 (see also ePrint Report 2019/1368).

• Daniel Kales and Greg Zaverucha. Improving the Performance of the Picnic Signature Scheme. IACR ePrint Report 2020/427, April 2020.

Libraries Implementing Picnic

• Optimized Implementation An implementation optimized for speed, able to make use of processor specific features.

• Reference Implementation An implementation that tries to be simple, and follow the spec closely, to illustrate the algorithm.

Talks

• Steven Goldfeder, Sebastian Ramacher - "Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives" - ACM CCS 2017 (slides).
• Sebastian Ramacher - "Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives" - CryptoAction Symposium (COST Action IC1306).
• Melissa Chase - "Post-Quantum Signatures from Symmetric-Key Primitives" - Real-World Crypto 2018 (recording).
• Greg Zaverucha - "The Picnic Digital Signature Algorithm" - NIST First PQC Standardization Conference (slides).
• Jonathan Katz - "Improved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures" - ACM CCS 2018 (recording).
• Greg Zaverucha - "The Picnic Digital Signature Algorithm" - NIST Second PQC Standardization Conference (slides).

Projects and Demos

• open-quantum-safe/liboqs: liboqs is a C library for quantum-resistant cryptographic algorithms. It has support for Picnic.
• HSM Demo: We have experimented with using Picnic on a commercial hardware security module, as described in the Design Document. The software is available here.

Flexibility of the Picnic Design

Although not directly related to Picnic, other post-quantum secure (privacy enhancing) primitives use the same building blocks as Picnic. We believe that this work nicely demonstrates the flexibility of the basic Picnic design, which is why we list the respective papers below.

• Dan Boneh, Saba Eskandarian, Ben Fisch. Post-Quantum Group Signatures from Symmetric Primitives. CT-RSA 2019.
• David Derler, Sebastian Ramacher, Daniel Slamanig. Post-Quantum Zero-Knowledge Proofs for Accumulators with Applications to Ring Signatures from Symmetric-Key Primitives. PQCrypto 2018.

Picnic was designed by a group of cryptographers from Aarhus University, AIT Austrian Institute of Technology GmbH, DFINITY, Graz University of Technology, George Mason University, Georgia Tech, Microsoft Research, Northwestern University, Cornell Tech, and the Technical University of Denmark. The team includes Melissa Chase, David Derler, Steven Goldfeder, Daniel Kales, Jonathan Katz, Vladimir Kolesnikov, Claudio Orlandi, Sebastian Ramacher, Christian Rechberger, Daniel Slamanig, Xiao Wang, and Greg Zaverucha.

                            

Funding Acknowledgments

In addition to support from the institutions listed above, this work has been supported in part by EU H2020 projects PRISMACLOUD (grant agreement number 644962) and PQCRYPTO (grant agreement number 645622), by the NSF Graduate Research Fellowship (grant number DGE 1148900), by COST Action IC1306, by the Danish Council for Independent Research, by A-SIT, and by iov42.