From: fnerd@smds.com (FutureNerd Steve Witham)
Date: Mon, 26 Apr 93 15:17:49 PDT
To: cypherpunks@toad.com
Subject: Report on Adi Shamir talk
Message-ID: <9304262127.AA28339@smds.com>
MIME-Version: 1.0
Content-Type: text/plain


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)