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
Post by Jan DušátkoDear,
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
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
tel;cell:+420602427840
note:SkypeID: darmodej
x-mozilla-html:TRUE
url:http://www.dusatko.org
version:2.1
end:vcard
_______________________________________________
Curves mailing list
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