International Association
for Cryptologic Research

Time-lock puzzles (TLP) are a cryptographic tool that allow one to encrypt a message into the future, for a predetermined amount of time T . At present, we have only two constructions with provable security: One based on the repeated squaring assumption and the other based on indistinguishability obfuscation (iO). Basing TLP on any other assumption is a long-standing question, further motivated by the fact that know constructions are broken by quantum algorithms. In this work, we propose a new approach to construct time-lock puzzles based on lattices, and therefore with plausible post-quantum security. We obtain the following main results: • In the preprocessing model, where a one-time public-coin preprocessing is allowed, we obtain a time-lock puzzle with encryption time log(T ). • In the plain model, where the encrypter does all the computation, we obtain a time-lock puzzle with encryption time √T . Both constructions assume the existence of any sequential function f , and the hardness of the circular small-secret learning with errors (LWE) problem. At the heart of our results is a new construction of succinct randomized encodings (SRE) for T-folded repeated circuits, where the complexity of the encoding is √T . This is the first construction of SRE where the overall complexity of the encoding algorithm is sublinear in the runtime T , and which is not based on iO. Using our SRE we directly obtain the first non- interactive RAM delegation scheme with sublinear complexity (in the number of steps T ), again without iO. Finally, we also propose a new heuristic construction of SREs, and consequently of TLPs, with fully-efficient encoding complexity log(T ). Our scheme is inspired by iO techniques, but carefully sidesteps the regime of zeroizing attacks that plague lattice-based iO candidates.

In the average-case k-SUM problem, given r integers chosen uniformly at random from {0,\dots,M-1}, the objective is to find a ``solution'' set of k numbers that sum to 0 modulo M. In the dense regime of M <= r^k, where solutions exist with high probability, the complexity of these problems is well understood. Much less is known in the sparse regime of M >> r^k, where solutions are unlikely to exist. Motivated by applications to cryptography, we initiate the study of the sparse regime for k-SUM and its variant k-XOR, especially their planted versions, where a random solution is planted in a randomly generated instance and has to be recovered. We provide evidence for the hardness of these problems and show applications to constructing public-key encryption schemes. Our contributions are summarized below. Complexity: We study the complexity of these problems in the sparse regime and show: - Conditional Lower Bounds: Assuming established conjectures about the hardness of average-case (non-planted) k-SUM/k-XOR when M = r^k, we provide non-trivial lower bounds on the running time of algorithms for planted k-SUM when r^k <= M <= r^{2k}. - Hardness Amplification: We show that for any M \geq r^k, if an algorithm running in time T solves planted k-SUM/k-XOR with success probability Omega(1/polylog(r)), then there is an algorithm running in time Otilde(T) that solves it with probability (1-o(1)). This enables us to use even relatively mild hardness of k-SUM/k-XOR in our cryptographic constructions. Our primary technical contribution is the proof of this result, which departs significantly from existing approaches to hardness amplification. - New Reductions and Algorithms: We provide reductions for k-SUM/k-XOR from search to decision, as well as worst-case and average-case reductions to the Subset Sum problem from k-SUM. Additionally, we present a new algorithm for average-case k-XOR that is faster than known worst-case algorithms at low densities. Applications: We show that by additionally assuming mild hardness of k-XOR, we can construct Public Key Encryption (PKE) from a weaker variant of the Learning Parity with Noise (LPN) problem than was known before. In particular, such LPN hardness does not appear to imply PKE on its own -- this suggests that k-XOR/k-SUM can be used to bridge ``minicrypt'' and ``cryptomania'' in some cases. We are optimistic that this technique will find other applications in cryptography

