und
(a,b) zwei Zufallszahlen aus 
(g
ist
ein Generator mod p, falls es für jedes y von 1 bis
eine
Zahl x gibt mit 
).
Die Diffie-Hellman-Annahme besagt nun, daß bei gegebenen 
und 
die
Berechnung von 
praktisch
undurchführbar ist.
3.12.1 ElGamal-Verschlüsselungsschema
Für das Alpha-System wird das ElGamal-Codierungsschema
(ElGamal, 1985) mit dem Schnorr-Signaturschema verwendet (Schnorr, 1991).
Die Sicherheit des ElGamal Verfahrens ist äquivalent zur Diffie-Hellman-Annahme,
die auf der Komplexität der Berechnung diskreter Logarithmen beruht
(Diffie/Hellman, 1976): Seien p eine Primzahl und g Generator
aus der Menge und
(a,b) zwei Zufallszahlen aus (g
ist
ein Generator mod p, falls es für jedes y von 1 biseine
Zahl x gibt mit ).
Die Diffie-Hellman-Annahme besagt nun, daß bei gegebenen und die
Berechnung von praktisch
undurchführbar ist.
Im weiteren operieren wir in einer Untergruppe 
(der
Ordnung 
von 
,
wobei p eine große Primzahl, 
und
einen
Generator der Ordnung q repräsentiert (Cramer/Gennaro/Schoenmakers,
1997). Diese Darstellungsform wird für das Schnorr-Verfahren benötigt.
Schlüsselerzeugungs-Algorithmus 
Der
Wert 
muß
als Sicherheitsparameter entsprechend gewählt werden.
sowie
einen öffentlichen Schlüssel 
.
und
korrespondierendem geheimen Schlüssel d aus 
Um
den nötigen Speicherplatz pro Schlüsselpaar zu reduzieren, können
alle Teilnehmer und Instanzen, die mit einer LA korrespondieren,
gemeinsam die eindeutigen Systemparameter (p,q,g) verwenden. Diese
Werte werden dann für die weitere Generierung neuer Schlüssel
als konstant vorausgesetzt.
Die Entschlüsselung ist korrekt, da 
und
somit folgt
.
Die Systemparameter sind dieselben wie im ElGamal-Schema. Das Schnorr-Signaturschema (Schnorr, 1991) verwendet zusätzlich eine kryptographisch sichere Hash-Funktion.
Schlüsselerzeugungs-Algorithmus
und
berechne
.
.
.
Wir realisieren das oben beschriebene Kollektivschlüssel-Erzeugungsprotokoll im Schnorr-ElGamal-System. Das Kollektivschlüssel-Erzeugungsprotokoll stellt den Spezialfall n=k des (n,k)-Schwellenwertschemas zur Schlüsselverteilung von Pedersen dar (Pedersen, 1991).
und
berechnet den korrespondierenden öffentlichen Schlüssel 
und
erbringt einen Nachweis, daß es sich tatsächlich um einen korrekten
öffentlichen Schlüssel handelt. Der Teilnehmer signiert deshalb
seinen öffentlichen Schlüssel, erhält 
und
überträgt insgesamt 
an
alle Teilnehmer.
für 
,der
im X.500 publiziert wird.
3.12.4 Kollektives Entschlüsselungsprotokoll
Wir realisieren das oben beschriebene Kollektivschlüssel-Erzeugungsprotokoll
im Schnorr-ElGamal-System. Das Protokoll zur Entschlüsselung wird
für ein codiertes Datum 
dargestellt.
Wenn der Wahlschein gemischt codiert wurde, dann ist 
(siehe
3.8.8). Ansonsten gilt 
.
eine
Teilentschlüsselung 
und
erbringt einen Nachweis, daß es sich tatsächlich um eine korrekte
Entschlüsselung handelt. Der Teilnehmer zeigt durch einen Beweis,
daß 
gilt,
ohne dabei seinen geheimen Schlüssel 
zu
enthüllen. Den Beweis realisiert z.B. eine nichtinteraktive modifizierte
Variante der Schnorr-Signaturprotokolls von Chaum und Pedersen (Chaum/Pedersen,
1993), das wir als Chaum-Schnorr-Pedersen-Signaturschema bezeichnen. Mit
diesem Protokoll kann die korrekte Potenzierung von 
überprüft
werden. Der Server berechnet die Signatur 
und
überträgt insgesamt 
an
alle Teilnehmer. Der Chaum-Schnorr-Pedersen-Algorithmus wird am Ende dieses
Abschnittes präsentiert. Falls ein Teilnehmer des Dechiffrierungskreises
diesen Beweis verweigert, dann gilt dieser als schuldig. Damit das Protokoll
erheblich beschleunigt wird, können und sollen sowohl die Teilentschlüsselungen
als auch die Beweisführung von jedem Protokollteilnehmer vor der Wahlzeit
parallel vorausberechnet und erst nach Ende der Wahlzeit publiziert werden.
Nach dem Ende der Wahl-zeit übertragen die Einheiten des Dechiffrierungskreises
gleichzeitig sämtliche Teildecodierungen an alle Teilnehmer (per Multicast).
= 
für Zur
Erreichung erhöhter Auswertungsgeschwindigkeit sollte VBeweis erst
nach dem Ende der Resultate durchgeführt werden.
berechnen.
,
sonst 
3.12.4.1 Chaum-Schnorr-Pedersen-Signaturschema
Die Systemparameter sind dieselben wie im ElGamal-Schema.
Schlüsselerzeugungs-Algorithmus
und
berechne die korrespondierenden öffentlichen Werte und 
.
..
.
.
Wir treffen hier keine besondere Auswahl des benützten symmetrischen Codierungsschemas. Mögliche Realisierungsarten sind u.a. DES, IDEA und BLOWFISH (siehe Schneier, 1996).
3.12.6 Hash-Funktion und Commitment
Als sichere Hash-Funktion verwenden wir den Secure Hash
Algorithm (SHA). SHA produziert für jede Eingabe
Bit
eine Ausgabe der Länge 160 Bit, die als Message-Digest bezeichnet
wird. "SHA wird als sicher bezeichnet, da er so entworfen wurde, daß
es vom Berechnungsaufwand her nicht durchführbar ist, eine Nachricht
zu einem vorgegebenen Message Digest zu bestimmen oder zwei Nachrichten
zu finden, die den gleichen Message Digest ergeben" (Schneier, 1996,
S. 504). Zur Zeit existieren keine bekannten Angriffe gegen SHA. Zudem
bietet SHA einen akzeptablen Schutz vor Brute-Force-Angriffe (einschließlich
dem Geburtstagsangriff).
Die Commitment-Funktion (BC) kann durch unterschiedliche
Verfahren (u.a. mit symmetrischer Kryptographie oder mit sicheren Hash-Funktionen
realisiert werden) (Realisierung siehe: Schneier, 1996, S. 104-107).
