Sunday, April 15, 2012

Zero Knowledge Proofs and Nuclear Disarmament

On the last (but not least) day of the workshop on Formal and Computational Cryptographic Proofs at the Newton Institute in Cambridge, Boaz Barak gave a talk on a connection between Zero Knowledge Proofs and Nuclear Disarmament. In Cryptography, we usually try to create digital analogs of physical concepts, such as locks and signatures. It was refreshing to see the converse for a change, as Boaz detailed how Zero Knowledge Proofs, a theoretical concept used in Cryptography, could be used in the physical process of verifying that a nuclear warhead is really a nuclear warhead.

The goal of nuclear disarmament is to reduce (and ultimately eliminate) nuclear weapons. Of course, this is only possible if everyone gets rid of their nuclear weapons, which has led to several treaties (mostly between the US and Russia) detailing how many nukes everyone is allowed to keep. This means that they have to get rid of all their other nukes. As trust is in short supply among powerful nations, the concerning nations would like to be able to verify that the others are dismantling their actual nuclear warheads, rather than dummy warheads. However, no one wants to allow the others to look too closely at their warheads, lest they steal the top-secret design.

To verify that a warhead is an actual nuke of a given design, the US picks a random warhead of the same design as a template (to prevent Russia from giving them a dummy template) and perform measurements to see if they are equivalent. It turns out that even seemingly innocuous measurements leak information about the design of the warheads. This has led to the intuition that "such measurements are useful and must therefore contain sensitive information".

As a result, the current approach uses a so-called information barrier: they put both warheads in a black box. This black box then compares the two by performing some measurements and outputs yes/no depending on whether the warhead is equivalent to the template warhead, without revealing any information about the design of the warheads. However, this information barrier approach is very cumbersome, because both parties need to be heavily involved in the design and construction of this black box.

So how can one work around this intuition of measurements containing sensitive information? This is exactly the problem that Zero Knowledge Proofs in Cryptography attempt to address! So all they need is a "physical" zero knowledge proof. How can this be done? Boaz first described a "cartoon version" of their proposed protocol. In this protocol, the Russian Anastasia has two pouches that contain x ∈ [0, n) marbles and she wants to prove to the American Bob that her pouches both contain the same number of marbles, without Bob finding out how many marbles she was storing in her pouches. She proves this using the following steps:

1) Anastasia prepares 10 pairs of buckets by putting a random number Ri ∈ [0,N) of marbles in both buckets of pair i and presents the buckets to Bob.

2) Bob chooses 9 pairs and verifies that for each pair, both buckets contains the same number of marbles. He returns the remaining pair of buckets to Anastasia without counting the number of marbles inside.

3) Anastasia empties one bucket in both of her pouches and presents them to Bob.

4) Bob verifies that both pouches contain the same number of marbles.

As Boaz mentioned, this would be very useful if both nations wanted to eliminate their stockpiles of marbles, but they are working with nuclear warheads instead. So how can you compare two warheads? It turns out that if you set up detectors around a warhead and fire neutrons at it, you will be able to measure a predictable pattern (according to computer simulations). However, knowing the full pattern would once again give you information about the design. Thus, they only measure certain random positions around the warheads and compare the number of neutrons here. The computer simulations suggest that the number of neutrons measured in a certain position should be roughly equal for both warheads. Still, this number might give away information as well. Anastasia and Bob will therefore go through the following protocol to hide this:

1) Anastasia prepares 10 pairs of neutron detectors by shooting a random number Ri ∈ [0,N) of neutrons at both detectors of pair i and presents the detectors to Bob.

2) Bob chooses 9 pairs and verifies that for each pair, both detectors have measured the same number of neutrons. He returns the remaining pair of detectors to Anastasia without reading out the number of measured neutrons.

3) Anastasia puts the detectors in the appropriate positions near the nuclear warheads and lets Bob fire neutrons at them.

4) Bob verifies that both detectors have measured the same number of neutrons.

The number of measured neutrons in the real protocol correspond to the marbles in the cartoon protocol. For both protocols Anastasia can cheat with probability no more than 90% (which can be increased by increasing the number of buckets/detectors). Furthermore, the protocols are ε-Zero Knowledge, where ε is non-negligible. This means that Bob does learn a fraction ε about the distribution of the actual measured neutrons (although ε can be improved by increasing N). Boaz noted that this ε could further be reduced if some extra physical assumptions were made about the warheads but that other info was going to leak in this case.

Boaz also mentioned that experiments will start in a few months, noting that "if it works for coffee makers it will probably work for nuclear warheads". In the rest of the talk, Boaz answered questions about possible issues with the protocol. For example, Nigel suggested that these warheads might actually behave like Physically Unclonable Functions (PUF), in contrast to what the simulations suggest. On a positive sidenote, this would mean that they discovered a new version of PUFs. In conclusion, Boaz said that their work is only one component of a much larger process and it is exclusively based on unclassified information. Thus, he concluded that while many questions and concerns remain, it is interesting to apply theoretical cryptographic constructs in the physical world.

No comments:

Post a Comment