Lower bounds for lattice-based compact functional encryption

Tairi E, Ünal A. 2024. Lower bounds for lattice-based compact functional encryption. Advances in Cryptology – EUROCRYPT 2024. EUROCRYPT: International Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol. 14652, 249–279.

Download (ext.)

Conference Paper | Published | English

Scopus indexed
Author
Tairi, Erkan; Ünal, AkinISTA
Department
Series Title
LNCS
Abstract
Functional encryption (FE) is a primitive where the holder of a master secret key can control which functions a user can evaluate on encrypted data. It is a powerful primitive that even implies indistinguishability obfuscation (iO), given sufficiently compact ciphertexts (Ananth-Jain, CRYPTO’15 and Bitansky-Vaikuntanathan, FOCS’15). However, despite being extensively studied, there are FE schemes, such as function-hiding inner-product FE (Bishop-Jain-Kowalczyk, AC’15, Abdalla-Catalano-Fiore-Gay-Ursu, CRYPTO’18) and compact quadratic FE (Baltico-Catalano-Fiore-Gay, Lin, CRYPTO’17), that can be only realized using pairings. This raises the question if there are some mathematical barriers that hinder us from realizing these FE schemes from other assumptions. In this paper, we study the difficulty of constructing lattice-based compact FE. We generalize the impossibility results of Ünal (EC’20) for lattice-based function-hiding FE, and extend it to the case of compact FE. Concretely, we prove lower bounds for lattice-based compact FE schemes which meet some (natural) algebraic restrictions at encryption and decryption, and have ciphertexts of linear size and secret keys of minimal degree. We see our results as important indications of why it is hard to construct lattice-based FE schemes for new functionalities, and which mathematical barriers have to be overcome.
Publishing Year
Date Published
2024-05-08
Proceedings Title
Advances in Cryptology – EUROCRYPT 2024
Acknowledgement
We want to thank the anonymous reviewers of TCC and Eurocrypt for their very helpful comments and suggestions. This work has received funding from the Austrian Science Fund (FWF) and netidee SCIENCE via grant P31621-N38 (PROFET).
Volume
14652
Page
249-279
Conference
EUROCRYPT: International Conference on the Theory and Applications of Cryptographic Techniques
Conference Location
Zurich, Switzerland
Conference Date
2024-05-26 – 2024-05-30
ISSN
eISSN
IST-REx-ID

Cite this

Tairi E, Ünal A. Lower bounds for lattice-based compact functional encryption. In: Advances in Cryptology – EUROCRYPT 2024. Vol 14652. Springer Nature; 2024:249-279. doi:10.1007/978-3-031-58723-8_9
Tairi, E., & Ünal, A. (2024). Lower bounds for lattice-based compact functional encryption. In Advances in Cryptology – EUROCRYPT 2024 (Vol. 14652, pp. 249–279). Zurich, Switzerland: Springer Nature. https://doi.org/10.1007/978-3-031-58723-8_9
Tairi, Erkan, and Akin Ünal. “Lower Bounds for Lattice-Based Compact Functional Encryption.” In Advances in Cryptology – EUROCRYPT 2024, 14652:249–79. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-58723-8_9.
E. Tairi and A. Ünal, “Lower bounds for lattice-based compact functional encryption,” in Advances in Cryptology – EUROCRYPT 2024, Zurich, Switzerland, 2024, vol. 14652, pp. 249–279.
Tairi E, Ünal A. 2024. Lower bounds for lattice-based compact functional encryption. Advances in Cryptology – EUROCRYPT 2024. EUROCRYPT: International Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol. 14652, 249–279.
Tairi, Erkan, and Akin Ünal. “Lower Bounds for Lattice-Based Compact Functional Encryption.” Advances in Cryptology – EUROCRYPT 2024, vol. 14652, Springer Nature, 2024, pp. 249–79, doi:10.1007/978-3-031-58723-8_9.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search