Paper 2023/628

SEC: Symmetric Encrypted Computation via Fast Look-ups

Abstract

Encrypted computation allows a client to securely outsource the storage and processing of sensitive private data to an untrusted third party cloud server. Fully Homomorphic Encryption (FHE) and Garbled Circuit (GC) are state-of-the-art general-purpose primitives that support encrypted computation. FHE enables arbitrary encrypted computation ensuring data-privacy but suffers from huge computation overhead and poor scalability. GC additionally provides function privacy, but is often not suitable for practical deployment because its translation tables need to be refreshed for every evaluation. We extend Searchable Symmetric Encryption (SSE), beyond encrypted searches, to perform arbitrary Boolean circuit evaluations over symmetrically encrypted data via look-ups, while ensuring data privacy. In this work, we propose Symmetric Encrypted Computation (SEC), the first practically efficient and provably secure lookup-based construction that supports evaluation 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(n!)$ re-evaluations of a circuit of size $n$. This is an improvement on GC that supports a single evaluation with a single setup. While SEC supports bounded re-evaluations with a single setup (unlike FHE), it is asymptotically large enough to scale to practical deployments of realistic circuits. Moreover, SEC completely bypasses bootstrapping thereby significantly improving on performance efficiency. SEC achieves this by relying on purely symmetric-key crypto primitives by extending and generalizing the functional capabilities of SSE, while inheriting its desirable performance benefits. The leakages incurred by underlying SSE scheme are rendered inconsequential with respect to SEC's security guarantees due to its meticulous design choices. 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, with around $1000\times$ speed-up in basic Boolean gate evaluations. 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 three max-pooling layers of AlexNet architecture. For both sets of experiments, SEC outperforms state-of-the-art and accelerated FHE implementations by $1000 \times$ in terms of processing time, while incurring $250 \times$ lower storage.