Title: On the Black-Box Complexity of Private-Key Inner-Product Functional Encryption
| Speaker: | Roman Langrehr |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: Traditional encryption (secret key and public key encryption) has a very limited functionality. Namely, it allows encryption of data for a single recipient that can recover the entire data. This is typically sufficient for transmitting data over insecure channels, but insufficient for many modern applications, like end-to-end encrypted cloud storage, where partial access to the data might be needed.
Functional encryption (FE) is a cryptographic primitive that can solve this challenge by allowing to generate customized secret keys that are associated with a function f. Decrypting with such a secret key will reveal only f(m), where m is the encrypted message, and reveal nothing else about m. One of the most well studied variants of FE is inner-product functional encryption (IPFE), where the functions f are restricted to linear functions.
All known instantiations of IPFE, even of its secret-key version, require strong assumptions typically used for public-key encryption. In this talk I will give an insight on why this is the case: An impossibility result for black-box constructions of IPFE from secret-key assumptions (like one-way functions).
The core of our proof is based on a new result of extremal combinatorics, which we proof based on Fourier analysis or the Cauchy-Schwartz inequality.
The talk will first introduce the cryptographic background and give an overview about the cryptographic part of the proof. Then, the combinatorial problem we encountered and our solution will be discussed in more detail. The talk will not require any prior knowledge in cryptography.
The full version of the paper presented can be found here: https://eprint.iacr.org/2024/1877