TY - JOUR

T1 - Decomposable Obfuscation

T2 - A Framework for Building Applications of Obfuscation from Polynomial Hardness

AU - Liu, Qipeng

AU - Zhandry, Mark

N1 - Funding Information:
This work is supported in part by NSF. The views expressed are those of the authors and do not reflect the official policy or position of the National Science Foundation or the U.S. Government.
Publisher Copyright:
© 2021, The Author(s), under exclusive licence to International Association for Cryptologic Research.

PY - 2021/7

Y1 - 2021/7

N2 - There is some evidence that indistinguishability obfuscation (iO) requires either exponentially many assumptions or (sub)exponentially hard assumptions, and indeed, all known ways of building obfuscation suffer one of these two limitations. As such, any application built from iO suffers from these limitations as well. However, for most applications, such limitations do not appear to be inherent to the application, just the approach using iO. Indeed, several recent works have shown how to base applications of iO instead on functional encryption (FE), which can in turn be based on the polynomial hardness of just a few assumptions. However, these constructions are quite complicated and recycle a lot of similar techniques. In this work, we unify the results of previous works in the form of a weakened notion of obfuscation, called decomposable obfuscation. We show (1) how to build decomposable obfuscation from functional encryption and (2) how to build a variety of applications from decomposable obfuscation, including all of the applications already known from FE. The construction in (1) hides most of the difficult techniques in the prior work, whereas the constructions in (2) are much closer to the comparatively simple constructions from iO. As such, decomposable obfuscation represents a convenient new platform for obtaining more applications from polynomial hardness.

AB - There is some evidence that indistinguishability obfuscation (iO) requires either exponentially many assumptions or (sub)exponentially hard assumptions, and indeed, all known ways of building obfuscation suffer one of these two limitations. As such, any application built from iO suffers from these limitations as well. However, for most applications, such limitations do not appear to be inherent to the application, just the approach using iO. Indeed, several recent works have shown how to base applications of iO instead on functional encryption (FE), which can in turn be based on the polynomial hardness of just a few assumptions. However, these constructions are quite complicated and recycle a lot of similar techniques. In this work, we unify the results of previous works in the form of a weakened notion of obfuscation, called decomposable obfuscation. We show (1) how to build decomposable obfuscation from functional encryption and (2) how to build a variety of applications from decomposable obfuscation, including all of the applications already known from FE. The construction in (1) hides most of the difficult techniques in the prior work, whereas the constructions in (2) are much closer to the comparatively simple constructions from iO. As such, decomposable obfuscation represents a convenient new platform for obtaining more applications from polynomial hardness.

KW - Functional encryption

KW - Indistinguishability obfuscation

KW - Polynomial hardness

KW - PPAD

KW - Universal sampler

UR - http://www.scopus.com/inward/record.url?scp=85109698184&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85109698184&partnerID=8YFLogxK

U2 - 10.1007/s00145-021-09400-4

DO - 10.1007/s00145-021-09400-4

M3 - Article

AN - SCOPUS:85109698184

SN - 0933-2790

VL - 34

JO - Journal of Cryptology

JF - Journal of Cryptology

IS - 3

M1 - 35

ER -