Score:0

Anonymous Group Signature

il flag

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
knaccc avatar
es flag
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?
meshcollider avatar
gb flag
@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).
meshcollider avatar
gb flag
"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?
knaccc avatar
es flag
@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.
knaccc avatar
es flag
@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.
meshcollider avatar
gb flag
@knaccc I disagree, ring signatures are a general class of construction, and the one you're referring to is just a possible instantiation.
knaccc avatar
es flag
@meshcollider Perhaps I can generalize a little more and define a ring signature as a ring of challenges and responses, where only the holder of one of the private keys is capable of joining the ring together to form a valid signature. This is a different approach than a SAG based on accumulators or some other substantially different zero-knowledge proof approach that does not involve a ring of challenges and responses. I'm not clear about how you'd define and differentiate SAGs vs ring signatures.
CipherX avatar
il flag
@meshcollider if a generic receiver should be able to verify the signature I don't know how can is it possible to do that with a symmetric key (you need a key agreement like DH before, or you need to know what is the symmetric key used to do that). But, if you have a protocol in mind that can be good for my use case, please let me know.
knaccc avatar
es flag
@meshcollider Btw I located the reference for my terminology: "Some other works in the literature also call this kind of signature ‘Ring Signature’ although some of them may not have a ring structure for their construction. In alternative terminology, we call this kind of signature ‘Spontaneous Anonymous Group (SAG) Signature’ as they fulfill SAG properties regardless of the construction structure" (https://eprint.iacr.org/2004/027.pdf Page 2). So by the stricter definition, AOS signatures are not ring signatures, they are 1-out-of-n signatures or spontaneous anonymous group signatures.
meshcollider avatar
gb flag
@knaccc Thanks! Btw, AOS refer to their third step (of computing $s = c - ax$) as "forming the ring" so even by the stricter definition, I'd still consider them to be ring signatures :)
knaccc avatar
es flag
@meshcollider When AOS talk about "forming the ring", they really are forming a ring because each challenge depends on the prior link in the ring. So you're right that AOS signatures are ring signatures. The confusion was that the answer you gave is not the same construction as that mentioned in the paper where they talk about forming the ring. The Appendix A version is "non-separable" in their terminology, and not based on a ring.
Score:2
gb flag

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)$.

CipherX avatar
il flag
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?
meshcollider avatar
gb flag
@CipherX the signature grows linearly in the number of participants - you include one public key and one $c_i$ value for each.
CipherX avatar
il flag
exactly...this aspect could be an issue for my scenario, but thanks a lot for your suggestion
meshcollider avatar
gb flag
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 :)
CipherX avatar
il flag
Sure @meshcollider. If you have some suggestions about the logarithmic size ring signatures protocols that are compliant with my requirements, it would be great!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.