Score:2

Is a non-correlating signed identity proof possible?

bh flag

Is it possible to receive from a party $I$ a signed message $M$ that can be presented to two independent other parties $V_1$ and $V_2$ as $M'_1$ and $M'_2$ in such a way that they cannot establish a correlation between $M'_1$ and $M'_2$, but that they can verify that the message was signed by $I$ and issued to the one presenting it?

EDIT:

To make it more clear what I would like to achieve here's an example:

The message $M$ contains the statement "the owner of public key $PK_H$ has blue eyes". The owner of the matching secret key $SK_H$ to $PK_H$ can prove that this attestation was issued to her. So everyone who trusts $I$ trusts that the person presenting that message and can prove knowledge of $SK_H$ has blue eyes.

This message is then sent to $V_1$ and $V_2$ so they can verify if the sender has blue eyes. But to prevent that $V_1$ and $V_2$ can collaborate and figure out that this is the same person, the message must be presented to them in some derived form, therefore $M'_1$ and $M'_2$.

It might well be completely impossible, but I'd like to confirm that.

poncho avatar
my flag
Hmmm, if I can verify that $M'_1$ is a signed version of $M$, and that $M'_2$ is a signed version of $M$, wouldn't that count as a correlation? Or, is it the idea that, from $M'_1, M'_2$ you cannot recover $M$?
no1dea avatar
bh flag
Good question. I would say yes, the idea is that you cannot recover *M* because otherwise indeed, correlation would be possible.
poncho avatar
my flag
Then what does $M_1'$ signify to $V_1$? What does $V_1$ learn from $M_1'$?
no1dea avatar
bh flag
Let's say Alice has blue eyes. $I$ sings a message $M$ saying Alice has blue eyes. $V_1$ learns from $M'_1$ that $I$ has confirmed that the person presenting $M'_1$ to $V_1$ is Alice and has blue eyes.
poncho avatar
my flag
And I assume $M'_2$ might signify "I'm Alice and I have blond hair"; correct?
no1dea avatar
bh flag
No, what I would like to achieve is that $M'_1$ and $M'_2$ contain the same statement but they are different so that correlation is not possible. By that I mean by looking at $M'_1$ and $M'_2$ one cannot correlate that this is the same Alice. $V_1$ and $V_2$ only know that the person presenting the respective message has blue eyes as attested by $I$ who signed the message.
Score:1
sm flag
Ron

Yes, you can do it, instead of sharing the signature of the message (msg='alice has blue eyes'), you will generate a zero-knowledge proof that will prove that you have a valid signature of that message, and only share the proof with the verifier.

The proof will be different for every verifier as the verifier will ask you to embed a random challenge into the proof, so the prover will need to generate a fresh proof for every verifier that request the same verification, which will result in a different proof every time and that will enforce the un-trackability between the different interactions with the different verifiers.

If you want to read more about it the topic is called "Non-correlating signatures", here is an example of a paper that mentioned it and discussed the zkp solution - zkKYC

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.