I want to design a zero-knowledge proof (ideally a NIZK, but could be a sigma protocol) so that Alice can prove that a certain encryption contains a value that has been signed by a certain key.

More specifically:

Let ek be an encryption key (e.g., ElGamal) and dk the corresponding decryption key. Let sk be a signing key (say DSA or Schnorr) and vk the corresponding verification key.

Alice wants to prove that she knows private values x, s such that public values e, vk, ek satisfy e = Enc_ek(x) and Verify_vk(x, s) = True.

(Here, x is a plaintext value, s is the signature on x, e is the encryption of x. Perhaps I also need a private value for the randomness in the encryption. Alice does not know dk or sk. I suggested using ElGamal/Schnorr, but I'd also be happy if it is in the RSA framework, or a different one.)

  • 1
    $\begingroup$ did you check non-interactive anonymous credentials? Existing schemes do essentially that: a NIZK proving that a commitment contains a valid signature. See e.g. this paper, or some of the (many) follow ups $\endgroup$ Mar 13 at 21:21
  • $\begingroup$ Thanks @GeoffroyCouteau! That looks relevant. However, if I understand correctly, the paper allows Alice to prove her commitment is to a signed value, whereas I wanted an encryption of a signed value. The important difference is that the encryption can eventually be decrypted. (I guess, in terms of anonymous creds, this means that the anonymity can be revoked by the decryption key holder.) $\endgroup$
    – knoob
    Mar 14 at 10:18
  • $\begingroup$ Right, but it is at least a good starting point. It should be checked carefully, but they use Groth Sahai commitments, which are extractable given an appropriate extraction trapdoor - in other words, this commitment scheme is already an encryption scheme unless I am missing something. $\endgroup$ Mar 14 at 17:11
  • $\begingroup$ Thanks again, @GeoffroyCouteau. Can you give me your opinion on whether there likely exists an "elementary" protocol answering my question? I mean something in the style of "KnowDlog" and "EqDlogs" on page 38 (which is page 39 of the PDF) of this paper. $\endgroup$
    – knoob
    Mar 15 at 17:33

Your Answer

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

Browse other questions tagged or ask your own question.