Return to Answer

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 $e_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

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

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 $e_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.

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 $e_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

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 $e_j$ and sign it to get $r_j$ ($r_j$ looks like every other random data)

Now she can choose $e_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.emphasized text

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 $e_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.