Jonathan Takeshita

Dayane Reis, Jonathan Takeshita, Taeho Jung et al.

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 paper introduces CiM-HE, a Computing-in-memory (CiM) architecture that can support operations for the B/FV scheme, a somewhat homomorphic encryption 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 (i) two optimized CPU HE implementations, and (ii) an FPGA-based HE accelerator implementation. When compared to a CPU solution, CiM-HE obtains speedups between 4.6x and 9.1x, and energy savings between 266.4x and 532.8x 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.1x, 7.7x, 7.1x, and 7.5x faster (and 301.1x, 404.6x, 532.3x, and 532.8x more energy efficient). Compared to CPU-based HE in a previous work, CiM-HE obtain 14.3x speed-up and >2600x energy savings. Finally, our design offers 2.2x speed-up with 88.1x energy savings compared to a state-of-the-art FPGA-based accelerator.

Jonathan Takeshita, Ryan Karl, Taeho Jung

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 locality-sensitive hashing (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.