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šátko*Dear,

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