- ESORICSEfficient Circuits for Permuting and Mapping Packed Values Across Leveled Homomorphic Ciphertexts2022
Cloud services are an essential part of our digital infrastructure as organizations outsource large amounts of data storage and computations. While organizations typically keep sensitive data in encrypted form at rest, they decrypt it when performing computations, leaving the cloud provider free to observe the data. Unfortunately, access to raw data creates privacy risks. To alleviate these risks, researchers have developed secure outsourced data processing techniques. Such techniques enable cloud services that keep sensitive data encrypted, even during computations. For this purpose, fully homomorphic encryption is particularly promising, but operations on ciphertexts are computationally demanding. Therefore, modern fully homomorphic cryptosystems use packing techniques to store and process multiple values within a single ciphertext. However, a problem arises when packed data in one ciphertext does not align with another. For this reason, we propose a method to construct circuits that perform arbitrary permutations and mappings of such packed values. Unlike existing work, our method supports moving values across multiple ciphertexts, considering that the values in real-world scenarios cannot all be packed within a single ciphertext. We compare our open-source implementation against the state-of-the-art method implemented in HElib, which we adjusted to work with multiple ciphertexts. When data is spread among five or more ciphertexts, our method outperforms the existing method by more than an order of magnitude. Even when we only consider a permutation within a single ciphertext, our method still outperforms the state-of-the-art works implemented by HElib for circuits of similar depth.
- IACR eprintFast Multi-party Private Set Operations in the Star Topology from Secure ANDs and ORsIACR Cryptol. ePrint Arch. 2022
Today, our society produces massive amounts of data, part of which are strictly private. So, a long line of research has worked to design protocols that perform functions on such private data without revealing them. One function that has attracted significant interest is a multi-party private set operation, where each party’s input is a set. The parties commonly intend to compute these sets’ collective intersection (MPSI) or union (MPSU), which finds uses in various applications, including private scheduling and threat intelligence. Most current protocols use integer-based homomorphic encryption, with large elements and expensive operations, or oblivious transfers, which require communicationally-expensive pairwise interactions between all parties. Thus, existing solutions introduce significant overhead that hinders practical use. This paper considers a certain class of previously-proposed MPSI and MPSU protocols. We propose to express them in terms of new private AND or OR operations among all parties and use elliptic curves to realize these operations efficiently. We achieve a significant performance gain: Firstly, our protocols take only three rounds of communication. Secondly, our constant-time open-source implementation is two orders of magnitude faster than the state-of-the-art MPSI for small universes and outperforms the state-of-the-art MPSI for large universes for three parties or more.
- IEEE T-IFSPractical Multi-Party Private Set Intersection ProtocolsAslı́ Bay, Zekeriya Erkin, Jaap-Henk Hoepman, Simona Samardjiska, and Jelle VosIEEE Trans. Inf. Forensics Secur. 2022
- SecryptMulti-Party Private Set Intersection Protocols for Practical ApplicationsAslı́ Bay, Zeki Erkin, Mina Alishahi, and Jelle Vos2021
Multi-Party Private Set Intersection (MPSI) is an attractive topic in research since a practical MPSI protocol can be deployed in several real-world scenarios, including but not limited to finding the common list of customers among several companies or privacy-preserving analyses of data from different stakeholders. Several solutions have been proposed in the literature however, the existing solutions still suffer from performance related challenges such as long run-time and high bandwidth demand, particularly when the number of involved parties grows. In this paper, we propose a new approach based on threshold additively homomorphic encryption scheme, e.g., Paillier, which enables us to process the bit-set representation of sets under encryption. By doing so, it is feasible to securely compute the intersection of several data sets in an efficient manner. To prove our claims on performance, we compare the communication complexity of our approach with the existing solutions and show p erformance test results. We also show how the proposed protocol can be extended to securely compute other set operations on multi-party data sets.
- IEEE WIFSCompare Before You Buy: Privacy-Preserving Selection of Threat Intelligence ProvidersJelle Vos, Zekeriya Erkin, and Christian Doerr2021
In their pursuit to maximize their return on in- vestment, cybercriminals will likely reuse as much as possible between their campaigns. Not only will the same phishing mail be sent to tens of thousands of targets, but reuse of the tools and infrastructure across attempts will lower their costs of doing business. This reuse, however, creates an effective angle for mitigation, as defenders can recognize domain names, attachments, tools, or systems used in a previous compromisation attempt, significantly increasing the cost to the adversary as it would become necessary to recreate the attack infrastructure each time. However, generating such cyber threat intelligence (CTI) is resource-intensive, so organizations often turn to CTI providers that commercially sell feeds with such indicators. As providers have different sources and methods to obtain their data, the coverage and relevance of feeds will vary for each of them. To cover the multitude of threats one organization faces, they are best served by obtaining feeds from multiple providers. However, these feeds may overlap, causing an organization to pay for indicators they already obtained through another provider. This paper presents a privacy-preserving protocol that allows an organization to query the databases of multiple data providers to obtain an estimate of their total coverage without revealing the data they store. In this way, a customer can make a more informed decision on their choice of CTI providers. We implement this protocol in Rust to validate its performance experimentally: When performed between three CTI providers who collectively have 20,000 unique indicators, our protocol takes less than 6 seconds to execute. The code for our experiments is freely available.