Imagine you have and , where . You want to prove that has the same discrete logarithm with respect to the different generators , or:
To prove this, you go through the following -protocol (inspired by the Schnorr identification protocol and taken from paper):
- The prover selects random and shares
- The verifier selects and shares a challenge
- The prover puts response and shares it with the verifier
- The verifier accepts if and
So, basically the solution is obvious: you sample different commitments for your points (with same private opening), but receive only one challenge. Then, you respond only one response (because it should be acceptable for both discrete log AoKs) and verifier becomes able to verify that you know the secret value , and it is the same in and .