Towards Secure Computation of Similar Patient Query on Genomic Data Under Multiple Keys

Genomics plays an especial role in our daily lives. Genomic data, however, are highly-sensitive and thus normally stored in repositories with strict access control insurance. This severely restricts the associated processing on genomic data, in which multiple institutes holding their own data hope to conduct specific computation on the entire dataset. Accordingly, researchers attempt to propose methods to enable secure computation on genomic data among multiple parties. Nevertheless, most of the existing solutions fall short in efficiency, security or scalability. In this paper, we focus on providing a secure and practical solution to perform similar patient query on distributed Electronic Health Records (EHR) databases with genomic data. To achieve this, we propose a privacy-preserving framework to execute similar patient query on genomic data owned by distributed owners in a server-aided setting. Specifically, we apply multi-key homomorphic encryption to the proposed framework, where each data owner performs queries on its local EHR database, encrypts query results with its unique public key, and sends them to the servers for further secure edit-distance computation on genomic data encrypted under multiple keys. Security and performance analysis show that our system achieves satisfactory efficiency, scalability, and flexibility while protecting the privacy of each data contributor.