Indistinguishability Obfuscation from Functional Encryption
© 2018 Association for Computing Machinery. Indistinguishability obfuscation (IO) is a tremendous notion, powerful enough to give rise to almost any known cryptographic object. Prior candidate IO constructions were based on specific assumptions on algebraic objects called multi-linear graded encodin...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/134910 |
| _version_ | 1811090760873803776 |
|---|---|
| author | Bitansky, Nir Vaikuntanathan, Vinod |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Bitansky, Nir Vaikuntanathan, Vinod |
| author_sort | Bitansky, Nir |
| collection | MIT |
| description | © 2018 Association for Computing Machinery. Indistinguishability obfuscation (IO) is a tremendous notion, powerful enough to give rise to almost any known cryptographic object. Prior candidate IO constructions were based on specific assumptions on algebraic objects called multi-linear graded encodings. We present a generic construction of indistinguishability obfuscation from public-key functional encryption with succinct encryption circuits and subexponential security. This shows the equivalence of indistinguishability obfuscation and public-key functional encryption, a primitive that has previously seemed to be much weaker, lacking the power and the staggering range of applications of indistinguishability obfuscation. Our main construction can be based on functional encryption schemes that support a single functional key, and where the encryption circuit grows sub-linearly in the circuit-size of the function. We further show that sublinear succinctness in circuit-size for single-key schemes can be traded with sublinear succinctness in the number of keys (also known as the collusion-size) for multi-key schemes. We also show that, under the Learning with Errors assumption, our techniques imply that any indistinguishability obfuscator can be converted into one where the size of obfuscated circuits is twice that of the original circuit plus an additive overhead that is polynomial in its depth, input length, and the security parameter. |
| first_indexed | 2024-09-23T14:51:32Z |
| format | Article |
| id | mit-1721.1/134910 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:51:32Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1349102023-12-19T20:43:12Z Indistinguishability Obfuscation from Functional Encryption Bitansky, Nir Vaikuntanathan, Vinod Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2018 Association for Computing Machinery. Indistinguishability obfuscation (IO) is a tremendous notion, powerful enough to give rise to almost any known cryptographic object. Prior candidate IO constructions were based on specific assumptions on algebraic objects called multi-linear graded encodings. We present a generic construction of indistinguishability obfuscation from public-key functional encryption with succinct encryption circuits and subexponential security. This shows the equivalence of indistinguishability obfuscation and public-key functional encryption, a primitive that has previously seemed to be much weaker, lacking the power and the staggering range of applications of indistinguishability obfuscation. Our main construction can be based on functional encryption schemes that support a single functional key, and where the encryption circuit grows sub-linearly in the circuit-size of the function. We further show that sublinear succinctness in circuit-size for single-key schemes can be traded with sublinear succinctness in the number of keys (also known as the collusion-size) for multi-key schemes. We also show that, under the Learning with Errors assumption, our techniques imply that any indistinguishability obfuscator can be converted into one where the size of obfuscated circuits is twice that of the original circuit plus an additive overhead that is polynomial in its depth, input length, and the security parameter. 2021-10-27T20:09:49Z 2021-10-27T20:09:49Z 2018 2019-07-09T16:49:38Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/134910 en 10.1145/3234511 Journal of the ACM Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) Other repository |
| spellingShingle | Bitansky, Nir Vaikuntanathan, Vinod Indistinguishability Obfuscation from Functional Encryption |
| title | Indistinguishability Obfuscation from Functional Encryption |
| title_full | Indistinguishability Obfuscation from Functional Encryption |
| title_fullStr | Indistinguishability Obfuscation from Functional Encryption |
| title_full_unstemmed | Indistinguishability Obfuscation from Functional Encryption |
| title_short | Indistinguishability Obfuscation from Functional Encryption |
| title_sort | indistinguishability obfuscation from functional encryption |
| url | https://hdl.handle.net/1721.1/134910 |
| work_keys_str_mv | AT bitanskynir indistinguishabilityobfuscationfromfunctionalencryption AT vaikuntanathanvinod indistinguishabilityobfuscationfromfunctionalencryption |