Post-Quantum Secure ID-Based (Threshold) Linkable Dual-Ring Signature and Its Application in Blockchain Transactions

Based on the lattice-based hard problem, we propose an identity-based linkable dual-ring signature scheme as well as its threshold extension. Our proposal has several advantages:

The first post-quantum one-time linkable ring signature was proposed by Torres et al. [18] in 2018. Le et al. [19] suggested IBLRS methods that rely on lattice-based SIS and ring-SIS. Tang et al. [20] proposed a new lattice-based IBLRS scheme in 2020, which reduced the signature size and computational complexity, making it more suitable for practical applications. Although lattice-based ring signature schemes offer more security and are particularly suitable for future quantum computing environments, they tend to have large signature sizes and high computational complexity. To further reduce the size of ring signatures, much effort has been made in recent years. Most schemes for reducing ring signature size use two methods: accumulators [21] and zero-knowledge proofs [22]. However, accumulators require a trusted setup. In 2021, Yuen et al. [23] introduced a novel type of ring signature known as the “dual-ring signature”. This signature scheme builds upon the type-T standard signature algorithm and includes a lattice-based variant of the dual-ring signature. This new structure of ring signatures significantly reduces the signature size and speeds up the signing and verification processes compared to ordinary ring signatures. In 2024, Feng et al. [24] proposed a dual-ring signature scheme based on SM2, initially converting SM2 digital signatures into Type-T, and then integrating dual-ring with a variant of SM2 digital signatures.

Table 1 lists the related symbols. When an integer N exists for each positive integer c and, for all $x>N$, $\left|f\left(x\right)\right|<{\displaystyle \frac{1}{x^c}}$, a function $f:\mathbb{N}\to \mathbb{R}$ is said to be negligible (negl). If all probabilistic polynomial-time (PPT) algorithms cannot solve a problem with a non-negligible probability, then the problem is considered hard.

In 2008, Gentry et al. [26] proposed the GPV lattice screening algorithm, which is used by most lattice-based signature schemes and mainly consists of the following three parts:

TrapGen($1^n$): Input the security parameter n; let $q=q\left(n\right)⩾3$, $m=5nlogq$, and $\sigma =\sqrt{m}·2^{\omega \left(\sqrt{logm}\right)}$. The algorithm TrapGen$\left(1^n\right)$ outputs a matrix $A\in {\mathbb{R}}_q^{n\times m}$ and a set of bases on $T\in {\mathbb{R}}_q^{m\times m}$, and satisfies $\tilde{T}=O(nlogq)$.

SampleDom($1^n,\sigma )$: Input the security parameter n and the Gaussian parameter $\sigma$. The algorithm SampleDom$(1^n,\sigma )$ selects a random vector $\mathit{v}\in$${\mathbb{Z}}^m$ according to the distribution $D_{\sigma }^m$, and with high probability satisfies $\Vert \mathit{v}\Vert \le \sigma \sqrt{m}$.

SamplePre($\mathit{A},\mathit{T},\sigma ,\mathit{y})$: Input the matrix $\mathit{A}\in {\mathbb{Z}}_q^{n\times m}$; $\mathit{T}$ is a trapdoor basis of the lattice ${\Lambda }^{\perp }$($\mathit{A}$); the parameter $\sigma \ge$ $\Vert \tilde{\mathit{T}}\Vert \omega$$\left(\sqrt{logm}\right)$; for any vector $\mathit{y}\in {\mathbb{Z}}_q^n$, the algorithm SamplePre($\mathit{A},\mathit{T},\sigma ,\mathit{y}$) outputs a random non-zero vector $\mathit{e}\in {\mathbb{Z}}_q^m$, where $\Vert \mathit{e}\Vert \le \sigma \sqrt{m}$ and $\mathit{A}\mathit{e}=\mathit{y}\left(modq\right)$.

In lattice-based digital signatures, the signer wants to output a vector z that is independent of the private key s, ensuring that z cannot be used to gain any information about the signer’s secret. In the protocol, the signer computes $z=r+ls$, where s can be the private key or randomness used for the signer’s secret, $l\leftarrow \mathcal{L}$ is a challenge polynomial, and r is a “masking” vector. To eliminate the dependence of z on s, rejection sampling can be applied [27].

As Theorem 1 shows, for any $\mathit{v}\in {\mathbb{Z}}^m$, $\sigma =\omega (\Vert \mathit{v}\Vert \sqrt{logm})$, $Pr[{\displaystyle \frac{(D_{\sigma }^m\left(z\right)}{(D_{\mathit{v},\sigma }^m\left(z\right)}}$ = $O\left(1\right):\mathit{z}\leftarrow D_{\sigma }^m]$ = $1-2^{-\omega (logm)}$.

  In 2000, Pointcheval and Stern proposed the forking lemma [28]. Suppose $(G,\Sigma ,V)$ is a digital signature scheme with security parameter n. A is a PPT algorithm whose input only consists of public data. Let Q be the maximum number of queries that A can make to the random oracle. If A generates a valid signature $(m,{\sigma }_1,h,{\sigma }_2)$ with probability $\epsilon \ge 7Q/2^n$ within time T, then there exists an algorithm B that controls algorithm A and can generate two valid signatures $(m,{\sigma }_1,h,{\sigma }_2)$ and $(m,{\sigma }_1,h^{\prime },{\sigma }_2^{\prime })$ within expected time $T^{\prime }\le 84480TQ/\epsilon$, where $h\ne h^{\prime }$.

To further shorten the ring signature size of the AOS structure [29], especially the number of responses, the dual-ring structure, an efficient approach for constructing ring signatures, is suggested by [23]. The dual-ring signature splits the AOS single-ring signature into two separate rings: the commitments ring and the challenges ring, which are connected using a hash function. A dual-ring signature consists of N challenges and one response. We further provide a high-level description of the dual-ring structure:

In Figure 1, $Com$ represents the function used by the signer. ⊙ and ⊗ are two commutative group operations. V is the verification function. The verification function is split into two parts, $V_1$ and $V_2$, and their relationship is $V=V_1\odot V_2$. Z is the response function.

As Figure 3 shows, the signer with $I{D}_i$ starts the transaction and creates a ring using his or her identity and the identity information of other users in the blockchain to protect anonymity in blockchain transactions. The signer signs the transaction data using their private key. Note that it is impossible for outsiders to identify which signer created the signature since the identities of the entire ring are used in the signature generation process. The ring signature and associated transaction details are broadcast along with the transaction to the blockchain network. The ring signature is validated by other nodes on the blockchain network, confirming that a member of the ring actually created it. Thus, the ring signature protects the identity privacy of its real signer.

Before giving the algorithms, we first introduce the related parameters as follows: $q\ge 3$ is defined as the modulus of odd numbers, $m\ge 5nlogq$; ${\sigma }_1,{\sigma }_2$ are real numbers such that ${\sigma }_2\ge {\sigma }_1$. ${\mathcal{R}}_q$ is a ring ${\mathbb{Z}}_q\left[X\right]/(X^d+1)$ of dimension d. The set D is the collection of polynomials in ${\mathbb{Z}}_q\left[X\right]/(X^d+1)$. We define the total ring as $W=\{I{D}_1,I{D}_2,\cdots ,I{D}_N\}$. Define the following challenge space: Observe that $\left|\mathcal{L}\right|=3^d$. When $d=128$, we have $\left|\mathcal{L}\right|=3^{128}>2^{202}$. During the computation, the polynomial coefficients need to be modulo 3. After performing the modulo operation, the polynomial coefficients will be within the range $\{-1,0,1\}$.

The proposed construction of the IB-LDRS scheme from lattices is described as follows:

IB-LDRS.Setup: The blockchain system executes Algorithm 1; this algorithm takes the security parameter $\lambda$ as input, and outputs the public parameter $pp$. $H_1$ and $H_2$ act as random oracles, and $H_3$ functions as a collision-resistant one-way function.

Algorithm 1: IB-LDRS.Setup

Input: $\lambda$. Output: $pp$. 1 define $H_1:{\{0,1\}}^{*}\to {\mathcal{R}}_q^n$, $H_2:{\{0,1\}}^{*}\to \mathcal{L}$, and $H_3:{\{0,1\}}^{*}\to {\mathcal{R}}_q^{n\times m}$; 2 generate $(\mathit{A},{\mathit{T}}_A)\leftarrow TrapGen(n,m,q)$, $\mathit{A}\in {\mathcal{R}}_q^{n\times m}$; 3 define $MSK:={\mathit{T}}_A$, $\Vert {\tilde{\mathit{T}}}_A\Vert \le O\left(\sqrt{nlogq}\right)$; 4 return $pp:=\{n,m,q,\mathit{A},H_1,H_2,H_3\}$.

IB-LDRS.KeyExt: The KGC runs Algorithm 2 to generate the user’s public and private keys; this algorithm takes the public parameters $pp=\{n,m,q,\mathit{A},H_1,H_2,H_3\}$, identity $I{D}_i$, and master private key $MSK$ as inputs; compute ${\mathit{p}}_{I{D}_i}$ using hash function $H_1\left(I{D}_i\right)$ and sample ${\mathit{s}}_{I{D}_i}$ using the $SamplePre(\mathit{A},{\mathit{T}}_A,{\sigma }_1,{\mathit{p}}_{I{D}_i})$ function. It outputs public key $I{D}_i$ and private key${\mathit{s}}_{I{D}_i}$.

Algorithm 2: IB-LDRS.KeyExt

Input: $\{I{D}_i,pp,MSK.\}$ Output: $p{k}_i,s{k}_i$. 1 compute ${\mathit{p}}_{I{D}_i}=H_1\left(I{D}_i\right)$; 2 sample ${\mathit{s}}_{I{D}_i}\leftarrow SamplePre(\mathit{A},{\mathit{T}}_A,{\sigma }_1,{\mathit{p}}_{I{D}_i})$ with trapdoor ${\mathit{T}}_A$, where ${\sigma }_1\ge \Vert {\tilde{\mathit{T}}}_A\Vert \omega \left(\sqrt{logq}\right)$, ${\mathit{s}}_{I{D}_i}\le {\sigma }_1\sqrt{md}$; 3 return: $(p{k}_i,s{k}_i)=(I{D}_i,{\mathit{s}}_{I{D}_i})$.

IB-LDRS.Sign: The transaction initiator, Alice, runs the signature Algorithm 3 to initiate a transaction; the following algorithm generates the ring signature of message $\mathit{\mu }$ based on the dual-ring architecture, given input $\mathit{\mu }$, $pp$, W. The signer’s index is $j,(1\le j\le N)$, ${\mathit{s}}_{I{D}_j}$.

Algorithm 3: IB-LDRS.Sign

Input: $pp,W,\mathit{\mu },{\mathit{s}}_{I{D}_j}$ Output: $Sig$. 1 compute ${\mathit{A}}_{com}=H_3(\mathit{A},\mathit{\mu })$; 2 define $\mathit{\tau }:={\mathit{A}}_{com}·{\mathit{s}}_{I{D}_j}$; 3 pick $\mathit{r}\leftarrow D_{{\sigma }_2}^m,\mathit{e}=\mathit{A}·\mathit{r}\in {\mathcal{R}}_q^n,l_i\leftarrow \mathcal{L},i\in \{1,\cdots ,N\}$, $i\ne j$; 4 compute $\mathit{c}=\mathit{e}-{\sum }_{i=1,i\ne j}^N{l}_i·H_1\left(I{D}_i\right)$ 5 compute $\mathit{u}={\mathit{A}}_{com}·\mathit{r}-{\sum }_{i=1,i\ne j}^N{l}_i·\mathit{\tau }$; 6 compute $l_j=H_2(\mathit{c},\mathit{\mu },W,\mathit{u})-{\sum }_{i=1,i\ne j}^N{l}_i$; 7 define and compute $\mathit{z}:=\mathit{r}+l_j·{\mathit{s}}_{I{D}_j}$; 8 if $\parallel \mathit{z}\parallel >({\sigma }_1+{\sigma }_2)\sqrt{md}$, then restart from step 3; 9 return $Sig=(l_1,l_2,\cdots ,l_N,\mathit{z},\mathit{\tau })$

   IB-LDRS.Verify: The transaction receiver, Bob, runs the verification Algorithm 4 to verify the transaction; given $pp$, W, $\mathit{\mu }$, and $Sig$, verify it by the following steps.

Algorithm 4: IB-LDRS.Verify

Input: $pp,W,\mathit{\mu },Sig$ Output: 0 or 1. 1 if    $l_i\notin \mathcal{L}$, return 0 2 if    $\parallel {\mathit{z}}^{\prime }\parallel >({\sigma }_1+{\sigma }_2)\sqrt{md}$, return 0 3 ${\mathit{A}}_{com}=H_3(\mathit{A},\mathit{\mu })$ 4 ${\mathit{c}}^{\prime }=\mathit{A}·{\mathit{z}}^{\prime }-{\sum }_{i=1}^N{l}_i·H_1\left(I{D}_i\right)$ 5 ${\mathit{u}}^{\prime }={\mathit{A}}_{com}·{\mathit{z}}^{\prime }-{\sum }_{i=1}^N{l}_i·\mathit{\tau }$ 6 check if ${\sum }_{i=1}^N{l}_i=H_2({\mathit{c}}^{\prime },\mathit{\mu },W,{\mathit{u}}^{\prime })$, if so return 1 7 else return 0

   IB-LDRS.Link: The blockchain link runs the linking Algorithm 4 to conduct “double-spending” detection. Once it receives two different and valid signatures $Sig,Si{g}^{\prime }$ to be tested, this algorithm checks whether $\mathit{\tau }\stackrel{?}{=}{\mathit{\tau }}^{\prime }$. If it does, it returns “linkable”; otherwise, it returns “unlinkable”. Note that this algorithm tests valid signatures only, because it can invoke Algorithm 4 to check the validity and reject the invalid signatures. If both of the signatures are accepted, go to Algorithm 5 to check whether they are generated by the same signer.

Algorithm 5: IB-LDRS.Link

Input: $Sig,Si{g}^{\prime }$ Output: linkable or unlinkable. 1 if $\mathit{\tau }={\mathit{\tau }}^{\prime }$, return “linkable” 2 else, return “unlinkable”