How to prove identity without revealing identity

Question

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?

Answer 1

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.

Answer 2

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).

Answer 3

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.