Key assumptions

Assumptions of difficulty

The security of any system of strong cryptography depends on key assumptions of the computational difficulty of solving certain mathematical problems. Designers of cryptosystems must be very explicit about all assumptions of computational difficulty on which the security of their system is based. There is no known proof that P≠NP or that one-way functions exist, although the fact that cryptocurrency exists on tradeable markets would lead us to believe that these problems so easy to pose are in fact quite difficult to solve. That is simply too much money on the table which would instantly be grabbed if there were any easy method of solving such problems.

The discrete logarithm problem

The main assumption on which public key schemes of elliptic curve cryptography are based is that the elliptic curve discrete logarithm problem is difficult to solve.

Counting points on elliptic curves over finite fields

Hasse’s theorem tells us that the number of points on an elliptic curve modulo a prime p is between $p+1-2{\sqrt {p}}$ and $p+1+2{\sqrt {p}}$ inclusive. If the prime modulus p is very large, we assume it is very difficult to calculate the exact number of points on the curve within this range.

Existence and practicality of quantum algorithms

Shor’s algorithm trivially cracks the discrete logarithm problem on a quantum computer, but these have not yet been physically demostrated beyond a very few “qubits.” Another possible theoretical concern is that quantum algorithms might be reduced to classical algorithms in polynomial time, even if proper “quantum” computers as such are not developed.