[3968] in cryptography@c2.net mail archive
Re: Matrix stuff...
daemon@ATHENA.MIT.EDU (Andrew Odlyzko)
Thu Jan 14 10:53:19 1999
Date: Thu, 14 Jan 1999 08:43:33 -0500 (EST)
From: Andrew Odlyzko <amo@research.att.com>
To: hal@mit.edu, rah@shipwright.com
Cc: cryptography@c2.net, dgs@live.co.uk, pcw@flyzone.com
Hal and Robert,
The only papers that I ever wrote that could conceivably be regarded
as concerned with matrix based public-key systems were on breaking such
schemes. Of course, Andrew Odzlyko (no relation, at least as far as
I know) may have done more, but if so, it remains well concealed from
the public eye.
On a more serious note, matrix approaches to public-key schemes are
usually classified with knapsack cryptosystems, and not RSA ones.
I can refer to two survey papers on variants of both RSA and knapsack
systems,
Cryptanalysis: A survey of recent results, E. F. Brickell and A. M. Odlyzko,
pp. 501-540 in "Contemporary Cryptology," G. J. Simmons (ed.), IEEE Press
(1991). Preliminary version in Proc. IEEE 76, 1988, pp. 578-593.
and
The rise and fall of knapsack cryptosystems, A. M. Odlyzko, pp. 75-88 in
"Cryptology and Computational Number Theory," C. Pomerance (ed.),
Am. Math. Soc., Proc. Symp. Appl. Math. #42 (1990).
Both are available online at
http://www.research.att.com/~amo/crypto.html
>From the very beginning, the big attraction of knapsack schemes compared
to RSA was their speed. Most operations in knapsacks were linear, and
so avoided the time-consuming modular exponentiation of RSA. Now of course
there had to be some nonlinearity, but the amounts put in turned out to be
insufficient. We'll have to wait to see the details of Sarah Flannery's
proposal to see if she has managed to overcome the problem.
Andrew
Robert Hettinga wrote:
Andrew,
Care to catch us all up on this?
Cheers,
Robert Hettinga
At 9:04 PM -0500 on 1/13/99, Hal Abelson wrote:
> >>>>> In reply to the message of Wed, 13 Jan 1999 19:55:55 -0500
> >>>>> from pcw :
>
> pcw> I vaguely remember reading several papers about matrix based
>public-key
> pcw> systems back in the early 1980's. They were in Cryptologia, I
>think. This
> pcw> idea doesn't sound too different, but my memory might be wrong.
>Can anyone
> pcw> else offer any insight?
>
> pcw> -Peter
>
>
> I believe that one of these is a paper by Andrew Odzlyko. Sorry, I
> don't have the reference here.
>
> == Hal
************************************************************************
Andrew Odlyzko amo@research.att.com
AT&T Labs - Research voice: 973-360-8410
http://www.research.att.com/~amo fax: 973-360-8178
************************************************************************
