The trouble with quantum computing and how CAKE can save us.

Incredible amounts of new web content are created every single day, and our technology-focused society fuels the rapid growth of the modern internet.  We now use it for messaging, electronic banking or even electronic voting. However, digital communication does not come without risks: just like talking to each other in a crowded cafe, there is always the risk of being overheard, when sending information on the web. Fortunately, we can use the science and tools of cryptography for keeping our private communications private, both in the real and digital world.

To give you an example, I will introduce you to Alice and Bob, who are chatting with each other. Alice is telling Bob some important secrets, so their conversation should stay confidential. But right next to them is Eve, who intends to eavesdrop.

Alice wants to talk to only Bob, but Eve likes to listen.

Fortunately, Alice and Bob know how to use an encryption scheme, allowing them to communicate in a way that only they can understand. One way to do this is to use a key to encrypt their messages before sending them.

Since Eve does not have the key, she cannot recover the message, even if she knows the method (the encryption scheme) used by Alice and Bob. However, emerging technologies can help Eve decipher the code even without knowing the key. Prominently, the advancement of quantum computing, while promising breakthroughs in many areas of science, poses a threat to commonly used cryptography such as RSA encryption or Diffie-Hellman key exchange, two of the most common ways to secure communication on the internet.

To be prepared, the European Commission has funded the quantum-secure internet (QSI) project to support doctoral candidates (such as me) in researching two promising approaches to prepare cryptography for the advent of quantum computing. These two areas are called Post-Quantum Cryptography (PQC) and Quantum Key Distribution (QKD). My research area is PQC, so I will be focusing on this part, while my colleagues posting their stories in the coming months can fill you in on QKD.

Alice and Bob use a key and symmetric encryption to hide their message from Eve.

Key exchange in a quantum world.

Let’s return to Alice and Bob. In the previous example they used a shared key to encrypt (and decrypt) their message. This is an example of what is called symmetric encryption, where encryption and decryption (what Alice and Bob use to hide and recover messages, respectively) use the same key.

But there is one big question we have not discussed: how do Alice and Bob get a key in a way that only they know it? This problem is known as key exchange. Additionally, Alice and Bob would like to ensure they are really talking to each other, and someone pretending to be one of them. In other words, they want the key exchange to be authentic (AKE).

Keys for digital communication are in general long and not human-memorable (unless you can remember hundreds of random characters). Fortunately, there are methods for key exchange using something quite simple: a password! Whoever has the password can access the key and then read the messages.

Now while passwords are nice because you can choose something that is easy to remember, that also means that someone else (talking about you, Eve…) may be able to guess it, or figure it out some other way. Even worse, imagine now that Eve has recently bought a quantum computer that is many orders of magnitude faster at guessing passwords than a normal PC, so things are looking bad! Once Eve has the password, they can not only read Alice and Bob’s messages, but potentially even impersonate either one of them, who are unaware of Eve.

This is where my research comes into action. We are working on developing an internet communication protocol called OCAKE that enables key exchange with high security guarantees even with weak (easily guessable) passwords. Like most password-authenticated key exchange (PAKE) protocols, OCAKE does not use the password as a key to encrypt messages, but as a means of authenticating the key exchange.

We accomplish our goal by using another type of cryptography called asymmetric encryption. We call it asymmetric since instead of having a shared key, Alice creates a key pair. One part is her secret key (symbolized by a key) that is used for decryption, which she keeps to herself. The other is the public key (symbolized by an open lock) that is she sends to Bob. Now Bob (and anyone else who has the public key) can send messages to Alice that only she can read using her secret key! You can think of the public key as a lock on a message, and the secret key as the key.

Alice and Bob use the OCAKE protocol. To do so, Alice generates a key pair (white key and lock) and shares  her public key (lock) with Bob, using the password ‘ilovefrogs’. Bob recovers the public key, chooses a symmetric key (the black key), that he encrypts to Alice, using her public key. Only Alice can then recover the shared key from the message.

In OCAKE, Alice generates an asymmetric key pair, encrypts it using the shared password, and sends this to Bob. We can think of this step as Alice proving that this public key belongs to her, a process called as authentication. She does this by using the password to do the encryption, as anyone who is not Alice is incapable of encrypting their own public key without knowing Alice’s password.

Since Bob is the only other person to know the password, only Bob can recover Alice’s public key. Bob can then use this to send her a message containing their new shared key. By sending Alice a message that was encrypted to her public key, Bob authenticates himself to Alice. If Bob did not know the password, he would be unable to encrypt his symmetric key under Alice’s public key.

Now both Alice and Bob share a cryptographic key that no one else knows!

Of course, this only works if Eve is unable to break the locks and either of the two messages sent by Alice and Bob. If you want to see how my co-authors and I mathematically proved that this is secure, you can check out our publication, which is access on eprint: https://eprint.iacr.org/2023/1368

TL;DR (Too long, did not read):

To sum it up: the advancement of quantum computing means that to keep our internet secure and future-proof, we need to come up with new encryption schemes and protocols. There are many ways to achieve secure communication, and if you want to use a password to do it, you can use PAKE protocols such as OCAKE.

I am excited to be allowed to work with such a diverse set of researchers and bridge the gap between our research areas.

Images sources: Silvia Ristch.