We provide the first attribute based encryption (ABE) scheme for Turing machines supporting unbounded collusions from lattice assumptions. In more detail, the encryptor encodes an attribute x together with a bound t on the machine running time and a message m into the ciphertext, the key generator embeds a Turing machine M into the secret key and decryption returns m if and only if M (x) = 1. Crucially, the input x and machine M can be of unbounded size, the time bound t can be chosen dynamically for each input and decryption runs in input specific time. Previously the best known ABE for uniform computation supported only non-deterministic log space Turing machines (NL from pairings (Lin and Luo, Eurocrypt 2020). In the post-quantum regime, the state of the art supports non-deterministic finite automata from LWE in the symmetric key setting (Agrawal, Maitra and Yamada, Crypto 2019). In more detail, our results are: 1. We construct the first ABE for NL from the LWE and evasive LWE assumptions. This yields the first (conjectured) post-quantum ABE for NL. 2. Relying on new and arguably natural assumptions which we call path LWE, evasive path LWE and circular tensor LWE, in addition to standard LWE, we construct ABE for all Turing machines. Towards our ABE for Turing machines, we obtain the first CP-ABE for circuits of unbounded depth and size from the same assumptions – this may be of independent interest. At a high level, our path LWE assumption states that the joint distribution of specially constructed FHE and ABE encodings are pseudorandom. The evasive path LWE assumption incorporates path LWE into the celebrated evasive LWE assumption (Wee, Eurocrypt 2022 and Tsabary, Crypto 2022), while the circular tensor LWE assumption incorporates circularity into the tensor LWE (Wee, Eurocrypt 2022) assumption. We believe these assumptions provide an important new tool for encrypted computation and are likely to find other applications.

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, so 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 be 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.

A {\it broadcast, trace and revoke} system generalizes broadcast encryption as well as traitor tracing. In such a scheme, an encryptor can specify a list $L \subseteq 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. {\it 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 (${\sf FE}$) and a key-policy attribute based encryption (${\sf 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. {\it 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 ${\sf LWE}$ (Goyal, Koppula, Waters and Wichs, Zirdelis, Focs 2017) and two ${\sf ABE}$ schemes: (i) the key-policy scheme with special efficiency properties by Boneh et al. (Eurocrypt 2014) and (ii) a ciphertext-policy ${\sf ABE}$ for ${\sf P}$ which was recently constructed by Wee (Eurocrypt 2022) using a new assumption called {\it evasive and tensor} ${\sf LWE}$. This assumption, introduced to build an ${\sf ABE}$, is believed to be much weaker than lattice based assumptions underlying ${\sf FE}$ or ${\sf iO}$ -- in particular it is required even for lattice based broadcast, without trace. Moreover, by relying on subexponential security of ${\sf LWE}$, both our constructions can also support a {\it 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.

Recently, Abdalla, Gong and Wee (Crypto 2020) provided the first functional encryption scheme for attribute-weighted sums (AWS), where encryption takes as input $N$ (unbounded) attribute-value pairs $\Set{x_i, z_i}_{i \in [N]}$ where $x_i$ is public and $z_i$ is private, the secret key is associated with an arithmetic branching programs $f$, and decryption returns the weighted sum ${\sum}_{{i \in [N]}} f(x_i)^\top z_i$, leaking no additional information about the $z_i$'s. We extend FE for AWS to the significantly more challenging multi-party setting and provide the first construction for {\it attribute-based} multi-input FE (MIFE) supporting AWS. For $i \in [n]$, encryptor $i$ can choose an attribute $y_i$ together with AWS input $\Set{x_{i,j}, z_{i,j}}$ where $j \in [N_i]$ and $N_i$ is unbounded, the key generator can choose an access control policy $g_i$ along with its AWS function $h_i$ for each $i \in [n]$, and the decryptor can compute $$\sum_{i \in [n]} \sum_{j \in [N_{i}]}h_{i}(x_{i,j})^\top z_{i,j} \text{ iff } g_{i}(y_{i}) =0 \text{ for all } i \in [n]$$ Previously, the only known attribute based MIFE was for the inner product functionality (Abdalla \etal~Asiacrypt 2020), where additionally, $y_i$ had to be fixed during setup and must remain the same for all ciphertexts in a given slot. Our attribute based MIFE implies the notion of multi-input attribute based encryption (MIABE) recently studied by Agrawal, Yadav and Yamada (Crypto 2022) and Francati, Friolo, Malavolta and Venturi (Eurocrypt 2023), for a conjunction of predicates represented as arithmetic branching programs (ABP). Along the way, we also provide the first constructions of multi-client FE (MCFE) and dynamic decentralized FE (DDFE) for the AWS functionality. Previously, the best known MCFE and DDFE schemes were for inner products (Chotard \etal~ePrint 2018, Abdalla, Benhamouda and Gay, Asiacrypt 2019, and Chotard \etal~Crypto 2020).

Constructing advanced cryptographic primitives such as obfuscation or broadcast encryption from standard hardness assumptions in the post quantum regime is an important area of research, which has met with limited success despite significant effort. It is therefore extremely important to find new, simple to state assumptions in this regime which can be used to fill this gap. An important step was taken recently by Wee (Eurocrypt '22) who identified two new assumptions from lattices, namely evasive LWE and tensor LWE, and used these to construct broadcast encryption and ciphertext policy attribute based encryption for P with optimal parameters. Independently, Tsabary formulated a similar assumption and used it to construct witness encryption (Crypto '22). Following Wee's work, Vaikuntanathan, Wee and Wichs independently provided a construction of witness encryption (Asiacrypt '22). In this work, we advance this line of research by providing the first construction of multi-input attribute based encryption (miABE) for the function class NC_1 for any constant arity from evasive LWE. Our construction can be extended to support the function class P} by using evasive and a suitable strengthening of tensor LWE. In more detail, our construction supports k encryptors, for any constant k, where each encryptor uses the master secret key msk to encode its input (x_i, m_i), the key generator computes a key sk_f for a function f \in NC_1 and the decryptor can recover (m_1,...,m_k) if and only if f(x_1,...,x_k)=1. The only known construction for miABE for NC_1 by Agrawal, Yadav and Yamada (Crypto '22) supports arity 2 and relies on pairings in the generic group model (or with a non-standard knowledge assumption) in addition to LWE. Furthermore, it is completely unclear how to go beyond arity 2 using this approach due to the reliance on pairings. Using a compiler from Agrawal, Yadav and Yamada (Crypto '22), our miABE can be upgraded to multi-input predicate encryption for the same arity and function class. Thus, we obtain the first constructions for constant-arity predicate and attribute based encryption for a generalized class such as NC_1 or P from simple assumptions that may be conjectured post-quantum secure. Along the way, we show that the tensor LWE assumption can be reduced to standard LWE in an important special case which was not known before. This adds confidence to the plausibility of the assumption and may be of wider interest.

We introduce a new cryptographic primitive, called Completely Anonymous Signed Encryption(CASE). CASE is a public-key authenticated encryption primitive, that offers anonymity for senders as well as receivers. A “case-packet” should appear, without a (decryption) key for opening it, to be a blackbox that reveals no information at all about its contents. To decase a case-packet fully – so that the message is retrieved and authenticated – a verification key is also required. Defining security for this primitive is subtle. We present a relatively simple Chosen Objects Attack (COA) security definition. Validating this definition, we show that it implies a comprehensive indistinguishability-preservation definition in the real-ideal paradigm. To obtain the latter definition, we extend the Cryptographic Agents framework to allow maliciously created objects. We also provide a novel and practical construction for COA-secure CASE under standard assumptions in public-key cryptography, and in the standard model. We believe CASE can be a staple in future cryptographic libraries, thanks to its robust security guarantees and efficient instantiations based on standard assumptions.

Motivated by several new and natural applications, we initiate the study of multi-input predicate encryption (${\sf miPE}$) and further develop multi-input attribute based encryption (${\sf miABE}$). Our contributions are: 1. {\it Formalizing Security:} We provide definitions for ${\sf miABE}$ and ${\sf miPE}$ in the {symmetric} key setting and formalize security in the standard {\it indistinguishability} (IND) paradigm, against {\it unbounded} collusions. 2. {\it Two-input ${\sf ABE}$ for ${\sf NC}_1$ from ${\sf LWE}$ and Pairings:} We provide the first constructions for two-input {\it key-policy} ${\sf ABE}$ for ${\sf NC}_1$ from ${\sf LWE}$ and pairings. Our construction leverages a surprising connection between techniques recently developed by Agrawal and Yamada (Eurocrypt, 2020) in the context of succinct {\it single}-input {\it ciphertext-policy} ${\sf ABE}$, to the seemingly unrelated problem of {\it two}-input {\it key-policy} ${\sf ABE}$. Similarly to Agrawal-Yamada, our construction is proven secure in the bilinear generic group model. By leveraging inner product functional encryption and using (a variant of) the KOALA knowledge assumption, we obtain a construction in the standard model analogously to Agrawal, Wichs and Yamada (TCC, 2020). 3. {\it Heuristic two-input ${\sf ABE}$ for ${\sf P}$ from Lattices:} We show that techniques developed for succinct single-input ciphertext-policy ${\sf ABE}$ by Brakerski and Vaikuntanathan (ITCS 2022) can also be seen from the lens of ${\sf miABE}$ and obtain the first two-input key-policy ${\sf ABE}$ from lattices for ${\sf P}$. 4. {\it Heuristic three-input ${\sf ABE}$ and ${\sf PE}$ for ${\sf NC}_1$ from Pairings and Lattices:} We obtain the first {\it three}-input ${\sf ABE}$ for ${\sf NC}_1$ by harnessing the powers of both the Agrawal-Yamada and the Brakerski-Vaikuntanathan constructions. 5. {\it Multi-input ${\sf ABE}$ to multi-input ${\sf PE}$ via Lockable Obfuscation:} We provide a generic compiler that lifts multi-input ${\sf ABE}$ to multi-input $\PE$ by relying on the hiding properties of Lockable Obfuscation (${\sf LO}$) by Wichs-Zirdelis and Goyal-Koppula-Waters (FOCS 2018), which can be based on ${\sf LWE}$. Our compiler generalises such a compiler for single-input setting to the much more challenging setting of multiple inputs. By instantiating our compiler with our new two and three-input ${\sf ABE}$ schemes, we obtain the first constructions of two and three-input ${\sf PE}$ schemes. Our constructions of multi-input ${\sf ABE}$ provide the first improvement to the compression factor of {\it non-trivially exponentially efficient Witness Encryption} defined by Brakerski et al. (SCN 2018) without relying on compact functional encryption or indistinguishability obfuscation. We believe that the unexpected connection between succinct single-input ciphertext-policy ${\sf ABE}$ and multi-input key-policy ${\sf ABE}$ may lead to a new pathway for witness encryption. We remark that our constructions provide the first candidates for a nontrivial class of ${\sf miFE}$ without needing ${\sf LPN}$ or low depth ${\sf PRG}$. \keywords{Multi-input \and Attribute Based Encryption \and Predicate Encryption.}

Multi-input functional encryption, MIFE, is a powerful generalization of functional encryption that allows computation on encrypted data coming from multiple different data sources. In a recent work, Agrawal, Goyal, and Tomida (CRYPTO 2021) constructed MIFE for the class of quadratic functions. This was the first MIFE construction from bilinear maps that went beyond inner product computation. We advance the state-of-the-art in MIFE, and propose new constructions with stronger security and broader functionality. • Stronger Security: In the typical formulation of MIFE security, an attacker is allowed to either corrupt all or none of the users who can encrypt the data. In this work, we study MIFE security in a stronger and more natural model where we allow an attacker to corrupt any subset of the users, instead of only permitting all-or-nothing corruption. We formalize the model by providing each user a unique encryption key, and letting the attacker corrupt all non-trivial subsets of the encryption keys, while still maintaining the MIFE security for ciphertexts generated using honest keys. We construct a secure MIFE system for quadratic functions in this fine-grained corruption model from bilinear maps. Our construction departs significantly from the existing MIFE schemes as we need to tackle a more general class of attackers. • Broader Functionality: The notion of multi-client functional encryption, MCFE, is a useful extension of MIFE. In MCFE, each encryptor can additionally tag each ciphertext with appropriate metadata such that ciphertexts with only matching metadata can be decrypted together. In more detail, each ciphertext is now annotated with a unique label such that ciphertexts encrypted for different slots can now only be combined together during decryption as long as the associated labels are an exact match for all individual ciphertexts. In this work, we upgrade our MIFE scheme to also support ciphertext labelling. While the functionality of our scheme matches that of MCFE for quadratic functions, our security guarantee falls short of the general corruption model studied for MCFE. In our model, all encryptors share a secret key, therefore this yields a secret-key version of quadratic MCFE, which we denote by SK-MCFE. We leave the problem of proving security in the general corruption model as an important open problem.

The recent work of Agrawal et al., [Crypto '21] and Goyal et al. [Eurocrypt '22] concurrently introduced the notion of dynamic bounded collusion security for functional encryption (FE) and showed a construction satisfying the notion from identity based encryption (IBE). Agrawal et al., [Crypto '21] further extended it to FE for Turing machines in non-adaptive simulation setting from the sub-exponential learining with errors assumption (LWE). Concurrently, the work of Goyal et al. [Asiacrypt '21] constructed attribute based encryption (ABE) for Turing machines achieving adaptive indistinguishability based security against bounded (static) collusions from IBE, in the random oracle model. In this work, we significantly improve the state of art for dynamic bounded collusion FE and ABE for Turing machines by achieving \emph{adaptive} simulation style security from a broad class of assumptions, in the standard model. In more detail, we obtain the following results: \begin{enumerate} \item We construct an adaptively secure (AD-SIM) FE for Turing machines, supporting dynamic bounded collusion, from sub-exponential LWE. This improves the result of Agrawal et al. which achieved only non-adaptive (NA-SIM) security in the dynamic bounded collusion model. \item Towards achieving the above goal, we construct a \emph{ciphertext policy} FE scheme (CPFE) for circuits of \emph{unbounded} size and depth, which achieves AD-SIM security in the dynamic bounded collusion model from IBE and \emph{laconic oblivious transfer} (LOT). Both IBE and LOT can be instantiated from a large number of mild assumptions such as the computational Diffie-Hellman assumption, the factoring assumption, and polynomial LWE. This improves the construction of Agrawal et al. which could only achieve NA-SIM security for CPFE supporting circuits of unbounded depth from IBE. \item We construct an AD-SIM secure FE for Turing machines, supporting dynamic bounded collusions, from LOT, ABE for NC1 (or NC) and private information retrieval (PIR) schemes which satisfy certain properties. This significantly expands the class of assumptions on which AD-SIM secure FE for Turing machines can be based. In particular, it leads to new constructions of FE for Turing machines including one based on polynomial LWE and one based on the combination of the bilinear decisional Diffie-Hellman assumption and the decisional Diffie-Hellman assumption on some specific groups. In contrast the only prior construction by Agrawal et al. achieved only NA-SIM security and relied on \emph{sub-exponential} LWE. To achieve the above result, we define the notion of CPFE for read only RAM programs and succinct FE for LOT, which may be of independent interest. \item We also construct an \emph{ABE} scheme for Turing machines which achieves AD-IND security in the \emph{standard model} supporting dynamic bounded collusions. Our scheme is based on IBE and LOT. Previously, the only known candidate that achieved AD-IND security from IBE by Goyal et al. relied on the random oracle model. \end{enumerate}

We construct the first multi-input functional encryption (MIFE) scheme for quadratic functions from pairings. Our construction supports polynomial number of users, where user $i$, for $i \in [n]$, encrypts input $\bfx_i \in \mbZ^m$ to obtain ciphertext $\ct_i$, the key generator provides a key $\sk_\bfc$ for vector $\bfc \in \mbZ^{({mn})^2}$ and decryption, given $\ct_1,\ldots,\ct_n$ and $\sk_\bfc$, recovers $\ip{\bfc}{\bfx \otimes \bfx}$ and nothing else. We achieve indistinguishability-based (selective) security against unbounded collusions under the standard bilateral matrix Diffie-Hellman assumption. All previous MIFE schemes either support only inner products (linear functions) or rely on strong cryptographic assumptions such as indistinguishability obfuscation or multi-linear maps.

We define and construct {\it 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 {\it 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 faking 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 faking probability. Canetti {\it et al.} argued that this dependence ``seems inherent'', but our constructions illustrate this is not the case. We note that the Sahai-Waters (STOC13) 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 faking probability, thus the scheme falls short of achieving simultaneously compactness, negligible deniability probability {\it 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. Interestingly, we note that 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. The running time of the online phase, is independent of the faking probability, whereas the offline encryption run-time grows with the inverse of the faking 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.

The classic work of Gorbunov, Vaikuntanathan and Wee (CRYPTO 2012) and follow-ups provided constructions of bounded collusion Functional Encryption (FE) for circuits from mild assumptions. In this work, we improve the state of affairs for bounded collusion FE in several ways: 1. {\it New Security Notion.} We introduce the notion of {\it dynamic} bounded collusion FE, where the declaration of collusion bound is delayed to the time of encryption. This enables the encryptor to dynamically choose the collusion bound for different ciphertexts depending on their individual level of sensitivity. Hence, the ciphertext size grows linearly with its own collusion bound and the public key size is independent of collusion bound. In contrast, all prior constructions have public key and ciphertext size that grow at least linearly with a fixed bound $Q$. 2. {\it CPFE for circuits with Dynamic Bounded Collusion.} We provide the first CPFE schemes for circuits enjoying dynamic bounded collusion security. By assuming identity based encryption (IBE), we construct CPFE for circuits of {\it unbounded} size satisfying {\it non-adaptive} simulation based security. By strengthening the underlying assumption to IBE with receiver selective opening security, we obtain CPFE for circuits of {\it bounded} size enjoying {\it adaptive} simulation based security. Moreover, we show that IBE is a necessary assumption for these primitives. Furthermore, by relying on the Learning With Errors (LWE) assumption, we obtain the first {\it succinct} CPFE for circuits, i.e. supporting circuits with unbounded size, but fixed output length and depth. This scheme achieves {\it adaptive} simulation based security. 3. {\it KPFE for circuits with dynamic bounded collusion.} We provide the first KPFE for circuits of unbounded size, but bounded depth and output length satisfying dynamic bounded collusion security from LWE. Our construction achieves {\it adaptive} simulation security improving security of \cite{GKPVZ13a}. 4. {\it KP and CP FE for TM/NL with dynamic bounded collusion.} We provide the first KPFE and CPFE constructions of bounded collusion functional encryption for Turing machines in the public key setting from LWE. Our constructions achieve non-adaptive simulation based security. Both the input and the machine in our construction can be of {\it unbounded} polynomial length. We provide a variant of the above scheme that satisfies {\it adaptive} security, but at the cost of supporting a smaller class of computation, namely Nondeterministic Logarithmic-space (NL). Since NL contains Nondeterministic Finite Automata (NFA), this result subsumes {\it all} prior work of bounded collusion FE for uniform models from standard assumptions \cite{AMY19,AS17}.

Can a sender encode a pair of messages (m_0,m_1) jointly, and send their encoding over (say) a binary erasure channel, so that the receiver can decode exactly one of the two messages and the sender does not know which one? Garg et al. (Crypto 2015) showed that this is information-theoretically impossible. We show how to circumvent this impossibility by assuming that the receiver is computationally bounded, settling for an inverse-polynomial security error (which is provably necessary), and relying on ideal obfuscation. Our solution creates a ``computational anti-correlation'' between the events of receiving m_0 and receiving m_1 by exploiting the anti-concentration of the binomial distribution. The ideal obfuscation primitive in our construction can either be directly realized using (stateless) tamper-proof hardware, yielding an unconditional result, or heuristically instantiated using existing indistinguishability obfuscation schemes. We put forward a new notion of obfuscation that suffices to securely instantiate our construction. As a corollary, we get similar feasibility results for general secure computation of sender-receiver functionalities by leveraging the completeness of the above ``random oblivious transfer'' functionality.

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.

Boneh, Waters and Zhandry (CRYPTO 2014) used multilinear maps to provide a solution to the long-standing problem of public-key broadcast encryption (BE) where all parameters in the system are small. In this work, we improve their result by providing a solution that uses only {\it bilinear} maps and Learning With Errors (LWE). Our scheme is fully collusion-resistant against any number of colluders, and can be generalized to an identity-based broadcast system with short parameters. Thus, we reclaim the problem of optimal broadcast encryption from the land of ``Obfustopia''. Our main technical contribution is a ciphertext policy attribute based encryption (CP-ABE) scheme which achieves special efficiency properties -- its ciphertext size, secret key size, and public key size are all independent of the size of the circuits supported by the scheme. We show that this special CP-ABE scheme implies BE with optimal parameters; but it may also be of independent interest. Our constructions rely on a novel interplay of bilinear maps and LWE, and are proven secure in the generic group model.

Candidates of Indistinguishability Obfuscation (iO) can be categorized as ``direct'' or ``bootstrapping based''. Direct constructions rely on high degree multilinear maps [GGH13,GGHRSW13] and provide heuristic guarantees, while bootstrapping based constructions [LV16,Lin17,LT17,AJLMS19,Agr19,JLMS19] rely, in the best case, on bilinear maps as well as new variants of the Learning With Errors (LWE) assumption and pseudorandom generators. Recent times have seen exciting progress in the construction of indistinguishability obfuscation (iO) from bilinear maps (along with other assumptions) [LT17,AJLMS19,JLMS19,Agr19]. As a notable exception, a recent work by Agrawal [Agr19] provided a construction for iO without using any maps. This work identified a new primitive, called Noisy Linear Functional Encryption (NLinFE) that provably suffices for iO and gave a direct construction of NLinFE from new assumptions on lattices. While a preliminary cryptanalysis for the new assumptions was provided in the original work, the author admitted the necessity of performing significantly more cryptanalysis before faith could be placed in the security of the scheme. Moreover, the author did not suggest concrete parameters for the construction. In this work, we fill this gap by undertaking the task of thorough cryptanalytic study of NLinFE. We design two attacks that let the adversary completely break the security of the scheme. Our attacks are completely new and unrelated to attacks that were hitherto used to break other candidates of iO. To achieve this, we develop new cryptanalytic techniques which (we hope) will inform future designs of the primitive of NLinFE. From the knowledge gained by our cryptanalytic study, we suggest modifications to the scheme. We provide a new scheme which overcomes the vulnerabilities identified before. We also provide a thorough analysis of all the security aspects of this scheme and argue why plausible attacks do not work. We additionally provide concrete parameters with which the scheme may be instantiated. We believe the security of NLinFE stands on significantly firmer footing as a result of this work.

Inner product functional encryption ( $${mathsf {IPFE}}$$ ) [ 1 ] is a popular primitive which enables inner product computations on encrypted data. In $${mathsf {IPFE}}$$ , the ciphertext is associated with a vector $$varvec{x}$$ , the secret key is associated with a vector $$varvec{y}$$ and decryption reveals the inner product $$langle varvec{x},varvec{y} angle $$ . Previously, it was known how to achieve adaptive indistinguishability ( $$mathsf {IND}$$ ) based security for $${mathsf {IPFE}}$$ from the $$mathsf {DDH}$$ , $$mathsf {DCR}$$ and $$mathsf {LWE}$$ assumptions [ 8 ]. However, in the stronger simulation ( $$mathsf {SIM}$$ ) 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 $$mathsf {DDH}$$ -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 $$mathsf {IND}$$ -secure $${mathsf {IPFE}}$$ schemes (which may be based on $$mathsf {DDH}$$ , $$mathsf {DCR}$$ and $$mathsf {LWE}$$ ) satisfy $$mathsf {SIM}$$ 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 $$mathsf {SIM}$$ -based security for $${mathsf {IPFE}}$$ by showing that variants of the $${mathsf {IPFE}}$$ constructions by Agrawal et al. , based on $$mathsf {DDH}$$ , Paillier and $$mathsf {LWE}$$ , satisfy the strongest possible adaptive $$mathsf {SIM}$$ -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 $${mathsf {IPFE}}$$ schemes, under all hardness assumptions on which it can (presently) be based.

The celebrated work of Gorbunov, Vaikuntanathan and Wee [GVW13] provided the first key policy attribute based encryption scheme (ABE) for circuits from the Learning With Errors (LWE) assumption. However, the arguably more natural ciphertext policy variant has remained elusive, and is a central primitive not yet known from LWE. In this work, we construct the first symmetric key ciphertext policy attribute based encryption scheme (CP-ABE) for all polynomial sized circuits from the learning with errors (LWE) assumption. In more detail, the ciphertext for a message m is labelled with an access control policy f, secret keys are labelled with public attributes x from the domain of f and decryption succeeds to yield the hidden message m if and only if f(x) = 1. The size of our public and secret key do not depend on the size of the circuits supported by the scheme – this enables our construction to support circuits of unbounded size (but bounded depth). Our construction is secure against collusions of unbounded size. We note that current best CP-ABE schemes [BSW07, Wat11, LOS+10, OT10, LW12, RW13, Att14, Wee14, AHY15, CGW15, AC17, KW19] rely on pairings and only support circuits in the class NC1 (albeit in the public key setting). We adapt our construction to the public key setting for the case of bounded size circuits. The size of the ciphertext and secret key as well as running time of encryption, key generation and decryption satisfy the efficiency properties desired from CP-ABE, assuming that all algorithms have RAM access to the public key. However, the running time of the setup algorithm and size of the public key depends on the circuit size bound, restricting the construction to support circuits of a-priori bounded size. We remark that the inefficiency of setup is somewhat mitigated by the fact that setup must only be run once. We generalize our construction to consider attribute and function hiding. The compiler of lockable obfuscation upgrades any attribute based encryption scheme to predicate encryption, i.e. with attribute hiding [GKW17, WZ17]. Since lockable obfuscation can be constructed from LWE, we achieve ciphertext policy predicate encryption immediately. For function privacy, we show that the most natural notion of function hiding ABE for circuits, even in the symmetric key setting, is sufficient to imply indistinguishability obfuscation. We define a suitable weakening of function hiding to sidestep the implication and provide a construction to achieve this notion for both the key policy and ciphertext policy case. Previously, the largest function class for which function private predicate encryption (supporting unbounded keys) could be achieved was inner product zero testing, by Shen, Shi and Waters [SSW09].

Broadcast Encryption with optimal parameters was a long-standing problem, whose first solution was provided in an elegant work by Boneh, Waters and Zhandry \cite{BWZ14}. However, this work relied on multilinear maps of logarithmic degree, which is not considered a standard assumption. Recently, Agrawal and Yamada \cite{AY20} improved this state of affairs by providing the first construction of optimal broadcast encryption from Bilinear Maps and Learning With Errors (LWE). However, their proof of security was in the generic bilinear group model. In this work, we improve upon their result by providing a new construction and proof in the standard model. In more detail, we rely on the Learning With Errors (LWE) assumption and the Knowledge of OrthogonALity Assumption (KOALA) \cite{BW19} on bilinear groups. Our construction combines three building blocks: a (computational) nearly linear secret sharing scheme with compact shares which we construct from LWE, an inner-product functional encryption scheme with special properties which is constructed from the bilinear Matrix Decision Diffie Hellman (MDDH) assumption, and a certain form of hyperplane obfuscation, which is constructed using the KOALA assumption. While similar to that of Agrawal and Yamada, our construction provides a new understanding of how to decompose the construction into simpler, modular building blocks with concrete and easy-to-understand security requirements for each one. We believe this sheds new light on the requirements for optimal broadcast encryption, which may lead to new constructions in the future.

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 {\em 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: 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. No Finite Channel is Complete with Negligible Error: To complement the above, we show that {\it 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. 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.

Constructing Attribute Based Encryption (ABE) [56] for uniform models of computation from standard assumptions, is an important problem, about which very little is known. The only known ABE schemes in this setting that (i) avoid reliance on multilinear maps or indistinguishability obfuscation, (ii) support unbounded length inputs and (iii) permit unbounded key requests to the adversary in the security game, are by Waters from Crypto, 2012 [57] and its variants. Waters provided the first ABE for Deterministic Finite Automata (DFA) satisfying the above properties, from a parametrized or “q-type” assumption over bilinear maps. Generalizing this construction to Nondeterministic Finite Automata (NFA) was left as an explicit open problem in the same work, and has seen no progress to date. Constructions from other assumptions such as more standard pairing based assumptions, or lattice based assumptions has also proved elusive.In this work, we construct the first symmetric key attribute based encryption scheme for nondeterministic finite automata (NFA) from the learning with errors (LWE) assumption. Our scheme supports unbounded length inputs as well as unbounded length machines. In more detail, secret keys in our construction are associated with an NFA M of unbounded length, ciphertexts are associated with a tuple $$(\mathbf {x}, m)$$ where $$\mathbf {x}$$ is a public attribute of unbounded length and m is a secret message bit, and decryption recovers m if and only if $$M(\mathbf {x})=1$$.Further, we leverage our ABE to achieve (restricted notions of) attribute hiding analogous to the circuit setting, obtaining the first predicate encryption and bounded key functional encryption schemes for NFA from LWE. We achieve machine hiding in the single/bounded key setting to obtain the first reusable garbled NFA from standard assumptions. In terms of lower bounds, we show that secret key functional encryption even for DFAs, with security against unbounded key requests implies indistinguishability obfuscation ($$\mathsf {iO}$$) for circuits; this suggests a barrier in achieving full fledged functional encryption for NFA.

Constructing indistinguishability obfuscation ($$\mathsf{iO}$$iO) [17] is a central open question in cryptography. We provide new methods to make progress towards this goal. Our contributions may be summarized as follows:1.Bootstrapping. In a recent work, Lin and Tessaro [71] (LT) show that $$\mathsf{iO}$$iO may be constructed using (i) Functional Encryption ($$\mathsf {FE}$$FE) for polynomials of degree L, (ii) Pseudorandom Generators ($$\mathsf{PRG}$$PRG) with blockwise localityL and polynomial expansion, and (iii) Learning With Errors ($$\mathsf{LWE}$$LWE). Since there exist constructions of $$\mathsf {FE}$$FE for quadratic polynomials from standard assumptions on bilinear maps [16, 68], the ideal scenario would be to set $$L=2$$L=2, yielding $$\mathsf{iO}$$iO from widely believed assumptionsUnfortunately, it was shown soon after [18, 73] that $$\mathsf{PRG}$$PRG with block locality 2 and the expansion factor required by the LT construction, concretely $$\varOmega (n \cdot 2^{b(3+\epsilon )})$$Ω(n·2b(3+ϵ)), where n is the input length and b is the block length, do not exist. In the worst case, these lower bounds rule out 2-block local $$\mathsf{PRG}$$PRG with stretch $$\varOmega (n \cdot 2^{b(2+\epsilon )})$$Ω(n·2b(2+ϵ)). While [18, 73] provided strong negative evidence for constructing $$\mathsf{iO}$$iO based on bilinear maps, they could not rule out the possibility completely; a tantalizing gap has remained. Given the current state of lower bounds, the existence of 2 block local $$\mathsf{PRG}$$PRG with expansion factor $$\varOmega (n \cdot 2^{b(1+\epsilon )})$$Ω(n·2b(1+ϵ)) remains open, although this stretch does not suffice for the LT bootstrapping, and is hence unclear to be relevant for $$\mathsf{iO}$$iO.In this work, we improve the state of affairs as follows.(a)Weakening requirements on Boolean PRGs: In this work, we show that the narrow window of expansion factors left open by lower bounds do suffice for $$\mathsf{iO}$$iO. We show a new method to construct $$\mathsf {FE}$$FE for $$\mathsf {NC}_1$$NC1 from (i) $$\mathsf {FE}$$FE for degree L polynomials, (ii) $$\mathsf{PRG}$$PRGs of block locality L and expansion factor $$\tilde{\varOmega }(n \cdot 2^{b(1+\epsilon )})$$Ω~(n·2b(1+ϵ)), and (iii) $$\mathsf{LWE}$$LWE (or $$\mathsf{RLWE}$$RLWE).(b)Broadening class of sufficient randomness generators: Our bootstrapping theorem may be instantiated with a broader class of pseudorandom generators than hitherto considered for $$\mathsf{iO}$$iO, and may circumvent lower bounds known for the arithmetic degree of $$\mathsf{iO}$$iO-sufficient $$\mathsf{PRG}$$PRGs [18, 73]; in particular, these may admit instantiations with arithmetic degree 2, yielding $$\mathsf{iO}$$iO with the additional assumptions of $$\mathsf{SXDH}$$SXDH on Bilinear maps and $$\mathsf{LWE}$$LWE. In more detail, we may use the following two classes of $$\mathsf{PRG}$$PRG:i.Non-Boolean PRGs: We may use pseudorandom generators whose inputs and outputs need not be Boolean but may be integers restricted to a small (polynomial) range. Additionally, the outputs are not required to be pseudorandom but must only satisfy a milder indistinguishability property (We note that our notion of non Boolean PRGs is qualitatively similar to the notion of $$\varDelta $$Δ RGs defined in the concurrent work of Ananth, Jain and Sahai [9]. We emphasize that the methods of [9] and the present work are very different, but both works independently discover the same notion of weak PRG as sufficient for building $$\mathsf{iO}$$iO.).ii.Correlated Noise Generators: We introduce an even weaker class of pseudorandom generators, which we call correlated noise generators ($$\mathsf{CNG}$$CNG) which may not only be non-Boolean but are required to satisfy an even milder (seeming) indistinguishability property than $$\varDelta $$Δ RG.(c)Assumptions and Efficiency. Our bootstrapping theorems can be based on the hardness of the Learning With Errors problem or its ring variant ($$\mathsf{LWE}/ \mathsf{RLWE}$$LWE/RLWE) and can compile $$\mathsf {FE}$$FE for degree L polynomials directly to $$\mathsf {FE}$$FE for $$\mathsf {NC}_1$$NC1. Previous work compiles $$\mathsf {FE}$$FE for degree L polynomials to $$\mathsf {FE}$$FE for $$\mathsf {NC}_0$$NC0 to $$\mathsf {FE}$$FE for $$\mathsf {NC}_1$$NC1 to $$\mathsf{iO}$$iO [12, 45, 68, 72].Our method for bootstrapping to $$\mathsf {NC}_1$$NC1 does not go via randomized encodings as in previous works, which makes it simpler and more efficient than in previous works.2.Instantiating Primitives. In this work, we provide the first direct candidate of $$\mathsf {FE}$$FE for constant degree polynomials from new assumptions on lattices. Our construction is new and does not go via multilinear maps or graded encoding schemes as all previous constructions. Together with the bootstrapping step above, this yields a completely new candidate for$$\mathsf{iO}$$iO (as well as $$\mathsf {FE}$$FE for $$\mathsf {NC}_1$$NC1), which makes no use of multilinear or even bilinear maps. Our construction is based on the ring learning with errors assumption ($$\mathsf{RLWE}$$RLWE) as well as new untested assumptions on NTRU rings.We provide a detailed security analysis and discuss why previously known attacks in the context of multilinear maps, especially zeroizing and annihilation attacks, do not appear to apply to our setting. We caution that our construction must yet be subject to rigorous cryptanalysis by the community before confidence can be gained in its security. However, we believe that the significant departure from known multilinear map based constructions opens up a new and potentially fruitful direction to explore in the quest for $$\mathsf{iO}$$iO.Our construction is based entirely on lattices, due to which one may hope for post quantum security. Note that this feature is not enjoyed by instantiations that make any use of bilinear maps even if secure instances of weak PRGs, as identified by the present work, the follow-up by Lin and Matt [69] and the independent work by Ananth, Jain and Sahai [9] are found.

Waters [Crypto, 2012] provided the first attribute based encryption scheme ABE for Deterministic Finite Automata (DFA) from a parametrized or “q-type” assumption over bilinear maps. Obtaining a construction from static assumptions has been elusive, despite much progress in the area of ABE.In this work, we construct the first attribute based encryption scheme for DFA from static assumptions on pairings, namely, the $$\mathsf{DLIN}$$ assumption. Our scheme supports unbounded length inputs, unbounded length machines and unbounded key requests. In more detail, secret keys in our construction are associated with a DFA M of unbounded length, ciphertexts are associated with a tuple $$(\mathbf {x}, \mathsf {\mu })$$ where $$\mathbf {x}$$ is a public attribute of unbounded length and $$\mathsf {\mu }$$ is a secret message bit, and decryption recovers $$\mathsf {\mu }$$ if and only if $$M(\mathbf {x})=1$$.Our techniques are at least as interesting as our final result. We present a simple compiler that combines constructions of unbounded ABE schemes for monotone span programs (MSP) in a black box way to construct ABE for DFA. In more detail, we find a way to embed DFA computation into monotone span programs, which lets us compose existing constructions (modified suitably) of unbounded key-policy ABE ($${\mathsf {kpABE}}$$) and unbounded ciphertext-policy ABE ($${\mathsf {cpABE}}$$) for MSP in a simple and modular way to obtain key-policy ABE for DFA. Our construction uses its building blocks in a symmetric way – by swapping the use of the underlying $${\mathsf {kpABE}}$$ and $${\mathsf {cpABE}}$$, we also obtain a construction of ciphertext-policy ABE for DFA.Our work extends techniques developed recently by Agrawal, Maitra and Yamada [Crypto 2019], which show how to construct ABE that support unbounded machines and unbounded inputs by combining ABE schemes that are bounded in one co-ordinate. At the heart of our work is the observation that unbounded, multi-use ABE for MSP already achieve most of what we need to build ABE for DFA.

We construct Indistinguishability Obfuscation ($$\mathsf {iO}$$) and Functional Encryption ($$\mathsf {FE}$$) schemes in the Turing machine model from the minimal assumption of compact $$\mathsf {FE}$$ for circuits ($$\mathsf {CktFE}$$). Our constructions overcome the barrier of sub-exponential loss incurred by all prior work. Our contributions are:1.We construct $$\mathsf {iO}$$ in the Turing machine model from the same assumptions as required in the circuit model, namely, sub-exponentially secure $$\mathsf {FE}$$ for circuits. The previous best constructions [6, 41] require sub-exponentially secure $$\mathsf {iO}$$ for circuits, which in turn requires sub-exponentially secure $$\mathsf {FE}$$ for circuits [5, 15].2.We provide a new construction of single input $$\mathsf {FE}$$ for Turing machines with unbounded length inputs and optimal parameters from polynomially secure, compact $$\mathsf {FE}$$ for circuits. The previously best known construction by Ananth and Sahai [7] relies on $$\mathsf {iO}$$ for circuits, or equivalently, sub-exponentially secure $$\mathsf {FE}$$ for circuits.3.We provide a new construction of multi-input $$\mathsf {FE}$$ for Turing machines. Our construction supports a fixed number of encryptors (say k), who may each encrypt a string $$\mathbf {x}_i$$ of unbounded length. We rely on sub-exponentially secure $$\mathsf {FE}$$ for circuits, while the only previous construction [10] relies on a strong knowledge type assumption, namely, public coin differing inputs obfuscation. Our techniques are new and from first principles, and avoid usage of sophisticated $$\mathsf {iO}$$ specific machinery such as positional accumulators and splittable signatures that were used by all relevant prior work [6, 7, 41].