STORY OF THE MONTH

LOST IN CRYPTOGRAPHY

Jun 2024

Álvaro Yángüez Bachiller

In which world do we live? It is the non-existential question that a cryptographer wonders about every month (or even every night). Maybe our cryptographer is having a tough day, but he does not want to meditate about the nature of the world surrounding him, he just wants to develop a new cryptographical protocol. And in both cases, he will find no answer.
Symmetric cryptography, asymmetric cryptography, public key encryption, Key Exchange, Key Encapsulation Mechanism, Quantum Key Distribution. Many options, many functionalities. Is our cryptographer blaming his field? Is he lost in a chaotic sea of protocols? No, do not worry for his mental health. We have seen different kinds of protocols during the last months. We have delved into the post-quantum world of Public Key Encryption with Silvia, Fabrizio and Gina. We have also explored the Quantum world with Alessandro, Vaisakh, Javier, Matías and Sergio. Does our cryptographer want to know if he is in a classical or a quantum world? No, he already knows the answer. We live in a world in which quantum physics applies to nature.

So, what does this question mean for a cryptographer? In 1995, Russell Impagliazzo described five possible cryptographic worlds in which we could live, with different complexity assumptions. These worlds have clear and self-contained hardness assumptions. For example, if we live in Cryptomania, then Public Key Encryption is possible, while in Minicrypt, we only assume the existence of One-way functions. One-way functions are functions that are easy to compute in one direction but difficult to do it in the opposite one.

Impaglazzo’s possible worlds.

Then, the higher our cryptographer is in the inverted pyramid, the more complex the protocols he can implement by making harder assumptions. How does this structure relate with what we have seen so far? Most of the post-quantum protocols we have seen in the previous months were based on public key encryption. This means that our cryptographers build their protocols given the hardness of a specific problem that lies in Cryptomania. In the case of the quantum key distribution (QKD) protocols, the story is different. If our cryptographer wants to build a QKD protocol, he just needs to implement an authentication protocol that could be in Minicrypt before the key exchange starts. Once he has done this, he has everlasting security thanks to the laws of quantum mechanics.

Why is not our cryptographer making every protocol quantum? Indeed, he is tempted to do so, but he discovered that he cannot translate every classical cryptographic functionality into a pure quantum one. He needs to take complexity assumptions; he must decide again in which world he lives. Oh no, here we go again! – claimed our cryptographer.

Multiparty computation functionality.

Nevertheless, our cryptographer can use the best of both worlds. In 2021, Grilo et al and Bartusek et al, proved that multiparty computation (MPC) is possible to implement in Mini(Q)crypt if we use quantum resources as a subroutine. This is a clear advantage with respect to the pure classical case, in which MPC is in Cryptomania. MPC is a very versatile primitive in cryptography in which many parties want to collectively compute a function on their private inputs, while maintaining them secret. In this project, my goal is to provide an implementable MPC protocol in Mini(Q)crypt.

Impagliazzo, R., “A personal view of average-case complexity”, Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference, Minneapolis, MN, USA, 1995.

Bartusek, J, Coladangelo, A., Khurana, D., Ma, F., “One-Way Functions Imply Secure Computation in a Quantum World”, Cryptology ePrint Archive, 2021.