Alice has a hidden message $g^{a \alpha}=(g^a)^\alpha$ where $g^a$ is the message, and a signature $s$ on $g^a$ from Charlie. She sends both $g^{a \alpha}$ and $s$ to Bob. She later wants to prove to Bob that she knows an $\alpha$ such that $s$ is a signature of $(g^{\alpha a})^{\alpha^{-1}}$ without disclosing neither $g^a$ nor $\alpha$.

Does such a PoK exist?

  • 1
    $\begingroup$ The message is $g^{\alpha a}$ or $g^a$? the signing key is $\alpha$? what's the corresponding verification key? What's the corresponding statement about the witness $g^a$? $\endgroup$
    – X.H. Yue
    Commented Jun 18 at 4:14
  • $\begingroup$ @X.H.Yue the message is $g^a$, and the signing key is not mentionned. We assume that $g^a$ has been signed by another entity, Charlie. We could write that $sk_C$ is the private key of Charlie that produced the signature $s$ which is only the appendix of signature (that is, without the message) $\endgroup$
    – Adam54
    Commented Jun 18 at 7:07
  • $\begingroup$ The solution of your question I think is the verifiable encryption, which provides a proof to convince the verifier that the message embedding in the ciphertext is well-formed. In your case, the message is the message $g^a$ and the corresponding signature $s$, the relationship between $g^a$ and $s$ is the verification algorithm of the signature scheme. Therefore, you can prove that I have a valid signature on some message meeting the mentioned relationship with PoK. $\endgroup$
    – X.H. Yue
    Commented Jun 19 at 2:53
  • $\begingroup$ @X.H.Yue Thank you very much for the reference. Are there some schemes which enable exactly this verification ? Are there popular approaches based on standard assumptions? $\endgroup$
    – Adam54
    Commented Jun 19 at 16:02
  • $\begingroup$ I recommend researching group signature schemes based on the Groth-Sahai proof system. In group signatures, members are required to prove in zero knowledge that they possess a valid signature issued by the group manager. I believe this topic will be beneficial for your research. $\endgroup$
    – X.H. Yue
    Commented Jun 20 at 6:38


Your Answer

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

Browse other questions tagged or ask your own question.