Keeping a Secret for a Whole Day
During the Oscars ceremony, the presenter receives a sealed envelope, so that neither the Oscar voters nor the presenter can tamper with the results once the choice has been made. A team of physicists has now demonstrated a system that provides similar security in the case of a single bit of information chosen by one party and revealed, 24 hours later, to another. The technique greatly extends the time during which the selected bit remains secure and has potential applications where high security is required, such as in auctions or electronic voting.
Researchers have given the name “bit commitment” to methods where Alice, say, wants to select a bit and send her choice to Bob without immediately revealing it. Alice wants to prevent Bob from “opening the envelope” too early, and Bob wants assurance that Alice did not change the bit after her initial choice.
Almost 30 years ago, theorists proposed bit commitment techniques in which Alice and Bob each control two agents at different locations: Alice’s first agent, A1, is near Bob’s agent B1, while A2 and B2 are close to each other but at some distance from A1 and B1. In order to place the bit in the “envelope,” A1 first receives a random binary number from B1 and then algebraically combines that random number with a secret number of the same length in a way that depends on the value of the committed bit. A1 then sends the result back to B1. Next, Alice reveals the committed bit along with the secret number by having A2 send them to B2, who then checks with B1 to make sure that the revealed information is consistent with the earlier encrypted number sent from A1 to B1.
The physical separation between A1/B1 and A2/B2 means that it takes at least half the light-travel time between those locations for Bob’s agents to combine their information and perform the verification. During that period—the commitment time—Bob cannot be sure of the committed bit, and Alice cannot change it faster than Bob can verify it. For two locations on Earth, the maximum commitment time with such a scheme is about 20 milliseconds. The method is equally secure against corruption or exposure by a third party, who would have to correctly guess the binary numbers used by Alice and Bob.
In 1999, Adrian Kent of the University of Cambridge devised a way to increase the commitment time [1]. In his scheme, rather than a single exchange between A1 and B1 at the start, there is a sequence of carefully timed exchanges, or “rounds,” involving first A1 and B1, then A2 and B2, then A1 and B1 again, and so on. The mathematical algorithm for combining numbers is such that, assuming Bob is honest, he can learn the committed bit from the results of the exchanges only after receiving the result of the final round. And he can also figure out at the end if Alice’s agents changed the committed bit at any time during the exchanges. The separation between the two pairs of agents is required because either side could cheat if an agent at one location could learn the results of the previous round at the other location before initiating the next exchange.
To guard against either side in Kent’s scheme correctly guessing the random numbers involved in the operations, the length of the binary numbers exchanged has to increase exponentially with each round. Researchers succeeded last year in implementing a version of this method, carrying out six exchanges between locations in Geneva and Berne, 131 km apart, and achieving a commitment time of 2 milliseconds [2]. Shortly afterward, however, re-analysis of the protocol showed that the minimum number length required for security increases only slowly with the number of rounds [3].
Capitalizing on that insight, Anthony Martin and his colleagues at the University of Geneva have now demonstrated a 24-hour commitment time in an experiment where the distance between A1/B1 and A2/B2 was just 7 km. Each agent was a dedicated computer communicating with others through standard links. Five billion exchanges of 128-bit numbers (longer than the minimum secure length) occurred during the 24-hour period. In principle, the team says, the same method could achieve a commitment time of a year with a 10,000-km separation.
An obvious application, Martin says, is electronic voting, where practical bit commitment techniques would give confidence to both voters and election authorities. “I congratulate the authors on the technological implementation,” says Kent. “I look forward to new, practical applications.”
This research is published in Physical Review Letters.
–David Lindley
David Lindley is a freelance science writer in Alexandria, Virginia.
References
- A. Kent, “Unconditionally Secure Bit Commitment,” Phys. Rev. Lett. 83, 1447 (1999).
- T. Lunghi, J. Kaniewski, F. Bussières, R. Houlmann, M. Tomamichel, S. Wehner, and H. Zbinden, “Practical Relativistic Bit Commitment,” Phys. Rev. Lett. 115, 030502 (2015).
- K. Chakraborty, A. Chailloux, and A. Leverrier, “Arbitrarily Long Relativistic Bit Commitment,” Phys. Rev. Lett. 115, 250501 (2015); S. Fehr and M. Fillinger, “On the Composition of Two-prover Commitments, and Application to Multi-round Relativistic Commitments,” in Advances in Cryptology-Eurocrypt 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part II (Springer, Berlin, 2016), p. 477-496[Amazon][WorldCat].
More Information
Demonstration of a single-exchange protocol relying on quantum communication techniques that achieved a commitment time of 15 milliseconds: Focus: Information Exchange for the Mistrustful