Security Analysis Of Several Zero-knowledge Proof Protocols

The primitive of zero-knowledge proof introduced by Goldwasser,Micali and Rackoff in the early of 1980s,is one important cornerstone of modern cryptography.At the end of 1980s,Blum et al.put forth the concept of non-interactive zero-knowledge proof,by replacing the interactive process with a shared secret string to construct zero-knowledge proof.In 2006,Groth et al.proposed several non-interactive zeroknowledge proof protocols based on bilinear groups and subgroup decision problem.Non-interactive zero-knowledge proof is very useful for large networks that need to implement a large number of cryptographic protocols.It can save expensive communication costs and has attracted much attention.There are four contributions in this thesis,which can be descried as follows.(1)We investigate the Blum et al.'s zero-knowledge proof protocol for prime factors,and find it is dependent on a premise which requires that the two participants should share a secret string.To do so,it needs some preset interactions between the two parties,and a designated verifier.Naturally,this requirement is somewhat incompatible with the basic model of non-interactive zero-knowledge proof.(2)We discuss the Groth et al.'s zero-knowledge proof protocol for one plaintext consisting of a single bit,and compare it with the Blum et al.'s zero-knowledge proof protocol for prime factors.We find it needs to introduce a completely trustworthy third party to set up public system parameters.The requirement is inconsistent with the general assumption for zero-knowledge proof.We propose an attack against the Groth et al.'s protocol,which shows that the prover can collude with the third party to cheat the verifier.(3)There is a similar flaw in the Groth et al.'s circuit satisfiability protocol,which has to invoke the above zero-knowledge proof for one plaintext consisting of a single bit.It cannot prevent the prover from cheating the verifier.Moreover,the circuit satisfiability protocol needs to make use of bilinear groups with a big composite order.The huge computational cost is far beyond the range of possibility.(4)We analyze the Groth et al.'s computational zero-knowledge proof for circuit satisfiability which is based on their homomorphic commitment scheme,and point out that its commitment method is flawed amid the construction of indistinguishable witnesses.The above results show that these zero-knowledge proof protocols have not effectively solved related problems.In the future,the revelent model recognition,method discrimination,and calculation optimization should be further discussed.