# A New Lattice-Based Blind Ring Signature for Completely Anonymous Blockchain Transaction Systems

Authors: Yi-Yang Xie; Xiu-Bo Chen; Yi-Xian Yang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Blockchain technology has been widely applied in numerous industries with its decentralization, verifiability, distributivity, and immutability. However, the identity privacy security of blockchain users is facing serious threats because of the openness of traditional blockchain transaction information. Moreover, numerous traditional cryptographic algorithms used by blockchain transaction networks are difficult to attack quantum computing. In this paper, we propose a new lattice-based blind ring signature scheme in allusion to completely anonymous blockchain transaction systems. There into, the blind ring signature can implement the complete anonymity of user identity privacy in blockchain transactions. Meanwhile, lattice cryptography can availably resist quantum computing attacks. Firstly, the proposed signature scheme has strong computational security based on the small integer solution (SIS) problem and a high sampling success rate by utilizing the techniques of rejection sampling from bimodal Gaussian distribution. Secondly, the proposed signature scheme can satisfy the correctness and security under the random oracle model, including anonymity, blindness, and one-more unforgeability. Thirdly, we construct a blockchain transaction system based on the proposed blind ring signature algorithm, which realizes the completely anonymous and antiquantum computing security of the blockchain users’ identity privacy. Finally, the performance evaluation results show that our proposed blind ring signature scheme has lower latency, smaller key size, and signature size than other similar schemes.


---

## Body

## 1. Introduction

Blockchain has gained much attention that is widely used in digital currency, medical, government services, and other applications, however, the security problems of blockchain have become increasingly prominent in recent years. As the data information needs to be jointly maintained by each node in the blockchain distributed network, it requires that the transaction information must be public, which will lead to the disclosure of personal identity privacy data. In many classical blockchain systems represented by Bitcoin [1], users utilize a string of numbers unrelated to their real identity information as the transaction address, which preliminarily realizes the anonymity of identity privacy. Unfortunately, because transactions in the Bitcoin network can be linked, attackers can discover users’ real identity information by their blockchain addresses [2, 3]. Therefore, to realize the veritable anonymity of the users’ identity privacy, it is necessary to ensconce the relationship between users and their corresponding blockchain addresses.The anonymity of identity information can be realized by ring signature and blind signature cryptography algorithms. Ring signature, developed from group signature [4], was first proposed by Rivest [5] in 2001. In the ring signature scheme, multiple users spontaneously constitute a ring and then randomly choose a member in the ring to sign the message. The signer uses his secret key and ring public keys of all members to generate a legal and valid ring signature. The ring signature prevents the exposure of the actual signer and invariably protects the signer’s identity privacy. Another algorithm that can provide anonymity is the blind signature, which was first proposed by Chaum [6] in 1983. In the blind signature scheme, the signer can sign the message in case of unknowing the true content of the signature file. The sign holder sends the blinded message to the signer for signature. The blind signature guarantees that signers hardly infer sign holders’ real identity information through the blind message, which effectively protects sign holders’ identity information privacy. In the blockchain transaction network, numerous anonymous transaction schemes are based on blind signature or ring signature [7–9]. However, the ring signature or blind signature can only guarantee the anonymity of a single user participating in the blockchain transaction, which cannot protect the identity privacy of both parties at the same time. To satisfy the complete anonymity of blockchain transaction users’ identity privacy, it is significant to establish a blind ring signature scheme suitable for complete anonymous blockchain transactions. In 2005, Chan et al. [10] first proposed a blind ring signature algorithm, and since then, numerous blind ring signature schemes have been designed [11–13].The security of traditional signature algorithms depends on integer decomposition, discrete logarithm and bilinear equivalent mathematical problems. Unfortunately, quantum computing can easily solve traditional difficult mathematical problems. Shor [14] proposed a quantum algorithm that lets RSA cryptography, elliptic curve cryptography, and cryptosystems based on bilinear pairings face serious security challenges. Grover [15] proposed a quantum search algorithm that could provide secondary acceleration for search problems, which seriously threatened the security of symmetric cryptography and the Hash function. Therefore, it is a key research work to find a cryptosystem that can resist quantum computing attacks.Lattice cryptography is a kind of antiquantum computing cryptography with strong security and high computational efficiency, which is widely used in digital signature algorithm design and blockchain transaction networks. Gentry et al. [16] first designed a signature algorithm with lattice trapdoor sampling, whose security depends on solving the SIS problem. Lyubashevsky [17] proposed a signature scheme without trapdoor sampling, which uses rejection sampling to greatly improve the sampling efficiency. Ducas et al. [18] designed a new signature algorithm with lattice rejection sampling, which further improves the sampling success rate through random sampling on bimodal Gaussian distribution. In 2018, Gao et al. [19] first proposed a postquantum blockchain system, which integrated a lattice-based signature algorithm. In 2022, Zou et al. [20] proposed a lattice-based proxy signature scheme for anonymous blockchain-enabled electronic reporting systems, which not only realized the anonymity of user identity but also solved the problem of misbehaviors untraceability on the blockchain. Moreover, Rückert [21] proposed the first blind lattice-based signature algorithm. Li et al. [22] proposed a new blind signature algorithm applied in blockchain anonymous transaction authentication on the lattice. In addition, Melchor et al. [23] designed the first ring signature algorithm based on lattice cryptography. To further improve the sampling success rate, Wang et al. [24] designed a new ring signature algorithm using Lyubashevsky’s rejection sampling signature [17]. In 2019, Le et al. [25] designed the first blind ring signature algorithm based on the SIS problem with rejection sampling. Moreover, numerous lattice-based blind signature and ring signature schemes have been proposed [26, 27].In this paper, we design a new lattice-based blind ring signature algorithm in allusion to the completely anonymous blockchain transaction system. The constructed transaction system satisfies the requirements of the user’s identity privacy protection and resistance to quantum attacks. There are three main contributions, which are as follows:(1)
We propose a new lattice-based blind ring signature algorithm using the rejection sampling technology. Sampling on the bimodal Gaussian distribution can greatly improve the success rate. In addition, we give proof of correctness and security under the random oracle model, including anonymity, blindness, and one-more unforgeability.(2)
We construct a completely anonymous blockchain transaction system based on the proposed blind ring signature and provide detailed processes of the anonymous transaction. The system satisfies the goal of blockchain users’ identity privacy protection and antiquantum computing security.(3)
We evaluate the performance of the proposed signature algorithm with other similar literature schemes, including the sampling method, algorithm latency, the size of the signature, and secret and public keys. The evaluation results indicate that our proposed scheme has lower latency and smaller key and signature sizes than other similar schemes.The organization of this paper is as follows: we present some lattice theories and the blind ring signature’s definition and security model in Section2. In Section 3, a new lattice-based blind ring signature is designed. In Section 4, we prove the security of our signature algorithm. We construct a completely anonymous blockchain transaction system based on the proposed blind ring signature in Section 5. The performance evaluation of signature algorithms is shown in Section 6. Finally, we provide a conclusion of the paper in Section 7.


## 2. Preliminaries

### 2.1. Some Related Theories of Lattice

