BLOOM: BLoom filter based oblivious outsourced matchings

Area of Science:

• Genomics
• Cryptography
• Bioinformatics

Background:

• Whole genome sequencing generates vast amounts of data, enabling biomedical advances but posing significant privacy risks.
• Cloud-based storage and processing of genomic data exacerbate these privacy concerns.
• Research is exploring cryptographic methods for privacy-preserving genomic computations.

Purpose of the Study:

• To propose and evaluate FHE-BLOOM and PHE-BLOOM, novel approaches for genetic disease testing using homomorphically encrypted Bloom filters.
• To enable secure outsourcing of genomic data storage and computation to untrusted cloud environments.
• To offer a trade-off between security and performance for privacy-preserving genomic analysis.

Main Methods:

• Development of FHE-BLOOM (fully secure in the semi-honest model) and PHE-BLOOM (partially homomorphic, improved performance).
• Implementation and evaluation on large datasets of up to 50 patient genomes, each with up to 1,000,000 variations (SNPs).
• Analysis of computational overheads and performance scaling with patient numbers and variations.

Main Results:

• Both FHE-BLOOM and PHE-BLOOM demonstrate linear scaling of overheads with the number of patients and variations.
• PHE-BLOOM achieves performance improvements of at least three orders of magnitude compared to FHE-BLOOM.
• Efficient processing of large datasets: 50 patients with 100,000 variations tested in 308.31s (FHE-BLOOM) vs. 0.07s (PHE-BLOOM).

Conclusions:

• FHE-BLOOM and PHE-BLOOM efficiently handle practical problem sizes and are parallelizable for cloud environments.
• FHE-BLOOM provides comprehensive cloud outsourcing with full security guarantees.
• PHE-BLOOM offers significant performance gains by slightly relaxing security, making it highly efficient for large-scale genetic analysis.