Cryptology ePrint Archive: Report 2016/781

Privately Matching $k$-mers

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

Abstract: 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.

Category / Keywords: homomorphic encryption, privacy preserving protocols

Date: received 13 Aug 2016, last revised 17 Feb 2017

Contact author: kim ramchen at unimelb edu au

Available format(s): PDF | BibTeX Citation

Version: 20170218:031710 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]