Paper 2017/080

From Minicrypt to Obfustopia via Private-Key Functional Encryption

Ilan Komargodski and Gil Segev

Abstract

Private-key functional encryption enables fine-grained access to symmetrically-encrypted data. Although private-key functional encryption (supporting an unbounded number of keys and ciphertexts) seems significantly weaker than its public-key variant, its known realizations all rely on public-key functional encryption. At the same time, however, up until recently it was not known to imply any public-key primitive, demonstrating our poor understanding of this extremely-useful primitive. Recently, Bitansky et al. [TCC '16B] showed that sub-exponentially-secure private-key function encryption bridges from nearly-exponential security in Minicrypt to slightly super-polynomial security in Cryptomania, and from sub-exponential security in Cryptomania to Obfustopia. Specifically, given any sub-exponentially-secure private-key functional encryption scheme and a nearly-exponentially-secure one-way function, they constructed a public-key encryption scheme with slightly super-polynomial security. Assuming, in addition, a sub-exponentially-secure public-key encryption scheme, they then constructed an indistinguishability obfuscator. We settle the problem of positioning private-key functional encryption within the hierarchy of cryptographic primitives by placing it in Obfustopia. First, given any quasi-polynomially-secure private-key functional encryption scheme, we construct an indistinguishability obfuscator for circuits with inputs of poly-logarithmic length. Then, we observe that such an obfuscator can be used to instantiate many natural applications of indistinguishability obfuscation. Specifically, relying on sub-exponentially-secure one-way functions, we show that quasi-polynomially-secure private-key functional encryption implies not just public-key encryption but leads all the way to public-key functional encryption for circuits with inputs of poly-logarithmic length. Moreover, relying on sub-exponentially-secure injective one-way functions, we show that quasi-polynomially-secure private-key functional encryption implies a hard-on-average distribution over instances of a PPAD-complete problem. Underlying our constructions is a new transformation from single-input functional encryption to multi-input functional encryption in the private-key setting. The previously known such transformation [Brakerski et al., EUROCRYPT '16] required a sub-exponentially-secure single-input scheme, and obtained a scheme supporting only a slightly super-constant number of inputs. Our transformation both relaxes the underlying assumption and supports more inputs: Given any quasi-polynomially-secure single-input scheme, we obtain a scheme supporting a poly-logarithmic number of inputs.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in EUROCRYPT 2017
Keywords
Private-key functional encryptionPublic-key functional encryptionPPAD hardnessIndistinguishability obfuscationgeneric constructions
Contact author(s)
ilan komargodski @ weizmann ac il
History
2017-02-06: received
Short URL
https://ia.cr/2017/080
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/080,
      author = {Ilan Komargodski and Gil Segev},
      title = {From Minicrypt to Obfustopia via Private-Key Functional Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2017/080},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/080}},
      url = {https://eprint.iacr.org/2017/080}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.