Obfuscation of Probabilistic Circuits and Applications
© International Association for Cryptologic Research 2015. This paper studies the question of how to define, construct, and use obfuscators for probabilistic programs. Such obfuscators compil a possibly randomized program into a deterministic one, which achieves computationally indistinguishable beh...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Nature America, Inc
2021
|
| Online Access: | https://hdl.handle.net/1721.1/138151 |
| _version_ | 1811072872947384320 |
|---|---|
| author | Ananth, Prabhanjan Brakerski, Zvika Segev, Gil Vaikuntananthan, Vinod |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Ananth, Prabhanjan Brakerski, Zvika Segev, Gil Vaikuntananthan, Vinod |
| author_sort | Ananth, Prabhanjan |
| collection | MIT |
| description | © International Association for Cryptologic Research 2015. This paper studies the question of how to define, construct, and use obfuscators for probabilistic programs. Such obfuscators compil a possibly randomized program into a deterministic one, which achieves computationally indistinguishable behavior from the original program as long as it is run on each input at most once. For obfuscation, we propose a notion that extends indistinguishability obfuscation to probabilistic circuits: It should be hard to distinguish between the obfuscations of any two circuits whose output distributions at each input are computationally indistinguishable, possibly in presence of some auxiliary input. We call the resulting notion probabilistic indistinguishability obfuscation (pIO). We define several variants of pIO, and study relations among them. Moreover, we give a construction of one of our variants, called X-pIO, from sub-exponentially hard indistinguishability obfuscation (for deterministic circuits) and one-way functions. We then move on to show a number of applications of pIO. In particular, we first give a general and natural methodology to achieve fully homomorphic encryption (FHE) from variants of pIO and of semantically secure encryption schemes. In particular, one instantiation leads to FHE from any X-pIO obfuscator and any re-randomizable encryption scheme that’s slightly super-polynomially secure. We note that this constitutes the first construction of full-fledged FHE that does not rely on encryption with circular security. Moreover, assuming sub-exponentially secure puncturable PRFs computable in NC1, sub-exponentially-secure indistinguishability obfuscation for (deterministic) NC1 circuits can be bootstrapped to obtain indistinguishability obfuscation for arbitrary (deterministic) poly-size circuits (previously such bootstrapping was known only assuming FHE with NC1 decryption algorithm). |
| first_indexed | 2024-09-23T09:18:33Z |
| format | Article |
| id | mit-1721.1/138151 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:18:33Z |
| publishDate | 2021 |
| publisher | Springer Nature America, Inc |
| record_format | dspace |
| spelling | mit-1721.1/1381512023-12-08T17:31:24Z Obfuscation of Probabilistic Circuits and Applications Ananth, Prabhanjan Brakerski, Zvika Segev, Gil Vaikuntananthan, Vinod Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © International Association for Cryptologic Research 2015. This paper studies the question of how to define, construct, and use obfuscators for probabilistic programs. Such obfuscators compil a possibly randomized program into a deterministic one, which achieves computationally indistinguishable behavior from the original program as long as it is run on each input at most once. For obfuscation, we propose a notion that extends indistinguishability obfuscation to probabilistic circuits: It should be hard to distinguish between the obfuscations of any two circuits whose output distributions at each input are computationally indistinguishable, possibly in presence of some auxiliary input. We call the resulting notion probabilistic indistinguishability obfuscation (pIO). We define several variants of pIO, and study relations among them. Moreover, we give a construction of one of our variants, called X-pIO, from sub-exponentially hard indistinguishability obfuscation (for deterministic circuits) and one-way functions. We then move on to show a number of applications of pIO. In particular, we first give a general and natural methodology to achieve fully homomorphic encryption (FHE) from variants of pIO and of semantically secure encryption schemes. In particular, one instantiation leads to FHE from any X-pIO obfuscator and any re-randomizable encryption scheme that’s slightly super-polynomially secure. We note that this constitutes the first construction of full-fledged FHE that does not rely on encryption with circular security. Moreover, assuming sub-exponentially secure puncturable PRFs computable in NC1, sub-exponentially-secure indistinguishability obfuscation for (deterministic) NC1 circuits can be bootstrapped to obtain indistinguishability obfuscation for arbitrary (deterministic) poly-size circuits (previously such bootstrapping was known only assuming FHE with NC1 decryption algorithm). 2021-11-18T13:54:13Z 2021-11-18T13:54:13Z 2015 2019-07-09T16:24:43Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/138151 Ananth, Prabhanjan, Brakerski, Zvika, Segev, Gil and Vaikuntananthan, Vinod. 2015. "Obfuscation of Probabilistic Circuits and Applications." en 10.1007/978-3-662-46497-7_19 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer Nature America, Inc Other repository |
| spellingShingle | Ananth, Prabhanjan Brakerski, Zvika Segev, Gil Vaikuntananthan, Vinod Obfuscation of Probabilistic Circuits and Applications |
| title | Obfuscation of Probabilistic Circuits and Applications |
| title_full | Obfuscation of Probabilistic Circuits and Applications |
| title_fullStr | Obfuscation of Probabilistic Circuits and Applications |
| title_full_unstemmed | Obfuscation of Probabilistic Circuits and Applications |
| title_short | Obfuscation of Probabilistic Circuits and Applications |
| title_sort | obfuscation of probabilistic circuits and applications |
| url | https://hdl.handle.net/1721.1/138151 |
| work_keys_str_mv | AT ananthprabhanjan obfuscationofprobabilisticcircuitsandapplications AT brakerskizvika obfuscationofprobabilisticcircuitsandapplications AT segevgil obfuscationofprobabilisticcircuitsandapplications AT vaikuntananthanvinod obfuscationofprobabilisticcircuitsandapplications |