Towards even more reliable data encryption
What is the context of your work?
In cryptography, there are two methods of encrypting messages: secret key and public key. In the first case, a single key is used to encrypt and decrypt the message. The method is effective, based on data mixing, but requires the communicating parties to be able to exchange the key (which is not without risk). The second method is based on asymmetry. On the one hand, you generate a public key that encrypts the message and send it to the recipient—it is visible to everyone but cannot be interpreted—and on the other hand, a secret key derived from the public key decrypts the message. The advantage of this latter method is that the public key can circulate on unsecured networks such as the web; the disadvantage is that it is larger than its secret cousin. The public key is also threatened by algorithms based on the factorization of large integers, which are capable of solving the complex mathematical problems that give rise to them. Finally, an additional challenge is that certain data must be secure over long periods of time. However, if quantum computers ever become a reality, they could use factorization algorithms to compromise public keys. We are therefore focusing our efforts on developing public key encryption based on mathematical problems that are resistant to quantum computers.
What avenues are you exploring to meet this challenge?
We are exploring a post-quantum encryption scheme called homomorphic encryption. This technique paves the way for calculations on encrypted data, which is an asset in terms of cybersecurity. Our work consists of determining how to perform these calculations reliably and optimizing this encryption scheme for specific applications. In this context, maintaining the confidentiality of the data used is only the first stage of the process and the easiest to implement. It is much more complex, however, to ensure that the calculation is verifiable (the second stage of the process) and to prove, for example, that a server has indeed performed the operations requested of it based on the encrypted data at its disposal.
Can you illustrate this with a few examples?
Machine learning is an area where our work is perfectly applicable. Imagine that a hospital uses my medical data to predict, using its AI model, my risk of developing a disease. I will encrypt my data using homomorphic encryption, send it to the hospital's server to feed its model, and then the results will be sent back to me. All of this is done in a completely secure manner, with no possibility of leaks, as the data is encrypted. But the real question is whether the server has performed the function it was asked to perform, in this case calculating the risk of disease based on my medical information. It is legitimate to wonder whether it has not distorted the results in order, for example, to prescribe additional tests and, ultimately, generate more profits. The problem also arises in online elections. Homomorphic encryption guarantees the secrecy of the vote, but has the server to which the ballots are sent taken all the votes into account?
We studied the verifiability of calculations based on the assumption that malicious servers would modify the operations requested of them. We published this work in two of the world's largest conferences dedicated to cryptography, AsiaCrypt and Crypto. There is still a lot of work to be done in this area, and it promises to be exciting!
What are the current applications for your work?
At the same time, we have developed a partnership with Flashbots, a research and development organization specializing in the creation and management of blocks for blockchains such as Ethereum. Blockchains are a technology that allows information or values to be recorded and exchanged reliably, without intermediaries and with complete transparency. However, this system does not impose a specific order on the sequence of transactions, which poses challenges for coordination and security. Specialized, automated actors can intercept users' transactions before they are finalized in order to profit from them. To counter this, we are integrating homomorphic encryption techniques into Flashbots' infrastructure tools. Users can then submit their intentions (such as transaction orders) in encrypted form, and the system determines the best order for these transactions by operating directly on the encrypted data. Everyone's intentions thus remain secret until finalization, preventing any form of exploitation not provided for by the homomorphic circuit.
What are your plans for the coming months?
I will soon be joining the Institut Polytechnique de Paris, specifically the Computer Science Laboratory of the École Polytechnique (LIX) and its SURYCAT project team, to continue my work on homomorphic encryption.
Other avenues of research are also worth exploring, such as threshold encryption, which involves splitting a cryptographic key into several pieces and requiring a minimum number of fragments to be gathered in order to decrypt messages. This type of cryptography, which can be applied to homomorphic encryption, is an important issue as it will give rise to new standards, particularly in the United States.
Anamaria Costache has been a visiting professor at the Computer Science Laboratory (LIX) of the École Polytechnique and an associate professor at the Norwegian University of Science and Technology (NTNU) since 2020. Before joining NTNU, she was a researcher at Intel Corporation. She also completed a postdoctoral fellowship with the ISG group at Royal Holloway, University of London (RHUL), collaborating with Martin Albrecht and Rachel Player. She holds a PhD in cryptography from the University of Bristol, where she worked under the supervision of Nigel Smart. Her research focuses primarily on fully homomorphic encryption and, more broadly, on computation on encrypted data, privacy-preserving machine learning, as well as network-based cryptography and post-quantum cryptography.
>> Anamaria Costache on Google Scholar
*LIX: a joint research unit CNRS, École Polytechnique, Institut Polytechnique de Paris, 91120 Palaiseau, France