%0 Journal Article
%T Extended Methodology of RS Design and Instances Based on GIP
%A Qian-Hong Wu
%A Bo Qin
%A Yu-Min Wang
%A <br>Qian-HongWu
%A BoQin
%A Yu-MinWang
%J 计算机科学技术学报
%D 2005
%I 
%X 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.
%K ring signature
%K knowledge signature
%K graph isomorphism problem<br>环签名
%K 图类质同晶
%K RS设计
%K GIP
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=D1245EE0845827365D6326C988B4D3FC&yid=2DD7160C83D0ACED&vid=A04140E723CB732E&iid=0B39A22176CE99FB&sid=2B25C5E62F83A049&eid=2B25C5E62F83A049&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=16