A New Anti-Quantum Proxy Blind Signature for Blockchain-Enabled Internet of Thin

Chaoyang Li,Gang XuYuling Chen,Haseeb Ahmad and Jian Li

Abstract:Blockchain technology has become a research hotspot in recent years with the prominent characteristics as public,distributed and decentration.And blockchain-enabled internet of things (BIoT)has a tendency to make a revolutionary change for the internet of things (IoT)which requires distributed trustless consensus.However,the scalability and security issues become particularly important with the dramatically increasing number of IoT devices.Especially,with the development of quantum computing,many extant cryptographic algorithms applied in blockchain or BIoT systems are vulnerable to the quantum attacks.In this paper,an anti-quantum proxy blind signature scheme based on the lattice cryptography has been proposed,which can provide user anonymity and untraceability in the distributed applications of BIoT.Then,the security proof of the proposed scheme can derive that it is secure in random oracle model,and the efficiency analysis can indicate it is efficient than other similar literatures.

Keywords:Blockchain,blockchain-enabled internet of things,quantum computers,proxy blind signature.

1 Introduction

Blockchain has gained much attention in recent years with its public,distributed,decentration and chronological characteristics.It is usually considered as a reliable database with high Byzantine fault tolerance (Fig.1),and used in finance,cloud computing,IoT systems and other applications.Bitcoin is the first application of the blockchain technology,which constructs a peer-to-peer electronic cash system[Nakamoto (2008)].BIoT has a promising outlook to build more efficient and resourcesaving industrial systems,which can solve many problems in the centralized cloud systems and platforms [Banafa (2017)].And it also can realize peer-to-peer transmission between unfamiliar users and build a distributed and append-only block storage structure among the trustless environment.

Figure1:Structure of the blockchain.As the block contains a number of transactions in the latest time period,and the head of block contains the PreHash,Hash,Timstamp,and so on.Here,PreHash is the Hash value of the former block; Hash is the Hash value of this block; Timstamp is the setup time of this block

So far,IoT has gained more attraction in many fields,such as manufacturing,logistics,retailing and pharmaceutics.Since the high level of heterogeneity of IoT devices,the openness of wireless channel and limited resources of IoT devices,there are a number of serious security problems and challenges in IoT systems [Sicari,Rizzardi,Grieco et al.(2015);Pang,Liu,Zhou et al.(2017);Li,Wang,Li et al.(2018)].Wang et al.[Wang and Wang (2014)] pointed that the former cryptography,such as symmetric cryptography protocols and hash-based user authentication protocols,are vulnerable to user anonymity and smart card security breach attack.Therefore,the public-key cryptography,for example the elliptic curve cryptography (ECC),can be used to strengthen the security for WSNs [Yeh,Chen,Liu et al.(2011);Shi and Gong (2013)].However,the former two protocols cannot satisfy user anonymity and untraceability.Then,Jiang et al.[Jiang,Ma,Wei et al.(2016)] presented an ECC-based untraceable authentication scheme,which was computational efficiency.Recently,Li et al.[Li,Peng,Niu et al.(2017)] has presented a three-factor user authentication protocol based on ECC to secure WSNs,and it declares that can eliminate the weaknesses of former protocols.

Unfortunately,the quantum attacks take a significant threaten to most current digital signature schemes used for authentication in current blockchain-enabled systems along with the development of quantum computing and quantum communication [Li,Chen,Xu et al.(2015);Xu,Chen,Li et al.(2015);Qu,Cheng,Liu et al.(2018);Liu,Xu,Yang et al.(2018);Chen,Wang,Xu (2019);Chen,Sun,Xu et al.(2017);Jiang,Xu,Xu et al.(2018)].As the classical mathematic hard problems widely applied in most asymmetric cryptosystems,such as the integer’s factorization problem and discrete logarithm problem,can be solved by the quantum computer with super-polynomial speedup.While in Bitcoin system,the Elliptic Curve Digital Signature Algorithm (ECDSA)used which is constructed by the discrete logarithm problem.However,Shor’s algorithm [Shor (1999)] can solve the integer factorization problem and discrete logarithm problem with exponential speedup by the quantum Fourier transform [Nielsen and Chuang (2000)].And Grover's algorithm[Grover (1996);Jiang,Wang,Xu et al.(2018)] can search the objective from solution space with quadratic speedup.As it can decrease the complexity of seeking the pre-image for a certain function value tohere the complexity of the classical brute force search isHence,by using the Grover algorithm,the adversary can easily destroy the current blockchain-enabled systems in two ways：

● It can make full control over the generation of new blocks,as the acquisition of accounting rights depends on finding a particular hash value in POW-enabled blockchain systems.

● It can tamper the transaction records in former blocks equipped with greater computing power by speeding up the generation of nonce.

Therefore,how to resist the incoming quantum attacks becomes a more important research topic.In recently years,some promising visions have been invested which can weak above threats effectively,such as the quantum-resistant cryptography,postquantum blockchain (PQB),quantum hashing and quantum network time machine.As the lattice-based cryptography [Gentry,Peikert and Vaikuntanathan (2008);Ajtai (1996);Zhang and Ma (2014);Zhu,Tan,Zhu et al.(2018);Yin,Wen,Li et al.(2018)] and the Hash-based cryptography [Dong,Zhang,Zhang et al.(2014);Jiang,Jiang and Ling(2014)] can significantly resist the quantum attack,which are also more appropriate for the transaction authentication in current blockchain system.And the quantum informational vision system,for example the post-quantum blockchain,is the conjugate of classical blockchain system and quantum-resist cryptography [Gao,Chen,Sun et al.(2018);Li,Chen,Chen et al.(2018)].While the storage structure is classical and the communication protocol is quantum [Xu,Chen,Dou et al.(2015);Qu,Wu,Wang et al.(2017);Liu,Wang,Yuan et al.(2016);Wei,Chen,Niu et al.(2015);Xu,Chen,Dou et al.(2016);Qu,Chen,Ji et al.(2018);Liu,Gao,Yu et al.(2018);Chen,Tang,Xu et al.(2018)].Then,the quantum hashing is a more robust system than the binary hash system against various distortions,though they have the same intermediate hash values [Jin and Yoo (2009)].While the quantum network time machine a novel design of quantum blockchain which was claimed as a quantum blockchain using entanglement in time.Meanwhile,it is also a more promising method against the quantum attacks [Rajan and Visser (2018)].

Lattice cryptography served as a candidate for the quantum-resistant methods,which has more advantages than any other theories and is suitable for the blockchain-enabled systems.In 2008,Gentry et al.[Gentry,Peikert and Vaikuntanathan (2008)] proposed the first lattice-based signature scheme which is provable secure in the random oracle based on SIS problem [Ajtai (1996)].And there is a novel cryptographic primitive has been presented which was called the preimage sample function (PSF).Recently,based on the lattice cryptography,some anti-quantum cryptographic schemes have been presented to strength the protection of the transaction authentication process in blockchain network.Zhang et al.[Zhang and Ma (2014)] proposed an identity-based proxy blind signature scheme based on lattice cryptography,and it showed that the proposed scheme was secure in standard model.Recently,Zhu et al.[Zhu,Tan,Zhu et al.(2018)] proposed an efficient identity-based proxy blind signature for semi-offline service,which showed that it could satisfy anti-quantum security.And Yin et al.[Yin,Wen,Li et al.(2018)] adopted Bonsai Tree technology to generate the private keys from the seed key,which could construct a lightweight nondeterministic wallet for anti-quantum transaction authentication.While Gao et al.[Gao,Chen,Sun et al.(2018);Li,Chen,Chen et al.(2019)] presented a secure cryptocurrency scheme based a lattice-based double-signature scheme in PQB.

