On the Black-Box Complexity of Private-Key Inner-Product Functional Encryption

Mohammad Hajiabadi, Roman Langrehr, Adam O’Neill, Mingyuan Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We initiate the study of the black-box complexity of private-key functional encryption (FE). Of central importance in the private-key setting is the inner-product functionality, which is currently only known from assumptions that imply public-key encryption, such as Decisional Diffie-Hellman or Learning-with-Errors. As our main result, we rule out black-box constructions of private-key inner-product FE from random oracles. This implies a black-box separation between private-key inner-product FE from all symmetric-key primitives implied by random oracles (e.g., symmetric-key encryption and collision-resistant hash functions). Proving lower bounds for private-key functional encryption schemes introduces challenges that were absent in prior works. In particular, the combinatorial techniques developed by prior works for proving black-box lower bounds are only useful in the public-key setting and predicate encryption settings, which all fail for the private-key FE case. Our work develops novel combinatorial techniques based on Fourier analysis to overcome these barriers. We expect these techniques to be widely useful in future research in this area.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 22nd International Conference, TCC 2024, Proceedings
EditorsElette Boyle, Elette Boyle, Mohammad Mahmoody
PublisherSpringer Science and Business Media Deutschland GmbH
Pages318-343
Number of pages26
ISBN (Print)9783031780196
DOIs
StatePublished - 2025
Event22nd Theory of Cryptography Conference, TCC 2024 - Milan, Italy
Duration: Dec 2 2024Dec 6 2024

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume15366 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd Theory of Cryptography Conference, TCC 2024
Country/TerritoryItaly
CityMilan
Period12/2/2412/6/24

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'On the Black-Box Complexity of Private-Key Inner-Product Functional Encryption'. Together they form a unique fingerprint.

Cite this