Cryptography with Updates

Abstract

Starting with the work of Bellare, Goldreich and Goldwasser [CRYPTO’94], a rich line of work has studied the design of updatable cryptographic primitives. For example, in an updatable signature scheme, it is possible to efficiently transform a signature over a message into a signature over a related message without recomputing a fresh signature.

In this work, we continue this line of research, and perform a systematic study of updatable cryptography. We take a unified approach towards adding updatability features to recently studied cryptographic objects such as attribute-based encryption, functional encryption, witness encryption, indistinguishability obfuscation, and many others that support non-interactive computation over inputs. We, in fact, go further and extend our approach to classical protocols such as zero-knowledge proofs and secure multiparty computation.

To accomplish this goal, we introduce a new notion of updatable randomized encodings that extends the standard notion of randomized encodings to incorporate updatability features. We show that updatable randomized encodings can be used to generically transform cryptographic primitives to their updatable counterparts.

We provide various definitions and constructions of updatable randomized encodings based on varying assumptions, ranging from one-way functions to compact functional encryption.

P. Ananth—Work done in part while visiting the Simons Institute for Theoretical Computer Science, supported by the Simons Foundation and and by the DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467. This work was partially supported by grant #360584 from the Simons Foundation.

A. Cohen—Supported in part by NSF MACS CNS-1413920, DARPA IBM W911NF-15-C-0236, and Simons Investigator Award Agreement Dated 6-5-12.

A. Jain—Work done in part while visiting the Simons Institute for Theoretical Computer Science, supported by the Simons Foundation and and by the DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467. Supported in part by a DARPA/ARL Safeware Grant W911NF-15-C-0213 and NSF CNS-1414023.

1 Introduction

The last decade has seen the advent of a vast array of advanced cryptographic primitives such as attribute-based encryption [45, 55], predicate encryption [20, 43, 47, 57], fully homomorphic encryption [36], fully homomorphic signatures [7, 17, 44], functional encryption [19, 41, 54, 55], constrained pseudorandom functions [21, 22, 48], witness encryption [34, 38], witness PRFs [60], indistinguishability obfuscation [9, 32], and many more. Most of these primitives can be viewed as “cryptographic circuit compilers” where a circuit C can be compiled into an encoding $\langle C \rangle$ and an input x can be encoded as $\langle x \rangle$ such that they can be evaluated together to compute C(x). For example, in a functional encryption scheme, circuit compilation corresponds to the key generation process whereas input encoding corresponds to encryption. Over the recent years, cryptographic circuit compilers have revolutionized cryptography by providing non-interactive means of computing over inputs/data.

A fundamental limitation of these circuit compilers is that they only support static compilation. That is, once a circuit is compiled, it can no longer be modified. In reality, however, compiled circuits may need to undergo several updates over a period of time. For example, consider an organization where each employee is issued a decryption key $SK_{P}$ of an attribute-based encryption scheme where the predicate P corresponds to her access level determined by her employment status. However, if her employment status later changes, then we would want to update the predicate P associated with her decryption key. Known schemes, unfortunately, do not support this ability.

Motivated by the necessity of supporting updates in applications, in this work, we study and build dynamic circuit compilers. In a dynamic circuit compiler, it is possible to update a compiled circuit $\langle C \rangle$ into another compiled circuit $\langle C' \rangle$ by using an encoded update string whose size only depends on the “difference” between the plaintext circuits C and $C'$. For example, if the difference between C and $C'$ is simply a single gate change, then this should be reflected in the size of the encoded update. Note that this rules out the trivial solution of simply releasing a new compiled circuit at the time of update.

Background: Incremental Cryptography. The study of cryptography with updates was initiated by Bellare, Goldreich and Goldwasser [10] under the umbrella of incremental cryptography. They studied the problem of incremental digital signatures, where given a signature of a message m, it should be possible to efficiently compute a signature of a related message $m'$, without having to recompute the signature of $m'$ from scratch. Following their work, the study of incremental cryptography was extended to other basic cryptographic primitives such as encryption and hash functions [10,11,12, 24, 31, 52, 53], and more recently, indistinguishability obfuscation [5, 35].

Our Goal. In this work, we continue this line of research, and perform a systematic study of updatable cryptographic primitives. We take a unified approach towards adding updatability features to recently studied primitives such as attribute-based encryption, functional encryption and more generally, cryptographic circuit compilers. We, in fact, go further and also study updatability for classical protocols such as zero-knowledge proofs and secure multiparty computation.

To accomplish this goal, we introduce a new notion of updatable randomized encodings that extends the standard notion of randomized encoding [46] to incorporate updatability features. We show that updatable randomized encodings can be used to generically transform cryptographic primitives (discussed above) to their updatable counterparts.

Updatable Randomized Encodings. The notion of randomized encoding [46] allows one to encode a “complex” computation C(x) into a “simple” randomized function ${\mathsf {Encode}}(C,x;r)$ such that given the output $\langle C(x) \rangle$ of the latter, it is possible to recover the value C(x) (by running a public ${\mathsf {Decode}}$ algorithm) but it is impossible to learn anything else about C or x. The typical measure of complexity studied in the literature is parallel-time complexity or circuit depth. Such randomized encodings are known to exist for general circuits based on only the existence of one-way functions [6] (also referred to as Yao’s garbled circuits [59], where ${\mathsf {Encode}}(C,x;r)$ is in ${{\mathbf {N}}}{{\mathbf {C}}}^1$).

In this work, we study updatable randomized encodings ($\mathsf {URE}$): given a randomized encoding $\langle C(x) \rangle$ of C(x), we want the ability to update it to an encoding $\langle C'(x') \rangle$ of $C'(x')$, where $C'$ and $x'$ are derived from C and x by applying some “update” ${\mathbf {u}}$. For now, we may think of this update as some small modification to the circuit or input (e.g., change the output gate of C to AND and the second bit of x to 1). We require that the update ${\mathbf {u}}$ can be encoded as $\langle {\mathbf {u}} \rangle$ which can then be used to transform $\langle C(x) \rangle$ into $\langle C'(x') \rangle$, a randomized encoding of $C'(x')$. A bit more precisely, a $\mathsf {URE}$ scheme consists of the following algorithms:

• ${\mathsf {Encode}}(C,x)$ takes as input a circuit C and an input x, and outputs an encoding $\langle C(x) \rangle$ and a secret state ${\mathsf {st}}$.

• ${\mathsf {GenUpd}}({\mathsf {st}},{\mathbf {u}})$ takes as input an update ${\mathbf {u}}$, and outputs an encoded update $\langle {\mathbf {u}} \rangle$ and a possibly updated state ${\mathsf {st}}'$.

• $\mathsf {ApplyUpd}\left( \langle C(x) \rangle ,\langle {\mathbf {u}} \rangle \right)$ takes as input a randomized encoding $\langle C(x) \rangle$ and an update encoding $\langle {\mathbf {u}} \rangle$, and outputs an (updated) encoding $\langle C'(x') \rangle$.

• ${\mathsf {Decode}}\left( \langle C(x) \rangle \right)$ takes as input a (possibly updated) randomized encoding $\langle C(x) \rangle$, and outputs the value $y=C(x)$.

If we make no additional requirements, the above could be easily achieved. For instance, let ${\mathsf {Encode}}$ output the state ${\mathsf {st}}= (C,x)$, and let ${\mathsf {GenUpd}}$ – which now has access to C and x from ${\mathsf {st}}$ in addition to the update ${\mathbf {u}}$ – compute the updated $C'$ and $x'$ directly and output a as the encoded update $\langle {\mathbf {u}} \rangle$ the standard randomized encoding of $\langle C'(x') \rangle$. $\mathsf {ApplyUpd}$ would correspondingly output $\langle {\mathbf {u}} \rangle = \langle C'(x') \rangle$. The drawback of this approach is that a fresh randomized encoding is computed during every evaluation of ${\mathsf {GenUpd}}$, irrespective of whether ${\mathbf {u}}$ constitutes a minute or significant change to the underlying C and x.

Our key efficiency requirement is that the running time of the ${\mathsf {GenUpd}}$ algorithm must be a fixed polynomial size of the update (and a security parameter), and independent of the size of the circuit and input being updated. This, in particular, implies that the size of an update encoding $\langle {\mathbf {u}} \rangle$ is also a fixed polynomial in the size of ${\mathbf {u}}$ (and the security parameter).

The above discussion immediately generalizes to the setting of multiple sequential updates.¹ Let $\langle C_0(x_0) \rangle$ denote an initial randomized encoding. Let ${\mathbf {u}}_1,\ldots ,{\mathbf {u}}_n$ denote a sequence of updates and let $\langle {\mathbf {u}}_i \rangle$ denote an encoding of ${\mathbf {u}}_i$. In a $\mathsf {URE}$ scheme for multiple updates, $\langle C_0(x_0) \rangle$ can be updated to $\langle C_1(x_1) \rangle$ using $\langle u_1 \rangle$; the result can then be updated into $\langle C_2(x_2) \rangle$ using $\langle u_2 \rangle$, and so on, until we obtain $\langle C_n(x_n) \rangle$. We allow the number of updates n to be an arbitrary polynomial in the security parameter.

Within this framework, two distinct notions naturally arise.

 

URE with multiple evaluations::

Every intermediate encoding $\langle C_i(x_i \rangle$ can be decoded to obtain $C_i(x_i)$. For security, we require that given an initial randomized encoding $\langle C_0(x_0) \rangle$ and a sequence of encoded updates $\{\langle {\mathbf {u}}_i \rangle \}_{i=1}^{n}$, an adversary can learn only the outputs $\{C_i(x_i)\}_{i=0}^{n}$, and nothing else.

URE with single evaluation::

Only the final encoding $\langle C_n(x_n) \rangle$ can be decoded. To enable this, we will consider an augmented decoding algorithm that additionally requires an “unlocking key.”² This unlocking key is provided after all the updates are completed, allowing the user to decode the final encoding, but preventing her from decoding any intermediate values. For security, we require that given an initial randomized encoding $\langle C_0(x_0) \rangle$ and a sequence of encoded updates $\{\langle {\mathbf {u}}_i \rangle \}_{i=1}^{n})$, an adversary can only learn the final output $C_n(x_n)$, and nothing else.

Except where otherwise specified, we use $\mathsf {URE}$ to mean the multiple-evaluation variant. For both conceptual reasons and to minimize confusion, we in fact consider an alternative but equivalent formulation of single-evaluation $\mathsf {URE}$ which we call updatable garbled circuits ($\mathrm {UGC}$). A garbled circuit [59] is a “decomposable” randomized encoding, where a circuit C and an input x can be encoded separately. In an updatable garbled circuit scheme, given an encoding $\langle C_0 \rangle$ of a circuit $C_0$ and a sequence of update encodings $\langle {\mathbf {u}}_1 \rangle ,\ldots ,\langle {\mathbf {u}}_n \rangle$, it is possible to compute updated circuit encodings $\langle C_1 \rangle ,\ldots ,\langle C_n \rangle$, where $C_i$ is derived from $C_{i-1}$ using ${\mathbf {u}}_i$. Once all the updates are completed, an encoding $\langle x \rangle$ for an input x is released. This input encoding can then be used to decode the final circuit encoding $\langle C_n \rangle$ and learn $C_n(x_n)$. Intuitively, the input encoding can be viewed as the unlocking key in single-evaluation $\mathsf {URE}$.

It is easy to see that $\mathrm {UGC}$ is a weaker notion than multi-evaluation $\mathsf {URE}$. In particular, since $\mathrm {UGC}$ only allows for decoding “at the end,” it remains single-use, while multi-evaluation $\mathsf {URE}$ captures reusability.

We find the notions of $\mathsf {URE}$ and $\mathrm {UGC}$ to be of interest from a purely complexity-theoretic perspective. Further, as we discuss later, they have powerful applications to updatable cryptography.

1.1 Our Results

In this work, we initiate the study of updatable randomized encodings. We study both simulation and indistinguishability-based security definitions and obtain general positive results. We showcase $\mathsf {URE}$ as a central object for the study of updatable cryptography by demonstrating applications to other updatable cryptographic primitives. The technical ideas we develop for our constructions are quite general, and may be applicable to future works on updatable cryptography.

Multi-evaluation URE for General Updates. Before stating our positive results for multi-evaluation $\mathsf {URE}$, we first informally describe which classes of updates we can support. An update ${\mathsf {Update}}\in {\mathcal {U}}$ represents some way to modify any circuit C and an input x to some modified circuit $C'$ and input $x'$. We denote by ${\mathbf {u}}$ the procedure $(C',x')\leftarrow {\mathbf {u}}(C,x,{\mathsf {Update}})$ which applies the update to C and x. We consider all ${\mathcal {U}}$ and ${\mathsf {Update}}$ subject to two restrictions: (1) ${\mathsf {Update}}$ is computed by a (family) of circuits, one for every circuit size |C|, and (2) ${\mathsf {Update}}$ preserves circuit size (i.e., $|C| = |C'|$). We refer to this very broad class of updates as general circuit updates.

For general circuit updates, we construct $\mathsf {URE}$ from compact functional encryption. The summary below focuses on indistinguishability-based security, and concludes with a remark on achieving simulation-based security.

Theorem 1

(Informal). Assuming the existence of secret-key, compact functional encryption supporting a single key query and B ciphertexts, there exists a multi-evaluation $\mathsf {URE}$ scheme supporting B sequential general circuit updates.

A compact functional encryption is one where the running time of the encryption algorithm for a message m is a fixed polynomial in the size of m and the security parameter, and independent of the complexity of the function family supported by the FE scheme.

For the case of unbounded updates, a recent work of Bitansky et al. [14] shows that secret-key compact functional encryption with unbounded-many ciphertexts implies exponentially-efficient indistinguishability obfuscation (XIO) [49]. Put together with the results of [49] and [3, 15], it shows that sub-exponentially secure secret-key compact FE that supports a single function key query together with the learning with errors (LWE) assumption implies indistinguishability obfuscation.

In contrast, in Theorem 1, we require secret-key compact FE with only polynomial security. Such an FE scheme can be based on polynomial-hardness assumptions on multilinear maps using the results of [33] and [4, 15].

For the case of polynomially-bounded updates, we can, in fact, relax our assumption to only one-way functions. We obtain this result by using a stateful single-key compact secret-key FE scheme for an a priori bounded number B of ciphertexts. A stateful single-key compact secret-key FE scheme can be constructed from garbled circuits: a functional key consists of B garbled circuits, $i^{th}$ ciphertext consists of garbled wire keys corresponding to the $i^{th}$ garbled circuit. This FE scheme is stateful since the encryption algorithm needs to store how many messages it has encrypted so far.

Plugging in such an FE scheme in Theorem 1 yields the following corollary.

Corollary 1

(Informal). Assuming one-way functions, for any fixed polynomial B, there exists a multi-evaluation $\mathsf {URE}$ scheme supporting B sequential general circuit updates.

On the necessity of functional encryption. It is natural to ask whether secret-key compact FE is necessary for building multi-evaluation $\mathsf {URE}$ with unbounded updates. We show that if a (multi-evaluation) $\mathsf {URE}$ scheme is output compact, then it implies XIO. Put together with the result of [49], we have that a $\mathsf {URE}$ scheme with output compactness together with LWE implies a public-key compact FE scheme that supports a single key query.

Theorem 2

(Informal). Assuming LWE, a multi-evaluation $\mathsf {URE}$ scheme with unbounded output-compact updates implies a public-key compact FE scheme that supports a single key query.

In an output-compact $\mathsf {URE}$ scheme, the running time of the ${\mathsf {GenUpd}}$ algorithm is independent of the output length of the updated circuit. We remark that the $\mathsf {URE}$ scheme obtained from Theorem 1 is, in fact, output compact. Our construction in Theorem 1 is in this sense tight.

On output compactness. We study both indistinguishability and simulation-based security notions for $\mathsf {URE}$. In the context of FE, it is known from [1, 26] that simulation-secure FE with output compactness is impossible for general functions. We observe that the same ideas as in [1, 26] can be used to establish impossibility of simulation-secure $\mathsf {URE}$ with output compact updates.

However, when we consider indistinguishability-based security, $\mathsf {URE}$ with output compact updates is indeed possible. The results in Theorem 1 and Corollary 1 are stated for this case. Furthermore, using the trapdoor circuits technique of [26], one can generically transform output-compact $\mathsf {URE}$ with indistinguishability security to non-output-compact $\mathsf {URE}$ with simulation-based security.

Updatable garbled circuits with gate-wise updates. We now turn to updatable garbled circuits, an alternate formulation of single-evaluation $\mathsf {URE}$. We consider the family of gate-wise updates, where an update ${\mathbf {u}}$ can modify a single gate of a circuit or add or delete a gate. Below, we consider the case of unbounded updates and bounded updates separately.

$\mathrm {UGC}$ with Unbounded Updates from Lattice Assumptions. Our first result is a construction of $\mathrm {UGC}$ for general circuits that supports an unbounded number of sequential updates from the family of gate-wise updates. We build such a scheme from worst-case lattice assumptions.

Theorem 3

(Informal). Let ${\mathcal {C}}$ be a family of general circuits. Assuming the hardness of approximating either GapSVP or SIVP to within sub-exponential factors, there exists a $\mathrm {UGC}$ scheme for ${\mathcal {C}}$ that supports an unbounded polynomial number of sequential gate-wise updates.

We defer the proof of this theorem to the full version. [2] At the heart of this result is a new notion of puncturable symmetric proxy re-encryption scheme that extends the well-studied notion of proxy re-encryption [16]. In a symmetric proxy re-encryption scheme, for any pair of secret keys ${{\mathsf {S}}}{{\mathsf {K}}}_1$, ${{\mathsf {S}}}{{\mathsf {K}}}_2$, it is possible to construct a re-encryption key ${{\mathsf {R}}}{{\mathsf {K}}}_{1\rightarrow 2}$ that can be used to publicly transform a ciphertext w.r.t. ${{\mathsf {S}}}{{\mathsf {K}}}_1$ into a ciphertext w.r.t. ${{\mathsf {S}}}{{\mathsf {K}}}_2$. In our new notion of puncturable proxy re-encryption, re-encryption keys can be “disabled” on ciphertexts ${{\mathsf {C}}}{{\mathsf {T}}}^*$ (w.r.t. ${{\mathsf {S}}}{{\mathsf {K}}}_1$) s.t. the semantic security of ${{\mathsf {C}}}{{\mathsf {T}}}^*$ holds even if the adversary is given the punctured key ${{\mathsf {R}}}{{\mathsf {K}}}_{1\rightarrow 2}^{{{\mathsf {C}}}{{\mathsf {T}}}^*}$ and ${{\mathsf {S}}}{{\mathsf {K}}}_2$. We give a construction of such a scheme based on the hardness of approximating either GapSVP or SIVP to within sub-exponential factors.

Given the wide applications of proxy re-encryption (see, e.g., [8] for a discussion), we believe that our notion of puncturable proxy re-encryption is of independent interest and likely to find new applications in the future.

UGC with Bounded Updates from One-Way Functions. For the case of a polynomially-bounded number of updates, we can relax our assumption to only one-way functions. We obtain this result by using a puncturable PRF scheme that can be based on one-way functions [40, 56].

Theorem 4

(Informal). Let ${\mathcal {C}}$ be a family of general circuits, and $\lambda$ be a security parameter. Assuming one-way functions, for any fixed polynomial p, there exists a $\mathrm {UGC}$ scheme for ${\mathcal {C}}$ that supports $p(\lambda )$ sequential gate-wise updates. The size of the initial garbled circuit as well as each update encoding is independent of p. However, the initial circuit garbling time and update generation time grows with p.

The construction of this scheme is quite simple and does not require a puncturable proxy re-encryption scheme. We provide an informal description of this scheme in the technical overview Sect. 2.1.

Applications. We next discuss applications of our results.

Updatable Primitives with IND security. We start by discussing application of multi-evaluation $\mathsf {URE}$ to dynamic circuit compilers. Here, we demonstrate our main idea by a concrete example, namely, by showing how to use $\mathsf {URE}$ to transform any (key-policy) attribute-based encryption (ABE) scheme into updatable ABE. The same idea can be used in a generic way to build dynamic circuit compilers and obtain updatable functional encryption, updatable indistinguishability obfuscation, and so on. We refer the reader to the full version [2] for the general case.

We briefly describe a generic transformation from any ABE scheme to one where the policies associated with secret keys can be updated. The setup and encryption algorithms for the updatable ABE scheme are the same as in the underlying ABE scheme. The key generation algorithm in the updatable ABE scheme works as follows: to compute an attribute key for a function f, we compute a $\mathsf {URE}$ $\langle C_f \rangle$ of a circuit $C_f$ where C runs the key generation algorithm of the underlying ABE scheme using function f and outputs a key ${{\mathsf {S}}}{{\mathsf {K}}}_f$. To decrypt a ciphertext, a user can first decode $\langle C_f \rangle$ to compute ${{\mathsf {S}}}{{\mathsf {K}}}_f$ and then use it to decrypt the ciphertext.

In order to update an attribute key for a function f to another key for function $f'$, we can simply issue an update encoding $\langle {\mathbf {u}} \rangle$ for $\langle C_f \rangle$ where ${\mathbf {u}}$ captures the modification from f to $f'$. To compute the updated attribute key, a user can first update $\langle C_f \rangle$ using $\langle {\mathbf {u}} \rangle$ to obtain $\langle C_{f'} \rangle$, and then decode it to obtain an attribute key ${{\mathsf {S}}}{{\mathsf {K}}}_{f'}$ for $f'$.

Let us inspect the efficiency of updates in the above updatable ABE scheme. As in $\mathsf {URE}$, we would like the size (as well as the generation time) of an update encoding here to be independent of the size of the updated function. Note, however, that the output of the updated function $C_{f'}$ is very large – an entire attribute key ${{\mathsf {S}}}{{\mathsf {K}}}_{f'}$! Thus, in order to achieve the aforementioned efficiency, we require that the $\mathsf {URE}$ scheme has updates with output compactness.

Recall that $\mathsf {URE}$ with output compact updates is only possible with indistinguishability based security. As such, the above idea is only applicable to cryptographic primitives with indistinguishability-based security.

Updatable Primitives with SIM security. Next, we discuss applications of $\mathsf {URE}$ to cryptographic primitives with simulation-based security. In the main body of the paper, we describe two concrete applications, namely, updatable non-interactive zero-knowledge proofs (UNIZK) and updatable multiparty computation (UMPC). A notable feature of these constructions is that they only require a $\mathsf {URE}$ scheme with non-output-compact updates and simulation-based security. Below, we briefly describe our main idea for constructing UNIZKs.

Let (x, w) denote an instance and witness pair for an ${\mathbf{N }}{\mathbf{P }}$ language L. Let ${\mathbf {u}}$ denote an update that transforms (x, w) to another valid instance and witness pair $(x',w')$. In a UNIZK proof system for L, it should be possible for a prover to efficiently compute an encoding $\langle {\mathbf {u}} \rangle$ of ${\mathbf {u}}$ that allows a verifier to transform a valid proof $\pi$ for x into a proof $\pi '$ for $x'$ and verify its correctness.

We now briefly describe our transformation. A proof $\pi$ for (x, w) in the UNIZK scheme is computed as follows: we first compute a $\mathsf {URE}$ $\langle C_{x,w} \rangle$ for a circuit $C_{x,w}$ that checks whether (x, w) satisfies the ${\mathbf{N }}{\mathbf{P }}$ relation associated with L and outputs 1 or 0 accordingly. Furthermore, we also compute a regular NIZK proof $\phi$ to prove that $\langle C_{x,w} \rangle$ is computed “honestly.” To verify $\pi =(\langle C_{x,w} \rangle ,\phi )$, a verifier first verifies $\phi$ and if the check succeeds, it decodes $\langle C_{x,w} \rangle$ and outputs its answer.

In order to update a proof $\pi$, we can simply issue an update encoding $\langle {\mathbf {u}} \rangle$ for the randomized encoding $\langle C_{x,w} \rangle$, along with a regular NIZK proof $\phi '$ that $\langle {\mathbf {u}} \rangle$ was computed honestly. Upon receiving the update $(\langle {\mathbf {u}} \rangle ,\phi ')$, a verifier can first verify $\phi '$ and then update $\langle C_{x,w} \rangle$ using $\langle {\mathbf {u}} \rangle$ to obtain $\langle C_{x',w'} \rangle$. Finally, it can decode the updated $\mathsf {URE}$ $\langle C_{x',w'} \rangle$ to learn whether $x'$ is in the language L or not.

It should be easy to see that the above idea can, in fact, be also used to make interactive zero-knowledge proofs updatable. Finally, we note that the above is a slightly oversimplified description and we refer the reader to the full version [2] for further details on UNIZK and UMPC, respectively.

1.2 Related Work

Incremental Cryptography. The area of incremental cryptography was pioneered by Bellare, Goldreich and Goldwasser [10]. While their work dealt with signature schemes, the concept of incremental updates has been subsequently studied for other basic cryptographic primitives such as hash functions, semantically-secure encryption and deterministic encryption [11, 24, 31, 52, 53]. To the best of our knowledge, all of these works only consider bit-wise updates, in which a single bit of the message is modified.

While our work shares much in spirit with these works, we highlight one important difference. In incremental cryptography, update operation is performed “in house,” e.g., in the case of signatures, the entity who produces the original signature also performs the update. In contrast, we consider a client-server scenario where the client simply produces an update encoding, and the actual updating process is performed by the server. This difference stipulates different efficiency and security requirements. On the one hand, incremental cryptography necessarily requires efficient updating time for the notion to be non-trivial, while we consider the weaker property of efficient update encoding generation time. On the other hand, our security definition is necessarily stronger since we allow the adversary to view the update encodings – a property not necessary when the updating is done “in house.”

Incremental/Patchable Obfuscation. Recently, [35] and [5] study the notion of updatability in the context of indistinguishability obfuscation. The work of [35] considers incremental (i.e., bit-wise) updates, while [5] allow for arbitrary updates, including those that may increase the size of the program (modeled as a Turing machine).

We note that one of our results, namely, $\mathsf {URE}$ with unbounded updates can be derived from [5] at the cost of requiring sub-exponentially secure ${{\mathsf {i}}}{{\mathsf {O}}}$. In contrast, we obtain our result by using polynomially secure secret-key compact FE.

Malleable NIZKs. Our notion of updatable NIZKs should be contrasted with the notion of malleable NIZKs proposed by Chase et al. [28]. In a malleable NIZK, it is possible to publicly “maul” a proof string $\pi$ for a statement x into a a proof string $\pi '$ for a related statement $x'$. In contrast, our notion of $\mathsf {UNIZK}$ only allows for privately generated updates. To the best of our knowledge, malleable NIZKs are only known either for a limited class of update relations from standard assumptions [28], or for general class of update relations based on non-falsifiable assumptions such as succinct non-interactive arguments [29]. In contrast, we show how to build $\mathsf {UNIZK}$ for unbounded number of general updates from compact secret-key FE and regular NIZKs, and for a bounded number of general updates from regular NIZKs.

Updatable Codes. The concept of updating was also studied in the context of error correcting codes by [27]. In this context, it is difficult to model the problem of updating – we should be able to change few bits of the code to correspond to a codeword of a different message and at the same time we want the distance between codewords of different messages to be far apart. We refer the reader to their work for discussion on this seemingly contradictory requirement. In a subsequent work, [30] studied this problem in the context of non-malleable codes.

2 Our Techniques

We start with the construction of $\mathrm {UGC}$ and present the main ideas underlying the construction. We then build upon the intuition developed in the construction of $\mathrm {UGC}$, to construct (multi-evaluation) $\mathsf {URE}$.

2.1 Construction of UGC

Below, we restrict our discussion to updates that correspond to a gate change.

A Lock-and-Release Mechanism for Single Update. Let us first start with the simpler goal of building a $\mathrm {UGC}$ scheme that supports updating a single gate. Let C be a circuit comprised of s-many gates $C^1$,...,$C^s$. Our starting idea towards a $\mathrm {UGC}$ scheme with single update is as follows: in order to garble C, we simply compute a garbling of C using a standard gate-by-gate garbling scheme such as [59].³ We denote by ${{\langle {C}\rangle }_{{\mathsf {gc}}}}$ the garbled circuit for C, and by ${{\langle {C}\rangle }^{i}_{{\mathsf {gc}}}}$ the garbled gate corresponding to gate $C^i$. Encrypt each garbled gate, and output the resulting ciphertexts ${{\mathsf {C}}}{{\mathsf {T}}}_1,\ldots ,{{\mathsf {C}}}{{\mathsf {T}}}_{s}$.

Now, suppose we wish to update garbling of C to garbling of $C'$ where $C'$ only differs from C in the first gate. Then, a natural idea is to release a decryption key that only decrypts the ciphertexts ${{\mathsf {C}}}{{\mathsf {T}}}_2,\ldots ,{{\mathsf {C}}}{{\mathsf {T}}}_{s}$ (but not ${{\mathsf {C}}}{{\mathsf {T}}}_1$). The encoding of the update is consists of these $s-1$ keys and, along with a garbled-version of the new gate ${{\langle {C'}\rangle }^{1}_{{\mathsf {gc}}}}$. Using this information, the receiver can decrypt and recover the garbled gates ${{\langle {C}\rangle }^{2}_{{\mathsf {gc}}}}$,...,${{\langle {C}\rangle }^{s}_{{\mathsf {gc}}}}$. Together with ${{\langle {C}\rangle }^{1}_{{\mathsf {gc}}}}$, this forms a complete garbled circuit for $C'$.

The main remaining question is how to implement the aforementioned conditional decryption mechanism. A naive way to achieve this is to encrypt each ciphertext with an independent encryption key, and then release the decryption key for every position $i\ne 1$. However, note that in this naive solution, the size of the update encoding is proportional to $s = |C|$. In terms of size, this is no better than garbling $C'$ from scratch.

To address this, we could instead use a (secret key) puncturable encryption scheme. In such a scheme, for any ciphertext ${{\mathsf {C}}}{{\mathsf {T}}}$, it is possible to compute “punctured decryption key” that enables one to decrypt all ciphertexts except ${{\mathsf {C}}}{{\mathsf {T}}}$. In order to be non-trivial, the size of punctured decryption keys must be independent of the number of ciphertexts generated. Such an encryption scheme can be built from puncturable pseudorandom functions [21, 22, 48, 56] (c.f. Waters [58]) which in turn can be based on any one-way function. It is easy to verify that given such an encryption scheme, we can efficiency we desire in above construction for $\mathrm {UGC}$ supporting a single update.

We find it instructive to abstract the above idea as a lock-and-release mechanism. Roughly speaking, the encryption of the wire keys corresponding to C constitutes the locking step, while the dissemination of the punctured decryption key constitutes the (conditional) release step. We find this abstraction particularly useful going forward, in order to develop our full solution for an unbounded number of updates.

Multiple Updates: Main Challenges. The above solution does not offer any security for multiple sequential updates – even for two. If the two updates for two different gates would allow an adversary to recover a garbling of the original circuit Additionally, the above scheme does not “connect” the two updates in any manner; an adversary could choose to apply none, one, or both of the updates before evaluating the circuit.

A Layered Lock-and-Release Mechanism for Bounded Updates. We next consider the case of an a priori bounded number of updates (the setting of Theorem 4). The key idea, in a nutshell, is to use layered punctured encryption, or alternatively, a layered lock-and-release mechanism.

Suppose we wish to handle p-many of updates. When garbling the circuit C, instead of encrypting the garbled gates a single time, we instead use p “onion” layers of encryption scheme, each using a punctured encryption scheme. Let ${\mathbf {u}}_1$,...,${\mathbf {u}}_p$ be a sequence of gate updates, each consisting of a gate $g \in [s]$ to change and a new gate type. To generate an updatable garbled circuit for C, first garble ${\tilde{C}}$ using a traditional gate-by-gate scheme. Sample p keys $SK_1$,...,$SK_p$ for a puncturable encryption scheme. Encrypt each garbled gate ${{\langle {C}\rangle }^{i}_{{\mathsf {gc}}}}$ of the garbled circuit in p layers, yielding a ciphertext ${{\mathsf {C}}}{{\mathsf {T}}}_i = \mathsf {Enc}(SK_1, \mathsf {Enc}(SK_2,\ldots \mathsf {Enc}(SK_p,{{\langle {C}\rangle }^{i}_{{\mathsf {gc}}}})))$.

The encoding of the first update ${\mathbf {u}}_1 = (g_1,\mathsf {gateType}_1)$ simply corresponds to releasing a decryption key for the outermost encryption layer that is punctured at ${{\mathsf {C}}}{{\mathsf {T}}}_{g_1}$, along with a layer $(p-1)$ encryption ${{\mathsf {C}}}{{\mathsf {T}}}_{g_i}' = \mathsf {Enc}(SK_2,\mathsf {Enc}(SK_3,\ldots \mathsf {Enc}(SK_p,{{\langle {C'}\rangle }^{g_i}_{{\mathsf {gc}}}})))$, where ${{\langle {C'}\rangle }^{g_i}_{{\mathsf {gc}}}}$ is the new garbled gate corresponding to replacing gate $g_i$ of C with $\mathsf {gateType}$. Likewise, an encoding of the i-th update ${\mathbf {u}}_i$ corresponds to releasing a punctured decryption key for $SK_i$, $(i-1)$ encryption of the new garbled gate.

The above idea of layered (punctured) encryption ensures that the receiver cannot “skip” any update, and instead must apply all the updates one-by-one to “peel-off” all the encryption layers from the garbled gates. Furthermore, since the encryption layers can only be removed in a prescribed order, the receiver must applies the updates in order. Finally, after all the decryption operations, the receiver only obtains a single garbled gate every location in the (updated) circuit.

We now briefly argue that the above construction satisfies the efficiency properties stated in Theorem 4. We first note that punctured encryption scheme in the above construction can simply correspond to a one-time pad where the randomness for computing the ith ciphertext, for every $i\in |C|$, is generated by evaluating a puncturable PRF over the index i. The PRF key (i.e., the secret key for the punctured encryption scheme) is different for every layer. With this instantiation, note that the size of the initial garbled circuit as well as every update is independent of the total number of updates p; however, the garbling time as well as update generation time depends on p.

A Relock-and-Eventual-Release Mechanism for Unbounded Updates. The above solution is that it inherently requires the number of updates to be a priori bounded. To support multiple updates, our main insight is to develop a relock-and-eventual-release mechanism as opposed to the layered lock-and-release mechanism discussed above. That is, instead of removing a lock at every step, our idea is to change the lock at every step. In encryption terminology, our idea is to replace the layered encryption in the above approach with a symmetric re-encryption scheme [16]. In a symmetric re-encryption scheme, given two encryption keys ${{\mathsf {S}}}{{\mathsf {K}}}_1$ and ${{\mathsf {S}}}{{\mathsf {K}}}_2$, it is possible to issue a re-encryption key ${{\mathsf {R}}}{{\mathsf {K}}}_{1\rightarrow 2}$ that transforms any ciphertext w.r.t. ${{\mathsf {S}}}{{\mathsf {K}}}_1$ into a ciphertext w.r.t. ${{\mathsf {S}}}{{\mathsf {K}}}_2$. In order to allow for updates, we, require the re-encryption scheme to support key puncturing. That is, we require that it is possible to compute a punctured re-encryption key ${{\mathsf {R}}}{{\mathsf {K}}}_{1\rightarrow 2}^{{{\mathsf {C}}}{{\mathsf {T}}}^*}$ that allows one to transform any ciphertext w.r.t. ${{\mathsf {S}}}{{\mathsf {K}}}_1$ into a ciphertext w.r.t. ${{\mathsf {S}}}{{\mathsf {K}}}_2$, except the ciphertext ${{\mathsf {C}}}{{\mathsf {T}}}^*$ (computed under ${{\mathsf {S}}}{{\mathsf {K}}}_1$). From a security viewpoint, we require that the semantic security of ${{\mathsf {C}}}{{\mathsf {T}}}^*$ should hold even if the adversary is given ${{\mathsf {R}}}{{\mathsf {K}}}_{1\rightarrow 2}^{{{\mathsf {C}}}{{\mathsf {T}}}^*}$ and the terminal secret key ${{\mathsf {S}}}{{\mathsf {K}}}_2$. We refer to such an encryption scheme as a puncturable symmetric re-encryption scheme. While the above description only refers to a “single-hop” puncturable re-encryption scheme, we in fact consider a “multi-hop” scheme.

Armed with the above insight, we modify the previous solution template as follows: the garbling of a circuit C consists of ${\tilde{U}}$ as before. The main difference is that the wire keys $w_{C}= \{w_{C_1},\ldots ,w_{C_n}\}$ corresponding to the circuit C are now encrypted w.r.t. a puncturable re-encryption scheme. Let ${{\mathsf {S}}}{{\mathsf {K}}}_0$ denote the secret key used to encrypt the wire keys. In order to issue an update encoding for an update ${\mathbf {u}}_i$, we release (a) a re-encryption key ${{\mathsf {R}}}{{\mathsf {K}}}_{i-1\rightarrow i}^{{{\mathsf {C}}}{{\mathsf {T}}}}$ that is punctured at ciphertext ${{\mathsf {C}}}{{\mathsf {T}}}$, where ${{\mathsf {C}}}{{\mathsf {T}}}$ is the encryption of $w_{C_{\ell }}$ w.r.t. ${{\mathsf {S}}}{{\mathsf {K}}}_{i-1}$ and $\ell$ is the position associated with update ${\mathbf {u}}_i$, along with (b) an encryption of $w_{\bar{C_{\ell }}}$ w.r.t. ${{\mathsf {S}}}{{\mathsf {K}}}_{i}$. For the final update L, we simply release the Lth secret key ${{\mathsf {S}}}{{\mathsf {K}}}_{L}$.

We argue the security of the construction by using the security of the puncturable re-encryption scheme and the garbling scheme (see the technical sections for details). We note, however, that this construction does not hide the location of the updates. Indeed, the correctness of the above scheme requires the evaluator to know the locations that are being updated. To address this, we provide a generic transformation from any UGC scheme (or in fact, any URE scheme) that does not achieve update hiding into one that achieves update hiding. Our transformation uses non-interactive oblivious RAM in the same manner as in [35]. Finally, we note that while the above only discusses single-bit updates, our construction handles multi-bit updates as well.

The only missing piece in the above solution is a construction of a puncturable symmetric re-encryption scheme. We discuss it next.

Puncturable Symmetric Re-encryption from Worst-case Lattice Assumptions. The work of [18] constructs re-encryption schemes from key homomorphic PRFs, which have the property that for all x, $K_1$, and $K_2$, $\mathsf {PRF}(K_1,x) + \mathsf {PRF}(K_2,x) = \mathsf {PRF}(K_1 + K_2,x)$, where the keys and outputs of the PRF lie in appropriate groups. A secret key for the encryption scheme is simply a PRF key, and the encryption of a message m with secret key $K_1$ and randomness r is ${{\mathsf {C}}}{{\mathsf {T}}}= (r,m + \mathsf {PRF}(K_1,r))$.

A re-encryption key between between secret keys $K_1$ and $K_2$ is simply their difference: ${{\mathsf {R}}}{{\mathsf {K}}}_{1\rightarrow 2} = K_2 - K_1$. The key-homomorphism suggests a natural way to re-encrypt ciphertexts, as $(r, m + \mathsf {PRF}(K_1,r) + \mathsf {PRF}({{\mathsf {R}}}{{\mathsf {K}}}_{1\rightarrow 2}, r)) = (r,m+ (K_2,r))$ is a ciphertext w.r.t $K_2$. Observe that successful re-encryption of a ciphertext with randomness r relies on the ability to compute $\mathsf {PRF}({{\mathsf {R}}}{{\mathsf {K}}}_{1\rightarrow 2}, r)$.

We construct puncturable proxy re-encryption scheme following the above approach, but instantiated with constrained key-homomorphic PRFs [23]. A punctured re-encryption key ${{\mathsf {R}}}{{\mathsf {K}}}_{1\rightarrow 2}^{{{\mathsf {C}}}{{\mathsf {T}}}^*}$ for a ciphertext ${{\mathsf {C}}}{{\mathsf {T}}}^*$ with randomness $r^*$ is the PRF key $K_2 - K_1$ punctured at the input $r^*$. This key, which can be used to evaluate $\mathsf {PRF}(K_2 - K_1,r)$ for all $r \ne r^*$, enables the re-encryption of all ciphertexts except for the ciphertext ${{\mathsf {C}}}{{\mathsf {T}}}^*$.

For security, we require that the semantic security of ${{\mathsf {C}}}{{\mathsf {T}}}^*$ holds given both ${{\mathsf {R}}}{{\mathsf {K}}}_{1\rightarrow 2}^{{{\mathsf {C}}}{{\mathsf {T}}}^*}$ and $K_2$. We reduce to the security of the constrained PRF, which guarantees that $y^*:=\mathsf {PRF}(K_2 - K_1, r^*)$ is pseudorandom. The key idea is that (partial information about) $y^*$ can be computed given ${{\mathsf {C}}}{{\mathsf {T}}}^*$, $K_2$, and (partial information about) the message m.

2.2 Construction of URE

We now shift our focus on building multi-evaluation URE.

Relock-and-Release Mechanism. Recall that the main difference between $\mathrm {UGC}$ and $\mathsf {URE}$ is that $\mathrm {UGC}$ only allows for a single evaluation after a sequence of updates, while $\mathsf {URE}$ allows for evaluation after every update. As such, the relock-and-eventual-release mechanism that we discussed above does not suffice for building $\mathsf {URE}$. Our starting insight is to instead develop a relock-and-release mechanism that performs both relocking and release at every step. Intuitively, relocking allows us to “carry over” the updates, while the release mechanism allows us to evaluate the updated randomized encoding at every step.

Starting Idea: Garbled RAM with Persistent Memory. A natural starting approach to implement such a relock-and-release mechanism is via the use of garbled RAMs with persistent memory [37, 51]. In a garbled RAM scheme, it is possible to encode a database $D_0$ and later issue encodings for RAM programs $M_1,\ldots ,M_n$. Each RAM program encoding $\widetilde{M_i}$ updates the database encoding from $\widetilde{D_{i-1}}$ to $\widetilde{D_i}$, and outputs the result of some computation on $D_i$.

Given this description, it is not difficult to see why such a notion is useful for our purpose. Starting from a garbled RAM scheme and a standard randomized encodings scheme without updates [59], we can build a candidate construction of multi-evaluation URE as follows:

• We set the initial database $D_0$ in garbled RAM to the initial circuit and input pair $(C_0,x_0)$ in the $\mathsf {URE}$ scheme. The initial updatable randomized encoding of $(C_0,x_0)$ is an encoding of $D_0$, computed under garbled RAM scheme, along with an encoding of $(C_0,x_0)$ computed under the standard randomized encoding scheme.

• In order to compute an encoding $\langle {\mathbf {u}}_i \rangle$ for an update ${\mathbf {u}}_i$, we compute an encoding $\widetilde{M_i}$ of a machine $M_i$ w.r.t. the garbled RAM scheme where the machine $M_i$ has ${\mathbf {u}}_i$ hardcoded in it. The machine $M_i$ on input $D_{i-1} = (C_{i-1},x_{i-1})$ first updates the database to $D_i = (C_i,x_i)$, where $(C_i,x_i)\leftarrow {\mathsf {Update}}(C_{i-1},x_{i-1};{\mathbf {u}}_i)$, and outputs a fresh standard randomized encoding of $(C_i,x_i)$.

Let us inspect the above solution closely; specifically, the complexity of the machine $M_i$ corresponding to an update ${\mathbf {u}}_i$. Since $M_i$ computes a fresh (standard) randomized encoding “on-the-fly,” in order to achieve the necessary efficiency guarantee for $\mathsf {URE}$, we will require that the encoding time for $M_i$ is independent of its running time. Such a garbled RAM scheme is called a succinct garbled RAM scheme [13, 25]. Furthermore, since the output of $M_i$ consists of a fresh randomized encoding, we will also require that the time of encode $M_i$ is independent of its output length. Such a garbled RAM scheme is referred to as output-compressing [3, 50].

Recent works [3, 50] show that output-compressing succinct garbled RAM (with sub-exponential security) imply indistinguishability obfuscation (${{\mathsf {i}}}{{\mathsf {O}}}$). Furthermore, the only known constructions for such a garbled RAM scheme are based on ${{\mathsf {i}}}{{\mathsf {O}}}$, which, in turn seems to require sub-exponential hardness assumptions. Our goal, however, is to obtain a solution for $\mathsf {URE}$ using polynomial hardness assumptions. As such, the above is not a viable solution for us.

Garbled RAM meets Delegation of Computation. Towards that end, our next idea is to instantiate the above approach using a non-succinct garbled RAM scheme where the size of the encoding of a machine $M_i$ depends on the running time and the output length of $M_i$. Such garbled RAM schemes are known to exist based on only one-way functions. At first, it is not clear how to make this approach work since the efficiency requirements of $\mathsf {URE}$ are immediately violated.

Towards that end, our next idea is to delegate the computation of the encoding of $M_i$ to the receiver. We implement this idea by using secret-key functional encryption [19, 54, 55]. Roughly speaking, the initial encoding of $C_0(x_0)$ now corresponds to a database encoding of $D_0=(C_0,x_0)$ w.r.t. a non-succinct garbled RAM scheme along with FE functional key for a circuit P that takes as input an update string ${\mathbf {u}}_i$ and outputs an encoding $\widetilde{M_i}$ of the machine $M_i$ (as described before). Encoding of an update ${\mathbf {u}}_i$ now corresponds to an FE encryption of ${\mathbf {u}}_i$.

In order to achieve the necessary efficiency guarantee of $\mathsf {URE}$, we require that the secret-key FE scheme used above is compact, i.e., where the running time of the encryption algorithm on a message m is a fixed polynomial in the length of m and the security parameter, and in particular, independent of the size complexity of any function f in the function family supported by the FE scheme. Indeed, if this were not the case, then the encoding time for an update ${\mathbf {u}}_i$ in the above solution would depend on the size of the circuit C, which in turn depends on the running time and output length of $M_i$. Therefore, if the FE scheme were not compact, then the efficiency requirements of $\mathsf {URE}$ would once again be violated.

As discussed earlier, a secret-key compact FE scheme with polynomial hardness can be built from polynomial hardness assumptions on multilinear maps using using the results of [33] and [4, 15].

Challenges in Proving Security. While the above construction seems to achieve correctness, it is not immediately clear how to argue security. Note that the circuit P computed by an FE key in the above construction contains the garbling key of the garbled RAM scheme hardwired inside it. Indeed, this is necessary for it to compute the encodings corresponding to machines $M_i$ as discussed above. In order to leverage security of garbled RAM, one approach is to remove the garbling key from the FE function key. However, in order to maintain functionality, this would require hardwiring the output of P, either in the FE key, or in the FE ciphertext. We cannot afford to hardwire the output in the ciphertext since that would violate the efficiency requirements of $\mathsf {URE}$. Thus, our only option is to hardwire the output in the FE key. Note, however, that in the setting of multiple updates, we have to deal with multiple outputs. In particular, the above approach would require hardwiring all the outputs (one corresponding to each update) in the FE key. Doing so “at once” would require putting a bound on the number of updates.

A better option is to hardwire the outputs “one-at-a-time,” analogous to many proofs in the ${{\mathsf {i}}}{{\mathsf {O}}}$ literature (see, e.g., [3, 23, 39]). Implementing this idea, however, would require puncturing the garbling key. Such a notion of key puncturing is not supported by standard garbled RAM schemes.

Using Cascaded Garbled Circuits. Towards that end, we take a step back and revisit our requirements from the garbled RAM scheme. Our first observation is that in the above solution template, machine $M_i$ need not be a RAM since we are already requiring it to read the entire database! Instead, the key property of garbled RAM with persistent memory that is used in the above template is its ability to maintain updated state in the form of encoded database.

We now discuss how to implement this property in a more direct manner by “downgrading” the garbled RAM to a cascaded garbled circuit. Along the way, we will also address the security issues discussed above. Very briefly, we modify the above construction as follows: consider a circuit $Q_i$ that has an update string ${\mathbf {u}}_i$ hardwired in its description. It takes as input $(C_{i-1},x_{i-1})$ and outputs two values. The first value is a fresh randomized encoding of $C_i(x_i)$ where $(C_i,x_i)\leftarrow {\mathsf {Update}}(C_{i-1},x_{i-1};{\mathbf {u}}_i)$, and the second value is a set of wire keys for the string $(C_i,x_i)$ corresponding to a garbling of the circuit $Q_{i+1}$ (that is defined analogously to $Q_i$). The initial encoding of $C_0(x_0)$ now corresponds to the input wire keys for the string $(C_0,x_0)$ corresponding to a garbling of circuit $Q_1$ as defined above, as well as an FE key for a function f that takes as input ${\mathbf {u}}_i$ and outputs a garbling a circuit $Q_i$. The encoding of an update ${\mathbf {u}}_i$ now corresponds to an FE encryption of ${\mathbf {u}}_i$ as before.

We prove the security of the above construction with respect to indistinguishability based security definition. Simulation-based security can be argued via a generic transformation following [26]. Let $C^0_0,C^1_0,x$ be the initial circuits and input submitted by the adversary in the security proof. And let, $({\mathbf {u}}_1^0,{\mathbf {u}}_1^1),\ldots ,({\mathbf {u}}_q^0,{\mathbf {u}}_q^1)$ be the tuple of updates. There are two “chains” of updating processes with the $0^{th}$ chain starting from $C^0_0$ and $1^{st}$ chain starting from $C_1^1$. The $i^{th}$ “bead” on $0^{th}$ (resp., $1^{st}$) chain corresponds to update ${\mathbf {u}}_i^0$ (resp., ${\mathbf {u}}_i^1$).

In the security proof, we start with the real experiment where challenge bit 0 is used. That is, the $0^{th}$ chain is active in the experiment. In the next step, we introduce the $1^{st}$ chain, along with the already present $0^{th}$ chain, into the experiment. However even in this step, $0^{th}$ chain is still active – that is, generating the randomized encoding at every step is performed using the $0^{th}$ chain. In the next intermediate hybrids, we slowly switch from $0^{th}$ chain being activated to $1^{st}$ chain being activated. In the $i^{th}$ intermediate step, the first i beads on $1^{st}$ chain are active and on the $0^{th}$ chain, all except the first i beads are active – this means that the first i updated randomized encodings are computed using the $1^{st}$ chain and the rest of them are computed using $0^{th}$ chain. At the end of these intermediate hybrids, we have the $1^{st}$ chain to be active and $0^{th}$ chain to be completely inactive. At this stage, we can remove the $0^{th}$ chain and this completes the proof.

The two chains described above are implemented in a sequence of garbled circuits, that we call cascaded garbled circuits. That is, every $i^{th}$ garbled circuit in this sequence produces wire keys for the next garbled circuit. Every garbled circuit in this sequence is a result of $\mathsf {ApplyUpd}$ procedure and encapsulates, for some i, the $i^{th}$ beads on both the chains. In order to move from the $i^{th}$ intermediate step to $(i+1)^{th}$ intermediate step, we use the security of garbled circuits. But since these garbled circuits are not given directly, but instead produced by a FE key, we need to make use of security of FE to make this switch work.

3 Preliminaries

We denote the security parameter by $\lambda$. The background for randomized encodings and private key (function hiding) functional encryption can be found in the full version [2].

3.1 Updatable Circuits

A boolean circuit C is an directed acyclic graph of in-degree at most 2 with the non-leaf nodes representing $\vee$ (OR), $\wedge$ (AND) and $\lnot$ (NOT) gates and the leaf nodes representing the input variables and constants 0 and 1. The nodes with no outgoing edges are designated to be output gates. The size of a circuit |C| is the number of nodes in the graph. Each node is labeled with a different index between 1 and |C|. The evaluation of C on input x is performed by first substituting the leaf nodes with the value x and then evaluating gate-by-gate till we reach the output gates. The joint value of all the output gates determine the output of the circuit. Circuit C is said to represent a function $f:\{0,1\}^{\lambda } \rightarrow \{0,1\}^{\ell (\lambda )}$ if for every $x \in \{0,1\}^{\lambda }$ we have $C(x)=f(x)$. We assume that the class of all boolean circuits for every fixed size |C| and n inputs has an efficient binary representation $\mathsf {binary}(C) \in \{0,1\}^{O(|C|)}$. That is, there is an efficient algorithm that computes $C \mapsto (n,|C|, \mathsf {binary}(C))$, and its inverse.

We define the notion of updatable circuits next. A family of updatable circuits ${\mathcal {C}}$ has associated with it a class of updates ${\mathcal {U}}$. Given any circuit $C \in {\mathcal {C}}$ we can transform this circuit into another circuit $C' \in {\mathcal {C}}$ with the help of an update ${\mathbf {u}}\in {\mathcal {U}}$. The updating process could, for instance, change one of the output gates from $\vee$ to $\lnot$, change all the gates to $\wedge$ gates and so on. Formally,

Definition 1

(Updatable Circuits). Consider a circuit family ${\mathcal {C}}=\{{\mathcal {C}}_{\lambda }\}_{\lambda \in {\mathbb {N}}}$, where ${\mathcal {C}}_{\lambda }$ contains $\mathrm {poly}(\lambda )$-sized boolean circuits $C:\{0,1\}^{\lambda } \rightarrow \{0,1\}^{\ell (\lambda )}$. Consider a set system of strings ${\mathcal {U}}=\{{\mathcal {U}}_{\lambda }\}_{\lambda \in {\mathbb {N}}}$, where ${\mathcal {U}}_{\lambda }$ is a set of strings of length $\mathrm {poly}(\lambda )$. We define ${\mathcal {C}}$ to be $(\mathsf {Upd},{\mathcal {U}})$ -updatable if $C' \leftarrow \mathsf {Upd}(C,{\mathbf {u}}\in {\mathcal {U}}_{\lambda })$ is also a boolean circuit with input domain $\{0,1\}^{\lambda }$ and output domain $\{0,1\}^{\ell (\lambda )}$.

The size of update ${\mathbf {u}}$ could potentially be much smaller than the size of the circuit C. For instance, the length of the instruction to change all the gates in C to $\wedge$ gate is in fact independent of |C|.

4 Updatable Randomized Encodings

We define the notion of updatable randomized encodings (URE) next. Since this notion deals with transforming circuits, this notion will be associated to a class of updatable circuits. But to also capture the joint updatability of both the circuit and the input together, we introduce the notion of hardwired circuits below.

Hardwired Circuits. A hardwired circuit, associated to a circuit C and input x, takes no input but upon evaluation yields a fixed output C(x).

We provide the formal definition of hardwired circuits below.

Definition 2

(Hardwired Circuit). Consider a circuit $C:\{0,1\}^{\lambda } \rightarrow \{0,1\}^{\ell (\lambda )}$ and $x \in \{0,1\}^{\lambda }$. We define a hardwired circuit, denoted by C[x], to be a circuit such that,

• it takes no input.

• upon evaluation (always) outputs C(x).

We interchangeably use C[x] to denote the circuit as well as the output C(x) it computes.

Two hardwired circuits $C_0[x_0]$ and $C_1[x_1]$ are equivalent if and only if $C_0(x_0)=C_1(x_1)$ and $|C_0|=|C_1|$. If $C_0[x_0]$ and $C_1[x_1]$ are equivalent then they are denoted by $C_0[x_0] \equiv C_1[x_1]$. We can generalize this notion and define a class of hardwired circuits as stated below.

Definition 3

Consider a circuit family ${\mathcal {C}}=\{{\mathcal {C}}_{\lambda }\}_{\lambda \in {\mathbb {N}}}$. We define a hardwired circuit family $\{{\mathcal {C}}[X]_\lambda \}_{\lambda \in {\mathbb {N}}}$ where ${\mathcal {C}}[X]_\lambda$ comprises of hardwired circuits of fixed input length and is associated with a bijective function $\phi : {\mathcal {C}}_{\lambda } \times \{0,1\}^{\lambda } \rightarrow {\mathcal {C}}[X]_\lambda$ such that if $\phi \left( C \in {\mathcal {C}}_{\lambda },x \right) ={\mathbf {C}}$ then the output of the hardwired circuit ${\mathbf {C}}$ is C(x).

We can now talk about updatability of hardwired circuits. Note that this captures joint updating of both the circuit as well as the input hardwired into it.

Definition 4

(Updatable Hardwired Circuits). Consider a family of hardwired circuits $\{{\mathcal {C}}[X]_\lambda \}_{\lambda \in {\mathbb {N}}}$, where ${\mathcal {C}}[X]_{\lambda }$ contains $\mathrm {poly}(\lambda )$-sized boolean circuits $C[X]:\bot \rightarrow \{0,1\}^{\ell (\lambda )}$. Consider a set system of strings ${\mathcal {U}}=\{{\mathcal {U}}_{\lambda }\}_{\lambda \in {\mathbb {N}}}$, where ${\mathcal {U}}_{\lambda }$ contains a set of strings of length $\mathrm {poly}(\lambda )$. We define ${\mathcal {C}}[X]$ to be $(\mathsf {Upd},{\mathcal {U}})$ -updatable if ${\mathbf {C}} \leftarrow \mathsf {Upd}\left( C[x] ,{\mathbf {u}}\right)$, where $C[x] \in {\mathcal {C}}[X]_{\lambda },{\mathbf {u}}\in {\mathcal {U}}_{\lambda }$, then ${\mathbf {C}}$ is also a hardwired circuit.

We now proceed to give a formal definition of URE.

Syntax. A scheme $\mathsf {URE}=({\mathsf {Encode}},{\mathsf {GenUpd}},\mathsf {ApplyUpd},{\mathsf {Decode}})$ for a $(\mathsf {Upd},{\mathcal {U}})$-updatable class of circuits ${\mathcal {C}}=\{{\mathcal {C}}_{\lambda }\}_{\lambda \in {\mathbb {N}}}$ is defined below. We denote ${\mathcal {C}}[X]$ to be the corresponding updatable hardwired circuit family.

• Encode, $({\left\langle C[x]\right\rangle }_{\mathsf {ure}},{\mathsf {st}}) \leftarrow {\mathsf {Encode}}\left( 1^{\lambda },C,x\right)$: On input security parameter $\lambda$, circuit $C \in {\mathcal {C}}_{\lambda }$, input $x \in \{0,1\}^{\lambda }$, it outputs the joint encoding ${\left\langle C[x]\right\rangle }_{\mathsf {ure}}$ and state ${\mathsf {st}}$.

• Generating Secure Update, $({\langle {\mathbf {u}}\rangle }_\mathsf {ure},{\mathsf {st}}') \leftarrow {\mathsf {GenUpd}}\left( {\mathsf {st}},{\mathbf {u}}\right)$: On input state ${\mathsf {st}}$, update ${\mathbf {u}}\in {\mathcal {U}}_{\lambda }$, output the secure update ${\langle {\mathbf {u}}\rangle }_\mathsf {ure}$ along with the new state ${\mathsf {st}}'$.

• Apply Secure Update, ${\left\langle C'[x']\right\rangle }_{\mathsf {ure}} \leftarrow \mathsf {ApplyUpd}\left( {\left\langle C[x]\right\rangle }_{\mathsf {ure}},{\langle {\mathbf {u}}\rangle }_\mathsf {ure} \right)$: On input randomized encoding ${\left\langle C[x]\right\rangle }_{\mathsf {ure}}$, secure update ${\langle {\mathbf {u}}\rangle }_\mathsf {ure}$, output the updated randomized encoding ${\left\langle C'[x']\right\rangle }_{\mathsf {ure}}$.

• Evaluation, $\alpha \leftarrow {\mathsf {Decode}}\left( {\left\langle C[x]\right\rangle }_{\mathsf {ure}} \right)$: On input randomized encoding ${\left\langle C[x]\right\rangle }_{\mathsf {ure}}$, output the decoded value $\alpha$.

We associate the above scheme with efficiency, correctness and security properties. We first talk about the efficiency requirement. Modeling of correctness and security properties is tricky and we will deal with them in a separate subsection.

Efficiency. We lay out different efficiency properties associated with the above scheme.

• Encoding Time: This property requires that the encoding time of (C, x) is significantly “simpler” than computing C(x). The efficiency aspect can be quantified in many ways – in this work, we define encoding to be efficient if the depth of ${\mathsf {Encode}}$ circuit is smaller than C.

• Secure Update Generation Time: This property requires that the runtime of ${\mathsf {GenUpd}}\left( {\mathsf {st}},{\mathbf {u}}\right)$ is $p(\lambda ,|{\mathbf {u}}|)$, where p is an a priori fixed polynomial. In other words, the update generation time is independent of the size of the encoded circuit.

• State Size: This property requires that the size of the state maintained by the authority is a fixed polynomial in the security parameter. That is, the size of ${\mathsf {st}}$ output by ${\mathsf {Encode}}$ and ${\mathsf {GenUpd}}$ is always $\mathrm {poly}(\lambda )$ independent of the size of the machines and the update sizes.

• Secure Update Size: This property states that the size of the secure version of the update should solely depend on the size of the update. Formally, we have the size of the secure update to be $|{\langle {\mathbf {u}}\rangle }_\mathsf {ure}|=p(\lambda ,|{\mathbf {u}}|)$, where $({\langle {\mathbf {u}}\rangle }_\mathsf {ure},{\mathsf {st}}') \leftarrow {\mathsf {GenUpd}}\left( {\mathsf {st}},{\mathbf {u}}\right)$. Note that any URE scheme that satisfies the above secure update generation time property also satisfies this property.

• Runtime of Update: Informally, this property states that the time to update the secure encoding incurs a polynomial overhead in the time to update the plaintext circuit. Formally, the runtime of $\mathsf {ApplyUpd}({\left\langle C[x]\right\rangle }_{\mathsf {ure}},{\langle {\mathbf {u}}\rangle }_\mathsf {ure})$ is $p(\lambda ,t,|{\mathbf {u}}|)$, where t is the time taken to execute $\mathsf {Upd}(C[x],{\mathbf {u}})$.

Our constructions achieve a restricted version of the above properties. On the positive side, our construction in Sect. 5 achieves the ‘Encoding Time’ property and ‘Secure Update Generation Time’ properties. We use a term to define a URE scheme that satisfies the secure update generation time property – we call it output compact URE.

Definition 5

(Output Compact URE). An URE scheme that is said to be output compact if it satisfies ‘Secure update generation time’ property.

In the case of indistinguishability security, our construction will be output-compact, i.e., the updates will be independent of the output length of the circuit. In the case of simulation-based security, our construction will not achieve output compactness. This is, in fact, inherent and a formal lower bound to this effect can be established along the same lines as in [1, 26]. On the flip side, our construction does not satisfy ‘Runtime of Update’ property.

In the full version [2], we provide a transformation from any URE scheme that satisfies the ‘Secure Update Generation Time’ property to one that additionally satisfies the ‘State Size’ property. This transformation uses non-succinct garbled RAMs, and assumes only one-way functions.

4.1 Sequential Updating

We first consider sequential updating process that will be the main focus of this work. For alternate updating processes, refer to the full version [2]. Sequential Updating process allows for updating a randomized encoding using multiple patches in a sequential manner. That is, given secure updates ${\langle {\mathbf {u}}_1\rangle }_\mathsf {ure},\ldots ,{\langle {\mathbf {u}}_{\ell }\rangle }_\mathsf {ure}$, we can update a randomized encoding ${\left\langle C[x]\right\rangle }_{\mathsf {ure}}$ by first applying ${\langle {\mathbf {u}}_1\rangle }_\mathsf {ure}$ on ${\left\langle C[x]\right\rangle }_{\mathsf {ure}}$ to obtain the updated encoding ${\left\langle C_1[x_1]\right\rangle }_{\mathsf {ure}}$; next we apply ${\langle {\mathbf {u}}_2\rangle }_\mathsf {ure}$ on ${\left\langle C_1[x_1]\right\rangle }_{\mathsf {ure}}$ to obtain the updated encoding ${\left\langle C_2[x_2]\right\rangle }_{\mathsf {ure}}$ and so on. After all the updates, we end up with the updated encoding ${\left\langle C_{\ell }[x_{\ell }]\right\rangle }_{\mathsf {ure}}$.

Correctness of Sequential Updating. Intuitively, the correctness property states that computing the randomized encoding ${\left\langle C[x]\right\rangle }_{\mathsf {ure}}$, applying the secure updates ${\langle {\mathbf {u}}_1\rangle }_\mathsf {ure},\ldots ,{\langle {\mathbf {u}}_{\ell }\rangle }_\mathsf {ure}$ sequentially and finally decoding yields the same result as the output of the circuit obtained by updating the hardwired circuit C[x] by applying the updates ${\mathbf {u}}_1,\ldots ,{\mathbf {u}}_{\ell }$ sequentially. We give the formal description below.

Consider a circuit $C \in {\mathcal {C}}_{\lambda }$, input $x \in \{0,1\}^{\lambda }$. Consider a vector of updates ${\mathbf {U}}\in \left( {\mathcal {U}}_{\lambda } \right) ^{q}$, where $q(\lambda )$ is a polynomial in $\lambda$. Consider the following two processes:

Secure updating process:

• 1. $({\left\langle C[x]\right\rangle }_{\mathsf {ure}},{\mathsf {st}}_0) \leftarrow {\mathsf {Encode}}\left( 1^{\lambda },C,x \right)$.

• 2. For every $i \in [q]$; $({\langle {\mathbf {u}}_{i}\rangle }_\mathsf {ure},{\mathsf {st}}_i) \leftarrow {\mathsf {GenUpd}}\left( {\mathsf {st}}_{i-1},{\mathbf {u}}_{i} \right)$, where ${\mathbf {u}}_{i}$ is the $i^{th}$ entry in ${\mathbf {U}}$.

• 3. Let ${\left\langle C_0[x_0]\right\rangle }_{\mathsf {ure}}:={\left\langle C[x]\right\rangle }_{\mathsf {ure}}$. For every $i \in [q]$;

  $$\begin{aligned}{\left\langle C_i[x_i]\right\rangle }_{\mathsf {ure}} \leftarrow \mathsf {ApplyUpd}\left( {\left\langle C_{i-1}[x_{i-1}]\right\rangle }_{\mathsf {ure}},{\langle {\mathbf {u}}_{i}\rangle }_\mathsf {ure} \right) .\end{aligned}$$

Insecure updating process:

• 1. Let $(C_0,x_0):= (C,x)$. For every $i \in [q]$, we have $C_i[x_i] \leftarrow \mathsf {Upd}(C_{i-1}[x_{i-1}],{\mathbf {u}}_{i})$. The output of $C_q[x_q]$ is $C_q(x_q)$.

We have,

$$\begin{aligned}{\mathsf {Decode}}\Big ( {\left\langle C_q[x_q]\right\rangle }_{\mathsf {ure}} \Big ) = C_{q}(x_q)\end{aligned}$$

Security of Sequential Updating. We consider two different security notions of sequential updatable RE. First, we consider simulation-based notion and then we consider the weaker indistinguishability-based notion.

Our security notions attempt to capture the intuition that an updateable randomized encoding ${\left\langle C_0[x_0]\right\rangle }_{\mathsf {ure}}$ and a sequence of updates ${\langle {\mathbf {u}}_1\rangle }_\mathsf {ure},\ldots ,{\langle {\mathbf {u}}_q\rangle }_\mathsf {ure}$ should reveal only the outputs $C_0(x_0)$, $C_1(x_1)$,...$C_q(x_q)$ where $C_i$ and $X_i$ are defined as in the preceding correctness definition. In addition to hiding the circuits and inputs as in traditional randomized encodings, a URE additionally hides the sequence of updates. Our URE construction satisfies this update-hiding property.

We could instead consider a relaxed notion, in which updates are partially or wholly revealed (modifying the definitions appropriately). Indeed, this is what we will do in the context of updatable garbled circuits. In the full version [2], we provide a generic transformation from an update-revealing URE scheme to an update-hiding URE scheme, assuming only the existence of one-way functions.

Simulation-Based Security. We adopt the real world/ideal world paradigm in formalizing the simulation-based security definition of sequential updatable RE. In the real world, the adversary receives a randomized encoding and encodings of updates. All the encodings are generated honestly as per the description of the scheme. In the ideal world, the adversary is provided simulated randomized encodings and encodings of updates. These simulated encodings are generated as a function of the outputs and in particular, the simulation process does not receive as input the circuit, input or the plaintext updates. A sequential updatable RE scheme is secure if an efficient adversary cannot tell apart real world from the ideal world.

The ideal world is formalized by considering a simulator $\mathsf {Sim}$ that runs in probabilistic polynomial time. $\mathsf {Sim}$ gets as input the output of circuit C(x), the length of C and produces a simulated randomized encoding. We emphasize that $\mathsf {Sim}$ does not receive as input C or x. After this, $\mathsf {Sim}$ simulates the update encodings. On input length of update ${\mathbf {u}}_i$, value $C_i(x_i)$, it generates a simulated encoding of ${\mathbf {u}}_i$. Here, $C_i(x_i)$ is obtained by first updating $C_{i-1}[x_{i-1}]$ using ${\mathbf {u}}_i$ to obtain $C_i[x_i]$, whose output is $C_i(x_i)$ and also, $C_0[x_0]$ is initialized with C[x]. For this discussion, we consider the scenario where the circuit, input along with the updates are fixed at the beginning of the experiment. This is termed as the selective setting. We describe the formal experiment in Fig. 1.

We present the formal security definition below.

Definition 6

(SIM-secure Sequential URE). A sequential URE scheme $\mathsf {URE}$ for $(\mathsf {Upd},{\mathcal {U}})$-updatable class of circuits ${\mathcal {C}}=\{{\mathcal {C}}_{\lambda }\}_{\lambda \in {\mathbb {N}}}$ is said to be SIM-secure if for every PPT adversary ${\mathcal {A}}$, for every circuit $C \in {\mathcal {C}}_{\lambda }$, updates ${\mathbf {u}}_1,\ldots ,{\mathbf {u}}_{q} \in {\mathcal {U}}_{\lambda }$, there exists a PPT simulator $\mathsf {Sim}$ such that the following holds for sufficiently large $\lambda \in {\mathbb {N}}$,

$$\begin{aligned}&\left| {{\mathsf {P}}}{{\mathsf {r}}}\left[ 0 \leftarrow \mathsf {IdealExpt}^{{\mathcal {A}}}\left( 1^{\lambda },C,x,\{{\mathbf {u}}_i\}_{i \in [q]} \right) \right] \right. \\&\qquad \left. -\,\, {{\mathsf {P}}}{{\mathsf {r}}}\left[ 0 \leftarrow \mathsf {RealExpt}^{{\mathcal {A}}}\left( 1^{\lambda },C,x,\{{\mathbf {u}}_i\}_{i \in [q]} \right) \right] \right| \le \mathsf {negl}(\lambda ), \end{aligned}$$

where $\mathsf {negl}$ is a negligible function.

Fig. 1.

Selective simulation-based definition of sequential URE.

We also define indistinguishability-based security notion. We show a transformation from indistinguishability-based security notion to simulation based security notion. This can be found in the full version.

5 Output-Compact URE from FE

In this section, we present our construction of updatable randomized encodings satisfying output compactness properties.

5.1 Construction

Our goal is to construct an updatable randomized encoding scheme, $\mathsf {URE}=({\mathsf {Encode}},{\mathsf {GenUpd}},\mathsf {ApplyUpd},{\mathsf {Decode}})$ for ${\mathcal {C}}$. The main tools we use in our construction are the following. We refer the reader to the preliminaries for the definitions of these primitives.

• Randomized Encoding scheme, ${{\mathsf {R}}}{{\mathsf {E}}}=({{\mathsf {R}}}{{\mathsf {E}}}.\mathsf {Enc},{{\mathsf {R}}}{{\mathsf {E}}}.\mathsf {Dec})$ for the same class of circuits ${\mathcal {C}}$.

• Compact, Function-private, Single-Key, Secret-key functional encryption (FE) scheme, ${{\mathsf {F}}}{{\mathsf {E}}}=(\mathsf {{{\mathsf {F}}}{{\mathsf {E}}}.Setup},{{\mathsf {F}}}{{\mathsf {E}}}.\mathsf {KeyGen},{{\mathsf {F}}}{{\mathsf {E}}}.\mathsf {Enc},{{\mathsf {F}}}{{\mathsf {E}}}.\mathsf {Dec})$.

• Garbling Scheme for circuits, ${{\mathsf {G}}}{{\mathsf {C}}}=(\mathsf {GrbCkt},\mathsf {GrbInp},\mathsf {EvalGC})$.

Remark 1

In the full version [2], we show that compact secret-key functional encryption is necessary for our construction of updatable randomized encodings if we believe that learning with errors assumption holds true.

We assume, without loss of generality, that all randomized algorithms require only $\lambda$-many random bits. We use the above tools to design the algorithms of $\mathsf {URE}$ as given below.

The updatable randomized encoding of (C, x) will consist of a (standard) randomized encoding (C, x) and some additional information necessary to carry out the updating process. This additional information consists of a garbled input encoding of C and x with respect to ${{\mathsf {G}}}{{\mathsf {C}}}$, and a ${{\mathsf {F}}}{{\mathsf {E}}}$ secret key for a function that takes as input an update and outputs a garbled circuit mapping C and x to a new randomized encoding and new garbled circuit input encodings of $C'$ and $x'$, which are the updated values. Henceforth, we denote by s the size of the representation of the harwired circuit .

${\underline{{\mathsf {Encode}}\left( 1^{\lambda },C,x\right) }}$: On input security parameter $\lambda$, perform the following operations.

• 1. Execute the setup of ${{\mathsf {F}}}{{\mathsf {E}}}$, ${{\mathsf {F}}}{{\mathsf {E}}}.\mathsf {MSK}\leftarrow \mathsf {{{\mathsf {F}}}{{\mathsf {E}}}.Setup}(1^{\lambda })$.

• 2. Compute a functional key ${{\mathsf {F}}}{{\mathsf {E}}}.{{\mathsf {S}}}{{\mathsf {K}}}_\mathsf {RRGarbler}\leftarrow {{\mathsf {F}}}{{\mathsf {E}}}.\mathsf {KeyGen}({{\mathsf {F}}}{{\mathsf {E}}}.\mathsf {MSK},\mathsf {RRGarbler})$, where $\mathsf {RRGarbler}$ is as defined in Fig. 3.

• 3. In the next step, generate a randomized encoding of input (C, x). That is, compute ${{\mathsf {R}}}{{\mathsf {E}}}.\mathsf {Enc}(1^{\lambda },C,x)$ to obtain ${{\langle {C[x]}\rangle }_{{{\mathsf {r}}}{{\mathsf {e}}}}}$.

• 4. As stated earlier, let s be the size of the representation of . Generate a garbled circuit input encoding of by evaluating , where $r_{{{\mathsf {gc}}}}$ is the randomness used to garble the input. Here we view as an input (to the circuit $\mathsf {RelockRelease}$).

• 5. Output as the randomized encoding the tuple,

  

  and set the state to be ${\mathsf {st}}=\left( {{\mathsf {F}}}{{\mathsf {E}}}.\mathsf {MSK},\ r_{{{\mathsf {gc}}}} \right)$.

Fig. 2.

RelockRelease$_{i+1}$.

Fig. 3.

RRGarbler.

${\underline{{\mathsf {GenUpd}}\left( {\mathsf {st}}_i,\ {\mathbf {u}}_{i+1} \right) }}$: It takes as input the state ${\mathsf {st}}_i=\left( {{\mathsf {F}}}{{\mathsf {E}}}.\mathsf {MSK}, r_{{{\mathsf {gc}}},i} \right)$ and update ${\mathbf {u}}_{i+1}$.

• 1. Sample random coins $r_{{{\mathsf {r}}}{{\mathsf {e}}},i+1}$ and $r_{{{\mathsf {gc}}},i+1}$. Let $\mathsf {mode}= 0$.

• 2. Generate the FE ciphertext,

  $$\begin{aligned}{{\mathsf {C}}}{{\mathsf {T}}}_{i+1} \leftarrow {{\mathsf {F}}}{{\mathsf {E}}}.\mathsf {Enc}\left( {{\mathsf {F}}}{{\mathsf {E}}}.\mathsf {MSK},\ \left( {\mathbf {u}}_{i+1},\ \bot ,\ r_{{{\mathsf {gc}}},i},\ r_{{{\mathsf {gc}}},i+1},\ r_{{{\mathsf {r}}}{{\mathsf {e}}},i+1},\ \mathsf {mode}\right) \right) \end{aligned}$$

• 3. Set the new state ${\mathsf {st}}_{i+1} =\left( {{\mathsf {F}}}{{\mathsf {E}}}.\mathsf {MSK},\ r_{{{\mathsf {gc}}},i+1} \right)$.

• 4. Output ${\langle {\mathbf {u}}_{i+1}\rangle }_\mathsf {ure} = {{\mathsf {C}}}{{\mathsf {T}}}_{i+1}$.

${\underline{\mathsf {ApplyUpd}\left( {\left\langle C_i[x_i]\right\rangle }_{\mathsf {ure}},{\langle {\mathbf {u}}_{i+1}\rangle }_\mathsf {ure} \right) }}$: On input circuit encoding ${\left\langle C_i[x_i]\right\rangle }_{\mathsf {ure}}$ and update encoding ${\langle {\mathbf {u}}_{i+1}\rangle }_\mathsf {ure} = {{\mathsf {C}}}{{\mathsf {T}}}_{i+1}$, execute the following (Fig. 2).

• 1. Parse the circuit encoding as:

  

• 2. Execute the FE decryption, ${{\mathsf {F}}}{{\mathsf {E}}}.\mathsf {Dec}({{\mathsf {F}}}{{\mathsf {E}}}.{{\mathsf {S}}}{{\mathsf {K}}}_{\mathsf {RRGarbler}},{{\mathsf {C}}}{{\mathsf {T}}}_{i+1})$ to obtain:

  $$\begin{aligned}{{\langle {\mathsf {RelockRelease}_{i+1}}\rangle }_{{\mathsf {gc}}}}.\end{aligned}$$

• 3. Execute the decode algorithm of the garbling scheme,

  

  That is, the decode algorithm outputs the randomized encoding of updated hardwired circuit $C_{i+1}[x_{i+1}]$ and also wire keys of that will be input to the next level garbled circuit.

• 4. Output .

: On input encoding

decode the encoding ${{\langle {C_{i}[x_{i}]}\rangle }_{{{\mathsf {r}}}{{\mathsf {e}}}}}$ by executing ${{\mathsf {R}}}{{\mathsf {E}}}.\mathsf {Dec}({{\langle {C_{i}[x_{i}]}\rangle }_{{{\mathsf {r}}}{{\mathsf {e}}}}})$ to obtain $\alpha$. Output the value $\alpha$.

In the full version [2], we show that the above scheme satisfies all the properties of an updatable randomized encodings scheme.