The Pedersen commitment allows us to commit to a message, but not actually reveal it until some time in the future. We can also use the Pedersen commitment to add commitment values (and thus implement partial homomorphic encryption):
Pedersen Commitment |
Method
In the Pedersen commitment we take two large prime numbers (\(p\) and \(q\)) and we create a generator value (\(g\)) which is of the order of \(q\) and a subgroup of \(Z_p^*\). Then \(s\) becomes a secret from 0 to \(Z_q\), and we calculate:
\(h=g^s \pmod p\)
The sender now creates a commitment for a message (\(m\)) and with a random number (\(r\)):
\(c=g^m h^r \pmod p\)
The sender can then send \(c\) to the receiver. Next, the sender will then reveal \(m\) and \(r\) for the commitment, and the receiver verifies with:
\(c=g^m h^r \pmod p\)
If the values match, the receiver has proven the commitment.
We can also use as homomorphic encryption, and where we multiply commitments, and which is equivalent to adding the secret values.
Coding
The following provides some code [code]:
from Crypto import Random from Crypto.Util import number import sys def generate(param): q = param[1] g = param[2] h = param[3] return q,g,h class verifier: def setup(self, security): p = number.getPrime(2 * security, Random.new().read) q = 2*p + 1 g = number.getRandomRange(1, q-1) s = number.getRandomRange(1, q-1) print("Secret value:\t",s) h = pow(g,s,q) param = (p,q,g,h) print("p=",p) print("q=",q) print("g=",g) print("h=",h) return param def open(self, param, c, x, *r): result = "False" q,g,h = generate(param) sum = 0 for i in r: sum += i res = (pow(g,x,q) * pow(h,sum,q)) % q if(c == res): result = "True" return result def add(self, param, *cm): addCM = 1 for x in cm: addCM *= x addCM = addCM % param[1] return addCM class prover: def commit(self, param, x): q,g,h = generate(param) r = number.getRandomRange(1, q-1) c = (pow(g,x,q) * pow(h,r,q)) % q return c, r security = 80 msg1 = 1 msg2 = 2 if (len(sys.argv)>1): msg1=int(sys.argv[1]) if (len(sys.argv)>2): msg2=int(sys.argv[2]) v = verifier() p = prover() param = v.setup(security) c1, r1 = p.commit(param, msg1) c2, r2 = p.commit(param, msg2) addCM = v.add(param, c1, c2) print("\nMsg1:",msg1) print("Msg2:",msg2) print("\nc1,r1:",c1,",",r1) print("c2,r2:",c2,",",r2) print("\nWe can now multiply c1 and c2, which is same as adding Msg1 and Msg2") print("\nCommitment of adding (Msg1+Msg2):\t",addCM) result1 = v.open(param, c1, msg1, r1) result2 = v.open(param, c2, msg2 , r2) print("\nResult of verifying c1:\t\t",result1) print("Result of verifying c2:\t\t",result2) result = v.open(param, addCM, msg1 + msg2 , r1, r2) print("Result of verify Msg+Msg2:\t",result)
A sample run is:
Secret value: 1600218503816068609616068262186085211385912913449 p= 835633126610936170404251455173303609923742171077 q= 1671266253221872340808502910346607219847484342155 g= 853879156962728674489578584402624767640115848839 h= 312816528258481903392461143384659987330939968504 Msg1: 70 Msg2: 70 c1,r1: 931432606187308599362760090383550998212817597419 , 1331540638789558839751757756218591899240229287857 c2,r2: 377312755894089489173415862148929013782547633796 , 1062296325886690334534931368033516581934275153224 We can now multiply c1 and c2, which is same as adding Msg1 and Msg2 Commitment of adding (Msg1+Msg2): 943416350824651526788742276019896656762684796624 Result of verifying c1: True Result of verifying c2: True Result of verify Msg+Msg2: True
Presentation
The following is a presentation [slides]: