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

[Kristian Gjøsteen]

31. aug. 2016 kl. 10.33 skrev Georgi Guninski <guninski at guninski.com>:
> 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?

Can you find a mistake in the paper? I looked briefly at it, and the equations seemed correct to me.

Linearization is an interesting technique. The idea is that you have a system of non-linear equations, say u1 x^2 + v1 x  = w1 and u2 x^2 + v2 x = w2, and you want to solve it, but you cannot. However, you know that there is a solution.

Now replace the x^2 terms with y. You get the linear system of equations

	u1 y + v1 x = w1
	u2 y + v2 x = w2

with two unknowns and two equations. Since you know that there is a solution x0 to your original system, you know that y=x0^2 and x=x0 is a solution to the linear system.

The point is that if your linear system of equations has a unique solution, you can find this solution and it must be y=x0^2 and x=x0. So this is a method for solving certain non-linear systems of equations using linear equations. It has found reasonably interesting applications in cryptography.

However, if you have only one non-linear equation, this technique isn’t very useful, since there’s nothing to force any solution you find to be the correct solution.


The Chinese remainder theorem is also a massively useful theorem. It allows you to solve some equation modulo a bunch of relatively prime moduluses and then «glue» your results together to get solution(s) modulo the product of the moduluses. If everything is nice, you get a unique solution. However, if you cannot solve the equations (e.g. if you have a linear equation with two unknowns), trying to solve it modulo several moduluses doesn’t really help you, since the different equations are essentially independent.


I should also mention that this stuff modulo squares appear in a neat cryptosystem by Okamoto and Uchiyama. Paillier extended their construction into a properly useful cryptosystem. Later, at PKC 2006 Chevallier-Mames, Paillier and Pointcheval have an interesting cryptosystem modulo p^2.

The current paper, however, is a case of funny computations that aren’t really interesting.

-- 
Kristian Gjøsteen