Secure Computation on Encrypted Data in Multi-User Systems
Robert Schädlich
Abstract
Functional encryption (FE) is an advanced form of traditional public-key encryption that enables complex computations to be performed directly on encrypted data, revealing only the final result of the computation. This thesis presents new constructions for two variants of FE, targeting specific limitations of the standard FE model. The proposed schemes advance the state of the art along (a subset of) the axes expressiveness, security, computational assumptions, and efficiency.First, standard FE requires encrypting the entire input in one shot. In practice, however, it may be desirable to encrypt portions of the data independently, for example at separate locations or by different parties. To address this, we study the multi-client extension of FE, focusing on attribute-based functionalities that provide fine-grained access control to data. Our constructions support a range of policy classes, including \NC0 and conjunction policies, and achieve varying levels of security assuming matrix DDH on pairings, LWE, or public-coin evasive LWE.Second, standard FE relies on a trusted authority to issue secret keys, which is often difficult to implement and undesirable in decentralized environments. To overcome this, we investigate the recently introduced primitive of registered functional encryption (RFE). In RFE, each user independently generates a public/secret key pair and registers their public key along with a function to an auditable key curator. We provide two types of results: constructions for restricted function classes under the standard matrix DDH assumption, and schemes supporting powerful function classes---including both unbounded depth circuits and Turing machines---under a nonstandard lattice-based assumption. Notably, we study RFE for uniform models of computation for the first time in the literature.