Multivariate public key cryptosystems (MPKC) is a fast-developing new area in cryptography. In the past 10 years, MPKC schemes have increasingly been seen as a possible alternative to number theoretic-based cryptosystems such as RSA, as they are generally more efficient in terms of computational effort. As quantum computers are developed, MPKC will become a necessary alternative.
Multivariate Public Key Cryptosystems systematically presents the subject matter for a broad audience. Information security experts in industry can use the book as a guide for understanding what is needed to implement these cryptosystems for practical applications, and researchers in both computer science and mathematics will find this book a good starting point for exploring this new field. It is also suitable as a textbook for advanced-level students. Written more from a computational perspective, the authors provide the necessary mathematical theory behind MPKC; students with some previous exposure to abstract algebra will be well-prepared to read and understand the material.
In the last ten years, multivariate public key cryptosystems, or MPKCs for short, have increasingly been seen by some as a possible alternative to the public key cryptosystem RSA, which is widely in use today. The security of RSA depends on the difficulty of factoring large integers on a conventional computer. Shor's polynomial-time integer factorization algorithm for a quantum computer means that eventually such alternatives will be necessary, provided that we can build a quantum computer with enough quantum bits.
A result from complexity theory states that solving a set of randomly chosen nonlinear polynomial equations over a finite field is NP-hard. So far quantum computers have not yet been shown to be able to solve a set of multivariate polynomial equations efficiently, and the consensus is that quantum computers are unlikely to provide an advantage for this type of problem. Moreover, MPKC schemes are in general much more computationally efficient than number theoretic-based schemes. This has led to many new cryptographic schemes and constructions such as the Matsumoto-Imai cryptosystem (C* or MI), the Hidden Field Equations cryptosystem (HFE), the Oil-Vinegar signature scheme, the Tamed Transformation Method cryptosystem (TTM), and cryptosystems derived from internal perturbation. Some of these schemes seem to be very suitable for use in the ubiquitous computing devices with limited computing capacity, such as smart cards, wireless sensor networks, and active RFID tags. Indeed, Flash, also known as Sflash^^, a multivariate signature scheme, was recently accepted as a security standard for use in low-cost smart cards by the New European Schemes for Signatures, Integrity and Encryption (NESSIE): IST-1999-12324.