If I want to add zero-knowledge proof to the ElGamal signature, is it reasonable to write that?

$$ \pi \gets \operatorname{NIZK.Prove}\bigl(u=((r,s),y,m),w=(x,k)\bigr) $$

$$ R=\{u,w:g^{H(m)}=y^rr^s \bmod p \bigwedge r=g^k\bmod p \bigwedge s=(H(m)-xr)k^{-1}\bmod (p-1)\} $$

But I can't prove one and three parts of $R$, so how do I prove this part?

  • $\begingroup$ Are you asking for a zero-knowledge proof that a public ElGamal signature is matching a public key and message (as suggested by "add zero-knowledge proof to the ElGamal signature"), or for a zero-knowledge proof of knowledge of a (non-disclosed) ElGamal signature? In the first case, why is that useful, since the El Gmamal signature can be verified, yielding evidence that the signature is correct, and there can't be less information disclosure than by not adding anything? $\endgroup$
    – fgrieu
    Commented Jun 26 at 5:26
  • 1
    $\begingroup$ The signature is public, and the public key $y$ and message $m$ are known to the verifier. Well,I want to use it as part of an algorithm that guarantees the origin and efficient generation of the signature before verifying it. But proving the signature while the prover proves the private key $x$ and random number $k$ to the verifier seems a bit difficult. $\endgroup$
    – Anja
    Commented Jun 26 at 5:41
  • $\begingroup$ We can't "guarantee (…) efficient generation of the signature", for it's easy to turn an efficient method into an inefficient one yielding the same result. The best that could perhaps be proved is that the signature has the value that it would have if it was generated by some specified algorithm. And then it seems that would require deterministic generation of $k$, and we'd need to prove that $k$ is as generated by some algorithm without disclosing $k$ (which would reveal the ElGamal private key). So that algorithm would need to be keyed. I don't say that's impossible, but I pass. $\endgroup$
    – fgrieu
    Commented Jun 26 at 7:21


Your Answer

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