15. ÖMG-Kongress
Jahrestagung der Deutschen Mathematikervereinigung

16. bis 22. September 2001 in Wien

Sektion 3 - Diskrete Mathematik, Algorithmen
Montag, 17. September 2001, 17.00, Hörsaal 23

 

Zur Komplexität der Diffie-Hellman Abbildung und des diskreten Logarithmus

Arne Winterhof, Österreichische Akademie der Wissenschaften

 

Sei $q$ eine Primzahlpotenz, $F_q$ der endliche Körper der Ordnung $q$ und $\gamma$ ein primitives Element von $F_q$. Das Diffie-Hellman Problem in $F_q$ ist folgendermaßen definiert: Finde zu zwei Elementen $\gamma^x, \gamma^y$ aus $F_q$ das Element $\gamma^{xy}$ ohne $x$ und $y$ zu kennen. Die Diffie-Hellman Abbildung wird durch

$$F(\gamma^x,\gamma^y)=\gamma^{xy}$$   für$$\ 0\le x,y \le q-2$$

definiert. Um das Diffie-Hellman Kryptosystem zu brechen, würde es reichen ein einfaches Polynom $F\in F_q[U,V]$ mit $F(\gamma^x,\gamma^y)=\gamma^{xy}$ für alle Paare $(x,y)$ einer großen Teilmenge von $[0,\ldots,q-2]^2$ zu haben. Für zahlreiche Teilmengen zeigen wir, dass solch ein Polynom großen Grad haben muss.

Der diskrete Logarithmus (oder Index) eines Elementes $0\neq \xi \in F_q$ zur Basis $\gamma$, bezeichnet mit ${\rm ind}_\gamma(\xi)$, ist die eindeutige ganze Zahl $l$ mit $0 \le l \le q-2$, so dass $\xi = \gamma^l$. Offensichtlich hängt die Unangreifbarkeit der Diffie-Hellman Abbildung von der Unangreifbarkeit des diskreten Logarithmus ab. Wir untersuchen Darstellungen des diskreten Logarithmus durch lineare Rekursionsfolgen und leiten untere Schranken für die lineare Komplexität dieser Folgen her.

E-Mail:	arne.winterhof@oeaw.ac.at
Homepage:	www.dismat.oeaw.ac.at/Winterhof.shtml

Zeitplan der Sektion   Tagesübersicht   Liste der Vortragenden