Distributed Protocols from Isogenies

Public-key cryptography, which allows parties to communicate securely without the need of establishing a secret beforehand, has proven to be invaluable in the age of the internet and has become central in the daily lives of billions of users, protecting not only their privacy, but also mitigating the risks from fraud, theft or misuse. The security of public-key cryptography fundamentally relies on mathematical problems that are considered to be hard to solve. Although currently deployed cryptography has stood the test of time against any conceivable attack, a new threat is emerging. Quantum computers, although still in their infancy, have shown to be able to solve these mathematical problems, and consequently break the cryptographic schemes used throughout the internet.

As a consequence, research into quantum-secure cryptography has started in recent years. This so-called post-quantum cryptography is based on mathematical problems that are not easily solvable by either classical or quantum computers. Although a handful of promising post-quantum cryptographic paradigms exist, there are many security aspects yet to be explored and many cryptographic functionalities still to be translated to achieve post-quantum security. A race between the transition to a quantum-secure internet and the realization of large scale quantum computers, able to break currently deployed schemes, has started.

One of these post-quantum cryptographic paradigms is called isogeny-based cryptography. Isogenies are maps between elliptic curves that interconnect to so-called isogeny graphs, which have many strong properties advantageous to cryptography. So far, these graphs have proven powerful in the construction of cryptographic protocols that elude quantum attacks. But there is still a lot of work to be done towards realizing many of the complex cryptographic functionalities needed throughout the internet.

This thesis aims to reduce this gap by presenting new quantum-secure cryptographic applications based on isogenies. In particular, this thesis focuses on protocols involving multiple parties which jointly execute specific cryptographic functionalities. In distributed schemes, these parties all have shares of a specific secret that they need to combine to successfully realize these executions. Secrets are shared in such a way that at least a specific number of these parties need to cooperate. Such schemes have the dual advantage of protecting the secret against direct theft, but also to allow specific functionalities to only be executed, when a certain consensus threshold is reached.

As the main results of this thesis, we present distributed protocols based on isogenies with strong security guarantees. All of our schemes allow to be executed, even if up to a certain number of parties with secret shares are malicious. Furthermore, all of our schemes are robust, i.e. the execution of the algorithm succeeds, even if these malicious parties try to actively sabotage the computation. Throughout the different results, we discuss various ways of generating and verifying the sharing of the secret, as well as different structures for the related public key. A main focus lies on distributed key generation and threshold signatures, but as a stepping stone, we also explore new signature schemes and verifiable secret sharing protocols. The results from this thesis contribute to the state of the art of post-quantum cryptography, and in particular isogeny-based cryptographic protocols. It further presents results for generic secret sharings that are also shown to improve various aspects of discrete-logarithm based schemes.