Picnic - Quantum-Safe Digital Signatures

About Picnic

Picnic is a post-quantum digital signature algorithm that uses a novel approach based on zero-knowledge proofs and symmetric-key primitives. It was an alternate candidate in the third round of the NIST Post-Quantum Cryptography standardization process.

Key Features:

• Type: Zero-knowledge proof-based digital signature algorithm
• Security Basis: Relies only on the security of symmetric-key primitives (block ciphers and hash functions)
• Quantum Resistance: Designed to be secure against attacks from quantum computers
• Key Sizes: Very small public and private keys
• Signature Size: Moderate to large signatures (depending on the parameter set)
• Variants: Multiple parameter sets with different security levels and performance characteristics

How Picnic Works:

Picnic uses a "MPC-in-the-head" approach to create zero-knowledge proofs:

1. Key Generation:
   • Generate a random private key (a symmetric key)
   • Encrypt a fixed plaintext with this key using a block cipher
   • The public key consists of the plaintext and ciphertext pair
2. Signing:
   • Create a zero-knowledge proof that demonstrates knowledge of the private key
   • This proof shows that the signer knows a key that transforms the plaintext to the ciphertext
   • The proof is created using a "multi-party computation in the head" technique
   • The signature consists of this zero-knowledge proof
3. Verification:
   • Verify the zero-knowledge proof using the public key
   • If the proof is valid, the signature is authentic

Parameter Sets:

Picnic offers several parameter sets with different security levels and performance characteristics:

Parameter Set	Security Level	Signature Size	Performance
Picnic-L1-FS	NIST Level 1 (128-bit classical)	Medium	Balanced
Picnic-L1-UR	NIST Level 1 (128-bit classical)	Smaller	Slower
Picnic-L1-full	NIST Level 1 (128-bit classical)	Larger	Faster
Picnic-L3-FS	NIST Level 3 (192-bit classical)	Medium	Balanced
Picnic-L3-UR	NIST Level 3 (192-bit classical)	Smaller	Slower
Picnic-L3-full	NIST Level 3 (192-bit classical)	Larger	Faster
Picnic-L5-FS	NIST Level 5 (256-bit classical)	Medium	Balanced
Picnic-L5-UR	NIST Level 5 (256-bit classical)	Smaller	Slower
Picnic-L5-full	NIST Level 5 (256-bit classical)	Larger	Faster

Advantages of Picnic:

• Minimal Assumptions: Security relies only on well-studied symmetric-key primitives
• Small Keys: Very compact public and private keys
• Flexibility: Multiple parameter sets offering different tradeoffs
• Diversity: Provides a different approach compared to other post-quantum signature schemes

Limitations:

• Signature Size: Larger signatures compared to classical algorithms and some other post-quantum alternatives
• Performance: Signing and verification are computationally intensive