To A Life Dedicated To Anonymity …

To A Life Dedicated To Anonymity …

Our cybersecurity world has not been built by large and faceless companies, but by individuals who created truly inspirational work and who have since provided us with the foundations of our digital world. And thus we turn to people like Ron Rivest, Whitfield Diffie, Ralph Merkle [here], Adi Shamir [here], Stephen Pohlig [here] … and to David Lee Chaum.

David has contributed so much to cybersecurity, and especially around anonymity methods. In 1981, he laid down a foundation of anonymity with his paper on “Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms”. He also went on to develop the first anonymised electronic cash method (ecash) and created the first electronic money company (DigiCash).

In 1991, the mighty Torben Pedersen published his classic paper of “Non-interactive and information-theoretic secure verifiable secret sharing.” [pdf] and were he outlined a method that would soon be known as a Pedersen Commitment [here]:

This method is now being used extensively with anonmyisation in cryptocurrencies. Pedersen actually acknowledges that his paper owned a great deal to an unpublished paper written by Chaum. In the same year they collaborated in publishing a paper which defined one of the first new zero-knowledge proof techniques ... the Chaum-Pedersen method.

Chaum-Pedersen Zero Knowledge Proof Method

What a crazy data world we live in. On a regular basis we give away our sensitive information. We gladly pass passwords to companies, and then who hash it. Unfortunately if someone gets the hashed value, it is not too difficult to find out the original password, even if we add salt to the hash. So what’s the solution? Well our data world ready for Zero Knowledge Proofs (ZKPs), and where Peggy provides to Victor that she still knows her secret.

The Chaum-Pedersen Zero Knowledge Proof can be used to show that Peggy (the Prover) knows a secret to Victor (the Verifier). We initially define the values of ⟨g,A,B,C⟩ = ⟨g,g^a,g^b,g^{ab}⟩, and the basic method is defined as:

Peggy (the Prover) defines a secret value of r.

Peggy sends Vector (the Verifier) the commitments of:

y1=g^r and

y2=B^r

Victor generates a random value (c) and sends it to Peggy.

Peggy computes z=r+as (mod q) and sends it to Victor.

Victor checks that g^z=A^s y1 (modq)

and:

Victor checks that B^z=C^s y2 (modq)

An outline of the code is [demo]:

import random

q=10009

s=random.randint(1,1000)
r=random.randint(1,1000)

if (len(sys.argv)>1):
        r=str(sys.argv[1])

g=3
a=10
b=13
A=g**a % q
B=g**b % q
C=g**(a*b) % q

y1=g**r % q
y2=B**r % q

z=(r+a*s) % q

print "Victor and Peggy agree of (g,g^a, g^b and g^ab) =(",g,A,B,C,")"
print "\nPeggy defines a secret value (r)",r
print "Peggy sends y1 (g^r, B^r)=(",y1,y2,")"

print

print "Victor sends a challenge (s)=",s

print "Peggy computes z=r+as (mod q)=",z

print "\nVictor now checks these are the same"
print "Victor checks g^z=",g**z % q

print "Victor checks A^s y1=",(A**s * y1) % q

print "\nVictor now checks these are the same"
print "Victor checks B^z=", B**z % q
print "Victor checks C^s y2=",(C**s * y2) % q

A sample run is [demo]:

Victor and Peggy agree of (g,g^a, g^b and g^ab) =(3 9004 2892 5980 )

Peggy generates random number (r) 887
Peggy sends y1 (g^r, B^r)=( 4584 834 )

Victor sends a challenge (s)= 396
Peggy computes z=r+as (mod q)= 4847

Victor now checks these are the same
Victor checks g^z= 9541
Victor checks A^s y1= 9541

Victor now checks these are the same
Victor checks B^z= 5923
Victor checks C^s y2= 592

Conclusions

We need to give up our 1980s viewpoint of data, and adopt the methods used within blockchain, and where privacy-preserving methods are just seen as a natural part of the toolkit for building systems.