1.  The first sample project explores Hidden Field Equations.  In 1996 Patarin  announced the Hidden Field Equation (HFE) public key cryptosystem. HFE is based upon the “Big Field” method.  Here is a brief version of the “Big Field” method.  Let k be a finite field of q elements, and let K be an extension of k of degree n; i.e., where  is an irreducible polynomial of degree n.  K as a vector space is isomorphic to.  The isomorphism  is given by

.

Let  be a polynomial map over K; is defined by

where F is a polynomial of degree less than or equal to a fixed parameter d and  are randomly chosen elements of K.

Because K can be identified with an n-dimensional k-vector space, we can construct a mapping  over

where  and  are two randomly chosen affine maps over, and  stands for composition.

If we denote an element in  by  then

Because the Frobenious mappings  are linear over, each of the component polynomials  turns out to be of total degree two.

The collection of component polynomials  is the public key of the HFE scheme.

Plaintext is an element in, say.  Ciphertext is  -- another element in.

To decrypt a message, it is thought to be necessary to invert and, hence, know the individual components of.  These components are the private key.  In particular to decrypt messages it is necessary to invert F; it is necessary to be able to solve  for a given element  of K.  This inversion can be done using Berlekamp’s algorithm provided d is small; if d is sufficiently large, decryption will not work.  However, when d is small, a method using a Gröbner basis method can break HFE.

Patarin claims that if the coefficients of F are randomly selected, then, on average, F is a one-to-one map.  The first question to be answered is: is this true?  If the claim is false, the second question would be: what is the ratio of the size of the image space to the entire space and does this depend on d (and if so, how)?  The final question would be: for a random quadratic map from  to, what is the ratio of the image space to the entire space?

2.  The second sample project explores the MinRank problem:  Assume that we have a set of  matrices ; we want to find the matrix  such that B is of  nonzero minimum rank.  An efficient solution of the MinRank problem would break several multivariate public key cryptosystems.  If the minimum rank is n – 1 and there are n nondegenerate matrices, this is an NP-hard problem.  For small minimum rank there are several solutions to this problem, but no analysis of which solution is best given specific conditions has been done.  Participants could explore solutions of the MinRank problem by doing computer experiments that could lead to conjectures.

3.  The third sample project explores algebraic cryptanalysis.  Algebraic cryptanalysis is a new tool that, in general terms, attempts to view cryptosystems as (probably huge) systems of multivariate polynomial equations whose solutions might correspond to the secret key or to a decryption.  Algebraic cryptanalysis has been used to attack, for example, the Advanced Encryption Standard (AES) and various stream ciphers.  It generalizes techniques that have been used for many years to attack stream ciphers that are based upon linear feedback shift registers.  Participants will be taught basic methods of algebraic cryptanalysis and will be asked to attack simplified versions of either a block cipher or a stream cipher or NTRU (a non-number theoretic public key cryptosystem) by transforming their attack into a problem involving a system of multivariate polynomial equations.