From daemon@Sunburn.Stanford.EDU Thu May 6 14:34:13 1993 Date: Thu, 6 May 93 14:18:26 -0700 From: Daphne Koller <daphne@Theory.Stanford.EDU> To: stc@Theory.Stanford.EDU Subject: STANFORD THEORY COLLOQUIUM

S T A N F O R D T H E O R Y C O L L O Q U I U M =====================================================

The Stanford Computer Science Department is pleased to announce the eighth Stanford Theory Colloquium this Thursday, May 13.

Polynomials and Cryptography - Some Recent Results

Professor Adi Shamir Weizmann Institute of Science

The talk will take place 4:15 -- 5:45 p.m. in Jordan 041.

A RECEPTION in honor of the speaker will be held in the third floor lounge of MJH around 3:45. Everyone is welcome.

------------------------------------------------------------------- | Professor Adi Shamir is a coinventor of the RSA public key | | cryptographic scheme and of several other key management and | | signature schemes. He was involved in the cryptanalytic attack | | on the knapsack scheme, and more recently he developed (with E. | | Biham) the new technique of differential cryptanalysis and | | applied it to the Data Encryption Standard. | -------------------------------------------------------------------

-----------------------------------------------------------------------------

Polynomials and Cryptography - Some Recent Results

Professor Adi Shamir Weizmann Institute of Science

Mappings defined by polynomials modulo n=pq are a fundamental tool in modern cryptography. However, the inversion of such mappings usually requires the extraction of roots or the evaluation of high degree polynomials, which is quite slow. This talk will consist of two parts. In the first part, we give an introduction to some basic cryptographic techniques. The second part will describe some new results in the area. We consider the class of birational permutations f, in which both f and f^-1 are low degree multivariate rational functions mod n. We describe new families of birational permutations, and how to turn them into new cryptographic schemes which are much faster than previously known schemes. In addition, we consider the general problems of factoring multivariate polynomials mod n and solving systems of polynomial equations mod n, and develop new techniques for proving the hardness of randomly chosen instances of such problems.

The talk will be self contained and accessible to a wide audience. +----------------------------------------------------------------------------+