# Post-Quantum Privacy-Preserving Provable Data Possession Scheme Based on Smart Contracts

Authors: Zhengwen Li; Tengjiao Zhang; De Zhao; Yaxing Zha; Jun Sun
Journal: Wireless Communications and Mobile Computing
 (2023)

---

## Abstract

Provable data possession (PDP) is a crucial means of protecting the integrity of data in the domain of cloud storage. In the post-quantum era, the PDP scheme that uses lattices relies too heavily on the third-party auditor (TPA), which is not entirely trustworthy and is easily affected by a single point of failure. Moreover, the scheme often leads to the leakage of private user data while attempting to satisfy the demand for public verification. In response to the above problems, this paper designs a protocol for post-quantum privacy-preserving PDP and uses it to develop a scheme based on smart contracts. The proposed scheme has the characteristics of being post quantum and can satisfy the demand for public verification while preserving user privacy. The property of noninteraction of the protocol can reduce transaction fees incurred owing to the frequent operation of the blockchain, and the smart contract with a deposit mechanism can ensure fair payments to all parties. The results of a theoretical analysis and experiments show that the proposed scheme is highly secure and efficient.


---

## Body

## 1. Introduction

Cloud storage has emerged as the crucial infrastructure for data storage with the rapid development of cloud computing, big data, the Internet of Things, the mobile Internet, and artificial intelligence in recent years. It can deliver services on demand with just-in-time capacity and costs and eliminates the need for users to buy and manage their own infrastructure for data storage. This provides users with agile, global, and durable—“anytime, anywhere”—access to data [1].While cloud storage is widely used, it poses new security threats to cloud data because users lose physical control over their data [2]. An untrusted cloud storage provider (CSP) may reclaim storage space for economic reasons by deleting infrequently accessed data or even concealing events of data loss to avoid damage to its reputation. In addition, server failures, power outages, and security attacks occasionally occur to seriously compromise the integrity and availability of data in the cloud. Owing to various security-related incidents, such as the service downtime of cloud storage and the leakage of private data [3, 4], the integrity of data in cloud storage is a cause for concern for users and has greatly restricted the development of this technology.Researchers have proposed efficient schemes of verification to protect the integrity of data in cloud storage. Data integrity can be verified by computing a small number of data blocks without downloading all the data in the cloud to the local server. Provable data possession (PDP) is the most common scheme to verify the integrity of data. The user in this scheme divides the uploaded data into blocks of equal size and then calculates the tag of each block. The data blocks and the tags are then sent to the CSP. When data integrity needs to be verified, the user randomly selects a few data blocks, asks the CSP to calculate a short proof based on their tags, and then verifies the proof returned by it to determine whether it stores all of the user’s data. Ateniese et al. [5] proposed a PDP scheme that uses RSA-based homomorphic verifiable tags to aggregate signatures, thus reducing the burden of computation and I/O access to significantly improve the efficiency of verification. Wang et al. [6] used the BLS [7] to design a scheme to verify data integrity. They constructed a Merkle hash tree (MHT) that supports dynamic data operations, where the security of the system depends on the computational Diffie–Hellman (CDH) problem. Curtmola et al. [8] extended PDP to the case of replicas and proposed multiple-replica provable data possession (MR-PDP) that can reduce the overhead of all replicas due to verification to roughly the same as that of a single replica.It is essential for users with limited computing resources and capabilities to provide public verification. They can designate external auditors to check the integrity of data in cloud storage when needed. A variant of PDP has been proposed [5] to support public verification. It allows anyone (not just the data owner) to challenge and check the data ownership of the CSP. Wang et al. [9] introduced a third-party auditor (TPA), instead of users, that regularly verifies the integrity of remote data without storing all data. Once verification fails, it can immediately notify the user that the data are damaged and take timely measures to avoid more significant losses. On the contrary, the results of an audit submitted by the TPA ensure some objectivity and fairness, where this is conducive to the accountability of users after disputes with the CSP. Therefore, most subsequent PDP schemes [10–15] tend to include a TPA.However, we cannot base data security on the assumption of a fully trustworthy TPA. A malicious TPA may corrupt and leak user data or deceive users with fake audits. Some researchers have used the blockchain instead of the TPA in the PDP scheme. Because the blockchain is open, transparent, and tamper resistant, it provides users with a completely trusted third-party audit, and users can supervise the entire process. Zhang et al. [16] proposed a blockchain-based fair payment framework for outsourcing services in cloud computing and used it to build a blockchain-based PDP scheme. Chen et al. [17] proposed a decentralized blockchain-based PDP scheme that uses a rank-based MHT to support the dynamic operation of outsourced data, uses the blockchain to record all transaction behaviors, and deploys smart contracts combined with the deposit mechanism to ensure the automatic execution of the protocol and fair payments. Chen et al. [18] proposed the first decentralized system for proofs of data retrievability and replication—BOSSA, which is incentive-compatible for each party and realizes automated auditing by using smart contracts on the Ethereum blockchain. Wang et al. [19] proposed the concept of noninteractive public provable data possession and used it to design a blockchain-based smart contract for the public auditing of cloud storage. This scheme is based on bilinear pairing, and its security relies on the CDH problem and the discrete logarithm problem.Since public verification allows people other than users to verify data integrity, it is necessary to ensure that the audit process preserves user privacy such that the auditors cannot obtain any original user data based on the information collected. Encrypting data before uploading them is one way to protect user privacy but can be used only as a supplement and does not by itself prevent data from “flowing” out if appropriate protocols are not designed. Wang et al. [9] used random masking technology to solve the problem of privacy leakage. Two random parameters are introduced to the process of proof generation to prevent the adversary from obtaining private data by solving linear equations based on the content of the message. References [20–22] used the same idea to protect user privacy. Tong et al. [23] used private information retrieval and the tag repacking technique to enable the TPA to check the integrity of data without violating the privacy of the user data and the query pattern.With the development of quantum computing [24] in recent years, the hard problems of traditional cryptography, such as integer factorization and the discrete logarithm, can be solved by quantum computers in polynomial time. The security of all information systems designed based on these problems is thus seriously affected, and a PDP scheme is needed to resist attacks based on quantum computing. Lattice cryptography has the advantages of a strong proof of security with worst-case hardness, simple construction, and easy implementation [25]. It has a high speed of calculation and low communication overhead and can be used to construct various cryptographic algorithms and applications. It is thus considered the most efficient and promising method of post-quantum cryptography. Zhang and Xu [26] proposed a post-quantum secure cloud storage system that supports privacy preservation and public auditing. Its security is based on the hardness of inhomogeneous small integer solution (ISIS) on lattices. The lattice signatures generated by a function with preimage sampling are used for random masking to ensure that the TPA cannot acquire knowledge about the data. Yang et al. [27] proposed an identity-based model to audit the integrity of data that does not rely on a public key infrastructure, and its security is based on ring learning with errors (RLWE). Tan et al. [28] proposed a provable data integrity scheme based on lattices in cloud storage that uses the homomorphic signature technique on lattices [29] and supports dynamic data operation and batch verification. Based on the work in [28], Tan et al. [30] used random masking technology to achieve privacy preservation such that the TPA cannot obtain the original data.In the context of the post-quantum era, the PDP scheme based on lattice cryptography relies too heavily on the TPA, which is not entirely trustworthy and is easily affected by a single point of failure. Moreover, this scheme often leads to the leakage of private user data in the quest to satisfy the demand for public verification. In response to these problems, this paper designs a post-quantum privacy-preserving PDP protocol and uses it to propose a privacy-preserving scheme based on smart contracts. The proposed scheme is post quantum and can be used for public verification while ensuring the preservation of private user data. The characteristic of noninteraction of the protocol can reduce transaction fees incurred by the frequent operation of the blockchain, and the smart contract with a deposit mechanism can ensure fair payments to all parties.The main contributions of this research can be summarized as follows:(1)
We design a post-quantum privacy-preserving PDP protocol. It uses linearly homomorphic signatures on lattices to calculate the signatures of different data blocks and generate a short proof. Data possession can be verified through this proof. The security of the scheme depends on the hardness of the inhomogeneous small integer solution on the lattices, thereby ensuring resistance against quantum computing-based attacks. The protocol also uses random masking technology to add random variables to the generated proof so that the verifier cannot obtain the user’s data by solving a linear system of equations composed of multiple pieces of proof, thereby preserving user privacy(2)
We propose a post-quantum privacy-preserving PDP scheme based on smart contracts. The audit process is open and transparent and is regularly and automatically verified by deploying smart contracts on the blockchain. The smart contract stipulates the rights and obligations of all parties involved. Once the conditions have been triggered, the contract is automatically executed to ensure fair payments to all parties, and this reduces the cost of handling disputes. In addition, the cost of transactions decreases significantly because the participants do not need to interact in the “challenge–response” phase owing to frequent interactions on the blockchain, and this increases the verifier’s enthusiasm for executing smart contracts(3)
We analyze the correctness and capability of privacy preservation of the proposed scheme and prove that it is secure under the random oracle model through interactive analysis of the construction of a series of games. Finally, the practicability and efficiency of the proposed scheme are verified through comparative experiments with prevalent methods in the areaThe rest of the paper is organized as follows. Section2 recalls some preliminaries used in our scheme. Section 3 defines the model of our scheme, gives the formal definition, and presents the concrete construction. Section 4 provides the security proof of the protocol. Section 5 evaluates the performance of our scheme. Finally, we give a conclusion in Section 6.


## 2. Preliminary

### 2.1. Provable Data Possession

To reduce storage overhead, users store their original data in the cloud instead of doing so locally. Therefore, the CSP is needed to prove the possession of data to periodically ensure their integrity. The TPA is introduced to the PDP scheme to verify the integrity of the data on behalf of the users to reduce the overheads incurred by them due to computation and communication. During the verification process, the CSP needs to respond to the challenge initiated by the TPA and generate a proof for it. The result of verification is returned to the user.According to the basic definition of PDP, a general system model of it is shown in Figure1. The participating entities include the users, CSP, and TPA.Figure 1
General system model of PDP.The PDP scheme consists of five algorithms: key generation, tag generation, challenge generation, proof generation, and proof verification. The description of each follows.(1)
KeyGen1λ⟶pk,sk: the key generation algorithm is run by the user. The input to it is the system security parameter λ and the output is a public–private key pair pk,sk(2)
TagGenpk.sk,mi⟶Ti: the tag generation algorithm is run by the user. The inputs are the public–private key pair pk,sk and the data block mi, and the output is the signature Ti of mi. The user sends mi,Ti to the CSP(3)
GenChallengeIdm,τ,Q⟶chal: the challenge generation algorithm is run by the TPA. The inputs to it are the identification information Idm, a random number τ∈ℤq∗, and a challenge set Q, and the output is the challenge chal(4)
GenProofmi,Ti,chal⟶ρ: the proof generation algorithm is run by the CSP. The input to it consists of the data block mi, the signature Ti, and the challenge chal, and the output is the proof ρ. The CSP obtains the proofs μ and σ by using homomorphic aggregation technology to process mi and Ti, respectively, and the CSP returns the result of aggregation ρ=μ,σ to the TPA(5)
ProofCheckρ⟶"true","false": the proof verification algorithm is run by the TPA. The input to it is the proof ρ=μ,σ. If the proof is verified, the output is true; otherwise, the output is falseThe above algorithms constitute the general PDP scheme. To satisfy the requirements of different application scenarios, researchers have improved and supplemented this scheme.


