Picnic: Signatures from Symmetric Primitives and Zero Knowledge

Picnic: Signatures from Symmetric Primitives and Zero Knowledge

Introduction

Most signature schemes rest on a hard algebraic problem. RSA uses factoring, and ECDSA uses the discrete logarithm. Picnic takes another road. Its only ingredients are a block cipher and a hash function. The public key is a plaintext and its encryption, and the private key is the cipher key. The signature is a zero-knowledge proof that the signer knows that key, tied to the message.

The proof system is the interesting part. It uses the idea of MPC in the head: the signer simulates a computation between three imaginary parties, commits to what each party saw, and lets a hash decide which two of the three views to open. This guide builds Picnic-L1-FS from the specification of the third round, version 3.0. My code reproduces the signatures of all 100 official known-answer tests byte for byte.

Picnic was a candidate in the NIST post-quantum process, and it was not selected. The story is still worth knowing. The same proof idea lives on in later designs, and the scheme shows how a signature can be built from almost nothing. For other hash-based and structured designs, see the SPHINCS+ guide and the XMSS and LMS guide. The Dilithium guide covers the lattice signature that NIST standardized.

Table of Contents

• History and Standards
• The Idea: Proving Knowledge of a Key
• LowMC: a Cipher with Few AND Gates
• Three Parties in One Head
• Commitments and the Challenge
• The Signature and Its Size
• Verification
• Why 219 Repetitions
• Other Parameter Sets and Picnic3
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Where It Stands
• Limitations
• Security Status
• FAQ
• References

History and Standards

Picnic comes from a research line on zero-knowledge proofs for Boolean circuits. The specification names ZKBoo, a 2016 paper by Giacomelli, Madsen, and Orlandi. It also names ZKB++, an optimized variant of ZKBoo from the ACM CCS 2017 paper “Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives”. That paper turns the proof into a signature scheme. A second proof system, by Katz, Kolesnikov, and Wang, appeared at CCS in 2018, and it gave much shorter signatures.

The design team has 12 members, from Microsoft, DFINITY, Princeton, the University of Maryland, Graz University of Technology, Georgia Tech, Aarhus University, the AIT Austrian Institute of Technology, and Northwestern University. The specification lists Greg Zaverucha as the contact. It went through several versions:

• Version 1.1 changed how the random tapes are derived. Itai Dinur and Niv Nadler found that, without a salt, an attacker could guess a seed, rebuild its tape, and match it against the tapes of many signatures. Given the seed, the attacker could solve for the secret key. The fix adds a random salt.
• Version 2.0 added the proof system of Katz, Kolesnikov, and Wang.
• Version 3.0, dated 30 September 2020, replaced those parameters with the Picnic3 sets and added the “full” sets, which use a cipher with a full S-box layer.

NIST made Picnic a third-round alternate candidate for signatures, together with GeMSS and SPHINCS+. The third-round report, NIST IR 8413, removed it from consideration. It gives this reason: NIST chose to standardize SPHINCS+, and Picnic and SPHINCS+ have similar profiles, with small public keys and large signatures. The report adds that the security of Picnic is not better than that of SPHINCS+. It says that SPHINCS+ is a mature design and that Picnic and related schemes would continue to benefit from future research.

The Idea: Proving Knowledge of a Key

The public key is a pair (C, p). The plaintext p is a random block, and C = E(sk, p) is its encryption under the secret key sk with the cipher E. Finding sk from (C, p) is a key-recovery problem for a block cipher. The scheme assumes that this is hard.

To sign a message, the signer proves in zero knowledge that it knows an sk with E(sk, p) = C. The message is mixed into the hash that makes the proof non-interactive, so the proof is bound to it. This is the Fiat-Shamir transform, and the sets with the letters FS in their names use it. The sets with UR use the Unruh transform, which gives a proof that is secure in the quantum random oracle model at the price of larger signatures.

Here is how the interactive proof works in three steps.

1. Share the key. The prover splits sk into three random shares x0, x1, x2 with x0 xor x1 xor x2 = sk. Any two shares look random, and they reveal nothing about sk.
2. Compute in the head. The prover simulates three parties. Each holds one share, and together they compute E(sk, p) without any party learning sk. Each party ends with an output share. The three output shares XOR to C. The prover records what each party saw, which is its view, and commits to the three views.
3. Open two. The verifier picks e in {0, 1, 2}. The prover opens the views of parties e and e + 1. The verifier replays the computation for those two parties, checks their commitments, and checks that the outputs fit C.

Two opened views reveal nothing about the key, since any two shares are random. A cheating prover, who does not know a valid key, cannot make all three possible challenges pass. The verifier catches the cheat in at least one of the three cases, so one round has a soundness error of 2/3. Repeating the round T times drives that error down.

LowMC: a Cipher with Few AND Gates

In the three-party computation, XOR and linear maps are free. Each party applies them to its own share. An AND gate is expensive, because the parties must exchange information. A cipher for Picnic should therefore have as few AND gates as possible. AES has many of them. LowMC was designed for this setting, and Picnic uses it.

A LowMC instance has a block size and key size n, a number s of S-boxes per round, and r rounds. Level 1 of Picnic-FS uses n = 128, s = 10, and r = 20. One round does these things:

