International Association
for Cryptologic Research

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 One-sFE) 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.

Incrementally verifiable computation (IVC) [Valiant, TCC'08] allows one to iteratively prove that a configuration $x_0$ reaches another configuration $x_T$ after repeated applications of a (possibly non-deterministic) transition function $\mathcal{M}$. The key requirement is that the size of the proof and the time to update the proof is sublinear in the number of steps $T$. IVC has numerous applications such as proving correctness of virtual machine executions in blockchains. Currently, IVC for $\mathsf{NP}$ is only known to exist in idealized models, or based on knowledge assumptions. No constructions are known from standard assumptions, or even in the random oracle model. Furthermore, as observed in prior works, since IVC for $\mathsf{NP}$ implies adaptive succinct non-interactive arguments for $\mathsf{NP}$, the work of Gentry-Wichs [STOC `11] seemingly poses barriers to constructing IVC for $\mathsf{NP}$ from falsifiable assumptions. In this work, we observe that the Gentry-Wichs barrier can be overcome for IVC for NP. We show the following two results: * Assuming subexponential $i\mathcal{O}$ and LWE (or bilinear maps), we construct IVC for all $\mathsf{NP}$ with proof size $\mathsf{poly}(|x_i|,\log T)$. * Assuming subexponential $i\mathcal{O}$ and injective PRGs, we construct IVC for \emph{trapdoor IVC languages} where the proof-size is $\mathsf{poly}(\log T)$. Informally, an IVC language has a trapdoor if there {\em exists} a (not necessarily easy to find) polynomial-sized circuit that determines if a configuration $x_i$ is reachable from $x_0$ in $i$ steps.

This paper presents the *first adaptively secure* streaming functional encryption (sFE) scheme for P/Poly. sFE extends traditional FE to vast and/or dynamically evolving data sets, enabling incremental encryption of streaming inputs and iterative partial decryption over encrypted prefixes. The proposed sFE scheme is built from indistinguishability obfuscation for P/Poly and injective PRGs. We achieve this result via two core technical contributions which may be of independent interest. First, we introduce a novel "gluing" mechanism to achieve adaptive security by intertwining two schemes, each possessing one aspect of adaptive security. Second, we enhance the powerful Koppula-Lewko-Waters [STOC 2015] framework with a "sliding window" technique, enabling authenticated iterative computation with fresh inputs at each iteration. Prior work by Guan, Korb, and Sahai [CRYPTO 2023] constructed sFE but only under a (semi-adaptive) function-selective security model, requiring all functional keys to be queried before observing any ciphertext. This severe limitation precludes practical scenarios and leaves adaptive security as a crucial *open challenge* — explicitly highlighted by their work — which we address in this paper.

Randomized functional encryption (rFE) generalizes functional encryption (FE) by incorporating randomized functionalities. Randomized multi-input functional encryption (rMIFE) extends rFE to accommodate multi-input randomized functionalities. In this paper, we reassess the framework of rFE/rMIFE enhancing our understanding of this primitive and laying the groundwork for more secure and flexible constructions in this field. Specifically, we make three key contributions: - Stronger IND definition: We show the prevailing indistinguishability-based security definition protects *only* against malicious *decryptors* and leaves systems *vulnerable* to malicious *encryptors* -- a critical requirement for rFE/rMIFE since their inception. We then propose a refined IND notion that simultaneously handles both threats. - Separating counterexample: Illustrating this definitional gap, we meticulously craft an rFE scheme -- using standard tools (FE, PRF, PKE, simulation‑sound NIZK) -- that satisfies the old definition yet is blatantly insecure in practice (and where this insecurity would be precluded by our enhanced definition). - Adaptive, unbounded‑message rMIFE: The sole, viable prior rMIFE construction by Goldwasser et al. [EUROCRYPT 2014] permits only a fixed message bound per encryption slot and offers merely selective security. Leveraging sub‑exponentially secure indistinguishability obfuscation and techniques of Goyal et al. [ASIACRYPT 2016] built for deterministic MIFE, we give the first rMIFE scheme that supports an unbounded number of messages per slot and attains full adaptive security.

We initiate the study of streaming functional encryption (sFE) which is designed for scenarios in which data arrives in a streaming manner and is computed on in an iterative manner as the stream arrives. Unlike in a standard functional encryption (FE) scheme, in an sFE scheme, we (1) do not require the entire data set to be known at encryption time and (2) allow for partial decryption given only a prefix of the input. More specifically, in an sFE scheme, we can sequentially encrypt each data point x_i in a stream of data x = x_1 . . . x_n as it arrives, without needing to wait for all n values. We can then generate function keys for streaming functions which are stateful functions that take as input a message x_i and a state st_i and output a value y_i and the next state st_{i+1}. For any k ≤ n, a user with a function key for a streaming function f can learn the first k output values y_1 . . . y_k where (y_i, st_{i+1}) = f (x_i, st_i) and st_1 = ⊥ given only ciphertexts for the first k elements x_1 . . . x_k. In this work, we introduce the notion of sFE and show how to construct it from FE. In particular, we show how to achieve a secure sFE scheme for P/Poly from a compact, secure FE scheme for P/Poly, where our security notion for sFE is similar to standard FE security except that we require all function queries to be made before the challenge ciphertext query. Furthermore, by combining our result with the FE construction of Jain, Lin, and Sahai (STOC, 2022), we show how to achieve a secure sFE scheme for P/Poly from the polynomial hardness of well-studied assumptions.

A wiretap coding scheme (Wyner in Bell Syst Tech J 54(8):1355–1387, 1975) enables Alice to reliably communicate a message m to an honest Bob by sending an encoding c over a noisy channel $$\textsf{ChB}$$ ChB , while at the same time hiding m from Eve who receives c over another noisy channel $$\textsf{ChE}$$ ChE . Wiretap coding is clearly impossible when $$\textsf{ChB}$$ ChB is a degraded version of $$\textsf{ChE}$$ ChE , in the sense that the output of $$\textsf{ChB}$$ ChB can be simulated using only the output of $$\textsf{ChE}$$ ChE . A classic work of Csiszár and Korner (IEEE Trans Inf Theory 24(3):339–348, 1978) shows that the converse does not hold. This follows from their full characterization of the channel pairs $$(\textsf{ChB},\textsf{ChE})$$ ( ChB , ChE ) that enable information-theoretic wiretap coding. In this work, we show that in fact the converse does hold when considering computational security ; that is, wiretap coding against a computationally bounded Eve is possible if and only if $$\textsf{ChB}$$ ChB is not a degraded version of $$\textsf{ChE}$$ ChE . Our construction assumes the existence of virtual black-box obfuscation of specific classes of “evasive” functions that generalize fuzzy point functions and can be heuristically instantiated using indistinguishability obfuscation. Finally, our solution has the appealing feature of being universal in the sense that Alice’s algorithm depends only on $$\textsf{ChB}$$ ChB and not on $$\textsf{ChE}$$ ChE .

A wiretap coding scheme (Wyner, Bell Syst.\ Tech.\ J.\ 1975) enables Alice to reliably communicate a message m to an honest Bob by sending an encoding c over a noisy channel ChB while at the same time hiding m from Eve who receives c over another noisy channel ChE. Wiretap coding is clearly impossible when ChB is a degraded version of ChE, in the sense that the output of ChB can be simulated using only the output of ChE. A classic work of Csiszár and Korner (IEEE Trans.\ Inf.\ Theory, 1978) shows that the converse does not hold. This follows from their full characterization of the channel pairs (ChB, ChE) that enable information-theoretic wiretap coding. In this work, we show that in fact the converse does hold when considering computational security; that is, wiretap coding against a computationally bounded Eve is possible if and only if ChB is not a degraded version of ChE. Our construction assumes the existence of virtual black-box (VBB) obfuscation of specific classes of ``evasive'' functions that generalize fuzzy point functions, and can be heuristically instantiated using indistinguishability obfuscation. Finally, our solution has the appealing feature of being universal in the sense that Alice's algorithm depends only on ChB and not on ChE.

Security amplification is a fundamental problem in cryptography. In this work, we study security amplification for functional encryption. We show two main results: - For any constant epsilon in (0,1), we can amplify an epsilon-secure FE scheme for P/poly which is secure against all polynomial sized adversaries to a fully secure FE scheme for P/poly, unconditionally. - For any constant epsilon in (0,1), we can amplify an epsilon-secure FE scheme for P/poly which is secure against subexponential sized adversaries to a subexponentially secure FE scheme for P/poly, unconditionally. Furthermore, both of our amplification results preserve compactness of the underlying FE scheme. Previously, amplification results for FE were only known assuming subexponentially secure LWE. Along the way, we introduce a new form of homomorphic secret sharing called set homomorphic secret sharing that may be of independent interest. Additionally, we introduce a new technique, which allows one to argue security amplification of nested primitives, and prove a general theorem that can be used to analyze the security amplification of parallel repetitions.