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 axby ). 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.