World's first demonstration of bit commitment performed at CQT

How can Alice submit a sealed bid to Bob without needing to trust him (or watch him all the time)? Quantum technology can do it, CQT researchers show in a paper published in Nature Communications.

Who needs trust? Computer scientists and quantum optics researchers at CQT have collaborated to perform the world's first demonstration of secure bit commitment: a communication system for people who don't trust each other.

The work by the groups of Principal Investigators Stephanie Wehner and Christian Kurtsiefer was published in Nature Communications on 27 December. The team used hundreds of thousands of entangled photon pairs in the demonstration.

Many scenarios in business and communication require that two parties share information without either being sure if they can trust the other. Examples include secure auctions and identification at ATM machines. In general such problems are known as two-party cryptographic problems. 'Bit commitment' is a simple protocol that can serve as a building block for solving more complicated two-party problems.

Bit commitment is similar to submitting a sealed bid in a house auction. One party, usually known as Alice, 'commits' some information (a bit) to another party, usually known as Bob, with Alice later choosing when to reveal the committed bit. A bit commitment protocol is secure if Bob can't learn anything about the bit until Alice reveals it, and if Alice can't change the bit between committing and revealing it.

Compare the situation with a sealed-bid auction: the bidder must commit to an amount they will pay, and they should remain the only one who knows what the amount is until all the bids are opened. This is desirable, because a dishonest auctioneer or anyone who accessed the information early could influence the bidding. At the same time, we want to make sure that the bidder cannot change the bid depending on any news he receives later on. This means that we cannot simply solve the problem by allowing the bidder to keep hold of their bid, because they might be dishonest and change the amount.

Traditional solutions to such a problem — think sealed envelopes or data held by a third party — always depend on trust. Indeed, it has been proven that with classical communication alone there is no solution that can totally protect the bidder and the bid receiver from unscrupulous behaviour.

In the new demonstration, the researchers harness some of the strange behaviours of the quantum world to guarantee secure bit commitment. Even quantum effects aren't enough on their own: the protocol depends on the assumption that the cheating party is limited to some degree.

In earlier papers, Stephanie introduced and developed the idea of the dishonest party being limited by 'noisy storage' for quantum information. It is a realistic, physical assumption to make: that the dishonest party has a memory of finite size, which is subject to noise that can introduce errors in any stored information. The papers made various theoretical proposals for how to do secure bit commitment under these conditions.

Christian Kurtsiefer's group at CQT had built this table-top apparatus for creating entangled photon pairs. Entangled photons enable the bit commitment.

"I wanted to demonstrate that it can work in the real world, and to gain insight into the challenges to security in such a setting," says Stephanie. Having Christian's group at CQT made this possible: the group has an entangled photon source and detection kit used for previous quantum cryptography demonstrations that was readily adapted.

In the experiment, Alice and Bob used 250,000 pairs of entangled photons to commit a single bit. This vast number of photons is needed to counter losses in the experiment and guard against the possibility of cheating.

Deciding on the strategy took much theoretical work, since the original protocols could not tolerate nearly enough errors. The team thought they'd need even more photons until coming up with a new theoretical tool for proving security, published earlier.

Alice encodes her committed bit in the photons by choosing one of two possible measurements for each photon she receives. The other half of each photon pair is sent to Bob to measure. Because the photons are entangled, Bob's results will match Alice's when he picks the right measurement type, but be random when he picks the wrong one. The idea is that Bob ends up seeing enough of the 250,000 bits to decide whether Alice has tried to cheat when she reveals her committed bit by sending the whole lot over, but not enough that he can guess the bit beforehand.

The noisy storage comes in because Bob could cheat perfectly if he could store all the photons until Alice told him about her measurement choices (an intermediate step in the protocol). He could then repeat the measurements exactly, revealing the committed bit early.

Today it's only possible to store a handful of qubits, and the CQT researchers showed that their 250,000 photon exchange would be secure against a memory of 972 qubits suffering a certain noise. If quantum memories get bigger, security could be restored by increasing the waiting time or boosting the total number of bits sent.

The collaboration of computer scientists and experimentalists was not without challenges — "some of the common experimental terms I used turned out to have very specific and different meanings in theoretical computer science," says Siddarth Joshi, a PhD student in Christian's group, but he found it rewarding overall. "Theoretical protocols currently outstrip experimental capabilities by several decades and if I am to live to own a quantum laptop, these kind of collaborative efforts are a must," he says.

CQT Research Assistant Nelly Ng Huei Ying presented the bit commitment work in August at the 11th International Conference on Quantum Communication, Measurement and Computing in Vienna, Austria.

"It's really cool that it worked — we achieved security on a practical level!" says Nelly Ng, who became involved in the project while still an undergraduate at Nanyang Technological University. She has since graduated (with two awards) and is now a Research Assistant in Stephanie's group.

Practical in a lab setting, that is. To commercialise the system would require boosting the bit rate, among other improvements. Alice and Bob exchanged the 250,000 photons required to commit a single bit in a little over 10 seconds, then mathematical processing of the data took many times longer. To make the bit commitment fast will require more efficient ways to crunch the data and exchange details.

For more details, see "Experimental implementation of bit commitment in the noisy-storage model" Nature Communications doi:10.1038/ncomms2268 (2012); arXiv:1205.3331.