Lower Bounds for Lattice-based Compact Functional Encryption

Erkan Tairi; Akın Ünal

Paper 2023/719

Lower Bounds for Lattice-based Compact Functional Encryption

Erkan Tairi

, DIENS, École normale supérieure, CNRS, Inria, PSL University, Paris, France

Akın Ünal

, ISTA, Klosterneuburg, Austria

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in EUROCRYPT 2024
Keywords: Lower Bounds Lattice-based Cryptography Functional Encryption Compact
Contact author(s): erkan tairi @ gmail com
akin uenal @ posteo de
History: 2024-02-27: revised; 2023-05-18: received; See all versions
Short URL: https://ia.cr/2023/719
License: CC BY

BibTeX

@misc{cryptoeprint:2023/719,
      author = {Erkan Tairi and Akın Ünal},
      title = {Lower Bounds for Lattice-based Compact Functional Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2023/719},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/719}},
      url = {https://eprint.iacr.org/2023/719}
}