Solving systems of multivariate polynomials modulo 2^32

Danilo Gligoroski gligoroski at
Mon Aug 21 00:21:33 EDT 2006

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
>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.

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

More information about the cryptography mailing list