TY - GEN
T1 - On the Black-Box Complexity of Private-Key Inner-Product Functional Encryption
AU - Hajiabadi, Mohammad
AU - Langrehr, Roman
AU - O’Neill, Adam
AU - Wang, Mingyuan
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2025.
PY - 2025
Y1 - 2025
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85211355321&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85211355321&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-78020-2_11
DO - 10.1007/978-3-031-78020-2_11
M3 - Conference contribution
AN - SCOPUS:85211355321
SN - 9783031780196
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 318
EP - 343
BT - Theory of Cryptography - 22nd International Conference, TCC 2024, Proceedings
A2 - Boyle, Elette
A2 - Boyle, Elette
A2 - Mahmoody, Mohammad
PB - Springer Science and Business Media Deutschland GmbH
T2 - 22nd Theory of Cryptography Conference, TCC 2024
Y2 - 2 December 2024 through 6 December 2024
ER -