Sind Schnorr-Signaturen quantencomputerresistent?

Hier ( https://bitcoincore.org/en/2017/03/23/schnorr-signature-aggregation/ ) heißt es, Schnorr ersetzt ECDSA, wir wissen, dass ECDSA durch Quantencomputer gebrochen werden kann. Ist Schnorr sicher vor Q-Computern?

Antworten (2)

Nein, ECDSA und EC-Schnorr sowie verwandte Schemata wie EdDSA gehören alle zur Klasse der Kryptografie mit elliptischen Kurven. Ihre Sicherheit basiert auf der Annahme, dass der diskrete EC-Logarithmus unmöglich schwer zu berechnen ist. Diese Annahme ist nicht wahr, wenn ein ausreichend starker Allzweck-Quantencomputer existieren würde.

Es gibt quantenresistente Signaturalgorithmen, aber sie sind alle auf sehr große Signaturen angewiesen – was sie für Zwecke wie Bitcoin undurchführbar teuer machen kann. Darüber hinaus gibt es viel weniger Forschung zu Funktionen (wie homomorphe Ableitung wie BIP32-Verwendungen oder Aggregation), was sie in Bezug auf die Funktionalität effektiv zu einem Rückschritt macht, wenn wir dies stattdessen übernehmen würden.

Allerdings mache ich mir darüber keine großen Sorgen. Quantencomputer im Allgemeinen haben noch einen sehr langen Weg vor sich, bevor sie auch nur annähernd Probleme wie das Lösen diskreter Logarithmen für Kurven unserer Größe angehen können. Eine Allzweck-QC mit mehreren 1000 Qbits wäre erforderlich, und es ist nicht einmal bekannt, ob es physikalisch möglich ist, einen solchen Computer zu bauen.

Dies ist im Grunde eine ungültige Frage. Es spielt keine Rolle, wie Sie Daten signieren. Solange Sie elliptische Kurven und (EC) DLP (Elliptic Curve Discrete Logarithm Problem) verwenden, sollte ein Quantencomputer (per Definition mit Shors Algorithmus) in der Lage sein, es zu brechen. Dies liegt daran, dass die Signaturprüfung einen öffentlich verfügbaren öffentlichen Schlüssel erfordert. Wenn Sie einen Quantencomputer und einen öffentlichen Schlüssel haben, erhalten Sie den privaten Schlüssel.

Die Frage, ob Quantencomputer digitale Signaturen knacken können, ist wie die Frage, ob ein verstärkter Safe von jedermann geöffnet werden kann, während der Schlüssel zu diesem Safe öffentliche Informationen sind. Es spielt keine Rolle, wie Sie den Safe verstärken, ob es eine Möglichkeit gibt, einen Schlüssel herzustellen, der diesen Safe für jedermann öffnet.

Es gibt (vermutete) postquantensichere digitale Signaturalgorithmen, die private und öffentliche Schlüssel beinhalten. Diese Schlüssel basieren jedoch nicht auf Varianten des Problems des diskreten Logarithmus.
@PieterWuille Wenn ich Ihren Standpunkt richtig verstehe, sagen Sie, dass es Post-Quanten-Signaturen gibt, die asymmetrische Schlüssel beinhalten und sicher sind. Ja, natürlich, da gibt es keine Meinungsverschiedenheiten. Meine Kritik an der Frage basierte darauf, dass behauptet wurde, die Signatur sei "anfällig", anstatt sich auf den Schlüsselgenerierungsalgorithmus zu konzentrieren, der anfällig sein kann oder nicht, und welche Komponenten normalerweise die Sicherheit tragen, seit der Überschrift von Die Beteiligung von Quantencomputern an der Kryptowährung bricht ECDLP.
Das ist fair - obwohl es theoretisch nicht unmöglich ist, dass der Schlüsselgenerierungsalgorithmus quatumsicher ist, der Signaturalgorithmus jedoch nicht. Das ist natürlich eine Strecke, im Allgemeinen basieren sie auf demselben Rechenhärteproblem. Aber es ist nicht unmöglich, ein (möglicherweise erfundenes) Signaturschema zu konstruieren, für das dies der Fall ist.
Sie könnten beispielsweise ein Schema erstellen, bei dem ein geheimer Schlüssel nur aus zufälligen Bytes besteht und der öffentliche Schlüssel ein (traditioneller, z. B. SHA256) Hash des privaten Schlüssels ist. Aber dann ist die Signatur ein DL- oder Pairing-basierter Zero-Knowledge-Beweis dafür, dass dieser Hash korrekt berechnet wurde, was zusätzlich die Nachricht bestätigt. Dadurch kann ein Quantenangreifer den privaten Schlüssel nicht unbedingt finden, aber er könnte Signaturen fälschen.
@PieterWuille Macht Sinn. Stimme dir da voll und ganz zu. Das ist ein Fall, den ich in meiner Antwort nicht behandelt habe. Prost!
Sind Schnorr-Signaturen quantencomputerresistent?
AntwortenHierDatenschutz-Bestimmungen1y, 0v