Commitment schemes

In setup phase the involved parties agree to use the 'SHA1' hashing:

  import random
  from hashlib import sha1

During the commit phase, Peggy 'calls' her bet m which will be kept secret for now, seals the bet and releases the commitment value c:

  m = 6
  c = sha1(bytes(m)).hexdigest()
  print(c)

7722745105e9e02e8f1aaf17f7b3aac5c56cd805

Before the verify phase the following events happen:

• Victor rolls the dice, let's assume it shows a 6
• Peggy reveals the secret message m

Then, during verify phase Victor hashes the dice outcome and checks against commitment value c. If they are equal then Peggy won.

  o = 6
  check = sha1(bytes(o)).hexdigest()
  print("Peggy won!") if c == check else "Try again!"

Peggy won!

Note: We can easily notice that naive hash-based commitment is both computationally hiding and binding becasue an adversary with unlimited computation power can execute a preimage attack (by brute forcing or other algorithms) and:

• as a verifier/receiver - find the committed message m (the hiding property)
• as a prover/sender - find another message m' to open the commitment (the binding property)

So far so good but there is a problem with the above implementation: since all possible dice outputs are known in advance, Victor (or third-party) can precompute the hashes for all possible outcomes (known as Rainbow table attack) and bet against Peggy.

We can do better, instead of hashing only the committed message itself, we can concatenate with another random value called salt (or blinding factor) which will also be kept secret.

  m = 6
  s = random.randint(1, 9999)
  c = sha1(bytes(m + s)).hexdigest()
  print(c)

9a8e3678280e57c9b9f9d66f771a8f896f8517fe

This time, before the verify phase, Peggy releases both message value s and random value (or opening value) s.

  o = 6
  check = sha1(bytes(m + s)).hexdigest()
  print("Peggy won!") if c == check else "Try again!"

Peggy won!

Note: Our salted hash-based commitment is also computationally hiding and binding because an unbounded adversary can find the concatenated value m + s then find the committed message m, also a prover/sender adversary can find another message m' to open the commitment.

During setup phase we agree on ElGamal's parameters. The p and g parameters are explained in ElGamal blog while h is another randomly chosen generator of prime order q.

from random import randint
p = 11
q = 7
g = 3
s = randint(1, q-1)
h = g**s % p
print("h:", h, ", group:", [h**i % q for i in range(1, q)])

h: 5, group: [5, 4, 6, 2, 3, 1]

During commit phase, Peggy bets on message m, generates random value r and releases commitment tuple (c0, c1). Also, notice the blinding factor h**r that is thrown into the c1 mix.

m = 6
r = randint(1, q-1)
c0 = ((g**r)) % p
c1 = ((g**m) * (h**r)) % p
print((c0, c1))

(3, 4)

Then roll the dice, Peggy reveals the message m and the opening value r and Victor checks the commitment, if equal, Peggy wins.

check = (g**m * h**r) % p
print("Peggy won!") if check == c1 else "Try again!"

Peggy won!

Note: maybe this is not so obvious but ElGamal commitment is computational hiding and perfectly binding because an unbounded adversary can try all possible values for r and solve the discrete logarithm (dlog) behind c0 commitment, then using r solve the dlog behind c1 commitment and figure out m.

Pedersen commitment is similar to ElGamal above with a few differences that we will see below:

from random import randint
p = 11
q = 7
g = 3
s = randint(1, q-1)
h = g**s % p
print(h)

5

Peggy commits on message m, generates random r and releases commitment c:

m = 6
r = randint(1, q-1)
c = ((g**m) * (h**r)) % p
print(c)

4

At a later time the she reveals (m, r) tuple to Victor to verify the commitment.

check = (g**m * h**r) % p
print("Peggy won!") if check == c else "Try again!"

Peggy won!

Note: the Pedersen commitment is perfectly hiding and computationally binding because:

• as a verifier/receiver - has no way to uniquely identify the committed message m, there is an infinite number of (m, r) pairs that satisfy the commitment equation
• as a prover/sender - with infinite computation power can solve the dlog and find another message m'

So far, we can see that Pedersen commitment provides better security (perfectly hiding) than hash-based commitments but it has another property that makes it special.

  p = 103
  F = FiniteField(p)
  E = EllipticCurve(F, [0, 7])
  print(E)
  G = E([97, 10])
  print(G)
  s = randint(2, p)
  H = s * G
  print(H)

Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 103
(97 : 10 : 1)
(33 : 10 : 1)

  m = 2
  r = randint(2, p)
  C = m * H + r * G
  print(C)

(53 : 7 : 1)

  r = randint(2, p)
  CI1 = 2 * H + r * G
  CI2 = 5 * H + r * G
  CO = 6 * H + r * G
  CC = 1 * H + r * G

  print "YOU ARE A CRYPTOSTAR!" if CI1 + CI2 == CO + CC else "YOU SUCK!"

YOU ARE A CRYPTOSTAR!

Let's recap:

1. hash-based commitments - provide both computationally hiding and binding
2. ElGamal - is computationally hiding and perfectly binding
3. Pedersen - is perfectly hiding and computationally binding

Alright….

• What about a commitment scheme that is both perfectly hiding and binding?
• I am afraid you won't like the answer because hiding and biding properties are mutually exclusive, you can only have one or the other, not both
• What the heck are switch commitments then?
• It is just a combination of ElGamal and Pedersen commitments with the ability to toggle one or the other on the fly in case shit hits the fan and quantum computers break encryption schemes over night