Abstract. The notion of multi-input functional encryption (MI-FE) was recently introduced by Goldwasser et al. [EUROCRYPT’14] as a means to non-interactively compute aggregate information on the joint private data of multiple users. A fundamental limitation of their work, however, is that the total number of users (which corresponds to the arity of the functions supported by the MI-FE scheme) must be a priori bounded and fixed at the system setup time. In this work, we overcome this limitation by introducing the notion of unbounded input MI-FE that supports the computation of functions with unbounded arity. We construct such an MI-FE scheme with indis-tinguishability security in the selective model based on the existence of public-coin differing-inputs obfuscation for turing machines and collision-resistant hash functions. Our result enables several new exciting applications, including a new paradigm of on-the-fly secure multiparty computation where new users can join the system dynamically.
Abstract. The notion of multi-input functional encryption (MI-FE) was recently introduced by Goldwasser et al. [EUROCRYPT’14] as a means to non-interactively compute aggregate information on the joint private data of multiple users. A fundamental limitation of their work, however, is that the total number of users (which corresponds to the arity of the functions supported by the MI-FE scheme) must be a priori bounded and fixed at the system setup time. In this work, we overcome this limitation by introducing the notion of unbounded input MI-FE that supports the computation of functions with unbounded arity. We construct such an MI-FE scheme with indis-tinguishability security in the selective model based on the existence of public-coin differing-inputs obfuscation for turing machines and collision-resistant hash functions. Our result enables several new exciting applications, including a new paradigm of on-the-fly secure multiparty computation where new users can join the system dynamically.
The arrival of indistinguishability obfuscation (iO) has transformed the cryptographic land-scape by enabling several security goals that were previously beyond our reach. Consequently, one of the pressing goals currently is to construct iO from well-studied standard cryptographic assumptions. In this work, we make progress in this direction by presenting a reduction from iO to a natural form of public-key functional encryption (FE). Specifically, we construct iO for general functions from any single-key FE scheme for NC1 that achieves selective, indistinguishability security against sub-exponential time adversaries. Further, the FE scheme should be compact, namely, the running time of the encryption algorithm must only be a polynomial in the security parameter and the input message length (and not in the function description size or its output length). We achieve this result by developing a novel arity amplification technique to transform FE for single-ary functions into FE for multi-ary functions (aka multi-input FE). Instantiating our approach with known, non-compact FE schemes, we obtain the first constructions of multi-input FE for constant-ary functions based on standard assumptions. Finally, as a result of independent interest, we construct a compact FE scheme from ran-domized encodings for Turing machines and learning with errors assumption.
Functional encryption (FE) is a powerful primitive enabling fine-grained access to encrypted data. In an FE scheme, secret keys (“tokens”) correspond to functions; a user in possession of a ciphertext ct = Enc(x) and a token TKf for the function f can compute f(x) but learn nothing else about x. An active area of research over the past few years has focused on the development of ever more expressive FE schemes. In this work we introduce the notion of multi-input functional encryption. Here, informally, a user in possession of a token TKf for an n-ary function f and multiple ciphertexts ct1 = Enc(x1), . . . , ctn = Enc(xn) can compute f(x1, . . . , xn) but nothing else about the {xi}. Besides introducing the notion, we explore the feasibility of multi-input FE in the public-key and symmetric-key settings, with respect to both indistinguishability-based and simulation-based definitions of security. ∗ACS. Email: sgordon@appcomsci.com. †Department of Computer Science, University of Maryland. Email: jkatz@cs.umd.edu. This research was sponsored by NSF award #1223623 and by the US Army Research Laboratory and the UK Ministry of Defence under Agreement Number W911NF-06-3-0001. ‡Department of Computer Science, University of Maryland. Email: fenghao@cs.umd.edu. §Department of Computer Science, University of Maryland. Email: elaine@cs.umd.edu. This work is partially supported by NSF award CNS-1314857 and a Google Research Award. ¶Department of Computer Science, Virginia Commonwealth University. Email: hszhou@vcu.edu. This work is partially supported by an NSF CI postdoctoral fellowship, and was mostly done while at the University of Maryland.
We construct a general-purpose multi-input functional encryption scheme in the private-key setting. Namely, we construct a scheme where a functional key corresponding to a function f enables a user holding encryptions of x1; : : : ; xt to compute f(x1; : : : ; xt) but nothing else. This is achieved starting from any general-purpose private-key single-input scheme (without any additional assumptions), and is proven to be adaptively secure for any constant number of inputs t. Moreover, it can be extended to a super-constant number of inputs assuming that the underlying single-input scheme is sub-exponentially secure. Instantiating our construction with existing single-input schemes, we obtain multi-input schemes that are based on a variety of assumptions (such as indistinguishability obfuscation, multilinear maps, learning with errors, and even one-way functions), offering various trade-offs between security and efficiency. Previous and concurrent constructions of multi-input functional encryption schemes either rely on stronger assumptions and provided weaker security guarantees (Goldwasser et al. [EU-ROCRYPT '14], and Ananth and Jain [CRYPTO '15]), or relied on multilinear maps and could
Functional encryption (FE) is a versatile paradigm that enables fine-grained access control over encrypted data. Despite its potential, achieving the gold standard of simulation-based security for FE is impossible in full generality. Known impossibility results demonstrate that simulation security cannot be attained if an adversary in the security experiment is permitted either an unbounded number of functional key queries or an unbounded number of challenge ciphertexts. In this work, we circumvent these fundamental barriers by considering two distinct memory-restricted settings: the Bounded Quantum Storage Model and the Bounded Classical Storage Model. In these settings, the plain model impossibility results no longer apply, allowing us to obtain new positive results. Specifically, we construct two adaptively simulation-secure FE schemes in the Bounded Quantum Storage Model: 1) Many functional key scheme: A construction supporting many functional key queries and a single challenge ciphertext, assuming only the existence of one-way functions. 2) Many ciphertext scheme: An information-theoretic secure construction supporting a single non-adaptive functional key, many challenge ciphertexts, and many adaptive functional key queries. Furthermore, we demonstrate that both schemes can be ported to the Bounded Classical Storage Model, assuming the existence of disappearing grey-box obfuscation.
We introduce and study the notion of non-interactive secure multiparty computation (NIMPC). An NIMPC protocol for a function f(x1,..., xn) is specified by a joint probability distribution R = (R1,..., Rn) and local encoding functions Enci(xi, Ri), 1 ≤ i ≤ n. Given correlated randomness (R1,..., Rn) ∈R R, each party Pi, using its input xi and its randomness Ri, computes the message mi = Enci(xi, Ri). The messagesm1,...,mn can be used to decode f(x1,..., xn). For a set T ⊆ [n], the protocol is said to be T-robust if revealing the messages (Enci(xi, Ri))i 6∈T together with the random-ness (Ri)i∈T gives the same information about (xi)i 6∈T as an oracle access to the function f restricted to these input values. Namely, a coalition T can learn no more than the restriction of f fixing the inputs of uncorrupted parties, which, in this non-interactive setting, one cannot hope to hide. For 0 ≤ t ≤ n, the protocol is t-robust if it is T-robust for every T of size at most t and it is fully robust if it is n-robust. A 0-robust NIMPC protocol for f coincides with a protocol in the private simultaneous messages model of Feige et al. (STOC 1994). In the setting of computational (indistinguishability-based) security, fully robust NIMPC is implied by multi-input functional encryption, a notion that was recently introduced by Goldwasser et al. (Euro-
In a functional encryption (FE) scheme, a user that holds a ciphertext and a function key can learn the result of applying the function to the plaintext message. Security requires that the user does not learn anything beyond the function evaluation. We extend this notion to the quantum setting by providing definitions and a construction for a quantum functional encryption (QFE) scheme which allows for the evaluation of polynomialy-sized circuits on arbitrary quantum messages. Our construction is built upon quantum garbled circuits [BY22]. We also investigate the relationship of QFE to the seemingly unrelated notion of unclonable encryption (UE) and find that any QFE scheme universally achieves the property of unclonable functional encryption (UFE). In particular we assume the existence of an unclonable encryption scheme with quantum decryption keys which was recently constructed by [AKY24]. Our UFE guarantees that two parties cannot simultaneously recover the correct function outputs using two independently sampled function secret keys. As an application we give the first construction for public-key UE with variable decryption keys. Lastly, we establish a connection between quantum indistinguishability obfuscation (qiO) and quantum functional encryption (QFE); Showing that any multi-input indistinguishability-secure quantum functional encryption scheme unconditionally implies the existence of qiO.