Epione: Lightweight Contract Tracing with Strong Privacy

Epione: Lightweight Contact Tracing with Strong Privacy

My three main tips for researchers:

• To be known to be an expert in something, rather than being general in lots of areas.
• Pick two papers to read each week.
• Implement the methods from the papers and validate them.

For the papers, for me, I select one classic paper of the past — and which has hundreds of citations - and another is a fairly new paper which is showing potential. I thus search Google Scholar on a regular basis and look for papers that have relatively high citations for their recent publication. These papers perhaps show an upward tick on the method being proposed. Normally I look for at least 30 citations within a year, so this paper popped up as one of the papers to read:

It covers the Epione Protocol [1] and which can be used to alert users directly when contacts have been diagnosed as being COVID-19 positive [here]:

The method has also been picked up by NIST as good practice for “Encounter Metrics and Exposure Notification” [here]:

Epione 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:

[r a_i G]

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} (mod n)

and where n is the order of the curve. He then multiplies each of the values returned with this value, and will get:

[s a_i G]

Alice then takes her values (b_i) and then multiplies these by s

to get:

[s b_i G]

She returns these to Bob, and who now can match [s a_i G] and [s b_i G]. Bob will only be able to determine the total number of matches and not the actual match.

The code used is [here]:

from ecpy.curves import Curve
import secrets

import sys,random

if (len(sys.argv)>1):
  msg=str(sys.argv[1])

curve = Curve.get_curve('secp256k1')

G = curve.generator
order = curve.order

a=[54,44,33,60]
b=[60,54,19,4]

if (len(sys.argv)>1):
  a=eval(sys.argv[1])
if (len(sys.argv)>2):
  b=eval(sys.argv[2])

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}")
print (f"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"Match found {j}. Value: {b[j]})")

print(f"Count {count}")

A sample run [here]:

a: [54, 44, 33, 60]
b: [60, 54, 19, 4]
Encrypted and shuffled a: 
(33154728198007877406679896344922399384077674820702618247154111812291249751964,43450745038633382231888843746259569439229961684635884963971631324842358232156)
(20359085876831051142903158215711661403117985676379611235397744907830849112491,77657799878541882508219999670336342856176267416880560228145616367858719079376)
(65165529953105696370895668972166343773767723651841337834003930352388608385661,31783721178853081426050066393878785244863489313873611774776863163515454012885)
(88874489235262388029371849976331961859395095876768290462359966314039690701548,23719643418948340134272405738825359334081709734669377842199162760815738223118)
Encrypted b: 
(88874489235262388029371849976331961859395095876768290462359966314039690701548,23719643418948340134272405738825359334081709734669377842199162760815738223118)
(20359085876831051142903158215711661403117985676379611235397744907830849112491,77657799878541882508219999670336342856176267416880560228145616367858719079376)
(80643845521464880166347153741337140376450345631821894301655488605812569683841,32129529374063613893257591014256204485159719999027720734573067237119189761809)
(109123088169403844376361846554869882759592673858355377792750946809336591396539,10078315691360916011120109977676692476637448846325764021688085367553152943459)

Matching ....
Match found 1. Value: 54)
Match found 0. Value: 60)
Count 2

Here is the code:

Conclusions

Read, implement and learn. Pick a classic paper, and understand it. Pick a new paper and implement it.

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.