Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:01
Douglas Hoover (doug@arcot.com)
Mon, 04 Jan 1999 11:35:42 -0800
The Kozen and Landau work cited below appears to apply only to polynomials of
one variable. The Tame Transformation Method uses uses multivariate polynomials
(usually with a rather large number of variables), which I thought were much
less tractable. Can anyone comment on whether Kozen-Landau really applies to
TTM?
best,
doug
Paulo Barreto wrote:
> At 10:21 1999.01.01 -0200, I wrote:
>
> >At 00:29 1999.01.01 -0500, Lewis McCarthy wrote:
> >
> >>Regarding the use of polynomial composition in the www.usdsi.com
> >>system, see http://www.cs.umass.edu/~landau/alg_alg.html for work
> >>by Kozen and Landau on fast polynomial decomposition. Thee's an
> >>online copy of the paper, I` believe.
> >
> >Yes, but it is stated there that "polynomials could be factored over
> >algebraic number fields in time polynomial in the size of the polynomial
> >and the size of the field extension.", and the polynomial g^-1 in the TTM
> >system can be quite large -- 2^(2^(m-2)) for an underlying Galois field
> >GF(2^m), if I computed it correctly.
>
> Oops, I must've been sleepy after the reveillon when I wrote that, sorry :-)
>
> Obviously, polynomial decomposition is to be applied to g, not g^-1, hence
> taking polynomial (actually quadratic, thus quite manageable) time. The
> very reference to the Kozen-Landau algorithm above states that "the
> existence of a fast decomposition algorithm makes it unlikely that
> polynomial composition could ever form part of a public-key type
> cryptosystem".
>
> So much for the Tame Transformation Method. All evidence indicates it's
> very, very weak (whether it should be included in the "snake oil" list I'll
> let for Bruce to decide in his forthcoming article).
>
> Paulo.
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:01