Solving systems of multivariate polynomials modulo 2^32

[Ariel Waissbein]

Hi Danilo,

the information you can extract from the system relies largely in the
hypoteses. If you don't bound the degree then the polynomials can define
the zero function, while they are not the zero polynomial. Say, the
univariate 2^{31}X(X+1) defines the zero function in Z_{232}. Also
notice that it is the zero polynomial in Z_{2^i} for i<32.

I don't know of any bound that will work in Z_{232}. Most bounds are
good over algebraically closed fields (some over the reals), but
bounding solutions in the complex numbers (which contains Z) will not
include points (x_1,x_2,x_3) that are mapped to P_i(x_1,x_2,x_3) that is
an integer multiple of 232.

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





Danilo Gligoroski wrote:
> > Danilo Gligoroski writes:
>> >> [...] solve a system of 3 polynomials of order 3
>> >> with 3 variables x1, x2 and x3 in the set Z_{232}
> > and
>> >> coeficients also in Z_{232} [...]
> >
> > 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_{232} 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_{232}, what
> > would be the workfactor to find the solutions?
> > For example Mathematica's function
> > Reduce[...,{x1,x2,x3},Modulus->232] 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
> >

-- Ariel Waissbein RESEARCHER CORE SECURITY TECHNOLOGIES Tel./Fax:
(54-11) 5556-2673 Humboldt 1967, 2do piso Capital Federal, Argentina
http://www.coresecurity.com/corelabs

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