Abstract
Most public key cryptosystems used in practice are based on integer factorization
or discrete logarithms (in finite fields or elliptic curves). However, these systems suffer from
two potential drawbacks. First, they must use large keys to maintain security, resulting
in decreased efficiency. Second, if large enough quantum computers can be built, Shor’s
algorithm will render them completely insecure.
Multivariate public key cryptosystems (MPKC) are one possible alternative. MPKC
makes use of the fact that solving multivariate polynomial systems over a finite field is an
NP-complete problem, for which it is not known whether there is a polynomial algorithm
on quantum computers.
The main goal of this work is to show how to use new mathematical structures,
specifically polynomial identities from algebraic geometry, to construct new multivariate
public key cryptosystems. We begin with a basic overview of MPKC and present several
significant cryptosystems that have been proposed. We also examine in detail some of
the most powerful attacks against MPKCs. We propose a new framework for constructing
multivariate public key cryptosystems and consider several strategies for constructing poly-
nomial identities that can be utilized by the framework. In particular, we have discovered
several new families of polynomial identities. Finally, we propose our new cryptosystem
and give parameters for which it is secure against known attacks on MPKCs.
ii
