Attribute-Based Signatures for Unbounded Circuits in the ROM and Efficient Instantiations from Lattices

Abstract

Attribute-based signature (ABS), originally introduced by Maji et al. (CT-RSA’11), represents an essential mechanism to allow for fine-grained authentication. A user associated with an attribute x can sign w.r.t. a given public policy C only if his attribute satisfies C, i.e., $C(x)=1$. So far, much effort on constructing bilinear map-based ABS schemes have been made, where the state-of-the-art scheme of Sakai et al. (PKC’16) supports the very wide class of unbounded circuits as policies. However, construction of ABS schemes without bilinear maps are less investigated, where it was not until recently that Tsabary (TCC’17) showed a lattice-based ABS scheme supporting bounded circuits as policies, at the cost of weakening the security requirement.

In this work, we affirmatively close the gap between ABS schemes based on bilinear maps and lattices by constructing the first lattice-based ABS scheme for unbounded circuits in the random oracle model. We start our work by providing a generic construction of ABS schemes for unbounded-circuits in the rand om oracle model, which in turn implies that one-way functions are sufficient to construct ABS schemes. To prove security, we formalize and prove a generalization of the Forking Lemma, which we call “general multi-forking lemma with oracle access”, capturing the situation where the simulator is interacting with some algorithms he cannot rewind, and also covering many features of the recent lattice-based ZKPs. This, in fact, was a formalization lacking in many existing anonymous signatures from lattices so far (e.g., group signatures). Therefore, this formalization is believed to be of independent interest. Finally, we provide a concrete instantiation of our generic ABS construction from lattices by introducing a new $\varSigma$-protocol, that highly departs from the previously known techniques, for proving possession of a valid signature of the lattice-based signature scheme of Boyen (PKC’10).

1 Introduction

1.1 Background

Attribute-based signature (ABS) was introduced by [MPR11] as a versatile tool allowing a signer to anonymously authenticate a message $\mathsf {M}$ w.r.t. a public signing policy C only if the signer has a signing key associated to an attribute $x\in \{0,1\}^*$ that satisfies C, i.e., $C(x)=1$. An attribute-based signature scheme reveals no information on the signer’s identity or the attribute other than the fact that the signature is valid, hence the anonymity property of ABS schemes. One of the central research themes on ABS is to expand the expressiveness of the class of policies that can be supported by the schemes. In the bilinear map setting, there has been a long line of interesting works, including ABS schemes for threshold policy (e.g., [HLLR12]), boolean formula (e.g., [MPR11, OT11, OT13, EGK14]) and the current state-of-the-art; unbounded circuits [SAH16].¹

On the other hand, the constructions of ABS schemes without bilinear maps, in particular ABS schemes from lattices, are much less investigated. To the best of our knowledge, there are only two major works concerning lattice-based ABS schemes [EE16, Tsa17]. El Bansarkhani et al. [EE16] construct a lattice-based ABS scheme for boolean formulas using a non-interactive zero-knowledge (NIZK) proof system as the main building block, following one of the most promising ways of constructing ABS schemes [MPR11, EGK14, SAH16]. Informally, a signature for a signer with attribute $\mathbf {x}$ is simply a zero-knowledge proof attesting to the fact that he has a certificate corresponding to the attribute $\mathbf {x}$ issued by the authority and that the policy C associated to the message $\mathsf {M}$ satisfies $C(\mathbf {x}) = 1$. Although this approach has been very effective in the bilinear map setting where [SAH16] were able to obtain ABS schemes for unbounded circuits, this has not been the case for lattices. One of the main reasons behind this is the lack of efficient lattice-based NIZK proof systems for a wide enough language. In particular, we only have efficient NIZK proof systems tailored for specific languages, such as proving possession of a solution to the short integer solution (SIS) problem or the learning with errors (LWE) problem [LNSW13], proving possession of a valid signature of the Boyen digital signature scheme [Boy10, LLNW14, LNW15] and so on, which in general does not seem strong enough for constructing ABS schemes. Recently, [YAL+17] showed (informally) how to construct lattice-based NIZK proof systems for languages accepted by monotone span programs, however, this still does not seem strong enough to use as a building block for ABS schemes supporting unbounded circuits as policies.

Tsabary [Tsa17] constructs lattice-based ABS schemes following a different approach; they show equivalence between a homomorphic signature (HS) scheme and a (message-policy) ABS scheme. Therefore, based on the HS construction of Gorbunov et al. [GVW15], they achieve a lattice-based ABS scheme for bounded circuits that does not make use of NIZK proof systems.² Here, by bounded, we mean that the required hardness assumptions on the LWE and/or SIS problems grow exponentially in the depth of the circuit, e.g., to base the security of the ABS scheme under a polynomial LWE assumption, we need to restrict the depth of the circuit to be $O(\log \lambda )$, where $\lambda$ is the security parameter. However, it seems challenging to improve their techniques to ABS schemes for unbounded circuits, due to the inherent noise-growth incurred by the homomorphic operations of matrices while computing the circuit gate-by-gate. The only known method of overcoming these $O(\log \lambda )$ depth barrier concerning homomorphic operations is the bootstrapping technique of fully homomorphic encryptions [Gen09], however, it is still an open problem whether there is a signature analogue of this technique.

1.2 Our Contribution

In this paper, we affirmatively close the gap between the state-of-the-art ABS schemes based on bilinear maps and lattices by constructing the first lattice-based ABS scheme for unbounded circuits in the random oracle model. We start by providing a general construction of ABS schemes supporting unbounded-circuits as policies. We then give an instantiation in the lattice setting showing that all the building blocks required by our generic construction is obtainable from lattices. We stress that, despite the expressiveness of the signing policy, we manage to prove the security of our scheme under surprisingly mild SIS and LWE assumptions with polynomial modulus size $q = \tilde{O}(\ell \lambda ^{1.5})$, where $\ell$ denotes the length of the inputs to the circuits. Specifically, the required hardness assumptions are independent of the depth of the circuits that express the policies. Furthermore, the sizes of the public parameter, signing keys and signatures are $\tilde{O}(\ell \lambda ^2)$, $\tilde{O}(\lambda )$ and $\tilde{O}((\ell \lambda + \left| C \right| )\lambda ^2)$, respectively, where $\left| C \right|$ is the size of the circuit (i.e., policy) associated to the message.

To this end we prepare two new tools equipped for the lattice setting: we provide a generalization of the forking lemma of [PS00] which we call the general multi-forking lemma with oracle access and further construct a new lattice-based NIZK proof system for proving possession of a valid Boyen signature [Boy10] that departs from the previously known techniques (e.g., [LLNW14, LNW15]). Below, we give a more detailed overview of the techniques we used in our work.

Generic Construction of ABS for Unbounded Circuits. We propose a generic construction of ABS schemes supporting unbounded depth circuits as policies in the random oracle model³, which employs the following primitives as its building blocks; a commitment scheme, a digital signature scheme and a $\varSigma$-protocol for a sufficiently wide relation. As a separate theoretical contribution, since all of the above primitives are implied from one-way functions, our result implies that one-way functions are sufficient to construct an ABS scheme for unbounded circuits in the random oracle model. Here, the random oracle is used only to convert the underlying $\varSigma$-protocol into a NIZK proof system via the Fiat-Shamir transformation [FS86].

At a high level, the generic construction of our ABS scheme follows closely the bilinear map based construction of [SAH16] (which is non-generic and proven in the standard model). We briefly review the construction in slightly more detail; first, the attribute authority issues a signature $\sigma$ on an attribute $\mathbf {x}\in \{ 0, 1 \}^\ell$ to certify that a signer is indeed authorized to sign a message on behalf of that attribute. Then, to sign anonymously, the signer produces a zero-knowledge proof attesting to the following two facts:

• (I) the signature $\sigma$ issued by the authority is valid, and

• (II) the corresponding secret attribute $\mathbf {x}$ satisfies the circuit C associated to the message $\mathsf {M}$.

However, in spite of the similarities shared with the construction of [SAH16], the security proof of our construction requires a rather sensitive and technical analysis, which calls for new tools. This difficulty mainly stems from the fact that security proofs relying on the Fiat-Shamir-based NIZK proof systems are often times not as simple as the construction appears to be and in some cases the intuition may fail, e.g., [BPW12, BFW16].

Our proof of security of the generic ABS scheme relies on our generalization of the forking lemma of [PS00], which we call the general multi-forking lemma with oracle access. Our forking lemma can be seen as a generalization and a simplification of the general forking lemma of [BN06] and the improved forking lemma of [BPVY00]. In particular, we analyze the output behavior of an algorithm when run multiple times on related inputs, instead of when only run twice as in [BN06], while also providing it with oracle access to a deterministic algorithm. Recall that the original forking lemma of [PS00] applies to Fiat-Shamir type signature schemes and roughly states that, if there exists a valid forger $\mathcal {A}$, then one can rewind $\mathcal {A}$ initialized with the same randomness tape to find two accepting transcripts with the same commitment but different challenges, leading, via the special soundness property of $\varSigma$-protocols, to extract the secret signing key from the transcripts and hence a proof of security of the signature scheme in the random oracle model.

First, we require the forking lemma to analyze the output behavior of an algorithm on multiple runs to capture the situation arising in the recent lattice-based NIZK proof systems (e.g., [LNSW13, LLNW14, LNW15]) where the extractor of the underlying $\varSigma$-protocol requires more than two valid transcripts to extract a witness. Although the improved forking lemma of [BPVY00] captures this multiplicity of the forking lemma of a particular El Gamal-type signature scheme, it seems hard to apply in situations like ours where we are not dealing with regular signature schemes. Our forking lemma, similar to the one of [BN06], divorces the probabilistic essence of the forking lemma from any particular application context. Furthermore, our forking lemma provides worst-case rather than expected-time guarantees; the improved forking lemma of [BPVY00] roughly states that an expected $O(1/\epsilon )$ repeated executions of a forger $\mathcal {A}$ with advantage $\epsilon$ is required to extract a valid witness. We believe this feature to be more suitable for standard assumptions that are defined for PPT algorithms, as also stated in [BN06].

Second, and more importantly, our forking lemma allows the algorithm $\mathcal {A}$ that can be rewinded, to have oracle access to some algorithm $\mathcal O$ that cannot be rewinded. This is a useful feature for the forking algorithm to have in situations where the simulator cannot rewind all the algorithms which he is interacting with. This may be easiest to explain with a concrete example; in particular, when we reduce the $\mathsf {eu\text {-}cma}$ security of the underlying digital signature scheme to the security of our ABS scheme, the simulator (which is the $\mathsf {eu\text {-}cma}$ adversary) simulates the view of an ABS security game to the ABS adversary $\mathcal {A}$, and answers the queries made by $\mathcal {A}$ using its $\mathsf {eu\text {-}cma}$ challenger $\mathcal O$. At some point when $\mathcal {A}$ outputs a forgery for the ABS security game, the simulator hopes to extract the witness from the forgery and use it to win his own $\mathsf {eu\text {-}cma}$ security game. However, for this particular situation, the problem with all the previous forking lemmas is that the simulator will not be able to run the forking algorithm in the specified way; the simulator can rewind $\mathcal {A}$ to a particular point where the fork happens, however, the simulator cannot rewind the $\mathsf {eu\text {-}cma}$ challenger $\mathcal O$ in the same way, since it is outside the simulator’s (i.e., $\mathsf {eu\text {-}cma}$ adversary’s) control. Then, since the behavior of $\mathcal {A}$ is implicitly dependent on the behavior of the $\mathsf {eu\text {-}cma}$ challenger, the standard forking lemma does not provide meaningful analysis of the output of $\mathcal {A}$ on multiple runs. We therefore present a general multi-forking lemma with oracle access to capture these situations where the simulator is restricted to rewinding only some of the algorithms he is interacting with. We note that in case one is willing to use some algebraic problem such as the SIS or LWE problem as the underlying hardness assumption, these situations do not show up, since once given a fixed problem instance, the simulator can reuse it in every run to simulate the view to $\mathcal {A}$.

Finally, one of the benefits of using the Fiat-Shamir-based NIZK proof system is that we do not have to rely on the dummy attribute technique of those ABS schemes based on Goth-Sahai NIZK proof systems [MPR11, SAH16] to prove adaptive unforgeability and hence obtaining a more efficient signing algorithm. At a high level, this is because Fiat-Shamir based NIZK proof systems can be simulation-sound and extractable at the same time, whereas Goth-Sahai NIZK proof systems can only be instantiated to have one of the two properties. Therefore, during the proof of adaptive unforgeability, since the simulator needs to set up the common reference string in the extractable mode to extract a witness from the forgery, the simulator has to rely on these extra dummy attributes, which are never used in the actual scheme, to simulate signatures (i.e., proofs).

Instantiation from Lattices. To instantiate our generic ABS construction from lattices, we require three primitives: a signature scheme, a commitment scheme, and a $\varSigma$-protocol for a relation capturing the aforementioned items (I) and (II). As for the signature scheme, we can use the simple and efficient lattice-based signature scheme of Boyen [Boy10], which has been extensively studied in the lattice-based NIZK literatures. In particular, Ling et al. [LNSW13] provides an efficient $\varSigma$-protocol for proving possession of a valid Boyen signature (i.e., item (I)). However, unfortunately, it is not known whether the $\varSigma$-protocol of Ling et al. can be extended to prove circuit satisfiability, which is what we require in item (II), and in fact, recent subsequent results of [LLM+16, YAL+17] suggest that they are not powerful enough to capture circuit satisfiability. On the other hand, Xie et al. [XXW13] provides a lattice-based $\varSigma$-protocol for proving NP relations via arithmetic circuit satisfiability, which is what we exactly require in item (II), however, it does not seem possible to simply combine the two different types of $\varSigma$-protocols of [LNSW13, XXW13].

To this end, in this paper we present a new $\varSigma$-protocol for proving possession of a valid Boyen signature by expressing the verification algorithm of the Boyen signature as a simple arithmetic circuit that is compatible with the $\varSigma$-protocol of Xie et al. Specifically, since both items (I) and (II) can now be represented as arithmetic circuits, we can use the $\varSigma$-protocol of Xie et al. to obtain our desired $\varSigma$-protocol. The main observation is that, most operations that show up in lattice-based cryptography are composed of simple arithmetic operations such as matrix multiplications, and therefore naturally leads to simple arithmetic circuit representations. For our particular case, the verification algorithm of the Boyen signature scheme essentially boils down to checking two simple conditions; whether a vector $\mathbf {z}$ satisfies $||\mathbf {z} ||_\infty \le \beta$ and $\mathbf {A}\mathbf {z}= \mathbf {u}\mod q$, where we intentionally dismiss the message for simplicity. As it can be seen, the latter equation is readily expressed by a very simple arithmetic circuit. On the other hand, the first inequality requires some extra work, however, this too can be expressed as an simple arithmetic circuit without much overhead by efficiently encoding predicates such as $x {\mathop {\in }\limits ^{?}} \{ -1,0,1 \}$ into arithmetic circuits.

2 Preliminaries

2.1 Commitment Schemes with Gap Openings

We define a standard commitment scheme that supports an additional notion we call gap openings. This additional notion will make it conceptually easier when we combine it with gap-$\varSigma$-protocols, which we later define. Informally, a commitment scheme with a gap opening is a standard commitment scheme where there may exist additional valid openings that are never created during the commitment algorithm.

Definition 1

(Commitments). A commitment scheme with message space $\mathcal M$ and commitment space $\mathcal C$ is a triple of PPT algorithms $(\mathsf {C}.\mathsf {Gen}, \mathsf {C}.\mathsf {Com}, \mathsf {C}.\mathsf {Open})$ of the following form:

• $\mathsf {C}.\mathsf {Gen}(1^\lambda ) \rightarrow \mathsf {pk}$: The key generation algorithm takes as input the security parameter $1^\lambda$ and outputs a public commitment key $\mathsf {pk}$.

• $\mathsf {C}.\mathsf {Com}(\mathsf {pk}, \mathsf {M}) \rightarrow (c, d)$: The commitment algorithm takes as inputs the commitment key $\mathsf {pk}$ and message $\mathsf {M}\in \mathcal M$, and outputs a commitment/opening pair (c, d). We denote $\mathcal {D}_{\mathsf {Com}}(\mathsf {pk}, \mathsf {M})$ as the set of all possible outputs of this algorithm under fixed $\mathsf {pk}$ and $\mathsf {M}$.

• $\mathsf {C}.\mathsf {Open}(\mathsf {pk}, \mathsf {M}, c, d)\rightarrow 1 \backslash 0$: The deterministic opening algorithm takes as inputs the commitment key $\mathsf {pk}$, message $\mathsf {M}$ and commitment/opening pair (c, d) as inputs and outputs 1 or 0. We denote $\mathcal {D}_{\mathsf {G\text {-}Com}}(\mathsf {pk}, \mathsf {M})$ as the set of all possible pairs (c, d) this algorithm outputs 1 under fixed $\mathsf {pk}$ and $\mathsf {M}$.

Here, we require the commitment scheme to satisfy the following correctness notion: for all $\mathsf {M}\in \mathcal M, \mathsf {pk}\leftarrow \mathsf {C}.\mathsf {Gen}(1^\lambda ), (c, d)\leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, \mathsf {M})$ we have $\mathsf {C}.\mathsf {Open}(\mathsf {pk}, \mathsf {M}, c, d) = 1$.

It is clear that we have $\mathcal {D}_{\mathsf {Com}}(\mathsf {pk}, \mathsf {M}) \subseteq \mathcal {D}_{\mathsf {G\text {-}Com}}(\mathsf {pk}, \mathsf {M})$ for all $\mathsf {pk}$ and $\mathsf {M}\in \mathcal M$. We say the commitment scheme has a gap-opening when $\mathcal {D}_{\mathsf {Com}} \subset \mathcal {D}_{\mathsf {G\text {-}Com}}$. We require the following security notions for a commitment scheme:

Binding. We call the scheme unconditionally (resp. computationally) binding if for all (resp. PPT) algorithm $\mathcal {A}$, we have the following:

$$\begin{aligned} \Pr [ \mathsf {pk}\leftarrow \mathsf {C}.&\mathsf {Gen}(1^\lambda ); (c, \mathsf {M}, \mathsf {M}', d, d') \leftarrow \mathcal A(\mathsf {pk}) : \\&\mathsf {C}.\mathsf {Open}(\mathsf {pk}, \mathsf {M}, c, d) = \mathsf {C}.\mathsf {Open}(\mathsf {pk}, \mathsf {M}', c, d') = 1 \wedge \mathsf {M}\ne \mathsf {M}'] \le \mathsf {negl}(\lambda ) \end{aligned}$$

Note that even though such a pair (c, d) may never be outputted by the commitment algorithm $\mathsf {C}.\mathsf {Com}$, the binding property must hold even for adversaries that output $(c, d) \in \mathcal {D}_{\mathsf {G\text {-}Com}}(\mathsf {pk}, \mathsf {M}) \backslash \mathcal {D}_{\mathsf {Com}}(\mathsf {pk}, \mathsf {M})$.

Hiding. We call the scheme unconditionally (resp. computationally) hiding if for all (resp. PPT) algorithm $\mathcal {A}$ and any message $\mathsf {M}\in \mathcal M$, we have the following:⁴

$$\begin{aligned} \Pr [ \mathsf {pk}\leftarrow \mathsf {C}.\mathsf {Gen}(1^\lambda );~ b\leftarrow \{ 0, 1 \};~&c_0 \leftarrow \mathcal C;~ (c_1, d) \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, \mathsf {M}); \\&b' \leftarrow \mathcal A(\mathsf {pk}, \mathsf {M}, c_b): b= b'] \le 1/2 + \mathsf {negl}(\lambda ) \end{aligned}$$

2.2 Digital Signature Schemes

In this paper, we use deterministic digital signature schemes; a scheme where the randomness of the signing algorithm is derived from the secret key and message. We briefly recall the standard syntax and security notions, and refer the full version for the exact definition. A deterministic digital signature scheme is a tuple of PPT algorithms $(\mathsf {S}.\mathsf {KeyGen}, \mathsf {S}.\mathsf {Sign}, \mathsf {S}.\mathsf {Verify})$, such that the key generation algorithm $\mathsf {S}.\mathsf {KeyGen}$ outputs a verification key $\mathsf {vk}$ and a signing key $\mathsf {sk}$. The deterministic signing algorithm $\mathsf {S}.\mathsf {Sign}$ on input the signing key $\mathsf {sk}$ and a message $\mathbf {x}$ outputs a signature $\sigma$, and the verification algorithm $\mathsf {S}.\mathsf {Verify}$ verifies the signature $\sigma$ using the verification key $\mathsf {vk}$. We consider the standard security notion of existential unforgeability under an adaptive chosen message attack ($\mathsf {eu\text {-}cma}$).

2.3 Arithmetic Circuit Representation

Here, we explain how we represent an arithmetic circuit. Let $C$ be an arithmetic circuit over a ring $R$ having $\ell$ input wires, one output wire and N gates. Here the gates are labelled by either $+$ (addition) or $\times$ (product) gates. The input wires are indexed by $1, \cdots , \ell$, the internal wires are indexed by $\ell + 1, \cdots , \ell + N - 1$ and the output wire has index $\ell + N$. We assume each gate takes only two incoming wires with multiple fan-out wires, where all the fan-out wires are indexed with the same index. We specify the topology of an arithmetic circuit by a function $\mathsf {topo}: \{ \ell + 1, \cdots , \ell + N \} \rightarrow \{ +, \times \} \times \{ 1, \cdots , \ell + N-1 \} \times \{ 1, \cdots , \ell + N-1 \}$. They map a non-input wire to its first and second incoming wires in which these three wires are connected by either a gate labelled by $+$ or $\times$. For $( \star , i_1, i_2 ) \leftarrow \mathsf {topo}(i)$, we require that $i_1, i_2 < i$ where $\star \in \{ +, \times \}$.

2.4 Attribute-Based Signature Scheme

An attribute-based signature scheme supporting the class of arithmetic circuits $\mathcal C = \{ \mathcal C_{\lambda } \}_{\lambda \in \mathbb N}$ and message space $\{ 0, 1 \}^*$ is defined by the following four probabilistic polynomial time algorithms $(\mathsf {Setup}, \mathsf {KeyGen}, \mathsf {Sign}, \mathsf {Verify})$:

• $\mathsf {Setup}(1^\lambda , 1^\ell ) \rightarrow (\mathsf {mpk}, \mathsf {msk})$: The setup algorithm takes as input the security parameter $1^\lambda$ and the input length $1^\ell$ of the circuits in $\mathcal C_\ell$, and outputs the master public key $\mathsf {mpk}$ and the master secret key $\mathsf {msk}$.

• $\mathsf {KeyGen}(\mathsf {mpk}, \mathsf {msk}, \mathbf {x}) \rightarrow \mathsf {sk}_{\mathbf {x}}$: The signing key generation algorithm takes as input the master public key $\mathsf {mpk}$, the master secret key $\mathsf {msk}$ and an attribute $\mathbf {x}\in \{ 0, 1 \}^\ell$, and outputs a signing key $\mathsf {sk}_\mathbf {x}$.

• $\mathsf {Sign}(\mathsf {mpk}, \mathsf {sk}_\mathbf {x}, C, \mathsf {M}) \rightarrow \varSigma$: The signing algorithm takes as input the master public key $\mathsf {mpk}$, a secret key $\mathsf {sk}_\mathbf {x}$ associated with an attribute $\mathbf {x}$, a circuit $C\in \mathcal C_{\ell }$ and a message $\mathsf {M}\in \{ 0, 1 \}^*$, and outputs a signature $\sigma$.

• $\mathsf {Verify}(\mathsf {mpk}, \mathsf {M}, C, \varSigma ) \rightarrow \mathsf {Valid}/ \mathsf {Invalid}$: The verification algorithm takes as input the master public key $\mathsf {mpk}$, a message $\mathsf {M}$, a circuit $C$ and a signature $\varSigma$, and outputs $\mathsf {Valid}$ or $\mathsf {Invalid}$.

Correctness. We require the following correctness condition to hold: for all $\lambda , \ell \in \mathbb N$, $\mathbf {x}\in \{ 0, 1 \}^\ell$, $C\in \mathcal C_\ell$ such that $C(\mathbf {x}) = 1$, it holds with all but negligible probability that $\mathsf {Verify}(\mathsf {mpk}, \mathsf {M}, C$, $\mathsf {Sign}(\mathsf {mpk}, \mathsf {sk}_\mathbf {x}, C, \mathsf {M}))$ $= \mathsf {Valid}$, where the probability is taken over the randomness used in $(\mathsf {mpk}, \mathsf {msk}) \leftarrow \mathsf {Setup}(1^\lambda , 1^\ell )$ and $\mathsf {sk}_\mathbf {x}\leftarrow \mathsf {KeyGen}(\mathsf {mpk}, \mathsf {msk}, \mathbf {x})$.

We require two types of security notions for attribute-based signature schemes.

Definition 2

(Privacy). The security notion of privacy for an attribute-based signature scheme is defined by the following game between a challenger and an adversary $\mathcal {A}$:  

Setup. :

The challenger runs $(\mathsf {mpk}, \mathsf {msk}) \leftarrow \mathsf {Setup}(1^\lambda , 1^\ell )$ and gives $(\mathsf {mpk}, \mathsf {msk})$ to $\mathcal {A}$.

Challenge. :

$\mathcal {A}$ outputs a message $\mathsf {M}\in \{ 0, 1 \}^{*},$ two attributes $\mathbf {x}_0, \mathbf {x}_1 \in \{ 0, 1 \}^\ell$ and a circuit $C\in \mathcal C_\ell$ such that $C(\mathbf {x}_0) = C(\mathbf {x}_1) = 1$ to the challenger. The challenger first runs $\mathsf {sk}_{\mathbf {x}_\beta } \leftarrow \mathsf {KeyGen}(\mathsf {mpk}, \mathsf {msk}, \mathbf {x}_\beta )$ for $\beta = 0, 1$. Then, it picks a random bit $b \leftarrow \{ 0, 1 \}$ and returns to $\mathcal {A}$ the signature $\varSigma ^* \leftarrow \mathsf {Sign}(\mathsf {mpk}, \mathsf {sk}_{\mathbf {x}_b}, C, \mathsf {M})$ along with the two secret keys $(\mathsf {sk}_{\mathbf {x}_0}, \mathsf {sk}_{\mathbf {x}_1})$.

Forgery. :

Finally, $\mathcal {A}$ outputs a guess $b' \in \{ 0, 1 \}$ for b.

 

The advantage of $\mathcal {A}$ is defined as $\left| \Pr [b' = b] - 1/2 \right|$. We say that the attribute-based signature scheme is computationally private if the advantage of any PPT algorithm $\mathcal {A}$ is negligible. We say it is unconditionally private if the advantage of any (possibly inefficient) algorithm $\mathcal {A}$ is negligible.

Definition 3

(Unforgeability). The security notion of adaptively unforgeable for an attribute-based signature scheme is defined by the following game between a challenger and an adversary $\mathcal {A}$:

 

Setup. :

The challenger runs $(\mathsf {mpk}, \mathsf {msk}) \leftarrow \mathsf {Setup}(1^\lambda , 1^\ell )$ and gives $\mathsf {mpk}$ to $\mathcal {A}$.

Queries. :

$\mathcal {A}$ may adaptively make the following queries to the challenger:

 

• Signing. $\mathcal {A}$ submits a signing query on any attribute, message and circuit tuple $(\mathbf {x}, \mathsf {M}, C)$ such that $C(\mathbf {x}) = 1$ to the challenger. The challenger runs $\mathsf {sk}_\mathbf {x}\leftarrow \mathsf {KeyGen}(\mathsf {mpk}, \mathsf {msk}, \mathbf {x})$. Then, it returns the signature $\varSigma \leftarrow \mathsf {Sign}(\mathsf {mpk}, \mathsf {sk}_\mathbf {x}, C, \mathsf {M})$ to $\mathcal {A}$.

• Key reveal. $\mathcal {A}$ submits a key reveal query on any attribute $\mathbf {x}$ to the challenger. The challenger returns the signing key $\mathsf {sk}_\mathbf {x}\leftarrow \mathsf {KeyGen}(\mathsf {mpk}, \mathsf {msk}, \mathbf {x})$ to $\mathcal {A}$.

 

Forgery. :

Finally, $\mathcal {A}$ outputs a signature $(\mathsf {M}^*, C^*, \varSigma ^*)$.

  The adversary $\mathcal {A}$ wins the game if the following three conditions hold:

 

(i) :

$\mathsf {Verify}(\mathsf {mpk}, \mathsf {M}^*, C^*, \varSigma ^*) = \mathsf {Valid}$,

(ii) :

Adversary $\mathcal {A}$ did not submit a key reveal query for $\mathbf {x}$ such that $C^*(\mathbf {x}) = 1$,

(iii) :

Adversary $\mathcal {A}$ did not submit a signing query on $(\mathbf {x}, \mathsf {M}^*, C^*)$ for any $\mathbf {x}$ such that $C^*(\mathbf {x}) = 1$.

 

The advantage of $\mathcal {A}$ is defined as the probability of $\mathcal {A}$ winning the above game. We say that the attribute-based signature scheme is adaptively unforgeable if the advantage of any PPT algorithm $\mathcal {A}$ is negligible.

2.5 General Multi-forking Lemma with Oracle Access

Here we state and prove an extended version of the forking lemma of [PS00], which will play a central role in our proof of security of our ABS scheme. Our forking lemma analyzes the output behavior of an algorithm $\mathcal {A}$ when run multiple times on related inputs, instead of when only run twice, while also providing it with oracle access to a deterministic algorithm $\mathcal O$.

Lemma 1

(General Multi-forking Lemma with Oracle Access). Fix an integer $q \ge 1$ and a set $\mathcal H$ of size $h \ge 2$. Let $\mathcal {A}$ be a randomized algorithm that has oracle access to some deterministic algorithm $\mathcal O$, where on input $\mathsf {par}, h_1, \cdots , h_q$, algorithm $\mathcal {A}$ returns a pair; the first element is an integer in the range $0, \cdots , q$ and the second element is what we refer to as a side output. Let $\mathsf {IG}$ be a randomized algorithm called the input generator. The accepting probability of $\mathcal {A}$, denoted $\mathsf {acc}$, is defined as the probability that $J \ge 1$ in the experiment below:

$$\begin{aligned} (\mathsf {par}, \overline{\mathsf {par}}) \leftarrow \mathsf {IG}; ~h_1, \cdots , h_q \leftarrow \mathcal H; ~(J, \sigma ) \leftarrow \mathcal A^{\mathcal O(\overline{\mathsf {par}}, \cdot )}(\mathsf {par}, h_1, \cdots , h_q). \end{aligned}$$

For a positive integer $\ell \ge 2$, the forking algorithm $\mathsf {F}_{\mathcal A, \ell }^{\mathcal O(\overline{\mathsf {par}}, \cdot )}$ associated to $\mathcal A^{\mathcal O(\overline{\mathsf {par}}, \cdot )}$ is a randomized oracle algorithm that takes input $\mathsf {par}$ and proceeds as in Fig. 1, where $\{ \epsilon _k \}_{k \in [\ell ]}$ denotes an arbitrary set of strings. Let

$$\begin{aligned} \mathsf {frk}= \Pr [(\mathsf {par}, \overline{\mathsf {par}}) \leftarrow \mathsf {IG};~ (b, \{ \sigma _k \}_{k \in [\ell ]} ) \leftarrow \mathsf {F}_{\mathcal A, \ell }^{\mathcal O(\overline{\mathsf {par}}, \cdot )}(\mathsf {par}) ~:~ b = 1]. \end{aligned}$$

Then,

$$\begin{aligned} \mathsf {frk}\ge \mathsf {acc}\cdot \left( \left( \frac{\mathsf {acc}}{q}\right) ^{\ell - 1} - \frac{f(\ell )}{h} \right) , \end{aligned}$$

(1)

where $f(\ell )$ is some universal positive valued function that only depends on the value $\ell$.

Fig. 1.

Description of the forking algorithm $\mathsf {F}^{\mathcal O(\overline{\mathsf {par}}, \cdot )}_{\mathcal A, \ell }$.

Proof

For any input $x = (\mathsf {par}, \overline{\mathsf {par}})$, denote $\mathsf {acc}(x)$ as the probability that $J \ge 1$ in the following experiment:

$$\begin{aligned} h_1, \cdots , h_q \leftarrow H; ~(J, \sigma ) \leftarrow \mathcal A^{\mathcal O(\overline{\mathsf {par}}, \cdot )}(\mathsf {par}, h_1, \cdots , h_q). \end{aligned}$$

Also, let $\mathsf {frk}(x) = \Pr [ (b, \{ \sigma _k \}_{k \in [\ell ]}) \leftarrow \mathsf {F}^{\mathcal O(\overline{\mathsf {par}}, \cdot )}_{\mathcal A, \ell }(\mathsf {par}) ~:~ b = 1]$. We claim that there exists some universal positive valued function $f(\ell )$ such that for all x,

$$\begin{aligned} \mathsf {frk}(x) \ge \mathsf {acc}(x) \cdot \left( \left( \frac{\mathsf {acc}(x)}{q}\right) ^{\ell - 1} - \frac{f(\ell )}{h} \right) . \end{aligned}$$

(2)

By taking the expectation of $\mathsf {frk}(x)$ over $x = (\mathsf {par}, \overline{\mathsf {par}}) \leftarrow \mathsf {IG}$ and using the fact $\mathbb {E}[\mathsf {acc}(x)^\ell ] \ge \mathbb {E}[\mathsf {acc}(x)]^\ell$ (which follows from Jensen’s inequality), we obtain Eq. (1). Therefore, to prove the claim, we must prove Eq. (2). Now, for any input x, with the probabilities taken over the coin tosses of $\mathsf {F}^{\mathcal O(\overline{\mathsf {par}}, \cdot )}_{\mathcal A, \ell }(\mathsf {par})$, $\mathsf {frk}(x)$ is equivalent to the following.

$$\begin{aligned}&\Pr \big [ ( I^{(1)} = I^{(k)}\,\,\text {for all}\,\, k \in [\ell ] ) \wedge ( I^{(1)} \ge 1 ) \wedge ( h^{(k)}_{I^{(1)}} \ne h^{(k')}_{I^{(1)}}\,\,\text {for all}\,\, k, k' \in [\ell ] )\big ] \\ \ge&\Pr \big [ ( I^{(1)} = I^{(k)} ~\text {for all}~ k \in [\ell ] ) \wedge ( I^{(1)} \ge 1 )\big ] \\&\quad \quad \quad \quad \quad \quad - \Pr \big [ ( I^{(1)} \ge 1 ) \wedge ( h^{(k)}_{I^{(1)}} = h^{(k')}_{I^{(1)}} ~\text {for some}~ k, k' \in [\ell ] ) \big ] \\ =&\Pr \big [ ( I^{(1)} = I^{(k)}\,\,\text {for all}\,\, k \in [\ell ] ) \wedge ( I^{(1)} \ge 1 ) \big ] - \Pr \big [ ( I^{(1)} \ge 1 ) \big ] \cdot ( 1 - \prod ^{\ell - 1}_{k = 1} \frac{h- k}{h} ) \end{aligned}$$

Here, we can rewrite $1 - \prod _{k = 1}^{\ell - 1} \frac{h - k}{h} = \frac{1}{h} \cdot \Big ( \sum _{k = 0}^{\ell - 2} \alpha _k(\ell ) \cdot \frac{1}{h^k} \Big ),$ where $( \alpha _k(\ell ) )_{k = 0}^{\ell - 2}$ are functions that only depend on $\ell$. Since $h \ge 1$, we can always upper bound the right hand side by $f(\ell ) / h$ using some positive valued function $f(\ell )$ that only depends on $\ell$, where for example, we can use $f(\ell ) = (\ell - 1) \cdot \max \{ \left| \alpha _k(\ell ) \right| \}_{k = 0}^{\ell - 2}$. Here, note that $f(\ell )$ is some universal function that depends neither on $\mathcal {A}$ nor $\mathcal O$. Therefore, we can further rewrite the inequality as follows:

$$\begin{aligned} \mathsf {frk}(x) \ge \Pr \big [ ( I^{(1)} = I^{(k)} \,\,\text {for all}\,\, k \in [\ell ] ) ~\wedge ~ ( I^{(1)} \ge 1 ) \big ] - \frac{\mathsf {acc}(x)\cdot f(\ell )}{h}. \end{aligned}$$

Hence, it remains to show that $\Pr \left[ \left( I^{(1)} = I^{(k)} \,\,\text {for all}\,\, k \in [\ell ]\right) ~\wedge ~ \left( I^{(1)} \ge 1\right) \right] \ge \mathsf {acc}(x)^\ell / q^{\ell - 1}$. Let $\mathcal R$ denote the set from which $\mathcal {A}$ draws its random coins. For each $i \in [q]$, let $X_i : \mathcal R \times \mathcal H^{i - 1} \rightarrow [0, 1]$ be defined by setting $X_i(\rho , h_1, \cdots , h_{i - 1})$ to

$$\begin{aligned} \Pr [h_i , \cdots , h_q \leftarrow \mathcal H ~;~ (J, \sigma ) \leftarrow \mathcal A^{\mathcal O(\overline{\mathsf {par}}, \cdot )}(\mathsf {par}, h_1, \cdots , h_q; \rho ) ~:~ J = i] \end{aligned}$$

for all $\rho \in \mathcal R$ and $h_1, \cdots , h_{i -1} \in \mathcal H$. Here, regard $X_i$ as a random variable over the uniform distribution on its domain. Then,

$$\begin{aligned} \Pr&\big [ ( I^{(1)} = I^{(k)} \,\,\text {for all}\,\, k \in [\ell ] ) ~\wedge ~ ( I^{(1)} \ge 1 ) \big ] = \sum _{i = 1}^{q} \Pr \big [ I^{(k)} = i \,\,\text {for all}\,\, k \in [\ell ] \big ] \nonumber \\&= \sum _{i = 1}^{q} \Big ( \Pr [ I^{(1)} = i] \cdot \prod _{ k = 2 }^{\ell }\Pr [I^{(k)} = i \mid I^{(1)} = i ] \Big ) \end{aligned}$$

(3)

$$\begin{aligned}&= \sum _{i = 1}^{q} \sum _{\rho , h_1, \cdots , h_{i - 1}} X_i(\rho , h_1, \cdots , h_{i - 1})^{\ell } \cdot \frac{1}{\left| \mathcal R \right| \cdot \left| \mathcal {H} \right| ^{i - 1}} \nonumber \\&= \sum _{i = 1}^{q} \mathbb {E}[X_i^\ell ] \quad \ge \quad \sum _{i = 1}^{q} \mathbb {E}[X_i]^\ell . \end{aligned}$$

(4)

Here Eq. (3) follows from independence of $I^{(k)}$ and $I^{(k')}$ for $k, k' \in [2, \ell ]$, and Eq. (4) follows from Jensen’s inequality where we use the fact that $f(x) = x^\ell$ is a convex function. Finally, using Holder’s inequality, we obtain

$$\begin{aligned} \sum _{i = 1}^{q} \mathbb {E}[X_i]^\ell \ge \frac{1}{q^{\ell - 1}}\cdot \left( \sum _{i = 1}^{q} \mathbb {E}[X_i] \right) ^\ell = \frac{1}{q^{\ell - 1}} \cdot \mathsf {acc}(x)^\ell . \end{aligned}$$

This completes the proof of Eq. (1), hence concluding our claim.

Remark

As can be checked from the proof, we can set the function $f(\ell )$ so that in case $\ell = 2$, we have $f(2) = 1$. Therefore, by setting the deterministic oracle $\mathcal O$ to be an oracle that outputs nothing, the above lemma implies the general forking lemma of [BN06].

3 Gap-$\varSigma$-Protocols and Non-interactive Zero-Knowledge Proofs

Before presenting the main tools we use in this paper, we first recall the definition of languages and relations. A language $\mathcal {L}\subseteq \{ 0, 1 \}^*$ is said to have polynomial time recognizable relation $\mathcal {R}\subseteq \{ 0, 1 \}^* \times \{ 0, 1 \}^*$ if $\mathcal {L}= \{ x ~|~ \exists w \text {s.t.} (x, w) \in \mathcal {R} \}$ where $\left| w \right| \le \mathsf {poly}(\left| x \right| )$. We call the string w a witness to the statement $x \in \mathcal {L}$.

3.1 Gap-$\varSigma$-Protocols

$\varSigma$-protocols are a special type of 3-round interactive proof systems that is also a proof of knowledge. Below, we define (a special type of) the gap-$\varSigma$-protocol, which is a generalization of the standard $\varSigma$-protocol where we allow the extracted witness to lie in a slightly larger space than the actual witness being proven during the protocol. Furthermore, the special soundness is defined for cases where more than 2 valid transcripts are required to extract a witness. These non-standard formalizations are required, since most of the lattice-based $\varSigma$-protocols are not captured by the standard formalizations.

Definition 4

(Gap- $\varSigma$ -protocols). Let m be an integer constant and t an integer-valued function of the security parameter. Let $(\mathcal {P}, \mathcal {V})$ be a two-party protocol, where $\mathcal {V}$ is PPT, and let $\mathcal {L}, \mathcal {L}' \subseteq \{ 0, 1 \}^*$ be languages with witness relations $\mathcal {R}, \mathcal {R}'$ such that $\mathcal {R}\subseteq \mathcal {R}'$. Then $(\mathcal {P}, \mathcal {V})$ is called a gap-$\varSigma _{m, t}$-protocol for relations $(\mathcal {R}, \mathcal {R}')$ with challenge space $\mathcal C = \{ 0, 1, \cdots , m-1 \}^t$, if it satisfies the following conditions:

• 3-move form: The protocol is of the following form:

• The prover $\mathcal {P}$, on input $(x, w) \in \mathcal {R}$, sends a commitment $\alpha$ to $\mathcal {V}$.

• The verifier $\mathcal {V}$ samples a challenge $\beta \leftarrow \mathcal C$ and sends it to $\mathcal {P}$.

• The prover $\mathcal {P}$ sends a response $\gamma$ to $\mathcal {V}$, and $\mathcal {V}$ decides to accept of reject based on the protocol transcript $(\alpha , \beta , \gamma )$.

The protocol transcript $(\alpha , \beta , \gamma )$ is called a valid transcript if the verifier $\mathcal {V}$ accepts the protocol run.

• Completeness: Whenever $(x, w) \in \mathcal {R}$, $\mathcal {V}$ accepts with probability 1.

• Soundness: If $(x, w) \not \in \mathcal {R}$, then any cheating (possibly inefficient) prover $\mathcal {P}^*$ succeeds with probability at most $(\frac{m - 1}{m})^{t}$. We call this value the soundness error.

• Special gap-soundness: There exists a PPT algorithm $\mathcal {E}$ (the knowledge extractor) which takes m valid transcripts $\{ (\alpha , \beta _i, \gamma _i) \}_{i \in [m]}$ for some statement $x \in \mathcal {L}$, where there exists at least one index $j \in [t]$ such that $\{ \beta _{i, j} \}_{i \in [m]} = \{ 0, 1, \cdots , m-1 \}$ as inputs, and outputs w such that $(x, w) \in \mathcal {R}'$. Here $\beta _{i, j}$ denotes the j-th value of the string $\beta _{i}$. Note that the knowledge extractor outputs a witness in the gap relation.

• Special honest-verifier zero-knowledge (HVZK): There exists a PPT algorithm $\mathcal {S}$ (the HVZK simulator) taking $x \in \mathcal {L}$ as input, that outputs $(\alpha , \beta , \gamma )$ whose distribution is indistinguishable from an accepting protocol transcript generated by a real protocol run. Although no guarantees on the outputs are made, the simulator $\mathcal {S}$ is also defined over the inputs $x \not \in \mathcal {L}$.

We call the gap-$\varSigma _{m, t}$-protocol computationally (resp. statistically) special HVZK if the simulated transcript is computationally (resp. statistically) indistinguishable from a real transcript.

Lastly, we say the gap-$\varSigma$-protocol has high-commitment entropy if for all $(x, w)\in \mathcal {R}$ and $\alpha$, the probability that an honestly generated commitment by $\mathcal {P}$ takes on the value $\alpha$ is negligible.

We omit the subscript (m, t) of the gap-$\varSigma _{m, t}$-protocol whenever it is irrelevant to the context. Occasionally, we omit t and simply write gap-$\varSigma _m$-protocol to emphasize that the soundness error is negligible in the security parameter. We note that the standard $\varSigma$-protocol is a special case of the gap-$\varSigma$-protocol where $m = 2, \mathcal {R}= \mathcal {R}'$. In this case the soundness error will simply be $2^{- t}$ and special gap-soundness implies special soundness, since if there exists an index $j \in [t]$ for which the binary strings (i.e., the challenges) differ, then it implies that the two challenges are different. Finally, we assume without loss of generality that all of the gap-$\varSigma$-protocols we consider in this paper have high-commitment entropy, since the condition can be easily met by appending a super-logarithmic number of public random bits to the commitments.

Often times, the gap in the relations allows for much more efficient schemes, and do not affect their usefulness in practice as long as $\mathcal {R}'$ is still a sufficiently hard relation, e.g., [FO97, DF02, AJLA+12, BCK+14]. We note that for simplicity, in this paper we only consider gap-$\varSigma$-protocols that are complete with probability 1. Namely, our formalization does not capture those gap-$\varSigma$-protocols that are based on the rejection sampling technique such as [Lyu09, Lyu12, BCK+14].⁵

Finally, we formally describe the Fiat-Shamir transformation [FS86] which is a technique to make any (gap-)$\varSigma$-protocol into a non-interactive proof system by using a cryptographic hash function.

Definition 5

Let $(\mathcal {P}, \mathcal {V})$ be a gap-$\varSigma$-protocol with relation $(\mathcal {R}, \mathcal {R}')$, and $H(\cdot )$ a hash function with range equal to the verifier’s challenge space $\mathcal C$. The Fiat-Shamir transformation of gap-$\varSigma$ is the non-interactive proof system $(\mathcal {P}^{H}, \mathcal {V}^H)$ defined as follows:

• $\mathcal {P}^H(x, w)$: Run $\mathcal {P}(x, w)$ to obtain a commitment $\alpha$, and compute $\beta \leftarrow H(x, \alpha )$. Then complete the run of $\mathcal {P}$ with $\beta$ as the challenge to get the response $\gamma$. Finally output the pair $(\alpha , \gamma )$

• $\mathcal {V}^H(x, \alpha , \gamma )$: Compute $\beta = H(x, \alpha )$ and return the output of $\mathcal {V}(\alpha , \beta , \gamma )$.

3.2 Non-interactive Zero-Knowledge Proof Systems

We formalize the notion of non-interactive zero-knowledge (NIZK) proof systems in the explicitly programmable random oracle model [Wee09], where the zero-knowledge (ZK) simulator is allowed to explicitly program the random oracle. We follow the notations provided in [FKMV12] for presentation. Namely, we model the ZK simulator of a NIZK proof system as a stateful PPT algorithm $\mathcal {S}$ that can operate in two modes: $(h, \mathsf {st}) \leftarrow \mathcal {S}(1, \mathsf {st}, q)$ takes care of answering random oracle queries, and $(\pi , \mathsf {st}) \leftarrow \mathcal {S}(2, \mathsf {st}, x)$ simulates the proof. Here, the calls to $\mathcal {S}(1, \cdots )$ and $\mathcal {S}(2, \cdots )$ share the common state $\mathsf {st}$ that is updated after each invocation of the simulator. Furthermore, we define three algorithms $\mathcal {S}_1, \mathcal {S}_2, \hat{\mathcal {S}}_2$ that run simulator $\mathcal {S}$ internally: $\mathcal {S}_1(q)$ returns the first output of $(h, \mathsf {st}) \leftarrow \mathcal {S}(1, \mathsf {st}, q)$, $\mathcal {S}_2(x, w)$ ignores the second input w and returns the first output of $(\pi , \mathsf {st}) \leftarrow \mathcal {S}(2, \mathsf {st}, x)$ if and only if $(x, w) \in \mathcal {R}$ (or equivalently $x \in \mathcal {L}$), and $\hat{\mathcal {S}}_2(x)$ is essentially the same as $\mathcal {S}_2(x, w)$ except that it does not take a second input w and is also defined for inputs such that $x \not \in \mathcal {L}$. Observe that $\mathcal {S}_2$ and $\hat{\mathcal {S}}_2$ are identical for inputs $x \in \mathcal {L}$, and unlike $\mathcal {S}_2$, $\hat{\mathcal {S}}_2$ may be invoked to simulate proofs for invalid statements.

Definition 6

(Non-interactive Zero-Knowledge Proof System). Let $\mathcal {R}$ be a relation with an associated language $\mathcal {L}_\mathcal {R}$. We say a non-interactive proof system $(\mathcal {P}, \mathcal {V})$ is a statistical NIZK proof system for language $\mathcal {L}_\mathcal {R}$ with a (PPT) ZK simulator $\mathcal {S}$ in the random oracle model, if for any algorithm $\mathcal D$ we have

$$\begin{aligned} \left| \Pr [\mathcal D^{H(\cdot ), \mathcal {P}^{H}(\cdot , \cdot )}(1^\lambda ) = 1] - \Pr [\mathcal D^{\mathcal {S}_1(\cdot ), \mathcal {S}_2(\cdot , \cdot )}(1^\lambda ) = 1] \right| = \mathsf {negl}(\lambda ), \end{aligned}$$

where $H(\cdot )$ is modeled as a random oracle, and both $\mathcal {P}$ and $\mathcal {S}_2$ output $\bot$ if $(x, w) \not \in \mathcal {R}$. It is called a computational NIZK proof system in case the above holds only for all PPT algorithms $\mathcal D$.

It is a well known fact that in the random oracle model, the Fiat-Shamir transformation of any $\varSigma$-protocol is a NIZK proof system. It is straightforward to prove that it is also the case for gap-$\varSigma$-protocols, as we state in the following lemma.

Lemma 2

(Fiat-Shamir NIZK Proof Systems). Let $(\mathcal {P}, \mathcal {V})$ be a gap-$\varSigma$-protocol with relation $(\mathcal {R}, \mathcal {R}')$ that is computationally (resp. statistically) special HVZK, and $H(\cdot )$ a hash function with range equal to the verifier’s challenge space $\mathcal C$. Then, in the random oracle model, the non-interactive proof system $(\mathcal {P}^H, \mathcal {V}^H)$ obtained by the Fiat-Shamir transformation of gap-$\varSigma$ is a computational (resp. statistical) non-interactive zero-knowledge proof system for the language $\mathcal {L}_\mathcal {R}$.

Proof

(Proof sketch.). To prove that the proof system $(\mathcal {P}^H, \mathcal {V}^H)$ is a NIZK proof system for the language $\mathcal {L}_\mathcal {R}$, it suffices to show that there exists a ZK simulator $\mathcal {S}$ as in the above Definition 6. Below, we construct $\mathcal {S}$ by invoking the HVZK simulator $\mathcal {S}_\varSigma$ of the underlying gap-$\varSigma$-protocol $(\mathcal {P}, \mathcal {V})$:

• $\mathcal {S}(1, \mathsf {st}, q = (x, \alpha )) \rightarrow (h = \beta , \mathsf {st})$: To answer random oracle queries, it searches the table $\mathcal {T}_{H}$ kept in the state $\mathsf {st}$ whether an output for $q = (x, \alpha )$ is already defined. If so it returns the previously defined assigned value. If not, it samples a uniformly random value $\beta \leftarrow \mathcal C$ and stores $(q = (x, \alpha ), h = \beta )$ in the table. Note that this corresponds to algorithm $\mathcal {S}_1$.

• $\mathcal {S}(2, \mathsf {st}, x) \rightarrow (\pi = (\alpha , \beta , \gamma ), \mathsf {st})$: To simulate a proof for the statement $x \in \mathcal {L}_\mathcal {R}$, it runs the HVZK simulator $\mathcal {S}_{\varSigma }$ on input x to obtain a proof $(\alpha , \beta , \gamma )$. Then, it updates the table $\mathcal T_{H}$ by adding $(q = (x, \alpha ), h = \beta )$. If $\mathcal T_{H}$ happens to be already defined on input $q = (x, \alpha )$, $\mathcal {S}$ aborts. This completely specifies algorithm $\mathcal {S}_2$ as required. Observe that the simulator $\mathcal {S}$ can also be run on statements $x \not \in \mathcal {L}_\mathcal {R}$ using the above method, since $\mathcal {S}_\varSigma$ is well-defined for $x \in \mathcal {L}$ as well. In particular, the above description for $\mathcal {S}$ also specifies algorithm $\hat{\mathcal {S}}_2$ as well.

Since, we only consider gap-$\varSigma$-protocols with high-commitment entropy, the probability of simulator $\mathcal {S}$ aborting is negligible, which ends the proof sketch.

In the following, we use the above algorithm $\mathcal {S}$ as the ZK simulator for a NIZK proof system $(\mathcal {P}^H, \mathcal {V}^H)$ based on the Fiat-Shamir transformation of a gap-$\varSigma$-protocol $(\mathcal {P}, \mathcal {V})$. Note that we do not explicitly define the soundness property of the NIZK proof system, since this property will be implicitly implied when we construct a knowledge extractor during the security proof.

4 Generic Construction of Attribute-Based Signatures

Preparation. Before presenting our construction, we describe the relations and languages we require for our NIZK proof system. Our construction relies on a gap-$\varSigma$-protocol for the relations $(\mathcal {R}_\mathsf{ABS}, \mathcal {R}'_\mathsf{ABS})$ defined below and employs the Fiat-Shamir transformation provided in Definition 5 to turn it in into a NIZK proof system. In the following, $x_i$ for $i \in [\ell + 1,\ell + N - 1]$ denotes the values assigned to the i-th (internal) wire of C on input $\mathbf {x}= (x_1, \cdots , x_\ell )$ and $\mathsf {vk}_{\mathsf {Sign}}$, $\mathsf {pk}_{\mathsf {Com}}$ denotes the verification key and public commitment key of the underlying digital signature scheme and commitment scheme, respectively. Then the relation $\mathcal {R}_\mathsf{ABS}$ is defined as follows:

$$\begin{aligned} \mathcal {R}_\mathsf{ABS}&= \Big \{ \Big ( \mathsf {statement} = \big ( \mathsf {vk}_\mathsf {Sign}, \mathsf {pk}_\mathsf {Com}, C\in \mathcal C_\ell , c_\sigma , ( c_i )_{i = 1}^{\ell + \left| C \right| - 1} \big ), \\&\quad \quad \quad \quad \mathsf {witness} = \big ( \mathbf {x}= (x_1, \cdots , x_\ell ), \sigma , d_\sigma , ( d_i )_{i = 1}^{\ell + \left| C \right| -1} \big ) \Big ) \Big |\end{aligned}$$

the committed values in   $c_\sigma , ( c_i )_{i = 1}^{\ell + \left| C \right| - 1}$   satisfy the following conditions:

• $\mathsf {S}.\mathsf {Verify}(\mathsf {vk}_{\mathsf {Sign}}, \mathbf {x}, \sigma ) = 1$

• $x_i = x_{i_1} \star _i x_{i_2} \,\,\text {for}\,\, i \in [\ell + 1, \ell + \left| C \right| -1]\,\,\text {for}\,\,(\star _i, i_{1}, i_2) \leftarrow \mathsf {topo}_C(i)$

• $1 = x_{(\ell + \left| C \right| )_1} \star _{\ell + \left| C \right| } x_{(\ell + \left| C \right| )_2}\,\,\text {for}\,\,(\star _{\ell + \left| C \right| }, i_{(\ell + \left| C \right| )_1}, i_{(\ell + \left| C \right| )_2}) \leftarrow \mathsf {topo}_C(\ell + \left| C \right| )$

• $(c_\sigma , d_\sigma ) \in \mathcal {D}_{\mathsf {Com}}(\mathsf {pk}_\mathsf {Com}, \sigma )\,\,\text {and}\,\, (c_i, d_i) \in \mathcal {D}_{\mathsf {Com}}(\mathsf {pk}_\mathsf {Com}, x_i)\,\,\text {for}\,\, \left. i \in [\ell + \left| C \right| - 1] \right\}$

Here, recall that $\mathcal {D}_{\mathsf {Com}}(\mathsf {pk}_\mathsf {Com}, \mathsf {M})$ is the set of all possible outputs of the commitment algorithm $\mathsf {C}.\mathsf {Com}(\mathsf {pk}_{\mathsf {Com}}, \mathsf {M})$ . We simply define the corresponding language $\mathcal {L}_\mathsf{ABS}$ as the language induced by the relation $\mathcal {R}_\mathsf{ABS}$. Furthermore, the gap-relation $\mathcal {R}'_\mathsf{ABS}$ is defined analogously to $\mathcal {R}_\mathsf{ABS}$ except that we replace the last condition as follows:

• $(c_\sigma , d_\sigma ) \in \mathcal {D}_{\mathsf {G\text {-}Com}}(\mathsf {pk}_\mathsf {Com}, \sigma ) \wedge (c_i, d_i) \in \mathcal {D}_{\mathsf {G\text {-}Com}}(\mathsf {pk}_\mathsf {Com}, x_i)$ for $i \in [\ell + \left| C \right| - 1]$

The only difference between the two relations are the condition on the commitment and opening pairs. In the latter, it is only required that the pairs are in the set $\mathcal {D}_{\mathsf {G\text {-}Com}}(\cdot )$ and not in the more restricted set $\mathcal {D}_{\mathsf {Com}}(\cdot )$. Recall that $\mathcal {D}_{\mathsf {G\text {-}Com}}(\mathsf {pk}_\mathsf {Com}, \mathsf {M})$ is the set of all commitment and opening pairs that the opening algorithm outputs 1 on message $\mathsf {M}$. As we noted in Sect. 3.1, we require this gap-relation $\mathcal {R}'_\mathsf{ABS}$ purely for technical reasons, since in many of the lattice-based $\varSigma$-protocols we can only extract witnesses that lie in a slightly larger space than the actual witnesses being proven in the actual protocol. Similarly to above, we define the language $\mathcal {L}'_\mathsf{ABS}$ as the language induced by the relation $\mathcal {R}'_\mathsf{ABS}$.

For simplicity, in the following we omit $\mathsf {vk}_\mathsf {Sign}$ and $\mathsf {pk}_\mathsf {Com}$ from the statement, since they are fixed by the $\mathsf {Setup}$ algorithm and all signers use the same $\mathsf {vk}_\mathsf {Sign}$ and $\mathsf {pk}_\mathsf {Com}$.

Construction. Here, we provide our attribute-based signature scheme for unbounded (arithmetic) circuits. In the following, assume a digital signature scheme $(\mathsf {S}.\mathsf {KeyGen}$, $\mathsf {S}.\mathsf {Sign}$, $\mathsf {S}.\mathsf {Verify})$, a commitment scheme $(\mathsf {C}.\mathsf {Gen}, \mathsf {C}.\mathsf {Com}, \mathsf {C}.\mathsf {Open})$ and a NIZK proof system for the relation $\mathcal {R}_\mathsf{ABS}$.  

$\mathsf {Setup}(1^\lambda , 1^\ell )$::

On input the security parameter $1^\lambda$ and the input length $1^\ell$ for the family of circuits $\mathcal C_\ell$, generate a verification key and a signing key $(\mathsf {vk}_{\mathsf {Sign}}, \mathsf {sk}_{\mathsf {Sign}}) \leftarrow \mathsf {S}.\mathsf {KeyGen}(1^\lambda , 1^{\ell })$ and a public commitment key $\mathsf {pk}_\mathsf {Com}\leftarrow \mathsf {C}.\mathsf {Gen}(1^\lambda )$. Then output

$$\begin{aligned} \mathsf {mpk}= (\mathsf {vk}_{\mathsf {Sign}}, \mathsf {pk}_\mathsf {Com}, H(\cdot ), G(\cdot )) \quad \text {and} \quad \mathsf {msk}= (\mathsf {sk}_{\mathsf {Sign}}). \end{aligned}$$

Here, $H(\cdot )$ and $G(\cdot )$ are hash functions used by the NIZK proof system and by algorithm $\mathsf {Sign}$, respectively, which are programmed as random oracles in the security reduction. Further, we assume the output space of $G(\cdot )$ to be $\{ 0, 1 \}^\ell$.⁶

$\mathsf {KeyGen}(\mathsf {mpk}, \mathsf {msk}, \mathbf {x})$::

On input $\mathbf {x}= (x_1 \cdots , x_\ell ) \in \{ 0, 1 \}^\ell$, create a signature on the attribute $\mathbf {x}\in \{ 0, 1 \}^{\ell }$ by running $\sigma \leftarrow \mathsf {S}.\mathsf {Sign}(\mathsf {sk}_{\mathsf {Sign}}, \mathbf {x})$. Then, output the secret key as $\mathsf {sk}_{\mathbf {x}} = (\mathbf {x}, \sigma )$.

$\mathsf {Sign}(\mathsf {mpk}, \mathsf {sk}_{\mathbf {x}}, C, \mathsf {M})$::

On input message $\mathsf {M}\in \{ 0, 1 \}^{\star }$ and circuit $C\in \mathcal C_\ell$ with an associating topology $\mathsf {topo}_C$ proceed as follows:

 

• 1. Compute $\mathbf {h}= (h_1, \cdots , h_\ell ) \leftarrow G(\mathsf {M}, C)$ ⁷ and create a new circuit $\hat{C} \in \mathcal {C}_\ell$ with two dummy gates connected to each of the input wires of $C$. Namely, to the input wires $i \in [\ell ]$ of $C$, we add a series composition of two addition gates where one gate adds $h_i$ and the other gate adds $-h_i$; on input $x_i$ to the i-th input wire of $\hat{C}$, it first evaluates to $x_i + h_i$ and then evaluates back to $x_i$, on which point it gets fed to the i-th (input) wire of $C$. Here, the value $\mathbf {h}$ is hard-wired into $\hat{C}$, and is considered as one of the internal wires. Further, let N be the number of gates $| \hat{C} |$.

• 2. Compute the assignment to each non-input wires in $\hat{C}(x_1, \cdots , x_\ell )$: for all $i \in [\ell + 1, \ell + (N - 1)]$, compute $(\star _i, i_1, i_2) \leftarrow \mathsf {topo}(i)$ where $\star _i \in \{ +, \times \}$, and denote the newly created values $( x_i )_{i = \ell + 1}^{\ell + N - 1}$ in ascending order as

  $$\begin{aligned} {\left\{ \begin{array}{ll} ~x_{i} = x_{i_1} + x_{i_2} \quad &{}\text {if}\,\,\star _i = +\\ ~x_{i} = x_{i_1} \cdot x_{i_2} \quad &{}\text {if}\,\, \star _i = \times \end{array}\right. }. \end{aligned}$$

• 3. Create a commitment $(c_{\sigma }, d_{\sigma }) \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}_\mathsf {Com}, \sigma )$ of the signature $\sigma$. Furthermore, for all $i \in [\ell + N - 1]$, create a commitment $(c_i, d_i) \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}_\mathsf {Com}, x_i)$ that commits to the value of each wire in $\hat{C}$ (except for the output wire).

• 4. Generate a NIZK proof $\pi$ proving that the committed values satisfy relation $\mathcal {R}_\mathsf{ABS}$. Concretely, it generates a proof for the following conditions.⁸

• The attribute $\mathbf {x}= (x_1, \cdots , x_\ell )$ committed to $( c_i )_{i = 1}^{\ell }$ and the signature $\sigma$ committed to $c_{\sigma }$ satisfy the following verification equation:

  $$\begin{aligned} \mathsf {S}.\mathsf {Verify}(\mathsf {vk}_\mathsf {Sign}, \mathbf {x}, \sigma ) = 1. \end{aligned}$$

  (5)

• For all $i \in [\ell + 1, \ell + N - 1]$, the value $x_i$ committed to $c_i$ satisfy the following equation:

  $$\begin{aligned} {\left\{ \begin{array}{ll} ~x_{i} = x_{i_1} + x_{i_2} \quad &{}\text {if}\,\, \star _i = +\\ ~x_{i} = x_{i_1} \cdot x_{i_2} \quad &{}\text {if}\,\,\star _i = \times \end{array}\right. }. \end{aligned}$$

  (6)

• The values $x_{(\ell + N)_1}$ and $x_{(\ell + N)_2}$ committed to $c_{(\ell + N)_1}$ and $c_{(\ell + N)_2}$, respectively, satisfy the following equation:

  $$\begin{aligned} {\left\{ \begin{array}{ll} ~1 = x_{(\ell + N)_1} + x_{(\ell + N)_2} \quad &{}\text {if}\,\, \star _{\ell + N} = +\\ ~1 = x_{(\ell + N)_1} \cdot x_{(\ell + N)_2} \quad &{}\text {if}\,\, \star _{\ell + N} = \times \end{array}\right. }. \end{aligned}$$

  (7)

• 5. Finally, output $\varSigma = \big ( c_\sigma , ( c_i )_{i = 1}^{\ell + N - 1}, \pi \big )$.

 

$\mathsf {Verify}(\mathsf {mpk}, \mathsf {M}, C, \varSigma )$::

Compute $\mathbf {h}\leftarrow G(\mathsf {M}, C)$ and construct the circuit $\hat{C}$ as in Step 1 of the $\mathsf {Sign}$ algorithm. Then, verify the proof with respect to the circuit $\hat{C}$. Output $\mathsf {Valid}$ if the proof is verified valid, and output $\mathsf {Invalid}$ otherwise.

 

Correctness. Observe that $\hat{C} (\mathbf {x}) = C(\mathbf {x})$ for all $\mathsf {M}, \mathbf {x}$. Therefore, the correctness of the scheme follows simply from the correctness of the underlying NIZK proof system. In particular, a signer that has a certified attribute $\mathbf {x}$ such that $C(\mathbf {x}) = 1$ can properly generate a proof proving Eqs. (5–7).

4.1 Security Analysis

Theorem 1

(Privacy). Assume a statistically hiding commitment scheme with gap-openings and a statistically special HVZK gap-$\varSigma$-protocol for relations $(\mathcal {R}_\mathsf{ABS},$ $\mathcal {R}'_\mathsf{ABS})$. Then, converting the gap-$\varSigma$-protocol into a Fiat-Shamir NIZK proof system, the above attribute-based signature scheme is statistically private in the random oracle model. In case either the hiding property or the special HVZK property only holds computationally, then we obtain computational privacy.

The proof follows naturally from the zero-knowledge property of the NIZK proof system, and is deferred the full version.

Theorem 2

(Adaptive Unforgeability). Assume a computationally hiding and a statistically binding commitment scheme with gap openings, a computationally special HVZK gap-$\varSigma _m$-protocol⁹ for relations $(\mathcal {R}_\mathsf{ABS}, \mathcal {R}'_\mathsf{ABS})$ and an $\mathsf {eu\text {-}cma}$ secure (deterministic) digital signature scheme. Then, by converting the gap-$\varSigma _m$-protocol into a Fiat-Shamir NIZK proof system, the above attribute-based signature scheme is adaptively unforgeable in the random oracle model.

Proof

Assume there exists a PPT adversary $\mathcal {B}_\mathsf{ABS}$ that wins the adaptive unforgeability game with advantage $\epsilon = \epsilon (\lambda )$. Furthermore, let $Q_H = Q_H(\lambda )$ be the number of unique random oracle queries $\mathcal {B}_\mathsf{ABS}$ makes to $H(\cdot )$ that is bounded by some polynomial in the security parameter $\lambda$. Our proof proceeds in a sequence of games, where $X_i$ denotes the event the adversary wins in $\mathsf {Game}_i$. Our final goal is to construct an adversary $\mathcal {B}_{\mathsf {Sign}}$ that breaks the $\mathsf {eu\text {-}cma}$ security of the underlying digital signature scheme by using $\mathcal {B}_\mathsf{ABS}$. For our Fiat-Shamir NIZK proof system, we use the ZK simulator $\mathcal S$ that we have defined in Lemma 2.

 

$\mathsf {Game}_\mathsf{real}{:}$ :

This game is identical to the real adaptive unforgeability game where all the random oracle queries to $H(\cdot )$ and $G(\cdot )$ are answered randomly by the challenger. At the end of the game, $\mathcal {B}_\mathsf{ABS}$ outputs a valid forged signature $(\mathsf {M}^*, C^*, \varSigma ^*)$ with probability $\Pr [X_\mathsf{real}] = \epsilon$.

$\mathsf {Game}_1{:}$ :

In this game, we change the way the challenger answers the random oracle queries to $H(\cdot )$ and the signing queries. Namely, we use the ZK simulator $\mathcal {S}$ associated to the NIZK proof system to answer these. Recall that simulator $\mathcal {S}$ has two modes for running the two oracles $\mathcal {S}_1$ and $\hat{\mathcal {S}}_2$. When $\mathcal {B}_\mathsf{ABS}$ submits a random oracle query to $H(\cdot )$, the challenger relays this to oracle $\mathcal {S}_1$ and returns the value outputted by $\mathcal {S}_1$ to $\mathcal {B}_\mathsf{ABS}$. Here, the random oracle queries to $G(\cdot )$ are answered by the $\mathsf {Game}_1$ challenger as in the previous game. Furthermore, when $\mathcal {B}_\mathsf{ABS}$ submits a signing query on an attribute, message and circuit tuple $(\mathbf {x}, \mathsf {M}, C)$ such that $C(\mathbf {x}) = 1$, it first runs $\mathsf {sk}_\mathbf {x}= (\mathbf {x}, \sigma ) \leftarrow \mathsf {KeyGen}(\mathsf {mpk}, \mathsf {msk}, \mathbf {x})$ and constructs the circuit $\hat{C}$ with N gates using $\mathbf {h}\leftarrow G(\mathsf {M}, C)$ as in Step 1 of the $\mathsf {Sign}$ algorithm. Then it proceeds with Step 2 and 3 to create commitments $\big ( c_\sigma , ( c_i )_{i = 1}^{\ell + N -1} \big )$ along with valid openings $\big ( d_\sigma , ( d_i )_{i = 1}^{\ell + N -1} \big )$. Finally, it invokes $\hat{\mathcal {S}}_2$ on input the statement $\big ( \hat{C}, c_\sigma , ( c_i )_{i = 1}^{\ell + N -1} \big ) \in \mathcal {L}_\mathsf{ABS}$ ¹⁰ and obtains a proof $\pi$, and returns the signature $\varSigma = \big ( c_\sigma , ( c_i )_{i = 1}^{\ell + N -1}, \pi \big )$ to $\mathcal {B}_\mathsf{ABS}$. Here, the simulated proofs of $\hat{\mathcal {S}}_2$ are distributed negligibly close to the actual proofs in $\mathsf {Game}_\mathsf{real}$ by the definition of the NIZK proof system (See Definition 6), and the fact that the oracles $\mathcal {S}_2$ and $\hat{\mathcal {S}}_2$ are equivalent in case the statement to be proven is in the language. Hence, $\left| \Pr [X_\mathsf{real}] - \Pr [X_1] \right| = \mathsf {negl}(\lambda ).$

$\mathsf {Game}_2{:}$ :

In this game, we change the way the challenger creates the commitment for the signature $\sigma$ produced during the signing query. In the previous game, when $\mathcal {B}_\mathsf{ABS}$ submitted a signing query on an attribute, message and circuit tuple $(\mathbf {x}, \mathsf {M}, C)$ such that $C(\mathbf {x}) = 1$, the challenger created a proper commitment $c_\sigma$ for the signature $\sigma$ following Step 3 of the $\mathsf {Sign}$ algorithm, i.e., $(c_\sigma , d_\sigma ) \leftarrow \mathsf {Com}(\mathsf {pk}_{\mathsf {Com}}, \sigma )$. In this game, however, the $\mathsf {Game}_2$ challenger will instead sample a random value c in the commitment space $\mathcal C_{\mathsf {Com}}$ and sets $c_\sigma = c$. Then, as in $\mathsf {Game}_2$, it invokes $\hat{\mathcal {S}}_2$ on input $\big ( \hat{C}, c_\sigma , ( c_i )_{i = 1}^{\ell + N -1} \big )$ and obtains a proof $\pi$, and returns the signature $\varSigma = \big ( c_\sigma , ( c_i )_{i = 1}^{\ell + N -1}, \pi \big )$ to $\mathcal {B}_\mathsf{ABS}$. Here, recall that oracle $\hat{\mathcal {S}}_2$ is defined to simulate proofs for false statements that are not in the language $\mathcal {L}_\mathsf{ABS}$ as well. Then, the differences in the view of the adversary in $\mathsf {Game}_1$ and $\mathsf {Game}_2$ are computationally indistinguishable due to the computationally hiding property of the commitment scheme.¹¹ In other words, we have $\left| \Pr [X_1] - \Pr [X_2] \right| = \mathsf {negl}(\lambda ).$

$\mathsf {Game}_3{:}$ :

In this game, we add an additional winning condition for adversary $\mathcal {B}_\mathsf{ABS}$ to satisfy. Namely, when $\mathcal {B}_\mathsf{ABS}$ outputs a forgery $(\mathsf {M}^*, C^*, \varSigma ^*)$, the $\mathsf {Game}_3$ challenger checks if the random oracle $G(\cdot )$ was ever queried on a message-circuit pair $(\mathsf {M}, C) \ne (\mathsf {M}^*, C^*)$ such that $\hat{C} = \hat{C}^*$. Note that this implies $G(\mathsf {M}, C) = G(\mathsf {M}^*, C^*)$. Hereafter, we say $\mathcal {B}_\mathsf{ABS}$ wins if and only if in addition to the winning condition of the previous game, there are no such message-circuit pairs. Since, the output values of the random oracle $G(\cdot )$ are uniformly random over $\{ 0, 1 \}^\ell$ for $\ell = \mathsf {poly}(n)$, the probability that a collision occurs for different message-circuit pairs is negligible. Hence, $\left| \Pr [X_2] - \Pr [X_3] \right| = \mathsf {negl}(\lambda ).$ Below, we denote $\epsilon _3 = \Pr [X_3]$.

 

In the following, we define the algorithms $\mathcal {A}$ and $\mathcal O$ to be used in the forking algorithm $\mathsf {F}_{\mathcal A, m}^{\mathcal O(\overline{\mathsf {par}}, \cdot )}$ of the generfal multi-forking lemma with oracle access (See Lemma 1). Looking ahead, the forking algorithm will be used by adversary $\mathcal {B}_{\mathsf {Sign}}$ to win the $\mathsf {eu\text {-}cma}$ security of the underlying digital signature scheme.

To provide the full description of algorithms $\mathcal {A}$ and $\mathcal O$, we first define the input generator $\mathsf {IG}$, the set $\mathcal H$ and the integer q, which are required to define the inputs for $\mathcal {A}$ and $\mathcal O$. First, the input generator $\mathsf {IG}$ outputs $(\mathsf {par}, \overline{\mathsf {par}})$ where $\mathsf {par}$ constitutes of the verification key $\mathsf {vk}_{\mathsf {Sign}}$, public commitment key $\mathsf {pk}_{\mathsf {Com}}$ and any extra auxiliary parameters required to specify the ABS scheme (e.g., the family of circuits), and $\overline{\mathsf {par}}$ is simply the signing key $\mathsf {sk}_{\mathsf {Sign}}$. Here, $\mathsf {vk}_{\mathsf {Sign}}, \mathsf {sk}_{\mathsf {Sign}}$ and $\mathsf {pk}_{\mathsf {Com}}$ are generated by running $(\mathsf {vk}_\mathsf {Sign}, \mathsf {sk}_\mathsf {Sign}) \leftarrow \mathsf {S}.\mathsf {KeyGen}(1^\lambda , 1^\ell )$ and $\mathsf {pk}_\mathsf {Com}\leftarrow \mathsf {C}.\mathsf {Gen}(1^\lambda )$. Furthermore, we define the set $\mathcal H$ to be the verifier’s challenge space $\mathcal C_\varSigma$ of the underlying gap-$\varSigma _m$-protocol, and set q as $Q_H$; the number of unique random oracle queries made to $H(\cdot )$ by $\mathcal {B}_\mathsf{ABS}$. To summarize, $\mathcal {A}$ will be given $\mathsf {par}$ and $h_1, \cdots , h_{Q_H} \in \mathcal H$ as input.

We next specify how algorithms $\mathcal {A}$ and $\mathcal O$ run. First, the deterministic algorithm $\mathcal O$ is simply defined as the signing algorithm of the underlying deterministic digital signature scheme; $\mathcal O(\overline{\mathsf {par}}, \cdot ) = \mathsf {S}.\mathsf {Sign}(\mathsf {sk}_{\mathsf {Sign}}, \cdot )$. Here, $\mathcal O$ is deterministic since the signing algorithm is deterministic once fixed a signing key $\mathsf {sk}_{\mathsf {Sign}}$. Next, we define $\mathcal {A}$ as the randomized algorithm that simulates $\mathsf {Game}_3$ and outputs a small modification of the forgery returned by $\mathcal {B}_\mathsf{ABS}$. We first explain how $\mathcal {A}$ simulates $\mathsf {Game}_3$: $\mathcal {A}$ essentially runs the $\mathsf {Game}_3$ challenger, $\mathcal {B}_\mathsf{ABS}$ and the ZK simulator $\mathcal {S}$ internally, with two conceptual changes concerning the $\mathsf {Game}_3$ challenger and the ZK simulator $\mathcal {S}$. In particular the $\mathsf {Game}_3$ challenger is modified to an algorithm which we call the $\mathsf {Game}_3'$ challenger, so that it does not run $(\mathsf {vk}_\mathsf {Sign}, \mathsf {sk}_\mathsf {Sign}) \leftarrow \mathsf {S}.\mathsf {KeyGen}(1^\lambda , 1^\ell )$ anymore. Instead of generating $(\mathsf {vk}_\mathsf {Sign}, \mathsf {sk}_\mathsf {Sign})$ on its own, the $\mathsf {Game}_3'$ challenger is provided with $\mathsf {vk}_\mathsf {Sign}$ by $\mathcal {A}$, and no longer possesses $\mathsf {sk}_\mathsf {Sign}$. Whenever the $\mathsf {Game}_3'$ challenger requires to run the signing algorithm $\mathsf {S}.\mathsf {Sign}(\mathsf {sk}_{\mathsf {Sign}}, \cdot )$, $\mathcal {A}$ simply invokes $\mathcal O(\overline{\mathsf {par}}, \cdot ) = \mathsf {S}.\mathsf {Sign}(\mathsf {sk}_{\mathsf {Sign}}, \cdot )$, which it has oracle access to, and returns whatever output by $\mathcal O$ to the $\mathsf {Game}_3'$ challenger. Furthermore, the ZK simulator $\mathcal {S}$ (See Lemma 2) is modified in a way so that it does not sample a random value $h_i \leftarrow \mathcal C_{\varSigma }$ when invoked on a random oracle query to $H(\cdot )$. Concretely, on the i-th unique random oracle query to $H(\cdot )$, it simply outputs the value $h_i$ provided by $\mathcal {A}$.¹² This is only a conceptual change, since $\mathcal C_{\varSigma } = \mathcal H$ and $h_i$ are sampled uniformly over $\mathcal H$. Therefore, the above changes do not alter the view of $\mathcal {B}_\mathsf{ABS}$. Hence the advantage of $\mathcal {B}_\mathsf{ABS}$ winning the game simulated by $\mathcal {A}$ is exactly the same as of $\mathsf {Game}_3$. Finally, we describe the output of $\mathcal {A}$. In particular, at the end of the simulation of $\mathsf {Game}_3$, $\mathcal {B}_\mathsf{ABS}$ outputs a valid forgery $(\mathsf {M}^*, C^*, \varSigma ^*)$ where $\varSigma ^*= \big ( c^*_\sigma , ( c^*_i )_{i = 1}^{\ell + N - 1}, \pi ^* \big )$ with probability $\epsilon _3$. In the following let $\chi ^*$ denote the statement $( \hat{C}^*, c^*_\sigma , ( c^*_i )_{i = 1}^{\ell + N - 1} )$, where $\hat{C}^*$ is the circuit with N gates constructed from $C^*$ in Step 1 of the $\mathsf {Sign}$ algorithm. Since this is a valid forgery, we must have $\chi ^* \in \mathcal {L}_\mathsf{ABS}$. Given the forgery of $\mathcal {B}_\mathsf{ABS}$, $\mathcal {A}$ first parses the proof $\pi ^*$ as $(\alpha ^*, \gamma ^*)$, where $\alpha ^*$, $\gamma ^*$ are the commitment and response of the underlying gap-$\varSigma _m$-protocol (See Definition 5), respectively. $\mathcal {A}$ then checks whether $H(\cdot )$ was queried on $(\chi ^*, \alpha ^*)$. If not it outputs $(0, \epsilon _1)$. Otherwise, there exists an index $i^* \in [Q_H]$ for which the challenge $H(\chi ^*, \alpha ^*)$ is set to $h_{i^*}$. In this case, it outputs $(i^*, ( \alpha ^*, h_{i^*}, \gamma ^*, \chi ^*, \mathsf {M}^*, C^* ))$. Now, since $\mathcal {A}$ simulates $\mathsf {Game}_3$ perfectly and the probability of $\mathcal {B}_\mathsf{ABS}$ outputting a valid forgery without knowledge of the output of $H(\chi ^*, \alpha ^*)$ (i.e., the challenge) is negligible, we have

$$\begin{aligned} \mathsf {acc}&= \Pr \big [(i^*, ( \alpha ^*, h_{i^*}, \gamma ^*, \chi ^*, \mathsf {M}^*, C^* )) \leftarrow \mathcal A^{\mathcal O(\overline{\mathsf {par}}, \cdot )}(\mathsf {par}, h_1, \cdots , h_{Q_H}) ~:~ i^* \ge 1\big ] \nonumber \\&\ge \epsilon _3 - \mathsf {negl}(\lambda ), \end{aligned}$$

(8)

where the probability is taken over the choice of $(\mathsf {par}, \overline{\mathsf {par}}), ( h_i )_{i = 1}^{Q_H}$ and the randomness used by $\mathcal {A}$.

Finally we construct an adversary $\mathcal {B}_{\mathsf {Sign}}$ against the $\mathsf {eu\text {-}cma}$ security of the underlying digital signature scheme using the forking algorithm $\mathsf {F}_{\mathcal A, m}^{\mathcal O(\overline{\mathsf {par}}, \cdot )}$. In particular the advantage of $\mathcal {B}_{\mathsf {Sign}}$ will be $\epsilon ^{m}_3/Q_H^{m - 1} - \mathsf {negl}(\lambda )$ for a constant m. Hence, assuming the $\mathsf {eu\text {-}cma}$ security of the digital signature scheme, $\epsilon _3$ is negligible. Therefore, since $\epsilon = \epsilon _3 \pm \mathsf {negl}(\lambda )$, we conclude that $\epsilon$ is negligible, thus completing the proof. Below, let $\mathcal C_{\mathsf {Sign}}$ be the challenger for the $\mathsf {eu\text {-}cma}$ game of the underlying digital signature scheme. Also, let $\mathsf {vk}_{\mathsf {Sign}}$ be the verification key given to $\mathcal {B}_{\mathsf {Sign}}$ and $\mathsf {sk}_{\mathsf {Sign}}$ be the signing key used by $\mathcal C_{\mathsf {Sign}}$ to answer the signature queries. In particular, $\mathcal C_\mathsf {Sign}$ uses the signing algorithm $\mathsf {S}.\mathsf {Sign}(\mathsf {sk}_\mathsf {Sign}, \cdot )$ to answer signature queries made be $\mathcal {B}_\mathsf{ABS}$. Now, given $\mathsf {vk}_\mathsf {Sign}$, $\mathcal {B}_\mathsf {Sign}$ runs $\mathsf {pk}_\mathsf {Com}\leftarrow \mathsf {C}.\mathsf {Gen}(1^\lambda )$ and prepares $\mathsf {par}$, i.e., the input to $\mathcal {A}$ provided by the input generator $\mathsf {IG}$. This can be done efficiently since $\mathsf {par}$ constitutes only of public values: $\mathsf {vk}_\mathsf {Sign}, \mathsf {pk}_\mathsf {Com}$ and some other public auxiliary parameters specifying the ABS scheme. Since the forking algorithm only requires oracle access to the deterministic algorithm $\mathcal O(\overline{\mathsf {par}}, \cdot ) = \mathsf {S}.\mathsf {Sign}(\mathsf {sk}_\mathsf {Sign}, \cdot )$, which is provided by $\mathcal C_\mathsf {Sign}$, $\mathcal {B}_\mathsf {Sign}$ can properly run the forking algorithm $\mathsf {F}_{\mathcal A, m}^{\mathcal O(\overline{\mathsf {par}}, \cdot )}(\mathsf {par})$ as specified. Note that $\mathsf {par}, \overline{\mathsf {par}}$ are distributed exactly as the output of the input generator $\mathsf {IG}$ defined above. Now, due to the general multi-forking lemma with oracle access (Lemma 1), we obtain the following pairs with probability $\mathsf {frk}$:

$$\begin{aligned} \Big ( 1,~~ \big \{ \alpha ^{(k)}, h^{(k)}, \gamma ^{(k)}, \chi ^{(k)}, \mathsf {M}^{(k)}, C^{(k)} \big \}_{k \in [m]} \Big ), \end{aligned}$$

(9)

where $\chi ^{(k)} = \Big ( \hat{ C}^{(k)}, c^{(k)}_\sigma , ( c^{(k)}_i )_{i = 1}^{\ell + N - 1} \Big )_{k \in [m]}$. Here, by Eq. (1) of Lemma 1, we have

$$\begin{aligned} \mathsf {frk}\ge \mathsf {acc}\cdot \left( \left( \frac{\mathsf {acc}}{Q_H}\right) ^{m - 1} - \frac{f(m)}{\left| \mathcal C_\varSigma \right| } \right) = \frac{\mathsf {acc}^{m}}{Q_H^{m - 1}} - \mathsf {negl}(\lambda ), \end{aligned}$$

(10)

where $\mathcal C_\varSigma$ is the output range of $H(\cdot )$ that is super-polynomially large, m is a constant representing the number of valid transcripts we require to extract a witness and f(m) is a universal positive valued function that only depends on m, i.e., a constant value when viewed as a funtion on the security parameter $\lambda$. Now, we argue that for all $k \in [m]$, the values of the commitments $\alpha ^{(k)}$ and statements $\chi ^{(k)}$ are equivalent, respectively. Let $i^* \in [Q_H]$ be the index outputted by $\mathcal {A}$ in the first run inside the forking algorithm $\mathsf {F}_{\mathcal A, m}^{\mathcal O(\overline{\mathsf {par}}, \cdot )}(\mathsf {par})$. Then, up until the $i^*$-th unique random oracle query to $H(\cdot )$, the behavior of $\mathcal {B}_\mathsf{ABS}$ is the same for every run, since we fix the randomness being used by the challenger $\mathsf {Game}_3'$, $\mathcal {B}_\mathsf{ABS}$ and the ZK simulator $\mathcal {S}$. This implies that whatever submitted by $\mathcal {B}_\mathsf{ABS}$ on the $i^*$-th unique random oracle query to $H(\cdot )$, which is the pair $(\alpha ^{(k)}, \chi ^{(k)})$, must be the same in every run. Let us denote this as $(\alpha ^*, \chi ^* = ( \hat{ C}^*, c_\sigma ^*, ( c^*_i )_{i = 1}^{\ell + N - 1} ))$. Therefore, by running $\mathsf {F}_{\mathcal A, m}^{\mathcal O(\overline{\mathsf {par}}, \cdot )}(\mathsf {par})$, $\mathcal {B}_{\mathsf {Sign}}$ obtains m valid transcript of the form $\big ( \alpha ^*, h^{(k)}, \gamma ^{(k)}, \chi ^*, \mathsf {M}^*, C^* \big )_{k \in [m]}$ where $\mathsf {M}^*,C^*$ are the same in every run as well, due to the winning condition we added in $\mathsf {Game}_3$ and the fact that $\hat{ C}^*$ is the same in every run.

Next, we show that $\mathcal {B}_{\mathsf {Sign}}$ can properly extract a witness from the valid transcripts using the knowledge extractor of the underlying gap-$\varSigma _m$-protocol (See special gap-soundness of Definition 4). Recall that the range of the random oracle $H(\cdot )$ is $\mathcal C_\varSigma = \{ 0, 1, \cdots , m-1 \}^t$ for some constant m and an integer-valued function t that is poly-logarithmic in the security parameter $\lambda$. Now, by Definition 4, in order to extract a witness there needs to exist at least one index $j \in [t]$ such that $\{ h^{(k)}_j \}_{k \in [m]} = \{ 0, 1, \cdots , m - 1 \}$. Since each $h^{(k)}$ are sampled uniformly random over $\mathcal C_H = \{ 0, 1, \cdots , m-1 \}^t$, the probability of no such $j \in [t]$ existing is $(1 - \frac{m!}{m^m})^t$, which is negligible in the security parameter for our choices of m, t. Therefore, with all but negligible probability, $\mathcal {B}_{\mathsf {Sign}}$ is able to extract a witness $(\mathbf {x}^*, \sigma ^*, d^*_{\sigma }, ( d^*_i )_{i = 1}^{\ell + N - 1})$ in the gap-language $\mathcal {L}'_\mathsf{ABS}$ from the m valid transcripts. Furthermore, since we use a statistically binding commitment scheme, the $(\mathbf {x}^*, \sigma ^*)$ pair extracted from the transcripts are the actual pairs used by $\mathcal {B}_\mathsf{ABS}$ to create a forgery, with all but negligible probability.

Finally, we show that $(\mathbf {x}^*, \sigma ^*)$ is a valid signature forgery that allows $\mathcal {B}_{\mathsf {Sign}}$ to win the $\mathsf {eu\text {-}cma}$ game between the challenger $\mathcal C_{\mathsf {Sign}}$. Namely, we show that $\mathbf {x}^*$ was never queried as the key reveal query by $\mathcal {B}_\mathsf{ABS}$ in all of the m runs of $\mathcal {A}$. Note that the only situation $\mathcal {A}$ invokes the signing oracle $\mathcal O(\overline{\mathsf {par}}, \cdot ) = \mathsf {S}.\mathsf {Sign}(\mathsf {sk}_\mathsf {Sign}, \cdot )$ is when $\mathcal {B}_\mathsf{ABS}$ submits a key reveal query to the $\mathsf {Game}_3'$ challenger. This is because we altered the game in $\mathsf {Game}_2$ so that the ZK simulator is used to answer the signing queries made by $\mathcal {B}_\mathsf{ABS}$. Now, since $\mathcal {B}_\mathsf{ABS}$ outputs a valid forgery we have $\hat{C}^*(\mathbf {x}^*) = 1$. Then, by the way we construct $\hat{ C}^*(\mathbf {x}^*)$ in Step 1 of the $\mathsf {Sign}$ algorithm, we have $C(\mathbf {x}^*) = 1$ as well. On the other hand, due to the winning condition of $\mathcal {B}_\mathsf{ABS}$, $\mathcal {B}_\mathsf{ABS}$ must have never made a key reveal query on $\mathbf {x}^*$ such that $C^* (\mathbf {x}^*) = 1$ (in any of the runs). Therefore, we conclude that $\mathbf {x}^*$ was never queried to the $\mathsf {Game}_3'$ challenger by $\mathcal {B}_\mathsf{ABS}$ in any of the runs of $\mathcal {A}$; $(\mathbf {x}^*, \sigma ^*)$ is a valid forgery. Hence, combining Eqs. (8) and (10), the advantage of $\mathcal {B}_\mathsf {Sign}$ is $\epsilon ^{m}_3/Q_H^{m - 1} - \mathsf {negl}(\lambda )$.

4.2 Implications

Since a computationally hiding and statistically binding commitment scheme, a deterministic digital signature scheme and a computationally special HVZK $\varSigma$-protocols for any NP-language are all implied from one-way functions (See for example [Nao91, Rom90, PSV06]), we obtain the following lemma as an implication of our above result:

Lemma 3

If one-way functions exist, then there exist computationally private and adaptive unforgeable attribute-based signature schemes for unbounded circuits in the random oracle model.

5 ABS for Unbounded Circuits from Lattices

In this section, we provide an efficient instantiation of our generic ABS construction for unbounded circuits from lattices. In particular, we prepare a lattice-based signature scheme and a commitment scheme with gap-openings, and construct an associating lattice-based gap-$\varSigma$-protocol for the relation $\mathcal {R}_\mathsf{ABS}$. We believe our gap-$\varSigma$-protocol for proving possession of a valid signature, which departs from the previously known stern-type protocol of [LNSW13], to have applications in other contexts such as group signatures.

5.1 Preparing Tools

We present the underlying lattice-based digital signature scheme and commitment scheme with gap-openings that we use as building blocks for our lattice-based ABS scheme.

Digital Signature Scheme. Here, we review the lattice-based digital signature scheme of Boyen [Boy10] with an improved security reduction by [MP12]. Below, we provide a deterministic version of Boyen’s signature scheme, where the signing algorithm uses a PRF for generating the required randomness. We defer the formal definition of lattices and PRFs to the full version. In the following, by lattice convention, we use the dimension of the lattice n to denote the security parameter.

Theorem 3

Let n, m, q be positive integers such that $m \ge 2n \log q$. Let $\alpha , \beta$ be positive reals such that $\alpha = \varOmega (\sqrt{\ell n \log q} \log n)$ and $\beta = \alpha \omega (\sqrt{\log m})$. Then, the following algorithms $(\mathsf {S}.\mathsf {KeyGen}, \mathsf {S}.\mathsf {Sign}, \mathsf {S}.\mathsf {Verify})$ form a deterministic digital signature scheme with message space $\mathcal M = \{ 0, 1 \}^\ell$ that is $\mathsf {eu\text {-}cma}$ secure under hardness of the $\mathsf {SIS}^\infty _{n, m, q, \ell \tilde{O}(n)}$ problem.

 

$\mathsf {S}.\mathsf {KeyGen}(1^n, 1^\ell )$::

It samples a matrix $\mathbf {A}\in \mathbb Z_q^{n \times m}$ with a trapdoor $\mathbf {T}_\mathbf {A}\in \mathbb Z^{m \times m}$ using algorithm $\mathsf {TrapGen}(1^n, 1^m, q)$. It also samples matrices $\mathbf {A}_i \leftarrow \mathbb Z_q^{n \times m}$ for $i \in [0, \ell ]$, a vector $\mathbf {u}\in \mathbb Z_q^n$ and generates a seed for a PRF by running $r \leftarrow \mathsf {PRF.Gen}(1^n)$. Finally it outputs the verification key $\mathsf {vk}$ and signing key $\mathsf {sk}$ as

$$\begin{aligned} \mathsf {vk}= ( \mathbf {A}, \mathbf {A}_0, \cdots , \mathbf {A}_\ell , \mathbf {u} ), \quad \mathsf {sk}= (\mathbf {T}_\mathbf {A}, r). \end{aligned}$$

$\mathsf {S}.\mathsf {Sign}(\mathsf {sk}, \mathbf {x})$::

On input the message $\mathbf {x}\in \{ 0, 1 \}^\ell$, it first constructs the matrix $\mathbf {A}_\mathbf {x}= \mathbf {A}_0 + \sum _{i = 1}^\ell x_i \mathbf {A}_i \in \mathbb Z_q^{n \times m}$, where $x_i$ is the i-th bit of $\mathbf {x}$. Then using $\mathbf {T}_\mathbf {A}$, it samples a short vector $\mathbf {z}\in \mathbb Z^{2m}$ such that $[\mathbf {A}| \mathbf {A}_\mathbf {x}] \mathbf {z}= \mathbf {u}\mod q$ using algorithm $\mathsf {SampleLeft}(\mathbf {A}, \mathbf {A}_\mathbf {x}, \mathbf {u}, \mathbf {T}_\mathbf {A}, \alpha )$, where the output of $\mathsf {PRF.Eval}(r, \mathbf {x})$ is used as the randomness. Finally, it outputs $\sigma = \mathbf {z}$ as the signature.

$\mathsf {S}.\mathsf {Verify}(\mathsf {vk}, \mathbf {x}, \sigma )$::

It first checks that $\mathbf {x}\in \{ 0, 1 \}^\ell$. Next, it checks whether $[\mathbf {A}| \mathbf {A}_\mathbf {x}] \mathbf {z}= \mathbf {u}\mod q$ and $||\mathbf {z} ||_\infty \le \beta$. It outputs 1 if all the above check passes, otherwise it outputs 0.

 

Commitment Scheme. Here, we present the commitment scheme of [XXW13] with minor modification. In the following let $[\cdot || \cdot ]$ denote the vertical concatenation of vectors.

Theorem 4

Let $n, \bar{m}, q$ be positive integers such that $\bar{m} \ge 3n$, q a prime. Further, let $\gamma , \gamma '$ be positive reals such that $q \ge (4 \gamma + 1)^2$ and $\gamma \ge \gamma ' \omega (\log n)$.¹³ Then, the following algorithms $(\mathsf {C}.\mathsf {Gen}, \mathsf {C}.\mathsf {Com}, \mathsf {C}.\mathsf {Open})$ form a computationally hiding and statistically binding commitment scheme with gap openings under the hardness of the $\mathsf {LWE}_{n, \bar{m}, q, D_{\mathbb Z, \gamma }}$ problem. Here the message space $\mathcal M$ is $\mathbb Z_q$ and the commitment space $\mathcal C$ is $\mathbb Z_q^{\bar{m}}$.  

$\mathsf {C}.\mathsf {Gen}(1^n)$::

It samples $\mathbf {B}\leftarrow \mathbb Z_q^{(n + 1) \times \bar{m}}$ and outputs $\mathsf {pk}= \mathbf {B}$.

$\mathsf {C}.\mathsf {Com}(\mathsf {pk}, \mathsf {M})$::

For a message $\mathsf {M}\in \mathbb Z_q$, it samples a random vector $\mathbf {s}\leftarrow \mathbb Z_q^n$. Then, it samples $\mathbf {e}\leftarrow D_{\mathbb Z^{\bar{m}}, \gamma '}$ until $||\mathbf {e} ||_\infty \le \gamma$ holds.¹⁴ Finally, it outputs $(c, d) = (\mathbf {B}^\top [\mathbf {s}||\mathsf {M}] + \mathbf {e}\mod q, (\mathbf {s}, \mathbf {e}))$.

$\mathsf {C}.\mathsf {Open}(\mathsf {pk}, \mathsf {M}, c, d)$::

It first checks if $\mathsf {M}\in \mathbb Z_{q}$. It then parses $d = (\mathbf {s}, \mathbf {e})$ and checks if $c = \mathbf {B}^\top [\mathbf {s}||\mathsf {M}] + \mathbf {e}\mod q$ and $||\mathbf {e} ||_\infty \le 2\gamma$ hold. If all the check passes it outputs 1, otherwise it outputs 0.

 

Observe that the above commitment scheme has gap-openings; although the commitment algorithm $\mathsf {C}.\mathsf {Com}$ only samples vectors $\mathbf {e}$ such that $||\mathbf {e} ||_\infty \le \gamma$, the opening algorithm $\mathsf {C}.\mathsf {Open}$ accepts $\mathbf {e}$ such that $\gamma < ||\mathbf {e} ||_\infty \le 2\gamma$ as well.

Furthermore, [XXW13] provides three gap-$\varSigma$-protocols for proving useful relations over committed values: $\varSigma _{\mathsf {Open}}$ for proving knowledge of a valid opening and $\varSigma _{\mathsf {Add}}$, $\varSigma _{\mathsf {Mult}}$ ¹⁵ for proving arithmetic relations (over $\mathbb Z_q$) of committed values. We additionally construct one useful gap-$\varSigma$-protocol $\varSigma _\mathsf {EqTo\star }$ for proving that a commitment opens to a specific value. The details of the construction are provided in the full version. Then, the above commitment scheme is equipped with the following four basic gap-$\varSigma$-protocols.

Theorem 5

The commitment scheme with gap openings in Theorem 4 has associating computationally special HVZK gap-$\varSigma$-protocols $(\varSigma _{\mathsf {Open}}, \varSigma _\mathsf {EqTo\star }, \varSigma _\mathsf{Add},$ $\varSigma _\mathsf{Mult})$ for the following four relations:

$$\begin{aligned} \mathcal {R}_{\mathsf {Open}}&= \{ (\mathsf {pk}, c), (\mathsf {M}, d) \mid (c, d) \in \mathcal {D}_\mathsf {Com}(\mathsf {pk}, \mathsf {M}) \},\\ \mathcal {R}_{\mathsf {EqTo\star }}&= \{ (\mathsf {pk}, c, \mathsf {M}), d \mid (c, d) \in \mathcal {D}_\mathsf {Com}(\mathsf {pk}, \mathsf {M}) \},\\ \mathcal {R}_{\mathsf {Add}}&= \{ ( \mathsf {pk}, ( c_i )_{i = 1}^{3} ), ( ( \mathsf {M}_i, d_i )_{i = 1}^3 ) \mid \mathsf {M}_3 = \mathsf {M}_1 + \mathsf {M}_2 \\&\quad \quad \quad \quad \quad \quad \qquad \qquad \qquad \qquad ~\wedge ~ (c_i, d_i) \in \mathcal {D}_\mathsf {Com}(\mathsf {pk}, \mathsf {M}_i)\,\, { for }\,\, i\in [3] \}, \\ \mathcal {R}_{\mathsf {Mult}}&= \{ ( \mathsf {pk}, ( c_i )_{i = 1}^{3} ), ( ( \mathsf {M}_i, d_i )_{i = 1}^3 ) \mid \mathsf {M}_3 = \mathsf {M}_1\cdot \mathsf {M}_2 \\&\quad \quad \quad \quad \quad \quad \qquad \qquad \qquad \qquad ~\wedge ~ (c_i, d_i) \in \mathcal {D}_\mathsf {Com}(\mathsf {pk}, \mathsf {M}_i)\,\, { for }\,\, i\in [3] \}. \end{aligned}$$

The gap-relations $(\varSigma '_{\mathsf {Open}}, \varSigma '_\mathsf {EqTo\star }, \varSigma '_\mathsf{Add}, \varSigma '_\mathsf{Mult})$ are defined similarly except that the set $\mathcal {D}_{\mathsf {G\text {-}Com}}$ is used instead of $\mathcal {D}_\mathsf {Com}$.

The above gap-$\varSigma$-protocols of [XXW13] additionally require internally a standard commitment scheme, which is used by the prover in the first round to send a commitment to the verifier. Although, we can use the commitment scheme of [XXW13] provided above, we use the more efficient lattice-based commitment scheme of Kawachi et al. [KTX08] to instantiate the gap-$\varSigma$-protocols. In this case, the communication costs of $\varSigma _\mathsf {Open}, \varSigma _\mathsf {EqTo\star }$ are $\omega (\bar{m} \log q \log \gamma \log n)$ and $\varSigma _\mathsf {Add}, \varSigma _\mathsf {Mult}$ are $\omega (\bar{m} \log ^3 q \log \gamma \log n)$.

Remark 1

The above four basic gap-$\varSigma$-protocols can be composed in parallel to obtain a gap-$\varSigma$-protocol for larger relations, e.g., provided with commitments $( c_i )_{i = 1}^4$ of the values $( \mathsf {M}_i )_{i = 1}^4$ satisfying $\mathsf {M}_4 = \sum _{i = 1}^3 \mathsf {M}_i$, we can prove this relation by creating one extra auxiliary commitment $c_\mathsf{aux}$ for $\mathsf {M}_\mathsf{aux} = \mathsf {M}_1 + \mathsf {M}_2$ and running two $\varSigma _\mathsf {Add}$ in parallel for the statement pairs $(\mathsf {pk}, c_1, c_2, c_\mathsf{aux})$ and $(\mathsf {pk}, c_\mathsf{aux}, c_3, c_4)$.

5.2 ABS for Unbounded Circuits Based on Lattices

To instantiate the generic ABS construction in Sect. 4 from lattices, it is sufficient to prove that the above digital signature scheme and commitment scheme are equipped with a gap-$\varSigma$-protocol for the relation $\mathcal {R}_\mathsf{ABS}$. Therefore, below we aim at constructing a gap-$\varSigma$ protocol for proving Eqs. (5)–(7) in our ABS construction, where the attribute $\mathbf {x}$ and Boyen signatures $\sigma$ are committed using the commitment scheme of [XXW13]. Here, taking the above Remark 1 into consideration, a gap-$\varSigma$-protocol for proving Eqs. (6) and (7), which are essentially proving that the circuit is computed correctly, can be constructed by simply composing the basic gap-$\varSigma$-protocols $\varSigma _\mathsf {EqTo\star }, \varSigma _{\mathsf {Add}}, \varSigma _\mathsf {Mult}$ in parallel. In more detail, we use $\varSigma _\mathsf {Add}$ and $\varSigma _\mathsf {Mult}$ to prove that we computed each gates correctly, and use $\varSigma _\mathsf {EqTo\star }$ to prove that the value associated to the output wire is equal to 1. Therefore, in the following, we only focus on how to construct a gap-$\varSigma$-protocol for proving Eq. (5); we construct a gap-$\varSigma$-protocol for proving possession of a valid Boyen-signature using $\varSigma _\mathsf {EqTo\star }, \varSigma _{\mathsf {Add}}, \varSigma _\mathsf {Mult}$. Here, we stress that we cannot simply use the gap-$\varSigma$-protocol for proving possession of a valid Boyen-signature of [LNSW13] for our purpose, since their protocol does not allow us to efficiently prove possession of messages satisfying complex arithmetic relations.¹⁶ In other words, since Eqs. (5) and (6) share the same witness $\mathbf {x}= (x_1, \cdots , x_\ell )$, we will not be able to combine the different types of gap-$\varSigma$-protocols of [LNSW13] and [XXW13] to construct a gap-$\varSigma$ protocol for the relation $\mathcal {R}_\mathsf{ABS}$.

To summarize, our goal is to construct a gap-$\varSigma$-protocol for proving possession of a valid Boyen signature $\sigma = \mathbf {z}= [z_1, \cdots , z_{2m}]^\top \in \mathbb Z^{2m}$, where $\mathbf {x}$ $= (x_1, \cdots , x_\ell ) \in \{ 0, 1 \}^\ell$ is viewed as the message, provided the verification key $\mathsf {vk}_\mathsf {Sign}$ and the commitments to the signature $\sigma$ and message $\mathbf {x}$. Then, since the basic gap-$\varSigma$-protocols of Theorem 4 allows for parallel composition, our desired gap-$\varSigma$-protocol for the relation $\mathcal {R}_\mathsf{ABS}$ is obtained by composing the gap-$\varSigma$ protocol for the Boyen signature with the gap-$\varSigma$-protocols for Eqs. (6) and (7) together. Below, we assume the commitment $c_\sigma$ of the signature is provided in the form $( \bar{c}_k )_{k \in [2m]}$ where each $\bar{c}_i$ is a commitment of the k-th element $z_k \in \mathbb Z$ of $\mathbf {z}$ (viewed as an element in $\mathbb Z_q$), and the commitment of the message $c_\mathbf {x}$ is provided in the form $( c_i )_{i \in [\ell ]}$ where each $c_i$ is a commitment of the value $x_i \in \{ 0,1 \}$. Now, due to the verification algorithm of the Boyen signature scheme, proving a signature is valid is equivalent to proving the following three statements:

$$\begin{aligned}&\mathbf {x}\in \{ 0, 1 \}^\ell \quad \Longleftrightarrow \quad x_i \in \{ 0, 1 \}\,\, \text { for } \,\, i \in [\ell ], \end{aligned}$$

(11)

$$\begin{aligned}&||\mathbf {z} ||_\infty \le \beta \quad \Longleftrightarrow \quad \left| z_k \right| \le \beta \,\, \text { for } \,\,\, k \in [2m], \end{aligned}$$

(12)

$$\begin{aligned}&\Big [\mathbf {A}| \mathbf {A}_0 + \sum _{i = 1}^\ell x_i\mathbf {A}_i \Big ] \mathbf {z}= \mathbf {u}\mod q . \end{aligned}$$

(13)

Below we construct gap-$\varSigma$-protocols respectively for the above equations by converting each of them into an arithmetic circuit, and using the basic gap-$\varSigma$-protocols provided in Theorem 4 as building blocks to prove the satisfiability of each circuit.

Gap- $\varSigma$ -Protocol for Proving Eq. (11). It is sufficient to prove that for every $i \in [\ell ]$, the commitment $c_i \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, x_i)$ opens to either 0 or 1. To do so, we first create auxiliary commitments $c_\mathsf{zero} \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, 0)$ and $g_i \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, x^2_i)$ for $i \in [\ell ]$. Then using the commitments $( c_i )_{i \in [\ell ]}$ and the auxiliary commitments, and combining the basic gap-$\varSigma$-protocols $\varSigma _\mathsf {EqTo\star }, \varSigma _{\mathsf {Add}}$ and $\varSigma _{\mathsf {Mult}}$ together, we construct a gap-$\varSigma$-protocol for proving the following statement for all $i \in [\ell ]$:

$$\begin{aligned} c_\mathsf{zero}\,\, \text {opens}\,\,\text {to}\,\text {0} \quad \wedge \quad x^2_i = x_i \cdot x_i \quad \wedge \quad 0 = x^2_i - x_i \end{aligned}$$

Since all arithmetic operations are over the finite field $\mathbb Z_q$, the only $x_i$ that satisfy the above relations are $x_i = 0$ or 1. Therefore, the above gap-$\varSigma$-protocol indeed proves Eq. (11). The total communication cost is $\omega (\ell \bar{m} \log ^3q \log \gamma \log n)$ ¹⁷.

Gap- $\varSigma$ -Protocol for Proving Eq. (12). Here, for simplicity of the protocol, we assume that $\beta$ can be written as $2^\zeta - 1$ for some positive integer $\zeta$. Equivalently, $\zeta = \log (\beta + 1)$. This does not harm the efficiency nor the security of the signature scheme by much, since given any $\beta$, there always exists a value of the form $2^\zeta - 1$ in between $\beta$ and $2\beta$.

First, we prepare some notations. For $k \in [2m]$, let $z_{k, j}$ be the j-th bit of the binary representation of $z_k \in \mathbb Z$ for $j \in [\zeta ]$. Note that, we extend the standard binary decomposition to negative integers as well in the obvious way. In particular, we can bit decompose any $z_k \in [-\beta , \beta ]$ as $z_k = \sum _{j = 1}^{\zeta } 2^{j - 1} z_{k, j}$, where $z_{k, j} \in \{ -1, 0, 1 \}$.¹⁸ Further, set $w_{k, j} = 2^{j - 1} z_{k, j}$ for $j \in [\zeta ]$ and $w_{k, [j']} = \sum _{j = 1}^{j'} w_{k, j}$ for $j' \in [2, \zeta ]$. Finally, define $w_{k, [1]} = w_{k, 1}$. Next, create the following auxiliary commitments for $k \in [2m]$: $c_{\mathsf {zero}} \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, 0)$, $c_{\mathsf {coeff}, j} \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, 2^{j - 1})$, $\bar{c}_{k, j, \mu } \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, z^\mu _{k, j})$, $h_{k, j} \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, w_{k, j})$ for $\mu \in [3]$, $j \in [\zeta ]$, and $h_{k, [j']} \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, w_{k, [j']})$ for $j' \in [2, \zeta ]$. Then, using the commitments $( \bar{c}_k )_{k \in [2m]}$, the auxiliary commitments and composing the gap-$\varSigma$-protocols $\varSigma _\mathsf {EqTo\star }, \varSigma _{\mathsf {Add}}$ and $\varSigma _{\mathsf {Mult}}$ together, we construct a gap-$\varSigma$-protocol for the following statement for all $k \in [2m], j \in [\zeta ]$ and $j' \in [2, \zeta ]$:¹⁹

$$\begin{aligned}&c_{\mathsf {zero}}\,\,\text {opens}\,\,\text {to}\,\, 0 ~ \wedge \,\, c_{\mathsf {coeff},j}\,\, \text {opens}\,\text {to}\,\, 2^j\,\, \wedge ~ z^2_{k, j} = z_{k, j} \cdot z_{k, j} ~ \wedge ~ z^3_{k, j} = z^2_{k, j} \cdot z_{k, j} ~ \wedge ~ \\&0 = z^3_{k, j} - z_{k, j} \wedge w_{k, j} = 2^{j - 1} \cdot z_{k, j} \wedge w_{k, [j']} = w_{k, j' } + w_{k, [j' - 1]} \wedge 0 = z_k - w_{k, [\zeta ]} . \end{aligned}$$

We check that the above statement is equivalent to Eq. (12), i.e., each $z_k$ satisfy $\left| z_k \right| \le \beta$ for all $k \in [2m]$. First, since q is a prime, the only $z_{k, j}$ satisfying $z^3_{k, j} - z_{k, j} = 0$ over $\mathbb Z_q$ are $-1, 0, 1$. Hence, the above statement proves that $z_{k, j} \in \{ -1, 0, 1 \}$. Furthermore, when $z_{k, j} \in \{ -1, 0, 1 \}$, we have $\left| z_k \right| \le \sum _{j = 1}^{\zeta } 2^{j - 1} \left| z_{k, j} \right| \le 2^{\zeta - 1} = \beta$. Therefore, if the above statement holds, then we must have $\left| z_k \right| \le \beta$ for all $k \in [2m]$. The total communication cost is $\omega (m \bar{m} \log \beta \log ^3q \log \gamma \log n)$.

Gap- $\varSigma$ -Protocol for Proving Eq. (13). We first prepare some notations. Let $a_{s, k}$ (resp., $a_{i, s, k}$) denote the $(s, k_1)$-th (resp., $(s, k_2 - m)$-th) entry of $\mathbf {A}$ (resp., $\mathbf {A}_i) \in \mathbb Z_q^{n \times m}$, for $s \in [n]$, $k_1 \in [m]$ (resp., $k_2 \in [m + 1, 2m]$) and $i \in [0, \ell ]$. Then, observe that we can rewrite Eq. (13) using the following equations for $s \in [n]$:

$$\begin{aligned} \sum _{k_1 = 1}^{m} a_{s, k_1} \cdot z_{k_1} + \sum _{k_2 = m + 1}^{2m} \Big ( a_{0, s, k_2} + \sum _{i = 1}^{\ell } x_i \cdot a_{i, s, k_2} \Big ) \cdot z_{k_2} = u_s \end{aligned}$$

(14)

Next, we prepare some auxiliary values for $s \in [n]$ in order to prove the above equations using the gap-$\varSigma$-protocols $\varSigma _\mathsf {EqTo\star }, \varSigma _{\mathsf {Add}}$ and $\varSigma _\mathsf {Mult}$: $w_{i, s, k_2} = x_i \cdot a_{i, s, k_2}$, $w_{[i'], s, k_2} = \sum _{i = 1}^{i'} w_{i, s, k_2}$, $a_{s, k_2} = a_{0, s, k_2} + w_{[\ell ], s, k_2}$ for $i \in [\ell ]$, $i' \in [2, \ell ]$, $k_2 \in [m + 1, 2m]$, $b_{s, k} = a_{s, k} \cdot z_k$ for $k \in [2m]$, $b_{s, [k']} = \sum _{k_1 = 1}^{k'} b_{s, k_1}$ for $k' \in [2, m]$, $b_{s, [k']} = \sum _{k_2= m + 1}^{k'} b_{s, k_2}$ for $k' \in [m + 2, 2m]$ and $t_{s} = b_{s, [m]} + b_{s, [2m]}$. Further define $w_{[1], s, k_2} = w_{1, s, k_2}$, $b_{s, [1]} = b_{s, 1}$ and $b_{s, [m + 1]} = b_{s, m + 1}$. Next, we create auxiliary commitments for the related values for $s \in [n]$: $c_{\mathsf {mat}, s, k_1} \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, a_{s, k_1})$, $c_{\mathsf {mat}, i, s, k_2} \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, a_{i, s, k_2})$ for $i \in [0, \ell ]$, $k_1 \in [m]$, $k_2 \in [m + 1, 2m]$, $\omega _{i ,s, k_2} \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, w_{i, s, k_2})$, $\omega _{[i'], s, k_2} \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, w_{[i'], s, k_2})$, $\alpha _{s, k_2} \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, a_{s, k_2})$ for $i \in [\ell ]$, $i' \in [2, \ell ]$, $k_2 \in [m + 1, 2m]$, $\beta _{s, k} \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, b_{s, k})$ for $k \in [2m]$, $\beta _{s, [k']} \leftarrow \mathsf {C}.\mathsf {Com}(\mathsf {pk}, b_{s, [k']})$ for $k' \in [2, m]\cup [m + 2, 2m]$. Then, using the commitment $( c_i )_{i = 1}^\ell$, $( \bar{c}_k )_{k \in [2m]}$, the auxiliary commitments and composing the gap-$\varSigma$-protocols $\varSigma _{\mathsf {EqTo\star }}, \varSigma _{\mathsf {Add}}$ and $\varSigma _{\mathsf {Mult}}$ together, we construct a gap-$\varSigma$-protocol for the following statement for all $s \in [n]$, $i \in [\ell ]$, $i' \in [2, \ell ]$, $k_1 \in [m]$, $k_2 \in [m+ 1, 2m]$, $k \in [2m]$, $k' \in [2, m] \cup [m + 2, 2m]$:

$$\begin{aligned}&c_{\mathsf {zero}}\,\,\text {opens}\,\,\text {to}\, 0 ~~ \wedge ~~ \\&c_{\mathsf {mat}, s, k_1}, c_{\mathsf {mat}, 0, s, k_2}, c_{\mathsf {mat}, i, s, k_2} \,\,\text {opens}\, \text {to}\,\, a_{s, k}, a_{0, s, k}, a_{i, s, k}, \,\,\text {respectively} ~~\wedge ~~ \\&w_{i, s, k_2} = x_i \cdot a_{i, s, k_2} ~ \wedge ~ w_{[i'], s, k_2} = w_{i', s, k_2} + w_{[i' - 1], s, k_2} ~ \wedge ~ \\&a_{s, k_2} = a_{0, s, k_2} + w_{[\ell ], s, k_2} ~ \wedge ~ b_{s, k} = a_{s, k} \cdot z_{k} ~ \wedge ~ b_{s, [k']} = b_{s, k'} + b_{s, [k' - 1]} ~ \wedge ~ \\&t_s = b_{s, [m]} + b_{s, [2m]} ~ \wedge ~ 0 = u_s - t_s \end{aligned}$$

The above statement can be checked that it is equivalent to proving Eq. (14) for $s \in [n]$. The total communication cost is $\omega (\ell n m \bar{m} \log ^3q \log \gamma \log n)$.

Gap- $\varSigma$ -Protocol for $\mathcal {R}_\mathsf{ABS}$. To summarize, we obtain a gap-$\varSigma$-protocol for proving possession of a valid Boyen signature by composing the gap-$\varSigma$-protocols for proving Eqs. (11–13) together. Then, by composing this protocol with the aforementioned gap-$\varSigma$-protocols for proving Eqs. (6) and (7), we obtain our desired gap-$\varSigma$-protocol for the relation $\mathcal {R}_\mathsf{ABS}$ where the total communication cost is $\omega ( ( m (\ell n + \log \beta ) + \left| C \right| ) \bar{m} \log ^3q \log \gamma \log n )$. Here, $\left| C \right|$ is size of the circuit (i.e., policy) associated to the message. Thus, we obtain our lattice-based ABS scheme for unbounded circuits in the random oracle model by instantiating the generic ABS construction in Sect. 4 with our gap-$\varSigma$ protocol for $\mathcal {R}_\mathsf{ABS}$.