International Association for Cryptologic Research

International Association
for Cryptologic Research


Impossibility Results for Lattice-Based Functional Encryption Schemes

Akın Ünal , Karlsruhe Institute of Technology and ETH Zurich, Switzerland
DOI: 10.1007/978-3-030-45721-1_7 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2020
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 et al., ITCS'12) 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.
Video from EUROCRYPT 2020
  title={Impossibility Results for Lattice-Based Functional Encryption Schemes},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  keywords={Functional Encryption;Function-Hiding;Impossibility;LWE;Lattice-based;Online/Offline},
  author={Akın Ünal},