Having read some papers about RSA accumulators applied to ring signatures schemes, I ended up thinking why would we need to accumulate all the members public keys for our specific use case.

So I came up with a scheme, but have the feeling that there is either an obvious flaw that I cannot see or it is (a variant of) something well known, or there is a obvious simpler way of achieving the same.

The hypothesis is that this a valid ring signature (with no member revocation: we either add a new member, or invalidate whole the group and force members to join a new one):

  • User cannot create valid signatures without being registered in the group.
  • Server cannot identify the specific user who sent the message nor link together messages sent by the same user (the latter with some exceptions in bonus).

Assume we work in the group of quadratic residues modulus $n$ (RSA accumulator).

The modulus $n$ and generator $g$ are chosen by the server (non-trusted) and are unique per group. AFAIK the server can provide a NIZKP that modulus $n$ is a product of two big enough safe primes, and user can check that $g$ is indeed a generator of QR mod $n$ cyclic group.

  • Join a group: user chooses a random prime $e$ and sends it to the server. Server returns a witness $w = g^d$ such that $w^e = g$ (so $e \cdot d = 1$ mod hidden QR group order).
  • Sign a message: user performs a NIZKP (http://www.cs.nyu.edu/~dodis/ps/subring.pdf) that she knows a value $w$ such that $w^e = g$ (without revealing anything about w or e, nor showing any value that the server can use to link different messages from her together).

Bonus (if the previous scheme is correct): assume prime $e$ chosen by the user has the form $(e - 1)/2 = e_1 \cdot e_2$, with $e_1, e_2$ big enough, far enough from each other primes. We can extend the NIZKP to show that we know $e_1$, $e_2$ such that $e = 2 \cdot e1 \cdot e2 + 1$ and provide $digest(M)^{e_1 + e_2}$ (https://eprint.iacr.org/2004/281.pdf), where $digest(M)$ is some mapping from the message to a generator of the quadratic residues modulus $n$. We can specify this mapping in such a way that we can identify two messages sent by the same user under some circumstances (e.g. repeated message in a given time span), because $digest(M)^{e_1 + e_2}$ will be the same for those messages.

Are there any obvious flaws in the scheme? Is it known (any references)?

  • $\begingroup$ That's not a ring signature scheme, since it requires that the server respond to potential signers. $\hspace{.48 in}$ $\endgroup$ – user991 May 25 '17 at 7:11