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]