Towards an interpreter for efficient encrypted computation
Fully homomorphic encryption (FHE) techniques are capable of performing encrypted computation on Boolean circuits, i.e., the user specifies encrypted inputs to the program, and the server computes on the encrypted inputs. Applying these techniques to general programs with recursive procedures and da...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/86170 https://orcid.org/0000-0001-8253-7714 https://orcid.org/0000-0002-1224-0314 https://orcid.org/0000-0003-1467-2150 |
| _version_ | 1811080017789059072 |
|---|---|
| author | Devadas, Srinivas Fletcher, Christopher Wardlaw Van Dijk, Marten |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Devadas, Srinivas Fletcher, Christopher Wardlaw Van Dijk, Marten |
| author_sort | Devadas, Srinivas |
| collection | MIT |
| description | Fully homomorphic encryption (FHE) techniques are capable of performing encrypted computation on Boolean circuits, i.e., the user specifies encrypted inputs to the program, and the server computes on the encrypted inputs. Applying these techniques to general programs with recursive procedures and data-dependent loops has not been a focus of attention. In this paper, we take a first step toward building an interpreter that, given programs with complex control flow, schedules efficient code suitable for the application of FHE schemes.
We first describe how programs written in a small Turing-complete instruction set can be executed with encrypted data and point out inefficiencies in this methodology. We then provide examples of scheduling (a) the greatest common divisor (GCD) problem using Euclid's algorithm and (b) the 3-Satisfiability (3SAT) problem using a recursive backtracking algorithm into path-levelized FHE computations. We describe how path levelization reduces control flow ambiguity and improves encrypted computation efficiency. Using these techniques and data-dependent loops as a starting point, we then build support for hierarchical programs made up of phases, where each phase corresponds to a fixed point computation that can be used to further improve the efficiency of encrypted computation.
In our setting, the adversary learns an estimate of the number of steps required to complete the computation, which we show is the least amount of leakage possible. |
| first_indexed | 2024-09-23T11:24:22Z |
| format | Article |
| id | mit-1721.1/86170 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:24:22Z |
| publishDate | 2014 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/861702022-09-27T19:18:08Z Towards an interpreter for efficient encrypted computation Devadas, Srinivas Fletcher, Christopher Wardlaw Van Dijk, Marten Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Fletcher, Christopher Wardlaw Van Dijk, Marten Devadas, Srinivas Fully homomorphic encryption (FHE) techniques are capable of performing encrypted computation on Boolean circuits, i.e., the user specifies encrypted inputs to the program, and the server computes on the encrypted inputs. Applying these techniques to general programs with recursive procedures and data-dependent loops has not been a focus of attention. In this paper, we take a first step toward building an interpreter that, given programs with complex control flow, schedules efficient code suitable for the application of FHE schemes. We first describe how programs written in a small Turing-complete instruction set can be executed with encrypted data and point out inefficiencies in this methodology. We then provide examples of scheduling (a) the greatest common divisor (GCD) problem using Euclid's algorithm and (b) the 3-Satisfiability (3SAT) problem using a recursive backtracking algorithm into path-levelized FHE computations. We describe how path levelization reduces control flow ambiguity and improves encrypted computation efficiency. Using these techniques and data-dependent loops as a starting point, we then build support for hierarchical programs made up of phases, where each phase corresponds to a fixed point computation that can be used to further improve the efficiency of encrypted computation. In our setting, the adversary learns an estimate of the number of steps required to complete the computation, which we show is the least amount of leakage possible. 2014-04-14T19:11:45Z 2014-04-14T19:11:45Z 2012-10 Article http://purl.org/eprint/type/ConferencePaper 9781450316651 http://hdl.handle.net/1721.1/86170 Christopher W. Fletcher, Marten van Dijk, and Srinivas Devadas. 2012. Towards an interpreter for efficient encrypted computation. In Proceedings of the 2012 ACM Workshop on Cloud computing security workshop (CCSW '12). ACM, New York, NY, USA, 83-94. https://orcid.org/0000-0001-8253-7714 https://orcid.org/0000-0002-1224-0314 https://orcid.org/0000-0003-1467-2150 en_US http://dx.doi.org/10.1145/2381913.2381928 Proceedings of the 2012 ACM Workshop on Cloud computing security workshop (CCSW '12) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Devadas, Srinivas Fletcher, Christopher Wardlaw Van Dijk, Marten Towards an interpreter for efficient encrypted computation |
| title | Towards an interpreter for efficient encrypted computation |
| title_full | Towards an interpreter for efficient encrypted computation |
| title_fullStr | Towards an interpreter for efficient encrypted computation |
| title_full_unstemmed | Towards an interpreter for efficient encrypted computation |
| title_short | Towards an interpreter for efficient encrypted computation |
| title_sort | towards an interpreter for efficient encrypted computation |
| url | http://hdl.handle.net/1721.1/86170 https://orcid.org/0000-0001-8253-7714 https://orcid.org/0000-0002-1224-0314 https://orcid.org/0000-0003-1467-2150 |
| work_keys_str_mv | AT devadassrinivas towardsaninterpreterforefficientencryptedcomputation AT fletcherchristopherwardlaw towardsaninterpreterforefficientencryptedcomputation AT vandijkmarten towardsaninterpreterforefficientencryptedcomputation |