---
_id: '17126'
abstract:
- lang: eng
  text: "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.\r\n\r\nIn 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."
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).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Erkan
  full_name: Tairi, Erkan
  last_name: Tairi
- first_name: Akin
  full_name: Ünal, Akin
  id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
  last_name: Ünal
  orcid: 0000-0002-8929-0221
citation:
  ama: 'Tairi E, Ünal A. Lower bounds for lattice-based compact functional encryption.
    In: <i>Advances in Cryptology – EUROCRYPT 2024</i>. Vol 14652. Springer Nature;
    2024:249-279. doi:<a href="https://doi.org/10.1007/978-3-031-58723-8_9">10.1007/978-3-031-58723-8_9</a>'
  apa: 'Tairi, E., &#38; Ünal, A. (2024). Lower bounds for lattice-based compact functional
    encryption. In <i>Advances in Cryptology – EUROCRYPT 2024</i> (Vol. 14652, pp.
    249–279). Zurich, Switzerland: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-58723-8_9">https://doi.org/10.1007/978-3-031-58723-8_9</a>'
  chicago: Tairi, Erkan, and Akin Ünal. “Lower Bounds for Lattice-Based Compact Functional
    Encryption.” In <i>Advances in Cryptology – EUROCRYPT 2024</i>, 14652:249–79.
    Springer Nature, 2024. <a href="https://doi.org/10.1007/978-3-031-58723-8_9">https://doi.org/10.1007/978-3-031-58723-8_9</a>.
  ieee: E. Tairi and A. Ünal, “Lower bounds for lattice-based compact functional encryption,”
    in <i>Advances in Cryptology – EUROCRYPT 2024</i>, Zurich, Switzerland, 2024,
    vol. 14652, pp. 249–279.
  ista: 'Tairi E, Ünal A. 2024. Lower bounds for lattice-based compact functional
    encryption. Advances in Cryptology – EUROCRYPT 2024. EUROCRYPT: Theory and Applications
    of Cryptographic Techniques, LNCS, vol. 14652, 249–279.'
  mla: Tairi, Erkan, and Akin Ünal. “Lower Bounds for Lattice-Based Compact Functional
    Encryption.” <i>Advances in Cryptology – EUROCRYPT 2024</i>, vol. 14652, Springer
    Nature, 2024, pp. 249–79, doi:<a href="https://doi.org/10.1007/978-3-031-58723-8_9">10.1007/978-3-031-58723-8_9</a>.
  short: E. Tairi, A. Ünal, in:, Advances in Cryptology – EUROCRYPT 2024, Springer
    Nature, 2024, pp. 249–279.
conference:
  end_date: 2024-05-30
  location: Zurich, Switzerland
  name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
  start_date: 2024-05-26
date_created: 2024-06-09T22:01:03Z
date_published: 2024-05-08T00:00:00Z
date_updated: 2025-09-08T07:48:18Z
day: '08'
department:
- _id: KrPi
doi: 10.1007/978-3-031-58723-8_9
external_id:
  isi:
  - '001278247600009'
intvolume: '     14652'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2023/719.pdf
month: '05'
oa: 1
oa_version: Submitted Version
page: 249-279
publication: Advances in Cryptology – EUROCRYPT 2024
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783031587221'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lower bounds for lattice-based compact functional encryption
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 14652
year: '2024'
...