1 BC with equality

1.1 Comparing equality of two committed inputs

Example 1.1 bit commitment based on GNI.

GNI : (G_{1}, G_{2}) ∈ GNI

P  V
ZK((G_{1},G_{2})∈GNI) >

commit(b_{1}),

G ≈ G_{b_{1}}

G >

commit(b_{2}),

G′ ≈ G_{b_{2}}

G′ >
G=π(G′) >
if G = π(G′) then accept b_{1} = b_{2}.

Example 1.2 bit commitment based on QNR.

y ∈ QNR_{n}[+1]

P  V
ZK(y∈QNR_{n}[+1]) >
commit(b_{1}),

z_{1} ≡ y^{b_{1}} ∗ r^{2} mod n,

r ∈_{R} Z_{n}^{∗},

z_{1} >
commit(b_{2}),

z_{2} ≡ y^{b_{2}} ∗ r^{′2} mod n,

r′ ∈_{R} Z_{n}^{∗},

z_{2} >

v:=rr′y^{b_{1}} >
if z_{1}z_{2} = v^{2} then accept b_{1} = b_{2}.

To prove b_{1} ≠ b_{2} P sends \sqrt{yz_{1}z_{2}}.

1.2 Computation on boolean circuits using committed inputs

We shall use the previous two examples to do computations on boolean circuits. Prover commits to three bits: b_{1}, b_{2}, b_{3} ∈ {0, 1}, s.t. B: b_{1} ∧ b_{2} = b_{3}. There are only four possible situations of B (see Table T), i.e. B (three bits) must belong to one of the following situation T_{j} (three bits).

Table T
T_{1} : 0 ∧ 0 = 0
T_{2} : 0 ∧ 1 = 0
T_{3} : 1 ∧ 0 = 0
T_{4} : 1 ∧ 1 = 1

We design the protocol by using the ”Cut and Choose” technique in order to prove that B ∈ T. P permutes the Table T then commit to (π(T)) to V.

P  V
commit(π(T)) >
c ∈_{R} {0, 1},
<^{c}
if c = 0,
π, unveil(π(T)) >
if c = 1,
ZK(B=T_{i}) >

Note:

1. π is a permutation of Table T.

2. Using example 1.1, P can show to V that the three committed bits B: b_{1}, b_{2} and b_{3} are equal to the three committed bits of T_{i} respectly.

If b_{1} ∧ b_{2} = b_{3}, Pr[accept]=1,

If b_{1} ∧ b_{2} ≠ b_{3}, Pr[accept]≤ 1/2^{k}, where k=# of rounds.

We can use this method for any logical gate: ∧, ∨, −, ⊕.

1.3 Rudich’s Trick

Now we are going to talk about a general way to obtain a bit commitment where we can prove equality based on any bit commitment. Here “Rudich’s Trick” is the way to show two committed bits are equal.

Suppose b = b′, where b, b′ ∈ {0, 1}, let u_{i}, x_{i} be random bits and v_{i}, y_{i} be defined according to u_{i} ⊕ v_{i} = b, x_{i} ⊕ y_{i} = b′, i = 1, ⋯ 2n. We shall use 4n committed bits to commit one bit.

Alice Bob

commit(b) :  commit(b′) :
α_{1} : C(u_{1}), C(v_{1})  C(x_{1}), C(y_{1}) : β_{1}
α_{2} : C(u_{2}), C(v_{2})  C(x_{2}), C(y_{2}) : β_{2}
⋮  ⋮
α_{2n} : C(u_{2n}), C(v_{2n})  C(x_{2n}), C(y_{2n}) : β_{2n}

where α_{i} and β_{i} are two committed bits and C denotes commit.

• Bob imposes two random permutations π_{α}, π_{β} to Alice who permutes α_{i} using π_{α} and β_{i} using π_{β}.

C(u_{9}), C(v_{9})  C(x_{2}), C(y_{2})
C(u_{n}), C(v_{n})  C(x_{7}), C(y_{7})
⋮  ⋮
C(u_{3}), C(v_{3})  C(x_{6}), C(y_{6})

• Regardless of b, u_{i}, x_{i} and v_{i}, y_{i} are either identical or opposite. Alice will claim for the first half of the lines whether they are “=” or “≠”.

C(u_{9}), C(v_{9})  =  C(x_{2}), C(y_{2})
C(u_{n}), C(v_{n})  ≠  C(x_{7}), C(y_{7})
⋮  ⋮
C(u_{41}), C(v_{41})  =  C(x_{63}), C(y_{63})
C(u_{99}), C(v_{99})  C(x_{n−9}), C(y_{n−9})
C(u_{2n}), C(v_{2n})  C(x_{55}), C(y_{55})
⋮  ⋮
C(u_{3}), C(v_{3})  C(x_{6}), C(y_{6})

for example:

b = b′ = 0  b = b′ = 1
0 ⊕ 0 = 0 ⊕ 0 : u_{i} = x_{i}, v_{i} = y_{i},  0 ⊕ 1 = 0 ⊕ 1 : u_{i} = x_{i}, v_{i} = y_{i},
0 ⊕ 0 = 1 ⊕ 1 : u_{i} ≠ x_{i}, v_{i} ≠ y_{i},  1 ⊕ 0 = 0 ⊕ 1 : u_{i} ≠ x_{i}, v_{i} ≠ y_{i}.

• For each line Bob randomly chooses to see the both left sides or both right sides, but not both sides, then Alice unveils them to Bob.

C(u_{9}), U(v_{9})  =  C(x_{2}), U(y_{2})
U(u_{n}), C(v_{n})  ≠  U(x_{7}), C(y_{7})
⋮  ⋮
C(u_{41}), U(v_{41})  =  C(x_{63}), U(y_{63})
C(u_{99}), C(v_{99})  C(x_{n−9}), C(y_{n−9})
C(u_{2n}), C(v_{2n})  C(x_{55}), C(y_{55})
⋮  ⋮
C(u_{3}), C(v_{3})  C(x_{6}), C(y_{6})

where U denotes unveil.

If Alice wants to cheat, suppose b=1, b’=0 and Alice cliams that α_{i} = β_{i}, for example:

b = 1  b′ = 0
α_{i} : 0 ⊕ 1 = 1 ⊕ 1 : β_{i}

With 1/2 probability, Bob will request to see the left sides and Alice unveils to him that (u_{i} = 0) ≠ (x_{i} = 1), then Bob rejects.

With 1/2 probability, Bob will request to see the right sides and Alice unveils to him that v_{i} = 1 = y_{i}, then Bob accepts. So if b ≠ b′, 1/2 probability Bob will be cheated.

Therefore, If b=b’, Pr[accept]=1, If b ≠ b′, Pr[accept]≤ (1/2)^{n}, at each line, if b ≠ b′, regardless of Alice’s

answer, the probability Bob finds out that Alice is cheating is 1/2.

After a test is conclusive, Alice can construct a new valid commitment to represent both b and b′ using the untouched commitments:

commit(b, b′) :
C(u_{99}), C(v_{99})
C(u_{2n}), C(v_{2n})
⋮
C(u_{3}), C(v_{3})
C(x_{n−9}), C(y_{n−9})
C(x_{55}), C(y_{55})
⋮
C(x_{6}), C(y_{6})