Proving that you have $k$ keys out of $n$ without revealing which keys they are

I'm looking for a cryptographic algorithm where Alice can prove that she has at least $k$ private keys out of $n$ to Bob, without revealing which keys she knows.

As I wrote in a comment, I believe your solution only works with some public-key schemes, because usually a full-blown public encryption scheme must include randomness to allow encryption of low entropy plaintexts without others being able to guess and encrypt. (Still, it would probably allow verification of key-ownership in some such schemes if access to the underlying primitive like unpadded RSA is assumed.)

A patched solution is for Bob to use Shamir Secret Sharing to share a symmetric key, which he uses to encrypt all the necessary information to reproduce the public-key ciphertexts. That is, he creates a symmetric key, computes the shares and encrypts them using each public key. He then encrypts both all the coordinates and the steps taken to encrypt them, including any randomness the schemes may use, using the symmetric key.

(He does not need to reveal any coordinates in plaintext, but should encrypt all the public keys if Alice does not know them. This means the scheme reveals to Alice which the other public keys were if she has the $k$-subset.)

Alice will be able to verify that the coordinates are on the same polynomial and that they were indeed encrypted using each public key.

We use Shamir's Secret Sharing.

A simple (and wrong) solution to this is for Bob to set up a Shamir's Secret Sharing problem with each $(x, y)$ coordinate pair encrypted by one of the $n$ public keys.

However, a malicious Bob can use this to leak information about which keys Alice has by sending $n$ coordinate pairs that are not consistently part of the same $k-1$-degree polynomial, and the secret that Alice comes up with will reveal which $k$ points were used.

To solve this issue, Bob can reveal the $x$ coordinate of each pair, and only keep the $y$ coordinate secret. Once Alice has found the secret, she can use this to calculate the $y$ coordinates for the remaining $n-k$ points and verify that Bob sent the correct ciphertext (since she, too, has access to all $n$ public keys).

Revealing $x$ coordinates is safe. Alice already knows that the polynomial is an integer valued one, so every $x$ coordinate has a corresponding integer $y$ coordinate. Knowing that a particular $x$ coordinate has an integer $y$ coordinate doesn't reveal additional information, since we know that all of them do. As long as the polynomial is computed on a (large enough) finite prime field, Alice can't figure out the other $y$ coordinates unless she has the quorum $k$ private keys.

(In general, revealing $x$ coordinates in Shamir's Secret Sharing may not be safe, because it does mean that post-decryption everyone will know everyone else's $y$ coordinate. In this case, it's a one-time use set of coordinates, so it's fine.)

• I was initially confused about the legitimacy of revealing $x$ coordinates, and was going to ask about that when I realized why it was safe. Since I'd already typed everything up, thought I'd self-answer :) – Manishearth Aug 10 '16 at 4:02
• I think you assume that Alice will be able to encrypt the $y$ coordinates and see that they match the ones encrypted by Bob? This is not possible with many public-key encryption schemes due to their use of randomized padding, so this solution only works with some schemes. – otus Aug 10 '16 at 4:45