Decentralized multi-authority anonymous credential system with bundled languages on identifiers in bilinear groups

Our contribution

In this paper, we propose a multi-show dACS, which is able to treat any given all-AND formula. We first give syntax of our dACS. Then we give three security notions. One is existential unforgeability (EUF) against collusion attacks. There, we introduce corruption of authorities reflecting a real scenario that an adversary can corrupt some of the authorities and get their master secret keys. The second and third are anonymity and unlinkability of proofs. In our definitions, anonymity means that any probabilistic polynomial-time (PPT) adversary including the issuer can get only a negligible amount of information on identifiers from given proofs. On the other hand, unlinkability means that any PPT adversary cannot distinguish two cases; the first case is that two given proofs are generated by a single entity and the second case is that the two proofs are generated by two entities with different identifiers. Thus, the unlinkability of proofs is a stronger notion than the anonymity in our definitions, and we will prove the implication.

We then give a generic construction of dACS. In our dACS, a feature is that an attribute authority who issues a private secret key to an entity only has to sign the entity's identifier. At that time, the authority uses a set of common public parameters in a standard like NIST FIPS 186-4^[16]. Then, according to the principle of "commit-to-identifier", the entity generates a proof of knowing credentials. There are two building blocks in the construction. One is the structure-preserving signature scheme^[17] and the other is the Groth-Sahai non-interactive proof system^[18,19], where both blocks are based on Type 3 asymmetric bilinear groups^[20]. In the construction, the principle is realized with a bundled language that is simultaneous pairing-product equations on the entity's identifier and a structure-preserving signature on the identifier. Thus, the bundled language works for preventing collusion attacks. The bundled language is a special case of simultaneous equation systems. It would be natural to consider a generalization into the case of more than one common variable. The study of this direction is of independent interest.

In the succeeding section, we instantiate our generic dACS under the Symmetric External Diffie-Hellman (SXDH) assumption^[17-19] on the Type 3 pairings. Then we compare features of our instantiated $$ \mathrm{dACS_{sxdh}} $$ with previous work and evaluate efficiency. As a result, it turns out that "decentralized multi-authority, security in the standard model and unforgeability under the (simple) SXDH assumption" is a positive aspect, as well as security considering partial corruption of authorities. Efficiency evaluation of our $$ \mathrm{dACS_{sxdh}} $$ shows that, when the number of attribute credentials involved in a proof is two, the data length of a proof is 68k bytes, and generation and verification times are 2.8 and 1.8 s, respectively. Since the proof size is linear in the number of attribute credentials involved in a proof, a construction with smaller asymptotic behavior should be our future work.

Related recent work

From the viewpoint of issuing authorities, the work by Garman et al. is the first ACS with decentralized multi-authority in the attribute-based setting (dACS, for short), which is capable of treating all-AND formulas^[10]. Our dACS, in addition, is proven secure even when some of the authorities are corrupted (i.e., the master secret keys of them are leaked to adversaries).

Collusion attacks are also considered in the work by Garman et al., but the security claim is in the random oracle model^[10]. As for collusion resistance in the standard model, Camenisch et al. proposed a dACS that has the property^[21]. Moreover, the ACS^[21] has the security of the universal composability^[22,23]. Our $$ \mathrm{dACS_{sxdh}} $$ instantiated under the SXDH assumption is also universally composable due to the universal composability of the Groth-Sahai proof system^[18,19]. We note that, though the dACS^[21] and our $$ \mathrm{dACS_{sxdh}} $$ attain similar properties, the ACS by Camenisch et al. needs more assumptions than our $$ \mathrm{dACS_{sxdh}} $$ in the security proof of unforgeability^[21].

As for fine-grained access control, the abACS by Sadiah et al. is capable of treating monotone formulas, though the proof size is exponential to the number of attributes appearing in the formula^[24]. The abACS by Okishima-and-Nakanishi^[25] is capable of treating Conjunctive Normal Form (CNF) formulas. The abACS by Fuchsbauer et al. is capable of treating all-and formulas with an advantage of prover anonymity at issuing phase^[26]. We note that these three abACSs have not been studied in a security experiment of collusion resistance. Though the two abACSs by Tan and Groß^[8] and Chan and Yuen^[9] mentioned above are capable of treating monotone formulas and have collusion resistance, they are not in the setting of decentralized multi-authority. Concerning the attributes issued under each authority, our dACS can treat any access policy of an all-AND formula that covers plural attributes for each authority (and the number of authorities is more than one). From the viewpoint, designing a decentralized multi-authority abACS with more fine-grained access policies, for instance, any monotone formulas, is a challenging problem.

Replay attack is one of the most typical threats to authentication systems. In a replay attack, an attacker intercepts valid data that are transmitted from a prover to a verifier. Then it maliciously re-sends them, after some time intervals, to make the verifier accept the prover. Thus, the aim of a replay attack is to cause mis-authentication that leads to potential stronger security breaches. It is also possibly applicable to ACSs, especially because of anonymity. One of the typical countermeasures against replay attack is introducing interactive proofs. That is, the verifier generates a random challenge message at every session of authentication to reject a re-sent response message. As for non-interactive proofs, in recent privacy-preserving systems^[27,28] in which proofs are non-interactive, permissioned blockchains are employed, which is in contrast with the permissionless blockchain employed in Bitcoin^[29]. A permissioned blockchain fits our dACS because transactions including anonymous credentials are permitted by the authorities. In the systems, the replay attack can be detected by the authorities.

Finally, we note here recent studies that developed more functions than our dACS. Au et al. proposed a dynamic $$ k $$-times anonymous authentication ($$ k $$-TAA) scheme, which allows members of a group to be authenticated anonymously by application providers for a bounded number of times, where application providers can independently and dynamically grant or revoke access rights to members in their own group^[30]. Concerning a revocation mechanism that is needed for real usage, Ma and Chow^[31] proposed updatable anonymous credentials with revocation and reputation management. Extending these concepts to multi-authority systems (as discussed in its appendix) would provide a broader context for our dACS. As for threshold signatures, Doerner et al. proposed an ACS with threshold issuance by constructing a secure multiparty signing protocol for the BBS+ signature scheme^[32]. Wong et al. proposed a secure multiparty computation of threshold signatures, which presented an efficient threshold Elliptic Curve Digital Signature Algorithm (ECDSA) protocol^[33].

Our work in this paper is a significantly extended version of the proceeding paper presented at SecITC 2020^[34]. Especially the sections of "Introduction", "Instantiation" and "Feature Comparison and Efficiency Evaluation" are totally expanded.

Organization of the paper

In Section "PRELIMINARIES", we fix notations and summarize the needed notions for later sections. In Section "BUNDLED LANGUAGE", we explain our ideas, which is for the Groth-Sahai proofs. In Section "DECENTRALIZED MULTI-AUTHORITY ANONYMOUS CREDENTIAL SYSTEM", we propose the syntax and security definitions of our dACS. In Section "GENERIC CONSTRUCTION", we give a construction of our dACS employing the Groth-Sahai proof system and a structure-preserving signature scheme. In Section "INSTANTIATION", we concretely describe our dACS under the SXDH assumption. In Section "FEATURE COMPARISON AND EFFICIENCY EVALUATION", we compare the features of our instantiated $$ \mathrm{dACS_{sxdh}} $$ with those of the previous abACSs. Then we evaluate efficiency of our $$ \mathrm{dACS_{sxdh}} $$ by partial implementation and estimation. In Section "CONCLUSION", we summarize our work and state future directions.

Bilinear groups

Let $$ \mathcal{BG} $$ be a generation algorithm of bilinear groups^[20]: $$ \mathcal{BG}(1^{ \lambda}) \to (p, {\hat{\mathbb G}}, \check{{\mathbb G}}, \mathbb{T}, e, \hat{G}, \check{G}) $$. Here $$ p $$ is a prime number of bit-length $$ \lambda $$, $$ {\hat{\mathbb G}}, \check{{\mathbb G}} $$ and $$ \mathbb{T} $$ are cyclic groups of order $$ p $$, and $$ \hat{G} $$ and $$ \check{G} $$ are generators of $$ {\hat{\mathbb G}} $$ and $$ \check{{\mathbb G}} $$, respectively. We denote operations in $$ {\hat{\mathbb G}} $$, $$ \check{{\mathbb G}} $$ and $$ \mathbb{T} $$ multiplicatively. $$ e $$ is the bilinear map $$ {\hat{\mathbb G}} \times \check{{\mathbb G}} \to \mathbb{T} $$. $$ e $$ should have the following two properties: Non-degeneracy: $$ e( \hat{G}, \check{G}) \neq 1_{ \mathbb{T}} $$, and Bilinearity: $$ \forall a \in \mathbb{Z}_p, \forall b \in \mathbb{Z}_p, \forall \hat{X} \in {\hat{\mathbb G}}, \forall \check{Y} \in \check{{\mathbb G}}, e( \hat{X}^{a}, \check{Y}^b) = e( \hat{X}, \check{Y})^{ab} $$. Hereafter we denote an element in $$ {\hat{\mathbb G}} $$ and $$ \check{{\mathbb G}} $$ with hat "$$ \hat{\ } $$" and check "$$ \check{\ } $$", respectively. Then, according to the previous work by Escala and Groth^[19], we introduce the following linear algebra-friendly additive notations.

Then, for further simplicity, we introduce the following notation.

Then it is easy to see that the following equality holds.

Finally, we extend the notation [Equation (3)] to a vector and a matrix form in the following way.

and

Structure-preserving signature scheme

The structure-preserving signature scheme^[17,35]$$ \textsf{Sig} $$ consists of four PPT algorithms: $$ \textsf{Sig} = $$$$ ( \textsf{Sig.Setup}, $$$$ \textsf{Sig.KG}, $$$$ \textsf{Sig.Sign}, $$$$ \textsf{Sig.Vrf}) $$.

$$ \textsf{Sig.Setup}(1^{ \lambda}) \to pp $$. On input the security parameter $$ 1^{ \lambda} $$, this PPT algorithm executes the generation algorithm of bilinear groups, and it sets the output as a set of public parameters: $$ \mathcal{BG}(1^{ \lambda}) \to (p, {\hat{\mathbb G}}, \check{{\mathbb G}}, \mathbb{T}, e, \hat{G}, \check{G}) =: pp $$. It returns $$ pp $$.

$$ \textsf{Sig.KG}() \to ( \text{PK}, \text{SK}) $$. Based on the set of public parameters $$ pp $$, this PPT algorithm generates a signing key $$ \text{SK} $$ and the corresponding public key $$ \text{PK} $$. It returns $$ ( \text{PK}, \text{SK}) $$.

$$ \textsf{Sig.Sign}( \text{PK}, \text{SK}, m) \to \sigma $$. On input the public key $$ \text{PK} $$, the secret key $$ \text{SK} $$ and a message $$ m \in {\hat{\mathbb G}} $$ or $$ \check{{\mathbb G}} $$, this PPT algorithm generates a signature $$ \sigma $$. In the case of the structure-preserving signatures, $$ \sigma $$ consists of elements $$ (V_{i})_{i} $$ where $$ V_i $$ is in either $$ {\hat{\mathbb G}} $$ or $$ \check{{\mathbb G}} $$. It returns $$ \sigma := (V_{i})_{i} $$.

$$ \textsf{Sig.Vrf}( \text{PK}, m, \sigma) \to d $$. On input the public key $$ \text{PK} $$, a message $$ m \in {\hat{\mathbb G}} $$ or $$ \check{{\mathbb G}} $$ and a signature $$ \sigma = (V_{i})_{i} $$, this deterministic algorithm returns a boolean decision $$ d $$.

The correctness should hold for the scheme $$ \textsf{Sig} $$: For any security parameter $$ 1^{ \lambda} $$, any set of public parameters $$ pp \gets \textsf{Sig.Setup}(1^{ \lambda}) $$ and any message $$ m $$, $$ \Pr[ d = 1 \mid ( \text{PK}, \text{SK}) \gets \textsf{Sig.KG}(), \sigma \gets \textsf{Sig.Sign}( \text{PK}, \text{SK}, m), d \gets \textsf{Sig.Vrf}( \text{PK}, m, \sigma) ] = 1 $$.

Adaptive chosen-message attack of an existential forgery on the scheme $$ \textsf{Sig} $$ by a forger algorithm $$ \mathbf{F} $$ is defined by the following algorithm of an experiment.

In the above experiment, $$ \mathbf{F} $$ issues a query $$ m_j $$ to its signing oracle $$ \mathbf{SignO}( \text{PK}, \text{SK}, \cdot) $$. Then $$ \mathbf{F} $$ receives a valid signature $$ \sigma_j $$ as a reply. The queries are at most $$ q_{ \text{s}} $$ times ($$ 1 \leq j \leq q_{ \text{s}} $$), and are bounded by a polynomial in $$ \lambda $$. After receiving the replies, $$ \mathbf{F} $$ returns a message-signature pair $$ (m^*, \sigma^*) $$. A restriction is imposed on $$ \mathbf{F} $$ that the message $$ m^* $$ of the forgery should not be contained in the set of queries $$ \{ m_j \}_{1 \leq j \leq q_{ \text{s}}} $$. The advantage of $$ \mathbf{F} $$ over $$ \textsf{Sig} $$ is defined as $$ \mathbf{Adv}^{ \text{euf-cma}}_{\textsf{Sig}, \mathbf{F}}(\lambda) := \Pr[ \textsf{Exp}^{ \text{euf-cma}}_{\textsf{Sig}, \mathbf{F}}(1^\lambda) \text{ returns } \text{Win}] $$.

Definition 1 (EUF-CMA^[36]) The scheme $$ {Sig} $$ is said to be existentially unforgeable against adaptive chosen-message attacks (EUF-CMA) if, for any PPT algorithm $$ \mathbf{F} $$, the advantage $$ \mathbf{Adv}^{ {euf-cma}}_{{Sig}, \mathbf{F}}(\lambda) $$ is negligible in $$ \lambda $$.

Non-interactive commit-and-prove scheme for structure-preserving signatures

According to the "fine-tuning Groth-Sahai proofs" system^[19], we survey here the non-interactive commit-and-prove scheme on pairing-product equations, though we treat them in their additive forms. A commit-and-prove scheme $$ \textsf{CmtPrv} $$ consists of six PPT algorithms: $$ \textsf{CmtPrv} = [ \textsf{CmtPrv}\textsf{.Setup}, \textsf{Cmt} = ( \textsf{Cmt.KG}, \textsf{Cmt.Com}, \textsf{Cmt.Vrf}), \Pi = ( \textsf{Prv.P}, \textsf{Prv.V})] $$. Intuitively, there are three parts in $$ \textsf{CmtPrv} $$ and they function as follows. The first part $$ \textsf{CmtPrv}\textsf{.Setup} $$ generates a set of public parameters $$ pp $$. The second, commit-part, provides a set of tools that realize a "cryptographic envelope" from a sender to a receiver, which is along the technique of "dual-mode" commitment^[18]. The third, prove-part, is for a prover to generate a proof to a verifier, which is to prove that the prover knows the data committed by the commit-algorithm of the commit-part, in a witness-indistinguishable way.

Four properties of commit-part

Definition 2 (Correctness^[18,19]) A commitment scheme $$ {Cmt} $$ is said to be correct if it satisfies the following condition: For any security parameter $$ 1^{ \lambda} $$, any set of public parameters $$ pp \gets {CmtPrv}{.Setup}(1^{ \lambda}) $$, any commitment key $$ ck \gets {Cmt.KG}( {mode}) $$ where $$ {mode} = {nor} $$ or $$ {ext} $$ or $$ {sim} $$, and any message $$ w $$,

Definition 3 (Dual Mode^[18]) A commitment scheme $$ {Cmt} $$ is said to be dual mode if it satisfies the following condition: For any security parameter $$ 1^{ \lambda} $$, any set of public parameters $$ pp \gets {CmtPrv}{.Setup}(1^{ \lambda}) $$ and any PPT algorithm $$ \mathbf{A} $$,

From Equation (13), the computational indistinguishability [(Equation (14)] is equivalent to the following: For any security parameter $$ 1^{ \lambda} $$, for any set of public parameters $$ pp \gets \textsf{CmtPrv}\textsf{.Setup}(1^{ \lambda}) $$ and any PPT algorithm $$ \mathbf{A} $$, the advantage $$ \mathbf{Adv}^{ \text{ind-dual}}_{\textsf{Cmt}, \mathbf{A}}(\lambda) $$ of $$ \mathbf{A} $$ over $$ \textsf{Cmt} $$ defined by the difference below is negligible in $$ \lambda $$:

The indistinguishability [Equation (15)] holds, for example, for an instance of the Groth-Sahai proof system under the SXDH assumption^[18,19].

Definition 4 (Perfectly Binding^[18]) A commitment scheme $$ {Cmt} $$ is said to be perfectly binding if it satisfies the following condition for some unbounded algorithm $$ {Cmt.Open} $$: For any security parameter $$ 1^{ \lambda} $$, any set of public parameters $$ pp \gets {CmtPrv}{.Setup}(1^{ \lambda}) $$, any commitment key $$ ck \gets {Cmt.KG}( {nor}) $$ and any message $$ w $$,

Definition 5 (Perfectly Hiding^[18]) A commitment scheme $$ {Cmt} $$ is said to be perfectly hiding if it satisfies the following condition: For any security parameter $$ 1^{ \lambda} $$, any set of public parameters $$ pp \gets {CmtPrv}{.Setup}(1^{ \lambda}) $$, any commitment key $$ ck $$ s.t. $$ ( ck, tk) \gets {Cmt.KG}( {sim}) $$ and any PPT algorithm $$ \mathbf{A} $$,

Four properties of prove-part

Definition 6 (Perfect Correctness^[18]) A commit-and-prove scheme $$ {CmtPrv} $$ is said to be perfectly correct if it satisfies the following condition: For any security parameter $$ 1^{ \lambda} $$, any set of public parameters $$ pp \gets {CmtPrv}{.Setup}(1^{ \lambda}) $$, any commitment key $$ ck \gets {Cmt.KG}( {mode}) $$ where $$ {mode} = {nor} $$ or $$ {ext} $$ or $$ {sim} $$ with $$ pp := ( pp, ck) $$, and any PPT algorithm $$ \mathbf{A} $$,

Definition 7 (Perfect Soundness^[18]) A commit-and-prove scheme $$ {CmtPrv} $$ is said to be perfectly sound if it satisfies the following condition for some unbounded algorithm $$ {Cmt.Open} $$: For any security parameter $$ 1^{ \lambda} $$, any set of public parameters $$ pp \gets {CmtPrv}{.Setup}(1^{ \lambda}) $$, any commitment key $$ ck \gets {Cmt.KG}( {nor}) $$ and any PPT algorithm $$ \mathbf{A} $$,

Let $$ \mathcal{C}_{ ck} $$ be the set of commitments under $$ ck $$ to some message $$ w $$.

Definition 8 (Perfect Knowledge Extraction^[18]) A commit-and-prove scheme $$ {CmtPrv} $$ is said to be perfectly knowledge extractable if it satisfies the following condition for some PPT algorithm $$ {Cmt.Ext} $$: For any security parameter $$ 1^{ \lambda} $$, any set of public parameters $$ pp \gets {CmtPrv}{.Setup}(1^{ \lambda}) $$, any commitment key $$ ( ck, xk) \gets {Cmt.KG}( {ext}) $$ and any PPT algorithm $$ \mathbf{A} $$,

Definition 9 (Composable Witness-Indistinguishability^[18]) A commit-and-prove scheme $$ {CmtPrv} $$ is said to be composably witness-indistinguishable if it satisfies the following condition: For any security parameter $$ 1^{ \lambda} $$, any set of public parameters $$ pp \gets {CmtPrv}{.Setup}(1^{ \lambda}) $$ and any PPT algorithm $$ \mathbf{A} $$, the following holds.

Especially, perfect witness-indistinguishability holds from Equation (17).

Syntax

Our dACS consists of five PPT algorithms, $$ ( \textsf{Setup} $$, $$ \textsf{AuthKG} $$, $$ \textsf{PrivKG} $$, $$ \textsf{Prover} $$, $$ \textsf{Verifier}) $$. Intuitively, $$ \textsf{Setup} $$ generates a set of common public parameters $$ pp $$. In a real use, it is executed only once by an entity that maintains a standard like NIST FIPS 186-4^[16]. Then a key-issuing authority of an attribute executes $$ \textsf{AuthKG} $$ to generate its master secret key and public key. Then, the authority, being asked by an entity possessing an attribute, generates and issues a private secret key of the attribute for the entity. By using the private secret key(s), the entity executes $$ \textsf{Prover} $$ to generate a proof of knowing the key(s) of attribute(s). Receiving the proof, any verifier executes $$ \textsf{Verifier} $$ and decides whether the proof is valid to confirm the knowledge of attribute(s) or not.

$$ \bullet \ \textsf{Setup}(1^{ \lambda}) \to pp $$. This PPT algorithm is needed to generate a set of public parameters $$ pp $$. On input the security parameter $$ 1^{ \lambda} $$, it generates the set $$ pp $$. It returns $$ pp $$.

$$ \bullet \ \textsf{AuthKG}(a) \to ( \text{PK}^{a}, \text{MSK}^{a}) $$. This PPT algorithm is executed by a key-issuing authority indexed by $$ a $$. On input the authority index $$ a $$, it generates the $$ a $$-th public key $$ \text{PK}^{a} $$ of the authority and the corresponding $$ a $$-th master secret key $$ \text{MSK}^{a} $$. It returns $$ ( \text{PK}^{a}, \text{MSK}^{a}) $$.

$$ \bullet \ \textsf{PrivKG}( \text{PK}^{a}, \text{MSK}^{a}, \texttt{i}) \to \text{sk}^{a}_{ \texttt{i}} $$. This PPT algorithm is executed by the $$ a $$-th key-issuing authority. On input the $$ a $$-th public and master secret keys $$ ( \text{PK}^{a}, \text{MSK}^{a}) $$ and an element $$ \texttt{i} \in {\hat{\mathbb G}} $$ (that is an identifier of a prover), it generates a private secret key $$ \text{sk}^{a}_{ \texttt{i}} $$ of a prover. It returns $$ \text{sk}^{a}_{ \texttt{i}} $$.

$$ \bullet \ \textsf{Prover}(( \text{PK}^{a})^{a \in A'}, \texttt{i}, ( \text{sk}^{a}_{ \texttt{i}})^{a \in A'}) \to \pi $$. This PPT algorithm is executed by a prover who is to be authenticated, where $$ A' $$ denotes a subset of the set $$ A $$. On input the public keys $$ ( \text{PK}^{a})^{a \in A'} $$, an identity element $$ \texttt{i} $$ and the corresponding private secret keys $$ ( \text{sk}^{a}_{ \texttt{i}})^{a \in A'} $$, it returns a proof $$ \pi $$.

$$ \bullet \ \textsf{Verifier}(( \text{PK}^{a})^{a \in A'}, \pi) \to d $$. This deterministic polynomial-time algorithm is executed by a verifier who confirms that the prover certainly knows the secret keys for indices $$ a \in A' $$. On input the public keys $$ ( \text{PK}^{a})^{a \in A'} $$ and the proof $$ \pi $$, it returns $$ d: = 1 $$ ("accept") or $$ d := 0 $$ ("reject").

Security definitions

We define three security notions for our ACS dACS; EUF against collusion attacks, anonymity and unlinkability of proofs. Hereafter, the notation "(algorithm name)+O" means the oracle that functions as the algorithm.

Construction

According to our syntax, the scheme dACS consists of five PPT algorithms: $$ \textsf{dACS} = $$$$ ( \textsf{Setup}, $$$$ \textsf{AuthKG}, $$$$ \textsf{PrivKG}, $$$$ \textsf{Prover}, $$$$ \textsf{Verifier}) $$.

$$ \bullet \ \textsf{Setup}(1^{ \lambda}) \to pp $$. On input the security parameter $$ 1^{ \lambda} $$, it runs the generation algorithm of bilinear groups, and it sets the output as a set of public parameters: $$ \mathcal{BG}(1^{ \lambda}) \to (p, {\hat{\mathbb G}}, \check{{\mathbb G}}, \mathbb{T}, e, \hat{G}, \check{G}) =: pp $$. Note that $$ pp $$ is common for both the structure-preserving signature scheme $$ \textsf{Sig} $$ and the commit-and-prove scheme $$ \textsf{CmtPrv} $$. Besides, it runs the generation algorithm of commitment key: $$ \textsf{Cmt.KG}( \texttt{nor}) \to ck $$. It returns $$ pp := ( pp, ck) $$.

$$ \bullet \ \textsf{AuthKG}(a) \to ( \text{PK}^{a}, \text{MSK}^{a}) $$. On input an authority index $$ a $$, it executes the key-generation algorithm $$ \textsf{Sig.KG}() $$ to obtain $$ ( \text{PK}, \text{SK}) $$. It sets $$ \text{PK}^{a} := \text{PK} $$ and $$ \text{MSK}^{a} := \text{SK} $$. It returns $$ ( \text{PK}^{a}, \text{MSK}^{a}) $$.

$$ \bullet \ \textsf{PrivKG}( \text{PK}^{a}, \text{MSK}^{a}, \texttt{i}) \to \text{sk}^{a}_{ \texttt{i}} $$. On input $$ \text{PK}^{a} $$, $$ \text{MSK}^{a} $$ and an element $$ \texttt{i} \in {\hat{\mathbb G}} $$, it sets $$ \text{PK} := \text{PK}^{a} $$ and $$ \text{SK} := \text{MSK}^{a} $$ and $$ m := \hat{M} := \texttt{i} $$. It executes the signing algorithm $$ \textsf{Sig.Sign}( \text{PK}, \text{SK}, m) $$ to obtain a signature $$ \sigma $$. It sets $$ \text{sk}^{a}_{ \texttt{i}} := \sigma $$. It returns $$ \text{sk}^{a}_{ \texttt{i}} $$.

$$ \bullet \ \textsf{Prover}(( \text{PK}^{a})^{a \in A'}, \texttt{i}, ( \text{sk}^{a}_{ \texttt{i}})^{a \in A'}) \to \pi $$. On input $$ ( \text{PK}^{a})^{a \in A'} $$, $$ \texttt{i} $$ and $$ ( \text{sk}^{a}_{ \texttt{i}})^{a \in A'} $$, it first commits to $$ \texttt{i} $$:

Second, for each $$ a \in A' $$, it commits to the components $$ ( \sigma^{a}_{k})_{k} $$ of the signature $$ \sigma^{a} $$ in the componentwise way.

Then, for each authority index $$ a $$ it sets $$ x^{a} := \text{PK}^{a} $$. It also sets $$ c^{a} := (c_0, (c^{a}_{k})_{k}) $$, $$ w^{a} := (w_0, (w^{a}_{k})_{k}) := ( \texttt{i}, ( \sigma^{a}_{k})_{k}) $$ and $$ r^{a} := (r_0, (r^{a}_{k})_{k}) $$. It executes the prove-algorithm to obtain a proof:

It sets $$ \bar{\pi}^{a} := ( (c^{a}_{k})_{k}, \pi^{a} ) $$ for each $$ a \in A' $$, and it merges all the $$ \bar{\pi}^{a} $$s and the commitment $$ c_0 $$ as $$ \pi := (c_0, (\bar{\pi}^{a})^{a \in A'} ) $$. It returns $$ \pi $$.

$$ \bullet \ \textsf{Verifier}(( \text{PK}^{a})^{a \in A'}, \pi) \to d $$. On input $$ ( ( \text{PK}^{a})^{a \in A'}, \pi) $$, it sets $$ x^{a} := \text{PK}^{a} $$ and it sets $$ c^{a} := (c_0, (c^{a}_{k})) $$ for each $$ a \in A' $$. Then it executes the verify-algorithm for each $$ a \in A' $$ to obtain the decisions:

If all the decisions $$ d^{a} $$s are $$ 1 $$, then it returns $$ d := 1 $$; otherwise, it returns $$ d := 0 $$.

Security proofs

Theorem 1 (EUF against Collusion Attacks). For any PPT algorithm $$ \mathbf{A} $$ that is in accordance with the experiment $$ {Exp}^{ {euf-coll}}_{{dACS}, \mathbf{A}}{(1^\lambda, 1^\mu)} $$, there exists a PPT algorithm $$ \mathbf{F} $$ that is in accordance with the experiment $$ {Exp}^{ {euf-cma}}_{{Sig}, \mathbf{F}}(1^\lambda) $$ and the following inequality holds.

Theorem 1 means that, if the structure-preserving signature scheme $$ \textsf{Sig} $$ is existentially unforgeable against adaptive chosen-message attacks, then our $$ \textsf{dACS} $$ is EUF against collusion attacks.

Proof. Given any PPT algorithm $$ \mathbf{A} $$ that is in accordance with the experiment $$ \textsf{Exp}^{ \text{euf-coll}}_{\textsf{dACS}, \mathbf{A}}{(1^\lambda, 1^\mu)} $$, we construct a PPT algorithm $$ \mathbf{F} $$ that generates an existential forgery of $$ \textsf{Sig} $$ according to the experiment $$ \textsf{Exp}^{ \text{euf-cma}}_{\textsf{Sig}, \mathbf{F}}(1^\lambda) $$. $$ \mathbf{F} $$ is given as input the set of public parameters $$ pp $$ and a public key $$ \text{PK}_{ \textsf{Sig}} $$. $$ \mathbf{F} $$ is also given an auxiliary input $$ \mu $$. $$ \mathbf{F} $$ executes $$ \textsf{Cmt.KG}( \texttt{ext}) $$ to obtain a pair $$ ( ck, xk) $$. $$ \mathbf{F} $$ sets $$ pp := ( pp, ck) $$. $$ \mathbf{F} $$ invokes the algorithm $$ \mathbf{A} $$ with $$ 1^{ \lambda} $$ to obtain the number $$ \mu $$ and $$ S t $$. $$ \mathbf{F} $$ chooses a target index$$ a^{\dagger} $$ from the set $$ A := [\mu] $$uniformly at random. $$ \mathbf{F} $$ executes the generation algorithm of an authority key honestly for $$ a \in A $$except the target index $$ a^{\dagger} $$. As for $$ a^{\dagger} $$, $$ \mathbf{F} $$ uses the input public key:

$$ \mathbf{F} $$ inputs $$ S t $$ and the public keys $$ ( \text{PK}^{a})^{a \in A} $$ into $$ \mathbf{A} $$. Then $$ \mathbf{F} $$ obtains a set of corrupted authority indices $$ \tilde{A} $$ from $$ \mathbf{A} $$. $$ \mathbf{F} $$ sets $$ \bar{\tilde{A}} := A \backslash \tilde{A} $$. If $$ a^{\dagger} \in \bar{\tilde{A}} $$ (the case $$ \text{TgtIdx}_1 $$), then $$ a^{\dagger} $$ is not in $$ \tilde{A} $$ and $$ \mathbf{F} $$ is able to input $$ [ S t, ( \text{MSK}^{a})^{a \in \tilde{A}}] $$ into $$ \mathbf{A} $$. Otherwise, $$ \mathbf{F} $$ aborts.

Simulation of private secret key oracle. When $$ \mathbf{A} $$ issues a private secret key query with $$ a \in A_j \subsetneq \bar{\tilde{A}} $$ and $$ \texttt{i}_j \in \mathbb{Z}_p (j=1, \dots, q_{ \text{sk}}) $$, $$ \mathbf{F} $$ executes the generation algorithm of private secret key with $$ \texttt{i}_j $$ honestly for $$ a \in \bar{\tilde{A}} $$ such that $$ a \neq a^{\dagger} $$. As for $$ a = a^{\dagger} $$, $$ \mathbf{F} $$ issues a signing query to its oracle with $$ \texttt{i}_j $$:

$$ \mathbf{F} $$ replies to $$ \mathbf{A} $$ with the secret key $$ \text{sk}^{a}_{ \texttt{i}_j} $$. This is a perfect simulation.

At the end $$ \mathbf{A} $$ returns a forgery proof and the target set of authority indices $$ (\pi^*, A^*) $$. Note here that $$ A^* \subset \bar{\tilde{A}} $$ as in the definition.

Generating Existential Forgery. Next, $$ \mathbf{F} $$ runs a $$ \textsf{Verifier} $$ with an input $$ [( \text{PK}^{a})^{a \in A^*}, \pi^*] $$. If the decision $$ d $$ of $$ \textsf{Verifier} $$ is $$ 1 $$, then $$ \mathbf{F} $$ executes for each $$ a \in A^* $$ the extraction algorithm $$ \textsf{Cmt.Ext}( xk, c^{a}) $$ to obtain a committed message $$ (w^{a})^* = ((w^{a}_0)^*, ((w^{a}_{k})^*)_{k} ) $$ (see Definition 8). Note here that, for all $$ a \in A^* $$, $$ (w^{a}_0)^* $$ is equal to a single element $$ (w_0)^* $$ in $$ {\hat{\mathbb G}} $$. This is because of the perfectly binding property of $$ \textsf{Cmt} $$. Then $$ \mathbf{F} $$ sets $$ \texttt{i}^* := (w_0)^* $$. Here the restriction [Equations (21)and (22)] assures that, if $$ q_{ \text{sk}} > 0 $$, then there exists at least one $$ \hat{a} \in (A^* \backslash A_j) $$ for some $$ j \in [q_{ \text{sk}}] $$. If $$ q_{ \text{sk}} = 0 $$, then there exists at least one $$ \hat{a} \in A^* $$. $$ \mathbf{F} $$ chooses one such $$ \hat{a} $$ and sets $$ \sigma^* := ( \sigma^{\hat{a}})^* :=[(w^{\hat{a}}_{k})^*]_{k} $$. $$ \mathbf{F} $$ returns a forgery pair of a message and a signature $$ ( \texttt{i}^*, \sigma^*) $$. This completes the description of $$ \mathbf{F} $$.

Probability evaluation. The probability that the returned value $$ ( \texttt{i}^*, \sigma^*) $$ is actually an existential forgery is evaluated as follows. We name the events in the above $$ \mathbf{F} $$ as:

We have the following equalities.

The left-hand side of the equality [Equation (24)] is expanded as follows.

Claim 1

Proof. $$ \hat{a} $$ coincides with $$ a^{\dagger} $$ with probability $$ 1/|A| $$ because $$ a^{\dagger} $$ is chosen uniformly at random from $$ A $$ by $$ \mathbf{F} $$ and no information of $$ a^{\dagger} $$ is leaked to $$ \mathbf{A} $$. □

Claim 2If $$ \text{TgtIdx} $$ occurs, then $$ \texttt{i}^* $$ is not queried by $$ \mathbf{F} $$ to its oracle $$ \mathbf{SignO} $$.

Proof. This is because of the restriction [Equations (21) and (22)]. □

Claim 3

Proof. This is because of the perfect knowledge extraction of $$ \Pi $$ (see Definition 8). □

Combining Equations (23)-(28) we have:

as is claimed in Theorem 1. □

Theorem 2 (Unlinkability of Proofs). For any PPT algorithm $$ \mathbf{A} $$ that is in accordance with the experiment $$ {Exp}^{ {unlink-prf}}_{{dACS}, \mathbf{A}}{(1^\lambda, 1^\mu)} $$, there exists a PPT algorithm $$ \mathbf{D} $$ and the following inequality holds.

[For the definition of $$ \mathbf{Adv}^{ {ind-dual}}_{{Cmt}, \mathbf{D}}(\lambda) $$, see Definition 3.]

Theorem 2 means that, if the dual-mode commitment keys are indistinguishable, then our dACS has unlinkability.

Proof. Suppose that any PPT algorithm $$ \mathbf{A} $$ that is in accordance with the experiment $$ \textsf{Exp}^{ \text{unlink-prf}}_{\textsf{dACS}, \mathbf{A}}{(1^\lambda, 1^\mu)} $$ is given. We set a sequence of games, $$ \textsf{Game}_0 $$ and $$ \textsf{Game}_1 $$, as follows. $$ \textsf{Game}_0 $$ is exactly the same as $$ \textsf{Exp}^{ \text{unlink-prf}}_{\textsf{dACS}, \mathbf{A}}{(1^\lambda, 1^\mu)} $$. Note that when a set of public parameters $$ pp = ( pp', ck) $$ is given to $$ \mathbf{A} $$ where $$ pp' $$ is for bilinear groups, the commitment key $$ ck $$ is chosen as a commitment key $$ ck $$ of the mode $$ \texttt{nor} $$. We denote the probability that $$ \textsf{Game}_0 $$ returns $$ \text{Win} $$ as $$ \Pr[ \text{Win}_0] $$.

$$ \textsf{Game}_1 $$ is the same as $$ \textsf{Game}_0 $$ except that, when a set of public parameters $$ pp = ( pp', ck) $$ is given to $$ \mathbf{A} $$, the commitment key $$ ck $$ is chosen as a commitment key $$ ck $$ of the mode $$ \texttt{sim} $$. We denote the probability that $$ \textsf{Game}_1 $$ returns $$ \text{Win} $$ as $$ \Pr[ \text{Win}_1] $$. The values in $$ \textsf{Game}_1 $$ are distributed identically for both $$ \texttt{i}_0 $$ and $$ \texttt{i}_1 $$ due to the perfectly hiding property [Equation (16)] and the perfect witness-indistinguishability [Equation (17)]. Therefore, $$ \Pr[ \text{Win}_1] = 1/2 $$.

Employing $$ \mathbf{A} $$ as a subroutine, we construct a PPT distinguisher algorithm $$ \mathbf{D} $$ as follows. Given an input $$ pp, ck $$, $$ \mathbf{D} $$ reads out the security parameter. $$ \mathbf{D} $$ simulates the environment of $$ \mathbf{A} $$ in $$ \textsf{Game}_0 $$ or $$ \textsf{Game}_1 $$ honestly except that $$ \mathbf{D} $$ sets $$ pp := ( pp, ck) $$ instead of executing $$ \textsf{Setup}(1^{ \lambda}) $$. If $$ b = b' $$, then $$ \mathbf{D} $$ returns $$ 1 $$, and otherwise, $$ 0 $$. By Equations (13) and (14) (see Definition 3), $$ \Pr[ \mathbf{D}( pp, ck) = 1 \mid ck \gets \textsf{Cmt.KG}( \texttt{nor}) ] = \Pr[ \text{Win}_0] $$ and $$ \Pr[ \mathbf{D}( pp, ck) = 1 \mid ( ck, tk) \gets \textsf{Cmt.KG}( \texttt{sim}) ] = \Pr[ \text{Win}_1] $$, and

Therefore,

as is claimed in Theorem 2. □

Construction

According to our syntax, our instantiated scheme $$ \mathrm{dACS_{sxdh}} $$ consists of five PPT algorithms: $$ \textsf{dACS}_{ \text{sxdh}} = $$$$ ( \textsf{Setup}, $$$$ \textsf{AuthKG}, $$$$ \textsf{PrivKG}, $$$$ \textsf{Prover}, $$$$ \textsf{Verifier}) $$.

$$ \bullet \ \textsf{Setup}(1^{ \lambda}) \to pp $$. On input the security parameter $$ 1^{ \lambda} $$, it runs the generation algorithm of bilinear groups, and it sets the output as a set of public parameters: $$ \mathcal{BG}(1^{ \lambda}) \to (p, {\hat{\mathbb G}}, \check{{\mathbb G}}, \mathbb{T}, e, \hat{G}, \check{G}) =: pp $$. Note that $$ pp $$ is common for both the commit-and-prove scheme $$ \textsf{CmtPrv} $$ and the structure-preserving signature scheme $$ \textsf{Sig} $$. Besides, it runs the generation algorithm of a commitment key: $$ \textsf{Cmt.KG}( \texttt{nor}) \to ck $$. That is, it generates a CRS of mode $$ \texttt{nor} $$ for the Groth-Sahai NIZK proof system^[19] as Diffie-Hellman tuples, as follows. It first samples $$ \chi, \xi, \chi', \xi' \in_R \mathbb{Z}_p $$, and it computes $$ \hat{Q} :=\chi \hat{G}, \hat{U} :=\xi \hat{G}, \hat{V} :=\chi\xi \hat{G} $$, $$ \check{Q} :=\chi' \check{G}, \check{U} :=\xi' \check{G}, \check{V} :=\chi'\xi' \check{G} $$. Then it sets

and it sets

It returns $$ pp := ( pp, ck) $$.

$$ \bullet \ \textsf{AuthKG}(a) \to ( \text{PK}^{a}, \text{MSK}^{a}) $$. On input an authority index $$ a $$, it executes the key-generation algorithm of the structure-preserving signature scheme^[17], $$ \textsf{Sig.KG}(1^{ \lambda}) $$, to obtain $$ ( \text{PK}, \text{SK}) $$. Precisely, it generates a CRS of mode $$ \texttt{nor} $$ for the Groth-Sahai proof systems^[19]$$ \Pi_{ \textsf{Sig}, 0} $$ and $$ \Pi_{ \textsf{Sig}, 1} $$ as Diffie-Hellman tuples, as follows. (Note that the authority index $$ a $$ is omitted for simplicity). That is, for $$ i=0, 1 $$, it first samples $$ \chi_i, \xi_i, \chi'_i, \xi'_i \in_R \mathbb{Z}_p $$, and it computes $$ \hat{Q}_i :=\chi_i \hat{G}, \hat{U}_i :=\xi_i \hat{G}, \hat{V}_i :=\chi_i\xi_i \hat{G} $$, $$ \check{Q}_i :=\chi'_i \check{G}, \check{U}_i :=\xi'_i \check{G}, \check{V}_i :=\chi'_i\xi'_i \check{G} $$. Then it sets

Then it generates exponent values as

Then it generates the secret keys of the ElGamal encryption as

Then it generates commitments as

where $$ [\hat{ \textsf{x}}]_i $$ and $$ [ \check{ \textsf{y}}]_j $$ ($$ i=0, 1, \ j=0, 1 $$) are computed as follows.

Then it generates a basis of messages as

Finally, it sets

It sets $$ \text{PK}^{a} := \text{PK} $$ and $$ \text{MSK}^{a} := \text{SK} $$. It returns $$ ( \text{PK}^{a}, \text{MSK}^{a}) $$.

$$ \bullet \ \textsf{PrivKG}( \text{PK}^{a}, \text{MSK}^{a}, \texttt{i}) \to \text{sk}^{a}_{ \texttt{i}} $$. On input $$ \text{PK}^{a} $$, $$ \text{MSK}^{a} $$ and an element $$ \texttt{i} \in {\hat{\mathbb G}} $$, it sets $$ \text{PK} := \text{PK}^{a} $$ and $$ \text{SK} := \text{MSK}^{a} $$ and $$ m := \hat{M} := \texttt{i} $$. It executes the signing algorithm $$ \textsf{Sig.Sign}( \text{PK}, \text{SK}, m) $$ to obtain a signature $$ \sigma $$ on $$ \texttt{i} $$. Precisely, it generates a one-time key pair $$ \alpha \in_R \mathbb{Z}_p^* $$ and $$ \check{A}:= \alpha \hat{G} $$, and it generates a one-time signature $$ ( \hat{Z}, \hat{R}) $$ as

Then it encrypts $$ z_0=z_1:=x_0 $$ and $$ z_2:=0 $$ as

Then it generates commitments as

where $$ \hat{[z_2]}_1 $$, $$ \check{[z_0]}_0 $$, $$ \check{[z_0]}_1 $$ and $$ \check{[z_1]}_1 $$ are computed as follows.

Then it generates commitments as

Then it generates Groth-Sahai proofs as

where $$ \pi_{0, 0} $$, $$ \pi_{0, 1} $$, $$ \theta_{1, 0, 1} $$, $$ \theta_{1, 0, 2} $$, $$ \pi_{1, 0, 1} $$, $$ \pi_{1, 0, 2} $$, $$ \pi_{1, 1} $$, $$ \pi_{1, 2} $$ and $$ \pi_{1, 3} $$ are computed as follows.

Then it sets

It sets $$ \text{sk}^{a}_{ \texttt{i}} := \sigma $$. It returns $$ \text{sk}^{a}_{ \texttt{i}} $$.

$$ \bullet \ \textsf{Prover}(( \text{PK}^{a})^{a \in A'}, \texttt{i}, ( \text{sk}^{a}_{ \texttt{i}})^{a \in A'}) \to \pi $$. According to the previous work on the structure-preserving signatures^[17], verification equations are given as an equation system below. In the equation system, we denote $$ ( \hat{C}_{ \textsf{x}, 1}, \hat{C}_{ \textsf{x}, 2})_i = [\hat{ \textsf{x}}]_i $$ and $$ ( \check{D}_{ \textsf{y}, 1}, \check{D}_{ \textsf{y}, 2})_j = [ \check{ \textsf{y}}]_j $$ for a variable $$ \textsf{x}, \textsf{y} $$ and the indices $$ i, j $$. Also note that we put an index $$ {\ }^a $$ to distinguish each equation for $$ a \in A' $$, while the identity element $$ \hat{M} (= m = \texttt{i}) $$ is simultaneous for those equations.

We note that each of the Equations (50)-(56) can be transformed into the following canonical form.

Then the $$ \textsf{Prover} $$ algorithm applies the Groth-Sahai NIZK proof system to Equation (58), as follows. First, by using $$ \hat{\mathbf{crs}}_{ \Pi} $$ and $$ \check{\mathbf{crs}}_{ \Pi} $$, set

Also, set scalar vectors as

Then, generate commitments as follows.

We stress that, in the computation of the commitment $$ \hat{\mathit{\boldsymbol{c}}} $$ for the equation Equation (50), the randomness to compute the commitment $$ \hat{\mathit{\boldsymbol{c}}}_0 (\in {\hat{\mathbb G}}^{2 \times 1}) $$ to $$ \hat{M} (= \texttt{i}) $$ is common over all $$ a \in A' $$, and hence the randomness is sampled only once. This is why a single identity $$ \texttt{i}^* $$ is extracted in the security proof of unforgeability against collusion attacks.

Then, from Equations (58), (61) and (62), generate

Finally, obtain a Groth-Sahai proof $$ ( \check{\mathit{\boldsymbol{\pi}}}_{ \hat{v}}, \check{\mathit{\boldsymbol{\pi}}}_{ \hat{w}}, \hat{\mathit{\boldsymbol{\pi}}}_{ \check{v}}, \hat{\mathit{\boldsymbol{\pi}}}_{ \check{w}}) $$ by randomizing Equations (64) and (65), as follows.

To summarize, the $$ \textsf{Prover} $$ algorithm obtains Groth-Sahai proofs by computing $$ ( \hat{\mathit{\boldsymbol{c}}}, \check{\mathit{\boldsymbol{d}}}, \check{\mathit{\boldsymbol{\pi}}}_{ \hat{v}}, \check{\mathit{\boldsymbol{\pi}}}_{ \hat{w}}, \hat{\mathit{\boldsymbol{\pi}}}_{ \check{v}}, \hat{\mathit{\boldsymbol{\pi}}}_{ \check{w}}) $$ for each of the fifteen equations in Equations (50)-(56). We distinguish them by double index $$ (a, k) $$, where $$ a \in A' $$ and $$ k \in [15] $$. Then the algorithm returns all the commitments and proofs as $$ \mathit{\boldsymbol{\pi}} $$, but the commitment $$ \hat{\mathit{\boldsymbol{c}}}_0 $$ to $$ \texttt{i} (= \hat{M}) $$ is especially placed at the first entry. That is,

$$ \bullet \ \textsf{Verifier}(( \text{PK}^{a})^{a \in A'}, \pi) \to d $$. On input $$ ( ( \text{PK}^{a})^{a \in A'}, \mathit{\boldsymbol{\pi}}) $$, this verification algorithm does the checks the following evaluation.

Theorem 3 (EUF against Collusion Attacks) For any PPT algorithm $$ \mathbf{A} $$ that is in accordance with the experiment $$ sf{Exp}^{ {euf-coll}}_{sf{dACS}, \mathbf{A}}{(1^\lambda, 1^\mu)} $$, our instantiated $$ {dACS_{sxdh}} $$ is EUF against collusion attacks under the SXDH assumption.

Theorem 4 (Unlinkability of Proofs) For any PPT algorithm $$ \mathbf{A} $$ that is in accordance with the experiment $$ sf{Exp}^{ {unlink-prf}}_{sf{dACS}, \mathbf{A}}{(1^\lambda, 1^\mu)} $$, our instantiated $$ {dACS_{sxdh}} $$ is unlinkable under the SXDH assumption.

Acknowledgments

The author would like to express his sincere thanks to the three anonymous reviewers as well as the associated editor for their helpful comments from their technical and editorial viewpoints. Part of this work was presented at Innovative Security Solutions for Information Technology and Communications - 13th International Conference, SecITC 2020 (Bucharest, Romania, November 19-20, 2020, pp.71-90)^[34], and the sole author agrees to submit and publish it in this new article.

Authors' contributions

The author contributed solely to the article.

Availability of data and materials

Not applicable.

Financial support and sponsorship

This work was supported by JSPS KAKENHI Grant Number JP23K11106.

Conflicts of interest

The author declared that there are no conflicts of interest.

Ethical approval and consent to participate

Not applicable.

Consent for publication

Not applicable.

Copyright

© The Author (s) 2024.