One-Stop Efficient PKI Authentication Service Model Based on Blockchain

Abstract

Public Key Infrastructure (PKI) technology is a widely used identity authentication technology. This paper uses blockchain technology to improve it and implements decentralized PKI authentication, which resolves the issues in the traditional PKI such as single point of failure and certificate transparency. However, most of the current research uses the method of traversing the blockchain to query the certificate (identity, public key) to realize identity authentication, which is inefficient. And as the size of blockchain continues to grow, storage overhead is growing. In this paper, we combine the blockchain and the dynamic accumulator to construct a blockchain PKI model that can batch update certificates, which improves the efficiency of identity authentication. The model can effectively add, revoke and update user certificates. Meanwhile, this paper builds a one-stop PKI authentication service model based on blockchain, Through the certificate blockchain, we can provide one-stop user authentication service to third-party service providers. Finally, we verify the security and effectiveness of the scheme.

1 Introduction

PKI is a universal security infrastructure that provides information security services based on public key cryptography, so that users can communicate and make e-commerce transactions through a series of trust relationships based on certificates when they do not know each other’s identity. As the foundation and core of current network security, PKI is the basic guarantee for e-commerce security development. To ensure the secure transmission of information, an effective PKI system must be secure and transparent. However, faced with the biggest problem that the CAs are not trusted, traditional centralized PKI in a distributed environment results in an untrustworthy problem of the identity of the entity. A CA that is attacked or maliciously issues certificate will bring significant security risks to the information system. The hacker can achieve a man-in-the-middle attack by attacking a trusted CA to perform malicious operations, such as issuing a user’s certificate containing false information. The user cannot verify the process of issuing a certificate by CAs, and there is a certificate transparency issue. In addition, the centralized CA management architecture will lead to single point of failure [1]. As a new type of distributed technology that cannot be tampered with, blockchain brings new ideas to the implementation of decentralized PKI.

At present, the blockchain-based PKI uses the blockchain to store information such as identity and public key. In the process of implementing identity authentication, the method of traversing the blockchain is generally used to look up the certificate, and then check whether the public key belongs to its declared identity. Finally, verifying the digital signature to determine whether the other party holds the matching private key by sending a challenge information. However, the block-chain is a public chain that can only be added. Its characteristics ensure that the amount of data will continue to grow. In recent years, the blockchain has exceeded 100 Gb in volume and will continue to grow in the future. By then, the method of traversing the blockchain will be more inefficient, and the time required for identity authentication will be difficult to meet the actual needs. At the same time, such a large amount of data cannot be stored for carriers such as mobile phones. The dynamic accumulator maps a collection containing multiple elements to an accumulated value and provides a smaller witness to prove that a given element does belong to the set. Its introduction can resolve the issue that member verification is inefficient in the process of identity authentication.

In this paper, we improve the traditional PKI model by using dynamic accumulator and blockchain, and propose a PKI authentication service model based on blockchain. First, we build an interaction model between users, miners, and supervisory nodes. The miner is responsible for the distribution and management of the certificate, at the same time, provides authorization tickets to third-party service providers. The supervisory node reviews the transaction submitted by the user and ensures the consistency of the block transaction with miners through the consensus mechanism. It resolves the problem of single point of failure and certificate transparency in the traditional PKI. Secondly, in view of the shortage of certificate management methods, this paper proposes a certificate management method that can batch update and revoke certificates based on dynamic accumulators, which improves the efficiency of identity authentication. Thirdly, this paper builds a one-stop PKI authentication service model based on blockchain to ensure that users can access the third-party services by registering the certificate simply in the certificate blockchain. Finally, we analyze the security of the scheme in detail, and the results show that the scheme can resist the enemy forgery attack and Sybil attack. In terms of efficiency, the space complexity of storage overhead is $O(1)$.

The rest of the paper is organized as follows: In Sect. 2, we introduce the relevant research of blockchain-based PKI systems. In Sect. 3 we introduce the supporting techniques of this scheme. In Sect. 4, we describe the system model, security model and threat model. The specific construction of the program is discussed in detailed in Sect. 5. A security analysis and efficiency analysis for the scheme are described in Sect. 6. In Sect. 7 we compare the relevant scheme. Section 8 draws a conclusion of our scheme.

2 Related Work

An important application of blockchain in the direction of identity authentication is to build a distributed public PKI based on blockchain [2]. PKI can be established based on public general ledger, which can eliminate the trust center CA of PKI and realize real distributed PKI construction.

In 2014, MIT scholar Conner proposed the first distributed PKI solution based on blockchain which called Certcoin [3, 4]. The core idea is to record the user certificate through the public general ledger, and associate the user identity with the certificate public key in a public manner to realize the decentralized PKI construction. Any user can query the certificate issuance process and resolve the issue of certificate transparency and CA single point of failure. Certcoin implements the registration, update and revocation of certificates by publishing users and their public keys in the form of blockchain transactions. The normal operation of the PKI is guaranteed by the attributes of the blockchain that cannot be tampered with. The Merkle root only records the hash value of the transaction, and users do not need to download all blockchain transaction data to complete the verification of the certificate. However, on the one hand, Certcoin cannot prevent the illegal occupancy of legitimate users like other schemes. On the other hand, the scheme completes the user’s certificate revocation by retaining the certificate blacklist and periodically recalculating the accumulator from zero, which will increase the computational overhead.

Authcoin is a decentralized PKI scheme proposed by Benjamin [5]. To reduce illegal occupancy and Sybil attack, Authcoin emphasizes the actual binding of the user when registering the public key by adding a complex challenge response step that makes it resilient to Sybil attack. However, as the number of interactive communication steps increases, so does the performance cost. This scheme does not take into account the credibility of the person performing the operations during the verification and authentication process.

BIX protocol is more flexible for cyber-attack and doesn’t cause single point of failure [6]. The BIX protocol is designed to distribute the role of CAs and preserve security features. In fact, the BIX protocol is designed with a blockchain-like structure, with a decentralized structure replacing CAs, which implements distributed certificate distribution. The certificate is a block in the blockchain, an effective user can attach their certificates to the blockchain by proper interaction protocol. Then Longo et al. proposed improvements to the BIX protocol and security proof. The formalized analysis shows the PKI system based on BIX protocol is more suitable for large-scale network attacks than the standard PKI protocol based on CA [7]. However, the protocol is still incomplete and there are no steps to revoke and update certificates.

Matsumoto et al. proposed a timely and automatic response PKI framework IKP (instant karma PKI) [8]. Based on the Ethereum platform, IKP uses the smart contract and consensus mechanism to stimulate the CA center to issue certificates correctly. It introduces detector to give reward to report illegal certificates, and imposes financial penalties on CAs that issue illegal certificates. In addition, the detector also needs to pay for the report. If the reported certificate is indeed an illegal certificate, the detector will receive a corresponding reward which can effectively prevent the detector from reporting all certificates to defraud the reward. However, the problem is that a malicious user may maliciously register a fake identity for execution fraud.

BKI is a blockchain-based PKI [9]. It uses a tunable number of CAs to issue certificates, but it is not extendable. In addition, BKI requires all clients to contact third parties (blockchain-based log maintainers) during certificate verification, which can cause latency and privacy issues. Syta et al. proposed an efficient method for joint signature of statements issued by CA using multiple signatures [10]. Each certificate requires a certain number of witnesses to sign together in order to be accepted by others. Therefore, even if an attacker compromises a certain privilege, all malicious statements need to be made public before being used for the attack. But CoSi needs to be coordinated in the cosign protocol and relies on direct communication between witnesses. In addition, the security of CoSi is still limited by its weakest link, because witnesses only approve statements issued by CA, without full domain verification, and the attacker can still exploit the vulnerability. Based on base on BKI and Cosi, Dykcik et al. propose an automated public key infrastructure relying on smart contracts called BlockPKI [11], in which CAs use multi-signature to sign and verify certificates. BlockPKI uses the smart contract to realize the automated certificate creation and the automated domain verification, and it encourages the CAs to participate in the authentication and obtain the reward.

Qin et al. proposed a distributed certificate scheme called Cecoin [12]. Cecoin treats certificates as currency processing and records them on the blockchain to eliminate single points of failure. Miners can verify the validity of a certificate against a set of rules to ensure consistency of ownership and allow identity to bind multiple public key certificates. At the same time, based on the Merkle Patricia tree, this paper describes the distributed management of certificates, including efficient retrieval and verification of certificates, and fast operations, also supports the transaction of certificates. However, this solution does not consider the correspondence between nodes and identities. One identity can correspond to several certificates, which will lead to the risk of being attacked by Sybil. At the same time, for the average user, it cannot withstand the huge storage overhead brought by the distributed certificate library.

3 Preliminary Knowledge

3.1 Cryptographic Accumulator

Benaloh et al. first proposed the use of a cryptographic accumulator as a decentralized digital signature alternative in 1993 [13]. It is a constant size representation of a set of elements. When an element is added to the cryptographic accumulator, a witness is generated that can be used to prove that the added element has been accumulated.

Definition 1.

The cryptographic accumulator scheme consists of the following four polynomial time algorithms:

${\text{KeyGen}}(k,M)$: A probabilistic algorithm for instantiating a scheme. Enter the security parameter $1^{k}$ and the upper bound $M$ on the number of accumulated elements, returning an accumulator key ${\mathcal{P}} = (PK,SK)$ where $PK$ is the public key and $SK$ is the private key.

${\text{AccVal}}(L,{\mathcal{P}})$: A probabilistic algorithm for calculating the cumulative value. Enter a set of elements $L = \{ c_{1} , \ldots ,c_{m} \} (1 \le m \le M)$ based on set C and parameters ${\mathcal{P}}$, returning an accumulated value v and auxiliary information $Aux$ that can be used by other algorithms.

${\text{WitGen}}(a_{c} ,Aux,{\mathcal{P}})$: A probabilistic algorithm that generates a witness for an element. Enter auxiliary information $Aux$, parameters ${\mathcal{P}}$, and elements $c_{i} \{ i = 1, \ldots ,m\}$, and if the element $c_{i}$ is indeed in the collection $L$, return a corresponding witness $W_{i}$.

${\text{Verify}}(c_{i} ,W_{i} ,v,PK)$: A deterministic algorithm that checks if a given element is in the accumulated value v. Input $c_{i}$, $W_{i}$, v, and accumulator public key $PK$, verify whether $c_{i}$ is accumulated in v according to $W_{i}$, then output Yes or No.

Applying a password accumulator to authentication not only enables efficient authentication, but also ensures security. However, when a general password accumulator adds or deletes an element, it needs to recalculate the current accumulated value and the respective witnesses. The accumulator cannot operate efficiently to cope with the actual application requirements when the element set dynamically changes. How to ensure that the accumulated value and the witness of each element can be updated and revoked efficiently when the set of elements changes. Thus, Camenisch and Lysyanskaya proposed the concept of a dynamic accumulator [14]. The dynamic accumulator accumulates a set of input values ​​into a value such that the input values ​​can prove themselves in the accumulated value, while allowing the operator to dynamically add or delete a value such that the cost of adding or deleting is independent of the number of members being added. In 2008, Peishun Wang et al. summarized the formal definition of the accumulator and proposed a new dynamic accumulator [15]. The dynamic accumulator adds adding, deleting and updating operations on the four algorithms of the original accumulator scheme.

