Zero Knowledge Proofs with Elliptic Curves and Schnorr

Prof Bill Buchanan OBE FRSE
2 min readMay 21, 2024

With Zero Knowledge Proofs (ZKPs), Peggy can have a signature and then use this to prove that she still knows her secret. The method we will use is based on Schnorr’s protocol [1][here]:

Let’s say that Peggy wants to prove that she knows her password (secret) to Victor. First we take a hash of this with:

k=H(secret||salt) (mod n)

and where n is the order of the curve. We then convert this to a point with:

S=k.G

This is a signature that is represented as an (x,y) point. We can then publish this signature publicly, and where subsequent messages are proven to have been produced by the same key. Overall, the signature does not reveal anything about the data.

Messages are thus verified with the signature. For this the verifier (Victor) produces a random message (t) and sends to Peggy for them to generate a proof against her public signature. Victor produces:

t=Random_token()

and send this to Peggy. Peggy then produces:

k=H(secret || salt) (mod n)

Then creates a random value r and then:

R=r.G

c=H(t || R || salt)

m=r+c.k

The value of (c,m) is the proof, and Peggy sends this to Victor. Victor then computes:

M=m.G

C=c.S

This is valid if H(t || MC || salt)==c

This works because:

H(t|| MC || salt)=H(t || m.Gc.S || salt)=H(t || (r+ck).Gc.k.G || salt)=H(t || R ||salt)=c

and where “||” represents the concatenation of bytes.

Coding

The coding is [here]:


from noknow.core import ZK, ZKSignature, ZKParameters, ZKData, ZKProof

import sys

peggy_pass="Test 456"
victor_pass="Test 123"

if (len(sys.argv)>1):
peggy_pass=str(sys.argv[1])
if (len(sys.argv)>2):
victor_pass=str(sys.argv[2])

peggy_zk = ZK.new(curve_name="secp256k1", hash_alg="sha3_256")
sig= peggy_zk.create_signature(peggy_pass)


victor_zk = ZK.new(curve_name="secp384r1", hash_alg="sha3_512")
ZKSignature = victor_zk.create_signature(victor_pass)


peggy_signature = ZKSignature.load(sig.dump())
peggy_zk = ZK(peggy_signature.params)


token = victor_zk.sign(victor_pass, peggy_zk.token())




proof = peggy_zk.sign(peggy_pass, token).dump()

print("Peggy password: ",peggy_pass)
print("Victor password: ",victor_pass)
print("\nToken: ",token)
print("\nProof: ",proof)

proof = ZKData.load(proof)


if not victor_zk.verify(token, ZKSignature):
print("\nNo Success")
else:
print("\nSuccess")

A sample run is:

Peggy password:  Password123
Victor password: Qwerty123

Token: ZKData(data='81930730754975846550651490215858155325882479908069374833713307654784472301582', proof=ZKProof(params=ZKParameters(alg='sha3_512', curve='secp384r1', s=30362916872582642706586062362154770243174361856544376065482591318283091333274230929425547648048534537594676220516460), c=22343220969211452067991264626309151572084864743363500494981585814687978888806693886674828609333605909945220782952734, m=508237979522639044600634315780116214512265292822324425710203106179778359099968666235103885823384722916635873478605604063015728894342060254156429024054071358094806550772823751843262445696956554562144941252457587192557557640490735938))

Proof: ZKData(data='81930730754975846550651490215858155325882479908069374833713307654784472301582', proof=ZKProof(params=ZKParameters(alg='sha3_512', curve='secp384r1', s=30362916872582642706586062362154770243174361856544376065482591318283091333274230929425547648048534537594676220516460), c=22343220969211452067991264626309151572084864743363500494981585814687978888806693886674828609333605909945220782952734, m=508237979522639044600634315780116214512265292822324425710203106179778359099968666235103885823384722916635873478605604063015728894342060254156429024054071358094806550772823751843262445696956554562144941252457587192557557640490735938))
eyJwYXJhbXMiOnsiYWxnIjoic2hhM18yNTYiLCJjdXJ2ZSI6InNlY3AyNTZrMSIsInMiOjUxNzUxOTUzMDQ5MzE2Njk3MTU0NjU4NzU1OTUyODYyOTMzNDg0ODE4MDg1MzQ3MDk5NTUxODk0OTA0ODYwOTc5MDU3ODc4MDE1MTU1fSwiYyI6NDA5MjEyMTYwNjUyNDAzMjM5NDc1NzU1MDY2MzUyOTYxNjQ5OTQzNzgxOTM1Njk1NjE4OTgwNjUyMDIxOTMzNDE3NTYwMDA1MjkxODcsIm0iOjIzNTQ3MzE3MDIxODY0MDM5OTEwOTExNzkzMTI0ODgyMjIzMTg1MjAyNzMyODg1MDkyNDYxMzM1ODcwNjI0MzE2NzI5MTAyNTYwNjA2MTYzNjAyNTA1MjUzNTcwNjM2OTA1MDI0MzYxODg4NTI5ODI5NTE4NDQyNzE3ODgzODIyMTU0NzczNDg1NDU4NDYyMTk4NDk0NzM3NjN9

Success

Conclusions

If you love ZKPs, try here:

References

[1] Chatzigiannakis, I., Pyrgelis, A., Spirakis, P. G., & Stamatiou, Y. C. (2011, October). Elliptic curve based zero knowledge proofs and their applicability on resource constrained devices. In 2011 IEEE eighth international conference on mobile ad-hoc and sensor systems (pp. 715–720). IEEE.

--

--

Prof Bill Buchanan OBE FRSE
Prof Bill Buchanan OBE FRSE

Written by Prof Bill Buchanan OBE FRSE

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. Based in Edinburgh. Old World Breaker. New World Creator. Building trust.

No responses yet