# Blockchain-Based Secure Outsourcing of Polynomial Multiplication and Its Application in Fully Homomorphic Encryption

Authors: Mingyang Song; Yingpeng Sang; Yuying Zeng; Shunchao Luo
Journal: Security and Communication Networks
 (2021)

---

## Abstract

The efficiency of fully homomorphic encryption has always affected its practicality. With the dawn of Internet of things, the demand for computation and encryption on resource-constrained devices is increasing. Complex cryptographic computing is a major burden for those devices, while outsourcing can provide great convenience for them. In this paper, we firstly propose a generic blockchain-based framework for secure computation outsourcing and then propose an algorithm for secure outsourcing of polynomial multiplication into the blockchain. Our algorithm for polynomial multiplication can reduce the local computation cost toOn. Previous work based on Fast Fourier Transform can only achieve Onlogn for the local cost. Finally, we integrate the two secure outsourcing schemes for polynomial multiplication and modular exponentiation into the fully homomorphic encryption using hidden ideal lattice and get an outsourcing scheme of fully homomorphic encryption. Through security analysis, our schemes achieve the goals of privacy protection against passive attackers and cheating detection against active attackers. Experiments also demonstrate our schemes are more efficient in comparisons with the corresponding nonoutsourcing schemes.


---

## Body

## 1. Introduction

As the development of the big data era, there is an increasing demand for large-scale time-consuming computations. Fortunately, with the emergence of cloud computing, computation outsourcing brings convenience to resource-constrained users. They can outsource complex computing tasks into the cloud by paying a fee and avoiding buying expensive high-performance hardware. It not only improves the resource utilization in cloud but also brings economic benefits to resource-constrained users. Nevertheless, the attractive computing scheme also causes security issues. A passive attacker in the cloud may be only curious about the privacy contained in the user’s outsourced data, while an active attacker may make malicious damage or forge the results to sabotage the computation. Even if there is no attacker, computing errors caused by cloud hardware failure and software errors, etc. should also be considered. Furthermore, it should not be a great burden for the user to check the correctness of the returned results from the cloud; otherwise, the efficiency benefit of outsourcing will be nullified. Therefore, the secure and efficient outsourcing of computations that can not only protect the privacy of users but also ensure the correct results has become a hot research topic.Gentry proposed a homomorphic encryption algorithm based on ideal lattice [1] for the first time, providing us with a direction to solve the privacy issues in computation outsourcing. The direction is a secure computation outsourcing mode: encryption-outsourcing-decryption (EOD). Even if we use the common EOD model, the device should also undertake the computations of secret key generation, encryption, verification, decryption, and so on, locally. These computations are also great burden for the resource-constrained devices (such as mobile phones and IoT nodes).Blockchain has attractive features such as transparency, traceability, decentralization, and immutability, which make it an optimal approach for applications intrinsically with untrusted natures, such as computation outsourcing. A central trusted entity is not required for the computation outsourcing based on blockchain. Information about the whole data exchange process, computations, users, and computational nodes is recorded and is traceable in blockchain. Besides, smart contract can be utilized to digitally facilitate the implementation of whole transaction, which greatly improves the speed of building applications on blockchain. However, privacy is still an issue in the computation outsourcing based on blockchain.Owing to the low efficiency of fully homomorphic encryption algorithms, the general computation outsourcing mode based on EOD is impractical on the resource-constrained devices. In this paper, we will outsource some complex computations in the fully homomorphic encryption using hidden ideal lattice (FHEHIL) [2] into a blockchain framework. The contributions of this paper can be summarized as follows:(1)
We propose a framework of blockchain-based computation outsourcing, in which we can implement secure outsourcing for FHEHIL. The framework has a credit-based task allocation strategy, which will significantly reduce the probability of malicious nodes participating in computing.(2)
We propose a secure outsourcing algorithm for polynomial multiplication, which reduces the local computation cost (including the cost on result verification) toOn. Previous work based on the Fast Fourier Transform (FFT) can only achieve Onlogn for the local cost. Besides, the algorithm can not only detect cheating but also identify cheating nodes combining with blockchain. The result verification in the outsourcing algorithm does not cause extra burden.(3)
We also extend the secure outsourcing algorithm of modular exponentiation, in [3], in our blockchain-based framework. The two algorithms for polynomial multiplication and modular exponentiation are employed in FHEHIL as basic operations, and the FHEHIL implementation on the blockchain-based framework can have higher efficiency compared with previous work.


## 2. Related Work

At present, research studies on secure outsourcing can be roughly divided into two directions. In one direction, a general outsourcing mechanism is studied. In this mechanism, a fully homomorphic encryption algorithm is designed and the EOD model is used to outsource any computations. After the work of Gennaro et al. [1], great progress has been made in the field of fully homomorphic encryption [4–6]. However, the fully homomorphic encryption algorithms have high computational complexity. Recently, there are many researches to reduce the computation cost of homomorphic encryption algorithm. For example, Su et al. accelerated the leveled Ring-LWE fully homomorphic encryption [7]. These research studies mainly focus on the efficiency of hardware. However, secure outsourcing complex computations of fully homomorphic encryption is a better way to improve efficiency for resource-constrained devices.In the other direction, specific outsourcing algorithms are designed for various scientific computations, e g., modular exponentiation, solution of large-scale linear equations [8], bilinear pairings, and extend Euclidean. The Wei pairing and Tate pairing in algebraic curves are commonly used in key establishment and signature schemes in the field of cryptography. However, the computation of bilinear pairings is time-consuming in resource-constrained devices. Thus, many outsourcing schemes have been proposed [9–11]. To our knowledge, the scheme in [9] is the most efficient and secure till now. Because of the wide application in cryptography, the study on modular exponentiation is also a hot topic of research. Hohenberger and Lysyanskaya [12] proposed a modular exponentiation secure outsourcing scheme. Chen et al. [13] further improved its efficiency and verifiability. Ren et al. [14] proposed a scheme that only protects the privacy of exponent. Recently, Fu et al. [3] proposed a secure outsourcing scheme of modular exponentiation with hidden exponent and base. It has a stronger checkability. In cryptography, extended Euclidean algorithm is usually used to calculate modular inverse, which is widely used in RSA encryption algorithm. Similarly, Euclidean algorithm can be used to find the greatest common factor of two polynomials, which is commonly used in encryption algorithm based on Lattice. Zhou et al. [15] proposed the secure outsourcing algorithm of extended Euclidean algorithm.Polynomial multiplication is likewise a commonly used operation in cryptography schemes, error correcting codes, and computer algebra. The complexity of polynomial multiplication is still a major open problem. Using the FFT, the local computation of polynomial multiplication can achieve the complexity ofOnlogn. Recently, some efficient polynomial multiplication methods based on the FFT are proposed. Harvey et al. proposed a faster method over finite fields Zp when the degree of polynomials is less than p [16]. The efficiency has been further improved in [17]. For the hardware utilization, Liu et al. designed a high hardware efficiency polynomial multiplication on field-programmable gate array (FPGA) platform [18]. Hsu and Shieh proposed a method with less addition and multiplication [19] in 2020. Besides, there are also some research studies on reducing the space complexity of polynomial multiplication [20, 21]. However, the complexity of some research studies based on the acceleration of FFT remains at Onlogn. Other methods using distributed computing to improve hardware utilization are not applied to the resource-constrained device. Till now, there are few research studies on the secure outsourcing of polynomial multiplication.Due to the characteristics of the blockchain and Bitcoin [22], there are lots of research studies and applications on blockchain in recent years including the secure outsourcing. Lin et al. studied the secure outsourcing for bilinear pairings based on blockchain [23]. Zheng et al. [24] proposed a secure outsourcing scheme for attribute-based encryption on blockchain. There are also some schemes [25, 26] of outsourced data integrity verification. The fairness problem in blockchain-based secure multiparty computation was also solved by multiple efforts. For example, Gao et al. [27] proposed a scheme which realized fairness by maintaining an open reputation system. This type of general scheme for secure multiparty computation can be cumbersome for the problems in secure outsourcing computation.Andrychowicz et al. [28] utilized only scripts in Bitcoin currency to construct a fair protocol for secure multiparty lotteries, without relying on a trusted third party. Zhang et al. proposed BCPay in [29] and BPay in [30] to achieve fair payment for blockchain-based outsourcing services, which are compatible with the Bitcoin and Ethereum platforms. However, these frameworks can only provide fairness between the client and a single server. They are applicable to the outsourcing scenarios where the task is outsourced to a single server from the client. In the problem of our work, the computation task needs to be outsourced to multiple computational nodes simultaneously. Therefore, we propose a new one, considering the penalty on the cheating nodes, compensation on the honest nodes, and application of a credit-based scheme.


## 3. Notations and Background

### 3.1. Notations

We use upper case bold letters for matrices anddetM for the determinant of matrix M. Lower case bold letters represent vectors (eg., v=v1,…,vn), where vi is the ith element in v. We denote polynomial by lower case italics (eg., fx). For a rational number r, roundr represents the nearest integer to r. The rational vector v can also be rounded to roundv=roundv1,…,roundvn. We use vx for the polynomial form of the vector v. We use v1×v2 for polynomial multiplication (v1×v2=v1x×v2xmodfx) on the ring. We use v for the norm of v and S for the base of set S. We use v∘w for correlation (v∘w=v1∗w1,…,wn). We use Rv,f for the rotation matrix of v whose ith row is the coefficients of vx×xi−1modfx. We use xgcdax,bx for the extended Euclidean algorithm on ax and bx. degfx represents the degree of fx. We use Fv to denote the coefficient set of Discrete Fourier transform (DFT) of v and Fv− for the coefficient set of inverse DFT of v.


### 3.2. Fully Homomorphic Encryption Using Hidden Ideal Lattice

The FHEHIL scheme [2] is described in Algorithm 1, including the components of key generation, encryption, and decryption. The related parameters are shown in Table 1.As shown in Algorithm1, it is obvious that polynomial multiplication is the primary computation in encryption and decryption. Therefore, our proposed algorithm for the secure outsourcing of polynomial multiplication can be directly applied. As for the key generation, the computing burden is from Step 7, 9, and 11. The main computational cost of Step 7 is on computing the determinant of matrix V. The most time-consuming operation in Step 9 is polynomial multiplication. Step 11 computes the inverse of polynomial. Below, we will analyze the detailed computations in Step 7 and 11 and demonstrate that polynomial multiplication and modular exponentiation are the main types of computations, which are the two improvement aims of this paper.


#### 3.2.1. The Method of Computingd in Algorithm 1

Because of the characteristic ofV, computing the determinant of matrix V needs only logn times of polynomial multiplication using the method in [31]. d is the free item of gz=∏i−0n−1vpi−z. Thus, d=∏i=0n−1vpi, where pi is the root of fx=0 in the complex domain and they satisfy equation (2). Due to equation (2), we have d=∏i=0n−1vpi=∏i=0n/2−1vpiv−pi=∏i=0n/2−1api. Thus, the computation of d mainly involves polynomial multiplications and modular exponentiations.


#### 3.2.2. The Method of Computingw in Algorithm 1 When d Is a Prime

In the algorithm of FHEHIL, ifd is a prime, we can obtain w by performing xgcdv,f once. The extended Euclidean algorithm computes xgcdax,bx to get ux, vx, and dx, satisfying ux×ax+vx×bx=dx. The specific procedures of secure outsourcing for extended Euclidean algorithm [15] are summarized in Algorithm 2. It can be seen that the local computations of this algorithm consist of mostly modular exponentiation and polynomial multiplications. Detailed analysis of Algorithm 2 can be found in [15].


#### 3.2.3. The Method of Computingw in Algorithm 1 When d Is Not a Prime

