Privacy-Preserving Similar Patient Query over Genomic Data

This chapter introduces an efficient and privacy-preserving similar patient query (SPQ) scheme over genomic data. Given a genome collected from a new patient, the scheme can help physicians quickly find target patients with similar genomes on cloud data while keeping all genomes secret. Specifically, we first design a novel data structure named GBK-tree based on BK-tree, whose similarity metric is approximate edit distance and can be applied to improve the performance of the proposed scheme. Then, combined with random sorting, hash-based message authentication code, and symmetric key encryption, we achieve the search over encrypted GBK-tree. With the proposed scheme, a medical institution can outsource its genomic database to an honest-but-curious cloud server, and physicians can enjoy SPQ services without revealing their queries. Furthermore, detailed security analysis shows the scheme can guarantee security under different threats, and extensive performance evaluations demonstrate the scheme is highly accurate and efficient.