Study on Zero-Knowledge Proof Based on Independent Set Problem
Pingshui Wang · Computer Technology and Development · 2007
Zero-knowledge proof has been one of the key technologies to be applied in identity authentication in the fields of information security.To avoid the use of the graph isomorphism problem in the known zero-knowledge proof systems,an efficient computational zero-knowledge proof of knowledge whose security relies on the NP-Completeness of the independent set problem is presented here.The proposed logarithm is constructed from a bit commitment scheme based on the hardness of the discrete logarithm problem,which guarantees the fulfillment of soundness,completeness and computational zero-knowledge properties.The system and its logarithm parameter choice were analyzed from two aspects of computational complexity and communication complexity.It was proved theoretically that the system is feasible and effective.