[37364] in cryptography@c2.net mail archive
Re: Solving systems of multivariate polynomials modulo 2^32
daemon@ATHENA.MIT.EDU (Danilo Gligoroski)
Mon Aug 21 09:53:27 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Sun, 20 Aug 2006 21:21:33 -0700 (PDT)
From: Danilo Gligoroski <gligoroski@yahoo.com>
Reply-To: danilo@pmf.ukim.edu.mk
To: cryptography@metzdowd.com
Ariel wrote:
>A root that you lift using Hensel to Z_{p^n} looks
>like a_0 + a_1 p + a_2 p2 +... +a_n p^n where a_i is
>in Z_p. What will happen in your case
>is that at first, in (Z_2)3 you can have at most 8
>roots, once you lift to Z_{22} some of these roots
can
>be "split" into more roots (if p=2
>and n=3, then at most 8 roots). A root at step i-1
>will split at step i depending on whether your
>approximation at the step i-1 annhilates the
>jacobian determinant of P1,P2,P3.
>
>Good luck.
>
>Cheers,
>Ariel
Ariel you are right.
David Wagner had also a similar opinion (he sent me a
private message for this matter). Actually I had made
a small experiment to test his (and your claims), and
for the values of the solutions over Z_{2^i}, i=1,20
from lift to lift after i=3 the number of possible
solutions stays constant to 16 (not 8??!?!).
Anyway, this suggest one obvious thing: if a PK system
is built over Z_{2^x}[x_1,x_2,...,x_m] then the number
of variables m have to be at least 80 (or 128, or 196,
...) in order to eliminate the Hansel lifting as a
form of attack. But that is another story ...
Thank you.
Danilo Gligoroski
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