Definition 1.
(Lattice [28]). Given a matrix B∈ℝm×n consists of a group of m-dimensional linearly independent vectors b1,…, b2, … bn. where m≥n Define lattice Λ generated by B as the set.(1)ΛB=Bx|x∈ℤn.
Given a prime numberq, a matrix A∈ℤqn×m, and e∈ℤqn, define some q-ary lattices.(2)ΛqA=y∈ℤm|y∈ATxmodq,x∈ℤn,Λq⊥A=y∈ℤm|Ay=0modq,ΛqeA=y∈ℤm|Ay=emodq.Definition 2.
(Discrete Gaussian Distribution [17]). Define Dv,σmz=ρv,σmz/ρv,σmℤm as a discrete Gaussian distribution, where ρv,σmz=1/2πσ2me−z−v2/2σ2 and ρv,σmℤm=∑z∈ℤmρσmz.Definition 3.
(SIS problem). Given a random matrixA∈ℤqn×m and parameters m, n, q, β, the SISq,n,m,β problem is to find a nonzero integer vector v∈ℤqm, such that Av=0modq and v≤β.Lemma 1.
(see [17]). For any v∈ℝm, σ>0, k>1, it satisfies the following:(3)Prz>kσm;z←Dσm≤kmem/21−k2.Lemma 2.
(see [17]). For any v∈ℤm, σ=αv, α>0, it satisfies the following:(4)PrDσmzDv,σmz<e12/α+1/2α2:z←Dσm>1−2−100.
More specially, ifα=12, σ=12v, then Dσmz/Dv,σmz<e1+1/288 with a probability of at least 1−2−100.Lemma 3.
(Rejection Sampling [17]).Select a random vector v∈ℤm and a real number σ=ωtlogm, given a subset V=v∈ℤm:v<t, and define on V a probability distribution h:V⟶ℝ. Then, there exists a constant M=O1 such that the outputs of the following two algorithms Α and B have a negligible statistical distance of ΔA,B=2−ωlogm/M:AlgorithmΑ: v←h, z←Dv,σm, output z,v with probability minDσmz/MDv,σmz,1.AlgorithmB: v←h, z←Dσm, output z,v with probability 1/M.
Moreover, the probability that the algorithmΑ outputs something is at least 1−2−ωlogm/M.
More specially, ifσ=αt for any α>0, then M=e12/α+1/2α2. The two algorithms Α and B have a negligible statistical distance off ΔA,B=2−100/M, and the probability that Α outputs something is at least 1−2−100/M.


### 2.2. Blind Ring Signature Model

#### 2.2.1. System Model

The blind ring signature system model is composed of four parts called setup, key generation, signature, and verification [25]. The detailed steps are as follows:Setup. Input a security parametern and output public parameters PP.Key generation. Generate public keypk and secret key sk for each member of the ring R=S1,S2,…,Sl according to the input set of public parameters PP.Signature. The user ϒ submits a messagem and blinds it to μ before sending the message to the signer. Then, the ring R chooses a signer Σj, who takes the secret key skj. The signer Σj signs the message μ and generates a blinded signature Σ′. The user ϒ unblinds Σ′ and gets the real signature Σ.Verification. Output 1 or 0 according to the public parameters PP, messagem, signature Σ, and ring public keys PK=pkii∈l. The output of 1 means that the verification is passed, and 0 indicates that it is otherwise.


#### 2.2.2. Security Model

The security model of the blind ring signature includes anonymity, blindness, and one-more unforgeability.Anonymity: the anonymity property ensures that the user cannot know which member of the ring was the real signer participating in the blind ring signature protocol. For any polynomial-time adversary, the blind ring signature scheme satisfies the anonymity under full key exposure if his advantage in winning the following game with the challenger is negligible.(1)
Setup: assumen to be the system security parameter. The challenger calls the setup algorithm in the blind ring signature scheme to generate the set of common parameters PP. Then, according to the common parameters PP, the challenger calls the key generation algorithm to generate a set of public and secret keys (PK, SK) for the ring R=S1,S2,…,Sl. The challenger sends the set of common parameters PP and public key PK to the adversary .(2)
Query: the adversary submits a messagem, a ring R, an index I, and the corresponding public key pki to the challenger . The challenger queries the corresponding secret key ski according to the index I and then calls the signature algorithm to generate a blinded signature Σi′ on m for the adversary .(3)
Challenge: the adversary submits a messagem, a ring R, and two public keys pkib∈R to the challenger for the signature query, where b∈0,1. The challenger chooses a random bit b∈0,1. Then, it uses the secret key skib and calls the signature algorithm to generate a blinded signature Σi′ on m and returns Σi′ to the adversary .(4)
Guess: the adversary outputs a bitb′ as a guess of the random bit b. He wins the game if b′=b.The advantage of the adversary in the above game is defined as follows:(5)AdvBRSanonymityA=Prb′=b−12.Blindness: it is a basic attribute of the blind ring signature, i.e., all members in the ring cannot know any information about the message to be signed. In other words, the attacker cannot distinguish the original signature of which message a blind ring signature comes from. For any polynomial-time adversary , the blind ring signature scheme satisfies the statistical blindness if his advantage in winning the following game with the challenger is negligible.(1)
Setup: assumen to be the system security parameter. The challenger calls the setup algorithm in the blind ring signature scheme to generate the set of common parameters PP. Then, according to the common parameters PP, the challenger calls the key generation algorithm to generate a set of public and secret keys (PK, SK) for the ring R=S1,S2,…,Sl. The challenger sends the set of common parameters PP and public key PK to the adversary .(2)
Challenge: the adversaryα chooses two different blinded messages μ0 and μ1, a subring R′∈R, and its corresponding public keys PK to send it to the challenger . The challenger chooses a random bit b∈0,1, then sets up a blind ring signature protocol taking μb and the ring R′ as input. The adversary chooses a signer Σj in the ring R′ to sign the hidden blinded message μb. Finally, the adversary obtains the unblinded signature Σb≠⊥, otherwise, it restarts this game.(3)
Guess: the adversary outputs a bitb′ as a guess of the random bit b. He wins the game if b′=b.The advantage of the adversary in the above game is defined as follows:(6)AdvBRSblindnessA=Prb′=b−12.One-more unforgeability: the one-more unforgeability property ensures that the attacker cannot successfully forge a new correct signature through multiple signature inquiries. For any polynomial-time adversary , the blind ring signature scheme satisfies the one-more unforgeability if his probability of winning the following game with the challenger is negligible.(1)
Setup: assumen to be the system security parameter. The challenger calls the setup algorithm in the blind ring signature scheme to generate the set of common parameters PP. Then, according to the common parameters PP, the challenger calls the Key generation algorithm to generate a set of public and secret keys (PK, SK) for the ring R=S1,S2,…,Sl. The challenger sends the set of common parameters PP and public key PK to the adversary . The secret key SK cannot be disclosed.(2)
Query: the adversary submits a messagem, a ring R, and its corresponding public keys PK. Then, adaptively, it makes multiple hash queries and blind ring signature queries to the challenger . The challenger must return the hash value Hm and signature value Σ of the corresponding message m to the adversary .(3)
Forge: the adversary uses the result of multiple queries to forgeΣ∗ of the target message m∗. One-more unforgeability requires that the pair m∗,Σ∗ has never passed the signature verification algorithm.


## 2.1. Some Related Theories of Lattice

