Last Friday, the 23rd, Adi Shamir (the S of RSA) gave a talk at MIT about some recent crypto results of his. (He was introduced by Ron Rivest, the R of RSA.) Shamir is in the country to give a talk about the history of crypto, in Washington DC, I think. It was actually two related talks, one on each of two papers of his: "On the Generation of Multivariate Polynomials which are Hard to Factor" and "Efficient Signature Schemes Based on Birational Permutations" Any misrepresentations and misunderstandings here are mine. The first paper is about factoring polynomials that are products of two polynomials, F = PQ where all these polynomials are on numbers that are mod the product of two primes. n = pq There are a lot of cases where F is easy to factor, and sometimes the easy cases seem to be only slightly different from the hard cases, but Shamir has found a large, easy-to-specify class of forms of (P, Q) where factoring their product is as hard as factoring n (the notorious hard problem that's the basis for the supposed strength of RSA). The second paper is about looking for public key crypto methods that are as strong as RSA but don't require such large amounts of computing on one end. In regular RSA, for instance, the number of multiplications for decrypting (for the legitimate key owner) goes up with key size, and so does the difficulty of multiplication. Shamir has found a scheme that takes about 20 multiplies on each side, period. However, it would be easily breakable as a crypto scheme, so he shows a variation that doesn't give as much info to an attacker, but works as a signature scheme. It *looks* secure to him and others he's shown it to, but it isn't proven as hard as factoring big numbers. The tie between the two papers is that the keys used in the scheme in the second paper are polynomials of the form discussed in the first paper. --fnerd@smds.com (FutureNerd Steve Witham)