Interactive proof and zero-knowledge proof systems are two important concepts in cryptography and complexity theory. In the past two decades, a great number of interactive proof and zero-knowledge proof protocols have...Interactive proof and zero-knowledge proof systems are two important concepts in cryptography and complexity theory. In the past two decades, a great number of interactive proof and zero-knowledge proof protocols have been designed and applied in practice. In this paper, a simple memorizable zero-knowledge protocol is proposed for graph non-isomorphism problem, based on the memorizable interactive proof system, which is extended from the original definition of interactive proof and is more applicable in reality. Keywords interactive proof - zero-knowledge proof - memorizable interactive proof - memorizable zero-knowledge proof This work was supported by the ministry of Science and Technology of China (Grant No.2001CCA03000), and the National Natural Science Foundation of China (Grant No.60273045).Ning Chen received his B.S. degree from Fudan University in 2001. Now he is a master candidate of Department of Computer Science, Fudan University. His research interests include computational complexity, computational cryptography, algorithm design and analysis.Jia-Wei Rong received her B.S. degree from Fudan University in 2002. Now she is a master candidate of Department of Computer Science, Fudan University. Her research interests include computational cryptography, machine learning, artificial intelligence.展开更多
文摘Interactive proof and zero-knowledge proof systems are two important concepts in cryptography and complexity theory. In the past two decades, a great number of interactive proof and zero-knowledge proof protocols have been designed and applied in practice. In this paper, a simple memorizable zero-knowledge protocol is proposed for graph non-isomorphism problem, based on the memorizable interactive proof system, which is extended from the original definition of interactive proof and is more applicable in reality. Keywords interactive proof - zero-knowledge proof - memorizable interactive proof - memorizable zero-knowledge proof This work was supported by the ministry of Science and Technology of China (Grant No.2001CCA03000), and the National Natural Science Foundation of China (Grant No.60273045).Ning Chen received his B.S. degree from Fudan University in 2001. Now he is a master candidate of Department of Computer Science, Fudan University. His research interests include computational complexity, computational cryptography, algorithm design and analysis.Jia-Wei Rong received her B.S. degree from Fudan University in 2002. Now she is a master candidate of Department of Computer Science, Fudan University. Her research interests include computational cryptography, machine learning, artificial intelligence.
