Attribute-based encryption (ABE) [SW05] provides a method for encrypting data which allows for sharing at a much finer-grained level than standard public key cryptography. In an ABE system one associates a ciphertext with an attribute string w when encrypting message m to form a ciphertext ct. A secret key (as issued by some authority) is associated with a predicate function f . A decryption algorithm using sk f on the ciphertext will be able to return the message m if and only if f (w) = 1.
The initial and many subsequent ABE constructions (e.g. [GPSW06,BSW07]) provided functionality for when f was a boolean formula or circuit that would operate over a fixed set of attributes. This works well for the setting when an attribute string could say represent a record that was of a fixed form, however, would not work as well in a setting where we want the attribute string structure to be less rigid and of arbitrary length. Initial progress towards resolving such issue was by Waters [Wat12] who provided the first ABE construction for a uniform model of computation where the attribute string w ∈ {0, 1} * could be an arbitrary length string and f is a Deterministic Finite Automata (DFA). A user in such a setting can decrypt a ciphertext whenever the DFA f accepts w.
Since then, ABE systems in uniform models of computation have been very well studied, with subsequent works roughly falling into the following three categories grouped by the hardness assumption.
• The ABE construction of Waters [Wat12] for DFAs was built from bilinear maps and was collusion resistant in that it allowed for an unbounded number of private keys to be issued, but was only selectively secure in that the attacker was required to submit a challenge string w * before seeing the public parameters of the system. Unlike constructions where the length of w is fixed by the security parameter, there is no known way of generically moving from selective to adaptive security using complexity leveraging and assuming sub-exponential hardness. Subsequent works [Att14, Att16, AC17, GWW19, AMY19b, GW20] in the bilinear map setting improved upon the security arguments in this setting as well as gave "ciphertext-policy" variants of the construction.
• A second cohort of constructions [BCP14, IPS15, KLW15, BCG + 18] arise by constructing ABE for Turing Machines from obfuscation culminating in the work of Ananth and Sahai [AS16] that achieves functional encryption for Turing Machines from indistinguishability obfuscation with no a-priori bound on the input size or machine description. We refer the reader to [AS16] for a discussion of the tradeoffs present in prior works.
• In a third line of work, Agrawal and Singh [AS17] gave a construction of a single-key secure functional encryption scheme provably secure under the Learning with Errors (LWE) [Reg05] assumption. They could prove security only when the single private key was requested before the challenge ciphertext.
Additionally, in their model the encryptor had to specify the maximum time t that the Turing Machine computation is allowed to run for during decryption. The work of Gentry et al. [GHRW14b] also gave a construction for single-key secure functional encryption for RAM computation from single-key secure functional encryption for circuits and garbled RAM, but the key generator not only takes the RAM program as input but the input size and run-time bound as well. Thus, the encryption algorithm could only encrypt messages of a-priori fixed length.
For unbounded collusions, Boyen and Li [BL15] gave constructions for DFAs from the LWE assumption and Agrawal, Maitra, and Yamada [AMY19a] did this for NFAs, but in the secret key setting. Ananth, Fan and Shi [AFS19] give an LWE solution for unbounded collusions in the problem of constructing ABE for RAM Turing Machines. However, the maximum number of machine steps is given as a parameter to the setup algorithm and will serve as a bound for the system.
One common thread of the above works is that they all depended upon a specific number theoretic setting. Even in the case of indistinguishability obfuscation, the best known construction in the recent breakthrough work [JLS21] relies on a careful combination of multiple specific algebraic assumptions.
Here we pursue a new direction of obtaining Attribute-Based Encryption for uniform computation models from general assumptions. In particular, we provide solutions that assume Identity-Based Encryption (IBE) [Sha85,BF01]. We believe IBE is a good platform for this pursuit as it is known under most "mainstream" number theoretic assumptions that imply public key cryptography such as factoring, search Diffie-Hellman, and Learning with Errors [BF01,Coc01,GPV08,DG17a].
In this work we show how to achieve Attribute-Based Encryption for Turing Machines that is adaptively secure against any attacker that requests at most q = q(λ) private keys where q can be any polynomial function determined at system setup. Our work is logically broken into two parts.
In the first part we develop our core construction which is an ABE system for Turing Machines secure against any poly-time attacker that requests a single key before declaring the attribute string w * for a challenge ciphertext. In this system the maximum running time t of the Turing Machine is determined by the encryption algorithm as in [AS17].
Our approach leverages a garbled RAM construction due to Gentry, Halevi, Raykova, and Wichs (GHRW) [GHRW14a] which intuitively allows a sequence of t garbled programs to run while maintaining a persistent database across invocations. We combine this with an IBE system in a spirit motivated by [DG17a,DG17b,GS17,GHMR18] which allows us to securely evaluate a Turing Machine computation that delivers the message on decryption only if the machine accepts. One challenge we encounter is that the GHRW definition of simulation security is defined as distinguishing between a real garbled RAM and a simulated one over the whole computation. However, this notion of simulation is not fine-grained enough for our purposes. Instead we need to introduce a notion of iterated simulation security where it is hard to distinguish whether the first i or i + 1 programs were simulated, and not just indistinguishability of the entire computation. Fortunately, we were able to show that the existing GHRW construction satisfies this notion of security as well. Since the GHRW Garbled RAM itself only relies on IBE, the entire security of our construction still depends on IBE only.
The second part of our work is focused on moving from a single key system that is limited to coming before the challenge ciphertext to a q-query system that allows for key requests to come at arbitrary times. We first tackle the question of giving flexibility for when the key query is placed. To do this we use a very relaxed form of non-committing encryption [CFGN96,DN00,KO04] where the non-committing simulation property must hold when an attacker is given the secret key of a public key encryption system. (But not the randomness for encryption and key generation as in [CFGN96].) We show that this form of non-committing encryption is strong enough to transform our single key ABE system into one where the key query can come before or after the challenge ciphertext. We follow this transformation with another one to allow for q queries by applying standard combinatorial techniques. To complete the transformation we provide a simple construction for such a non-committing encryption scheme from public key encryption in the case of bounded length messages, while for unbounded messages we additionally rely on hash function modeled as a Random Oracle [BR93]. The non-committing encryption we consider in this work is very similar to that of receiver non-committing encryption [CHK05].
We want to emphasize that prior to our work, all other ABE systems in uniform computation models either relied on specific algebraic assumptions, or powerful notions such as succinct function encryption and program obfuscation. That is, unlike for non-uniform models where we have numerous generic constructions (e.g., [SS10,GVW12,AV19]) from general assumptions such as public-key encryption, it was believed that relying on algebraic manipulation or powerful encryption/obfuscation primitives might be necessary for handling uniform models where the attribute space is not statically fixed. Ours is the first work that dispels this belief. Thus, we want to highlight that one of our main take-away messages is that the central source of hardness is only full collusion resistance, and not the underlying model of computation in functional encryption.
Organization We begin by providing a technical overview of our approach in the next section. Since our bounded collusion secure ABE system for TM predicates relies extensively on garbled RAM, thus we start by describing our notations and other standard cryptographic primitives in Section 2, and recalling the definition of garbled RAM along with the our proposed iterated simulation security definition in Section 3. In Section 4, we describe our main construction for ABE for TMs via the usage of IBE and garbled RAM. Later in Appendix A, we describe our relaxed notion of non-committing encryption, a simple construction, and its usage in the transformation from key-selective secure ABE to standard security. We then follow this by providing a transformation to go from 1-query security to q-query security in Appendix B. Finally, in Appendix C, we show that the GHRW garbled RAM scheme [GHRW14a] satisfies the iterated simulation security that we rely on.
The overview is split into two parts where we first describe our core construction from garbled RAM and identity-based encryption. This construction gives us 1-query secure ABE scheme for TMs where the secret key query must be made before obtaining the challenge ciphertext. In the second part, we describe how to lift the security of any ABE scheme for TMs, which guarantees security in this restricted 1-query key-selective setting, to provide general bounded collusion security via a sequence of generic black-box transformations. We conclude with some interesting open directions for further investigation.
As highlighted in the previous section, the aspect of ABE systems in a uniform model of computation (such as Turing Machines in our case) that makes it quite appealing is that it allows an encryptor to specify an a-priori unbounded length attribute during encryption while still enabling a fixed decryption key to work on all such varying length ciphertexts. From a mechnical perspective, this suggests that ciphertexts for such computation models should possess a self-reducibility feature. By this we mean that in a structural sense the ciphertext could be broadly divided into two components -one being reusable, while other being execution time-step dependent. Here we expect the reusable component to store the current state of computation during decryption, and the time-step dependent component to self-reduce, i.e. to be used piece-by-piece (with each piece annotated with an execution time-step) for updating the reusable component thereby guiding the decryption process to either the plaintext or failure depending on the predicate.
Comparing this mechnical view with that for ABE systems in a non-uniform model of computation, the stark difference comes up in the implementation of the reusable component which for non-uniform models could mostly be relegated to the predicate key instead, since each key already fixes an upper bound on the number of such re-use operations/computation steps. This restriction is very consequential both for the construction as well as proof purposes. Circumventing such unbounded reusability problems under standard cryptographic assumptions has been a difficult task so far.
Our approach is to start with the simplest goal which is of security in presence of a single key corruption where the challenge attribute as well as the TM key queried must be selectively chosen by the attacker.foot_0 Now we already know that the concept of garbled circuits [Yao86] have been tremendously useful in building bounded collusion secure ABE systems in a non-uniform circuit model (and bounded collusion secure functional encryption more generally) [SS10,GVW12]. A natural question is whether the same could be stated if we switch to a uniform computation model such as TMs since, despite the strengthening of the computation model, the targetted encryption primitive still provides only an all-or-nothing style guarantee.
A building block construction. First, note that plugging in TMs as the model of computation in the mechnical picture described above, we get the reusable ciphertext component to correspond to the tape of the TM being operated on, while the time-step dependent component is being used to emulate a step-by-step execution of the TM itself. Next, consider a highly simplified TM model where the number of states as well as the size of the TM tape are a-priori fixed polynomials, say N and L respectively. (Although this simplified model no longer resembles our targetted TM model of computation, this will serve as a good starting point to convey the main idea which we afterwards extend to capture the more general model.) It turns out that for such a model there is a natural candidate ABE system from just plain public-key encryption and garbled circuits.
Let us start by sharing our methodology for encrypting a message m under attribute string w with time bound t.foot_1 At a high level, the idea is to let encryptor create a sequence of t step circuits, where each step circuit takes as input the entire state of TM (which contains the current state, location of the tape header, and the entire tape of the TM) and it performs one execution step (that is, applies one transition) and its output is the entire TM state after this execution step (that is, output state, tape header and full tape contents). Here the last step circuit simply outputs the encrypted message m if the execution lands in accepting state. An encryptor then garbles each such step circuit starting from the last one (that is, t-th step circuit first), and encodes the wire labels for the i-th garbled step circuit in the (i -1)-th step circuit. Now each garbled circuit must not output the wire labels in the clear, thus it instead encrypts the labels corresponding to the TM state for next step circuit under a group of carefully selected PKE public keys. The idea here is that during setup we sample a pair of PKE public-secret keys for each state transitionfoot_2 , and a secret key for any TM in this system consists of a sequence of PKE secret keys corresponding to all the state transition supported by the corresponding TM.
Intuitively, a ciphertext consists of a sequence of t garbled circuits, and a secret key consists of a polynomial-sized set of PKE secret keys such that to decrypt a ciphertext, one evaluates each garbled circuit in a sequential order thereby revealing the state of the TM computation after each execution step encrypted under appropriate PKE public keys. An honest decryptor can always recover the relevant garbled circuit wires along its path of computation, and finally recovers the message if the machine accepts within the ciphertext specified time bound t. One could also provide security of this construction by a straightforward sequence of hybrids where the simulator would, instead of computing the garbled circuits honestly, replace each garbled circuit with a simulated garbled circuit one by one. And, since our assumption was the tape size and number of states to be polynomially bounded, thus this scheme is efficient (i.e., runs in polynomial time) as well.
Looking ahead, the above approach serves as a good warm-up construction for our core construction which does not suffer from the above limitations. Very briefly, we make the following observations. First, note that the above construction does not exploit the fact that a given step circuit does not need to look at the entire TM tape, but instead it needs to make changes right next to the location of tape header. Thus, instead of passing around the entire TM tape to each step circuit, we can maintain a persistent storage that contains the full TM tape while each step circuit only affects a few particular locations in the storage. To this end, we replace our usage of garbled circuits with garbled RAMs [LO13] thereby bypassing the above problem. Second, we assumed that the number of states are a-priori polynomially bounded. This was mainly needed so to avoid the exponential blow-up due to the exponential state space which we could not hope to generically encode using only public-key encryption. To solve this issue, we use an identity-based encryption scheme to provide a succinct mechanism to encode the state transitions without this exponential blow-up. Similar ideas of encoding exponential size strings succinctly have been used in numerous other contexts [GKW16, DG17a, GHMR18, GGLW21, AMVY21].
Main construction. Before moving to a more technical description of our scheme, we fix our notation and interpretation of a TM. This will help in understanding our main construction more clearly. We consider a TM to be represented by a large set T of state transitions (q in , b in , q out , b out , dir) , where each transition is associated with an input state q in , the input bit read b in , the output state q out , the bit to written b out , and the direction dir in which the tape head moves. Also, let each state q be represented as an n-bit string.
As hinted previously, a central component of our construction is the notion of garbled RAMs. Recall that a RAM program P gets random access to a large memory D (upon which it can perform arbitrary reads and writes) along with a short input x, and at the end of its computation it produces an output y. Here we will be interested in multi-program versions of RAM programs where given a sequence of RAM programs P 1 , . . . , P and corresponding short inputs x 1 , . . . , x , and an initial memory D, the programs are run in succession on their respective inputs wherein say program P i outputs some result y i and updates the database D which is then used by the next program P i+1 .
Garbled RAMs. The notion of garbled RAMs is a generalization of circuit garbling to RAM programs, where the memory owner first garbles the memory D generating a pair of garbled database D along with a garbling key k D . The garbling key k D can then be used to garble any RAM program P with respect to program index j to produce a garbled program P along with input labels {lab i,b } i,b . Here the program index j is meant to capture the number of programs that have been run (including P ). 4 For example, to garble the previously defined sequence of RAM programs, when the garbling party runs the program garbling procedure for program P j it specifies index j as the program index since it wants P j to be the j-th RAM program being evaluated in the sequence. Also, as in the case of circuit garbling, to evaluate a garbled program P with labels {lab i,b } i,b on an input x, the evaluator selects the labels corresponding to bits of x, i.e. y = Eval D ( P , {lab i,xi } i ) where y is the output of running P on x with memory D. The standard security property considered in most prior works [LO13, GHRW14a, LO14, GHL + 14, GLOS15, GLO15] is of static (full) simulation security wherein an adversary must not be able to distinguish a sequence of honestly garbled RAM programs and database from a simulated sequence of programs and database, where the simulator only knows the corresponding outputs {y i } i of each RAM program (but not the database D, or any of the individual programs P i , or their corresponding inputs x i ).
Core construction: switching from garbled circuits to garbled RAMs. With all the notation set, our main construction is very simple to follow. The setup of our system simply corresponds to sampling a IBE master public-secret key pair. (Recall that previously in our simplified building block construction, the setup was sampling a large number of PKE public-secret key pairs. As we noted then, here we use IBE instead of do the same more efficiently.) Next, to generate a secret key for a TM represented by a set T of transitions, the key generator encodes each transition (q in , b in , q out , b out , dir) ∈ T into (n + 2) distinct identities. (The identity-encodings we employ are the well known bit-decomposition style encodings where one encodes the output state q out bit-by-bit into n strings of the form (i, q out [i]) ∈ [n] × {0, 1}.) Here n of these IDs jointly encode the output state q out , while the other two encode the output bit to written b out , and the direction dir separately.
The encryption algorithm in our core construction follows a similar paradigm to that described in our building block construction with the only major change being we move to using garbled RAMs instead. Concretely, to encrypt a message m under an unbounded length attribute string w ∈ {0, 1} * with time bound t, the encryptor first creates an empty memory D of size t + 1.foot_4 It then writes the attribute w on the RAM memory D, and garbles it to get the corresponding garbled database D. (Basically this memory is used as the tape of the TM embedded in the predicate keys during decryption.) Next, the encryptor creates a sequence of t RAM programs where the i-th program takes as input the TM state q in , bit to be written b out , and the direction dir that was output by the previous (i.e., (i -1)-th) program/TM transition. Given these inputs, the RAM program writes the bit b out at the current tape header, updates the tape header location depending on dir, and encrypts the garbled labels for the next (i.e., (i + 1)-th) RAM program under appropriate identities. (Note that here we crucially rely on our bit-decomposition style identity-encodings of the output state while encrypting the next program labels.) Thus, a ciphertext contains t such garbled RAM programs in which the programs are garbled one-by-one from the last to first since each program contains labels for the next successive garbled program. Connecting this to original mechnical viewpoint, the garbled database should be thought of as the reusable ciphertext component while the garbled programs as the timestep dependent components. During decryption, an evaluator simply decrypts the wire labels depending on the current state of its TM execution and evaluates the garbled programs to recover encryptions of the wire labels for the next program. Doing this successively, an evaluator recovers the message if its TM accepts the attribute word within the ciphertext specified time bound.
Security: how to prove it? Although the above simple scheme seems to be secure when an adversary makes only a single key query and that too before receiving the challenge ciphertext, proving the same seems a bit challenging. This stems from the fact that a natural proof strategy seems to be incompatible with the full simulation security guaranteed by the underlying garbled RAM scheme. To better understand this, first recall that the garbled RAM security property for multi-program version states that no adversary can distinguish between a sequence of honestly garbled RAM programs (along with half of the honestly computed corresponding garbled labels) from a sequence of simulated garbled RAM programs (again along with half of the simulated garbled labels), where the garbled labels provided depend on the input to be fed to each RAM program. Next, observe that in our construction, the RAM programs which we garble are not independent programs but instead each RAM program in our construction directly depends on the garbling of the next RAM program in the sequence (since the i-th RAM program contains labels for the (i + 1)-th RAM program). Juxtaposing these two facts, we get that no reduction algorithm in the proof could even statically define the sequence of RAM programs it wants garbled without interacting with the garbled RAM challenger.
Thus, this circularity/interdependence prevents a natural proof strategy from working. But it turns out that the problem is a bit deeper than what one can perceive at this point. That is, suppose we could somehow make the RAM programs (that we want to garble) fully independent, the problem is that the underlying sequence of RAM programs that we want to simulate will still be executing the TM step-by-step where each program reveals the labels for the next garbled program, thus a reduction algorithm can only simulate the garbled programs one at a time, and not all at once. Let us clarify this second issue further by first suggesting a modification to our current construction to solve the first interdependence problem.
The modification to our construction for solving this interdependence problem is to sample a fresh PRF keys for each label of the garbled RAM program at the beginning, and instead of letting a RAM program output encryptions of the labels for the next program, we make each program output encryptions of the corresponding PRF keys. Once we set the underlying RAM programs this way, we garble them and to tie them together we encrypt the labels for the (i + 1)-th RAM program under PRF keys hardwired in the i-th RAM program. Intuitively, this means evaluating the garbled RAM programs an evaluator learns encryptions of some of the PRF keys which are then used to recover the garbled labels outside of this garbled RAM structure.
Getting back to proving security, the problem we still encounter is that as a reduction algorithm it is unclear on how to simulate all the garbled RAM programs at once, since for simulation the reduction needs to able to generate the ciphertext given only half of the wire labels, but those wire labels are encrypted under PRF keys which are hardwired inside each RAM program. Therefore, for a proof to go through a reduction algorithm needs to first remove information about half of garbled labels from the ciphertexts for which it needs to remove the information about half of the corresponding PRF keys which means the reduction must be able to simulate the garbled programs instead which is what we were trying to do in the first place. This circularity stems from the fact that the garbled RAM full simulation security only guarantees security when all the garbled programs are being simulated at the same time, instead of being partially/sequentially simulated.
Strengthening garbled RAM security. To fix the above problem we introduce a stronger security notion for garbled RAMs which we call iterated simulation security. 6 To us, it seems a more natural notion of security for multi-program garbled RAM versions, and also captures the kind of garbled RAM security we need for our proof to go through. We describe it in detail later in Section 3, but very briefly it states that there exists an efficient simulator such that for any sequence of programs and inputs, it is hard to distinguish between simulations of the first i programs and inputs along with honest garblings of the remaining -i programs from simulations of the first i + 1 programs and inputs along with honest garblings of the remaining -i -1 programs. That is, partial executions of the multi-program garbled RAMs are also simulatable.
Plugging in the strengthened garbled RAM security property, we are able to prove security of our ABE scheme by organizing an iterated hardwiring-style proof strategy where we start by simulating the first garbled program, then remove the information about labels for the next program by relying on PRF security (and the fact that only half of the PRF keys are needed to simulate the first garbled program), and keep on interleaving garbled RAM security with PRF security to eventually remove the plaintext information whenever the underlying TM does not accept the attribute word.
In order to complete the proof, we need to construct such a garbled RAM scheme that achieves our notion of iterated simulation security. Fortunately, we were able to show that most existing garbled RAM schemes already are secure under this partial simulation framework. Later in Appendix C, we show that the IBE-based garbled RAM construction in [GHRW14a] is an iterated simulation secure garbled RAM scheme. Although we believe that garbled RAM construction of Garg et al. [GLOS15] from one-way functions can also be proven to be secure in this iterated simulation framework, since our ABE construction already relies on IBE thus we chose to provide a proof of iterated simulation security for the simpler IBE-based scheme of Gentry et al. [GHRW14a].
Lifting the core construction to q-query adaptive security After a closer look at the proof overview provided for our core construction, the reason behind our construction only enabling a proof in key-selective model (that is, where the key query must be made before receiving the challenge ciphertext) becomes apparent. Very briefly, the bottleneck is that the reduction algorithm needs to know the current state of partial TM execution while embedding the challenge ciphertext with partially simulated components. Thus, the reduction must know the TM of the key query before creating the challenge ciphertext. Now instead of modifying our core construction to resolve this bottleneck, we instead observe that if the adversary gets to corrupt at most one key, then we could generically amplify key-selective security in a black-box manner to adaptive security. The only tool needed for such an amplification is a relaxed notion of non-committing encryption (NCE) [CFGN96, DN00, KO04] which we call weak non-committing encryption (wNCE). In a wNCE system, there is an efficient simulator that could "open" the ciphertext to any message by providing a simulated secret key after already committing to the public key in the beginning. For security, it is only required that the distribution of simulated keys and ciphertext is computationally indistinguishable from the distribution generated by the real encryption protocol. 7Given such a weak NCE scheme, the idea is pretty straightforward. During setup, we would additionally sample a wNCE key pair, and encryption algorithm will be a simple double encryption where each (keyselective secure) ABE ciphertext will be encrypted under the wNCE system. Each predicate key now contains the wNCE secret key as well as the underlying ABE key, where during decryption, the decryptor first decrypts the outer wNCE ciphertext to learn the core ABE ciphertext which it then decrypts using the core ABE key. Now the adaptive security of this transformed scheme follows directly from wNCE simulation security and the key-selective ABE security. The idea there is that the challenge ciphertext will be computed as a simulated wNCE ciphertext instead, and when the adversary makes the post-challenge key query, then the reduction algorithm opens the wNCE ciphertext to the challenge ciphertext provided by the key-selective security ABE challenger, and answers the adversary's key query with a simulated wNCE secret key along with the core ABE key provided by the ABE challenger. Similar ideas were also used in [GVW12] in the context of simulation secure functional encryption.
Since there is a very simple construction for a weak NCE scheme from regular public key encryption, this seems to suggest that any 1-query key-selective secure ABE scheme could be generically lifted to achieve 1-query adaptive security instead, however there is an important caveat. The caveat is that this weak NCE construction from PKE has public-secret keys whose sizes grow linearly with length of the messages. Recall that in our generical transformation we encrypt the key-selective ABE ciphertext using the wNCE scheme. If the size of key-selective ABE ciphertext is fixed at setup time, then the transformation goes through as is, but this is not true for ABE in uniform models of computation where the whole motivation is being able to encrypt messages under unrestricted length attributes, thus the ciphertext sizes are a-priori unbounded. This implies that for the above transformation to work in the case of ABE for TMs we need a succinct weak NCE, where by succinct we mean that the system supports encryption of unbounded length messages. To this end, we show another generic transformation that takes any non-succinct weak NCE scheme and compiles it into a succinct NCE scheme albeit in the Random Oracel Model (ROM) [BR93]. Very briefly, the idea here is use the ROM as an adaptive programmable PRF to indistinguishably open simulated ciphertexts to arbitrary messages. During encryption, an encryptor chooses a random λ-bit string K which it encrypts under the non-succinct NCE scheme, and then encrypts the unbounded length message block-by-block using K as a secret key and ROM as a PRF. The simulatability of this scheme follows directly from the simulatability of the non-succinct scheme and programmability of the ROM. This is discussed in detail later in Appendix A. We want to point out that building a succinct weak NCE scheme as described above is impossible in the standard model [Nie02], thus adaptive security of our construction crucially relies on the usage of ROM.
Combining the above ideas, we obtain a 1-query adaptively secure ABE scheme for TMs. To conclude, we show that by using standard combinatorial techniques, the security could be improved to q-query adap-tive security for any a-priori fixed polynomial q(•). Since we are dealing with just an ABE scheme, thus this transformation is much simpler than for other related transformations such as the one for functional encryption in [GVW12]. For completeness, we provide it in Appendix B.
Comparison with Agrawal-Singh [AS17]. Closest to us is the work of Agrawal-Singh [AS17] who construct a 1-query functional encryption scheme for Turing Machines where, like our ABE system, the encryption algorithm depends on the worst case running time of the TM. Ours and their construction share the same mechnical perspective of traversing through a sequence of garbled circuits for encrypting unbounded length inputs, however differ in overall execution since they rely on a succinct single-key FE scheme with the TM evaluation happening under the FE hood, whereas we work with more general primitives such as IBE and garbled RAM thereby our TM evaluation happens on encrypted pieces that come out as outputs of garbled RAM evaluations. The usage of a succinct single-key FE scheme has the benefit of the resulting encryption scheme being a FE scheme with short keys (and not just an ABE scheme like ours), but given the current state-of-the-art [GKP + 13] it also means relying on the LWE assumption, while we rely on much weaker primitives thus are not tethered to the LWE assumption. Like our core key-selective secure ABE scheme, they also prove security in the weaker model where there is a single-key query which must be made before receiving the challenge ciphertext. Although they do not provide any follow-up transformations to improve security like us, we believe our non-committing encryption idea could also be used with their FE construction. However, extending to q-query bounded collusion security would be more tricky than our case, but might be possible to adapt a more elaborate transformation along the lines of [GVW12].
ABE via laconic OT. Cho et al. [CDG + 17] introduced the concept of laconic transfer for secure computation over large inputs. They described an application of laconic OT to non-interactively compute in the RAM setting. Although this application does not directly lead to ABE schemes that supports (RAM) Turing Machine computation, it might be possible to repurpose the underlying ideas to build ABE by going through laconic OT along with garbling techniques. One would need to be careful in executing this idea so that the description size of the Turing Machine does not need to be a-priori bounded at setup time, and this might require adjusting the definition of the corresponding primitives. Additionally, such an approach would need one to rely on laconic OT whereas we chose to focus on IBE since it is both supported by multiple number theoretic assumptions as well as there are multiple number theoretic IBE constructions that do not themselves invoke garbling and thus avoid a double layer of garbling in the eventual construction. There have been prior works [DG17b,KNTY19] which observe that laconic OT could be replaced by IBE in certain applications, and it would be interesting to look at whether same could be done for this alternate approach. In our work, we provide a much direct construction directly from any regular IBE scheme.
Future directions. In this work we focus on proving standard semantic security of our ABE scheme, but we believe one could extend it to CCA security by either relying on the ROM, or on other generic transformations such as [KW19a], and prove it to be a 1-sided predicate encryption scheme directly without relying on generic transformations [GKW17,WZ17]. An interesting open question is whether one could extend our current approach to either achieve succinctness similar to [AS17], or extend it to FE without relying on stronger assumptions. Another related question is whether we could avoid the ROM for amplifying the security of our core ABE scheme from key-selective to fully adaptive. It might be useful look at the graph pebbling techniques [FKPR14, FJP15, JW16, JKK + 17, KW19b] to develop a more intricate hybrid structure for proving adaptive security directly. Another interesting thought might be to rely on adaptive security of garbled RAM schemes [GOS18] instead, however it is unclear how to leverage having an adaptive garbled RAM in our setting. Briefly, the reason is that the extra adaptivity it provides is useful in cryptosystems where an attacker is able to see some of the garbled RAM programs and then somehow influence the inputs or programs for the rest of them; while in our case all the garbling program calls are bundled together in a single call to the encryption oracle. Lastly, another important question is whether these techniques could be used to build ABE systems for TMs where the encryption algorithm no longer depends on the worst case running of the TM.
Notations For any distribution D, we write x ← D to denote that x is sampled from D. For any set S, we write y ← S to denote that y is sampled from the uniform distribution on the S. For any randomized algorithm A(•), we write y ← A(x) to denote that y is chosen as the output of A when run on input x. For positive integers m, n satisfying m ≤ n, we write [m, n] to denote the set {m, m + 1, m + 2, . . . , n}. We write, [n] as shorthand to denote the set [1, n]. For any set S, we write |S| to denote its cardinality. For any string x, we write |x| to denote its length. For any string x (or other ordered set), we write x[i] to denote the i th element of x. We use λ throughout for the security parameter in all algorithms.
Turing Machine Formalism A Turing Machine T is represented as a tuple
where, Q is a finite set of states, Σ is a finite tape alphabet, q start ∈ Q is a unique starting state, F ⊂ Q is a set of accepting states, and δ :
Without loss of generality, we will restrict to Turing Machines operating on a single tape, with state set Q = {0, 1} n for some n, and Σ = {0, 1}. At the start of the computation, we say the machine is in state q start . The input w ∈ Σ * is written on the tape, and the machine head is scanning the leftmost symbol of w. All remaining cells are blank. Computation then proceeds in discrete time steps where at each step, the machine is initially in some state q in ∈ Q and is scanning a cell containing bit b in ∈ Σ. It proceeds by applying the transition relation. If δ(q in , b in ) is defined and
the machine updates its state to q out , overwrites the cell it is currently scanning with b out , and then moves the head by one cell in the direction dir. We call one such application, a transition. The machine proceeds in this way until it either enters an accepting state q ∈ F in which case we say T accepts w, or it enters a state q ∈ Q \ F and is scanning a bit b for which δ(q, b) is undefined. For a positive integer t, if T accepts w after performing at most t transitions, we say T accepts w within t steps. We write |T | to denote the size of T and in particular the number of transitions defined under δ i.e. |T | = |{(q, b) : δ(q, b) is defined}|.
We describe the notion of RAM Programs following the notions of [GHRW14a]. A RAM program P takes a small input x, has random access to a large memory database D upon which it can perform arbitrary reads and writes, performs a sequence of computational steps during a time interval [t init , t fin ], and at the end of its computation produces an output y. More concretely, the program P is represented as a sequence of t step circuits which we denote by C P RAM . Each of the step circuits performs one of the computational steps of P . Each circuit takes as input a small state state as well as the most recently read bit b read from the database D. It outputs an updated state state along with the next read and write instructions to be executed. More formally we write the circuit C P RAM computing the function:
where i read , i write , b write are the next location in D to read from, the next location in D to write to, and the next bit to write respectively. Throughout, we will use the notation C P RAM j for the step circuit which represents the computational step performed by program P at time step j.
Computation of program P with input x on database D begins with the initial step circuit C P RAM t init being evaluated with x as the state input and an arbitrary read input b read which by convention we assume the initial circuit ignores. The circuit outputs state , i read , i write , b write . The database is overwritten at location i write with bit b write , and then the next read bit bread is read from location i read . Then, the subsequent step circuit C P RAM t init +1 is evaluated with inputs (state , bread ). Computation proceeds in this way, with the updated state output by C P RAM j being fed as the state input to C P RAM j+1 , the write location output by C P RAM j being overwritten with the write bit output by C P RAM j , and the bit read at the read location output by C P RAM j being fed as the read bit input to C P RAM j+1 . Finally, the updated state output by the final step circuit C P RAM t fin is taken to be the output y of the computation. By convention, we assume that the final step circuit does not produce any further writes. We also assume without loss of generality that all step circuits of P are of equal size, take the same size input, and produce the same size output.
We allow for multiple programs P k to be run on database D in sequence, with writes made by each program persisting for the subsequent program. For each program P k , we define its memory access pattern access k to be the sequence of reads and writes P k makes to D throughout its computation. More formally we write
where i read j , i write j , b write j are respectively the read location, write location, and write bit output by the step circuit C P k RAM j for time j. We use the notation y ← P (x) D to denote that program P operating on database D with input x outputs y. For multiple programs and inputs, we write (y 1 , . . . , y ) ← (P 1 (x 1 ), . . . , P (x )) D to denote that for all k ∈ , y k is the result of running P k with input x k on database D after running programs P k on input x k in sequence on D for all k < k with changes made to D persisting across program executions.
An Attribute-Based Encryption (ABE) scheme ABE for set of attribute space {0, 1} * , Turing Machines classes T = {T λ } λ∈N , and message spaces M = {M λ } λ∈N consists of four polynomial time algorithms (Setup, KeyGen, Enc, Dec) with the following syntax: Correctness. We say an ABE scheme ABE = (Setup, KeyGen, Enc, Dec) satisfies correctness if for all λ ∈ N, (pp, msk) ← Setup(1 λ ), T ∈ T λ , m ∈ M λ , sk T ← KeyGen(msk, T ), t ∈ N, and w ∈ {0, 1} * for which T accepts w within t steps, and ct ← Enc(pp, m, (w, t)) we have that Dec(sk T , ct) = m.
Efficiency. We require that the algorithm Setup(1 λ ) runs in time polynomial in the security parameter λ. We require that the algorithm KeyGen(msk, T ) runs in time polynomial in the security parameter λ and the size |T | of T . We require that the algorithm Enc(pp, m, (w, t)) runs in time polynomial in the security parameter λ, the length |m| of the message m, the length |w| of the attribute w, and the time bound t. We require that the algorithm Dec(sk T , ct) runs in time polynomial in the security parameter λ and the size |ct| of the ciphertext ct.
Security. Next, we define the security notions we consider for ABE systems.
Definition 2.1 (adaptive security). We say an ABE scheme ABE = (Setup, KeyGen, Enc, Dec) is fully secure if for any PPT adversary A = (A 0 , A 1 ) there exists a negligible function negl(•), such that for all λ ∈ N the following holds
where all Turing Machines T queried by A do not accept the word w within t steps.
In this work, we focus on bounded collusion security for ABE systems where the adversary is restricted to make an a-priori bounded number of key generation queries, say at most Q queries (for some polynomially bounded function Q(λ)). The definition is given below.
Definition 2.2 (Q-query adaptive security). An ABE scheme is said to be Q-query adaptively secure if in the above security game (see Definition 2.1), the adversary can make at most Q queries to the key generation oracle.
We also define the weaker notion which we call key-selective security, where the adversary to must make all key queries before it is given the challenge ciphertext. The definition is given below.
Definition 2.3 (Q-query key-selective security). An ABE scheme is said to be Q-query key-selective secure if in the above security game (see Definition 2.1), the adversary can make at most Q queries to the key generation oracle, and all key queries must be made before getting the challenge ciphertext. Correctness. We say a secret key encryption scheme SKE = (Setup, Enc, Dec) satisfies correctness if for all λ ∈ N, K ← Setup(1 λ ), m ∈ M λ , and ct ← Enc(K, m), we have that Dec(K, ct) = m.
Definition 2.4. We say a secret key encryption scheme SKE = (Setup, Enc, Dec) is secure if for any PPT adversary A = (A 0 , A 1 ) there exists a negligible function negl(•), such that for all λ ∈ N, the following holds
An Identity-Based Encryption (IBE) scheme IBE for set of identity spaces I = {I λ } λ∈N and message spaces M = {M λ } λ∈N consists of four polynomial time algorithms (Setup, KeyGen, Enc, Dec) with the following syntax:
Setup(1 λ ) → (pp, msk). The setup algorithm takes as input the security parameter λ. It outputs the public parameters pp and the master secret key msk.
KeyGen(msk, id) → sk id . The key generation algorithm takes as input the master secret key msk and an identity id ∈ I λ . It outputs a secret key sk id .
Enc(pp, m, id) → ct. The encryption algorithm takes as input the public parameters pp, a message m ∈ M λ , and an identity id ∈ I λ . It outputs a ciphertext ct.
Dec(sk id , ct) → m/⊥. The decryption algorithm takes as input a secret key sk id and a ciphertext ct. It outputs either a message m ∈ M λ or a special symbol ⊥.
Correctness. We say an IBE scheme IBE = (Setup, KeyGen, Enc, Dec) satisfies correctness if for all λ ∈ N, (pp, msk) ← Setup(1 λ ), id ∈ I λ , m ∈ M λ , sk id ← KeyGen(msk, id), and ct ← Enc(pp, m, id), we have that Dec(sk id , ct) = m.
Definition 2.5. We say an IBE scheme IBE = (Setup, KeyGen, Enc, Dec) is secure if for any PPT adversary A = (A 0 , A 1 ) there exists a negligible function negl(•), such that for all λ ∈ N, the following holds
where all id queried by A satisfy id = id .
In our main construction of ABE for Turing Machines, we will make use of the following modified security definition, where the challenge may consist of some polynomial number of message pairs. Definition 2.6 (multi-challenge security). We say an IBE scheme satisfies multi-challenge security if the adversary can not distinguish with non-negligible probability even when it receives polynomially many challenge ciphertexts on polynomially many message-identity tuples of the form {(m
It follows by a simple hybrid argument that any scheme IBE which is fully secure for a single challenge message pair, also satisfies multi-challenge security described above.
In this section we define a notion of Garbled RAM security which abstracts out properties of Garbled RAM constructions in previous works which we will use in our construction of ABE. At a high level, our security notion, which we call Iterated Simulation Security requires that there exists an efficient simulator such that for any sequence of programs and inputs, it is hard to distinguish simulations of the first k programs and inputs along with honest garblings of the remaining -k programs from simulations of the first k + 1 programs and inputs along with honest garblings of the remaining -k -1 programs. Our security definition will actually be a notion of security with Unprotected Memory Access (UMA), that is security in which the garbling may leak the contents of the garbled database D, and the memory access patterns access j of the programs. We drop the label UMA in the subsequent to reduce clutter.
A Garbled RAM scheme GRAM consists of three polynomial time algorithms (GData, GProg, Eval) with the following syntax: . It outputs a value y. As in [GHRW14a], we will think of the evaluation algorithm as a RAM program operating on database D which is able to perform arbitrary reads and writes on D. We slightly abuse notation, and will write
to denote that for all j ∈ , y j is the result of the evaluation algorithm on garbled program P j with labels {lab in,j i } i∈[nj ] on garbled database D after running the evaluation algorithm on garbled programs P j with labels {lab in,j i } i∈[n j ] in sequence on D for all j < j with changes made to D persisting across evaluations.
Correctness. Fix parameters λ, , m ∈ N, a database D ∈ {0, 1} m , and programs and inputs {(P j , x j ∈ {0, 1} nj , n j , t init,j , t fin,j )} j∈[ ] . Let (y 1 , . . . , y ) ← (P 1 (x 1 ), . . . , P (x )) D be the result of sequentially running the programs P j on inputs x j operating on persistent database D. We say a garbled RAM scheme GRAM = (GData, GProg, Eval) satisfies correctness, if for all j ∈ [ ] the following holds Pr y j = y j :
Definition 3.1 (iterated simulation security). We say a garbled RAM scheme GRAM = (GData, GProg, Eval) satisfies iterated simulation security if there exists a polynomial time simulator Sim such that for any PPT adversary A = (A 0 , A 1 ) there exists a negligible function negl(•), such that for all λ ∈ N, the following holds
β ← {0, 1} (st, k, D, {(P j , x j , n j , (t init,j , t fin,j ))} j∈[ ] ) ← A 0 (1 λ ) chal ← Exp λ k-β (D, {(P j , x j , n j , (t init,j , t fin,j ))} j∈[ ] )
where for 0 ≤ k ≤ , the output of Exp λ k (D, {(P j , x j , n j , (t init,j , t fin,j )
where for all j, |P j | is the size of the program P j , y j is the result of running P j with input x j on the database D after having run the previous j -1 programs and inputs, and access j is the memory access pattern of P j . Note, that all the inputs to Sim(•), can be computed from the inputs to Exp λ k . Remark 3.2. As a point of comparison with the simulation security notions considered in prior works such as [GHRW14a], we would want to highlight that in prior works the simulator always outputs a fully simulated execution of the garbled RAM which must be indistinguishable from honestly garbled programs. We, on the other hand, consider indistinguishability in between these partial execution steps.
Efficiency. We require that the algorithm GData(1 λ , D) runs in time polynomial in the security parameter λ and the size |D| of the database D. We require that the algorithms GProg(1 λ , k D , m, P, 1 n , (t init , t fin )) and Eval D ( P , {lab in i } i∈[n] ) both run in time polynomial in the security parameter λ, log(m) where m is the size of D, the size |P | of P , the size n of the input taken by P , and the total number of steps (t fin -t init ) taken by P .
In this section we give our main construction of an ABE scheme for Turing Machines. The scheme will be for message spaces M = {{0, 1} λ } λ∈N .
The primitives used by our construction are as follows. Let GRAM = (GData, GProg, Eval) be a garbled RAM scheme satisfying Iterated Simulation Security. In addition, let IBE be a secure IBE scheme which can encrypt messages of length λ, and assume there is some polynomial n(•) for which the identity space of IBE includes identities of length n (λ) := n(λ) + log(n + 2) + 2. In the subsequent discussion we will simply write n as shorthand for n(λ). Our scheme additionally uses a secret key encryption scheme SKE = (SKE.Setup, SKE.Enc, SKE.Dec). For simplicity of exposition, we assume (w.l.o.g.) that the IBE encryption algorithm takes as input λ-bits of randomness.
In our scheme, we will allow secret key queries for deterministic Turing Machines T = (Q, Σ, q start , F, δ) with the following restrictions. We assume:
• The alphabet Σ is binary. That is Σ = {0, 1}.
• The all 0 state 0 n is reserved as the unique start state q start for all machines.
• The all 1 state 1 n is reserved as the unique accept state q accept ∈ F .
• The transition relation δ is a partial function. In particular, all machines are deterministic.
The above assumptions are essentially without loss of generality for deterministic Turing Machines. In particular, any deterministic Turing Machine with constant size alphabet and a polynomial number of states can be transformed in to a machine satisfying these assumptions with at most polynomial blowup. We will identify each machine T with the set of possible transitions it can make under δ:
Thus, the notation |T |, will simply be the cardinality of the right hand side of the above.
The secret keys of our scheme will be carefully chosen sets of identity secret keys from the IBE scheme IBE. In particular, each identity secret key will be for an identity id ∈ {0, 1} n+ log(n) +2 .
We now formally describe the construction of our ABE scheme, ABE = (Setup, KeyGen, Enc, Dec).
Setup(1 λ ) → (pp, msk). The setup algorithm chooses (pp, msk) ← IBE.Setup(1 λ ), and outputs (pp, msk). KeyGen(msk, T ) → sk T . Let the Turing machine T be given as the set of possible transitions it can make under its transition relation δ:
For each transition (q in , b in , q out , b out , dir) ∈ T the key generation algorithm samples n + 2 identity secret keys. Let ID T be the set of (n + 2) • |T | identities described below:
where in the above b dir = 0 if dir = L and b dir = 1 if dir = R.
Next, the key generation algorithm samples an IBE secret key for each identity in ID T . Concretely, it chooses ∀ (q in , b in , i, β) ∈ ID T , sk (q in ,b in ,i,β) ← IBE.KeyGen(msk, (q in , b in , i, β)).
Finally, the key generation algorithm sets the key to be the machine description T and the entire set of identity secret keys it chose:
Enc(pp, m, (w, t)) → ct. The encryption algorithm garbles a database D along with several copies of a step program P . We formally describe the RAM program P in Fig. 1 before moving on to the encryption algorithm.
The program P operates on a database D of size t + 1 + log(t + 1) . For convenience, we will think of the database as a length t + 1 array D concatenated with an integer index idx ∈ The encryption algorithm proceeds as follows.
1. The encryption algorithm sets a database D ∈ {0, 1} t+1+ log(t+1) . It sets the first |w| bits of D to match w, and sets the remaining bits to 0. More formally,
where || denotes concatenation. The algorithm next garbles the database ( D, k D ) ← GData(1 λ , D).
3. Let P be the RAM program described as described in Fig. 1. For each j ∈ [t + 1], the algorithm sets P j as P j := P [pp, {K
i,b } i,b , m, j; {r
]. 4. Let be the number of steps P takes to run on a database of length |D|. For each j ∈ [t + 1], the algorithm garbles the program P j , computing
, the algorithm computes ciphertexts ct
).
6. Let {lab in,1 i,b } i,b be the set of input labels computed when garbling program P 1 . Recall that the all zero state is the canonical start state. The algorithm outputs the ciphertext
Dec(sk T , ct) → m/⊥. The decryption algorithm parses the ciphertext and secret key as
Let t ≤ t be the maximum number of well defined transitions the machine T can make on input w within t time steps. Let
be the t transitions T makes on input w. The decryption algorithm sets
, and then proceeds to evaluate the garbled RAM programs in ascending order for j = 1 to j = t + 1 as follows:
1. The decryption algorithm evaluates the jth garbled RAM program P j on the current value of the garbled database D with the input given by labels in lab j :
({ct
i,b } i,b , y j ) ← Eval D ( P j , lab j ).
Note that the garbled database D has now been updated after running Eval(•).
2. If y j = ⊥, the algorithm breaks and exits the loop, sets m := y j , and outputs m.
3. Otherwise, if y j = ⊥ it continues. Let (q in j , b in j , q out j , b out j , dir j ) be the jth transition T makes on input w. Also, for i ∈ [n + 2], let b i,j denote the following bit
where in the above b dir j = 0 if dir j = L and b dir j = 1 if dir j = R. The algorithm computes the labels for the next program as follows. For i ∈ [n + 2], it decrypts the IBE and SKE ciphertexts as:
i,bi,j ).
4. If j < t + 1, the algorithm sets the labels for the garbled program P j+1 as
and otherwise if j = t + 1, the algorithm exits the loop and returns ⊥.
We show that the above construction satisfies correctness. Fix message m, attribute w, time bound t, and Turing Machine T . Let (pp, msk) ← Setup(1 λ ), sk T ← KeyGen(msk, T ), ct ← Enc(pp, m, (w, t)). Fix t ≤ t, and assume T accepts w, and transitions to being in state accept for the first time after t transitions. Now, for j ∈ [t ], let (q in j , b in j , q out j , b out j , dir j ) be the jth transition made by T on input w. In particular, note that q in 1 = start = 0 n and q out t = accept = 1 n . Next, for j ∈ [t ], let tape j and pos j respectively be the contents of the first t + 1 cells of the Turing Machine tape and the position of the tape head before the jth transition. Parse the ciphertext ct as
).
We now show that Dec(sk T , ct) outputs m. The decryption algorithm evaluates the garbled programs P j in ascending order starting with P 1 . We claim that the loop satisfies the following invariant. For each j ∈ [t ], q out j , b out j , b dir j is the input encoded by lab j+1 , and the garbled database D at the start of iteration j + 1 of the loop has contents tape j ||pos j . We establish this claim by induction on j.
First we establish the claim when j = 1. At the start of the first iteration of the loop, the garbled database D has contents w||0 t+1+ log(t+1) -|w| . The label set lab 1 , which is used to evaluate P 1 , encodes the all 0 input. Now, the underlying program P 1 has hard-coded pp, the secret keys {K
i,b , (start,
By the definition of sk T and the keys K 1 is encoded by lab 2 . Since P 1 does not modify the database, the contents of the database at the start of the second iteration are tape 1 ||pos 1 . This establishes the claim for j = 1. Now, assume the claim holds for some j < t . Then at the start of iteration j + 1 of the loop, the garbled database D has contents tape j ||pos j . The label set lab j+1 , which is used to evaluate P j+1 , encodes the input q out j , b out j , b dir j . Note, that q in j+1 = q out j . Now, the underlying program P j+1 has hard-coded pp, the secret keys {K
By the definition of sk T and the keys K
i,b as well as the correctness of IBE and SKE, for each i ∈ [n] the algorithm decrypts . Thus q out j+1 , b out j+1 , b dir j+1 is encoded by lab j+2 . Also, by the definition of P j+1 and correctness of GRAM, after the first step of iteration j + 1, D has been modified so that its contents are tape j+1 ||pos j+1 . This established the claim for j + 1.
By induction, the claim holds for all j ∈ [t ]. In particular, the label set lab j+1 encodes the input (q out t +1 , b out t +1 , b dir t +1 ). As we assumed, q out t +1 = accept. By correctness of GRAM, in iteration t + 1,
m). It follows then that the decryption algorithm outputs m, and we are done.
We discuss the efficiency of the algorithms of the above construction. Since Setup(λ) simply runs IBE.Setup(λ), the runtime is poly(λ) whenever the runtime of IBE.Setup(λ) is poly(λ). Next, the algorithm KeyGen(msk, T ) runs IBE.KeyGen(msk, •) a total of n+2 times for each transition of T . Since n is bounded by poly(λ), we have that if the runtime of IBE.KeyGen(msk, •) is poly(λ) then KeyGen(msk, T ) has runtime |T | • poly(λ). Next, the algorithm Enc(pp, m, (w, t)) runs GData(1 λ , D) on a database of size O(t), and garbles t+1 copies of the stepprogram P . Assume |w| ≤ t and that each P has representation of size poly(λ)•polylog(t). If IBE.Enc(pp, •) has runtime poly(λ), GData(1 λ , D) has runtime |D|•polylog(|D|)•poly(λ), and GProg(1 λ , log(|D|), P, 1 n , (t init , t fin )) has runtime |P | • polylog(|D|, |P|) • poly(λ), then Enc(pp, m, (w, t)) has runtime t • polylog(t) • poly(λ). Finally, the algorithm Dec(sk T , ct) evaluates a garbled program and decrypts a set of n ciphertexts of the IBE system t + 1 many times, where t is the time T takes to accept the underlying attribute w used to compute ct. Thus, if IBE.Dec(sk id , ct) has runtime poly(λ) and if Eval D ( P , lab) has runtime |P | • polylog(|D|) • poly(λ) then Dec(sk T , ct) has runtime t • polylog(t) • poly(λ) where t is the time T takes to accept the attribute w used when computing ct and t is the time bound set at encryption time when computing ct.
Next, we prove the following.
Theorem 4.1. Let IBE be a secure IBE scheme as per Definition 2.6, SKE be a secure symmetric key encryption scheme as per Definition 2.4, and GRAM be a garbled RAM scheme satisfying Iterated Simulation Security as per Definition 3.1. Then ABE described above is an ABE scheme satisfying 1-query key-selective security as per Definition 2.3.
We prove Theorem 4.1 via a sequence of hybrid games. First, we describe the games and later on prove that any two adjacent games are indistinguishable.
Game 0. This game corresponds to the original 1-query key-selective security game.
• Setup Phase: The challenger chooses (pp, msk) ← IBE.Setup(1 λ ), and sends pp to the adversary.
(Note that Setup in our scheme is precisely IBE.Setup.)
• Key Query Phase: The adversary submits a single key query for machine T to the challenger. Let the Turing machine T be given as the set of possible transitions it can make under its transition relation δ:
Let ID T be the set of (n + 2) • |T | identities as defined in Eq. (1). The challenger samples an IBE secret key for each identity in ID T . Concretely, it chooses
Finally, it sends the key sk
• Challenge Phase: The adversary submits two challenge messages (m 0 , m 1 ) and the challenge attribute and time bound (w, 1 t ) to the challenger. It must be the case that the machine T for which the adversary was given a secret key sk T during the key query phase does not accept the word w within t steps.
The challenger samples a bit β ← {0, 1}, and computes the challenge ciphertext as follows.
1. The challenger sets a database D ∈ {0, 1} t+1+ log(t+1) . It sets the first |w| bits of D to match w, and sets the remaining log(t + 1) bits to 0. More formally,
where || denotes concatenation. It next garbles the database ( D, k D ) ← GData(1 λ , D).
3. Let P be the RAM program described as described in Fig. 1. For each j ∈ [t + 1], the challenger sets P j as P j := P [pp, {K
i,b } i,b , m β , j; {r
Let be the number of steps P takes to run on a database of length |D|. For each j ∈ [t + 1], the challenger garbles the program P j , computing
, the challenger computes ciphertexts ct
).
6. Let {lab in,1 i,b } i,b be the set of input labels computed when garbling program P 1 . Recall that the all zero state is the canonical start state. The challenger outputs the ciphertext
).
• Guess Phase: The adversary submits its guess β , and wins the game if
). This game is defined similar to Game 0, except now the challenger simulates the first k (out of t + 1) garbled RAM programs and the SKE ciphertexts encrypting the labels for first k -1 levels are also simulated (i.e., half of them contain the simulated wire label keys, while other half encrypt all zeros). Note that while setting up the garbled programs to be simulated, the challenger needs to sample the IBE ciphertexts appropriately where the IBE ciphertexts for the first k -1 simulated garbled programs encrypt only half of the corresponding SKE keys and the IBE ciphertexts for the k-th simulated program encrypts all the keys honestly. Below we describe it in detail highlighting the differences.
• Challenge Phase: The adversary submits two challenge messages (m 0 , m 1 ) and the challenge attribute and time bound (w, 1 t ) to the challenger. It must be the case that the machine T for which the adversary was given a secret key sk T during the key query phase does not accept the word w within t steps.
Let {(q in j , b in j , q out j , b out j , dir j )} j∈[t] be the sequence of the first t transitions made by machine T on input w. Let x 1 = 0 n+2 , and for all other j let x j be the (n + 2)-bit representation of (q out j-1 , b out j-1 , b dir j-1 ). Let D ∈ {0, 1} t+1+ log(t+1) match w in the first |w| bits, and be 0 elsewhere. Let {access j } j∈[t+1] be the memory access patterns of the t + 1 step programs P j run on D in sequence with inputs x j . Note that the hard-coded inputs do not affect the memory access pattern, so for all j ∈ [t + 1], access j can be computed as a function of the machine T , the challenge attribute w, and the time bound t.
The challenger samples a bit β ← {0, 1}, and computes the challenge ciphertext as follows.
1. The challenger sets a database D ∈ {0, 1} t+1+ log(t+1) . It sets the first |w| bits of D to match w, and sets the remaining log(t + 1) bits to 0. More formally,
where || denotes concatenation. It next garbles the database ( D, k D ) ← GData(1 λ , D).
3. Let P be the RAM program as described in Fig. 1. For each j ∈ [k + 1, t + 1], the challenger sets P j as P j := P [pp, {K
i,b } i,b , m β , j; {r
4. Let be the number of steps P takes to run on a database of length |D|. For each j ∈ [k + 1, t + 1], the challenger garbles the program P j , computing
For j ∈ [k], the challenger computes a simulated program
5. Next, it computes the ciphertexts ct
i,b as follows:
i,b ← SKE.Enc(K
),
← SKE.Enc(K
i] , 0)
6. Let {lab in,1 i } i be the set of input labels computed when simulating program P 1 . The challenger outputs the ciphertext
). This game is defined identically to Game k.1, except now IBE ciphertexts hardwired in the k-th simulated garbled program also encrypt only half of the corresponding SKE keys (as for first k -1 simulated programs). Below we simply describe the change in game description when compared with previous game.
• Challenge Phase: The adversary submits two challenge messages (m 0 , m 1 ) and the challenge attribute and time bound (w, 1 t ) to the challenger. It must be the case that the machine T for which the adversary was given a secret key sk T during the key query phase does not accept the word w within t steps. The challenger samples a bit β ← {0, 1}, and computes the challenge ciphertext as in Game k.1, except the following:
3. Let P be the RAM program as described in Fig. 1. For each j ∈ [k + 1, t + 1], the challenger sets P j as P j := P [pp, {K
i,b } i,b , m β , j; {r
). This game is defined identically to Game k.2, except now the SKE ciphertexts encrypting the garbled program labels for the (k + 1)-th garbled program encrypt only half of the label keys (i.e., only the label keys corresponding to the k-th state transition). Below we simply describe the change in game description when compared with previous game.
• Challenge Phase: The adversary submits two challenge messages (m 0 , m 1 ) and the challenge attribute and time bound (w, 1 t ) to the challenger. It must be the case that the machine T for which the adversary was given a secret key sk T during the key query phase does not accept the word w within t steps. The challenger samples a bit β ← {0, 1}, and computes the challenge ciphertext as in Game k.2, except the following:
5. Next, it computes the ciphertexts ct
i,b as follows:
i,b ← SKE.Enc(K
),
Analysis of game indistinguishability. We complete the proof by showing that adjacent hybrid games are indistinguishable. For any adversary A and game Game s, we denote by Adv A s (λ), the probability that A wins in Game s. For ease of exposition, in the sequel we use Game 0.3 to denote Game 0. Lemma 4.2. If IBE is a secure IBE scheme, then for any PPT adversary A and k ∈ [t + 1], we have that
for some negligible function negl(•).
Proof. Suppose for contradiction that A is a PPT adversary for which
, where is non-negligible. We give a reduction B which uses A to break the security of IBE. In particular, our reduction B will break the multi-challenge security of IBE.
The reduction algorithm B plays a game with an IBE challenger. The reduction B samples a bit β ← {0, 1}. The challenger chooses (pp, msk) ← IBE.Setup(1 λ ) and sends pp to B who forwards it to A. Next, A submits a key query for machine T to the reduction B. Let ID T denote the set of identities corresponding to machine T as per Eq. (1). B then makes a key query for every identity in ID T to the challenger, and let S denote set containing all the secret keys sent by the challenger to B. The reduction B then set sk T = S, and it sends sk T to A. Now, A submits two challenge messages (m 0 , m 1 ) and the challenge attribute and time bound (w, 1 t ) to B. The reduction B now computes the challenge ciphertext ct * as in Game k.1, except for how it computes the IBE ciphertexts which constitute the output of the k-th simulated program in step 3 of the challenge phase.
Let x k be the n + 2 bit representation of (q out k-1 , b out k-1 , b dir k-1 ), and let {K
as its challenge vector of message-identity tuples. (Recall that we are considering the multi-challenge version of IBE security.) Let {ct * i } i denote the set of challenge ciphertexts received by B. It then sets the ciphertexts ct
The remaining portion of the challenge ciphertext is computed as in Game k.1.
Finally, after sending the challenge ciphertext to A, the adversary outputs a bit γ. If γ = β, then B guesses 0 to the challenger signalling that ciphertexts {ct * i } i encrypt the PRF keys. Otherwise, B guesses 1 to the challenger signalling they encrypt all zeros. Observe that the reduction B perfectly simulates the view of Game k.1 and k.2 to A, respectively, depending upon the challenger's bit. Note that B is an admissible adversary as per the multi-challenge IBE game, since the adversary A makes only a single key query for machine T such that T does not accept w after t steps, and the IBE keys queried by B are completely disjoint with the set of challenge identities. Thus, the lemma follows. function negl(•), such that for every λ ∈ N, the following holds
Weak NCE for bit messages from PKE
In this section, we show a simple construction for weak NCE from regular public key encryption. We start with a public-key bit encryption scheme, and use it build a weak non-committing bit encryption scheme, that is M = {0, 1}. By a standard hybrid argument (i.e., the repitition scheme), one could extend it to encrypt multi-bit messages, but that has the limitation of key sizes growing linearly with the bit length of the messages. Later on we sketch a simple extension in the Random Oracle Model (ROM) [BR93] that avoids this key size limitation. Below we sketch a simple scheme wNCE from any plain public key bit encryption scheme PKE = (PKE.Setup, PKE.Enc, PKE.Dec).
Setup(1 λ ) → (pk, sk). The algorithm samples two independent public-secret key pairs (pk b , sk b ) ← PKE.Setup(1 λ ) for b ∈ {0, 1}, and a random bit β ← {0, 1}. It outputs the public-secret key pair as pk = (pk 0 , pk 1 ) and sk = (β, sk β ).
Enc(pk, m) → ct. Let pk = (pk 0 , pk 1 ). It encrypts m independently under both keys as ct b ← PKE.Enc(pk b , m) for b ∈ {0, 1}, and outputs the ciphertext ct = (ct 0 , ct 1 ).
Dec(sk, ct) → m. Let ct = (ct 0 , ct 1 ) and sk = (β, sk β ). It decrypts ct β using key sk β , and thus outputs the message as m ← PKE.Dec(sk β , ct β ).
Sim-Setup(1 λ ) → (pk, ct, t). The algorithm samples two independent public-secret key pairs (pk b , sk b ) ← PKE.Setup(1 λ ) for b ∈ {0, 1}, and a random bit δ ← {0, 1}. Next, it computes two PKE ciphertexts as ct b ← PKE.Enc(pk b , δ ⊕ b) for b ∈ {0, 1}, and outputs the ciphertext as ct = (ct 0 , ct 1 ), public key as pk = (pk 0 , pk 1 ), and trapdoor as t = (sk 0 , sk 1 , δ).
Sim-Open(t, m) → sk. Let t = (sk 0 , sk 1 , δ). It simply outputs the secret key as sk = (δ ⊕ m, sk δ⊕m ).
The correctness of the above scheme follows directly from the correctness of the underlying PKE system. For security, we could very easily reduce weak simulatability to semantic security of the underlying PKE system. We provide a brief proof sketch below.
Theorem A.2. If PKE is an IND-CPA secure public key bit encryption scheme, then wNCE scheme described above is a weakly simulation secure non-committing bit encryption scheme as per Definition A.1.
Proof sketch. The proof of weak simulation security follows mostly directly from the semantic security of the PKE system. First, observe that since δ is a random bit, thus δ ⊕ m is a random bit as well. Therefore, the distribution of secret keys is identical in both cases (honest and simulated). Next, observe that the only difference between honestly computed and simulated ciphertext is the way ciphertext component ct 1⊕δ⊕m is created. In the honest case, it encrypts message m honestly, whereas in the simulated case it encryption 1 ⊕ m. Now since the adversary never received the corresponding PKE secret key, thus a reduction could simply guess the message bit m that it has to be simulate and use semantic security of PKE to switch between honestly computed and simulated ciphertext. key-selective secure, and the wNCE scheme is weak simulation secure, then the resulting scheme is 1-query adaptively secure. Formally, we prove the following.
Theorem A.3. If sABE is a 1-query key-selective secure ABE scheme (Definition 2.3), and wNCE is a weakly simulation secure NCE scheme (Definition A.1), then the scheme ABE described above is 1-query fully secure ABE scheme (Definition 2.2) for the same message space and predicate class as sABE.
Proof. We start by dividing the adversary into two types. We say an adversay A is "Type-1" if it makes its challenge encryption query before making its key query. Otherwise we say it is "Type-2". Note that a Type-2 adversary is already an admissible adversary as per the key-selective ABE security game, thus for any Type-2 adversary, security of the above ABE scheme follows directly from the key-selective security of the underlying 1-query key-selective secure ABE scheme. Now for the case of Type-1 attackers, the proof of security following via a short sequence of hybrid games. Below we describe them more formally.
Game 0. This corresponds to the 1-query adaptive security for ABE as defined in Definition 2.2.
Game 1. This is same as the previous game, except now the challenger makes the following changes:
-it simulates the wNCE parameters during setup (i.e., (nce.pk, nce.ct, t) ← wNCE.Sim-Setup(1 λ )), instead of running the wNCE setup honestly;
-note that the adversary makes an encryption query before making its key query, thus the challenger computes the underlying ABE ciphertext honestly (i.e., abe.ct ← sABE.Enc(abe.pp, m b , (w, t)), where b is the challenge bit and rest of inputs are provided by the attacker), and "opens" the simulated ciphertext nce.ct to abe.ct as nce.sk ← wNCE.Sim-Open(t, abe.ct). It then responds with nce.ct as the challenge ciphertext, and when/if the adversary makes its key query, then the challenger samples the underlying ABE honestly as abe.sk T ← sABE.KeyGen(abe.msk, T ), and uses the simulated key nce.sk to respond to the key query as sk T = (nce.sk, abe.sk T ).
Let Adv A i (λ) denote the adversary A's advantage in Game i. To complete the proof, we prove the following lemmas.
Lemma A.4. If wNCE is a weakly simulation secure NCE scheme, then for any Type-1 PPT adversary A, we have that Adv A 0 (λ) -Adv A 1 (λ) ≤ negl(λ) for some negligible function negl(•). Proof. The proof of this lemma follows directly from the simulation security of the wNCE scheme.
Lemma A.5. If sABE is a 1-query key-selective secure ABE scheme, then for any Type-1 PPT adversary A, we have that Adv A 1 (λ) ≤ negl(λ) for some negligible function negl(•). Proof. The proof of this lemma follows directly from the key-selective security of the ABE scheme. Briefly, the reduction algorithm proceeds as follows. It receives the ABE public parameters abe.pp from the challenger, and simulates the wNCE parameters (nce.pk, nce.ct, t) at the beginning. It then sends (nce.pk, abe.pp) to A as the public key. Since A is a Type-1 attacker, thus it sends its challenge messages and attribute next. The reduction stores the challenge messages and attribute, and simply responds with nce.ct as the challenge ciphertext to A. Next, if/when A makes its only key query, then the reduction algorithm forwards it as its own key query to the challenger and receives the underlying ABE key abe.sk T . The reduction then forwards the challenge messages and attribute as its own challenge to the underlying ABE challenger. Let abe.ct * be the challenger's responce. The reduction then opens the simulated ciphertext to abe.ct * as nce.sk ← wNCE.Sim-Open(t, abe.ct * ), and sends (nce.sk, abe.sk T ) as the response to adversary's key query. Finally, A outputs its guess which the reduction forwards to its ABE challenger as its own guess.
First, note that the reduction algorithm is an admissible adversary as per the1-query key-selective security game since it makes its key query before asking for the challenge ciphertext. Thus, the reduction perfectly simulates Game 1 for any Type-1 adversary. Hence, the lemma follows.
Game : for ∈ [N ]. In the -th game, we modify how the challenge ciphertext ct * = {ct i } i∈[N ] is formed. Let I ⊂ [ ] consist of all i such that for two distinct j, j , i ∈ S j ∩ S j . If i ∈ I, then we replace ct i with the encryption of a random message. Otherwise ct i is computed as in Game 0. We now prove a sequence of lemmas showing that adjacent hybrid games are indistinguishable. For any adversary A and Game , we denote by Adv A (λ), the advantage of A in that game Game , where the advantage is A's success probability less 1/2. Lemma B.2. If sABE is a single key secure ABE scheme, then for any PPT adversary A and ∈ [N ], Adv A (λ) -Adv A -1 (λ) ≤ negl(λ) for some negligible function negl(•).
Proof. Observe that the difference between Game -1 and Game is in how the challenge ciphertext is generated. In particular, if is not contained in two distinct S j , S j sampled during the key query phase, then ct i is replaced with the encryption of a random message. In this case, since no machine queried accepts w within t steps, indistinguishability of the two games follows immediately from security of sABE, which holds since for the -th instance of the single key scheme A receives a single key. In the case that was sampled in two distinct S j , S j , the games are identical. The lemma follows.
Lemma B.3. Let c 1 , c 2 be as in Lemma B.1. If d > c 1 q 2 λ, N > c 2 q 4 λ, and |F| > N , for any PPT adversary A, Adv A N (λ) ≤ negl(λ) for some negligible function negl(•).
Proof. Let I ⊂ [N ] be defined as in Game N. Suppose that |I| ≤ d, and let p(•) be the polynomial sampled by the challenger during the challenge phase. Observe that the challenge ciphertext only consists of encryptions of d many points of p. Indeed, for all i ∈ I, ct i is independent of of m β , and all other ct i . Moreover, given up to d samples {(x i , p(x i ))} i∈I , p is not fully determined, and the constant term m β = p(0) remains information theoretically hidden. Thus, in this case ct * is independent of β and thus A has advantage 0. On the other hand, by Lemma B.1, |I| > d with probability exponentially small in λ. The lemma follows.
The q-query security of our scheme follows immediately from the above two lemmas.
C Garbled RAM: Iterated Simulation Security of [GHRW14a] Our ABE construction uses a Garbled RAM scheme GRAM which satisfies our notion of Iterated Simulation Security.
[GHRW14a] construct a basic Garbled RAM scheme which satisfies security with Unprotected Memory Access (UMA), a simulation based notion of security where simulator is given the memory access patterns of the programs being simulated. Using Oblivious RAM they then bootstrap this basic scheme to satisfy a stronger notion of full security. In this appendix we sketch the construction of the basic UMA secure scheme of [GHRW14a], and prove that it already satisfies Iterated Simulation Security. We review the required primitives before formally describing the scheme and then proving our security claim.
The scheme of [GHRW14a] uses a variant of IBE (in fact a variant of hierarchical IBE) which the authors name Timed IBE. Moreover, they show that Timed IBE can be constructed from any selectively-secure IBE scheme. We review the syntax and security definition here, and refer to [GHRW14a] for the construction and security proof. A Timed Identity-Based Encryption (TIBE) scheme TIBE for set of identity spaces I = {I λ } λ∈N and message spaces M = {M λ } λ∈N consists of five polynomial time algorithms (Setup, TimeGen, KeyGen, Enc, Dec) with the following syntax:
• Setup(1 λ ) → (pp, msk): The setup algorithm takes as input the security parameter λ. It outputs the public parameters pp and the master secret key msk.
• TimeGen(msk, j) → tsk j : The time-key generation algorithm takes as input the master secret key msk and an integer j ∈ N. It outputs a time secret key tsk j .
• KeyGen(tsk j , (j, v)) → sk (j,v) : The key generation algorithm takes as input a time secret key tsk j and an identity (j, v). It outputs a secret key sk (j,v) .
• Enc(pp, m, (j, v)) → ct: The encryption algorithm takes as input the public parameters pp, a message m ∈ M λ , and an identity (j, v). It outputs a ciphertext ct.
• Dec(sk (j,v) , ct) → m or ⊥: The decryption algorithm takes as input a secret key sk (j,v) and a ciphertext ct. It outputs either a message m ∈ M λ or a special symbol ⊥.
Correctness. We say a Timed IBE scheme TIBE = (Setup, TimeGen, KeyGen, Enc, Dec) satisfies correctness if for all λ ∈ N, (pp, msk) ← Setup(1 λ ), j ∈ N, m ∈ M λ , tsk j ← TimeGen(msk, j), sk (j,v) ← KeyGen(tsk j , (j, v)), and ct ← Enc(pp, m, (j, v)) the following holds:
Definition C.1. We say a timed IBE scheme TIBE = (Setup, KeyGen, Enc, Dec) is secure if for any PPT adversary A = (A 0 , A 1 , A 2 ) there exists a negligible function negl(•), such that for all λ ∈ N, the adversary's advantage Adv A (λ) ≤ negl(λ), where advantage of A is defined as
(t ∈ N, j * ∈ [t], (j * , v * ), S 0 , S, st 0 ) ← A 0 (1 λ ) (pp, msk) ← Setup(1 λ ); b ← {0, 1} tsk j ← TimeGen(msk, j) for j ∈ [0, t] sk (0,v) ← KeyGen(tsk 0 , v) for (0, v) ∈ S 0 sk (j,v) ← KeyGen(tsk j , v) for (j, v) ∈ S (st 1 , m 0 , m 1 ) = A 1 (pp, {sk (0,v) } (0,v)∈S0 , {sk (j,v) } (j,v)∈S , {tsk j } j>j * , st 0 ) ct ← Enc(pp, m b , (j * , v * ))
where the adversary may receive all time secret keys tsk j for times j > j * , an arbitrary set of identity secret keys for identities (0, v) where the time is 0, and precisely one secret key for identity (j, v) for all positive j ≤ j * . We additionally require that the adversary not receive a secret key for identity (j * , v * ).
The construction in [GHRW14a] also uses a Garbled Circuit scheme which allows for specifying labeled outputs. A Garbled Circuit scheme with output labels allows the garbling algorithm to accept as input a collection of output labels for the output wires to the circuit being garbled. More formally a scheme GC for circuit classes C = {C λ } λ∈N consists of two polynomial time algorithms (GC.Garble, GC.Eval) with the following syntax: GProg(1 λ , k D , 1 m , P, 1 n , (t init , t fin )) → ( P , {lab in i,b }): The algorithm parses the key as k D = (pp, msk), and parses the program as P = {C P RAM j } j∈[t init ,t fin ] . We assume the state input (and updated state output) for each step program will be of length n. For each j, the algorithm chooses tsk j ← TimeGen(msk, j). For each step circuit C P RAM j we define an augmented step circuit C P RAM j+ . The augmented step circuit will have hard-coded the public paramters pp, the time secret key tsk j , the labels lab 0 , lab 1 , and randomness strings r, r 0 , r 1 . We define the augmented step circuit
RAM j+ [pp, tsk j , lab 0 , lab 1 , r, r 0 , r 1 ](state, b read ) which takes as input an n bit long state state and read bit b read . The circuit C P RAM j+ computes as follows:
1. The circuit computes (state , i read , i write , b write ) := C P RAM j (state, b read ) 2. If (i write , b write ) = ⊥, the circuit computes sk (j,id) := KeyGen(tsk j , (j, id))
where id = (i write , b write ) and sets sk write = sk (j,id) . If (i write , b write ) = ⊥, the circuit sets sk write = ⊥.
3. Let u = WriteTime(j, state, i read ), be the largest time u < j such that location i read was written to at time u. where for each b, id b = (i read , b). 4. The circuit outputs (state , i read , i write , sk write , ct 0 , ct 1 ) Now, the algorithm garbles the augmented versions of the step circuits {C P RAM j } t init ≤j≤t fin . Let ρ 1 , ρ 2 be the number of random bits used by the algorithms KeyGen(•) and Enc(•) respectively. Starting with j = t fin and counting down to j = t init , the algorithm proceeds as follows.
1. The algorithm computes a set lab out,j of output labels. If j = t fin , then it sets lab out,j so that the updated state output (which is simply the output y of the program) is given in the clear, and the labels for the other outputs are set to ⊥. If j = t fin it sets lab out,j so that the output labels for the updated state output (i.e. for the first n output wires) match the input labels {lab i b,j+1 } i∈n b∈{0,1}
for the first n input wires of C P RAM (j+1)+ . The labels for all other outputs are set so that they are given in the clear. 2. The algorithm computes hard-coded inputs. It chooses tsk j ← TimeGen(msk, j). It sets lab 0 := lab n+1 0,j+1 and lab 1 := lab n+1 1,j+1 to be the labels for the last input wire of C P RAM (j+1)+ . Finally, it chooses randomness strings r ← {0, 1} ρ1 and for each b ∈ {0, 1} it chooses r b ← {0, 1} ρ2 . 3. The algorithm sets the augmented step circuit as C P RAM j+ := C P RAM j+ [pp, tsk j , lab 0 , lab 1 , r, r 0 , r 1 ] and then it garbles the circuit The challenger computes (y 1 , . . . , y ) ← (P 1 (x 1 ), . . . , P (x )) D . For each k the challenger computes access k to be memory access pattern of the k th program.
• Data Garbling: The challenger chooses (pp, msk) ← Setup(1 λ ). It then chooses tsk 0 ← TimeGen(msk, 0), and for each i ∈ m it chooses sk (0,idi) ← KeyGen(tsk 0 , (0, id i ))
where for each i ∈ [|D|], id i = (i, D[i]). The challenger sets D := {sk 0,idi } i∈[|D|] as the garbled database, and k D := (pp, msk) as the program garbling key.
• Honest Garbling: For k > a, the challenger honestly garbles the k th program P k . In particular, for each k ∈ [a + 1, ], the challenger computes
• Program a: The challenger parses the a th program as P a = {C Pa RAM j } j∈[t init,a ,t fin,a ] . Let ρ 1 , ρ 2 be the number of random bits used by the algorithms KeyGen(•) and Enc(•) respectively. Starting with j = t fin,a and counting down to j = t init,a , the challenger proceeds as follows.
1. The challenger computes a set lab out,j of output labels. If j = t fin,a , then it sets lab out,j so that the updated state output (which is simply the output y a of the program) is given in the clear, and the labels for the other outputs are set to ⊥. If j = t fin,a it sets lab out,j so that the output labels for the updated state output (i.e. for the first n output wires) match the input labels {lab i b,j+1 } i∈na b∈{0,1}
for the first n a input wires of C Pa RAM (j+1)+ . The labels for all other outputs are set so that they are given in the clear.
As we later show, such a core encryption scheme with such simple and weak security guarantees could be generically amplified to better and more general bounded collusion security guarantees.
Recall that in this work we require the encryptor to provide an upper bound on the running time of the TM.
Since the number of states is polynomially bounded, thus this is efficient.
For the purposes of a technical overview, we significantly simplify and relax the notation. Here we consider each program to be of fixed length, and not take time range among other things as additional inputs. Later in the main body, we define it in full generality.
Since the ciphertexts need only be decryptable by keys whose corresponding TMs accept the word within time t, thus the encryptor only needs to instantiate the database with t bits of memory. To be fully accurate, we actually a little more memory for storing the TM state which we discuss later in the main body.
Although prior works [LO13, GHRW14a, LO14, GHL + 14, GHRW14b, GLOS15, GLO15, KLW15, BCG + 18] have studied other adaptive and reusable variants of garbled RAM security notions, our notion of iterated simulation security has not yet been explicitly studied previously to the best of our knowledge.
In regular notions of non-committing encryption, the simulator must also be able to indistinguishably explain the ciphertexts by providing encryption randomness too. We do not require that, thus regard our notion as a weak NCE system. Our notion is similar to that of receiver non-committing encryption[CHK05].
Here we write {L, R} to denote the set of directions left and right.
We point out that the challenger does not need use all the sampled random coins and secret keys anymore. However, for ease of exposition we still sample all of them as before.
Since the size of ciphertexts in a ABE system for TMs is not a-priori bounded, thus we rely on a weak NCE scheme with unbounded length messages. However, if the size of ciphertexts is a-priori bounded, then one could simply rely on a wNCE scheme for fixed length messages (that is, implied by regular PKE itself).
Before applying this transformation, we amplify the security of our construction to 1-query adaptive security via the weak NCE approach described in Appendix A.
We could have also used the template by Itkis et al. [ISV + 17] to perform desired amplification.