5
$\begingroup$

If the prover provides a block of data and a public key. The provided data is supposedly ciphertext that was encrypted using the provided public key. Is there a way to prove that the provided data has infact been encrypted using that specific public key?

The verifier does not have access in any way to the plaintext data or the private key. However, the prover does have access to the plaintext data and private key, and can provide additional information to assist in proving, as long as zero knowledge of the plaintext data and private key are exposed to the verifier.

Update: Based on the current responses, it seems unlikely that the verifier would be able to prove or disprove the claim by the prover using only the provided data and public key. However, the question still remains if this could be accomplished using some form of additional proof data, possibly in conjuction with a zero knowledge based algorithm.

$\endgroup$
  • 2
    $\begingroup$ Any specific schemes you want us to refer to? The schemes in RSA/PKCS#1 for instance? I know one way in which it is possible to show that something was not encrypted with a specific key in certain conditions, but usually the schemes are randomized enough, so you can never be certain who encrypted it. $\endgroup$ – Maarten Bodewes Apr 5 '17 at 21:31
  • $\begingroup$ @MaartenBodewes There isn't really any specific scheme, but I do slightly favor anything that is believed to be post-quantum secure and has a public key size that is 5KiB or smaller. $\endgroup$ – Jordan Mack Apr 6 '17 at 6:25
  • $\begingroup$ Is the "piece of data" the alleged-ciphertext or the plaintext? ​ (In the latter case, presumably there's an encapsulation of the plaintext.) ​ Is [the "you" who does "not have access in any way to the decrypted data or the private key"] the prover or the verifier? ​ ​ ​ ​ $\endgroup$ – user991 Apr 7 '17 at 14:27
  • 1
    $\begingroup$ You may be interested in the paper Key-Privacy in Public-Key Encryption $\endgroup$ – Ella Rose Apr 7 '17 at 17:29
  • $\begingroup$ @RickyDemer The prover submits data and a public key. The data is claimed to be ciphertext which has been encrypted using the provided public key. The verifier must determine if the claim is true or false. The claim is true if the provided data has been encrypted using the provided public key. The verifier does not have access in any way to the plaintext, or the private key. The prover does have access to the plaintext and private key. The prover can provide additional data to the verifier to assist with proving as long as it gives zero knowledge about the plaintext data and private key. $\endgroup$ – Jordan Mack Apr 7 '17 at 19:41
3
$\begingroup$

This depends on the scheme that is being used.

In the case of a scheme that behaves like a random oracle: We could assume that the scheme that is used behaves as a random oracle, and that we are to infer by the ciphertext that some specific key was used. This would imply that we could actually get some information about the key, by knowing only the ciphertext (and not the plaintext). Namely if a specific key was used to encrypt the plaintext. This would however violate the assumption that the scheme behaves like a random oracle. So in the case of a random oracle the answer would be no.

$\endgroup$

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.