Sirene Online Abstracts 1989

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: In present-day cashless payment systems, the banks and (by installing a Trojan Horse) even the manufacturers of the computer equipment used could easily observe who pays what amount to whom and when. With the increasing digitization of these systems, e.g. point-of-sale terminals and home banking, the amount of transaction data and their computerization drastically increases. Therefore these payment systems become completely unacceptable, since compiling dossiers on the lifestyle and whereabouts of all clients will become easy.
We describe the digital payment systems enabling unobservability of clients and arrange them in a general model to compare their different degrees of unobservability and their different levels of security. Since no single system has all desired features, we propose a suitable synthesis.

Abstract: In öffentlichen Kommunikationsnetzen, z.B. dem Fernsprechnetz oder dem ISDN, muß der Datenschutz der Teilnehmer sichergestellt werden. Dieser umfaßt nicht nur den Schutz von Nachrichteninhalten, sondern auch den Schutz des Kommunikationsverhaltens (wer kommuniziert wann, wieviel, mit welchem Dienst, mit wem?).
Insbesondere das ISDN ermöglicht diesen Schutz nur sehr unzureichend. Im folgenden wird daher eine praktikable, Daten umfassend schützende Alternative zum ISDN aufgezeigt.
Um mit den ISDN-Normen und bereits vorhandenen ISDN-Ortsnetzen kompatibel zu sein, wird die Digitalisierung der Übertragung auf den vorhandenen Teilnehmeranschlußleitungen und der Ausbau des Fernnetzes wie für das ISDN geplant bzw. bereits realisiert angenommen. Die Ortsvermittlungsstellen nebst angeschlossenen Netzabschlüssen können also schrittweise modernisiert und erweitert werden. Auch die Aufteilung des Basisanschlusses in zwei unabhängige 64-kbit/s-Vollduplexkanäle für die Nutzdatenübertragung und einen 16-kbit/s-Signalisierungskanal wird übernommen.
Als bereitzustellender Dienst wird lediglich die Schaffung von 64-kbit/s-Verbindungen zwischen Netzabschlüssen mit Aufbauzeiten im Bereich von 3 s betrachtet. Ebenfalls den 16-kbit/s-Signalisierungskanal nutzende schmalstbandige Dienste werden nur am Rande betrachtet.
Der Schutz des Nachrichteninhalts wird wie üblich durch Ende-zu-Ende-Verschlüsselung, der Schutz der Teilnehmer vor Beobachtung ihres Kommunikationsverhaltens durch eine Variante des MIX-Netzes, Telefon-MIXe genannt, realisiert.
Eine alsbaldige Entwicklung und Realisierung eines Datenschutz garantierenden ISDN erscheint daher technisch möglich.

Abstract: In Journal of Cryptology 1/1 (1988) 65-75 (= [Chau_88]) David Chaum describes a technique, the DC-net, to send and receive messages anonymously over an arbitrary network. Section 2 gives a short and slightly generalized description of the DC-net and describes some known reservation techniques.

In [Chau_88] the untraceability of senders and recipients of messages is proved to be unconditional, but this proof implicitly assumes a reliable broadcast network, i.e. each message broadcast by an honest participant is received by each other participant without alterations.
Since unconditional Byzantine Agreement (i.e. BA in spite of an attacker with unlimited computational power who may control an arbitrary number of participants) is impossible, such a network cannot be realized by cryptographic means. Thus the assumption may be rather unrealistic.

In section 3 it is shown how the sending of a specific participant X can be traced by an active attacker who is able to manipulate broadcast and controls the current communication partner of X.
A number of countermeasures, called fail-stop key generation schemes, are suggested and it is proved that each of them will realize the desired unconditional untraceability in spite of active attacks.

Section 4 discusses the problem of guaranteeing serviceability while preserving untraceability.
In [Chau_88 sect. 2.5] a protocol for solving this problem is suggested which again depends on the assumption of a reliable broadcast network. It is shown that the protocol is insecure (even on the reliable broadcast assumption): the sender of one randomly selected message can always be identified.
We give several solutions for the problem: Assuming for the attacker on untraceability ...

