{"id":381917,"date":"2017-05-08T16:42:58","date_gmt":"2017-05-08T23:42:58","guid":{"rendered":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/?p=381917"},"modified":"2017-05-09T06:00:45","modified_gmt":"2017-05-09T13:00:45","slug":"cryptography-quantum-computing-intersect","status":"publish","type":"post","link":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/blog\/cryptography-quantum-computing-intersect\/","title":{"rendered":"Where cryptography and quantum computing intersect"},"content":{"rendered":"

By Kristin Lauter<\/a>, Principal Researcher, Microsoft Research<\/em><\/p>\n

Last week I spent time at the American Institute of Mathematics (opens in new tab)<\/span><\/a>in San Jose, working with a group of 20 or so mathematicians and computer scientists on questions related to quantum arithmetic, at a conference co-organized by researchers in the Microsoft Research (MSR) Quantum Architectures and Computation (QuArC)<\/a> group. You might ask, why is a cryptographer working on this topic? (And also, when will we have a quantum computer? \ud83d\ude42 )<\/p>\n

I was at this workshop (opens in new tab)<\/span><\/a>thanks to a surprising intersection between cryptography and quantum computing: An algorithm for breaking a cryptographic hash function which we found more than 10 years ago turns out to be relevant for designing efficient circuits for quantum arithmetic! In 2008, we published an efficient and constructive algorithm to find paths in LPS graphs (opens in new tab)<\/span><\/a>to break the cryptographic hash function (opens in new tab)<\/span><\/a>. The hash function was one in a family I had proposed in 2005 with Denis Charles (MSR) and Eyal Goren, professor, McGill University. Finding preimages for this hash function involved identifying paths in the well-known Lubotzky-Phillips-Sarnak (LPS) graphs (opens in new tab)<\/span><\/a>, the celebrated Ramanujan (yes, The Man Who Knew Infinity (opens in new tab)<\/span><\/a>) graphs constructed in the 1980s. This had been an open problem for several decades; we were delighted when we solved it.<\/p>\n

But due to the stove pipes among research communities, our algorithm was not known to a group of researchers in quantum arithmetic, who wanted to solve this problem for a completely different reason. In 2014, Neil Ross and Peter Selinger published an algorithm (opens in new tab)<\/span><\/a>that they found independently in a different setting, but which turns out to be essentially the same as our algorithm. They were trying to solve the problem of decomposing operations on a single qubit into quantum circuits and for finding the shortest possible circuit.<\/p>\n

Researchers in the QuArC group at Microsoft Research, Vadym Kliuchnikov<\/a>, Krysta Svore<\/a>, Martin Roetteler<\/a>, and others, had played a crucial role in developing a framework (opens in new tab)<\/span><\/a>for addressing questions in quantum arithmetic more broadly, including for topological qubits (opens in new tab)<\/span><\/a>, the focus of Microsoft’s approach to quantum computing (for Ising anyons, Fibonacci anyons, and metaplectic anyons).\u00a0 This is important for the future of quantum computing because once a quantum computer is built, we will need to efficiently express operations on qubits in terms of fundamental gates (opens in new tab)<\/span><\/a>that can be realized in the physical world.\u00a0 One of the candidates identified are the Clifford+T gates.\u00a0 The connection between our LPS path-finding algorithm and this area was discovered in 2015 by Alex Gamburd (opens in new tab)<\/span><\/a>, professor, Graduate Center, CUNY, and Peter Sarnak (opens in new tab)<\/span><\/a>, professor, Princeton University, and now, topics from both cryptography and quantum arithmetic are included in the workshop.<\/p>\n

I have recently become interested in quantum computation for another reason that is important to the future of cryptography. The security of our e-commerce and cloud-based systems and the privacy of much of our data rely on the strength of currently deployed public key cryptographic systems such as RSA and Elliptic Curve Cryptography (ECC).\u00a0 Once robust quantum computers can be built at a large enough scale, polynomial time quantum algorithms (opens in new tab)<\/span><\/a>can be implemented to attack the underlying math problems for these cryptosystems, rendering them insecure. However, it is not clear how soon a sufficiently large and robust quantum computing device will be built, and also which architecture and gate set will be realizable. This makes it difficult to estimate the concrete security for cryptosystems of a given bit length in a post-quantum environment, and difficult to estimate the appropriate timeline for migration to new cryptosystems. In collaboration with researchers in QuArC, we have been developing concrete quantum estimates for breaking current encryption systems. At the workshop, we discussed various possible quantum gate sets that might become real; some of the project groups focused on developing the mathematics to implement efficient computation if those gate sets are built.<\/p>\n

There may be hard instances of the “path-finding problem”\u009d for explicit choices of expander graphs, and such graphs could be the foundation for post-quantum cryptosystems, meaning classical protocols that are resistant to quantum attacks. This year, the National Institute of Standards and Technology (NIST) is running an international Post-Quantum Cryptography (PQC) (opens in new tab)<\/span><\/a> competition, with submissions due in November, to determine possible replacements for currently deployed cryptographic systems. One of the possible candidates for standardization is based on the hard problem, path-finding in Supersingular Isogeny Graphs, introduced in our 2006 cryptographic hash function (opens in new tab)<\/span><\/a>paper.\u00a0 This paper was presented at an NIST workshop (opens in new tab)<\/span><\/a>in 2005, a workshop leading to standardizing the new cryptographic hash function SHA-3 (opens in new tab)<\/span><\/a>, and was described in a news article (opens in new tab)<\/span><\/a>in Science magazine in 2008.<\/p>\n

In that paper we proposed the hard problem of finding paths or cycles in the Supersingular Isogeny Graph. This hard problem has since been used as the basis for proposals for encryption, key exchange and digital signatures, which are the three tracks of the NIST competition. Supersingular Isogeny Graphs consist of vertices, which are isomorphism classes of supersingular elliptic curves in characteristic p, and the edges are isogenies, or maps between curves that are homomorphisms, thus the name Supersingular Isogeny Graph. Originally studied and generalized by Arnold Pizer (opens in new tab)<\/span><\/a>, professor emeritus, University of Rochester, these graphs have connections to deep theorems in number theory and beautiful properties such as optimal expansion constants. The expansion constants ensure that relatively short walks on the graph quickly approximate the uniform distribution in the output.<\/p>\n

 <\/p>\n

\"Supersingular

A small example of a Supersingular Isogeny Graph, for the prime p=2521, graph image by Denis Charles, principal applied scientist, Microsoft Research<\/p><\/div>\n

Like many other public key systems, operations necessary to implement Supersingular Isogeny Graphs can be costly, so there is no guarantee that these systems would be competitive from a performance point of view. Also, like many of the other possible math-based candidates such as code-based cryptography, lattice-based cryptography and multivariate cryptosystems, relatively new math problems need to be studied for possible vulnerability to both classical and quantum algorithms. Thanks to the NIST PQC competition, we can expect mathematicians and cryptographers to be very busy during the next few years as we determine the best possible choices for our post-quantum cryptography standards.<\/p>\n

Learn more<\/strong><\/p>\n