Seite 1 von 1

Security of Schnorr Signature

Verfasst: 14. Feb 2010 11:10
von jm1035
Hi,

ich versuche gerade verzweifelt den Beweis von Theorem 9.2 ("Schnorr signature scheme is EUF-CMA secure under the DL assumption in the random oracle model") nachzuvollziehen. (Seite 16, Foliensatz 9)

Insbesondere verstehe ich folgende Punkte nicht:
  • Es heißt B befragt so lange A, bis zwei Fälschungen (m, (c, s)) und (m, (c', s')) auftreten.
    Das heißt, es wird erwartet, dass A früher oder später irgendwann einmal die gleiche Nachricht mit verschiedenen Signaturen versieht. Ist die Wahrscheinlichkeit, dass dieser Fall jemals eintritt nicht vernachlässigbar aufgrund der beliebigen Länge der zu signierenden Nachrichten?
    Bzw. anders ausgedrückt: Selbst wenn A erfolgreich signierte Nachrichten fälschen kann, folgt daraus doch nicht, dass ein solches Paar jemals ausgegeben wird. Das heißt ja nur, dass A irgendeine signierte Nachricht generieren kann.
    Oder nochmal anders ausgedrückt: Wie ist sichergestellt, dass solch ein Paar in akzeptabler Zeit (oder überhaupt jemals) auftreten wird?
  • Angenommen ein solcher Fall tritt tatsächlich ein, dann verstehe ich nicht, woraus die Behauptung folgt, dass \(y^{-c}g^{s} = y^{-c'}g^{s'}\) gilt.
  • Wenn die obige Behauptung gilt, folgt daraus doch, dass r = r' und damit dann, dass c = H(r|m) = H(r'|m) = c'. Was bedeuten würde, dass c' - c = 0 und damit nicht invertierbar wäre...
Es wäre echt klasse, wenn das jemand verstanden hat und mir so erklären kann, dass auch ich das verstehe oder mir jemand eine Quelle nennen könnte, die mir weiterhilft.

vielen Dank schonmal.

Re: Security of Schnorr Signature

Verfasst: 14. Feb 2010 14:00
von poetter
* Es heißt B befragt so lange A, bis zwei Fälschungen (m, (c, s)) und (m, (c', s')) auftreten.
Das heißt, es wird erwartet, dass A früher oder später irgendwann einmal die gleiche Nachricht mit verschiedenen Signaturen versieht. Ist die Wahrscheinlichkeit, dass dieser Fall jemals eintritt nicht vernachlässigbar aufgrund der beliebigen Länge der zu signierenden Nachrichten?
Bzw. anders ausgedrückt: Selbst wenn A erfolgreich signierte Nachrichten fälschen kann, folgt daraus doch nicht, dass ein solches Paar jemals ausgegeben wird. Das heißt ja nur, dass A irgendeine signierte Nachricht generieren kann.
Oder nochmal anders ausgedrückt: Wie ist sichergestellt, dass solch ein Paar in akzeptabler Zeit (oder überhaupt jemals) auftreten wird?
* Angenommen ein solcher Fall tritt tatsächlich ein, dann verstehe ich nicht, woraus die Behauptung folgt, dass y−cgs=y−cgs gilt.
* Wenn die obige Behauptung gilt, folgt daraus doch, dass r = r' und damit dann, dass c = H(r|m) = H(r'|m) = c'. Was bedeuten würde, dass c' - c = 0 und damit nicht invertierbar wäre...
Deine einwände sind zwar korrekt, beruhen aber auf einem missverständnis. Der beweis im skript ist
eher als skizze zu verstehen, da die theorie und die mechanismen dahinter etwas komplizierter sind.
Ich skizziere den beweis unten etwas ausführlicher. Zunächst aber ist festzuhalten, dass adversary A nach polynomieller
laufzeit EINE fälschung m,(c,s) ausgibt. Danach hält A an. Er gibt insbesondere keine weiteren fälschungen aus (vgl. S.5).

Der beweis benutzt die sog. "rewinding technique". Dabei wird ausgenutzt, dass A eine turingmaschine ist,
deren gesamter innerer zustand sich zu jedem zeitpunkt im inhalt der bänder und im zustand in der endlichen kontrolle
vollständig wiederspiegelt. Nichtdeterministische TMs werden simuliert mithilfe von zufallsbändern, die apriori feststehen.

B startet also A und beantwortet Sign() und H() queries. Irgendwann gibt A eine
fälschung "m,(c,s)" aus und hält an. Würde B jetzt A resetten und nochmal starten, und die Sign() und H() queries genauso beantworten
wie beim ersten mal, würde auch dieselbe fälschung "m,(c,s)" ausgegeben. Nun macht B aber einen trick und beantwortet beim zweiten
mal die H() query, die A für die "gefälschte nachricht" m stellt, anders (und gibt c' statt c zurück). Da alle vorherigen queries
konsistent mit dem 1. durchlauf beantwortet werden, ist klar, dass A die H() query auf m tatsächlich irgendwann fragt.
Wenn A auch beim zweiten mal eine fälschung für m ausgibt, dann mit c' statt mit c, also "m,(c',s')". Aus (c,s) und (c',s') kann B dann
x extrahieren. Wenn A aber beim zweiten durchlauf keine fälschung mehr für m präsentiert, sondern für eine andere nachricht m',
dann startet B einen dritten durchlauf, der bis zur H-anfrage von m' konsistent mit dem 2. ist, usw.
Es ist klar, dass B es auf dieses weise immer schafft, aus A eine nachricht mit zwei verschiedenen signaturen zu extrahieren. Also
kann auch stets der private key extrahiert werden.
Es wäre echt klasse, wenn [...] mir jemand eine Quelle nennen könnte, die mir weiterhilft.
Die klassische referenz auf das thema ist: Pointcheval and Stern: "Security Proofs for Signature Schemes"
http://www.springerlink.com/content/k0x ... 56f1&pi=32

Lies evtl auch mal http://en.wikipedia.org/wiki/Forking_lemma

Re: Security of Schnorr Signature

Verfasst: 14. Feb 2010 22:33
von jm1035
Wenn ich behaupten würde, ich hätte den Beweis jetzt vollständig verstanden, müsste ich lügen, aber ich bin der Erkenntnis damit schon ein ganzes Stück näher gekommen.

Vielen Dank für diese ausführliche Erklärung. :)