Identity Hiding Ring Signature Zero Knowledge Proof27 Mar 2020
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 didn’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 gets 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
and the corresponding public key , where 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 downloads 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
Let’s pretend we are a Bob wanting to create a ring signature. We of course know our own private key, let’s
call it and the corresponding public key. We are also given a bunch of public keys from all kind of Bobs,
let’s call them .
The linked paper also introduces so called key images which stays 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
To sign, we first identify the index called of our own public key, so that . After that, we generate a bunch
of random values and store them in and .
This allows us to calculate the first challenge . We can now use
the initial challenge to calculate the rest of the challenges
for . After that, we set and 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 a pen and a 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 cannot 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 and calculates
- Alice calculates the masked public keys
- Alice uploads the picture alongside the masked pubic keys and the public masking key to Dave.
There is also a bit of communication between Dave and Bob when downloading a picture:
- Dave sends the masked keys to Bob
- Bob find's it's index with and calculates
- Bob generates random and
- Bob calculates and for
- Bob sets
- Bob sends to Dave
To verify the signature, Dave now only has to perform the following the steps:
- Check if has already been used before for the picture.
- Calculate for
- Check if
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 -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).