随机自归约的一个四步零知识证明协议

A FOUR ROUND INTERACTIVE PROTOCOL OF THE RANDOM SELF REDUCIBILITY

文中用位提交（ｂｉｔ－ｃｏｍｍｉｔ）等方法，构造了随机归约的一个四步零知识证明协议，该协议没有附加任何复杂性假设和证明者的计算能力假设，且交互次数最优，适应面更广（二次剩余、离散对数、图同构等问题都在其中）．该协议符合知识和语言的证明系统的完备性、完美零知识性等条件，但它不符合知识和语言的证明系统的可靠性定义．文中给出新的可靠性定义，在实际应用中，该定义是合理的，该协议是可靠的，可用在安全保密，身份识别等系统中．

In the paper,a four round interactive protocol of the random self reducibility is constructed,which doesn't rely on any complex assumption or any power of prover.The protocol is applied in wider areas including quadratic residues,discrete logarithms and graph isomorphism and is optimal with the round complexity.The protocol satisfies some properties of the knowlege and the language membership interactive proof systems such as the completeness and the perfect zero knowledge,but does not satisfy the soundness.A new definition of soundness is given,and the definition is reasonable in practice.The protocol is practically sound,which can be used to a cryptographic identification scheme.