Happy Birthday to John Napier … Helping To Build A More Trusted World

Last week (4 April) wasthe birthday of John Napier, and who is one of Edinburgh’s (and the world’s) greatest scientists. I am so proud to work in the same tower that John Napier accompanied all those years ago. He may be forgotten by many and disliked by pupils but he is one of the true geniuses that changed our world.

And so, we are now building a new world build on cryptography, and with methods build on the factorization of prime numbers struggling to cope with the advance of technology, it is to discrete logarithms that we increasingly look too for our new inspirations.

For new ways of building trust, it is discrete logarithms that provide us with a way to protect privacy. In the following, I have created a program which allows voters to hide their voting

import random
import math
import sys
g=2
p=67
nvoters = 5
voter = [int] * nvoters
public = [int] * nvoters
Y = [int] * nvoters
make_votes = [int] * nvoters
vote = [int] * nvoters
vote[0]=0
vote[1]=0
vote[2]=0
vote[3]=0
vote[4]=0
def extended_euclidean_algorithm(a, b):"""
    Returns a three-tuple (gcd, x, y) such that
    a * x + b * y == gcd, where gcd is the greatest
    common divisor of a and b.
    This function implements the extended Euclidean
    algorithm and runs in O(log b) in the worst case.
    """
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a
    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
    return old_r, old_s, old_t

def inverse_of(n, p):"""
    Returns the multiplicative inverse of
    n modulo p.
    This function returns an integer m such that
    (n * m) % p == 1.
    """
    gcd, x, y = extended_euclidean_algorithm(n, p)
    assert (n * x + p * y) % p == gcd
    if gcd != 1:
        # Either n is 0, or p is not a prime number.raise ValueError('{} has no multiplicative inverse ''modulo {}'.format(n, p))
    else:
        return x % p
print "Votes: ",vote[0],vote[1],vote[2],vote[3],vote[4]
print "----"
for i in range(0,nvoters):
	voter[i] = random.randint(1, 30) 
for i in range(0,nvoters):
	public[i] = g**voter[i]  % p
for i in range(0,nvoters):
	Y[i]=1
	for j in range(0,i): 
		Y[i] = (Y[i] * public[j]) % p
	for j in range(i+1,nvoters):
		Y[i] = Y[i] * inverse_of(public[j],p) % p
for i in range(0,nvoters):
	print "Public value: ",public[i]
for i in range(0,nvoters):
	print "Y value: ",Y[i]
for i in range(0,nvoters):
	make_votes[i] = (Y[i]**voter[i])*(g**vote[i]) % p
result = make_votes[0]
for i in range(1,nvoters):
	result = (result *make_votes[i]) % p
for i in range(0,nvoters):
	print "Vote ",make_votes[i] 
print "---"
print "Vote tally: ",math.log(result)/math.log(g)

We see the continual usage of the operation G (a generator) to the power of x:

Y = G^x

In a coding form this looks like:

Y = G**x

John would we this as a log base of G, and would immediately say that to find x we would have to take the inverse log to the base G of x. For example:

Y = 6³ = 6 x 6 x6 = 216

To take the inverse log we would get:

invlog[6](216) = log10(216)/log10(6) = 6

But we are not protecting any values here, so how do we protect the values. we bring in a prime number and use the mod operator:

Y = G^x mod P

now it is difficult (if G^x is much larger than P) to actually find the value of x that will give us a given Y value. Note that only certain values of G and P can be used together.

Bob, Alice and Trent can agree on G and P, and then Trent can calculate their total salary if Bob cases and encrypted value of:

Bob Salary (Encrypted) = G^{Bob salary} mod P

and Alice does the same:

Alice Salary (Encrypted) = G^{Alice salary} mod P

Trent then takes the encrypted values and multiplies them today, and returns the result, and which should be:

G^{Bob salary} x G^{Alice salary} = G^{Bob salary + Alice salary}

More details on how the method works here.

Homomorphic encryption

It is now thanks to John Napier that we can now look to build privacy into everything that we do. One challenge is to make sure that we can operate on encrypted values. In we can perform mathematical operations on data without actually revealing the data.

With homomorphic encryption, defined by Craig Gentry in 2010 [here], we can operate on data without ever decrypting it. Craig defined a scenario where Alice had a jewellery box, which she locked with her key, and where her workers could not gain access to the gems contained with it. Then when they wanted to work on the gems, they could do so with special gloves but couldn’t remove them from the box.

With homomorphic encryption allows ciphered values to be moved to wherever they are required, and then processed, without giving away the original data. Data could thus traverse across the Internet and move to places that it is required, and then used to calculate results.

For your tax return we might see:

Sales (Web)    &*X43=%
Sales (Print) *65tfd1=
              ----------
Total Sales   64,532 (=B1+B2)

In the sales values are ciphered, but we can still process the addition of the two values. We could also apply subtraction, multiplication and division.

We can achieve partial homomorphic encryption with the RSA method:

where we have V1 and V2 as values, an e is the encryption key. So when we decrypt, we will get the value of V1 multiplied by V2. For we pick a public key and a private one. Let’s take versions:

public n: 130784737441990876177357958243693644830726563721360660466
5770676951886355197246857671425655271383319262162735337210458386204
0163830698132957651336978954339749368441676984294775404141089096283
2351079743260650676667850963174834563099364787739637456417087216464
138309745263545890374086809359145644559146264924083
private lambda: 653923687209954380886789791218468224153632818606803
3023328853384759431775986234288357128276356916596310813676686052291
9310200819153490664788256684894771687304547314630213923451602062915
4472442118777485906270040640743230185779181324696482484077330728806
14461484567777528120031610918117114758246385659532477104
Elapsed time (keygen): 364 ms

Now go and try:

http://asecuritysite.com/encryption/pal

In next few years, expect to see a massive increase secure processing and in the passing of encrypted data. If you want to see how we can use a public and private key with homomorphic encryption, try here:

https://asecuritysite.com/encryption/hom_public