Solving systems of multivariate polynomials modulo 2^32

[Danilo Gligoroski]

Danilo Gligoroski writes:
>[...] solve a system of 3 polynomials of order 3
>with 3 variables x1, x2 and x3 in the set Z_{2^32}
and
>coeficients also in Z_{2^32} [...]

David Wagner wrote:
>Here is a trick that should solve these kinds of
>equations extremely quickly.  First, you solve the
>system of equations modulo 2.  Then, for each mod-2
>solution, you try to extend it to a solution modulo
4.  >Then, for each mod-4 solution, you extend it to a
>solution modulo 8.  And so on. This is sometimes
known >under the name "Hensel lifting".

>Here's an example.  
>[...]


Thanks David, 

In the example you gave, the coefficients are from
Z_{2}. If they are from Z_{2^32} the situation is
similar but not the same (a little bit more
complicated). Does anybody examined how does the
complexity of the Hensel lifting goes whit the 
increasment of the degree and dencity of the
mutivariate polynomials Z_{2^n}[x1,x2,x3]?

For example if we have 3 multivariate polynomials
P1[x1,x2,x3], P2[x1,x2,x3] and P3[x1,x2,x3]
with 3 variables x1, x2 and x3 but the degrees of the
polynomials are high (say 32) and the number of terms
they have is also big (for example 833, 2825 and 4708)
and all their coeficients are from Z_{2^32}, what
would be the workfactor to find the solutions?
For example Mathematica's function
Reduce[...,{x1,x2,x3},Modulus->2^32] can not solve the
problem (as opposite of the situation when the degree
of P1, P2 and P3 is small. )  

I suppose that if we work with m variables, high
degree of the polynomials in Z_{2^n}[x_1,x_2,...x_m]
and those polynomials are dense - then he number of
candidates from lift to lift in the Hensel lifting is
encreasing exponentially at least for the first n/2
lifts. 
However, I couldn't find any mathematical prove in the
literature for this. 
I found many interesting papers that deals with Hensel
lifting and applications in cryptography, and among
others I found these:
1. The Hardness of Hensel Lifting: The Case of RSA and
Discrete Logarithm (2002)
Citeseer:
http://citeseer.ist.psu.edu/catalano02hardness.html
2. An Approach to Hensel's Lemma (2001)
Citeseer:
http://citeseer.ist.psu.edu/mcguire01approach.html
3. Cryptanalysis of an Algebraic Privacy Homomorphism
(2003)
Citeseer: http://citeseer.ist.psu.edu/677289.html

But the question that bothers me is not addressed
there.

Best regards,
Danilo Gligoroski


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com