Extended Methodology of RS Design and Instances Based on GIP

Abe et al. proposed the methodology of ring signature (RS) design in 2002 and showed how to construct RS with a mixture of public keys based on factorization and/or discrete logarithms. Their methodology cannot be applied to knowledge signatures (KS) using the Fiat-Shamir heuristic and cut-and-choose techniques, for instance, the Goldreich KS. This paper presents a more general construction of RS from various public keys if there exists a secure signature using such a public key and an efficient algorithm to forge the relation to be checked if the challenges in such a signature are known in advance. The paper shows how to construct RS based on the graph isomorphism problem (GIP). Although it is unknown whether or not GIP is NP-Complete, there are no known arguments that it can be solved even in the quantum computation model. Hence, the scheme has a better security basis and it is plausibly secure against quantum adversaries.