Applying Twisted Hessian Curves to Supersingular Isogeny Diffie-Hellman

Abstract

Sikkerheten til nesten all offentlig nøkkelkryptografi er basert på vanskeligheten til et av to matematiske problemer. Selvom disse problemene virker vanskelige på klassiske datamskiner, eksisterer det en algoritme for å løse begge disse problemene, som kun kjører på kvantemaskiner. Resultatet av dette er at dersom det noen gang bygges en kvantemaskin som er stor nok til å kjøre denne algoritmen, vil sikkerheten til digital kommunikasjon, slik som på internett, være ansett som kompromittert. På grunn av dette, utvikles det nå ny offentlig nøkkelkryptografi, som er basert på vanskeligheten av andre matematiske problemer. Et eksempel på et slikt system er Supersingulær Isogeni Diffie-Hellman (SIDH), som baserer seg på vanskelige problemer fra teori om elliptiske kurver. Disse problemene er relatert til isogenier, som er spesielle, struktur-bevarende avbildninger mellom elliptiske kurver.

I denne oppgaven utforsker vi en ny måte å instansiere SIDH på, ved å bruke vridde Hessianske kurver. En vridd Hessiansk kurve er en elliptisk kurve modell, som har relativt raske formler for punkt dobling og tripling. Videre er formler for isogenier mellom slike kurver nylig blitt studert. Vi benytter disse formlene i en implementasjon av SIDH. I tillegg diskuterer vi noen strukturelle egenskaper ved vridde Hessianske kurver, og deres relasjon til SIDH. Disse egenskapene kan gi opphav til en alternativ måte å instansiere SIDH på, hvor kravene til primtallet p er betydelig redusert. Dette gir muligheten til å benytte mye mindre kropper, uten tap av sikker, som igjen resulterer i nøkler som er rundt halvparten så store som de som brukes i SIDH idag.

Most public-key cryptography relies on the hardness of one of two mathematical problems. While these problems seem intractable on classical computers, there exists an algorithm for solving both of these problems, which runs on a quantum computer. The result of this is that if a quantum computer large enough to run this algorithm is ever built, it would severely compromise the security of real-world digital communications, such as on the internet. Because of this, new public-key cryptographic standards are currently being developed, which necessarily rely on the hardness of other problems. One example of such a scheme is the Supersingular Isogeny Diffie-Hellman (SIDH) key exchange, which relies on hard problems from the theory of elliptic curves. The hard problems are related to isogenies, which are special, structure-preserving maps between elliptic curves.

In this thesis, we investigate a new way of instantiating the SIDH key-exchange, by using twisted Hessian curves. A twisted Hessian curve is a specific elliptic curve model, which has relatively fast formulae for point doubling and point tripling. Further, direct formulae for isogenies between these curves have recently been studied. We use these formulae to implement the SIDH key exchange. Additionally, we discuss some of the structural properties of twisted Hessian curves, in relation to SIDH. These properties may suggest an alternative way of instantiating the SIDH key exchange, where the requirements for the prime p are significantly relaxed. This gives the possibility of using much smaller field sizes at no loss in security, resulting in key sizes that are about half the size of those used in SIDH today.