The proxy blind signature can provide delegation and anonymous authentication to protect the user’s privacy,which was widely used in e-cash,voting and oblivious transfer.For some situations in BIoT,user must delegate his signing rights to another user,and the transaction information should be covert but verifiable.Therefore,in this paper,an antiquantum proxy blind signature depend on the lattice cryptography has been presented,which can strength the transaction information security in the blockchain-enabled platforms for BIoT.And the proposed scheme not only can provide remarkable result against the quantum attacks,but can satisfy the properties of user anonymity and untraceability.In addition,the security proof of the proposed scheme has been proved secure in random oracle model,while the efficiency comparison also has been analyzed with some similar literatures.

The organization of this paper is as follows：some lattice theories and some related facts have been given in Section 2.A lattice-based proxy blind signature scheme has been proposed in Section 3.While the security proof has been presented in Section 4.And discussed the application in BIoT systems in Section 5.Then,the efficiency comparison and conclusion are shown in Section 6.

2 Preliminary

2.1 Some lattice theories

Definition 1 (Lattice)[Micciancio and Regev (2013)]:Letbeam×mmatrix,hereare linearly independent vectors.Based onthe latticeΛis a set

where the two lattices are dual to each other under normalization,just asand

The shortest vector problem (SVP)and short integer solution (SIS)problem are two hard computational problems in lattice cryptography.And the hardness of SIS problem is the foundation of lattice-based signature scheme,which also widely used in one-way and collision-resistant hash functions,identification schemes and digital signatures.

Definition 2 (SVP problem)[Ajtai (1996)]:Given latticeL=L(B),B is the basis,output a shortest nonzero lattice vector,i.e.,aV∈Lsatisfying||v||=λ1(L).

Definition 3 (SIS problem)[Ajtai (1996)]:Given the system parameters n,m,q,β,andis a uniform and random matrix.Output a nonzero integer vectortwo-dimensionalq-arylattices：satisfying||v||≤βandAv= 0modq.

Gaussian Distribution:With the standard deviationσ∈R,and the centerc∈Rn,the un-normalized definition of Gaussian distribution is

In order to decreasing the signature size,Lemma 1about the discrete Gaussian distribution are used in our proxy blind signature scheme.

Lemma 1[Micciancio and Regev (2007)]:Fork≥1,itsatisfiesAnd then,for any vectorv∈Rmandσ,r＞0,we can get

2.2 Security model

As for security,the proxy blind signature scheme should satisfy the three fundamental properties：non-authorization unforgeable,blindnessandone-more unforgeability[Ruckert (2010)].

Non-authorization unforgeable:The adversary cannot obtain anything about the proxy private key secretly established between the user and the proxy signer without authorization.

Blindness:The experimentdenotes the notion of blindness,where the adversarial signerS*try to forge the valid signature in three modes：find,issueandguess.Then,in modefind,randomly chooses two messagesM0,M1and interacts with two different users in modeissue.According to the coin flipb,the two different users obtain blind signature for the messagesMb,M1-b,respectively.And in modeguess,by seeing the unblinded signatures respect toM0,M1in the original order,the signer should guess the bitb.Neither of the two different users’s algorithms cannot output a valid signature,the adversarial signer declares failure and does not get any information of the valid signature.In addition,note that we allow the adversary to keep a state that is fed back in subsequent calls.A blind signature schemeBSis(t,δ)-blind,if there does not exist an adversaryS*that wins the above experiment with probability at leastδwithin the time at mostt,where the probability is defined asThus,a blind signature scheme isstatisticallyblind if the blind signature scheme is(∞,δ)-blindwith the negligible probabilityδ.

One-more unforgeability:The other security property is one-more unforgeability,which ensures that once completed interaction can only generate one signature between the signer and the user.Experimentcan show the interaction between the adversarial user and the honest signer,as thejvalid signatures can be obtained with at leastl＜jcompleted interactions.NoteHis a set of random oracles,the formal definition of blind signature scheme isBSis(t,qSign,qH,δ)-one-more unforgeability,if there does not exist an adversaryA,running in time at mostt,making at mostqSignsignature queries and at mostqHhash oracle queries,can win the former defined experiment with negligible probabilityδ.

