Preface

About Cryptology

It is now widely perceived that we are experiencing an information revolution whose effects will ultimately be as pervasive and profound as was brought by the industrial revolution of the last century. From the beginning of time, information has been an important asset for humans. In the early days of human existence, the mere knowledge of where to most easily gather food was the difference between life and death. Throughout history, information has provided the means for winning wars, making fortunes, and shaping history. The underlying theme of the information revolution is that we continue to find new ways to use information. These new uses for information serve to highlight our need to protect different aspects of information.

Cryptology may be broadly defined as the scientific study of adversarial information protection. Cryptology has traditionally dealt with the confidentiality of information, but innovation in using information produces new requirements for protection of that information. Some are longstanding and fundamental - how do we guarantee that information is "authentic"? How do we guarantee that information is timely? How can we produce bits that have the same properties as "money"? Each of these questions has been grappled with in the cryptologic research community.

History of the IACR

Cryptography has a long and illustrious history, but relatively little published scientific literature existed prior to the mid 1970s, when public key cryptography was discovered and interest was sparked in the scientific study of information protection. The early 1980's saw a number of conferences on the subject of cryptography, including the first conference held in Santa Barbara in 1981, organized by Alan Gersho of UCSB. This was followed in 1982 by the Crypto '82 conference. A report on this conference was published by David Kahn in Cryptologia the following year:

``At the initiative of David Chaum the organizer of Crypto '82, some attendees met the last day to begin organizing what they tentatively called an International Association for Cryptologic Research. Its main functions would be (1) to coordinate meetings on cryptology as to time, place and program and in some cases to run them, and (2) to publish a bulletin to give notice of conferences and of cryptologic sessions other conferences. Members of the organizing committee are Chaum; Henry J. Beker of RACAL-Comsec Ltd. in Salisbury, England; Whitfield Diffie of BNR in Palo Alto, California; Robert R. Jueneman of Satellite Business Systems in McLean, Virginia; Ernest F. Brickell of Sandia National Laboratories in Albuquerque, New Mexico; Stephen Kent of Bolt, Beranek & Newman in Cambridge, Massachusetts; and David Kahn of Great Neck, New York, an editor of Cryptologia.''

Crypto '83 then became the first conference officially sponsored by IACR. From these early beginnings, IACR has grown to be a scientific organization with over a thousand members worldwide, representing over 65 countries. IACR now sponsors two conferences each year, called Crypto and Eurocrypt. Crypto is held each year in August at the University of California in Santa Barbara, USA. Eurocrypt is held each spring in a different location in Europe. IACR will also begin sponsorship of the Asiacrypt conference in 2000.

Proceedings of Crypto and Eurocrypt

The work published here includes the proceedings of all conferences that have been organized by the International Association for Cryptologic Research since 1983. In addition, material from a few other conferences that spawned IACR is included:

proceedings of Crypto '81. These were first published as a technical report by the University of California, Santa Barbara, and have had only very limited circulation prior to this volume. In addition, it was previously published in SIGACT News in 1983.
proceedings of the 1982 predecessor to Eurocrypt. The IACR was in the process of being formed at that time, but there was already an intent among many of the organizers for this to be the first in a series of European conferences on cryptology organized by IACR. The '82 conference was not originally called Eurocrypt, but is now generally referred to as Eurocrypt '82.
proceedings of Crypto '82 and '83. These were originally published by Plenum Publishing. As of the time of this writing (mid-1998), the proceedings of Crypto '83 are no longer available in print.
abstracts from Eurocrypt '86. This volume was only distributed to conference attendees.

Eurocrypt '86 and Crypto '81 had no formal proceedings, and the material included here consists mostly of abstracts. In fact, over time it is possible to detect a noticeable change in the tone of papers in all of these volumes, from early publication of ``Extended Abstracts'' to more carefully refereed high quality papers.

