How Do You Make A Bet So That The Bookie Can’t Tell How Much You Have Won?
How Do You Make A Bet So That The Bookie Can’t Tell How Much You Have Won?
I have created a demo here of the method used, and is just a simple example that illustrates how we can multiply cipher values with RSA.
Homomorphic encryption
Too much of our data world gives away sensitive information, and we thus need to move to a world where we can process data without revealing its actual information. In this way we can process data within systems and even though someone is looking at the data processing, they cannot determine the actual values being used. This is the dream of homomorphic encryption.
Some of the proposed schemes are defined as partially homomorphic — where they can support a number of mathematical operations on encrypted values — and others as fully homomorphic. In this case, I’ll use a simple RSA method to multiply two ciphered values, and gain the result of a multiplication when we decipher them.
Multiplying cipher values with RSA
So with RSA we cipher with:
Cipher = Mᵉ mod N
and where e is the encryption key, and N is the multiplication of two prime numbers (p and q). The difficulty in this is factorizing N to get two prime numbers. To decrypt, we find the decryption key (d) and then perform:
M = Cipherᵈ mod N
So if we take two values (a and b), then we can cipher them as:
Cipher1 = aᵉ mod N
Cipher2 = bᵉ mod N
If we multiply the ciphers we get:
Cipher3 = Cipher1 𝗑 Cipher2 = aᵉ mod N 𝗑 bᵉ mod N = aᵉ 𝗑 bᵉ (mod N)
This is then:
Cipher3= (ab)ᵉ (mod N)
When we can then decrypt and determine the value of a times b:
ab = (Cipher3)ᵈ (mod N)
Here is a demo: http://asecuritysite.com/encryption/hom_rsa
Alice makes a bet, but doesn’t trust Bob The Bookie
Now let’s make a bet for Alice, and make sure that the bookie (Bob) doesn’t actually know how much she has bet, and how much she has won.
Our stake can be the value of a, and the odds will be b. If we stake £11 and the odds are 4/1, then we would encrypt a, and then the bookie could encrypt the odds. We can add different keys, but to keep it simple, we will just use the same encryption and decryption keys for both values (using commutative encryption).
Here is some simple code:
print "RSA Encryption parameters. Public key: [e,N]."
cipher1=pow(a,e,n)
cipher2=pow(b,e,n)
cipher3=(cipher1 * cipher2) % n
print "a:\t\t",a
print "b:\t\t",b
print "Cipher1:\t",cipher1
print "Cipher2:\t",cipher2
print "Cipher3:\t",cipher3
print "e:\t\t",e
print "N:\t\t",n
val=pow(cipher3,d,n)
print "Result:\t\t",val
Now with a stake of £11 and with odds of 4/1 we get:
a: 11
b: 5
Cipher1: 587594386702964443000198582993090352
Cipher2: 190679432787271388486300698180475703
Cipher3: 313370008825595405710726217490873530
e: 65537
N: 594816299572474213456473242614358287
Result: 55
Coding
The following code implements the basic method (using small prime numbers):
import pyprimes
import sys
import random
import math
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
def rabinMiller(n):
s = n-1
t = 0
while s&1 == 0:
s = s/2
t +=1
k = 0
while k<128:
a = random.randrange(2,n-1)
#a^s is computationally infeasible. we need a more intelligent approach
#v = (a**s)%n
#python's core math module can do modular exponentiation
v = pow(a,s,n) #where values are (num,exp,mod)
if v != 1:
i=0
while v != (n-1):
if i == t-1:
return False
else:
i = i+1
v = (v**2)%n
k+=2
return True
def isPrime(n):
#lowPrimes is all primes (sans 2, which is covered by the bitwise and operator)
#under 1000. taking n modulo each lowPrime allows us to remove a huge chunk
#of composite numbers from our potential pool without resorting to Rabin-Miller
lowPrimes = [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179
,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269
,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367
,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461
,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571
,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661
,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773
,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883
,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]
if (n >= 3):
if (n&1 != 0):
for p in lowPrimes:
if (n == p):
return True
if (n % p == 0):
return False
return rabinMiller(n)
return False
def generateLargePrime(k):
#k is the desired bit length
r=100*(math.log(k,2)+1) #number of attempts max
r_ = r
while r>0:
#randrange is mersenne twister and is completely deterministic
#unusable for serious crypto purposes
n = random.randrange(2**(k-1),2**(k))
r-=1
if isPrime(n) == True:
return n
return "Failure after "+`r_` + " tries."
import random
val=0
bits=60
if (len(sys.argv)>1):
val=int(sys.argv[1])
p= generateLargePrime(bits)
q= generateLargePrime(bits)
n=p*q
e=65537
PHI=(p-1)*(q-1)
d=inverse_of(e,PHI)
a = 11
b = 5
print "RSA Encryption parameters. Public key: [e,N]."
cipher1=pow(a,e,n)
cipher2=pow(b,e,n)
cipher3=(cipher1 * cipher2) % n
print "a:\t\t",a
print "b:\t\t",b
print "Cipher1:\t",cipher1
print "Cipher2:\t",cipher2
print "Cipher3:\t",cipher3
print "e:\t\t",e
print "N:\t\t",n
val=pow(cipher3,d,n)
print "Result:\t\t",val
A sample run:
a: 11
b: 5
Cipher1: 587594386702964443000198582993090352
Cipher2: 190679432787271388486300698180475703
Cipher3: 313370008825595405710726217490873530
e: 65537
N: 594816299572474213456473242614358287
Result: 55
Conclusions
We need to move to a world where we do not pass our core information. Homomorphic encryption and zero knowledge proof are just two methods we can use to protect your data.
This is the world we are building with Blockchain, and it is one where we preserve the rights of privacy on data, but allow processing on it.
If you are interested in full homomorphic encryption, here is an example: