Photo by Markus Winkler on Unsplash

Epione: Lightweight Contact Tracing with Strong Privacy

Prof Bill Buchanan OBE
Apr 12 · 4 min read

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

A sample run [here]:

Here is the code:

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

[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.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store