Paper 2016/781

Privately Matching $k$-mers

Justin Bed{ő}, Thomas Conway, Kim Ramchen, and Vanessa Teague


We construct the first noninteractive protocols for several tasks related to private set intersection. We provide efficient protocols for three related problems, each motivated by a particular kind of genomic testing. Set intersection with labelling hides the intersecting set itself and returns only the labels of the common elements, thus allowing a genomics company to return diagnoses without exposing the IP of its database. Fuzzy matching with labelling extends this to allow matching at a particular Hamming distance, which solves the same problem but incorporates the possibility of genetic variation. Closest matching returns the item in the server's database closest to the client's query - this can be used for taxonomic classification. Our protocols are optimised for the matching of $k$-mers (sets of $k$-length strings) rather than individual nucleotides, which is particularly useful for representing the short reads produced by next generation sequencing technologies.

Available format(s)
Publication info
Preprint. MINOR revision.
homomorphic encryptionprivacy preserving protocols
Contact author(s)
kim ramchen @ unimelb edu au
2017-02-18: last of 2 revisions
2016-08-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Justin Bed{ő} and Thomas Conway and Kim Ramchen and Vanessa Teague},
      title = {Privately Matching $k$-mers},
      howpublished = {Cryptology ePrint Archive, Paper 2016/781},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.