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: ia.cr/2016/781
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]