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