0
$\begingroup$

I have been doing some research in group and ring signature literature for anonymous signatures. I am trying to find a group signature scheme which provide the following proprieties:

  • Anonymity for the signer
  • The signature can be verified by a generic receiver
  • Output just one signature (I do not want a kind of LSAG Signature Scheme)
  • Signer in the group should be able to create the signature on their own
  • The construction should be based on elliptic curve and should be pairing free
$\endgroup$
11
  • $\begingroup$ If you don't need it to be linkable, then the technical term for what you're looking for is a Spontaneous Anonymous Group signature (SAG). There are many ways to implement a SAG, and a SAG is always one signature. I think you might mean that certain SAGs that you've seen so far are too costly in terms of storage or verification? $\endgroup$
    – knaccc
    Mar 2, 2022 at 9:46
  • $\begingroup$ @knaccc what is the difference between a SAG and a normal ring signature? From what I understand, spontaneity implies there is no group manager, hence it seems like a ring signature (the signer can create an ad-hoc ring on their own and generate a signature under it). $\endgroup$ Mar 3, 2022 at 7:41
  • $\begingroup$ "The construction should be based on elliptic curve" -> what exactly does this mean? Can other primitives (like symmetric key primitives) be used as well? Do you just mean that the public keys have to be EC points? $\endgroup$ Mar 3, 2022 at 8:11
  • $\begingroup$ @meshcollider An EC Schnorr-based ring signature is one way to implement a SAG signature. Another recent method that can achieve this is ZK-STARKS. $\endgroup$
    – knaccc
    Mar 3, 2022 at 10:53
  • $\begingroup$ @meshcollider "spontaneous anonymous group signature" is just a list of requirements. A ring signature is a particular way of achieving those requirements using a half-Chameleon hash that allows each member of the ring to answer a challenge from the prior link in the ring, but being able to 'close' the ring through knowledge of one of the private keys. $\endgroup$
    – knaccc
    Mar 3, 2022 at 11:48

1 Answer 1

2
$\begingroup$

Ring signatures are similar to group signatures, but do not have group managers. Another key difference is that a "ring" can be formed at signing time with whoever's keys you like - you don't have a fixed "group" like in a group signature.

Signatures cannot be "linked" unless you are specifically using a linkable ring signature scheme. Moreover, the signer's identity is hidden in the ring and cannot be identified, by design, just like in a group signature. Most schemes have that verification can be done by anyone (publicly verifiable). And signers can create the ring and sign on their own without anyone else's participation. So this meets all your requirements, ignoring the last (that they are based on elliptic curves).

The first ring signature construction was the one by Rivest, Shamir and Tauman. Their scheme uses RSA keys. Abe, Ohkubo, and Suzuki gave a scheme in which is able to use a mixture of RSA and DL-type keys. Appendix A of their paper shows how you can construct a ring signature with just schnorr signature public keys, which can be adapted to the elliptic curve setting (and use EC-schnorr).

Specifically, let's say each party in the ring has a public key $Y_i = [x_i]G$, and participant $k$ wants to generate a signature on behalf of them all. Let the order of $G$ be $p$, and let $H$ be a hash function whose codomain is $\mathbb{Z}/p\mathbb{Z}$. The signer will choose a random value $\alpha$, and random values $c_i$ for all the other ring members. The signer will then create an "aggregate key" $$ K = [\alpha]G + \sum_{i \neq k} [c_i]Y_i \, . $$

Then, the signer will compute the hash $c = H(Y_0, Y_1, \ldots, Y_n, M, K)$ for message $M$. Compute $$ c_k = c - \sum_{i \neq k} c_i \pmod{p}, $$ so that all the $c_i$ including $c_k$ sum to $c$ (the hash).

Finally, let $s = \alpha - c_k \cdot x_k \bmod{p}$. The signature is $(s, c_0, \ldots, c_n)$. To verify, simply recompute the aggregate key and the hash as follows: $$ K' = [s]G + \sum_i [c_i]Y_i\\ c' = H(Y_0, Y_1, \ldots, Y_n, M, K') $$ and check that $c' = \sum_i c_i \pmod{p}$.

You can see that performing the protocol honestly will let $K' = K$ because $$ K' = [s]G + \sum_i [c_i]Y_i \\ = [\alpha]G - [c_k \cdot x_k]G + \sum_i [c_i]Y_i\\ = [\alpha]G - [c_k]Y_k + \sum_i [c_i]Y_i\\ = [\alpha]G + \sum_{i \neq k} [c_i]Y_i = K. $$

Then verification works regardless of which $k$ was the signer, as required, and anyone can verify the signature given the set of public keys $Y_i$, the message $M$, the signature $(s, c_i)$, and the public parameters $(G, p, E, \ldots)$.

$\endgroup$
5
  • $\begingroup$ WIth this schema, the size of the signature will depend by the number of the entities involved in the ring. I was thinking about the transmission overhead (even adopting a compression technique) in case of N=10, 100, 1,000, 10,000. What do you think about it? $\endgroup$
    – CipherX
    Mar 7, 2022 at 8:57
  • 1
    $\begingroup$ @CipherX the signature grows linearly in the number of participants - you include one public key and one $c_i$ value for each. $\endgroup$ Mar 7, 2022 at 11:00
  • $\begingroup$ exactly...this aspect could be an issue for my scenario, but thanks a lot for your suggestion $\endgroup$
    – CipherX
    Mar 7, 2022 at 11:20
  • $\begingroup$ No problem, you didn't mention you needed a shorter one. You could look up logarithmic size ring signatures, there are some. Anyway please accept my answer if it helped :) $\endgroup$ Mar 7, 2022 at 11:26
  • $\begingroup$ Sure @meshcollider. If you have some suggestions about the logarithmic size ring signatures protocols that are compliant with my requirements, it would be great! $\endgroup$
    – CipherX
    Mar 7, 2022 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.