# A Hybrid Design of Linkable Ring Signature Scheme with Stealth Addresses

Authors: Weizhou Li; Zhiqiang Lin; Qi Chen
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Blockchain is a transformational technology which affects finance, Internet, and politics. However, many privacy protection problems for blockchain are waiting to be solved. In this study, we propose a novel linkable ring signature scheme with stealth addresses, which enables the payer and payee of the transaction to be anonymous and unlinkable in the cryptocurrency. The scheme is combined with an elliptic curve discrete logarithm (ECD logarithm)-based key encapsulation mechanism (KEM) stage and a lattice-based signature stage. The master public key and master secret key are much smaller compared with the previous scheme. Complete secure proof of the scheme is also presented in this study.


---

## Body

## 1. Introduction

### 1.1. Background

As a novel technology, blockchain technology has been widely used in many fields since its introduction in [1–6]. The development of blockchain is also inseparable from digital signatures. Digital signature provides security and authentication for information during the process of information dissemination, such as protecting user’s privacy and preventing double spending with the support of the anonymity and linkability of the ring signature scheme [7, 8].In [9], the authors proposed a linkable ring signature scheme with stealth addresses denoted by SALRS. This scheme enables the payer and payee of the transaction to be anonymous and unlinkable in the cryptocurrency. Specifically, the linkable ring signature and stealth address [10–12] are employed in CryptoNote [10]. When a payer A wants to pay a payee B through a transaction, the payer B uses a stealth address to generate a derived public key. Then, the payer A uses the derived public key as the address of the payee B. Also, transactions cannot be identified because of the absence of the master public key. When the payee B, as a payer in transaction, wants to spend his coins on the derived public key, he generates a linkable ring signature with the support of a set of derived public keys. In order to verify the linkable ring signature, it is not necessary for anyone to find out that the actual signer is corresponding to the derived public key. When it comes to the linkability which can prevent double spending in a transaction, if two signatures are generated by the payee B corresponding to a derived public key, they will be detected as linked because the coin corresponding to the derived public key can be used only once. In this study, we focus on concrete construction of the SALRS scheme in order to enable both payer and payee of a transaction to be hidden in the cryptocurrency.


### 1.2. Our Contribution

We propose a novel concrete linkable ring signature scheme with stealth addresses based on the elliptic curve discrete logarithm (ECD logarithm) for the key encapsulation mechanism (KEM) stage and lattice for signature stage. The ECD-based KEM provides smaller keys. In particular, the size of the master public key is 510 bits, and the size of the master secret key is 512 bits, which is much smaller than the ones in the previous scheme in [9]. Moreover, all the secure properties which a SALRS should have, including unforgeability, linkability, nonslanderability, anonymity, master-public-key-unlinkability, and derived-public-key-unlinkability, still keep.


### 1.3. Organization of This Paper

The rest of the study is organized as follows. Preliminaries are given in Section2. In Section 3, we formally propose the SALRS scheme. Afterwards, the security models of the SALRS scheme are presented in Section 4. As a vital content of this study, in Section 5, our concrete SALRS scheme is showed. In Section 6, we analyze and prove the security of our SALRS scheme. Moreover, efficiency analysis, especially less storage cost of our SALRS scheme, is introduced in Section 7. Finally, we summarize this study and come out conclusions in Section 8.


### 1.4. Related Work

There are a lot of classic linkable ring signature schemes relied on the hardness number-theoretic problems, such as [13, 14]. Many of them have specific application scenarios, for example, [15, 16] are based on certificates and identity-based, respectively. However, a lot of cryptographic schemes based on classical number theories are suffered from future quantum computer’s threats [17]. All the same, some advantages of cryptographic schemes relying on classical number theory, for example, the elliptic curve discrete logarithm [18], are faster calculation and less storage cost.Lattice-based ring signatures were first introduced by Brakerski and Tauman-Kalai in 2010. They proposed a construction of ring signature scheme based on SIS assumption. Then, in 2013, Melchor et al. proposed a ring signature scheme based on LWE assumption. Until now, many lattice-based ring signature schemes have been proposed, such as [19–21].The existing works on the linkable ring signature and stealth address have been proposed, e.g., [8, 22]. However, most of the existing works above either merely consider linkable ring signature or stealth address rather than both of them. Fortunately, literature [9] has successfully proposed a new cryptographic primitive denoted by SALRS. The new cryptographic primitive has not only combined the linkable ring signature with the stealth address but also captured adversarially chosen key attacks in the linkability model. Additionally, it is also potentially quantum resistant.


## 1.1. Background

As a novel technology, blockchain technology has been widely used in many fields since its introduction in [1–6]. The development of blockchain is also inseparable from digital signatures. Digital signature provides security and authentication for information during the process of information dissemination, such as protecting user’s privacy and preventing double spending with the support of the anonymity and linkability of the ring signature scheme [7, 8].In [9], the authors proposed a linkable ring signature scheme with stealth addresses denoted by SALRS. This scheme enables the payer and payee of the transaction to be anonymous and unlinkable in the cryptocurrency. Specifically, the linkable ring signature and stealth address [10–12] are employed in CryptoNote [10]. When a payer A wants to pay a payee B through a transaction, the payer B uses a stealth address to generate a derived public key. Then, the payer A uses the derived public key as the address of the payee B. Also, transactions cannot be identified because of the absence of the master public key. When the payee B, as a payer in transaction, wants to spend his coins on the derived public key, he generates a linkable ring signature with the support of a set of derived public keys. In order to verify the linkable ring signature, it is not necessary for anyone to find out that the actual signer is corresponding to the derived public key. When it comes to the linkability which can prevent double spending in a transaction, if two signatures are generated by the payee B corresponding to a derived public key, they will be detected as linked because the coin corresponding to the derived public key can be used only once. In this study, we focus on concrete construction of the SALRS scheme in order to enable both payer and payee of a transaction to be hidden in the cryptocurrency.


## 1.2. Our Contribution

We propose a novel concrete linkable ring signature scheme with stealth addresses based on the elliptic curve discrete logarithm (ECD logarithm) for the key encapsulation mechanism (KEM) stage and lattice for signature stage. The ECD-based KEM provides smaller keys. In particular, the size of the master public key is 510 bits, and the size of the master secret key is 512 bits, which is much smaller than the ones in the previous scheme in [9]. Moreover, all the secure properties which a SALRS should have, including unforgeability, linkability, nonslanderability, anonymity, master-public-key-unlinkability, and derived-public-key-unlinkability, still keep.


## 1.3. Organization of This Paper

The rest of the study is organized as follows. Preliminaries are given in Section2. In Section 3, we formally propose the SALRS scheme. Afterwards, the security models of the SALRS scheme are presented in Section 4. As a vital content of this study, in Section 5, our concrete SALRS scheme is showed. In Section 6, we analyze and prove the security of our SALRS scheme. Moreover, efficiency analysis, especially less storage cost of our SALRS scheme, is introduced in Section 7. Finally, we summarize this study and come out conclusions in Section 8.


## 1.4. Related Work

There are a lot of classic linkable ring signature schemes relied on the hardness number-theoretic problems, such as [13, 14]. Many of them have specific application scenarios, for example, [15, 16] are based on certificates and identity-based, respectively. However, a lot of cryptographic schemes based on classical number theories are suffered from future quantum computer’s threats [17]. All the same, some advantages of cryptographic schemes relying on classical number theory, for example, the elliptic curve discrete logarithm [18], are faster calculation and less storage cost.Lattice-based ring signatures were first introduced by Brakerski and Tauman-Kalai in 2010. They proposed a construction of ring signature scheme based on SIS assumption. Then, in 2013, Melchor et al. proposed a ring signature scheme based on LWE assumption. Until now, many lattice-based ring signature schemes have been proposed, such as [19–21].The existing works on the linkable ring signature and stealth address have been proposed, e.g., [8, 22]. However, most of the existing works above either merely consider linkable ring signature or stealth address rather than both of them. Fortunately, literature [9] has successfully proposed a new cryptographic primitive denoted by SALRS. The new cryptographic primitive has not only combined the linkable ring signature with the stealth address but also captured adversarially chosen key attacks in the linkability model. Additionally, it is also potentially quantum resistant.


## 2. Preliminaries

In this section, before showing our concrete SALRS construction, we give some preliminary results about the mathematical background concerning bilinear maps and lattice and complexity assumptions. For more details, please refer to [23–26].


### 2.1. Mathematical Background

LetG1, G2, and GT be the groups of prime order p, and gi be a generator of Gi (i = 1,2). Set G1≠G2, and there exists no efficient homomorphism between G1 and G2. We say that e: G1×G2⟶GT is a bilinear, efficient, and computable map if it satisfies the following two properties.(1)
Bilinear: for∀a,b∈ℤp, where the integers modulo p is denoted by ℤp, we have e(g1a, g1b) = eg1,g2ab.(2)
Efficient:e(g1, g2) ≠ 1.Letq and n be two positive integers, and denote the integers modulo q by ℤq, which will be represented in the range (-q/2,q/2] or [-q−1/2,q−1/2], where q is even or odd, respectively. Let R and Rq be the rings ℤ [X]/(Xn +1) and ℤq [X]/(Xn +1), respectively. We set r = a0 + a1X + … + an−1Xn−1∈ R and r = (r1,…rk) ∈Rk to define the l1, l2, and l∞ norms of r and r as follows:(1)
r∞≜maxiai(2)
r1≜∑iai(3)
r2≜a02+⋯+an−12(4)
r∞≜maxiri∞(5)
r1≜∑ir1(6)
r2≜r122+⋯+rk22We also denote two sets:(1)
SSη≜\r∈R|r∞≤\\{r∈R|‖r‖∞≤η\}(2)
Bθ≜\{r∈, Rq|r has θ coefficients that are ±1 and the rest are 0\}


### 2.2. Complexity Assumptions

The security of our novel SALRS scheme is based on bilinear Diffie-Hellman 1 assumption, module-SIS assumption, and module-LWE assumption.


#### 2.2.1. Bilinear Diffie-Hellman 1 (BDH-1) Assumption

LetG1, G2, and GT be groups of prime order p, and gi be a generator of Gi (i = 1,2). Set G1≠G2, and there exists no efficient homomorphism between G1 and G2. e: G1×G2⟶GT is a bilinear, efficient, and computable map. The Bilinear Diffie-Hellman 1 (BDH-1) problem is that given g1, g2, g1a, g1b, compute e(g1, g2), where a, b∈ℤp.


#### 2.2.2. Module-SIS Assumption

The module-SIS problem with parameters (n, q, k, l, β) is that for uniformly random A∈Rqk×l, t∈, Rqk, and k × k identity matrix I, find x∈, Rk+l, such that ‖x‖2≤β and [A|I]⋅x = t. The problem can be adapted into the infinity-norm version, where ‖x‖∞≤β. Additionally, the homogeneous version of the module-SIS problem is defined with t = 0 and x ≠ 0.


#### 2.2.3. Module-LWE Assumption

The module-LWE problem with parameters (n, q, k, l, η) is that for uniformly random A∈Rqk×l, let b = As + e∈Rqk, where s ∈ Sηl, e ∈ Sηk have their entries selected concerning some distributions (uniform distribution, Gaussian distribution) over Sη. There are two versions about module-LWE. The search variant of module-LWE is to find s given (A, b). The decision variant is to distinguish (A, b) from a uniformly random pair over Rqk×l×, Rqk. In this study, we use a transformed version of the decision variant of module-LWE, which is to distinguish (A, As) from (A, r), where A←, Rqk×l, s←, Sηl, and r←, Rqk.


## 2.1. Mathematical Background

LetG1, G2, and GT be the groups of prime order p, and gi be a generator of Gi (i = 1,2). Set G1≠G2, and there exists no efficient homomorphism between G1 and G2. We say that e: G1×G2⟶GT is a bilinear, efficient, and computable map if it satisfies the following two properties.(1)
Bilinear: for∀a,b∈ℤp, where the integers modulo p is denoted by ℤp, we have e(g1a, g1b) = eg1,g2ab.(2)
Efficient:e(g1, g2) ≠ 1.Letq and n be two positive integers, and denote the integers modulo q by ℤq, which will be represented in the range (-q/2,q/2] or [-q−1/2,q−1/2], where q is even or odd, respectively. Let R and Rq be the rings ℤ [X]/(Xn +1) and ℤq [X]/(Xn +1), respectively. We set r = a0 + a1X + … + an−1Xn−1∈ R and r = (r1,…rk) ∈Rk to define the l1, l2, and l∞ norms of r and r as follows:(1)
r∞≜maxiai(2)
r1≜∑iai(3)
r2≜a02+⋯+an−12(4)
r∞≜maxiri∞(5)
r1≜∑ir1(6)
r2≜r122+⋯+rk22We also denote two sets:(1)
SSη≜\r∈R|r∞≤\\{r∈R|‖r‖∞≤η\}(2)
Bθ≜\{r∈, Rq|r has θ coefficients that are ±1 and the rest are 0\}


## 2.2. Complexity Assumptions

The security of our novel SALRS scheme is based on bilinear Diffie-Hellman 1 assumption, module-SIS assumption, and module-LWE assumption.


### 2.2.1. Bilinear Diffie-Hellman 1 (BDH-1) Assumption

LetG1, G2, and GT be groups of prime order p, and gi be a generator of Gi (i = 1,2). Set G1≠G2, and there exists no efficient homomorphism between G1 and G2. e: G1×G2⟶GT is a bilinear, efficient, and computable map. The Bilinear Diffie-Hellman 1 (BDH-1) problem is that given g1, g2, g1a, g1b, compute e(g1, g2), where a, b∈ℤp.


### 2.2.2. Module-SIS Assumption

The module-SIS problem with parameters (n, q, k, l, β) is that for uniformly random A∈Rqk×l, t∈, Rqk, and k × k identity matrix I, find x∈, Rk+l, such that ‖x‖2≤β and [A|I]⋅x = t. The problem can be adapted into the infinity-norm version, where ‖x‖∞≤β. Additionally, the homogeneous version of the module-SIS problem is defined with t = 0 and x ≠ 0.


### 2.2.3. Module-LWE Assumption

The module-LWE problem with parameters (n, q, k, l, η) is that for uniformly random A∈Rqk×l, let b = As + e∈Rqk, where s ∈ Sηl, e ∈ Sηk have their entries selected concerning some distributions (uniform distribution, Gaussian distribution) over Sη. There are two versions about module-LWE. The search variant of module-LWE is to find s given (A, b). The decision variant is to distinguish (A, b) from a uniformly random pair over Rqk×l×, Rqk. In this study, we use a transformed version of the decision variant of module-LWE, which is to distinguish (A, As) from (A, r), where A←, Rqk×l, s←, Sηl, and r←, Rqk.


## 2.2.1. Bilinear Diffie-Hellman 1 (BDH-1) Assumption

LetG1, G2, and GT be groups of prime order p, and gi be a generator of Gi (i = 1,2). Set G1≠G2, and there exists no efficient homomorphism between G1 and G2. e: G1×G2⟶GT is a bilinear, efficient, and computable map. The Bilinear Diffie-Hellman 1 (BDH-1) problem is that given g1, g2, g1a, g1b, compute e(g1, g2), where a, b∈ℤp.


## 2.2.2. Module-SIS Assumption

The module-SIS problem with parameters (n, q, k, l, β) is that for uniformly random A∈Rqk×l, t∈, Rqk, and k × k identity matrix I, find x∈, Rk+l, such that ‖x‖2≤β and [A|I]⋅x = t. The problem can be adapted into the infinity-norm version, where ‖x‖∞≤β. Additionally, the homogeneous version of the module-SIS problem is defined with t = 0 and x ≠ 0.


## 2.2.3. Module-LWE Assumption

The module-LWE problem with parameters (n, q, k, l, η) is that for uniformly random A∈Rqk×l, let b = As + e∈Rqk, where s ∈ Sηl, e ∈ Sηk have their entries selected concerning some distributions (uniform distribution, Gaussian distribution) over Sη. There are two versions about module-LWE. The search variant of module-LWE is to find s given (A, b). The decision variant is to distinguish (A, b) from a uniformly random pair over Rqk×l×, Rqk. In this study, we use a transformed version of the decision variant of module-LWE, which is to distinguish (A, As) from (A, r), where A←, Rqk×l, s←, Sηl, and r←, Rqk.


## 3. SALRS Scheme

The syntax of linkable ring signature scheme with stealth addresses (SALRS) was first purposed by [9], which realizes the cryptographic functions that a cryptocurrency wants to hide payers and payees of transactions. There are eight algorithms in a SALRS scheme.Setupλ⟶ PP: the input to this algorithm is a security parameter λ and outputs the public parameters PP.MasterKeyGen (PP)⟶ (MPK, MSK): the input to this algorithm is the public parameters (PP) and outputs the user’s master key pair (MPK, MSK) (master public key, master secret key).DerivedPublicKeyGen (MPK)⟶ DPK: the input to this algorithm is a master public key (MPK) and outputs the derived public key (DPK).DerivedPublicKeyOwnerCheck (DPK, MPK, MSK)⟶ 1/0: the input to this algorithm is a derived public key (DPK) and a master key pair (MPK, MSK) and outputs b∈\{0,1\}. 1 and 0 indicate that the derived public key (DPK) is valid or invalid, respectively.DerivedPublicKeyPublicCheck (DPK)⟶ 1/0: the input to this algorithm is a derived public key (DPK) and outputs b∈\{0,1\}. 1 and 0 indicate that the derived public key (DPK) is well-formed or not well-formed, respectively.Sign (M, R, DPK, MPK, MSK) ⟶σ: the input to this algorithm is a message M, a ring of well-formed derived public keys R =  DPK1,…,DPKr (where we regard the public key ring R as an order set, namely, it consists of the public keys which are ordered and have indexes), a derived public key DPK ∈R, and a master key pair (MPK, MSK) for the derived public key (DPK) and outputs a signature σ.Verify(M, R, σ) ⟶ 1/0: the input to this algorithm is a message M, a ring of well-formed derived public keys R, and a signature σ and outputs b∈\{0,1\}. 1 and 0 indicate that the signature σ is valid or invalid, respectively.Link (M0, R0, σ0, M1, R1, σ1) ⟶ 1/0: the input to this algorithm is two valid (message M, derived public key ring R, signature σ) tuples (M0, R0, σ0) and (M1, R1, σ1) and outputs 0 or 1. 1 and 0 indicate that the two signatures are linked or unlinked, respectively.


## 4. Security Model of SALRS

A SALRS scheme should be correctness, unforgeable, linkable, nonslanderable, anonymous, master-public-key-unlinkable, and derived-public-key-unlinkable, which ensure the scheme satisfying the security and privacy protection requirements of cryptocurrencies in most practical settings.In the following games, we useA or n() to denote any probabilistic polynomial time (PPT) adversary or polynomial, respectively.


### 4.1. Correctness

Correctness means that one can derive a “right” feedback while honestly performing the protocols.Let PP← setup λ,(1)
For any (MPK, MSK)←MasterKeyGen (PP) and any DPK ←DerivedPublicKeyGen (MPK), we have DerivedPublicKeyOwnerCheck (DPK, MPK, MSK) = 1 and DerivedPublicKeyPublicCheck (DPK) = 1.(2)
For any messageM, any ring of well-formed derived public keys R, and any derived public key DPK ∈R, such that DerivedPublicKeyOwnerCheck (DPK, MPK, MSK) = 1 for some master key pair (MPK, MSK), we have verify (M, R, sign (M, R, DPK, MPK, MSK)) = 1.(3)
For any messageMi, any ring of well-formed derived public keys Ri, and any derived public key DPKi∈, Ri, such that DerivedPublicKeyOwnerCheck (DPKi, MPKi, MSKi) = 1 for some master key pair (MPKi, MSKi), let σi← sign (Mi, Ri, DPKi, MPKi, MSKi) (i = 0,1). We have link (M0, R0, σ0, M1, R1, σ1) = 1 if DPK0  =  DPK1, and Pr[link (M0, R0, σ0, M1, R1, σ1) = 0] ≥ 1 − neglλ if DPK0≠DPK1, where negl is a negligible function.


### 4.2. Unforgeability

Unforgeability means that only the user who knows the secret key for some public key in a ring can generate a valid signature.


#### 4.2.1. Setup

PP← setup λ is run. PP is given to A. \MPKi,MSKi←MasterKeyGenPP\i=1nλ are run and MPKi are given to A.


#### 4.2.2. Probing Phase

A can query the following oracles:(1)
Derived Public Key Adding Oracle, ODPKAdd(): it means that ODPKAdd (DPK, MPK) returnsb← DerivedPublicKeyOwnerCheck (DPK, MPK, MSK) to A. If b = 1, set Ldpk =  Ldpk∪\{DPK\}, where Ldpk  =  ∅ is initialized.(2)
Signing Oracle, OSign(): it means that OSign (M, R, DPK), where DPK∈R∩, Ldpk, returns σ← sign (M, R, DPK, MPK, MSK) to A, where (MPK, MSK) is the master key pair for DPK.


#### 4.2.3. Output Phase

A outputs a message M∗, a ring of well-formed derived public keys R∗, and a signature σ∗.LetSso  = \{(M, R, DPK, σ)\} be the query-answer tuples for OSign. A succeeds if(1)
Verify (M∗, R∗, σ∗) = 1 and(2)
R∗⊆Ldpk and(3)
(M∗, R∗, ?, σ∗) ∉Sso, where ? means that (M∗, R∗, σ∗) is not a tuple obtained by querying OSign.Definition 1.
The SALRS is unforgeable if for allA, AdvAuf is negligible, where AdvAuf  = Pr[A succeeds]. We name the game for unforgeability Gameuf.


### 4.3. Linkability

Linkability means that if the key owner generates two or multiple valid signatures with respect to one derived public key, the signatures will be found to be linked.


#### 4.3.1. Setup

PP← setup λ is run. PP is given to A.


#### 4.3.2. Output Phase

A outputs k (k≥ (2) tuples (Mi∗, Ri∗, σi∗) (i = 1,…,k).A succeeds if(1)
Verify (Mi∗, Ri∗, σi∗) = 1 and(2)
Link (Mi∗, Ri∗, σi∗, Mj∗, Rj∗, σj∗) = 0(∀i, j ∈ [1,k], s.t. i ≠ j) and(3)
∪i=1kR1∗<k.Definition 2.
The SALRS is linkable if for allA, AdvAlink is negligible, where AdvAlink  = Pr[A succeeds]. We name the game for linkability Game link.


### 4.4. Nonslanderability

Nonslanderability means that no one can frame other users by creating a signature which is linked to a signature of the target user.


#### 4.4.1. Setup

Same as that ofGameuf.


#### 4.4.2. Probing Phase

Same as that ofGameuf.


#### 4.4.3. Output Phase

A outputs two tuples (M′, R′, σ′) and (M∗, R∗, σ∗).LetSso = \{(M, R, DPK, σ)\} be the query-answer tuples for OSign. A succeeds if(1)
Verify (M∗, R∗, σ∗) = 1 and(2)
(M′, R′, σ′) ∈Sso for some derived public keys DPK′∈R′, ∩Ldpk and(3)
(M∗, R∗, DPK′, σ∗) ∉Sso and(4)
Link (M∗, R∗, σ∗, M′, R′, σ′) = 1Definition 3.
The SALRS is nonslanderable if for allA, AdvAns is negligible, where AdvAns  = Pr[A succeeds]. We name the game for nonslanderability Gamens.


### 4.5. Anonymity

Anonymity means that no one can identify the signer’s derived public key out of the ring, with a valid signature with respect to a ring of derived public keys.


#### 4.5.1. Setup

Same as that ofGameuf.


#### 4.5.2. Probing Phase 1

Same as the probing phase ofGameuf.


#### 4.5.3. Challenge Phase

A outputs a message M∗, a ring of well-formed derived public keys R∗, and two distinct indices 1 ≤i0, i1≤nλ, such that(1)
DPKi0, DPKi1∈R∗∩Ldpk(2)
None of OSign withDPKi0 and DPKi1 was queried.A random bitb∈\{0,1\} is chosen, and A is given the σ← sign (M∗, R∗, DPKib, MPK, MSK), where (MPK, MSK) is the master key pair for DPKib.


#### 4.5.4. Probing Phase 2

Same as the probing phase 1, but with the restriction that OSign withDPKi0 and DPKi1 cannot be queried.


#### 4.5.5. Output Phase

A outputs a bit b′ as its guess to b.Definition 4.
The SALRS is anonymous if for allA, AdvAano is negligible, where AdvAano  = Prb=b−1/2 . We name the game for anonymity Gameano.


### 4.6. Master-Public-Key-Unlinkability

Master-public-key-unlinkability means that with the support of a derived public key and the corresponding signatures, no one can distinguish which master public key is the one which it was derived from.


#### 4.6.1. Setup

Same as that ofGameuf.


#### 4.6.2. Probing Phase 1

Same as the probing phase ofGameuf.


#### 4.6.3. Challenge

A outputs two distinct indices 1 ≤i0, i1≤nλ. A random bit b∈\{0,1\} is chosen, and DPK∗←DerivedPublicKeyGenMPKib is given to A. Set Ldpk = Ldpk∪, DPK∗\}.


#### 4.6.4. Probing Phase 2

Same as the probing phase 1, with the restriction that ODPKAdd (DPK∗, MPKij) (j∈\{0,1\}) cannot be queried.


#### 4.6.5. Output Phase

A outputs a bit b′∈\{0,1\} as its guess to b.Definition 5.
The SALRS is master-public-key-unlinkable if for allA, AdvAmpkunl is negligible, where AdvAmpkunl = Prb=b−1/2 . We name the game for master-public-key-unlinkability Gamempkunl.


### 4.7. Derived-Public-Key-Unlinkability

Derived-public-key-unlinkability means that with the support of two derived public keys and the corresponding signatures, no one can figure out whether they are derived from the same master public key.


#### 4.7.1. Setup

Same as that ofGameuf.


#### 4.7.2. Probing Phase 1

Same as the probing phase ofGameuf.


#### 4.7.3. Challenge

A outputs two distinct indices 1 ≤i0,i1≤nλ. A random bit c∈\{0,1\} is chosen. Compute DPK0∗←DerivedPublicKeyGenMPKic.A random bitb∈\{0,1\} is chosen. If b = 0, compute DPK1∗←DerivedPublicKeyGenMPKic; otherwise, compute DPK1∗←DerivedPublicKeyGenMPKi1−c. (DPK0∗, DPK1∗) are given to A. Set Ldpk  = Ldpk, ∪\{DPK0∗, DPK1∗\}.


#### 4.7.4. Probing Phase 2

Same as the probing phase 1, with the restriction that ODPKAdd (DPKj∗, MPKik) (j, k∈\{0,1\}) can only be queried on at most one j∈ \{0,1\}.


#### 4.7.5. Output Phase

A outputs a bit b′, ∈\{0,1\} as its guess to b.Definition 6.
The SALRS is derived-public-key-unlinkable, if for allA, AdvAdpkunl is negligible, where AdvAdpkunl = Prb=b−1/2. We name the game for derived-public-key-unlinkability Gamedpkunl.


## 4.1. Correctness

Correctness means that one can derive a “right” feedback while honestly performing the protocols.Let PP← setup λ,(1)
For any (MPK, MSK)←MasterKeyGen (PP) and any DPK ←DerivedPublicKeyGen (MPK), we have DerivedPublicKeyOwnerCheck (DPK, MPK, MSK) = 1 and DerivedPublicKeyPublicCheck (DPK) = 1.(2)
For any messageM, any ring of well-formed derived public keys R, and any derived public key DPK ∈R, such that DerivedPublicKeyOwnerCheck (DPK, MPK, MSK) = 1 for some master key pair (MPK, MSK), we have verify (M, R, sign (M, R, DPK, MPK, MSK)) = 1.(3)
For any messageMi, any ring of well-formed derived public keys Ri, and any derived public key DPKi∈, Ri, such that DerivedPublicKeyOwnerCheck (DPKi, MPKi, MSKi) = 1 for some master key pair (MPKi, MSKi), let σi← sign (Mi, Ri, DPKi, MPKi, MSKi) (i = 0,1). We have link (M0, R0, σ0, M1, R1, σ1) = 1 if DPK0  =  DPK1, and Pr[link (M0, R0, σ0, M1, R1, σ1) = 0] ≥ 1 − neglλ if DPK0≠DPK1, where negl is a negligible function.


## 4.2. Unforgeability

Unforgeability means that only the user who knows the secret key for some public key in a ring can generate a valid signature.


### 4.2.1. Setup

PP← setup λ is run. PP is given to A. \MPKi,MSKi←MasterKeyGenPP\i=1nλ are run and MPKi are given to A.


### 4.2.2. Probing Phase

A can query the following oracles:(1)
Derived Public Key Adding Oracle, ODPKAdd(): it means that ODPKAdd (DPK, MPK) returnsb← DerivedPublicKeyOwnerCheck (DPK, MPK, MSK) to A. If b = 1, set Ldpk =  Ldpk∪\{DPK\}, where Ldpk  =  ∅ is initialized.(2)
Signing Oracle, OSign(): it means that OSign (M, R, DPK), where DPK∈R∩, Ldpk, returns σ← sign (M, R, DPK, MPK, MSK) to A, where (MPK, MSK) is the master key pair for DPK.


### 4.2.3. Output Phase

A outputs a message M∗, a ring of well-formed derived public keys R∗, and a signature σ∗.LetSso  = \{(M, R, DPK, σ)\} be the query-answer tuples for OSign. A succeeds if(1)
Verify (M∗, R∗, σ∗) = 1 and(2)
R∗⊆Ldpk and(3)
(M∗, R∗, ?, σ∗) ∉Sso, where ? means that (M∗, R∗, σ∗) is not a tuple obtained by querying OSign.Definition 1.
The SALRS is unforgeable if for allA, AdvAuf is negligible, where AdvAuf  = Pr[A succeeds]. We name the game for unforgeability Gameuf.


## 4.2.1. Setup

PP← setup λ is run. PP is given to A. \MPKi,MSKi←MasterKeyGenPP\i=1nλ are run and MPKi are given to A.


## 4.2.2. Probing Phase

A can query the following oracles:(1)
Derived Public Key Adding Oracle, ODPKAdd(): it means that ODPKAdd (DPK, MPK) returnsb← DerivedPublicKeyOwnerCheck (DPK, MPK, MSK) to A. If b = 1, set Ldpk =  Ldpk∪\{DPK\}, where Ldpk  =  ∅ is initialized.(2)
Signing Oracle, OSign(): it means that OSign (M, R, DPK), where DPK∈R∩, Ldpk, returns σ← sign (M, R, DPK, MPK, MSK) to A, where (MPK, MSK) is the master key pair for DPK.


## 4.2.3. Output Phase

A outputs a message M∗, a ring of well-formed derived public keys R∗, and a signature σ∗.LetSso  = \{(M, R, DPK, σ)\} be the query-answer tuples for OSign. A succeeds if(1)
Verify (M∗, R∗, σ∗) = 1 and(2)
R∗⊆Ldpk and(3)
(M∗, R∗, ?, σ∗) ∉Sso, where ? means that (M∗, R∗, σ∗) is not a tuple obtained by querying OSign.Definition 1.
The SALRS is unforgeable if for allA, AdvAuf is negligible, where AdvAuf  = Pr[A succeeds]. We name the game for unforgeability Gameuf.


## 4.3. Linkability

Linkability means that if the key owner generates two or multiple valid signatures with respect to one derived public key, the signatures will be found to be linked.


### 4.3.1. Setup

PP← setup λ is run. PP is given to A.


### 4.3.2. Output Phase

A outputs k (k≥ (2) tuples (Mi∗, Ri∗, σi∗) (i = 1,…,k).A succeeds if(1)
Verify (Mi∗, Ri∗, σi∗) = 1 and(2)
Link (Mi∗, Ri∗, σi∗, Mj∗, Rj∗, σj∗) = 0(∀i, j ∈ [1,k], s.t. i ≠ j) and(3)
∪i=1kR1∗<k.Definition 2.
The SALRS is linkable if for allA, AdvAlink is negligible, where AdvAlink  = Pr[A succeeds]. We name the game for linkability Game link.


## 4.3.1. Setup

PP← setup λ is run. PP is given to A.


## 4.3.2. Output Phase

A outputs k (k≥ (2) tuples (Mi∗, Ri∗, σi∗) (i = 1,…,k).A succeeds if(1)
Verify (Mi∗, Ri∗, σi∗) = 1 and(2)
Link (Mi∗, Ri∗, σi∗, Mj∗, Rj∗, σj∗) = 0(∀i, j ∈ [1,k], s.t. i ≠ j) and(3)
∪i=1kR1∗<k.Definition 2.
The SALRS is linkable if for allA, AdvAlink is negligible, where AdvAlink  = Pr[A succeeds]. We name the game for linkability Game link.


## 4.4. Nonslanderability

Nonslanderability means that no one can frame other users by creating a signature which is linked to a signature of the target user.


### 4.4.1. Setup

Same as that ofGameuf.


### 4.4.2. Probing Phase

Same as that ofGameuf.


### 4.4.3. Output Phase

A outputs two tuples (M′, R′, σ′) and (M∗, R∗, σ∗).LetSso = \{(M, R, DPK, σ)\} be the query-answer tuples for OSign. A succeeds if(1)
Verify (M∗, R∗, σ∗) = 1 and(2)
(M′, R′, σ′) ∈Sso for some derived public keys DPK′∈R′, ∩Ldpk and(3)
(M∗, R∗, DPK′, σ∗) ∉Sso and(4)
Link (M∗, R∗, σ∗, M′, R′, σ′) = 1Definition 3.
The SALRS is nonslanderable if for allA, AdvAns is negligible, where AdvAns  = Pr[A succeeds]. We name the game for nonslanderability Gamens.


## 4.4.1. Setup

Same as that ofGameuf.


## 4.4.2. Probing Phase

Same as that ofGameuf.


## 4.4.3. Output Phase

A outputs two tuples (M′, R′, σ′) and (M∗, R∗, σ∗).LetSso = \{(M, R, DPK, σ)\} be the query-answer tuples for OSign. A succeeds if(1)
Verify (M∗, R∗, σ∗) = 1 and(2)
(M′, R′, σ′) ∈Sso for some derived public keys DPK′∈R′, ∩Ldpk and(3)
(M∗, R∗, DPK′, σ∗) ∉Sso and(4)
Link (M∗, R∗, σ∗, M′, R′, σ′) = 1Definition 3.
The SALRS is nonslanderable if for allA, AdvAns is negligible, where AdvAns  = Pr[A succeeds]. We name the game for nonslanderability Gamens.


## 4.5. Anonymity

Anonymity means that no one can identify the signer’s derived public key out of the ring, with a valid signature with respect to a ring of derived public keys.


### 4.5.1. Setup

Same as that ofGameuf.


### 4.5.2. Probing Phase 1

Same as the probing phase ofGameuf.


### 4.5.3. Challenge Phase

A outputs a message M∗, a ring of well-formed derived public keys R∗, and two distinct indices 1 ≤i0, i1≤nλ, such that(1)
DPKi0, DPKi1∈R∗∩Ldpk(2)
None of OSign withDPKi0 and DPKi1 was queried.A random bitb∈\{0,1\} is chosen, and A is given the σ← sign (M∗, R∗, DPKib, MPK, MSK), where (MPK, MSK) is the master key pair for DPKib.


### 4.5.4. Probing Phase 2

Same as the probing phase 1, but with the restriction that OSign withDPKi0 and DPKi1 cannot be queried.


### 4.5.5. Output Phase

A outputs a bit b′ as its guess to b.Definition 4.
The SALRS is anonymous if for allA, AdvAano is negligible, where AdvAano  = Prb=b−1/2 . We name the game for anonymity Gameano.


## 4.5.1. Setup

Same as that ofGameuf.


## 4.5.2. Probing Phase 1

Same as the probing phase ofGameuf.


## 4.5.3. Challenge Phase

A outputs a message M∗, a ring of well-formed derived public keys R∗, and two distinct indices 1 ≤i0, i1≤nλ, such that(1)
DPKi0, DPKi1∈R∗∩Ldpk(2)
None of OSign withDPKi0 and DPKi1 was queried.A random bitb∈\{0,1\} is chosen, and A is given the σ← sign (M∗, R∗, DPKib, MPK, MSK), where (MPK, MSK) is the master key pair for DPKib.


## 4.5.4. Probing Phase 2

Same as the probing phase 1, but with the restriction that OSign withDPKi0 and DPKi1 cannot be queried.


## 4.5.5. Output Phase

A outputs a bit b′ as its guess to b.Definition 4.
The SALRS is anonymous if for allA, AdvAano is negligible, where AdvAano  = Prb=b−1/2 . We name the game for anonymity Gameano.


## 4.6. Master-Public-Key-Unlinkability

Master-public-key-unlinkability means that with the support of a derived public key and the corresponding signatures, no one can distinguish which master public key is the one which it was derived from.


### 4.6.1. Setup

Same as that ofGameuf.


### 4.6.2. Probing Phase 1

Same as the probing phase ofGameuf.


### 4.6.3. Challenge

A outputs two distinct indices 1 ≤i0, i1≤nλ. A random bit b∈\{0,1\} is chosen, and DPK∗←DerivedPublicKeyGenMPKib is given to A. Set Ldpk = Ldpk∪, DPK∗\}.


### 4.6.4. Probing Phase 2

Same as the probing phase 1, with the restriction that ODPKAdd (DPK∗, MPKij) (j∈\{0,1\}) cannot be queried.


### 4.6.5. Output Phase

A outputs a bit b′∈\{0,1\} as its guess to b.Definition 5.
The SALRS is master-public-key-unlinkable if for allA, AdvAmpkunl is negligible, where AdvAmpkunl = Prb=b−1/2 . We name the game for master-public-key-unlinkability Gamempkunl.


## 4.6.1. Setup

Same as that ofGameuf.


## 4.6.2. Probing Phase 1

Same as the probing phase ofGameuf.


## 4.6.3. Challenge

A outputs two distinct indices 1 ≤i0, i1≤nλ. A random bit b∈\{0,1\} is chosen, and DPK∗←DerivedPublicKeyGenMPKib is given to A. Set Ldpk = Ldpk∪, DPK∗\}.


## 4.6.4. Probing Phase 2

Same as the probing phase 1, with the restriction that ODPKAdd (DPK∗, MPKij) (j∈\{0,1\}) cannot be queried.


## 4.6.5. Output Phase

A outputs a bit b′∈\{0,1\} as its guess to b.Definition 5.
The SALRS is master-public-key-unlinkable if for allA, AdvAmpkunl is negligible, where AdvAmpkunl = Prb=b−1/2 . We name the game for master-public-key-unlinkability Gamempkunl.


## 4.7. Derived-Public-Key-Unlinkability

Derived-public-key-unlinkability means that with the support of two derived public keys and the corresponding signatures, no one can figure out whether they are derived from the same master public key.


### 4.7.1. Setup

Same as that ofGameuf.


### 4.7.2. Probing Phase 1

Same as the probing phase ofGameuf.


### 4.7.3. Challenge

A outputs two distinct indices 1 ≤i0,i1≤nλ. A random bit c∈\{0,1\} is chosen. Compute DPK0∗←DerivedPublicKeyGenMPKic.A random bitb∈\{0,1\} is chosen. If b = 0, compute DPK1∗←DerivedPublicKeyGenMPKic; otherwise, compute DPK1∗←DerivedPublicKeyGenMPKi1−c. (DPK0∗, DPK1∗) are given to A. Set Ldpk  = Ldpk, ∪\{DPK0∗, DPK1∗\}.


### 4.7.4. Probing Phase 2

Same as the probing phase 1, with the restriction that ODPKAdd (DPKj∗, MPKik) (j, k∈\{0,1\}) can only be queried on at most one j∈ \{0,1\}.


### 4.7.5. Output Phase

A outputs a bit b′, ∈\{0,1\} as its guess to b.Definition 6.
The SALRS is derived-public-key-unlinkable, if for allA, AdvAdpkunl is negligible, where AdvAdpkunl = Prb=b−1/2. We name the game for derived-public-key-unlinkability Gamedpkunl.


## 4.7.1. Setup

Same as that ofGameuf.


## 4.7.2. Probing Phase 1

Same as the probing phase ofGameuf.


## 4.7.3. Challenge

A outputs two distinct indices 1 ≤i0,i1≤nλ. A random bit c∈\{0,1\} is chosen. Compute DPK0∗←DerivedPublicKeyGenMPKic.A random bitb∈\{0,1\} is chosen. If b = 0, compute DPK1∗←DerivedPublicKeyGenMPKic; otherwise, compute DPK1∗←DerivedPublicKeyGenMPKi1−c. (DPK0∗, DPK1∗) are given to A. Set Ldpk  = Ldpk, ∪\{DPK0∗, DPK1∗\}.


## 4.7.4. Probing Phase 2

Same as the probing phase 1, with the restriction that ODPKAdd (DPKj∗, MPKik) (j, k∈\{0,1\}) can only be queried on at most one j∈ \{0,1\}.


## 4.7.5. Output Phase

A outputs a bit b′, ∈\{0,1\} as its guess to b.Definition 6.
The SALRS is derived-public-key-unlinkable, if for allA, AdvAdpkunl is negligible, where AdvAdpkunl = Prb=b−1/2. We name the game for derived-public-key-unlinkability Gamedpkunl.


## 5. Our Concrete Scheme of SALRS

In this section, as a building block for our SALRS construction, we first introduce our novel concrete key encapsulation mechanism (KEM) based on the elliptic curve discrete logarithm. Then, we propose our concrete SALRS construction.


### 5.1. KEM Based on Elliptic Curve Discrete Logarithm

Formally, our novel concrete KEM based on the elliptic curve discrete logarithm consists of algorithms as follows.


#### 5.1.1. Setup1λ⟶ Params

The input to this algorithm is a security parameter1λ and outputs system global parameters params.The params are generated as follows. LetG1, G2, and GT be groups of prime order p, ℤp be an integer group of order p, gi be a generator of (i = 1,2), and e: G1×G2⟶GT be a bilinear, efficient, and computable map. Set G1≠G2, and there exists no efficient homomorphism between G1 and G2. H: GT⟶ℤp is a collision-resistant hash function. Then, we set params=(G1, G2, GT, ℤp, g1, g2, H).


#### 5.1.2. KeyGen (params)⟶ (pk, sk)

The input to this algorithm is the params and output a (public key, secret key) pair (pk, sk).The pair (pk, sk) is generated as follows. First, choose a randomα∈ℤp and then compute g1α. Finally, the pair (pk, sk) is set as (pk, sk)=(g1α, α).


#### 5.1.3. Encaps (pk, params)⟶ (AD, K)

The input to this algorithm is the pk and params, and output a ciphertext AD and a keyK. We let AD and K denote the ciphertext space and key space, respectively.The pair (AD, K) is generated as follows. First, choose a random r∈ℤp, compute the key g1r, compute HV≜H(e(pk, g2r)), and then compute g1HV. Finally, set (AD, K)=(g1HV, g1r).


#### 5.1.4. Decaps (params, AD, pk, sk)⟶K/ ⊥

The input to this algorithm is the params, ciphertextAD, public key pk, and secret key sk and outputs a key K or a special symbol ⊥ to indicate rejection.TheK/ ⊥ is generated as follows. If ∃r∈ℤp, the equation AD = g1SHV holds, where SHV≜H(e(g1r, g2sk)), output a key K = g1r; otherwise, output a special symbol ⊥.


### 5.2. Concrete SALRS Construction

#### 5.2.1.Setupλ⟶ PP

The input to this algorithm is a security parameterλ, the algorithm sets the parameters n, q, k, l, m, η, γ, and θ, let HA: 0,1\∗↦RRqk×l, expandV: K↦Sηl, Hθ: \0,1\∗↦Bθ, and Hm: Rqk↦Rqm×l be functions which are random oracles. The algorithm runs:(1)
SetA≜HA (cstr), where cstr is a random string belonging to 0,1\∗(2)
Run params← KEM⋅setup 1λ.Output the public parameters, PP = (n, q, k, l, m, η, γ, θ, HA, cstr, A, KEM, params, expandV, Hθ, Hm). PP are implicit input parameters to every algorithm as follows.


#### 5.2.2. MasterKeyGen (PP)⟶ (MPK, MSK)

The input to this algorithm is the PP; the algorithm runs:(1)
(pk, sk)←KEM⋅KeyGen (params)(2)
Sett←As, where s←RSηlOutput MPK≜ (pk, t) and MSK ≜ (sk, s).


#### 5.2.3. DerivedPublicKeyGen (MPK)⟶ DPK

The input to this algorithm is the MPK = (pk, t); the algorithm runs:(1)
Run (AD, K) ← KEM⋅Encaps (pk, params).(2)
Sets′≜ expandV (K) ∈, Sηl, t′←As′, and t^←t + t′.Output DPK≜ (AD, t^).


#### 5.2.4. DerivedPublicKeyOwnerCheck (DPK, MPK, MSK)⟶ 1/0

The input to this algorithm is a DPK, and pair (MPK, MSK) with MPK = (pk, t) and MSK = (sk, s); the algorithm runs:(1)
If DPK∈AD×, Rqk, set DPK ≜ (AD, t^) ∈AD×, Rqk; otherwise, return 0.(2)
RunK← KEM⋅Decaps (params, AD, pk, sk).(3)
Sets′≜ expandV (K) and t′←As′.Ift^ = t + t′, return 1; otherwise, return 0.


#### 5.2.5. DerivedPublicKeyPublicCheck (DPK)⟶ 1/0

The input to this algorithm is DPK; the algorithm runs: if DPK∈AD×, Rqk, return 1; otherwise, return 0.


#### 5.2.6. Sign (M, R, DPK, MPK, MSK) ⟶σ

The input to this algorithm is a messageM, a ring of well-formed derived public keys R = DPK1,…,DPKr, a derived public key DPK ∈R, and the master key pair for DPK, where MPK = (pk, t) and MSK = (sk, s); the algorithm runs:(1)
SetDPKi≜ (ADi, t^i) ∈AD×, Rqk and Hi≜, Hm (t^i) (i = 1, …,r).(2)
Leti¯ be DPK = DPKi¯ = (ADi¯, t^i¯), run K← KEM⋅Decaps (params, ADi¯, pk, sk). Set si¯′≜ expand (K) and s^i¯←s+ si¯′.(3)
UseHi¯ and s^i¯ above, and set I←Hi¯s^i¯.(4)
Setwi¯← Ay and vi¯←Hi¯y, where y←RSγl.(5)
Setci←Hθ (M, R, wi−1, vi−1, I), where we set c1←Hθ (M, R, wr, vr, I), and set wi←Azi−, cit^i and vi←Hizi−ciI, where zi←RSγ−2θηl, i =  i¯ +1, ⋯,r,1, ⋯,i¯−1.(6)
Setci¯←Hθ (M, R, wi¯−1, vi¯−1, I).Set <b>zi¯← y</b> + ci¯s^i¯. If zi¯∈, Sγ−2θηl, output σ≜ (cc1,\{zi\ i=1r, I) ∈, Bθ×(SSγ−2θηl)r × Rqm; otherwise, return to (4).


#### 5.2.7. Verify (M, R, σ) ⟶ 1/0

The input to this algorithm is a messageM, a ring of well-formed derived public keys R = DPK1,…,DPKr, and a signature σ =(c1,\zi\i=1r, I); the algorithm runs:(1)
Ifc1∉Bθ or zi∉Sγ−2θηl, ∃i∈\{1, …,r\}, return 0.(2)
SetDPKi≜ (ADi, t^i) ∈ (AD, Rqk) and Hi≜Hm (t^i) (i = 1, …,r). Then, set <b>wi←Azi−</b>cit^i, <b>vi←Hi</b> zi−ciI, and ci+1←Hθ (M, R, wi, vi, I).Ifcr+1 = c1, return 1; otherwise, return 0.


#### 5.2.8. Link (M0, R0, σ0, M1, R1, σ1) ⟶ 1/0

The input to this algorithm is two valid (messageM, derived public key ring R, and signature σ) tuples (M0, R0, σ0) and (M1, R1, σ1), where σ0 =(c10,\zi0\i=1r0, I0) and σ1 =(c11,\zi1\i=1r1, I1); the algorithm runs: if I0 = I1, return 1; otherwise, return 0.


## 5.1. KEM Based on Elliptic Curve Discrete Logarithm

Formally, our novel concrete KEM based on the elliptic curve discrete logarithm consists of algorithms as follows.


### 5.1.1. Setup1λ⟶ Params

The input to this algorithm is a security parameter1λ and outputs system global parameters params.The params are generated as follows. LetG1, G2, and GT be groups of prime order p, ℤp be an integer group of order p, gi be a generator of (i = 1,2), and e: G1×G2⟶GT be a bilinear, efficient, and computable map. Set G1≠G2, and there exists no efficient homomorphism between G1 and G2. H: GT⟶ℤp is a collision-resistant hash function. Then, we set params=(G1, G2, GT, ℤp, g1, g2, H).


### 5.1.2. KeyGen (params)⟶ (pk, sk)

The input to this algorithm is the params and output a (public key, secret key) pair (pk, sk).The pair (pk, sk) is generated as follows. First, choose a randomα∈ℤp and then compute g1α. Finally, the pair (pk, sk) is set as (pk, sk)=(g1α, α).


### 5.1.3. Encaps (pk, params)⟶ (AD, K)

The input to this algorithm is the pk and params, and output a ciphertext AD and a keyK. We let AD and K denote the ciphertext space and key space, respectively.The pair (AD, K) is generated as follows. First, choose a random r∈ℤp, compute the key g1r, compute HV≜H(e(pk, g2r)), and then compute g1HV. Finally, set (AD, K)=(g1HV, g1r).


### 5.1.4. Decaps (params, AD, pk, sk)⟶K/ ⊥

The input to this algorithm is the params, ciphertextAD, public key pk, and secret key sk and outputs a key K or a special symbol ⊥ to indicate rejection.TheK/ ⊥ is generated as follows. If ∃r∈ℤp, the equation AD = g1SHV holds, where SHV≜H(e(g1r, g2sk)), output a key K = g1r; otherwise, output a special symbol ⊥.


## 5.1.1. Setup1λ⟶ Params

The input to this algorithm is a security parameter1λ and outputs system global parameters params.The params are generated as follows. LetG1, G2, and GT be groups of prime order p, ℤp be an integer group of order p, gi be a generator of (i = 1,2), and e: G1×G2⟶GT be a bilinear, efficient, and computable map. Set G1≠G2, and there exists no efficient homomorphism between G1 and G2. H: GT⟶ℤp is a collision-resistant hash function. Then, we set params=(G1, G2, GT, ℤp, g1, g2, H).


## 5.1.2. KeyGen (params)⟶ (pk, sk)

The input to this algorithm is the params and output a (public key, secret key) pair (pk, sk).The pair (pk, sk) is generated as follows. First, choose a randomα∈ℤp and then compute g1α. Finally, the pair (pk, sk) is set as (pk, sk)=(g1α, α).


## 5.1.3. Encaps (pk, params)⟶ (AD, K)

The input to this algorithm is the pk and params, and output a ciphertext AD and a keyK. We let AD and K denote the ciphertext space and key space, respectively.The pair (AD, K) is generated as follows. First, choose a random r∈ℤp, compute the key g1r, compute HV≜H(e(pk, g2r)), and then compute g1HV. Finally, set (AD, K)=(g1HV, g1r).


## 5.1.4. Decaps (params, AD, pk, sk)⟶K/ ⊥

The input to this algorithm is the params, ciphertextAD, public key pk, and secret key sk and outputs a key K or a special symbol ⊥ to indicate rejection.TheK/ ⊥ is generated as follows. If ∃r∈ℤp, the equation AD = g1SHV holds, where SHV≜H(e(g1r, g2sk)), output a key K = g1r; otherwise, output a special symbol ⊥.


## 5.2. Concrete SALRS Construction

### 5.2.1.Setupλ⟶ PP

The input to this algorithm is a security parameterλ, the algorithm sets the parameters n, q, k, l, m, η, γ, and θ, let HA: 0,1\∗↦RRqk×l, expandV: K↦Sηl, Hθ: \0,1\∗↦Bθ, and Hm: Rqk↦Rqm×l be functions which are random oracles. The algorithm runs:(1)
SetA≜HA (cstr), where cstr is a random string belonging to 0,1\∗(2)
Run params← KEM⋅setup 1λ.Output the public parameters, PP = (n, q, k, l, m, η, γ, θ, HA, cstr, A, KEM, params, expandV, Hθ, Hm). PP are implicit input parameters to every algorithm as follows.


### 5.2.2. MasterKeyGen (PP)⟶ (MPK, MSK)

The input to this algorithm is the PP; the algorithm runs:(1)
(pk, sk)←KEM⋅KeyGen (params)(2)
Sett←As, where s←RSηlOutput MPK≜ (pk, t) and MSK ≜ (sk, s).


### 5.2.3. DerivedPublicKeyGen (MPK)⟶ DPK

The input to this algorithm is the MPK = (pk, t); the algorithm runs:(1)
Run (AD, K) ← KEM⋅Encaps (pk, params).(2)
Sets′≜ expandV (K) ∈, Sηl, t′←As′, and t^←t + t′.Output DPK≜ (AD, t^).


### 5.2.4. DerivedPublicKeyOwnerCheck (DPK, MPK, MSK)⟶ 1/0

The input to this algorithm is a DPK, and pair (MPK, MSK) with MPK = (pk, t) and MSK = (sk, s); the algorithm runs:(1)
If DPK∈AD×, Rqk, set DPK ≜ (AD, t^) ∈AD×, Rqk; otherwise, return 0.(2)
RunK← KEM⋅Decaps (params, AD, pk, sk).(3)
Sets′≜ expandV (K) and t′←As′.Ift^ = t + t′, return 1; otherwise, return 0.


### 5.2.5. DerivedPublicKeyPublicCheck (DPK)⟶ 1/0

The input to this algorithm is DPK; the algorithm runs: if DPK∈AD×, Rqk, return 1; otherwise, return 0.


### 5.2.6. Sign (M, R, DPK, MPK, MSK) ⟶σ

The input to this algorithm is a messageM, a ring of well-formed derived public keys R = DPK1,…,DPKr, a derived public key DPK ∈R, and the master key pair for DPK, where MPK = (pk, t) and MSK = (sk, s); the algorithm runs:(1)
SetDPKi≜ (ADi, t^i) ∈AD×, Rqk and Hi≜, Hm (t^i) (i = 1, …,r).(2)
Leti¯ be DPK = DPKi¯ = (ADi¯, t^i¯), run K← KEM⋅Decaps (params, ADi¯, pk, sk). Set si¯′≜ expand (K) and s^i¯←s+ si¯′.(3)
UseHi¯ and s^i¯ above, and set I←Hi¯s^i¯.(4)
Setwi¯← Ay and vi¯←Hi¯y, where y←RSγl.(5)
Setci←Hθ (M, R, wi−1, vi−1, I), where we set c1←Hθ (M, R, wr, vr, I), and set wi←Azi−, cit^i and vi←Hizi−ciI, where zi←RSγ−2θηl, i =  i¯ +1, ⋯,r,1, ⋯,i¯−1.(6)
Setci¯←Hθ (M, R, wi¯−1, vi¯−1, I).Set <b>zi¯← y</b> + ci¯s^i¯. If zi¯∈, Sγ−2θηl, output σ≜ (cc1,\{zi\ i=1r, I) ∈, Bθ×(SSγ−2θηl)r × Rqm; otherwise, return to (4).


### 5.2.7. Verify (M, R, σ) ⟶ 1/0

The input to this algorithm is a messageM, a ring of well-formed derived public keys R = DPK1,…,DPKr, and a signature σ =(c1,\zi\i=1r, I); the algorithm runs:(1)
Ifc1∉Bθ or zi∉Sγ−2θηl, ∃i∈\{1, …,r\}, return 0.(2)
SetDPKi≜ (ADi, t^i) ∈ (AD, Rqk) and Hi≜Hm (t^i) (i = 1, …,r). Then, set <b>wi←Azi−</b>cit^i, <b>vi←Hi</b> zi−ciI, and ci+1←Hθ (M, R, wi, vi, I).Ifcr+1 = c1, return 1; otherwise, return 0.


### 5.2.8. Link (M0, R0, σ0, M1, R1, σ1) ⟶ 1/0

The input to this algorithm is two valid (messageM, derived public key ring R, and signature σ) tuples (M0, R0, σ0) and (M1, R1, σ1), where σ0 =(c10,\zi0\i=1r0, I0) and σ1 =(c11,\zi1\i=1r1, I1); the algorithm runs: if I0 = I1, return 1; otherwise, return 0.


## 5.2.1.Setupλ⟶ PP

The input to this algorithm is a security parameterλ, the algorithm sets the parameters n, q, k, l, m, η, γ, and θ, let HA: 0,1\∗↦RRqk×l, expandV: K↦Sηl, Hθ: \0,1\∗↦Bθ, and Hm: Rqk↦Rqm×l be functions which are random oracles. The algorithm runs:(1)
SetA≜HA (cstr), where cstr is a random string belonging to 0,1\∗(2)
Run params← KEM⋅setup 1λ.Output the public parameters, PP = (n, q, k, l, m, η, γ, θ, HA, cstr, A, KEM, params, expandV, Hθ, Hm). PP are implicit input parameters to every algorithm as follows.


## 5.2.2. MasterKeyGen (PP)⟶ (MPK, MSK)

The input to this algorithm is the PP; the algorithm runs:(1)
(pk, sk)←KEM⋅KeyGen (params)(2)
Sett←As, where s←RSηlOutput MPK≜ (pk, t) and MSK ≜ (sk, s).


## 5.2.3. DerivedPublicKeyGen (MPK)⟶ DPK

The input to this algorithm is the MPK = (pk, t); the algorithm runs:(1)
Run (AD, K) ← KEM⋅Encaps (pk, params).(2)
Sets′≜ expandV (K) ∈, Sηl, t′←As′, and t^←t + t′.Output DPK≜ (AD, t^).


## 5.2.4. DerivedPublicKeyOwnerCheck (DPK, MPK, MSK)⟶ 1/0

The input to this algorithm is a DPK, and pair (MPK, MSK) with MPK = (pk, t) and MSK = (sk, s); the algorithm runs:(1)
If DPK∈AD×, Rqk, set DPK ≜ (AD, t^) ∈AD×, Rqk; otherwise, return 0.(2)
RunK← KEM⋅Decaps (params, AD, pk, sk).(3)
Sets′≜ expandV (K) and t′←As′.Ift^ = t + t′, return 1; otherwise, return 0.


## 5.2.5. DerivedPublicKeyPublicCheck (DPK)⟶ 1/0

The input to this algorithm is DPK; the algorithm runs: if DPK∈AD×, Rqk, return 1; otherwise, return 0.


## 5.2.6. Sign (M, R, DPK, MPK, MSK) ⟶σ

The input to this algorithm is a messageM, a ring of well-formed derived public keys R = DPK1,…,DPKr, a derived public key DPK ∈R, and the master key pair for DPK, where MPK = (pk, t) and MSK = (sk, s); the algorithm runs:(1)
SetDPKi≜ (ADi, t^i) ∈AD×, Rqk and Hi≜, Hm (t^i) (i = 1, …,r).(2)
Leti¯ be DPK = DPKi¯ = (ADi¯, t^i¯), run K← KEM⋅Decaps (params, ADi¯, pk, sk). Set si¯′≜ expand (K) and s^i¯←s+ si¯′.(3)
UseHi¯ and s^i¯ above, and set I←Hi¯s^i¯.(4)
Setwi¯← Ay and vi¯←Hi¯y, where y←RSγl.(5)
Setci←Hθ (M, R, wi−1, vi−1, I), where we set c1←Hθ (M, R, wr, vr, I), and set wi←Azi−, cit^i and vi←Hizi−ciI, where zi←RSγ−2θηl, i =  i¯ +1, ⋯,r,1, ⋯,i¯−1.(6)
Setci¯←Hθ (M, R, wi¯−1, vi¯−1, I).Set <b>zi¯← y</b> + ci¯s^i¯. If zi¯∈, Sγ−2θηl, output σ≜ (cc1,\{zi\ i=1r, I) ∈, Bθ×(SSγ−2θηl)r × Rqm; otherwise, return to (4).


## 5.2.7. Verify (M, R, σ) ⟶ 1/0

The input to this algorithm is a messageM, a ring of well-formed derived public keys R = DPK1,…,DPKr, and a signature σ =(c1,\zi\i=1r, I); the algorithm runs:(1)
Ifc1∉Bθ or zi∉Sγ−2θηl, ∃i∈\{1, …,r\}, return 0.(2)
SetDPKi≜ (ADi, t^i) ∈ (AD, Rqk) and Hi≜Hm (t^i) (i = 1, …,r). Then, set <b>wi←Azi−</b>cit^i, <b>vi←Hi</b> zi−ciI, and ci+1←Hθ (M, R, wi, vi, I).Ifcr+1 = c1, return 1; otherwise, return 0.


## 5.2.8. Link (M0, R0, σ0, M1, R1, σ1) ⟶ 1/0

The input to this algorithm is two valid (messageM, derived public key ring R, and signature σ) tuples (M0, R0, σ0) and (M1, R1, σ1), where σ0 =(c10,\zi0\i=1r0, I0) and σ1 =(c11,\zi1\i=1r1, I1); the algorithm runs: if I0 = I1, return 1; otherwise, return 0.


## 6. Security Analysis of Our SALRS Construction

Now, we prove that our construction has the usual properties for a SALRS such as correctness, unforgeability, anonymity, linkability, nonslanderability, master-public-key-unlinkability, and derived-public-key-unlinkability.


### 6.1. Correctness Analysis

It is obvious that from our SALRS construction, (1) and (2) of correctness are satisfied. Therefore, we next prove (3) of correctness. Letσj = (c1j,zij\i=1rj, Ij) be generated by sign (Mj, Rj, DPKj, MPKj, MSKj) (j = 0,1) and let DPKi = (ADi, t^i).(1)
IfDPK0 = DPK1, we have s^0 = s^1, and then I0 = I1. In this case, we have link outputs 1.(2)
IfDPK0≠DPK1, we now prove that link outputs 0 with overwhelming probability. If t^0≠t^1, we can see that Hm (t^0), Hm (t^1) are distinct. s^0 and s^1 are distinct. Then we have the result that the probability of I0 = Hm (t^0) s^0 =Hm (t^1) s^1 = I1 is negligible. If t^0 = t^1 but AD0≠AD1, we want to prove s^0 = s^1. We consider s^0≠s^1. If s^0≠s^1 and t^0 = As^0 = As^1 = t^1, its probability is negligible, so we must have s^0 = s^1. s^0 = s^1 have two cases.(1)
s0≠s1 and s0′ ≠ s1′:The probability of this scenario is negligible because of the randomness ofs0, s1, s0′, and s1′.(2)
s0 = s1 and s0′ = s1′:The probability ofss0 = s1 is negligible because two different executions of algorithm DerivedPublicKeyGen with AD0≠AD1 will produce distinct s0′ = s1′ with overwhelming probability. This completes the correctness analysis.


### 6.2. Security Analysis

We useA to denote any probabilistic polynomial time (PPT) adversary in security games.Theorem 1.
The SALRS construction is linkable.Proof.
We now prove that our SALRS construction is linkable under module-SIS assumption. IfA succeeds because (3) of linkability holds, it means that ∃i,j∈ [1,k] and i ≠ j, DPKi¯ = DPKj¯ where DPKi¯∈Ri∗ and DPKj¯∈Rj∗ . Then, we set DPKi¯ = (ADi¯, t^i¯) and DPKj¯ = (ADj¯, t^j¯), and we have t^i¯ = t^j¯  = As^j¯ = As^i¯. With the support of module-SIS assumption, we have s^i¯ = s^j¯ with overwhelming probability, which also means DPKi¯ = DPKj¯ with overwhelming probability. From (1) of linkability and (1) of correctness, we have σi∗ = sign (Mi∗, Ri∗, DPKi¯, MPKi¯, MSKi¯) and σj∗ = sign (Mj∗, RRj∗, DPKj¯, MPKj¯, MSKj¯). Finally, from (3) of correctness, we can find that (2) of linkability is not satisfied. This completes the proof.Theorem 2.
The SALRS construction is nonslanderable.Proof.
We now prove that our SALRS construction is nonslanderable under the correctness of the SALRS scheme. IfA succeeds, from (1) and (2) of nonslanderability and (1) of correctness, we have σ∗ = sign (M∗, R∗, DPK∗, MPK∗, MSK∗) and σ′ = sign (M′, R′, DPK′, MPK′, MSK′). Because of (4) of nonslanderability and (3) of correctness, we have DPK∗ = DPK′ with overwhelming probability. So, we can find that (3) of nonslanderability is not satisfied. This completes the proof.Lemma 1.
(See [9]). If a SALRS scheme is linkable and nonslanderable, then it is unforgeable.Theorem 3.
The SALRS construction is unforgeable.Proof.
According to Theorem1, Theorem 2, and Lemma 1, our SALRS scheme is unforgeable. This completes the proof.Theorem 4.
The SALRS construction is anonymous.Proof.
We now prove that our SALRS construction is anonymous under the decision module-LWE assumption. IfA succeeds, we set σ = (c1,\zi\i=1r, I) and DPKib = (ADib, t^ib) (b∈\{0,1\}). From algorithm sign, we have I = Hibs^ib. It means that A can distinguish Hi0s^i0 and Hi1s^i1, which contradicts the decision module-LWE assumption. This completes the proof.Theorem 5.
The SALRS construction is master-public-key-unlinkable.Proof.
We now prove that our SALRS construction is master-public-key-unlinkable under the BDH-1 assumption. IfA succeeds, we set DPK∗ = (AD, t^), AD = ADi, and t^ = t^i (i∈\{0,1\}), that means that A can distinguish (ADi, t^i) with a nonnegligible probability. From the algorithm DerivedPublicKeyGen, we have t^i = ti + ti′, ti′ = Asi′, si′ = expandV (K), and (AD, K) ← KEM⋅Encaps (pk, params), where K = Ki. It is obvious that because of the randomness of r∈G1 and K = g1r in the algorithm Decaps, A cannot distinguish K with an overwhelming probability. Therefore, A cannot distinguish si′, so A cannot distinguish t^i with an overwhelm probability.
We now prove thatA cannot distinguish ADi with an overwhelming probability too. If A can distinguish ADi with a nonnegligible probability ϵ, we can construct a PPT algorithm ℬ that solves the BDH-1 problem. To be specific, we assume that A and ℬ play the game Gamesec, and ℬ simulates the challenger and tries to solve the BDH-1 problem. Suppose the BDH-1 instance (g1, g2, g1a, g1b) is given to ℬ. ℬ initializes system parameters and gets params=(G1, G2, GT, ℤp, g1, g2, H) from KEM. Then, ℬ interacts with A as follows.


#### 6.2.1. Setup

ℬ sends params to A.


#### 6.2.2. Query 1

(1)
Key pair query:A asks ℬ to use the algorithm KeyGen of KEM to compute a key pair (pk, sk)=(g1α, α) and return it to A. A can only query at most q1 times for key pairs.(2)
Public key query:A ask ℬ to use the algorithm KeyGen of KEM to compute a key pair (pk, sk) and return the public key pk to A. A can only query at most q2 times for key pairs.(3)
Hash query:ℬ sets a hash list Hlist. Hlist is initialized as an empty set. When A submits a random element gT∈GT to ℬ, ℬ answers as follows. If it has not appeared in Hlist, ℬ choose a random element z∈ℤp and returns it to A. Then, ℬ stores the tuple (gT, z) in Hlist. Otherwise, ℬ finds out the tuple (gT, z) and returns z to A. A can only query at most q3 times for hash queries.


#### 6.2.3. Challenge

A chooses a public key pk∗ from (1) of query 1 and sends it to ℬ. ℬ chooses a random bit δ, ∈\{0,1\}; if δ = 0, ℬ sets K∗  = g1b and computesAD∗← Encaps (pk∗, params) and then returns them to A. Otherwise, ℬ chooses a random element AD∗, ∈G1 and sets K∗ = g1b and returns them to A.


#### 6.2.4. Query 2

A can make queries as he does in query 1 except secret keys for pk∗.


#### 6.2.5. Guess

Finally,A outputs a bit δ′ as the guess of δ.IfA can distinguish ADi, then A can guess the answer. Then, ℬ chooses tuple (gT, z) in Hlist, which satisfies gT = eg1,g2ab. Then, ℬ outputs z as the solution to BDH-1 problem. The probability that ℬ solves the BDH-1 problem is that Pr[ℬsucceeds] = ϵ⋅Pr[A (pk∗ =  g1a)]⋅Pr[ℬ (z = e(g1a, g1b))].Ifℬ succeeds in obtaining a solution of BDH-1 problem, the following conditions must be satisfied:(1)
Pr[A (pk∗ =  g1a)] ≥1/q2 (A correctly chooses pk∗).(2)
Pr[ℬ (z = e(g1a, g2b))] ≥1/q3 (ℬ correctly chooses z).Therefore, we havePr[ℬsucceeds] ≥ϵ/q2q3). It means that the probability of the fact that ℬ solves BDH-1 problem is nonnegligible, which contradicts BDH-1 assumption. This completes the proof.Lemma 2.
(See [9]). If a SALRS scheme is master-public-key-unlinkable, then it is derived-public-key-unlinkable.Theorem 6.
The SALRS construction is derived-public-key-unlinkable.Proof.
According to Theorem5 and Lemma 2, our SALRS scheme is derived-public-key-unlinkable. This completes the proof.


## 6.1. Correctness Analysis

It is obvious that from our SALRS construction, (1) and (2) of correctness are satisfied. Therefore, we next prove (3) of correctness. Letσj = (c1j,zij\i=1rj, Ij) be generated by sign (Mj, Rj, DPKj, MPKj, MSKj) (j = 0,1) and let DPKi = (ADi, t^i).(1)
IfDPK0 = DPK1, we have s^0 = s^1, and then I0 = I1. In this case, we have link outputs 1.(2)
IfDPK0≠DPK1, we now prove that link outputs 0 with overwhelming probability. If t^0≠t^1, we can see that Hm (t^0), Hm (t^1) are distinct. s^0 and s^1 are distinct. Then we have the result that the probability of I0 = Hm (t^0) s^0 =Hm (t^1) s^1 = I1 is negligible. If t^0 = t^1 but AD0≠AD1, we want to prove s^0 = s^1. We consider s^0≠s^1. If s^0≠s^1 and t^0 = As^0 = As^1 = t^1, its probability is negligible, so we must have s^0 = s^1. s^0 = s^1 have two cases.(1)
s0≠s1 and s0′ ≠ s1′:The probability of this scenario is negligible because of the randomness ofs0, s1, s0′, and s1′.(2)
s0 = s1 and s0′ = s1′:The probability ofss0 = s1 is negligible because two different executions of algorithm DerivedPublicKeyGen with AD0≠AD1 will produce distinct s0′ = s1′ with overwhelming probability. This completes the correctness analysis.


## 6.2. Security Analysis

We useA to denote any probabilistic polynomial time (PPT) adversary in security games.Theorem 1.
The SALRS construction is linkable.Proof.
We now prove that our SALRS construction is linkable under module-SIS assumption. IfA succeeds because (3) of linkability holds, it means that ∃i,j∈ [1,k] and i ≠ j, DPKi¯ = DPKj¯ where DPKi¯∈Ri∗ and DPKj¯∈Rj∗ . Then, we set DPKi¯ = (ADi¯, t^i¯) and DPKj¯ = (ADj¯, t^j¯), and we have t^i¯ = t^j¯  = As^j¯ = As^i¯. With the support of module-SIS assumption, we have s^i¯ = s^j¯ with overwhelming probability, which also means DPKi¯ = DPKj¯ with overwhelming probability. From (1) of linkability and (1) of correctness, we have σi∗ = sign (Mi∗, Ri∗, DPKi¯, MPKi¯, MSKi¯) and σj∗ = sign (Mj∗, RRj∗, DPKj¯, MPKj¯, MSKj¯). Finally, from (3) of correctness, we can find that (2) of linkability is not satisfied. This completes the proof.Theorem 2.
The SALRS construction is nonslanderable.Proof.
We now prove that our SALRS construction is nonslanderable under the correctness of the SALRS scheme. IfA succeeds, from (1) and (2) of nonslanderability and (1) of correctness, we have σ∗ = sign (M∗, R∗, DPK∗, MPK∗, MSK∗) and σ′ = sign (M′, R′, DPK′, MPK′, MSK′). Because of (4) of nonslanderability and (3) of correctness, we have DPK∗ = DPK′ with overwhelming probability. So, we can find that (3) of nonslanderability is not satisfied. This completes the proof.Lemma 1.
(See [9]). If a SALRS scheme is linkable and nonslanderable, then it is unforgeable.Theorem 3.
The SALRS construction is unforgeable.Proof.
According to Theorem1, Theorem 2, and Lemma 1, our SALRS scheme is unforgeable. This completes the proof.Theorem 4.
The SALRS construction is anonymous.Proof.
We now prove that our SALRS construction is anonymous under the decision module-LWE assumption. IfA succeeds, we set σ = (c1,\zi\i=1r, I) and DPKib = (ADib, t^ib) (b∈\{0,1\}). From algorithm sign, we have I = Hibs^ib. It means that A can distinguish Hi0s^i0 and Hi1s^i1, which contradicts the decision module-LWE assumption. This completes the proof.Theorem 5.
The SALRS construction is master-public-key-unlinkable.Proof.
We now prove that our SALRS construction is master-public-key-unlinkable under the BDH-1 assumption. IfA succeeds, we set DPK∗ = (AD, t^), AD = ADi, and t^ = t^i (i∈\{0,1\}), that means that A can distinguish (ADi, t^i) with a nonnegligible probability. From the algorithm DerivedPublicKeyGen, we have t^i = ti + ti′, ti′ = Asi′, si′ = expandV (K), and (AD, K) ← KEM⋅Encaps (pk, params), where K = Ki. It is obvious that because of the randomness of r∈G1 and K = g1r in the algorithm Decaps, A cannot distinguish K with an overwhelming probability. Therefore, A cannot distinguish si′, so A cannot distinguish t^i with an overwhelm probability.
We now prove thatA cannot distinguish ADi with an overwhelming probability too. If A can distinguish ADi with a nonnegligible probability ϵ, we can construct a PPT algorithm ℬ that solves the BDH-1 problem. To be specific, we assume that A and ℬ play the game Gamesec, and ℬ simulates the challenger and tries to solve the BDH-1 problem. Suppose the BDH-1 instance (g1, g2, g1a, g1b) is given to ℬ. ℬ initializes system parameters and gets params=(G1, G2, GT, ℤp, g1, g2, H) from KEM. Then, ℬ interacts with A as follows.


### 6.2.1. Setup

ℬ sends params to A.


### 6.2.2. Query 1

(1)
Key pair query:A asks ℬ to use the algorithm KeyGen of KEM to compute a key pair (pk, sk)=(g1α, α) and return it to A. A can only query at most q1 times for key pairs.(2)
Public key query:A ask ℬ to use the algorithm KeyGen of KEM to compute a key pair (pk, sk) and return the public key pk to A. A can only query at most q2 times for key pairs.(3)
Hash query:ℬ sets a hash list Hlist. Hlist is initialized as an empty set. When A submits a random element gT∈GT to ℬ, ℬ answers as follows. If it has not appeared in Hlist, ℬ choose a random element z∈ℤp and returns it to A. Then, ℬ stores the tuple (gT, z) in Hlist. Otherwise, ℬ finds out the tuple (gT, z) and returns z to A. A can only query at most q3 times for hash queries.


### 6.2.3. Challenge

A chooses a public key pk∗ from (1) of query 1 and sends it to ℬ. ℬ chooses a random bit δ, ∈\{0,1\}; if δ = 0, ℬ sets K∗  = g1b and computesAD∗← Encaps (pk∗, params) and then returns them to A. Otherwise, ℬ chooses a random element AD∗, ∈G1 and sets K∗ = g1b and returns them to A.


### 6.2.4. Query 2

A can make queries as he does in query 1 except secret keys for pk∗.


### 6.2.5. Guess

Finally,A outputs a bit δ′ as the guess of δ.IfA can distinguish ADi, then A can guess the answer. Then, ℬ chooses tuple (gT, z) in Hlist, which satisfies gT = eg1,g2ab. Then, ℬ outputs z as the solution to BDH-1 problem. The probability that ℬ solves the BDH-1 problem is that Pr[ℬsucceeds] = ϵ⋅Pr[A (pk∗ =  g1a)]⋅Pr[ℬ (z = e(g1a, g1b))].Ifℬ succeeds in obtaining a solution of BDH-1 problem, the following conditions must be satisfied:(1)
Pr[A (pk∗ =  g1a)] ≥1/q2 (A correctly chooses pk∗).(2)
Pr[ℬ (z = e(g1a, g2b))] ≥1/q3 (ℬ correctly chooses z).Therefore, we havePr[ℬsucceeds] ≥ϵ/q2q3). It means that the probability of the fact that ℬ solves BDH-1 problem is nonnegligible, which contradicts BDH-1 assumption. This completes the proof.Lemma 2.
(See [9]). If a SALRS scheme is master-public-key-unlinkable, then it is derived-public-key-unlinkable.Theorem 6.
The SALRS construction is derived-public-key-unlinkable.Proof.
According to Theorem5 and Lemma 2, our SALRS scheme is derived-public-key-unlinkable. This completes the proof.


## 6.2.1. Setup

ℬ sends params to A.


## 6.2.2. Query 1

(1)
Key pair query:A asks ℬ to use the algorithm KeyGen of KEM to compute a key pair (pk, sk)=(g1α, α) and return it to A. A can only query at most q1 times for key pairs.(2)
Public key query:A ask ℬ to use the algorithm KeyGen of KEM to compute a key pair (pk, sk) and return the public key pk to A. A can only query at most q2 times for key pairs.(3)
Hash query:ℬ sets a hash list Hlist. Hlist is initialized as an empty set. When A submits a random element gT∈GT to ℬ, ℬ answers as follows. If it has not appeared in Hlist, ℬ choose a random element z∈ℤp and returns it to A. Then, ℬ stores the tuple (gT, z) in Hlist. Otherwise, ℬ finds out the tuple (gT, z) and returns z to A. A can only query at most q3 times for hash queries.


## 6.2.3. Challenge

A chooses a public key pk∗ from (1) of query 1 and sends it to ℬ. ℬ chooses a random bit δ, ∈\{0,1\}; if δ = 0, ℬ sets K∗  = g1b and computesAD∗← Encaps (pk∗, params) and then returns them to A. Otherwise, ℬ chooses a random element AD∗, ∈G1 and sets K∗ = g1b and returns them to A.


## 6.2.4. Query 2

A can make queries as he does in query 1 except secret keys for pk∗.


## 6.2.5. Guess

Finally,A outputs a bit δ′ as the guess of δ.IfA can distinguish ADi, then A can guess the answer. Then, ℬ chooses tuple (gT, z) in Hlist, which satisfies gT = eg1,g2ab. Then, ℬ outputs z as the solution to BDH-1 problem. The probability that ℬ solves the BDH-1 problem is that Pr[ℬsucceeds] = ϵ⋅Pr[A (pk∗ =  g1a)]⋅Pr[ℬ (z = e(g1a, g1b))].Ifℬ succeeds in obtaining a solution of BDH-1 problem, the following conditions must be satisfied:(1)
Pr[A (pk∗ =  g1a)] ≥1/q2 (A correctly chooses pk∗).(2)
Pr[ℬ (z = e(g1a, g2b))] ≥1/q3 (ℬ correctly chooses z).Therefore, we havePr[ℬsucceeds] ≥ϵ/q2q3). It means that the probability of the fact that ℬ solves BDH-1 problem is nonnegligible, which contradicts BDH-1 assumption. This completes the proof.Lemma 2.
(See [9]). If a SALRS scheme is master-public-key-unlinkable, then it is derived-public-key-unlinkable.Theorem 6.
The SALRS construction is derived-public-key-unlinkable.Proof.
According to Theorem5 and Lemma 2, our SALRS scheme is derived-public-key-unlinkable. This completes the proof.


## 7. Efficiency Analysis

In this section, we make a comparison with the efficiency of the SALRS scheme in [9]. The parameters n, l, k, q, m, θ, η, and γ are set to be same as which in [9], i.e., n = 256, l = 5, k = 3, q≈235 and q = 17 mod 32, m = 1, θ = 60, η = 3, and γ = 699453. Additionally, the functions HA, Hm, Hθ, and expandV are set to be same as which in [9], that is to say, we use SHAKE-256 to implement the functions HA, Hm, and expandV and use the algorithm SampleInBall to implement Hθ. Moreover, with the parameter selection above, we have the fact that in order to obtain the signature in our SALRS scheme, the signer has to run Step 4−Step 6 of algorithm sign at most twice. Because, the probability of restarting of Step 4−Step 6, which can be easily worked out, is 2θη/γ+0.5≈1−, e−2nlθη/γ.From [10, 18, 27], we can obtain an instantiation of KEM where the system global parameters params of KEM are set to be the public parameters of the stealth address scheme in [27]. Especially, the group G1 in our novel concrete KEM is instantiated to be the special elliptic curve called Ed25519 in [18].The Ed25519 curve in [18] obviously tells us that in our SALRS scheme, the size of public key pk, secret key sk, or ciphertext AD is (256–1) × 2 = 510 bits, 256 × 2 = 512 bits, or (256–1) × 2 = 510 bits, respectively. On the other hand, the efficiency analysis of the SALRS scheme in [9] also tells us that its size of public key, secret key, or ciphertext is 1088 bytes, 2400 bytes, or (1184–32) = 1152 bytes, respectively. With the datum above, we can find that the size of public key in our SALRS scheme is smaller than that in [9], which means that from the construction of master public key (MPK), the size of MPK in our SALRS scheme is also smaller than that in [9]. The same applies to the master secret key (MSK) and derived public key (DPK). It comes out a conclusion that with regard to the size of MPK, MSK, and DPK, our SALRS scheme has less storage cost.


## 8. Conclusion

In this study, the linkable ring signature scheme with stealth addresses were addressed. Then, we proved the security of proposed schemes under the assumptions of BDH-1 problem, module-SIS problem, and module-LWE problem. The results showed that our schemes have all the properties that a linkable ring signature scheme with stealth addresses should have, i.e., unforgeability, anonymity, linkability, nonslanderability, master-public-key-unlinkability, and derived-public-key-unlinkability. Efficiency analysis showed that our SALRS scheme has less storage cost than the SALRS scheme in [9] under the same security conditions.



---

*Source: 1417607-2022-02-07.xml*