### 2.2. Lattice-Based Homomorphic Signature

Notation 1.
For any integerq≥2, we let ℤq denote the ring of integer modulo q. If q is a prime number, ℤq is a field and is denoted by Fq. We let ℤqm×n denote the set of m×n matrices with entries ℤq. We use standard big-O notation to classify the growth of functions and say that iffn=Ogn⋅logcn, we letpolyndenote an unspecified functionfn=Oncfor some constantc. A negligible function, denoted generically by negln, is an fn such that fn=on−c for every fixed constant c. We say that a probability is overwhelming if it is 1−negln. The base 2 logarithm is denoted logx.Definition 2.
Lattice: ann-dimensional lattice of rank k≤n is
(1)Λ=LB=Bc:c∈Zk,B∈ℝn×k,where the k columns b1,⋯,bk∈ℝn of the basis B are linearly fn=O~gn independent. B denotes the length of the longest vector in B, i.e., max1≤i≤kbi, and B~=b~1,⋯,b~k denotes the Gram–Schmidt orthogonalization of the vectors b1,⋯,bk.For any integerq≥2 and any A∈ℤqm×n, we define
(2)Λq⊥A≔e∈ℤn:A⋅e=0modq,ΛquA≔e∈ℤn:A⋅e=umodq.The latticeΛquA is a coset of Λq⊥A, namely, ΛquA=Λq⊥A+t for any t such thatA⋅t=umodq.Lemma 3 ([31] Lemma 7.1).
LetΛ be an m-dimensional lattice. There is a deterministic polynomial-time algorithm that, given an arbitrary basis of Λ and a full-rank set S=s1,⋯,sm in Λ, returns a basis T of Λ satisfying
(3)T~≤S~,T≤S⋅m2.Theorem 4 ([32] Theorem 3.2).
Letq,m,n be positive integers with q≥2 and m≥6nlogq. There is a probabilistic polynomial-time algorithm TrapGenq,n,m that outputs A∈ℤqn×m,S∈ℤm×m such that A is statistically close to a uniform in ℤqn×m and S is a basis for Λq⊥A that satisfies
(4)S~≤On⋅logq,S≤On⋅logq,with all but negligible probability in n.Definition 5.
Gaussian distributions: letL be a subset of ℤn. For any vector c∈ℝn and any positive σ∈ℝ+, let ρσ,cx≔exp−πx−c2/σ2 be a Gaussian function on ℝn with center c and parameter σ. Let ρσ,cL≔∑x∈Lρσ,cx be the discrete integral of ρσ,c over L, and let DL,σ,c be the discrete Gaussian distribution over L with center c and parameter σ. For all y∈L, DL,σ,cy=ρσ,cy/ρσ,cL. For notational convenience, ρσ,0 and DL,σ,0 are abbreviated as ρσ and DL,σ, respectively.Gentry et al. [33] constructed algorithms to sample from discrete Gaussian distributions.Theorem 6.
(a)
There is a probabilistic polynomial-time algorithm SampleGaussian that, given a basisT of an n-dimensional lattice Λ, a parameter σ≥T~⋅ωlogn, and a center c∈ℝn, outputs a sample from a distribution that is statistically close to DΛ,σ,c(b)
There is a probabilistic polynomial-time algorithm SamplePre that, given a basisT of an n-dimensional lattice Λ, a parameter σ≥T~⋅ωlogn, and a vector t∈ℝn, outputs a sample from a distribution that is statistically close to DΛ+t,σDefinition 7 ([34] Definition 3.1).
Smoothing parameter: for ann-dimensional lattice Λ and positive real ε>0, the smoothing parameter ηεΛ of Λ is defined to be the smallest positive s such that ρ1/sΛ∗\0≤ε, where Λ∗ is the dual lattice of Λ.The critical property of the smoothing parameter is that ifσ>ηεΛ, then every coset of Λ has roughly equal mass under the distribution DΛ,σ,c.Lemma 8 ([34] Lemma 4.4).
LetΛ be an n-dimensional lattice. Let T be a basis for Λ, and suppose σ≥T~⋅ωlogn. Then, for any c∈ℝn, we have
(5)Prx−c>σn:x⟵RDΛ,σ,c≤negln.
LetΛ1 and Λ2 be two lattices in ℤn such that Λ1+Λ2=ℤn. We show that a discrete Gaussian sampling from Λ1 is close to uniform in ℤn/Λ2 by the following lemma.Lemma 9 ([29] Lemma 3.9).
LetΛ1 and Λ2 be n-dimensional lattice such that Λ1+Λ2=ℤn. For any ε∈0,1/2 and σ≥ηεΛ1∩Λ2 and any c∈ℝn, the distribution DΛ1,σ,cmodΛ2 is within statistical distance at most 2ε of the uniform distribution over Λ1+Λ2/Λ2.Definition 10.
The inhomogeneous small integer solution (ISIS) problem is as follows: givenq∈ℤ,β∈ℝ,A∈ℤqn×m,u∈ℤqn, find a nonzero vector v∈ℤm such that Av=umodq and v≤β.Lemma 11 ([33] Proposition 5.7).
For any poly-boundedm,β=polyn and any prime q≥β⋅ωn⋅logn, the average-case problem ISIS is as hard as that of approximating the SIVP problem in the worst case.


### 2.3. Blockchain and Smart Contracts

The blockchain is managed by a peer-to-peer network for maintaining a secure and decentralized distributed ledger of transactions, where nodes collectively adhere to a protocol to communicate and validate new blocks. It is best known for its vital role in cryptocurrency systems such as Bitcoin [35]. The innovation of the blockchain guarantees the fidelity and security of data records and generates trust without the need for a trusted third party.The difference between the blockchain and other databases lies mainly in how the data are composed. The data are stored in blocks, which are generated in chronological order and connected to a chain. This data structure forms an immutable data timeline, with each block in the chain being added with a precise timestamp. As shown in Figure2, each block contains a block header and a block body. The block header contains the hash value of the previous block, a version number, a random value, a timestamp, a Merkle root hash, and a difficulty value. The block body contains all transactions generated during block creation. Each block in the blockchain is identified by a hash value obtained by twice executing the SHA256 algorithm of the block header. Each block can find its previous block by using the hash value contained in its block header. Any changes to the data in the block lead to a series of changes in subsequent blocks, and distributed nodes run a consensus protocol to synchronously update the hash chain. Therefore, the blockchain has the characteristics of decentralization, transparency, openness, immutability, and traceability.Figure 2
Structure of the blockchain.The smart contract [36] is a piece of code in the blockchain in which the logic of the code defines the contents of the contract. Smart contracts operate under a set of conditions agreed upon by all parties involved; when these conditions are triggered, the contents of the contract are automatically executed. Say that a tenant wants to use a smart contract to lease an apartment from a landlord. First, the tenant and the landlord negotiate details of the contract, such as the duration of the lease, rent, deposit, and the terms of compensation. They then write the content as agreed by both parties into the smart contract and deploy it on the blockchain. The contract takes effect within the specified time. It is automatically executed according to its contents such that this reduces the costs of notarization, mediation, and litigation in case disputes arise.We can say that the blockchain provides a trusted execution environment for smart contracts, which in turn extends the application of the blockchain. Smart contracts have been used in many fields, such as electronic voting [37] and insurance [38], and have excellent prospects for further use.


## 2.1. Provable Data Possession

To reduce storage overhead, users store their original data in the cloud instead of doing so locally. Therefore, the CSP is needed to prove the possession of data to periodically ensure their integrity. The TPA is introduced to the PDP scheme to verify the integrity of the data on behalf of the users to reduce the overheads incurred by them due to computation and communication. During the verification process, the CSP needs to respond to the challenge initiated by the TPA and generate a proof for it. The result of verification is returned to the user.According to the basic definition of PDP, a general system model of it is shown in Figure1. The participating entities include the users, CSP, and TPA.Figure 1
General system model of PDP.The PDP scheme consists of five algorithms: key generation, tag generation, challenge generation, proof generation, and proof verification. The description of each follows.(1)
KeyGen1λ⟶pk,sk: the key generation algorithm is run by the user. The input to it is the system security parameter λ and the output is a public–private key pair pk,sk(2)
TagGenpk.sk,mi⟶Ti: the tag generation algorithm is run by the user. The inputs are the public–private key pair pk,sk and the data block mi, and the output is the signature Ti of mi. The user sends mi,Ti to the CSP(3)
GenChallengeIdm,τ,Q⟶chal: the challenge generation algorithm is run by the TPA. The inputs to it are the identification information Idm, a random number τ∈ℤq∗, and a challenge set Q, and the output is the challenge chal(4)
GenProofmi,Ti,chal⟶ρ: the proof generation algorithm is run by the CSP. The input to it consists of the data block mi, the signature Ti, and the challenge chal, and the output is the proof ρ. The CSP obtains the proofs μ and σ by using homomorphic aggregation technology to process mi and Ti, respectively, and the CSP returns the result of aggregation ρ=μ,σ to the TPA(5)
ProofCheckρ⟶"true","false": the proof verification algorithm is run by the TPA. The input to it is the proof ρ=μ,σ. If the proof is verified, the output is true; otherwise, the output is falseThe above algorithms constitute the general PDP scheme. To satisfy the requirements of different application scenarios, researchers have improved and supplemented this scheme.


## 2.2. Lattice-Based Homomorphic Signature

Notation 1.
For any integerq≥2, we let ℤq denote the ring of integer modulo q. If q is a prime number, ℤq is a field and is denoted by Fq. We let ℤqm×n denote the set of m×n matrices with entries ℤq. We use standard big-O notation to classify the growth of functions and say that iffn=Ogn⋅logcn, we letpolyndenote an unspecified functionfn=Oncfor some constantc. A negligible function, denoted generically by negln, is an fn such that fn=on−c for every fixed constant c. We say that a probability is overwhelming if it is 1−negln. The base 2 logarithm is denoted logx.Definition 2.
Lattice: ann-dimensional lattice of rank k≤n is
(1)Λ=LB=Bc:c∈Zk,B∈ℝn×k,where the k columns b1,⋯,bk∈ℝn of the basis B are linearly fn=O~gn independent. B denotes the length of the longest vector in B, i.e., max1≤i≤kbi, and B~=b~1,⋯,b~k denotes the Gram–Schmidt orthogonalization of the vectors b1,⋯,bk.For any integerq≥2 and any A∈ℤqm×n, we define
(2)Λq⊥A≔e∈ℤn:A⋅e=0modq,ΛquA≔e∈ℤn:A⋅e=umodq.The latticeΛquA is a coset of Λq⊥A, namely, ΛquA=Λq⊥A+t for any t such thatA⋅t=umodq.Lemma 3 ([31] Lemma 7.1).
LetΛ be an m-dimensional lattice. There is a deterministic polynomial-time algorithm that, given an arbitrary basis of Λ and a full-rank set S=s1,⋯,sm in Λ, returns a basis T of Λ satisfying
(3)T~≤S~,T≤S⋅m2.Theorem 4 ([32] Theorem 3.2).
Letq,m,n be positive integers with q≥2 and m≥6nlogq. There is a probabilistic polynomial-time algorithm TrapGenq,n,m that outputs A∈ℤqn×m,S∈ℤm×m such that A is statistically close to a uniform in ℤqn×m and S is a basis for Λq⊥A that satisfies
(4)S~≤On⋅logq,S≤On⋅logq,with all but negligible probability in n.Definition 5.
Gaussian distributions: letL be a subset of ℤn. For any vector c∈ℝn and any positive σ∈ℝ+, let ρσ,cx≔exp−πx−c2/σ2 be a Gaussian function on ℝn with center c and parameter σ. Let ρσ,cL≔∑x∈Lρσ,cx be the discrete integral of ρσ,c over L, and let DL,σ,c be the discrete Gaussian distribution over L with center c and parameter σ. For all y∈L, DL,σ,cy=ρσ,cy/ρσ,cL. For notational convenience, ρσ,0 and DL,σ,0 are abbreviated as ρσ and DL,σ, respectively.Gentry et al. [33] constructed algorithms to sample from discrete Gaussian distributions.Theorem 6.
(a)
There is a probabilistic polynomial-time algorithm SampleGaussian that, given a basisT of an n-dimensional lattice Λ, a parameter σ≥T~⋅ωlogn, and a center c∈ℝn, outputs a sample from a distribution that is statistically close to DΛ,σ,c(b)
There is a probabilistic polynomial-time algorithm SamplePre that, given a basisT of an n-dimensional lattice Λ, a parameter σ≥T~⋅ωlogn, and a vector t∈ℝn, outputs a sample from a distribution that is statistically close to DΛ+t,σDefinition 7 ([34] Definition 3.1).
Smoothing parameter: for ann-dimensional lattice Λ and positive real ε>0, the smoothing parameter ηεΛ of Λ is defined to be the smallest positive s such that ρ1/sΛ∗\0≤ε, where Λ∗ is the dual lattice of Λ.The critical property of the smoothing parameter is that ifσ>ηεΛ, then every coset of Λ has roughly equal mass under the distribution DΛ,σ,c.Lemma 8 ([34] Lemma 4.4).
LetΛ be an n-dimensional lattice. Let T be a basis for Λ, and suppose σ≥T~⋅ωlogn. Then, for any c∈ℝn, we have
(5)Prx−c>σn:x⟵RDΛ,σ,c≤negln.
LetΛ1 and Λ2 be two lattices in ℤn such that Λ1+Λ2=ℤn. We show that a discrete Gaussian sampling from Λ1 is close to uniform in ℤn/Λ2 by the following lemma.Lemma 9 ([29] Lemma 3.9).
LetΛ1 and Λ2 be n-dimensional lattice such that Λ1+Λ2=ℤn. For any ε∈0,1/2 and σ≥ηεΛ1∩Λ2 and any c∈ℝn, the distribution DΛ1,σ,cmodΛ2 is within statistical distance at most 2ε of the uniform distribution over Λ1+Λ2/Λ2.Definition 10.
The inhomogeneous small integer solution (ISIS) problem is as follows: givenq∈ℤ,β∈ℝ,A∈ℤqn×m,u∈ℤqn, find a nonzero vector v∈ℤm such that Av=umodq and v≤β.Lemma 11 ([33] Proposition 5.7).
For any poly-boundedm,β=polyn and any prime q≥β⋅ωn⋅logn, the average-case problem ISIS is as hard as that of approximating the SIVP problem in the worst case.


## 2.3. Blockchain and Smart Contracts

The blockchain is managed by a peer-to-peer network for maintaining a secure and decentralized distributed ledger of transactions, where nodes collectively adhere to a protocol to communicate and validate new blocks. It is best known for its vital role in cryptocurrency systems such as Bitcoin [35]. The innovation of the blockchain guarantees the fidelity and security of data records and generates trust without the need for a trusted third party.The difference between the blockchain and other databases lies mainly in how the data are composed. The data are stored in blocks, which are generated in chronological order and connected to a chain. This data structure forms an immutable data timeline, with each block in the chain being added with a precise timestamp. As shown in Figure2, each block contains a block header and a block body. The block header contains the hash value of the previous block, a version number, a random value, a timestamp, a Merkle root hash, and a difficulty value. The block body contains all transactions generated during block creation. Each block in the blockchain is identified by a hash value obtained by twice executing the SHA256 algorithm of the block header. Each block can find its previous block by using the hash value contained in its block header. Any changes to the data in the block lead to a series of changes in subsequent blocks, and distributed nodes run a consensus protocol to synchronously update the hash chain. Therefore, the blockchain has the characteristics of decentralization, transparency, openness, immutability, and traceability.Figure 2
Structure of the blockchain.The smart contract [36] is a piece of code in the blockchain in which the logic of the code defines the contents of the contract. Smart contracts operate under a set of conditions agreed upon by all parties involved; when these conditions are triggered, the contents of the contract are automatically executed. Say that a tenant wants to use a smart contract to lease an apartment from a landlord. First, the tenant and the landlord negotiate details of the contract, such as the duration of the lease, rent, deposit, and the terms of compensation. They then write the content as agreed by both parties into the smart contract and deploy it on the blockchain. The contract takes effect within the specified time. It is automatically executed according to its contents such that this reduces the costs of notarization, mediation, and litigation in case disputes arise.We can say that the blockchain provides a trusted execution environment for smart contracts, which in turn extends the application of the blockchain. Smart contracts have been used in many fields, such as electronic voting [37] and insurance [38], and have excellent prospects for further use.


## 3. Our Scheme

### 3.1. System Model

The system model of a post-quantum privacy-preserving provable data possession scheme based on smart contracts contains three entities: the data owner, the cloud storage provider, and the verifier (see Figure3).
(1)
Data owner (DO): to save the cost of local storage and use data conveniently and flexibly, cloud storage users pay a certain fee and store their data on a remote server owned by the cloud storage provider(2)
Cloud storage provider (CSP): it provides computing, storage, and network bandwidth for the DO. The CSP needs to periodically perform PDP to prove that it maintains the integrity of data. If verification fails, it pays the DO a certain fee by way of compensation(3)
Verifier: this is the executor of the proof verification algorithm. Because the scheme is publicly verifiable, all members of the blockchain can theoretically act as verifiers, usually as third-party miners. Verifiers get a certain compensation by executing smart contracts deployed on the blockchainFigure 3
System model.


### 3.2. Formal Definition

Our scheme contains four algorithms: KeyGen, TagGen, ProofGen, and ProofVerify. Each is formally defined below.(1)
KeyGen1n,k⟶pk,sk: the key generation algorithm is run by the DO. The inputs to it are the security parameter n and the number of data blocks k, and the outputs is a public–private key pair (pk, sk)(2)
TagGenpk,sk,F⟶ψ,ζ: the tag generation algorithm is run by the DO. The input to it consists of the public key pk, private key sk, and file F. The outputs are a set of block signatures ψ and a set of block indices ζ(3)
ProofGenF,ψ,ζ,h,ω⟶P: the proof generation algorithm is run by the CSP. The inputs to it are F, a set of block signatures ψ, a set of block indices ζ, the hash value h of the previous block, and timestamp ω. The output is the proof P(4)
ProofVerifyP,pk⟶SUCCESS,FALSE: the proof verification algorithm is run by the verifier. The inputs are the proof P and the public key pk. If the proof is verified, the output is SUCCESS; otherwise, the output is FALSE


### 3.3. Scheme Implementation

We first design a post-quantum privacy-preserving PDP protocol and then combine it with smart contract technology to develop our scheme.


#### 3.3.1. Post-Quantum Privacy-Preserving PDP Protocol

We set a security parametern and a maximum file block size k. Two hash functions H1:0,1∗⟶0,1m and H2:0,1∗⟶Fqn (modeled as a random oracle) are used as well.KeyGen(1)
Choose two primesp=2 and q=polyn with q≥nkp2. Define m=6nlogq and v=p⋅mlogq⋅logm(2)
SetΛ1=p⋅ℤm. Use TrapGenq,n,m to generate a matrix A∈Fqn×m, which results in a lattice Λq⊥A and a short basis Tq of Λq⊥A. Define Λ2=Λq⊥A and T=p⋅Tq, and note that T is a basis of the lattice Λ1∩Λ2=p⋅Λ2(3)
Output the public keypk=Λ1,Λ2,A,v,p,q and the private key sk=TTagGen(1)
Given the fileF=mi1≤i≤k,mi∈Fpm, its fingerprint value can be denoted by the hash τ⟵H1F(2)
Compute the indexαi=H2τi∈Fqn for each block mi(3)
Compute the vectorti∈ℤm such that timodp=mi and A⋅timodq=αi(4)
Compute the signature ofmi:(6)σi⟵SamplePreΛ1∩Λ2,T,ti,v∈pΛ2+ti(5)
Output a set of signaturesψ=σi1≤i≤k and a set of block indices ζ=αi1≤i≤kProofGen(1)
The CSP obtains the header of the newly generated block to obtain the hash valueh of the previous block and the corresponding timestamp ω. Because the blockchain uses SHA-256, h=h1h2⋯h256,hi∈0,1(2)
Define the challenge set asQ=c1,c2,⋯,ck∈ℤk, where ci=hj and i=jmod256. ci∈0,1 satisfies ci∈−p/2,p/2(3)
Select two random vectorsR=r1,⋯,rk∈ℤpk and s∈ℤpm. Compute s+∑i=1kricimi=μ∈ℤpmmodp, σ=s+∑i=1kriciσi, and As+∑i=1kriciαi=ϕ∈Fqn(4)
Output the proofP=μ,σ,ϕ,h,ωProofVerify(1)
Verify the authenticity of the timestampω and the hash value of the previous block h from P. Return FALSE if it fails, and continue if it succeeds(2)
Verify the conditions below. If all conditions are met, output SUCCESS; otherwise, output FALSE:(a)
σ≤vk+1m(b)
σmodp=μ(c)
A⋅σmodq=ϕ


