Paper 2020/163

Impossibility Results for Lattice-Based Functional Encryption Schemes

Akin Ünal, ETH Zurich
Abstract

Functional Encryption denotes a form of encryption where a master secret key-holder can control which functions a user can evaluate on encrypted data. Learning With Errors (LWE) (Regev, STOC'05) is known to be a useful cryptographic hardness assumption which implies strong primitives such as, for example, fully homomorphic encryption (Brakerski-Vaikuntanathan, FOCS'11) and lockable obfuscation (Goyal et al., Wichs et al., FOCS'17). Despite its strength, however, there is just a limited number of functional encryption schemes which can be based on LWE. In fact, there are functional encryption schemes which can be achieved by using pairings but for which no secure instantiations from lattice-based assumptions are known: function-hiding inner product encryption (Lin, Baltico et al., CRYPTO'17) and compact quadratic functional encryption (Abdalla et al., CRYPTO'18). This raises the question whether there are some mathematical barriers which hinder us from realizing function-hiding and compact functional encryption schemes from lattice-based assumptions as LWE. To study this problem, we prove an impossibility result for function-hiding functional encryption schemes which meet some algebraic restrictions at ciphertext encryption and decryption. Those restrictions are met by a lot of attribute-based, identity-based and functional encryption schemes whose security stems from LWE. Therefore, we see our results as important indications why it is hard to construct new functional encryption schemes from LWE and which mathematical restrictions have to be overcome to construct secure lattice-based functional encryption schemes for new functionalities.

Note: Updated author's information and fixed two typos.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2020
DOI
10.1007/978-3-030-45721-1_7
Keywords
Functional EncryptionFunction-HidingImpossibilityLWELattice-basedOnlineOffline
Contact author(s)
akin uenal @ inf ethz ch
History
2023-04-30: revised
2020-02-13: received
See all versions
Short URL
https://ia.cr/2020/163
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/163,
      author = {Akin Ünal},
      title = {Impossibility Results for Lattice-Based Functional Encryption Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2020/163},
      year = {2020},
      doi = {10.1007/978-3-030-45721-1_7},
      note = {\url{https://eprint.iacr.org/2020/163}},
      url = {https://eprint.iacr.org/2020/163}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.