[curves] DLP to Linear Multivariable Chinese Remainder?

[Andrew Poelstra]

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:		jan at 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:jan at 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 at 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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20160901/a48bd744/attachment.sig>