The book deals with algorithmic problems related to binary quadratic forms. It uniquely focuses on the algorithmic aspects of the theory. The book introduces the reader to important areas of number theory such as diophantine equations, reduction theory of quadratic forms, geometry of numbers and algebraic number theory. The book explains applications to cryptography and requires only basic mathematical knowledge. The author is a world leader in number theory.

Quantum computers will break today's most popular public-key cryptographic systems, including RSA, DSA, and ECDSA. This book introduces the reader to the next generation of cryptographic algorithms, the systems that resist quantum-computer attacks: in particular, post-quantum public-key encryption systems and post-quantum public-key signature systems.

Leading experts have joined forces for the first time to explain the state of the art in quantum computing, hash-based cryptography, code-based cryptography, lattice-based cryptography, and multivariate cryptography. Mathematical foundations and implementation issues are included.

This book is an essential resource for students and researchers who want to contribute to the field of post-quantum cryptography.

Cryptography is a key technology in electronic key systems. It is used to keep data secret, digitally sign documents, access control, and so forth. Users therefore should not only know how its techniques work, but they must also be able to estimate their efficiency and security. Based on courses taught by the author, this book explains the basic methods of modern cryptography. It is written for readers with only basic mathematical knowledge who are interested in modern cryptographic algorithms and their mathematical foundation. Several exercises are included following each chapter. This revised and extended edition includes new material on the AES encryption algorithm, the SHA-1 Hash algorithm, on secret sharing, as well as updates in the chapters on factoring and discrete logarithms.

Johannes A. Buchmann is Professor of Computer Science and Mathematics at the Technical University of Darmstadt, and an Associate Editor of the Journal of Cryptology. In 1985, he received a Feodor Lynen Fellowship of the Alexander von Humboldt Foundation. He has also received the most prestigious award in science in Germany, the Leibniz Award of the German Science Foundation (Deutsche Forschungsgemeinschaft).

This book constitutes the refereed proceedings of the 11th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2019, held in Rabat, Morocco, in July 2019. The 22 papers presented in this book were carefully reviewed and selected from 53 submissions. The papers are organized in topical sections on protocols; post-quantum cryptography; zero-knowledge; lattice based cryptography; new schemes and analysis; block ciphers; side-channel attacks and countermeasures; signatures. AFRICACRYPT is a major scientific event that seeks to advance and promote the field of cryptology on the African continent. The conference has systematically drawn some excellent contributions to the field. The conference has always been organized in cooperation with the International Association for Cryptologic Research (IACR).

This book presents the first comprehensive overview of various verifiable computing techniques, which allow the computation of a function on outsourced data to be delegated to a server. It provides a brief description of all the approaches and highlights the properties each solution achieves. Further, it analyzes the level of security provided, how efficient the verification process is, who can act as a verifier and check the correctness of the result, which function class the verifiable computing scheme supports, and whether privacy with respect to t he input and/or output data is provided. On the basis of this analysis the authors then compare the different approaches and outline possible directions for future work. The book is of interest to anyone wanting to understand the state of the art of this research field.

Homomorphic signature schemes are an important primitive for many applications and since their introduction numerous solutions have been presented. Thus, in this work we provide the first exhaustive, complete, and up-to-date survey about the state of the art of homomorphic signature schemes. First, the general framework where homomorphic signatures are defined is described and it is shown how the currently available types of homomorphic signatures can then be derived from such a framework. In addition, this work also presents a description of each of the schemes presented so far together with the properties it provides. Furthermore, three use cases, electronic voting, smart grids, and electronic health records, where homomorphic signature schemes can be employed are described. For each of these applications the requirements that a homomorphic signature scheme should fulfill are defined and the suitable schemes already available are listed. This also highlights the shortcomings of current solutions. Thus, this work concludes with several ideas for future research in the direction of homomorphic signature schemes.

