[Alg. Kryptographie]QR-Bit-Commitment

[rumpels]

Hi zusammen,

für die, die schon ein bisschen in der Materie drinnen stecken. Ich habe eine Sache, die ich nicht verstehe.

Das commitement lautet c = r^2 * v^b für ein bit b, eine Zufallszahl r und ein v aus QR_n (mit Jakobi-Symbol 1) für ein n (Produkt aus zwei Primzahlen)

Warum muss v ein pos. Jakobi-Symbol haben, das bit wäre doch auch nicht veränderbar, wenn v einfach nur ein quadr. Rest mod n ist.

Vielleicht hat ja schon wer dafür gelernt, der mir das erklären kann...

Danke euch schonmal

Beste Grüße

[fw]

Vielleicht guckst du dir nochmal die Definition des Jacobi Symbols an, dann erübrigt sich die Frage.

[rumpels]

Versteh nicht ganz, worauf du hinauswillst. Da n=pq, weiss ich, dass Jacobi-Symbol Produkt aus den beiden Legendre-Symbolen ist, also (v/pq)=(v/p)*(v/q). Damit Jabobi nun 1 ist, sind Legendres entweder beide 1 oder beide -1. Demnach ist v also entweder QR von p und q oder QNR von p und q... weiter funktioniert meine Herleitung nicht.
Oben hatte ich das alsch geschrieben, natürlich muss v ein quadratischer Nichtrest (QNR) aus der Einheitengruppe Z_n^* sein, woher die Anforderung an das pos. Jacobi-Symbol jetzt kommt, versteh ich weiterhin nicht ganz.
Stehe irgendwie auf dem Schlauch

[fw]

Erstmal: Ich höre die Vorlesung nicht, aber ich kenne das von Prof. Mathars Vorlesung und hoffe, dass wir nicht von unterschiedlichen Dingen reden

Die Idee ist doch, dass c genau dann ein quadratischer Rest (mod n) ist, wenn b=0 war. Die Tatsache dass man quadratische Nichtreste (mod n, mit Jakobi Symbol 1) von quadratischen Resten algorithmisch nicht gut unterscheiden kann führt dann zur Sicherheit des Protokolls. Hätte v nun Jacobi Symbol -1 (was man effizient berechnen kann, auch wenn das auf den ersten Blick nicht so aussieht!) dann wüsstest du, dass v kein Rest bzgl. einer der beiden Primzahlen sein kann (und damit auch keiner mod n, denn jeder quadratische Rest mod p*q ist auch zwangsweise quadratischer Rest mod p und mod q).

Nochmal anders erklärt:
Wie du schon sagtest ist das Jacobi Symbol genau dann 1 wenn das Legendre Symbol bzgl. beiden Primzahlen 1 ist oder bzgl. beiden -1 ist. D.h. wenn das Jacobi Symbol -1 ist, muss schon eines der beiden Legendre Symbole -1 gewesen sein. a heißt quadratischer Rest wenn ein b existiert mit b²=a (mod n), d.h. n teilt b²-a. Da p,q beide n teilen folgt dass p,q (da prim) auch beide b²-a teilen, also ist auch b²=a (mod p) und b²=a (mod q), d.h. a ist auch quadratischer Rest mod p und mod q. Im Umkehrschluss: Wenn es mod p oder mod q keiner ist (was man am negativen Jacobi Symbol erkennt), kann es auch keiner mod n sein. In dem Fall könnte man also einfach das Jacobi Symbol von c = r² * v^b ausrechnen. Das Jacobi Symbool von r² ist aufjedenfall 1. Insgesamt also: Falls -1 rauskommt war b=1, sonst b=0. Kaputt

[rumpels]

Danke Dir,

hast dir wirklich viel Zeit genommen für die Antwort. Habs glaube ich jetzt verstanden:

Wenn v Jacobi -1 (zb. für v QR_p und v QNR_q => v QNR_n) hätte, hätte für den Fall, dass Empfänger Jacobi von c als -1 ausrechnet (easy berechenbar), dieser die Gewissheit, dass b=1 wäre, da sonst in jedem Fall für b=0 Jacobi +1 wäre. Das Problem umschifft man mit der Restriktion v QNR & Jacobi+1 ...

so hab ich das nun verstanden. Bitte bitte sag das stimmt so ...

[fw]

Genau richtig