Sigma protocol for faster proof of simultaneous homomorphism relations

The Σ ‐protocols for homomorphism relations are one of the cryptographic protocols which are used to prove knowledge of homomorphism relations. The Schnorr protocol is one of the most famous Σ ‐protocols used for proving knowledge of discrete logarithm (DL) relation in which the verifier essentially performs one double‐exponentiation (i.e. a group computation of the form a x b y ). A direct application of the Schnorr protocol for proving simultaneous knowledge of n DLs with a common base leads to a Σ ‐protocol in which the verifier performs n double‐exponentiations. In this study, the authors propose another Σ ‐protocol for homomorphism relations. The proposed Σ ‐protocol has fast verification when is used to prove the simultaneous homomorphism relations with a common homomorphism. Also, when the DL instantiation (DL‐instantiation) of the proposed Σ ‐protocol is used to prove simultaneous knowledge of n DLs with a common base, it leads to a Σ ‐protocol in which the verifier performs n +1 single‐exponentiations.