#### 3.3.2. Post-Quantum Privacy-Preserving PDP Scheme Based on Smart Contracts

The DO needs to pay the CSP to purchase storage space in the traditional cloud storage system. If the DO’s data are unavailable or have been tampered with, it is difficult to protect the data rights and obtain economic compensation. On the contrary, the laws and regulations on data security in various countries are not necessarily complete, especially in case of transnational disputes. Legal action also often incurs additional costs in terms of money and time.The emergence of smart contracts has helped solve the above problems. As smart contracts are immutable and automatically triggered, the contract is executed immediately once all parties have agreed to its contents if all its conditions are met. No one can then change the contents of the contract.We propose a post-quantum privacy-preserving provable data possession scheme based on smart contracts for cloud storage systems. We provide parties with tamper-resistant integrity verification through smart contracts deployed on the blockchain that pass the deposit mechanism to guarantee fair payment. To protect against dishonest verifiers and ensure the correctness of verifiers when executing smart contracts, a consensus mechanism is needed. This is not discussed in detail in this article.The flow logic of the scheme is shown in Figure4 and is described below. The smart contracts used are shown in Table 1.
(1)
The DO, CSP, and verifier are registered on the blockchain to obtain the public–private key pair and account addressesAddressDO, AddressCSP, and AddressV. The public–private key pair is used for signing and verifying on the blockchain. The account addresses are generated from the public key to indicate the identity of the transactions. When the scheme is applied to multiple users, different DOs will product their own AddressDO and SignDO, by which they distinguish each other and generate different smart contracts. The DO and CSP need to pay a certain deposit to ensure the smooth completion of subsequent transactions(2)
The DO runs the algorithm KeyGen and outputs a public–private key pair (pk, sk). The algorithm TagGen is run to output the block signaturesψ and the block indices ζ(3)
The DO uploadsF,ψ,ζ to the CSP, generates T1, and deploys it on the blockchain. The storage contract T1 contains basic file information (name, hash, and upload time) and transaction-related information (storage fee, DO’s address, CSP’s address, and DO’s signature). This contract can ensure that the DO must pay the CSP in time if the latter stores all of the files of the former and the data satisfy the proof of verification(4)
When the CSP receivesF,ψ,ζ, it generates T2 and deploys it on the blockchain. The compensation contract T2 contains basic file information (name, hash, and receive time) and transaction-related information (compensation fee, DO’s address, CSP’s address, and CSP’s signature). This contract can ensure that the CSP pays/compensates the DO in time if it does not store its entire data such that integrity verification fails(5)
The CSP periodically runs the algorithm ProofVerify to generate the proofP according to the hash value of the previous block h and the corresponding timestamp ω of the latest block generated. It generates T3 and deploys it on the blockchain. The verification contract T3 contains basic file information (name, hash value, and proof), the related contracts (T1 and T2), and transaction-related information (verification fee, CSP’s address, verifier’s address, and CSP’s signature). To obtain the reward, the verifier executes contract T3 and chooses to activate T1 or T2 according to the resultFigure 4
The flow logic of the scheme.Table 1
Smart contractsT1, T2, and T3.
Storage contractT1Compensation contractT2Verification contractT3File’s nameFNFile’s nameFNFile’s nameFNFile’s hashFHFile’s hashFHFile’s hashFHUpload timeUTReceive timeRTProofPStorage feeSFCompensation feeCFStorage contractT1DO’s addressAddressDODO’s addressAddressDOCompensation contractT2CSP’s addressAddressCSPCSP’s addressAddressCSPVerification feeVFDO’s signatureSignDOCSP’s signatureSignCSPCSP’s addressAddressCSPContract content:PromiseIfProofVerifypk,P⟶SUCCESSPay SF from AddressDO to AddressCSPContract content:PromiseIfProofVerifypk,P⟶FALSEPay CF from AddressCSP to AddressDOVerifier’s addressAddressVCSP’s signatureSignCSPContract content:(1) Execute the algorithm ProofVerifyIfProofVerifypk,P⟶SUCCESS, then activate the contract T1IfProofVerifypk,P⟶FALSE, then activate the contract T2(2) Pay VF from AddressCSP to AddressV


### 3.4. Brief Summary

We have developed a post-quantum privacy-preserving provable data possession scheme based on smart contracts that not only meets the essential requirements of correctness and security but also has the following characteristics.(1)
Post quantum: the scheme uses the linear homomorphic signature on lattices based on the preimage sampling algorithm. Its security depends on the ISIS problem on lattices and provides a strong proof of security based on the worst-case hardness so that it can meet the requirements of protecting against the quantum attacks(2)
Public verification: the proof verification algorithm of the scheme is public and does not require the use of a private key. Any third-party auditor can obtain a public conclusion on whether the CSP completely stores the DO’s data, which liberates users from the arduous task of verification(3)
Privacy preservation: the random masking technology introduces random variables to ProofGen. The adversary cannot obtain the user’s original data by solving the linear equations composed of different proofs, which satisfies the demand for privacy preservation(4)
Noninteractive: the scheme uses the time-varying hash value of the previous block to generate the challenge set so that the parties do not need to interact in the traditional “challenge–response” phase. On the one hand, the DO and CSP do not need to stay online all the time, which makes the operation of the scheme more flexible, and on the other hand, it can reduce the cost of transactions due to interactions in the blockchain(5)
Fair payment: the DO, CSP, and verifier trade according to the agreed smart contract. The smart contract is immutable and automatically executed such that fair payment can be guaranteed


## 3.1. System Model

The system model of a post-quantum privacy-preserving provable data possession scheme based on smart contracts contains three entities: the data owner, the cloud storage provider, and the verifier (see Figure3).
(1)
Data owner (DO): to save the cost of local storage and use data conveniently and flexibly, cloud storage users pay a certain fee and store their data on a remote server owned by the cloud storage provider(2)
Cloud storage provider (CSP): it provides computing, storage, and network bandwidth for the DO. The CSP needs to periodically perform PDP to prove that it maintains the integrity of data. If verification fails, it pays the DO a certain fee by way of compensation(3)
Verifier: this is the executor of the proof verification algorithm. Because the scheme is publicly verifiable, all members of the blockchain can theoretically act as verifiers, usually as third-party miners. Verifiers get a certain compensation by executing smart contracts deployed on the blockchainFigure 3
System model.


## 3.2. Formal Definition

Our scheme contains four algorithms: KeyGen, TagGen, ProofGen, and ProofVerify. Each is formally defined below.(1)
KeyGen1n,k⟶pk,sk: the key generation algorithm is run by the DO. The inputs to it are the security parameter n and the number of data blocks k, and the outputs is a public–private key pair (pk, sk)(2)
TagGenpk,sk,F⟶ψ,ζ: the tag generation algorithm is run by the DO. The input to it consists of the public key pk, private key sk, and file F. The outputs are a set of block signatures ψ and a set of block indices ζ(3)
ProofGenF,ψ,ζ,h,ω⟶P: the proof generation algorithm is run by the CSP. The inputs to it are F, a set of block signatures ψ, a set of block indices ζ, the hash value h of the previous block, and timestamp ω. The output is the proof P(4)
ProofVerifyP,pk⟶SUCCESS,FALSE: the proof verification algorithm is run by the verifier. The inputs are the proof P and the public key pk. If the proof is verified, the output is SUCCESS; otherwise, the output is FALSE


## 3.3. Scheme Implementation

We first design a post-quantum privacy-preserving PDP protocol and then combine it with smart contract technology to develop our scheme.


### 3.3.1. Post-Quantum Privacy-Preserving PDP Protocol

We set a security parametern and a maximum file block size k. Two hash functions H1:0,1∗⟶0,1m and H2:0,1∗⟶Fqn (modeled as a random oracle) are used as well.KeyGen(1)
Choose two primesp=2 and q=polyn with q≥nkp2. Define m=6nlogq and v=p⋅mlogq⋅logm(2)
SetΛ1=p⋅ℤm. Use TrapGenq,n,m to generate a matrix A∈Fqn×m, which results in a lattice Λq⊥A and a short basis Tq of Λq⊥A. Define Λ2=Λq⊥A and T=p⋅Tq, and note that T is a basis of the lattice Λ1∩Λ2=p⋅Λ2(3)
Output the public keypk=Λ1,Λ2,A,v,p,q and the private key sk=TTagGen(1)
Given the fileF=mi1≤i≤k,mi∈Fpm, its fingerprint value can be denoted by the hash τ⟵H1F(2)
Compute the indexαi=H2τi∈Fqn for each block mi(3)
Compute the vectorti∈ℤm such that timodp=mi and A⋅timodq=αi(4)
Compute the signature ofmi:(6)σi⟵SamplePreΛ1∩Λ2,T,ti,v∈pΛ2+ti(5)
Output a set of signaturesψ=σi1≤i≤k and a set of block indices ζ=αi1≤i≤kProofGen(1)
The CSP obtains the header of the newly generated block to obtain the hash valueh of the previous block and the corresponding timestamp ω. Because the blockchain uses SHA-256, h=h1h2⋯h256,hi∈0,1(2)
Define the challenge set asQ=c1,c2,⋯,ck∈ℤk, where ci=hj and i=jmod256. ci∈0,1 satisfies ci∈−p/2,p/2(3)
Select two random vectorsR=r1,⋯,rk∈ℤpk and s∈ℤpm. Compute s+∑i=1kricimi=μ∈ℤpmmodp, σ=s+∑i=1kriciσi, and As+∑i=1kriciαi=ϕ∈Fqn(4)
Output the proofP=μ,σ,ϕ,h,ωProofVerify(1)
Verify the authenticity of the timestampω and the hash value of the previous block h from P. Return FALSE if it fails, and continue if it succeeds(2)
Verify the conditions below. If all conditions are met, output SUCCESS; otherwise, output FALSE:(a)
σ≤vk+1m(b)
σmodp=μ(c)
A⋅σmodq=ϕ


### 3.3.2. Post-Quantum Privacy-Preserving PDP Scheme Based on Smart Contracts

