Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Multivariate public key cryptosystems (Advances in Information Security)
Ding J., Gower J., Schmidt D., Springer-Verlag New York, Inc., Secaucus, NJ, 2006. 260 pp. Type: Book (9780387322292)
Date Reviewed: Mar 2 2007

Multivariate public key cryptosystems (MPKC), developed in the last ten years, have become a potential alternative to number theoretic-based cryptography (in this book, all comparisons regarding security and encryption complexity use the RSA cryptosystem). Their complexity is based on the fact that solving a set of randomly chosen nonlinear polynomial equations over a finite field is a nondeterministic polynomial time (NP) hard problem. Some of the cryptographic schemes in this area seem to be suitable for use in ubiquitous devices with limited computing capacity, such as smart cards or wireless sensor networks. One of them, Sflash-v2, a multivariate signature scheme (a variant of Matsumoto-Imai), was accepted by New European Schemes for Signatures, Integrity, and Encryption (NESSIE) as a security standard for use in low-cost smart cards (IST-1999-12324). Research on MPKCs has undergone rapid development, providing many interesting results, and offering new ideas in pure mathematical problems, such as solving systems of multivariate polynomial equations over a finite field.

The book begins with an overview of the basic ideas and early development of multivariate public key cryptography and signature schemes. The next few chapters present the main families of multivariate schemes: the Matsumoto-Imai cryptosystem and its variants (chapter 2); oil-vinegar signature schemes and their classification (chapter 3); the hidden field equations cryptosystem and its variants, including signature schemes (chapter 4); and the tame transformation method (TTM) cryptosystem with tame transformation signatures (TTS), a variant proposed as a signature (chapter 6). Generally speaking, all existing multivariate cryptosystems are divided into two classes: bipolar and mixed cryptosystems (the isomorphism and polynomial authentication scheme is an exception). The concept of perturbation, the means by which the security of various schemes can be improved without much cost in terms of efficiency and cryptanalysis of previous cryptosystems, forms the content of chapter 5.

As a remark, the Matsumoto-Imai cryptosystem was submitted as a candidate for security standards to the Japanese government, but before the final selection it was broken by Jacques Patarin (1995). Based on this attack (the linearization equation attack), Patarin constructed the oil-vinegar signature scheme (the balanced variant).

Each family of cryptographic schemes defined in chapters 2, 3, 4, and 6 is introduced in terms of the origin of the mathematical idea behind its construction, followed by generalizations and related attacks specific to that family. Generic attacks that can be applied to any MPKC (in particular, methods for solving systems of multivariate polynomial equations over a finite field) are then addressed (chapter 7). The last part, chapter 8, offers a detailed discussion about the future of MPKCs. A supplementary appendix collects results from finite field theory, needed in the main text of the book.

This work can be used by industry experts as a guide for understanding the basic mathematical structures needed to implement these cryptosystems for practical applications, and as a starting point for researchers in both computer science and the mathematical theory of polynomials over finite fields. The book is mainly based on the lecture notes for a graduate course at the University of Cincinnati, taught by Jintai Ding during the 2004-2005 and 2005-2006 academic years.

Reviewer:  Adrian Atanasiu Review #: CR133996 (0804-0327)
Bookmark and Share
  Reviewer Selected
 
 
Public Key Cryptosystems (E.3 ... )
 
 
Standards (E.3 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Public Key Cryptosystems": Date
Direct demonstration of the power to break public-key cryptosystems
Koyama K.  Advances in cryptology (, Sydney, Australia, Jan 8-11, 1990)211990. Type: Proceedings
Sep 1 1991
Public-key cryptography
Salomaa A., Springer-Verlag New York, Inc., New York, NY, 1990. Type: Book (9783540528319)
Feb 1 1992
Computation of discrete logarithms in prime fields
LaMacchia B., Odlyzko A. Designs, Codes and Cryptography 1(1): 47-62, 1991. Type: Article
Apr 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy