Secure Federated Boolean Count Queries Using Fully-Homomorphic Cryptography

Biomedical data is often distributed between a network of custodians, causing challenges for researchers wishing to securely compute aggregate statistics on those data without centralizing everything—the prototypical ‘count query’ asks how many patients match some multifaceted set of conditions across a network of hospitals. Difficulty arises from two sources: (1) the need to deduplicate patients who may be present in the records of multiple hospitals and (2) the need to unify partial records for the same patient which may be split across hospitals. Although cryptographic tools for secure computation promise to enable collaborative studies with formal privacy guarantees, existing approaches either are computationally impractical or support only simplified analysis pipelines. To the best of our knowledge, no existing practical secure method addresses both of these difficulties simultaneously. Here, we introduce secure federated Boolean count queries using a novel 2-stage probabilistic sketching and sampling protocol that can be efficiently implemented in off-the-shelf federated homomorphic encryption libraries (Palisade and Lattigo), provably ensuring data security. To this end, we needed several key technological innovations, including re-encoding the LogLog union-cardinality sketch and designing an appropriate sampling for intersection cardinalities. Our benchmarking shows that we can answer federated Boolean count queries in less than 2 CPU-minutes with absolute errors in the range of 6% of the total number of touched records, while revealing only the final answer and the total number of touched records. With modern core-parallelism, we can thus answer queries on the order of seconds. Our study demonstrates that by computing on compressed and encrypted data, it is possible to securely answer federated Boolean count queries in real-time.