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.
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
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 do so, Alice needs to do a little more work than before when uploading a picture:

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

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

1. Check if $I$ has already been used before for the picture.
2. 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$
3. 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
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).