| NSF Org: |
CNS Division Of Computer and Network Systems |
| Recipient: |
|
| Initial Amendment Date: | August 17, 2018 |
| Latest Amendment Date: | August 17, 2018 |
| Award Number: | 1840893 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Nina Amla
namla@nsf.gov (703)292-7991 CNS Division Of Computer and Network Systems CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | October 1, 2018 |
| End Date: | September 30, 2020 (Estimated) |
| Total Intended Award Amount: | $100,000.00 |
| Total Awarded Amount to Date: | $100,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
3112 LEE BUILDING COLLEGE PARK MD US 20742-5100 (301)405-6269 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
College Park MD US 20742-5141 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Secure &Trustworthy Cyberspace |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
Current technology for securing Internet traffic relies on cryptographic protocols that are based on the presumed difficulty of two mathematical problems - the factorization problem and the discrete logarithm problem. However, the emerging technology of quantum computers - a type of computer that leverages the laws of quantum mechanics to perform certain computations faster than classical computers - can efficiently solve both of these problems and thus effectively attack the respective cryptographic protocols. Anticipating the advent of quantum computers, efforts to standardize new quantum-safe (also called "post-quantum") cryptographic protocols are in progress. It is important to note that quantum attacks not only render factoring and discrete-logarithm based cryptosystems insecure, but also compromise the security of cryptosystems employing a technique known as the "random oracle methodology." This methodology assumes that all parties have access to an ideal object known as a random oracle and the security of the cryptosystem is analyzed in the random oracle model. Classical security proofs in the random oracle model fail in the quantum setting since quantum superposition queries to the oracle allow for improved attacks. This project will develop crucial tools for the security analysis of random oracle based, post-quantum cryptosystems by means of a quantum analogue of the indifferentiability framework.
A fundamental tool for analyzing the security of classical cryptosystems in the random oracle model involves proving the so-called indifferentiability of constructions. The notion of indifferentiability formalizes the properties required of a construction to securely replace an ideal object (such as a random oracle) in arbitrary cryptosystems. Although often taken for granted, indifferentiability results from the classical setting do not necessarily extend to the quantum setting. Moreover, the quantum setting presents unique obstacles to proving indifferentiability, leaving in doubt whether the entire indifferentiability technique is applicable in the quantum oracle setting. This project explores the possibility of an indifferentiability framework in the quantum oracle setting. Specifically, the project encompasses the following technical problems: (1) Determining whether or not broad impossibility results apply to the quantum indifferentiability setting; (2) Developing new techniques for proving quantum indifferentiability; (3) Defining new formal security models for the analysis of symmetric and public key cryptosystems in the quantum oracle model; (4) Analyzing the security of essential constructions with respect to quantum indifferentiability or the newly introduced formal models.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
The goals of this project were to investigate the security of post-quantum cryptosystems, especially in the so-called quantum random oracle model. Specifically, these are cryptosystems that make use of a public random oracle. In this case, security may no longer hold in the quantum setting, where an attacker may make quantum superposition queries to the oracle.
Intellectual Merit: The outcomes of this project include five major publications. The first work ["Constant-Round Group Key-Exchange from the Ring-LWE Assumption." D. Apon, D.Dachman-Soled, H. Gong, J. Katz. PQCrypto 2019] presents a new construction of a group key exchange scheme from the Ring-LWE assumption. Such a scheme is used to efficiently establish a common cryptographic key across a group of parties, as opposed to each pair of parties establishing a separate cryptographic key. The next three works ["Security of NewHope Under Partial Key Exposure." D Dachman-Soled, H Gong, M Kulkarni, A Shahverdi. Research in Mathematics and Public Policy, 93-125."(In) Security of Ring-LWE Under Partial Key Exposure." D Dachman-Soled, H Gong, MKulkarni, A Shahverdi. Journal of Mathematical Cryptology 15 (1), 72-86."Towards a Ring Analogue of the Leftover Hash Lemma." D Dachman-Soled, H Gong,M Kulkarni, A Shahverdi. Journal of Mathematical Cryptology 15 (1), 87-110.] analyze the security of ring-LWE-based cryptosystems in the random oracle model, under leakage of the secret key. These results are applicable in side-channel settings, where an attacker obtains additional information about the secret key. The last work ["LWE with side information: attacks and concrete security estimation." D Dachman-Soled, L Ducas, H Gong, M Rossi. Annual International Cryptology Conference, 329-358.] provides a new framework for establishing concrete parameters for LWE-based cryptographic schemes, which are typically in the random oracle model. Our work is influencing the concrete paraters chosen for candidates submitted to the NIST post-quantum standardization effort. Finally, we have released an open-source Toolkit for determining the concrete security of LWE-based cryptosystems. The toolkit can be applied to both the standard setting and the setting in which side-channel information is available. The open-source Toolkit is available hereon GitHub: https://github.com/lducas/leaky-LWE-Estimator.
Broader Impacts: The outcomes of this project include advising and career development for the PhD students of the PI and co-organization of an IPAM Graduate Summer School: "Post-Quantum and Quantum Cryptography."
Last Modified: 02/09/2021
Modified by: Dana Dachman-Soled
Please report errors in award information by writing to: awardsearch@nsf.gov.
