When Bob Bought Some Vouchers For Carol, Trent and Faith

And Where Alice Can’t Trace Them Back to Bob

A demo of the method I will present is [here].

So how can Bob purchase 10 vouchers for presents for Carol, Trent and Faith, and then for Alice’s store to not be able to tell it was Bob who had bought them. For this, we can turn to obvious transfer, and zero-knowledge proof (ZPK) method. One of the best around uses the power of elliptic curve methods and is defined as EC-VOPRF (Elliptic Curve Verifiable Oblivious Pseudo-Random Function).

Now Bob wants to buy 10 vouchers from Alice, and he wants to give them to Carol, Trent and Faith. For this he generates 10 random numbers (x1, x2, … x10). He then matches these onto elliptic curve points (finding the nearest x-axis point). For these 10 vouchers, he then creates a random value for a blinding factor (b). Bob then multiplies each of the elliptic curve points with b, and hands these 10 elliptic curve points to Alice, and pays for 10 vouchers.

Alice then multiplies each of these points with her private key (k), and sends them back to Bob. When Bob receives these he now unblinds each voucher by dividing each of them by his blinding factor (b). The values he now has are k×X1, k×X2, … k×X10.Next, Bob gives Carol the values of X1 and k×X1, X2 and k×X2 to Trent, and X3 and k×X3 to Faith. Each of them can then go to Alice’s shop and give Alice their values. For Carol, Alice then checks that the value of X1 multiplied by her private key (k) is the other value that Carol has given her (k×X1). If this checks out, she will approve the purchase, but will not know where the voucher came from. For this only Bob is able to generate the values of X1 and k×X1, as Alice only knows k.

And there you go. We have created a world where Alice cannot determine where the vouchers came from, and we have preserved the rights of Bob to privacy. We have also created purchase receipts which can be trusted, but which cannot be tracked. If an auditor wants to resolve, Bob can reveal his blinding factor.

A sample run with a blinding factor of 200 is:

`Bob's secret key:	14740736474426194531991971984653537731905408749855764823599798340081744951236Bob's public key:	(93337810080056808509143628030711186374649707518966393007145508355141043725976L, 89984156688937262044671618721504988493956786224984493903982837891549653699065L)Alice's private key:	89305535952581699375152380663798359425217323217249314939419531091958137015823Bob's blinding value:	200==========================Bob sends:	(18596347454806314617546420688351915830023283853668514133074243099405745649845L, 64617527428093632813388283524274192193044853232912157518001869558548410052218L)Alice sends:	(31878088913995653806919695713432488276334299481378560104342584683002673166698L, 103705587118533077091760072597215457686031621435501948801185592847662523540405L)Divide by blinding:	(17518998733162042340917617062932188545103969459451983686440483965055076635903L, 110235880626729109887528707294137377769315565282992016601256532683996902787041L)Alice Private Key times Bob Public:	(17518998733162042340917617062932188545103969459451983686440483965055076635903L, 110235880626729109887528707294137377769315565282992016601256532683996902787041L)`

The following is an outline of the code:

`import collectionsimport hashlibimport randomimport binasciiimport sys`
`EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h')`
`curve = EllipticCurve(    'secp256k1',    # Field characteristic.    p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,    # Curve coefficients.    a=0,    b=7,    # Base point.    g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,       0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),    # Subgroup order.    n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,    # Subgroup cofactor.    h=1,)`
`# Modular arithmetic ##########################################################`
`def inverse_mod(k, p):    """Returns the inverse of k modulo p.    This function returns the only integer x such that (x * k) % p == 1.    k must be non-zero and p must be a prime.    """    if k == 0:        raise ZeroDivisionError('division by zero')`
`    if k < 0:        # k ** -1 = p - (-k) ** -1  (mod p)        return p - inverse_mod(-k, p)`
`    # Extended Euclidean algorithm.    s, old_s = 0, 1    t, old_t = 1, 0    r, old_r = p, k`
`    while r != 0:        quotient = old_r // r        old_r, r = r, old_r - quotient * r        old_s, s = s, old_s - quotient * s        old_t, t = t, old_t - quotient * t`
`    gcd, x, y = old_r, old_s, old_t`
`    assert gcd == 1    assert (k * x) % p == 1`
`    return x % p`
`# Functions that work on curve points #########################################`
`def is_on_curve(point):    """Returns True if the given point lies on the elliptic curve."""    if point is None:        # None represents the point at infinity.        return True`
`    x, y = point`
`    return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0`
`def point_add(point1, point2):    """Returns the result of point1 + point2 according to the group law."""    assert is_on_curve(point1)    assert is_on_curve(point2)`
`    if point1 is None:        # 0 + point2 = point2        return point2    if point2 is None:        # point1 + 0 = point1        return point1`
`    x1, y1 = point1    x2, y2 = point2`
`    if x1 == x2 and y1 != y2:        # point1 + (-point1) = 0        return None`
`    if x1 == x2:        # This is the case point1 == point2.        m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)    else:        # This is the case point1 != point2.        m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)`
`    x3 = m * m - x1 - x2    y3 = y1 + m * (x3 - x1)    result = (x3 % curve.p,              -y3 % curve.p)`
`    assert is_on_curve(result)`
`    return result`
`def scalar_mult(k, point):    """Returns k * point computed using the double and point_add algorithm."""    assert is_on_curve(point)`
`    if k % curve.n == 0 or point is None:        return None`
`    if k < 0:        # k * point = -k * (-point)        return scalar_mult(-k, point_neg(point))`
`    result = None    addend = point`
`    while k:        if k & 1:            # Add.            result = point_add(result, addend)`
`        # Double.        addend = point_add(addend, addend)`
`        k >>= 1`
`    assert is_on_curve(result)`
`    return result`
`# Keypair generation ################################################`
`def make_keypair():    """Generates a random private-public key pair."""    private_key = random.randrange(1, curve.n)    public_key = scalar_mult(private_key, curve.g)`
`    return private_key, public_key`
`if (len(sys.argv)>1):	b=int(sys.argv)`
`bobSecretKey, bobPublicKey = make_keypair()aliceSecretKey, alicePublicKey = make_keypair()`
`print "\nBob\'s secret key:\t", bobSecretKeyprint "Bob\'s public key:\t", bobPublicKeyprint "Alice\'s private key:\t", aliceSecretKeyprint "Bob's blinding value:\t",b`
`print "=========================="`
`bobsend = scalar_mult(b,bobPublicKey)`
`print "Bob sends:\t",bobsend`
`alicesend = scalar_mult(aliceSecretKey,bobsend)`
`print "Alice sends:\t",alicesend`
`val = scalar_mult(inverse_mod(b,curve.n),alicesend)`
`print "Divide by blinding:\t",val`
`print "Alice times Bob Public:\t",scalar_mult(aliceSecretKey,bobPublicKey)`

And outline is here:

For voting:

Conclusions

A simple conclusion … we need to blind sensitive data, and respect the rights of privacy of individuals. The core business model of the Internet is to track citizens, and increasingly we are being mined for our data on a continual basis.