Paper 2023/628

SEC: Symmetric Encrypted Computation via Fast Look-ups

Debadrita Talapatra, Indian Institute of Technology Kharagpur
Nimish Mishra, Indian Institute of Technology Kharagpur
Arnab Bag, Indian Institute of Technology Kharagpur
Sikhar Patranabis, IBM Research India
Debdeep Mukhopadhyay, Indian Institute of Technology Kharagpur
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 re-evaluations of a circuit of size . 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 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 in terms of processing time, while incurring lower storage.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Fully Homomorphic EncryptionEncrypted Functional ComputationSearchable Symmetric Encryption
Contact author(s)
debadritat fg2219 @ gmail com
neelam nimish @ gmail com
amiarnabbolchi @ gmail com
sikharpatranabis @ gmail com
debdeep mukhopadhyay @ gmail com
History
2025-02-14: last of 3 revisions
2023-05-02: received
See all versions
Short URL
https://ia.cr/2023/628
License
Creative Commons Attribution-NonCommercial-ShareAlike
CC BY-NC-SA

BibTeX

@misc{cryptoeprint:2023/628,
      author = {Debadrita Talapatra and Nimish Mishra and Arnab Bag and Sikhar Patranabis and Debdeep Mukhopadhyay},
      title = {{SEC}: Symmetric Encrypted Computation via Fast Look-ups},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/628},
      year = {2023},
      url = {https://eprint.iacr.org/2023/628}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.