Open Access

Okamoto (Crypto 1992) hat die RSA-Repräsentation als Basis eines gegen aktive Angreifer sicheren Identifikationsschemas eingeführt. Eine RSA- Repräsentation von X E Z * N ist ein Paar (x; r) E Z e x Z * N mit X = g x r e (mod N) für vorgegebenes g E ZN , RSA-Modul N und primen RSA- Exponenten e. Das zugehörige Repräsentationsproblem, also das Auffinden eines Wertes X samt zweier verschiedener Darstellungen, ist äquivalent zum RSA-Problem, der Berechnung einer e-ten Wurzel von g modulo N . Von Brassard, Chaum und Crépeau (Journal Computing System Science, 1988) sowie Damgard (Journal of Cryptology, 1995) stammt eine analoge Konstruktion der Form X = g x r 2 t (mod N) mit x E Z 2 t für den Spezialfall der Blum-Zahlen als Modul N und gegebenes t größer gleich 1, wo die Möglichkeit, zwei verschiedene Repräsentationen zu berechnen, gleichbedeutend zur Zerlegung des Moduls in die Primfaktoren ist. Im ersten Abschnitt der vorliegenden Arbeit verallgemeinern wir dieses Konzept systematisch auf beliebige (RSA-)Module durch die Einführung eines Anpassungsparameters r:= r (N ), so dass X = g x r 2 r t (mod N) mit x E Z 2 t. Basierend auf dieser als Faktorisierungsrepräsentation bezeichneten Darstellung leiten wir Identifikations-, Signatur- und Blinde-Unterschriften-Verfahren her. Im zweiten Teil verwenden wir sowohl RSA- als auch Faktorisierungsrepräsentation als Grundlage sogenannter non-malleable Commitment-Schemata zur Hinterlegung (Verbriefung) einer geheimen Nachricht. Bei dem von Dolev, Dwork und Naor (SIAM Journal on Computing, 2000) eingeführten Begriff der Non-Malleability soll ein Angreifer außer Stande sein, die Hinterlegung einer Nachricht m so abzuändern, dass er diese später dann mit einem in Relation zu m stehenden Wert, man denke zum Beispiel an m 1, aufdecken kann. Von Dolev, Dwork und Naor stammt ein allgemeiner Ansatz zur Konstruktion von non-malleable Commitment-Schemata aufbauend auf einem sogenannten Knowledge-Extraktor. Für die RSA-Darstellung verfügt das von Okamoto entworfene Protokoll als Proof-Of-Knowledge über einen solchen Extraktor, bei dem im Fall der Faktorisierungsrepräsentation von uns entwickelten Verfahren fehlt allerdings der Extraktor. Aus diesem Grund stellen wir mit Hilfe des Chinesischen Restsatzes ein neues, auf Commitments zugeschnittenes Protokoll mit Knowledge-Extraktor vor, das in Verbindung mit der Faktorisierungsrepräsentation ein effizientes Hinterlegungsschema ergibt. Zum Abschluß wird bei einem Commitment- Verfahren mit abgeschwächter Non-Malleability-Eigenschaft von Di Crescenzo, Katz, Ostrovsky und Smith (Eurocrypt 2001) die RSA- durch die Faktorisierungsrepräsentation ersetzt und das Schema vereinfacht.

Informally, commitment schemes can be described by lockable steely boxes. In the commitment phase, the sender puts a message into the box, locks the box and hands it over to the receiver. On one hand, the receiver does not learn anything about the message. On the other hand, the sender cannot change the message in the box anymore. In the decommitment phase the sender gives the receiver the key, and the receiver then opens the box and retrieves the message. One application of such schemes are digital auctions where each participant places his secret bid into a box and submits it to the auctioneer. In this thesis we investigate trapdoor commitment schemes. Following the abstract viewpoint of lockable boxes, a trapdoor commitment is a box with a tiny secret door. If someone knows the secret door, then this person is still able to change the committed message in the box, even after the commitment phase. Such trapdoors turn out to be very useful for the design of secure cryptographic protocols involving commitment schemes. In the first part of the thesis, we formally introduce trapdoor commitments and extend the notion to identity-based trapdoors, where trapdoors can only be used in connection with certain identities. We then recall the most popular constructions of ordinary trapdoor protocols and present new solutions for identity-based trapdoors. In the second part of the thesis, we show the usefulness of trapdoors in commitment schemes. Deploying trapdoors we construct efficient non-malleable commitment schemes which basically guarantee indepency of commitments. Furthermore, applying (identity-based) trapdoor commitments we secure well-known identification protocols against a new kind of attack. And finally, by means of trapdoors, we show how to construct composable commitment schemes that can be securely executed as subprotocols within complex protocols.

Wir behandeln Kettenbruchentwicklungen in beliebiger Dimension. Wir geben einen Kettenbruchalgorithmus an, der für beliebige Dimension n simultane diophantische Approximationen berechnet, die bis auf den Faktor 2 exp (n+2)/4 optimal sind. Für einen reellen Eingabevektor x := (x1,...,X n-1, 1) berechnet der Algorithmus eine Folge ganzzahliger Vektoren ....., so daß für i =1, ...., n-1 : | q exp (k) xi -pi exp (k)| <= 2 exp (n+2)/4 sqrt (1 + xi exp 2) / q exp (1/n-1). Nach Sätzen von Dirichlet und Borel ist die Schranke optimal in dem Sinne, als daß der Exponent 1/(n-1) im allgemeinen nicht erhöht werden kann. Der Algorithmus konstruiert eine Folge von Gitterbasen des Zn, welche die Gerade x R approximieren. Für gegebenes E > 0 findet der Algorithmus entweder eine Relation zu x, das heißt einen ganzzahligen zu x orthogonalen Vektor (ungleich Null), mit euklidischer Länge kleiner oder gleich E exp -1, oder er schließt Relationen zu x mit euklidischer Länge kleiner als E exp -1 aus. Der Algorithmus führt in der Dimension n und |log E| polynomial viele arithmetische Operationen auf rellen Zahlen in exakter Arithmetik aus. Für rationale Eingaben x := (p1, ....., pn)/pn, E>0 mit p1,.....,pn Teil von Z besitzt der Algorithmus polynomiale Bitkomplexität in O........ Eine Variante dieses Algorithmus konstruiert für Eingabevektoren x einen (von x nicht notwendigerweise verschiedenen) Nahebeipunkt x' zu x und eine kurze Relation zu x'. Im Falle x<>x können wir die Existenz von Relationen kleiner als (2E)exp -1 für Punkte in einer kleinen offenen Umgebung um x' ausschließen. Wir erhalten in diesem Sinne eine stetige untere Schranke für die Länge der kürzesten Relation zu Punkten in dieser Umgebung. Die für x' berechnete Relation ist bis auf einen in der Dimension n exponentiellen Faktor kürzeste Relation für x'. Zur Implementierung des Kettenbruchalgorithmus stellen wir ein numerisch stabiles Verfahren vor und berichten über experimentelle Ergebnisse. Wir geben untere Schranken für die Approximierbarkeit kürzester Relationen in der Maximum-Norm und minimaler diophantischer Approximationen an: Unter der Annahme, daß die Klasse NP nicht in der deterministischen Zeitklasse O(n exp poly log n) enthalten ist, zeigen wir: Es existiert kein Algorithmus, der für rationale Eingabevektoren x polynomial in der Bitlänge bin(x) von x ist und die in der Maximum-Norm kürzeste Relation bis auf einen Faktor 2 exp (log 0.5 - zeta bin(x)) approximiert. Dabei ist zeta eine beliebig kleine positive Konstante. Wir übertragen dieses Resultat auf das Problem, zu gegebenen rationalen Zahlen x1,....,xn-1 und einem rationalen E > 0 gute simultane diophantische Approximationen zu finden, das heißt rationale Zahlen p1/q,...; (p n-1/)q mit möglichst kleinem Hauptnenner q zu konstruieren, so daß max 1 <=i <= n-1 |q xi - pi| <= E. Wir zeigen unter obiger Annahme, daß kein Algorithmus existiert, der für gegebene rationale Zahlen x1,........,x n-1 und natürlicher Zahl N polynomial-Zeit in der Bitlänge bin(x) von x ist und simultane diophantische Approximationen berechnet, so daß max 1 <=i <= n-1 |q xi - pi| für q gehört zu [1, N] bis auf den Faktor 2 exp (log 0.5 - zeta bin(x)) minimal ist. Hierbei ist zeta wieder eine beliebig kleine positive Konstante.

Ein Gitter vom Rang n ist die Menge der ganzzahligen Linerkombinationen von n linear unabhängigen Vektoren im Rm. Unter der Annahme P <> NP beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der eine kürzeste Gitterbasis bis auf einen Faktor nO exp(1/log log n) berechnet, wobei die Länge einer Menge von Vektoren durch die maximale Euklidische Länge der Vektoren definiert ist. Weiter zeigen wir, daß eine Verbesserung dieses Resultates bis hin zu einem Faktor n/ sqrt(log n) unter plausiblen Annahmen nicht möglich ist. Ein simultaner Diophantischer Best Approximations Nenner für reelle Zahlen alpha1, .... , alpha n und Hauptnennerschranke N ist eine natürliche Zahl q mit 1 <= q >= N, so daß maxi minp2Z |q alpha i - p| minimal ist. Unter der Annahme, daß die Klasse NP keine fast-polynomiellen Algorithmen besitzt, beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der für gegebene rationale Zahlen. Ein Gitter vom Rang n ist die Menge der ganzzahligen Linerkombinationen von n linear unabhängigen Vektoren im Rm. Unter der Annahme P 6= NP beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der eine kürzeste Gitterbasis bis auf einen Faktor nO(1= log log n) berechnet, wobei die Länge einer Menge von Vektoren durch die maximale Euklidische Länge der Vektoren definiert ist. Weiter zeigen wir, daß eine Verbesserung dieses Resultates bis hin zu einem Faktor n=plog n unter plausiblen Annahmen nicht möglich ist. Ein simultaner Diophantischer Best Approximations Nenner für reelle Zahlen alpha1, .... , alpha n und Hauptnennerschranke N ist eine natürliche Zahl q mit 1 <= q <= N, so daß maxi ...... minimal ist. Unter der Annahme, daß die Klasse NP keine fast-polynomiellen Algorithmen besitzt, beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der für gegebene rationale Zahlen alpha1,......, alphan und eine Hauptnennerschranke N einen Nenner ~q mit 1 <= ~q <= f(n)N berechnet, so daß ~q bis auf einen Faktor f(n) = nO(1= log0:5+epsilon n) ein Best Approximations Nenner ist, wobei epsilon > 0 eine beliebige Konstante ist. Wir zeigen, daß eine Verbesserung dieses Resultates bis hin zu einem Faktor n=log n unter plausiblen Annahmen nicht mölich ist. Wir untersuchen die Konsequenzen dieser Resultate zur Konstruktion von im Durchschnitt schwierigen Gitterproblemen.