Zero knowledge proof: zkp with DDH assumption

Proof of zero knowledge ： have DDH Hypothetical ZKP

Diffie-Hellman part

We must prove that we still hold a secret ( private ) secret key , This is a very typical case . Then how can we put Victor and Peggy Binding to a proof infrastructure allows Peggy towards Victor Prove that she still has a private key ？ So , We will exchange Diffie-Hellman Key to bind Victor and Peggy.

stay DDH in , We have one by * g、g^a*、*gb、g^{ab }* A tuple of components , among a and b It's a secret .g^{a and g}b After the two sides exchange , Should be able to generate g^{ab}：

Chaum-Pedersen part

If Peggy Is the certifier , and Victor Is the verifier , that Peggy Need to show that she knows a secret value a. With Chaum-Pedersen ZKP,Victor Give Way Peggy Generate a ZKP To protect a secret . In the process , She will g^a (mod p) Value sent to Victor, When Victor Need to prove that she still knows a value , He will send a challenge value (s), then Alice Generate a random value , And back to y_1=g^{r and y_2=B}r. then Victor Check gz=A^s y_1 (mod p) and B^z=Cs y_2 (mod p) Whether it is equal or not .

stay Victor and Peggy After exchanging their secrets ,Victor Will hold g^a (mod p), Peggy Will hold g^b(mod p). For zero knowledge proof , Let's start like this ：

Peggy There is a secret value a And generate A = g^a.Victor The secret value of is b And generate B = g^b. They exchange A and B, And then use Diffie Hellman Method generation C.

Victor towards Peggy Send a commitment：

Peggy Calculate a random value ：

She sent it to Victor：

and ：

Peggy Also send ：

Victor Will check the ：

and ：

If all this is true , that Peggy It has been proved that she knows the secret (a). because ：

Code

The code is as follows ：

import random
import libnum
import sys

bitsize=128
if (len(sys.argv)>1):
    bitsize=int(sys.argv[1])
      
p=libnum.generate_prime(bitsize)
s=random.getrandbits(bitsize)
g=2
a=random.getrandbits(bitsize)
b=random.getrandbits(bitsize)
c=random.getrandbits(bitsize)

r=random.getrandbits(bitsize)
A=pow(g,a,p)
B=pow(g,b,p)
C=pow(g,a*b,p)

y1=pow(g,r,p)
y2=pow(B,r,p)

z=(r+a*s) % (p-1)


print("== Chaum-Pederson ZKP with DDH ==")
print("p=",p)
print("a=",a)
print("A=g^a (mod p)=",A)
print("b=",b)
print("B=g^a (mod p)=",B)
print("ab=",a*b)
print("C=g^{ab} (mod p)=",C)


print("\nProof: g^z = A^s y1")
val1= pow(g,z,p)
val2=(pow(A,s,p)*y1) % p
print("Val1=",val1)
print("Val2=",val2)

if (val1==val2):
    print("- Proof verified")
    
print("\nProof: B^z = C^s y2")
val3= pow(B,z,p)
val4=(pow(C,s,p)*y2) % p

print("Val3=",val3)
print("Val4=",val4)

if (val3==val4):
    print("- Proof verified")

256 An example of the operation of bitwise primes is as follows ：

== Chaum-Pederson ZKP ==
p= 71808837207067558396943502247178805470599306337269585872075038503116361400603
a= 36623398984913964172485596625205226031763309121917034188846578869320021978402
A=g^a= 32096207796582799691444233880948982714496908564580085529419678203181985482397
b= 31626404664308059618102781249870451013488637545242770934698960204990436278054
B=g^a= 22868249499514124460303251323889043821880224466294750444534923941031732565838
ab= 1158266436479298052448345755868228483694002563526288816181771624565721107667448582344993414115064433575649547672009235534272667805336831732117954454589708
C=g^{ab}= 8021151953795073005899136029637476282156155200732630284950825682466003109726
Proof: g^z = A^s y1
Val1= 9590670516289397297344719778854690756344241363231213529959870845950311348445
Val2= 9590670516289397297344719778854690756344241363231213529959870845950311348445

- Proof verified
Proof: B^z = C^s y2
Val3= 56336209634019548929170814618015392124101293159018455662661735618180853220223
Val4= 56336209634019548929170814618015392124101293159018455662661735618180853220223

- Proof verified

Conclusion

The only direction of network security is zero trust mode . One way to prevent the leakage of sensitive information and data is not to store these secrets , Instead, they are replaced by random oracle machines . Even if these prophecies are leaked , True secrets will not be revealed . In the method I outlined , We can easily convert the generated value of the proof into NI-ZKP（ Non interactive ZKP）.

Source：https://medium.com/asecuritysite-when-bob-met-alice/hellman-pedersen-and-chaum-zkps-with-the-decisional-diffie-hellman-ddh-assumption-4ed7d4a3220d

About

ChinaDeFi - ChinaDeFi.com It's a research driven DeFi Innovation organizations , We are also a blockchain development team . From all over the world every day 500 Close to a good source of information 900 In the content , Looking for deeper thinking 、 Sort out more systematic content , Provide decision-making assistant materials to the Chinese market at the fastest speed .

Layer 2 friends sharing same hobby - Welcome to Layer 2 Interested blockchain technology enthusiasts 、 Study and analyze people and Gavin（ WeChat : chinadefi） contact , Discuss together Layer 2 Landing opportunities . Please pay attention to our official account of WeChat “ Decentralized financial community ”.