Multivariate Public Key Cryptography and Signature Schemes

Most communication takes place over insecure communication channels. Private (symmetric) key cryptography is the typical choice for exchanging secret messages since most private key cryptosystems are generally very fast and efficient. However, first the private key must be agreed upon by the two parties without anyone else learning this information. Public (asymmetric) key cryptography provides a solution, though it is typically much slower and less efficient than private key cryptography.

The most commonly used public key cryptosystem in use today is RSA, the security of which rests on the difficulty of factoring very large numbers. As factorization algorithms, software, and hardware become faster, more efficient, and cheaper, the security of these cryptosystems decreases. To regain an acceptable level of security, larger and larger numbers must be used, which in turn decreases speed and efficiency. Eventually quantum computers, for which there exists a polynomial-time integer factorization algorithm, will effectively end the security of cryptosystems based on integer factorization and other "hard" problems in number theory.

Alternatives to number theory-based public key cryptosystems include multivariate public key cryptosystems. The security of these cryptosystems rests on the difficulty of solving a system of nonlinear multivariate polynomial equations over a finite field. Since evaluating polynomials in a relatively small finite field is faster and more efficient than working with very large integers, multivariate public key cryptography holds particular promise for use in low-cost, low-resource devices such as smart cards and cell phones. Our group is particularly interested in the design and implementation aspects of multivariate public key cryptosystems and their related signature schemes, as well as the cryptanalysis of such schemes using algebraic algorithms such as modern Gröbner bases algorithms.

Gröbner Bases Algorithms

Let k be a field. Then with a suitable generalization for k[x₁, ..., x_n] of the usual division algorithm for k[x], one may think of computing a Gröbner basis for a system of non-linear multivariate polynomial equations as a generalization of Gaussian row-reduction. Thus modern Gröbner bases algorithms such as Faugère's versions F₄ and F₅ are very useful for solving general systems of multivariate polynomial equations. We are interested in the theoretical computational complexity (time/number-of-steps and memory requirements) analysis and possible improvements of these algorithms in the general case. We are particularly interested in the computational complexity of Gröbner bases algorithms applied to systems of equations that arise from multivariate public key cryptosystems and signature schemes.