Whend is not a prime, the fastest method to calculate polynomial inverse at present is Gentry’s method in [31]. The method is based on fast Fourier transform and halves the number of terms in each step to offset the doubling of the bit length of the coefficients. This method relays on fx=xn+1, where n is a power of 2. The method is analyzed as follows.Firstly, the second coefficientg1 of polynomial gz=∏i=0n−1vpi−z can be computed, where pi is the ith root of fx=0 in the complex domain. We can get w0=g1/n. Secondly, v′x=x×vxmodfx can be constructed. Then, the second coefficient g1′) of polynomial g′z=∏i=0n−1v′pi−z can be computed. We can get w1=g1′/n. Finally, other coefficients of w can be computed by(1)w1w0=w2w1=⋯=wn−1wn−2,(2)pi+nj22i=−pi2inj=n2j.Sincen is a power of 2 in fx, the roots satisfy equation (2). In the process of computing coefficients g1 and g1′, the major computations are also polynomial multiplications and modular exponentiations.Algorithm 1: Fully homomorphic encryption using hidden ideal lattice.
Input:ζ, γ, η, t, nOutput:SK=d,w, PK=p1,…,pt(1)
function KEY GENERARTION ζ,γ,η,t,n(2)
generate a random vectorv satisfying v∈Zn,2γ−1<v<2γ,∑i=0n−1vimod2=1(3)
generatet − 1 random vectors g1,…gt−1 satisfying gi∈Zn,2n−1<gi<2n(4)
generate a random vectorgt satisfying gt∈Zn,gi<2n,∑i−0n−1gtimod2=1(5)
generatet − 1 random vectors r1,…,rt−1 satisfying ri∈0,1,−1n,ri<ζ(6)
generate a random vectorrt satisfying rt∈0,1,−1n,rt<ζ,∑i=0n−1rtimod2=1(7)
fx⟵xn+1;V⟵Rv,f;d⟵detV(8)
fori=1⟶tdo(9)
pi⟵gi×v+ri(10)
end for(11)
Getw satisfying w×v = d mod f(12)
returnSK=d,w,PK=p1,…,pt(13)
end return(14)
function ENCRYPTION PK=p1,…,pt,plaintext(15)
generatet − 1 random integer vectors s1,…,st−1 satisfying ∑j=0n−1sijmod2=0(16)
generate a random vectorst satisfying ∑j=0n−1stjmod2=plaintext(17)
generate a random vectorst+1 satisfying ∑j=0n−1st+1jmod2=0(18)
ψ⟵∑i=1tsi×pi+st+1(19)
returnψ(20)
end function(21)
function DECRYPTION SK=d,w,ψ(22)
ψ′⟵roundψ×w/d(23)
plaintext⟵ψ′1mod2(24)
return plaintext(25)
end functionTable 1
Parameters in the FHEHIL algorithm.
ParametersImplicationζThe norm of random noise vectorγThe bit length of norm of generating polynomialηThe bit length of norm of the random multiplier vectortThe number of vectors contained in the public keynThe dimension of the hidden lattice (power of 2)


## 3.1. Notations

We use upper case bold letters for matrices anddetM for the determinant of matrix M. Lower case bold letters represent vectors (eg., v=v1,…,vn), where vi is the ith element in v. We denote polynomial by lower case italics (eg., fx). For a rational number r, roundr represents the nearest integer to r. The rational vector v can also be rounded to roundv=roundv1,…,roundvn. We use vx for the polynomial form of the vector v. We use v1×v2 for polynomial multiplication (v1×v2=v1x×v2xmodfx) on the ring. We use v for the norm of v and S for the base of set S. We use v∘w for correlation (v∘w=v1∗w1,…,wn). We use Rv,f for the rotation matrix of v whose ith row is the coefficients of vx×xi−1modfx. We use xgcdax,bx for the extended Euclidean algorithm on ax and bx. degfx represents the degree of fx. We use Fv to denote the coefficient set of Discrete Fourier transform (DFT) of v and Fv− for the coefficient set of inverse DFT of v.


## 3.2. Fully Homomorphic Encryption Using Hidden Ideal Lattice

The FHEHIL scheme [2] is described in Algorithm 1, including the components of key generation, encryption, and decryption. The related parameters are shown in Table 1.As shown in Algorithm1, it is obvious that polynomial multiplication is the primary computation in encryption and decryption. Therefore, our proposed algorithm for the secure outsourcing of polynomial multiplication can be directly applied. As for the key generation, the computing burden is from Step 7, 9, and 11. The main computational cost of Step 7 is on computing the determinant of matrix V. The most time-consuming operation in Step 9 is polynomial multiplication. Step 11 computes the inverse of polynomial. Below, we will analyze the detailed computations in Step 7 and 11 and demonstrate that polynomial multiplication and modular exponentiation are the main types of computations, which are the two improvement aims of this paper.


### 3.2.1. The Method of Computingd in Algorithm 1

Because of the characteristic ofV, computing the determinant of matrix V needs only logn times of polynomial multiplication using the method in [31]. d is the free item of gz=∏i−0n−1vpi−z. Thus, d=∏i=0n−1vpi, where pi is the root of fx=0 in the complex domain and they satisfy equation (2). Due to equation (2), we have d=∏i=0n−1vpi=∏i=0n/2−1vpiv−pi=∏i=0n/2−1api. Thus, the computation of d mainly involves polynomial multiplications and modular exponentiations.


### 3.2.2. The Method of Computingw in Algorithm 1 When d Is a Prime

In the algorithm of FHEHIL, ifd is a prime, we can obtain w by performing xgcdv,f once. The extended Euclidean algorithm computes xgcdax,bx to get ux, vx, and dx, satisfying ux×ax+vx×bx=dx. The specific procedures of secure outsourcing for extended Euclidean algorithm [15] are summarized in Algorithm 2. It can be seen that the local computations of this algorithm consist of mostly modular exponentiation and polynomial multiplications. Detailed analysis of Algorithm 2 can be found in [15].


### 3.2.3. The Method of Computingw in Algorithm 1 When d Is Not a Prime

Whend is not a prime, the fastest method to calculate polynomial inverse at present is Gentry’s method in [31]. The method is based on fast Fourier transform and halves the number of terms in each step to offset the doubling of the bit length of the coefficients. This method relays on fx=xn+1, where n is a power of 2. The method is analyzed as follows.Firstly, the second coefficientg1 of polynomial gz=∏i=0n−1vpi−z can be computed, where pi is the ith root of fx=0 in the complex domain. We can get w0=g1/n. Secondly, v′x=x×vxmodfx can be constructed. Then, the second coefficient g1′) of polynomial g′z=∏i=0n−1v′pi−z can be computed. We can get w1=g1′/n. Finally, other coefficients of w can be computed by(1)w1w0=w2w1=⋯=wn−1wn−2,(2)pi+nj22i=−pi2inj=n2j.Sincen is a power of 2 in fx, the roots satisfy equation (2). In the process of computing coefficients g1 and g1′, the major computations are also polynomial multiplications and modular exponentiations.Algorithm 1: Fully homomorphic encryption using hidden ideal lattice.
Input:ζ, γ, η, t, nOutput:SK=d,w, PK=p1,…,pt(1)
function KEY GENERARTION ζ,γ,η,t,n(2)
generate a random vectorv satisfying v∈Zn,2γ−1<v<2γ,∑i=0n−1vimod2=1(3)
generatet − 1 random vectors g1,…gt−1 satisfying gi∈Zn,2n−1<gi<2n(4)
generate a random vectorgt satisfying gt∈Zn,gi<2n,∑i−0n−1gtimod2=1(5)
generatet − 1 random vectors r1,…,rt−1 satisfying ri∈0,1,−1n,ri<ζ(6)
generate a random vectorrt satisfying rt∈0,1,−1n,rt<ζ,∑i=0n−1rtimod2=1(7)
fx⟵xn+1;V⟵Rv,f;d⟵detV(8)
fori=1⟶tdo(9)
pi⟵gi×v+ri(10)
end for(11)
Getw satisfying w×v = d mod f(12)
returnSK=d,w,PK=p1,…,pt(13)
end return(14)
function ENCRYPTION PK=p1,…,pt,plaintext(15)
generatet − 1 random integer vectors s1,…,st−1 satisfying ∑j=0n−1sijmod2=0(16)
generate a random vectorst satisfying ∑j=0n−1stjmod2=plaintext(17)
generate a random vectorst+1 satisfying ∑j=0n−1st+1jmod2=0(18)
ψ⟵∑i=1tsi×pi+st+1(19)
returnψ(20)
end function(21)
function DECRYPTION SK=d,w,ψ(22)
ψ′⟵roundψ×w/d(23)
plaintext⟵ψ′1mod2(24)
return plaintext(25)
end functionTable 1
Parameters in the FHEHIL algorithm.
ParametersImplicationζThe norm of random noise vectorγThe bit length of norm of generating polynomialηThe bit length of norm of the random multiplier vectortThe number of vectors contained in the public keynThe dimension of the hidden lattice (power of 2)


## 3.2.1. The Method of Computingd in Algorithm 1

Because of the characteristic ofV, computing the determinant of matrix V needs only logn times of polynomial multiplication using the method in [31]. d is the free item of gz=∏i−0n−1vpi−z. Thus, d=∏i=0n−1vpi, where pi is the root of fx=0 in the complex domain and they satisfy equation (2). Due to equation (2), we have d=∏i=0n−1vpi=∏i=0n/2−1vpiv−pi=∏i=0n/2−1api. Thus, the computation of d mainly involves polynomial multiplications and modular exponentiations.


## 3.2.2. The Method of Computingw in Algorithm 1 When d Is a Prime

In the algorithm of FHEHIL, ifd is a prime, we can obtain w by performing xgcdv,f once. The extended Euclidean algorithm computes xgcdax,bx to get ux, vx, and dx, satisfying ux×ax+vx×bx=dx. The specific procedures of secure outsourcing for extended Euclidean algorithm [15] are summarized in Algorithm 2. It can be seen that the local computations of this algorithm consist of mostly modular exponentiation and polynomial multiplications. Detailed analysis of Algorithm 2 can be found in [15].


## 3.2.3. The Method of Computingw in Algorithm 1 When d Is Not a Prime

Whend is not a prime, the fastest method to calculate polynomial inverse at present is Gentry’s method in [31]. The method is based on fast Fourier transform and halves the number of terms in each step to offset the doubling of the bit length of the coefficients. This method relays on fx=xn+1, where n is a power of 2. The method is analyzed as follows.Firstly, the second coefficientg1 of polynomial gz=∏i=0n−1vpi−z can be computed, where pi is the ith root of fx=0 in the complex domain. We can get w0=g1/n. Secondly, v′x=x×vxmodfx can be constructed. Then, the second coefficient g1′) of polynomial g′z=∏i=0n−1v′pi−z can be computed. We can get w1=g1′/n. Finally, other coefficients of w can be computed by(1)w1w0=w2w1=⋯=wn−1wn−2,(2)pi+nj22i=−pi2inj=n2j.Sincen is a power of 2 in fx, the roots satisfy equation (2). In the process of computing coefficients g1 and g1′, the major computations are also polynomial multiplications and modular exponentiations.Algorithm 1: Fully homomorphic encryption using hidden ideal lattice.
Input:ζ, γ, η, t, nOutput:SK=d,w, PK=p1,…,pt(1)
function KEY GENERARTION ζ,γ,η,t,n(2)
generate a random vectorv satisfying v∈Zn,2γ−1<v<2γ,∑i=0n−1vimod2=1(3)
generatet − 1 random vectors g1,…gt−1 satisfying gi∈Zn,2n−1<gi<2n(4)
generate a random vectorgt satisfying gt∈Zn,gi<2n,∑i−0n−1gtimod2=1(5)
generatet − 1 random vectors r1,…,rt−1 satisfying ri∈0,1,−1n,ri<ζ(6)
generate a random vectorrt satisfying rt∈0,1,−1n,rt<ζ,∑i=0n−1rtimod2=1(7)
fx⟵xn+1;V⟵Rv,f;d⟵detV(8)
fori=1⟶tdo(9)
pi⟵gi×v+ri(10)
end for(11)
Getw satisfying w×v = d mod f(12)
returnSK=d,w,PK=p1,…,pt(13)
end return(14)
function ENCRYPTION PK=p1,…,pt,plaintext(15)
generatet − 1 random integer vectors s1,…,st−1 satisfying ∑j=0n−1sijmod2=0(16)
generate a random vectorst satisfying ∑j=0n−1stjmod2=plaintext(17)
generate a random vectorst+1 satisfying ∑j=0n−1st+1jmod2=0(18)
ψ⟵∑i=1tsi×pi+st+1(19)
returnψ(20)
end function(21)
function DECRYPTION SK=d,w,ψ(22)
ψ′⟵roundψ×w/d(23)
plaintext⟵ψ′1mod2(24)
return plaintext(25)
end functionTable 1
Parameters in the FHEHIL algorithm.
ParametersImplicationζThe norm of random noise vectorγThe bit length of norm of generating polynomialηThe bit length of norm of the random multiplier vectortThe number of vectors contained in the public keynThe dimension of the hidden lattice (power of 2)


## 4. The Framework of Blockchain-Based Computation Outsourcing

This section introduces a blockchain-based computation outsourcing framework. The overall system model is illustrated in Figure1, and the related symbols are described in Table 2. In Figure 1, we assume that, at least, one trusted third party is available to implement the smart contract. This is a generic model on which a variety of computational tasks can be implemented, including the tasks of secure outsourcing of polynomial multiplication and modular exponentiation. The two specific tasks will be given in details in the rest of this paper.


### 4.1. Registration

Users and computational nodes need to register before joining the network. They need to pay deposits in advance, the amount of which needs to be greater than a specified threshold or they will be rejected. The smart contract initializes the same credit score to all new nodes and users. After registration, information of users and computational nodes is written to the smart contract. The specific function is shown as Algorithm3. In this algorithm, addr[p] is the deposit account of node p in the smart contract. Node p’s asset privacy is protected because it is unnecessary for him to expose his total asset to the smart contract.Algorithm 2: Securely outsource the extended Euclidean algorithm.
Input:ax, bxOutput:vx, vx, dx(1)
generaterx and a∈Z randomly(2)
fx⟵aαx,gαx⟵bx(3)
a′x⟵rx×fx,b′x⟵rx×gx(4)
a″x⟵u11x×a′x+u12x×b′x,b″x⟵u21x×a′x+u22xb′x(5)
senda″xandb″x to computational node(6)
getu″x,v″xandd″x from computational mode(7)
verifya″x×u″x+b″x×v″x=d″x;degu″x<degb″x/d″x;degv″x<dega″x/d″x;(8)
ux⟵αdegd″x−degrxu11α−1x×u″α−1x+u21α−1x×v″α−1x(9)
vx⟵αdegd″x−degrxu12α−1x×u″α−1x+u22α−1x×v″α−1x(10)
dx⟵αdegd″x−degrxd″α−1x/rα−1xFigure 1
The framework of blockchain-based computation outsourcing.Table 2
Symbols in the framework of blockchain-based computation outsourcing.
SymbolImplicationaddrpThe account address ofpUser/nodeThe set of users/computational nodesReppThe reputation ofpTaskThe queue of published tasksAllocatedThe queue of allocated tasksDataThe queue of published dataTimeThe set of the latest result return timeDishonest/honestThe set of dishonest/honest nodesResultThe set of resultsΔbThe amount of economic punishmentΔcThe amount of credit punishment/rewardΔtThe longest computing time consumptionAlgorithm 3: Registration.
(1)
function Registration(p, role)(2)
if the balance of addr[p] ≥ the threshold then(3)
if role = user then(4)
put addr[p] into User(5)
else(6)
put addr[p] into Node(7)
end if(8)
Rep[p] ⟵ Default credit value; state ⟵ true(9)
else(10)
state ⟵ false(11)
end if(12)
return false(13)
end function


### 4.2. Computational Service

Userp posts computing tasks, data, and rewards of each task to the smart contract. If the account balance of p is insufficient for the computations, smart contract refuses this service and reduces the credit score of p, to prevent malicious users from attacking the smart contract by constantly sending tasks that they cannot afford to. After the smart contract accepts the tasks of p, the user’s computing tasks are stored in the task queue and wait for the selection of computational nodes.To achieve a high benefit, the computational nodes will be active to undertake computing tasks. If multiple computational nodes select the same task at the same time, the node with the highest credit score will win the task. Nodes that undertake the computing task should submit the results after completing. If any computational node cannot finish on time, it will be added to the dishonest set. If all computational nodes can submit the results on time, the smart contract sends the results to user and initiates the period of dispute resolving. During this period, the user needs to verify the results locally and notify the smart contract whether the results are accepted or not. If the period of dispute ends and there is no feedback received from the user, the smart contract assumes that the computations succeed and performs the reward and charge operations. If the user does not accept the results in the feedback, the smart contract will verify the results by itself. The specific function is shown as Algorithm4.Algorithm 4: Computational service.
(1)
function TASK UPLOAD (user, tasks, data, price)(2)
if the balance of addr[user] ≥ |tasks| ∗ price then(3)
put tasks into Task; put data into Data(4)
else(5)
Rep[user]⟵Rep[user] − ∆c(6)
end if(7)
end function(8)
function TASK ALLOCATION (nodes, task)(9)
if task ≠ ALLOCATED then(10)
sort the nodes with their credit descending; send task and Data[task] to nodes [0](11)
put task into ALLOCATED; Time[task]⟵current time + ∆t(12)
end if(13)
end function(14)
function RESULT UPLOAD (node, task, result)(15)
if current time < Time[task] then(16)
put node into Honest; Put result into result(17)
else(18)
put node into Dinhonest(19)
end if(20)
end function(21)
function RESULT UPLOAD(node, task, result)(22)
if Dishonest = 0 and |Result| = |Task| then(23)
send Result to user; Wait for the feedback from user(24)
end if(25)
call verification and payment(26)
end function


### 4.3. Verification and Payment

If the user does not accept the computing results, the smart contract will perform verification operations to find dishonest nodes or users. In the verification, he will simulate all computations required by the user on the encrypted data uploaded by the latter. This means he will repeat exactly every step the computational nodes have carried out, so as to find which step is not correct and who is cheating. Decryptions are not required in the simulation, and thus, the data privacy of the user is protected.To complete the verification, the smart contract should be equipped with the same function modules as those of the computational nodes. For example, in the secure outsourcing of polynomial multiplication, a function should be added into the smart contract to simulate the FFT/IFFT operations on the data uploaded by the user in case of disputes.The dishonest nodes and users will be put into the dishonest set. If no one is put into the dishonest set, the user will pay the reward to all participating nodes. Otherwise, cheating nodes will be penalized and the honest nodes will be compensated. The credit score of the participating nodes that have correctly completed their tasks will increase, while the credit score of the malicious nodes will decrease. When the account balance of a node is lower than the threshold value or its credit score is reduced to zero, the system will remove it. The specific function is shown as Algorithm5.A malicious user with enough balance may constantly initiate transactions, aiming to increase the burden of the smart contract. However, he cannot refuse to pay because his deposit account is managed by the smart contract. By setting up a suitable threshold in the registration, sooner or later his balance will be used up by his attack.Algorithm 5: Verification and payment.
(1)
function VERIFICATION AND PAYMENT (feedback, Result, Honest, user, price)(2)
if feedback ≥ user or (feedback = NULL and |Result| = |Task|) then(3)
addr[user] ⟵ addr[user]-[Honest]∗price(4)
fori = 1⟶|Honest| do(5)
Rep[nodei] ⟵ Rep[nodei] + ∆c; addr[nodei]⟵addr[nodei] + price(6)
end for(7)
else(8)
stimulate all computations and put dishonest user or nodes intoDishonest(9)
t ⟵ ∆b∗[IDishonest](10)
fori = 1⟶|Dishonest| do(11)
Rep[nodei]⟵Rep[nodei] + ∆c; addr[nodei] ⟵ addr[nodei]−∆b(12)
end for(13)
fori = 1⟶|Honest|do(14)
Rep[nodei] ⟵ Rep[nodei] + ∆c; addr[nodei] ⟵ addr[nodei] + t/|Honest|(15)
end for(16)
end if(17)
end function


### 4.4. Security Analysis

Both the malicious user nodes and computational nodes can launch attacks to the framework, but their strategies are different. The malicious user nodes could launch a DDoS attack. A malicious computational node could destroy the computation by returning forged results or not returning any result.The user nodes could employ two ways to launch a DDoS attack. One is to continuously publish the tasks that the user actually cannot afford to; the other is to maliciously inform the smart contract that the results are not accepted during the dispute resolving period. For the first attack, the smart contract will refuse to add the computing tasks and data to the queue and reduce the credit score of the user. Moreover, when the node’s credit score drops below 0, the node will be removed. We can increaseΔc in the function of TASK UPLOAD to remove malicious users as soon as possible. For the second attack, the smart contract has to simulate the computations of all nodes participating in the outsourcing according to the data and records. This attack has a greater impact on the smart contract, but it brings more loss to the attackers (including the financial punishment). Similarly, we can increase Δb in Algorithm 5 to mitigate the impact on smart contracts.The computational nodes also have two ways to deploy attack: returning forged results or not returning any result. The cost of both attacks is the same (in financial and credit punishment). Since forged results render the smart contract to simulate the computations of all nodes, rational computational nodes prefer to attack by returning forged results, rather than return nothing. Similarly, we can increaseΔb and Δc in Algorithm 5 to mitigate the impact on smart contracts. The proposed framework adopts a task allocation strategy based on credit scores. When malicious nodes are found, their credit score is reduced, and their probability of obtaining computing tasks in the next time is also reduced. We assume there are enough computational nodes which are willing to return correct results to fulfil the requirement of outsourcing, under the incentives of achieving financial and credit reward.


### 4.5. Compatibility Analysis

We know that the Bitcoin script is not Turing-complete, and Ethereum has a complete programming language on the blockchain to execute more complex smart contracts. It is easy to see that our framework is compatible with opcodes allowed by the Ethereum blockchain. Since the function of Verification and Payment (Algorithm5) involves loops, which are not allowed by the Bitcoin script, our framework is not compatible with opcodes of the Bitcoin blockchain.


## 4.1. Registration

Users and computational nodes need to register before joining the network. They need to pay deposits in advance, the amount of which needs to be greater than a specified threshold or they will be rejected. The smart contract initializes the same credit score to all new nodes and users. After registration, information of users and computational nodes is written to the smart contract. The specific function is shown as Algorithm3. In this algorithm, addr[p] is the deposit account of node p in the smart contract. Node p’s asset privacy is protected because it is unnecessary for him to expose his total asset to the smart contract.Algorithm 2: Securely outsource the extended Euclidean algorithm.
Input:ax, bxOutput:vx, vx, dx(1)
generaterx and a∈Z randomly(2)
fx⟵aαx,gαx⟵bx(3)
a′x⟵rx×fx,b′x⟵rx×gx(4)
a″x⟵u11x×a′x+u12x×b′x,b″x⟵u21x×a′x+u22xb′x(5)
senda″xandb″x to computational node(6)
getu″x,v″xandd″x from computational mode(7)
verifya″x×u″x+b″x×v″x=d″x;degu″x<degb″x/d″x;degv″x<dega″x/d″x;(8)
ux⟵αdegd″x−degrxu11α−1x×u″α−1x+u21α−1x×v″α−1x(9)
vx⟵αdegd″x−degrxu12α−1x×u″α−1x+u22α−1x×v″α−1x(10)
dx⟵αdegd″x−degrxd″α−1x/rα−1xFigure 1
The framework of blockchain-based computation outsourcing.Table 2
Symbols in the framework of blockchain-based computation outsourcing.
SymbolImplicationaddrpThe account address ofpUser/nodeThe set of users/computational nodesReppThe reputation ofpTaskThe queue of published tasksAllocatedThe queue of allocated tasksDataThe queue of published dataTimeThe set of the latest result return timeDishonest/honestThe set of dishonest/honest nodesResultThe set of resultsΔbThe amount of economic punishmentΔcThe amount of credit punishment/rewardΔtThe longest computing time consumptionAlgorithm 3: Registration.
(1)
function Registration(p, role)(2)
if the balance of addr[p] ≥ the threshold then(3)
if role = user then(4)
put addr[p] into User(5)
else(6)
put addr[p] into Node(7)
end if(8)
Rep[p] ⟵ Default credit value; state ⟵ true(9)
else(10)
state ⟵ false(11)
end if(12)
return false(13)
end function


## 4.2. Computational Service

Userp posts computing tasks, data, and rewards of each task to the smart contract. If the account balance of p is insufficient for the computations, smart contract refuses this service and reduces the credit score of p, to prevent malicious users from attacking the smart contract by constantly sending tasks that they cannot afford to. After the smart contract accepts the tasks of p, the user’s computing tasks are stored in the task queue and wait for the selection of computational nodes.To achieve a high benefit, the computational nodes will be active to undertake computing tasks. If multiple computational nodes select the same task at the same time, the node with the highest credit score will win the task. Nodes that undertake the computing task should submit the results after completing. If any computational node cannot finish on time, it will be added to the dishonest set. If all computational nodes can submit the results on time, the smart contract sends the results to user and initiates the period of dispute resolving. During this period, the user needs to verify the results locally and notify the smart contract whether the results are accepted or not. If the period of dispute ends and there is no feedback received from the user, the smart contract assumes that the computations succeed and performs the reward and charge operations. If the user does not accept the results in the feedback, the smart contract will verify the results by itself. The specific function is shown as Algorithm4.Algorithm 4: Computational service.
(1)
function TASK UPLOAD (user, tasks, data, price)(2)
if the balance of addr[user] ≥ |tasks| ∗ price then(3)
put tasks into Task; put data into Data(4)
else(5)
Rep[user]⟵Rep[user] − ∆c(6)
end if(7)
end function(8)
function TASK ALLOCATION (nodes, task)(9)
if task ≠ ALLOCATED then(10)
sort the nodes with their credit descending; send task and Data[task] to nodes [0](11)
put task into ALLOCATED; Time[task]⟵current time + ∆t(12)
end if(13)
end function(14)
function RESULT UPLOAD (node, task, result)(15)
if current time < Time[task] then(16)
put node into Honest; Put result into result(17)
else(18)
put node into Dinhonest(19)
end if(20)
end function(21)
function RESULT UPLOAD(node, task, result)(22)
if Dishonest = 0 and |Result| = |Task| then(23)
send Result to user; Wait for the feedback from user(24)
end if(25)
call verification and payment(26)
end function


## 4.3. Verification and Payment

If the user does not accept the computing results, the smart contract will perform verification operations to find dishonest nodes or users. In the verification, he will simulate all computations required by the user on the encrypted data uploaded by the latter. This means he will repeat exactly every step the computational nodes have carried out, so as to find which step is not correct and who is cheating. Decryptions are not required in the simulation, and thus, the data privacy of the user is protected.To complete the verification, the smart contract should be equipped with the same function modules as those of the computational nodes. For example, in the secure outsourcing of polynomial multiplication, a function should be added into the smart contract to simulate the FFT/IFFT operations on the data uploaded by the user in case of disputes.The dishonest nodes and users will be put into the dishonest set. If no one is put into the dishonest set, the user will pay the reward to all participating nodes. Otherwise, cheating nodes will be penalized and the honest nodes will be compensated. The credit score of the participating nodes that have correctly completed their tasks will increase, while the credit score of the malicious nodes will decrease. When the account balance of a node is lower than the threshold value or its credit score is reduced to zero, the system will remove it. The specific function is shown as Algorithm5.A malicious user with enough balance may constantly initiate transactions, aiming to increase the burden of the smart contract. However, he cannot refuse to pay because his deposit account is managed by the smart contract. By setting up a suitable threshold in the registration, sooner or later his balance will be used up by his attack.Algorithm 5: Verification and payment.
(1)
function VERIFICATION AND PAYMENT (feedback, Result, Honest, user, price)(2)
if feedback ≥ user or (feedback = NULL and |Result| = |Task|) then(3)
addr[user] ⟵ addr[user]-[Honest]∗price(4)
fori = 1⟶|Honest| do(5)
Rep[nodei] ⟵ Rep[nodei] + ∆c; addr[nodei]⟵addr[nodei] + price(6)
end for(7)
else(8)
stimulate all computations and put dishonest user or nodes intoDishonest(9)
t ⟵ ∆b∗[IDishonest](10)
fori = 1⟶|Dishonest| do(11)
Rep[nodei]⟵Rep[nodei] + ∆c; addr[nodei] ⟵ addr[nodei]−∆b(12)
end for(13)
fori = 1⟶|Honest|do(14)
Rep[nodei] ⟵ Rep[nodei] + ∆c; addr[nodei] ⟵ addr[nodei] + t/|Honest|(15)
end for(16)
end if(17)
end function


## 4.4. Security Analysis

Both the malicious user nodes and computational nodes can launch attacks to the framework, but their strategies are different. The malicious user nodes could launch a DDoS attack. A malicious computational node could destroy the computation by returning forged results or not returning any result.The user nodes could employ two ways to launch a DDoS attack. One is to continuously publish the tasks that the user actually cannot afford to; the other is to maliciously inform the smart contract that the results are not accepted during the dispute resolving period. For the first attack, the smart contract will refuse to add the computing tasks and data to the queue and reduce the credit score of the user. Moreover, when the node’s credit score drops below 0, the node will be removed. We can increaseΔc in the function of TASK UPLOAD to remove malicious users as soon as possible. For the second attack, the smart contract has to simulate the computations of all nodes participating in the outsourcing according to the data and records. This attack has a greater impact on the smart contract, but it brings more loss to the attackers (including the financial punishment). Similarly, we can increase Δb in Algorithm 5 to mitigate the impact on smart contracts.The computational nodes also have two ways to deploy attack: returning forged results or not returning any result. The cost of both attacks is the same (in financial and credit punishment). Since forged results render the smart contract to simulate the computations of all nodes, rational computational nodes prefer to attack by returning forged results, rather than return nothing. Similarly, we can increaseΔb and Δc in Algorithm 5 to mitigate the impact on smart contracts. The proposed framework adopts a task allocation strategy based on credit scores. When malicious nodes are found, their credit score is reduced, and their probability of obtaining computing tasks in the next time is also reduced. We assume there are enough computational nodes which are willing to return correct results to fulfil the requirement of outsourcing, under the incentives of achieving financial and credit reward.


## 4.5. Compatibility Analysis

We know that the Bitcoin script is not Turing-complete, and Ethereum has a complete programming language on the blockchain to execute more complex smart contracts. It is easy to see that our framework is compatible with opcodes allowed by the Ethereum blockchain. Since the function of Verification and Payment (Algorithm5) involves loops, which are not allowed by the Bitcoin script, our framework is not compatible with opcodes of the Bitcoin blockchain.


## 5. Polynomial Multiplication and Modular Exponentiation Secure Outsourcing Algorithm

### 5.1. Polynomial Multiplication Secure Outsourcing Algorithm

The computational complexity of traditional polynomial multiplication isOn2, which is reduced to Onlogn by the FFT. In this section, we employ secure outsourcing to further reduce the local computational complexity to On. The outsourcing is implemented in our proposed framework of blockchain-based secure computation outsourcing. The main idea of our algorithm is as follows. Firstly, the Fourier transform of the polynomial coefficients are securely outsourced. Secondly, correlation operation on the results of the Fourier transform is locally performed. Finally, the inverse Fourier transform on result of the correlation operation are securely outsourced. The specific process of our algorithm is shown as Algorithm 6.


#### 5.1.1. Description

In Algorithm6, the input polynomials are fx=a0+a1x+⋯+an−1xn−1 and gx=b0+b1x+⋯+bn−1xn−1. The output is tx=fx×gx=c0+c1x+⋯+c2n−1x2n−1. For convenience, polynomials are replaced with vectors of polynomial coefficients (a=a0,a1,…,an−1, b=b0,b1,…,bn−1, and c=c0,c1,…,c2n−2). Besides, Wnm=e−2πjm/n, in this section. We use 6p computational nodes in this algorithm, where p is a parameter associated with the number of computational nodes. There are six steps in the algorithm:(1)
Six parameters are picked randomly, three of which arei,j,β,s.t.0≤n−1,0≤j≤n−1 and 0≤β≤2n−2. The other three are k1,k2,k3∈RZ. We define that Li,k,n:Z3⟶Zn can generate one n-dimensional vector in which the ith element is k, and all the other elements are zeros. We define that Tv,r:zn∗2⟶Zn∗p can generate a random matrix W=w1,w2,…,wp satisfying v=∑i=1pwi+r. Then, the user generates r1=Li,k1,n, r2=Lj,k2,n, r3=Lβ,k3,2n, V=Ta,r1, U=Ta,r1, Z=Tb,r2, and S=Tb,r2. In this way, one must know r1 to recover a from V or U and know r2 to recover b from Z or S.(2)
The user uploads the data (V, U, Z, and S) and task requirement (i.e., FFT) to smart contract, by the function TASK UPLOAD. The smart contract calls the function TASK ALLOCATION and distributes the vectors in V, U, Z, and S to Z and 4p computational nodes. After receiving the vectors, the computational nodes perform the Fourier transform on the received vectors and call the function RESULT UPLOAD. The smart contract collects the results and returns Fv1,…,Fvp, Fu1,…,Fup, Fz1,…,Fzp, and Fs1,…,Fsp to the user by calling the function RETURN RESULT. Meanwhile, the user locally computes Fr1Fr2 and Fr1- which are Fourier transform of r1 and r2 and inverse Fourier transform of r3, respectively. Because there is only one nonzero coefficient in r1, as well as r2and r3, we simplify the DFT/IDFT, as shown in the DFTRV/IDFTRV functions in Algorithm 6.(3)
The user verifies equations (3) and (4). If they are valid, the user computes Fa=∑i−1pFa+Fr1+Fb, Fb=∑i−1pFzi+Fr2, and Fc=Fa∘Fb:(3)∑i−1pFvi=?∑i−1pFui,(4)∑i−1pFzi=?∑i−1pFsi.(4)
The user generatesD=TFc,r3 and E=TFc,r3 and uploads them with the task requirement (i.e., IFFT) to smart contract, by the function TASK UPLOAD. Calling the function TASK ALLOCATION, the smart contract distributes the vectors in D and E to 2p computational nodes.(5)
After receiving the vectors, the computational nodes perform the inverse Fourier transform on the received vectors and returnFd1-,…,Fdp- and Fe1-,…,Fep- to smart contract by the function TASK UPLOAD. Smart contract returns them to the user by calling the function RETURN RESULT.(6)
The user computesc=Frs−+∑i=1pFd1−, selects two integers m,l∈R0,…,2n−2 randomly, and verifies equations (5)–(7). If they are valid, the computing succeeds; otherwise, the computing fails. The user sends a message to the smart contract. Then, the latter calls the function VERIFICATION AND PAYMENT:(5)∑i=1pFdi−=?∑i=1pFei−,(6)∑i=0paibl−i=?∑i=02n−2W2n−1−liFci,(7)∑i=02n−2W2n−1mici=?Fcm.In Algorithm6, if any verification fails, the user will report a cheating and the algorithm will come to an end.Figure2 demonstrates the procedures and data communications in the six steps of Algorithm 6.Algorithm 6: Secure outsourcing of polynomial multiplication.
Input: a,bOutput:c=a×b(1)
function DISCRETE FOURIER TRANSFORM FOR RESERVED VECTOR (DFTRV) (r, i)(2)
n⟵the length of r(3)
base⟵Wni(4)
Fr0⟵ri(5)
forj=1⟶n−1do(6)
Frj⟵Frj−1∗base(7)
end for(8)
returnFr(9)
end function(10)
function INVERSE DISCRETE FOURIER TRANSFORM FOR RESERVED VECTOR(IDFTRV) (r, i)(11)
n⟵the length or r(12)
base⟵Wn−i(13)
Fr−0⟵ri(14)
forj=1⟶n−1do(15)
Fr−j⟵Fr−j−1∗base(16)
end for(17)
returnFr−(18)
end function(19)
The user picks random parametersi,j,β,k1,k2,k3, and generates(20)
r1⟵Li,k1,n,r2⟵Lj,k2,n,r3⟵Lβ,k3,2n,(21)
V⟵Ta,r1,U⟵a,r1,Z⟵Tb,r2,S⟵Tb,r2;(22)
The user calls TASK UPLOAD locally and uploadsU,V,Z,Sto the smart contract;(23)
The smart contract calls TASK ALLOCATION and sends vectors inU,V,Z,Sto 4p nodes;(24)
The computational nodes computeFv1,…,Fvp,Fu1,…,Fup,Fz1,…,Fzp,Fs1,…,Fsp, and call RESULT UPLOAD;(25)
The smart contract calls RETURN RESULT;(26)
The user computesFr1⟵DFTRVr1,i,Fr2⟵DFTRVr2,j,Fr3-⟵IDFTRVr3,β, and verifies equations (3) and (4) locally;(27)
The user computesFa⟵∑i=1pFvi+Fr1,Fb⟵∑i=1pFzi+Fr2,Fc⟵Fa∘Fb;(28)
The user generatesD⟵TFc,r3,E⟵TFc,r3, calls TASK UPLOAD locally and uploads D,E to the smart contract;(29)
The smart contract calls TASK ALLOCATION and sends vectors inD,E to 2pnodes;(30)
The computational nodes computeFd1-,…,Fdp-,Fe1-,…,Fep-, and call RESULT UPLOAD;(31)
The smart contract calls RETURN RESULT;(32)
The user computesc⟵∑i=1pFdi−+Fr3−, and verifies equations (5)–(7) locally;(33)
The user sends feedback to the smart contract;(34)
The smart contract calls VERIFICATION AND PAYMENT.Figure 2
Blockchain-based secure outsourcing of polynomial multiplication.


