Table 1 Complexity analysis of FHE-BLOOM and PHE-BLOOM: Setup overheads are similar in both approaches and grow linearly in the number of patients n and Bloom filter size l which is proportional to the number of SNPs m, i.e., l=−m log(p)/ log(2)2
From: BLOOM: BLoom filter based oblivious outsourced matchings
Approach | DB setup (Client) | Query (Cloud) | Query (Client) | ||
|---|---|---|---|---|---|
| Â | Time | Comm | Time | Time | Comm. |
Fhe-Bloom | \(\mathcal {O}(n \cdot l / s_{F})~\text {Enc}_{F}\) | \(\mathcal {O}(n \cdot l / s_{F})~\mathrm {C}_{F}\) | \(\mathcal {O}(n \cdot l / s_{F})~\text {Mul}_{F} + \mathcal {O}(n \cdot l / s_{F})~\text {Add}_{F}\) | \(\mathcal {O}(l / s_{F}) ~\text {Enc}_{F} +\mathcal {O}(n) ~ \text {Dec}_{F}\) | \(\mathcal {O}(l / s_{F}+n) ~\mathrm {C}_{F}\) |
Phe-Bloom | \(\mathcal {O}(n \cdot l / s_{P})~\text {Enc}_{P}\) | \(\mathcal {O}(n \cdot l / s_{P})~\mathrm {C}_{P}\) | \(\mathcal {O}(n / s_{P}) ~\text {Add}_{P}\) | \(\mathcal {O}(n / s_{P}) ~\text {Dec}_{P}\) | \(\mathcal {O}(n / s_{P}) ~ \mathrm {C}_{P}\) |