We will use Pailler homomorphic encryption to perform an add and subtract using encrypted values. These homomorphic values will be protected with an RSA public key, and decrypted by a private key. In this case we will generate some time samples, and then determine if the time difference between samples is less than 10 seconds using homomorphic encryption. For this we will use a subtract method. The values for the differences will contain a number of contacts. We will use the homomorphic add to total these up. [With Montgomery reduction]
Homomorphic encryption (add and subtract) and RSA protection |
Outline
We will use Pailler homomorphic encryption to perform an add and subtract using encrypted values. These homomorphic values will be protected with an RSA public key, and decrypted by a private key. In this case we will generate some time samples, and then determine if the time difference between samples is less than 10 seconds using homomorphic encryption. For this we will use a subtract method. The values for the differences will contain a number of contacts. We will use the homomorphic add to total these up.
Coding
The coding is here:
import libnum from params import genparams import numpy as np import random from rsa import rsa_encrypt,rsa_decrypt,show_rsa_key # Demo times select 10 samples for time differences with up to 100 seconds in-between. Search with homomorphic encryption for a time difference of less than 20 seconds starttime=1614205069 endtime=starttime+100 timediff=20 # 10 second difference num=10 # number of samples def encrypt(k,r): k1=pow(g,k,n*n) k2=pow(r,n,n*n) return (k1*k2)%(n*n) def decrypt(cipher): l = (pow(cipher, gLambda, n*n)-1) // n mess= (l * gMu) % n return mess def add(cipher,cipher2): return (cipher* cipher2) % (n*n) def sub(cipher,cipher2): v1=(cipher* (libnum.invmod(cipher2,n*n)) % (n*n)) v2=(cipher2* (libnum.invmod(cipher,n*n)) % (n*n)) return v1,v2 def L(x,n): return ((x-1)//n) ######## Encrypting gLambda, n, g, gMu, primesize = genparams() r=random.randint(0,2e72) a = np.random.randint(starttime,high=endtime, size=num) b = np.random.randint(starttime,high=endtime, size=num) contacts = np.random.randint(0,high=10, size=num) enc_a = [] enc_b = [] enc_contacts = [] for i in range(0,len(a)): enc_a.append( rsa_encrypt(encrypt(int(a[i]),r))) enc_b.append( rsa_encrypt(encrypt(int(b[i]),r))) enc_contacts.append( encrypt(int(contacts[i]),r)) show_rsa_key() print (f"=== Homomorphic key ===\nPublic key: g={g}, n={n}\nPrivate key: lambda={gLambda}, Mu={gMu}\n") print (f"Samples: ={num}\n") print (f"Time difference: {timediff} seconds\n") print (f"Contacts: {contacts}\n") contacts_total=encrypt(0,r) count=0 for i in range(0,len(a)): cipher2_1,cipher2_2 = sub(rsa_decrypt(enc_a[i]),rsa_decrypt(enc_b[i])) mess1= decrypt(cipher2_1) mess2= decrypt(cipher2_2) res=mess1 if (mess1>n/8): res=mess2 if (res<timediff): print(f"{(i)} - Time1={a[i]},Time2={b[i]}. Diff: {res}") print(f" Enc={enc_a[i]},Enc={enc_b[i]}") contacts_total=add(contacts_total,enc_contacts[i]) contacts_final_total=decrypt(contacts_total) print(f"\nContacts (enc)={contacts_total}") print(f"\nContacts={contacts_final_total}")
Here are the Pallier encryption methods (params.py):
from Crypto.Util.number import getPrime from Crypto.Random import get_random_bytes from random import randint import libnum primebits=40 def genparams(): p = getPrime(primebits, randfunc=get_random_bytes) q = getPrime(primebits, randfunc=get_random_bytes) n = p*q g=n while (gcd(g,n*n)!=1): g = randint(20,150) gLambda = lcm(p-1,q-1) l = (pow(g, gLambda, n*n)-1)//n gMu = libnum.invmod(l, n) return gLambda, n, g, gMu,primebits def L(x,n): return ((x-1)//n) def gcd(a,b): """Compute the greatest common divisor of a and b""" while b > 0: a, b = b, a % b return a def lcm(a, b): """Compute the lowest common multiple of a and b""" return a * b // gcd(a, b)
And the RSA code (rsa.py):
# RSA bit from Crypto.Util.number import bytes_to_long, long_to_bytes from Crypto.Random import get_random_bytes import Crypto import libnum bits=128 p = Crypto.Util.number.getPrime(bits, randfunc=get_random_bytes) q = Crypto.Util.number.getPrime(bits, randfunc=get_random_bytes) n = p*q PHI=(p-1)*(q-1) e=65537 d=libnum.invmod(e,PHI) def rsa_encrypt(val): return (pow(val,e,n)) def rsa_decrypt(val): return (pow(val,d,n)) def show_rsa_key(): print (f"=== RSA key ===\nPublic key: {e},{n}\nPrivate key: {d},{n}\n") ####
A sample run:
=== RSA key === Public key: 65537,58306003443228937641233965294684420342803068957979364316409386737743228867901 Private key: 5523932669774455251452182591737424140645186348597521243104012350489333104957,58306003443228937641233965294684420342803068957979364316409386737743228867901 === Homomorphic key === Public key: g=114, n=516857476397544579849913 Private key: lambda=86142912732678328888998, Mu=260985462438832858133209 Samples: =10 Time difference: 20 seconds Contacts: [8 7 7 2 2 0 5 3 0 1] 2 - Time1=1614205112,Time2=1614205120. Diff: 8 Enc=52121574421833923191505218335826566819868124187061766945217953411342384535886,Enc=38533025693508220846411515656319894761862023679496294474520149264057139500972 4 - Time1=1614205100,Time2=1614205109. Diff: 9 Enc=11411919788070887014752227721559872563705213648715721419182673308468851118640,Enc=42450383205108616685383724355998159233226265918664311260912959336636914512091 Contacts (enc)=130540798042877416424652991829463580786031964400 Contacts=9