Grant: Discovery Grants Program - Individual
McGill University
$20,000.00
Quantum-safe Cryptographic protocols
FY 2015-16
Summary
While physical implementation of a quantum computer still seems far away, the perspective of such a realization is so profound to the world of cryptography that it is worth considering already what this science will become after the construction of a quantum computer. The study of Quantum-safe (aka Post-Quantum) cryptographic tools and protocols follow from the belief that we must start now to prepare for this future.
Quantum-Safe Oblivious Transfer and Fully Homomorphic Encryption
*******************************************************
In the classical world there used to be very general techniques to achieve Oblivious Transfer from various cryptographic assumption. In the Quantum-safe cryptographic world we have no such things: several techniques have been proposed to obtain Quantum-safe Oblivious Transfer but no general technique has emerged yet. The search for such a general approach will be one objective of our research. We will also consider the relation between Oblivious Transfer and the related task of Fully Homomorphic Encryption as implemented under the Learning with error assumption or the Approximate Integer GCD assumption. We would like to show that in the quantum world OT is inherently easier to achieve than FHE.
Interactive Hashing and Statistical Zero-Knowledge Arguments
**************************************************
Another specific target is to study a powerful tool to construct secure protocols known as ""Interactive Hashing"". This tool was used in the classical setting both in the information theoretical and computational framework. Currently, none of the proofs of security of protocols involving interactive hashing is valid in the quantum setting. We will develop new techniques to establish security proofs in the quantum world. We hope to achieve the same result as in the classical world: It is possible to build statistical zero-knowledge arguments for NP under the sole assumption that a quantum one-way function exists.
Non-Interactive Quantum-Safe Zero-Knowledge Proofs
********************************************
Another classical cryptographic situation that is no longer available in the Quantum-safe world, is the primitive of Non-Interactive Zero-Knowledge protocols under computational assumptions. Such protocols have been proposed for prefect or statistical Non-Interactive Zero-Knowledge proofs under no computational assumption (although using quantum communication to achieve that). However, it does not seem to apply to situations where only Computational Zero-Knowledge is achievable (for NP-complete languages for example) or where the soundness of the proof system is only valid because a certain computational assumption cannot be broken (Perfect or Statistical Zero-Knowledge Arguments).
This research program will contain theoretical work only but will produce significant training of HQPs.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2014-04698
Name nom
Crépeau, Claude
Department département
Computer Science, School of
Organization id
61
Institution établissement
McGill University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2014
Award amount
20000
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
803
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer communications
Area of application fr
Téléinformatique
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
2
Nb partie
5
Application title
Quantum-safe Cryptographic protocols
Keyword
NSERC
Application summary
While physical implementation of a quantum computer still seems far away, the perspective of such a realization is so profound to the world of cryptography that it is worth considering already what this science will become after the construction of a quantum computer. The study of Quantum-safe (aka Post-Quantum) cryptographic tools and protocols follow from the belief that we must start now to prepare for this future.
Quantum-Safe Oblivious Transfer and Fully Homomorphic Encryption
*******************************************************
In the classical world there used to be very general techniques to achieve Oblivious Transfer from various cryptographic assumption. In the Quantum-safe cryptographic world we have no such things: several techniques have been proposed to obtain Quantum-safe Oblivious Transfer but no general technique has emerged yet. The search for such a general approach will be one objective of our research. We will also consider the relation between Oblivious Transfer and the related task of Fully Homomorphic Encryption as implemented under the Learning with error assumption or the Approximate Integer GCD assumption. We would like to show that in the quantum world OT is inherently easier to achieve than FHE.
Interactive Hashing and Statistical Zero-Knowledge Arguments
**************************************************
Another specific target is to study a powerful tool to construct secure protocols known as ""Interactive Hashing"". This tool was used in the classical setting both in the information theoretical and computational framework. Currently, none of the proofs of security of protocols involving interactive hashing is valid in the quantum setting. We will develop new techniques to establish security proofs in the quantum world. We hope to achieve the same result as in the classical world: It is possible to build statistical zero-knowledge arguments for NP under the sole assumption that a quantum one-way function exists.
Non-Interactive Quantum-Safe Zero-Knowledge Proofs
********************************************
Another classical cryptographic situation that is no longer available in the Quantum-safe world, is the primitive of Non-Interactive Zero-Knowledge protocols under computational assumptions. Such protocols have been proposed for prefect or statistical Non-Interactive Zero-Knowledge proofs under no computational assumption (although using quantum communication to achieve that). However, it does not seem to apply to situations where only Computational Zero-Knowledge is achievable (for NP-complete languages for example) or where the soundness of the proof system is only valid because a certain computational assumption cannot be broken (Perfect or Statistical Zero-Knowledge Arguments).
This research program will contain theoretical work only but will produce significant training of HQPs.