Logarithmic size ring signatures without random oracles
2015; Institution of Engineering and Technology; Volume: 10; Issue: 1 Linguagem: Inglês
10.1049/iet-ifs.2014.0428
ISSN1751-8717
AutoresClémentine Gritti, Willy Susilo, Thomas Plantard,
Tópico(s)Complexity and Algorithms in Graphs
ResumoIET Information SecurityVolume 10, Issue 1 p. 1-7 Research ArticleFree Access Logarithmic size ring signatures without random oracles Clémentine Gritti, Corresponding Author Clémentine Gritti cjpg967@uowmail.edu.au Centre for Computer and Information Security Research, School of Computer Science and Software Engineering, University of Wollongong, Wollongong, AustraliaSearch for more papers by this authorWilly Susilo, Willy Susilo Centre for Computer and Information Security Research, School of Computer Science and Software Engineering, University of Wollongong, Wollongong, AustraliaSearch for more papers by this authorThomas Plantard, Thomas Plantard Centre for Computer and Information Security Research, School of Computer Science and Software Engineering, University of Wollongong, Wollongong, AustraliaSearch for more papers by this author Clémentine Gritti, Corresponding Author Clémentine Gritti cjpg967@uowmail.edu.au Centre for Computer and Information Security Research, School of Computer Science and Software Engineering, University of Wollongong, Wollongong, AustraliaSearch for more papers by this authorWilly Susilo, Willy Susilo Centre for Computer and Information Security Research, School of Computer Science and Software Engineering, University of Wollongong, Wollongong, AustraliaSearch for more papers by this authorThomas Plantard, Thomas Plantard Centre for Computer and Information Security Research, School of Computer Science and Software Engineering, University of Wollongong, Wollongong, AustraliaSearch for more papers by this author First published: 01 January 2016 https://doi.org/10.1049/iet-ifs.2014.0428Citations: 3AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract Ring signatures enable a user to anonymously sign a message on behalf of group of users. In this study, the authors propose the first ring signature scheme whose size is O (log2 N), where N is the number of users in the ring. They achieve this result by improving Chandran et al.’s ring signature scheme presented at the International Colloquium on Automata, Languages and Programming 2007. Their scheme uses a common reference string and non-interactive zero-knowledge proofs. The security of their scheme is proven without requiring random oracles. 1 Introduction The notion of ring signature was put forth by Rivest et al. [1] in 2001. In such a scheme, anyone can sign a message on behalf of an ad-hoc created group (i.e. the ring) anonymously. In 2007, Chandran et al. [2] presented a novel approach to achieve a sub-linear size ring signature scheme without random oracles, with perfect anonymity in the common reference string model. Their scheme is proven secure under the strong Diffie–Hellman and the subgroup decision assumptions, by setting the ring as a matrix for N members. In this work, we aim to further reduce the size of a ring signature, which is a very challenging task. 1.1 Our contributions In this paper, we provide the first ring signature with logarithmic size without random oracles. To achieve our result, we extend the idea proposed by Chandran et al. [2]. We construct our scheme following their techniques using composite order groups with a bilinear map. We prove it secure under the strong Diffie–Hellman and the subgroup decision assumptions. We obtain perfect anonymity in the common reference string model. The crux of our scheme is that we achieve for the ring signatures size, where N is the number of members in the ring. In Table 1, we compare our scheme with the one from Chandran et al. [2] to highlight the difference in performance. Table 1. Comparison of the size of the ring signature and the number of elements in the signature between Chandran et al.’s work [2] and ours, including the size of the common reference string Scheme Size of the common reference string Size of the ring signature Number of elements in the signature Typical values for k = 128 N = 1000 N = 10 000 N = 100 000 Chandran et al.’s [2] O (k) 24292 76806 242869 our approach O (k) 8935 11912 14888 Let N be the number of members and k be the security parameter. 1.2 Our technique The novelty of our scheme is to construct the ring as a log2 (N)-dimensional hypercube for N members, which yields a logarithmic size ring signature scheme. A d -dimensional hypercube has N = 2d vertices and d 2d−1 edges. Each vertex corresponds to a d -bit binary string and two vertices are linked with an edge if and only if their binary strings differ in precisely one bit. Therefore each vertex is adjacent to d = log2 (N) other vertices, one for each bit position. We illustrate the hypercubes with N equal to 2, 4 and 8 in Fig. 1. Fig. 1Open in figure viewerPowerPoint N-vertex hypercube for N = 2, 4, 8 Two vertices are linked with an edge if and only their string differs in precisely one bit position. Diameters are shown in dashed line In [2], a grid is picked such that the diameter is of the square root of the number of the points on the graph, that is, . In our paper, we consider the hypercube as a graph which has the smallest diameter for a given number of points. Thus, the diameter is of the logarithm of number of the points on the graph, that is, log2 (N). In our approach, we use a log2 (N)-dimensional hypercube as a N -member ring to construct the signature. Each verification key v in the ring is indexed by a d -bit string, denoted as b1 b2 …bd. To retrieve v, we need to follow the path formed by all the bits, from b1 to bd. We obtain v as the vertex corresponding to b1 …bd. Moreover, the signature related to the verification key v has an equal size to the length of the path between two vertices of the hypercube, that is, between two points of the graph. We illustrate the graph with N equal to 16 in Fig. 2. Fig. 2Open in figure viewerPowerPoint Diameter is shown in dashed line and the squares represent the points through which the diameter passes; N = 16 In Fig. 3, we compare the paths in the grid and the hypercube. The paths start from point (resp. vertex) 0010 and finish at point (resp. vertex) 1100. We note that in the grid, the path is five-edge long, whereas in the hypercube, it is only three-edge long. This is due to that in a hypercube, we reach intermediate vertices that differ from their direct neighbours in only one bit. Since 0010 and 1100 differ in three bits (only the last bit remains unchanged), we must pass through 1010 and 1110 to reach 1100. In the grid, we pass through ‘useless’ points 0110 and 1101, increasing the number of edges in the path's length. The diameter of a hypercube is always shorter than the one of the grid and the same property holds for the paths between two given vertices (resp. points). While Chandran et al. [2] constructed their scheme based on a matrix, which is treated as a grid, our construction relies on structure of a hypercube. Hence, in our scheme, the verification keys will be the vertices of a hypercube of dimension log2 (N) and the size of the signature will depend on the path built to reach a targeted verification key. Fig. 3Open in figure viewerPowerPoint In the grid (resp. hypercube), the path is drawn from point (resp. vertex) 0010 to point (resp. vertex) 1100; N = 16. Grid's path is two edges longer than the hypercube's one. 1.3 Related work Ring signatures have been found very promising in many practical applications [3, 4]. Rivest et al. [1] proved their unconditional anonymous scheme is secure in the random oracle model. Zhang and Kim [5] incorporated the notion of identity-based cryptography to avoid the necessity of incorporating certificates. Subsequently, Au et al. constructed a certificate-based ring signature scheme in [6]. Traceable ring signature was proposed by Fujisaki and Suzuki [7]. Liu et al. [8] presented the first linkable ring signature scheme satisfying anonymity, linkability and spontaneity. Wang and Liu [9] introduced the notion of signer-admission ring signature, which is a combination of designated confirmer signatures and designated verifier proofs. In most practical applications, the description of the ring is linear to the number of members, but Dodis et al. [4] proposed a scheme that is independent of the size of the ring in the random oracle model. Chow et al. [10] constructed a scheme that proved secure against the adaptive chosen message attack without random oracles. In the same way, Bender et al. [11] suggested a scheme using generic ZAPs for non-deterministic polynomial time (NP) in the standard model, but it seems impractical. In addition, Shacham and Waters [12] gave a linear size ring signature, whose security relies on the computational setting of the new definitions of [11], without random oracles. Namely, they proposed a scheme anonymous against full key exposure and unforgeable with respect to insider corruption attacks. Finally, Boyen [13] proposed a construction of linear size in the common random string model with everlasting perfect anonymity. Schäge and Schwenk [14] constructed another ring signature scheme in the standard model using basic assumptions. 2 Preliminaries and definitions 2.1 Negligible function Let negl(k) be a function in the security parameter k. We say that negl(k) is a ‘negligible function’ if for all polynomials p (k), for all sufficiently large k, negl(k) < 1/p (k). 2.2 Bilinear composite order groups Let BMGen be a randomised algorithm that outputs as follows: and are multiplicative cyclic groups of order n = pq, g is a generator of , is an efficiently computable map such that: o Bilinearity: , , e (ua, vb) = e (u, v)ab, o Non-degeneracy: e (g, g) is a generator of whenever g is a generator of , the group operations on and can be performed efficiently. Let and be the unique subgroups of of orders p and q, respectively. We recall that maps u into . 2.3 Boneh–Boyen signature scheme Our approach is inspired by Chandran et al. [2], where the main ingredient of the construction is Boneh–Boyen signature scheme [15], proved existentially unforgeable under weak chosen message attack based on the strong Diffie–Hellman assumption. As in [2], one can translate the Boneh–Boyen's scheme into one in the composite group order model such that forging a signature in under weak chosen message attack is infeasible, based on the strong Diffie–Hellman assumption in . The Boneh–Boyen signature scheme consists of three algorithms: KeyGen: Given a tuple , pick at random and compute v = gsk. The key pair is (v, sk). Sign: Given a secret key and a message M ∈ {0, 1}l, output the signature δ = g(1/(sk +M)). By convention, 1/0 is defined to be 0, thus sk + M = 0⇒δ = 1. We have l < |p |. Verify: Given a public key v, a message M ∈ {0, 1}l and a signature , verify that e (δ, vgM) = e (g, g). If equality holds, output ‘Accept’; otherwise ‘Reject’. 2.4 Commitment and encryption schemes The commitment/encryption scheme based on the subgroup decision assumption proposed in [16] is employed in our construction. The assumption is defined in the next section. We construct a scheme where a public key v and an element h are description of the composite order group . This element h is random and of order either n for perfect hiding commitment or q for encryption. It implies that perfect hiding commitment keys look exactly the same as encryption keys. 2.5 Ring signature scheme We define a ring signature scheme as the following [2, 11]. Definition 1 (Ring signature).A ring signature comprises four probabilistic polynomial-time (PPT) algorithms as follows:• Gen (1k): on input the security parameter k, outputs a common reference string λ.• KeyGen (λ) is run by the user: on input a common reference string λ, outputs a public verification key v and a private signing key sk.• Sign (λ, sk, M, S): on input a message M and the ring S = {v1, …, vN }, outputs a signature δ along with (M, S). We require that (v, sk) is a valid key pair output by KeyGen and that v ∈ S.• Verify (λ, S, M, δ): on input a purported signature δ on a message M with respect to the ring of public keys S, outputs ‘Accept’ if the signature is correctly verified, otherwise ‘Reject’.Perfect Correctness: A ring signature (Gen, KeyGen, Sign, Verify) has perfect correctness if for all PPT adversary , the probability of is equal to 1. 3 Security 3.1 Security properties Intuitively, we require that a ring signature (Gen, KeyGen, Sign, Verify) has perfect anonymity if a signature on message M under ring S and key is indistinguishable from a signature on message M under ring S and key . The formal definition is as follows. Definition 2 (Perfect anonymity).Given a ring signature (Gen, KeyGen, Sign, Verify), a polynomial N (_), and a PPT adversary , we consider the following game: chooses the ring of verification keys S = {v1, …, vN(k) }, such that λ ← Gen (1k) and (vi, ski) ← KeyGen (λ), where i ∈ {1, …, N (k)}. is given access (throughout the entire game) to an oracle OSign, such that OSign (α, M, S) returns Sign (λ, skα, M, S), where vα ∈ S. outputs a message M, distinct indices i0, i1, and a ring S for which [i.e. and have been generated by the oracle KeyGen (λ)]. A random bit b is chosen, and is given the signature . The adversary outputs a bit b ′, and succeeds if b ′ = b. A ring signature scheme achieves perfect anonymity, if for any PPT adversary and any polynomial N (_), the success probability of in the above game is equal to 1/2. We also require that a ring signature (Gen, KeyGen, Sign, Verify) is unforgeable (regarding insider corruption) if it is not feasible to forge a ring signature on a message without controlling one of the members in the ring. Definition 3 (Computational unforgeability).A ring signature (Gen, KeyGen, Sign, Verify) is computationally unforgeable if for any PPT adversary and any polynomial N (_), the probability that succeeds in the following game is negligible: is given the ring of verification keys S = {v1, …, vN(k) }, such that λ ← Gen (1k) and (vi, ski) ← KeyGen (λ), where i ∈ {1, …, N (k)}. is given access to a generator oracle VKGen, where VKGen (α, wα) runs (vα, skα) ← KeyGen (λ, wα), such that wα is randomly selected by the oracle, and outputs vα. is given access to a signing oracle OSign, where OSign (α, M, S) outputs Sign (λ, skα, M, S), such that (vα, skα) has been generated by VKGen. is given access to a corrupt oracle Corrupt, where Corrupt (α) outputs skα. outputs (S *, M *, δ *), and succeeds if Verify (λ, S *, M *, δ *) = 1. We require that never queried (_, M *, S *), and S * only contains verification keys vα generated by VKGen, where α has not been corrupted. 3.2 Assumptions Definition 4 (Subgroup decision assumption).Given the generator BMGen, we define the following distribution The subgroup decision assumption holds if there is a negligible function ε (in the security parameter k) so for any non-uniform polynomial time adversary , we have Definition 5 (Strong Diffie–Hellman assumption).Given the generator BMGen, we define the following distribution The strong Diffie–Hellman assumption holds in if there is a negligible function ε (in the security parameter k) so for any non-uniform polynomial time adversary , we have 3.3 Non-interactive zero-knowledge proof To prove that a statement is true, we can use a non-interactive zero-knowledge (NIZK) proof which is ‘complete’ and ‘sound’, such that no interaction is needed between the prover and the verifier. Using results in [17] providing short common reference string and NIZK proofs for any NP language, Boyen and Waters [18] gave a NIZK proof for the statement γ = (g2M −1 hr)r verified by . For h of order n, the proof has perfect zero knowledge as γ is determined from the verification equation and thus, no information is leaked from the proof. For h of order q, the verification enables us to show that e (c, g−1) has order q, that implies M = 0 mod p or 1 mod p. In [19], general methods are presented for constructing simple and efficient NIZK proofs over bilinear groups. 4 Logarithmic-size ring signature scheme Let ring S = {v1, …, vN } be fixed and public. A signer knows ska corresponding to one of the verification keys in the ring S and wants to sign message M. The verification keys are issued as the ones in Boneh–Boyen signature scheme. The signer creates a signature as follows: The signer selects one-time signature keys (vkOT, skOT) ← OTGen (1k). The message M is signed following the one-time signature scheme. The verification key vkOT and the one-time signature are published. The signer certifies vkOT by signing it with Boneh–Boyen signature under va. The signer needs to hide va and the certifying signature on vkOT. Therefore he/she makes two perfectly hiding commitments to va and the signature, respectively. Then, the signer makes a NIZK proof that the commitments contain the aforementioned elements. The signer proves that the committed verification key is an element of ring S. The innovation in the scheme is the logarithmic size proof. The signer arranges S in a d -dimensional hypercube, where N = 2d (we carefully explain the process below). For i ∈ {1, …, d }, he/she commits from the first bit b1 to the last bit bd of the string a of the hypercube that contains va and makes a NIZK proof that the committed verification key appears in this vertex vb1 …bd. 4.1 Construction Gen generates a common reference string that contains the description of a composite order group and a public key for the perfectly hiding commitment scheme. Gen (1k): Let the perfectly hiding commitment scheme be as follows. Run . Set n = pq, pick at random and compute h = gx. Output . The users’ key generation algorithm KeyGen takes as input a common reference string and outputs a signing public–private key pair (v, sk). In this case, it will output keys for the Boneh–Boyen signature scheme that is secure against weak message attack. : Let the Boneh–Boyen signature scheme with public key (g, v) be as follows. Pick at random , and compute v = gsk. Output (v, sk). A user with keys (va, ska) wants to sign message M under the ring S = {v1, …, vN } of size N. Then, a is mapped to a d -bit binary string as follows: such that f :S → {b1 b2 …bd;bi ∈ {0, 1}, i ∈ {1, …, d }} is public and bijective. It is useful to think S as a d -dimensional hypercube: we assume the existence of a public map from S onto a d -dimensional hypercube that identifies each vka with exactly one vertex of the hypercube, labelled with a d -bit binary string. For instance, for , va corresponds to the vertex defined as b1 b2 …bd. The verification key v is seen as a point in a d -dimensional space, where d = log2 (N). A ring S contains N elements v indexed by log2 (N) bits. Informally, we construct the commitments using the following idea. From the vertex vb1 b2 …bd, there are d edges that reach d different vertices. These vertices differ from the vertex vb1 b2 …bd in exactly one bit. For instance, from v000…000, we can reach v000…001, v000…010, …, v010…000 and v100…000. In particular, from vb1 b2 …bi …bd, we can reach the vertex such that . Let * denote the sequence of bits from the j th position until the d th position such that 1 ≤ j ≤ d and for j ≤ i ≤ d, the bit is equal to either bi or (we only consider strings of bit length d). Thus, we can retrieve the verification key following the path formed by the vertices . More precisely, from the verification key va such that , we can reach either . Therefore when we want to reach va, we first access the first bit b1 of a, that is, . If we find , then we know that one of the direct neighbours is that we decide to reach. We then access the second bit b2 of a, that is, . We have already found , thus we may meet either or . If we find , we remain there. If we find , then we know that one of the direct neighbours is that we decide to reach. We apply the same methodology for the other bits b3, …, bd. Moreover, if we see the hypercube as a graph whose diameter is the smallest for a given number of points, then the resulting signature is of length of the path between two points of the graph. We illustrate the methodology to reach v for hypercubes with N equal to 4 and 8 in Fig. 4 First, establish a one-time signature on the message and the ring, such that the pair (vkOT, δOT) is public. Run (vkOT, skOT)←OTGen (1k), and δOT ←Sign (skOT, M, S). The pair (vkOT, δOT) is made public. Fig. 4Open in figure viewerPowerPoint N-vertex hypercube for N = 4, 8 Paths are shown in dashed lines to reach v11 and v011 We arbitrary start from v00 and v000, but we can start anywhere Pick at random and compute . Randomly choose and . δa is the signer's certifying signature on vkOT, and A and B are perfectly hiding commitments to va, δa, respectively. γB is a NIZK proof that A and B contain, respectively, a verification key and a signature on vkOT, using results from [17]. The rest of the protocol is a NIZK proof that A contains va ∈ S without revealing which one, using results from [17, 18]. For a = b1 b2 …bd, start the NIZK proof from the first bit b1 of a, then the second bit b2, and so on until the last bit bd. Let and , where * denotes the sequence of bits from the i + 1th position until the d th position such that, for i + 1 ≤ j ≤ d, the bit is equal to either bj or . Randomly choose , and set and . Set , and . More precisely, for i ∈ {1, …, d }, the commitments are chosen so that is a commitment to g whereas is a commitment to 1, that is, . The proofs are NIZK proofs such that each contains either g or 1. tells the verifier that there is exactly one that contains g, while the other commitment contains 1. Compute , which is a commitment to . Pick at random , and compute , and . Specifically, the are commitments to verification keys such that the i th bit of a is bi, for i = 1, …, d. In particular, is the commitment to verification key . The contain the bit bi of S paired with g. are NIZK proofs that contain elements that paired with g give the contents of . This demonstrates to the verifier that contain the bit bi in the indices of the verification keys in S. Compute for bd as the last bit of a. Here, is a commitment to . We recall that . γA is a NIZK proof that the content of A paired with g corresponds to the content in E. Output the signature : Verify that δOT is a one-time signature of M, S under vOT. Verify . Verify and for all 1 ≤ i ≤ d and . Compute and verify for all 1 ≤ i ≤ d. Compute and verify . If all the above steps verify correctly, then output ‘Accept’; otherwise, output ‘Reject’. 4.2 Security proofs Theorem 1.The quadruple (Gen, KeyGen, Sign, Verify) is a ring signature scheme with perfect correctness, perfect anonymity and computational unforgeability under the subgroup decision assumption, the strong Diffie–Hellman assumption and given that the one-time signature is unforgeable. Proof (Perfect correctness).For λ ←Gen (1k), for (v, sk)←KeyGen (λ), for any message M with respect to a ring S, we prove the perfect correctness by showing that the equalities in the algorithm Verify hold. Point 2: Verify the following equality Point 3: For i ∈ {1, …, d } Point 4: Verify the following equality for all i ∈ {1, …, d } Point 5: Verify the following equality Perfect anonymity: Following [17-19], we will prove that our scheme is secure in the anonymity game against adaptively chosen message attacks. Informally, the perfect anonymity comes from two intuitive arguments. First, for , and for some message M, , meaning that vkOT and δOT are similarly generated, regardless which signing key is used. Second, all the commitments are perfectly hiding and the proofs are perfectly zero knowledge, when h has order n. In addition, an adversary can tell whether h is a random generator of or with negligible probability using a reduction proof based on the subgroup decision problem.We assume there exist a simulator that plays the subgroup decision problem with probability and an adversary that wants to break the anonymity of the above ring signature scheme. In the game G0, the simulator computes h as an element in and in the game G1, it computes h as an element in . We denote the adversary's advantage in these games as and , respectively.We consider a simulator receiving the subgroup decision challenge . It then creates the public parameters as in the real scheme, and sends the parameters to an adversary and plays the anonymity game with it. If , then plays the normal game G0. If , then plays the hybrid game G1. We assume that is able to reply all the adaptively chosen message queries, that is, it is able to issue the signing keys for any user and to sign any message by any user, since it knows the challenge λ. At some point, chooses one message M and two identities i0 and i1 it wishes to be challenged on. We assume that the adversary had not previously made a signing key query on ix. creates a challenge signature on M, and guesses the identity of the signer. If answers correctly, then the simulator outputs b = 1, meaning that h is guessed to be in . Otherwise, it outputs b = 0, meaning that h is guessed to be in .We denote the simulator's advantage as in the subgroup decision game. Since , we obtain that The result that comes from must be smaller than ε because of the hardness of the assumption.Next, in the real scheme, when h belongs to instead of , the challenge signature is statistically independent of the signer's identity in the adversary's view: we will determine what the adversary may deduce from δ.First, we observe that vkOT, δOT, A, B, γB do not depend on the signer identity. However, since is computationally unbounded, we assume that these values reveal some information relative to the exponents. Second, we consider , and the corresponding for each i ∈ {1, …, d }. There are two hypotheses that may be formulated by : bi = 0 or bi = 1. For either hypothesis, there is a solution. Since h is a generator of , there are for each i ∈ {1, …, d }, such that . Thus, we obtain that . This means that the knowledge of for each i ∈ {1, …, d } does not reveal any information about the bit bi, and therefore, it does not reveal the identity of the signer.Finally, we focus on for i ∈ {1, …, d }, and γA. These values are redundant in the adversary's view since the already knows all the values that determine them.Therefore the identity is statistically independent of the entire signature δ, that means . Thus, we obtain that .Computational unforgeability: Following [17-19], our scheme is proved computationally unforgeable with relation to insider corruption. Informally, under the subgroup decision assumption, the probability that the forgery happens when we switch from h of order n in a common reference string to h of order q is negligible. The commitments are now perfectly binding in and the NIZK proofs are perfectly sound in , and therefore some uncorrupted va ∈ S is contained in A and a signature δa on vkOT under va is contained in B. We carefully develop this part in the proof below. Next, by the properties of the one-time signature scheme, vkOT has not been used in any other signature and thus, δa is a forged Boneh–Boyen signature on vkOT. We omit this part since the proof is quite straightforward: Boneh and Boyen [15] showed that this probability is negligible under the strong Diffie–Hellman assumption.We assume there exists a simulator that plays the subgroup decision problem with probability and an adversary that wants to break the unforgeability of the above ring signature scheme. receives the subgroup decision challenge , where and h is either equal to gr for or to gpr for . More precisely, in the game G0, computes h as an element in and in the game G1, it computes h as an element in . runs with input the verification keys S = {v1, …, vN } that generates as in the real scheme. also selects a user at random. If , then plays the normal game G0. Otherwise, if , then plays the hybrid game G1. proceeds to simulate the oracle queries of as follows: When requests a signature on a message M, with respect to ring S (S might contain some verification keys generated in an arbitrary manner by ), to be signed by user , then can easily generate the response to this query by running the Sign algorithm in a honest manner. When requests a signature on message M, with respect to ring S (S might contain some verification keys generated in an arbitrary manner by ), to be signed by user , then cannot directly respond to this query since it does not have the appropriate secret key for (we recall that for some unknown ). Instead, submits M to its signing oracle and obtains in return a signature for . The remainder of the signature is calculated as in the real scheme using h. Any corruption query made by for user can be accurately answered by . However, if ever makes a corruption query for , then simply aborts. At some point, outputs a forgery on a message M * regarding some ring of honest user verification keys . If , then aborts. If ‘Accept’, then the adversary wins the game. We denote the adversary's advantage in the games G0 and G1 as and , respectively.If as in the game G0, then provides a perfect simulation for the adversary since the signature given to is as in the real game. Otherwise (i.e. as in the game G1), then the forgery is uniformly distributed in and independent of the random choices made by . We recall that the simulator's advantage is in the subgroup decision game. Since , we obtain the following Now in the game G1, the commitments are perfectly binding in and the NIZK proofs are perfectly sound in . We show these results for the commitments , the other commitments following a similar demonstration. We recall that , for i = 1, …, d. The corresponding NIZK proof for the statement is verified by checking . When and since is uniquely determined from the verification equation, the proof has perfectly zero knowledge. When , the verification shows that has order q. Since this happens for all the commitments and the corresponding NIZK proofs, there is a honest user a with uncorrupted signing public key vka ∈ S such that A * = vka hr and so there is a signer's certifying signature δa on vkOT such that B * = δa hs. In other words, if outputs a valid forgery, then with all but negligible probability ε2 by soundness of NIZK, it holds that δ * is a valid signature of M * regarding va for some a. From this, with probability 1/N, we get that the event did not abort ∧δ * is a valid signature of M * regarding for occurs. Therefore the advantage of the adversary in the game G1 is Later, the forgery δ * on M * implies a forgery of the Boneh–Boyen signature. More precisely, A contains a verification key that is not corrupted and B contains a signature on vkOT under this verification key. We recall that the probability of the event (vkOT has not been used in any other signature) is negligible based on the properties of the one-time signature scheme and the strong Diffie–Hellman assumption. For simplicity, we do not count this part in our security analysis.We conclude that the adversary succeeds with probability . □ 4.3 Working in prime order groups We work in composite order groups in our construction. The anonymity relies on the hardness of the subgroup decision assumption. This assumption is as follows: given a group of composite order n = pq, it is hard to decide whether a given element is in the subgroup of order p without knowing p and q. It has to be infeasible to factor n to achieve this hardness. This results in very large parameter sizes, for example, log2 n = 3072 or 3248 for a 128-bit security level, according to the National Institute of Standards and Technology (NIST) or the European Network of Excellence in Cryptology II (ECRYPT II) recommendations [20]. Extending our scheme in prime order groups would be an interesting challenge to gain in efficiency. In addition, the pairing computation seems to be much slower in the composite order setting than in the prime order setting. We reckon that there are useful properties for bilinear composite order models to design protocols; however, the latter is not very competitive compared with the protocols relying on other assumptions such that prime order models with asymmetric pairings. Recently, Groth and Sahai [19] have shown that their non-interactive witness-indistinguishable (NIWI) and NIZK techniques can be realised in prime order groups under the decision linear problem. We could apply these results in our ring signature protocol to obtain a scheme in prime order groups. 5 Conclusion In this paper, we constructed ‘the first’ ring signature scheme of logarithmic size in the number of users in the ring, improving the sub-linear size result obtained in [2]. Inspired by Chandran et al.’s work [2], our scheme requires a common reference string and the NIZK proofs and is proved secure without relying on random oracles. 6 References 1Rivest, R., Shamir, A., Tauman, Y.: ‘How to leak a secret: theory and applications of ring signatures’. In Essays in Memory of Shimon Even, 2006 (LNCS, 3895), pp. 164– 186 2Chandran, N., Groth, J., Sahai, A.: ‘Ring signatures of sub-linear size without random oracles’. Proc. of ICALP'07, Wrocław, Poland, 2007 (LNCS, 4596), pp. 423– 434 3Naor, M.: ‘Deniable ring authentication’. Proc. of CRYPTO'02, 2002 (LNCS, 2442), pp. 481– 498 4Dodis, Y., Kiayias, A., Nicolosi, A., Shoup, V.: ‘Anonymous identification in ad hoc groups’. Proc. of EUROCRYPT'04, Interlaken, Switzerland, 2004 (LNCS, 3027), pp. 609– 626 5Zhang, F., Kim, K.: ‘ID-based blind signature and ring signature from pairings’. Proc. of ASIACRYPT'02, Queenstown, New Zealand, 2002 (LNCS, 2501), pp. 533– 547 6Au, M.H., Liu, J.K., Susilo, W., Yuen, T.H.: ‘Certificate based (linkable) ring signature’. Proc. of ISPEC'07, Hong Kong, China, 2007 (LNCS, 4464), pp. 79– 92 7Fujisaki, E., Suzuki, K.: ‘Traceable ring signature’. Proc. of PKC'07, Beijing, China, 2007 (LNCS, 4450), pp. 181– 200 8Liu, J.K., Wei, V.K., Wong, D.S.: ‘Linkable and anonymous signature for ad hoc groups’. ACISP'04, 2004 (LNCS, 3108), pp. 325– 335 9Wang, C.-H., Liu, C.-Y.: ‘A new ring signature scheme with signer-admission property’, Inf. Sci., 2007, 177, (3), pp. 747– 754 (https://doi.org/10.1016/j.ins.2006.03.016) 10Chow, S.S.M., Wei, V.K., Liu, J.K., Yuen, T.H.: ‘Ring signatures without random oracles’. Proc. of ASIACCS'06, Taipei, Taiwan, 2006 (CCS), pp. 297– 302 11Bender, A., Katz, J., Morselli, R.: ‘Ring signatures: stronger definitions and construction without random oracles’. J. Cryptol., 2008, 22, pp. 114– 138 (https://doi.org/10.1007/s00145-007-9011-9) 12Shacham, H., Waters, B.: ‘Efficient ring signatures without random oracles’. Proc. PKC'07, Beijing, China, 2007 (LNCS, 4450), pp. 166– 180 13Boyen, X.: ‘Mesh signatures’. Proc. of EUROCRYPT'07, Barcelona, Spain, 2007 (LNCS, 4515), pp. 210– 227 14Schäge, S., Schwenk, J.: ‘A CDH-based ring signature scheme with short signatures and public keys’. Proc. of FC'10, Tenerife, Spain, 2010 (LNCS, 6052), pp. 129– 142 15Boneh, D., Boyen, X.: ‘Short signatures without random oracles’. Proc. of EUROCRYPT'04, Interlaken, Switzerland, 2004 (LNCS, 3027), pp. 56– 73 16Boneh, D., Goh, E.-J., Nissim, K.: ‘Evaluating 2-DNF formulas on ciphertexts’. Proc. of TCC'05, Cambridge, MA, 2005 (LNCS, 3378), pp. 325– 341 17Groth, J., Ostrovsky, R., Sahai, A.: ‘Perfect non-interactive zero-knowledge for NP’. Proc. of EUROCRYPT'06, St. Petersburg, Russia, 2006 (LNCS, 4004), pp. 339– 358 18Boyen, X., Waters, B.: ‘Compact group signatures without random oracles’. Proc. of EUROCRYPT'06, St. Petersburg, Russia, 2006 (LNCS, 4004), pp. 427– 444 19Groth, J., Sahai, A.: ‘Efficient non-interactive proof systems for bilinear groups’. Proc. of EUROCRYPT'08, Istanbul, Turkey, 2008 (LNCS, 4965), pp. 415– 432 20Guillevic, A.: ‘ Comparing the pairing efficiency over composite-order and prime-order elliptic curves’. Cryptology ePrint Archive, Report 2013/218 (2013) Citing Literature Volume10, Issue1January 2016Pages 1-7 FiguresReferencesRelatedInformation
Referência(s)