1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thank you Geoffroy! Do you know any public library that could do the full-fledged encryption + zero-knowledge proof by any chance? $\endgroup$ Commented Jul 19, 2021 at 16:52
  • $\begingroup$ 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. $\endgroup$ Commented Jul 19, 2021 at 16:58
  • $\begingroup$ 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? $\endgroup$ Commented Jul 19, 2021 at 16:59
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jul 19, 2021 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.