In many real-world scenarios, there are cases where a client wishes to check if a data element they hold is included in a set segmented across a large number of data holders. To protect user privacy, the client's query and the data holders' sets should remain encrypted throughout the whole process. Prior work on Private Set Intersection (PSI), Multi-Party PSI (MPSI), Private Membership Test (PMT), and Oblivious RAM (ORAM) falls short in this scenario in many ways. They either require data holders to possess the sets in plaintext, incur prohibitively high latency for aggregating results from a large number of data holders, leak the information about the party holding the intersection element, or induce a high false positive. This paper introduces the primitive of a Private Segmented Membership Test (PSMT). We give a basic construction of a protocol to solve PSMT using a threshold variant of approximate-arithmetic homomorphic encryption and show how to overcome existing challenges to construct a PSMT protocol without leaking information about the party holding the intersection element or false positives for a large number of data holders ensuring IND-CPA^D security. Our novel approach is superior to existing state-of-the-art approaches in scalability with regard to the number of supported data holders. This is enabled by a novel summation-based homomorphic membership check rather than a product-based one, as well as various novel ideas addressing technical challenges. Our PSMT protocol supports many more parties (up to 4096 in experiments) compared to prior related work that supports only around 100 parties efficiently. Our experimental evaluation shows that our method's aggregation of results from data holders can run in 92.5s for 1024 data holders and a set size of 2^25, and our method's overhead increases very slowly with the increasing number of senders. We also compare our PSMT protocol to other state-of-the-art PSI and MPSI protocols and discuss our improvements in usability with a better privacy model and a larger number of parties.

Fully Homomorphic Encryption (FHE) allows outsourced computation on clients’ encrypted data while preserving data privacy. FHE’s high computational intensity incurs high overhead from data transfer with hardware such as CPU, GPU, and FPGA, due to the inherent separation between computing and data. To overcome this limitation, Compute-Enabled RAM (CE-RAM) has been explored; however, prior work using CE-RAM to accelerate FHE only explores a simple implementation of a finite-field FHE scheme and did not explore algorithmic optimizations.In this paper, we investigate CE-RAM acceleration FHE more deeply, implementing both the finite-field B/FV and torus-based TFHE cryptosystems in CE-RAM with common FHE optimizations. This is the first work to explore using CE-RAM to accelerate TFHE. For B/FV, we explore parameter-specific algorithmic optimizations specifically designed for CE-RAM friendliness. We evaluate our implementation as compared to prior work in CE-RAM FHE acceleration and other hardware acceleration strategies. We demonstrate speedups of up to 784x for B/FV homomorphic multiplication and 38x for TFHE bootstrapping as compared to CPU implementations. We also discuss the overhead of CE-RAM for FHE on energy and area consumption, showing comparable or improved performance as compared to other work or hypothetical near-memory accelerators.

Histograms have a large variety of useful applications in data analysis, e.g., tracking the spread of diseases and analyzing public health issues. However, most data analysis techniques used in practice operate over plaintext data, putting the privacy of users’ data at risk. We consider the problem of allowing an untrusted aggregator to privately compute a histogram over multiple users’ private inputs (e.g., number of contacts at a place) without learning anything other than the final histogram. This is a challenging problem to solve when the aggregators and the users may be malicious and collude with each other to infer others’ private inputs, as existing black box techniques incur high communication and computational overhead that limit scalability. We address these concerns by building a novel, efficient, and scalable protocol that intelligently combines a Trusted Execution Environment (TEE) and the Durstenfeld-Knuth uniformly random shuffling algorithm to update a mapping between buckets and keys by using a deterministic cryptographically secure pseudorandom number generator. In addition to being provably secure, experimental evaluations of our technique indicate that it generally outperforms existing work by several orders of magnitude, and can achieve performance that is within one order of magnitude of protocols operating over plaintexts that do not offer any security.

Cloud computing is often utilized for file storage. Clients of cloud storage services want to ensure the privacy of their data, and both clients and servers want to use as little storage as possible. Cross-user deduplication is one method to reduce the amount of storage a server uses. Deduplication and privacy are naturally conflicting goals, especially for nearly-identical ("fuzzy") deduplication, as some information about the data must be used to perform deduplication. Prior solutions thus utilize multiple servers, or only function for exact deduplication. In this paper, we present a single-server protocol for cross-user nearly-identical deduplication based on secure LSH (SLSH). We formally define our ideal security, and rigorously prove our protocol secure against fully malicious, colluding adversaries with a proof by simulation. We show experimentally that the individual parts of the protocol are computationally feasible, and further discuss practical issues of security and efficiency.

Homomorphic encryption (HE) allows direct computations on encrypted data. Despite numerous research efforts, the practicality of HE schemes remains to be demonstrated. In this regard, the enormous size of ciphertexts involved in HE computations degrades computational efficiency. Near-memory processing (NMP) and computing-in-memory (CiM)—paradigms where computation is done within the memory boundaries—represent architectural solutions for reducing latency and energy associated with data transfers in data-intensive applications, such as HE. This article introduces CiM-HE, a CiM architecture that can support operations for the Brakerski/Fan–Vercauteren (B/FV) scheme, a somewhat HE scheme for general computation. CiM-HE hardware consists of customized peripherals, such as sense amplifiers, adders, bit shifters, and sequencing circuits. The peripherals are based on CMOS technology and could support computations with memory cells of different technologies. Circuit-level simulations are used to evaluate our CiM-HE framework assuming a 6T-SRAM memory. We compare our CiM-HE implementation against: 1) two optimized CPU HE implementations and 2) a field-programmable gate array (FPGA)-based HE accelerator implementation. Compared with a CPU solution, CiM-HE obtains speedups between$4.6\times $and$9.1\times $and energy savings between$266.4\times $and$532.8\times $for homomorphic multiplications (the most expensive HE operation). Also, a set of four end-to-end tasks, i.e., mean, variance, linear regression, and inference, are up to$1.1\times $,$7.7\times $,$7.1\times $, and$7.5\times $faster (and$301.1\times $,$404.6\times $,$532.3\times $, and$532.8\times $more energy efficient). Compared with CPU-based HE in previous work, CiM-HE obtains$14.3\times $speedup and$> 2600\times $energy savings. Finally, our design offers$2.2\times $speedup with$88.1\times $energy savings compared with a state-of-the-art FPGA-based accelerator.