Zero Knowledge Proof of a preimage, without revealing the preimage

proof-of-insecurity.txt

# Random element of S
ℝ ∈ S = λS -> {ω ∈ Ω | ℝ_ω ∈ S}

# A homomorphic function which transforms `x` from its additive
# group into its equivalent in the multiplicative group
G^x = {λx | x ∈ Z_(q-1)} -> X

# Maps `x` to `X` within `Z_q` while adhering to the random oracle model
H = λx -> X ∈ Z_q

# a, n and c are 'secret parameters'
# Alice knows `a`, Bob knows `b` and `c` is known by both
a, b, c <- ℝ ∈ Z_q

# X and Y are the public parameters
A, B <- G^a, G^b

# Generating the preimage proves knowledge of `A`, `B` and `c`
p = (a+b)*c % Z_q
  = (a*c + b*c) % Z_q

# Proof of the preimage discloses neither `A`, `B` or `c`
P = G^p
  = (A+B)^c
  = A^c + B^c

w = H(c)

T = G^w

z = H(P||T)
Z = G^z

y = (w + (p*z)) % Z_q
  = (w + (z*p)) % Z_q


S = G^y
  = T+(P^z)
  = T+(Z^p)
  = T+(((A+B)^c)^z)
  = T+(((A+B)^z)^c)

# Therefore, with only knowledge of `A` and `B`, `c` and `z` Alice can forge a signature on behalf of Bob, without needing `b`

zero-knowledge-proof.py

from py_ecc import bn128
from random import randint
from hashlib import sha256
from py_ecc.bn128 import add, multiply, curve_order, G1, eq

def bytes_to_int(x):
    o = 0
    for b in x:
        o = (o << 8) + ord(b)
    return o

rands = lambda: randint(1, curve_order - 1)
sbmul = lambda s: multiply(G1, s)
hashs = lambda *x: bytes_to_int(sha256('.'.join(['%X' for _ in range(0, len(x))]) % x).digest()) % curve_order
hashp = lambda *x: hashs(*[item.n for sublist in x for item in sublist])
ecdhs = lambda A, b: hashp(multiply(A, b))


"""
Given public knowledge of `y`, `Y` and `(X+Y)^z`, prove that you know `Y`
without revealing `y`, `Y` or `z`.

This mechanism forms the basis of an exchange between two parties, 
Alice and Bob.

 1) Alice proves knowledge of `y` so an honest verifier with only `Y`.
 2) This reveals `y` to Bob
 3) Bob then reveals knowledge of `y` to an honest verifier with only `(X+Y)^z`

Both Alice and Bob can verify each other are honest with knowledge of `X`, `Y` and `z`.

An observer cannot link the actions of Alice and Bob without learning `z`.

By learning `z` and `y` an observer can determine what `X` is from `(X+Y)^z`
and subsequently determine that Alice's proof of `y` is related to Bob's proof of `y`.

Given `(X+Y)^z - Y^z = X^z` is a valid curve point, this creates an oracle of proof.

`z` can be derived `ECDH(X, y)` or `ECDH(Y, x)`, so if `X` is ever revealed
then `z` will be known too.
"""


exch_x = rands() # Only Bob knows `x`
exch_y = rands() # Bob learns `y` from the exchange after Alice reveals it


# Alice and Bob know X, Y and z
X = sbmul(exch_x)
Y = sbmul(exch_y)
exch_z = rands()


# Only Bob can prove knowledge of the preimage without revealing `y`
preimage = ((exch_x + exch_y) * exch_z) % curve_order
B = sbmul(preimage)
assert B == multiply(add(X, Y), exch_z)


# Bob constructs Schnorr proof of knowledge of `preimage`
# Because `w` and `t` are fixed to specific values and
# cannot be changed the attack against Schnorr protocol fails.
w = hashs(exch_z)
t = sbmul(w)
c = hashp(B, t)
Proof = w + (c * preimage) % curve_order


# Honest verifier checks proof of `y` without knowing `X`, `Y` or `z`
# Verifier knows `B`, `t`, will only allow Bob to prove
# This requires one PointAdd, two ScalarMult and one `Hash` operations
v_c = hashp(B, t)
v_x = add(t, multiply(B, v_c))
v_s = sbmul(Proof)
assert eq(v_x, v_s)