1. S-box layer. The first 3s = 30 bits of the state go through 10 copies of the 3-bit S-box (a, b, c) -> (a xor bc, a xor b xor ac, a xor b xor c xor ab). The other 98 bits pass unchanged.
2. Linear layer. The state is multiplied by a 128 by 128 matrix over GF(2).
3. Round constant. It is added to the state.
4. Round key. It is added to the state, and it is the key multiplied by another matrix.

The cipher starts with a whitening step: the plaintext plus the key times a matrix. The matrices and the constants are fixed. The specification takes them without change from the LowMC reference implementation, and they are part of the package. There are 21 key matrices, 20 linear matrices, and 20 constants, which is 84,288 bytes. I read them from lowmc_constants.c with a short script, and the script is below with the other code.

The S-box has three AND gates, so a round has 30 of them, and the whole cipher has 3 r s = 600. Each gate costs one bit of transcript for each party. The design document gives the security margin of these parameters. For Level 1, the best known attack reaches 12 of the 20 rounds, and that attack needs two plaintext and ciphertext pairs for the same key. In Picnic an attacker sees one pair for each key. The document also notes that the authors of LowMC recommend 1.3 times as many rounds as a margin, and that Picnic does not use the extra rounds.

Three Parties in One Head

The signer needs to evaluate LowMC on shares. For the linear parts this is simple.

• Adding a constant. Only party 0 adds the constant, so the XOR of the shares changes by that constant.
• Multiplying by a matrix. Each party multiplies its own share, because the map is linear.
• Adding the round key. Each party adds its share of the round key, which it gets from its key share and the key matrix.

An AND gate on shared bits needs more. Let a and b be bits that are shared among the three parties as a0, a1, a2 and b0, b1, b2. Each party also has a random bit r_i from its random tape. Party i computes this value, with indices taken modulo 3:

c_i = (a_i AND b_(i+1)) XOR (a_(i+1) AND b_i) XOR (a_i AND b_i) XOR r_i XOR r_(i+1)

The three results XOR to a AND b. The random bits cancel, because each r_i appears twice. Each party writes its c_i into its transcript. The party before it, with index i - 1, needs that bit to replay the gate. The transcript of a party is the list of the 600 bits c_i that it computed.

The random tapes come from the seeds. For party j in repetition t, the specification gives

tape = SHAKE128( H2(seed) || salt || t || j || output length )

where H2(x) is SHAKE128 of the byte 0x02 followed by x, the numbers t, j, and the length are 16-bit integers in little-endian order, and salt has 32 bytes. For parties 0 and 1 the tape is 16 + 75 bytes: the first 16 bytes are the key share, and the other 75 bytes hold the 600 bits for the AND gates. Party 2 has only the 75 bytes, and its key share is x2 = sk xor x0 xor x1. The seeds and the salt are not random in the specification. They come from SHAKE128 of the secret key, the message, the public key, and the number 128. A signature is therefore a deterministic function of the key and the message.

In the specification, bit 0 of a string is the most significant bit of the first byte. My code follows that order. This detail matters for matching the official signatures.

Commitments and the Challenge

After the simulation, each party has a view: its input share, its transcript, and its output share. The signer commits to each view with a hash:

C_j = SHAKE128( 0x00 || H4(seed_j) || input share || transcript || output share )

The commitment has 32 bytes. Hashing the seed first with H4 keeps the raw seed out of the commitment. The seed is revealed for the opened parties, and H4(seed) is what the commitment binds.

The challenge comes from one hash of everything the signer has committed to:

1. All the output shares of all repetitions, 3 shares of 16 bytes for each of the 219.
2. All the commitments, 3 of 32 bytes for each repetition.
3. The public key (C, p), the salt, and the message.

The hash is SHAKE128 with the prefix 0x01, and it gives 32 bytes. Read as pairs of bits, 00 gives the value 0, 01 gives 1, 10 gives 2, and 11 is skipped. If 32 bytes do not yield 219 values, the hash of the hash gives more. This is the function H3 of the specification. The result is one value e in {0, 1, 2} for each of the 219 repetitions.

The Signature and Its Size

For the repetition with challenge e, the signature contains the proof that the verifier needs to replay parties e and e + 1:

• the commitment of the third party, e + 2, 32 bytes;
• the transcript of party e + 1, 75 bytes;
• the seeds of parties e and e + 1, 16 bytes each;
• the input share of party 2, 16 bytes, only if e is 1 or 2.

When e is 0, the opened parties 0 and 1 derive their input shares from their seeds. When e is 1 or 2, party 2 is opened, and its input share sk xor x0 xor x1 cannot come from a seed. This is why those rounds need the 16 extra bytes.

In front of these proofs stand the challenge, packed as 2 bits for each repetition, which is 55 bytes, and the salt of 32 bytes. The total length in bytes is the following sum:

55 + 32 + 219 x (32 + 75 + 16 + 16) + 16 x (number of challenges that are not 0)

so the length depends on the challenge. With no zero challenge it is the maximum, 34,032 bytes. With all challenges equal to 0 it is 30,528. The specification lists a maximum of 34,032 bytes for this set. That equals the maximum I compute, and it shows that the serialization is understood correctly. Over the 100 known-answer tests, the sizes range from 32,592 to 33,104 bytes, with a mean of 32,872 and a standard deviation of 114. The specification gives a mean of 32,838 and a deviation of 107 for its own sample of 100 signatures. The public key has 32 bytes and the private key 16.

Verification

The verifier first checks the format. The challenge must contain no pair of bits equal to 3, the padding bits at its end must be zero, and the total length must match the length that the challenge requires. A signature that fails these checks is rejected before any hashing.