#### 5.1.2. Correctness and Complexity

Because∑i=0pvi+r1=a and ∑i=0pzi+r2=b and the Fourier transform is a linear transform, we can have ∑i=0pFv1+Fr1=Fa and ∑i=1pFz1+Fr2=Fb. We get Fc=Fa∘Fb. Because of the convolution theorem, FFc−=FFa∘Fb−=a×b=c.Using the DFTRV/IDFTRV in Algorithm6, computing Fourier transform of r1,r2 and inverse Fourier transform of rs needs 4n multiplications. Because of the characteristics of r1,r2, and r3, only one multiplication is needed to compute each term in Fr1,Fr2, and Frs−. Computing Fa and Fb needs 2pn additions. Computing Fc needs 2n multiplications. The verification of equations (3)–(5) takes 6p−1n additions. 6p−1n additions are needed to compute c. The final verification (equations (6) and (7)) needs l+2n multiplications. To sum up, we need l+8n multiplications and 10pn−6n additions. The local complexity of multiplication in this algorithm is On, and the local complexity of addition is On. Therefore, the local complexity of this algorithm is On.


#### 5.1.3. Security against Passive Attackers

A participant may be a passive attacker. Passive attackers will follow the scripts of the algorithm while exploiting the intermediate information to breach the privacy of polynomials. In the following, we analyze the security of our algorithm against passive attackers.The algorithm should protect the privacy offx, gx, c, and Fc. As it is known to all, when all nodes collude, the passive attackers can get the most information, and the security of privacy is the lowest.Since the operations onfx and gx are consistent, the risks of privacy leakage of them are the same. We analyze the security of fx in the worst case, i e., collusion of all nodes. When all the computational nodes collude, they can guess a set of values a0′,a1′,…,an−1′, in which n−1 values are consistent with the true coefficients of fx, while one value is not. Because of r1, they even do not know the position of the false value. They still have to make a brute-force guessing. If ai∈D, where the base of D is m, the attackers should traverse all possibilities by taking m different values for each coefficient. In this case, the attackers have to make mn attempts to get fx. However, ai∈Z in FHEHIL. Then, m⟶∞, and the attackers cannot get fx.Fc and c are also privacy-protected. For the security of Fc, when all the computational nodes collude, the passive attackers can guess a set of values Fc10,Fc11,…,Fc12n−2, in which 2n−2 values are consistent with the true coefficients of Fc, while one value is not. However, the existence of r3 shows that passive attackers do not know the position of the false value. The only way to attack is by making a brute-force guessing. Same as a and b, the domain of the coefficients of Fc is infinite. Therefore, the attackers cannot get Fc. For the security of c, on the one hand, the attackers cannot compute c using inverse Fourier transform without knowing Fc. On the other hand, it is easy to see that when lacking Fra−, attackers cannot get c which is equal to ∑i=1pFdi−+Frs−.


#### 5.1.4. Security against Active Attackers

A participant may also be an active attacker. Active attackers will inject false computations into the algorithm to tamper with the whole process. In the following, we analyze the security of our algorithm against active attackers.Active attackers may return forged values to damage computing. To damage computing without being detected, attackers prefer to make minimal changes on results. In Algorithm6, it is easy to see that the lowest risk way for computational nodes to cheat is to tamper with only one item of the results returned to the user, while the other items are correct.There is one way to cheat in the process of securely outsourcing Fourier transform. For example, the nodes of computing the DFT offx perform honestly, while the nodes of computing the DFT of gx do not. One node nj changed the ith term in Fzj and another node nk′ also changed the ith term in Fsk. This way of cheating can nullify the verification at equations (3) and (4) and damage the result of Fb, whereas the error in the ith term of Fb will be propagated to Fci and every term of c. Equation (6) computes the correct c1=∑i=0laibl−i and the false cl′=∑i=02n−2W2n−1−liFci. Since Fci is false, cl′ is not equal to cl for any random l. The verification at equation (6) can certainly detect this cheating.There is the other way to cheat in the process of securely outsourcing the inverse DFT ofFc. One node nj changed the ith term in Fdj− and another node nk′ also changed the ith term in Fek−. In this way, we can nullify the verification at equation (9) and return a false item ci. The false item ci causes that Fc′m=∑i=02n−2W2n−1mici is also a false value in equation (7). Fc′m will not be equal to Fcm, for all 0≤m≤2n−2. The verification at equation (7) can certainly detect this way of cheating.


### 5.2. Secure Outsourcing of Modular Exponentiation

To the secure outsourcing of modular exponentiation, we extend the algorithm in [3] and apply it to the blockchain. In our extension, six modular exponentiation pairs are outsourced to six computational nodes, instead of a single cloud, aiming to protect against possible attacks on small discrete logarithms. The process is shown as Algorithm 7. The input is two integers. The output is ud, where u is the base and d is the exponent. In a similar way to Figure 2, Algorithm 7 can be implemented in the framework of Blockchain-based computation outsourcing, but we omit it due to limitation of space.


#### 5.2.1. Correctness and Complexity

It is easy to prove that the algorithm is correct from equations (8) and (9). In the process of parameter generation, there are two exponentiations, two divisions, and two multiplications. Two exponentiations and six multiplications are involved during the verification. Compared with the exponentiation, the complexity of multiplication and division can be ignored. However, in the algorithm, the exponents are e and t1 which are much smaller than the original exponent d through the transformation of t1=d−k1e. Therefore, local complexity will be greatly reduced:(8)v1k1w1l1g1w1k2t1=v1k1g1t1w1l1w1k2t1=v1k2g1t2w1l1+k2t1=g1dw1d=vd,(9)v2k1w2l1g2w2k2t1=v2k1g2t1w2l1w2k2t1=v2k2g2t2w2l1+k2t1=g2dw2d=vd.Algorithm 7: Secure outsourcing of modular exponentiation.
Input: u,dOutput: ud(1)
The user generates random parametersg1,g2,e,k1,k2∈Z,(2)
and computesv1⟵gle,v2⟵g2e,w1⟵u/g1,w2⟵u/g2,(3)
t1⟵d−k1e,l1⟵d−k2t1;(4)
The user uploadsk1,v1,k1,v2,l1,w1,k2,w1,l1,w2,k2,w2 to the smart contract;(5)
The smart contract distributesk1,v1,k1,v2,l1,w1,k2,w1,l1,w2,k2,w2 to 6 computational nodes;(6)
The computational nodes computeba after receiving a,b and return results to the smart contract;(7)
The user getsv1k1,v2k1,w1l1,w1k2,w2l1,w2k2 from the smart contract;(8)
The user verifiesv1k1w1l1g1w1k2t1=v2k1w2l1g2w2k2t1.(9)
If the verification is valid,ud⟵v1k1w1l1g1w1k2t1


#### 5.2.2. Security

The only way to pass the verification is that the six computational nodes perform correctly. The forged results of active attackers cannot pass the verification in Step 8. The user only needs to know whether the results are correct or not, and the smart contract can detect the cheating nodes according to the records.We analyze the security against passive attackers in the worst case, i e., the conspiring of six computational nodes. The exponentsk1, l1, and k2 are visible for attackers, while the other exponents t1, d, and e are not. The bases v1, v2, w1, and w2 are visible for attackers, while g1, g2, and e are not. We discover that the privacy of u may leak in [3], which sends six pairs to a single node in the cloud. In [3], the base and exponent are about 1000 bit, while the parameters including g1, g2, e, k1, and k2 are only 64-bit long, to reduce the overhead of local computation. The shorter bit length of parameters may promote an easier attack on the small discrete logarithms. In this kind of attack, an attacker in the cloud can exhaust x so that w1∗∗v1=w2∗∗v2. Then, e is breached. The attacker then exhausts g, satisfying ge=v1. Finally, the cloud can obtain u by w1∗g.We solve this attack by distributing six modular exponentiation pairs to six computational nodes, which increases the difficulty of the above attack.


## 5.1. Polynomial Multiplication Secure Outsourcing Algorithm

The computational complexity of traditional polynomial multiplication isOn2, which is reduced to Onlogn by the FFT. In this section, we employ secure outsourcing to further reduce the local computational complexity to On. The outsourcing is implemented in our proposed framework of blockchain-based secure computation outsourcing. The main idea of our algorithm is as follows. Firstly, the Fourier transform of the polynomial coefficients are securely outsourced. Secondly, correlation operation on the results of the Fourier transform is locally performed. Finally, the inverse Fourier transform on result of the correlation operation are securely outsourced. The specific process of our algorithm is shown as Algorithm 6.


### 5.1.1. Description

In Algorithm6, the input polynomials are fx=a0+a1x+⋯+an−1xn−1 and gx=b0+b1x+⋯+bn−1xn−1. The output is tx=fx×gx=c0+c1x+⋯+c2n−1x2n−1. For convenience, polynomials are replaced with vectors of polynomial coefficients (a=a0,a1,…,an−1, b=b0,b1,…,bn−1, and c=c0,c1,…,c2n−2). Besides, Wnm=e−2πjm/n, in this section. We use 6p computational nodes in this algorithm, where p is a parameter associated with the number of computational nodes. There are six steps in the algorithm:(1)
Six parameters are picked randomly, three of which arei,j,β,s.t.0≤n−1,0≤j≤n−1 and 0≤β≤2n−2. The other three are k1,k2,k3∈RZ. We define that Li,k,n:Z3⟶Zn can generate one n-dimensional vector in which the ith element is k, and all the other elements are zeros. We define that Tv,r:zn∗2⟶Zn∗p can generate a random matrix W=w1,w2,…,wp satisfying v=∑i=1pwi+r. Then, the user generates r1=Li,k1,n, r2=Lj,k2,n, r3=Lβ,k3,2n, V=Ta,r1, U=Ta,r1, Z=Tb,r2, and S=Tb,r2. In this way, one must know r1 to recover a from V or U and know r2 to recover b from Z or S.(2)
The user uploads the data (V, U, Z, and S) and task requirement (i.e., FFT) to smart contract, by the function TASK UPLOAD. The smart contract calls the function TASK ALLOCATION and distributes the vectors in V, U, Z, and S to Z and 4p computational nodes. After receiving the vectors, the computational nodes perform the Fourier transform on the received vectors and call the function RESULT UPLOAD. The smart contract collects the results and returns Fv1,…,Fvp, Fu1,…,Fup, Fz1,…,Fzp, and Fs1,…,Fsp to the user by calling the function RETURN RESULT. Meanwhile, the user locally computes Fr1Fr2 and Fr1- which are Fourier transform of r1 and r2 and inverse Fourier transform of r3, respectively. Because there is only one nonzero coefficient in r1, as well as r2and r3, we simplify the DFT/IDFT, as shown in the DFTRV/IDFTRV functions in Algorithm 6.(3)
The user verifies equations (3) and (4). If they are valid, the user computes Fa=∑i−1pFa+Fr1+Fb, Fb=∑i−1pFzi+Fr2, and Fc=Fa∘Fb:(3)∑i−1pFvi=?∑i−1pFui,(4)∑i−1pFzi=?∑i−1pFsi.(4)
The user generatesD=TFc,r3 and E=TFc,r3 and uploads them with the task requirement (i.e., IFFT) to smart contract, by the function TASK UPLOAD. Calling the function TASK ALLOCATION, the smart contract distributes the vectors in D and E to 2p computational nodes.(5)
After receiving the vectors, the computational nodes perform the inverse Fourier transform on the received vectors and returnFd1-,…,Fdp- and Fe1-,…,Fep- to smart contract by the function TASK UPLOAD. Smart contract returns them to the user by calling the function RETURN RESULT.(6)
The user computesc=Frs−+∑i=1pFd1−, selects two integers m,l∈R0,…,2n−2 randomly, and verifies equations (5)–(7). If they are valid, the computing succeeds; otherwise, the computing fails. The user sends a message to the smart contract. Then, the latter calls the function VERIFICATION AND PAYMENT:(5)∑i=1pFdi−=?∑i=1pFei−,(6)∑i=0paibl−i=?∑i=02n−2W2n−1−liFci,(7)∑i=02n−2W2n−1mici=?Fcm.In Algorithm6, if any verification fails, the user will report a cheating and the algorithm will come to an end.Figure2 demonstrates the procedures and data communications in the six steps of Algorithm 6.Algorithm 6: Secure outsourcing of polynomial multiplication.
Input: a,bOutput:c=a×b(1)
function DISCRETE FOURIER TRANSFORM FOR RESERVED VECTOR (DFTRV) (r, i)(2)
n⟵the length of r(3)
base⟵Wni(4)
Fr0⟵ri(5)
forj=1⟶n−1do(6)
Frj⟵Frj−1∗base(7)
end for(8)
returnFr(9)
end function(10)
function INVERSE DISCRETE FOURIER TRANSFORM FOR RESERVED VECTOR(IDFTRV) (r, i)(11)
n⟵the length or r(12)
base⟵Wn−i(13)
Fr−0⟵ri(14)
forj=1⟶n−1do(15)
Fr−j⟵Fr−j−1∗base(16)
end for(17)
returnFr−(18)
end function(19)
The user picks random parametersi,j,β,k1,k2,k3, and generates(20)
r1⟵Li,k1,n,r2⟵Lj,k2,n,r3⟵Lβ,k3,2n,(21)
V⟵Ta,r1,U⟵a,r1,Z⟵Tb,r2,S⟵Tb,r2;(22)
The user calls TASK UPLOAD locally and uploadsU,V,Z,Sto the smart contract;(23)
The smart contract calls TASK ALLOCATION and sends vectors inU,V,Z,Sto 4p nodes;(24)
The computational nodes computeFv1,…,Fvp,Fu1,…,Fup,Fz1,…,Fzp,Fs1,…,Fsp, and call RESULT UPLOAD;(25)
The smart contract calls RETURN RESULT;(26)
The user computesFr1⟵DFTRVr1,i,Fr2⟵DFTRVr2,j,Fr3-⟵IDFTRVr3,β, and verifies equations (3) and (4) locally;(27)
The user computesFa⟵∑i=1pFvi+Fr1,Fb⟵∑i=1pFzi+Fr2,Fc⟵Fa∘Fb;(28)
The user generatesD⟵TFc,r3,E⟵TFc,r3, calls TASK UPLOAD locally and uploads D,E to the smart contract;(29)
The smart contract calls TASK ALLOCATION and sends vectors inD,E to 2pnodes;(30)
The computational nodes computeFd1-,…,Fdp-,Fe1-,…,Fep-, and call RESULT UPLOAD;(31)
The smart contract calls RETURN RESULT;(32)
The user computesc⟵∑i=1pFdi−+Fr3−, and verifies equations (5)–(7) locally;(33)
The user sends feedback to the smart contract;(34)
The smart contract calls VERIFICATION AND PAYMENT.Figure 2
Blockchain-based secure outsourcing of polynomial multiplication.


### 5.1.2. Correctness and Complexity

Because∑i=0pvi+r1=a and ∑i=0pzi+r2=b and the Fourier transform is a linear transform, we can have ∑i=0pFv1+Fr1=Fa and ∑i=1pFz1+Fr2=Fb. We get Fc=Fa∘Fb. Because of the convolution theorem, FFc−=FFa∘Fb−=a×b=c.Using the DFTRV/IDFTRV in Algorithm6, computing Fourier transform of r1,r2 and inverse Fourier transform of rs needs 4n multiplications. Because of the characteristics of r1,r2, and r3, only one multiplication is needed to compute each term in Fr1,Fr2, and Frs−. Computing Fa and Fb needs 2pn additions. Computing Fc needs 2n multiplications. The verification of equations (3)–(5) takes 6p−1n additions. 6p−1n additions are needed to compute c. The final verification (equations (6) and (7)) needs l+2n multiplications. To sum up, we need l+8n multiplications and 10pn−6n additions. The local complexity of multiplication in this algorithm is On, and the local complexity of addition is On. Therefore, the local complexity of this algorithm is On.


### 5.1.3. Security against Passive Attackers

A participant may be a passive attacker. Passive attackers will follow the scripts of the algorithm while exploiting the intermediate information to breach the privacy of polynomials. In the following, we analyze the security of our algorithm against passive attackers.The algorithm should protect the privacy offx, gx, c, and Fc. As it is known to all, when all nodes collude, the passive attackers can get the most information, and the security of privacy is the lowest.Since the operations onfx and gx are consistent, the risks of privacy leakage of them are the same. We analyze the security of fx in the worst case, i e., collusion of all nodes. When all the computational nodes collude, they can guess a set of values a0′,a1′,…,an−1′, in which n−1 values are consistent with the true coefficients of fx, while one value is not. Because of r1, they even do not know the position of the false value. They still have to make a brute-force guessing. If ai∈D, where the base of D is m, the attackers should traverse all possibilities by taking m different values for each coefficient. In this case, the attackers have to make mn attempts to get fx. However, ai∈Z in FHEHIL. Then, m⟶∞, and the attackers cannot get fx.Fc and c are also privacy-protected. For the security of Fc, when all the computational nodes collude, the passive attackers can guess a set of values Fc10,Fc11,…,Fc12n−2, in which 2n−2 values are consistent with the true coefficients of Fc, while one value is not. However, the existence of r3 shows that passive attackers do not know the position of the false value. The only way to attack is by making a brute-force guessing. Same as a and b, the domain of the coefficients of Fc is infinite. Therefore, the attackers cannot get Fc. For the security of c, on the one hand, the attackers cannot compute c using inverse Fourier transform without knowing Fc. On the other hand, it is easy to see that when lacking Fra−, attackers cannot get c which is equal to ∑i=1pFdi−+Frs−.


### 5.1.4. Security against Active Attackers

A participant may also be an active attacker. Active attackers will inject false computations into the algorithm to tamper with the whole process. In the following, we analyze the security of our algorithm against active attackers.Active attackers may return forged values to damage computing. To damage computing without being detected, attackers prefer to make minimal changes on results. In Algorithm6, it is easy to see that the lowest risk way for computational nodes to cheat is to tamper with only one item of the results returned to the user, while the other items are correct.There is one way to cheat in the process of securely outsourcing Fourier transform. For example, the nodes of computing the DFT offx perform honestly, while the nodes of computing the DFT of gx do not. One node nj changed the ith term in Fzj and another node nk′ also changed the ith term in Fsk. This way of cheating can nullify the verification at equations (3) and (4) and damage the result of Fb, whereas the error in the ith term of Fb will be propagated to Fci and every term of c. Equation (6) computes the correct c1=∑i=0laibl−i and the false cl′=∑i=02n−2W2n−1−liFci. Since Fci is false, cl′ is not equal to cl for any random l. The verification at equation (6) can certainly detect this cheating.There is the other way to cheat in the process of securely outsourcing the inverse DFT ofFc. One node nj changed the ith term in Fdj− and another node nk′ also changed the ith term in Fek−. In this way, we can nullify the verification at equation (9) and return a false item ci. The false item ci causes that Fc′m=∑i=02n−2W2n−1mici is also a false value in equation (7). Fc′m will not be equal to Fcm, for all 0≤m≤2n−2. The verification at equation (7) can certainly detect this way of cheating.


## 5.1.1. Description

