Multi-party private set union (mPSU) allows multiple parties to compute the union of their private input sets without revealing any additional information. Existing efficient mPSU protocols can be categorized into symmetric key encryption (SKE)-based and public key encryption (PKE)-based approaches. However, neither type of mPSU protocol scales efficiently to a large number of parties, as they fail to fully utilize available computational resources, leaving participants idle during various stages of the protocol execution.

DNA edit distance (ED) measures the minimum number of single nucleotide insertions, substitutions, or deletions required to convert a DNA sequence into another. ED has broad applications in healthcare such as sequence alignment, genome assembly, functional annotation, and drug discovery. Privacy-preserving computation is essential in this context to protect sensitive genomic data. Nonetheless, the existing secure DNA edit distance solutions lack efficiency when handling large data sequences or resort to approximations and fail to accurately compute the metric. In this work, we introduce ScureED, a protocol that tackles these limitations, resulting in a significant performance enhancement of approximately 2-24 times compared to existing methods. Our protocol computes a secure ED between two genomes, each comprising 1,000 letters, in just a few seconds. The underlying technique of our protocol is a novel approach that transforms the established approximate matching technique (i.e., the Ukkonen algorithm) into exact matching, exploiting the inherent similarity in human DNA to achieve cost-effectiveness. Furthermore, we introduce various optimizations tailored for secure computation in scenarios with a limited input domain, such as DNA sequences composed solely of the four nucleotide letters.

This paper studies a multi-party private set union (mPSU), a fundamental cryptographic problem that allows multiple parties to compute the union of their respective datasets without revealing any additional information. We propose an efficient mPSU protocol which is secure in the presence of any number of colluding semi-honest participants. Our protocol avoids computationally expensive homomorphic operations or generic multi-party computation, thus providing an efficient solution for mPSU. The crux of our protocol lies in the utilization of new cryptographic tool, namely, Membership Oblivious Transfer (mOT). We believe that the mOT may be of independent interest. We implement our mPSU protocol and evaluate its performance. Our protocol shows an improvement of up to $80.84 times$ in terms of running time and $405.73 times$ bandwidth cost compared to the existing state-of-the-art protocols.

We describe a new paradigm for multi-party private set intersection cardinality (PSI-CA) that allows $n$ parties to compute the intersection size of their datasets without revealing any additional information. We explore a variety of instantiations of this paradigm. By operating under the assumption that a particular subset of parties refrains from collusion, our protocols avoid computationally expensive public-key operations and are secure in the presence of a semi-honest adversary. We demonstrate the practicality of our PSI-CA with an implementation. For $n=16$ parties with data-sets of $2^{20}$ items each, our server-aided variant takes 71 seconds. Interestingly, in the server-less setting, the same task takes only 7 seconds. To the best of our knowledge, this is the first `special purpose' implementation of a multi-party PSI-CA from symmetric-key techniques (i.e. an implementation that does not rely on a generic underlying MPC).We study two interesting applications -- heatmap computation and associated rule learning (ARL) -- that can be computed securely using a dot-product as a building block. We analyse the performance of securely computing heatmap and ARL using our protocol and compare that to the state-of-the-art.

Abstract Contact tracing is an essential tool for controlling the spread of disease through human populations. However, existing contact tracing applications are either vulnerable to privacy and security attacks or heavy bandwidth/computational requirements on the client's devices. In this work, we introduce SecureCT , a Secure Contact Tracing platform with strong privacy protection and lightweight cost. SecureCT prevents linkage attacks, eliminates replay and relay attacks, and allows the phone's holder to delegate their contact tracing computation to untrusted servers while maintaining the user's privacy. The technical core of our scheme is an efficient Private Set Intersection Cardinality protocol which only relies on symmetric‐key primitives. We evaluate its performance to show the feasibility of our proposed system in practice.