Eurocrypt 2015: Nobody Should Know What You Bought Last Summer

It has emerged that Bitcoin does not really live up to the promise of anonymous transactions because the transactions can be linked publicly. While there are mixers that offer to break this link (but sometimes simply steal your money), it would be desirable to have unlinkability built in to a crypto currency. The challenge here is the following: If the transaction graph is public as it is in Bitcoin, it is easy to find the predecessor of a new transaction to check its validity. For real anonymity, one has to be able to prove that one knows the secret key of one of the existing transaction without revealing which one.

Jens Groth presented such a scheme at his talk. More technically, the scheme allows to prove that one out of a list of Pedersen commitments hides zero. Recall that Pedersen commitments are homomorphic with respect to a group operation both for the secret and the randomness. This makes them particularly suited for the so-called Sigma protocols, which consist of three rounds and can be made non-interactive in the random oracle model by hashing the first message to get the challenge. Furthermore, they offer special soundness, that is, one can extract the secret from a number of correct answers to different challenges, and special honest-verifier zero-knowledge, which means that the protocol can be simulated without knowing the secret if the challenge is chosen independently of the first message.

In summary, they authors propose a Sigma protocol to prove that one out of $N$ Pedersen commitments hides a zero. It provides computational $(\log N + 1)$-soundness and logarithmic communication. The core idea is to understand the $N$ commitments as the leaves of a binary tree and then let the prover commit to the bits of the path to the commitment he knows. This allows to obliviously compute a commitment of the secret known to the prover from the list of commitments. The communication is logarithmic in the size of the list because it is already known to the verifier. On the downside, the verification complexity still is linear in the list size, which seems to be inherent to the problem.

The paper can be found on ePrint.