The proceedings of both Crypto and Eurocrypt have been published by Springer-Verlag since 1984 in the series "Lecture Notes in Computer Science". Prior to 1994, authors submitted abstracts that were distributed to attendees at the conference, and these abstracts were then refined and published as a formal proceedings at a later date. (an exception was made at Eurocrypt '86). Beginning with Crypto '94, proceedings of Eurocrypt and Crypto have been available at the conference.

The Evolution of Cryptology Research

The work published here represents the majority of the important research work that has been published by the open cryptologic research community during the last fifteen years. In spite of the great work that has been done, there are still huge gaps in our knowledge of information protection. I hope that the republication of these proceedings will stimulate further research in the field and I thank Springer-Verlag for supporting the initiative to produce them.

Looking at how the field has evolved over the years, there are some noticeable trends. The ones that are most noticeable to this author are the following:

Complexity-based reasoning on security

The first mention that I am aware of involving reasoning about security based on what an adversary could compute appeared in Shannon's seminal paper of 1948. Once Diffie and Hellman published their paper on public key cryptography, we were presented with concrete constructions that led to a huge body of work on complexity-based reasoning on security. In recent years some of the work in complexity-based security has incorporated some of the original ideas of Shannon on information-theoretic security. In spite of the considerable progress that has been made, I would argue that the field is still not closed, because some of the assumptions we are required to make in order to prove reasonable security are still questionable. Moreover, computing is fundamentally about resource management, and in spite of Moore's law, there continue to be increasing demands for processing speed, storage, and communication. The constructions that we have today may have considerable room for improvement, both in their security and their practicality.

Environmental Attacks and Protocols

I use the term ``environmental attacks'' to include things such as fault analysis, timing attacks, and power analysis. Each of these has been demonstrated to pose a serious hazard in real world applications, and also serves to highlight several defects in our abstract modeling of security. First is the fact that our models of computers fail to take into account all aspects of their physical instantiation. Looking at a computer as a ``black box'' provides an elegant abstraction, but in practice the box exists in three dimensional space, manipulates energy, and produces ancillary outputs. Future models of computers and security may emerge to describe these phenomena. The second deficiency in our understanding has to do with the fact that true security requires analysis of protocols instead of serial algorithms. If we include parallel and distributed algorithms, then the difference between a protocol and an algorithm is that an algorithm may involve multiple parties, but a protocol always does. When reasoning about security, there are always at least two parties: the adversary and the participant. Any analysis that fails to address the capabilities of an adversary to affect the outputs is doomed to failure.

Linear and Differential Cryptanalysis

Linear and Differential cryptanalysis have emerged as the most effective general techniques available for attacking practical ciphers. At the same time, progress has been made in designing ciphers that are resistant to these attacks.

New Applications

Cryptology is no longer restricted to the study of only encryption and confidentiality. As new uses of information emerge, they bring with them new requirements for information. As a result, we have seen discussion of cryptographic constructions for electronic cash, timestamping, program checking, intellectual property protection, etc. Each of these applications raises whole new areas for investigation.

It is ironic that the publication of this CDROM itself raises interesting and serious issues in the protection of information, since the information age is changing the very foundation of what it means to "publish". Some have argued that electronic publishing raises serious concerns about the mechanism for archiving scientific work for the ages. Others have argued that the role of traditional publishers is threatened by the information age. Some publishers are concerned that their ability to make a living is threatened by electronic distribution of information, since bits are easily copied and the meaning of traditional copyrights are evolving. Nevertheless, Springer-Verlag has taken the lead in developing technologies that offer new capabilities for the use of information.

Some Statistics

I close this section with some statistics and trivia about the body of literature. This collection contains 1285 individual papers, by a total of 854 authors.

Most Authors on a Single Paper

The following papers have the most co-authors.

10 authors: c83-171, Davio, M., Desmedt, Y., Fosseprez, M., Govaerts, R., Hulsbosch, J., Neutjens, P., Piret, P., Quisquater, J. J., Vandewalle, J. and Wouters, P., Analytical characteristics of the DES
7 authors: c88-37, Ben-Or, M., Goldreich, O., Goldwasser, S., Hastad, J., Kilian, J., Micali, S. and Rogaway, P., Everything provable is provable in zero-knowledge
7 authors: c91-44, Bird, R., Gopal, I., Herzberg, A., Janson, P., Kutten, S., Molva, R. and Yung, M., Systematic design of two-party authentication protocols
7 authors: e92-194, Desmedt, Y., Landrock, P., Lenstra, A. K., McCurley, K. S., Odlyzko, A. M., Rueppel, R. A. and Smid, M. E., The Eurocrypt '92 Controversial Issue: Trapdoor Primes and Moduli
6 authors: e89-267, Vandewalle, J., Chaum, D., Fumy, W., Jansen, C. J. A., Landrock, P. and Roelofsen, G., A European call for cryptographic algorithms: RIPE; Race Integrity Primitives Evaluation
6 authors: e91-547, Preneel, B., Chaum, D., Fumy, W., Jansen, C. J. A., Landrock, P. and Roelofsen, G., Race Integrity Primitives Evaluation
6 authors: c92-471, Blundo, C., De Santis, A., Herzberg, A., Kutten, S., Vaccaro, U. and Yung, M., Perfectly-secure key distribution for dynamic conferences
5 authors: c96-329, Hughes, R. J., Luther, G. G., Morgan, G. L., Peterson, C. G. and Simmons, C., Quantum Cryptography over Underground Optical Fibers
5 authors: c81-154, Diffie, W., Klein, M., Dertouzos, M. L., Gleason, A. and Smith, D., Panel Discussion: National Security and Commercial Security: Division of Responsibility
5 authors: c84-144, Davio, M., Desmedt, Y., Goubert, J., Hoornaert, F. and Quisquater, J. J., Efficient hardware and software implementations for the DES
5 authors: e85-43, Vandewalle, J., Govaerts, R., De Becker, W., Decroos, M. and Speybrouck, G., Implementation study of public key cryptography protection in an existing electronic mail and document handling system.
5 authors: c85-3, Estes, D., Adleman, L. M., Kompella, K., McCurley, K. S. and Miller, G. L., Breaking the Ong-Schnorr-Shamir signature scheme for quadratic number fields
5 authors: c86-277, Orton, G. A., Roy, M. P., Scott, P. A., Peppard, L. E. and Tavares, S. E., VLSI implementation of public-key encryption algorithms
5 authors: c88-297, Abadi, M., Allender, E., Broder, A., Feigenbaum, J. and Hemachandra, L. A., On generating solved instances of computational problems
5 authors: e89-294, Chaum, D., den Boer, B., van Heyst, E., Mjoelsnes, S. F. and Steenbeek, A., Efficient offline electronic checks (extended abstract)
5 authors: e90-161, Preneel, B., Van Leekwijck, W., Van Linden, L., Govaerts, R. and Vandewalle, J., Propagation characteristics of Boolean functions
5 authors: e90-253, Bennett, C. H., Bessette, F., Brassard, G., Salvail, L. and Smolin, J., Experimental quantum cryptography
5 authors: e90-465, Guillou, L. C., Quisquater, J. J., Walker, M., Landrock, P. and Shaer, C., Precautions taken against various potential attacks in ISO/IEC DIS 9796
5 authors: e92-356, Biehl, I., Buchmann, J. A., Meyer, B., Thiel, C. and Thiel, C., Tools for proving zero knowledge
5 authors: c92-215, Dwork, C., Feige, U., Kilian, J., Naor, M. and Safra, M., Low communication 2-prover zero-knowledge proofs for NP
5 authors: e93-126, Kurosawa, K., Okada, K., Sakano, K., Ogata, W. and Tsujii, S., Nonperfect secret sharing schemes and matroids
5 authors: e94-433, Charnes, C., O'Connor, L., Pieprzyk, J., Safavi-Naini, R. and Zheng, Y., Comments on Soviet encryption algorithm
5 authors: c94-150, Blundo, C., De Santis, A., Di Crescenzo, G., Gaggia, A. Giorgio and Vaccaro, U., Multi-secret sharing schemes

Most Papers by a Single Author

The following authors have the most papers published in the series:

Chaum, D. (38): c81-138, c82-199, c83-153, c83-387, c84-432, c84-481, e85-241, c85-18, c85-192, c86-49, c86-118, c86-195, c86-200, e87-127, e87-227, c87-87, c87-156, c87-462, e88-177, c88-319, e89-267, e89-288, e89-294, c89-212, c89-591, e90-458, c90-189, c90-206, e91-96, e91-257, e91-547, e91-554, c91-470, e92-390, c92-1, c92-89, e93-344, e94-86
Desmedt, Y. (34): c83-171, e84-62, e84-142, c84-144, c84-147, c84-359, c85-42, c85-516, c85-537, e86-17, c86-111, c86-459, c87-21, c87-120, e88-23, e88-183, c88-375, e89-75, e89-122, c89-6, c89-307, e90-1, e90-11, c90-169, c90-177, e91-81, e91-205, c91-457, e92-25, e92-194, c92-549, e94-275, e95-147, e96-107
Yung, M. (30): c84-439, c85-128, c87-40, c87-135, e89-3, e89-192, e89-196, e90-412, c90-94, c90-177, c90-366, e91-205, c91-44, c92-196, c92-442, c92-471, e93-267, e94-67, c95-222, c95-287, c95-339, e96-72, c96-89, c96-186, e97-62, e97-280, e97-450, c97-31, c97-264, c97-440
Damgård, I. B. (27): e87-203, c87-87, c87-156, c87-462, e88-167, c88-163, c88-328, c88-580, c88-583, c89-17, c89-416, c90-189, c91-445, e92-341, e92-461, c92-358, e93-200, e93-286, c93-100, c93-250, e94-140, c94-174, c95-297, c95-325, e96-372, c96-173, e97-75
Goldreich, O. (26): c82-205, c82-315, c83-43, c83-133, c83-383, e84-127, e84-387, c84-276, c84-303, c85-58, c85-448, c86-104, c86-171, c86-426, c87-73, c88-37, c88-57, c88-146, c89-113, c89-263, c92-390, c94-216, c95-325, c97-46, c97-105, c97-112
Shamir, A. (25): c81-1, c82-279, c84-37, c84-47, e85-31, c85-58, c85-280, c86-186, c87-398, c88-244, c88-284, c89-526, c89-606, c90-2, c90-353, c90-394, e91-1, c91-156, c91-213, c92-487, c93-1, e94-1, e94-445, e97-52, c97-513
Quisquater, J. J. (23): e82-283, c83-171, e84-62, c84-144, c84-359, c85-537, e86-17, c86-111, c87-203, c87-223, c87-255, e88-123, c88-216, e89-102, e89-429, e89-662, c89-253, c89-408, c89-628, e90-465, c90-502, c94-83, c95-57
Okamoto, T. (22): c88-232, e89-134, c89-481, e90-446, c90-456, e91-96, e91-243, e91-446, c91-252, c91-267, c91-324, e92-324, e92-420, c92-31, c92-54, e93-461, e94-306, c94-61, c95-325, c95-438, c97-16, c97-31
Brickell, E. F. (22): c82-15, c82-51, c82-289, c83-25, c83-39, c84-342, c85-28, e86-21, c86-3, e87-117, c87-156, c87-418, e88-51, e88-275, c88-564, e89-403, e89-468, c89-278, c89-368, e90-63, c90-242, e92-200
Micali, S. (21): c82-211, c84-276, c86-171, c86-381, c87-52, c88-37, c88-173, c88-200, c88-244, c88-256, c88-269, c89-263, c89-545, c89-547, c90-253, c91-392, c92-113, c93-456, e95-168, c95-185, c96-201
Simmons, G. J. (21): c81-31, c81-79, c82-289, c83-51, e84-183, e84-364, c84-411, e85-261, c85-33, e86-16, c86-9, e87-151, c87-211, c87-269, e88-35, c88-390, e89-436, e90-266, c90-216, e93-218, e93-448
Brassard, G. (20): c81-54, c82-79, c82-267, c84-475, c85-468, c86-223, c86-234, c86-443, c87-461, c88-580, e89-16, e89-181, e89-192, e90-253, c90-49, c90-94, c91-351, e93-410, e97-334, c97-337
Maurer, U. M. (19): e87-237, e89-636, c89-100, e90-361, c90-409, e91-458, e91-498, c91-252, e92-239, e92-429, e92-458, c92-461, e94-266, c94-75, c94-271, c96-268, e97-209, c97-292, c97-307
Crépeau, C. (19): c85-73, c86-223, c86-234, c86-239, c86-443, c87-350, c87-462, c88-2, e89-150, e89-181, e89-192, c90-49, e91-106, c91-351, c93-319, e95-133, c95-110, e97-306, e97-334
Schnorr, C. P. (18): e82-325, e82-331, c83-117, e84-113, c84-37, e88-225, c88-173, e89-688, c89-239, e90-432, e91-54, e91-281, e92-45, e92-408, e94-47, e95-1, c96-143, e97-267
Bellare, M. (17): c88-200, c89-194, c89-547, c89-604, c92-390, c92-442, c93-232, e94-92, c94-216, c94-341, c95-15, e96-399, c96-1, e97-163, e97-280, c97-277, c97-470
Ohta, K. (16): c87-175, e88-11, c88-232, e89-134, c89-481, e90-326, e90-446, c90-456, e91-96, e91-243, c91-183, c91-324, e92-324, c93-200, c94-12, c95-157
Kilian, J. (16): c88-2, c88-37, c89-498, c89-545, c90-62, c90-313, c90-378, c91-225, c92-215, c93-319, c94-341, c94-411, e95-393, c95-208, c95-311, c96-252
Vandewalle, J. (16): c83-171, e85-43, e86-20, e87-109, e87-287, e88-257, e89-267, c89-154, e90-161, e91-141, e93-159, c93-175, c93-224, c93-368, c96-298, e97-348
Pedersen, T. P. (16): c88-583, c90-189, e91-221, e91-522, c91-129, e92-366, e92-390, c92-15, c92-89, e93-329, c93-250, e94-140, e94-171, e95-39, e96-237, e96-372
Stinson, D. R. (15): c86-418, c87-330, c87-355, e88-51, c88-564, c90-242, c91-62, c91-74, e92-1, c92-168, e94-35, c94-247, c96-16, c96-387, e97-409
Goldwasser, S. (15): c82-211, c84-276, c84-289, c85-448, c88-37, c89-194, c89-498, c89-589, c89-604, c90-77, c92-228, c94-216, c97-105, c97-112, c97-277
Govaerts, R. (14): c83-171, e85-43, e86-20, e87-109, e88-257, c89-154, e90-161, e91-141, e93-159, c93-175, c93-224, c93-368, c96-298, e97-348
Massey, J. L. (14): e82-289, e84-74, e86-35, e87-3, e87-237, e89-382, c89-100, e90-389, e91-17, e92-55, c92-540, c94-332, e95-24, c96-358
Zheng, Y. (13): e89-412, c89-461, c90-285, c92-292, e93-181, c93-49, e94-299, e94-376, e94-433, c94-383, e95-274, e96-294, c97-165
De Santis, A. (13): c87-52, c88-269, e90-46, e90-412, c90-366, c91-101, e92-1, c92-148, c92-471, e93-118, c93-73, c93-110, c94-150
Pfitzmann, B. (13): e89-373, e89-690, e90-441, c91-338, c91-470, e92-153, c92-15, c93-250, e94-332, e95-121, e96-84, e97-88, e97-480
Beaver, D. (12): c89-560, c89-589, c90-62, c90-326, c91-377, c91-420, e92-285, e92-307, e93-424, c95-97, e96-119, c97-75
Krawczyk, H. (12): c88-146, c89-113, c89-138, c93-22, c93-136, c94-129, e95-301, c95-339, e96-354, c96-1, c96-157, c97-132
Stern, J. (12): e89-173, e90-313, c91-204, e93-50, c93-13, c93-435, c94-164, c94-202, e96-245, e96-387, e97-27, c97-198
Golic, J. D. (12): e90-487, e91-160, e91-527, e92-113, e92-124, e92-472, e94-230, e95-248, e96-268, e97-226, e97-239, c97-499
Naor, M. (12): c88-319, c89-128, c92-139, c92-196, c92-215, c93-355, c93-480, e94-1, c94-234, c94-257, c97-90, c97-322
Knudsen, L. R. (11): c92-497, c92-566, e93-286, e94-410, e94-419, c95-274, e96-224, e96-237, c96-216, e97-1, c97-485
Peralta, R. (11): e84-379, e85-62, c85-87, e86-15, c86-200, c87-128, e89-75, c89-507, e90-11, c92-324, e96-131
Rogaway, P. (11): c88-37, c90-62, c91-392, c93-232, e94-92, c94-341, c95-15, c95-29, e96-399, c96-252, c97-470
Kurosawa, K. (11): e90-374, c90-339, e93-126, e93-248, e93-461, c94-140, e95-289, c95-410, e96-200, e97-409, e97-434
Yacobi, Y. (11): e87-117, c87-418, c87-429, c89-344, e90-222, c90-268, c90-639, e91-498, e92-208, e92-458, c95-197
Beth, T. (11): e82-1, e84-88, c86-302, e87-25, e88-77, e89-533, e90-189, c90-169, e91-316, e93-65, c94-318

Program Committee Service

Serving on a program committee is a time consuming task, and often results in little recognition from the community. The following people have served on at least five program committees:

Odlyzko, Andrew (10)
Rivest, Ronald (9)
Schnorr, Claus (7)
Massey, James L. (7)
Beth, Thomas (7)
Berson, Thomas (7)
Rueppel, Rainer (6)
Desmedt, Yvo (6)
Davies, Donald W. (6)
Damgård, Ivan (6)
Brickell, Ernest (6)
Simmons, Gustavus J. (5)
Quisquater, Jean-Jacques (5)
Okamoto, Tatsuaki (5)
Maurer, Ueli (5)
Ingemarsson, Ingemar (5)
Feigenbaum, Joan (5)
Diffie, Whitfield (5)
Denning, Dorothy (5)
Chaum, David (5)
Beker, Henry (5)

A complete list of program committees is included in this volume.

Kevin S. McCurley
IBM Almaden Research Center
September 1998