Paper 2020/163
Impossibility Results for Lattice-Based Functional Encryption Schemes
, ETH ZurichAbstract
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
-
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},
url = {https://eprint.iacr.org/2020/163}
}