Definition 2:

A dynamic accumulator consists of the following seven polynomial time algorithms:

${\text{KeyGen}}$, ${\text{AccVal}}$, ${\text{WitGen}}$ and ${\text{Verify}}$ are consistent with the algorithm in Definition 1.

${\text{Add}}(L^{ + } ,Aux,v,{\mathcal{P}})$: A probability algorithm for adding new elements to the accumulated value. Enter a set of new elements $L^{ + } = \{ c_{1}^{ + } , \ldots ,c_{k}^{ + } \} (L^{ + } \subset C,1 \le k \le M - m)$ that are to be added, the auxiliary information $Aux$, the accumulated values $v$ and the parameters ${\mathcal{P}}$, return the new accumulated value $v^{{\prime }}$ corresponding to the set $L^{ + } \cup L$, the witness $W_{1}^{ + } , \ldots ,W_{k}^{ + }$ of the newly added element $\{ c_{1}^{ + } , \ldots ,c_{k}^{ + } \}$ and the new auxiliary information $Aux^{{\prime }}$ for future updates.

${\text{Delete}}(L^{ - } ,Aux,v,{\mathcal{P}})$: A probability algorithm for deleting certain elements. Enter a set of elements $L^{ - } \{ c_{1}^{ - } , \ldots ,c_{k}^{ - } \}$ $(L^{ - } \subset L,1 \le k < m)$ that are to be deleted, auxiliary information $Aux$, the accumulated values $v$ and the parameters ${\mathcal{P}}$, and output a new accumulated value $v^{{\prime }}$ corresponding to the set $L\backslash L^{ - }$, and the new auxiliary information $Aux^{{\prime }}$ being used in future update operations.

${\text{UpdWit(}}W_{i} ,Aux,pk)$: Deterministic algorithm for updating the witness of element which has been added to $v^{{\prime }}$. Enter the witness $W_{i}$, the auxiliary information $Aux$, and the accumulator public key $pk$, return an updated witness $W_{i}^{{\prime }}$.

3.2 Complexity Assumption

Let $n = pq$, $p,q$ are different odd prime numbers, so the elements in the multiplicative group $Z_{n}^{*}$ which contains $\phi (n) = (p - 1)(q - 1)$ elements are all positive integers smaller than $n$ and mutually prime with $n$. $\phi (n)$ is the Euler function and $\phi (n^{2} ) = n\phi (n)$. Carmichael number $\lambda (n) = lcm(p - 1,q - 1)$, $\lambda (n^{2} ) = lcm((p - 1)p$, $(q - 1)q)$. There are three difficult assumptions described as below.

Strong RSA Assumption: Given the security parameters $n$ and random numbers $y \in Z_{n}^{*}$, there is no polynomial time algorithm to find $s$ and $x$ make $y \equiv x^{s} (\bmod \,\,n)$.

CSR Assumption: Given security parameters $n$, integers $s \in Z_{{n^{2} }}^{*} (s > 2)$ and random numbers $y \in Z_{{n^{2} }}^{*}$, there is no polynomial time algorithm to find out $x \in Z_{n}$ and make $y \equiv x^{s} (\bmod \,\,n^{2} )$.

es-RSA Assumption: Given the security parameters $n$ and random numbers $y \in Z_{{n^{2} }}^{*}$, there is no polynomial time algorithm to find $s$ and $x \in Z_{n}$ make $y \equiv x^{s} (\bmod \,\,n^{2} )$, where $n^{2} > s > 2$.

Lemma 1:

If the CSR hypothesis and the strong RSA assumption are true, the es-RSA assumption is true.

4 System Model

Conner Fromknecht proposed in Certcoin that there are two ways to deploy a password accumulator in a blockchain [3]. One is that each user node maintains its own password accumulator, and the other is that the entire blockchain maintains one Cryptographic accumulator. Since the general cryptographic accumulator accumulates the number of elements subject to the threshold, it is not sufficient to maintain only one accumulator in the blockchain, especially as the number of users in the blockchain increases. Therefore, this paper adopts the method of grouping users. Each user group jointly maintains a password accumulator. Since this paper uses the dynamic accumulator proposed by [15], its own function of batch dynamic update members can be a very good solution to the problem of not being able to effectively test new members (values) in [3]. Compared with the global accumulator and the solution for accumulator information attached to each block proposed in [3], our solution is relatively simple, and the required storage space is small, which effectively saves computational overhead and improves verification efficiency.

The system model of the proposed scheme is shown in the Fig. 1. The whole system includes five participating entities: user, miner node, supervisory node, certificate blockchain and third-party service provider.

Fig. 1.

One-stop PKI authentication service model based on blockchain

• User: Submit the identity and its own public key to the supervisory node for investigation in the registration phase. After joining the system, apply to the miner node or query the blockchain to obtain its own witness for future identity authentication.

• Miner node: Initialize the system, generate the system parameter, accumulate the initial participating user information and output the initial accumulated value and the witness corresponding to each user. Select certificate transactions signed by the supervisory node and execute the corresponding algorithm, then package the corresponding information into blocks for broadcast to the network. Provides the user with a Server-Granting Ticket (SGT). Receives the authorization request sent by the user, verifies and returns session key $K_{c,V}$ and the SGT $Ticket_{V}$ for the user to use. The miner node was initially 21.

• Supervisory node: It is composed of 11 institutions (such as government agencies, core enterprise nodes, etc.), which are responsible for receiving user certificate registration, update or revocation requests, and questioning the transaction initiator. After verification, sign the transaction and sent it to the Pool for further processing.

• Certificate blockchain: After the miner node broadcasts new block information, the supervisory node and other miner nodes respectively verify the block, and after the consensus is reached, the block is mined.

• Third-party service providers: Provide third-party applications or services to users. Receive user service requests, verify and provide related services. Third-party service providers itself have completed the authentication in the certificate blockchain, that is, each service $ID$ has a corresponding witness.

When A proves identity to B, since the nodes in the blockchain are divided into full nodes and light nodes, the efficiency of identity verification is different corresponding to the different node states of B. If B is a full node, you must query all the locally stored information on the chain, that is, traverse the entire blockchain. The authentication efficiency decreases as the blockchain size increases. If B is a light node, the local area is not stored. Blockchain, unable to authenticate, can only request queries from all nodes, which will traverse the blockchain again. The introduction of a dynamic cryptographic accumulator can alleviate the problem of reducing authentication efficiency due to the increase in blockchain size. The authentication procedure of introducing of the dynamic accumulator is improved as follows:

• 1. A sends to B $(c_{A} ,W_{A} ,pk_{A} ,v_{A} )$, where $c_{A} = h(id_{A} ,AD_{A} )$, $h$ is a hash function, $AD_{A}$ is a hash of the network address which uses the unidirectionality of the hash function to guarantee One-to-one correspondence between $c_{A}$, $id_{A}$ and $AD_{A}$, at the same time, it can ensure that the private information is not stolen. It is called that witness $W_{A}$ belongs to user $c_{A}$.

• 2. B compares the accumulated value $v$ with $v_{A}$ which query from the blockchain, if they are consistent, then B runs the algorithm $\text{Verify}(c_{A} ,W_{A} ,v,PK)$ to verify Whether the user’s identity and witness are legal.

• 3. B sends a random challenge string $ch$ to A, A signs $\sigma = sig(sk_{A} ,ch)$ for the information containing the string.

• 4. B uses $pk_{A}$ to verify the digital signature, if $\text{Verify}(pk_{A} ,\sigma ,ch) = 1$, it proves that A holds the private key $sk_{A}$, that means A has identity $c_{A} (id_{A} ,AD_{A} )$.

4.1 Threat Model

This article assumes that communication is secure, it means the private keys of participating entities and systems are not compromised. This makes the supervisory nodes in the proposed scheme completely credible; most miners are honest but curious, will participate in block production and certificate registration, revocation and update according to the rules, but may steal users when participating. Identity privacy information. For the miner node M1 that is partially faulty or evil, when it does not produce the block or even falsify the false certificate according to the regulations, the right of the production block is handed over to the next miner node M2; some users are malicious and may initiate false transactions and malicious preemption registration, even forgery of identity and witness.

4.2 Security Model

In this paper, we define the security model of this scheme by the Chosen Element Attack security game which is described as follows:

Setup:

The challenger ${\mathcal{B}}$ executes the initialization algorithm, and the adversary ${\mathcal{A}}$ adaptively selects a set of elements $L^{ *} \in C$ to send to the challenger who calculates their accumulated value and witness return to the adversary.

Query:

The adversary ${\mathcal{A}}$ chooses the element to be added or the element to be deleted and sends it to the challenger ${\mathcal{B}}$. The challenger returns the witness of the added element after adding or deleting, the new accumulated value, and the auxiliary information of the updated witness. The adversary calculates the witness after each element is updated.

Challenge:

After performing several inquiries, the adversary ${\mathcal{A}}$ selects a set of elements $L \in C$ to send to the challenger ${\mathcal{B}}$, and the challenger returns the corresponding accumulated value and witness. The adversary gives an element $c_{i}$ and its corresponding witness $W_{i}$, then sent them to the challenger who verifies whether the element and its corresponding witness are legal, that is mean, whether the element has been accumulated in the accumulator.

If the polynomial time adversary ${\mathcal{A}}$ forges a legitimate element $c_{i}$ and witness $W_{i}$ with a non-negligible advantage, the witness $W_{i}$ can prove that the element is included in the set corresponding to the accumulated value, which means that the adversary can forge a legal certificate, and the adversary wins this game.

5 Specific Construction

In this part, we present the specific algorithm structure and concrete implementation of the blockchain-based PKI authentication service model.

• 1. Initialization: First, a node group elects miner nodes according to the consensus mechanism such as DPOS, and the miner node M1 with the highest weight creates a security parameter $n$ of length $k{\text{-bit}}$ and an empty set A_u. Let $C = Z_{{n^{2} }}^{*} \backslash \{ 1\}$, $T^{{\prime }} = \{ 3, \cdots ,n^{2} \}$, set the initial participating member list $L = \{ c_{1} , \ldots ,c_{m} \}$, the number of members $m$ $1 \le m \le M$, then proceed with the following steps:

  • Adaptability choose $\sigma \in Z_{{n^{2} }}$, calculate $\beta = \sigma \lambda \bmod$ $\phi (n^{2} ), \, \beta \in T^{{\prime }}$. Uniform random choose $\gamma \xleftarrow{R}Z_{{\phi (n^{2} )}}$, $\gamma \notin (\beta ,\sigma )$, remember the dynamic accumulator key ${\mathcal{P}} = (PK,SK)$, where $PK = (n,\beta )$ $SK = (\sigma ,\lambda ,\gamma )$.

  • Choose $c_{m + 1} \xleftarrow{R}C$, calculates

    $$ \begin{aligned} x_{i} & = F(c_{i}^{{\gamma \sigma^{ - 1} }} \bmod n^{2} )\bmod \,\,n \, \,\,{ (}i = 1, \cdots ,m + 1 ) ,\\ v & = \sigma \sum\limits_{i = 1}^{m + 1} {x_{i} \bmod n,} \\ y_{i} & = c_{i}^{{\gamma \beta^{ - 1} }} \bmod n^{2} \, \,\, (i = 1, \cdots ,m + 1 ) ,\\ a_{c} & = \prod\limits_{i = 1}^{m + 1} {y_{i} \bmod n^{2} } \\ \end{aligned} $$

    (1)

    Output initial $v_{0}$, auxiliary information $a_{c}$ and $A_{l} = (y_{1} , \cdots ,y_{m} )$. P.S. $F(x) = (x - 1)/n$.

  • Package $v_{0}$, $a_{c}$, $A_{l}$ and other related parameters into block and broadcast to network. If block is verified by other miners and supervisory nodes, mining blocks will be successful. Otherwise mining right takes turns to the next miner node M2. The initialization is completed.