This book constitutes the refereed proceedings of the 15th International Conference on Practice and Theory in Public Key Cryptography, PKC 2012, held in Darmstadt, Germany, in May 2012. The 41 papers presented were carefully reviewed and selected from 188 submissions. The book also contains one invited talk. The papers are organized in the following topical sections: homomorphic encryption and LWE, signature schemes, code-based and multivariate crypto, public key encryption: special properties, identity-based encryption, public-key encryption: constructions, secure two-party and multi-party computations, key exchange and secure sessions, public-key encryption: relationships, DL, DDH, and more number theory, and beyond ordinary signature schemes.

Cryptography is a key technology in electronic security systems. Modern cryptograpic techniques have many uses, such as to digitally sign documents, for access control, to implement electronic money, and for copyright protection. Because of these important uses it is necessary that users be able to estimate the efficiency and security of cryptographic techniques. It is not sufficient for them to know only how the techniques work. This book is written for readers who want to learn about mod- ern cryptographic algorithms and their mathematical foundation but who do not have the necessary mathematical background. It is my goal to explain the basic techniques of modern cryptography, including the necessary mathematical results from linear algebra, algebra, number theory, and probability theory. I assume only basic mathematical knowledge. The book is based on courses in cryptography that I have been teaching at the Technical University, Darmstadt, since 1996. I thank all students who attended the courses and who read the manuscript carefully for their interest and support. In particular, I would like to thank Harald Baier, Gabi Barking, Manuel Breuning, Sa- fuat Hamdy, Birgit Henhapl, Michael Jacobson (who also corrected my English), Andreas Kottig, Markus Maurer, Andreas Meyer, Stefan v vi Preface Neis, Sachar Paulus, Thomas Pfahler, Marita Skrobic, Edlyn Thske, Patrick Theobald, and Ralf-Philipp Weinmann. I also thank the staff at Springer-Verlag, in particular Martin Peters, Agnes Herrmann, Claudia Kehl, Ina Lindemann, and Thrry Kornak, for their support in the preparation of this book.

The book deals with algorithmic problems related to binary quadratic forms. It uniquely focuses on the algorithmic aspects of the theory. The book introduces the reader to important areas of number theory such as diophantine equations, reduction theory of quadratic forms, geometry of numbers and algebraic number theory. The book explains applications to cryptography and requires only basic mathematical knowledge. The author is a world leader in number theory.

Quantum computers will break today's most popular public-key cryptographic systems, including RSA, DSA, and ECDSA. This book introduces the reader to the next generation of cryptographic algorithms, the systems that resist quantum-computer attacks: in particular, post-quantum public-key encryption systems and post-quantum public-key signature systems.

Leading experts have joined forces for the first time to explain the state of the art in quantum computing, hash-based cryptography, code-based cryptography, lattice-based cryptography, and multivariate cryptography. Mathematical foundations and implementation issues are included.

This book is an essential resource for students and researchers who want to contribute to the field of post-quantum cryptography.

Threedecadesagopublic-keycryptosystemsmadea revolutionarybreakthrough in cryptography. They have developed into an indispensable part of our m- ern communication system. In practical applications RSA, DSA, ECDSA, and similar public key cryptosystems are commonly used. Their security depends on assumptions about the di?culty of certain problems in number theory, such as the Integer Prime Factorization Problem or the Discrete Logarithm Problem. However, in 1994 Peter Shor showed that quantum computers could break any public-key cryptosystembased on these hard number theory problems. This means that if a reasonably powerful quantum computer could be built, it would put essentially all modern communication into peril. In 2001, Isaac Chuang and NeilGershenfeldimplemented Shor'salgorithmona7-qubitquantumcomputer. In 2007 a 16-qubit quantum computer was demonstrated by a start-up company with the prediction that a 512-qubit or even a 1024-qubit quantum computer would become available in 2008. Some physicists predicted that within the next 10 to 20 years quantum computers will be built that are su?ciently powerful to implement Shor's ideas and to break all existing public key schemes. Thus we need to look ahead to a future of quantum computers, and we need to prepare the cryptographic world for that future.

Leading researchers in the field of coding theory and cryptography present their newest findings, published here for the first time following a presentation at the International Conference on Coding Theory, Cryptography and Related Areas. The authors include Tom Hoeholdt, Henning Stichtenoth, and Horacio Tapia-Recillas.

This book presents refereed proceedings of the First International Conference on Algebra, Codes and Cryptology, A2C 2019, held in Dakar, Senegal, in December 2019. The 14 full papers were carefully reviewed and selected from 35 submissions. The papers are organized in topical sections on non-associative and non-commutative algebra; code, cryptology and information security.

Dieses Kryptographiebuch ist geschrieben fur Studierende der Mathematik, Informatik, Physik, Elektrotechnik oder andere Leser mit mathematischer Grundbildung und wurde in vielen Vorlesungen erfolgreich eingesetzt. Es behandelt die aktuellen Techniken der modernen Kryptographie, zum Beispiel Verschlusselung und digitale Signaturen. Das Buch vermittelt auf elementare Weise alle mathematischen Grundlagen, die zu einem prazisen Verstandnis der Kryptographie noetig sind, mit vielen Beispielen und UEbungen. Die Leserinnen und Leser erhalten ein fundiertes Verstandnis der modernen Kryptographie und werden in die Lage versetzt Forschungsliteratur zur Kryptographie zu verstehen.

Dieser Band erscheint aus Anlafi des sechzigsten Geburtstags von Gunter Hotz. Er enthiilt Arbeiten seiner Schuler, Freunde und Kollegen. Gunter Hotz ist seit 1969 Professor fur Numerische Mathematik und Informatik an der Universitiit des Saarlandes. Er hat am Aufbau des Fachbereichs Informatik der Universitiit des Saarlandes groBen Anteil, und er hat die Entwicklung der Infor matik in Deutschland wesentlich mitgepriigt. Dies wird durch die Vielfalt der hier erscheinenden Arbeiten eindrucksvoll belegt. Mit den Beitriigen im vorliegenden Buch mochten die Autoren bei Herrn Hotz einen Teil des Dankes, zu dem sie aus unterschiedlichen Grunden verpflichtet sind, abstatten. Saarbrucken, im November 1991 J. Buchmann, H. Ganzinger, W. J. Paul Inhaltsverzeichnis Abolhassan, Drefenstedt, Keller, Paul, Scheerer: On the Physical Design of PRAMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Bernd Becker: Synthesis for Testability: Binary Decision Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Eberhard Bertsch: Ahnlichkeit von Grammatiken - Ansatze und Erfahrungen . . . . . . . . . . . . . . . . . . . . 41 Hans-Peter Blatt: Verteilung der Nullstellen von Polynomen auf JordanbOgen . . . . . . . . . . . . . . . . . . . . 55 Johannes Buchmann, Stephan Diillmann: Distributed Class Group Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Volker Claus: Complexity Measures on Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 Martin Dietzfelbinger, Friedheim Meyer auf der Heide: Dynamic Hashing in Real Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Ferdinand, Seidl, Wilhelm: Baumautomaten zur Codeselektion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Michael J. Fischer, Sophia A. Paleologou: Decision Making in the Presence of Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 B. Halstenberg, R. Reischuk: Uber den Nutzen von Orakelfragen bei nichtdeterministischen Kommunikationsprotokollen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 Uwe Hinsberger, Reiner Kalla: Performance Optimization of Combinational Circuits . . . . . . . . . . . . . . . . . . . . . . . . . 185 Thomas Kretschmer: An Algebraic Characterization of Context-Free Languages . . . . . . . . . . . . . . . . . . . . 209 Juraj Hromkovi, Burkhard Monien: The Bisection Problem for Graphs of Degree 4 (Configuring Transputer Systems) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ."