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: With a fail-stop signature scheme, the supposed signer of a forged signature can prove to everybody else that it was a forgery. Thus the signer is secure even against computationally unrestricted forgers. Until recently, efficient constructions were only known for restricted cases, but at Eurocrypt '92, van Heijst and Pedersen presented an efficient general scheme, where the unforgeability is based on the discrete logarithm.
We present a similar scheme based on factoring: Signing a message block requires approximately one modular exponentiation, and testing it requires a little more than two exponentiations. It is useful to have such alternative constructions in case one of the unproven assumptions is broken.
With all fail-stop signatures so far, the size of the secret key is linear in the number of messages to be signed. In one sense, we prove that this cannot be avoided: The signer needs so many secretly chosen random bits. However, this does not imply that these bits ever have to be secretly stored at the same time: We present a practical construction with only logarithmic secret storage and a less practical one where the amount of secret storage is constant.
We also prove rather small lower bounds for the length of public keys and signatures. All three lower bounds are within a small factor of what can be achieved with one of the known schemes.
Finally, we prove that with unconditionally secure signatures, like those presented by Chaum and Roijakkers at Crypto '90, the length of a signature is at least linear in the number of participants who can test it. This shows that such schemes cannot be as efficient as fail-stop signatures.
Abstract: This paper serves two purposes: We present some generalizations of the Data Encryption Standard (DES) and explain how to efficiently implement DES and its generalizations in software.
By preserving the macro structure of DES, but by allowing the user to choose
We choose, in an unorthodox way, from some well known equivalent representations of G-DES and some well suited table combinations and implementations. Concatenations of substitutions and permutations are precomputed and tabulated. Since direct tabulation of e.g. a permutation of 32 bits requires 232 entries of 4 bytes each, which clearly exceeds today's main memories, the big table is split into smaller ones that permute disjoint and compact parts of the input bits at the appropriate positions. To compute an entry in the big table, the corresponding entries in the smaller tables are ORed.
For some specific expanding permutations (including the original E in DES), the expense of this permutation can be reduced drastically: Only copy, rotate, and AND with a mask stored in a register is necessary, if the bits in the register and the tables of the substitutions are ordered appropriately. Since this is the only way we know of to achieve better performance for DES than for G-DES, it does not seem to make sense to implement anything more narrow in software than G-DES with non-arbitrary E.
Using these techniques, we get by far the fastest software implementations of DES (more specifically: G-DES with non-arbitrary E) and G-DES known to us. The same DES and G-DES implementations, partly in MC68000 assembler language, achieve
To avoid unnecessary IP and IP-1 executions and to enable multiple encryption in all modes of operation, our implementation supports multiple encryption.
Our table implementation makes it possible to save key EORing (Exclusive OR = bitwise addition mod 2) in each round by precomputing a key-specific table for every (or in some cases only every second) round. Memory requirements can be reduced by not copying bits which are input to one combined S-box.
Abstract: Digital signature schemes are a fundamental tool for secure distributed systems. It is important to have a formal notion of what a secure digital signature scheme is, so that there is a clear interface between designers and users of such schemes. A definition that seemed final was given by Goldwasser, Micali, and Rivest in 1988, and although most signature schemes used in practice cannot be proved secure with respect to it, they are all built so that they hopefully fulfil it, e.g., by the inclusion of hash functions or redundancy to counter active attacks.
Recently, however, several signature schemes with new security properties have been presented. Most of them exist in several variants, and some of them pay for the new properties with restrictions in other respects, whose relation is not always clear. Obviously, these new properties need definitions and some classification. Unfortunately, however, none of the new schemes is covered by the definition mentioned above. Hence the new properties cannot be defined as additions, but each new type of scheme needs a new definition from scratch, although there are similarities between the definitions. This is unsatisfactory.
This paper presents (an overview of) a general definition of digital signature schemes that covers all known schemes, and hopefully all that might be invented in future. Additional properties of special types of schemes are then presented in an orthogonal way, so that existing schemes can be classified systematically.
It turns out that signature schemes are best defined by a separation of service, structure, and degree of security, with a service specification in temporal logic. Several parts of such a definition can easily be reused for general definitions of other classes of cryptologic schemes.
Relations to secure multi-party protocols and logics of authentication are discussed.
Abstract: Digital signature schemes are a fundamental tool for secure distributed systems. A formal definition of digital signature schemes is important, so that there is a clear interface between designers and users of such schemes. A definition that seemed final was given by Goldwasser, Micali, and Rivest in 1988. Recently, however, several signature schemes with new security properties have been presented. Most of them exist in several variants, and some of them pay for the new properties with restrictions in other respects. These new properties need definitions and some classification. Unfortunately, however, none of the new schemes is covered by the definition mentioned above. Hence the new properties cannot be defined as additions, but each new type of scheme needs a new definition from scratch. This is unsatisfactory.
This paper presents a general definition of digital signature schemes that covers all known schemes, and hopefully all that might be invented in future. Additional properties of special types of schemes are then presented in an orthogonal way, so that existing schemes can be classified systematically.
It turns out that signature schemes are best defined by a separation of service, structure, and degree of security, with a service specification in temporal logic. Several parts of such a definition can easily be reused for general definitions of other classes of reactive cryptologic schemes, such as payment schemes.
Relations to secure multi-party protocols and so-called logics of authentication are discussed.
Abstract: Eine gründliche Analyse der Datenschutzprobleme in öffentlichen Funknetzen ergibt 8 technische Datenschutzforderungen. Nach dem Aufzeigen der erheblichen und tiefliegenden Datenschutzdefizite der bestehenden öffentlichen Funknetze wird unter defensiven Annahmen über die Peil- und Identifizierbarkeit von Funkstationen grundlegend geklärt, wie weit und wie nicht nur die Nutzdaten, sondern auch die Verkehrsdaten, insbesondere der momentane Ort mobiler Teilnehmer(stationen), überprüfbar geschützt werden können.
Das hierzu entwickelte Verfahren der Funk-MIXe wird danach um die Funktionalität des "digitalen Kommunikationsleibwächters" erweitert, um die Teilnehmer vor Belästigung und vor Ermittlung ihres Aufenthaltsortes mittels unerwünschter Anrufe zu schützen.
Möglichkeiten zur datenschutzgerechten Entgeltabrechnung und Fehlertoleranz werden erläutert.
Danach wird mittels eines einfachen Leistungsmodells die Praktikabilität des Verfahrens der Funk-MIXe demonstriert: Selbst in der für Schutz der Verkehrsdaten extrem ungünstigen Funkzellenstruktur des D-Netzes läßt sich das Verfahren der Funk-MIXe ohne neue Frequenzzuweisung realisieren. Verbindungswünsche können innerhalb von mehr als 5 Millionen Teilnehmern verteilt werden, so daß der momentane Ort eines empfangsbereiten Teilnehmers dem Netz nicht bekannt zu sein braucht.
Überlegungen zum Forschungs-, Normungs- und Entwicklungsbedarf schließen die Arbeit ab.
Abstract: Digital signature schemes are cryptologic schemes that provide a similar function for digital messages as handwritten signatures do for messages on paper: They guarantee the authenticity of a message to its recipient, and the recipient can prove this authenticity to third parties, such as courts, afterwards. Hence digital signatures are necessary wherever legal certainty is to be achieved for digital message exchange, e.g., in digital payment schemes. However, in all previously known digital signature schemes, the security for signers was based on computational assumptions, i.e., an attacker with an unexpectedly good algorithm or unexpectedly large resources could forge signatures for which a signer would be held responsible just as for her real signatures. In a certain sense, this was proved to be inevitable.
Fail-stop signature schemes, as presented in the following, improve upon it nevertheless: Forging a signature is as hard as in the most secure ordinary digital signature schemes, but if someone nevertheless succeeds in it, the supposed signer can prove that this happened, or, more precisely, that the underlying assumption was broken. Thus one can relieve her from the responsibility for the signature. Additionally, one should stop the signature system or increase the security parameters. The impossibility proof is circumvented by an extension to the definition of digital signature schemes.
In the following, first a very general semiformal definition of digital signature schemes and a classification of such schemes -- ordinary, fail-stop, others that have been invented since, and their subtypes --, are presented. Concrete definitions of fail-stop signature schemes in the conventional style and proofs of relations among them and to ordinary digital signature schemes follow. Constructions of fail-stop signature schemes are presented and proved next. They are sufficiently efficient to be used in practice. Finally, lower bounds on the efficiency achievable with fail-stop signature schemes and newer schemes with even higher security are proved. The latter indicate that those schemes cannot be as efficient as fail-stop signature schemes. Altogether, fail-stop signature schemes seem to be the most viable way of offering signers in digital signature schemes security that does not rely on computational assumptions.
Abstract: Die Vielfalt der in ihrer Qualität und praktischen Brauchbarkeit durchweg umstrittenen staatlichen Initiativen und Dokumente zur IT-Sicherheit verwirrt inzwischen auch einen aufmerksamen Beobachter. Der vorliegende Basisbeitrag wendet sich bewußt an den Nichtfachmann, also den Leser, der keine vertieften Kenntnisse der IT-Sicherheit besitzt. Die Abhandlung stellt alle wesentlichen Dokumente und Initiativen vor, charakterisiert Inhalte und Ziele und benennt die wesentlichen Schwachstellen. Sie gelangt zu dem Schluß, daß die Wirtschaftskraft und sogar die Demokratie gefährdet werden, wenn Evaluation, Zertifizierung und Akkreditierung weiterhin so unvollkommen stattfinden wie bisher. (Red.)
Abstract: On Crypto '88, Matsumoto, Kato, and Imai presented protocols to speed up secret computations with insecure auxiliary devices. The two most important protocols enable a smart card to compute the secret RSA operation faster with the help of a server that is not necessarily trusted by the card holder.
It was stated that if RSA is secure, the protocols could only be broken by exhaustive search in certain spaces. Our main attacks show that much smaller search spaces suffice. These attacks are passive and therefore undetectable.
It was already known that one of the protocols is vulnerable to active attacks. We show that this holds for the other protocol, too. More importantly, we show that our attack may still work if the smart card checks the correctness of the result; this was previously believed to be an easy measure excluding all active attacks.
Finally, we discuss attacks on related protocols.
Back to SIRENE's Home or Pointers to the Outside World.