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
Paulo Barreto (pbarreto@nw.com.br)
Fri, 01 Jan 1999 18:15:31 -0200
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