# Zero knowledge RSA public key

Suppose Bob has $$k>1$$ RSA public keys $$(e_i, n_i)$$ without any knowledge of their corresponding private keys. Alice also has all the public keys, but also has a private key for only one of them, say, $$(d_j, n_j)$$. Is it possible for her to prove to Bob that she has at least one of the private keys, without revealing $$j$$

EDIT: changed notation according to fgrieu suggestions

Yes, it is even possible without interaction (nothing Bob needs to send to Alice). The method is called "ring signature".

Let's say she wants to sign a message like "I am Alice an hereby proof to Bob that I know one of the keys". She hashes it to get $$m$$.

Alice now generates a random value $$r_i$$ for every public key $$k_i$$ and encrypts them to get $$y_i$$.

Note that they all $$y_i$$ are unpredictable pseudorandom values. The only $$y_i$$ she can choose is the one that belongs to her key $$k_j$$, she just chooses $$y_j$$ and sign it to get $$r_j$$ ($$r_j$$ looks like every other random data)

Now she can choose $$y_j$$ so that the xor of all $$y_i$$ equals $$m$$.

She sends the message and all the $$r_i$$ to Bob (if the order is not clear, add a note which $$r_i$$ belongs to which key)

To verify, Bob just encrypts every $$r_i$$ with the public key $$k_i$$ to get the $$y_i$$, xors them all and checks if it equals $$m$$.

Since all $$y_i$$ are like random numbers, when you don't know the key, there is no way to fake a signature without knowing a private key. Additionally there is no way to tell which $$y_i$$ and $$r_i$$ was not randomly generated, because they all look random.

Important EDIT: I forgot the symmetric encryption step in the ring signature. Between the xor steps symmetric encryption should be applied. This still allows allice to recover the $$y_i$$ she needs, but makes attacks harder. For more details look at Wikipedia

• @fgrieu I changed the names von $e$ to $y$, thanks for that. You can just choose by xor-ing all other $y_i$ and $m$ to get $y_j$. There is no need for trial and error when you know the private key of $k_j$. The length problem can easily be fixed by limiting the bits to xor to the number of bits in m and ignore the others
– jjj
Jul 22 at 8:29
• Yes, masking out enough high order bits (just one if the $n_i$ are the same bit size) makes it possible to avoid any trial and error. Again, how the high order bit(s) of $y_j$ is chosen requires careful consideration.
– fgrieu
Jul 22 at 9:38
• When the hash is $h$-bit, I'm told there is an attack of cost $\mathcal O(2^{h/(1+\log_2(k))})$, which can get worrying for large $k$. On another front, I find it non-trivial to prevent an adversary from gaining some (little) advantage on guessing $j$, especially when $h$ approaches the width of the smallest $n_i$.
– fgrieu
Jul 22 at 19:27
• @fgrieu Ok, I checked and noticed that I did not remember the algorithm correctly. The base Idea is still correct. I added a note to my answer. Thanks for checking. I still think ring signatures are really good for this problem
– jjj
Jul 22 at 20:57
• Yes, ring signature works for this. But a critical detail is missing in the Wikipedia article and the answer: the domain for the $r_i$ and $y_i$ must be made the same size even though the $n_i$ are different, in order to prevent leak of information about $j$. This is addressed in the Extending trap-door permutations to a common domain section of the Rivest-Shamir-Tauman paper.
– fgrieu
Jul 23 at 6:35

Here is a proposal (out of my head). Big picture

• Bob draws a random $$X$$, and sends it deterministically enciphered under each public key
• Alice deciphers $$X$$ with the public key she holds
• Alice checks Bob did as expected given that $$X$$
• Alice reveals $$X$$ to Bob

More precisely:

