Identity Hiding Ring Signature Zero Knowledge Proof

Back in 2018, a few friends and me had the idea of creating a platform to privately and confidentially share pictures in a similar style to Snapchat. One of the problems we encountered was to make sure that each user could download a picture only once while keeping as little information about users at possible. We didn’t want to simply store which user had downloaded which file since we considered that to be “strongly compromising” metadata so we had to find another solution to solve that problem.

WARING: The scheme that I present below has not received any research regarding it’s security from the cryptographic community and I din’t even bother to write a security proof, so you should NEVER use it in any way except for research purposes.

Part 1: The partys involved

Sadly, these are not the kind of partys where everyone get’s drunk and has a good time. Instead, the three partys we are talking about are meant to represent two users and a server (they are still fun to work with, I promise).

  • Alice has a picture she want's to share.
  • Bob(s) are the people Alice want's to share the picture with
  • Dave is a server which can store the picture and controls who downloads it

For Dave to be able to control who accesses Alice’s picture, each Bob has his own private key xix_i and the corresponding public key Pi=xiGP_i = x_i G, where GG is the generator curve of an elliptic curve. These public keys are known by every party.

We also trust Dave to dutifully perform the checks we tell him to do and only allow people who pass these checks to download the picture. However, we believe that Dave might tell advertisement companies and surveillance agencies who download’s which picture, which we want to prevent.

Part 2: Monero RingCT

My solution is heavily based on the Monero RingCT linkable ring signature, which is used to increase the privacy of the Monero cryptocurrency. That’s why I’m going to describe it first:

Let’s pretent we are a Bob wanting to create a ring signature. We of course know our own private key, let’s call it xx and the corresponding public key. We are also given a bunch of public keys from all kind of Bobs, let’s call them P1,...,PnP_1, ..., P_n.

The linked paper also introduces so called key images which stay’s the same across multiple ring signatures, thereby allowing to determine if two signatures where signed by the same signer without revealing the identity of the signer. You can think of it as a hash which of the private key of the signer. These key images are calculated using the formula I=xHp(xG)I = x H_p(xG).

To sign, we first identify the index called jj of our own public key, so that Pj=xGP_j = xG. After that, we generate a bunch of random values and store them in α\alpha and s1,...,sns_1, ..., s_n.

This allows us to calculate the first challenge cj+1=H(m  αG  αH(xG))c_{j+1} = H(m\ ||\ \alpha G\ ||\ \alpha H(xG)). We can now use the initial challenge to calculate the rest of the challenges ci=H(m  siG+ci1Pi  siHp(Pi)+ci1I)c_i = H(m\ ||\ s_iG+c_{i-1}P_i\ ||\ s_iH_p(P_i)+c_{i-1}I) for i=j+1,...,n,1,...,ji = j + 1, ..., n, 1, ..., j. After that, we set sj=αcjxs_j = \alpha - c_j * x and (c0,I,s1,...,sn)(c_0, I, s_1, ..., s_n) is obviously a ring signature, right?

Well, I don’t expect you to understand these ring signatures that quickly. If you really want to understand how they work I can highly recommend taking pen and paper and going through one example and then try to “forge” a signature using a wrong private key etc. To get a more intuitive understanding of how this signature works, imagine having a chain of padlocks that require a key to open and to close. If you would have the key of the padlock at the end of the chain, you could open that padlock and use it to make a loop of padlocks. Some else, who would see the loop of padlocks would have no idea which padlock is yours, but could still know that you own one of the keys since you managed to create that loop.

Part 3: Increasing privacy even further

Right now, the ring signature provides anonymity for the party creating the signature, so that everyone taking a look at a signature can not determine who signed it. However, to verify such a signature one has to know every public key in the group. In the picture-sharing scenario this means that Dave may not now who currently is downloading a picture, but he still knows who is allowed that picture, which still is a threat to privacy since that information could show that Alice and Bob are friends etc. So we also want to hide the identity of the people allowed to download a picture.

To do so, Alice needs to do a little more work than before when uploading a picture:

  1. Alice creates a random temporary masking key mm and calculates M=mGM = mG
  2. Alice calculates the masked public keys Vi=mPiV_i = mP_i
  3. Alice uploads the picture alongside the masked pubic keys V1,...VnV_1, ... V_n and the public maksing key MM to Dave.

There is also a bit of communication between Dave and Bob when downloading a picture:

  1. Dave sends the masked keys (M,V1,...,Vn)(M, V_1, ..., V_n) to Bob
  2. Bob find's it's index jj with Vj=xMV_j = xM and calculates I=xHp(xVj)I = x H_p(xV_j)
  3. Bob generates random α\alpha and s1,...,sns_1, ..., s_n
  4. Bob calculates cj+1=H(αM  αHp(xM))c_{j+1} = H(\alpha M\ ||\ \alpha H_p(xM)) and ci=H(siM+ci1Vi  siHp(Vi)+ciI)c_i = H(s_i M + c_{i-1} V_i\ ||\ s_i H_p(V_i) + c_i I) for i=j+1,...n,1,...,ji = j + 1, ... n, 1, ..., j
  5. Bob sets sj=αcjxs_j = \alpha - c_j * x
  6. Bob sends (I,c1,s1,...,sn)(I, c_1, s_1, ..., s_n) to Dave

To verify the signature, Dave now only has to perform the following the steps:

  1. Check if II has already been used before for the picture.
  2. Calculate ci=H(siM+ci1Vi  siHp(Vi)+ciI)c_i = H(s_i M + c_{i-1} V_i\ ||\ s_i H_p(V_i) + c_i I) for i=2,...,ni = 2, ..., n
  3. Check if c1=H(s1M+cnV1  s1Hp(V1)+cnI)c_1 = H(s_1 M + c_n V_1\ ||\ s_1 H_p(V_1) + c_n I)

Using this scheme, Dave SHOULD be able to guarantee to only allow permitted users to download a picture once while not being able to know who’s downloading the pictures or who even these permitted users are. But there is a reason I put the “should” in the previous sentence into caps, because this scheme has not been proven to be secure nor been controlled by people who’s job is to find flaws in schemes like these. And even if the scheme itself is actually secure, there are still a lot of ways to mess up the implementation. For example, you could the point hashing or generate ss-values that are bigger than the group size, so you should be really careful when implementing this scheme (which shouldn’t do in the first place).