1 Introduction

Privacy is an important factor in many areas. For example, no one wants his/her own daily behaviours, either location information in the physical world or web-browsing history in the cyber world, to be known by others. There exist various kinds of anonymization technologies that can help one become “anonymous” and protect user privacy. However, this will raise another security concern. There are many services that are designated for a particular group of users, for example, those who have paid and subscribed for the service. Being totally anonymous prevents the service provider telling whether a user belongs to the subscribed group or not. Thus we need a kind of anonymous authentication mechanism to ensure the authenticity of users while privacy is preserved simultaneously.

Ring signature is a good candidate to provide anonymous authentication, especially to ad hoc group. A ring signature scheme (for examples [1–6, 8, 9, 13, 16, 18, 22, 24, 27–36, 38, 42–47]) allows members of a group to sign messages on behalf of the group without revealing their identities, i.e. signer anonymity. In addition, it is not possible to decide whether two signatures have been issued by the same group member. Different from a group signature scheme (for examples, [7, 10, 12]), the group formation is spontaneous and there is no group manager to revoke the identity of the signer. That is, under the assumption that each user is already associated with a public key of some standard signature scheme, a user can form a group by simply collecting the public keys of all the group members including his/her own. These diversion group members can be totally unaware of being conscripted into the group.

Ring signature schemes could be used for whistle blowing [38], anonymous membership authentication for ad hoc groups [9], anonymous data sharing [19], E-voting [14] and many other applications which do not want complicated group formation stage but require signer anonymity. For example, in the whistle blowing scenario, a whistleblower gives out a secret as well as a ring signature of the secret to the public. From the signature, the public can be sure that the secret is indeed given out by a group member while cannot figure out who the whistleblower is. At the same time, the whistleblower does not need any collaboration of other users who have been conscripted by him into the group of members associated with the ring signature. Hence the anonymity of the whistleblower is ensured and the public is also certain that the secret is indeed leaked by one of the group members associated with the ring signature.

Ring signature schemes can be used to derive other primitives as well. It had been utilized to construct non-interactive deniable ring authentication [40], perfect concurrent signature [41] and multi-designated verifiers signature [20].

Nevertheless, existing ring signature schemes need very heavy computations. All existing ring signature schemes require exponentiations, at least on the verification stage. (Some may require the execution of pairings, which is even computationally expensive) Usually the number of exponentiations required during the signing stage is proportional to the number of users included in the ring signature. Say, if the signature includes 10000 users, the signing stage requires at least 10000 exponentiations. This may not be a big problem for personal computers. However, the schemes will not be suitable in practice to be used in mobile devices as these computations will drain the battery quickly.

1.1 Our Contributions

In this paper, we address the problem specifically. Our solution does not require the signer or the verifier to execute any exponentiation or pairing. Both algorithms are considered heavy and not suitable for lightweight device (e.g. wireless sensor and RFID) to execute. Only hashing, modulus square and addition operations are needed in both stages. For a setting of n users, on average our new scheme requires \(n+4\) hashing, square and addition operations and one square-root operation for the signature generation. The verifier only requires n hashing, square and addition operations.

Note that our scheme is different from another primitive called online/offline ring signature [23]. Online/offline ring signature together with online/offline (identity-based) encryption [15, 17, 37], signcryption [25] and signature [26] belong to the paradigm of online/offline cryptogrpahy.

In an online/offline ring signature scheme, the signing part is splitted into two parts while some offline computations have to be completed before knowing the message and the set of public keys. While this will speed up the (online) signature generation, the verification cost of online/offline (ring) signature is not reduced. The scheme of [23] requires n exponentiations for verifying a ring signature containing n users. Nonetheless, despite the efficiency differences, both schemes are the same in terms of functionality. Thus we can regard our scheme is a further improvement of online/offline signature scheme in two ways: (1) We do not require any offline stage in the signing part; and (2) The verification is lightweight.

Paper Organisation. The remainder of this paper is organised as follows. Section 2 reviews the mathematical preliminaries and the syntax of ring signature. Our scheme is proposed in Sect. 3. Section 4 analyzes the performance of our scheme. We conclude the paper in Sect. 5.

2 Definitions

This section reviews the complexity assumption and definitions of ring signature.

2.1 Complexity Assumption

The security of our scheme relies on the factorization assumption with safe primes, which is defined as follows:

Definition 1

(Safe Prime). p is a safe prime if it is of the form \(2p' + 1\), where \(p'\) is also a prime.

Definition 2

(Factorization Assumption with Safe Prime). Let \(N = pq\) where p and q are k-bit length safe primes. Given N as the input, the goal of an algorithm of \({\mathcal {A}}\) is to output an unordered pair (p, q). \({\mathcal {A}}\) has at least an advantage of \(\epsilon \) if

$$\begin{aligned} \Pr [ {\mathcal {A}}(N) = {p,q} \ | \ N= pq ] \ge \epsilon . \end{aligned}$$

We say that the \((\epsilon ,\tau , k)\)-Factorization assumption holds if no algorithm running in time at most \(\tau \) can solve the factorization problem with advantage at least \(\epsilon \), where the modulus is a product of two safe primes and each is with k-bit length.

Definition 3

(Quadratic Residues). An integer \(y \in Z_{N}^*\) is called a quadratic residue modulo N if there exists an integer \(x\in Z_{N}^*\) such that: \(x^2=y \pmod N\). Let QR(N) denote the set of quadratic residues modulo N.

2.2 Security Model

Definition 4

A ring signature scheme consists of three algorithms:

  • Key-Gen \((k)\rightarrow (sk, pk)\): Key-Gen is a probabilistic algorithm taking as input a security parameter k. It returns the user secret key sk and public key pk.

  • Sign \((L,sk,m)\rightarrow \sigma \): Sign is a probabilistic algorithm taking (L, m, sk) as input, where L is the list of n public keys to be included in the ring signature, sk is the secret key of the actual signer (such that the corresponding public key is included in L) and m is the message to be signed. It returns a signature \(\sigma \).

  • Verify \((L,m,\sigma )\rightarrow \{\textsf {Accept}, \textsf {Reject}\}\). Verify is a deterministic algorithm taking \((L,m,\sigma )\) as input, where L is the list of n public keys of the ring members and \(m,\sigma )\) is the message/ring-signature pair. It outputs either Accept or Reject.

The security of a ring signature scheme consists of two requirements, namely Signer Ambiguity and Existential Unforgeability. They are defined as follows.

Definition 5

(Signer Ambiguity). Let \(L =\) \(\{ pk_1\), \(\cdots \), \(pk_n \}\) be the list of public keys and \(L_{sk} = \{sk_1,\) \(\cdots , sk_n \}\) be the corresponding secret keys. Each key is generated by Key-Gen. A ring signature scheme is said to be unconditionally signer ambiguous if, for any L, any message m, and any signature \(\sigma \leftarrow \textsf {Sign}(L, m, sk_\pi )\) where \(sk_\pi \in L_{sk}\), any unbound adversary \({\mathcal {A}}\) accepts as inputs L, m and \(\sigma \), outputs \(\pi \) with probability 1 / n.

It means that even all the private keys are known, it remains uncertain that who, out of n possible signers, actually produced the ring signature. Note that we do not allow \({\mathcal {A}}\) to know the random coins used to generate the signature.

Definition 6

(Existential Unforgeability). For a ring signature scheme with n public keys, the existential unforgeability is defined as the following game between a challenger and an adversary \({\mathcal {A}}\):

  1. 1.

    The challenger runs algorithm Key-Gen. Let \(L = \{ pk_1, \cdots , pk_n \}\) be the set of n public keys and \(L_{sk} = \{sk_1,\) \(\cdots , sk_n \}\) be the corresponding secret keys. \({\mathcal {A}}\) is given L.

  2. 2.

    \({\mathcal {A}}\) can adaptively queries the signing oracle \(q_S\) times: On input any message m and \(L'\) where \(L' \subseteq L\) (the corresponding secret keys are denoted by \({L'}_{sk}\)), the challenger returns a ring signature \(\sigma \leftarrow \textsf {Sign}(L', m, sk_\pi )\), where \(sk_\pi \in {L'}_{sk}\) and \(\textsf {Verify}(L',m,\sigma )\) \(= \textsf {Accept}\).

  3. 3.

    Finally \({\mathcal {A}}\) outputs a tuple \((L^*, m^*, \sigma ^*)\).

\({\mathcal {A}}\) wins the game if:

  1. 1.

    \(L^* \subseteq L\),

  2. 2.

    \((L^*, m^*)\) has not been submitted to the signing oracle, and

  3. 3.

    \(\textsf {Verify}(L^*,m^*,\sigma ^*)= \textsf {Accept}\)

We define \({\mathcal {A}}\)’s advantage in this game to be \(Adv({\mathcal {A}}) = \Pr [{\mathcal {A}}\text { wins}]\).

3 The Proposed Scheme

This section describes our proposal and its security analysis.

3.1 Construction

The details of our design are given as follows.

Let \(\kappa \) be security parameters. Each user selects two safe primes p, q of length k-bit, such that \(p = 2p' + 1, q= 2q' + 1\) where \(p', q'\) are also primes. The private key is (p, q) and public key is \(N = pq\).

Let \(L = \{N_1, \ldots , N_n\}\) be a list of n public keys to be included in the ring signature. Let \(H_i: \{0,1\}^* \rightarrow \mathbb {Z}_{N_i}\) be some hash functions for \(i = 1, \ldots , n\). \(H_i\) is a random oracle. W.l.o.g., we assume user n is the actual signer and thus the signer knows \(sk_n\) but not \(sk_i\) where \(i = 1, \ldots , n-1\). The actual signer executes the following steps:

  1. 1.

    Randomly generate \(r_n \in _R \mathbb {Z}_{N_n}\), compute \(c_1 = H_1(L,m, r_n)\).

  2. 2.

    (For \(n > 1\) only) For \(i=1, \ldots , n-1\), randomly generate \(x_i \in _R Z_{N_i}\) and compute \(c_{i+1} = H_{i+1}(L,m, c_i + x_i^2 \mod N_i )\).

  3. 3.

    Compute \(t_n = r_n - c_n \mod N_n\). If \(t_n \notin QR(N)\), repeat the following steps until \(t_n \in QR(N)\).

    • (For \(n>1\)) choose another random \(x_{n-1} \in _R Z_{N_{n-1}}\) and compute \(c_n = H_n(L,m, c_{n-1} + x_{n-1}^2 \mod N_{n-1})\).

    • (For \(n=1\)) choose another random \(r_1 \in _R \mathbb {Z}_{N_1}\) and compute \(c_1 = H_1(L,m, r_1)\).

  4. 4.

    Compute \(x_n = {t_n}^{1/2} \mod N_n\) using the knowledge of the factorization of \(N_n\).

Output the signature \(\sigma = (x_1, \ldots , x_n, c_1)\).

To verify a signature \(\sigma = (x_1, \ldots , x_n, c_1)\) for message m and public keys \(L = \{N_1, \ldots , N_n\}\), computes \(r_i = c_i + x_i^2 \mod N_i\) for \(i=1, \ldots , n\) and \(c_{i+1} = H_{i+1}(L,m,r_i)\) for \(i \ne n\). The Verify algorithm accepts the signature if \(c_1 = H_1(L,m,r_n)\). Otherwise, it rejects.

The correctness of our scheme is obvious and thus omitted.

3.2 Security Analysis

We will show that the proposed scheme is unconditionally signer ambiguous and existentially unforgeable.

Theorem 1

Our ring signature scheme is unconditionally signer ambiguous.

Proof

All \(x_i\) except \(x_n\) are taken randomly from \(\mathbb {Z}_{N_i}\). At the closing point, \(x_n \in \mathbb {Z}_{N_n}\) also distributes randomly as \(r_n\) is randomly chosen, \(c_n\) depends on previous \(x_{n-1}\) which is also a random number. Therefore, for fixed (L, m), \((x_1, \ldots , x_n)\) has \(\prod ^n_{i=1} N_i\) variation that are equally likely regardless of the closing point. The remaining \(c_1\) is uniquely determined from L, m and \(x_i\)’s and thus reveals no information of the actual signer.    \(\square \)

Theorem 2

Suppose the \((\epsilon ',\tau ', k)\)-Factorization assumption holds, then our ring signature scheme with n users is \((\tau , q_s, q_h, \epsilon )\)-secure against existential forgery under adaptive chosen message attacks in the random oracle model provided that:

$$\begin{aligned}\epsilon ' \le \frac{\Big ( 1 - \frac{q_h q_s}{N_{min}} \Big ) \Big ( 1 - \frac{1}{N_{min}} \Big ) \epsilon }{ q_h (q_h + 1) n }, \qquad \tau ' = \tau \end{aligned}$$

where \(N_{min}\) is the smallest modulus among n public keys, \(q_s\) is the maximum number of signing oracle queries allowed and \(q_h\) is the maximum number of \(H_i\) random oracle queries allowed.

Proof

The proof uses the approach described in [1]. (Readers may refer to [1] for some preliminary understanding.) Suppose the adversary \({\mathcal {A}}\) can forge the ring signature scheme with n users. We construct an algorithm \(\mathcal {S}\) that uses \({\mathcal {A}}\) to solve the factorization problem.

\(\mathcal {S}\) receives the problem instance N, which is the product of two safe prime numbers of length k-bit. \(\mathcal {S}\) is asked to output a non-trivial factor of N.

\(\mathcal {S}\) randomly chooses \(\pi \in _R [1,n]\) and assigns the public key of user \(\pi \) to be N (the problem instance). For the other \(n-1\) users’ public keys, \(\mathcal {S}\) generates them according to the algorithm. \(\mathcal {S}\) also chooses two integers u, v such that \(1 \le u \le v \le q_h\).

  • \(H_i\) Random Oracle: For simplicity, the \(H_i\) random oracles are treated as single oracle that takes \(Q_j = (i, L_j, m_j, r_j)\) as the j-th query and returns a random value that corresponds to \(H_i(L_j, m_j, r_j)\) maintaining consistency against duplicated queries.

  • Signing Oracle: Upon receiving the signing query for \((L_j, m_j)\), \(\mathcal {S}\) simulates the signing oracle in the following way.

    1. 1.

      Randomly choose \(c_1 \in _R \mathbb {Z}_{N_1}\).

    2. 2.

      For \(i = 1, \ldots , |L_j|\), randomly select integers \(x_i \in _R \mathbb {Z}_{N_i}\), compute \(r_i = x_i^{2} + c_i \mod N_i\), and then compute \(c_{i+1} = H_{i+1}(L_j, m_j, r_j)\) if \(i \ne |L_j|\).

    3. 3.

      Assign \(c_1\) to the value of \(H_1(L_j, m_j, r_{|L_j|})\).

Since the queries form a ring, there exists at least one index, say \(\kappa \), in \(\{1, \ldots , n \}\) such that \(Q_u = ( \kappa + 1, L, m, r_{\kappa })\) and \(Q_v (\kappa , L, m, r_{\kappa - 1})\) satisfy \(u \le v\). Namely, \(\kappa \) is in between the gap of query order. We call such (u, v) a gap index. Note that \(u=v\) happens only if \(n=1\), which means that the resulting L contains only one public-key. If there are two or more gap indices with regard to a signature, only the smallest one is considered.

At the beginning of the simulation, \(\mathcal {S}\) has chosen a pair of index (u, v) randomly such that \(1 \le u \le v \le q_h\). If the guess is correct, \(\mathcal {S}\) receives \(Q_u = (\kappa + 1, L, m, r_{\kappa })\) and \(Q_v = (\kappa , L, m, r_{\kappa - 1})\) so that (u, v) is a gap index. When query \(Q_v\) is made (u-th query has been already made by this moment), \(\mathcal {S}\) returns \(c_{\kappa } = r_{\kappa } - R \mod N_\kappa \) (where \(R = r^2 \mod N_\kappa \) and \(r \in _R {N_\kappa }\) is chosen by \(\mathcal {S}\)) as the value of \(H_{\kappa }(L,m, r_{\kappa -1})\). If \({\mathcal {A}}\) is successful in forgery, it outputs \(x_{\kappa }\) that satisfies \(r_{\kappa } = c_{\kappa } + x_{\kappa }^{2} \mod N_{\kappa }\). Since \(r_{\kappa } = c_{\kappa } + R \mod N_{\kappa }\), we obtain \(x_{\kappa }\) as the square root of R with regard to \(N_{\kappa }\). That is, \(x_{\kappa }^2 = R \mod N_{\kappa }\) or \(x_{\kappa }^2 = r^2 \mod N_{\kappa }\). With half probability, \(x_{\kappa } \ne r\). That is, \(x_{\kappa } - r\) and \(x_{\kappa } + r\) are two non-trivial factors of \(N_{\kappa }\).

\(\mathcal {S}\) is successful if

  1. 1.

    \({\mathcal {A}}\) outputs a valid forged signature;

  2. 2.

    There is no abortion or failure in any oracle simulation; and

  3. 3.

    All guesses are correct.

Suppose \({\mathcal {A}}\) outputs a valid forged signature with probability at least \(\epsilon \).

\(\mathcal {S}\) fails if Step 3 in the signing oracle simulation causes inconsistency in \(H_1\). It happens with probability at most \(q_h / N_{min}\) where \(N_{min}\) is the smallest \(N_i\) in L. Hence, the simulation is successful \(q_s\) times with probability at least

$$\begin{aligned} \Big ( 1 - \frac{q_h}{N_{min}} \Big )^{q_s} \ge 1 - \frac{q_h q_s}{N_{min}}. \end{aligned}$$

For \(H_i\) random oracle, with probability at least \(1 - 1 / N_{min}\), there exist queries \(Q_j = (i+1, L, m, r_i)\) for all \(i = 1, \ldots , n\) due to the ideal randomness of hash function.

At the beginning of the simulation, \(\mathcal {B}\) selects a pair of index (u, v). With probability \(2 / q_h (q_h + 1)\), the guess is correct. \(\mathcal {B}\) needs to guess the index of the user corresponding to the (u, v) gap. \(\mathcal {B}\) is correct if \(\pi = \kappa \). This happens with probability 1 / n. Finally, with probability 1 / 2, \(x \ne r\) for the square root of R.

Combining all cases, the overall successful probability of \(\mathcal {B}\) is at least

$$\begin{aligned} \frac{\Big ( 1 - \frac{q_h q_s}{N_{min}} \Big ) \Big ( 1 - \frac{1}{N_{min}} \Big ) \epsilon }{ q_h (q_h + 1) n } \end{aligned}$$

The running time of \(\mathcal {S}\) is almost the same as \(\tau \) as \(\mathcal {S}\) runs \({\mathcal {A}}\) only once and the simulation cost for the signing oracle and the random oracles are assumed to be sufficiently smaller than \(\tau \). This contradicts the assumption that the \((\epsilon ',\tau ', k)\)-Factorization assumption holds where

$$\begin{aligned}\epsilon ' \le \frac{ \Big ( 1 - \frac{q_h q_s}{N_{min}} \Big ) \Big ( 1 - \frac{1}{N_{min}} \Big ) \epsilon }{ q_h (q_h + 1) n }, \qquad \tau ' = \tau \end{aligned}$$

This completes our proof.    \(\square \)

4 Efficiency Analysis

4.1 Comparison of Existing Ring Signatures

The following table (Table 1) summarizes the time complexities of existing ring signatures. We breakdown the time complexity of the protocol into the number of exponentiations (EXP) and pairings (PAIR) (the other operation such as hashing or multiplication is relatively small when compared to exponentiation and pairing)Footnote 1. The running time of a pairing operation is about 2 to 3 times of an exponentiation. Let n be the size of the ring. We split the analysis into signing and verification. Note that no scheme in the comparison requires any pairing opeartions in the signing stage.

Table 1. Time complexities of existing ring signatures.
Full size table

4.2 Running Time

We also implement our scheme to analyze the running time. Details are as follows:

  • Equipment: Thinkpad x201s, Intel(R) Core\(^\mathtt{TM}\) I7 processor I7-640LM (2.13 GHz) with dual-core, 2.8 GB RAM running on 32 bits ubuntu 12.04

  • Key length: 1024 bits

  • Number of running times: average by 80,000,000 times

  • Library used: openSSL linux

  • Running time: It takes 0.000568101266 ms for an additional operation over modulus (1024 bits), 0.003478101266 ms for a square operation over modulus (1024 bits), 12.877974683544 ms for an exponentiation operation over modulus (1024 bits). Suppose there are n users included in the signature. Our scheme takes around \((0.0040462\,\times \,n)\) ms for signing and verification.

5 Conclusion

In this paper, we have proposed a lightweight anonymous authentication protocol, the essential of which is actually a lightweight ring signature scheme. It is lightweight in the sense that it does not contain any exponentiation or pairing in both prover and verifier sides. Instead, it only requires a few hashing and modulus square operations. We believe it is particular suitable for lightweight devices such as sensors and RFID and those applications that require authentication and privacy simultaneously. In the future, we may incorporate the technique from lattices [21] to further improve the efficiency while keeping all desired features.