In Algorithm6, the input polynomials are fx=a0+a1x+⋯+an−1xn−1 and gx=b0+b1x+⋯+bn−1xn−1. The output is tx=fx×gx=c0+c1x+⋯+c2n−1x2n−1. For convenience, polynomials are replaced with vectors of polynomial coefficients (a=a0,a1,…,an−1, b=b0,b1,…,bn−1, and c=c0,c1,…,c2n−2). Besides, Wnm=e−2πjm/n, in this section. We use 6p computational nodes in this algorithm, where p is a parameter associated with the number of computational nodes. There are six steps in the algorithm:(1)
Six parameters are picked randomly, three of which arei,j,β,s.t.0≤n−1,0≤j≤n−1 and 0≤β≤2n−2. The other three are k1,k2,k3∈RZ. We define that Li,k,n:Z3⟶Zn can generate one n-dimensional vector in which the ith element is k, and all the other elements are zeros. We define that Tv,r:zn∗2⟶Zn∗p can generate a random matrix W=w1,w2,…,wp satisfying v=∑i=1pwi+r. Then, the user generates r1=Li,k1,n, r2=Lj,k2,n, r3=Lβ,k3,2n, V=Ta,r1, U=Ta,r1, Z=Tb,r2, and S=Tb,r2. In this way, one must know r1 to recover a from V or U and know r2 to recover b from Z or S.(2)
The user uploads the data (V, U, Z, and S) and task requirement (i.e., FFT) to smart contract, by the function TASK UPLOAD. The smart contract calls the function TASK ALLOCATION and distributes the vectors in V, U, Z, and S to Z and 4p computational nodes. After receiving the vectors, the computational nodes perform the Fourier transform on the received vectors and call the function RESULT UPLOAD. The smart contract collects the results and returns Fv1,…,Fvp, Fu1,…,Fup, Fz1,…,Fzp, and Fs1,…,Fsp to the user by calling the function RETURN RESULT. Meanwhile, the user locally computes Fr1Fr2 and Fr1- which are Fourier transform of r1 and r2 and inverse Fourier transform of r3, respectively. Because there is only one nonzero coefficient in r1, as well as r2and r3, we simplify the DFT/IDFT, as shown in the DFTRV/IDFTRV functions in Algorithm 6.(3)
The user verifies equations (3) and (4). If they are valid, the user computes Fa=∑i−1pFa+Fr1+Fb, Fb=∑i−1pFzi+Fr2, and Fc=Fa∘Fb:(3)∑i−1pFvi=?∑i−1pFui,(4)∑i−1pFzi=?∑i−1pFsi.(4)
The user generatesD=TFc,r3 and E=TFc,r3 and uploads them with the task requirement (i.e., IFFT) to smart contract, by the function TASK UPLOAD. Calling the function TASK ALLOCATION, the smart contract distributes the vectors in D and E to 2p computational nodes.(5)
After receiving the vectors, the computational nodes perform the inverse Fourier transform on the received vectors and returnFd1-,…,Fdp- and Fe1-,…,Fep- to smart contract by the function TASK UPLOAD. Smart contract returns them to the user by calling the function RETURN RESULT.(6)
The user computesc=Frs−+∑i=1pFd1−, selects two integers m,l∈R0,…,2n−2 randomly, and verifies equations (5)–(7). If they are valid, the computing succeeds; otherwise, the computing fails. The user sends a message to the smart contract. Then, the latter calls the function VERIFICATION AND PAYMENT:(5)∑i=1pFdi−=?∑i=1pFei−,(6)∑i=0paibl−i=?∑i=02n−2W2n−1−liFci,(7)∑i=02n−2W2n−1mici=?Fcm.In Algorithm6, if any verification fails, the user will report a cheating and the algorithm will come to an end.Figure2 demonstrates the procedures and data communications in the six steps of Algorithm 6.Algorithm 6: Secure outsourcing of polynomial multiplication.
Input: a,bOutput:c=a×b(1)
function DISCRETE FOURIER TRANSFORM FOR RESERVED VECTOR (DFTRV) (r, i)(2)
n⟵the length of r(3)
base⟵Wni(4)
Fr0⟵ri(5)
forj=1⟶n−1do(6)
Frj⟵Frj−1∗base(7)
end for(8)
returnFr(9)
end function(10)
function INVERSE DISCRETE FOURIER TRANSFORM FOR RESERVED VECTOR(IDFTRV) (r, i)(11)
n⟵the length or r(12)
base⟵Wn−i(13)
Fr−0⟵ri(14)
forj=1⟶n−1do(15)
Fr−j⟵Fr−j−1∗base(16)
end for(17)
returnFr−(18)
end function(19)
The user picks random parametersi,j,β,k1,k2,k3, and generates(20)
r1⟵Li,k1,n,r2⟵Lj,k2,n,r3⟵Lβ,k3,2n,(21)
V⟵Ta,r1,U⟵a,r1,Z⟵Tb,r2,S⟵Tb,r2;(22)
The user calls TASK UPLOAD locally and uploadsU,V,Z,Sto the smart contract;(23)
The smart contract calls TASK ALLOCATION and sends vectors inU,V,Z,Sto 4p nodes;(24)
The computational nodes computeFv1,…,Fvp,Fu1,…,Fup,Fz1,…,Fzp,Fs1,…,Fsp, and call RESULT UPLOAD;(25)
The smart contract calls RETURN RESULT;(26)
The user computesFr1⟵DFTRVr1,i,Fr2⟵DFTRVr2,j,Fr3-⟵IDFTRVr3,β, and verifies equations (3) and (4) locally;(27)
The user computesFa⟵∑i=1pFvi+Fr1,Fb⟵∑i=1pFzi+Fr2,Fc⟵Fa∘Fb;(28)
The user generatesD⟵TFc,r3,E⟵TFc,r3, calls TASK UPLOAD locally and uploads D,E to the smart contract;(29)
The smart contract calls TASK ALLOCATION and sends vectors inD,E to 2pnodes;(30)
The computational nodes computeFd1-,…,Fdp-,Fe1-,…,Fep-, and call RESULT UPLOAD;(31)
The smart contract calls RETURN RESULT;(32)
The user computesc⟵∑i=1pFdi−+Fr3−, and verifies equations (5)–(7) locally;(33)
The user sends feedback to the smart contract;(34)
The smart contract calls VERIFICATION AND PAYMENT.Figure 2
Blockchain-based secure outsourcing of polynomial multiplication.


## 5.1.2. Correctness and Complexity

Because∑i=0pvi+r1=a and ∑i=0pzi+r2=b and the Fourier transform is a linear transform, we can have ∑i=0pFv1+Fr1=Fa and ∑i=1pFz1+Fr2=Fb. We get Fc=Fa∘Fb. Because of the convolution theorem, FFc−=FFa∘Fb−=a×b=c.Using the DFTRV/IDFTRV in Algorithm6, computing Fourier transform of r1,r2 and inverse Fourier transform of rs needs 4n multiplications. Because of the characteristics of r1,r2, and r3, only one multiplication is needed to compute each term in Fr1,Fr2, and Frs−. Computing Fa and Fb needs 2pn additions. Computing Fc needs 2n multiplications. The verification of equations (3)–(5) takes 6p−1n additions. 6p−1n additions are needed to compute c. The final verification (equations (6) and (7)) needs l+2n multiplications. To sum up, we need l+8n multiplications and 10pn−6n additions. The local complexity of multiplication in this algorithm is On, and the local complexity of addition is On. Therefore, the local complexity of this algorithm is On.


## 5.1.3. Security against Passive Attackers

A participant may be a passive attacker. Passive attackers will follow the scripts of the algorithm while exploiting the intermediate information to breach the privacy of polynomials. In the following, we analyze the security of our algorithm against passive attackers.The algorithm should protect the privacy offx, gx, c, and Fc. As it is known to all, when all nodes collude, the passive attackers can get the most information, and the security of privacy is the lowest.Since the operations onfx and gx are consistent, the risks of privacy leakage of them are the same. We analyze the security of fx in the worst case, i e., collusion of all nodes. When all the computational nodes collude, they can guess a set of values a0′,a1′,…,an−1′, in which n−1 values are consistent with the true coefficients of fx, while one value is not. Because of r1, they even do not know the position of the false value. They still have to make a brute-force guessing. If ai∈D, where the base of D is m, the attackers should traverse all possibilities by taking m different values for each coefficient. In this case, the attackers have to make mn attempts to get fx. However, ai∈Z in FHEHIL. Then, m⟶∞, and the attackers cannot get fx.Fc and c are also privacy-protected. For the security of Fc, when all the computational nodes collude, the passive attackers can guess a set of values Fc10,Fc11,…,Fc12n−2, in which 2n−2 values are consistent with the true coefficients of Fc, while one value is not. However, the existence of r3 shows that passive attackers do not know the position of the false value. The only way to attack is by making a brute-force guessing. Same as a and b, the domain of the coefficients of Fc is infinite. Therefore, the attackers cannot get Fc. For the security of c, on the one hand, the attackers cannot compute c using inverse Fourier transform without knowing Fc. On the other hand, it is easy to see that when lacking Fra−, attackers cannot get c which is equal to ∑i=1pFdi−+Frs−.


## 5.1.4. Security against Active Attackers

A participant may also be an active attacker. Active attackers will inject false computations into the algorithm to tamper with the whole process. In the following, we analyze the security of our algorithm against active attackers.Active attackers may return forged values to damage computing. To damage computing without being detected, attackers prefer to make minimal changes on results. In Algorithm6, it is easy to see that the lowest risk way for computational nodes to cheat is to tamper with only one item of the results returned to the user, while the other items are correct.There is one way to cheat in the process of securely outsourcing Fourier transform. For example, the nodes of computing the DFT offx perform honestly, while the nodes of computing the DFT of gx do not. One node nj changed the ith term in Fzj and another node nk′ also changed the ith term in Fsk. This way of cheating can nullify the verification at equations (3) and (4) and damage the result of Fb, whereas the error in the ith term of Fb will be propagated to Fci and every term of c. Equation (6) computes the correct c1=∑i=0laibl−i and the false cl′=∑i=02n−2W2n−1−liFci. Since Fci is false, cl′ is not equal to cl for any random l. The verification at equation (6) can certainly detect this cheating.There is the other way to cheat in the process of securely outsourcing the inverse DFT ofFc. One node nj changed the ith term in Fdj− and another node nk′ also changed the ith term in Fek−. In this way, we can nullify the verification at equation (9) and return a false item ci. The false item ci causes that Fc′m=∑i=02n−2W2n−1mici is also a false value in equation (7). Fc′m will not be equal to Fcm, for all 0≤m≤2n−2. The verification at equation (7) can certainly detect this way of cheating.


## 5.2. Secure Outsourcing of Modular Exponentiation

To the secure outsourcing of modular exponentiation, we extend the algorithm in [3] and apply it to the blockchain. In our extension, six modular exponentiation pairs are outsourced to six computational nodes, instead of a single cloud, aiming to protect against possible attacks on small discrete logarithms. The process is shown as Algorithm 7. The input is two integers. The output is ud, where u is the base and d is the exponent. In a similar way to Figure 2, Algorithm 7 can be implemented in the framework of Blockchain-based computation outsourcing, but we omit it due to limitation of space.


### 5.2.1. Correctness and Complexity

It is easy to prove that the algorithm is correct from equations (8) and (9). In the process of parameter generation, there are two exponentiations, two divisions, and two multiplications. Two exponentiations and six multiplications are involved during the verification. Compared with the exponentiation, the complexity of multiplication and division can be ignored. However, in the algorithm, the exponents are e and t1 which are much smaller than the original exponent d through the transformation of t1=d−k1e. Therefore, local complexity will be greatly reduced:(8)v1k1w1l1g1w1k2t1=v1k1g1t1w1l1w1k2t1=v1k2g1t2w1l1+k2t1=g1dw1d=vd,(9)v2k1w2l1g2w2k2t1=v2k1g2t1w2l1w2k2t1=v2k2g2t2w2l1+k2t1=g2dw2d=vd.Algorithm 7: Secure outsourcing of modular exponentiation.
Input: u,dOutput: ud(1)
The user generates random parametersg1,g2,e,k1,k2∈Z,(2)
and computesv1⟵gle,v2⟵g2e,w1⟵u/g1,w2⟵u/g2,(3)
t1⟵d−k1e,l1⟵d−k2t1;(4)
The user uploadsk1,v1,k1,v2,l1,w1,k2,w1,l1,w2,k2,w2 to the smart contract;(5)
The smart contract distributesk1,v1,k1,v2,l1,w1,k2,w1,l1,w2,k2,w2 to 6 computational nodes;(6)
The computational nodes computeba after receiving a,b and return results to the smart contract;(7)
The user getsv1k1,v2k1,w1l1,w1k2,w2l1,w2k2 from the smart contract;(8)
The user verifiesv1k1w1l1g1w1k2t1=v2k1w2l1g2w2k2t1.(9)
If the verification is valid,ud⟵v1k1w1l1g1w1k2t1


### 5.2.2. Security

The only way to pass the verification is that the six computational nodes perform correctly. The forged results of active attackers cannot pass the verification in Step 8. The user only needs to know whether the results are correct or not, and the smart contract can detect the cheating nodes according to the records.We analyze the security against passive attackers in the worst case, i e., the conspiring of six computational nodes. The exponentsk1, l1, and k2 are visible for attackers, while the other exponents t1, d, and e are not. The bases v1, v2, w1, and w2 are visible for attackers, while g1, g2, and e are not. We discover that the privacy of u may leak in [3], which sends six pairs to a single node in the cloud. In [3], the base and exponent are about 1000 bit, while the parameters including g1, g2, e, k1, and k2 are only 64-bit long, to reduce the overhead of local computation. The shorter bit length of parameters may promote an easier attack on the small discrete logarithms. In this kind of attack, an attacker in the cloud can exhaust x so that w1∗∗v1=w2∗∗v2. Then, e is breached. The attacker then exhausts g, satisfying ge=v1. Finally, the cloud can obtain u by w1∗g.We solve this attack by distributing six modular exponentiation pairs to six computational nodes, which increases the difficulty of the above attack.


## 5.2.1. Correctness and Complexity