The DO needs to pay the CSP to purchase storage space in the traditional cloud storage system. If the DO’s data are unavailable or have been tampered with, it is difficult to protect the data rights and obtain economic compensation. On the contrary, the laws and regulations on data security in various countries are not necessarily complete, especially in case of transnational disputes. Legal action also often incurs additional costs in terms of money and time.The emergence of smart contracts has helped solve the above problems. As smart contracts are immutable and automatically triggered, the contract is executed immediately once all parties have agreed to its contents if all its conditions are met. No one can then change the contents of the contract.We propose a post-quantum privacy-preserving provable data possession scheme based on smart contracts for cloud storage systems. We provide parties with tamper-resistant integrity verification through smart contracts deployed on the blockchain that pass the deposit mechanism to guarantee fair payment. To protect against dishonest verifiers and ensure the correctness of verifiers when executing smart contracts, a consensus mechanism is needed. This is not discussed in detail in this article.The flow logic of the scheme is shown in Figure4 and is described below. The smart contracts used are shown in Table 1.
(1)
The DO, CSP, and verifier are registered on the blockchain to obtain the public–private key pair and account addressesAddressDO, AddressCSP, and AddressV. The public–private key pair is used for signing and verifying on the blockchain. The account addresses are generated from the public key to indicate the identity of the transactions. When the scheme is applied to multiple users, different DOs will product their own AddressDO and SignDO, by which they distinguish each other and generate different smart contracts. The DO and CSP need to pay a certain deposit to ensure the smooth completion of subsequent transactions(2)
The DO runs the algorithm KeyGen and outputs a public–private key pair (pk, sk). The algorithm TagGen is run to output the block signaturesψ and the block indices ζ(3)
The DO uploadsF,ψ,ζ to the CSP, generates T1, and deploys it on the blockchain. The storage contract T1 contains basic file information (name, hash, and upload time) and transaction-related information (storage fee, DO’s address, CSP’s address, and DO’s signature). This contract can ensure that the DO must pay the CSP in time if the latter stores all of the files of the former and the data satisfy the proof of verification(4)
When the CSP receivesF,ψ,ζ, it generates T2 and deploys it on the blockchain. The compensation contract T2 contains basic file information (name, hash, and receive time) and transaction-related information (compensation fee, DO’s address, CSP’s address, and CSP’s signature). This contract can ensure that the CSP pays/compensates the DO in time if it does not store its entire data such that integrity verification fails(5)
The CSP periodically runs the algorithm ProofVerify to generate the proofP according to the hash value of the previous block h and the corresponding timestamp ω of the latest block generated. It generates T3 and deploys it on the blockchain. The verification contract T3 contains basic file information (name, hash value, and proof), the related contracts (T1 and T2), and transaction-related information (verification fee, CSP’s address, verifier’s address, and CSP’s signature). To obtain the reward, the verifier executes contract T3 and chooses to activate T1 or T2 according to the resultFigure 4
The flow logic of the scheme.Table 1
Smart contractsT1, T2, and T3.
Storage contractT1Compensation contractT2Verification contractT3File’s nameFNFile’s nameFNFile’s nameFNFile’s hashFHFile’s hashFHFile’s hashFHUpload timeUTReceive timeRTProofPStorage feeSFCompensation feeCFStorage contractT1DO’s addressAddressDODO’s addressAddressDOCompensation contractT2CSP’s addressAddressCSPCSP’s addressAddressCSPVerification feeVFDO’s signatureSignDOCSP’s signatureSignCSPCSP’s addressAddressCSPContract content:PromiseIfProofVerifypk,P⟶SUCCESSPay SF from AddressDO to AddressCSPContract content:PromiseIfProofVerifypk,P⟶FALSEPay CF from AddressCSP to AddressDOVerifier’s addressAddressVCSP’s signatureSignCSPContract content:(1) Execute the algorithm ProofVerifyIfProofVerifypk,P⟶SUCCESS, then activate the contract T1IfProofVerifypk,P⟶FALSE, then activate the contract T2(2) Pay VF from AddressCSP to AddressV


## 3.3.1. Post-Quantum Privacy-Preserving PDP Protocol

We set a security parametern and a maximum file block size k. Two hash functions H1:0,1∗⟶0,1m and H2:0,1∗⟶Fqn (modeled as a random oracle) are used as well.KeyGen(1)
Choose two primesp=2 and q=polyn with q≥nkp2. Define m=6nlogq and v=p⋅mlogq⋅logm(2)
SetΛ1=p⋅ℤm. Use TrapGenq,n,m to generate a matrix A∈Fqn×m, which results in a lattice Λq⊥A and a short basis Tq of Λq⊥A. Define Λ2=Λq⊥A and T=p⋅Tq, and note that T is a basis of the lattice Λ1∩Λ2=p⋅Λ2(3)
Output the public keypk=Λ1,Λ2,A,v,p,q and the private key sk=TTagGen(1)
Given the fileF=mi1≤i≤k,mi∈Fpm, its fingerprint value can be denoted by the hash τ⟵H1F(2)
Compute the indexαi=H2τi∈Fqn for each block mi(3)
Compute the vectorti∈ℤm such that timodp=mi and A⋅timodq=αi(4)
Compute the signature ofmi:(6)σi⟵SamplePreΛ1∩Λ2,T,ti,v∈pΛ2+ti(5)
Output a set of signaturesψ=σi1≤i≤k and a set of block indices ζ=αi1≤i≤kProofGen(1)
The CSP obtains the header of the newly generated block to obtain the hash valueh of the previous block and the corresponding timestamp ω. Because the blockchain uses SHA-256, h=h1h2⋯h256,hi∈0,1(2)
Define the challenge set asQ=c1,c2,⋯,ck∈ℤk, where ci=hj and i=jmod256. ci∈0,1 satisfies ci∈−p/2,p/2(3)
Select two random vectorsR=r1,⋯,rk∈ℤpk and s∈ℤpm. Compute s+∑i=1kricimi=μ∈ℤpmmodp, σ=s+∑i=1kriciσi, and As+∑i=1kriciαi=ϕ∈Fqn(4)
Output the proofP=μ,σ,ϕ,h,ωProofVerify(1)
Verify the authenticity of the timestampω and the hash value of the previous block h from P. Return FALSE if it fails, and continue if it succeeds(2)
Verify the conditions below. If all conditions are met, output SUCCESS; otherwise, output FALSE:(a)
σ≤vk+1m(b)
σmodp=μ(c)
A⋅σmodq=ϕ


## 3.3.2. Post-Quantum Privacy-Preserving PDP Scheme Based on Smart Contracts

The DO needs to pay the CSP to purchase storage space in the traditional cloud storage system. If the DO’s data are unavailable or have been tampered with, it is difficult to protect the data rights and obtain economic compensation. On the contrary, the laws and regulations on data security in various countries are not necessarily complete, especially in case of transnational disputes. Legal action also often incurs additional costs in terms of money and time.The emergence of smart contracts has helped solve the above problems. As smart contracts are immutable and automatically triggered, the contract is executed immediately once all parties have agreed to its contents if all its conditions are met. No one can then change the contents of the contract.We propose a post-quantum privacy-preserving provable data possession scheme based on smart contracts for cloud storage systems. We provide parties with tamper-resistant integrity verification through smart contracts deployed on the blockchain that pass the deposit mechanism to guarantee fair payment. To protect against dishonest verifiers and ensure the correctness of verifiers when executing smart contracts, a consensus mechanism is needed. This is not discussed in detail in this article.The flow logic of the scheme is shown in Figure4 and is described below. The smart contracts used are shown in Table 1.
(1)
The DO, CSP, and verifier are registered on the blockchain to obtain the public–private key pair and account addressesAddressDO, AddressCSP, and AddressV. The public–private key pair is used for signing and verifying on the blockchain. The account addresses are generated from the public key to indicate the identity of the transactions. When the scheme is applied to multiple users, different DOs will product their own AddressDO and SignDO, by which they distinguish each other and generate different smart contracts. The DO and CSP need to pay a certain deposit to ensure the smooth completion of subsequent transactions(2)
The DO runs the algorithm KeyGen and outputs a public–private key pair (pk, sk). The algorithm TagGen is run to output the block signaturesψ and the block indices ζ(3)
The DO uploadsF,ψ,ζ to the CSP, generates T1, and deploys it on the blockchain. The storage contract T1 contains basic file information (name, hash, and upload time) and transaction-related information (storage fee, DO’s address, CSP’s address, and DO’s signature). This contract can ensure that the DO must pay the CSP in time if the latter stores all of the files of the former and the data satisfy the proof of verification(4)
When the CSP receivesF,ψ,ζ, it generates T2 and deploys it on the blockchain. The compensation contract T2 contains basic file information (name, hash, and receive time) and transaction-related information (compensation fee, DO’s address, CSP’s address, and CSP’s signature). This contract can ensure that the CSP pays/compensates the DO in time if it does not store its entire data such that integrity verification fails(5)
The CSP periodically runs the algorithm ProofVerify to generate the proofP according to the hash value of the previous block h and the corresponding timestamp ω of the latest block generated. It generates T3 and deploys it on the blockchain. The verification contract T3 contains basic file information (name, hash value, and proof), the related contracts (T1 and T2), and transaction-related information (verification fee, CSP’s address, verifier’s address, and CSP’s signature). To obtain the reward, the verifier executes contract T3 and chooses to activate T1 or T2 according to the resultFigure 4
The flow logic of the scheme.Table 1
Smart contractsT1, T2, and T3.
Storage contractT1Compensation contractT2Verification contractT3File’s nameFNFile’s nameFNFile’s nameFNFile’s hashFHFile’s hashFHFile’s hashFHUpload timeUTReceive timeRTProofPStorage feeSFCompensation feeCFStorage contractT1DO’s addressAddressDODO’s addressAddressDOCompensation contractT2CSP’s addressAddressCSPCSP’s addressAddressCSPVerification feeVFDO’s signatureSignDOCSP’s signatureSignCSPCSP’s addressAddressCSPContract content:PromiseIfProofVerifypk,P⟶SUCCESSPay SF from AddressDO to AddressCSPContract content:PromiseIfProofVerifypk,P⟶FALSEPay CF from AddressCSP to AddressDOVerifier’s addressAddressVCSP’s signatureSignCSPContract content:(1) Execute the algorithm ProofVerifyIfProofVerifypk,P⟶SUCCESS, then activate the contract T1IfProofVerifypk,P⟶FALSE, then activate the contract T2(2) Pay VF from AddressCSP to AddressV


## 3.4. Brief Summary

We have developed a post-quantum privacy-preserving provable data possession scheme based on smart contracts that not only meets the essential requirements of correctness and security but also has the following characteristics.(1)
Post quantum: the scheme uses the linear homomorphic signature on lattices based on the preimage sampling algorithm. Its security depends on the ISIS problem on lattices and provides a strong proof of security based on the worst-case hardness so that it can meet the requirements of protecting against the quantum attacks(2)
Public verification: the proof verification algorithm of the scheme is public and does not require the use of a private key. Any third-party auditor can obtain a public conclusion on whether the CSP completely stores the DO’s data, which liberates users from the arduous task of verification(3)
Privacy preservation: the random masking technology introduces random variables to ProofGen. The adversary cannot obtain the user’s original data by solving the linear equations composed of different proofs, which satisfies the demand for privacy preservation(4)
Noninteractive: the scheme uses the time-varying hash value of the previous block to generate the challenge set so that the parties do not need to interact in the traditional “challenge–response” phase. On the one hand, the DO and CSP do not need to stay online all the time, which makes the operation of the scheme more flexible, and on the other hand, it can reduce the cost of transactions due to interactions in the blockchain(5)
Fair payment: the DO, CSP, and verifier trade according to the agreed smart contract. The smart contract is immutable and automatically executed such that fair payment can be guaranteed


## 4. Proof of Security

### 4.1. Correctness

Theorem 12.
Our post-quantum privacy-preserving PDP protocol proposed in Section3.3 is correct with an overwhelming probability.Proof.
Assume a fileF=mi1≤i≤k, block signatures σi⟵SamplePreΛ1∩Λ2,T,ti,v, a challenge set Q=c1,c2,⋯,ck, and the proof μ=s+∑i=1kricimi, σ=s+∑i=1kriciσi, and ϕ=As+∑i=1kriciαi. We check the three conditions separately in ProofVerify.
(a)
By Theorem4, we have T~≤Op⋅mlogq; therefore, v=p⋅mlogq⋅logm≥T~⋅logm≥T~⋅ωlogm. By Lemma 8, we have σi≤v⋅m. Since σ=s+∑i=1kriciσi, s∈ℤ2m, ri∈0,1, and ci∈0,1, we have that with overwhelming probability(7)σ≤s+∑i=1kriciσi≤m+kmax1≤i≤kσi≤vk+1m(b)
Sinceσi∈pΛ2+ti and timodp=mi, we have σi=ti=mimodp. Thus, the following equation holds:(8)σ=s+∑i=1kriciσi=s+∑i=1kriciti=s+∑i=1kricimi=μmodp(c)
We haveσi∈pΛ2+ti and Λ2=Λq⊥A. Since Atimodq=αi, we have Aσi=Ati=αimodq. Thus, the following equation holds:(9)Aσ=A⋅s+∑i=1kriciσi=As+∑i=1kriciAti=As+∑i=1kriciαi=ϕmodq


### 4.2. Soundness

We define the security of the scheme by formally describing a series of games between a challengerC and an adversary A.Setup: C runs the algorithm KeyGen to generate the public-private key pair (pk, sk), reserves sk for responding to the A ‘s query, and then sends pk to A.Queries: A can execute adaptive signature queries by interacting with C. A specifies a series of j files Fj=mij1≤i≤k to send to C. C generates the corresponding set of j signatures ψj=σij1≤i≤k and the set of block indices ζj=αij1≤i≤k by running the algorithm TagGen and then sends ψj,ζj to A.Output: A outputs the proof based on the results of multiple queries. For a fileFwith a set of signatureψ=σi1≤i≤kand a set of block indicesζ=αi1≤i≤k, the proofP∗=μ∗,σ∗,ϕ∗,h,ωis output when the hash value of the previous block ishand the timestamp isω.Definition 13.
The advantage of an adversaryA in the game is AdvA=PrProofVerifyP∗,pk=SUCCESS, and if AdvA is nonnegligible, we say that A wins the game.Definition 14.
The post-quantum privacy-preserving provable data possession protocol proposed in Section3.3 is secure. If there exists an efficient extraction algorithm Extr, such that any adversaryAwins the security game and outputs the proofP∗of the fileF, the probability that Extr can recoverFfromP∗(i.e.,Extrpk,P∗=F) is not negligible.Theorem 15.
If the algorithms used to generate the block signatures and block indices of the files are existentially unforgeable and theISISq,m,β problem is difficult in case β=2mkp⋅logmlogq+2m, then, under the random oracle model, the probability that any adversary breaking the security of our scheme passes ProofVerify by using a proof not generated by ProofGen is negligible.Proof.
We demonstrate Theorem15 through the interactive analysis of a series of games. The game’s restrictions on the opponent A are gradually tightened.Game-0: Game-0 is the first game. It is the security game defined at the beginning of this section.Game-1: Game-1 is similar to Game-0 with one difference: the challenger C maintains a list of block signatures that have been responded to during the query phase. If the adversary A submits a valid signature σi that is, however, not in the challenger’s signature list, C aborts and outputs failure.Game-2: Game-2 is similar to Game-1 with one difference: the challenger C maintains a list that stores the indices of the data blocks that have been responded to during the query phase. If the adversary A submits a valid index αi that is not in the challenger’s index list, C aborts and outputs failure.Game-3: Game-3 is similar to Game-2 with one difference: the challenger C maintains a list of all tag queries and responses initiated by the adversary A. IfAsubmits a proof of successful verification whereμis not equal tos+∑i=1kricimi,σis not equal tos+∑i=1kriciσi, andϕis not equal toAs+∑i=1kriciαi,Caborts and outputs failure.Lemma 16.
If there is an algorithmA that can distinguish Game-1 from Game-0 with a nonnegligible probability, we can construct an algorithm B that can counteract the existence of GPV signature scheme with a nonnegligible probability.Analysis: if the adversary A fails to output in Game-1, we can forge a valid signature σi, which contradicts the existential unforgeability of the GPV signature scheme.Lemma 17.
If there is an algorithmA that can distinguish Game-2 from Game-1 with a nonnegligible probability, we can construct an algorithm B for the collision resistance of the hash function with a nonnegligible probability.Analysis: if the adversary A fails to output in Game-2, we can forge a valid index αi∗≠αi, but they are all equal to H2τi, which contradicts the collision resistance of the hash function.Lemma 18.
If there exists an algorithmA that can distinguish Game-3 from Game-2 with a nonnegligible probability and β=2mkp⋅logmlogq+2m, we can construct an algorithm to solve the ISISq,m,β problem.Analysis: before analyzing the above, we establish some notation. Suppose that the file that caused the failure is divided into k blocks of equal length, denoted as F=mi1≤i≤k. The block signature set ψ=σi and the block index set ζ=αi are generated by TagGen. Assuming that Q=c1,c2,⋯,ck is the set of challenges that lead to failed queries, the outputs of the adversary’s response are μ∗, σ∗, and ϕ∗, where μ∗=s∗+∑i=1kri∗cimi, σ∗=s∗+∑i=1kri∗ciσi, and ϕ∗=As∗+∑i=1kri∗ciαi. Let the expected responses (generated by an honest prover) be μ, σ, and ϕ. We can ensure by Lemmas 16 and 17 that the block signature σi and block index αi used in the queries and output phases, both generated by the challenger C, are unforgeable. Thus, if μ∗=μ, there must be σ∗=σ and ϕ∗=ϕ, and if μ∗≠μ, there must be σ∗≠σ and ϕ∗≠ϕ.We now show that if the adversary fails the challenger with a nonnegligible probability in Game-3, we can construct a simulatorS to solve the ISIS problem on lattices.The inputs of the simulatorS are the file F and some parameters. Its goal is to output a vector σ∗−σ. The behavior of the emulator is different from that of the challenger in Game-2, including in terms of the algorithm setup, queries, outputs, and the hash:Setup: when generating the key, create a lattice Λ1 and its short basis T1. The other parameters are the same as in Game-2, meaning that the simulator does not know the private key T.Hash: the simulator writes a random oracle H and maintains a table of queries and responses. When the adversary chooses τi to initiate a query, it returns Hτi if it is in the queried list; otherwise, it returns Hτi=A⋅σimodq, where σi⟵Dℤn,v.Queries: when asked to sign the file F, the simulator does the following:
(1)
It randomly selectsτ⟵R0,1m as the tag. Since the selection space is large enough, the probability that the simulator selects a tag that has once initiated query τi to the random oracle H is negligible. If it has been queried, it aborts(2)
Chooseti such that timodp=mi, and output σi⟵SamplePreΛ1,T1,ti,v(3)
LetHτi=αi=A⋅σimodq,1≤i≤kOutput: for the challenge set Q=c1,c2,⋯,ck∈ℤk, compute μ∗, σ∗, and ϕ∗, and finally, output the vector σ∗−σ.We first show that the output of the simulatorS is distributed (up to a negligible statistical distance) as in the real signature scheme. Because the simulator chooses a random tag τ from 0,1m when signing, the probability that the simulator aborts is negligible. We may therefore assume that the simulator does not abort. Since v≥ηεΛ1∩Λ2 for a negligible ε, by Lemma 9, the vectors σi chosen in both hash and queries are statistically close to the uniform modulo Λ2, and thus, the output of Hτi=σimodΛ2 is indistinguishable from random. By Theorem 6, σi in the real scheme are distributed as DΛ1∩Λ2+ti,v such that timodp=mi and A⋅timodq=αi. The simulated σi, on the contrary, are distributed as DΛ1+ti,v such that timodp=mi, conditioned on A⋅σimodq=αi. By a straightforward generalization of Lemma 5.2 in [32], these two distributions are identical. Therefore, samplingσifromΛ1∩Λ2in the real scheme has the same distribution as sampling fromΛ1and then moduloΛ2in the simulator.We now show that the outputσ∗−σ of the simulator is a solution to the ISIS problem on lattices. The adversary’s proof as response is μ∗, σ∗, and ϕ∗, and the expected responses (generated by an honest prover) are μ, σ, and ϕ. They are different, but all can be successfully verified, so there is σ∗−σ=μ∗−μ≠0modp. According to
(10)σ≤vk+1m,σ=μmodp,A⋅σ=ϕmodq,σ∗≤vk+1m,σ∗=μ∗modp,A⋅σ∗=ϕ∗modq,σ∗−σ≤σ∗+σ≤2vk+1m=β. Assuming that Δs=s∗−s and Δt=t∗−t, let A⋅Δs+Δt⋅∑i=1kci⋅αi=d. Then, A⋅σ∗−σ=ϕ∗−ϕ=dmodq, i.e., σ∗−σ∈ΛqdA. We thus identify the nonzero vector σ∗−σ, which is a solution to the ISISq,m,β problem on the lattice ΛqdA.Summary. Any proof of successful verification is generated by an honest prover and cannot be forged. The challenger thus always aborts and outputs failure; i.e., any adversary’s advantage in Game-3 must be zero. The series of games and Lemmas 16–18 help ensure that any adversary’s advantage in Game-0 is negligible. Our proposed post-quantum privacy-preserving provable data possession protocol is thus secure.


### 4.3. Privacy-Preserving

We hope to ensure that the verifier cannot obtain user data based on the information collected during the verification process through the proof of the following theorem.Theorem 19.
The verifier cannot obtainmi from the proof P=μ,σ,ϕ,h,ω returned by the CSP.Proof.
According toσi⟵SamplePreΛ1∩Λ2,T,ti,v and αi=H2τi, we cannot obtain any information about mi from σ and ϕ. Therefore, the proof can be transformed into one whereby the verifier cannot obtain mi from μ.
We note that because the challenge setQ=c1,c2,⋯,ck is publicly available, if μ′=∑i=1krimi can be obtained by the verifier, then a set of linear equations for mi can be obtained after multiple challenges and mi can be obtained by solving them. We now prove that the verifier cannot obtain μ′ from μ.
According toμ=s+∑i=1kricimi, vectors R=r1,⋯,rk and s randomly chosen by CSP are unknown to the verifier; thus, μ′ cannot be derived from μ.


## 4.1. Correctness

Theorem 12.
Our post-quantum privacy-preserving PDP protocol proposed in Section3.3 is correct with an overwhelming probability.Proof.
Assume a fileF=mi1≤i≤k, block signatures σi⟵SamplePreΛ1∩Λ2,T,ti,v, a challenge set Q=c1,c2,⋯,ck, and the proof μ=s+∑i=1kricimi, σ=s+∑i=1kriciσi, and ϕ=As+∑i=1kriciαi. We check the three conditions separately in ProofVerify.
(a)
By Theorem4, we have T~≤Op⋅mlogq; therefore, v=p⋅mlogq⋅logm≥T~⋅logm≥T~⋅ωlogm. By Lemma 8, we have σi≤v⋅m. Since σ=s+∑i=1kriciσi, s∈ℤ2m, ri∈0,1, and ci∈0,1, we have that with overwhelming probability(7)σ≤s+∑i=1kriciσi≤m+kmax1≤i≤kσi≤vk+1m(b)
Sinceσi∈pΛ2+ti and timodp=mi, we have σi=ti=mimodp. Thus, the following equation holds:(8)σ=s+∑i=1kriciσi=s+∑i=1kriciti=s+∑i=1kricimi=μmodp(c)
We haveσi∈pΛ2+ti and Λ2=Λq⊥A. Since Atimodq=αi, we have Aσi=Ati=αimodq. Thus, the following equation holds:(9)Aσ=A⋅s+∑i=1kriciσi=As+∑i=1kriciAti=As+∑i=1kriciαi=ϕmodq


## 4.2. Soundness

We define the security of the scheme by formally describing a series of games between a challengerC and an adversary A.Setup: C runs the algorithm KeyGen to generate the public-private key pair (pk, sk), reserves sk for responding to the A ‘s query, and then sends pk to A.Queries: A can execute adaptive signature queries by interacting with C. A specifies a series of j files Fj=mij1≤i≤k to send to C. C generates the corresponding set of j signatures ψj=σij1≤i≤k and the set of block indices ζj=αij1≤i≤k by running the algorithm TagGen and then sends ψj,ζj to A.Output: A outputs the proof based on the results of multiple queries. For a fileFwith a set of signatureψ=σi1≤i≤kand a set of block indicesζ=αi1≤i≤k, the proofP∗=μ∗,σ∗,ϕ∗,h,ωis output when the hash value of the previous block ishand the timestamp isω.Definition 13.
The advantage of an adversaryA in the game is AdvA=PrProofVerifyP∗,pk=SUCCESS, and if AdvA is nonnegligible, we say that A wins the game.Definition 14.
The post-quantum privacy-preserving provable data possession protocol proposed in Section3.3 is secure. If there exists an efficient extraction algorithm Extr, such that any adversaryAwins the security game and outputs the proofP∗of the fileF, the probability that Extr can recoverFfromP∗(i.e.,Extrpk,P∗=F) is not negligible.Theorem 15.
If the algorithms used to generate the block signatures and block indices of the files are existentially unforgeable and theISISq,m,β problem is difficult in case β=2mkp⋅logmlogq+2m, then, under the random oracle model, the probability that any adversary breaking the security of our scheme passes ProofVerify by using a proof not generated by ProofGen is negligible.Proof.
We demonstrate Theorem15 through the interactive analysis of a series of games. The game’s restrictions on the opponent A are gradually tightened.Game-0: Game-0 is the first game. It is the security game defined at the beginning of this section.Game-1: Game-1 is similar to Game-0 with one difference: the challenger C maintains a list of block signatures that have been responded to during the query phase. If the adversary A submits a valid signature σi that is, however, not in the challenger’s signature list, C aborts and outputs failure.Game-2: Game-2 is similar to Game-1 with one difference: the challenger C maintains a list that stores the indices of the data blocks that have been responded to during the query phase. If the adversary A submits a valid index αi that is not in the challenger’s index list, C aborts and outputs failure.Game-3: Game-3 is similar to Game-2 with one difference: the challenger C maintains a list of all tag queries and responses initiated by the adversary A. IfAsubmits a proof of successful verification whereμis not equal tos+∑i=1kricimi,σis not equal tos+∑i=1kriciσi, andϕis not equal toAs+∑i=1kriciαi,Caborts and outputs failure.Lemma 16.
If there is an algorithmA that can distinguish Game-1 from Game-0 with a nonnegligible probability, we can construct an algorithm B that can counteract the existence of GPV signature scheme with a nonnegligible probability.Analysis: if the adversary A fails to output in Game-1, we can forge a valid signature σi, which contradicts the existential unforgeability of the GPV signature scheme.Lemma 17.
If there is an algorithmA that can distinguish Game-2 from Game-1 with a nonnegligible probability, we can construct an algorithm B for the collision resistance of the hash function with a nonnegligible probability.Analysis: if the adversary A fails to output in Game-2, we can forge a valid index αi∗≠αi, but they are all equal to H2τi, which contradicts the collision resistance of the hash function.Lemma 18.
If there exists an algorithmA that can distinguish Game-3 from Game-2 with a nonnegligible probability and β=2mkp⋅logmlogq+2m, we can construct an algorithm to solve the ISISq,m,β problem.Analysis: before analyzing the above, we establish some notation. Suppose that the file that caused the failure is divided into k blocks of equal length, denoted as F=mi1≤i≤k. The block signature set ψ=σi and the block index set ζ=αi are generated by TagGen. Assuming that Q=c1,c2,⋯,ck is the set of challenges that lead to failed queries, the outputs of the adversary’s response are μ∗, σ∗, and ϕ∗, where μ∗=s∗+∑i=1kri∗cimi, σ∗=s∗+∑i=1kri∗ciσi, and ϕ∗=As∗+∑i=1kri∗ciαi. Let the expected responses (generated by an honest prover) be μ, σ, and ϕ. We can ensure by Lemmas 16 and 17 that the block signature σi and block index αi used in the queries and output phases, both generated by the challenger C, are unforgeable. Thus, if μ∗=μ, there must be σ∗=σ and ϕ∗=ϕ, and if μ∗≠μ, there must be σ∗≠σ and ϕ∗≠ϕ.We now show that if the adversary fails the challenger with a nonnegligible probability in Game-3, we can construct a simulatorS to solve the ISIS problem on lattices.The inputs of the simulatorS are the file F and some parameters. Its goal is to output a vector σ∗−σ. The behavior of the emulator is different from that of the challenger in Game-2, including in terms of the algorithm setup, queries, outputs, and the hash:Setup: when generating the key, create a lattice Λ1 and its short basis T1. The other parameters are the same as in Game-2, meaning that the simulator does not know the private key T.Hash: the simulator writes a random oracle H and maintains a table of queries and responses. When the adversary chooses τi to initiate a query, it returns Hτi if it is in the queried list; otherwise, it returns Hτi=A⋅σimodq, where σi⟵Dℤn,v.Queries: when asked to sign the file F, the simulator does the following:
(1)
It randomly selectsτ⟵R0,1m as the tag. Since the selection space is large enough, the probability that the simulator selects a tag that has once initiated query τi to the random oracle H is negligible. If it has been queried, it aborts(2)
Chooseti such that timodp=mi, and output σi⟵SamplePreΛ1,T1,ti,v(3)
LetHτi=αi=A⋅σimodq,1≤i≤kOutput: for the challenge set Q=c1,c2,⋯,ck∈ℤk, compute μ∗, σ∗, and ϕ∗, and finally, output the vector σ∗−σ.We first show that the output of the simulatorS is distributed (up to a negligible statistical distance) as in the real signature scheme. Because the simulator chooses a random tag τ from 0,1m when signing, the probability that the simulator aborts is negligible. We may therefore assume that the simulator does not abort. Since v≥ηεΛ1∩Λ2 for a negligible ε, by Lemma 9, the vectors σi chosen in both hash and queries are statistically close to the uniform modulo Λ2, and thus, the output of Hτi=σimodΛ2 is indistinguishable from random. By Theorem 6, σi in the real scheme are distributed as DΛ1∩Λ2+ti,v such that timodp=mi and A⋅timodq=αi. The simulated σi, on the contrary, are distributed as DΛ1+ti,v such that timodp=mi, conditioned on A⋅σimodq=αi. By a straightforward generalization of Lemma 5.2 in [32], these two distributions are identical. Therefore, samplingσifromΛ1∩Λ2in the real scheme has the same distribution as sampling fromΛ1and then moduloΛ2in the simulator.We now show that the outputσ∗−σ of the simulator is a solution to the ISIS problem on lattices. The adversary’s proof as response is μ∗, σ∗, and ϕ∗, and the expected responses (generated by an honest prover) are μ, σ, and ϕ. They are different, but all can be successfully verified, so there is σ∗−σ=μ∗−μ≠0modp. According to
(10)σ≤vk+1m,σ=μmodp,A⋅σ=ϕmodq,σ∗≤vk+1m,σ∗=μ∗modp,A⋅σ∗=ϕ∗modq,σ∗−σ≤σ∗+σ≤2vk+1m=β. Assuming that Δs=s∗−s and Δt=t∗−t, let A⋅Δs+Δt⋅∑i=1kci⋅αi=d. Then, A⋅σ∗−σ=ϕ∗−ϕ=dmodq, i.e., σ∗−σ∈ΛqdA. We thus identify the nonzero vector σ∗−σ, which is a solution to the ISISq,m,β problem on the lattice ΛqdA.Summary. Any proof of successful verification is generated by an honest prover and cannot be forged. The challenger thus always aborts and outputs failure; i.e., any adversary’s advantage in Game-3 must be zero. The series of games and Lemmas 16–18 help ensure that any adversary’s advantage in Game-0 is negligible. Our proposed post-quantum privacy-preserving provable data possession protocol is thus secure.


## 4.3. Privacy-Preserving

