Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden.
powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden.
powered by
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.
Anzeige
Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.
The ACM CCS 2017 paper [6] introduced two signature scheme variants: Fish (which uses the Fiat-Shamir transform [10]), with claimed security against classical computer attacks, and Picnic (which uses Unruh’s transform [22]), with claimed security against quantum computer attacks. In the NIST submission [5], these variants were renamed to Picnic-FS and Picnic-UR, respectively. Our analysis applies to both variants, but we focus on Picnic-FS for simplicity.
Internally, Picnic uses a block cipher encryption \(f_i(x) = \mathrm {Enc}_{x}(p(i))\), where a different plaintext \(p = p(i)\) is used for each public key owner (defining a different encryption function).
In general, \(\kappa \) bits are sufficient to uniquely determine the key on average. However, even if several candidate keys are recovered, they can be filtered against the public key.
We assume here for that sake of simplicity that \(\tau \) is constant and does not depend on the analyzed run (although as we will see later, this does not necessarily hold).