3 Lattice-based proxy blind signature scheme

Now,we will present the new proposed lattice-based proxy blind signature scheme,which mainly contains three parts：key generation,delegation generation and proxy blind signature generation.in this chapter,we will present the new proposed lattice-based proxy blind signature scheme,which mainly contains three parts：key generation,delegation generation and proxy blind signature generation.

Key Generation:Chosenκas the system security parameter,and some other parametersn,q,κ,u,σ,ηare same as Ducas et al.[Ducas,Durmus,Lepoint et al.(2013)].Note that the public key is aand the private key is an×mmatrixwhile they satisfyAnd the public and private keys of the proxy signer arewhich also satisfy

As the bimodal Gaussian distribution can make the reject sampling more efficient,this paper will applied it in the proposed scheme,while the detail steps of reject sampling are described in Jiang et al.[Jiang,Liang,Liu et al.(2017)].

Delegation Generation:Firstly,the user signs the proxy signature certificateWwith his public and private keys,and sends the proxy warrantWA←Bto the proxy signer.Here,this proxy signature certificateWcontains the agent identity,proxy signature authority and authorization expiration date.Next,the proxy signer verifies the proxy warrant and generates the proxy public and private keys with proxy warrant for the proxy blind signature.

● The user randomly choosesandNext,he computesu1with his own public keyA,private keySand the proxy signature certificateW

Then,he will output the signature Warrantwith probabilityand send it to the proxy signer.

● When the proxy signer receives the signature Warrantshe will reject it ifand accept it if the following equation holds：

● The proxy signer generates the proxy public and private keys for the next proxy blind signature generation.Here,she choosesand computes

Proxy Blind Signature Generation:When the delegation has been established between the user and the proxy signer,they will implement the following algorithms to generate the proxy blind signature.And through the following four algorithms：Blinding Algorithm,Signing Algorithm,Unblinding AlgorithmandVerifying Algorithm,a legitimate proxy blind signature will be generated as shown in following：

● The proxy signer randomly choosesand computeswith his own public keyAP.Then,she sends (r,x)to the user.

● This is theBlinding Algorithm.When the user receivers (r,x)from the proxy signer,he first randomly choosesNext,he computesu2with the proxy signer's public keyAPand the messagem

Then,he will output blind messageu2with probabilityand send it to the proxy signer.

● This is theSigning Algorithm.When the proxy signer receivers blind messageu2from the user,she computeszwith her own private keySPand the former selectedr

Then,she will output the signaturezof the blind message with probabilityand send it to the user.

● This is theUnblinding Algorithm.When the user receivers the signaturezfrom the user,he computesewith the former selectedy2

Then,he will output the proxy blind signatureeof the original message with

Figure2:The lattice-based proxy blind signature scheme

4 Security proof

● This is theVerifying Algorithm.The generated proxy blind signature will be rejected if ||e| |＞B2and ||e| |∞＞q4,and accepted if the following equation holds：

By this time,a legal proxy blind signature has been generated as the above Eq.(10)through certification.And the simple processes of the proposed proxy blind signature scheme can be description as follows in Fig.2.

In this phase,the verifier will verify whether the proxy Blind signature ＜e,c2＞is legal or not firstly.If||e| |＞B2or ||e| |∞＞q4,the signature will be rejected.Otherwise,the correctness of the proposed proxy blind signature is mainly depending on equationAPe+qc2=x+APy2mod2q,and detail of it is showing as follows：

For the proxy blind signature scheme,it should resist the attack of the existence of strong unforgeable under the non-authorization (Shown inTheorem 1).And it also should satisfy the properties of blindness (Shown inTheorem 2)and one-more unforgeability(Shown inTheorem 3).

Theorem 1:The proposed proxy blind signature scheme can defeat strongly unforgeable under the non-authorization.

Proof:As this kind of forgery,the adversary cannot obtain anything about the proxy private key,which is generated from the proxy warrantWA←Bsecretly established between the user and the proxy signer.If the adversary has the ability that he can forge a valid proxy blind signature,it says that the adverasary can forge the delegation generation stage without knowing the original user’s secret key.If so,it will indicate that the latticebased signature scheme in Ducas et al.[Ducas,Durmus,Lepoint et al.(2013)] is not safe.

Theorem 2:The proposed proxy blind signature scheme is statistically blind.

Proof:Assume there exists two different usersthe adversary has ability to attack the proposed scheme with advantageand. As for the blindness, we only show that the outputsu2and signature (c2,e)are independent of their corresponding messages, note thatFirst, as the distribution ofu2, letubandu1-bbe generated by the interaction with the userandrespectively.Because the constructionand the output probabilitywe tailoredubandu1-bto be distributed depending on the same distributionby the rejection sampling lemma. Thus, the statistical distanceand they are distributed independently of the message being signed.Second, as the distribution of signaturee, which is similar tou2. Letebande1-bbe the blind signature ofandrespectively. Because the constructione←y2+zand the output probabilitythus the statistical distance satisfiesby the rejection sampling lemma. Therefore, the generated blind signatures are independent of their corresponding messages. And then the proposed proxy blind signature is statistically blind to the adversarialS*.

Theorem 3:Assume there exists an adversary F who can forge a valid proxy blind signature with non-negligible probabilityδ,then there will exist a polynomial-timealgorithm C which can solveproblem forβ=2B2.

Proof:The proposed proxy blind signature scheme follows the fact that the output is independent of the signing key.While the main outputs are the Hash value and signature of the message,so theForgeronly need to make theHash queriesandSign queries.Then,if the adversary has ability to against the property ofOne-more unforgeability,we will show that the simulator can find a solution ofSISproblem.

Hash queries:ChallengerCbuilds an initial empty listList1 to store the hash valueHash(m)of messagem.When theForgersends queries for messagemtoC,firstly he will check whether the pair ＜m,Hash(m)＞exists in theList1 or not.If it is,Ctake＜m,Hash(m)＞as the answer of theForger’s Hash queries;if not,Cwill compute the new hash value of messagem,and send the new pair＜m,Hash(m)＞toForgerand restore it to theList1.

Sign queries:Cholds an initial empty listList2 which contains the blind signature pairs＜e,c2＞.When theForgersends a queries for a signature about messagem,firstlyCwill checks whether this pair＜e,c2＞exists in theList2.If it is,Cwill take pair＜m,e,c2＞as the answer of theForger’s Sign queries;if not,Cwill run the blind signing process to generate a blind signature of the messagem,send the new signature pair＜e,c2＞to theForgerand restore it to theList2.

Forge:Assume thatcwas the answer to a Hash query made by theForger,then by the Eq.(5),we can derive thatfor the two different signature pairsand ＜m',e',c2＞.In case ofm≠m'orthere makes a hash collision.Due to the property of Hash function,it is impossible to arise that phenomenon.Therefore,we can getm=m'andwith overwhelming probability.Which also can yield the follow equationand we know thate-e'≠0.Hence,theSISproblem can be successfully solved.

And depending on the proof [Ducas,Durmus,Lepoint et al.(2013)],assume that thecjis a response whichCgives to theForger.We can set this blind signature as ＜e,cj＞ for messagem,and choose different random valuesThen,by theForking Lemma[Bellare and Neven (2006)],we can get the probability of

Form above simulation,theForgercan generate another new blind signature pair＜e′,c′j＞,which satisfyBased on the former designing,the proxy public and private key in the proposed scheme can also satisfyAnd then

Sincecj≠c′,we can havee-e′ ≠0mod2q.And,we will have ||e| |∞,||e′ ||∞≤q4 with overwhelming probability,thus ||e-e′ ||∞＜q2.As we also know thatmod2q=0,and we letv=e-e′ ≠0mod2q,then we haveAPv= 0mod2q.Note that ||v||≤β,and thevis one of theSISproblem’s solution withβ=2B2.

