Dynamic Bounded-Collusion Streaming Functional Encryption from Minimal Assumptions

Streaming functional encryption (sFE), recently introduced by Guan, Korb, and Sahai [Crypto 2023], is an extension of functional encryption (FE) tailored for iterative computation on dynamic data streams. Unlike in regular FE, in an sFE scheme, users can encrypt and compute on the data as soon as it becomes available and in time proportional to just the size of the newly arrived data.

As sFE implies regular FE, all known constructions of sFE and FE for P/poly require strong cryptographic assumptions which are powerful enough to build indistinguishability obfuscation (iO). In contrast, dynamic bounded-collusion FE, in which the adversary is restricted to making at most Q function queries for some Q determined during encryption (but not fixed at time of setup), can be built from the minimal assumptions of identity-based encryption (for public-key FE) [Agrawal, Maitra, Vempati and Yamada, Crypto 2021; Garg, Goyal, Lu and Waters, Eurocrypt 2022] and one-way functions (for secret-key FE), as secret-key IBE is implied by one-way functions (folklore).

In this paper, we introduce and build dynamic bounded-collusion streaming FE from the same minimal assumptions of identity-based encryption (for public-key sFE) and one-way functions (for secret-key sFE). Similarly to the original sFE paper of Guan, Korb, and Sahai, our scheme satisfies semi-adaptive-function-selective security which is similar to standard adaptive indistinguishability-based security except that we require all functions to be queried before any of the challenge messages.

Along the way, our work also replaces a key ingredient (called OnesFE) from the original work of Guan, Korb, and Sahai with a much simpler construction based on garbled circuits. In contrast, the original approach relied on the powerful object of compact FE (which is known to imply iO) to construct this primitive.