Portal de Periódicos da CAPES

Efficient blacklistable anonymous credential system with reputation using a pairing‐based accumulator

2020; Institution of Engineering and Technology; Volume: 14; Issue: 6 Linguagem: Inglês

10.1049/iet-ifs.2018.5505

1751-8717

Toru Nakanishi, Takeshi Kanatani,

Internet Traffic Analysis and Secure E-voting

IET Information SecurityVolume 14, Issue 6 p. 613-624 Research ArticleFree Access Efficient blacklistable anonymous credential system with reputation using a pairing-based accumulator Toru Nakanishi, Corresponding Author t-nakanishi@hiroshima-u.ac.jp orcid.org/0000-0001-8796-9508 Department of Information Engineering, Graduate School of Engineering, Hiroshima University, 1-4-1 Kagamiyama, Higashi-Hiroshima, 739-8527 JapanSearch for more papers by this authorTakeshi Kanatani, Department of Information Engineering, Graduate School of Engineering, Hiroshima University, 1-4-1 Kagamiyama, Higashi-Hiroshima, 739-8527 JapanSearch for more papers by this author Toru Nakanishi, Corresponding Author t-nakanishi@hiroshima-u.ac.jp orcid.org/0000-0001-8796-9508 Department of Information Engineering, Graduate School of Engineering, Hiroshima University, 1-4-1 Kagamiyama, Higashi-Hiroshima, 739-8527 JapanSearch for more papers by this authorTakeshi Kanatani, Department of Information Engineering, Graduate School of Engineering, Hiroshima University, 1-4-1 Kagamiyama, Higashi-Hiroshima, 739-8527 JapanSearch for more papers by this author First published: 01 November 2020 https://doi.org/10.1049/iet-ifs.2018.5505AboutSectionsPDF 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 onEmailFacebookTwitterLinked InRedditWechat Abstract As privacy-enhancing authentications without any TTP (Trusted Third Party), blacklistable anonymous credential systems with reputation have been proposed. However, the previous systems have the efficiency problem: The authentication data size is or , where L is the reputation list, and K is the size of a window indicating the most recent K authentications of the user. Therefore, the previous systems suffer from or -size data in each authentication. In addition, the authentication needs the computation of or exponentiations. In this paper, an efficient blacklistable anonymous credential system with reputation is proposed. In our system, the data size of the authentication is . Furthermore, although the computational costs in the authentication depend on some parameters, the parameter-related costs are only multiplications instead of exponentiations. Compared to the previously proposed blacklistable system FARB with the constant computational and communication costs, our system has the advantage that the clear/redeem protocol only has to be executed every interval instead of every session. For constructing our system, we newly introduce the concept of an accumulator for reputation, and propose an efficient construction. 1 Introduction 1.1 Backgrounds With the advance of information and communication technology, people can access networks from anywhere, where the authentication to protect illegal access is highly required. However, in conventional authentications using ID, such as password-based or digital signatures, we need to trust the authentication server in privacy protection. This is because the server can link the ID of a user to his access to services, and collect the access history, but may reveal such sensitive data to outsiders. On the background, anonymous authentications including group signatures and anonymous credentials have been intensively researched. In this type of authentication, in advance, a server issues a certificate (digital signature) to a user. In the authentication between the user and a service provider (SP), the user anonymously shows that he is a valid user, by proving the ownership of the certificate in a zero-knowledge fashion. In services based on the anonymous authentication, a user may misbehave without the fear of punishment. In group signature schemes, the countermeasure is to introduce a trusted opener, who has the authority to identify the user from the authentication. However, this approach means that the opener can de-anonymise all users anytime, and thus users cannot enjoy the privacy completely. In some applications, it is sufficient to block the access of the misbehaving users, while the anonymity of users remains. 1.2 Previous works In [1 ], a blacklistable anonymous credential (BLAC) system was proposed. In this system, any trusted third party is not needed, and a blacklist is used to block the access of a misbehaving user, as follows. Each authentication includes a ticket generated from the user's secret key. When the user misbehaves, the ticket is added to a blacklist L. In the authentication, the user additionally proves that each ticket in the blacklist L is not derived from his secret key, and thus the blacklisted user cannot succeed the authentication. However, this original system has the inefficiency that the authentication has -size data and cost of exponentiations. Thus, the following systems with more efficiency have been proposed. In [2 ], a blacklistable system called PEREA based on an accumulator has been proposed. In this system, since the tickets in the blacklist L are accumulated to one value, the authentication data size and the computation cost do not depend on . On the other hand, the revocation is based on a window with the most recent K authentications of the user, and the authentication needs K zero-knowledge proofs. When a past authentication becomes outside the window, the misbehaviour of the authentication is forgiven. This means that K should be as large as possible. Therefore, this system suffers from heavy computation costs. In [3 ], thanks to an efficient zero-knowledge proof for an accumulator, the zero-knowledge proof is executed once. However, the data size of the authentication is still due to the RSA-based accumulator, and the computation needs exponentiations. In [4 ], by using a pairing-based accumulator, the data size of the authentication becomes . Another research line of the BLAC systems is to introduce the severity and reputation. In [5 ] (the journal version of [1 ]), the extended BLAC system was proposed. In the original BLAC, after a user misbehaves once, he is blocked. However, it may be too harsh to be of practical use, and a more complex criterion to block such users is required. In the extended BLAC, for a threshold integer d, after a user misbehaves d times, then the user is blocked. In [6 ] (the journal version of [2 ]), a more complex criterion is introduced as follows. Each misbehaviour is given a weight of severity, which is called a score in this study, and added to the blacklist, which is called a reputation list. Then, after the total of scores of the user exceeds a threshold, the user is blocked. However, this extension [6 ] based on PEREA has the same drawback of efficiency as the original PEREA, i.e. the authentication data size is and the computation needs zero-knowledge proofs with exponentiations. In [7 ], as the further extended BLAC, BLAC with a reputation (BLACR) was proposed. The main contribution is to generalise the blacklisting based on the severity of the reputation. Namely, in addition to negative scoring for misbehaviour, a user's behaviour can be positively scored. The user can prove that his total score is more than a threshold to show his reliability based on his reputation. In [8 ], as the extended PEREA with reputation, PERM was also proposed. However, BLACR and PERM inherit the inefficiency of BLAC and PEREA, respectively. In BLACR, the communication and computation costs are linear for the reputation list size . In PERM, the communication and computation costs are linear for window size K. In [9 ], an efficient BLAC system with a reputation, called FARB, was proposed, where the authentication protocol needs only constant costs on both users and SP, using a different approach as follows. In this system, a redeem protocol is introduced as follows. Each user is issued a main certificate certifying an accumulated score that is the sum of scores for the user's past sessions. In addition, the score of each session is certified by a score certificate binding the session ID and the score. In the redeem protocol, after proving the certificates, a user is issued a new main certificate for the new accumulated score added by the score of the redeemed session. In the authentication protocol, the user proves that the accumulated score in the main certificate satisfies the designated policy. Note that the user has to redeem his all scores of judged sessions before the subsequent authentication. The advantage of this system is the efficiency of the authentication protocol, i.e. the data size and the computational cost in the authentication protocol are constant for the parameters and K. On the other hand, a demerit is the efficiency of the redeem protocol. The redeem protocol has to be executed for each session judged by the SP. Thus, the total cost of the redeem protocols depends on the number of redeemed sessions. 1.3 Our contributions In this paper, [The preliminary version of this paper was presented in TrustCom 2018 [10 ].] we propose an efficient BLAC system with reputations. In our system, as in [9 ], the data size of the authentication and SP's computational cost are constant for and the window size K. The user's computation of the authentication consists of the part with the constant complexity and the part with the parameter-related complexity. However, the parameter-related cost consists of multiplications instead of heavier exponentiations or pairings. In addition, our system equips the clear protocol that is similar to the redeem protocol. The different point from [9 ] is the clearing/redemption per interval instead of the session as follows. In our system, the reputation list and user's session list are managed for each time interval . We assume that scores for only sessions in the current interval can be changed, i.e. the scores for sessions in the past interval must be fixed. Using the clear protocol, a user can compute the total score of the user during interval , and add it to the accumulated score which is ensured by a certificate. In the authentication, the user can prove the sum of the accumulated score (for all past intervals) and the scores during the current interval. This is why the user's computational complexity actually depends on only the number of sessions of the user at the current interval , instead of all past sessions, and the parameter-related cost is multiplications, where is the number of sessions added in after the previous authentication of the user, and is the number of the past sessions of the user during the current interval. The user's parameter-related cost in the clear protocol is also multiplications. On the other hand, as well as the authentication, the SP's cost in the clear protocol is constant. As above-mentioned, the clear protocol for each user is needed once every interval, instead of session. Therefore, the SP's total cost for all users is greatly reduced, which is an advantage over the previous efficient system [9 ]. As in [4 ], we adopt a pairing-based accumulator to construct the system with the constant-size authentication. In the accumulator proposed in [4 ], a set of multiple values can be accumulated to one value using multiplications and a user can prove that for sets U and V. It leads the constant-size proof to show that the user is not blacklisted, but does not care about the reputation-based blacklisting. In this study, we newly construct an accumulator for reputation, where the user can prove the sum of scores of the user as follows. Let reputation list be a set of all session IDs during interval and the corresponding scores, i.e. , where is the score of session i. Let be a set of session IDs used by the user during interval . Then, our accumulator allows the user to prove the correctness of in the zero-knowledge fashion. Since such an accumulator to prove the sum of scores is not known, the concept and construction of the accumulator are included in our contributions. The accumulator for reputation means that a verifier (SP in BLAC system) can verify the sum of scores for a user, i.e. the user's reputation, using an accumulator (a value accumulated from all scores) efficiently. As in BLACR [7 ] and PERM [8 ], we consider the generalisation from the severity to the reputation. Namely, in addition to negative scoring for misbehaviour, a user's behaviour can be positively scored. To achieve this, in our system, for any integer range , the user can prove that his total score is in . Thus, in case of negatively scoring, using range dc4 for a threshold , when the total score of a user exceeds , the authentication of the user is rejected. On the other hand, in case of positively scoring, using range for integers , , the user can prove that his total score (i.e. reputation) is in the range to show his reliability. Difference from the conference version [10 ]: what we modify from the conference version [10 ] of this paper are mainly as follows. In Section 6, we add the detailed constructions of zero-knowledge proofs PK s, which are used in the construction of our BLAC system. In the conference version, only the proof sketches for security are shown. In this study, we show complete security proofs in Section 7. Furthermore, in Section 8, we add detailed efficiency comparisons to the previous BLAC systems with a reputation. 1.4 Related works Finally, we remark the other contributions in BLACR [7 ], PERM [8 ], and FARB [9 ]. In these systems, more complex reputation methods are available as follows. There are multiple different categories such that each score belongs to some category. In each category, the scores are summed up as the category score. Then, SP specifies a logical relation across multiple category scores such as where are the user's total scores on categories , and are the threshold values on categories , respectively. In addition, BLACR and FARB introduce an extension to increase the penalty for multiple misbehaviour. Namely, the second misbehaviour's score is more weighted than the first score, and the third misbehaviour's is much more weighted. 2 Preliminaries 2.1 Bilinear groups We utilise bilinear groups as follows: 1. and are multiplicative cyclic groups of prime order p, 2. g is a generator of , 3. e is an efficiently computable bilinear map: , i.e. (a) for all and , and (b) , where is the identity element of group . The bilinear map can be implemented by a pairing. 2.2 Assumptions The security of our system is based on the q -simultaneous flexible pairing (q -SFP) assumption [11 ], and n -DH exponent (n -DHE) assumption [12 ]. Definition 1.(q-SFP assumption): For all probabilistic polynomial-time (PPT) algorithm is negligible, where and all tuples , satisfy the above relations. Definition 2.(n-DHE assumption): For all PPT algorithms is negligible, where and . 2.3 Abe–Haralambiev–Ohkubo (AHO) signatures As in [4 ], in our construction, the signature on a vector of messages is proved in the zero-knowledge fashion. Thus, we adopt the AHO signature scheme in [11 ]. AHOKeyGen: Select , and , , . Compute , , . Output the public key as , , , , , and the secret key as , . AHOSign: Given a vector of messages together with , choose , and compute , , , , , , and . Output the signature . AHOVerify: Given pk, the messages and the signature , accept these if In our construction of an anonymous credential system, an AHO signature is re-randomised using the re-randomisation algorithm in [11 ]. Then, the AHO signature can be randomised to on the same messages. In the re-randomised signature, can be revealed with unlinkability to the original signature. On the other hand, have to be committed to the unlinkability. Remark 1.In the following construction, we use the AHO signature as a certificate to sign the accumulator of an -element, where the signature and accumulator can be proved in the zero-knowledge fashion. Furthermore, to easily capture our construction, we also use the AHO signature for a signature-based range proof. For the range proof, we can also adopt the more efficient BBS+ signature [13 ] used in other systems such as FARB. 2.4 Pedersen commitments As commitments, we adopt Pedersen commitments [14 ]. Let be random elements from . Then, the commitment to message is computed as for a randomly chosen , which is denoted as . The security of the commitment consists of the perfect hiding and computational biding. The former means that the commitments to any pair of messages are perfectly indistinguishable. The later means the infeasibility to compute s.t. , , and . The binding is satisfied with the discrete log assumption, which is implied by the DHE assumption. In the proposed system, -element P is also committed. As in the underlying system [4 ], we use as the commitment to P, where . The randomness of implies the perfect hiding. The binding also holds, as follows. If an adversary finds s.t. , we obtain , which means that we can compute , using the adversary. The computation of is denoted as . Remark 2.In the proposed system, similarly to the underlying system [4 ], the element in the AHO signature is committed as only without . In this case, the binding is not ensured (it can be opened to for any due to ). However, it is proved that the opened signature elements satisfy the verification AHOVerify on the signed messages. We need only the existence of a (randomised) AHO signature on the messages, but do not need the sameness of the AHO signatures committed and opened. This is why we use only . 2.5 Proving relations on representations In our construction, as in [4 ], zero-knowledge proofs of knowledge (PK s) proving the knowledge of a representation of to multiple bases , which are s.t. . This can be also constructed on group . In this PK, multiple representations on and on with equal parts can be proved. We adopt the standard notation of PK as PK proving the knowledge of secrets s.t. . 3 New accumulator for reputation In this section, we newly introduce a concept of the accumulator for reputation, construct an efficient pairing-based construction with multiplications, and prove the security based on formal definitions. In an accumulator, a set of multiple values can be accumulated to one value. In [12 ], a pairing-based accumulator was proposed, where the accumulation is efficient due to multiplications, and the user can prove that a value belongs to the accumulated set. In [15 ], an extended accumulator was proposed. Let be subsets of for a non-negative integer n. By using the extended accumulator, can be checked with a single pairing relation. In the BLAC system with constant-size authentication [4 ], the accumulator is furthermore extended and integrated, where is proved. Based on the accumulator [15 ], this section proposes an accumulator to prove the sum of scores. In this new accumulator, it is given and s.t. and each is an integer. Then, using the proposed accumulator, can be checked with a single pairing relation. 3.1 Definitions At first, we define the accumulator for reputation. The syntax of the accumulator is as follows: Acc.KeyGen : Given security parameter , the number of elements , and domain of integer scores , this key generation algorithm outputs the public parameters . Acc.AccGen U : Given , , this accumulator generation algorithm outputs the accumulator of U. Acc.AccGen L : Given , and reputation list s.t. and , this accumulator generation algorithm outputs the accumulator of L. Acc.WitGen: Given , U, and L, this witness generation algorithm outputs the witness W. Acc.Verify: Given , , , W, total score , this verification algorithm outputs the verification result 1 if and for , and 0 otherwise. The correctness and security of the accumulator are defined as follows: Correctness : The accumulator is correct, if for correctly computed by Acc.KeyGen, correctly computed by , correctly computed by , W correctly computed by Acc.WitGen, and , with any proper s.t. and Security : We define the following experiment: The accumulator is secure if, for any PPT adversary , the advantage is negligible for . 3.2 Proposed construction The construction of the proposed accumulator is as follows: Acc.KeyGen : Select bilinear groups with a prime order and a bilinear map e. Select a random generator . Select a random factor , and compute , and . Output , , , . Acc.AccGen U : Compute , and output . Acc.AccGen L : Parse L as to obtain V. Compute , and output . Acc.WitGen : Parse L as to obtain V. Compute and output W. Acc.Verify : Check the equality of If it holds, output 1, and otherwise output 0. For the security proof, we assume that and for the order p of groups . In the application of reputation, is a proven value of the total score and is the concrete sum of a user's scores, which satisfy those conditions. Intuition behind construction. In the underlying accumulator [15 ], is computed. By the verification equation is checked. In the verification, the left side produces Z for each matched , and thus the equality to means . In the proposed construction, we set , where score is powered. Then, in the verification, the left side produces for each matched , and in total the left side becomes when . Thus, we can check using the verification equation. 3.3 Correctness and security For correctness and security, we have the following theorems. Theorem 1.The proposed accumulator is correct. Proof.By substituting , and W to the verification equation, the left hand is equal to From , this is equal to Owing to , this is equal to , i.e. the right hand of the verification equation. □ Theorem 2.The proposed accumulator is secure under the n -DHE assumption. Proof.Assume an adversary s.t. is not negligible, and we will construct breaking the n -DHE assumption, as follows. is given . Similarly to Acc.KeyGen, generate without . Then, run with , which outputs . Obtain and . Then, with some non-negligible probability, for , we have the conditions From the first condition, we have By using , , and , we obtain Then, from , we have the following equations: for . Thus since .Here, since we assume and , it holds . On the other hand, it holds that . These mean that . Thus, we obtain This means that can compute from , using the output of , and thus the n -DHE assumption is broken. □ 4 Security model 4.1 Syntax The BLAC system with reputation consists of the following algorithm and protocols, where a user and an SP participate. Some notations w.r.t. indexes are shown in Table 1. Setup: This is an algorithm that outputs the secret key ssk and public key spk of including integer ranges for all where are integers s.t. , and initialises database of tags as empty and interval . Table 1. Notations serial number of interval reputation list at interval set of user's used session IDs at interval t serial number of one-time certificate one-time certificate of serial number t i session ID score of session ID i the j -th integer range Reg: This is an interactive protocol between and . The common inputs are spk and the current interval , and the input of is ssk. The output of is the secret key sec and a one-time certificate on the set of ’s used session IDs at interval as empty and the base score . Auth: This is an interactive protocol between and . The common input is spk, the current interval , the ID of this session, the current reputation list at interval , for V of IDs of all used sessions during , and an integer range . The input of is sec and on the interval , his session ID set , and base score B (his total score until the previous interval ) together with a tag tag, and the input of is ssk. If , , and , then is successfully authenticated. The output of is an updated certificate on new , which is updated as . Note that the outputs of including are hidden to for the following anonymity requirement. The output of is the updated database , which is updated as . Clear: This is an interactive protocol between and . The common input consists of spk, the current interval , some past interval (i.e. ), and the reputation list . The input of is sec and on the interval , his list at , and base score B (his total score until interval ) together with a tag tag. The input of is ssk. If is valid and , then this protocol is executed successfully. The output of is an updated certificate on the next interval , new list , and B, where is initialised as empty, and B is updated as for the past interval . The output of is the updated database , which is updated as . 4.2 Security definitions The security requirements of the BLAC system with the reputation are defined as follows. The definitions are derived from [2, 3 ]. Misauthentication resistance: This requirement captures the soundness of authentication. In the reputation setting, this means that any cannot succeed Auth for s.t. . Consider the following game. Misauthentication resistance game: The challenger conducts Setup to obtain . Initialise counters (for new user ID), (for the current interval), (for new session ID), and the initial reputation list , the set for session IDs in the first interval, and the set CU for corrupt users as empty. Let be a database with entries of . Then, run with spk, where can request the following queries. Evolve: Increment indicating the current interval, and initialise and as empty. C-Reg: Increment , add the user's ID to CU. Reg on the current interval is executed between the challenger as and as of user's ID i. Initialise entry in database , where and . C-Auth: On requested by , increment , and Auth on current interval , session , reputation list , and range is executed between the challenger as and as of user's ID i. Find entry ) in database . If the entry is not found, , or some i in is not scored, then abort. Otherwise, update the entry such that , and add to . C-Clear: On requested by , Clear on the current interval , past interval , and the cleared revocation list is executed between the challenger as and as of user's ID i. Find entry in database . If the entry is not found, , or some i in is not scored, then abort. Otherwise, update the entry such that , and . Modify-RL: To the request on for by , the challenger modifies the entry in reputation list . Finally, on requested by , increment , and Auth for the current interval , session , reputation list , and range is executed between the challenger as and as of user's ID . If some i in is not scored, then abort. wins if this final C-Auth is successful, and one of the following conditions holds: there is not entry in . for and some entry in . Definition 3.(Misauthentication resistance): A BLAC system with reputation is misauthentication resistant if all PPT adversaries win the misauthentication resistance game with negligible probability. Anonymity: The anonymity means the unlinkability of the sameness of the users in Auth protocol, which is defined similarly to the anonymity of the group signatures. Consider the following game. Anonymity game : The challenger conducts Setup to obtain . Initialise counters , , , reputation list , and sets (set of honest users) as empty. Let be a database with entries of . Then, run with , where the following phases happen. Queries: can adaptively query the challenger as follows. Evolve: Increment indicating the current interval, and initialise and as empty. H-Reg: Increment , add the user's ID to HU. Reg on the current interval is executed between as and the challenger as of user's ID i. Initialise entry in database , where is ’s output in this protocol Reg, , and . H-Auth: To the request on by , increment , and Auth on the current interval , session , reputation list , and range is executed between as and the challenger as of user ID i. Find entry ) in database . If the entry of the requested i is not found, , or some i in is not scored, then abort. Otherwise, update the entry such that for ’s output in this Auth, and . Add to . H-Clear: To the request on by , Clear on the current interval , past interval , and the cleared revocation list is executed between as and the challenger as of user ID i. Find entry in database . If the entry of the requested i is not found, , or some i in is not scored, then abort. Otherwise, update the entry such that , for ’s output in this Clear, , and . Modify-RL: To the request on by , the challenger modifies the entry in reputation list . Corrupt: To the request on by , the challenger sends ’s secret in to , and remove i from HU. Challenge: outputs two user IDs and range . For both and , the chall