• Define a $$8b$$-bit hash (say SHA-512) such that $$\min(n_i)>2^{16b}$$
• Define a Mask Generation Function (such as MGF1 with that hash) so that for bytestring $$X$$, $$\operatorname{MGF}(X,\ell)$$ is an $$\ell$$-byte hash of $$X$$
• Define the byte lengths $$\ell_i=\left\lfloor\log_2(n_i)/8\right\rfloor$$, which are such that $$2^{8\ell_i} (in order to avoid timing attacks, it's desirable that the $$n_i$$ have the same bit size, thus the $$l_i$$ equal)
• Bob draws a random $$X\in\{0,1\}^{8b}$$ (a $$b$$-byte bytestring)
• For each $$i$$, Bob
• computes $$M_i=\operatorname{MGF}\bigl(X\mathbin\|H(n_i),l_i-b\bigr)$$
• computes $$X_i=M_i\mathbin\|(X\oplus H(M_i\mathbin\|H(n_i)))$$ (an $$l_i$$-byte bytestring)
• computes and output $$C_i={X_i}^{e_i}\bmod n_i$$
• Alice gets the $$C_i$$, including $$C_j$$
• Alice computes $$f={C_j}^{d_j}\bmod n_j$$
• Alice expresses $$f$$ as bytestring $$M\mathbin\|G$$ with $$M$$ of $$l_i-b$$ bytes and $$G$$ of $$b$$ bytes.
• Alice recovers $$X$$ by computing $$X=G\oplus H(M\mathbin\|J)$$
• For each $$i$$, Alice
• computes $$M_i=\operatorname{MGF}\bigl(X\mathbin\|H(n_i),l_i-b\bigr)$$, where $$I$$ is index $$i$$ as a bytestring.
• computes $$X_i=M_i\mathbin\|(X\oplus H(M_i\mathbin\|H(n_i)))$$ (an $$l_i$$-byte bytestring)
• checks $${X_i}^{e_i}\bmod n_i=C_i$$ (when $$i=j$$, this checks $$M=\operatorname{MGF}\bigl(X\mathbin\|H(n_j),l_j-b\bigr)$$ as a side effect)
• Only if all the checks passed, and without revealing (e.g. by timing) where an error occurred if any, or which $$X_i$$ was used to recover $$X$$
• Alice reveals $$X$$
• Bob checks Alice revealed the right $$X$$

Rationale:

• Alice proves she can decipher one of the cryptograms $$C_i$$, thus that she holds a private key
• She does not reveal which, since she verified all the cryptograms match the same $$X$$. There is no risk that a bias in the high-order bits in some quantity in $$[0,n_j)$$ can give an advantage in guessing $$j$$ (as could be the case in a naive implementation of that other answer).
• Representatives $$X_i$$ of $$X$$ are spread on $$[0,n_i)$$ as in RSASSA-OAEP, with independent padding functions. Notice that directly enciphering $$X_i=X$$, or $$X_i=F(X)$$ for some fixed injection $$F$$, would leave the system vulnerable to Håstad's broadcast attack; further, it could be impossible to define a safe common width for the $$X_i$$, e.g. if $$n_0$$ is 2048-bit, $$n_1$$ 8192-bit, $$e_1=3$$; the padding solves that.
• Since $$X$$ is a challenge drawn by Bob, the protocol is immune to replay: Alice can't get away with data she precomputed before loosing access to her private key, or data previously computed by Amanda, who also holds a private key.

Possible improvements to further guard Alice from becoming a decryption oracle, Bob from tweaking its $$X$$, and perhaps make a proof easier:

• Alice first draws $$b$$-byte $$Y$$ and sends a commitment $$H(Y\mathbin\|S_0)$$
• Bob draws its $$b$$-byte $$X$$ and sends a commitment $$H(X\mathbin\|S_1)$$
• Alice reveals $$Y$$, Bob checks it against $$H(Y\mathbin\|0)$$
• the above protocol is modified
• it's used $$M_i=\operatorname{MGF}\bigl(X\mathbin\|Y\mathbin\|H(n_i),l_i-b\bigr)$$
• it's used $$X_i=M_i\mathbin\|(X\oplus H(M_i\mathbin\|Y\mathbin\|H(n_i)))$$
• Alice further checks $$H(X\mathbin\|1)$$ matches
• Alice reveals $$H(X\mathbin\|S_2)$$ rather than $$X$$
• Bob checks that. (where the $$S_i$$ are distinct arbitrary short non-empty bytestrings)

Update: Another method, outlined in this other answer, is to use an RSA-based ring signature, and make Alice demonstrate to Bob her capacity to sign a challenge message.

• There is no need for Bob to draw anything. Alice can do it. To prevent Alice from choosing instead of drawing, one can just use a hash of a message she publishes.
– jjj
Jul 22 at 0:39
• @jjj: your suggestion makes the protocol vulnerable to replay. See new fourth bullet in the rationale.
– fgrieu
Jul 22 at 5:46
• Not necessarily, it depends on the message that is hashed. One can just include a nonce.
– jjj
Jul 22 at 8:17