Hard problems and security proofs in a Quantum World

In modern Cryptography, the security of every cryptosystem is required to be formally proven. Most of the time, such formal proof is by contradiction: it shows that there cannot exist an adversary that breaks a specific cryptosystem, because otherwise the adversary would be able to solve a hard mathematical problem, i.e. a problem that needs an unfeasible amount of time (dozens of years) to be concretely solved, even with huge computational resources.

To be more precise, the security proof demonstrates that if an adversary can break the cryptosystem in an amount of time A, then they can solve the hard mathematical problem in an amount of time A+B. The size of B plays a fundamental role in the significance of the proof. If B is small, an adversary cannot break the scheme in a feasible amount of time A (e.g. weeks, months, or even a few years) otherwise also A+B would be a feasible amount of time, which would contradict the assumption that the mathematical problem is hard. However, if B is huge, then A+B might be an unfeasible amount of time even if A is feasible. In this case the above contradiction cannot be used and the effectiveness of the security proof is undermined. 

Therefore to have a secure system, B must be small and the mathematical problem must be hard, so that A (the time to break the scheme) can only be an unfeasible amount of time. This explains why cryptographers are always in search of mathematical problems that are hard to solve.

Classical Elliptic Curve Cryptography
In the last decades, cryptographers have found a precious ally in elliptic curves and the discrete logarithm problem, i.e the problem of determining the multiplicative factor of a multiple of a suitable elliptic-curve point. In 1994, P. Shor published a quantum algorithm capable of easily solving the discrete logarithm problem.

As a consequence, when in recent years the possibility of constructing scalable fault-tolerant quantum computers has become concrete, the marriage between elliptic curves and Cryptography seemed close to an end. 

Isogeny-based Cryptography
The proposal of using isogenies (special maps) between elliptic curves has brought elliptic curves to the attention of cryptographers once again, this time to construct schemes supposed to be secure even against quantum adversaries. Instead of considering the points of a given elliptic curve, as in classical Elliptic Curve Cryptography, Isogeny-based Cryptography works with graphs whose vertices are curves and edges are isogenies. The hard problem on which the isogeny-based cryptosystems rely is that of finding the random path connecting two curves, knowing only the starting and arrival point.   

Isogeny-based signatures and CSI-FiSh
While isogenies offer simple and efficient solutions to encryption schemes and key-exchange protocols, they turned out to be rather elusive in constructing signature schemes, which are ubiquitous in real life applications (they are, for example, used to securely distribute software updates). The first practical isogeny-based digital signature scheme, CSI-FiSh, was proposed one year ago. However, its security proof suffers the issue of having a huge B - a problem, as explained above. 

Lossy CSI-FiSh
In a joint work with his Oxford Mathematics colleague Ali El Kaafarani and with Dr. Shuichi Katsumata from AIST in Japan, Federico Pintore proposes a variant of CSI-FiSh, named Lossy CSI-FiSh, having a stronger security proof (B is approximately equal to A) and almost the same efficiency as CSI-FiSh. The work was presented at the conference Public Key Cryptography 2020 (planned for Edinburgh at the beginning of May, but then converted into a virtual conference).