Multilinear Maps in Cryptography

Bilinear maps have proven to be incredibly useful tools in cryptography. Initially a tool for cryptanalysis, the fact that they could be used for positive cryptographic applications was realised around the year 2000 by Joux, Sakai et al. and Boneh-Franklin. Since then, there has been an enormous explosion of research, and now growing commercial interest, in bilinear maps and their cryptographic applications. Early on in the development of this new field, it was recognised that multilinear maps, if they could be efficiently and securely realised, could allow even more far-reaching and surprising cryptographic applications. However, there was little activity on multilinear maps, due largely to a negative result of Boneh-Silverberg from 2003, which identified significant obstacles to the construction of multilinear maps using extensions of the known techniques for bilinear maps. Without a suitable instantiation, serious cryptographers could not sensibly proceed into this territory, no matter how attractive the possibilities.

The situation concerning multilinear maps changed dramatically in late 2012, when Garg, Gentry and Halevi proposed a candidate for objects approximating multilinear maps ``closely enough'' to allow new applications. This was rapidly followed by another proposal from Coron, Lepoint and Tibouchi. Both candidates rely on novel, non-standard hardness assumptions for the construction of secure cryptographic primitives. Very quickly, researchers have begun to take advantage of the availability of these candidates to propose innovative cryptographic schemes, with several papers recently appearing at leading conferences (including work by the PI and Visiting Researcher Hofheinz). With this sudden upswing in activity, it seems that we are at the start of an explosion in the development of multilinear maps in cryptography, akin to that experienced 12 years ago with bilinear maps.

The main purpose of this proposal is to bring together, in a timely fashion, a team of researchers with the skills and experience needed to take a leading role in this new wave of research. The team will comprise: the PI (Paterson), the named PDRA (Albrecht), a second PDRA (tbh), and the two Visiting Researchers (Galbraith, Hofheinz). We will work on three main objectives: applications, cryptanalysis and alternative constructions. Between them, these objectives cover a broad set of problems which need to be addressed in order to build confidence in the recent multilinear map proposals, and to open up the area to other researchers.

While the research to be carried out in this project is primarily theoretical in nature, cryptography is inherently an applicable subject, and there is a continuous transfer of knowledge and techniques from the more theoretical side of the field to the more applied side of the field. There is then an onward flow to the wider security and privacy research community, who use cryptography as a tool when building secure systems. This project will contribute to this flow of ideas and techniques, using a variety of specific means:

1. This proposal addresses significant barriers that need to be overcome before multilinear maps, as they are currently realised, can start to have any meaningful impact in the traditional sense: firstly we will develop a deeper understanding of the trade-offs that are available between security and efficiency with the current proposals for multilinear maps. Secondly, we will develop sound abstractions of existing proposals for multilinear maps so that they can be safely used by cryptographers when designing new cryptographic schemes based on these maps. Thirdly, we will investigate which problems believed to be hard the bilinear setting carry over to the currently known instantiations of multilinear maps and their abstractions; without having such assurances, there is a risk that theoretical cryptographers will put effort into building schemes that are insecure (because the underlying hardness assumptions are wrong). Taken together, these research tasks will help to construct a solid foundation for the subject on which others (and we) can build, and which is necessary for the maturation of the field towards standardisation and, eventually, the delivery of secure products and services. The specific pathways by which the impact of these research tasks will be realised is via traditional academic dissemination (publication at conferences and journals), through the delivery of invited talks at summer schools and conferences by the PI, and by presentation of the project's research results at the ``Real-World Cryptography'' workshop series.

2. We plan to make all of our source-code available via open-source licences, meaning that the code can be more easily integrated into cryptographic libraries (a necessary step for the uptake of cryptographic schemes making use of multilinear maps). We will also put some effort into making our code as user-friendly as we can.

3. Through RHUL's Research & Enterprise unit and the previous extensive patenting experience of the PI, the project is well placed to protect any IPR resulting from our research.

4. The PI has long-standing consulting activities with a number of companies who are likely to be interested in the commercial potential for cryptography based on multilinear maps. It cannot be stated with certainty that such arrangements will continue on the topic of the current proposal, but it is reasonable to assume that if the field develops in the anticipated way, then the PI will again be in demand as a consultant, helping to translate the latest research ideas for consumption by industrial audiences.