Open AccessArticle

Lattice-Based Logarithmic-Size Non-Interactive Deniable Ring Signatures

Huiwen Jia

¹,

Chunming Tang

^1,* and

Yanhua Zhang

^2,*

School of Mathematics and Information Science, Guangzhou University, No. 230 Wai Huan Xi Road, Guangzhou 510006, China

College of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China

Authors to whom correspondence should be addressed.

Entropy 2021, 23(8), 980; https://doi.org/10.3390/e23080980

Submission received: 10 June 2021 / Revised: 25 July 2021 / Accepted: 28 July 2021 / Published: 29 July 2021

(This article belongs to the Special Issue Applications of Codes and Lattices in Cryptography and Wireless Communications)

Download

Browse Figure

Versions Notes

Abstract

Deniable ring signature can be regarded as group signature without group manager, in which a singer is capable of singing a message anonymously, but, if necessary, each ring member is allowed to confirm or disavowal its involvement in the signature via an interactive mechanism between the ring member and the verifier. This attractive feature makes the deniable ring signature find many applications in the real world. In this work, we propose an efficient scheme with signature size logarithmic to the cardinality of the ring. From a high level, we adapt Libert et al.’s zero-knowledge argument system (Eurocrypt 2016) to allow the prover to convince the verifier that its witness satisfies an additional condition. Then, using the Fait-Shamir transformation, we get a non-interactive deniable ring signature scheme that satisfies the anonymity, traceability, and non-frameability under the small integer solution assumption in the random oracle model.

Keywords:

deniable ring signature; zero-knowledge protocols; accumulators

1. Introduction

Ring signature was first formalized by Rivest et al. [1] to deal with situations, such as leaking secrets anonymously. Specifically, a signer first picks up several public keys to form a ring; then, it generates a signature anonymously on behalf of the ring using its secret key. Any verifier is unable to get any information about the real signer, except that the message is signed by one of the ring member. This appealing feature has made the ring signature find various applications in cryptography [1,2,3]. In some situations, however, the anonymity feature is not always desirable, as it allows a user who signs a false message to shift the blame to other ring members.

It is well-known that group signature [4,5,6,7,8,9] can prevent its members from abusing anonymity, in which users are able to sign messages anonymously, but, when a dispute occurs, the group manager possessing a group master secret key is capable of revoking the anonymity of misbehaving signers. However, group signature cannot handle the leaking secrets scenario, as the the manager is always able to trace the real signer who leaks a piece of invaluable information. Besides, group signature has much higher costs on managing a dynamic group. Finally, the members are anxious that their anonymity will be or has been violated by the manager without notification.

In 2006, Komano et al. [10] formalized the notion of Deniable Ring Signature (DRS), which is as flexible as the ring signature and allows the members to confirm whether they are the real signer or not. Specifically, by using an interactive mechanism between the ring member and the verifier, it enables the real signer to confirm its signed action and allows other ring members to deny their involvement. In short, DRS can be regarded as a ‘lightweight’ group signature, i.e., group signature without the manager. For the security requirements, the DRS should satisfy:

Anonymity: Any adversary should not get any information from the signature, unless the ring members are required to confirm or disavow their involvement in the signature.
Traceability: Any adversary should not generate a valid ring signature such that no member will be detected as the real signer via the confirmation/disavowal protocol. In other words, the real singer cannot deny its signature.
Non-frameability: Any adversary should not produce a valid ring signature such that a ring member, whose secret key is unknown to the adversary, will be detected as the real signer via the confirmation/disavowal protocol. In other words, any adversary cannot frame an honest member.

In their pioneering work, Komano et al. [10] also presented a concrete scheme under the Decisional Diffie–Hellman (DDH) assumption. However, this assumption does not hold in the quantum world [11].

1.1. Contributions and Technical Overview

In this work, we propose an efficient lattice-based Non-interactive Deniable Ring Signature (NDRS) scheme. The notion NDRS, first formalized in Reference [12], means that the confirmation or disavowal of a signature is achieved in a non-interactive manner, instead of the interactive mechanism between the ring member and the verifier. In terms of effiency, our construction is efficient in the sense that the signature size is only logarithmic to the cardinality of the ring. In the aspect of security, our construction satisfies the anonymity, traceability, and non-frameability under the Small Integer Solution (SIS) assumption in the random oracle model.

From a high level, our scheme is a natural extension of the ring signature scheme in Reference [8] to the NDRS setting. In more detail, we adapt their argument system for a tree-based accumulator [8] to allow the prover to convince the verifier that the prover knows a witness which not only accumulates to the root of a Merkle tree but also satisfies some additional conditions. Specifically, compared with the ring signature scheme in Reference [8], we add one more additional condition, an non-interactive identification scheme used by the ring members to prove their identity. Combining zero-knowledge argument systems for two or more NP relations is a general strategy widely used in previous works, such as group signatures [8,9], policy-based signatures [13], compact e-cash [14], etc.

The starting point of our construction is the Zero Knowledge Argument of Knowledge (

ZKAoK

) for the Merkle tree-based accumulator [8]. Specifically, the underlying hash function is defined by

h_{A} (x) = bin (A \cdot x mod q) \in {0, 1}^{m / 2}

, where the uniformly random matrix

A \in Z_{q}^{n \times m}

serves as the common reference string,

x \in {0, 1}^{m}

is the input vector, and

bin (\cdot)

denotes the coordinate-wise binary decomposition of its input. Then, by using the framework of Stern’s protocol [15], Libert et al. [8] can prove knowledge of hash chain in a zero-knowledge fashion. Besides, through the Fait-Shamir transformation, they also build ring signature with logarithmic size in the number of ring. Note that their ring signature enjoys complete anonymity. To achieve our goal that each ring member is able to generate a piece of evidence demonstrating whether it is the real signer or not, we need another matrix

B \in Z_{q}^{n \times m}

which acts as the public key of an identification scheme. In more detail, to sign a message M, a signer possessing his secret

x

generates a zero-knowledge argument system to show that:

Fact 1: $d = h_{A} (x)$ .
Fact 2: $d$ is properly accumulated into the root of the Merkle tree.
Fact 3: $B \cdot x = b mod q$ .

We first use the procedure in Reference [8] as a sub-protocol to prove Fact 1 and Fact 2 in zero knowledge. The key point in our construction is to prove the secret in Fact 1 simultaneously satisfies Fact 3. To this end, we employ again the framework of Stern’s protocol [15] as a sub-protocol, such that it is compatible with the proof in Reference [8]. The details are presented in Section 3.

Then, we apply the Fait-Shamir transformation to our interactive protocol and obtain a signature scheme in the random oracle by repeating it

κ = ω (log n)

times to make the soundness error negligibly small. Generally, the anonymity of our NDRS scheme is based on the zero-knowledge property of the underlying argument system, while the traceability and the non-frameability are built on the fact that the underlying argument system is indeed an argument of knowledge. The description of the construction and its proof are described in Section 4.

1.2. Related Works

In 2006, Komano et al. [10] first introduced the notion of DRS and proposed a concrete DRS construction based on the DDH assumption. Recently, Gao et al. [12] put forward the NDRS notion, which is a direct generalization of DRS to the non-interactive setting. Besides, they proposed a concrete NDRS scheme under lattice assumptions, which is conjectured resistance against quantum computers. Their scheme, however, is shown to be insecure in Reference [16], as the scheme does not meet the ‘Traceability’ and ‘Non-frameability’ security requirements.

1.3. Organizations

We start in Section 2 by providing some background regarding NDRS and useful tools developed in Reference [8]. Then, in Section 3, we present an interactive protocol, which is the key component of our construction. In Section 4, we show the concrete scheme and its efficiency analysis and security proof. Finally, we conclude the paper with the obtained results.

2. Preliminaries

The set of integers

{1, \dots, k}

is denoted by

[k]

. If S is a finite set,

x \leftarrow S

means that x is chosen uniformly at random from S. For

b \in {0, 1}

, let

\bar{b} = 1 - b

. ⊕ denotes the bit XOR operation. For any positive integer q, denote by

Z_{q}

the quotient ring

Z / (q Z)

. Vectors, denoted by bold lowercase letters, are in column form. Matrices are represented in bold uppercase letters, and the concatenation of two matrices, say

A \in Z_{q}^{n \times m_{1}}

and

B \in Z_{q}^{n \times m_{2}}

, is denoted by

[A ∣ B] \in Z_{q}^{n \times (m_{1} + m_{2})}

. The tensor product is denoted by ⊗. Let

B_{2 m}^{m}

be the set of all vectors in

{0, 1}^{2 m}

with Hamming weight m, and

S_{2 m}

be the set of all permutations of

2 m

elements. The abbreviation PPT means “probabilistic polynomial time”.

Throughout the paper, we denote by n the security parameter and define:

q = \tilde{O} (n); k = ⌈ log q ⌉; m = 2 n k

. Let

G = I_{n} \otimes g^{t} \in Z_{q}^{n \times n k}

, where

g^{t}

is the row vector

g^{t} = [1 2 4 \dots 2^{k - 1}] \in Z_{q}^{1 \times k} .

Note that, for any

v \in Z_{q}^{n}

, we have

v = G \cdot bin (v)

, where

bin (v) \in {0, 1}^{n k}

denotes the binary representation of

v

2.1. Non-Interactive Deniable Ring Signature (NDRS)

For any positive integer

N \geq 2

, the ring R, formed by N users’ public keys, is denoted by

R = {p k_{i_{0}}, p k_{i_{1}}, \dots, p k_{i_{N - 1}}}

. For ease of notation, we simply let

R = {p k_{0}, p k_{1}, \dots, p k_{N - 1}}

with ring size N. Now, we recall the definition and security requirements for the NDRS presented in Reference [12].

$Setup (1^{n})$ : Take as input n and output the system parameter $pp$ .
$KeyGen (pp)$ : Take as input $pp$ and output a public/secret key pair $(p k, s k)$ .
$Sign (pp, R, s k, M)$ : Take as inputs $pp$ , a set of N public keys $R = {p k_{0}, p k_{1}, \dots, p k_{N - 1}}$ , a secret key $s k$ for which its corresponding $p k \in R$ and a message M to be signed, and output a ring signature $Σ$ .
$Verify (pp, R, M, Σ)$ : Take as inputs $pp$ , R, M, and $Σ$ , and output 1 if $Σ$ is valid or 0 otherwise.
$EvidenceGen (pp, R, s k_{i}, Σ)$ : Take as inputs $pp$ , R, user i’s secret key $s k_{i}$ , M, and $Σ$ , and output a piece of evidence $ξ_{i}$ .
$EvidenckCheck (pp, R, i, ξ_{i}, Σ)$ : Take as inputs $pp$ , R, an identity index i of a user, M and $Σ$ , and output “confirmation”, “disavowal”, or “reject”.

The correctness requirements for an NDRS scheme are formalized as follows:

The signature $Σ$ generated by the $Sign$ algorithm is properly accepted by the $Verify$ algorithm, i.e., $Verify (pp, R, M, Σ) = 1$ for any $pp \leftarrow Setup (1^{n})$ , any $(p k, s k) \leftarrow KeyGen (pp)$ , any R such that $p k \in R$ and any $M \in {0, 1}^{*}$ .
The real signer of the signature $Σ$ will generate a piece of evidence such that the evidence check algorithm outputs “confirmation”, i.e.,

$EvidenckCheck (pp, R, i, EvidenceGen (pp, R, s k_{i}, Σ), Σ) = ‘ ‘ confirmation "$

for any valid signature $Σ$ generated by user i.
The non-real signer should generate a piece of evidence such that the evidence check algorithm outputs “disavowal”, i.e.,

$EvidenceCheck (pp, R, j, EvidenceGen (pp, R, s k_{j}, Σ), Σ) = ‘ ‘ disavowal "$

for any ring member $j \neq i$ .

For the security requirements, we adopt the notions and games in References [10,12]. Suppose each user has a public/private key pair supported by the Public Key Infrastructure (PKI). Let

List

be a public key content issued by PKI, and let

MList

be a list of malicious signers. Let

GSet

be a list of message-signature pairs generated through a challenge oracle query

{Ch}_{b} (\cdot)

. An adversary is able to make the following queries.

$Add (i)$ : on input i, this oracle generates a key pair ( $p k_{i}$ , $s k_{i}$ ) for user i, adds i together with the key pair to $List$ , and returns $p k_{i}$ .
$Reg (i, p k_{i})$ : on inputs i and $p k_{i}$ , this oracle registers a new signer i with the given public key $p k_{i}$ in $List$ and adds user i to $MList$ .
$Crpt (i)$ : on input i, this oracle returns the secret key $s k_{i}$ and adds user i to $MList$ .
$DRSig (i_{k}; M, i_{1}, \dots, i_{k - 1}, i_{k + 1}, \dots, i_{t})$ : on inputs a specified user $i_{k}$ , a message M, and a set of identities, this oracle returns a signature $Σ$ associated with the ring formed by the input identities, by using the secret key of user $i_{k}$ .
${Ch}_{b} (i_{0}, i_{1}, M)$ : on inputs a pair of identities $(i_{0}, i_{1})$ and M, this oracle returns the signature $Sign (pp, {p k_{i_{0}}, p k_{i_{1}}}, s k_{i_{b}}, M)$ for a challenge bit $b \leftarrow {0, 1}$ , and adds it to $GSet$ . This oracle is only used in the definition of anonymity.
$EGen (i, M, Σ)$ : on inputs $i, M, Σ$ , this oracle returns a piece of evidence demonstrating whether the entity i is the real signer or not. This oracle will reject the query if the input signature is an output from the challenge oracle in the experiment of anonymity.
$Hash (\cdot)$ : this oracle outputs a random string with a fixed length for an arbitrary input.

As mentioned before, an (N)DRS scheme should satisfy anonymity, traceability, and non-frameability. Each of these security requirements is formalized by an experiment, as shown in Figure 1.

Anonymity

For an NDRS scheme, a security parameter n, and a PPT adversary

A

, the property of anonymity is formalized using the experiment

{Exp}_{N D R S, A}^{anon - b} (n)

, as described in Figure 1. The advantage

{Adv}_{N D R S, A}^{anon} (n)

is defined as

{Adv}_{N D R S, A}^{anon} (n) = | 2 \Pr [{Exp}_{N D R S, A}^{anon - b} (n) = b] - 1 | .

An NDRS has anonymity if

{Adv}_{N D R S, A}^{anon - b} (n)

is negligible for any PPT adversary

A

and security parameter n.

Traceability

The property of traceability is formalized using the experiment

{Exp}_{N D R S, A}^{trace} (n)

, as shown in Figure 1. The advantage of the adversary is given by:

{Adv}_{N D R S, A}^{trace} (n) = \Pr [{Exp}_{N D R S, A}^{trace} (n) = 1] .

An NDRS is said to hold traceability if

{Adv}_{N D R S, A}^{trace} (n)

is negligible for any PPT adversary

A

and security parameter n.

Non-frameability

The property of non-frameability is formalized using the experiment

{Exp}_{N D R S, A}^{nf} (n)

, as shown in Figure 1. The advantage of the adversary is defined as:

{Adv}_{N D R S, A}^{nf} (n) = \Pr [{Exp}_{N D R S, A}^{nf} (n) = 1] .

An NDRS is said to hold non-frameability if

{Adv}_{N D R S, A}^{nf} (n)

is negligible for any PPT adversary

A

and security parameter n.

2.2. Average-Case Lattice Problems

In this subsection, we briefly recall the average-case Small Integer Soulution (SIS) problem (in the infinity norm version) and its hardness guarantees. For more details, see References [17,18,19,20].

Definition 1

(Reference [17]). Given uniformly random matrix

A \in Z_{q}^{n \times m}

, the

{SIS}_{n, m, q, β}^{\infty}

problem asks to find a non-zero vector

x \in Z^{m}

such that

A \cdot x = 0 mod q

and

{∥ x ∥}_{\infty} \leq β

The hardness of the

SIS

problem is guaranteed by a certain lattice problems in the worst case, such as the Shortest Independent Vector Problem (SIVP).

Theorem 1

(References [18,19,20]). If

m, β = poly (n)

, and

q > β \cdot \tilde{O} (\sqrt{n})

, then the

{SIS}_{n, m, q, β}^{\infty}

problem is at least as hard as the worst-case problem

{SIVP}_{γ}

for some

γ = β \cdot \tilde{O} (\sqrt{m n})

. Specifically, for

β = 1, q = \tilde{O} (n), m = 2 n ⌈ log q ⌉

, the

{SIS}_{n, m, q, 1}^{\infty}

problem is at least as hard as

{SIVP}_{\tilde{O} (n)}

2.3. Statistical Zero-Knowledge Argument Systems

Let

R : {0, 1}^{*} \times {0, 1}^{*} \to {0, 1}

be an

NP

relation. The interaction

〈 P, V 〉

between a prover

P

and a verifier

V

is called an interactive argument system for the relation R if the following two conditions hold:

Completeness

R (x, w) = 1

, then

\Pr [〈 P (x, w), V (x) 〉 = 1] = 1 .

Soundness

R (x, w) = 0

, then, for every PPT

P^{*}

\Pr [〈 P^{*} (x, w), V (x) 〉 = 1] \leq e,

where

e \in [0, 1]

is called the soundness error.

In this work, we will employ the Stern-type

ZKAoK

[15], which is a

Σ

-protocol from a generalized point of view in References [21,22]. Besides, we will utilize the lattice-based string commitment scheme in Reference [23]

COM : {0, 1}^{*} \times {0, 1}^{m / 2} \to Z_{q}^{n}

, which is statistically hiding and computationally binding under the assumption that

{SIVP}_{\tilde{O} (n)}

is hard.

2.4. Lattice-Based Accumulator

We first recall a certain family of collision-resistant hash functions presented in Reference [8].

Definition 2.

The function family

H : {0, 1}^{n k} \times {0, 1}^{n k} \to {0, 1}^{n k}

is given by

H = {h_{A} : A \in Z_{q}^{n \times m}}

, where

h_{A} (u_{0}, u_{1}) = bin (A_{0} \cdot u_{0} + A_{1} \cdot u_{1} mod q) \in {0, 1}^{n k} .

for any

(u_{0}, u_{1}) \in {0, 1}^{n k} \times {0, 1}^{n k}

, and

A = [A_{0} ∣ A_{1}]

with

A_{0}, A_{1} \in Z_{q}^{n \times n k}

Then, we recall the Merkle tree accumulator with

N = 2^{l}

leaves based on the hash function family

H

above.

$TSetup (1^{n})$ : On input n, output $pp = A \leftarrow Z_{q}^{n \times m}$ .
$TAcc (A, R})$ : Given $R = {d_{j} \in {0, 1}^{n k}}_{j = 0}^{N - 1}$ , let $u_{j_{1}, \dots, j_{l}} = d_{j}$ , where $j_{1}, \dots, j_{l} \in {0, 1}$ is the l bits of j. Define the tree of depth l for the leaves $u_{0, \dots, 0}, \dots, u_{1, \dots, 1}$ as follows:
- The nodes $u_{b_{1}, \dots, b_{i}}$ at depth $i \in [l]$ is given by $h_{A} (u_{b_{1}, \dots, b_{i}, 0}, u_{b_{1}, \dots, b_{i}, 1})$ .
- The root $u \in {0, 1}^{n k}$ is defined as $h_{A} (u_{0}, u_{1})$ .
Output $u$ as the accumulator value.
$TWitness (A, R, d)$ : If $d \notin R$ , output ⊥; otherwise, $\exists j \in [0, N - 1]$ such that $d = d_{j}$ . Return the witness w defined by:

$w = ((j_{1}, \dots, j_{l}), (u_{j_{1}, \dots, j_{l - 1}, \bar{j_{l}}}, \dots, u_{j_{1}, \bar{j_{2}}}, u_{\bar{j_{1}}})) \in {0, 1}^{l} \times {({0, 1}^{n k})}^{l},$

where $u_{j_{1}, \dots, j_{l - 1}, \bar{j_{l}}}, \dots, u_{j_{1}, \bar{j_{2}}}, u_{\bar{j_{1}}}$ are computed by $TAcc (A, R)$ .
$TVerify (A, u, d, w)$ : Given witness

$w = ((j_{1}, \dots, j_{l}), (w_{l}, \dots, w_{1})) \in {0, 1}^{l} \times {({0, 1}^{n k})}^{l},$

let $v_{l} = d$ , and recursively compute $v_{l - 1}, \dots, v_{1}, v_{0} \in {0, 1}^{n k}$ for $i \in {l - 1, \dots, 0}$ as follows:

$v_{i} = \{\begin{matrix} h_{A} (v_{i + 1}, w_{i + 1}), & if j_{i + 1} = 0; \\ h_{A} (w_{i + 1}, v_{i + 1}), & if j_{i + 1} = 1 . \end{matrix}$

Return 1 if $v_{0} = u$ ; otherwise, return 0.

In Reference [8], the authors also design an argument system for the prover

P

to convince the verifier

V

that

P

knows a value-witness pair

(d, w)

such that

TVerify (A, u, d, w) = 1

. Toward this goal, they develop the following supporting techniques, which are necessary in our construction, as well.

Extension of $A = [A_{0} ∣ A_{1}]$ to $A^{*} = [A_{0} ∣ 0^{n \times n k} ∣ A_{1} ∣ 0^{n \times n k}] \in Z_{q}^{n \times 2 m}$ .
Extension of $G$ to $G^{*} = [G ∣ 0^{n \times n k}] \in Z_{q}^{n \times m}$ .
Extensions of $v_{1}, \dots, v_{l}, w_{1}, \dots, w_{l}$ to $v_{1}^{*}, \dots, v_{l}^{*}, w_{1}^{*}, \dots, w_{l}^{*} \in B_{m}^{n k}$ by appending to each vector a length- $n k$ vector with suitable Hamming weight.
For $i \in {n k, m}, b \in {0, 1}$ and $v \in {0, 1}^{i}$ , let $ext (b, v)$ denote the vector $z \in {0, 1}^{2 i}$ of the form $z = (\begin{matrix} \bar{b} \cdot v \\ b \cdot v \end{matrix}) .$
For $b \in {0, 1}$ and $π \in S_{m}$ , define the permutation $F_{b, π}$ that transforms $z = (\begin{matrix} z_{0} \\ z_{1} \end{matrix}) \in Z_{q}^{2 m}$ consisting of 2 blocks of size m into $F_{b, π} (z) = (\begin{matrix} π (z_{b}) \\ π (z_{\bar{b}}) \end{matrix})$ .

Observe that, for all

c, b \in {0, 1}, π, ϕ \in S_{m}

and

v, w \in {0, 1}^{m}

\begin{matrix} z = ext (c, v) \land v \in B_{m}^{n k} ⟺ F_{b, π} (z) = ext (c \oplus b, π (v)) \land π (v) \in B_{m}^{n k}; \\ y = ext (\bar{c}, w) \land w \in B_{m}^{n k} ⟺ F_{\bar{b}, ϕ} (y) = ext (c \oplus b, ϕ (w)) \land ϕ (w) \in B_{m}^{n k} . \end{matrix}

3. The Underlying Zero-Knowledge Argument System

In this section, we present an interactive protocol, upon which our NDRS scheme is built. This protocol bears much resemblance to that in Section 4.2 of Reference [8], except that one more layer is added. Specifically, in our protocol, the prover

P

is able to convince the verifier

V

on input

(A, B, u, b)

that

P

knows a secret tuple

(d, w, x)

such that:

$d = h_{A} (x) \in {0, 1}^{n k}$ ,
$TVerify (A, u, d, w) = 1$ ,
$B \cdot x = b mod q \in Z_{q}^{n}$ .

More formally, the associated relation

R_{NDRS}

is given by

\begin{matrix} R_{NDRS} = {((A, B, u, b) \in Z_{q}^{n \times m} \times Z_{q}^{n \times m} \times {0, 1}^{n k} \times Z_{q}^{n}; \\ d \in {0, 1}^{n k}, w \in {0, 1}^{l} \times {({0, 1}^{n k})}^{l}, x \in {0, 1}^{m}) : \\ A \cdot x = G \cdot d mod q \land B \cdot x = b mod q \land TVerify (A, u, d, w) = 1} . \end{matrix}

3.1. Description of the Interactive Protocol

The public parameters are

n, m, q, k, l, G, G^{*}, \hat{A}

, and

\hat{B}

, where

\hat{A} = [A ∣ 0^{n \times m}], \hat{B} = [B ∣ 0^{n \times m}] \in Z_{q}^{n \times 2 m} .

The prover

P

, using its witness, prepares, according to Section 2.4, the following vectors:

v_{i}^{*}, w_{i}^{*} \in B_{m}^{n k}, z_{i} = ext (j_{i}, v_{i}^{*}), y_{i} = ext ({\bar{j}}_{i}, w_{i}^{*}),

for all

i \in [l]

such that

\{\begin{matrix} A^{*} \cdot z_{1} + A^{*} \cdot y_{1} = G \cdot u mod q; \\ A^{*} \cdot z_{i + 1} + A^{*} \cdot y_{i + 1} = G^{*} \cdot v_{i}^{*} mod q \end{matrix},

(1)

for all

i \in [l - 1]

. Observe that

G^{*} \cdot v_{l}^{*} = G \cdot d

. First,

P

extends

x

into

x^{*} \in B_{2 m}^{m}

. Clearly,

\hat{A} \cdot x^{*} = A \cdot x

and

\hat{B} \cdot x^{*} = B \cdot x

. In Stern’s framework, a random permutation

τ \leftarrow S_{2 m}

and a random ‘mask’

r_{x} \leftarrow Z_{q}^{2 m}

give a

ZKAoK

of the secret

x

according to the equivalence

x^{*} \in B_{2 m}^{m} \Leftrightarrow τ (x^{*}) \in B_{2 m}^{m}

After these preparations,

P

’s goal is to convince

V

that it knows the vectors

v_{i}^{*}, w_{i}^{*}

z_{i}, y_{i}

for all

i \in [l]

and

x^{*} \in B_{2 m}

such that:

Equation (1) holds;
$\hat{A} \cdot x^{*} = G^{*} \cdot v_{l}^{*} mod q$ and $\hat{B} \cdot x^{*} = b mod q$ .

The interaction between

P

and

V

is detailed as follows.

1.

Commitment.

P

firstly picks the following randomness:

\begin{matrix} ρ_{1}, ρ_{2}, ρ_{3} \in {0, 1}^{m / 2} for COM \\ τ \leftarrow S_{2 m}; b_{1}, \dots, b_{l} \leftarrow {0, 1}; π_{1}, \dots, π_{l}, ϕ_{1}, \dots, ϕ_{l} \leftarrow S_{m} \\ r_{x} \leftarrow Z_{q}^{2 m}; r_{v_{1}}, \dots, r_{v_{l}} \leftarrow Z_{q}^{m}; r_{z_{1}}, \dots, r_{z_{l}}, r_{y_{1}}, \dots, r_{y_{l}} \leftarrow Z_{q}^{2 m} . \end{matrix}

Then, the commitment CMT=(

C_{1}, C_{2}, C_{3}

) is sent to

V

, where

\begin{matrix} C_{1} & = COM (τ; \hat{A} \cdot r_{x} - G^{*} \cdot r_{v_{l}}; \hat{B} \cdot r_{x}; {b_{i}, π_{i}, ϕ_{i}}_{i = 1}^{l}; A^{*} \cdot r_{z_{1}} + A^{*} \cdot r_{y_{1}}; \\ {A^{*} \cdot r_{z_{i + 1}} + A^{*} \cdot r_{y_{i + 1}} - G^{*} \cdot r_{v_{i}}}_{i = 1}^{l - 1}; ρ_{1}) \\ C_{2} & = COM (τ (r_{x}); {π_{i} (r_{v_{i}}), F_{b_{i}, π_{i}} (r_{z_{i}}), F_{{\bar{b}}_{i}, ϕ_{i}} (r_{y_{i}})}_{i = 1}^{l}; ρ_{2}) \\ C_{3} & = COM (τ (x^{*} + r_{x}); {π_{i} (v_{i}^{*} + r_{v_{i}}), F_{b_{i}, π_{i}} (z_{i} + r_{z_{i}}), F_{{\bar{b}}_{i}, ϕ_{i}} (y_{i} + r_{y_{i}})}_{i = 1}^{l}; ρ_{3}) . \end{matrix}

2.

Challenge.

V

sends to

P

a challenge

C h \leftarrow {1, 2, 3}

3.

Response.

P

sends the response RSP depending on

C h

as follows:

$C h = 1$ : Let ${\tilde{x}}^{*} = τ (x^{*}), {\tilde{r}}_{x} = τ (r_{x})$ , and, for each $i \in [l]$ , let:

$\begin{matrix} {\tilde{b}}_{i} = j_{i} \oplus b_{i}; {\tilde{v}}_{i}^{*} = π_{i} (v_{i}^{*}); {\tilde{w}}_{i}^{*} = ϕ_{i} (w_{i}^{*}) \\ {\tilde{r}}_{v_{i}} = π_{i} (r_{v_{i}}); {\tilde{r}}_{z_{i}} = F_{b_{i}, π_{i}} (r_{z_{i}}); {\tilde{r}}_{y_{i}} = F_{{\bar{b}}_{i}, ϕ_{i}} (r_{y_{i}}) . \end{matrix}$

Set RSP= $({\tilde{x}}^{*}; {\tilde{r}}_{x}; {{\tilde{b}}_{i}, {\tilde{v}}_{i}^{*}, {\tilde{w}}_{i}^{*}, {\tilde{r}}_{v_{i}}, {\tilde{r}}_{z_{i}}, {\tilde{r}}_{y_{i}}}_{i = 1}^{l}; ρ_{2}; ρ_{3})$ .
$C h = 2$ : Let $τ^{'} = τ, s_{x} = x^{*} + r_{x}$ , and, for each $i \in [l]$ , let:

$\begin{matrix} b_{i}^{'} = b_{i}; π_{i}^{'} = π_{i}; ϕ_{i}^{'} = ϕ_{i}; \\ s_{v_{i}} = v_{i}^{*} + r_{v_{i}}; s_{z_{i}} = z_{i} + r_{z_{i}}; s_{y_{i}} = y_{i} + r_{y_{i}} . \end{matrix}$

Set RSP= $(τ^{'}; s_{x}; {b_{i}^{'}, π_{i}^{'}, ϕ_{i}^{'}, s_{v_{i}}, s_{z_{i}}, s_{y_{i}}}_{i = 1}^{l}; ρ_{1}; ρ_{3})$ .
$C h = 3$ : Let $τ^{''} = τ, r_{x}^{'} = r_{x}$ , and, for each $i \in [l]$ , let:

$\begin{matrix} b_{i}^{''} = b_{i}; π_{i}^{''} = π_{i}; ϕ_{i}^{''} = ϕ_{i}; \\ r_{v_{i}}^{'} = r_{v_{i}}; r_{z_{i}}^{'} = r_{z_{i}}; r_{y_{i}}^{'} = r_{y_{i}} . \end{matrix}$

Set RSP= $(τ^{''}; r_{x}^{'}; {b_{i}^{''}, π_{i}^{''}, ϕ_{i}^{''}, r_{v_{i}}^{'}, r_{z_{i}}^{'}, r_{y_{i}}^{'}}_{i = 1}^{l}; ρ_{1}; ρ_{2})$ .

4.

Verification. Given RSP,

V

proceeds as follows.

$C h = 1$ : Check that ${\tilde{x}}^{*} \in B_{2 m}$ for $i \in [p]$ , ${\tilde{v}}_{i}^{*}, {\tilde{w}}_{i}^{*} \in B_{m}^{n k}$ for $i \in [l]$ and that

$\begin{matrix} C_{2} & = COM ({\tilde{r}}_{x}; {{\tilde{r}}_{v_{i}}, {\tilde{r}}_{z_{i}}, {\tilde{r}}_{y_{i}}}_{i = 1}^{l}; ρ_{2}), \\ C_{3} & = COM ({\tilde{x}}^{*} + {\tilde{r}}_{x}; {{\tilde{v}}_{i}^{*} + {\tilde{r}}_{v_{i}}, ext ({\tilde{b}}_{i}, {\tilde{v}}_{i}^{*}) + {\tilde{r}}_{z_{i}}, ext ({\tilde{b}}_{i}, {\tilde{w}}_{i}^{*}) + {\tilde{r}}_{y_{i}}}_{i = 1}^{l}; ρ_{3}) . \end{matrix}$
$C h = 2$ : Check that

$\begin{matrix} C_{1} & = COM (τ^{'}; \hat{A} \cdot s_{x} - G^{*} \cdot s_{v_{l}}; \hat{B} \cdot s_{x} - b; {b_{i}^{'}, π_{i}^{'}, ϕ_{i}^{'}}_{i = 1}^{l}; \\ A^{*} \cdot s_{z_{1}} + A^{*} \cdot s_{y_{1}} - G \cdot u; {A^{*} \cdot s_{z_{i + 1}} + A^{*} \cdot s_{y_{i + 1}} - G^{*} \cdot s_{v_{i}}}_{i = 1}^{l - 1}; ρ_{1}), \\ C_{3} & = COM (τ^{'} (s_{x}); {π_{i}^{'} (s_{v_{i}}), F_{b_{i}^{'}, π_{i}^{'}} (s_{z_{i}}), F_{{\bar{b}}_{i}^{'}, ϕ_{i}^{'}} (s_{y_{i}})}_{i = 1}^{l}; ρ_{3}) . \end{matrix}$
$C h = 3$ : Check that

$\begin{matrix} C_{1} & = COM (τ^{''}; \hat{A} \cdot r_{x}^{'} - G^{*} \cdot r_{v_{l}}^{'}; \hat{B} \cdot r_{x}^{'}; {b_{i}^{''}, π_{i}^{''}, ϕ_{i}^{''}}_{i = 1}^{l}; A^{*} \cdot r_{z_{1}}^{'} + A^{*} \cdot r_{y_{1}}^{'}; \\ {A^{*} \cdot r_{z_{i + 1}}^{'} + A^{*} \cdot r_{y_{i + 1}}^{'} - G^{*} \cdot r_{v_{i}}^{'}}_{i = 1}^{l - 1}; ρ_{1}), \\ C_{2} & = COM (τ^{''} (r_{x}^{'}); {π_{i}^{''} (r_{v_{i}}^{'}), F_{b_{i}^{''}, π_{i}^{''}} (r_{z_{i}}^{'}), F_{{\bar{b}}_{i}^{''}, ϕ_{i}^{''}} (r_{y_{i}}^{'})}_{i = 1}^{l}; ρ_{2}) . \end{matrix}$

V

outputs 1 only if all the conditions hold in each cases. Otherwise, output 0.

3.2. Analysis of the Interactive Protocol

We summarize several properties of the above protocol in the following theorem. Since the proof of the properties of the protocol is similar with that of Reference [8], we omit the details. (See Appendix A)

Theorem 2.

The given interactive protocol has perfect completeness and communication cost

\tilde{O} (l \cdot n)

. If

COM

is a statistically hiding and computationally binding string commitment scheme, then it is an

ZKAoK

for the relation

R_{NDRS}

4. Our Non-Interactive Deniable Ring Signature Scheme from Lattices

We now construct an NDRS scheme for rings with

N = 2^{l}

users (It can be easily adapted for any other values of N as in Reference [8].) and prove that our construction satisfies the security requirements: anonymity, traceability, and non-frameability. We use a public Pseudo-random Generator (PRG), and a random oracle

H_{FS} : {0, 1}^{*} \to {1, 2, 3}^{κ}

$Setup (1^{n})$ : On input n, output $pp = A \leftarrow Z_{q}^{n \times m}$ .
$KeyGen (pp)$ : On input $pp$ , output $(p k, s k) = (d, x)$ , where $x \leftarrow {0, 1}^{m}$ , and $d = bin (A \cdot x mod q)$ .
$Sign (pp, R, s k, M)$ : On inputs $pp$ , $R = {d_{0}, \dots, d_{N - 1}}$ , $s k$ , and M, it works as follows (Notice that, for the public key $p k$ corresponding to the input $s k$ , we have $p k \in R$ .) to output the signature $Σ$ .
- Run $TAcc (A, R)$ and obtain $u \in {0, 1}^{n k}$ . Recall that $u$ is the root of the Merkle tree defined on R.
- Run $TWitness (A, R, d)$ and obtain
  
  $w = ((j_{1}, \dots, j_{l}) \in {0, 1}^{l}, (w_{l} \dots, w_{1}) \in {({0, 1}^{n k})}^{l}) .$
  
  Recall that w is a witness to the fact that $d \in R$ .
- Sample a seed $s \leftarrow {0, 1}^{n}$ , generate a matrix $B = PRG (s) \in Z_{q}^{n \times m}$ and compute $b = B \cdot x mod q$ . Then, produce an $NIZKAoK$ $Π$ by repeating our interactive protocol $κ = ω (log n)$ times. By using the Fiat-Shamir heuristic, we transform $Π$ to the triple
  
  $Π = ({{CMT}_{i}}_{i = 1}^{κ}, CH, {{RSP}_{i}}_{i = 1}^{κ}),$
  
  where
  
  $CH = H_{FS} (M, {{CMT}_{i}}_{i = 1}^{κ}, A, B, u, b, R) = (C h_{1}, \dots, C h_{κ}) \in {1, 2, 3}^{κ} .$
- Output $Σ = (s, b, Π)$ .
$Verify (pp, R, M, Σ)$ : Pm inputs $pp, R, M, Σ$ , the verification procedure is detailed as follows:
- Run $TAcc (A, R)$ and obtain $u$ .
- Parse $Σ = (s, b, {{CMT}_{i}}_{i = 1}^{κ}, CH, {{RSP}_{i}}_{i = 1}^{κ})$ . Let $B = PRG (s)$ . Output 0 if
  
  $(C h_{1}, \dots, C h_{κ}) \neq H_{FS} (M, {{CMT}_{i}}_{i = 1}^{κ}, A, B, u, b, R) .$
- For $i = 1, \dots, κ$ , check the validity of RSP $_{i}$ $w . r . t .$ CMT $_{i}$ and $C h_{i}$ . If all the conditions hold, output 1; otherwise, output 0.
$EvidenceGen (pp, R, s k_{i}, Σ)$ : On inputs $pp$ , R, a secret key $s k_{i} = x^{'}$ , and the pair $(s, b)$ contained in $Σ$ , the algorithm produces a piece of evidence $ξ_{i}$ as follows:
- Run $TAcc (A, R)$ and obtain the Merkle tree’s root $u \in {0, 1}^{n k}$ .
- Let $p k_{i} = d^{'} = bin (A \cdot x^{'} mod q)$ . Generate a witness
  
  $w^{'} = ((j_{1}^{'}, \dots, j_{l}^{'}) \in {0, 1}^{l}, (w_{l}^{'} \dots, w_{1}^{'}) \in {({0, 1}^{n k})}^{l})$
  
  to the fact that $d^{'} \in R$ by running $TWitness (A, R, d^{'})$ , i.e., $d^{'}$ was properly accumulated in $u$ .
- Let $B = PRG (s)$ . Compute $b^{'} = B \cdot x^{'} mod q$ and generate a $NIZKAoK$ $Π^{'}$ as in the signing algorithm to demonstrate the possession of a valid pair $(p k_{i}, s k_{i}) = (d^{'}, x^{'})$ such that $b^{'} = B \cdot x^{'} mod q$ and that $d^{'} \in R$ , i.e.,
  
  $Π^{'} = ({{CMT}_{i}^{'}}_{i = 1}^{κ}, {CH}^{'}, {{RSP}_{i}^{'}}_{i = 1}^{κ}),$
  
  where
  
  ${CH}^{'} = H_{FS} ({{CMT}_{i}^{'}}_{i = 1}^{κ}, A, B, u, b^{'}, R) \in {1, 2, 3}^{κ} .$
- Output $ξ_{i} = (s, b^{'}, Π^{'})$ . Note that $ξ_{i}$ can be seen just as a signature on the empty message with the given seed s (instead of choosing a random seed by the algorithm itself).
$EvidenceCheck (pp, R, i, ξ_{i}, Σ)$ : On inputs $pp, R, i, ξ_{i}, Σ$ , the evidence $ξ_{i}$ is checked as follows:
- Check the validity of $ξ_{i}$ and $Σ$ by verifying the underlying protocols. If either is invalid, then output “reject”.
- If $(s, b^{'}) = (s, b)$ , then output “confirmation”; otherwise, output “disavowal”.

Analysis of Our NDRS Scheme

We first briefly analyze the correctness and efficiency properties.

Theorem 3

(Correctness and Efficiency). The NDRS scheme described in the previous section is correct and produces signatures of bit-size

\tilde{O} (n \cdot log N)

Correctness. It is easy to check that:

By the perfect completeness of the argument system presented in the previous section, each member of a ring is always capable of obtaining a tuple $(x, d, w)$ such that

$((A, B, u, b), d, w, x) \in R_{NDRS} .$

Thus, by the Fiat-Shamir heuristic, the ring signature on M is valid.
Meanwhile, for any signature $Σ = (s, b, Π)$ , the real signer can always produce a piece of valid evidence $ξ = (s, b^{'}, Π^{'})$ such that $b = b^{'}$ , i.e., $EvidenceCheck$ outputs ‘confirmation’.
By the randomness of the secret keys $x, x^{'} \leftarrow {0, 1}^{m}$ , the non-real signer can always produce a piece of valid evidence $\tilde{ξ} = (s, \tilde{b}, \tilde{Π})$ such that $b = B \cdot x mod q \neq b^{'} = B \cdot x^{'} mod q$ with overwhelming probability.

Efficiency. It is not hard to check that the underlying interactive procedure in previous section has communication cost

\tilde{O} (l \cdot n)

; therefore, the resulting signature has bit-size

\tilde{O} (κ \cdot l \cdot n + n) = \tilde{O} (n \cdot log N)

Now, we analyze the security requirements: anonymity, traceability, and non-frameability.

Theorem 4

(Anonymity). Assume that

COM

is a statistical hiding commitment scheme. Then, our NDRS scheme provides statistical anonymity in the random oracle model.

Proof.

We consider a sequence of games. The challenger

C

runs experiment

{Exp}_{N D R S, A}^{anon - 0} (n)

in the first game, while, in the last one, it runs

{Exp}_{N D R S, A}^{anon - 1} (n)

Game G $_{0}^{(b)}$ :

Exactly, it is the real experiment

{Exp}_{N D R S, A}^{anon - b} (n)

, where the adversary is given a challenge signature

Σ^{*} \leftarrow Sign (pp, {p k_{i_{0}}, p k_{i_{1}}}, s k_{i_{b}}, M^{*})

. Namely, given

(i_{0}, i_{1}, M^{*})

, the challenger

C

chooses a random

b \leftarrow {0, 1}

and computes a legitimate signature

Σ^{*}

using the secret key

s k_{i_{b}} = x_{i_{b}}

of user

i_{b}

Run $TAcc (A, R)$ and obtain $u \in {0, 1}^{n k}$ , where $R = {p k_{i_{0}}, p k_{i_{1}}}$ .
Run $TWitness (A, R, d_{i_{b}})$ and obtain a witness $w_{i_{b}}$ to the fact that $d_{i_{b}} = A \cdot x_{i_{b}} mod q \in R$ .
Sample a seed $s \leftarrow {0, 1}^{n}$ , generate matrix $B = PRG (s) \in Z_{q}^{n \times m}$ and compute $b = B \cdot x_{i_{b}} mod q$ . Then, produce a $NIZKAoK$ $Π$ with public input $(A, B, u, b)$ and prover’s witness $(d_{i_{b}}, w_{i_{b}}, x_{i_{b}})$ , i.e.,

$Π = ({{CMT}_{i}}_{i = 1}^{κ}, CH, {{RSP}_{i}}_{i = 1}^{κ}),$

where

$CH = H_{FS} (M^{*}, {{CMT}_{i}}_{i = 1}^{κ}, A, B, u, b, R) \in {1, 2, 3}^{κ} .$
Output $Σ^{*} = (B, b, Π)$ .

Game G $_{1}$ :

Generally, this game is identical to G

_{0}^{(b)}

, except that the challenge signature

Σ^{*}

is made independent of the coin b, while preserving the statistical closeness to G

_{0}^{(b)}

. In more detail, the following modifications are introduced with respect to G

_{0}^{(b)}

In Step 3, we change how the vector $b$ is generated. Specifically, $C$ samples $b \leftarrow Z_{q}^{n}$ uniformly at random, instead of computing $b = B \cdot x_{i_{b}} mod q$ .
In addition, in Step 3, the proof $Π$ contained in the challenge signature $Σ^{*}$ is produced in the simulation manner by $C$ ’s programming on the random oracle $H_{FS} (\cdot)$ .
(a)
For each $j \in [κ]$ , choose a ‘fake challenge’ ${\bar{C h}}_{j} \leftarrow {1, 2, 3}$ and prepare the ‘commitment’ ${CMT}_{j}$ according to ${\bar{C h}}_{j}$ . Then, randomly pick a ‘real challenge’ $C h_{j} \leftarrow {1, 2, 3} ∖ {{\bar{C h}}_{j}}$ .
(b)
Program the random oracle and set

$CH = {C h_{j}}_{j = 1}^{κ} = H_{FS} (M^{*}, {{CMT}_{j}}_{j = 1}^{κ}, A, B, u, b, R) .$

(c)
Prepare the ‘response’ ${{RSP}_{j}}_{j = 1}^{κ}$ in accordance with the normal procedure.
(d)
Output

$Σ^{*} = (s, b, Π) = (s, b, {{CMT}_{i}}_{i = 1}^{κ}, CH, {{RSP}_{i}}_{i = 1}^{κ}) .$

Observe that, for each

j \in [κ]

C h_{j}

is uniformly distributed in

{1, 2, 3}

, satisfying the requirement on the output of the random oracle. Besides,

{CMT}_{j}

and

{RSP}_{j}

are prepared in the same way as in Lemma A2 for proving the zero-knowledge property, implying that the challenge signature is valid. Finally, notice that the vector

b

in this game or G

_{0}^{(b)}

follows a uniform distribution over

Z_{q}^{n}

. As a result, G

_{0}^{(b)}

and G

_{1}

are statistically indistinguishable.

Now, we obtain a sequence of indistinguishable games G

_{0}^{(0)}

, G

_{1}

and G

_{0}^{(1)}

. Since G

_{1}

is independent of the random coin b, the advantage of

A

in G

_{1}

is 0. Then, we have the advantage of

A

in G

_{0}^{(0)}

and G

_{0}^{(1)}

is negligible. This completes the proof. □

Next, we prove the traceability and the non-frameability. Before doing so, we first recall two useful lemmas.

Lemma 1

(Reference [8]). For any matrix

A \in Z_{q}^{n \times m}

and a uniform random

x \in {0, 1}^{m}

, the probability that there exists another

x^{'} \in {0, 1}^{m} ∖ {x}

such that

A \cdot x = A \cdot x^{'} mod q

is at least

1 - 2^{n \cdot log q - m}

Lemma 2

(Reference [13]). Let

SS

be a signature scheme with security parameter n. Let

A

be a PPT algorithm whose input consists only of public data and which can ask

q_{H} > 0

queries to the random oracle. Assume that

A

produces within time bound T a valid signature

({{CMT}_{i}}_{i = 1}^{κ}, CH, {{RSP}_{i}}_{i = 1}^{κ})

of message M with probability ϵ. Then, within time

32 \cdot T \cdot q_{H} / ϵ

and with probability

ϵ^{'} > 1 / 2

, a replay of

A

outputs 3 valid signatures of M:

\begin{matrix} ({{CMT}_{i}}_{i = 1}^{κ}, {CH}^{(1)}, {{RSP}_{i}^{(1)}}_{i = 1}^{κ}), ({{CMT}_{i}}_{i = 1}^{κ}, {CH}^{(2)}, {{RSP}_{i}^{(2)}}_{i = 1}^{κ}), \\ ({{CMT}_{i}}_{i = 1}^{κ}, {CH}^{(3)}, {{RSP}_{i}^{(3)}}_{i = 1}^{κ}) \end{matrix}

for the same

{{CMT}_{i}}_{i = 1}^{κ}

such that

{CH}^{(1)}, {CH}^{(2)}, {CH}^{(3)}

are pairwise distinct.

Theorem 5

(Traceability and Non-frameability). Our NDRS scheme provides traceability and non-frameability in the random oracle model if the

{SIVP}_{\tilde{O} (n)}

is hard.

Proof.

Assume that there exists a PPT

A

has nonnegligible advantage

ϵ

in the experiment Exp

_{N D R S, A}^{trace} (n)

or Exp

_{N D R S, A}^{nf} (n)

, i.e.,

A

is able to output a valid signature

Σ^{*}

on message

M^{*}

under some ring

R^{*} = (p k_{i_{0}}, \dots, p k_{i_{r}}) = (d_{0}, \dots, d_{r})

such that

either $EvidenceCheck (pp, R^{*}, i_{j}, ξ_{i_{j}}, Σ^{*})$ will output ‘disavowal’ for each $j \in {0, \dots, r}$ , where $ξ_{i_{j}}$ is a piece of evidence generated by user $i_{j}$ ;
or $EvidenceCheck (pp, R^{*}, i_{j^{*}}, ξ_{i_{j^{*}}}, Σ^{*})$ will output ‘confirmation’ for some honest user $i_{j^{*}}$ .

We construct an algorithm

B

that solves the

{SIVP}_{\tilde{O} (n)}

problem with nonnegligible probability. Let

pp = A

. During the game,

B

generates the secrets of all the queried users as in the real scheme. With these secret keys,

B

is capable of faithfully answering all the queries. For the random oracle

H_{FS} (\cdot)

, we assume without loss of generality that: (1)

A

makes any given query to

H_{FS} (\cdot)

only once; (2) if

A

outputs a signature, then

A

had previously queried

H_{FS} (\cdot)

When

A

halts, it outputs a valid triple

(R^{*}, M^{*}, Σ^{*})

, where

Σ^{*} = (s^{*}, b^{*}, {{CMT}_{i}^{*}}_{i = 1}^{κ}, {CH}^{*}, {{RSP}_{i}^{*}}_{i = 1}^{κ}) .

We denote by

q_{H}

the upper bound on the number of queries that

A

makes to

H_{FS} (\cdot)

Then, by Lemma 2, when

B

runs up to

32 \cdot q_{H} / ϵ

extra executions of

A

with the same random tap and inputs as in the first execution, with probability at least

1 / 2

A

will get a 3-fork responses

{CH}^{(1)}, {CH}^{(2)}, {CH}^{(3)}

(pairwise distinct) from the oracle

H_{FS} (\cdot)

With probability

1 - {(7 / 9)}^{κ}

, there exists some

j \in [κ]

for which the j-th bits of

{CH}^{(1)}, {CH}^{(2)}

, and

{CH}^{(3)}

are

{C h_{j}^{(1)}, C h_{j}^{(2)}, C h_{j}^{(3)}} = {1, 2, 3}

. By the soundness of the argument system for the relation

R_{NDRS}

B

is able to extract a tuple

(d^{*}, w^{*}, x^{*})

from the responses

{RSP}_{j}^{(1)}, {RSP}_{j}^{(2)}, {RSP}_{j}^{(3)}

such that

A \cdot x^{*} = G \cdot d^{*} mod q, TVerify (A, u^{*}, d^{*}, w^{*}) = 1 .

According to the value of

d^{*}

, there are two cases:

$d^{*} \notin R^{*} = (d_{0}, \dots, d_{r})$ . This means $B$ can use $(R^{*}, d^{*}, w^{*})$ to break the security of the underlying accumulator, whose security is based on the assumption that ${SIVP}_{\tilde{O} (n)}$ is hard [8].
$d^{*} \in R^{*} = (d_{0}, \dots, d_{r})$ , i.e., $d^{*} = d_{j^{*}}$ . Note that the secret key $s k_{i_{j^{*}}}$ consists of a vector $x_{i_{j^{*}}} \in {0, 1}^{m}$ such that $A \cdot x_{i_{j^{*}}} = G \cdot d_{j^{*}} mod q$ . If $x_{i_{j^{*}}} \neq x^{*}$ , then $x_{i_{j^{*}}} - x^{*} \in {- 1, 0, 1}^{m}$ is a valid solution for the ${SIS}_{n, m, q, 1}$ instance $A$ .
According to the experiments with respect to traceability and non-frameability, we distinguish the following two cases to discuss the probability that $x_{i_{j^{*}}} \neq x^{*}$ .
-
In the experiment Exp $_{N D R S, A}^{trace} (n)$ , $A$ has corrupted user $i_{j^{*}}$ , acts as the real malicious signer, and manages to evade the traceability. We claim that $x_{i_{j^{*}}} \neq x^{*}$ , since $A$ will otherwise be detected as the real singer by the algorithm $EvidenceCheck$ $(pp, R^{*}, i_{j^{*}}, ξ_{i_{j^{*}}}, Σ)$ , where $ξ_{i_{j^{*}}}$ contains an element $b = B^{*} \cdot x_{i_{j^{*}}} mod q$ .
-
In the experiment Exp $_{N D R S, A}^{nf} (n)$ , $A$ did not corrupt user $i_{j^{*}}$ , and temps to produce a valid signature such that the target victim $i_{j^{*}}$ will be detected as the real signer. We claim that $x_{i_{j^{*}}} \neq x^{*}$ with probability greater than $1 / 2$ by the following two facts: (1) There exists another vector $x^{*} \in {0, 1}^{m}$ such that $A \cdot x^{*} = A \cdot x_{i_{j^{*}}} mod q$ by Lemma 1. (2) The underlying argument system is zero-knowledge, which implies witness indistinguishability; thus, $A$ can hardly get useful information from the signing queries.

In conclusion, in the experiment Exp

_{N D R S, A}^{trace} (n)

or Exp

_{N D R S, A}^{nf} (n)

, a successful attacker

A

implies an attacker

B

that either defeats the soundness of the argument system, or breaks the security of the accumulator, or directly solves an

{SIS}_{n, m, q, 1}^{\infty}

instance

A

. Thus, our scheme provides traceability and non-frameability in the random oracle model, assuming that the

{SIVP}_{\tilde{O} (n)}

problem is hard. □

5. Conclusions

In this work, we propose an efficient lattice-based NDRS scheme by using the techniques developed in Reference [8]. Our scheme has signature size only logarithmic to the ring size, and we prove its security in the random oracle model under the SIS assumption. Notice that, in our NDRS scheme, each secret key can only be used, at most,

k - 1

times for producing ring signatures, where

k = log q

; otherwise, the secret key will be figured out from

B

’s and corresponding

b

’s. The direct way to increase the number of ring signatures for each user is to increase the parameter q, which will reduce efficiency. A better way is to develop new techniques that is able to authenticate the user’s identity while producing the ring signature for relative small q. We leave it as a future work.

Author Contributions

Conceptualization, H.J. and Y.Z.; methodology, H.J. and Y.Z.; validation, C.T. and Y.Z.; investigation, H.J.; resources, Y.Z.; writing—original draft preparation, H.J.; writing—review and editing, C.T. and Y.Z.; funding acquisition, H.J. and C.T. All authors have read and agreed to the published version of the manuscript.

Funding

This research was funded by the National Key R&D Program of China grant number 2017YFB0802000, the Young Scientists Fund grant numbers 61802075, 61802241, 61902303, the National Natural Science Foundation of China grant numbers 61972457, U19B2021, the Guangdong Province Natural Science Foundation of Major Basic Research and Cultivation Project grant number 2015A030308016, the Project of Ordinary University Innovation Team Construction of Guangdong Province grant number 2015KCXTD014, the Collaborative Innovation Major Projects of Bureau of Education of Guangzhou City grant number 1201610005, the National Natural Science Foundation of Shaanxi Province grant number 2020ZDLGY08-04, Natural Science Basic Research Program of Shaanxi Province grant number 2020JQ-832.

Conflicts of Interest

The authors declare no conflict of interest.

Appendix A. Proof of Theorem 2

Our proof follows closely from that of Lemma 4 in Reference [8].

Completeness and Efficiency. It can be checked that the protocol has perfect completeness: if

P

is honest and follows the protocol, then

V

always outputs 1. The communication cost of the protocol is of order

\tilde{O} (l \cdot m \cdot log q) = \tilde{O} (l \cdot n)

Lemma A1

(Zero-Knowledge Property). Assume that

COM

is a statistical hiding commitment scheme, then the protocol is a statistical zero-knowledge proof.

Proof.

To show the zero-knowledge property, we construct an efficient simulator

S

that outputs a simulated transcript statistically indistinguishable from the one produced by the honest prover.

The simulator

S

first randomly samples

\bar{C h} \leftarrow {1, 2, 3}

, which serves as a prediction of the challenge value that

\hat{V}

will not choose.

$\bar{C h} = 1$

First,

S

computes

x^{'} \in Z_{q}^{2 m}, v_{1}^{'}, \dots, v_{l}^{'} \in Z_{q}^{m}

and

z_{1}^{'}, \dots, z_{l}^{'}, y_{1}^{'}, \dots, y_{l}^{'} \in Z_{q}^{2 m}

such that

\begin{matrix} \hat{A} \cdot x^{'} & = G^{*} \cdot v_{l}^{'} mod q; \\ \hat{B} \cdot x^{'} & = b mod q; \\ A^{*} \cdot z_{1}^{'} + A^{*} \cdot y_{1}^{'} & = G \cdot u mod q; \\ A^{*} \cdot z_{i + 1}^{'} + A^{*} \cdot y_{i + 1}^{'} & = G^{*} \cdot v_{i}^{'} mod q \forall i \in [l - 1] . \end{matrix}

Then, sample randomness

ρ_{1}, ρ_{2}, ρ_{3}

for

COM

and

\begin{matrix} τ \leftarrow S_{2 m}; b_{1}, \dots, b_{l} \leftarrow {0, 1}; π_{1}, \dots, π_{l}, ϕ_{1}, \dots, ϕ_{l} \leftarrow S_{m} \\ r_{x}; r_{v_{1}}, \dots, r_{v_{l}} \leftarrow Z_{q}^{m}; r_{z_{1}}, \dots, r_{z_{l}}, r_{y_{1}}, \dots, r_{y_{l}} \leftarrow Z_{q}^{2 m} . \end{matrix}

Finally, send to

V

the commitment CMT=

(C_{1}^{'}, C_{2}^{'}, C_{3}^{'})

, where

\begin{matrix} C_{1}^{'} & = COM (τ; \hat{A} \cdot r_{x} - G^{*} \cdot r_{v_{l}}; \hat{B} \cdot r_{x}; {b_{i}, π_{i}, ϕ_{i}}_{i = 1}^{l}; A^{*} \cdot r_{z_{1}} + A^{*} \cdot r_{y_{1}}; \\ {A^{*} \cdot r_{z_{i + 1}} + A^{*} \cdot r_{y_{i + 1}} - G^{*} \cdot r_{v_{i}}}_{i = 1}^{l - 1}; ρ_{1}) \\ C_{2}^{'} & = COM (τ (r_{x}); {π_{i} (r_{v_{i}}), F_{b_{i}, π_{i}} (r_{z_{i}}), F_{{\bar{b}}_{i}, ϕ_{i}} (r_{y_{i}})}_{i = 1}^{l}; ρ_{2}) \\ C_{3}^{'} & = COM (τ (x^{'} + r_{x}); {π_{i} (v_{i}^{'} + r_{v_{i}}), F_{b_{i}, π_{i}} (z_{i}^{'} + r_{z_{i}}), F_{{\bar{b}}_{i}, ϕ_{i}} (y_{i}^{'} + r_{y_{i}})}_{i = 1}^{l}; ρ_{3}) . \end{matrix}

After receiving

C h

from

\hat{V}

\hat{S}

responds as follows:

If $C h = 1$ : Output ⊥ and abort.
If $C h = 2$ : Send

$RSP = (τ; x^{'} + r_{x}; {b_{i}, π_{i}, ϕ_{i}, v_{i}^{'} + r_{v_{i}}, z_{i}^{'} + r_{z_{i}}, y^{'} r_{y_{i}}}_{i = 1}^{l}; ρ_{1}; ρ_{3}) .$
If $C h = 3$ : Send

$RSP = (τ; r_{x}; {b_{i}, π_{i}, ϕ_{i}, r_{v_{i}}, r_{z_{i}}, r_{y_{i}}}_{i = 1}^{l}; ρ_{1}; ρ_{2}) .$

$\bar{C h} = 2$

First,

S

samples

\begin{matrix} x^{'} \leftarrow B_{2 m}^{m}; j_{1}^{'}, \dots, j_{l}^{'} \leftarrow {0, 1}; v_{1}^{'}, \dots, v_{l}^{'}; w_{1}^{'}, \dots, w_{l}^{'} \leftarrow B_{m}^{n k}; \\ τ \leftarrow S_{2 m}; b_{1}, \dots, b_{l} \leftarrow {0, 1}; π_{1}, \dots, π_{l}, ϕ_{1}, \dots, ϕ_{l} \leftarrow S_{m} \\ r_{x}; r_{v_{1}}, \dots, r_{v_{l}} \leftarrow Z_{q}^{m}; r_{z_{1}}, \dots, r_{z_{l}}, r_{y_{1}}, \dots, r_{y_{l}} \leftarrow Z_{q}^{2 m} . \end{matrix}

Then, compute

z_{i}^{'} = ext (j_{i}^{'}, v_{i}^{'}), y_{i}^{'} = ext ({\bar{j}}_{i}^{'}, w_{i}^{'})

for each

j \in [l]

. Finally, send the commitment CMT computed as in case

\bar{C h} = 1

After receiving

C h

from

\hat{V}

\hat{S}

responds as follows.

If $C h = 1$ : Send

$RSP = (τ (x^{'}); τ (r_{x}); {j_{i}^{'} \oplus b_{i}, π_{i} (v_{i}^{'}), ϕ_{i} (w_{i}^{'}), π_{i} (r_{v_{i}}), F_{b_{i}, π_{i}} (}} r_{z_{i}}), F_{{\bar{b}}_{i}, ϕ_{i}} (r_{y_{i}})}_{i = 1}^{l}; ρ_{1}; ρ_{3}) .$
If $C h = 2$ : Output ⊥ and abort.
If $C h = 3$ : Send RSP computed in the same manner as in the case ( $\bar{C h} = 1, C h = 3$ ).

$\bar{C h} = 3$

: First,

S

sample randomness as in the case

\bar{C h} = 2

. Then, send the commitments CMT=

(C_{1}^{'}, C_{2}^{'}, C_{3}^{'})

, where

C_{2}^{'}, C_{3}^{'}

are computed as in

\bar{C h} = 1

, and

C_{1}^{'}

is computed as

\begin{matrix} C_{1}^{'} = COM (τ; \hat{A} \cdot (x^{'} + r_{x}) - G^{*} \cdot (v_{l}^{'} + r_{v_{l}}); \hat{B} \cdot (x^{'} + r_{x}); {b_{i}, π_{i}, ϕ_{i}}_{i = 1}^{l}; \\ A^{*} \cdot (z_{1}^{'} + r_{z_{1}}) + A^{*} \cdot (y_{1}^{'} + r_{y_{1}}) - G \cdot u; \\ {A^{*} \cdot (z_{i + 1}^{'} + r_{z_{i + 1}}) + A^{*} \cdot (y_{i + 1}^{'} + r_{y_{i + 1}}) - G^{*} \cdot (v_{i}^{'} + r_{v_{i}})}_{i = 1}^{l - 1}; ρ_{1}) . \end{matrix}

After receiving

C h

from

\hat{V}

\hat{S}

responds as follows.

If $C h = 1$ : Send RSP computed as in the case ( $\bar{C h} = 2, C h = 1$ ).
If $C h = 2$ : Send RSP computed as in the case ( $\bar{C h} = 1, C h = 2$ ).
If $C h = 3$ : Output ⊥ and abort.

Because

COM

is statistically hiding, we have that, whenever

S

does not halt, it will output an accepting transcript, whose distribution is statistically close to that of the real prover. Besides,

S

halts with probability

1 / 3

. Therefore,

S

can successfully emulate the honest prover with probability

2 / 3

. □

To show the argument of knowledge property, it is enough to show that the protocol has the special soundness property [24].

Lemma A2

(Argument of Knowledge Property). Assume that

COM

is a statistical hiding commitment scheme, and then there exists an efficient knowledge extractor

K

that, given 3 valid responses

({RSP}_{1}, {RSP}_{2}, {RSP}_{3})

to the same commitment

CMT

, outputs a triple

(d^{'}, w^{'}, x^{'})

such that

((A, B, u, b); d^{'}, w^{'}, x^{'}) \in R_{NDRS}

Proof.

Denote the 3 valid responses

({RSP}_{1}, {RSP}_{2}, {RSP}_{3})

to the same commitment

CMT

as follows:

\begin{matrix} {RSP}_{1} & = ({\tilde{x}}^{*}; {\tilde{r}}_{x}; {{\tilde{b}}_{i}, {\tilde{v}}_{i}^{*}, {\tilde{w}}_{i}^{*}, {\tilde{r}}_{v_{i}}, {\tilde{r}}_{z_{i}}, {\tilde{r}}_{y_{i}}}_{i = 1}^{l}; ρ_{2}; ρ_{3}), \\ {RSP}_{2} & = (τ^{'}; s_{x}; {b_{i}^{'}, π_{i}^{'}, ϕ_{i}^{'}, s_{v_{i}}, s_{z_{i}}, s_{y_{i}}}_{i = 1}^{l}; ρ_{1}; ρ_{3}), \\ {RSP}_{3} & = (τ^{''}; r_{x}^{'}; {b_{i}^{''}, π_{i}^{''}, ϕ_{i}^{''}, r_{v_{i}}^{'}, r_{z_{i}}^{'}, r_{y_{i}}^{'}}_{i = 1}^{l}; ρ_{1}; ρ_{2}) . \end{matrix}

The validity of RSP

_{1}

implies that

{\tilde{x}}^{*} \in B_{2 m}^{m}

and

\forall i \in [l] : {\tilde{v}}_{i}^{*}, {\tilde{w}}_{i}^{*} \in B_{m}^{n k}

. Besides, we have:

\begin{matrix} τ^{'} = τ^{''}; τ^{''} (r_{x}^{'}) = {\tilde{r}}_{x}; τ^{'} (s_{x}) = {\tilde{x}}^{*} + {\tilde{r}}_{x}, \\ \hat{A} \cdot s_{x} - G^{*} \cdot s_{v_{l}} = \hat{A} \cdot r_{x}^{'} - G^{*} \cdot r_{v_{l}^{'}} mod q, \\ \hat{B} \cdot s_{x} = b + \hat{B} \cdot r_{x}^{'} mod q, \\ A^{*} \cdot s_{z_{1}} + A^{*} \cdot s_{y_{1}} - G \cdot u = A^{*} \cdot r_{z_{1}}^{'} + A^{*} \cdot r_{y_{1}}^{'} mod q, \end{matrix}

and, for each

i \in [l - 1]

A^{*} \cdot s_{z_{i + 1}} + A^{*} \cdot s_{y_{i + 1}} - G^{*} \cdot s_{v_{i}} = A^{*} \cdot r_{z_{i + 1}}^{'} + A^{*} \cdot r_{y_{i + 1}}^{'} - G^{*} \cdot r_{v_{i}}^{'} mod q,

and, for all

i \in [l]

\begin{matrix} b_{i}^{'} = b_{i}^{''}; π^{'} = π^{''}; ϕ^{'} = ϕ^{''}, \\ π_{i}^{'} (s_{x}) = {\tilde{x}}^{*} + {\tilde{r}}_{x}; π_{i}^{''} (r_{v}^{'}) = {\tilde{r}}_{v_{i}}, \\ F_{b_{i}^{'}, π_{i}^{'}} (s_{z_{i}}) = ext ({\tilde{b}}_{i}, {\tilde{v}}_{i}^{*}) + {\tilde{r}}_{z_{i}}; F_{b_{i}^{''}, π_{i}^{''}} (r_{z_{i}}^{'}) = {\tilde{r}}_{z_{i}}, \\ F_{{\bar{b}}_{i}^{'}, ϕ_{i}^{'}} (s_{y_{i}}) = ext ({\tilde{b}}_{i}, {\tilde{w}}_{i}^{*}) + {\tilde{r}}_{y_{i}}; F_{{\bar{b}}_{i}^{''}, ϕ_{i}^{''}} (r_{y_{i}}^{'}) = {\tilde{r}}_{y_{i}} . \end{matrix}

Now, the knowledge extractor

K

takes the following steps to extract the secret.

First, let

x^{*} = τ^{' - 1} ({\tilde{x}}^{*})

, and, for each

i \in [l]

, let

j_{i} = {\tilde{b}}_{i} \oplus b_{i}^{'}; v_{i}^{*} = π_{i}^{' - 1} ({\tilde{v}}_{i}^{*}); w_{i}^{*} = ϕ_{i}^{' - 1} ({\tilde{w}}_{i}^{*}); z_{i} = s_{z_{i}} - r_{z_{i}}^{'}; y_{i} = s_{y_{i}} - r_{y_{i}}^{'} .

Note that

x^{*} \in B_{2 m}^{m}

, and, for each

i \in [l], v_{i}^{*}, w_{i}^{*} \in B_{m}^{n k}

. Besides,

$F_{b_{i}^{'}, π_{i}^{'}} (z_{i}) = ext ({\tilde{b}}_{i}, {\tilde{v}}_{i}^{*}) = ext (j_{i} \oplus b_{i}^{'}, π^{'} (v_{i}^{*})) \Leftrightarrow z_{i} = ext (j_{i}, v_{i}^{*})$ ,
$F_{{\bar{b}}_{i}^{'}, ϕ_{i}^{'}} (y_{i}) = ext ({\tilde{b}}_{i}, {\tilde{w}}_{i}^{*}) = ext ({\bar{j}}_{i} \oplus b_{i}^{'}, ϕ^{'} (w_{i}^{*})) \Leftrightarrow y_{i} = ext ({\bar{j}}_{i}, w_{i}^{*})$ .

Further more,

\hat{A} \cdot x^{*} = G^{*} \cdot v_{l}^{*} mod q, \hat{B} \cdot x^{*} = b mod q

and

\begin{matrix} A^{*} \cdot z_{1} + A^{*} \cdot y_{1} & = G \cdot u mod q, \\ A^{*} \cdot z_{i + 1} + A^{*} \cdot y_{i + 1} & = G^{*} \cdot v_{i}^{*} mod q \forall i \in [l - 1], \end{matrix}

which are equivalent to

\begin{matrix} A^{*} \cdot ext (j_{1}, v_{1}^{*}) + A^{*} \cdot ext ({\bar{j}}_{1}, w_{1}^{*}) & = G \cdot u mod q, \\ A^{*} \cdot ext (j_{i + 1}, v_{i + 1}^{*}) + A^{*} \cdot ext ({\bar{j}}_{i + 1}, w_{i + 1}^{*}) & = G^{*} \cdot v_{i}^{*} mod q \forall i \in [l - 1] . \end{matrix}

Then,

K

drops the last m coordinates from

x^{*}

and obtains

x^{'} \in {0, 1}^{m}

. In addition, by dropping the last

n k

coordinates of

v_{1}^{*}, \dots, v_{l}^{*}, w_{1}^{*}, \dots, w_{l}^{*}

, it obtains

v_{1}^{'}, \dots, v_{l}^{'}, w_{1}^{'}, \dots, w_{l}^{'} \in {0, 1}^{n k}

. Observe that

A \cdot x^{'} = G \cdot v_{l}^{'} mod q, B \cdot x^{'} = b mod q

. Thus, the following relations holds:

\begin{matrix} A \cdot ext (j_{1}, v_{1}^{'}) + A \cdot ext ({\bar{j}}_{1}, w_{1}^{'}) & = G \cdot u mod q, \\ A \cdot ext (j_{i + 1}, v_{i + 1}^{'}) + A \cdot ext ({\bar{j}}_{i + 1}, w_{i + 1}^{'}) & = G \cdot v_{i}^{'} mod q \forall i \in [l - 1], \end{matrix}

which are equivalent to

\begin{matrix} v_{0}^{'} = u, \\ v_{i}^{'} = {\bar{j}}_{i + 1} \cdot h_{A} (v_{i + 1}^{'}, w_{i + 1}^{'}) + j_{i + 1} \cdot h_{A} (w_{i + 1}^{'}, v_{i + 1}^{'}) . \end{matrix}

Finally, let

d^{'} = v_{l}^{'}

and

w^{'} = ((j_{1}, \dots, j_{l}), (w_{l}^{'}, \dots, w_{1}^{'}))

, then

Verify (A, u, d^{'}, w^{'}) = 1

, and output

d^{'}, w^{'}, x^{'}

, which satisfy

((A, B, u, d), d^{'}, w^{'}, x^{'}) \in R_{NDRS} .

This concludes the proof. □

References

Rivest, R.L.; Shamir, A.; Tauman, Y. How to leak a secret: Theory and applications of ring signatures. Theor. Comput. Sci. 2006, 3895, 164–186. [Google Scholar]
Naor, M. Deniable ring authentication. In CRYPTO 2002, Proceedings of the Annual International Cryptology Conference, Santa Barbara, CA, USA, 18–22 August 2002; Springer: Berlin/Heidelberg, Germany, 2002; pp. 481–498. [Google Scholar]
Dodis, Y.; Kiayias, A.; Nicolosi, A.; Shoup, V. Anonymous identification in Ad Hoc Groups. In EUROCRYPT 2004, Proceedings of the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, 2–6 May 2004; Springer: Berlin/Heidelberg, Germany, 2004; pp. 609–626. [Google Scholar]
Chaum, D.; van Heyst, E. Group signatures. In EUROCRYPT 1991, Proceedings of the Workshop on the Theory and Application of of Cryptographic Techniques, Brighton, UK, 8–11 April 1991; Springer: Berlin/Heidelberg, Germany, 1991; pp. 257–265. [Google Scholar]
Bellare, M.; Micciancio, D.; Warinschi, B. Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions. In EUROCRYPT 2003, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, 4–8 May 2003; Springer: Berlin/Heidelberg, Germany, 2003; pp. 614–629. [Google Scholar]
Boyen, X.; Waters, B. Compact group signatures without random oracles. In EUROCRYPT 2006, Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, 28 May–1 June 2006; Springer: Berlin/Heidelberg, Germany, 2006; pp. 427–444. [Google Scholar]
Groth, J. Fully anonymous group signatures without random oracles. In ASIACRYPT 2007, Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Kuching, Malaysia, 2–6 December 2007; Springer: Berlin/Heidelberg, Germany, 2007; pp. 164–180. [Google Scholar]
Libert, B.; Ling, S.; Nguyen, K.; Wang, H. Zero-knowledge arguments for lattice-based accumulators: Logarithmic-size ring signatures and group signatures without trapdoors. In EUROCRYPT 2016, Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, 8–12 May 2016; Springer: Berlin/Heidelberg, Germany, 2016; pp. 1–31. [Google Scholar]
Ling, S.; Nguyen, K.; Wang, H.; Xu, Y. Lattice-based group signatures: Achieving full dynamicity (and deniability) with ease. Theor. Comput. Sci. 2019, 783, 71–94. [Google Scholar] [CrossRef] [Green Version]
Komano, Y.; Ohta, K.; Shimbo, A.; Kawamura, S. Toward the fair anonymous signatures: Deniable ring signatures. In CT-RSA 2006, Proceedings of the Cryptographers’ Track at the RSA Conference, San Jose, CA, USA, 13–17 February 2006; Springer: Berlin/Heidelberg, Germany, 2006; pp. 174–191. [Google Scholar]
Shor, P.W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput 1997, 26, 1484–1509. [Google Scholar] [CrossRef] [Green Version]
Gao, W.; Chen, L.; Hu, Y.; Newton, C.J.; Wang, B.; Chen, J. Lattice-based deniable ring signatures. Int. J. Inf. Secur. 2019, 18, 355–370. [Google Scholar] [CrossRef]
Cheng, S.; Nguyen, K.; Wang, H. Policy-based signature scheme from lattices. Des. Codes Cryptogr. 2016, 81, 43–74. [Google Scholar] [CrossRef]
Libert, B.; Ling, S.; Nguyen, K.; Wang, H. Zero-knowledge arguments for lattice-based PRFs and applications to e-cash. In ASIACRYPT 2017, Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Hong Kong, China, 3–7 December 2017; Springer: Cham, Switzerland, 2017; pp. 304–335. [Google Scholar]
Stern, J. A new paradigm for public key identification. IEEE Trans. Inf. Theory 1996, 42, 1757–1768. [Google Scholar] [CrossRef] [Green Version]
Jia, H.; Tang, C. Cryptanalysis of a non-interactive deniable ring signature scheme. Int. J. Inf. Secur. 2020, 20, 103–112. [Google Scholar] [CrossRef]
Ajtai, M. Generating hard instances of lattice problems. Quad. Mat. 2004, 13, 1–32. [Google Scholar]
Micciancio, D.; Regev, O. Worst-case to average-case reductions based on Gaussian measure. SIAM J. Comput. 2007, 37, 267–302. [Google Scholar] [CrossRef] [Green Version]
Gentry, C.; Peikert, C.; Vaikuntanathan, V. Trapdoors for hard lattices and new cryptographic constructions. In STOC 2008, Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, Victoria, BC, Canada, 17–20 May 2008; ACM: Denver, CO, USA, 2008; pp. 197–206. [Google Scholar]
Micciancio, D.; Peikert, C. Hardness of SIS and LWE with small parameters. In CRYPTO 2013, Proceedings of the Annual Cryptology Conference, Santa Barbara, CA, USA, 18–22 August 2013; Springer: Berlin/Heidelberg, Germany, 2013; pp. 21–39. [Google Scholar]
Jain, A.; Krenn, S.; Pietrzak, K.; Tentes, A. Commitments and efficient zero-knowledge proofs from learning parity with noise. In ASIACRYPT 2012, Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, 2–6 December 2012; Springer: Cham, Switzerland, 2012; pp. 663–680. [Google Scholar]
Benhamouda, F.; Camenisch, J.; Krenn, S.; Lyubashevsky, V.; Neven, G. Better zero-knowledge proofs for lattice encryption and their application to group signatures. In ASIACRYPT 2014, Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, 7–11 December 2014; Springer: Cham, Switzerland, 2014; pp. 551–572. [Google Scholar]
Kawachi, A.; Tanaka, K.; Xagawa, K. Concurrently secure identification schemes based on the worst-case hardness of lattice problems. In ASIACRYPT 2008, Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, VIC, Australia, 7–11 December 2008; Springer: Cham, Switzerland, 2008; pp. 372–389. [Google Scholar]
Groth, J. Evaluating security of voting schemes in the universal composability framework. In ACNS 2004, Proceedings of the InInternational Conference on Applied Cryptography and Network Security, Yellow Mountains, China, 8–11 June 2004; Springer: Berlin/Heidelberg, Germany, 2004; pp. 46–60. [Google Scholar]

Figure 1. Experiments of anonymity, traceability, and non-frameability.

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

© 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Jia, H.; Tang, C.; Zhang, Y. Lattice-Based Logarithmic-Size Non-Interactive Deniable Ring Signatures. Entropy 2021, 23, 980. https://doi.org/10.3390/e23080980

AMA Style

Jia H, Tang C, Zhang Y. Lattice-Based Logarithmic-Size Non-Interactive Deniable Ring Signatures. Entropy. 2021; 23(8):980. https://doi.org/10.3390/e23080980

Chicago/Turabian Style

Jia, Huiwen, Chunming Tang, and Yanhua Zhang. 2021. "Lattice-Based Logarithmic-Size Non-Interactive Deniable Ring Signatures" Entropy 23, no. 8: 980. https://doi.org/10.3390/e23080980

APA Style

Jia, H., Tang, C., & Zhang, Y. (2021). Lattice-Based Logarithmic-Size Non-Interactive Deniable Ring Signatures. Entropy, 23(8), 980. https://doi.org/10.3390/e23080980

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Lattice-Based Logarithmic-Size Non-Interactive Deniable Ring Signatures

Abstract

1. Introduction

1.1. Contributions and Technical Overview

1.2. Related Works

1.3. Organizations

2. Preliminaries

2.1. Non-Interactive Deniable Ring Signature (NDRS)

2.2. Average-Case Lattice Problems

2.3. Statistical Zero-Knowledge Argument Systems

2.4. Lattice-Based Accumulator

3. The Underlying Zero-Knowledge Argument System

3.1. Description of the Interactive Protocol

3.2. Analysis of the Interactive Protocol

4. Our Non-Interactive Deniable Ring Signature Scheme from Lattices

Analysis of Our NDRS Scheme

5. Conclusions

Author Contributions

Funding

Conflicts of Interest

Appendix A. Proof of Theorem 2

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI