Multivariate Public Key Cryptosystems

ISBN-13: 9781071609859 / Angielski / Twarda / 2020 / 253 str.

Jintai Ding; Albrecht Petzoldt; Dieter S. Schmidt

Recenzje

"The book is a well-assorted collection of cryptosystems based on the problem of solving non-linear systems of polynomial equations over finite fields ... . The book, in most of its contents, provides a sufficiently self-contained introduction to the design and the cryptanalysis of MPKCs and some of the chapters of the book can undoubtedly represent a useful resource for an advanced course in public-key cryptography." (Roberto Civino, zbMATH 1506.94001, 2023)

Spis treści

1 Introduction

References 

2 Multivariate Cryptography 

2.1 Multivariate Polynomials 

2.2 Construction Methods for MPKC’s

2.3 Underlying Problems

2.4 Security and Standard Attacks 

2.5 Advantages and Disadvantages 

References 

3 The Matsumoto-Imai Cryptosystem 

3.1 The Basic Matsumoto-Imai Cryptosystem

3.2 The Linearization Equations Attack

3.3 Encryption Schemes Based on MI

3.4 Signature Schemes Based on MI 

References 

4 Hidden Field Equations 

4.1 The Basic HFE Cryptosystem 

4.2 Attacks on HFE 

4.3 Encryption Schemes Based on HFE

4.4 Signature Schemes Based on HFE 

References

5 Oil and Vinegar 

5.1 The Oil and Vinegar Signature Scheme

5.2 Cryptanalysis of Balanced Oil and Vinegar and UOV

5.3 Other Attacks on UOV 

5.4 The Rainbow Signature Scheme

5.5 Attacks on Rainbow 

5.6 Reducing the Public Key Size

5.7 Efficient Key Generation of Rainbow 

References 

6 MQDSS 

6.1 The MQ Based Identification Scheme 

6.2 The Fiat-Shamir Transformation 

6.3 The MQDSS Signature Scheme 

References

7 The SimpleMatrix Encryption Scheme 

7.1 The Basic SimpleMatrix Encryption Scheme 

7.2 The Rectangular SimpleMatrix Encryption Scheme 

7.3 Attacks on SimpleMatrix 

References 

8 Solving Polynomial Systems 

8.1 History of Solving Polynomial Equations 

8.2 Solving Univariate Polynomials of High Degree 

8.3 The XL-Algorithm

8.4 Gr¨obner Bases 

8.5 Buchberger’s Algorithm and F4 

8.6 Estimating the Degree of Regularity

8.7 Solving Over- and Underdetermined Systems 

References

Index 

List of Toy Examples 

Software 

O autorze

Jintai Ding is a Charles Phelps Taft professor at the Department of Mathematical Sciences at the University of Cincinnati. He received B.A. from Xian Jiao tong University in 1988, M.A. from the University of Science and Technology of China in 1990 and PhD from Yale in 1995. He was a lecturer at the Research Institute of Mathematical Sciences of Kyoto University from 1995 to 1998. He has been at the University of Cincinnati since 1998. In 2006-2007, he was a visiting professor and Alexander von Humboldt Fellow at TU Darmstadt. He received the Zhong Jia Qing Prize from the Chinese Mathematical Society in 1990 for his Master Thesis on proving a conjecture by C. L. Siegel. His research was originally in quantum affine algebras and its representation theory, where he was credited for the invention of the Ding-Iohara-Miki algebra.  His current interest is in post-quantum cryptography, in particular, multivariate cryptography, latticed-based cryptography and quantum-proof blockchain. He was a co-chair of the 2nd, 10th and 11th international conference on post-quantum cryptography. He and his colleagues developed the Rainbow signature, the GUI HFEv- signature, the Simple Matrix encryption and the LWE-based key exchange schemes. Rainbow is a second round candidate for the NIST post-quantum standardization process. He and his students completely broke a NIST second round post-quantum signature candidate LUOV. 

Albrecht Petzoldt received a diploma in mathematics in 2009 from FAU Erlangen-Nuremberg and a PhD in Computer Science in 2013 from Technische Universität Darmstadt / Germany. Since then he worked for several academic and non academic institutions, including Kyushu University / Japan and the National Institute of Standards and Technology (NIST) / USA. Currently, he works as a lecturer at FAU Erlangen-Nuremberg / Germany.

His main research interests are located in the field of multivariate cryptography, and in particular in the development and improvement of multivariate signature schemes such as UOV and Rainbow. 

In 1966 Dieter Schmidt received his “Diplom in Mathematik” from the Technische Hochschule Stuttgart, Germany. He then went to the University of Minnesota, where he received his PhD in Mathematics in 1970. During that time he also worked for Univac and gained valuable experience in computer programming. 

After an initial appointment at the University of Maryland, he accepted a position in the Department of Mathematical Sciences at the University of Cincinnati. The department started offering courses in Computer Science in the late 1970's. It was natural for him to teach some of these courses and then to join the Department of Computer Science when it was formed in 1984. 

In 2002 he started his collaboration with Jintai Ding. He offered his expertise in programming in order to create the software for cryptographic schemes or the code to attack them. Although Dieter Schmidt retired from the University of Cincinnati in 2011, he has continued the collaboration with Jintai Ding.

Blurb

This book discusses the current research concerning public key cryptosystems. It begins with an introduction to the basic concepts of multivariate cryptography and the history of this field. The authors provide a detailed description and security analysis of the most important multivariate public key schemes, including the four multivariate signature schemes participating as second round candidates in the NIST standardization process for post-quantum cryptosystems. Furthermore, this book covers the Simple Matrix encryption scheme, which is currently the most promising multivariate public key encryption scheme. This book also covers the current state of security analysis methods for Multivariate Public Key Cryptosystems including the algorithms and theory of solving systems of multivariate polynomial equations over finite fields. Through the book’s website, interested readers can find source code to the algorithms handled in this book.

In 1994, Dr. Peter Shor from Bell Laboratories proposed a quantum algorithm solving the Integer Factorization and the Discrete Logarithm problem in polynomial time, thus making all of the currently used public key cryptosystems, such as RSA and ECC insecure. Therefore, there is an urgent need for alternative public key schemes which are resistant against quantum computer attacks. Researchers worldwide, as well as companies and governmental organizations have put a tremendous effort into the development of post-quantum public key cryptosystems to meet this challenge. One of the most promising candidates for this are Multivariate Public Key Cryptosystems (MPKCs). The public key of an MPKC is a set of multivariate polynomials over a small finite field. Especially for digital signatures, numerous well-studied multivariate schemes offering very short signatures and high efficiency exist. The fact that these schemes work over small finite fields, makes them suitable not only for interconnected computer systems, but also for small devices with limited resources, which are used in ubiquitous computing.

This book gives a systematic introduction into the field of Multivariate Public Key Cryptosystems (MPKC), and presents the most promising multivariate schemes for digital signatures and encryption. Although, this book was written more from a computational perspective, the authors try to provide the necessary mathematical background. Therefore, this book is suitable for a broad audience. This would include  researchers working in either computer science or mathematics interested in this exciting new field, or as a secondary textbook for a course in MPKC suitable for beginning graduate students in mathematics or computer science. Information security experts in industry, computer scientists and mathematicians would also find  this book valuable as a guide for understanding the basic mathematical structures necessary to implement multivariate cryptosystems for practical applications.