×

Multivariate public key cryptosystems. (English) Zbl 1105.94006

Advances in Information Security 25. New York, NY: Springer (ISBN 0-387-32229-9/hbk). xviii, 260 p. (2006).
This book consists of eight chapters plus a five-page appendix on basic finite field theory. The first chapter is an overview largely concentrating on Multivariate Public Key Cryptosystems (MPKC)s which have been viewed as possible alternatives to PKCs such as RSA.
Essentially an MPKC is a cryptosystem in which the public key is a finite set of multivariate polynomials \(f_j\in\mathbb{F}[x_1,\dots,x_n]\) where \(\mathbb{F}\) is a finite field. In this scenario, our usual cast of cryptographic characters, Alice and Bob, communicate as follows. If Alice wishes to send a message \((m_1,\dots,m_n)\in\mathbb{F}^n\) to Bob, she obtains Bob’s public key \(f_j\) and computes \(c_j=f_j(m_1,\dots,m_n)\) for \(j=1,\dots,\ell\) and sends ciphertext \((c_1,\dots,c_\ell)\) to him. Bob’s private key involves information about \(f_j\) which is a means of unlocking the one-way system \(f_j(m_1^\prime,\dots,m_n^\prime)=c_j\) for \(j=1,\dots,\ell\) without which it is computationally infeasible to solve it.
Reasons for the MPKC’s role as a possible alternative to standard PKCs such as RSA include the fact that the former are much more computationally efficient than the latter, whose security is based upon the presumed difficulty of factoring large integers – the Integer Factoring Problem (IFP). Since the (general) problem of solving a set of multivariate polynomial equations over a finite field is (provably) an NP-hard problem, quantum computers could not be expected to efficiently find a solution set. Yet quantum computers would solve the IFP, making such PKCs as RSA obsolete, but not MPKCs.
Chapter two delves into Matsumoto-Imai Cryptosystems (MIC)s, one of the first successful attempts to build an MPKC. The basic idea for this type of cryptosystem is to utilize a field extension \(K\) of degree \(n\) over a finite field \(\mathbb F\) (considered as an \(n\)-dimensional vector space over \(\mathbb{F}\)) and look for invertible maps on \(K\) which are then transformed into invertible maps over \(\mathbb {F}^n\). Attacks on MIC and its variants are considered and complexity issues discussed.
Chapter three is dedicated to the family of three signature schemes called Oil-Vinegar, which may be seen as arising from attacks on MICs. Chapter four investigates a mechanism for making the notion of an MPKC more secure using what is called a Hidden Field Equation (HFE) invented in 1996. Chapter five continues the investigation of extending MICs by looking at internal perturbations which were motivated by a desire to resist certain attacks without sacrificing efficiency.
Chapter six has its origins in algebraic geometry since the triangular schemes which it delineates, are motivated by the difficulty of decomposing a composition of invertible nonlinear polynomials maps – a problem closely related to the well-known Jacobian conjecture. Chapter six is the longest and most involved section, which collates much of what has been previously discussed. Chapter seven continues the foray into algebraic geometry by considering direct attacks on MPKCs. Typically, attacks employ numerical methods which are often based on ideas of Newton since it suffices to find approximate solutions to a set of equations. However, when the solutions of the equations are considered over a finite field, numerical methods are not applicable and exact solutions are required so algebraic geometry comes into play.
The concluding chapter eight looks to the future of MPKC research. This ten-page chapter summarizes and gathers results from the literature on the construction of MPKCs, their security, practical applications, and a brief look at underlying mechanisms.
Although the authors state, in their introduction, that this could be used as a textbook “suitable for beginning graduate students in mathematics or computer science”, it is hampered by the fact that there are no exercises, no theorems or proofs, indeed no rigorous mathematical development. Thus, especially given the very specialized topic matter, it would not be suitable for students in mathematics at any level. The authors admit, in the introduction, that “this book has been written from the computational perspective”, and this is evident. As a textbook, however, even in computer science, it might be suitable as a reference for specific aspects of an advanced course in cryptology with MPKCs as one of the topics. Certainly anyone interested in this area of cryptology would benefit from having this book as part of their library.

MSC:

94A60 Cryptography
94-02 Research exposition (monographs, survey articles) pertaining to information and communication theory
94A62 Authentication, digital signatures and secret sharing
14G50 Applications to coding theory and cryptography of arithmetic geometry
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI