A Searchable Encryption Scheme Based on Lattice for Log Systems in Blockchain

Gang Xu,Yibo Cao,Shiyuan Xu,Xin Liu,Xiu-Bo Chen,Yiying Yu and Xiaojun Wang

1School of Information Science and Technology,North China University of Technology,Beijing,100144,China

2School of Information Engineering,Inner Mongolia University of Science and Technology,Baotou,014010,China

3Information Security Center,State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing,100876,China

4School of Electronic Engineering,Dublin City University,Dublin,Ireland

Abstract: With the increasing popularity of cloud storage,data security on the cloud has become increasingly visible.Searchable encryption has the ability to realize the privacy protection and security of data in the cloud.However,with the continuous development of quantum computing,the standard Public-key Encryption with Keyword Search (PEKS)scheme cannot resist quantumbased keyword guessing attacks.Further, the credibility of the server also poses a significant threat to the security of the retrieval process.This paper proposes a searchable encryption scheme based on lattice cryptography using blockchain to address the above problems.Firstly, we design a lattice-based encryption primitive to resist quantum keyword guessing attacks.Moreover,blockchain is to decentralize the cloud storage platform’s jurisdiction of data.It also ensures that the traceability of keyword retrieval process and maintains the credibility of search result, which malicious platforms are prevented as much as possible from deliberately sending wrong search results.Last but not least, through security analysis, our proposed scheme satisfies the credibility and unforgeability of the keyword ciphertext.The comprehensive performance evaluates that our scheme has certain advantages in terms of efficiency compared with others.

Keywords: Lattice cryptography; searchable encryption; blockchain; privacy protection;log system;information security;applied cryptography

1 Introduction

With the advancement of the big data period,more and more log files containing private data are being stored by data owners in the cloud,facing significant privacy threats and challenges.Searchable encryption is a technology for searching the log ciphertext based on keyword trapdoors.In this technology, data users can obtain the search trapdoors based on the searching keywords provided to the servicer.Then, the servicer executes a search algorithm to search for the matching ciphertext to correctly retrieve the data required by the user without recovering the plaintext,which significantly protects data privacy.At the beginning of the 21st century,Song et al.[1]put forward the new academic concept of searchable encryption for the first time.They completed the first research plan for the search problem of encrypted data.Further,searchable encryption can be divided into two categories,whether the encryption key and the decryption key are the same.The encryption key and decryption key of symmetric searchable encryption are the same,which cannot guarantee data security.Generally,it is only used when the owner and user of the log file are the same people,and it fails to satisfy most applications.

In 2004, Boneh et al.[2] focused on searching for specific encrypted mailboxes to define the concept of Public-key Encryption with Keyword Search(PEKS)and gave a specific implementation.PEKS has different encryption and decryption keys, which can achieve the effect of sharing data information between data owners and data users so that searchable encryption can be applied to more practical scenarios.Many researchers have since improved and optimised the PEKS scheme to achieve faster search efficiency.Xu et al.[3] proposed Searchable Public Key Ciphertext with Hidden Structure(SPCHS),enabling the fastest possible search of keywords without compromising the encrypted keywords’contextual security.Cui et al.[4] proposed the concept of key aggregation searchable encryption and adopted the Key-Aggregate Searchable Encryption(KASE)scheme.In this scheme,the data owner is only required to issue a public key to the data users who share many files,which is helpful for the effective management of the key and makes this scheme easier to use in practical situations.Song et al.[5]proposed two searchable encryption schemes,FAST and FASTIO,to achieve forward privacy,dramatically improving I/O efficiency and reducing communication overhead.

However, traditional PEKS faces the problem of the untrustworthiness of the servicer, which is fortunately solved to a certain extent by the emergence of blockchain technology.Blockchain,proposed by Nakamoto[6]in 2008,is a distributed public ledger that records all transactions into the block without third-party control and ensures the security and fairness of each transaction.At present,the vigorous development of blockchain technology is favoured by many researchers[7-16].Wang et al.[17] proposed a scheme that uses blockchain technology to store the hash value of users’private data and the attribute set of third-party applications,which realises secure one-to-many transmission of personal data.Xu et al.[18] avoided the intervention of third-party agencies through blockchain technology and established a multi-party security system.However,blockchain can solve the problem of the untrustworthiness of third-party organisations.Based on this idea, Li et al.[19] proposed a searchable encryption scheme (SSE-using-BC)based on blockchain technology, storing encrypted data on a decentralised blockchain.It avoids the intervention of centralised service providers and ensures the privacy of encrypted data.In 2019, Chen et al.[20] proposed a searchable encryption scheme for Electronic Health Records (EHR).Researchers used logical expressions to generate an EHR index and store it in the blockchain to ensure the EHR index’s immutability, integrity, and traceability.In 2020, Nie et al.[21] used searchable encryption to safeguard the privacy of data information and applied the Ethereum blockchain to solve the fairness problem in the search process.Chen et al.[22] designed a new Blockchain-based Searchable Public-key Encryption Scheme with Forward and Backward Privacy (BSPEFB), which largely avoids the adaptive leakage-exploiting attacks of searchable encryption technology in the Vehicle Social Network (VSN)and reflects the practicality of the scheme.

Although the above scheme has improved the problem of the untrustworthiness of the service party in the searchable encryption process, with the rapid development of quantum computing[23], the Shor algorithm realises the rapid decomposition of large prime factors [24].As a result,malicious users with a quantum computer can launch a keyword guessing attack based on quantum computing,causing searchable encryption schemes based on traditional cryptography to lose security and privacy.As a result, more researchers have devoted themselves to proposing a post-quantum method.Nabil et al.[25] proposed that the traditional blockchain scheme is vulnerable to attacks by quantum adversaries.It designed the first post-quantum security signature scheme with public key re-randomisation by providing a deterministic wallet scheme with a post-quantum structure.However,lattice-based cryptography has the highest efficiency and low communication overhead among many post-quantum schemes,and is thus the most promising technology.

In a nutshell,we propose a searchable encryption scheme based on lattice for log systems in the blockchain.Then,we describe our main contributions as follows:

1.Firstly, we propose a searchable encryption scheme based on lattice cryptography to resist keyword guessing attacks under quantum computing.

2.Secondly, blockchain technology is applied to replace the authoritative and trusted party in the scheme to ensure the honesty and credibility of the server.

3.Finally, we conduct a security analysis of our scheme and compare it with other schemes,demonstrating its feasibility and efficiency.

2 Preliminary

Definition 1(Lattice)Suppose thata1,a2,...,am∈Rnaremlinearly independent vectors,then the set of linear combinations is called latticeL,denoted byL=L(A)={x1·a1+x2·a2+···+xm·am|xi∈Z},where the matrixA= {a1,a2,...,am} ∈Rn×mis called a basis ofL,mis called the rank ofL,andnis called the dimension ofL.Whenm=n,Lis called full rank.

Definition 2(Dual Lattice)Suppose thatL(A) is the lattice composed of basesA∈Rn×m, then define the dual lattice as:L*={x∈Rn|〈x,y〉∈Z,?y∈L}.

Definition 3(q-ary Lattice)Setqis a positive integer,given a matrixA∈Zn×mand vectoru∈Znq,we define:

Obviously,Lq(A) andL⊥q (A) are dual lattices of each other, and(A) can be obtained by translation(A).

Definition 4(Discrete Gaussian Distribution)Suppose thatDL,σ,cis a discrete Gaussian distribution defined on latticeLwith a vectorcas the center andσas a parameter,and the specific expression form is:such thatWhenc=0,it records asDL,σ.

Lemma 1(TrapGen)[26]Supposeq≥2,andm≥2nlogq,TrapGen algorithm outputs a matrixA∈which is a statistically approximation to auniform distribution and the basisTA∈Zm×mof(A)satisfying‖TA‖≤O(nlogq)and

Lemma 2(SamplePre)[27]SetTAis the basis of(A),the parametersand the vectoru∈,and then SamplePre algorithm outputs a vectorεthat is statistically close to,satisfyingAε=umodq.

Lemma 3(SampleL)[28] Suppose a positive integerm ＞n,q ＞2, given a latticeL⊥q (A), setTAas the basis ofL⊥q (A), matrixB∈parameters, and vectoru∈Znq, then SampleL algorithm outputs a vectorε, which is statistically close toDL⊥q,s, satisfying(A|B)ε=umodq.

Lemma 4(SampleR)[28] Suppose a positive integerm ＞n,q ＞2, given a lattice), setTBas the basis ofL⊥q (B), matrixA∈,R∈, parametersmax‖x‖=1‖Rx‖and vectoru∈Znq,then SampleR algorithm outputs a vectorεwhich is close tosatisfying(A|AR+B)ε=umodq.In particular,ifR∈{-1,1}m×m,then we obtain

Lemma 5(Gaussian Sampling)[27] Knowing the centrec, parameterσ, and an implicit safety parameterpof a distribution,the algorithm randomly selects an integerx←Z ∩[c-σ·t,c+σ·t]and outputsxwith a certain probability andxis close toDZ,σ,c.

Definition 5(ISIS problem)Suppose it is an integerq,matrixA∈,a real numberβ ＞0 and a vectorv,and there is a non-zero vectorεsatisfyingAε=vmodqand‖ε‖≤β.

3 Design of Our Scheme

3.1 Blockchain Architecture and Transaction Design

The structure of the blockchain and transaction constructed in this paper is shown in Fig.1.The keyword ciphertext attribute and number attribute are added to the transaction.The keyword ciphertext attribute is formed by the data owner encrypting the keyword with the data user’s public key,and the number attribute records the number corresponding to the keyword.Based on this,the smart contract traverses the ciphertext of each keyword according to the search trapdoor uploaded by the data user and returns the number corresponding to the qualified keyword to the cloud storage platform.In this way,data owners and data users can share data.

Figure 1:Blockchain and transaction structure

3.2 Our Scheme Architecture

The architecture of our scheme shows in Fig.2.The roles participating in this scheme include data owner,cloud storage platform,blockchain network,and data user.Their roles in the system are as follows:

(1)Data owner.A data owner is the owner of the log file.He/she divides the log file,generates a number set,and extracts a valid keyword set to store the encrypted log file information in the cloud storage platform.In addition,he/she calculates the keyword ciphertext set corresponding to the log and then uploads the data index to the blockchain.The main problem faced by our scheme is that malicious users perform keyword guessing attacks under quantum computing on the keyword ciphertext,so our scheme focuses on the description of the encryption process of keywords.

(2)Cloud storage platform.Cloud storage platform receives and stores the encrypted log file uploaded by the data owner.After getting the permission of the smart contract, the cloud storage platform returns the specific log file ciphertext to the data user.

Figure 2:Scheme architecture

(3)Blockchain network.By designing the algorithm in the smart contract,it receives the keyword ciphertext uploaded by the data owner and the trapdoor transmitted by the data user.After receiving a query request from a user, the query is performed according to a specific algorithm, and then the query result is returned to the cloud storage platform.The cloud storage platform is notified whether to send the ciphertext of the log file to the data user.

(4)Data user.A data user is responsible for making a query request to the smart contract.Thus,he/she gets the ciphertext of the corresponding logfile from the cloud storage platform and obtains the plaintext of the log file after decryption.

3.3 Related Algorithm Definition

Definition 6The searchable encryption scheme based on lattice includes:

(1)(p,pkown,skown,pkre,skre,$charge,$fund) ←Initialize(λ):We input the security parametersλof the architecture,output parametersp,the key held by the data owner(pkown,skown),the key held by the data user(pkre,skre),the single search price$charge of the blockchain,and the initial deposit value$fund of the data user.

(2)(I,CF) ←Encrypt(F,pkown,skown,pkre): Firstly, the data owner generates a number setNand then takes the effective keywordsWi(1 ≤i≤n) in the log file under each number to generate a keyword setW= {W1,W2,...;,Wn}.Then, the data owner inputs the private keyskownand the public keypkreto encrypt the keyword set to obtain the ciphertextCW.Furthermore,we combineCWandNto get the data indexI,and the data index performs the chain operation.Finally,the log file is encrypted with the data user’s public keypkre,and the ciphertextFis obtained and uploaded to the cloud storage platform.

(3)T←TrapGenerate(pkre,Wi):The algorithm takes the keywordWito be searched as well as the data user’s public keypkreas input.Then,the data user calculates and outputs the corresponding trapdoor T and uploads it to the blockchain network.

(4)NW←Verify(I,T): The algorithm is executed by the smart contract in the blockchain.According to the indexItransmitted to the blockchain and the trapdoorTgenerated by the data user,the smart contract executes theVerifyalgorithm to search for the keyword ciphertext that matches the trapdoorT.If the corresponding ciphertext is found,the numberNWof the ciphertext will be returned to the cloud storage platform.

4 Detailed Description of Our Scheme

4.1 Initialise(λ)

Initialise algorithm includes system initialisation, key initialisation, and blockchain network initialisation.In this algorithm, the system sets a series of parameters required for execution and distributes keys to the main participants of the system.The specific processInitialise(λ) is defined as follows:

(1)System initialisation.A series of system parameters(n,m,q)are specified,where q is a prime number, and the system runs the initialisation program to generate the system parametersp.In this process, the system uses the input parameters to construct Znqand, selects a random vectorvfrom the Znq, and randomly selects two matricesM1andM2from the.Then, it sets the hash functionsrequired by the system and outputsp={n,m,q,v,M1,M2,H1,H2}.

(2)Key initialisation.The system inputs the parameter p, Lemma 1 outputs the matrixMand the basisTof the latticeL(M) and satisfiesandMT= 0modq.Then, the system obtains the public-private key pair(pk,sk): =(M,T).Through the above process, the key(pkown,skown): =(Mown,Town)of the data owner and the key(pkre,skre): =(Mre,Tre)of the data user can be obtained,and then the system will transmit the generated key to the data owner and data user securely and confidentially.

(3)Blockchain network initialisation.The data owner initialises the single search cost$charge on the blockchain network.The data user uses a unique identity ID to register an identity account on the blockchain network and set the deposit$fund of ID.

4.2 Encrypt(F,pkown,skown,pkre)

Encrypt algorithm includes log file encryption and keyword encryption.At this stage,this paper mainly studies the process of keyword encryption.The specific stepsEncrypt(F,pkown,skown,pkre)are as follows:

(1)Preparation stage.The data owner will divide the log fileF,namelyF=(b1,b2,...,bn).After that, each division is numbered to generate a number setN=(1,2,...,n).Fori= 1,2,...,n,each keywordWiare extracted from each divisionbi.Finally, we obtain a keyword setW=(W1,W2,...,Wn).

(2)Log file encryption.The data owner uses the public keypkreof the data used to encrypt each division of the log file and generates the corresponding log file ciphertextCbito form the ciphertext setThen,the data owner uploadsCFto the cloud storage platform.

(3)Keyword encryption.The data owner randomly samples a vectorrand a noise vectoryin Znq.Then,for anyWi∈W,the data owner calculates:whereR∈{-1,1}.It is known that is the hash functionH1set by the system during the initialisation process.Then,the data owner randomly chooses a bitω∈{0,1}and calculates the corresponding hash valueAccording to Lemma 2,the data owner can obtain a vectorε,which satisfiesMownε=modq.In addition,the data owner calculates a parameter·ωfor each keyword ciphertext.The ciphertext corresponding to,and each division in the ciphertext corresponds to the number set to generate a ciphertext index

(4)Keyword ciphertext uploading.The data owner uses the private key to generate a digital signature for the hash valueof each keyword ciphertext, generates the corresponding transaction,and submits the transaction to the master node.Then all nodes in the blockchain execute the consensus algorithm.The master node packs the transaction in a period together to form a block and then sends it to the slave node,which receives the block delivery by the master node and verifies the transaction in it.The verification process is as follows:the slave node extractspkownstored in the transaction from the node to decrypt and obtain the hash valueof the keyword ciphertext.Ifthe slave node announces that the verification is successful.Otherwise,the data may have been tampered with,and the slave node returns this transaction to the data owner.Assuming that the maximum number of malicious nodes that can exist in the consensus algorithm isf,if the number of verifications isNT ＞f+1,each node on the blockchain will store the block.

4.3 TrapGenerate(pkre,Wi)

The data user inputs their public keypkreand keywordWiintoTrapGenerate(pkre,Wi).According to Lemma 3,the algorithm generates a vectorTsatisfying(Mre|M1+M2·Wi)T=vmodq.Then,Twill be outputted as a trapdoor and sent to the consensus node on the blockchain.

4.4 Verify(I,T)

Before runningVerify(I,T), the smart contract will compare the value of the deposit$fund of data user ID and the single search cost $charge.If $fund＜$charge, It returnsto the data user that the cost is insufficient.If $fund ≥$charge, the smart contract automatically executesVerifyto search for the keyword ciphertext and its number that match the user trapdoor in the data index set.Verifytakes data indexand trapdoorTas input.First,the algorithm enumerates the keyword ciphertextCWi (1 ≤i≤n)inI.For each ciphertext,calculate:then it can be concludedω= 1, otherwiseω= 0.Then the algorithm calculates the hash value, if it existsj∈[1,n] and satisfiesMreεj=modq,cWj′is the target keyword ciphertext corresponding to the trapdoorT.Finally,the numberNW=jof the keyword ciphertext is returned by the algorithm to the cloud storage platform.

The cloud storage platform finds the ciphertext of the corresponding log file according to the index value and transmits it to the data user.To obtain the plaintext of the log file,the data user decrypts the ciphertext.

Proof:For the method of restoring the value during the search and verification process,we give the proof as follow:

5 Security Analysis

5.1 Credibility

This solution is based on the blockchain network,which can ensure the honesty and credibility of search results and primarily resist malicious attacks by illegal users on the server.The keyword search process does not involve any third parties in the decentralised blockchain network, and the nodes conduct open and transparent interactions based on transactions.All transactions and operations are recorded on the block.The characteristics of traceability and non-tampering can ensure the fairness and credibility of each search operation.In addition, each transaction initiated in the blockchain network requires the payment of a particular cost, which effectively avoids the possibility of illegal users undermining the program’s regular operation through malicious and exhaustive means.

5.2 Unforgeability of Keyword Ciphertext

In this scheme, the keyword ciphertext of the log file is unforgeable, its security can be reduced to ISIS hardness,and it effectively resists keyword guessing attacks initiated by illegal users equipped with quantum computers,thereby ensuring privacy of the plaintext.

Theorem 1For any adversary A in polynomial time, the difficulty of forging the ciphertext of a keyword is equal to the difficulty of solving the difficult problem of ISIS currently.

Proof:Assuming that adversary A cracks the unforgeability of the ciphertext with a non-negligible probability,it is equivalent to constructing a challenger C capable of solving ISIS problems.

(1)Initialisation.Suppose adversary A initiates a keyword guessing attack on the system by forging the keyword ciphertext.In that case,challenger C executes the Setup algorithm to generate a series of parameters required by the system and sends the parameterspto adversary A.Then, C initiates an inquiry to the random prophecy and obtains the parametersMown*, which will be used as the public key of the data owner.Finally,C randomly selects a matrix∈as the data user’s public key and simultaneously dispatches two public keys to A.

(2)Inquiry phase 1.For any ciphertextCWiwith differentω∈ {0,1} keywords, ifCWi=andw=w*, the challenger C calculatesH1(cW,ω) and returns it to adversary A, and addsto the list.Otherwise,C randomly obtainsεwhich obeys(Mown*),σaccording to Lemma 5,then calculatesH1(cW,ω)=Mown*εmodqand adds(CW,ω,H1(cW,ω))to the list.

(3)Inquiry phase 2.For the keywordWi(1 ≤i≤n) that adversary A initiates an inquiry,challenger C calculatesand generates the first partcWiof the ciphertext.After obtainingεwhich obeysaccording to Lemma 5, challenger C will sendto adversary A.

(4)Forgery phase.In this phase, adversary A will forge a ciphertextrelated to the keywordWi*(1 ≤i≤n).To begin with, A gets a trapdoorT*through Lemma 2 and sends it to challenger C.Then C calculates,thenω*=1,otherwiseω*=0,and returns a second partε*of the ciphertext of the key set forged by A.In this process,C cannot obtain information related to this ciphertext by asking a random oracle.Therefore,the keyword ciphertextis forged by A,which is a solution to ISIS hardness.

Analysis:Assuming thatε*is a part of the effective keyword ciphertextCWi, and satisfyingmodq.If adversary A forges the keyword ciphertextwith probabilityp, it notices thatNis the number of times which the Inquiry phase 1 is executed in polynomial time.So, we obtain the probability that C successfully obtains the satisfying conditionis at least.Therefore,in the current situation,Challenger C has at least the advantageto break the assumption of ISIS hardness.In summary, the difficulty of adversary A forging the correct keyword ciphertext can be reduced to the difficulty of solving the ISIS hardness.

6 Comprehensive Evaluation Analysis

Our paper proposes a searchable encryption scheme based on lattice for log systems combined with blockchain.The test environment is a 64-bit Windows system with 16GB of memory.And the experimental process is completed by the local virtual machine Ubuntu 16.04.6.As shown in Tab.1,we compare the scheme in this paper with the schemes[30,31]in terms of methodology and hardness assumptions.

Table 1: Comparison of methodologies and hardness assumption

Through comparison,the common point between the literature[30]and our scheme is that they both use searchable encryption to ensure the fairness and credibility of the system environment.However, our scheme still provides the security of keyword ciphertexts facing quantum computing attacks.Consequently,the privacy of log files is well protected.

After that, in order to compare the differences between the literature [31] and our proposed scheme in the trapdoor cost, verify algorithm cost, ciphertext size, and trapdoor size, Tab.2 defines the acronyms used in the experimental process,and Tab.3 shows the performance comparison results.

Table 2: Glossary

Table 3: Performance comparison

Since our scheme uses the trapdoor generation algorithm based on lattice theory and mainly relies on the addition and multiplication of vectors, the overall efficiency of our scheme is superior to traditional cryptography.

Fig.3 shows the changing trend of the keyword search time under not introducing the blockchain and introducing the blockchain.Since the search operation in the blockchain requires more cost for on-chain transactions,the keyword search time is increased,but the credibility and traceability of the search results can be guaranteed.However,with the linear growth in the number of keywords,the time spent in the blockchain transaction will become insignificant compared to the time used to search for keywords,so the time is less and less affected by the blockchain transaction time.

Figure 3:Comparison of schemes

7 Conclusion

To solve the keyword guessing attacks launched by quantum attackers and the untrustworthiness of service providers,this paper designs and proposes a searchable encryption scheme based on lattice for log systems in the blockchain.The application of a lattice-based encryption algorithm makes the scheme resist quantum computing and ensures the security of the keyword ciphertext.At the same time, blockchain technology is employed to separate the keyword ciphertext search from the log file storage.Due to the keyword search is performed by designing a smart contract that ensures the reliability of the search results when the credibility of the servicer is unknown.According to the security analysis and experimental simulation, our scheme is secure in quantum attacks while being highly efficient.In the future,we will introduce forward security and optimize computational cost.

Funding Statement:This work was supported by the Open Fund of Advanced Cryptography and System Security Key Laboratory of Sichuan Province(Grant No.SKLACSS-202101),NSFC(Grant Nos.62176273, 61962009, U1936216), the Foundation of Guizhou Provincial Key Laboratory of Public Big Data (No.2019BDKFJJ010, 2019BDKFJJ014), the Fundamental Research Funds for Beijing Municipal Commission of Education, Beijing Urban Governance Research Base of North China University of Technology,the Natural Science Foundation of Inner Mongolia(2021MS06006),Baotou Kundulun District Science and technology plan project (YF2020013), and Inner Mongolia discipline inspection and supervision big data laboratory open project fund(IMDBD2020020).

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.