A New Public-Key System with Signature and Master Key

Prof Tzuong-Tsieng Moh
Purdue University, Indiana

About the talk:
The classical public key systems rely on non-polynomial functions of one variable. Higher security and faster speed can be achieved by using polynomials of several variables. We will demonstrate this phenomenon in this talk.

Let m, n, r, s be positive integers. Let K be a finite field of 2^m elements. Let f_s,...,f₂, f₁ be s tame (equivalently, triangular) automorphisms, which are elementary and easily computable, of the (n+r)-dimensional affine space K^n+r. Let the composition automorphism be g=f_s...f₂f₁. The automorphism g and some of the f_i's will be hidden.

Let the restriction of g to the n dimensional subspace be g'=(h₁,...,h_n+r): Kⁿ--> K ^n+r. The field K and the polynomial map (h₁,..., h_n+r) will be announced as the public key.

Given a plaintext (x₁,...,x_n) in Kⁿ, let y_i=h_i(x₁,...,x_n), then the ciphertext will be (y₁,...,y_n+r).

Given tame automorphisms f_i and (y₁,...,y_n+r), it is easy to find f_i^-1(y₁,...,y_n+r). Therefore, the plaintext can be recovered by taking (x₁,...,x_n,0...0) =f₁^-1f₂^-1...f_s^-1( y₁,...,y_n+r). The private key will be the set of map {f₁^-1,...,f_s^-1}.

The security of the system rests in part on the difficulty of finding the map g from the partial information provided by the map g' and the factorization of the map g into a product (i.e., composition) of tame automorphisms f_i.

No mathematical background beyond high school is required.

Professor Moh has provided a paper version of his talk.

About the speaker:

Tzuong-Tsieng Moh is a mathematician working in the fields of Algebraic Geometry and Commutative Algebra. He had been affiliated with Purdue U, U of Minnesota, Princeton Institute of Advanced Study, Harvard U, MSRI (Berkeley) etc.. Lately, he finds that it is interesting to work on some real problems in the real world. In this talk he will present a fast new public-key system which is based on some elementary results of high dimensional affine spaces.

Contact information:

T. Moh
Department of Mathematics, Purdue U, W. Laf., IN 47906


765-494-1930

ttm@math.purdue.edu