Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$31,000.00

Post-quantum cryptography from isogenies

FY 2016-17

Summary
Public-key cryptography is the foundation of internet security as we know it today, allowing for two parties to communicate securely without the need to exchange confidential key material in advance. All public key cryptosystems in widespread use today are based on either the problem of factoring large integers, or the problem of computing discrete logarithms in some group. In a seminal paper from 1994, Shor showed that both of these problems would be easy to solve on a quantum computer, one which uses quantum mechanics to perform calculations faster than any classical computer can achieve. Since then, much work has been done on the topic of constructing post-quantum public-key cryptosystems which would be secure against quantum computers. Some progress towards constructing quantum computers has been made, although no quantum computers with serious computing power have yet been built. Nevertheless, we believe it is prudent to plan ahead for future needs, because it normally takes many decades to change cryptosystem deployments, due to network effects. Recent announcements by the US government of upcoming plans to require post-quantum cryptosystems for all future US government security applications have provided new impetus to develop and deploy post-quantum cryptosystems. Our goal is to develop post-quantum cryptosystems in anticipation of the future construction of quantum computers. In particular, we aim to construct more (and more efficient) post-quantum protocols based on supersingular elliptic curve isogenies, which we believe offer several advantages compared to other approaches for post-quantum cryptography. Namely, isogeny-based cryptosystems are unique among all known post-quantum cryptosystems in the following ways: their security level is determined by a simple choice of a single public parameter; they achieve the smallest possible public key size; they are based on number-theoretic complexity assumptions; and implementations can leverage existing widely deployed software libraries to achieve necessary features such as side-channel resilience. We propose a number of research objectives intended to further improve the performance and security of isogeny-based cryptosystems. In addition, we also propose to develop new post-quantum aware security models for popular protocols for which no such security models are currently available in the literature, such as authenticated encryption and authenticated key exchange. We expect that isogeny-based cryptosystems will emerge as a viable mainstream option for post-quantum cryptography. Such systems will be much easier for end users to manage than the alternatives, and in many cases represent drop-in replacements for existing (non-post-quantum) cryptosystems. Student trainees from the project will be well-positioned to play a leading role in the future development of quantum computing and post-quantum cryptography.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2016-04130
Name nom
Jao, David
Department département
Combinatorics and Optimization - Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2016
Award amount
31000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2718
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Communication and information theory
Research subject fr
Théorie des télécommunications et de l'information
Partie
1
Nb partie
5
Application title
Post-quantum cryptography from isogenies
Keyword
NSERC
Application summary
Public-key cryptography is the foundation of internet security as we know it today, allowing for two parties to communicate securely without the need to exchange confidential key material in advance. All public key cryptosystems in widespread use today are based on either the problem of factoring large integers, or the problem of computing discrete logarithms in some group. In a seminal paper from 1994, Shor showed that both of these problems would be easy to solve on a quantum computer, one which uses quantum mechanics to perform calculations faster than any classical computer can achieve. Since then, much work has been done on the topic of constructing post-quantum public-key cryptosystems which would be secure against quantum computers. Some progress towards constructing quantum computers has been made, although no quantum computers with serious computing power have yet been built. Nevertheless, we believe it is prudent to plan ahead for future needs, because it normally takes many decades to change cryptosystem deployments, due to network effects. Recent announcements by the US government of upcoming plans to require post-quantum cryptosystems for all future US government security applications have provided new impetus to develop and deploy post-quantum cryptosystems. Our goal is to develop post-quantum cryptosystems in anticipation of the future construction of quantum computers. In particular, we aim to construct more (and more efficient) post-quantum protocols based on supersingular elliptic curve isogenies, which we believe offer several advantages compared to other approaches for post-quantum cryptography. Namely, isogeny-based cryptosystems are unique among all known post-quantum cryptosystems in the following ways: their security level is determined by a simple choice of a single public parameter; they achieve the smallest possible public key size; they are based on number-theoretic complexity assumptions; and implementations can leverage existing widely deployed software libraries to achieve necessary features such as side-channel resilience. We propose a number of research objectives intended to further improve the performance and security of isogeny-based cryptosystems. In addition, we also propose to develop new post-quantum aware security models for popular protocols for which no such security models are currently available in the literature, such as authenticated encryption and authenticated key exchange. We expect that isogeny-based cryptosystems will emerge as a viable mainstream option for post-quantum cryptography. Such systems will be much easier for end users to manage than the alternatives, and in many cases represent drop-in replacements for existing (non-post-quantum) cryptosystems. Student trainees from the project will be well-positioned to play a leading role in the future development of quantum computing and post-quantum cryptography.