Picnic with Friends: Constructing post quantum digital signature schemes

Abstract

Det digitale signatursystemet, Picnic [5], er et post-kvantesystem som ble introdusert som en del av NIST-prosessen for å standardisere post-kvantekryptografi [15]. Vi ser på hvordan Picnic er konstruert, og sikkerhetsegenskapene til systemet. Vi begynner med å introdusere noen kryptografiske konsepter som er brukt i systemet, blant annet kunnskapsbeviser, kunnskapsløse bevis, enveisfunksjoner og flerpartsberegning. Picnic består av en enveisfunksjon, som er instansiert med blokkchifferet LowMC [1], og et NIZK-kunnskapsbevis, det vil si et ikke-interaktivt kunnskapsbevis som ikke avslører hemmeligheten (”kunnskapsløst”), som er instansiert med ZKB++. ZKB++ er konstruert fra sigma-protokollen ZKBoo [10], som er et kunnskapsbevis som ikke avslører hemmeligheten. ZKBoo bruker også en teknikk som kalles MPC-in-the-head for å oppnå kunnskapsløshet med en ærlig verifisierings-part (HVZK). Noen optimaliseringer er gjort for å forbedre ZKBoo, i tillegg til at protokollen er gjort ikke-interaktiv ved å bruke Unruh’s transform [18]. Dette resulterer i ZKB++-protokollen. Signatursystemet vi får fra dette, Picnic, har sikkerhet mot EUF-CMA-angrep og reduserer bare til symmetrisk-nøkkel-primitiver.

The Picnic [5] digital signature scheme is a post-quantum scheme introduced as part of the NIST standardisation process for post-quantum cryptography [15]. We look at how Picnic is constructed and its security properties. We begin by introducing several cryptographic concepts that are used in the scheme, among these proofs of knowledge, zero knowledge, one-way functions and multi-party computation. Picnic consists of a one-way function, which is instantiated with the block cipher LowMC [1], and a non-interactive zero knowledge (NIZK) proof of knowledge, which is instantiated with ZKB++. ZKB++ is constructed based on the sigma protocol ZKBoo [10], which is a zero knowledge proof of knowledge. ZKBoo also uses a technique called MPC-in-the-head to achieve honest verifier zero knowledge (HVZK). Some optimisations are made to ZKBoo, and the protocol is made non-interactive using Unruh’s transform [18], resulting in the ZKB++ scheme. The resulting signature scheme, Picnic, has EUF-CMA security, which reduces solely to symmetric-key primitives.