Hi,
My understanding of the claim of the paper is that it would basically break the discrete logarithm problem for prime-order fields if it was true. (They end with a "numerical example" that gives them a pair of modular equations, say "the multivariate CRT is confusing, we don't know where to go from here" and end. But you can set the two unknowns to be on the curve (n, 2n), solve for n, and this completely solves DL. I learned to try this by typing "multivariate chinese remainder theorem" into Google and copying a technique from the first paper that came up. The fact that they failed to notice this is reason enough to be suspicious of their claims.) HOWEVER, I'm pretty certain that this paper is simply wrong. You can see immediately by working out the numerical example at the bottom of page 4 that they've made some mistake, since they say b1 = 28 (which is the value needed to solve DL) but if you use their equation from Lemma 2 for b1 you get 24. With 24 the equations don't work. Chasing through the derivation of Lemma 2, there is a logical jump from equation (14) to (15). They say "using the carry notation" (13) becomes (14). But if you try to work through the details of this analagously to the jump from equation (5) to (6) in the introduction, you don't get the equation they do. It's been a week since I worked this out, I forget the details, but the problem is something like a term of the form (p*phi(q) - 1) that you have to mistakenly write as p*(phi(q) - 1) to get their equation. Working it out properly, you get factors of `n` (the unknown discrete log) all over the place and there were no obvious ways to make them go away. The fact that their numerical example gives values that solve the discrete log, but don't match Lemma 2, suggests to me that they worked backwards assuming the discrete log, rather than actually using their stated results. Andrew On Thu, Sep 01, 2016 at 09:29:37PM +0200, Jan Dušátko wrote: > Dear, > I would like to ask, if someone have enought knowledge to proof or deny > mentioned: > The Discrete Logarithm Problem over Prime Fields can be transformed to a > Linear Multivariable Chinese Remainder Theorem > https://arxiv.org/abs/1608.07032 > > Regards > > Jan > > -- > Jan Dušátko > > Phone: +420 602 427 840 > e-mail: j...@dusatko.org > SkypeID: darmodej > GPG: http://www.dusatko.org/downloads/jdusatko.asc > > begin:vcard > fn;quoted-printable:Jan Du=C5=A1=C3=A1tko > n;quoted-printable:Du=C5=A1=C3=A1tko;Jan > email;internet:j...@dusatko.org > tel;cell:+420602427840 > note:SkypeID: darmodej > x-mozilla-html:TRUE > url:http://www.dusatko.org > version:2.1 > end:vcard > > _______________________________________________ > Curves mailing list > Curves@moderncrypto.org > https://moderncrypto.org/mailman/listinfo/curves -- Andrew Poelstra Mathematics Department, Blockstream Email: apoelstra at wpsoftware.net Web: https://www.wpsoftware.net/andrew "A goose alone, I suppose, can know the loneliness of geese who can never find their peace, whether north or south or west or east" --Joanna Newsom
signature.asc
Description: PGP signature
_______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves