Norbert Göb

• In this thesis we propose an efficient method to compute the automorphism group of an arbitrary hyperelliptic function field over a given constant field of odd characteristic as well as over its algebraic extensions. Beside theoretical applications, knowing the automorphism group also is useful in cryptography: The Jacobians of hyperelliptic curves have been suggested by Koblitz as groups for cryptographic purposes, because the discrete logarithm is believed to be hard in this kind of groups. In order to obtain "secure" Jacobians, it is necessary to prevent attacks like Pohlig/Hellman's and Duursma/Gaudry/Morain's. The latter is only feasible, if the corresponding function field has an automorphism of large order. According to a theorem by Madan, automorphisms seem to allow the Pohlig/Hellman attack, too. Hence, the function field of a secure Jacobian will most likely have trivial automorphism group. In other words: Computing the automorphism group of a hyperelliptic function field promises to be a quick test for insecure Jacobians. Let us outline our algorithm for computing the automorphism group Aut(F/k) of a hyperelliptic function field F/k. It is well known that Aut(F/k) is finite. For each possible subgroup U of Aut(F/k), Rolf Brandt has given a normal form for F if k is algebraically closed. Hence our problem reduces to deciding, whether a given hyperelliptic function field F=k(x,y), y^2=D_x has a defining equation of the form given by Brandt. This question can be answered using theorem III.18: We have F=k(t,u), u^2=D_t iff x is a fraction of linear polynomials in t and y=pu, where the factor p is a rational function w.r.t. t which can be determined explicitly from the coefficients of x. This condition can be checked efficiently using Gröbner basis techniques. With additional effort, it is also possible to compute Aut(F/k) if k is not algebraically closed. Investigating a huge number of examples one gets the impression that the above motivation of getting a quick test for insecure Jacobians is partially fulfilled: The computation of automorphism groups is quite fast using the suggested algorithm. Furthermore, fields with nontrivial automorphism groups seem to have insecure Jacobians. Only fields of small characteristic seem to have a reasonable chance of having nontrivial automorphisms. Hence, from a cryptographic point of view, computing Aut(F/k) seems to make sense whenever k has small characteristic.
• In dieser Arbeit wird ein effektiver Algorithmus vorgestellt, der die Automorphismengruppe eines beliebigen hyperelliptischen Funktionenkörpers über einem Konstantenkörper ungerader Charakteristik sowie über dessen algebraischen Abschluß berechnet. Neben theoretischen Anwendungen, ist die Kenntnis der Automorphismengruppe auch für die Kryptographie interessant: Die Jacobigruppen hyperelliptischer Kurven wurden von Koblitz zur Verwendung in Kryptosystemen vorgeschlagen, da das diskrete Logarithmenproblem für Jacobigruppen als schwer gilt. Um "sichere" Jacobigruppen zu erhalten, müssen Attacken wie die von Pohlig/Hellman oder Duursma/Gaudry/Morain verhindert werden. Die letztgenannte ist nur anwendbar, wenn der zugehörige Funktionenkörper einen Automorphismus großer Ordnung besitzt. Nach einem Satz von Madan ist bei Existenz von Automorphismen auch die Pohlig/Hellman Attacke zu befürchten. Somit besitzt der Funktionenkörper einer sicheren Jacobigruppe höchst wahrscheinlich triviale Automorphismengruppe. Anders ausgedrückt, verspricht die Berechnung von Aut(F/k) einen Schnelltest auf unsichere Jacobigruppen. Unser Verfahren zur Berechnung von Aut(F/k) basiert auf folgenden Ideen: Es ist allgemein bekannt, dass Aut(F/k) endlich ist. Für jede mögliche Untergruppe von Aut(F/k) hat Rolf Brandt eine Normalform für F angegeben. Hierbei muss k algebraisch abgeschlossen sein. Somit reduziert sich unser Problem darauf, zu entscheiden, ob ein gegebener hyperelliptischer Funktionenkörper F=k(x,y), y^2=D_x eine definierende Gleichung besitzt, die einer von Brandts Normalformen entspricht. Diese Frage beantwortet Theorem III.18: Es ist genau dann F=k(t,u), u^2=D_t, wenn x ein Bruch von linearen Polynomen in t und y=pu ist, wobei p eine rationale Funktion in t ist, die explizit durch die Koeffizienten von x bestimmt ist. Diese Bedingung kann mit Hilfe von Gröbnerbasen effizient überprüft werden. Mit zusätzlichem Aufwand ist es zudem möglich, Aut(F/k) zu berechnen, falls k nicht algebraisch abgeschlossen ist. Die Betrachtung einer großen Zahl an Beispielen erweckt den Eindruck, dass unsere obige Motivation - einen Schnelltest auf unsichere Jacobigruppen zu erhalten - teilweise erfüllt wurde: Mit dem vorgestellten Algorithmus ist die Berechnung von Automorphismengruppen schnell möglich. Weiterhin scheinen Körper mit nicht trivialen Automorphismengruppen stets unsichere Jacobigruppen zu besitzen. Nicht triviale Automorphismengruppen scheinen im Wesentlichen nur bei Körpern kleiner Charakteristik aufzutreten. Daher ist die Berechnung von Aut(F/k) aus kryptographischer Sicht bei Funktionenkörpern kleiner Charakteristik sinnvoll.