Shweta Agrawal

We define and construct Deniable Fully Homomorphic Encryption based on the Learning With Errors (LWE) polynomial hardness assumption. Deniable FHE enables storing encrypted data in the cloud to be processed securely without decryption, maintaining deniability of the encrypted data, as well the prevention of vote-buying in electronic voting schemes where encrypted votes can be tallied without decryption. Our constructions achieve compactness independently of the level of deniability- both the size of the public key and the size of the ciphertexts are bounded by a fixed polynomial, independent of the detection probability achieved by the scheme. This is in contrast to all previous constructions of deniable encryption schemes (even without requiring homomorphisms) which are based on polynomial hardness assumptions, originating with the seminal work of Canetti, Dwork, Naor and Ostrovsky (CRYPTO 1997) in which the ciphertext size grows with the inverse of the detection probability. Canetti et al. argued that this dependence “seems inherent”, but our constructions illustrate this is not the case. We note that the Sahai-Waters (STOC 2014) construction of deniable encryption from indistinguishability obfuscation achieves compactness and can be easily modified to achieve deniable FHE as well, but it requires multiple, stronger sub-exponential hardness assumptions, which are furthermore not post-quantum secure. In contrast, our constructions rely only on the LWE polynomial hardness assumption, as currently required for FHE even without deniability. The running time of our encryption algorithm depends on the inverse of the detection probability, thus the scheme falls short of achieving simultaneously compactness, negligible deniability probability and polynomial encryption time. Yet, we believe that achieving compactness is a fundamental step on the way to achieving all properties simultaneously as has been the historical journey for other primitives such as functional encryption. Our constructions support large message spaces, whereas previous constructions were bit by bit, and can be run in online-offline model of encryption, where the bulk of computation is independent of the message and may be performed in an offline pre-processing phase. This results in an efficient online phase whose running time is independent of the detection probability. At the heart of our constructions is a new way to use bootstrapping to obliviously generate FHE ciphertexts so that it supports faking under coercion.

We introduce the notion of public key encryption with secure key leasing (PKE-SKL). Our notion supports the leasing of decryption keys so that a leased key achieves the decryption functionality but comes with the guarantee that if the quantum decryption key returned by a user passes a validity test, then the user has lost the ability to decrypt. Our notion is similar in spirit to the notion of secure software leasing (SSL) introduced by Ananth and La Placa (Eurocrypt 2021) but captures significantly more general adversarial strategies. (In more detail, our adversary is not restricted to use an honest evaluation algorithm to run pirated software.) Our results can be summarized as follows: 1.Definitions: We introduce the definition of PKE with secure key leasing and formalize a security notion that we call indistinguishability against key leasing attacks (IND-KLA security). We also define a one-wayness notion for PKE-SKL that we call OW-KLA security and show that an OW-KLA secure PKE-SKL scheme can be lifted to an IND-KLA secure one by using the (quantum) Goldreich-Levin lemma.2.Constructing IND-KLA PKE with Secure Key Leasing: We provide a construction of OW-KLA secure PKE-SKL (which implies IND-KLA secure PKE-SKL as discussed above) by leveraging a PKE scheme that satisfies a new security notion that we call consistent or inconsistent security against key leasing attacks (CoIC-KLA security). We then construct a CoIC-KLA secure PKE scheme using 1-key Ciphertext-Policy Functional Encryption (CPFE) that in turn can be based on any IND-CPA secure PKE scheme.3.Identity Based Encryption, Attribute Based Encryption and Functional Encryption with Secure Key Leasing: We provide definitions of secure key leasing in the context of advanced encryption schemes such as identity based encryption (IBE), attribute-based encryption (ABE) and functional encryption (FE). Then we provide constructions by combining the above PKE-SKL with standard IBE, ABE and FE schemes. Notably, our definitions allow the adversary to request distinguishing keys in the security game, namely, keys that distinguish the challenge bit by simply decrypting the challenge ciphertext, as long as it returns them (and they pass the validity test) before it sees the challenge ciphertext. All our constructions satisfy this stronger definition, albeit with the restriction that only a bounded number of such keys is allowed to the adversary in the IBE and ABE (but not FE) security games. Prior to our work, the notion of single decryptor encryption (SDE) has been studied in the context of PKE (Georgiou and Zhandry, Eprint 2020) and FE (Kitigawa and Nishimaki, Asiacrypt 2022) but all their constructions rely on strong assumptions including indistinguishability obfuscation. In contrast, our constructions do not require any additional assumptions, showing that PKE/IBE/ABE/FE can be upgraded to support secure key leasing for free.

The Learning with Errors (LWE) problem has been extensively studied in cryptography due to its strong hardness guarantees, efficiency and expressiveness in constructing advanced cryptographic primitives. In this work, we show that using polar codes in conjunction with LWE-based encryption yields several advantages. To begin, we demonstrate the obvious improvements in the efficiency or rate of information transmission in the LWE-based scheme by leveraging polar coding (with no change in the cryptographic security guarantee). Next, we integrate wiretap polar coding with LWE-based encryption to ensure provable semantic security over a wiretap channel in addition to cryptographic security based on the hardness of LWE. To the best of our knowledge this is the first wiretap code to have cryptographic security guarantees as well. Finally, we study the security of the private key used in LWE-based encryption with wiretap polar coding, and propose a key refresh method using random bits used in wiretap coding. Under a known-plaintext attack, we show that non-vanishing information-theoretic secrecy can be achieved for the key. We believe our approach is at least as interesting as our final results: our work combines cryptography and coding theory in a novel 'non blackbox-way' which may be relevant to other scenarios as well.

Garg et al. (Crypto 2015) initiated the study of cryptographic protocols over noisy channels in the non-interactive setting, namely when only one party speaks. A major question left open by this work is the completeness of finite channels, whose input and output alphabets do not grow with the desired level of security. In this work, we address this question by obtaining the following results: 1.Completeness of Bit-ROT with Inverse Polynomial Error. We show that bit-ROT (i.e., Randomized Oblivious Transfer channel, where each of the two messages is a single bit) can be used to realize general randomized functionalities with inverse polynomial error. Towards this, we provide a construction of string-ROT from bit-ROT with inverse polynomial error.2.No Finite Channel is Complete with Negligible Error. To complement the above, we show that no finite channel can be used to realize string-ROT with negligible error, implying that the inverse polynomial error in the completeness of bit-ROT is inherent. This holds even with semi-honest parties and for computational security, and is contrasted with the (negligible-error) completeness of string-ROT shown by Garg et al.3.Characterization of Finite Channels Enabling Zero-Knowledge Proofs. An important instance of secure computation is zero-knowledge proofs. Noisy channels can potentially be used to realize truly non-interactive zero-knowledge proofs, without trusted common randomness, and with non-transferability and deniability features that cannot be realized in the plain model. Garg et al. obtain such zero-knowledge proofs from the binary erasure channel (BEC) and the binary symmetric channel (BSC). We complete the picture by showing that in fact any non-trivial channel suffices.

We initiate the study of multi-party functional encryption (MPFE) which unifies and abstracts out various notions of functional encryption which support distributed ciphertexts or secret keys, such as multi-input FE, multi-client FE, decentralized multi-client FE, multi-authority FE, dynamic decentralized FE, adhoc multi-input FE and such others. Using our framework, we identify several gaps in the literature and provide some constructions to fill these: 1. Multi-Authority ABE with Inner Product Computation. The recent work of Abdalla et al. (ASIACRYPT’20) constructed a novel “composition” of Attribute Based Encryption (ABE ) and Inner Product Functional Encryption (IPFE ), namely functional encryption schemes that combine the access control functionality of attribute based encryption with the possibility of performing linear operations on the encrypted data. In this work, we extend the access control component to support the much more challenging multi-authority setting, i.e. “lift” the primitive of ABE in their construction to multi-authority ABE for the same class of access control policies (LSSS structures). This yields the first construction of a nontrivial multi-authority FE beyond ABE from simple assumptions on pairings to the best of our knowledge. Our techniques can also be used to generalize the decentralized attribute based encryption scheme of Michalevsky and Joye (ESORICS’18) to support inner product computation on the message. While this scheme only supports inner product predicates which is less general than those supported by the Lewko-Waters (EUROCRYPT’11) construction, it supports policy hiding which the latter does not. Our extension inherits these features and is secure based on the k-linear assumption, in the random oracle model. 2. Function Hiding DDFE. The novel primitive of dynamic decentralized functional encryption (DDFE ) was recently introduced by Chotard et al. (CRYPTO’20), where they also provided the first construction for inner products. However, the primitive of DDFE does not support function hiding, which is a significant limitation for several applications. In this work, we provide a new construction for inner product DDFE which supports function hiding. To achieve our final result, we define and construct the first function hiding multi-client functional encryption (MCFE ) scheme for inner products, which may be of independent interest. 3. Distributed Ciphertext-Policy ABE. We provide a distributed variant of the recent ciphertext-policy attribute based encryption scheme, constructed by Agrawal and Yamada (EUROCRYPT’20). Our construction supports NC1 access policies, and is secure based on “Learning With Errors” and relies on the generic bilinear group model as well as the random oracle model. Our new MPFE abstraction predicts meaningful new variants of functional encryption as useful targets for future work.

In TCC 2013, Boyen suggested the first lattice based construction of attribute based encryption (ABE) for the circuit class NC1. Unfortunately, soon after, a flaw was found in the security proof of the scheme. However, it remained unclear whether the scheme is actually insecure, and if so, whether it can be repaired. Meanwhile, the construction has been heavily cited and continues to be extensively studied due to its technical novelty. In particular, this is the first lattice based ABE which uses linear secret sharing schemes (LSSS) as a crucial tool to enforce access control. In this work, we show that the scheme is in fact insecure,if the scheme is instantiated by the linear secret sharing scheme specified in the paper. To do so, we provide a polynomial-time attack that completely breaks the security of the scheme. We suggest a route to fix the security of the scheme, via the notion of admissible LSSS and instantiate these for the class of DNFs. Subsequent to our work, Datta et al. (Eurocrypt 2021) provided a construction of admissible LSSS for NC1 and resurrected Boyen’s claimed result.

A broadcast, trace and revoke system generalizes broadcast encryption as well as traitor tracing. In such a scheme, an encryptor can specify a list L⊆ N of revoked users so that (i) users in L can no longer decrypt ciphertexts, (ii) ciphertext size is independent of L, (iii) a pirate decryption box supports tracing of compromised users. The “holy grail” of this line of work is a construction which resists unbounded collusions, achieves all parameters (including public and secret key) sizes independent of |L| and |N|, and is based on polynomial hardness assumptions. In this work we make the following contributions: 1.Public Trace Setting: We provide a construction which (i) achieves optimal parameters, (ii) supports embedding identities (from an exponential space) in user secret keys, (iii) relies on polynomial hardness assumptions, namely compact functional encryption (FE ) and a key-policy attribute based encryption (ABE ) with special efficiency properties, and (iv) enjoys adaptive security with respect to the revocation list. The previous best known construction by Nishimaki, Wichs and Zhandry (Eurocrypt 2016) which achieved optimal parameters and embedded identities, relied on indistinguishability obfuscation, which is considered an inherently subexponential assumption and achieved only selective security with respect to the revocation list.2.Secret Trace Setting: We provide the first construction with optimal ciphertext, public and secret key sizes and embedded identities from any assumption outside Obfustopia. In detail, our construction relies on Lockable Obfuscation which can be constructed using LWE (Goyal, Koppula, Waters and Wichs, Zirdelis, Focs 2017) and two ABE schemes: (i) the key-policy scheme with special efficiency properties by Boneh et al. (Eurocrypt 2014) and (ii) a ciphertext-policy ABE for P which was recently constructed by Wee (Eurocrypt 2022) using a new assumption called evasive and tensor LWE. This assumption, introduced to build an ABE, is believed to be much weaker than lattice based assumptions underlying FE or iO – in particular it is required even for lattice based broadcast, without trace. Moreover, by relying on subexponential security of LWE, both our constructions can also support a super-polynomial sized revocation list, so long as it allows efficient representation and membership testing. Ours is the first work to achieve this, to the best of our knowledge.

We construct a functional encryption scheme for circuits which simultaneously achieves and improves upon the security of the current best known, and incomparable, constructions from standard assumptions: reusable garbled circuits by Goldwasser, Kalai, Popa, Vaikuntanathan and Zeldovich (STOC 2013) [GKP+13] and predicate encryption for circuits by Gorbunov, Vaikuntanathan and Wee (CRYPTO 2015) [GVW15]. Our scheme is secure based on the learning with errors (LWE) assumption. Our construction implies: 1.A new construction for reusable garbled circuits that achieves stronger security than the only known prior construction [GKP+13].2.A new construction for bounded collusion functional encryption with substantial efficiency benefits: our public parameters and ciphertext size incur an additive growth of O(Q2), where Q is the number of permissible queries (We note that due to a lower bound [AGVW13], the ciphertext size must necessarily grow with Q). Additionally, the ciphertext of our scheme is succinct, in that it does not depend on the size of the circuit. By contrast, the prior best construction [GKP+13, GVW12] incurred a multiplicative blowup of O(Q4) in both the public parameters and ciphertext size. However, our scheme is secure in a weaker game than [GVW12]. Additionally, we show that existing LWE based predicate encryption schemes [AFV11, GVW15] are completely insecure against a general functional encryption adversary (i.e. in the “strong attribute hiding” game). We demonstrate three different attacks, the strongest of which is applicable even to the inner product predicate encryption scheme [AFV11]. Our attacks are practical and allow the attacker to completely recover x from its encryption Enc(x) within a polynomial number of queries. This illustrates that the barrier between predicate and functional encryption is not just a limitation of proof techniques. We believe these attacks shed significant light on the barriers to achieving full fledged functional encryption from LWE, even for simple functionalities such as inner product zero testing [KSW08, AFV11]. Along the way, we develop a new proof technique that permits the simulator to program public parameters based on keys that will be requested in the future. This technique may be of independent interest.

We provide a single-key functional encryption scheme for Deterministic Finite Automata (DFA). The secret key of our scheme is associated with a DFA M, and a ciphertext is associated with an input x of arbitrary length. The decryptor learns M(x) and nothing else. The ciphertext and key sizes achieved by our scheme are optimal - the size of the public parameters is independent of the size of the machine or data being encrypted, the secret key size depends only on the machine size and the ciphertext size depends only on the input size. Our scheme achieves full functional encryption in the "private index model", namely the entire input x is hidden (as against x being public and a single bit b being hidden). Our single key FE scheme can be compiled with symmetric key encryption as in [12] to yield reusable garbled DFAs for arbitrary size inputs, that achieves machine and input privacy along with reusability under a strong simulation based definition of security. We generalize this to a functional encryption scheme for Turing machines TMFE which has short public parameters that are independent of the size of the machine or the data being encrypted, short function keys, and input-specific decryption time. However, the ciphertext of our construction is large and depends on the worst case running time of the Turing machine (but not its description size). These provide the first FE schemes that support unbounded length inputs, allow succinct public and function keys and rely on LWE. Our construction relies on a new and arguably natural notion of decomposable functional encryption which may be of independent interest.

Inner product functional encryption [1] is a popular primitive which enables inner product computations on encrypted data. In, the ciphertext is associated with a vector, the secret key is associated with a vector and decryption reveals the inner product. Previously, it was known how to achieve adaptive indistinguishability based security for from the assumptions [8]. However, in the stronger simulation based security game, it was only known how to support a restricted adversary that makes all its key requests either before or after seeing the challenge ciphertext, but not both. In more detail, Wee [46] showed that the-based scheme of Agrawal et al. (Crypto 2016) achieves semi-adaptive simulation-based security, where the adversary must make all its key requests after seeing the challenge ciphertext. On the other hand, O’Neill showed that all-secure schemes (which may be based on satisfy based security in the restricted model where the adversary makes all its key requests before seeing the challenge ciphertext. In this work, we resolve the question of-based security for by showing that variants of the constructions by Agrawal et al., based on, Paillier and, satisfy the strongest possible adaptive-based security where the adversary can make an unbounded number of key requests both before and after seeing the (single) challenge ciphertext. This establishes optimal security of the schemes, under all hardness assumptions on which it can (presently) be based.