Every online transaction we make with another person is protected so that a third person cannot read it without the permission of the two people exchanging the information in the first place. This process is called encryption of the data. The first person, say Alice, sends an encrypted message to the second, say Bob. How can Alice ensure that only Bob has the key to the code she has set and a trespasser, say Kate, can see that there is a transaction but cannot intercept it? To use a simple and oft-used analogy – let Alice send a trunk to Bob with a lock on it. Bob receives the trunk and locks it the second time with his own lock, sending it back to Alice. Alice now removes her lock and sends the trunk back to Bob. Bob now can unlock the lock he had put and open the trunk to see the secret message.
Thus, while the transaction took place in full public view, only Alice and Bob were able to read the message inside the trunk.
In the time of the classical computer, the lock in question consists of a problem that is mathematically hard for the computer to solve. For example, Alice takes a two very large prime numbers, that is, numbers that are only divisible by themselves and by one. She multiplies the two and creates an even larger number. She uses this number to encrypt or lock her message to Bob. Kate, now is in trouble because, in order to break the lock, she has to factorise a very large number whose factors are large prime numbers.
This is difficult because if the prime factors are large enough, the problem becomes very difficult to crack for a classical computer. It would take the classical computer “exponentially large” time to guess the factors.
This mathematical problem known as integer factorisation is one of the methods presently used to encrypt our secret or private messages. There are other methods using the so-called discrete logarithm problem, which again would take a normal computer exponentially large time to crack.
Quantum computers
This was all well, as long as we only had to deal with classical computers. Now, enters the quantum computer. One of the basic elements that make up this quantum computer is that where the classical one uses bits to compute this one uses “qubits”. What is the difference?
Classical bits can take the value 0 or 1, allowing for a binary system to be set up and the lowest level of computer language is done manipulating these bits. A qubit on the other hand can exist as a superposition of two states 0 and 1. So if you have an n-qubit number, it can exist as a superposition of 2 n states. This also allows for immense amount of parallel processing.
Hence the question of whether these problems which are “hard” for the classical computer become easier for a quantum one has the disturbing answer – yes. So, a new cryptography has to be devised, and that is where IIT Madras professor, Shweta Agrawal’s work comes into play. She works not just with quantum cryptography but with post quantum cryptography – a field which deals with additional possibilities offered by a quantum system, which goes beyond being able to break the integer factor code.
Enter lattices
One of the main contenders for a mathematical problem that is hard for the quantum computer to crack is the so-called shortest vector problem. This involves lattices. Lattices are regular arrangement of points in space; examples in nature include honeycombs and all crystalline solids, like common salt. A line of regularly spaced points is a lattice in one dimension, and a crystal of salt is a three-dimensional lattice. Mathematically, we can extend this construction to 5, 10 or even 500 dimensions.
At this magnitude, it becomes in theory a “hard” problem for a quantum computer to calculate the shortest vector from one point to any other point. This problem can therefore be used to construct “locks” that can even withstand a quantum attack. In her work which appeared at conferences Eurocrypt 2019 and 2020, Dr. Agrawal provides new methods to construct such encryption schemes which are secure against quantum computers.
As an example of what one can achieve using such encryption schemes, take two companies which are considering a merger, and want to find out if it will be mutually profitable by engaging in some computation, but without revealing their assets to each other. “We can encrypt the information about their individual assets, and provide a secret key which only reveals the output of the computation and does not reveal anything about the inputs!” says Dr. Agrawal.
Thus, it follows as she says: “In modern cryptography, not only can we create locks on information so that quantum computers cannot break them, we can even design the locks so that the information inside the locks can be manipulated without even opening the locks!”
