International Association
for Cryptologic Research

In recent years, functional encryption (FE) has established itself as one of the fundamental primitives in cryptography. The choice of model of computation to represent the functions associated with the functional keys plays a critical role in the complexity of the algorithms of an FE scheme. Historically, the functions are represented as circuits. However, this results in the decryption time of the FE scheme growing proportional to not only the worst case running time of the function but also the size of the input, which in many applications can be quite large. In this work, we present the first construction of a public-key collusion resistant FE scheme, where the functions, associated with the keys, are represented as random access machines (RAMs). We base the security of our construction on the existence of: (i) public-key collusion-resistant FE for circuits and, (ii) public-key doubly-efficient private-information retrieval [Boyle et al., Canetti et al., TCC 2017]. Our scheme enjoys many nice efficiency properties, including input-specific decryption time. We also show how to achieve FE for RAMs in the bounded-key setting with weaker efficiency guarantees from laconic oblivious transfer, which can be based on standard cryptographic assumptions. En route to achieving our result, we present conceptually simpler constructions of succinct garbling for RAMs [Canetti et al., Chen et al., ITCS 2016] from weaker assumptions.

In this work, we revisit the primitive functional encryption (FE) for inner products and show its application to decentralized attribute-based encryption (ABE). Particularly, we derive an FE for inner products that satisfies a stronger notion, and show how to use such an FE to construct decentralized ABE for the class $$\{0,1\}$$-$$\mathsf {LSSS} $$ against bounded collusions in the plain model. We formalize the FE notion and show how to achieve such an FE under the LWE or DDH assumption. Therefore, our resulting decentralized ABE can be constructed under the same standard assumptions, improving the prior construction by Lewko and Waters (Eurocrypt 2011). Finally, we also point out challenges to construct decentralized ABE for general functions by establishing a relation between such an ABE and witness encryption for general NP statements.

Attribute based encryption (ABE) is an advanced encryption system with a built-in mechanism to generate keys associated with functions which in turn provide restricted access to encrypted data. Most of the known candidates of attribute based encryption model the functions as circuits. This results in significant efficiency bottlenecks, especially in the setting where the function associated with the ABE key is represented by a random access machine (RAM) and a database, with the runtime of the RAM program being sublinear in the database size. In this work we study the notion of attribute based encryption for random access machines (RAMs), introduced in the work of Goldwasser, Kalai, Popa, Vaikuntanathan and Zeldovich (Crypto 2013). We present a construction of attribute based encryption for RAMs satisfying sublinear decryption complexity assuming learning with errors; this is the first construction based on standard assumptions. Previously, Goldwasser et al. achieved this result based on non-falsifiable knowledge assumptions. We also consider a dual notion of ABE for RAMs, where the database is in the ciphertext and we show how to achieve this dual notion, albeit with large attribute keys, also based on learning with errors.

We put forth a new notion of distributed public key functional encryption. In such a functional encryption scheme, the secret key for a function f will be split into shares $$\mathsf {sk}_i^f$$ skif. Given a ciphertext $$\mathsf {ct} $$ ct that encrypts a message x, a secret key share $$\mathsf {sk}_i^f$$ skif, one can evaluate and obtain a shared value $$y_i$$ yi. Adding all the shares up can recover the actual value of f(x), while partial shares reveal nothing about the plaintext. More importantly, this new model allows us to establish function privacy which was not possible in the setting of regular public key functional encryption. We formalize such notion and construct such a scheme from any public key functional encryption scheme together with learning with error assumption.We then consider the problem of hosting services in the untrusted cloud. Boneh, Gupta, Mironov, and Sahai (Eurocrypt 2014) first studied such application and gave a construction based on indistinguishability obfuscation. Their construction had the restriction that the number of corrupted clients has to be bounded and known. They left an open problem how to remove such restriction. We resolve this problem by applying our function private (distributed) public key functional encryption to the setting of hosting service in multiple clouds. Furthermore, our construction provides a much simpler and more flexible paradigm which is of both conceptual and practical interests.Along the way, we strengthen and simplify the security notions of the underlying primitives, including function secret sharing.