Then the verifier handles each repetition on its own:

1. Rebuild the random tapes of the two opened parties from their seeds, with the salt and the repetition number. For e = 1 or e = 2, one of the key shares comes from the signature.
2. Run LowMC on the two shares. Wherever an AND gate needs the bit of the second party, the verifier reads it from the transcript in the signature. The first party’s bit it computes itself, and it stores it.
3. Recompute the commitments of the two opened parties from their seeds, input shares, transcripts, and output shares.
4. Take the commitment of the third party from the signature. Compute the third party’s output share as o_e xor o_(e+1) xor C. That is the only value that the output shares may have if they XOR to C.

After all 219 repetitions, the verifier recomputes the challenge hash from the rebuilt output shares and commitments. If it equals the challenge in the signature, the signature is valid.

The check works because any change to an opened view alters its commitment, and so the hash. A change to the unopened party in a single round is hidden behind its commitment, and it matters only if the challenge would have opened it. This is the 2/3 argument in practice.

Why 219 Repetitions

One repetition has a soundness error of 2/3, so a cheater may get away with a round when the challenge falls on the lucky value. For T repetitions, a cheater has to be lucky in all of them, and the Fiat-Shamir hash gives the challenge pseudo-randomly. The design document chooses T so that (3/2)^T is at least 2^128. I compute (3/2)^219 as 2^128.11. At 218 repetitions it is 2^127.52, which falls short, so 219 is the smallest value.

My tests show the mechanism with a toy value. I set T = 4 and built a cheater that does not know the key. The cheater runs the simulation with a wrong key and then repairs the output share of party 2 so that the three output shares XOR to C. If the challenge is 0, the verifier opens parties 0 and 1 and never sees the repair, so the round passes. If the challenge is 1 or 2, the repaired party is opened, the replay gives a different output share, and the hash changes. The cheater tries new seeds until all four challenges are 0, which happens with probability (1/3)^4. In 20 trials, the verifier accepted a forged signature every time, after 98 attempts on average, where the expected number is 81. With T = 219 this naive cheater would need 3^219 attempts.

The soundness error of a real repetition is 2/3, which is the figure of the design document. My toy cheater is weaker, because it passes a round with probability 1/3. I did not search for a better strategy. For 128 bits of security against quantum attackers, the design document asks for 438 repetitions, because Grover’s algorithm halves the exponent. The specification claims at least S / 2 bits against quantum attacks for its sets, where S is the classical level.

Other Parameter Sets and Picnic3

The specification defines twelve parameter sets. All share the same ideas. The table lists the ones with the ZKB++ proof and their Fiat-Shamir or Unruh transform. The sizes are the maxima of the specification.

Set	LowMC (n, s, r)	Repetitions	Hash	Signature, maximum
picnic-L1-FS	128, 10, 20	219	SHAKE128	34,032 bytes
picnic-L1-UR	128, 10, 20	219	SHAKE128	53,961 bytes
picnic-L3-FS	192, 10, 30	329	SHAKE256	76,772 bytes
picnic-L5-FS	256, 10, 38	438	SHAKE256	132,856 bytes
picnic3-L1	129, 43, 4	250 (36 opened), 16 parties	SHAKE128	13,802 bytes
picnic3-L3	192, 64, 4	419 (52 opened), 16 parties	SHAKE256	29,750 bytes
picnic3-L5	255, 85, 4	601 (68 opened), 16 parties	SHAKE256	54,732 bytes

The “full” sets and Picnic3 use a LowMC instance with a full S-box layer: every state bit goes through an S-box in every round, and the number of rounds drops to 4. The state size is then a multiple of 3, so Level 1 uses 129 bits and Level 5 uses 255. The change notes of the team say that this reduces the cost of signing and verification by a factor of 1.3 to 1.8 for the ZKB++ sets.

Picnic3 uses the proof of Katz, Kolesnikov, and Wang. It simulates 16 parties instead of 3. The signer prepares and simulates 250 repetitions, and the challenge selects 36 of them. For those 36 the signature opens 15 of the 16 parties. For the other 214 it reveals only the seed, and the verifier redoes the preparation from it. The seeds are revealed through a binary seed tree, and the commitments of the online phase go into a Merkle tree. This cuts the signature to at most 13,802 bytes, about 40 percent of the ZKB++ size. The team recommends Picnic-full when speed matters more than size and Picnic3 when size matters more than speed. It moved the six FS and UR sets to historical status.

I implemented only Picnic-L1-FS, which the specification covers in section 6. The Picnic3 procedures of section 7 are described here from the specification, and I did not implement or test them.

Interactive Visualizer

The visualizer above runs the real Picnic-L1-FS in your browser. It has two variants.

• Sign and verify. Enter the secret key, the plaintext of the public key, and a message. The log shows the public key, the seeds, the key shares, the three-party computation, the commitments, the challenge, the proof, the signature size, and the verification of all 219 repetitions. A field selects which repetition to show in detail.
• The LowMC cipher alone. It encrypts one block and shows the state after each of the 20 rounds.

The field for bits to flip changes bits of the signature before it is verified, so you can see a single flipped bit being rejected. Bit k is bit k mod 8 of byte k div 8, counting from the lowest bit. The result line shows the SHAKE128 digest of the signature instead of the 32,960 bytes. The default values are the key and message of the first known-answer test, so the digest is the one of the official signature.

A Worked Example

