Multivariate public key cryptosystems

DOI10.1007/978-0-387-36946-4MaRDI QIDQ2509132zbMATH OpenOpenAlexFDO

Authors Jintai Ding, Jason E. Gower, Dieter Schmidt

Publication date 18 October 2006

Published in Advances in Information Security (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-0-387-36946-4

cryptology multivariate polynomials public-key

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

Review text

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 \textit{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 \textit{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 \textit{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 \textit{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 \textit{Hidden Field Equation} (HFE) invented in 1996. Chapter five continues the investigation of extending MICs by looking at \textit{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 \textit{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 \textit{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.

Recommendations

Cited in

(57)

This page was built for publication: Multivariate public key cryptosystems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2509132)