Most of the following papers are available online in gnuzipped Postscript, some also in PDF. There is also a complete list of all our publications sorted by language and subject.
Don't forget: some proceedings are published in a later year than the conference is held.
Abstract:
We present a protocol which achieves Byzantine Agreement (BA) if less than
half of the processors are faulty and which does not rely on
unproved computational assumptions such as the unforgeability of digital
signatures. This is the first protocol which achieves this level of security.
Our protocol needs reliable broadcast and secret channels in a precomputation
phase. For a security parameter k, it achieves BA with an error
probability exponentially small in k, whereas all computations are
polynomial in k and the number of processors, n. The number of
rounds is linear in k and independent of n. The
length of the precomputation phase is linear in n and
proportional to the number of BAs based on it.
As a subprotocol, we present a coin flipping protocol on the same assumptions.
Abstract: A new type of signature scheme, a signature scheme where forgery by an unexpectedly powerful attacker is provable, was suggested in [WaPf1_89]: if the signature of an honest participant Alice is forged, she can prove this forgery with arbitrarily high probability.
The possibility of proving forgeries does not depend on any unproven
assumptions. The impossibility of forgery is based on the existence of pairs of claw-free permutations.
We improve this scheme for the special case that the GMR-generator for pairs of claw-free permutations is used [GoMR_88]: During the set-up phase, Bob
generates a pair ([[florin]]0, [[florin]]1). Alice's security
depends entirely on the sufficiency of Bob's choice. Therefore, in the general
case, Bob has to prove to Alice the sufficiency of his choice by a
zero-knowledge proof (ZKP). We show that for the GMR-generator, this expensive ZKP can be replaced by the simple condition that the modulus chosen by Bob is odd.
In Section II, we sketch a simplified version of the signature scheme of
[WaPf1_89]. Section III contains the necessary notations. The GMR-generator is described in Section IV. In Section V we present our result.
Abstract: Es wird motiviert und gefordert, präzise zu dokumentieren, wer bei der Konstruktion von informationstechnischen Systemen wofür verantwortlich ist. Dies könnte das Spezifische eines zu schaffenden Berufsrechts für Informatiker sein.
Abstract:
1984 wurde von Goldwasser, Micali und Rivest erstmalig ein gegen adaptive,
aktive Angriffe beweisbar sicheres Signatursystem (GMR) vorgestellt. Bis dahin galt ein solches System als Paradoxon - den scheinbaren Widerspruch lösten die Autoren in ihrer Veröffentlichung.
Nach einer kurzen Einführung in die Funktionsweise von GMR arbeiten wir die schon bekannten Implementierungshinweise aus und erläutern eigene effizienzsteigernde Verbesserungen.
Diese nutzten wir für eine Implementierung auf MC680xy-Rechnern. Die von uns verwendete Langzahlarithmetik ist in Assembler geschrieben; die
GMR-spezifischen Funktionen wurden im wesentlichen in Pascal entwickelt.
Wir stellen relativ genaue allgemeine Aufwandsbetrachtungen an und
erläutern die Meßergebnisse unserer Implementierung. Beide Angaben werden mit Werten für das verbreitete RSA-Signatursystem verglichen. Dabei stellt sich heraus, daß GMR nicht nur praktikabel, sondern in manchen Fällen sogar effizienter ist als RSA (in reiner Form). Stellt man hohe Sicherheitsanforderungen, ist GMR demnach eine empfehlenswerte Alternative.
English abstract:
In 1984, Goldwasser, Micali, and Rivest first presented a signature scheme secure against adaptive active attacks (GMR). Until then, such a system had been regarded as a paradox - the apparent contradiction was solved by the authors in their publication.
After a short introduction into how GMR works, we elaborate known suggestions for an implementation and present improvements to increase the efficiency.
We used these in an implementation for MC680xy computers. The long integer arithmetic we used is written in assembler; the GMR-specific functions were mainly developed in Pascal.
We give compute the complexity quite precisely and explain the measured results of our implementation. Both data are compared with values for the well-known RSA signature schemes. It turns out that GMR is not only practical, but in some cases more efficient than RSA (in pure form). If one has high security requirements, GMR can therefore be recommended as an alternative.
Abstract:
In [Journal of Cryptology 1/1 (1988) 65-75] beschreibt DAVID CHAUM ein
Protokoll zum anonymen Senden und Empfangen, das DC-Netz. Die
Unbeobachtbarkeit des Sendens ist unbedingt, d.h. sie hängt von keinerlei
kryptographischen Annahmen ab. Die Unbeobachtbarkeit des Empfangens setzt
jedoch implizit ein zuverlässiges Verteilnetz voraus. Die
Unbeobachtbarkeit von Senden und Empfangen wird unbedingt, wenn
man die für das DC-Netz benötigten kryptographischen Schlüssel
auf geeignete Weise erzeugt, nämlich durch fail-stop
Schlüsselerzeugung.
Die von Michael Waidner in [Eurocrypt '89, Houthalen 1989, Session 7, 4.
Vortrag] vorgeschlagenen Verfahren verwenden zur fail-stop
Schlüsselerzeugung einfache arithmetische Ausdrücke über
endlichen Körpern. Der Aufwand zur Schlüsselerzeugung wird
näherungsweise halbiert, indem innerhalb dieser arithmetischen
Ausdrücke jeweils zwei Multiplikationen und eine Additionen durch eine
Multiplikation und zwei Additionen ersetzt werden, d.h. ax+by
durch (a+b)(x+y). Es wird gezeigt, daß die
Sicherheit hiervon unberührt bleibt.
Abstract: Es wird ein informeller Überblick über die Eigenschaften von herkömmlichen digitalen Signatursystemen gegeben, insbesondere deren Vor- und Nachteile bzgl. Sicherheit. Anschließend werden die Eigenschaften der neuartigen, sichereren Fail-stop-Signaturen dagegengestellt.
Abstract:
Digital signatures are necessary wherever legal certainty is to be achieved for
digital message exchange. However, the unforgeability of conventional digital
signatures is necessarily based on complexity theoretic assumptions. That is,
even the most secure schemes can be broken by an adversary with unexpected
computing abilities, e.g., one who can factor unexpectedly large numbers.
Fail-stop signatures improve upon this: They are as unforgeable as the best
conventional signatures; but if someone nevertheless succeeds in forging a
signature, this can be proved by the supposed signer. Thus one can relieve him
from the responsibility for this signature. Additionally, one should stop the
scheme or increase the security parameters.
As applications, mainly digital payment systems are discussed. The social and
legal advantages of such a scheme are discussed, and a sketch of the
construction of practical fail-stop signatures for this case is given (roughly
three times the expenditure of a conventional signature scheme).
Abstract:
Immer mehr kommunizieren Menschen und Maschinen über öffentliche
Vermittlungsnetze. Sensitive Daten (z.B. personenbezogene Daten,
Geschäftsgeheimnisse) können dabei sowohl aus den eigentlichen
Nutzdaten als auch aus den Vermittlungsdaten, z.B. Ziel- und
Herkunftsadresse, Datenumfang und Zeit, gewonnen werden.
Wir untersuchen, wie sie vor illegalen und legalen Netzbenutzern, dem Betreiber
des Netzes und seinen Angestellten sowie den Herstellern der
Vermittlungszentralen geschützt werden können. Manche
Vermittlungsdaten, z.B. die genauen Netzadressen der Teilnehmer, müssen
auch vor Kommunikationspartnern, etwa Datenbanken, geschützt werden, damit
sie nicht als Personenkennzeichen verwendbar werden.
Bei der heute üblichen und von der Deutschen Bundespost auch für die
Zukunft geplanten Struktur öffentlicher Netze, insbesondere des
diensteintegrierenden ISDN, erlauben auch juristische Datenschutzvorschriften
und Verschlüsselung keinen ausreichenden und mit vernünftigem Aufwand
überprüfbaren Datenschutz. Dies dürfte das im
Volkszählungsurteil des Bundesverfassungsgerichts formulierte "Recht auf
informationelle Selbstbestimmung" verletzen.
Deshalb werden die zur Abhilfe geeigneten bekannten Grundverfahren zusammen mit
einigen Überlegungen zu ihrer Implementierung dargestellt. Danach wird
gezeigt, wie diese Grundverfahren zum schrittweisen Ausbau eines Datenschutz
garantierenden offenen, zunächst schmalbandigen, später bei Bedarf
breitbandigen und diensteintegrierenden Digitalnetzes verwendet werden
können.
Abstract:
Untraceable communication for services like telephony is often considered
infeasible in the near future because of bandwidth limitations. We present a
technique, called ISDN-MIXes, which shows that this is not the case.
As little changes as possible are made to the narrowband-ISDN planned by the
PTTs. In particular, we assume the same subscriber lines with the same bit
rate, and the same long-distance network between local exchanges, and we offer
the same services.
ISDN-MIXes are a combination of a new variant of CHAUM's MIXes, dummy
traffic on the subscriber lines (where this needs no additional bandwidth), and
broadcast of incoming-call messages in the subscriber-area.
Abstract:
Mit dem DC-Protokoll von D. CHAUM sollen Teilnehmer über ein
beliebiges Kommunikationsnetz Nachrichten unbeobachtbar senden und
empfangen können. Dieses Protokoll hat zwei Schwachpunkte, die im
folgenden betrachtet und beseitigt werden:
1. Das Protokoll ist nicht robust: Jeder Teilnehmer kann das DC-Protokoll
unbeobachtbar und dauerhaft stören. Wir stellen ein Fallenprotokoll
vor, das Störer identifiziert und von der weiteren Teilnahme
ausschließt. Es setzt ein zuverlässiges Verteilnetz voraus und nimmt
an, der Störer verfüge nur über beschränkte
Berechnungsfähigkeiten (z.B. könne natürliche Zahlen mit
zwei sehr großen Primfaktoren nicht faktorisieren). Unser Protokoll ist
eine Verbesserung eines Protokolls von D. CHAUM.
2. Während im DC-Protokoll die Unbeobachtbarkeit des Sendens von
keinerlei Annahmen über den möglichen Angreifer abhängt
(unbedingte Senderunbeobachtbarkeit), setzt die des Empfangens
zuverlässige Verteilung voraus. Diese Annahme ist z.B. in Sternnetzen
unrealistisch. Wir stellen ein Protokoll vor, das Unbeobachtbarkeit
unter der Zusammenhangsannahme (= gute Teilnehmer können nicht
daran gehindert werden, paarweise miteinander zu kommunizieren) und
kryptographische Robustheit kombiniert. Dazu ersetzen wir die
angenommene zuverlässige Verteilung durch robuste fail-stop
Byzantinische Übereinstimmung: Diese garantiert zuverlässige
Verteilung, falls der Angreifer kryptographisch beschränkt ist und die
Zusammenhangsannahme zutrifft; verfügt er über unerwartet große
Berechnungsfähigkeiten, so stoppt das Protokoll. Sollen Unbeobachtbarkeit
und Robustheit garantiert werden, so ist die Zusammenhangsannahme notwendig.Im
Anhang beschreiben wir ein Protokoll zur adaptiven Byzantinischen
Übereinstimmung, d.h. Byzantinische Übereinstimmung, die nur
gestört werden kann, wenn ein Angreifer sowohl mindestens ein Drittel
(bzw. die Hälfte) aller Teilnehmer kontrolliert als auch Signaturen
fälschen kann.
Abstract:
The unforgeability of conventional digital signatures is necessarily based on
complexity theoretic assumptions, i.e. even the most secure schemes can be
broken by an adversary with unexpected computing abilities. Thus we introduce
fail-stop signatures: They are as unforgeable as the best conventional
signatures, but if a signature is forged nevertheless, the supposed signer can
prove the forgery unconditionally (i.e. without assumptions), with arbitrarily
high probability.
We construct actual fail-stop signature schemes, called hiding schemes, from
arbitrary claw-free pairs of permutations. As a special case, we obtain a
rather practical system where forging is as hard as factoring.
We also present applications to digital payment systems, and sketch those to
reliable broadcast.
Abstract:
Die Unfälschbarkeit konventioneller digitaler Signaturen beruht
zwangsläufig auf komplexitätstheoretischen Annahmen, d.h. selbst die
sichersten Systeme können durch einen unerwartet mächtigen Angreifer
gebrochen werden. Daher führen wir Fail-stop-Signaturen ein: Sie sind so
unfälschbar wie die besten konventionellen Signaturen, aber wenn doch eine
Signatur gefälscht wird, kann der angebliche Unterzeichner unbedingt (d.h.
ohne jegliche Annahmen) die Fälschung beweisen, mit beliebig hoher
Wahrscheinlichkeit.
Wir konstruieren konkrete Fail-stop-Signatursysteme, die sogenannten
Versteckssysteme, aus beliebigen kollisionsfreien Paaren von Permutationen. Als
Spezialfall ergibt sich ein relativ praktikables System, in dem Fälschen
so schwer ist wie Faktorisierung.
Ausführlich werden Anwendungen in digitalen Zahlungssystemen betrachtet,
auf Anwendungen auf zuverlässige Verteilung wird verwiesen.
Abstract:
PEASE/SHOSTAK/LAMPORT's Byzantine Generals Problem (also called
Reliable Broadcast or Byzantine Agreement) is the fundamental
problem of achieving reliable broadcast in a distributed system where this is
not available physically and where some processors (including the processor
whose message must be broadcast) may be faulty.
It is investigated how many faulty processors can be tolerated in the original
Byzantine failure model. It is assumed that all correct processors are
synchronized and are able to communicate reliably with each other. Up to
t of all n processors may become maliciously faulty. There are no
computational or cryptographic assumptions (like "digital signatures are
unforgeable") on the behaviour of faulty processors.
On these assumptions, many protocols are known which tolerate any number t
< n/3 of faulty processors, and it is well known that for
t >= n/3, there are no deterministic protocols.
For the first time, protocols are described which tolerate n/3 and more
faulty processors in the Byzantine failure model: They have an error
probability <= 2^\sigma and tolerate any t
< n/2 in a constant expected number of rounds (worst case in
O(\sigma) rounds), or any t < n in t+1
rounds. Their computational and communication complexity is polynomial in
n and \sigma.
For all our protocols, it is necessary that an arbitrary time before they are
executed a preparation protocol is performed during which each processor
broadcasts some information to all other processors reliably (similar to the
key distribution of digital signatures).
Basis of our protocol tolerating any t < n/2 is a verifiable
secret sharing scheme which needs reliable broadcast for sharing a secret, but
not for revealing it. Basis of our protocol tolerating any t <
n is a new unconditionally secure authentication technique, which can
replace computationally secure digital signatures in many authenticated
protocols.
Back to SIRENE's Home or Pointers to the Outside World.