From: fnerd@smds.com (FutureNerd Steve Witham)
Date: Mon, 3 May 93 16:44:15 PDT
To: cypherpunks@toad.com
Subject: Shamir papers in postscript
Message-ID: <9305032323.AA06924@smds.com>
MIME-Version: 1.0
Content-Type: text/plain


I have the postscript versions of the papers of the two Adi Shamir
talks I summarized last week.  Shamir gives permission to distribute
them freely.  If anyone's interested, please mail 
to me, and depending on how many ask for them,
I'll either mail directly or post to the list.

-fnerd

Titles:  ``On The Generation of Multivariate Polynomials Which Are Hard
          To Factor''
	                            and
           
           ``Cryptographic Applications of Birational Permutations''         

			     by Adi Shamir
		          Weizmann Institute

                           FIRST ABSTRACT: 
In this talk we consider the difficulty of factoring multivariate
polynomials F(x,y,z,...) modulo n. We consider in particular the case
in which F is the product of two randomly chosen polynomials P and Q
with algebraically specified coefficients, and n is the product of two
randomly chosen primes p and q. The main result of this talk is that
(with one trivial exception), the problem of factoring F is at least
as hard as the factorization of n whenever P and Q are chosen from the
same sample space, regardless of what may be known about its form.

                           SECOND ABSTRACT:
Many public key cryptographic schemes (such as cubic RSA) are based
on low degree polynomials whose inverses are high degree polynomials.
These functions are very easy to compute, but time consuming to invert
even by their legitimate users. To make such schemes more efficient,
we consider in this talk the class of birational permutations f over
k-tuples of numbers, in which both f and f^-1 are low degree
multivariate rational functions. We develop new families of birational
permutations, and describe how to use them in new cryptographic
schemes which are faster than the known schemes.

--