| NSF Org: |
CNS Division Of Computer and Network Systems |
| Recipient: |
|
| Initial Amendment Date: | July 21, 2017 |
| Latest Amendment Date: | June 25, 2021 |
| Award Number: | 1701567 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Andrew Pollington
adpollin@nsf.gov (703)292-4878 CNS Division Of Computer and Network Systems CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | August 1, 2017 |
| End Date: | March 31, 2022 (Estimated) |
| Total Intended Award Amount: | $400,000.00 |
| Total Awarded Amount to Date: | $400,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
450 JANE STANFORD WAY STANFORD CA US 94305-2004 (650)723-2300 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
450 Serra Mall Bldg 380 Rm 383E Stanford CA US 94305-2125 |
| 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
The project is an interdisciplinary collaboration between mathematicians and computer scientists in an intensive focused research effort to solve a central challenge in cryptography, namely constructing a family of secure and efficient algebraic multilinear maps. Multilinear maps have remarkable applications in cryptography, such as multiuser non-interactive key-exchange, general functional encryption, fully-homomorphic encryption, and indistinguishability obfuscation. The results of the project are expected to enable a new age of cryptographic systems and open new directions in the field. The project will train graduate students and postdoctoral associates through involvement in deep modern mathematics research with applications in computer science.
The first candidate multilinear maps are inefficient in practice, and have been shown to be insecure for some of the desired applications. This project takes a very different approach from earlier ones. The starting point is the observation that there already exist many natural multilinear maps in arithmetic geometry, arising naturally from the cohomology of arithmetic varieties and motives, and from K-theory. They give a richer class of objects than elliptic curves over finite fields, whose groups of points are widely used in practice for cryptographic key exchange and public-key encryption. The challenge is to find such algebraic structures for which the multilinear maps can be efficiently computed, and for which the associated cryptographic problems (e.g., discrete logarithm problems) are expected to be hard.
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 project was a collaboration of four researchers: Dan Boneh, Ted Chinburg, Alice Silverberg, and Akshay Venkatesh. We initially set out to search for a cryptographic multilinear map built from an algebraic object. Such an object has remarkable applications in cryptography, and constructing one is a major open problem in the field. We had regular phone meetings to discuss our progress. Our first progress was a proposal for something a little weaker that we called a cryptographic invariant map. This object gives many of the exciting applications in cryptography, and initially seemed to be constructible from isogenies on elliptic curves. The work was published in the Journal of Mathematical Cryptology in 2020. Alas, this framework has not yet been successfully instantiated. We also ran two week-long workshops for mathematicians to jointly explore the construction of a cryptographic multilinear map: one at the American iInstitute of Math (AIM) and one at the Banff International Research Station (BIRS). Beyond multilinear maps, we also explored various aspects of isogeny based cryptosystems. One key question in the area is how to generate a random supersingular elliptic curve without knowledge of its endomorphism ring. We explored a particular approach that led to some interesting discoveries about the structure of the isogeny graph of supersingular elliptic curves. This joint work with Jonathan Love won the Selfridge Prize at the Algorithmic Number Theory Symposium (ANTS) where it was presented. The project resulted in several other results in the area of mathematical cryptography, but the core question of constructing a cryptographic multilinear map remains open. We made a valiant effort, and the results we generated a long the way made the project a success. We continue to believe that this elusive algebraic object will eventually be found. However, it will clearly require much more work and a deep new idea.
Last Modified: 11/25/2022
Modified by: Dan Boneh
Please report errors in award information by writing to: awardsearch@nsf.gov.
