[Cryptography] MATH: Unlikely correctness of paper will break some discrete logarithm over F_p^*

Georgi Guninski guninski at guninski.com
Wed Aug 31 04:33:25 EDT 2016


https://arxiv.org/abs/1608.07032
The Discrete Logarithm Problem over Prime Fields can be
transformed to a Linear Multivariable Chinese Remainder
Theorem
H. Gopalakrishna Gadiyar, R. Padma
(Submitted on 25 Aug 2016)

I am pretty sure if this paper is fixable, it will efficiently break
DLs over F_p^* at least for primes of the form p=2q+1 with q prime.

Is the paper fixable?

How would it break IMHO:

The authors claim (18) (19) that they reduce DL to two constrained
linear congruences with different moduli in the two unknowns
n,\beta_n and the constraints are 0 < n < p, 0 < \beta_n < p.

This is efficiently solvable via integer programming due to result
of Lenstra about integer linear programs in fixed number of variables.

Work over the integers adding two integer unknowns $x,y$ to get rid
of the congruences and keep the inequality constraints, getting
integer program in _only four unknowns_.

Shorter version of this was posted few days ago on cpunks.org, no
replies so far.

The authors don't appear to be cranks/crackpots, though
scholar.google.com doesn't recognize them AFAICT.


More information about the cryptography mailing list