11 search hits
-
Komplexität von Gitterproblemen : Nicht-Approximierbarkeit und Grenzen der Nicht-Approximierbarkeit
(2000)
-
Jean-Pierre Seifert
- 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.
-
Efficient non-malleable commitment schemes
(2000)
-
Marc Fischlin
Roger Fischlin
- We present efficient non-malleable commitment schemes based on standard assumptions such as RSA and Discrete-Log, and under the condition that the network provides publicly available RSA or Discrete-Log parameters generated by a trusted party. Our protocols require only three rounds and a few modular exponentiations. We also discuss the difference between the notion of non-malleable commitment schemes used by Dolev, Dwork and Naor [DDN00] and the one given by Di Crescenzo, Ishai and Ostrovsky [DIO98].
-
Tensor-based trapdoors for CVP and their application to public key cryptography
(2000)
-
Roger Fischlin
Jean-Pierre Seifert
- We propose two trapdoors for the Closest-Vector-Problem in lattices (CVP) related to the lattice tensor product. Using these trapdoors we set up a lattice-based cryptosystem which resembles to the McEliece scheme.
-
Security Of Signed ELGamal Encryption
(2000)
-
Claus Peter Schnorr
Markus Jakobsson
- Assuming a cryptographically strong cyclic group G of prime order q and a random hash function H, we show that ElGamal encryption with an added Schnorr signature is secure against the adaptive chosen ciphertext attack, in which an attacker can freely use a decryption oracle except for the target ciphertext. We also prove security against the novel one-more-decyption attack. Our security proofs are in a new model, corresponding to a combination of two previously introduced models, the Random Oracle model and the Generic model. The security extends to the distributed threshold version of the scheme. Moreover, we propose a very practical scheme for private information retrieval that is based on blind decryption of ElGamal ciphertexts.
-
Security Of Discrete Log Cryptosystems in the Random Oracle and the Generic Model
(2000)
-
Claus Peter Schnorr
Markus Jakobsson
- We introduce novel security proofs that use combinatorial counting arguments rather than reductions to the discrete logarithm or to the Diffie-Hellman problem. Our security results are sharp and clean with no polynomial reduction times involved. We consider a combination of the random oracle model and the generic model. This corresponds to assuming an ideal hash function H given by an oracle and an ideal group of prime order q, where the binary encoding of the group elements is useless for cryptographic attacks In this model, we first show that Schnorr signatures are secure against the one-more signature forgery : A generic adversary performing t generic steps including l sequential interactions with the signer cannot produce l+1 signatures with a better probability than (t 2)/q. We also characterize the different power of sequential and of parallel attacks. Secondly, we prove signed ElGamal encryption is secure against the adaptive chosen ciphertext attack, in which an attacker can arbitrarily use a decryption oracle except for the challenge ciphertext. Moreover, signed ElGamal encryption is secure against the one-more decryption attack: A generic adversary performing t generic steps including l interactions with the decryption oracle cannot distinguish the plaintexts of l + 1 ciphertexts from random strings with a probability exceeding (t 2)/q.
-
Effiziente Signaturerzeugung durch Server-Unterstützung und Vorberechnung
(2000)
-
Johannes Merkle
- Es steht außer Zweifel, daß digitale Signaturen schon bald zu unserem Alltag gehören wer- den. Spätestens mit dem Inkrafttreten des Gesetzes zur digitalen Signatur (siehe [BMB]) sind sie zu einem wichtigen Instrument in der Telekommunikation geworden. Dabei kommt der Verwendung von Chipkarten eine wichtige Bedeutung zu: In ihnen lassen sich die sensiblen Daten (z.B. der geheime Schlüssel) auslesesicher aufbewahren; gleichzeitig können sie bequem mitgeführt werden. Aus diesen Gründen erlebt die Verwendung von Chipkarten zur Erzeugung von digitalen Signaturen zur Zeit einen enormen Aufschwung. Problematisch ist jedoch der oft unverhältnismäßig große Berechnungsaufwand für die Erzeugung von digitalen Signaturen. Ziel dieser Arbeit ist es, Methoden zu entwickeln und/oder zu untersuchen, welche die Berechnung digitaler Unterschriften wesentlich beschleunigen. Dabei spiegelt sich die Zweiteilung der in der Praxis hauptsächlich verwendeten Typen von Signaturverfahren in der Struktur der Arbeit wider. Der erste Teil dieser Arbeit untersucht Verfahren zur effizienten Berechnung von RSA-Unterschriften. Dabei entstanden die Untersuchungen in den Abschnitten 3.2.3 und 3.2.4 in Zusammenarbeit mit R. Werchner und der Inhalt der Abschnitte 3.1 - 3.2.4 ist bereits in [MW98] veröffentlicht. Im zweiten Teil entwickeln wir Verfahren zur effizienteren Generierung von Unterschriften, die auf dem diskreten Logarithmus basieren, und untersuchen deren Sicherheit. Dabei entstanden die Untersuchungen in den Abschnitten 4.2 (bis auf 4.2.2) und 4.3.1 in Zusammenarbeit mit C. P. Schnorr und sind teilweise in [MS98] zusammengefaßt. Obwohl diese Arbeit eine mathematische Abhandlung darstellt, versuchen wir, die praktische Anwendung nicht aus den Augen zu verlieren. So orientieren sich die betrachteten Verfahren stets an den durch die verfügbare Technologie gegebenen Rahmenbedingungen. Darüber hinaus richten wir unser Augenmerk weniger auf das asymptotische Verhalten der betrachteten Verfahren, als vielmehr auf konkrete, für die Anwendung relevante Beispiele.
-
Small Generic Hardcore Subsets for the Discrete Logarithm: Short Secret DL-Keys
(2000)
-
Claus Peter Schnorr
- Let G be a group of prime order q with generator g. We study hardcore subsets H is include in G of the discrete logarithm (DL) log g in the model of generic algorithms. In this model we count group operations such as multiplication, division while computations with non-group data are for free. It is known from Nechaev (1994) and Shoup (1997) that generic DL-algorithms for the entire group G must perform p2q generic steps. We show that DL-algorithms for small subsets H is include in G require m/ 2 + o(m) generic steps for almost all H of size #H = m with m <= sqrt(q). Conversely, m/2 + 1 generic steps are su±cient for all H is include in G of even size m. Our main result justifies to generate secret DL-keys from seeds that are only 1/2 * log2 q bits long.
-
Triangle groups and Jacobians of CM type
(2000)
-
Jürgen Wolfart
-
Gitter
(2000)
-
Jürgen Wolfart
- Skriptum zum Kapitel III der Vorlesung Höhere Algebra und Zahlentheorie, WS 2000/01.
-
Semiarithmetische Fuchssche Gruppen und modulare Einbettungen
(2000)
-
Sabine Ricker
