GK15-Ring Signature

1Homomorphic Commitment Scheme

We will want the commitment scheme to be homomorphic, which means that the commitment space is also a group (written multiplicatively) and we have for all well-formed commitment keys and and that

2-protocol for commitment to 0 or 1

By the homomorphic property of the commitment scheme is a commitment to , which is 0 if . With this in mind, it is straightforward to verify that the -protocol is perfectly complete.

3-protocol for one out of commitments containing 0

We will give a -protocol for knowledge of one out of commitments being a commitment to 0 . More precisely, we will give a -protocol for the relation

Fig. 2 gives the full -protocol for with being the key generation algorithm for the commitment scheme and running on , , and such that . Without loss of generality we assume .

To explain the idea behind the -protocol let us for simplicity assume the commitment scheme is perfectly binding such that each commitment has a unique committed value.

Saying that one of the commitments contains 0 is equivalent to saying there exists an index such that is a commitment to 0 , where is Kronecker's delta, i.e., and for .

We can always copy some commitments in the statement, so let us without loss of generality assume

Writing and in binary, we have so we can reformulate what we want to prove as being a commitment to

The prover will start by making commitments to the bits . She then engages in parallel -protocols as described above to demonstrate knowledge of openings of these commitments to values

In the -protocols for the prover reveals of the form

Let and

Then we have for each that the product is a polynomial of the form

The idea is now that the prover in the initial message will send commitments that will be used to cancel out the low order coefficients corresponding to .

Meanwhile the high order coefficient for will guarantee the commitment can be opened to More precisely, the verifier will at the end check that

is a commitment to 0 , which by the Schwartz-Zippel lemma has negligible probability of being true unless indeed is a commitment to 0 .

Theorem

The -protocol in Fig. 2 for knowledge of one out of commitments opening to 0 is perfectly complete. It is (perfect) -special sound if the commitment scheme is (perfectly) binding. It is (perfect) special honest verifier zero-knowledge if the commitment scheme is (perfectly) hiding.

To see that the -protocol is complete observe that is a polynomial in the challenge of the form . When is a commitment to 0 we therefore get that in the verification equation is a commitment to 0, while the other commitments get raised to polynomials of degree in as in the verification equation. With this in mind straightforward verification shows that the -protocol is perfectly complete.

4Ring Signature

Theorem

The scheme (Setup, KGen, Sign, Vfy) is a ring signature scheme with perfect correctness. It has perfect anonymity if the commitment scheme is perfectly hiding. It is unforgeable in the random oracle model if the commitment scheme is perfectly hiding and computationally binding.

Instantiation with Pedersen commitments

The Pedersen commitment scheme is a natural candidate for the commitment scheme. When our ring signature scheme is instantiated with the Pedersen commitment scheme, the public keys are of the form , i.e., they are single group elements and the corresponding secret keys are the discrete logarithms.

The instantiation with Pedersen commitments requires a simple setup that is realistic in many settings. Consider any organization where a standard group is used for all users and their secret keys are discrete logarithms of public group elements. The ring signature easily fits on top of this setup.

The ring signature scheme yields small signatures. The signature size is logarithmic in the number of ring members and instantiated over a compact group where elements have size it is bits. This compares favorably with all previous ring signature schemes.

The signer does exponentiations to generate a ring signature and the verifier uses exponentiations to verify a ring signature. However, when the same ring is used many times or there is significant overlap between different rings, the cost of verification can be reduced to multiplications in by batching the verification of many signatures.