# Identity Hiding Ring Signature Zero Knowledge Proof

27 Mar 2020Back 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 $x_i$ and the corresponding public key $P_i = x_i G$, where $G$ 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 $x$ and the corresponding public key. We are also given a bunch of public keys from all kind of Bobs, let’s call them $P_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 = x H_p(xG)$.

To sign, we first identify the index called $j$ of our own public key, so that $P_j = xG$. After that, we generate a bunch of random values and store them in $\alpha$ and $s_1, ..., s_n$.

This allows us to calculate the first challenge $c_{j+1} = H(m\ ||\ \alpha G\ ||\ \alpha H(xG))$. We can now use the initial challenge to calculate the rest of the challenges $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, ..., j$. After that, we set $s_j = \alpha - c_j * x$ and $(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:

- Alice creates a random temporary masking key $m$ and calculates $M = mG$
- Alice calculates the masked public keys $V_i = mP_i$
- Alice uploads the picture alongside the masked pubic keys $V_1, ... V_n$ and the public maksing key $M$ to Dave.

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

- Dave sends the masked keys $(M, V_1, ..., V_n)$ to Bob
- Bob find's it's index $j$ with $V_j = xM$ and calculates $I = x H_p(xV_j)$
- Bob generates random $\alpha$ and $s_1, ..., s_n$
- Bob calculates $c_{j+1} = H(\alpha M\ ||\ \alpha H_p(xM))$ and $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, ..., j$
- Bob sets $s_j = \alpha - c_j * x$
- Bob sends $(I, c_1, s_1, ..., s_n)$ to Dave

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

- Check if $I$ has already been used before for the picture.
- Calculate $c_i = H(s_i M + c_{i-1} V_i\ ||\ s_i H_p(V_i) + c_i I)$ for $i = 2, ..., n$
- Check if $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 screw up the point hashing or generate $s$-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).