The Epione Protocol [1] can be used to alert users directly when contacts have been diagnoised as being COVID-19 positive. It uses a secure two-party private set intersection cardinality (PSI-CA), and where Bob and Alice have a set of items and can reveal the intersection between these. The intersection reveals the total number of intersection items, and not the actual intersection values. Thus Bob may discover identifies of "5, 6, 4, 8, 9, 11" and Alice may have identities of "6, 1, 11, 3, 5, 2". The intersection of this will give the result of 3, as there is a match for 5, 6, and 11. Bob cannot find which of the values of matches, and only that there are three matches. Initially Bob has values of \(a_i\) and matches these the curve with \([a G]\). He then creates a random value of \(r\) and then multiplies these by \(r\) to get \(raG\). He sends these values of Alice, and who will shuffle them. Alice then create a secret value of \(s\) and multiplies each of these points to get \(sraG\). She sends these back, and Bob then takes the inverse of his value \(r^{-1} \pmod{n}\), and where \(n\) is the order of the curve. He then multiplies each of the values returned with this value, and will get \(saG\). Alice then takes her values (\(b_i\)) and then multiplies these by \(s\) to get \(sbG\). She returns these to Bob, and who now can match \(sAG\) and \(sbG\). Bob will only be able to determine the total number of matches, and not the actual match. The method is defined by NIST in [2].
Infection Tracking: The Epione Protocol |
Theory
The Epione Protocol [1] can be used to alert users directly when contacts have been diagnoised as being COVID-19 positive. It uses a secure two-party private set intersection cardinality (PSI-CA), and where Bob and Alice have a set of items and can reveal the intersection between these. The intersection reveals the total number of intersection items, and not the actual intersection values. Thus Bob may discover identifies of "5, 6, 4, 8, 9, 11" and Alice may have identities of "6, 1, 11, 3, 5, 2". The intersection of this will give the result of \(3\), as there is a match for 5, 6, and 11. Bob cannot find which of the values of matches, and only that there are three matches. Initially Bob has values of \(a_i\) and matches these the curve with:
\([a_i G]\)
He then creates a random value of \(r\) and then multiplies these by \(r\) to get:
\([ra_iG]\)
He sends these values of Alice, and who will shuffle them. Alice then create a secret value of \(s\) and multiplies each of these points to get:
\(s r a_i G\)
She sends these back, and Bob then takes the inverse of his value:
\(r^{-1} \pmod{n}\)
and where \(n\) is the order of the curve. He then multiplies each of the values returned with this value, and will get:
\([sa_iG]\)
Alice then takes her values (\(b_i\)) and then multiplies these by \(s\) to get:
\([sb_iG]\)
She returns these to Bob, and who now can match \([sa_iG]\) and \([sb_iG]\). Bob will only be able to determine the total number of matches, and not the actual match.
Code
The code used is:
from ecpy.curves import Curve import secrets import sys,random curve = Curve.get_curve('secp256k1') G = curve.generator order = curve.order a=[54,44,33,60] b=[60,54,19,4] t=0 if (len(sys.argv)>1): a=eval(sys.argv[1]) if (len(sys.argv)>2): b=eval(sys.argv[2]) if (len(sys.argv)>3): t=eval(sys.argv[3]) if (t==1): curve = Curve.get_curve('NIST-P192') elif (t==2): curve = Curve.get_curve('NIST-P224') elif (t==3): curve = Curve.get_curve('NIST-P256') elif (t==4): curve = Curve.get_curve('Ed25519') elif (t==5): curve = Curve.get_curve('secp192k1') elif (t==6): curve = Curve.get_curve('secp160k1') elif (t==7): curve = Curve.get_curve('secp224k1') elif (t==8): curve = Curve.get_curve('Brainpool-p256r1') elif (t==9): curve = Curve.get_curve('Brainpool-p224r1') elif (t==10): curve = Curve.get_curve('Brainpool-p192r1') elif (t==11): curve = Curve.get_curve('Brainpool-p160r1') elif (t==12): curve = Curve.get_curve('secp256r1') if (t!=4): print (f"Name: {curve.name}, y^2=x^3+a*x+b (mod p) Type: {curve.type}, Size: {curve.size}, a={curve.a}, b={curve.b}, G={curve.generator}, field={curve.field}, order={curve.order}") else: print (f"Name: {curve.name}, a*x^2+y^2=1+d*x^2*y^2 (mod p) Type: {curve.type}, Size: {curve.size}, a={curve.a}, d={curve.d}, G={curve.generator}, field={curve.field}, order={curve.order}") Ai =[0]*len(a) Bi=[0]*len(b) sAi =[0]*len(a) sBi=[0]*len(b) raAi =[0]*len(a) sraAi=[0]*len(a) print (f"a: {a}, b: {b}") s=secrets.randbits(32*8) r=secrets.randbits(32*8) for i in range(0,len(a)): raAi[i] = r*(a[i]*G) for i in range(0,len(a)): sraAi[i] = s*raAi[i] inv_r = pow(r,-1,order) random.shuffle(sraAi) print("Encrypted and shuffled a: ") for i in range(0,len(a)): sAi[i] = inv_r * sraAi[i] print (f"({sAi[i].x},{sAi[i].y})") print("Encrypted b: ") for i in range(0,len(b)): sBi[i] = s*(b[i]*G) print (f"({sBi[i].x},{sBi[i].y})") print ("\nMatching ....") count=0 for i in range(0,len(a)): for j in range(0,len(b)): if (sAi[i]==sBi[j]): count=count+1 print (f"({j}. Value: {b[j]}) ",end="") print (f"\nMatching .... {count}")
A sample run:
Name: secp256k1, y^2=x^3+a*x+b (mod p) Type: weierstrass, Size: 256, a=0, b=7, G=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 , 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8), field=115792089237316195423570985008687907853269984665640564039457584007908834671663, order=115792089237316195423570985008687907852837564279074904382605163141518161494337 a: (5, 6, 4, 8, 9), b: (6, 1, 11, 3, 5) r: 86030982499285773026134701779427842540954241883806286541094515354431211129580, s: 35810845382701678817314893630353364914492881860210893664709052909431690207 Matching .... Encrypted and shuffled a: (45821180220146655393197169836583231624462558246575300295423325628364099821838,84638598980453651399903838661136528379509906345146845548710209735410389109309) (32982782663913517851975625622028240708271485421225334217452394356165647406309,88830665148675042647144646111280475756161094535394182547646917241288373905087) (53173862989157954902755282151347704642855174558675549166163298706274002918397,37325209227456285307320895011112009905246861851268274980084824599007109098623) (18746354803801247260878768643417517539487989550881129014729202837588287450850,13358543306506409873867842134260805519344058064224391500719792814773808251034) (114179113713461696726999016458291313988370698171465757172406106495488725687966,69125231927073491438767534469290163350530532496789540336344091137259977467886) Encrypted b: (32982782663913517851975625622028240708271485421225334217452394356165647406309,88830665148675042647144646111280475756161094535394182547646917241288373905087) (85839078472703267195275267629113881260278011428702625188263268351553357181944,47343147588106775176240528643834521240134702819984032786753438147050137127440) (22254607272806765242678167501119476060524901175207973867647691000165173078120,94966464046192838480133919804049642574118342351839515319059695421284741551866) (107657226729357006667383440857846180714090282607137016214094732867190755980358,12593178110216479425019633053836538199005554532800068878969362422782214469005) (53173862989157954902755282151347704642855174558675549166163298706274002918397,37325209227456285307320895011112009905246861851268274980084824599007109098623) (0. Value: 6) (4. Value: 5) Matching .... 2
References
[1] Trieu, N., Shehata, K., Saxena, P., Shokri, R., & Song, D. (2020). Epione: Lightweight contact tracing with strong privacy. arXiv preprint arXiv:2004.13293. [paper]
[2] Peralta, R., & Robinson, A. (2021). Encounter Metrics and Exposure Notification. [paper]