Welcome to the resource topic for 2018/1212
Title:
Multi-Target Attacks on the Picnic Signature Scheme and Related Protocols
Authors: Itai Dinur, Niv Nadler
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.
ePrint: https://eprint.iacr.org/2018/1212
Talk: https://www.youtube.com/watch?v=BF8BMm9sYBY
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .