# How to prove identity without revealing identity

Let us say Alice publishes a book under the name of Claire. The book becomes wildly popular and now Bob comes along, claiming to be Claire, to reap all the success. How does Alice prove that she wrote the book (and Bob did not) as Claire without revealing that she is Alice? More specifically: what information can she include in her book to be able to later prove this?

I came across "zero-knowledge proof of knowledge" which sounds relevant, but I am not familiar enough with cryptography to understand if this is what I am looking for.

Also, can you point me to any usable implementations of such a scheme?

• Could this be a solution?: Alice publishes a public key in her book. Anyone who wishes to prove that they wrote the book must be in possession of the corresponding private key. Anyone could then ask Bob to encrypt some phrase and if his encryption of it cannot be decrypted with the key from the book, this means he cannot be the author. – Thomas Arildsen May 31 '14 at 23:38
• You might want to check out the paper of Fiat and Shamir How to prove yourself. Zero knowledge proofs actually contain more than what you described, because the verifier learns absolutely nothing by the protocol execution. Your proposition is good enough for a computationally secure proof of identity, but it's not zero knowledge. – tylo Jun 3 '14 at 9:28

She can generate a key-pair and include the public key in the book. Having the private counterpart she can at any time proove that she wrote the book by signing an arbitrary statament.

• You beat me to it :-) Actually seems like quite a simple solution. – Thomas Arildsen May 31 '14 at 23:43

Zero-knowledge proofs of knowledge basically allow Alice to convince someone beyond a reasonable doubt that she knows a certain piece of information (i.e., the answer to a certain question), without revealing what exactly that information is.

One simple example involves the discrete logarithm problem, which you might be familiar with: given a (large) prime $p$, an integer $g \bmod p$, and an integer $h\bmod p$, find an integer $x$ such that $g^x \equiv h \pmod p$ (asuming such an $x$ exists). It is difficult to find $x$, but if someone knows it, they can convince anybody of that fact without revealing it, using for example Schnorr's protocol.

So, Alice can just :

1. Pick a large prime $p$.
2. Pick a "nice" integer $g \bmod p$.
3. Pick an integer $x$.
4. Compute $h = g^x \bmod p$.
5. Put $p, g, h$ in the book, with a statement to the effect that "only the author of this book knows the number $x$ such that $g^x \equiv h \pmod p$".

If Bob claims to have written the book, he will be uncovered when he will be asked to show that he knows $x$. Alice, on the other hand, can convince someone that she does know $x$ without revealing it. However, this will require Alice to exchange messages with a potential challenger, so she must have a way to do it sufficiently anonymously (e.g., with a "free" e-mail address).

• Basically what you are suggesting is RSA algorithm approach, right? – hagrawal Aug 14 '15 at 19:07

Alice generates a signature key-pair and puts

$\;$ the fact that she's using this identity-proving construction
$\;\;\;\;$ and
$\;$ the digital signature scheme
$\;\;\;\;$ and
$\;$ the prefix-free code
$\;\;\;\;$ and
$\;$ the verification key

into the book, and keeps the signing key.

(Let "||" denote concatenation.)

For interactive verification, the verifier generates an unpredictable nonce,
sends it to the prover, the prover signs $\:$ "0" || prefixfree(nonce) || associated_data $\:$,
the prover sends the signature and associated_data to the verifier, and then the verifier
uses the verification key to check that the signature is valid for what it's supposed to be on.

For non-interactive verification, the prover signs $\:$ "10" || associated_data ,
the prover publishes the signature and associated_data to the verifier, and then the verifiers
use the verification key to check that the signature is valid for what it's supposed to be on.

If someone gives up with a valid signature under that verification key for a message that the
prover did not sign, then the prover signs $\:$ "11" $\:$ and publishes that claim with the signature.
Anyone can then use the verification key to confirm that either there was a forgery or the
signing key was leaked or the prover is falsely claiming that one of those two things happened.

I am not aware of any implementations of this scheme.

• This nonce, is this to prevent others from replaying the proof to fake identity? – Thomas Arildsen Jun 4 '14 at 23:13
• Yes. ${}{}{}\;$ – user991 Jun 5 '14 at 0:11
• I would like to understand the concepts behind your protocol better. Do you have some literature references I could explore? – Thomas Arildsen Jun 13 '14 at 21:17
• No; I'm not aware of any references for this. $\:$ It's just fairly direct use of a standard signature scheme. $\hspace{.27 in}$ – user991 Jun 13 '14 at 23:00