Join Log in
Score:1
Thierry Sans avatar Crypto

Proving ownership of an encryption key

pk flag
Thierry Sans

In the context of a host-proof storage service, is there an encryption scheme that allows me to prove to the server that I own the secret key to decrypt the ciphertext I am currently uploading but (indeed) without revealing the key nor the plaintext message?

Said differently, is there a way for the server to be sure that 1) an uploaded file is encrypted and that 2) the user owns the key to decrypt that file?

82
1 + 0
Score:1
Geoffroy Couteau avatar Crypto
cn flag
Geoffroy Couteau

Most standard algebraic encryption scheme admit such zero-knowledge proof of knowledge of the secret key. For example, if the encryption scheme is ElGamal (over a suitable group, e.g. an elliptic curve) with public key $(G,H)$, proving knowledge of the secret key is just proving knowledge of a value $s$ such that $G^s = H$, which is the standard Schnorr proof (the latter is only honest-verifier zero-knowledge, but it can be modified to be full-fledged zero-knowledge). Similar proof systems exist for other public-key encryption schemes, e.g. Goldwasser-Micali or Paillier (for those, it amounts to proving knowledge of the factors of an RSA modulus, which can be done but is significantly less efficient).

0 + 4
Thierry Sans avatar
pk flag
Thierry Sans
Thank you Geoffroy! Do you know any public library that could do the full-fledged encryption + zero-knowledge proof by any chance?
0
Reply
Geoffroy Couteau avatar
cn flag
Geoffroy Couteau
I don't, but that's mostly because I'm never implementing cryptography myself (I do mostly theoretical research). I'm pretty sure such a library exist, though I'm not sure what's an appropriate place to ask about this (I think it would be out of scope on this website). A quick Google search pointed me to zksk, but I don't know much about it.
0
Reply
us flag
thesquaregroot
Not sure if this is what OP has in mind, but I would think this only solves half of part 2. That is, one might prove that they are in possession of a given secret key but not necessarily whether that secret key could indeed decrypt the file. Is there a way in such a scheme for the server to verify that the public key (presumably uploaded with the encrypted data) does indeed correspond to a secret key that would decrypt the file? If that is not covered, couldn't an uploader include a key unrelated to the encrypted data and therefore prove they own the key but not that they decrypt the file?
0
Reply
Geoffroy Couteau avatar
cn flag
Geoffroy Couteau
That's a good point. For all examples I mentioned above, though (ElGamal, Goldwasser-Micali, and Paillier), the problem does not exist, since any ciphertext can be publicly checked to be well-formed (with respect to the given public key). Hence, if one proves knowledge of the secret key associated to the public key, it always implies that any ciphertext can be correctly decrypted by the prover.
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.