09/05/2022 02:35

The solution to a cryptographic puzzle

  • Blog Fundamental Science

Bárbara Amaral wants to use quantum physics to reopen an old information security issue

Art: Livia Serri Francoio

By Pedro Lira

Two people choose heads or tails by phone. How do you make sure that no one will cheat? One option is for player number 1 to write his or her choice on a piece of paper, lock it in a safe and send it to player number 2, who flips the coin and only then opens the safe. However, in this scenario, in which the two parties cannot communicate through live images, there is no guarantee that the second player will not break the safe before flipping the coin, falsifying the result in his or her favor.

The example may seem far from a case of digital security, but the analogy explains the research of Bárbara Amaral, a physics professor at the University of São Paulo (USP), and her collaborators, Charles Tresser (National Institute of Pure and Applied Mathematics – IMPA) and Paulo Nussenzveig (USP), who believe they have the solution to an old problem: bit commitment. The scientist argues that she can develop a quantum cryptographic protocol, i.e., a more effective strategy to keep the information exchanged online protected.

Cryptography is the field of knowledge that investigates communication techniques that allow only the sender and the receiver access to a particular message, providing us with more security to make a Zoom call or an online bank transfer. This is possible due to different protocols that keep the system safe. Bit commitment, one of these cryptographic protocols, is a weakness that has haunted researchers in the field for years.

“It is as if these digital security strategies were a jigsaw puzzle composed of several pieces, and bit commitment is a fundamental piece,” explains Amaral. That is, in theory, whoever has a superpowered computer and is able to break that sensitive link can hack several current protocols. “Our plan is to solve this weak point.”

Despite the researcher’s confidence, the challenge is not simple – there is even a consensus that the issue is unsolvable. At the end of the 1990s, two articles in Physical Review Letters, one of the most prestigious journals in the field, showed that even using quantum physics, bit commitment is impossible to circumvent 100%: in the game of heads or tails by phone, one of the two parties always manages to cheat. “These studies brought theorems that closed the subject and reduced the community’s interest in this issue,” recalls Amaral.

Although there are no doubts about the studies, the professor and her team believe that it is possible to circumvent some of the hypotheses presented. “Studying the proofs of the theorems, I found a possible way out: we want to add an auxiliary system to the protocol that will serve to ensure that the party receiving the safe follows the instructions correctly,” she explains. “There may be a stronger correlation between quantum systems than between classical systems, a phenomenon known as quantum entanglement, and it is these correlations that can help us.”

This auxiliary system sent to the second party must be correlated to another system that the first party keeps in its possession. If the second player attempts to cheat, they will destroy these correlations between the auxiliary systems in a way that can be verified by the first player.

In the analogy of the game, it would be like the first person sending two safes, one with their commitment and one with the additional auxiliary system. The party receiving the safe does not know which is which. If they try to break the safe, they will destroy the correlation between the auxiliary system that was sent and the system that stayed with the first player. “It is a daring project, considering that an entire community worked on it for years and could not escape this impossibility. However, if we can solve it even partially, it would be a very significant advance,” Amaral says.

The group needs to show that the theory is feasible in practice. For 2022, the plan is to develop a protocol that works in an ideal scenario and have the case analysis ready and published. “This will cause a boom in the community – even if we find a small flaw in the idea, the result will generate a discussion, inspiring people to return to the topic,” says Amaral. If it works, in about three years the group will begin the experimental implementation in the USP laboratories. “It is in risky projects that lies the science we need to do”, she concludes.”

This text was originally publicated on Serrapilheira’s Ciência Fundamental blog on Folha de S.Paulo

  • Topics
  • cryptographic puzzle
  • Cryptography
  • quantum physics