Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annea...Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.展开更多
Abe et al. proposed the methodology of ring signature (RS) design in 2002 andshowed how to construct RS with a mixture of public keys based on factorization and/or discretelogarithms. Their methodology cannot be appli...Abe et al. proposed the methodology of ring signature (RS) design in 2002 andshowed how to construct RS with a mixture of public keys based on factorization and/or discretelogarithms. Their methodology cannot be applied to knowledge signatures (KS) using the Fiat-Shamirheuristic and cut-and-choose techniques, for instance, the Goldreich KS. This paper presents a moregeneral construction of RS from various public keys if there exists a secure signature using such apublic key and an efficient algorithm to forge the relation to be checked if the challenges in sucha signature are known in advance. The paper shows how to construct RS based on the graph isomorphismproblem (GIP). Although it is unknown whether or not GIP is NP-Complete, there are no knownarguments that it can be solved even in the quantum computation model. Hence, the scheme has abetter security basis and it is plausibly secure against quantum adversaries.展开更多
基金the National Natural Science Foundation of China (60373089, 60674106, and 60533010)the National High Technology Research and Development "863" Program (2006AA01Z104)
文摘Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.
文摘Abe et al. proposed the methodology of ring signature (RS) design in 2002 andshowed how to construct RS with a mixture of public keys based on factorization and/or discretelogarithms. Their methodology cannot be applied to knowledge signatures (KS) using the Fiat-Shamirheuristic and cut-and-choose techniques, for instance, the Goldreich KS. This paper presents a moregeneral construction of RS from various public keys if there exists a secure signature using such apublic key and an efficient algorithm to forge the relation to be checked if the challenges in sucha signature are known in advance. The paper shows how to construct RS based on the graph isomorphismproblem (GIP). Although it is unknown whether or not GIP is NP-Complete, there are no knownarguments that it can be solved even in the quantum computation model. Hence, the scheme has abetter security basis and it is plausibly secure against quantum adversaries.
