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 i1
will split at step i depending on whether your
approximation at the step i1 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]