It is easy to prove that the algorithm is correct from equations (8) and (9). In the process of parameter generation, there are two exponentiations, two divisions, and two multiplications. Two exponentiations and six multiplications are involved during the verification. Compared with the exponentiation, the complexity of multiplication and division can be ignored. However, in the algorithm, the exponents are e and t1 which are much smaller than the original exponent d through the transformation of t1=d−k1e. Therefore, local complexity will be greatly reduced:(8)v1k1w1l1g1w1k2t1=v1k1g1t1w1l1w1k2t1=v1k2g1t2w1l1+k2t1=g1dw1d=vd,(9)v2k1w2l1g2w2k2t1=v2k1g2t1w2l1w2k2t1=v2k2g2t2w2l1+k2t1=g2dw2d=vd.Algorithm 7: Secure outsourcing of modular exponentiation.
Input: u,dOutput: ud(1)
The user generates random parametersg1,g2,e,k1,k2∈Z,(2)
and computesv1⟵gle,v2⟵g2e,w1⟵u/g1,w2⟵u/g2,(3)
t1⟵d−k1e,l1⟵d−k2t1;(4)
The user uploadsk1,v1,k1,v2,l1,w1,k2,w1,l1,w2,k2,w2 to the smart contract;(5)
The smart contract distributesk1,v1,k1,v2,l1,w1,k2,w1,l1,w2,k2,w2 to 6 computational nodes;(6)
The computational nodes computeba after receiving a,b and return results to the smart contract;(7)
The user getsv1k1,v2k1,w1l1,w1k2,w2l1,w2k2 from the smart contract;(8)
The user verifiesv1k1w1l1g1w1k2t1=v2k1w2l1g2w2k2t1.(9)
If the verification is valid,ud⟵v1k1w1l1g1w1k2t1


## 5.2.2. Security

The only way to pass the verification is that the six computational nodes perform correctly. The forged results of active attackers cannot pass the verification in Step 8. The user only needs to know whether the results are correct or not, and the smart contract can detect the cheating nodes according to the records.We analyze the security against passive attackers in the worst case, i e., the conspiring of six computational nodes. The exponentsk1, l1, and k2 are visible for attackers, while the other exponents t1, d, and e are not. The bases v1, v2, w1, and w2 are visible for attackers, while g1, g2, and e are not. We discover that the privacy of u may leak in [3], which sends six pairs to a single node in the cloud. In [3], the base and exponent are about 1000 bit, while the parameters including g1, g2, e, k1, and k2 are only 64-bit long, to reduce the overhead of local computation. The shorter bit length of parameters may promote an easier attack on the small discrete logarithms. In this kind of attack, an attacker in the cloud can exhaust x so that w1∗∗v1=w2∗∗v2. Then, e is breached. The attacker then exhausts g, satisfying ge=v1. Finally, the cloud can obtain u by w1∗g.We solve this attack by distributing six modular exponentiation pairs to six computational nodes, which increases the difficulty of the above attack.


## 6. Results and Discussion

In this section, we conduct three types of experiments. Firstly, we evaluate the efficiency of the secure outsourcing of polynomial multiplication in various numbers of polynomial multiplications and compare it with the traditional nonoutsourcing method using FFT. Secondly, we evaluate the efficiency of the secure outsourcing of polynomial multiplication by varying the numbers of items and bit length of coefficients and also compare it with the nonoutsourcing method. Finally, we complete the secure outsourcing for FHEHIL in blockchain, analyze the time consumption of each step, and compare it with the nonoutsourcing method. The experiments are simulated on two machines with Intel Core i7 processor running at 2.90 GHz and 16G memory as a cloud server and Intel Core i5 processor running at 1.80 GHz and 8G memory as a local user. The communication bandwidth is 20 Mbps.


### 6.1. The Evaluation of Secure Outsourcing of Polynomial Multiplication

We make experiments to evaluate the efficiency of the secure outsourcing algorithm for polynomial multiplication. We implement this experiment using Python3 language.We compare the secure outsourcing of polynomial multiplication with the nonsourcing algorithm on time consumption with different numbers of polynomial multiplication, in whichn=1024, p=3, and all the coefficients are 512-bit long. As demonstrated in Figure 3, it is easy to see that when the number of polynomial multiplications is less than 60, the efficiency of the outsourcing scheme is lower than the nonoutsourcing scheme due to the communication time consumption. However, when the number of polynomial multiplications increases above 60, the efficiency of the outsourcing scheme becomes higher than the nonoutsourcing scheme. When the number of polynomial multiplications is less than 300, the bottleneck of the outsourcing scheme is the time consumption on nodes’ computations and interactions. When the number of polynomial multiplications becomes larger, the bottleneck is the time consumption on local computation.We make another type of experiments to analyze the influence of number of terms and bit length of coefficients on the efficiency of secure outsourcing of polynomial multiplication. We count the time consumption of 400 random polynomial multiplications, with the number of polynomial items varying from 50 to 1000, and the item bit length varying from 50 to 1000. Figure4(a) demonstrates that the time consumption increases with the increase of items of polynomials and bit length of coefficients. Moreover, the number of terms has a more obvious effect on time consumption. Besides, compared with the nonoutsourcing polynomial multiplication, our method always has a higher efficiency under all scales of data, as shown in Figure 4(b).Figure 3
Comparison of time consumption on the outsourcing and nonoutsourcing scheme of polynomial multiplications.Figure 4
Comparison of time consumption on the outsourcing and nonoutsourcing scheme of polynomial multiplications.
(a)(b)


### 6.2. The Evaluation of Blockchain-Based Secure Outsourcing Scheme of Fully Homomorphic Encryption Using Hidden Ideal Lattice

We employ the relevant security parameters recommended in [2], i.e., n=1024, t=310, and p=3. Our outsourcing scheme consists of the local user’s program and the computational nodes’ program. Our outsourcing scheme is compared with the nonoutsourcing scheme. The programs are written in Python3, and the smart contract based on the Ethereum platform is written in Solidity. The smart contract interacts with computational nodes’ program and local program by the interface provided by Web3.Figure5 demonstrates the running time at all stages of the two schemes. This figure does not display the time consumption on generating parameters in the FHEHIL because that is not what we are improving. In the process of computing w efficiency is slightly improved. Compared with the non-sourcing scheme, our scheme saves about 2.6 s. The overall time consumption is improved by about 40.7% (the unmarked areas in Figure 5 are the communication time consumption for interacting with the blockchain). Table 3 shows the detailed time consumption of different entities (user, smart contract, and computational nodes) in different stages (verification, communication, DFTRV/IDFTRV, FFT/IFFT, and other computations) for Key Generation. Table 4 shows the detailed time consumption of different entities in different stages for encryption.The time consumption of decryption is not shown in Figure5. Since there is only one polynomial multiplication, the time consumption of communication is dominant in the process of decryption, as illustrated in Figure 3. Therefore, the time consumption of outsourcing decryption (0.379 s) is larger than the nonoutsourcing decryption (0.103 s).Figure 5
Time consumption on stages of the outsourcing and nonoutsourcing schemes.Table 3
Details of time consumption in key generation.
Verification (s)DFTRV/IDFTRV (s)Communication (s)Others (s)FFT/IFFT (s)User0.370.890.460.580Smart contract001.0100Computational nodes000.5200.19Table 4
Details of time consumption in encryption.
Verification (s)DFTRV/IDFTRV (s)Communication (s)Others (s)FFT/IFFT (s)User0.240.930.430.110Smart contract000.9900Computational nodes000.3700.20


## 6.1. The Evaluation of Secure Outsourcing of Polynomial Multiplication

We make experiments to evaluate the efficiency of the secure outsourcing algorithm for polynomial multiplication. We implement this experiment using Python3 language.We compare the secure outsourcing of polynomial multiplication with the nonsourcing algorithm on time consumption with different numbers of polynomial multiplication, in whichn=1024, p=3, and all the coefficients are 512-bit long. As demonstrated in Figure 3, it is easy to see that when the number of polynomial multiplications is less than 60, the efficiency of the outsourcing scheme is lower than the nonoutsourcing scheme due to the communication time consumption. However, when the number of polynomial multiplications increases above 60, the efficiency of the outsourcing scheme becomes higher than the nonoutsourcing scheme. When the number of polynomial multiplications is less than 300, the bottleneck of the outsourcing scheme is the time consumption on nodes’ computations and interactions. When the number of polynomial multiplications becomes larger, the bottleneck is the time consumption on local computation.We make another type of experiments to analyze the influence of number of terms and bit length of coefficients on the efficiency of secure outsourcing of polynomial multiplication. We count the time consumption of 400 random polynomial multiplications, with the number of polynomial items varying from 50 to 1000, and the item bit length varying from 50 to 1000. Figure4(a) demonstrates that the time consumption increases with the increase of items of polynomials and bit length of coefficients. Moreover, the number of terms has a more obvious effect on time consumption. Besides, compared with the nonoutsourcing polynomial multiplication, our method always has a higher efficiency under all scales of data, as shown in Figure 4(b).Figure 3
Comparison of time consumption on the outsourcing and nonoutsourcing scheme of polynomial multiplications.Figure 4
Comparison of time consumption on the outsourcing and nonoutsourcing scheme of polynomial multiplications.
(a)(b)


## 6.2. The Evaluation of Blockchain-Based Secure Outsourcing Scheme of Fully Homomorphic Encryption Using Hidden Ideal Lattice

We employ the relevant security parameters recommended in [2], i.e., n=1024, t=310, and p=3. Our outsourcing scheme consists of the local user’s program and the computational nodes’ program. Our outsourcing scheme is compared with the nonoutsourcing scheme. The programs are written in Python3, and the smart contract based on the Ethereum platform is written in Solidity. The smart contract interacts with computational nodes’ program and local program by the interface provided by Web3.Figure5 demonstrates the running time at all stages of the two schemes. This figure does not display the time consumption on generating parameters in the FHEHIL because that is not what we are improving. In the process of computing w efficiency is slightly improved. Compared with the non-sourcing scheme, our scheme saves about 2.6 s. The overall time consumption is improved by about 40.7% (the unmarked areas in Figure 5 are the communication time consumption for interacting with the blockchain). Table 3 shows the detailed time consumption of different entities (user, smart contract, and computational nodes) in different stages (verification, communication, DFTRV/IDFTRV, FFT/IFFT, and other computations) for Key Generation. Table 4 shows the detailed time consumption of different entities in different stages for encryption.The time consumption of decryption is not shown in Figure5. Since there is only one polynomial multiplication, the time consumption of communication is dominant in the process of decryption, as illustrated in Figure 3. Therefore, the time consumption of outsourcing decryption (0.379 s) is larger than the nonoutsourcing decryption (0.103 s).Figure 5
Time consumption on stages of the outsourcing and nonoutsourcing schemes.Table 3
Details of time consumption in key generation.
Verification (s)DFTRV/IDFTRV (s)Communication (s)Others (s)FFT/IFFT (s)User0.370.890.460.580Smart contract001.0100Computational nodes000.5200.19Table 4
Details of time consumption in encryption.
Verification (s)DFTRV/IDFTRV (s)Communication (s)Others (s)FFT/IFFT (s)User0.240.930.430.110Smart contract000.9900Computational nodes000.3700.20


## 7. Conclusions

In this paper, we propose a secure outsourcing algorithm for polynomial multiplication that reduces the local complexity toOn. According to security analysis, our algorithm is secure against passive and active attackers. We also propose a framework for blockchain-based computation outsourcing. It has a credit-based task allocation strategy, which significantly reduces the probability of failed computations. Using this framework, we implement the secure outsourcing of FHEHIL, in which the basic computations including polynomial multiplication and modular exponentiation can be securely outsourced by our proposed algorithms. The security analysis and experimental results show that our proposed outsourcing schemes are secure and efficient. In the future, we will apply the secure outsourcing of FHEHIL into some practical secure computation problems, such as the millionaire problem, and set operation problems.



---

*Source: 9962575-2021-06-25.xml*