Mutable Batch Arguments and Applications

An aggregate signature [17] scheme allows public aggregation of a sequence of verification-key-message-signature tuples ${\{({\mathrm{𝗏𝗄}}_i,m_i,{\sigma }_i)\}}_i$ into a single short aggregated signature $\widehat{\sigma }$. Such signatures prove possession of signatures for $m_i$ under key ${\mathrm{𝗏𝗄}}_i$ (for all $i$) by just providing $\widehat{\sigma }$. In a recent work [52], Goyal and Vaikuntanthan studied a new generalization of aggregate signatures. Their goal was to enable fast verification of an aggregate signature, where a local verifier can check signature validity for a single message in time and space independent of the number of signatures aggregated. To avoid trivial impossibility, they defined an additional algorithm referred to as the hint generator that creates a short hint for an aggregated signature. Given such a short hint, a verifier can locally and efficiently inspect whether a signature for a particular message was aggregated inside the aggregated signature without reading all the verification-key-message pairs.

As an application of mutable BARGs supporting identity mutations, we obtain the first locally verifiable multi-signer aggregate signature satisfying message privacy under adversarial openings from standard assumptions. Prior works on aggregate signatures with local verifiability did not achieve such properties. Either they worked in the single-signer model [52], or relied on SNARGs for $\mathrm{𝐍𝐏}$.

Our starting point is a recent observation [78, 44] that BARGs can be used generically to obtain aggregate signature. The key intuition was that the aggregation procedure can be implemented as a BARG prover where the sequence of key-message pairs ${\{({\mathrm{𝗏𝗄}}_i,m_i)\}}_i$ can be used as the instance, and their corresponding signatures ${\{{\sigma }_i\}}_i$ as the witnesses. We show that this core idea can be naturally extended to the local verifiability model. By replacing the underlying BARG with a mutable BARG for identity mutations, the resulting aggregate signature scheme also satisfies desired local verifiability property. The resulting construction also satisfies strong message privacy for such aggregate signatures, which was not known previously. We refer to the full version for more details.

At first glance, it might appear that designing mutable BARGs for subset mutations could be more challenging. Interestingly, we show this is not the case, and design a generic approach from identity mutations to subset mutations. Our main observation is that a locally verifiable BARG is really a deletable BARG, where the deletion operation only supports deletion of “all-but-one” instances. That is, if the goal is to delete all but the $j^{th}$ instance, then we could simply run $\mathrm{𝖫𝖮𝗉𝖾𝗇}$ on proof $\pi$ for instances ${\{x_i\}}_i$ with target index $j$ to generate a local opening ${\mathrm{𝖺𝗎𝗑}}_j$ for $x_j$. Here opening ${\mathrm{𝖺𝗎𝗑}}_j$ along with the mutated proof ${\pi }^{\prime }$ can be viewed as a redacted proof for instance $x_j$.

With the above observation, our strategy for building de-BARGs is to lift the mutable BARG scheme supporting all-but-one deletion into a scheme that supports arbitrary deletion. To execute this, we use a rather simple idea. The general deletion algorithm now works in two phases– (1) it simply generates local openings for every instance that is not being deleted (i.e., ${\{x_i\}}_{i\notin S}$), and (2) then generates a fresh BARG proof for all these instances ${\{x_i\}}_{i\notin S}$ using the individual all-but-one deleted proofs as the new witnesses. Basically, we are recursively generating BARGs of BARGs to perform deletion. The core insight here is that the local verifiability feature enables translating a short proof $\pi$ with large verification time (due to having to read entire batch of instances) into another short proof $\mathrm{𝖺𝗎𝗑}$ with small verification time (as $\mathrm{𝖫𝖵𝖿𝗒}$ only reads a single instance). Thus, while BARGing of BARGs could have been very inefficient (and also not necessarily privacy preserving), introducing local verifiability as an intermediate operation before BARGing a proof again solves the efficiency problem. Moreover, as long as the local openings also satisfy mutation privacy, this approach ensures full deletion privacy nearly generically. We discuss the above (and achieving more properties) in detail in the full version.

Extending to general subset mutations. We highlight that the above approach directly extends to the more general setting of subset mutations. That is, even when the instance lists $X_i$’s and corresponding proofs ${\pi }_i$’s are no longer identical, the above strategy is sufficient for handling subset mutations. Although there is one subtle technical difference. When all the instance lists and proofs are the same, then our approach guarantees that the size of the mutated (deleted) proof grows only by an additive factor that can be made independent of the original witness size. This is because in our formulation locally opened proofs have two components– auxiliary opening information and a mutated batch proof. Now for a fixed batch proof, the actual mutated batch proof portion for different target indices are the same. Thus, they can be simply kept as part of the instance or the $\mathrm{𝐍𝐏}$ language instead. This optimization suggests that the locally opened proofs for a single batch proof can be batched more efficiently, but this cannot be guaranteed when $X_i$’s and ${\pi }_i$’s are no longer identical. It is an interesting problem to design mutable BARGs for general subset mutations with only a fixed polynomial additive proof growth. We believe that this might either need to develop new algebraic techniques for composing batch arguments, or a careful use of optimal-rate batch arguments [44, 70].

Redactable signatures [57, 76] allow a signature holder to publicly censor parts of a signed document such that the corresponding signature $\sigma$ can be efficiently updated without the secret signing key, and the updated signature can still be verified given only the redacted document. These signatures have many real-world applications in privacy-preserving authentication as they can be used to sanitize digital signatures. (See [43, 42] for a detailed overview.) We show that deletable BARGs provide a clean and natural framework to design redactable signatures with many interesting properties.

Our intuition is to make a signer partition the document into equal sized chunks and sign each chunk⁴⁴4By a chunk, we refer to the smallest portion of the message that a user might want to redact. E.g., depending upon application, one can partition word-by-word or sentence-by-sentence. individually. For simplicity, one could consider breaking a long message bit-by-bit, and signing each bit individually along with its position in the message. Next, using de-BARGs, a signer can create a succinct batch proof proving knowledge of valid signatures for each chunk. (In order to prevent trivial forgery attacks, the signer alsos sample a random tag and adds the same tag to each chunk before signing. This avoids trivial mix-and-match forgery attacks.) We show by a simple reduction to de-BARGs and signature security that the above scheme satisfies stronger notions of unforgeability. More importantly, this also enables a simple approach to redact signatures. Whenever a user has to redact a signature (i.e., a batch proof as per our design), then it can run the proof deletion algorithm to delete desired chunks. The resulting deleted proof is then set as the redacted signature. Any user can verify the redacted signature given just the non-redacted message chunks and their locations. Moreover, deletion privacy of de-BARGs also guarantees that the resulting scheme guarantees privacy of redacted messages.

We want to point out that in all known redactable signatures, the size of a redacted signature scales at least linearly with the length of non-redacted message. However, our redactable signatures are truly optimal since both the non-redacted and redacted signatures are of fixed size. Thus, to the best of our knowledge, this gives the first truly compact redactable signature scheme where all system parameter sizes are asymptotically optimal. We refer to the full version for more details.

Our intuition is that, to support ${ℒ}_{𝒞}^{(k)}$ mutations, it is sufficient to combine SNARGs for ${ℒ}_{𝒞}^{(k)}$ with any lc-BARG scheme. This further illustrates the fundamental nature of the identity mutation class as it enables such a wide array of mutation functions via simple generic compilers. Our main idea is as follows. The prover and verifier algorithms for the mutable BARG system simply use the lv-BARG prover and verifier algorithms as is. Now, to mutate a sequence of $k$ index-instances-proof tuples ${\{(j_i,X_i,{\pi }_i)\}}_i$ w.r.t. monotone circuit $C$, one performs a two-step approach: first, each batch proof ${\pi }_i$ is locally opened for index $j_i$; second, run the $\mathrm{𝖻𝖺𝗍𝖼𝗁𝖭𝖯}$ SNARG prover for circuit $C$ and instances ${\{x_{i,j_i}\}}_i$ using the locally opened proofs as the corresponding witnesses. The output proof is simply set to be the succinct mutated proof.

Unfortunately, soundness of the above design is not as straightforward. This is because the underlying lv-BARG scheme is only computationally sound, thus to argue soundness of the above design we need a reasonable notion of extraction for the underlying SNARGs. So far, for other mutation classes, the notion of somewhere extractability for BARGs was sufficient. However, here we need a stronger notion of extractability for the $\mathrm{𝖻𝖺𝗍𝖼𝗁𝖭𝖯}$ SNARGs. A starting point would be to rely on the somewhere argument of knowledge property for such SNARGs as defined in [23], but it is unclear how to select the “necessary subset” non-adaptively to enable somewhere extraction. Fortunately, Brakerski et al. [23] also proved a stronger notion of non-adaptive full extractability for their SNARGs. Specifically, they proved their SNARG to be an argument of knowledge under the hardness of learning with errors assumption [72]. By relying on full extractability, we can bypass the above technical issue and prove non-adaptive soundness of our mutable BARG system. Furthermore, we can combine this with somewhere extractability of our underlying lv-BARG system to get obtain an appropriate notion of somewhere extractability for our mutable BARG proof system. This property will be later useful for our final application to homomorphic signatures.

Later in the full version, we provide the above construction in full detail. Next, we overview the key ideas behind our homomorphic signature schemes based on mutable BARGs.

Homomorphic signatures [3, 15, 16] allow a signature holder to publicly run homomorphic computations on a signature, without the knowledge of the signing key. As discussed in many prior works [3, 15, 16, 27, 28, 51, 46], homomorphic signatures are very useful for numerous applications.

Our observation is that any mutable BARG system supporting monotone policy $\mathrm{𝖻𝖺𝗍𝖼𝗁𝖭𝖯}$ mutations can be used to design homomorphic signatures for circuits. That is, even when the mutable BARG system only support mutation of monotone circuits, we can still design homomorphic signatures to evaluate non-monotone circuits. Let us first explain the core idea by evaluating monotone circuits, and later we discuss how this can be generalized for arbitrary non-monotone circuits as well.

Homomorphically evaluating monotone circuits. As a starting point, let us consider the simpler case of evaluating monotone circuits with single-bit output, and consider that the attacker’s goal is to create a forgery ${\sigma }^{\prime }$ w.r.t. a monotone circuit $C^{\ast }$, such that the circuit’s output is $0$ on the queried dataset $M=(m_1,\mathrm{\dots },m_{\mathrm{\ell }})$, yet the verifier accepts it as a valid signature for output bit $1$. We informally refer to this as 1-sided forgery. This simplifying assumption follows without loss of generality.

Our core insight for designing homomorphic signatures for monotone circuits (with 1-sided forgery as describe above) is to simply start with an aggregate signature scheme from BARGs that we discussed earlier, and use the monotone policy $\mathrm{𝖻𝖺𝗍𝖼𝗁𝖭𝖯}$ mutation feature for BARGs to compute the evaluated signature as a mutated batch proof. In words, the idea is to generate signatures individually (using a standard signature scheme), and then aggregate them using the BARG prover’s algorithm. That is, each dataset bit-value pair $(i,m_i)$ is individually signed using a regular signing key $\mathrm{𝗌𝗄}$. Then all these bit-by-bit signatures ${\sigma }_i$ are aggregated in a batch proof $\pi$. Since we only want to guarantee 1-sided forgery, we do not aggregate all signatures ${\sigma }_i$ but only those where the corresponding message bit $m_i=1$. That is, we only aggregate a signature if it can be useful⁶⁶6Note that since we are only considering monotone circuits here, thus only an input wire with value $1$ can be useful in proving the output of the circuit is $1$. in proving the evaluated circuit output to be $1$.

Now the idea for evaluating a monotone circuit on any given signature $\sigma$ of some dataset $M=(m_1,\mathrm{\dots },m_{\mathrm{\ell }})$ is to simply run the proof mutation algorithm on the signature $\sigma$, where the mutation function is set to be $C$. To fit the notation of the mutation function, we have to set the index-instances-proof tuples ${\{(j_i,X_i,{\pi }_i)\}}_i$ appropriately. That is, each ${\pi }_i$ is either $\sigma$ or (depending upon $i^{th}$ message bit $m_i$), and the index-instances are set as $j_i=i$ and $X_i=(1,\mathrm{\dots },\mathrm{\ell })$.⁷⁷7In the main body, we set the values a bit differently for technical reasons. However, the intuition stays the same. The proof of unforgeability boils down to the mutation (knowledge) soundness of the underlying mutable BARG. Moreover, the signature scheme also satisfies context hiding if the BARG scheme satisfies mutation privacy. Since both of these propoerties are satisfied by our design of mutable BARGs, thus our homomorphic signatures are unforgeable and context hiding.

Beyond monotone circuits. While at first it might seem that designing homomorphic signature for classes beyond monotone circuits will be difficult following the above approach (unless we can design non-monotone $\mathrm{𝖻𝖺𝗍𝖼𝗁𝖭𝖯}$ SNARGs), we show this can be done. Our intuition is to rely on folklore approaches to transform any non-monotone boolean circuits into monotone boolean circuits by introducing more input wires. Concretely, our approach is to use well-known and commonly-used technique of translating any non-monotone boolean circuits into a monotone boolean circuits of similar size.

Once we do such a transformation, then we can just use the proof mutation algorithm as before to mutate a BARG proof for “monotonized” circuit $C^{\neg }$. The soundness and context hiding proofs also can be naturally reduced to the security of underlying mutable BARGs and signature scheme. Later in the full version, we describe this in full detail. We briefly remark that our usage of mutable BARGs as an abstraction also ensures that our homomorphic signatures satisfy many new interesting properties such as aggregatability of signatures and evaluation of aggregate signatures etc. This shows additional advantages of using mutable batch arguments as a core cryptographic primitive for applications. Moreover, our template for designing homomorphic signatures also readily extends to handle homomorphic computations over signatures created by multiple signers (i.e., multi-key setting [46]) as well as multi-hop evaluation of already evaluated signatures.

This concludes the overview of our main results and applications. Next, we briefly discuss some additional results and related work.

In a concurrent work, Anthoine et al. [6] designed multi-key homomorphic signatures [46] by combining batch arguments and functional commitments [64]. Their scheme only supports chained multi-hop evaluation (where only a single evaluated signature can be further evaluated), whereas our homomorphic signatures support general multi-hop evaluation (where multiple evaluated signatures can be further evaluated). However, they could support a polynomial number of multi-hop evaluations, while we can only support constant number of multi-hop evaluations.

In two independent works, Brodsky et al. [25] and Nassar et al. [68] introduced and designed a new generalization of aggregate signatures called monotone-policy aggregate signatures. Such aggregate signatures enable aggregating signatures on a fixed message $m$ coming from $\le n$ different signers w.r.t. an $n$-bit monotone-policy predicate $P$. Although these signatures seem incomporable to out applications, we believe we can also design them from our mutable BARGs by adjusting our homomorphic signatures. In a follow-up work, Afshar et al. [2] extended our techniques to design (multi-key) homomorphic signatures that could support polynomial number of multi-hop evaluations.

As a feasibility result, we outline a high level sketch for constructing general mutable BARGs from any succinct non-interactive arguments of knowledge (SNARKs) [63, 66]. The idea is to simply use the mutation program $P$ along with entire list of index-instances-proof tuples ${\{(j_i,X_i,{\pi }_i)\}}_i$ as the witness for showing the validity of the mutated instance $x_P=P(x_{1,j_1},\mathrm{\dots },x_{\mathrm{\ell },j_{\mathrm{\ell }}})$ as per language ${ℒ}_P$. Now, whenever $P$ and ${\{(j_i,X_i,{\pi }_i)\}}_i$ are enough to efficiently decide $x_P\in {ℒ}_P$, then we can simply create a SNARK proof using them as the witness⁸⁸8As we discussed earlier, mutable BARGs are only feasible when $P$ and ${\{(j_i,X_i,{\pi }_i)\}}_i$ are sufficient to efficiently decide whether $x_P\in {ℒ}_P$ or not. If this is not feasible, then it is unclear whether such a mutable BARG can be designed.. And, any cheating prover can be caught by running the SNARK extractor, and using that to break soundness of the underlying BARG scheme. This suggests that assuming SNARKs, we can design general-purpose mutable BARGs. Our focus is on designing mutable BARGs from standard falsifiable assumptions.

As we hinted earlier, we also studied alternate approaches to design locally verifiable BARGs with mutation privacy. One successful strategy is to use NIZKs as a last step; that is, take a locally opened batch proof and then create a NIZK proof of it. Since all inputs to the local verifier are short, thus the size of the NIZK proof will still be short. Moreover, the resulting mutated proof satisfies mutation privacy because of the zero-knowledge property. Concretely, given a (non-private) local opening $\mathrm{𝖺𝗎𝗑}$ and batch proof $\pi$, we could generate a NIZK proving knowledge of $\mathrm{𝖺𝗎𝗑}$ and $\pi$ such that they verify membership of target instance $x$.

While this also satisfies mutation privacy and seems simpler than our current approach, this has multiple limitations that we briefly summarize.

1. 1.

   Complementary mutations. Using puncturable PRFs, we could easily handle complementary mutations. However, it seems unclear whether that follows from NIZKs-on-top approach.

2. 2.

   Inefficient proof mutation. Further, by using NIZKs-on-top, the proof mutation algorithm would run in time polynomial in the witness size. This is because a batch proof size does grow with the size of a single witness and, if this batch proof is used as a witness by a NIZK prover, the proof mutation algorithm runtime would grow polynomially with the witness size. Our approach already gives us fast proof mutation.

3. 3.

   Black-box vs. non-black-box. We wanted to avoid making non-black-box use of BARGs (if at all possible). Using NIZKs as a last step would mean making non-black-box use of cryptography, both inside and outside BARGs. Our current transformations only make black-box use of BARGs, and only within BARG themselves do we make non-black-box use of other cryptographic objects. We believe this will eventually lead to more practical constructions.

4. 4.

   Minimizing assumptions. Moreover, from a theoretical view point, our approach requires far simpler assumptions. Observe that in our current construction (combining all individual transformations in one bigger transformation), we only need to rely on a NIZK proof system for language $ℒ\wedge \mathrm{𝖢𝖮𝖬}.\mathrm{𝖵𝖾𝗋𝗂𝖿𝗒}$. That is, we need a NIZK for just a slightly bigger language than $ℒ$. Whereas NIZKs-on-top would need a NIZK proof for language defined by the BARG verifier circuit which is far more complicated. E.g., if $ℒ$ is simply $\mathrm{𝐔𝐏}$, then our approach only needs the minimal assumptions of BARGs and NIZKs for $\mathrm{𝐔𝐏}$ (since $\mathrm{𝖢𝖮𝖬}.\mathrm{𝖵𝖾𝗋𝗂𝖿𝗒}$ can be specified within $\mathrm{𝐔𝐏}$ as well). Thus, our current approach seems to be a better approach for understanding minimal cryptographic complexity of these concepts.

   Lastly, although currently we have a separate transformation for making our BARGs witness private, our hope is that concrete BARG constructions in the future might be directly zero-knowledge by exploiting the underlying mathematical structure in them. This would lead to concretely efficient constructions of instance private BARGs.

Additionally, we show that we can prove adaptive soundness of BARGs from the polynomial harndess of any non-adaptively-sound BARG by relying on sub-exponential hardness of somewhere extractable hash (SEH) functions. Recall that adaptive soundness states that an attacker receives $\mathrm{𝖼𝗋𝗌}$ before selecting the batch of instances ${\{x_i\}}_i$ and the proof $\pi$ it submits as its soundness attack. It is well known [24] that there are significant technical challenges to adaptive soundness from falsifiable assumptions. However, we show these barriers can be bypassed if BARG is only somewhere extractable and not everywhere extractable. While this does not impact our results, we formalize this later in the full version as it may be of independent interest⁹⁹9In an independent work, Bradley et al. [22] also observed that sub-exponentially somewhere sound BARGs are also adaptively sound. Our transformation proves a slightly more general statement as we show that just sub-exponentially secure SEH is enough to go from somewhere sound BARGs to adaptively sound BARGs..

BARGs for $\mathrm{𝐍𝐏}$ follow directly from any SNARG for $\mathrm{𝐍𝐏}$, and starting with the work of Micali [66], there has been tremendous research advances in designing SNARGs from a wide variety of assumptions. However, all such current constructions of SNARGs for $\mathrm{𝐍𝐏}$ rely on either idealized assumptions [54, 9, 34, 33, 75], or non-falsifiable assumptions [53, 11, 39, 65, 71, 48, 14, 13, 18, 10], or obfuscation [74]. Moreover, due to Gentry-Wichs [49], we know that we cannot build an adaptively sound SNARG for $\mathrm{𝐍𝐏}$ (via a black-box reduction) to a falsifiable assumption [67]. The landscape for BARGs for $\mathrm{𝐍𝐏}$ from standard assumptions is a lot more promising due to several outstanding results [60, 37, 38, 61, 78, 56, 36, 59, 44, 70, 58].