• ... reliable broadcast, we can guarantee computationally secure serviceability (sect. 4.3).
• ... reliable broadcast and that there is an honest majority of all participants, we can guarantee serviceability on the same assumption (sect. 4.5).
• ... that the attacker is not able to prevent Byzantine Agreement, we can guarantee serviceability as secure as the Byzantine Agreement (sect. 4.4.1).
• ... that the attacker is not able to prevent the honest participants from communicating (which is considerably less than reliable broadcast), we can guarantee computationally secure serviceability (sect. 4.4.3).

Our fourth solution is based on the problem of digital signatures whose forgery by an unexpectedly powerful attacker is provable. We give a first such (one-time) signature scheme; the forgery of signatures is equivalent to the factoring problem (sect. 4.4.3.1.2).
With such signatures we can realize

• Fail-stop Byzantine Agreement, i.e. Byzantine agreement with signatures and the additional property that as soon as the attacker is able to forge signatures all other participants will recognize this (4.4.3.3). This can be used for implementing fail-stop broadcast.
• Adaptive Byzantine Agreement, i.e. Byzantine agreement which can be disturbed only by an attacker who controls more than a third of all participants and who is able to forge signatures (sect. 5).

Abstract: In Journal of Cryptology 1/1 (1988) 65-75 (= [Chau_88]), David Chaum describes a beautiful technique, the DC-net, which should allow participants to send and receive messages anonymously in an arbitrary network. The untraceability of the senders is proved to be unconditional, but that of the recipients implicitly assumes a reliable broadcast network. This assumption is unrealistic in some networks, but it can be removed completely by using the fail-stop key generation schemes by Waidner (these proceedings, = [Waid_89]). In both cases, however, each participant can untraceably and permanently disrupt the entire DC-net.
We present a protocol which guarantees unconditional untraceability, the original goal of the DC-net, on the inseparability assumption (i.e. the attacker must be unable to prevent honest participants from communicating, which is considerably less than reliable broadcast), and computationally secure serviceability: Computationally restricted disrupters can be identified and removed from the DC-net.
On the one hand, our solution is based on the lovely idea by David Chaum [Chau_88 [[section]] 2.5] of setting traps for disrupters. He suggests a scheme to guarantee unconditional untraceability and computationally secure serviceability, too, but on the reliable broadcast assumption. The same scheme seems to be used by Bos and den Boer (these proceedings, = [BoBo_89]). We show that this scheme needs some changes and refinements before being secure, even on the reliable broadcast assumption.
On the other hand, our solution is based on the idea of digital signatures whose forgery by an unexpectedly powerful attacker is provable, which might be of independent interest. We propose such a (one-time) signature scheme based on claw-free permutation pairs; the forgery of signatures is equivalent to finding claws, thus in a special case to the factoring problem. In particular, with such signatures we can, for the first time, realize fail-stop Byzantine Agreement, and also adaptive Byzantine Agreement, i.e. Byzantine Agreement which can only be disrupted by an attacker who controls at least a third of all participants and who can forge signatures.
We also sketch applications of these signatures to a payment system, solving disputes about shared secrets, and signatures which cannot be shown round.

Some younger cryptographers ...
are spending the evening in a disco. They are feeling quite relaxed and decide to tell each other who they think are the most fascinating dancers and the best cryptographers among them. However, they haven't lost all inhibitions yet and decide to say their opinions anonymously, remembering that their three bosses once invented a nice protocol for such purposes in a three-star restaurant [Chau_88].
They have some difficulties: The music is loud, and the darkness only broken by flashlights, hence their only way of communicating is to scream into each other's ears. But the admission to the disco was expensive, so they don't want to leave it for a more quiet conversation. They also fear that some of them, afraid that nobody will mention them, might disrupt the conversation. Luckily, their bosses also mentioned ideas of how disrupters could be excluded from the dinner-table.
Now one cryptographer, who thought he was at least a good dancer and therefore did not disrupt the conversation, is excluded. He is so indignant that he leaves the disco and, in the sudden silence outside, notices that the noise may have been the reason for his humiliation. Therefore, he invents a protocol which allows him to simulate the dinner-table broadcast in the disco, which will protect him from such experiences in the future, even if cryptography is wrong and any number of his colleagues are cheaters.

Back to SIRENE's Home or Pointers to the Outside World.