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. --