Definition 1.
(Lattice [28]). Given a matrix B∈ℝm×n consists of a group of m-dimensional linearly independent vectors b1,…, b2, … bn. where m≥n Define lattice Λ generated by B as the set.(1)ΛB=Bx|x∈ℤn.
Given a prime numberq, a matrix A∈ℤqn×m, and e∈ℤqn, define some q-ary lattices.(2)ΛqA=y∈ℤm|y∈ATxmodq,x∈ℤn,Λq⊥A=y∈ℤm|Ay=0modq,ΛqeA=y∈ℤm|Ay=emodq.Definition 2.
(Discrete Gaussian Distribution [17]). Define Dv,σmz=ρv,σmz/ρv,σmℤm as a discrete Gaussian distribution, where ρv,σmz=1/2πσ2me−z−v2/2σ2 and ρv,σmℤm=∑z∈ℤmρσmz.Definition 3.
(SIS problem). Given a random matrixA∈ℤqn×m and parameters m, n, q, β, the SISq,n,m,β problem is to find a nonzero integer vector v∈ℤqm, such that Av=0modq and v≤β.Lemma 1.
(see [17]). For any v∈ℝm, σ>0, k>1, it satisfies the following:(3)Prz>kσm;z←Dσm≤kmem/21−k2.Lemma 2.
(see [17]). For any v∈ℤm, σ=αv, α>0, it satisfies the following:(4)PrDσmzDv,σmz<e12/α+1/2α2:z←Dσm>1−2−100.
More specially, ifα=12, σ=12v, then Dσmz/Dv,σmz<e1+1/288 with a probability of at least 1−2−100.Lemma 3.
(Rejection Sampling [17]).Select a random vector v∈ℤm and a real number σ=ωtlogm, given a subset V=v∈ℤm:v<t, and define on V a probability distribution h:V⟶ℝ. Then, there exists a constant M=O1 such that the outputs of the following two algorithms Α and B have a negligible statistical distance of ΔA,B=2−ωlogm/M:AlgorithmΑ: v←h, z←Dv,σm, output z,v with probability minDσmz/MDv,σmz,1.AlgorithmB: v←h, z←Dσm, output z,v with probability 1/M.
Moreover, the probability that the algorithmΑ outputs something is at least 1−2−ωlogm/M.
More specially, ifσ=αt for any α>0, then M=e12/α+1/2α2. The two algorithms Α and B have a negligible statistical distance off ΔA,B=2−100/M, and the probability that Α outputs something is at least 1−2−100/M.


## 2.2. Blind Ring Signature Model

### 2.2.1. System Model

The blind ring signature system model is composed of four parts called setup, key generation, signature, and verification [25]. The detailed steps are as follows:Setup. Input a security parametern and output public parameters PP.Key generation. Generate public keypk and secret key sk for each member of the ring R=S1,S2,…,Sl according to the input set of public parameters PP.Signature. The user ϒ submits a messagem and blinds it to μ before sending the message to the signer. Then, the ring R chooses a signer Σj, who takes the secret key skj. The signer Σj signs the message μ and generates a blinded signature Σ′. The user ϒ unblinds Σ′ and gets the real signature Σ.Verification. Output 1 or 0 according to the public parameters PP, messagem, signature Σ, and ring public keys PK=pkii∈l. The output of 1 means that the verification is passed, and 0 indicates that it is otherwise.


### 2.2.2. Security Model

The security model of the blind ring signature includes anonymity, blindness, and one-more unforgeability.Anonymity: the anonymity property ensures that the user cannot know which member of the ring was the real signer participating in the blind ring signature protocol. For any polynomial-time adversary, the blind ring signature scheme satisfies the anonymity under full key exposure if his advantage in winning the following game with the challenger is negligible.(1)
Setup: assumen to be the system security parameter. The challenger calls the setup algorithm in the blind ring signature scheme to generate the set of common parameters PP. Then, according to the common parameters PP, the challenger calls the key generation algorithm to generate a set of public and secret keys (PK, SK) for the ring R=S1,S2,…,Sl. The challenger sends the set of common parameters PP and public key PK to the adversary .(2)
Query: the adversary submits a messagem, a ring R, an index I, and the corresponding public key pki to the challenger . The challenger queries the corresponding secret key ski according to the index I and then calls the signature algorithm to generate a blinded signature Σi′ on m for the adversary .(3)
Challenge: the adversary submits a messagem, a ring R, and two public keys pkib∈R to the challenger for the signature query, where b∈0,1. The challenger chooses a random bit b∈0,1. Then, it uses the secret key skib and calls the signature algorithm to generate a blinded signature Σi′ on m and returns Σi′ to the adversary .(4)
Guess: the adversary outputs a bitb′ as a guess of the random bit b. He wins the game if b′=b.The advantage of the adversary in the above game is defined as follows:(5)AdvBRSanonymityA=Prb′=b−12.Blindness: it is a basic attribute of the blind ring signature, i.e., all members in the ring cannot know any information about the message to be signed. In other words, the attacker cannot distinguish the original signature of which message a blind ring signature comes from. For any polynomial-time adversary , the blind ring signature scheme satisfies the statistical blindness if his advantage in winning the following game with the challenger is negligible.(1)
Setup: assumen to be the system security parameter. The challenger calls the setup algorithm in the blind ring signature scheme to generate the set of common parameters PP. Then, according to the common parameters PP, the challenger calls the key generation algorithm to generate a set of public and secret keys (PK, SK) for the ring R=S1,S2,…,Sl. The challenger sends the set of common parameters PP and public key PK to the adversary .(2)
Challenge: the adversaryα chooses two different blinded messages μ0 and μ1, a subring R′∈R, and its corresponding public keys PK to send it to the challenger . The challenger chooses a random bit b∈0,1, then sets up a blind ring signature protocol taking μb and the ring R′ as input. The adversary chooses a signer Σj in the ring R′ to sign the hidden blinded message μb. Finally, the adversary obtains the unblinded signature Σb≠⊥, otherwise, it restarts this game.(3)
Guess: the adversary outputs a bitb′ as a guess of the random bit b. He wins the game if b′=b.The advantage of the adversary in the above game is defined as follows:(6)AdvBRSblindnessA=Prb′=b−12.One-more unforgeability: the one-more unforgeability property ensures that the attacker cannot successfully forge a new correct signature through multiple signature inquiries. For any polynomial-time adversary , the blind ring signature scheme satisfies the one-more unforgeability if his probability of winning the following game with the challenger is negligible.(1)
Setup: assumen to be the system security parameter. The challenger calls the setup algorithm in the blind ring signature scheme to generate the set of common parameters PP. Then, according to the common parameters PP, the challenger calls the Key generation algorithm to generate a set of public and secret keys (PK, SK) for the ring R=S1,S2,…,Sl. The challenger sends the set of common parameters PP and public key PK to the adversary . The secret key SK cannot be disclosed.(2)
Query: the adversary submits a messagem, a ring R, and its corresponding public keys PK. Then, adaptively, it makes multiple hash queries and blind ring signature queries to the challenger . The challenger must return the hash value Hm and signature value Σ of the corresponding message m to the adversary .(3)
Forge: the adversary uses the result of multiple queries to forgeΣ∗ of the target message m∗. One-more unforgeability requires that the pair m∗,Σ∗ has never passed the signature verification algorithm.


## 2.2.1. System Model

The blind ring signature system model is composed of four parts called setup, key generation, signature, and verification [25]. The detailed steps are as follows:Setup. Input a security parametern and output public parameters PP.Key generation. Generate public keypk and secret key sk for each member of the ring R=S1,S2,…,Sl according to the input set of public parameters PP.Signature. The user ϒ submits a messagem and blinds it to μ before sending the message to the signer. Then, the ring R chooses a signer Σj, who takes the secret key skj. The signer Σj signs the message μ and generates a blinded signature Σ′. The user ϒ unblinds Σ′ and gets the real signature Σ.Verification. Output 1 or 0 according to the public parameters PP, messagem, signature Σ, and ring public keys PK=pkii∈l. The output of 1 means that the verification is passed, and 0 indicates that it is otherwise.


## 2.2.2. Security Model

The security model of the blind ring signature includes anonymity, blindness, and one-more unforgeability.Anonymity: the anonymity property ensures that the user cannot know which member of the ring was the real signer participating in the blind ring signature protocol. For any polynomial-time adversary, the blind ring signature scheme satisfies the anonymity under full key exposure if his advantage in winning the following game with the challenger is negligible.(1)
Setup: assumen to be the system security parameter. The challenger calls the setup algorithm in the blind ring signature scheme to generate the set of common parameters PP. Then, according to the common parameters PP, the challenger calls the key generation algorithm to generate a set of public and secret keys (PK, SK) for the ring R=S1,S2,…,Sl. The challenger sends the set of common parameters PP and public key PK to the adversary .(2)
Query: the adversary submits a messagem, a ring R, an index I, and the corresponding public key pki to the challenger . The challenger queries the corresponding secret key ski according to the index I and then calls the signature algorithm to generate a blinded signature Σi′ on m for the adversary .(3)
Challenge: the adversary submits a messagem, a ring R, and two public keys pkib∈R to the challenger for the signature query, where b∈0,1. The challenger chooses a random bit b∈0,1. Then, it uses the secret key skib and calls the signature algorithm to generate a blinded signature Σi′ on m and returns Σi′ to the adversary .(4)
Guess: the adversary outputs a bitb′ as a guess of the random bit b. He wins the game if b′=b.The advantage of the adversary in the above game is defined as follows:(5)AdvBRSanonymityA=Prb′=b−12.Blindness: it is a basic attribute of the blind ring signature, i.e., all members in the ring cannot know any information about the message to be signed. In other words, the attacker cannot distinguish the original signature of which message a blind ring signature comes from. For any polynomial-time adversary , the blind ring signature scheme satisfies the statistical blindness if his advantage in winning the following game with the challenger is negligible.(1)
Setup: assumen to be the system security parameter. The challenger calls the setup algorithm in the blind ring signature scheme to generate the set of common parameters PP. Then, according to the common parameters PP, the challenger calls the key generation algorithm to generate a set of public and secret keys (PK, SK) for the ring R=S1,S2,…,Sl. The challenger sends the set of common parameters PP and public key PK to the adversary .(2)
Challenge: the adversaryα chooses two different blinded messages μ0 and μ1, a subring R′∈R, and its corresponding public keys PK to send it to the challenger . The challenger chooses a random bit b∈0,1, then sets up a blind ring signature protocol taking μb and the ring R′ as input. The adversary chooses a signer Σj in the ring R′ to sign the hidden blinded message μb. Finally, the adversary obtains the unblinded signature Σb≠⊥, otherwise, it restarts this game.(3)
Guess: the adversary outputs a bitb′ as a guess of the random bit b. He wins the game if b′=b.The advantage of the adversary in the above game is defined as follows:(6)AdvBRSblindnessA=Prb′=b−12.One-more unforgeability: the one-more unforgeability property ensures that the attacker cannot successfully forge a new correct signature through multiple signature inquiries. For any polynomial-time adversary , the blind ring signature scheme satisfies the one-more unforgeability if his probability of winning the following game with the challenger is negligible.(1)
Setup: assumen to be the system security parameter. The challenger calls the setup algorithm in the blind ring signature scheme to generate the set of common parameters PP. Then, according to the common parameters PP, the challenger calls the Key generation algorithm to generate a set of public and secret keys (PK, SK) for the ring R=S1,S2,…,Sl. The challenger sends the set of common parameters PP and public key PK to the adversary . The secret key SK cannot be disclosed.(2)
Query: the adversary submits a messagem, a ring R, and its corresponding public keys PK. Then, adaptively, it makes multiple hash queries and blind ring signature queries to the challenger . The challenger must return the hash value Hm and signature value Σ of the corresponding message m to the adversary .(3)
Forge: the adversary uses the result of multiple queries to forgeΣ∗ of the target message m∗. One-more unforgeability requires that the pair m∗,Σ∗ has never passed the signature verification algorithm.


## 3. Proposed Blind Ring Signature Algorithm

Our proposed blind ring signature algorithm includes five parts: key generation, message blinded, signature, unblind, and verification.Key generation. Assumen is a system security parameter. We generate the common parameter PP, which has been selected by the same methodology of Li’s scheme [22]. The independent public and secret key pairs Ai,Si for each signer Si,i∈l of the ring R=S1,S2,…,Sl are generated using the method described in Ducas’s scheme [18], where Ai∈ℤ2qn×m, Si∈ℤ2qm×n, and satisfying AiSi=qInmod2q.Message blinded: the signer of the ringR first computes a commitment to the user ϒ. Then, the user ϒ hides the original message m by running the message blinded algorithm and outputting the blinded messageμ. The detail is shown in algorithm 1.Algorithm 1: Message blinded algorithm.
Input: system public parameters PP, original messagem, public keys Aii∈l of the ring R.Output: blinded messageμ.Step 1: choose a set of random vectorsrii∈l from the bimodal Gaussian distribution Dσ2m.Step 2: compute the commitmentx=∑i∈lAirimod2q.Step 3: choose a set of blind factorsyii∈l from the bimodal Gaussian distribution Dσ3m.Step 4: computew=∑i∈lAiyimod2q.Step 5: computec=Hx+wmod2q,m.Step 6: choose a random bitt←0,1n.Step 7: computeμ=−1tc.Step 8: output the blinded messageμ with probability minDσ1mμ/M1Dc,σ1mμ,1.Signature: the ringR chooses a signer Σj. Σj calls the signature algorithm after receiving the blinded message μ and then outputs the blinded signature Σ′. The detail is shown in algorithm 2.Algorithm 2: Signature algorithm.
Input: system public parameters PP, blinded messageμ, the secret key Sj of the signer Σj.Output: blinded signatureΣ′=zii∈l.Step 1: for alli∈l/j: compute zi=ri; for j: compute zj=rj+Sjμ.Step 2: outputzj with probability minDσ2mzj/M2DSjμ,σ2mzj,1.Step 3: output the blinded signatureΣ′=zii∈l.Unblind: the user ϒ runs the unblind algorithm after receiving the blinded signatureΣ′ and then outputs the real blind ring signature Σ. The detail is shown in algorithm 3.Algorithm 3: Unblind algorithm.
Input: system public parameters PP, blinded signatureΣ′=zii∈l.Output: blind ring signatureΣ=eii∈l,c.Step 1: for alli∈l: compute ei=yi+zi.Step 2: outputei with probability minDσ3mei/M3Dyi,σ3mei,1.Step 3: output the real blind ring signatureΣ=eii∈l,c.Verification: the verifier runs the verification algorithm after receiving the original messagem and bling ring signature Σ. Then, he outputs 1 if the verification is passed. It is 0, otherwise. The detail is shown in algorithm 4.Algorithm 4: Verification algorithm.
Input: system public parameters PP, original messagem, public keys Aii∈l of the ring R, blind ring signature Σ=eii∈l,c.Output: 1 or 0.Step 1: verify thatei≤ησ3m for all i∈l.Step 2: verify thatc=H∑i∈lAiei+qcmod2q,m.Step 3: output 1 if the verification in steps 1 and 2 passed and 0 otherwise.


## 4. Correctness and Security Proof

### 4.1. Correctness

For the generated blind ring signatureΣ=eii∈l,c, eii∈l are sampled from the distribution Dσ3m, and according to Lemma 1, ei≤ησ3m is established with an overwhelming probability for all i∈l. Therefore, the correctness is to prove ∑i∈lAiei+qc=x+wmod2q. The proof of the equation is as follows:(7)∑i∈lAiei+qc=∑i∈lAiyi+∑i∈lAizi+qc=∑i∈l\jAizi+Ajzj+∑i∈lAiyi+qc=∑i∈l\jAiri+Ajrj+Sjμ+∑i∈lAiyi+qc=∑i∈lAiri+AjSjμ+∑i∈lAiyi+qc=x+w+q−1tInc+qc=x+wmod2q.


### 4.2. Security Proof

#### 4.2.1. Anonymity

The adversary submits a messagem and two users Ui0,Ui1∈R to the challenger for a signature query. The challenger randomly chooses a bit b∈0,1 and calls the message blinded algorithm and signature algorithm to generate a blinded signature Σib′=z1,…,zib,…,zl on m, where zib=rib+Sibμ, output probability minDσ2mzib/M2DSibμ,σ2mzib,1, and zi=ri←Dσ2m for all i∈l/ib. Then, the challenger returns Σi′ to the adversary . Let two random variables X0 and X1 represent the blinded signatures generated by the user Ui0 and Ui1.Suppose that the adversary obtains the blinded signatureΣib′=z1,…,zib,…,zl by sampling each zi from Dσ2m with probability 1/M2, let the random variable Y represent the blinded signature generated by this way. The statistical distance [28] between X0 and Y satisfies ΔX0,Y≤2−ωlogm/M2, and the statistical distance between X1 and Y satisfies ΔX1,Y≤2−ωlogm/M2. Therefore, we have the following:(8)ΔX0,X1≤ΔX0,Y+ΔX1,Y≤21−ωlogmM2.The statistical distance betweenX1 and X1 is negligible. Therefore, the distribution of blinded signatures Σi0′ and Σi1′ is indistinguishable. The proposed scheme satisfies anonymity.


#### 4.2.2. Blindness

The adversary submits two different blinded messages,μ0 and μ1, and interacts with two different users Ui0 and Ui1. The adversary and the challenger only choose one of the two users for establishing an interactive blind ring signature protocol. It should be noted that the adversary does not know the user’s information who is interacting with him, i.e., we can only prove that the outputs, i.e., the two blind messages μ0 and μ1, are indistinguishable, and the corresponding blind ring signature Σi0 and Σi1 are also indistinguishable, where b∈0,1 and Σib=e1,…eib,…,el.For two blinded messages,μ0 and μ1, because of the construction μ=−1tc and the output probability minDσ1mμ/M1Dc,σ1mμ,1, we can get that μ0 and μ1 are sampled from the same distribution Dσ1m. Therefore, the statistical distance between μ0 and μ1 satisfies Δμ0,μ1=0 and they are indistinguishable. For two blind ring signatures Σi0 and Σi1, because ei=yi+zi for all i∈l and the output probability minDσ3mei/M3Dyi,σ3mei,1, we can get Σi0 and Σi1 are sampled from the same distribution Dσ3m. Therefore, the statistical distance between Σi0 and Σi1 satisfies ΔΣi0,Σi1=0, and they are indistinguishable. The proposed scheme satisfies blindness.


#### 4.2.3. One-More Unforgeability

Theorem 1.
If an adversaryα can successfully give the effective forgery, there will be existing a polynomial-time algorithm Φ that can solve the SISq,n,lm,β problem with non-negligible probability.Proof.
We will prove the one-more unforgeability of the scheme by the simulation game between challenger and adversary . The simulation game controlled by challenger is executed as follows:Setup: challenger builds two initial empty lists, List 1 and List 2, respectively, to store the hash valueHm and signature value Σ=eii∈l,c of message m. Then, adversary will make hash queries and signature queries to challenger.Hash queries:The adversary sends a hash query for message m to challenger . Challenger checks List 1, where List 1 consists of the pair m,Hm. If the queried message m is in List 1, challenger sends the corresponding Hm to adversary. If not, challenger will compute a new Hm, restore m,Hm into List 1, and send it to adversary.Signature queries:The adversary sends a signature query for message m to challenger. hThe challenger checks List 2, where List 2 consists of the pair m,Σ=eii∈l,c. If the queried message m is in List 2, challenger sends the corresponding signature value Σ=eii∈l,c to adversary . If not, challenger will generate a new signature, restore the new pair m,Σ=eii∈l,c into List 2, and send it to adversary .Forge: supposecj is a result of a hash query made by the adversary . Then, we can get the following:(9)H∑i∈lAiei∗+qcjmod2q,m∗=H∑i∈lAiei′+qcjmod2q,m′.
For two different blind ring signature pairs,m∗,Σ∗=ei∗i∈l,cj and m′,Σ′=ei′i∈l,cj. We can find a hash collision if there exists inequality in the input of the hash function H on both sides of the equal sign of equation (10). Therefore, we can derive that ∑i∈lAiei∗+qcj=∑i∈lAiei′+qcjmod2q, m∗=m′ with an overwhelming probability. Further simplification can be obtained as ∑i∈lAiei∗−ei′=0mod2q. Let ei=ei∗−ei′, and we have the following:(10)∑i∈lAiei=A1|A2|…|Ale1T,e2T,…,elTT.
LetA=A1|A2|⋯|Al∈ℤn×lm and e=e1T,e2T,…,elTT∈ℤlm. Then, we have Ae=0mod2q.As the forgery of the adversary is valid, there exists at least a bit i such that ei∗≠ei′ and ei∗−ei′≠0modq with an overwhelming probability, i.e., we can get e≠0modq with great probability. Finally, we say that we can successfully solve the SIS problem. The detailed proving process is as follows:
Suppose thatcj is a result of a hash query made by the adversary , and we can get a new valid forgery Σ′=ei′i∈l,cj′ for message m∗ and ring R∗. We have cj′≠cj and ∑i∈lAiei∗+qcj=∑i∈lAiei′+qcj′ with a non-negligible probability according to the Forking lemma [29]. Let ei=ei∗−ei′, A=A1A2⋯|Al and e=e1T,e2T,…,elTT. We have Ae=qcj′−cjmod2q. Because cj′≠cj and qcj′−cj=0modq, we can derive e≠0mod2q and Ae=0modq. In addition, as ei∗=ei′≤ησ3m for all i∈l, according to algorithm 4, we have ei=ei∗−ej′≤ei′+ei′=2ησ3m. Then, it satisfies e=∑i∈lei≤2lησ3m. Therefore, e is a solution to the SISq,n,lm,β problem with β=2lησ3m, where Ae=0modq and e≠0modq. The proposed scheme satisfies the one-more unforgeability.


## 4.1. Correctness

For the generated blind ring signatureΣ=eii∈l,c, eii∈l are sampled from the distribution Dσ3m, and according to Lemma 1, ei≤ησ3m is established with an overwhelming probability for all i∈l. Therefore, the correctness is to prove ∑i∈lAiei+qc=x+wmod2q. The proof of the equation is as follows:(7)∑i∈lAiei+qc=∑i∈lAiyi+∑i∈lAizi+qc=∑i∈l\jAizi+Ajzj+∑i∈lAiyi+qc=∑i∈l\jAiri+Ajrj+Sjμ+∑i∈lAiyi+qc=∑i∈lAiri+AjSjμ+∑i∈lAiyi+qc=x+w+q−1tInc+qc=x+wmod2q.


## 4.2. Security Proof

### 4.2.1. Anonymity

The adversary submits a messagem and two users Ui0,Ui1∈R to the challenger for a signature query. The challenger randomly chooses a bit b∈0,1 and calls the message blinded algorithm and signature algorithm to generate a blinded signature Σib′=z1,…,zib,…,zl on m, where zib=rib+Sibμ, output probability minDσ2mzib/M2DSibμ,σ2mzib,1, and zi=ri←Dσ2m for all i∈l/ib. Then, the challenger returns Σi′ to the adversary . Let two random variables X0 and X1 represent the blinded signatures generated by the user Ui0 and Ui1.Suppose that the adversary obtains the blinded signatureΣib′=z1,…,zib,…,zl by sampling each zi from Dσ2m with probability 1/M2, let the random variable Y represent the blinded signature generated by this way. The statistical distance [28] between X0 and Y satisfies ΔX0,Y≤2−ωlogm/M2, and the statistical distance between X1 and Y satisfies ΔX1,Y≤2−ωlogm/M2. Therefore, we have the following:(8)ΔX0,X1≤ΔX0,Y+ΔX1,Y≤21−ωlogmM2.The statistical distance betweenX1 and X1 is negligible. Therefore, the distribution of blinded signatures Σi0′ and Σi1′ is indistinguishable. The proposed scheme satisfies anonymity.


### 4.2.2. Blindness

The adversary submits two different blinded messages,μ0 and μ1, and interacts with two different users Ui0 and Ui1. The adversary and the challenger only choose one of the two users for establishing an interactive blind ring signature protocol. It should be noted that the adversary does not know the user’s information who is interacting with him, i.e., we can only prove that the outputs, i.e., the two blind messages μ0 and μ1, are indistinguishable, and the corresponding blind ring signature Σi0 and Σi1 are also indistinguishable, where b∈0,1 and Σib=e1,…eib,…,el.For two blinded messages,μ0 and μ1, because of the construction μ=−1tc and the output probability minDσ1mμ/M1Dc,σ1mμ,1, we can get that μ0 and μ1 are sampled from the same distribution Dσ1m. Therefore, the statistical distance between μ0 and μ1 satisfies Δμ0,μ1=0 and they are indistinguishable. For two blind ring signatures Σi0 and Σi1, because ei=yi+zi for all i∈l and the output probability minDσ3mei/M3Dyi,σ3mei,1, we can get Σi0 and Σi1 are sampled from the same distribution Dσ3m. Therefore, the statistical distance between Σi0 and Σi1 satisfies ΔΣi0,Σi1=0, and they are indistinguishable. The proposed scheme satisfies blindness.


### 4.2.3. One-More Unforgeability

Theorem 1.
If an adversaryα can successfully give the effective forgery, there will be existing a polynomial-time algorithm Φ that can solve the SISq,n,lm,β problem with non-negligible probability.Proof.
We will prove the one-more unforgeability of the scheme by the simulation game between challenger and adversary . The simulation game controlled by challenger is executed as follows:Setup: challenger builds two initial empty lists, List 1 and List 2, respectively, to store the hash valueHm and signature value Σ=eii∈l,c of message m. Then, adversary will make hash queries and signature queries to challenger.Hash queries:The adversary sends a hash query for message m to challenger . Challenger checks List 1, where List 1 consists of the pair m,Hm. If the queried message m is in List 1, challenger sends the corresponding Hm to adversary. If not, challenger will compute a new Hm, restore m,Hm into List 1, and send it to adversary.Signature queries:The adversary sends a signature query for message m to challenger. hThe challenger checks List 2, where List 2 consists of the pair m,Σ=eii∈l,c. If the queried message m is in List 2, challenger sends the corresponding signature value Σ=eii∈l,c to adversary . If not, challenger will generate a new signature, restore the new pair m,Σ=eii∈l,c into List 2, and send it to adversary .Forge: supposecj is a result of a hash query made by the adversary . Then, we can get the following:(9)H∑i∈lAiei∗+qcjmod2q,m∗=H∑i∈lAiei′+qcjmod2q,m′.
For two different blind ring signature pairs,m∗,Σ∗=ei∗i∈l,cj and m′,Σ′=ei′i∈l,cj. We can find a hash collision if there exists inequality in the input of the hash function H on both sides of the equal sign of equation (10). Therefore, we can derive that ∑i∈lAiei∗+qcj=∑i∈lAiei′+qcjmod2q, m∗=m′ with an overwhelming probability. Further simplification can be obtained as ∑i∈lAiei∗−ei′=0mod2q. Let ei=ei∗−ei′, and we have the following:(10)∑i∈lAiei=A1|A2|…|Ale1T,e2T,…,elTT.
LetA=A1|A2|⋯|Al∈ℤn×lm and e=e1T,e2T,…,elTT∈ℤlm. Then, we have Ae=0mod2q.As the forgery of the adversary is valid, there exists at least a bit i such that ei∗≠ei′ and ei∗−ei′≠0modq with an overwhelming probability, i.e., we can get e≠0modq with great probability. Finally, we say that we can successfully solve the SIS problem. The detailed proving process is as follows:
Suppose thatcj is a result of a hash query made by the adversary , and we can get a new valid forgery Σ′=ei′i∈l,cj′ for message m∗ and ring R∗. We have cj′≠cj and ∑i∈lAiei∗+qcj=∑i∈lAiei′+qcj′ with a non-negligible probability according to the Forking lemma [29]. Let ei=ei∗−ei′, A=A1A2⋯|Al and e=e1T,e2T,…,elTT. We have Ae=qcj′−cjmod2q. Because cj′≠cj and qcj′−cj=0modq, we can derive e≠0mod2q and Ae=0modq. In addition, as ei∗=ei′≤ησ3m for all i∈l, according to algorithm 4, we have ei=ei∗−ej′≤ei′+ei′=2ησ3m. Then, it satisfies e=∑i∈lei≤2lησ3m. Therefore, e is a solution to the SISq,n,lm,β problem with β=2lησ3m, where Ae=0modq and e≠0modq. The proposed scheme satisfies the one-more unforgeability.


## 4.2.1. Anonymity

The adversary submits a messagem and two users Ui0,Ui1∈R to the challenger for a signature query. The challenger randomly chooses a bit b∈0,1 and calls the message blinded algorithm and signature algorithm to generate a blinded signature Σib′=z1,…,zib,…,zl on m, where zib=rib+Sibμ, output probability minDσ2mzib/M2DSibμ,σ2mzib,1, and zi=ri←Dσ2m for all i∈l/ib. Then, the challenger returns Σi′ to the adversary . Let two random variables X0 and X1 represent the blinded signatures generated by the user Ui0 and Ui1.Suppose that the adversary obtains the blinded signatureΣib′=z1,…,zib,…,zl by sampling each zi from Dσ2m with probability 1/M2, let the random variable Y represent the blinded signature generated by this way. The statistical distance [28] between X0 and Y satisfies ΔX0,Y≤2−ωlogm/M2, and the statistical distance between X1 and Y satisfies ΔX1,Y≤2−ωlogm/M2. Therefore, we have the following:(8)ΔX0,X1≤ΔX0,Y+ΔX1,Y≤21−ωlogmM2.The statistical distance betweenX1 and X1 is negligible. Therefore, the distribution of blinded signatures Σi0′ and Σi1′ is indistinguishable. The proposed scheme satisfies anonymity.


## 4.2.2. Blindness

The adversary submits two different blinded messages,μ0 and μ1, and interacts with two different users Ui0 and Ui1. The adversary and the challenger only choose one of the two users for establishing an interactive blind ring signature protocol. It should be noted that the adversary does not know the user’s information who is interacting with him, i.e., we can only prove that the outputs, i.e., the two blind messages μ0 and μ1, are indistinguishable, and the corresponding blind ring signature Σi0 and Σi1 are also indistinguishable, where b∈0,1 and Σib=e1,…eib,…,el.For two blinded messages,μ0 and μ1, because of the construction μ=−1tc and the output probability minDσ1mμ/M1Dc,σ1mμ,1, we can get that μ0 and μ1 are sampled from the same distribution Dσ1m. Therefore, the statistical distance between μ0 and μ1 satisfies Δμ0,μ1=0 and they are indistinguishable. For two blind ring signatures Σi0 and Σi1, because ei=yi+zi for all i∈l and the output probability minDσ3mei/M3Dyi,σ3mei,1, we can get Σi0 and Σi1 are sampled from the same distribution Dσ3m. Therefore, the statistical distance between Σi0 and Σi1 satisfies ΔΣi0,Σi1=0, and they are indistinguishable. The proposed scheme satisfies blindness.


## 4.2.3. One-More Unforgeability

Theorem 1.
If an adversaryα can successfully give the effective forgery, there will be existing a polynomial-time algorithm Φ that can solve the SISq,n,lm,β problem with non-negligible probability.Proof.
We will prove the one-more unforgeability of the scheme by the simulation game between challenger and adversary . The simulation game controlled by challenger is executed as follows:Setup: challenger builds two initial empty lists, List 1 and List 2, respectively, to store the hash valueHm and signature value Σ=eii∈l,c of message m. Then, adversary will make hash queries and signature queries to challenger.Hash queries:The adversary sends a hash query for message m to challenger . Challenger checks List 1, where List 1 consists of the pair m,Hm. If the queried message m is in List 1, challenger sends the corresponding Hm to adversary. If not, challenger will compute a new Hm, restore m,Hm into List 1, and send it to adversary.Signature queries:The adversary sends a signature query for message m to challenger. hThe challenger checks List 2, where List 2 consists of the pair m,Σ=eii∈l,c. If the queried message m is in List 2, challenger sends the corresponding signature value Σ=eii∈l,c to adversary . If not, challenger will generate a new signature, restore the new pair m,Σ=eii∈l,c into List 2, and send it to adversary .Forge: supposecj is a result of a hash query made by the adversary . Then, we can get the following:(9)H∑i∈lAiei∗+qcjmod2q,m∗=H∑i∈lAiei′+qcjmod2q,m′.
For two different blind ring signature pairs,m∗,Σ∗=ei∗i∈l,cj and m′,Σ′=ei′i∈l,cj. We can find a hash collision if there exists inequality in the input of the hash function H on both sides of the equal sign of equation (10). Therefore, we can derive that ∑i∈lAiei∗+qcj=∑i∈lAiei′+qcjmod2q, m∗=m′ with an overwhelming probability. Further simplification can be obtained as ∑i∈lAiei∗−ei′=0mod2q. Let ei=ei∗−ei′, and we have the following:(10)∑i∈lAiei=A1|A2|…|Ale1T,e2T,…,elTT.
LetA=A1|A2|⋯|Al∈ℤn×lm and e=e1T,e2T,…,elTT∈ℤlm. Then, we have Ae=0mod2q.As the forgery of the adversary is valid, there exists at least a bit i such that ei∗≠ei′ and ei∗−ei′≠0modq with an overwhelming probability, i.e., we can get e≠0modq with great probability. Finally, we say that we can successfully solve the SIS problem. The detailed proving process is as follows:
Suppose thatcj is a result of a hash query made by the adversary , and we can get a new valid forgery Σ′=ei′i∈l,cj′ for message m∗ and ring R∗. We have cj′≠cj and ∑i∈lAiei∗+qcj=∑i∈lAiei′+qcj′ with a non-negligible probability according to the Forking lemma [29]. Let ei=ei∗−ei′, A=A1A2⋯|Al and e=e1T,e2T,…,elTT. We have Ae=qcj′−cjmod2q. Because cj′≠cj and qcj′−cj=0modq, we can derive e≠0mod2q and Ae=0modq. In addition, as ei∗=ei′≤ησ3m for all i∈l, according to algorithm 4, we have ei=ei∗−ej′≤ei′+ei′=2ησ3m. Then, it satisfies e=∑i∈lei≤2lησ3m. Therefore, e is a solution to the SISq,n,lm,β problem with β=2lησ3m, where Ae=0modq and e≠0modq. The proposed scheme satisfies the one-more unforgeability.


## 5. The Completely Anonymous Blockchain Transaction System

In this section, we construct a completely anonymous blockchain transaction system based on the proposed lattice-based blind ring signature algorithm. Assume a blockchain transaction is required between Alice and Bob, and stipulate that Alice transfers accounts to Bob. The transaction between Alice and Bob is recorded in a ledger and packaged into the blockchain. The overall schematic diagram of the anonymous blockchain transaction system is shown in Figure1. The detailed process mainly includes the following five steps:Key generation: firstly, Alice constructs a ringR composed of multiple members and calls the key generation algorithm and then gets the public and secret key pair pkA,skA of ring R, where pkA=pk1,…,pka,…pkn is a set of ring public keys.Transaction generation: Bob initiates a transaction request with Alice and generates a piece of transaction informationm. Bob and Alice run the blind ring signature algorithm in Section 3. Then, Bob selects the blind factor and utilizes the ring public keys pkA of Alice to blind the transaction information m to μ. Alice uses the secret key skA to generate a signature Σ′ for blinded transaction information μ. Bob obtains the real blind ring signature Σ of the transaction information m using the unblind algorithm. Finally, Bob generates a new transaction Tx utilizing the ring public keys pkA and the blind ring signature Σ of the transaction information m.Transaction authentication: Bob broadcasts the transactionTx to the blockchain network, and the miner nodes in the blockchain use the ring public keys pkA of Alice to verify whether the blind ring signature Σ is correct. It indicates that the transaction is correct if the verification passes, and then, it encapsulates the transaction Tx in a new block. Otherwise, the transaction will be discarded.Network-wide consensus. The miners broadcast communication through the consensus mechanism and agree to add a new block containing the transaction to the blockchain. Meanwhile, miners who create the new block will be rewarded by the system.Transaction completion: after blockchain miners have successfully reached the network-wide consensus on the transaction, Bob can consume the transfer received from Alice under the above steps.Figure 1
The completely anonymous blockchain transaction system.The proposed transaction system has the characteristic of complete anonymity that can hide the identity privacy information of both parties participating in a blockchain transaction. For the internal attackers involved in the transaction, based on the blind signature feature, as the transaction initiator performs blind processing on the transaction information, the internal attacker cannot associate any veritable identity of the initiator through the transaction information. Therefore, for the input of each transaction, the internal attacker cannot trace whether it was initiated by the same user. For the external attackers not involved in the transaction, based on the ring signature feature, as the signature of the transaction is verified through ring public keys rather than a unique public key, it is impossible to determine the specific public key associated with the real signer. Therefore, for the output of any two transactions, the external attacker cannot link to the same transaction user. Moreover, the signature algorithm adopted in this system is based on the SIS problem, which cannot be availably solved by existing quantum computing algorithms. Therefore, the system satisfies antiquantum computing security.


## 6. Performance Evaluation

In this section, we make an evaluation on the performance of the proposed signature algorithm by comparing with other similar literature schemes, including signature and verification algorithm latency, sampling method, the size of the signature, and secret and public keys. Firstly, we give some parameter settings, and then, the comparison results will be presented through theoretical analysis and simulation experiments.


### 6.1. Parameters Setting

The relevant public parameters of our scheme are set as shown in Table1, which are the same as in [17]. We select the security level k=128 bits and corresponding challenge size κ=28 as an example. Meanwhile, the computational complexity of the SIS problem is maintained by reasonably selecting the parameter n, m, q, which can guarantee the security of public key and secret key. Moreover, the correctness error of the reject sample will be at the most 2−100, which requires that σ1=12v=12κ and M1=e12κ/σ1+κ/2σ12=e1+1/288≈2.72. Then, M2 and M3 will be derived by the same method.Table 1
Public parameters setting.
Parameter PPDefinitionExampleNSecurity parameter512lNumber of ring members10Qpolyn, prime227mm=nlogq13824HHash functionH:0,1∗⟶c∈−1,0,1k:c1≤κ-k and κIn the hash functionH and 2κ⋅Ckκ≥2100k=128,κ=28η1.1,1.31.1σ112κ63σ212ησ1mk220σ312ησ2m230M1=M2=M3exp12κ/σ1+κ/2σ122.72Secret key sizelmnlog2q236 MBPublic key sizelmnlog2q236 MBSignature sizelmlog12σ3+κ0.55 MB


### 6.2. Comparison with Other Similar Schemes

We carry out the simulation experiment of efficiency comparison by utilizing MATLAB R2021b in the environment of Windows 11 with Intel(R) Core(TM) i7-10510U CPU 1.80 GHz and 16 G RAM. Assume that the same parametersn,m,q,l,k,κ, set according to Table 1, are utilized in each of these schemes, the detailed keys and signature size comparison results are shown in Table 2. We choose the parameters l=10, q=227, k=128 and κ=28 for the simulation experiment. Then, we compute the public key size, secret key size, and signature size for the different security parameter n, such as 80, 112, 128, 192, 256, 512. The comparison results of the public key size, secret key size, and signature size are separately shown in Figures 2–4. It can be seen from the experimental results that the size of the signature, secret, and public keys of our proposed scheme are all smaller than others [25, 30]. Moreover, we generate the public and secret keys without trapdoor sampling, which improves sampling efficiency and saves more time for performance.Table 2
Keys and signature size comparison.
SchemePublic key sizeSecret key sizeSignature sizeSampling methodWang et al. [30]6lmnlogql6m2logq6lmlogq+lTrapdoor samplingLe et al. [25]6lmnlogq6lmnlogq6lmlog12σ3+n+κTrapdoor samplingOur schemelmnlog2qlmnlog2qlmlog12σ3+κWithout trapdoor samplingFigure 2
The comparison of public key size.Figure 3
The comparison of secret key size.Figure 4
The comparison of signature size.Next, the results of the signature and verification algorithm latency comparison are shown in Table3. The signature algorithm latency of the blind ring signature scheme includes message blinded, signature, and unblind algorithm latency. Here, some notations, such as TMul, THash, TRS, and TCom, should be explained. The latency for multiplication is represented by TMul. The latency for the Hash operation is represented by THash. The latency for rejection sampling operation is represented by TRS. The latency for commitment function calculation is represented by TCom. As can be seen from Table 3, our proposed blind ring signature scheme has lower signature and verification algorithm latency than the other similar scheme [25].Table 3
Latency comparison.
SchemeSignature algorithm latencyVerification algorithm latencyLe et al. [25]4l+1TMul+2THash+3TRS+TComl+1TMul+THash+TComOur scheme2l+1TMul+THash+2TRSl+1TMul+THash


## 6.1. Parameters Setting

The relevant public parameters of our scheme are set as shown in Table1, which are the same as in [17]. We select the security level k=128 bits and corresponding challenge size κ=28 as an example. Meanwhile, the computational complexity of the SIS problem is maintained by reasonably selecting the parameter n, m, q, which can guarantee the security of public key and secret key. Moreover, the correctness error of the reject sample will be at the most 2−100, which requires that σ1=12v=12κ and M1=e12κ/σ1+κ/2σ12=e1+1/288≈2.72. Then, M2 and M3 will be derived by the same method.Table 1
Public parameters setting.
Parameter PPDefinitionExampleNSecurity parameter512lNumber of ring members10Qpolyn, prime227mm=nlogq13824HHash functionH:0,1∗⟶c∈−1,0,1k:c1≤κ-k and κIn the hash functionH and 2κ⋅Ckκ≥2100k=128,κ=28η1.1,1.31.1σ112κ63σ212ησ1mk220σ312ησ2m230M1=M2=M3exp12κ/σ1+κ/2σ122.72Secret key sizelmnlog2q236 MBPublic key sizelmnlog2q236 MBSignature sizelmlog12σ3+κ0.55 MB


## 6.2. Comparison with Other Similar Schemes

We carry out the simulation experiment of efficiency comparison by utilizing MATLAB R2021b in the environment of Windows 11 with Intel(R) Core(TM) i7-10510U CPU 1.80 GHz and 16 G RAM. Assume that the same parametersn,m,q,l,k,κ, set according to Table 1, are utilized in each of these schemes, the detailed keys and signature size comparison results are shown in Table 2. We choose the parameters l=10, q=227, k=128 and κ=28 for the simulation experiment. Then, we compute the public key size, secret key size, and signature size for the different security parameter n, such as 80, 112, 128, 192, 256, 512. The comparison results of the public key size, secret key size, and signature size are separately shown in Figures 2–4. It can be seen from the experimental results that the size of the signature, secret, and public keys of our proposed scheme are all smaller than others [25, 30]. Moreover, we generate the public and secret keys without trapdoor sampling, which improves sampling efficiency and saves more time for performance.Table 2
Keys and signature size comparison.
SchemePublic key sizeSecret key sizeSignature sizeSampling methodWang et al. [30]6lmnlogql6m2logq6lmlogq+lTrapdoor samplingLe et al. [25]6lmnlogq6lmnlogq6lmlog12σ3+n+κTrapdoor samplingOur schemelmnlog2qlmnlog2qlmlog12σ3+κWithout trapdoor samplingFigure 2
The comparison of public key size.Figure 3
The comparison of secret key size.Figure 4
The comparison of signature size.Next, the results of the signature and verification algorithm latency comparison are shown in Table3. The signature algorithm latency of the blind ring signature scheme includes message blinded, signature, and unblind algorithm latency. Here, some notations, such as TMul, THash, TRS, and TCom, should be explained. The latency for multiplication is represented by TMul. The latency for the Hash operation is represented by THash. The latency for rejection sampling operation is represented by TRS. The latency for commitment function calculation is represented by TCom. As can be seen from Table 3, our proposed blind ring signature scheme has lower signature and verification algorithm latency than the other similar scheme [25].Table 3
Latency comparison.
SchemeSignature algorithm latencyVerification algorithm latencyLe et al. [25]4l+1TMul+2THash+3TRS+TComl+1TMul+THash+TComOur scheme2l+1TMul+THash+2TRSl+1TMul+THash


## 7. Conclusion

In this paper, we propose a new lattice-based blind ring signature scheme, which satisfies the correctness and security under the random oracle model, including anonymity, blindness, and one-more unforgeability. Meanwhile, the constructed blockchain transaction system based on our proposed blind ring signature satisfies the complete anonymity and antiquantum computing security of users’ identity privacy. Moreover, the proposed signature scheme has lower latency, smaller key, and signature sizes than other similar schemes.However, our proposed scheme has some limitations. On the one hand, the proposed blind ring signature scheme relies on the difficult problem on the standard lattice, which leads to some disadvantages, such as large storage space of the key matrix, low operation speed, and slow sampling rate, by comparing with structured lattice, such as ideal lattice. On the other hand, our constructed blockchain transaction system focuses on the implementation of user identity anonymity while ignoring the problem of double-spending attacks. In the future, firstly, we will study the linkable blind ring signature algorithm based on the ideal lattice to solve the limitations in the current work. Secondly, we will introduce the proposed blind ring signature algorithm into more specific blockchain application scenarios, such as medical blockchain and blockchain-enabled Internet of Things. Finally, we will study more cryptographic methods for blockchain data privacy protection, such as searchable encryption [32, 33], to improve blockchain privacy protection mechanisms.



---

*Source: 4052029-2022-09-01.xml*