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) allows computing arbitrary functions over encrypted data, but incurs huge overheads and does not practically scale to large databases. Whereas, slightly weaker yet efficient constructions- Searchable Symmetric Encryption (SSE) support lookup-based evaluations of a restricted class of Boolean circuits over symmetrically encrypted data. In this paper, we investigate the use of SSE to efficiently perform arbitrary Boolean circuit evaluations over symmetrically encrypted data via look-ups. To this end, in this work, we propose Symmetric Encrypted Computation (SEC): the first practically efficient and provably secure lookup-based construction, analogous to traditional FHE, that supports evaluation of arbitrary Boolean circuits over symmetrically encrypted data. SEC relies on purely symmetric-key cryptoprimitives and achieves flexible performance versus leakage trade-offs. SEC extends and generalizes the functional capabilities of SSE, while inheriting its data privacy guarantees and desirable performance benefits. We provide a concrete construction of SEC and analyze its security with respect to a rigorously defined and thoroughly analyzed leakage profile. We also present a prototype implementation of SEC and experimentally validate its practical efficiency. Our experiments show that SEC outperforms state-of-the-art FHE schemes (such as Torus FHE) substantially, with around 1000× 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× in terms of processing time, while incurring 250× lower storage.