We hope to ensure that the verifier cannot obtain user data based on the information collected during the verification process through the proof of the following theorem.Theorem 19.
The verifier cannot obtainmi from the proof P=μ,σ,ϕ,h,ω returned by the CSP.Proof.
According toσi⟵SamplePreΛ1∩Λ2,T,ti,v and αi=H2τi, we cannot obtain any information about mi from σ and ϕ. Therefore, the proof can be transformed into one whereby the verifier cannot obtain mi from μ.
We note that because the challenge setQ=c1,c2,⋯,ck is publicly available, if μ′=∑i=1krimi can be obtained by the verifier, then a set of linear equations for mi can be obtained after multiple challenges and mi can be obtained by solving them. We now prove that the verifier cannot obtain μ′ from μ.
According toμ=s+∑i=1kricimi, vectors R=r1,⋯,rk and s randomly chosen by CSP are unknown to the verifier; thus, μ′ cannot be derived from μ.


## 5. Performance Evaluation

### 5.1. Comparative Analysis

This paper proposed a post-quantum privacy-preserving provable data possession scheme based on smart contracts that can verify whether the CSP holds all user data, and it is secure under the random oracle model. We compared our scheme with similar methods along five dimensions: post quantum, public verification, privacy-preserving, noninteractive, and fair payment. Table2 shows that our scheme has significant advantages over other schemes.Table 2
Comparison of the characteristics of schemes.
[15][17][19][28][30]Our schemePost quantum×××√√√Public verification√√√√√√Privacy-preserving××√×√√Noninteractive√×√××√Fair payment√×√××√


### 5.2. Experiments

We design a prototype of our scheme to evaluate its performance. Our experiments rely on the NTL Library (version 11.3.2) for matrix operation, lattice reduction, and SHA-256 for the hash algorithm. All experiments were conducted on a laptop running Windows 10 (x64) equipped with 3.20 GHz AMD Ryzen 7 5800H and 16 GB DDR4 RAM.The experiment takes the running time of the scheme as the evaluation basis, including KeyGen’s time, TagGen’s time, ProofGen’s time, and ProofVerify’s time, and mainly focuses on the relationship between the running time and system parametersn,q,m,k. Subsequently, comparisons will be made with two similar schemes [28, 30] and a BLS-based scheme [15], respectively. All results of experiments are representing 30 trials on average.First, we analyze the relationship between the running time of the scheme and the parameterm. It is the dimension of the lattice, determined by the security parameter n and the prime number q (i.e., m=6nlogq). It is also the length of each data block and signature, and the scheme’s security increases as m increases. We set the number of file blocks k=100; the experimental results are shown in Table 3. The running time of the scheme increases rapidly with the increase of m, and most of the time is spent on the algorithm TagGen. This is because TagGen needs to call the preimage sampling algorithm SamplePre. When the dimension of the lattice m increases, the computational complexity of performing lattice transformation and solving linear equations is much higher than other algorithms in the scheme.Table 3
The relationship between the running time of the scheme and the parameterm (k=100).
Algorithm’s time (s)KeyGenTagGenProofGenProofVerifyTotalm=32 (n=1, q=2560021)0.00213.7620.00810.00003143.7722314m=64 (n=2, q=2560021)0.006319.26760.01450.000064819.288465m=128 (n=4, q=2560021)0.0313125.01810.02510.0001594125.07466m=256 (n=8, q=2560021)0.1863896.0740.048670.0004037896.30937Second, we analyze the relationship between the running time of the scheme and the parameterk. The experimental results are shown in Figure 5.We set the system parameters n=1, q=2560021, and m=32. The running time of the scheme increases linearly with the number of file blocks k. The reason is that the running time is mainly consumed in the TagGen, and the number of signatures is determined by k.Figure 5
The relationship between the running time of the scheme and the parameterk (n=1, q=2560021, and m=32).Next, this scheme is compared with two similar schemes [28, 30]. The main difference between the three schemes is in ProofGen and ProofVerify. [28] uses the linear combination of data blocks and block tags as proof, namely, μ=∑i∈Ivimi and σ=∑i∈Iviσi; [30] randomly selects vectors r1 and r2, uses lattice theory to construct a random vector r satisfying
(11)rmodp=r1,ATrmodq=r2,and then uses r1 and r2 to hide the evidence
(12)μ=r1+μ′,σ=r+σ′.As shown in Table4, our scheme does not need to construct random vectors by solving equations, and the efficiency is significantly better than [30] in ProofGen and ProofVerify; due to the use of random masking technology, the running time of our scheme is comparable to that of [28] which has a slight increase but can provide privacy preservation with higher security.Table 4
Comparison of the running time between our scheme and [28, 30].
Algorithm’s time (s)KeyGenTagGenProofGenProofVerify[28]0.00243.62480.00610.0000177[30]0.00243.69120.20440.0000206Our scheme0.00223.64680.00650.0000193Finally, this scheme is compared with the BLS-based PDP scheme [15]. To achieve the same signature length of 160 bits as [15], we set k=100, n=5, q=2560021, and m=160. As shown in Table 5, although the efficiency of KeyGen and TagGen in our scheme is not as good as that of the scheme [15], ProofGen and ProofVerify take less time. The first two algorithms are completed before uploading data and only need to be run once. In comparison, the latter two algorithms need to be run for each verification, which is more important for the entire integrity verification, so our scheme verification is more efficient.Table 5
Comparison of the running time between our scheme and [15].
Algorithm’s time (s)KeyGenTagGenProofGenProofVerify[15]0.000020.42010.10290.0035Our scheme0.0313125.01810.02510.00016


## 5.1. Comparative Analysis

This paper proposed a post-quantum privacy-preserving provable data possession scheme based on smart contracts that can verify whether the CSP holds all user data, and it is secure under the random oracle model. We compared our scheme with similar methods along five dimensions: post quantum, public verification, privacy-preserving, noninteractive, and fair payment. Table2 shows that our scheme has significant advantages over other schemes.Table 2
Comparison of the characteristics of schemes.
[15][17][19][28][30]Our schemePost quantum×××√√√Public verification√√√√√√Privacy-preserving××√×√√Noninteractive√×√××√Fair payment√×√××√


## 5.2. Experiments

We design a prototype of our scheme to evaluate its performance. Our experiments rely on the NTL Library (version 11.3.2) for matrix operation, lattice reduction, and SHA-256 for the hash algorithm. All experiments were conducted on a laptop running Windows 10 (x64) equipped with 3.20 GHz AMD Ryzen 7 5800H and 16 GB DDR4 RAM.The experiment takes the running time of the scheme as the evaluation basis, including KeyGen’s time, TagGen’s time, ProofGen’s time, and ProofVerify’s time, and mainly focuses on the relationship between the running time and system parametersn,q,m,k. Subsequently, comparisons will be made with two similar schemes [28, 30] and a BLS-based scheme [15], respectively. All results of experiments are representing 30 trials on average.First, we analyze the relationship between the running time of the scheme and the parameterm. It is the dimension of the lattice, determined by the security parameter n and the prime number q (i.e., m=6nlogq). It is also the length of each data block and signature, and the scheme’s security increases as m increases. We set the number of file blocks k=100; the experimental results are shown in Table 3. The running time of the scheme increases rapidly with the increase of m, and most of the time is spent on the algorithm TagGen. This is because TagGen needs to call the preimage sampling algorithm SamplePre. When the dimension of the lattice m increases, the computational complexity of performing lattice transformation and solving linear equations is much higher than other algorithms in the scheme.Table 3
The relationship between the running time of the scheme and the parameterm (k=100).
Algorithm’s time (s)KeyGenTagGenProofGenProofVerifyTotalm=32 (n=1, q=2560021)0.00213.7620.00810.00003143.7722314m=64 (n=2, q=2560021)0.006319.26760.01450.000064819.288465m=128 (n=4, q=2560021)0.0313125.01810.02510.0001594125.07466m=256 (n=8, q=2560021)0.1863896.0740.048670.0004037896.30937Second, we analyze the relationship between the running time of the scheme and the parameterk. The experimental results are shown in Figure 5.We set the system parameters n=1, q=2560021, and m=32. The running time of the scheme increases linearly with the number of file blocks k. The reason is that the running time is mainly consumed in the TagGen, and the number of signatures is determined by k.Figure 5
The relationship between the running time of the scheme and the parameterk (n=1, q=2560021, and m=32).Next, this scheme is compared with two similar schemes [28, 30]. The main difference between the three schemes is in ProofGen and ProofVerify. [28] uses the linear combination of data blocks and block tags as proof, namely, μ=∑i∈Ivimi and σ=∑i∈Iviσi; [30] randomly selects vectors r1 and r2, uses lattice theory to construct a random vector r satisfying
(11)rmodp=r1,ATrmodq=r2,and then uses r1 and r2 to hide the evidence
(12)μ=r1+μ′,σ=r+σ′.As shown in Table4, our scheme does not need to construct random vectors by solving equations, and the efficiency is significantly better than [30] in ProofGen and ProofVerify; due to the use of random masking technology, the running time of our scheme is comparable to that of [28] which has a slight increase but can provide privacy preservation with higher security.Table 4
Comparison of the running time between our scheme and [28, 30].
Algorithm’s time (s)KeyGenTagGenProofGenProofVerify[28]0.00243.62480.00610.0000177[30]0.00243.69120.20440.0000206Our scheme0.00223.64680.00650.0000193Finally, this scheme is compared with the BLS-based PDP scheme [15]. To achieve the same signature length of 160 bits as [15], we set k=100, n=5, q=2560021, and m=160. As shown in Table 5, although the efficiency of KeyGen and TagGen in our scheme is not as good as that of the scheme [15], ProofGen and ProofVerify take less time. The first two algorithms are completed before uploading data and only need to be run once. In comparison, the latter two algorithms need to be run for each verification, which is more important for the entire integrity verification, so our scheme verification is more efficient.Table 5
Comparison of the running time between our scheme and [15].
Algorithm’s time (s)KeyGenTagGenProofGenProofVerify[15]0.000020.42010.10290.0035Our scheme0.0313125.01810.02510.00016


## 6. Conclusion

This paper designed a post-quantum privacy-preserving PDP protocol and used it to propose a scheme to this end based on smart contracts. The proposed scheme has the characteristics of being post quantum and is capable of public verification and privacy preservation. The noninteractive nature of the protocol can reduce the cost of blockchain transactions, and the smart contract with the deposit mechanism can ensure fair payments to all parties. In addition, the scheme’s efficiency is reflected in the fact that it mainly uses linear operations, thus avoiding a large number of modular exponential and bilinear pairing operations in the traditional method that can significantly reduce the amount of calculation and improve the efficiency of verification. The main bottleneck of the current lattice-based PDP scheme is that the signature process is slow, and the key and signature in the proposed scheme are long. Future research in the area should focus on ways to solve these problems.



---

*Source: 8772700-2023-02-02.xml*