Paper 2023/628

SEC: Symmetric Encrypted Computation via Fast Look-ups

Abstract

Garbled Circuits (GCs) and Fully Homomorphic Encryption (FHE) are state-of-the-art general-purpose primitives allowing a client to securely outsource the storage and processing of sensitive private data to an untrusted third party cloud server. GCs provide data privacy and function privacy while being efficient, but suffer from non-reusability of its translation tables. On the other extreme, FHE enables arbitrary encrypted computation ensuring data-privacy but suffers from huge computation overhead and limited scalability. Here, we explore the following question- Can encrypted computation guaranteeing data privacy be enabled through use of encrypted lookup tables (like GC) that are reusable for practically large circuits? Such a solution will retain the efficiency of GCs (because of encrypted table lookups); and while it cannot achieve unbounded reusability (like FHE, because of the inclination on computation rather than lookups), an interesting question is whether its reusability bound can be made sufficient for practically large circuits. In this work, we propose Symmetric Encrypted Computation (SEC), the first practically efficient and provably secure lookup-based construction that supports reusable evaluations of arbitrary Boolean circuits over symmetrically encrypted data, while ensuring data-privacy guarantees. With a single setup of encrypted look-up tables, SEC supports O(k) re-evaluations of the same circuit of size n (for client controlled k (≥ n)). Such reusability improves upon GC and is asymptotically large enough to scale to practical deployments of realistic circuits; also note that SEC completely bypasses bootstrapping, thereby being more efficient than FHE. This is achieved by relying on purely symmetric-key crypto-primitives by extending and generalizing the functional capabilities of Searchable Symmetric Encryption (SSE), while inheriting its desirable performance benefits. Reusability through SSE without leakage is ensured in SEC by the design choice to treat a generic 2-input Boolean gate as a 3-input encrypted query, with the third input randomizing access patterns across reuse. We provide a concrete construction of SEC and analyze its security with respect to a rigorous leakage profile. We also experimentally validate its practical efficiency. SEC outperforms state-of-the-art FHE schemes (such as Torus FHE) substantially. We further showcase the scalability of SEC for functions with multi-bit inputs via experiments performing encrypted evaluation of the entire AES-128 circuit, as well as the max-pooling layers of AlexNet architecture. For both sets of experiments, SEC outperforms state-of-the-art unaccelerated FHE implementations by 1000× in terms of processing time, while incurring 250× lower storage.