John Would Be So Proud To Help Build A New World Based on Logs
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^3 = 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. If you want to see a fun trick
homomorphic encryption, we need a system such as Paillier. 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
next few years, expect to see a massive increase secure processing and in the passing of encrypted data.