Re: Solving systems of multivariate polynomials modulo 2^32
On Mon, 14 Aug 2006, David Wagner wrote:
Here's an example. Suppose we have the equations:
x*y + z = 1
x^3 + y^2 * z = 1
x + y + z = 0
Step 1: Find all solutions modulo 2. This is easy: you just have to try
2^3 = 8 possible assignments and see which one satisfy the equations. In
this case, the only solution is x=0, y=1, z=1 (mod 2).
There is a small optimization: modulo 2, x^n = x and thus if ``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)'' it is not
more difficult to solve than degree 3 (xyz) with up to 8 terms. In
particular, the example is equivalent modulo 2 to
x*y + z = 1
x + y*z = 1
x + y + z = 0
[[[ Btw, something is wrong in the example: the following program
N = 2
for x in range(N):
for y in range(N):
for z in range(N):
if (x*y+z)%N==1 and (x**3+y**2*z)%N==1 and (x+y+z)%N==0:
print x,y,z
outputs
0 1 1
1 0 1
1 1 0
and apparently 1,0,1 is indeed a solution mod 2:
1*0+1=1, 1+0*1=1, and 1+1+0=0
]]]
Trying all combinations is a reasonable strategy, but it is also
possible to use an iterative simplification (especially if there are,
say, 80 variables):
if y = 0 we get a linear system
z = 1
x = 1
x + z = 0
that is 1,0,1 is a solution
if y = 1 we get also a linear system
x + z = 1
x + z = 1
x + 1 + z = 0
that is 0,1,1 and 1,1,0 are also solutions.
Linearization (and relinearization) may also be an option.
Step 2: Find all solutions modulo 4. This is again easy: since we know
x=0 (mod 2), then the only two possibilities for x mod 4 are 0 or 2.
Likewise, there are only two possibilities for y mod 4 and z mod 4.
Trying all 2^3 = 8 possible assignments, we find that the only two
solutions are x=0, y=3, z=1 (mod 4) and x=2, y=1, z=1 (mod 4).
Once we solved the system modulo 2^k, doing so modulo 2^{k+1} is much
simpler than trying all possibilities for the next bit. A nice
property of multiplication is that it gives linear relation in the
non-zero bit-slice, that is if we know that
X = x 2^k + A
Y = y 2^k + B,
where A and B are known and k0, then modulo 2^{k+1} we have
X*Y = xy 2^{2k} + (Bx+Ay) 2^k + AB = (bx+ay) 2^k + AB,
where a and b are the least significant bits of A and B (A = 2A'+a).
Since A and B are known constants, the next bit of XY is a linear
function (bx + ay + AB/2^k) of the next unknown bits of X and Y.
For example, in our case once we have (0,1,1) we represent X=2x,
Y=2y+1, and Z=2z+1 and write
2x(2y + 1) + 1 = 1
(2x)^3 + (2y+1)^2(2z+1) = 1
2x+(2y+1)+(2z+1) = 0
remove everything divisible by 4
2x + 1 = 1
2z + 1 = 1
2x + 2y + 2z + 2 = 0
and divide each equation by 2 (this is possible becuase (0,1,1) was a
solution modulo 2)
x = 0
z = 0
x+y+z=1,
that is (x,y,z)=(0,1,0) and thus (X,Y,Z) = (0,3,1) modulo 4.
We see that this requires performing 32 of these steps. On average, we
expect about one feasible solution to remain possible after each step
(though this number may vary). Each step requires testing 8 possible
assignments, times the number of assignments from the prior step. Thus,
on the average case we can expect this to run very fast.
Btw, the matrix (and thus its rank) depends only on the LSB of the
current solution, thus for each solution modulo 2, there is either a
split on each new step (if the rank is not maximal and the system is
consistent on this step), or no splits at all (if it is maximal).
--
Regards,
ASK
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Solving systems of multivariate polynomials modulo 2^32
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 [EMAIL PROTECTED]
Re: Solving systems of multivariate polynomials modulo 2^32
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 [EMAIL PROTECTED]
Solving systems of multivariate polynomials modulo 2^32
Hi,
In order to 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} I used the Mathematica
5.1 function Reduce[...,{x1,x2,x3},Modulus-2^32]. It
is giving the solutions but it is not very fast. I
wanted to programe a procedure in C in order to get
more speed in the computation.
I was trying to figure out what algorithms are used in
the Reduce function of Mathematica (reading Wolfram
web pages) but I couldn't find any specific
information for the algorithms they are using for
solving multivariate polynomials modulo 2^32.
I found several papers that are dealing with solving
univariate or multivariate polynomials in finite
fields such as:
1. Lauder :
http://www.maths.ox.ac.uk/~lauder/papers/LauderManyVarSept16.pdf
2. van de Woestijne :
http://www.math.leidenuniv.nl/~cvdwoest/maths/ober.pdf
and
http://www.math.leidenuniv.nl/~cvdwoest/maths/issac2005.pdf
3. Barreto and Voloch:
http://www.ma.utexas.edu/users/voloch/Preprints/roots.pdf
4. Ding, Gower and Schmidt:
http://eprint.iacr.org/2006/038.pdf
but the algorithms there are for soving polynomials
over finite fields GF(p) or GF(p^n) which is different
than just solving polynomials (univariate or
multivariate) modulo 2^32.
I will appreciate any hint or coment.
Regards,
Danilo Gligoroski
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Solving systems of multivariate polynomials modulo 2^32
Hi Danilo,
Maybe you should use some other function in Mathematica. Symbolic
solving polynomial equations is a very difficult task (e.g.,
doubly-exponential worst case time complexity). But in this case it
shouldn't take that much time.
Let me notice that Z_{2^32} is not the same as F_{2^32} the field of
2^32 elements. I presume that you mean the former, which is not a field!
If you mean the latter, then you are using the wrong domain
specification in Reduce.
If you meant the field of 2^32 elements, then you should check how to
specify this in Mathematica.
For option Z_{2^32} you could try to solve the system (with elimination)
over the rationals, and once you eliminated variables look at
everything in the integers (multiplying by the LCM of the denominators)
and then simply take modulo 2^32 over all the solutions! If the system
of 3 polynomials in 3 variables is generic-enough it should have only
finite solutions.
If you want to continue using Mathematica, you can try your luck with
functions such as Solve or GroebnerBasis. There exist alternatives to
Groebner basis which I prefer personally, such as the Kronecker solver
(http://www.math.uvsq.fr/~lecerf/software/kronecker/) which comes as a
Magma package.
I hope this helps.
Cheers,
Ariel
Danilo Gligoroski wrote:
Hi,
In order to 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} I used the Mathematica
5.1 function Reduce[...,{x1,x2,x3},Modulus-2^32]. It
is giving the solutions but it is not very fast. I
wanted to programe a procedure in C in order to get
more speed in the computation.
I was trying to figure out what algorithms are used in
the Reduce function of Mathematica (reading Wolfram
web pages) but I couldn't find any specific
information for the algorithms they are using for
solving multivariate polynomials modulo 2^32.
I found several papers that are dealing with solving
univariate or multivariate polynomials in finite
fields such as:
1. Lauder :
http://www.maths.ox.ac.uk/~lauder/papers/LauderManyVarSept16.pdf
2. van de Woestijne :
http://www.math.leidenuniv.nl/~cvdwoest/maths/ober.pdf
and
http://www.math.leidenuniv.nl/~cvdwoest/maths/issac2005.pdf
3. Barreto and Voloch:
http://www.ma.utexas.edu/users/voloch/Preprints/roots.pdf
4. Ding, Gower and Schmidt:
http://eprint.iacr.org/2006/038.pdf
but the algorithms there are for soving polynomials
over finite fields GF(p) or GF(p^n) which is different
than just solving polynomials (univariate or
multivariate) modulo 2^32.
I will appreciate any hint or coment.
Regards,
Danilo Gligoroski
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
--
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 [EMAIL PROTECTED]
Solving systems of multivariate polynomials modulo 2^32
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} [...]
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. Suppose we have the equations:
x*y + z = 1
x^3 + y^2 * z = 1
x + y + z = 0
Step 1: Find all solutions modulo 2. This is easy: you just have to try
2^3 = 8 possible assignments and see which one satisfy the equations. In
this case, the only solution is x=0, y=1, z=1 (mod 2).
Step 2: Find all solutions modulo 4. This is again easy: since we know
x=0 (mod 2), then the only two possibilities for x mod 4 are 0 or 2.
Likewise, there are only two possibilities for y mod 4 and z mod 4.
Trying all 2^3 = 8 possible assignments, we find that the only two
solutions are x=0, y=3, z=1 (mod 4) and x=2, y=1, z=1 (mod 4).
Step 3. Find all solutions modulo 8. First, take the mod-4 solution
x=0, y=3, z=1 (mod 4) and try extending it all 2^3 possible ways, to
see which of them lead to mod-8 solutions. Then, take the other mod-4
solution x=2, y=1, z=1 (mod 4) and try extending it all 2^3 possible
ways, too. The result is the set of mod-8 solutions.
Step 4. Find all solutions modulo 16. etc.
We see that this requires performing 32 of these steps. On average, we
expect about one feasible solution to remain possible after each step
(though this number may vary). Each step requires testing 8 possible
assignments, times the number of assignments from the prior step. Thus,
on the average case we can expect this to run very fast.
Note that this only works for Z_{2^32}. It doesn't work for GF(2^32).
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
