Google DeepMind formally verifies Signal protocol security with AI
Google DeepMind used AlphaProof Code to formally verify Signal's post-quantum handshake and Triple Ratchet, marking a first for AI-assisted cryptographic proof.
Photo: 9to5MacKey points
Google DeepMind used AI to formally verify the security of Signal's messaging protocol, proving its cryptographic guarantees under all conditions.
Google DeepMind researchers have completed a formal verification of Signal's messaging security, marking what they claim is the first time AI has helped devise a proof that links protocol-level security guarantees to a widely used cryptographic implementation. The analysis, conducted in four weeks, validated the design of libsignal's forward secrecy, authentication, post-compromise security, and handshake secrecy. The work was described as "a landmark development" and serves as further independent validation of the cryptography protecting communications on Signal, WhatsApp, and Google Messages.
Formal verification is the term given to mathematically proving or disproving that a cryptographic algorithm or protocol satisfies its security claims under all conditions. It guarantees that there is no situation in which the protocol will fail. This is a far higher standard than traditional testing methods, which seek to find vulnerabilities but cannot promise that others do not exist. The DeepMind analysis did not find any new vulnerabilities in the portions of the Signal protocol it looked at.
What was verified
The researchers used AlphaProof Code, a multi-agent framework for formal software specification and verification. AlphaProof Code relies on a human-guided agent that writes a Lean specification, assesses machine code semantics, and crafts an agent-authored proof that the Lean kernel checks against the specification. In this instance, it verified Signal's post-quantum PQXDH handshake and Triple Ratchet. The team included Swarat Chaudhuri, Andrew Ferraiuolo, Anton Kovsharov, Tej Chajed, Sam Schlesinger, Karn Seth, Jonathan Katz, Charles Sutton, and Pushmeet Kohli.
The AlphaProof Code process involves working with various models to turn Signal's security goals into a human-reviewed mathematical specification. Based on this spec, the researchers assigned Gemini Carbon agents to generate Lean code proving the correctness of the libsignal implementation. After the agents generated 6.5 million lines of Lean code, they undertook an auditing pass and flagged bits that required human review. The result is theoretical in that it assumes perfect cryptography and doesn't guarantee the computational secrecy of bytes, but it's still a meaningful assertion of correctness.
"It's a system that is fundamentally built for human AI collaboration," said Swarat Chaudhuri, research scientist at Google DeepMind and a professor at the University of Texas at Austin, in $1. Traditionally, you start proving theorems with well-defined problems formulated by a mathematician that get submitted to an AI agent for proof. In this case, the researchers had to figure out what to prove. "In formal methods, we always had this belief that verification is the hard bit," he said. "There's thirty or forty years of work on how to scale up verification."
How the proof worked
The work takes a step toward a challenge the Beneficial AI Foundation issued in April to formally verify the Signal protocol and Signal app with Lean. The researchers are releasing the specification and proof they developed for the Signal protocol analysis to aid other formal verification work. When tested against older versions of Signal that contained known vulnerabilities, AlphaProof Code identified those and flagged them as failing formal verification. This demonstrates the tool's ability to catch real-world flaws.
Formal verification used to require heroic efforts. Formally verifying the seL4 microkernel took 20 person-years, while developing the verified CompCert C compiler took six years. AlphaProof Code, the researchers believe, can drastically reduce the cost of formal verification, though their Signal work still took four weeks for a team of five people and "quite a few tokens." The scale of resources required has not yet been disclosed.
"We are very excited by this result, but there is a long distance to go before we are able to scale this to all the software of the world, and we want to do that," Swarat Chaudhuri tells WIRED. The open question across the tech sector is whether AI-automated formal verification can truly scale—and whether it can do so at a workable cost. DeepMind conducted the Signal analysis free of charge as a research project, and Google declined to share the cost of the analysis. The company also declined to comment on whether it has plans to release a commercial formal verification product or service.
Limits and next steps
The researchers emphasize that some of their crucial advancements are in developing a "human-AI collaboration process," as Chaudhuri puts it, that allows agents to contribute and self-correct at almost every phase of the process while still seeking human input and review at key junctures. "We don't want this sort of vibe world where AI is generating the goals and AI is generating the proofs and basically taking tests that are self-written," Chaudhuri says. "There's a middle ground."
Pointing to a related DeepMind project, AlphaProof Nexus, which is focused on mathematics, Chaudhuri said the next step is to apply this technology during the software design process—not just to cryptographic protocols but code in general. "We really believe that the next frontier is not going to be proof but specification in this kind of research," he said. "And so that's why we took on this domain where that was actually a hard problem. And I think that we have some really good insights now about how to go about this, although not the last word by any means."
For critical services used in high-stakes settings, it would be a dream to be able to formally verify every code base and entire software supply chains. "If you can now verify the correctness of these implementations, then you can rest easy," says Pushmeet Kohli, chief scientist at Google Cloud and DeepMind's vice president of research. "You can imagine banks, imagine all those other companies who rely on assurances and who worry about bugs who could now say, 'I can prove these properties.'"
Frequently asked questions
What did Google DeepMind formally verify about Signal?
Google DeepMind used AlphaProof Code to formally verify Signal's post-quantum PQXDH handshake and Triple Ratchet, proving the protocol's security guarantees under all conditions. The analysis covered libsignal's forward secrecy, authentication, post-compromise security, and handshake secrecy.
How long did the formal verification take?
The analysis took four weeks and involved a team of five people. The agents generated 6.5 million lines of Lean code. The scale of resources required has not been disclosed.
Did the verification find any new vulnerabilities?
No, the DeepMind analysis did not find any new vulnerabilities in the current Signal protocol. However, when tested on older versions with known flaws, AlphaProof Code correctly identified them and showed they failed formal verification.


