Sirene Online Abstracts 1991

(Sorted by authors.)

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.


Birgit Baum-Waidner, Birgit Pfitzmann, Michael Waidner: Unconditional Byzantine Agreement with Good Majority; STACS'91, LNCS 480, Springer-Verlag, Heidelberg 1991, 285-295.

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.


Gerrit Bleumer, Birgit Pfitzmann, Michael Waidner: A Remark on a Signature Scheme where Forgery can be Proved;Eurocrypt '90, LNCS 473, Springer-Verlag, Berlin 1991, 441-445.

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.


Wolfgang Clesle, Andreas Pfitzmann: Rechnerkonzept mit digital signierten Schnittstellenprotokollen erlaubt individuelle Verantwortungszuweisung; Datenschutz-Berater 14/8-9 (1991) 8-38.

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.


Dirk Fox, Birgit Pfitzmann: Effiziente Software-Implementierung des GMR-Signatursystems; Proc. GI-Fachtagung Verläßliche Informationssysteme (VIS'91), Mrz 1991, Darmstadt, Informatik-Fachberichte 271, Springer-Verlag, Heidelberg 1991, 329-345.

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.


Jörg Lukat, Andreas Pfitzmann, Michael Waidner: Effizientere fail-stop Schlüsselerzeugung für das DC-Netz; Datenschutz und Datensicherung DuD 15/2 (1991) 71-75.

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.


Birgit Pfitzmann: Neu und sicher: Digitale Fail-stop-Signaturen; KES - Zeitschrift für Kommunikations- und EDV-Sicherheit 7/5 (1991) 321-326.

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.


Birgit Pfitzmann: Fail-stop Signatures: Principles and Applications; Proc. Compsec '91, 8th world conference on computer security, audit and control, Elsevier, Oxford 1991, 125-134.

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).


Andreas Pfitzmann, Birgit Pfitzmann, Michael Waidner: Datenschutz garantierende offene Kommunikationsnetze; Teletech NRW, Landesinitiative Telekommunikation des Ministeriums für Wirtschaft, Mittelstand und Technologie des Landes Nordrhein-Westfalen; März 1991, Vortragsausarbeitung Nr. 2, Präsentation auf CeBIT'91.
Überarbeitungen in: Dokumentation des Fachseminars "Programm-Manipulationen in Netzen", SYSTEMS 91, München; Hrsg. Deutsche Informatik-Akademie, Bonn, Oktober 1991.
und: Vernetzte Systeme und Sicherheit der Informationsverarbeitung, Deutsche Informatik Akademie, Begleitunterlage zu einem Tutorium der GI-Jahrestagung 1992, Karlsruhe, 75-120.
und: Dokumentation Fachseminar Sicherheit in Netzen, 21. Okt. 1993, SYSTEMS 93, München, 75-121.

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.


Andreas Pfitzmann, Birgit Pfitzmann, Michael Waidner: ISDN-MIXes - Untraceable Communication with very small Bandwidth Overhead; Proc. Kommunikation in verteilten Systemen, Feb. 1991 Mannheim, Informatik-Fachberichte 267, Springer-Verlag, Heidelberg 1991, 451-463; Slightly extended in: Information Security, Proc. IFIP/Sec'91, Mai 1991, Brighton, D. T. Lindsay, W. L. Price (eds.), North-Holland, Amsterdam 1991, 245-258.

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.


Birgit Pfitzmann, Michael Waidner: Unbedingte Unbeobachtbarkeit mit kryptographischer Robustheit; Proc. of the GI-Fachtagung Verläßliche Informationssysteme (VIS'91), March 1991, Darmstadt, Informatik-Fachberichte 271, Springer-Verlag, Heidelberg 1991, 302-320.

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.


Birgit Pfitzmann, Michael Waidner: Fail-stop Signatures and their Application; SECURICOM 91; 9th Worldwide Congress on Computer and Communications Security and Protection, 20.-22. March 1991, Paris La Défense, 145-160.

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.


Birgit Pfitzmann, Michael Waidner: Fail-stop-Signaturen und ihre Anwendung; Proc. of the GI-Fachtagung Verläßliche Informationssysteme (VIS'91), March 1991, Darmstadt, Informatik-Fachberichte 271, Springer-Verlag, Heidelberg 1991, 289-301.

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.


Michael Waidner: Byzantinische Verteilung ohne kryptographische Annahmen trotz beliebig vieler Fehler; Doctoral Thesis, Universität Karlsruhe 1991.

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.


Birgit Pfitzmann, pfitzmann@cs.uni-sb.de
Last modified: $Date: 2000/02/28 16:01:38 $