I would like to create a server that would verify a public/private key pair where the private key is encrypted with a key unknown to the server.

The server should reject the keypair if the encrypted content is not the private key belonging to the public key.

Is there a way to cryptographically prove that the content of the encrypted data is the correct private key without the server having any way of decrypting the key?

A signature using the private key, sent along the keypair, to be verified with the public key is not enough since the client could send correctly signed garbage data instead of the private key and the signature would still be valid .


Can this be done?

In general, there is a way: you can prove the statement you sketch using zero-knowledge proofs. Due to [1] we know that zero-knowledge proofs for any language in NP exist. Let us write down what you want to prove as an NP language $L$. Therefore let $\sf (sk, pk)$ be the key pair, consisting of a secret key $\sf sk$ and a public key $\sf pk$, and let $\sf pk'$ be the public encryption key (corresponding to some secret decryption key $\sf sk'$) used to encrypt $\sf sk$ so that $C = {\sf Enc}({\sf pk'}, {\sf sk};~\rho)$, i.e., the ciphertext $C$ contains an encryption of $\sf sk$ under public encryption key $\sf pk'$ and $\rho$ denotes the randomness used upon encryption. In addition we may assume without loss of generality that there exists an efficient algorithm $\sf VKey$ which takes as input a key pair $\sf (sk, pk)$, and outputs $1$ whenever $\sf sk$ is the key corresponding to $\sf pk$ and $0$ otherwise. Now we can write down $L$ as follows: $$ L = \{ ({\sf pk'}, C, {\sf pk}) ~|~ \exists~({\sf sk}, \rho) : {\sf VKey}({\sf sk},{\sf pk}) = 1 ~\land~ C = {\sf Enc}({\sf pk'}, {\sf sk};~\rho)\}, $$ Clearly, if we know $({\sf sk}, \rho)$ corresponding to a tuple $({\sf pk'}, C, {\sf pk})$ we can efficiently verify membership in $L$. Therefore $L$ is indeed an NP language.

Efficient instantiations?

Regarding efficient instantiations one needs to be careful, as the most efficient approach no longer allows to obtain $\sf sk$ upon decryption but only $\sf pk$. In particular, assume that we have some group $\mathbb{G}$ of prime order $p$ generated by $g$ where we assume the decisional Diffie-Hellman assumption to hold. Now assume we use some scheme where the $\sf sk$ is a random element in $\mathbb{Z}_p$ and the corresponding public key is its "image" in the group with respect to $g$, i.e., ${\sf pk} = g^{\sf sk}$. Additionally assume that we choose to use exponential ElGamal in $\mathbb{G}$ as encryption scheme, (i.e., ${\sf Enc}({\sf pk}', {\sf sk}) := (g^r, {\sf pk}'^r \cdot g^{\sf sk})$ for some uniformly random $r$ in $\mathbb{Z}_p)$. Now, one may observe that we can no longer efficiently obtain $\sf sk$ upon decryption but only $\sf pk$. However, if your use case does not require to be able to recover $\sf sk$ upon decryption the aformentioned instantiation is very efficient: one can make use of $\Sigma$-protocols (see, e.g., [2]).

If your use case also requires to be able to efficiently recover $\sf sk$ upon decryption, you will require more costly zero knowledge proofs: for example encrypting a bit-wise representation of the key and proving the statement with respect to this bit-wise representation of the key, or to use Paillier as an encryption scheme, which however may require zero-knowledge proofs over groups of different orders (see e.g., [3]).

Instantiations using a symmetric encryption scheme?

In case you want to use a symmetric encryption scheme things will get a lot more expensive as this would require to prove statements over general circuits and also to somehow make the link to the algebraic setting where the keypair $({\sf sk}, {\sf pk})$ lives in. You could have a look at this paper [4] to find out more about how this could be instantiated.

Also note that, in contrast to asymmetric encryption schemes, symmetric encryption schemes are typically not binding. Thus such an instantiation will require some additional measures to ensure that the encryption key you use to prove the statement is indeed the key it should be.


I think that using an asymmetric encryption scheme will be preferable in practice - if your use case allows it at all. Even if one might have to do ZK proofs over groups of different orders this will be much more efficient and much simpler to implement compared to using a symmetric encryption scheme.


[1] http://www.wisdom.weizmann.ac.il/~oded/X/gmw1j.pdf

[2] http://www.cs.au.dk/~ivan/Sigma.pdf

[3] https://pdfs.semanticscholar.org/ad71/f5dcef871bdfaad01be9da6d378b010b36d4.pdf

[4] https://eprint.iacr.org/2016/583.pdf

  • $\begingroup$ I have to admit, I don't understand this. Any chance you can dumb this down for me? I'm glad to hear this is a solvable issue though, I currently have the protocol just blindly trust the encrypted blob, which is not ideal. $\endgroup$
    – LiraNuna
    Jan 1 '18 at 1:48
  • $\begingroup$ @LiraNuna could you give some details on which part you do not understand, so that I can try to add details in this part of the answer? $\endgroup$
    – dade
    Jan 1 '18 at 10:08
  • $\begingroup$ is sk public key and pk the unencrypted private key? does pk' have to be another private key from a keypair? can it be symmetric without the server knowing what it is? $\endgroup$
    – LiraNuna
    Jan 4 '18 at 6:23
  • $\begingroup$ No, $\sf sk$ is the secret key and $\sf pk$ is the public key of the "public/private key pair" which you mentioned in your question. I've just named them to ease the explanation. The public encryption key $\sf pk'$ constitutes some encryption key for an asymmetric encryption scheme (say ElGamal or Paillier). It corresponds to some secret key $\sf sk'$ which I have omitted to mention since it is needed nowhere in my explanations. So the key pair $(\sf sk', pk')$ should be the key pair corresponding to the encryption scheme. $\endgroup$
    – dade
    Jan 4 '18 at 6:44
  • $\begingroup$ @LiraNuna I have edited my answer above and tried to clarify the semantics of the keys. Let me know if there is still something unclear. $\endgroup$
    – dade
    Jan 4 '18 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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