• 2. Certificate generation: After the system is initialized, the accumulated users can calculate their own witnesses according to the information disclosed on the blockchain, or they can initiate an application to the miner node, and the miner node signs the corresponding witness. The specific steps are as follows:

Query to get existing auxiliary information $a_{c}$, $A_{l}$ parameters ${\mathcal{P}}$, and randomly select a collection $T = (t_{1} , \cdots ,t_{m} ) \subset T^{{\prime }} \backslash \{ \beta ,\gamma \}$ and calculated:

$$ w_{i} = a_{c} y_{i}^{{\frac{{ - t_{i} }}{\gamma }}} \bmod n^{2} \, \,\, (i = 1, \cdots ,m) $$

(2)

$W_{i} = (w_{i} ,t_{i} )$ is the witness for the user $c_{i}$. Think of the ($c_{i} = h(id_{i} ,AD_{i} )$, $W_{i}$, $pk_{i}$, $v_{i}$) quad as the user’s public key certificate.

• 3. Verify: Give $c_{i}$, $W_{i}$, v and $PK$, check if $\{ c_{i} ,w_{i} \} \subset C$, $t_{i} \in T^{{\prime }}$ and $F(w_{i}^{\beta } c_{i}^{{t_{i} }} \bmod \,n^{2} ) \equiv v \, (\bmod \,\,n)$, if true, output Yes which proved the user $c_{i}$ has indeed been accumulated in v, otherwise output No.

• 4. New user certificate registration: The new user $c_{i}^{ + }$ submits encrypted identity information $c_{i}$, $id_{i}$, $AD_{i}$, and public key $pk_{i}$ to the supervisory node, initiates a registration transaction request, the supervisory node checks $c_{A} = h(id_{A} ,AD_{A} )$ and initiates an acknowledgment to the network address. If supervisory node receives the acknowledgment, that is, the verification transaction can be legal. Then supervisory node signs and puts the transaction into the unprocessed transaction pool. The miner node selects some new user certificate registration transactions from the pool, which is recorded as the set $L^{ + } = \{ c_{1}^{ + } , \ldots ,c_{k}^{ + } \}$ to be added. Then select $c_{k + 1} \xleftarrow{R}C$ and $T^{ + } = \{ t_{1}^{ + } , \ldots ,t_{k}^{ + } \} \xleftarrow{R}T^{\prime}\backslash \{ T \cup \{ \beta ,\gamma \} \}$, calculate:

$$ \begin{aligned} x_{i}^{ + } & = F((c_{i}^{ + } )^{{\gamma \sigma^{ - 1} }} \bmod \,n^{2} )\bmod \,n \, \,\,{ (}i = 1, \cdots ,k + 1 ) ,\\ v^{{\prime }} & = v + \sigma \sum\limits_{i = 1}^{k + 1} {x_{i}^{ + } \bmod \,n,} \\ y_{i}^{ + } & = (c_{i}^{ + } )^{{\gamma \beta^{ - 1} }} \bmod \,n^{2} \, \,\,{ (}i = 1, \cdots ,k + 1 ) ,\\ a_{u} & = \prod\limits_{i = 1}^{k + 1} {y_{i}^{ + } \bmod \,n^{2} } , \\ w_{i}^{ + } & = a_{u} a_{c} (y_{i}^{ + } )^{{\frac{{ - t_{i}^{ + } }}{\gamma }}} \bmod \,n^{2} \, \,\, (i = 1, \cdots ,k + 1) \\ \end{aligned} $$

(3)

Let $T = T \cup T^{ + }$, $A_{u} = A_{u} \cup \{ a_{u} \}$, $a_{c} = a_{c} a_{u} \bmod n^{2}$, then get new accumulated values $v^{{\prime }}$, new auxiliary information $a_{u}$, $a_{c}$ and new witnesses $W_{i}^{ + } = (w_{i}^{ + } ,t_{i}^{ + } )$ of user $c_{i}^{ + }$. Being similar to the initialization, the miner node packages the corresponding information and broadcasts, and other miners add the new block to the blockchain. In addition, the recommended value is in the actual application.

• 5. User certificate revocation: The pre-revoked user $c_{i}^{ - }$ presents his own witness $W_{i} = (w_{i} ,t_{i} )$ and signature $\sigma$ to the supervisory node, initiates an identity revocation request, and also counts the signature into the unprocessed transaction pool. The miner node selects some user identity revocation transactions from the unprocessed transaction pools, which is recorded as the set $L^{ - } \{ c_{1}^{ - } , \ldots ,c_{k}^{ - } \}$ $(L^{ - } \subset L,1 \le k < m)$ to be revoked. For a user identity revocation transaction, the supervisory node first verifies the signature $\sigma$ to verify that the witness actually belongs to the user, and then proceeds to step 3 to verify that the user identity has been accumulated.

If yes, select $c_{k + 1}^{ - } \xleftarrow{R}C$ and calculate:

$$ \begin{aligned} x_{i}^{ - } & = F((c_{i}^{ - } )^{{\gamma \sigma^{ - 1} }} \bmod n^{2} )\bmod n \, \,\, (i = 1, \cdots ,k + 1 ) ,\\ v^{{\prime }} & = v - \sigma \sum\limits_{i = 1}^{k} {x_{i}^{ - } } + \sigma x_{k + 1}^{ - } \bmod n \\ y_{i}^{ - } & = (c_{i}^{ - } )^{{\gamma \beta^{ - 1} }} \bmod n^{2} \, \,\,{ (}i = 1, \cdots ,k + 1 ) ,\\ a_{u} & = y_{k + 1}^{ - } \prod\limits_{i = 1}^{k} {(y_{i}^{ - } )^{ - 1} \bmod n^{2} } \\ \end{aligned} $$

(4)

Let $a_{c} = a_{c} a_{u} \bmod \,\,n^{2}$, $A_{u} = A_{u} \cup \{ a_{u} \}$ then get the new accumulated value $v^{{\prime }}$, the new auxiliary information $a_{c}$ and $a_{u}$. Then, being similar to the initialization, the miner node packages and broadcasts the corresponding information. Other miners and supervisory nodes verify and add the new block to the blockchain, and the certificate revocation transaction is recorded on the chain. The witness $W_{i} = (w_{i} ,t_{i} )$ expires, that is, the user certificate has expired.

• 6. Certificate update: There are two ways to update a certificate. The first is to update the witness only. User presents his own witness and signature to the supervisory node, initiates a certificate update transaction request, which is verified into the unprocessed transaction pool. The miner node selects some user certificate update transactions from the pool, which is recorded as the set $L^{{\prime }} \{ c_{1} , \ldots ,c_{k} \}$$(L^{{\prime }} \subset L,1 \le k < m)$ to be updated. Then it calculates $w_{i}^{{\prime }} = w_{i} a_{u} \bmod n^{2}$ and the user’s update witness is $W_{i}^{{\prime }} = (w_{i}^{{\prime }} ,t_{i} )$. $t_{i}$ is generated when the user is added to the accumulator, it remains the same, and only changes with witness update and other transactions. Therefore, $t_{i}$ can also be used as an alternative identifier in the accumulator.

It should be noted that each certificate has a corresponding time stamp and accumulator related information. Whenever a miner performs a certificate transaction, the parameters $a_{u}$ are updated once and are credited to the collection $A_{u}$. When a user initiates a certificate update transaction, the miner needs to query the user’s for finding the elements $a_{{u_{i} }} (i = 1 \cdots k)$ in the collection $A_{u}$ from last certificate update or registration to this time, $k$ is the number of times for $a_{u}$ changes between the last certificate update and this transaction. Calculate $a_{u} = a_{{u_{1} }} \cdots a_{{u_{k} }} \bmod n^{2}$, $w_{i}^{{\prime }} = w_{i} a_{u} \bmod n^{2}$, then the user’s new witness is $W_{i}^{{\prime }} = (w_{i}^{{\prime }} ,t_{i} )$. In this way, the user certificate update is independent of the change of the accumulated value.

The second way is to update the witness and key. The user submits $c_{i}$, $W_{i} = (w_{i} ,t_{i} )$, $pk_{i}$, $pk_{i}^{{\prime }}$, $AD_{i}$ and $v_{i}$, where $pk_{i}^{{\prime }}$ is the new public key. When the user issues a request transaction to update the key, the supervisory node first performs a third step to verify that the user is registered and verifies the consistency of the network address with the user. Then find the current certificate of the user and verify that $pk$ and $pk_{i}$ are consistent. This is to prevent the adversary from maliciously updating the user certificate with the old public key that the user has previously leaked. After the verification, the miner updates the user’s witness, then packages the user’s new public key and other information into block and broadcastes. Other nodes verify the block and add it to blockchain.

• 7. User-service authentication exchange: The specific description is shown in Table 1. The user c sends $c$, $id_{V}$ of the service and the witness $W_{c}$ to the miners for Server-Granting Ticket, and the miner returns the session key $K_{c,V}$ and SGT $Ticket_{V}$. Then user $c$ sends $Ticket_{V}$ and $Authenticator_{c}$ to the third-party service provider V, and the server provider gives corresponding respond after verification. If mutual authentication is required, a reply message should be sent to c according to message (4) by V. Obviously, the message is encrypted by $K_{c,V}$, which guarantees that the message is only generated by $V$, and confirms the source of the message by verifying $W_{V}$.

  Table 1. User-service authentication exchange

$Authenticator_{c}$ is a legal authentication ticket generated by the user which ensures that the owner of the ticket is the same as the owner when the SGT generated. $Authenticator_{c}$ can only be used once and has a very short lifetime. Miner queries blockchain for $pk_{c}$ according to $id_{c}$ and $W_{c}$ to make decryption of the authentication ticket. The session key $K_{c,V}$ is issued by the miner to ensure secure exchange of information between the user and the third-party service provider. $AD_{c}$ is network address that used to prevent the ticket from being used on wrong workstations. $Lifetime$ is used to prevent the ticket from using after it expires; $TS$ is a timestamp for the ticket.

6 Security Analysis

According to the attack form summarized in the threat model, if the user issues a false transaction, the miner node can detect whether the transaction is legal when packing the block. When the enemy maliciously seizes the identity of others for registration, he must submit $c = h(id,AD)$ and $pk_{c}$, and the supervisory node initiates an acknowledgment to the network address. If the network address is false, no agreement can be reached between $c,id$ and $AD$, no malicious preemption is formed. If true, the preempted user will receive a confirmation message, then he can refuse to register and the transaction is invalid. In order to achieve the preemption registration, the adversary must ensure that the preempted user cannot receive the confirmation message and reply to the supervisory node with the correct network address, so that the certificate ownership belongs to the preempted user, as long as he logs in, the certificate can be found, and the preempted user can revise the certificate at any time.

Theorem 1.

Based on the es-RSA assumption, this scheme can resist Chosen Element Attack.

Proof.

Assume that a polynomial time adversary ${\mathcal{A}}$ wins a CEA game with a non-negligible advantage in a defined security model, which means that for input $(n,\beta )$, the adversary ${\mathcal{A}}$ gets $l$ elements $L^{*} :\{ c_{1} , \cdots ,c_{l} \} \subset C$, $\{ W_{1} , \cdots ,W_{l} \}$ and corresponding accumulated values $v$, he can find element $c^{{\prime }} \in C\backslash \{ c_{1} , \cdots ,c_{l} \}$ and corresponding $W^{\prime} = (w^{\prime},t^{\prime})$ make $F(w^{{{\prime }\beta }} c^{{{\prime }t^{{\prime }} }} \bmod \,\,n^{2} ) \equiv v(\bmod \,\,n)$ with a non-negligible advantage. This paper constructs the following simulator ${\mathcal{B}}$ to break the es-RSA hypothesis with a non-negligible advantage.

Initialization.

${\mathcal{B}}$ runs the initialization algorithm and gets the relevant system parameters, the accumulated values $v$ and witnesses of $l$ elements $L^{*} :\{ c_{1} , \cdots ,c_{l} \} \subset C$, the adversary request, and ${\mathcal{A}}$ requests $L^{*} :\{ c_{1} , \cdots ,c_{l} \} \subset C$, $v$ and $\{ W_{1} , \cdots ,W_{l} \}$ from ${\mathcal{B}}$.

Query 1.

The adversary ${\mathcal{A}}$ selects the set of elements $L^{ \pm } (L^{ \pm } \subset C)$ to be added or deleted and sends them to ${\mathcal{B}}$. ${\mathcal{B}}$ runs the corresponding algorithm to complete the addition or revocation of the user certificate, and gets the new accumulated value $v^{{\prime }}$, the new auxiliary information $a_{c} ,$$a_{u}$ and the corresponding witness $W_{i}^{ \pm } = (w_{i}^{ \pm } ,t_{i}^{ \pm } )$. Return to the adversary.

Query 2.

The adversary ${\mathcal{A}}$ selects a set $L^{{\prime }} (L^{{\prime }} \subset L^{*} )$ of updated users to send to the ${\mathcal{B}}$. $..$ runs the algorithm to update the user certificate and returns the update witness $W_{i}^{{\prime }} = (w_{i}^{{\prime }} ,t_{i} )$ corresponding to the relevant user.

Challenge:

After performing Query 1 and Query 2 several times, the adversary ${\mathcal{A}}$ selects $L:\{ c_{1} , \cdots ,c_{m} \} \subset C$ queries ${\mathcal{B}}$ for corresponding $v$ and $\{ W_{1} , \cdots ,W_{m} \}$, then forges element $c^{{\prime }} (c^{{\prime }} \in C\backslash L)$ and its corresponding witness $W^{{\prime }} = (w^{{\prime }} ,t^{{\prime }} )$ and sends them to ${\mathcal{B}}$. ${\mathcal{B}}$ runs the algorithm and verifies if the element $c^{\prime}$ has been accumulated in $v$. If the algorithm Verify outputs Yes with a non-negligible advantage, which means ${\mathcal{B}}$ can break the es-RSA assumption with a non-negligible advantage.

${\mathcal{B}}$ calculates $v$ and $\{ W_{1} , \cdots ,W_{m} \}$ corresponding to $L:$ $\{ c_{1} , \cdots ,c_{m} \}$ and therefore exist $F(w_{i}^{\beta } c_{i}^{{t_{i} }} \bmod n^{2} ) \equiv v(\bmod \,\,n) ,$ ${ (}i = 1, \cdots ,m )$, which means that:

$$ \exists k \in Z,\frac{{w_{i}^{\beta } c_{i}^{{t_{i} }} \bmod n^{2} - 1}}{n} = kn + v $$

(5)

Therefore,

$$ w_{i}^{\beta } c_{i}^{{t_{i} }} \equiv (vn + 1)(\bmod \,n^{2} ) $$

(6)

Also, we have

$$ w_{i}^{\beta } \equiv (vn + 1)c_{i}^{{ - t_{i} }} (\bmod \,\,n^{2} ),c_{i}^{{t_{i} }} \equiv (vn + 1)w_{i}^{ - \beta } (\bmod \,\,n^{2} ) $$

(7)

So there are $m$ triplets $(c_{i} ,w_{i} ,t_{i} )$, $c_{i} ,w_{i}$ and $t_{i}$ can be calculated from Eqs. (6) and (7).

Since $v$ is calculated by adding a random element each time an element is added or revoked, and $t_{i}$ is the randomly selected, the probability distributions of $v$, $w_{i}$, $t_{i}$ and $a_{u}$ are consistent, so Query 1, 2 does not help ${\mathcal{A}}$ forging. If ${\mathcal{B}}$ breaks the es-RSA hypothesis with a non-negligible advantage, he can get a different triplet $(c^{{\prime }} ,w^{{\prime }} ,t^{{\prime }} )$ make (6) true with a non-negligible advantage. At this time, we have:

$$ w^{{{\prime }\beta }} \equiv (vn + 1)c^{{{\prime } - t^{\prime}}} (\bmod \,n^{2} ) \Rightarrow w^{{{\prime }\beta }} \equiv \left( {(vn + 1)^{{ - \frac{1}{{t^{\prime}}}}} c^{\prime}} \right)^{{ - t^{\prime}}} (\bmod \,n^{2} ) $$

(8)

If $y = w^{{{\prime }\beta }}$, $x = (vn + 1)^{{ - \frac{1}{{t^{\prime}}}}} c^{\prime},s = - t^{\prime}$, that is $y \equiv x^{s} (\bmod \,n^{2} )$.

Obviously, if the adversary ${\mathcal{A}}$ can forge a triple $(c^{\prime},w^{\prime},t^{\prime})$, it can resolve Eq. (8), which is equivalent to solving $y \equiv x^{s} (\bmod \,n^{2} )$. This means that the es-RSA assumption is broken. This contradicts with Lemma 1. So, it can be concluded that no enemy can win the security game with obvious advantages. The scheme can defend against CEA. According to the previous security model, our scheme can prevent adversary from forging witnesses and identities.

Theorem 2.

The scheme can resist Sybil attack.

Proof.

Sybil attack refers to the creation of multiple account identities in one malicious node. The adversary ${\mathcal{A}}$ can control most of the network with few nodes to achieve refusal to deal, fork, double payment and so on. In this paper, the user’s network address and the user’s identity are bound, and the joining of the new node needs to be authenticated by the supervisory node, so that ${\mathcal{A}}$ cannot create multiple identities in one node, so the scheme can resist Sybil attack.

7 Analysis and Comparison

7.1 Efficiency Analysis

The overhead of this scheme is mainly divided into storage overhead and computational overhead, and communication overhead is not considered. For storage overhead, the user node only needs to store its own witness and the accumulated value can realize the identity verification. The miner node must retain the certificate data $(c_{i} ,W_{i} ,pk_{i} ,v)$ of the entire node group and maintain the relevant information of the accumulator (auxiliary information $a_{u}$, $a_{c}$, $A_{l}$ etc.). Supervisory node is only responsible for identity information and transaction auditing, no need to store relevant information. Since the magnitude of the witness and the accumulated value are small and constant, that is, the size of the dynamic accumulator is small, the full node and the light node can complete the corresponding identity authentication at any time only by updating regularly, and the space complexity of the corresponding storage overhead is $O(1)$, which improves the efficiency of certification.

The computation overhead mainly includes requests for registration, deletion, and update of certificates. Let $Md$ be the cost of modular operation, $E$ be the cost of exponential operation. For a group with $m$ initial member, the calculation cost of the scheme mainly includes:

Compute initial key: $Md$; Generate initial parameters: $2(m + 1)E + \left( {3m + 5} \right)Md$; Generation of each certificate: $E + Md$. Verification a certificate: $2E + 3Md$. $k$ Certificate registration: $(3k + 2)E + (4k + 6)Md$. $k$ Certificate revocation: $2(k + 1)E + (3k + 6)Md$. Update a certificate: $2Md$.

7.2 Scheme Comparison

The comparison between this paper and related PKI schemes is shown in Table 2. Certcoin proposed in [3] builds a PKI model based on blockchain, and uses the offline key to protect the online key. At the same time, the certificate is efficiently managed by means of RSA accumulator and distributed hash table. Aucoin is a decentralized PKI scheme [5]. The scheme uses a flexible challenge response mechanism for verification and authentication when issuing a public key, thereby reducing illegal occupancy and Sybil attack. The IKP scheme proposed in [8] uses smart contracts to reward detectors that report illegal certificates, impose financial penalties on CAs that issue illegal certificates, and to motivate CAs that work correctly to ensure proper certification. Cercoin in [12] proposed a set of rules based on the Bitcoin system to verify the validity of the certificate and the consistency of ownership, and to provide a method of identity assignment. At the same time, the scheme improves the Merkle Patricia tree to achieve efficient management of certificates, including efficient retrieval and verification of certificates.

Table 2. Comparison of this article and other PKI schemes

8 Conclusion

This paper proposes a one-stop efficient PKI authentication service model based on blockchain. Firstly, we divide the node group into five different participating entities: user, miner node, supervisory node, certificate blockchain and third-party service providers, and propose a new blockchain based PKI model that resolves the single point of failure problem and can resist Sybil attack. In addition, this paper uses the witness generated by the dynamic accumulator to replace the role of certificates in traditional PKI, and proposes new user certificate management (registration, revocation and update) algorithms based on the dynamic accumulator, which improves efficiency of authentication. This paper also builds an authentication interaction model between the certificate blockchain and the third-party service providers. This model can provide a one-stop authentication service for users and third-party service providers, which will facilitate the deployment of PKI on blockchain. Finally, Security and efficiency analyses show that our scheme can effectively resist the Chosen Element Attacking, and improve the identity verification efficiency.

However, there still exists improvement spaces in our scheme. Because this article uses the network address to ensure the identity authentication, once the user’s network address is changed, he must carry out the corresponding revoke and add a new certificate, this will bring inconvenience to users and improve the system overhead. In addition, the dynamic accumulator used in this paper exists much modular arithmetic, which brings high computational overhead. We will improve the dynamic accumulator to increase the calculation efficiency in future work, and further improve the model to avoid frequent certificate revocation and adding transactions in some cases.