The first known-answer test of picnicl1fs starts from the 48-byte seed 061550234d158c5ec95595fe04ef7a25767f2e24cc2bc479d09d86dc9abcfde7056a8c266f9ef97ed08541dbd2e1ffa1. The random generator of the test suite gives the secret key 7c9935a0b07694aa0c6d10e4db6b1add and the plaintext 91282214654cb55e7c2cacd53919604d. LowMC encryption gives C = 515486e906d9d106e5976de2740fd982. The public key of the file begins with the byte 01, which names the parameter set, followed by C and p, and it matches the file.

The message has 33 bytes. The salt that SHAKE128 derives from the key and the message is d0a36ef85e4406fd01f95fb2d5e942c5b5d68325802dd8aafa845f503ea3309d. For repetition 0, the seed of party 0 is 65592f1bd53345611ff2a312c7bd2a7e, and the three key shares are:

x0 = f55e61f4e4df0b9061c900f81ad63cee
x1 = 3de0012d0729b5f15a3e0eae0ca3bdaa
x2 = b427557953802acb379a1eb2cd1e9b99

Their XOR is the secret key. After the simulation, the three output shares are:

o0 = 58396904c51e5aaf4ec3ba708e29fd2b
o1 = 64fabce8987c77ad542bbd6083e0618a
o2 = 6d9753055bbbfc04ff7f6af279c64523

Their XOR is C. The transcripts of the three parties have 297, 281, and 304 bits equal to 1 out of 600, as you would expect from random bits. The transcript of party 0 starts with the bytes 42db78115440dc1d09c7a8f6. The commitments of this repetition begin with 46f4280aada960d6426901a19d61f71279f65b6bec65cc8cebef6325aadf69c6, 3bbe1e28ec084c04c35b4bd8e8ec3b09b4018c8263a1053a81cfce9034edc512, and c3bde418469930f63ffd459292fdf049e93825b823414deb009c67466976406a.

The challenge begins with 2212021010101022. Over 219 repetitions the value 0 occurs 67 times, the value 1 occurs 75 times, and 2 occurs 77 times, so 152 rounds carry an input share. The signature has 32,960 bytes, equal to 55 + 32 + 219 x 139 + 152 x 16. The test file says smlen = 32997, which is the signature plus the 4-byte length and the message. The signature begins with 591888850152246819685a285924220a64a5419a16a18465, and its SHAKE128 digest is:

462dd3328c6accdf91ad44b91d1569b80a99ee7caa90e72d7a45993f588b3f5f

Python Implementation

This is Picnic-L1-FS from the specification. A vector of 128 bits is a Python integer, with bit 0 of the specification as the top bit. First comes the script that reads the LowMC constants from the package.

# Reads the LowMC constants of Picnic-L1-FS (128 bit block, 20 rounds, 10 S-boxes) straight from
# lowmc_constants.c of the NIST package and writes them as one JSON file of hex strings.
import json
import re
import sys

source = sys.argv[1]
out = sys.argv[2]
wanted = {"linearMatrices_L1": (20, 128 * 16), "keyMatrices_L1": (21, 128 * 16), "roundConstants_L1": (20, 16)}
found = {}
for line in open(source, encoding="utf-8", errors="replace"):
    m = re.match(r"static const uint8_t (\w+)\[(\d+)\] = \{(.*)\};", line.strip())
    if m and m.group(1) in wanted:
        name, size, body = m.group(1), int(m.group(2)), m.group(3)
        data = bytes(int(x, 16) for x in re.findall(r"0x([0-9A-Fa-f]{2})", body))
        count, each = wanted[name]
        assert len(data) == size == count * each, (name, len(data), size)
        found[name] = [data[i * each:(i + 1) * each].hex() for i in range(count)]
assert set(found) == set(wanted)
json.dump(found, open(out, "w"))
print({k: len(v) for k, v in found.items()})

Then comes the scheme itself. The file lowmc_l1.json is the output of the script.

# picnic.py
# Picnic-L1-FS: the signature scheme of the Picnic submission (round 3, specification v3.0, section 6),
# written from the specification and checked against the NIST package. A vector of n bits is a Python
# integer. Bit number i of the specification (bit 0 is the first one) is the bit (n - 1 - i) of the integer,
# which is the order of a byte string read from the first byte and from the most significant bit.
import hashlib
import json
import os

N = 128            # the block size and key size of LowMC, in bits
ROUNDS = 20        # the number of rounds of LowMC
SBOXES = 10        # the number of S-boxes per round, so only the first 30 bits go through an S-box
T = 219            # the number of parallel repetitions of the proof
SEED_BYTES = 16
SALT_BYTES = 32
DIGEST_BYTES = 32
STATE_BYTES = N // 8
AND_BITS = 3 * ROUNDS * SBOXES          # one AND gate costs one bit of the transcript, 3 per S-box
AND_BYTES = (AND_BITS + 7) // 8

_constants = json.load(open(os.path.join(os.path.dirname(__file__), "lowmc_l1.json")))
K_MATRICES = [[int.from_bytes(bytes.fromhex(m)[16 * i:16 * i + 16], "big") for i in range(N)] for m in _constants["keyMatrices_L1"]]
L_MATRICES = [[int.from_bytes(bytes.fromhex(m)[16 * i:16 * i + 16], "big") for i in range(N)] for m in _constants["linearMatrices_L1"]]
ROUND_CONSTANTS = [int.from_bytes(bytes.fromhex(c), "big") for c in _constants["roundConstants_L1"]]


def bit(x, i, n=N):
    return (x >> (n - 1 - i)) & 1


def set_bit(x, i, value, n=N):
    mask = 1 << (n - 1 - i)
    return (x & ~mask) | (value * mask)


def matrix_mul(x, rows):
    # bit i of the result is the parity of x AND row i
    out = 0
    for row in rows:
        out = (out << 1) | ((x & row).bit_count() & 1)
    return out


# ---------------------------------------------------------------- LowMC

def sbox_layer(state):
    for i in range(0, 3 * SBOXES, 3):
        a, b, c = bit(state, i + 2), bit(state, i + 1), bit(state, i)
        state = set_bit(state, i + 2, a ^ (b & c))
        state = set_bit(state, i + 1, a ^ b ^ (a & c))
        state = set_bit(state, i, a ^ b ^ c ^ (a & b))
    return state


def lowmc_encrypt(plaintext, key):
    state = plaintext ^ matrix_mul(key, K_MATRICES[0])
    for r in range(1, ROUNDS + 1):
        state = sbox_layer(state)
        state = matrix_mul(state, L_MATRICES[r - 1])
        state ^= ROUND_CONSTANTS[r - 1]
        state ^= matrix_mul(key, K_MATRICES[r])
    return state


# ---------------------------------------------------------------- hashes (SHAKE128 at level 1)

def shake(data, length):
    return hashlib.shake_128(data).digest(length)


def H(prefix, *parts, length=DIGEST_BYTES):
    # H_i(x) = SHAKE128(0x0i || x)
    return shake(bytes([prefix]) + b"".join(parts), length)


def le16(x):
    return x.to_bytes(2, "little")


def to_bytes(x):
    return x.to_bytes(STATE_BYTES, "big")


def from_bytes(b):
    return int.from_bytes(b, "big")


def random_tape(seed, salt, t, j, length):
    # rand[j] = KDF(H2(seed) || salt || t || j || output length)
    return shake(H(2, seed) + salt + le16(t) + le16(j) + le16(length), length)


def tape_bit(tape, pos):
    return (tape[pos >> 3] >> (7 - (pos & 7))) & 1


def set_tape_bit(buf, pos, value):
    if value:
        buf[pos >> 3] |= 1 << (7 - (pos & 7))


# ---------------------------------------------------------------- the keys

def keygen(sk_bytes, p_bytes):
    # the secret key and the plaintext are random in the specification; here they are given
    sk, p = from_bytes(sk_bytes), from_bytes(p_bytes)
    c = lowmc_encrypt(p, sk)
    return sk_bytes, (to_bytes(c), p_bytes)


# ---------------------------------------------------------------- the MPC simulation of LowMC by three parties

def mpc_and(a, b, tapes, pos, comm):
    # a and b are lists of three bits (one per party); comm[i] collects the bits that party i sent
    r = [tape_bit(tapes[i], pos) for i in range(3)]
    c = [0, 0, 0]
    for i in range(3):
        c[i] = (a[i] & b[(i + 1) % 3]) ^ (a[(i + 1) % 3] & b[i]) ^ (a[i] & b[i]) ^ r[i] ^ r[(i + 1) % 3]
        set_tape_bit(comm[i], pos, c[i])
    return c


def mpc_sbox_layer(state, tapes, pos, comm):
    for i in range(0, 3 * SBOXES, 3):
        a = [bit(s, i + 2) for s in state]
        b = [bit(s, i + 1) for s in state]
        c = [bit(s, i) for s in state]
        ab = mpc_and(a, b, tapes, pos, comm)
        bc = mpc_and(b, c, tapes, pos + 1, comm)
        ca = mpc_and(c, a, tapes, pos + 2, comm)
        pos += 3
        for j in range(3):
            s = set_bit(state[j], i + 2, a[j] ^ bc[j])
            s = set_bit(s, i + 1, a[j] ^ b[j] ^ ca[j])
            state[j] = set_bit(s, i, a[j] ^ b[j] ^ c[j] ^ ab[j])
    return pos


def mpc_lowmc(plaintext, key_shares, tapes):
    comm = [bytearray(AND_BYTES) for _ in range(3)]
    state = [plaintext, 0, 0]                                       # the public constant goes into share 0
    for j in range(3):
        state[j] ^= matrix_mul(key_shares[j], K_MATRICES[0])
    pos = 0
    for r in range(1, ROUNDS + 1):
        pos = mpc_sbox_layer(state, tapes, pos, comm)
        for j in range(3):
            state[j] = matrix_mul(state[j], L_MATRICES[r - 1])
        state[0] ^= ROUND_CONSTANTS[r - 1]
        for j in range(3):
            state[j] ^= matrix_mul(key_shares[j], K_MATRICES[r])
    return state, [bytes(c) for c in comm]


def commit(seed, input_share, comm, output_share):
    # C = H0(H4(seed), view), with the view as input share, transcript, output share
    return H(0, H(4, seed), to_bytes(input_share), comm, to_bytes(output_share))


def challenge_from_hash(output_shares, commitments, c_bytes, p_bytes, salt, message):
    # H3: the hash of everything, read as pairs of bits, 00 -> 0, 01 -> 1, 10 -> 2, 11 skipped
    data = b"".join(to_bytes(o) for row in output_shares for o in row)
    data += b"".join(c for row in commitments for c in row)
    data += c_bytes + p_bytes + salt + message
    h = H(1, data)
    trits = []
    while True:
        for byte in h:
            for shift in (6, 4, 2, 0):
                pair = (byte >> shift) & 3
                if pair < 3:
                    trits.append(pair)
                    if len(trits) == T:
                        return trits
        h = H(1, h)


def pack_challenge(trits):
    out = bytearray((2 * T + 7) // 8)
    for t, e in enumerate(trits):
        set_tape_bit(out, 2 * t, e & 1)
        set_tape_bit(out, 2 * t + 1, (e >> 1) & 1)
    return bytes(out)


def unpack_challenge(data):
    return [(tape_bit(data, 2 * t + 1) << 1) | tape_bit(data, 2 * t) for t in range(T)]


# ---------------------------------------------------------------- signing

def derive_seeds(sk_bytes, message, c_bytes, p_bytes):
    blob = shake(sk_bytes + message + c_bytes + p_bytes + le16(N), T * 3 * SEED_BYTES + SALT_BYTES)
    seeds = [[blob[(3 * t + j) * SEED_BYTES:(3 * t + j + 1) * SEED_BYTES] for j in range(3)] for t in range(T)]
    return seeds, blob[T * 3 * SEED_BYTES:]


def sign(sk_bytes, pk, message, trace=None):
    c_bytes, p_bytes = pk
    sk, p, c = from_bytes(sk_bytes), from_bytes(p_bytes), from_bytes(c_bytes)
    seeds, salt = derive_seeds(sk_bytes, message, c_bytes, p_bytes)
    views, commitments, outputs = [], [], []
    for t in range(T):
        tapes, shares = [None] * 3, [0] * 3
        for j in range(2):
            raw = random_tape(seeds[t][j], salt, t, j, STATE_BYTES + AND_BYTES)
            shares[j] = from_bytes(raw[:STATE_BYTES])
            tapes[j] = raw[STATE_BYTES:]
        tapes[2] = random_tape(seeds[t][2], salt, t, 2, AND_BYTES)
        shares[2] = sk ^ shares[0] ^ shares[1]
        out, comm = mpc_lowmc(p, shares, tapes)
        assert out[0] ^ out[1] ^ out[2] == c, "the simulation must end at the public ciphertext"
        views.append((shares, comm, out))
        commitments.append([commit(seeds[t][j], shares[j], comm[j], out[j]) for j in range(3)])
        outputs.append(out)
    trits = challenge_from_hash(outputs, commitments, c_bytes, p_bytes, salt, message)
    body = b""
    for t, e in enumerate(trits):
        shares, comm, _ = views[t]
        body += commitments[t][(e + 2) % 3] + comm[(e + 1) % 3] + seeds[t][e] + seeds[t][(e + 1) % 3]
        if e != 0:
            body += to_bytes(shares[2])
    if trace is not None:
        trace.update(trits=trits, salt=salt, seeds=seeds, views=views, commitments=commitments)
    return pack_challenge(trits) + salt + body


# ---------------------------------------------------------------- verification

def signature_length(trits):
    per_round = DIGEST_BYTES + AND_BYTES + 2 * SEED_BYTES
    return (2 * T + 7) // 8 + SALT_BYTES + T * per_round + STATE_BYTES * sum(1 for e in trits if e != 0)


def parse_signature(sig):
    # the checks of the deserialization of section 6.5.2
    head = (2 * T + 7) // 8
    if len(sig) < head + SALT_BYTES:
        return None
    challenge_bytes = sig[:head]
    trits = unpack_challenge(challenge_bytes)
    if any(e == 3 for e in trits):
        return None
    if pack_challenge(trits) != challenge_bytes:      # the padding bits must be zero
        return None
    if len(sig) != signature_length(trits):
        return None
    salt, pos, rounds = sig[head:head + SALT_BYTES], head + SALT_BYTES, []
    for e in trits:
        c3 = sig[pos:pos + DIGEST_BYTES]; pos += DIGEST_BYTES
        comm = sig[pos:pos + AND_BYTES]; pos += AND_BYTES
        s1 = sig[pos:pos + SEED_BYTES]; pos += SEED_BYTES
        s2 = sig[pos:pos + SEED_BYTES]; pos += SEED_BYTES
        share = None
        if e != 0:
            share = from_bytes(sig[pos:pos + STATE_BYTES]); pos += STATE_BYTES
        rounds.append((c3, comm, s1, s2, share))
    return trits, salt, rounds


def verify(pk, message, sig):
    parsed = parse_signature(sig)
    if parsed is None:
        return False
    trits, salt, rounds = parsed
    c_bytes, p_bytes = pk
    p, c = from_bytes(p_bytes), from_bytes(c_bytes)
    outputs, commitments = [], []
    for t, (e, (c3, comm2, seed1, seed2, share)) in enumerate(zip(trits, rounds)):
        if e == 0:
            raw1 = random_tape(seed1, salt, t, 0, STATE_BYTES + AND_BYTES)
            raw2 = random_tape(seed2, salt, t, 1, STATE_BYTES + AND_BYTES)
            x1, tape1, x2, tape2 = from_bytes(raw1[:STATE_BYTES]), raw1[STATE_BYTES:], from_bytes(raw2[:STATE_BYTES]), raw2[STATE_BYTES:]
        elif e == 1:
            raw1 = random_tape(seed1, salt, t, 1, STATE_BYTES + AND_BYTES)
            x1, tape1 = from_bytes(raw1[:STATE_BYTES]), raw1[STATE_BYTES:]
            x2, tape2 = share, random_tape(seed2, salt, t, 2, AND_BYTES)
        else:
            x1, tape1 = share, random_tape(seed1, salt, t, 2, AND_BYTES)
            raw2 = random_tape(seed2, salt, t, 0, STATE_BYTES + AND_BYTES)
            x2, tape2 = from_bytes(raw2[:STATE_BYTES]), raw2[STATE_BYTES:]
        # the two opened parties are e and e + 1; party 0 holds the public constants, so it is
        # the first opened party when e = 0, the second one when e = 2, and not opened when e = 1
        constant_slot = 0 if e == 0 else (1 if e == 2 else None)
        key = [x1, x2]
        state = [0, 0]

        def add_constant(value):
            if constant_slot is not None:
                state[constant_slot] ^= value

        add_constant(p)
        for j in range(2):
            state[j] ^= matrix_mul(key[j], K_MATRICES[0])
        comm1 = bytearray(AND_BYTES)
        pos = 0
        tapes = [tape1, tape2]
        for r in range(1, ROUNDS + 1):
            for i in range(0, 3 * SBOXES, 3):
                a = [bit(s, i + 2) for s in state]
                b = [bit(s, i + 1) for s in state]
                cc = [bit(s, i) for s in state]
                products = []
                for (u, v) in ((a, b), (b, cc), (cc, a)):
                    r0, r1 = tape_bit(tapes[0], pos), tape_bit(tapes[1], pos)
                    out0 = (u[0] & v[1]) ^ (u[1] & v[0]) ^ (u[0] & v[0]) ^ r0 ^ r1
                    set_tape_bit(comm1, pos, out0)
                    products.append([out0, tape_bit(comm2, pos)])     # the other party's bit is read from the signature
                    pos += 1
                ab, bc, ca = products
                for j in range(2):
                    s = set_bit(state[j], i + 2, a[j] ^ bc[j])
                    s = set_bit(s, i + 1, a[j] ^ b[j] ^ ca[j])
                    state[j] = set_bit(s, i, a[j] ^ b[j] ^ cc[j] ^ ab[j])
            for j in range(2):
                state[j] = matrix_mul(state[j], L_MATRICES[r - 1])
            add_constant(ROUND_CONSTANTS[r - 1])
            for j in range(2):
                state[j] ^= matrix_mul(key[j], K_MATRICES[r])
        c1 = commit(seed1, x1, bytes(comm1), state[0])
        c2 = commit(seed2, x2, comm2, state[1])
        row_commit, row_out = [None] * 3, [None] * 3
        row_commit[e], row_commit[(e + 1) % 3], row_commit[(e + 2) % 3] = c1, c2, c3
        row_out[e], row_out[(e + 1) % 3], row_out[(e + 2) % 3] = state[0], state[1], state[0] ^ state[1] ^ c
        commitments.append(row_commit)
        outputs.append(row_out)
    return challenge_from_hash(outputs, commitments, c_bytes, p_bytes, salt, message) == trits


if __name__ == "__main__":
    # the key and the message of the first known-answer test of the NIST package (picnicl1fs)
    sk_bytes = bytes.fromhex("7c9935a0b07694aa0c6d10e4db6b1add")
    p_bytes = bytes.fromhex("91282214654cb55e7c2cacd53919604d")
    message = bytes.fromhex("d81c4d8d734fcbfbeade3d3f8a039faa2a2c9957e835ad55b22e75bf57bb556ac8")
    sk_bytes, pk = keygen(sk_bytes, p_bytes)
    print("ciphertext C of the public key:", pk[0].hex())
    trace = {}
    signature = sign(sk_bytes, pk, message, trace)
    counts = [trace["trits"].count(v) for v in range(3)]
    print("signature: %d bytes; challenge values 0, 1, 2 occur %s times" % (len(signature), counts))
    print("SHAKE128 digest of the signature:", shake(signature, 32).hex())
    print("verify the signature:", verify(pk, message, signature))
    print("verify another message:", verify(pk, message + b"!", signature))
    damaged = bytearray(signature)
    damaged[1000] ^= 1
    print("verify after one flipped bit:", verify(pk, message, bytes(damaged)))

Running the file signs the message of the first known-answer test:

ciphertext C of the public key: 515486e906d9d106e5976de2740fd982
signature: 32960 bytes; challenge values 0, 1, 2 occur [67, 75, 77] times
SHAKE128 digest of the signature: 462dd3328c6accdf91ad44b91d1569b80a99ee7caa90e72d7a45993f588b3f5f
verify the signature: True
verify another message: False
verify after one flipped bit: False

I checked the code against the official known-answer tests of the Picnic round 3 package, in the file for picnicl1fs. I read the file and the reference code, and I did not run that code. For each of the 100 vectors, the test starts the random generator of the NIST suite with the given seed, which I ported to Python from the code in the package. It draws the secret key and the plaintext, encrypts, and signs the message. The public key, the secret key, and the whole signature match the file byte for byte, and my verifier accepts every signature. The signature of the file is the output of the C implementation of the Picnic team, so the check does not depend on my reading of the specification alone.

The tests also cover rejection. They flip single bits at random positions in each part of a valid signature, in 40 places of the challenge, 40 of the salt, 30 each of commitments, transcripts, and seeds, and 21 of input shares. All of them are rejected. A changed or shortened message, a different public key, a signature one byte too short or too long, a nonzero padding bit, and a challenge pair equal to 3 are rejected too. The toy cheater of the previous section is part of the tests as well. The SHAKE128 of Python matches the known value for the empty string.

The page code has its own SHAKE128 and LowMC. It matches OpenSSL on 700 combinations of input and output length. It reproduces the digests of the first seven known-answer signatures. It matches all 50 test vectors that the Python code produces, including runs with flipped bits, and it gives the right verdict in each. I ran its page in a simulated browser.

Where It Stands

• A NIST candidate that was not selected. Picnic was a third-round alternate. The third-round report removed it from consideration, because NIST chose to standardize SPHINCS+, which has a similar profile. The scheme stays a clear example of a signature built from a block cipher and a hash through MPC in the head, and the Picnic3 sizes show how far the same idea can be improved.
• Large signatures. Picnic-L1-FS signatures have about 33 kilobytes. That is far more than lattice signatures. The Picnic3 sets are about 2.5 times smaller, with a maximum of 13,802 bytes.
• Small keys. A public key has 32 bytes and a private key 16. The security rests on the cipher and the hash.
• A proof system that others reuse. The idea of MPC in the head is not tied to Picnic. The Picnic team writes in the change notes that other cipher choices are possible, and that LowMC was chosen because it gave the smallest signatures.

Limitations

This is a teaching implementation, not a production one:

• Not constant time. Python integers and branches on secret bits leak timing. A real implementation needs constant-time code for LowMC and careful handling of the random tapes.
• Deterministic signing only. The seeds are derived from the key and the message, as in the test vectors. The specification explains that this can help side-channel and fault attacks, and it recommends adding a random value of 2S bits to the derivation.
• Only one parameter set. I did not implement the Unruh variant, the other levels, the full sets, or Picnic3.
• Bit order is easy to get wrong. The order of bits within bytes and the order of the tapes must match the specification exactly. The known-answer tests catch a mistake at once.
• Slow. Signing takes about half a second here, and a C implementation is much faster.
• Message length. The specification says 1 to 255 bytes, and it advises hashing longer messages first. The code does not enforce this.

Security Status

The security of Picnic rests on two assumptions: that LowMC with these parameters is a one-way function when used as in the key pair, and that the hash function behaves like a random oracle. The design document analyses the cipher for this setting. For Level 1, the best attack it names reaches 12 of 20 rounds and needs two pairs for the same key, whereas Picnic reveals one. For the full S-box instances it reports that algebraic attacks reach two rounds with less than brute-force effort, and a meet-in-the-middle tool finds nothing beyond two rounds. The document admits that the parameter choice may look aggressive for a general-purpose cipher.

The team put the FS and UR sets into historical status. The change notes say that there are no known security issues with them, but that the other sets outperform them. The known break of version 1.0 was a flaw in the derivation of the tapes, fixed by the salt, and not a break of the cipher or the proof. NIST’s remark that Picnic and related schemes would benefit from further research is a statement about maturity, and not about a known attack. For a mature hash-based alternative, see the SPHINCS+ guide.

FAQ

What is MPC in the head?

A technique to build zero-knowledge proofs. The prover simulates a secure multiparty computation of a function on secret shares of its input. The verifier looks at the views of a few of the simulated parties, and the privacy of the protocol hides the input. Picnic uses three parties and opens two.

Why does Picnic use LowMC and not AES?

The proof costs about one transcript bit for each AND gate. AES needs many more AND gates than LowMC, so signatures built on AES would be much larger. The design document says that LowMC gave the most efficient signatures.

Why are Picnic signatures so big?

Each of the 219 repetitions needs its own proof of 139 or 155 bytes, because one repetition catches a cheater only with probability 1/3. Many repetitions are needed for 128-bit security, so the signature has about 33 kilobytes.

Is the signature deterministic?

In the specification and the test vectors, yes. The seeds come from the key and the message. A randomized version is allowed, and the specification recommends deriving the seeds as usual and adding a random value as a hedge.

Was Picnic broken?

I found no break of the final parameter sets in the documents I read. An early version had a flaw in the derivation of the random tapes, and it was fixed in version 1.1. NIST did not select Picnic because it chose SPHINCS+ for a similar use case, and said that Picnic would continue to benefit from research.

Which Picnic set is the best?

The team recommends the full sets when speed matters and Picnic3 when size matters. The sets named FS and UR are historical. This guide implements Picnic-L1-FS because its proof is the simplest to follow.

References

1. Zaverucha, Greg, et al. “The Picnic Signature Algorithm Specification,” version 3.0. 30 September 2020. Included in the round 3 submission package. Available at: https://csrc.nist.gov/projects/post-quantum-cryptography

2. The Picnic Design Team. “Picnic Design Document,” version 3.0, and “Summary of Round 3 Changes for Picnic,” 30 September 2020. Included in the round 3 submission package.

3. Chase, Melissa, et al. “Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives.” ACM CCS 2017. Available at: https://eprint.iacr.org/2017/279

4. Katz, Jonathan, Vladimir Kolesnikov, and Xiao Wang. “Improved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures.” ACM CCS 2018.

5. Albrecht, Martin R., et al. “Ciphers for MPC and FHE.” EUROCRYPT 2015. Available at: https://eprint.iacr.org/2016/687

6. Alagic, Gorjan, et al. “Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process.” NIST Internal Report 8413, July 2022, updated 26 September 2022. Available at: https://doi.org/10.6028/NIST.IR.8413-upd1