Multi-Target Attacks on the Picnic Signature Scheme and Related Protocols

Abstract

Picnic is a signature scheme that was presented at ACM CCS 2017 by Chase et al. and submitted to NIST's post-quantum standardization project. Among all submissions to NIST's project, Picnic is one of the most innovative, making use of recent progress in construction of practically efficient zero-knowledge (ZK) protocols for general circuits. In this paper, we devise multi-target attacks on Picnic and its underlying ZK protocol, ZKB++. Given access to $S$ signatures, produced by a single or by several users, our attack can (information theoretically) recover the $\kappa$-bit signing key of a user in complexity of about $2^{\kappa - 7}/S$. This is faster than Picnic's claimed $2^{\kappa}$ security against classical (non-quantum) attacks by a factor of $2^7 \cdot S$ (as each signature contains about $2^7$ attack targets). Whereas in most multi-target attacks, the attacker can easily sort and match the available targets, this is not the case in our attack on Picnic, as different bits of information are available for each target. Consequently, it is challenging to reach the information theoretic complexity in a computational model, and we had to perform cryptanalytic optimizations by carefully analyzing ZKB++ and its underlying circuit. Our best attack for $\kappa = 128$ has time complexity of $T = 2^{77}$ for $S = 2^{64}$. Alternatively, we can reach the information theoretic complexity of $T = 2^{64}$ for $S = 2^{57}$, given that all signatures are produced with the same signing key. Our attack exploits a weakness in the way that the Picnic signing algorithm uses a pseudo-random generator. The weakness is fixed in the recent Picnic 2.0 version. In addition to our attack on Picnic, we show that a recently proposed improvement of the ZKB++ protocol (due to Katz, Kolesnikov and Wang) is vulnerable to a similar multi-target attack.

Available format(s)
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2019
Keywords
Cryptanalysismulti-target attackPicnicsignature schemezero-knowledge protocolZKB++MPCblock cipherLowMC.
Contact author(s)
dinuri @ cs bgu ac il
History
2019-02-27: revised
See all versions
Short URL
https://ia.cr/2018/1212

CC BY

BibTeX

@misc{cryptoeprint:2018/1212,
author = {Itai Dinur and Niv Nadler},
title = {Multi-Target Attacks on the Picnic Signature Scheme and Related Protocols},
howpublished = {Cryptology ePrint Archive, Paper 2018/1212},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/1212}},
url = {https://eprint.iacr.org/2018/1212}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.