TY - GEN

T1 - Functional encryption without obfuscation

AU - Garg, Sanjam

AU - Gentry, Craig

AU - Halevi, Shai

AU - Zhandry, Mark

PY - 2016/1/1

Y1 - 2016/1/1

N2 - Previously known functional encryption (FE) schemes for general circuits relied on indistinguishability obfuscation, which in turn either relies on an exponential number of assumptions (basically, one per circuit), or a polynomial set of assumptions, but with an exponential loss in the security reduction. Additionally most of these schemes are proved in the weaker selective security model, where the adversary is forced to specify its target before seeing the public parameters. For these constructions, full security can be obtained but at the cost of an exponential loss in the security reduction. In this work, we overcome the above limitations and realize an adaptively secure functional encryption scheme without using indistinguishability obfuscation. Specifically the security of our scheme relies only on the polynomial hardness of simple assumptions on composite order multilinear maps. Though we do not currently have secure instantiations for these assumptions, we expect that multilinear maps supporting these assumptions will discovered in the future. Alternatively, follow up results may yield constructions which can be securely instantiated. As a separate technical contribution of independent interest, we show how to add to existing graded encoding schemes a new extension function, that can be thought of as dynamically introducing new encoding levels.

AB - Previously known functional encryption (FE) schemes for general circuits relied on indistinguishability obfuscation, which in turn either relies on an exponential number of assumptions (basically, one per circuit), or a polynomial set of assumptions, but with an exponential loss in the security reduction. Additionally most of these schemes are proved in the weaker selective security model, where the adversary is forced to specify its target before seeing the public parameters. For these constructions, full security can be obtained but at the cost of an exponential loss in the security reduction. In this work, we overcome the above limitations and realize an adaptively secure functional encryption scheme without using indistinguishability obfuscation. Specifically the security of our scheme relies only on the polynomial hardness of simple assumptions on composite order multilinear maps. Though we do not currently have secure instantiations for these assumptions, we expect that multilinear maps supporting these assumptions will discovered in the future. Alternatively, follow up results may yield constructions which can be securely instantiated. As a separate technical contribution of independent interest, we show how to add to existing graded encoding schemes a new extension function, that can be thought of as dynamically introducing new encoding levels.

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

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

U2 - 10.1007/978-3-662-49099-0_18

DO - 10.1007/978-3-662-49099-0_18

M3 - Conference contribution

AN - SCOPUS:84954177032

SN - 9783662490983

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 480

EP - 511

BT - Theory of Cryptography - 3th International Conference, TCC 2016-A, Proceedings

A2 - Malkin, Tal

A2 - Kushilevitz, Eyal

PB - Springer Verlag

T2 - 13th International Conference on Theory of Cryptography, TCC 2016

Y2 - 10 January 2016 through 13 January 2016

ER -