Solving systems of multivariate polynomials modulo 2^32

[Danilo Gligoroski]

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 at metzdowd.com