5 The transaction implementation in BIoT

Equipping with the former proposed proxy blind signature scheme,current BIoT systems will have enough ability to resist the quantum attacks.It also can provide delegation and anonymous authentication to protect the user’s privacy.

Figure3:The transaction implementation

In the distributed blockchain-enabled systems,the general user and the miner are different independent entities who have different function to maintain the whole network.More importantly,the transaction address is essential for transaction implementation,which is generated by the public key.Here,the user should generate many more public keys for the generation of the every new address to prevent the statistical attack.Then,for a transaction,it is a data structure with different inputs and outputs.As the inputs are thePrevious tx.,IndexandScriptSig,herePrevious tx.denotes the Hash value of previous transaction;Indexdenotes the value index of previoustx.’s output;andScriptSigis the signature of transaction creator.Meanwhile,the outputs are theValueandScriptPubkeywhich are the value of this transaction and the receiver’s public key,respectively (Fig.3).

For the general user,two usersAandBcan establish one transaction by the following four steps：

● First,the userAinitiates a transfer request with userB.

● Second,the userBchooses one pair of his unused public and private key,generates a new address and sends it to userAfor transaction implementation.

● Third,the userAestablish a new transaction with above mentioned inputs and outputs,and broadcasts it to the whole blockchain network.

● Last,this transaction will be collected and verified by the miners,and it is finished until the record is confirmed and stored in the BIoT system.

Here,some more important issues should be noted.The reward for the miner’s work of establishing the new block should also be recorded as a general transaction in the blockchain.And once one new block has been established,the compensation deal for the miner will become valid and the reward bitcoin will be consumable for the general transaction.In addition,the more important thing is that the total input amount and output amount of the transaction should be equal.While the total inputs may come from one or more wallet address of the sender.And the sender may need to prepare a new address to receive the surplus inputs if the input amount is more than required.

In the blockchain network,the broadcasted transactions will be verified firstly by the miner.Then,the valid transactions will be packaged into a temporary block.When a miner obtains the right for establishing the new block,the temporary block created by this miner will be attached in the longest chain as the newest block.After this,when another new block has been established,all the transactions in this block have been verified for one time.Then,these transactions will be verified for many times by attaching more and more new blocks at the end of the longest chain,since the blockchain is an append-only chain where the new block is established with the former block.In general,the transactions in this block cannot be tampered after six blocks since that there needs huge computation to rebuild six blocks.Therefore,the blockchain can store the transaction information as an inalterable record and make them more secure in the BIoT system.

6 Efficiency and conclusion

Assume the parameters (n,m,q,k,σ)in this paper are the same as that in the similar literatures,then Tab.1 shows the efficiency comparison results in detail.As comparing with Zhang et al.[Zhang and Ma (2014);Ruckert (2010),the size of public key,private key and signature are all bigger than the proposed scheme.In addition,our scheme can resist the quantum attacks.

Table1:Comparison with similar literatures

In this paper,the proposed lattice-based proxy blind signature can provide high security level for the systems and applications of BIoT.It not only can resist the quantum attacks,but can provide agency transaction and anonymous authentication properties.Then,the security analysis in random oracle model and efficient comparison of the proposed scheme have been given,and the results show that our scheme is secure and more efficient.Moreover,this work also can help to rich the security research of BIoT.

Acknowledgement:Project supported by NSFC (Grant No.U1836205),the Major Scientific and Technological Special Project of Guizhou Province (Grant No.20183001),the Foundation of Guizhou Provincial Key Laboratory of Public Big Data (Grant No.2018BDKFJJ016),and the Foundation of State Key Laboratory of Public Big Data(Grant No.2018BDKFJJ018),CCF-Tencent Open Fund WeBank Special Funding (CCFWebankRAGR20180104).