Lightning-Fast and Privacy-Preserving Outsourced Computation in the Cloud
Ximeng Liu Robert H. Deng Pengfei Wu Yang Yang









































 
 






























 




In this paper, we propose a framework for lightning-fast   privacy-preserving   outsourced computation framework in the cloud, which we refer to as LightCom. Using LightCom, a user can securely achieve the outsource     data storage and fast secure data processing   in a single cloud server  different  from  the existing  multi-server outsourced computation  model.
Specifically, we first present a general secure computation framework for LightCom under the cloud server equipped with multiple Trusted Processing Units (TPUs) which face the side-channel attack. Under the LightCom, we design two specified fast processing toolkits which allow the user to achieve the commonly-used  secure integer computation and secure floating-point computation against the  side-channel information leakage of TPUs, respectively.
 Furthermore, our LightCom can also  guarantee access pattern protection during the data processing and achieve user private information  retrieve after the computation. We prove that the proposed LightCom can successfully achieve the goal of single cloud outsourced data processing to avoid the extra computation server and trusted computation server, and demonstrate the utility and the efficiency of LightCom using simulations.
 







 Privacy-Preserving;    Secure Outsourced Computation; Homomorphic Encryption;  Secret Sharing Technique; Against Side-channel Attack.   


 Lightning-Fast and Privacy-Preserving Outsourced Computation  in the Cloud
    Ximeng Liu Member, IEEE,
Robert H. Deng, Fellow, IEEE, Pengfei Wu, Student Member, IEEE, Yang Yang, Member, IEEE
                       
         
         X. Liu,  Y. Yang are with  College of Mathematics and Computer Science, Fuzhou University, Fuzhou, China. E-mail: snbnix@gmail.com (X. Liu),  yang.yang.research@gmail.com (Y. Yang).
         
         X. Liu,  R.H. Deng, Y. Yang  are with the School of Information Systems, Singapore
Management University, Singapore. E-mail:   robertdeng@smu.edu.sg (R.H. Deng)
         
       P. Wu is with School of Software and Microelectronics, Peking University, Beijing, China. E-mail: wpf9808@pku.edu.cn.      
       




 
    Received: date / Accepted: date
====================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================











































































































































§ INTRODUCTION








  

 
 
 
 
 
 
THE internet of things (IoT), embedded with electronics, Internet connectivity, and other forms of hardware (such as sensors), is a computing concept that describes the idea of everyday physical objects being connected to the internet and being able to identify themselves to other devices. With large numbers  of IoT devices, huge amount of data are generated for usage. 
 According to  IDC[http://www.vebuso.com/2018/02/idc-80-billion-connected-devices-2025-generating-180-trillion-gb-data-iot-opportunities/], the connect IoT devices  will reach  80 billion  in 2025, and help to  generate 180 trillion gigabytes of new data that year.  A quarter of the data will create in real time, and  95% is to come from  IoT real time data. With such large volume real-time data are generated, it is impossible  for  the resource-limited IoT devices to store and do the data analytics in time.  
Cloud computing, equipped     
 almost unlimited power of storage and computing, provides diversity of   services on    demand, such as,  storage, databases, networking, software, analytics, intelligence. With the help of cloud computing, 49 percent of data will be stored in public cloud environments by 2025 [ https://economictimes.indiatimes.com/tech/internet/global-data-to-increase-10x-by-2025-data-age-2025/articleshow/58004862. cms?from=mdr]. Thus, it is unsurprisingly that
 the huge volume  data generated by IoT devices are outsourced  to the cloud for long-term storage and achieve real-time online processing. 

 







 


Despite the advantages provided by IoT-cloud  data outsourcing  architecture,  the individual IoT users are hesitated to the   system for data storage and processing  without any  protection method. 
In the Internet of Medical Things example <cit.>,  patients' wearable mHealth devices that always  equipped with the biometric measurements sensors (such as heart rate, perspiration levels, oxygen levels) to  record  the physical sign of the patient.  The hospital can use client’s PHI decision-making model to automatically check a patients’ health status.  If no   protection method is adopted, patients's physical sign can be capture by adversary.  Moreover, the hospital model can be got  by other third-party company to make profit.  Use the traditional  encryption technique  can protect the data from leakage, however,  the ciphertext lost the original meaning of the plaintext which cannot doing any computations.

 

  
  
  
  
  Protecting the data and achieve the secure outsource computation   simultaneously is an eye-catching field to solve the above problems. 
Currently, there are typically   two aspects of  techniques  to achieve secure outsourced computation: theoretical cryptography solution and system security  solution. 
  For the cryptography point of view, homomorphic encryption  <cit.>  is considered as a super-excellent solution for the outsourced computation which allows the third-party to perform the computation on the encrypted data without reveal the content of the plaintext.  Fully homomorphic encryption <cit.> can achieve arbitrary computation on the plaintext corresponding to the    complex operations on ciphertext. However, the computation overhead is still tremendous which is not fit for the piratical usage (e.g., it requires 29.5 s to run secure integer multiplication computation with a common PC <cit.>).  
  Semi-homomorphic encryption <cit.> only supports one types of  homomorphic (e.g. additive homomorphic), can achieve  complex data computation on the encrypted data with the help of  extra honest-but-curious servers. But, the extra computation server will increase possibility of the information leakage. Recently, for the industrial community,  trusted execution environment  (TEE, such as Intel^ Software Guard Extensions (SGX)[https://software.intel.com/en-us/sgx] and ARM TrustZone[https://developer.arm.com/ip-products/security-ip/trustzone]) is developed to achieve the secure computation which 
   allows user-level or operating system code to define private regions of memory, also called enclaves.  The data in the enclave are protected and unable to be either read or saved by any process outside the enclave itself. The performance of the TEE is equivalent to the plaintext     computation overhead. Unfortunately, TEE     easily faces the side-channel attack, and the information inside the enclave can be leaked to the adversary[https://software.intel.com/en-us/articles/intel-sgx-and-side-channels] [https://www.arm.com/products/silicon-ip-security/side-channel-mitigation].
Thus,
an fascinating problem appears for creating a system to balance the  usage of   practical outsourced  computation system and  eliminate the extra information leakage risk: how can a single cloud securely perform the  arbitrary outsourced computation without the help of extra third-party computation server or trusted authority, which interactions between the user and the cloud kept to a minimum.
   
  
 









In this paper, we seek to address the above-mentioned challenge by presenting a framework for   lightning-fast  and privacy-preserving outsourced computation Framework in a Cloud (LightCom). We regard the contributions of this paper to be six-fold, namely:



  * Secure Data Outsourced Storage. The LightCom allows each user  to outsource his/her individual data to a cloud data center   for secure storage without compromising the privacy of his/her own   data to the other unauthorized storage.  


  * Lightning-fast and Secure Data Processing in   Single Cloud. The LightCom   can allow  in a single cloud  equipped  with multiple Trusted Processing Units (TPUs), which provides a TEE to achieve the user-centric  outsourced   computation on the user's encrypted data. 
Moreover, the data in  outside untrusted storage are secure against  chosen ciphertext attack for long-term, while data  insider TPUs can be  protected against side-channel attack. 



  * Outsourced  Computation Primitive Combinable.   Currently,   the outsourced computation methods focus on a special computation task, such as outsourced exponential computation. Different specific outsourced tasks are constructed with different crypto preliminary. Thus, the previous computation result cannot be directly used for the input of the next computation.
Our LightCom can directly solve the problem with uniform design method which can achieve computation combinable. 



  * No Trusted Authority Involved.
In most of the existing cryptosystem,  trusted authority is fully trusted which is an essential party in charge of distributing the public/private keys for all the other parties in the system. Our LightCom does not involve an additional fully trusted party in the system which makes the system more efficient and practical.













  * Dynamic Key/Ciphertext Shares Update. To reduce the user's private key and data leakage risk during the processing, our LightCom randomly splits the key and data into different shares which are processed in different TPUs, cooperatively. To avoid long-term shares leaking for recovering the original secrets, 
our LightCom allows TPUs updating  user's   “old” data/private-key shares  into the “new” shares on-the-fly dynamically 
 without  the participation of the data user.
 


  * High User Experience. 

Most existing privacy-preserving computation technique requires user to  preform different  pre-processing technique   according the function type  prior to  data outsourcing. 
The LightCom  does not need the data owner to perform any pre-processing procedure - only needs to encrypt and outsource the data to the cloud for storage. 
Thus, interactions between the user and the cloud     kept to a minimum - send the encrypted data to the cloud,  and received  outsourced  computed results in a single round.

Motivation and Technique Overview. As the sensitive information contained inside   TPU   can be attacked, our primary goal of the LightCom framework is to achieve secure computation in a single cloud without the help of an additional party.  The idea is to let the data store in the outside storage, and achieve privacy-preserving computation insider TPU.
  The main challenges are how to achieve both secure data storage and data processing against side-channel attacks, simultaneously.  To solve the previous challenge, 
 we use a new  Paillier Cryptosystem Distributed Decryption (PCDD) which can achieve semantic secure data storage.  To prevent information leakage inside  TPU,   our LightCom uses one-time pad   by adding some random numbers on plaintext of the  PCDD ciphertext.
Even the “padded” ciphertext for TPU enclave for decryption and process, the attacker still cannot get the original message of the plaintext.  To achieve ciphertext decryption, our LightCom uses multiple TPUs, and each TPU only stores a share of the private key to prevent the user's key leakage risk. 
Even some partial private key/data shares may leak to the adversary; our framework can successfully update these shares dynamically inside the TPU to make the leaked shares useless.    
More importantly, all the secure execution environment  (called TPU enclaves) in TPUs are dynamically building and release for the secure computation in our LightCom framework,  which can further decrease the information leak risk in the enclave. 
  

   
   
   
  

 


  

 






 







§ PRELIMINARY






 §.§ Notations

 
Throughout the paper, we use x to denote bit-length of x, while  L(x)  denotes the number of element in x. Moreover, we use pk_a and sk_a to denote the public and private keys of a Request User (RU) a,  sk_a^(1), sk_a^(2) to denote the partial private keys that form sk_a, [[x]]_pk_a to denote the encrypted data of x using pk_a in public-key cryptosystem. For simplicity, if all ciphertexts belong to a specific RU, say a, we   simply use [[x]] instead of [[x]]_pk_a. We use notion ⟨ m  ⟩ to denote the data share of m, i.e., each party  i (i = 1,⋯, P) holds m_i, such that ∑_i=1^Pm_i = m.
 
  

 §.§ Additive Secret Sharing Scheme (ASS)

 
 Give m∈𝔾 (𝔾 is a finite abelian
group under addition),  the  
additive secret sharing scheme (a.k.a. P-out-of-P secret sharing scheme) can be classified into   the following two algorithms – Data Share Algorithm () and Data Recovery Algorithm (): 

(m): Randomly generate X_1,⋯, X_P-1∈𝔾,  the algorithm  computes X_P = m -(X_1+⋯ +X_P-1), and outputs X_1,⋯, X_P.

 (X_1,⋯,X_P): With the shares  X_1,⋯,X_P, the algorithm can recover the message m by computing  
 with m = X_1+⋯+X_P under group 𝔾.
 


 §.§ Additive Homomorphic Encryption Scheme



To reduce the communication cost of the LightCom, we used an Additive Homomorphic Encryption (AHE)  scheme as the basis.  Specifically, we use one of the AHE support threshold decryption called  Paillier Cryptosystem Distributed Decryption  (PCDD) in our previous work which contains six algorithms called 
 Key Generation (),  Data Encryption (),  Data Decryption (), 
 Private Key Splitting (),   
 Partially decryption (), 
 Threshold decryption  ().    
 The plaintext is belonged to ℤ_N and the ciphertext is belonged to ℤ_N^2.
 The construction of the above algorithms can be found in Supplementary Materials Section C. 
Here, we introduce the two properties of the PCDD as follows:
1)  Additive Homomorphism:  Given ciphertexts [[m_1]] and [[m_2]] under a same public key pk, the additive homomorphism can be computed  by ciphertext multiplication, i.e., compute
[[m_1]] · [[m_2]]  = [[m_1+m_2]].  
2) Scalar-multiplicative Homomorphism: Given ciphertext [[m]]  and a constant number c ∈ℤ_N, it has 
([[m]])^c  
= [[cm]]. 


With the two properties given above,  we   show that our PCDD have the polynomial  homomorphism property, i.e.,  given [[x_1]],⋯, [[x_n]] and a_1,⋯,a_n,  it has 
 

 [[a_1 · x_1 + a_2 · x_2 + ⋯ a_n x_n ]]  ← [[x_1]]^a_1· [[x_2]]^a_2⋯ [[x_n]]^a_n.
  

 
   

 §.§ Mathematical Function Computation

In this section, we define the function which is used for data processing in our LightCom. 

 
  Let D = {(x_1,⋯, x_v) : x_i ∈𝔾} be a subset of 𝔾^v. We define the deterministic multiple-output  multivariable function as follows:
 (I) A multiple-output  multivariable function F of v variables is a rule which assigns  each
ordered vector (x_1,⋯, x_v)   in D to a unique vector denoted (y_1,⋯, y_w), denote (y_1,⋯, y_w) ←F(x_1,⋯,x_v). 
 (II) The set D is called the domain of F. 
 (III) The set {F(x_1,⋯,x_v)| (x_1,⋯, x_v) ∈ D} is called the range of F.
  
  
     Note that the deterministic  multiple-output  multivariable  function is the general case of the deterministic   multiple-output  single-variable function   (v=1),  deterministic   single-output  multivariable  function (w =1), and deterministic single-output single variable function  (v =1, w=1). As all the functions used in our paper can  be successfully executed by a polynomial deterministic Turing machine (See Supplementary materials Section A), we omit the   word  “deterministic” in the rest of the paper. 

 

 


      
     

  

  
 

  
 



§ SYSTEM MODEL & PRIVACY REQUIREMENT


In this section, we formalize the LightCom system model,  and define the attack model.



 §.§ System Model



In our LightCom system, we mainly focus on how the cloud server responds to a user request on outsourced computation   in a  privacy-preserving manner. The system comprises Request User (RU) and  a Cloud with Untrusted Storage  (UnS) and Trusted Processing Units (TPUs)  - see   Fig. <ref>.



  
  * A RU   generates his/her public key, private key shares, and data shares. After that, the RU can securely outsource the public key and private/data shares to the cloud‘s  UnS for secure storage (See 1).  
   Moreover, the RU can also request a cloud to perform some secure outsourced computations on the outsourced data, and securely retrieve the final encrypted results (See  5).
  
  * A UnS of the cloud has `unlimited' data storage space to store and manage data outsourced from the registered RU.  Also, the UnS also stores all the intermediate and final results for the RU in encrypted form.
  
  * The TPUs of the cloud provides online computation ability for each  RUs.   Each TPU provides isolation secure computing environment for individual RU and can load   RU's data shares from UnS (See 2), perform certain calculations over the data shares (See 3), and then securely seal the data shares in UnS for storage (See 4)[See the algorithm  and  in Section <ref>.].  Note that one TPU cannot load other TPU's sealed data which are stored in UnS.  


 












 




 



 §.§ Attack Model
 
 In our attack model,  the cloud is curious-but-honest party, which strictly follow the protocol, but are also interested in learning  data belonged  to the RUs.  The UnS inside the cloud is transparency to both the cloud and the outsider passive attackers. Every  TPU can provide a secure execution environment (a.k.a., TPU enclave) for a RU which is secure against the other RU, the cloud and outsider passive attackers. 
 The inside non-challenge 
 RUs and outside attackers can also be interested to learn challenge RU's data.   Therefore, we introduce  three active adversaries A^*_1, A^*_2, A^*_3, which can  simulate the malicious actions corresponding to the outside attackers, non-challenge RUs, UnS, respectively. The goal of these adversaries is to get the challenge RU's plaintext or try to let the challenge RU get wrong computation result with the following capabilities:
  
1) A^*_1 acts as the outside attacker that  may eavesdrop on all communication links and CP's UnS, and  try to decrypt the challenge RU's  encrypted data. 
  2) A^*_2 may compromise RUs, with the exception of the challenge RU, to get access to their decryption capabilities, and try to guess all plaintexts belonging to the challenge RU.  
     3) A^*_3 may compromise the TPU to guess plaintext values of all data shares sent from the UnS by executing an interactive protocol.  
Noting that the above  adversaries A^*_1, A^*_2, A^*_3 are restricted from compromising (i) all the TPUs concurrently[Note that P≥ 3 TPUs are required in LightCom for the security consideration.], and (ii) the challenge RU. 











 





§ BASIC PRIVACY PRESERVING   COMPUTATION PROTOCOLS


In this section, we introduce our general design method of the mathematical function for LightCom. Moreover, the dynamic private/data share update without the participation of the DO are also introduced. 


   
 
 

 




 
 
 

 
 
    
   
   
   

 §.§ The LightCom Design Method for the Single  Functions

   
  
   Our LightCom achieves the user data's privacy during the efficiency in the outsourced cloud with three-dimensional protection: 1) secure storing in the untrusted cloud storage; 2) secure processing in TPUs against side-channel attack; 3) efficient and dynamic outsourced key and data shares updating. Specifically, 
     to outsource the data to the cloud, the RU first initializes the system, uses the RU's public key to encrypt the data and outsource these encryptions along with the system parameters to UnS for storage. To achieve the second-dimensional protection,   our LightCom  uses the data sharing-based secure computation method between TPUs which can resist the side-channel attacks even the PPCD ciphertexts are decrypted. After finishing the   processing,   the data are sent back to UnS for further processing to finish the corresponding functionality defined in the program, and the enclaves in TPUs are released.  Moreover, to tackle the leaked private key and data shares, all the TPUs can jointly update these shares without the help of RU. Thus, the LightCom can classify into the following four phases.  
      
         

 1) System Initialize Phase:
 Firstly,  
  the RU generates a    public key pk and  private key is sk of appropriate public key crypto-system, and then   splits the private key sk into P shares sk_i (i = 1,⋯, P) with the  algorithm. After that, 
  for each TPU i in the cloud,    it initials an enclave i,  builds a secure channel, and 
   uploads the sk_i to the     enclave i securely. Finally, the TPU i uses the data sealing to securely  stored the   pk, sk_i in to UnS.  
   
   
 
   
   
   
   2) Data Upload Phase: 
  In the phase, the  RU  
    randomly separate  the data  
   x_j,1,⋯,x_j,P∈𝔾, such that x_j,1+ ⋯ +x_j,P = x_j for j = 1,⋯, v. Then, the TPU i
(i = 1,⋯, P)   creates the enclave i. After that, 
       the RU  defines  the program C_i for some specific computation function,  builds a secure channel with TPU enclave  i, 
        remotely loads x_1,i,⋯,x_v,i, C_i into the enclave i,  and securely seals      x_1,i,⋯,x_v, i, C_i in the UnS.  After that,   TPU i release    enclaves i for all the i = 1,⋯, P.

   
   
    3) Secure  Computation Phase:     The goal of the phase is to achieve the secure computation among the TPUs according to the user-defined program C_i. Thus, it works as follows:
       

  * (3-1) Each TPU i generates an enclave i. After that, all the TPUs build a secure channel with each other.     Load  sealed   data  x_1,i,⋯,x_v,i, pk, sk_i,  C_i  to enclave i from UnS,  and denote them as S_i.

  * (3-2)  TPUs jointly compute  
        ( y_1,1,⋯,y_w,1:⋯: y_1,P,⋯,y_w,P ) ← (S_1:⋯:S_P)
        according to the user-defined  program C_1,⋯,C_P. [The construction of  General Secure Function Computation Algorithm (GenCpt) can be found in section <ref>.]
        
  
  * (3-3)      All the TPUs   jointly  update the private key shares and data shares dynamically. 

    
     After  the above computation, the TPU i seals y_1,i,⋯,y_w,i into the UnS, and releases the enclave.
    
    
   
    
    
 

 
  
       
     
    4) Data Retrive  Phase:
If the RU needs to retrieve the computation results from the cloud, the  TPU i creates an enclave i, opens the sealed data y_1,i,⋯,y_w,i,  builds a secure channel with the RU, and sends the data shares back to RU. 
   Once all the shares are sends to   RU, the RU computes y_j = ∑_i=1^P y_j,i for j = 1,⋯,w. 
      
   
     

 §.§ The LightCom Design for   Combination of the Functions

      
   Our LightCom can support for single data outsourced with  multiple function  operations. The procedure is as follows:
   
   1) System Initialize Phase: Same to the LightCom with single function in Section <ref>.
   
     2) Data Upload Phase:  
     After the system initialize phase, the  RU  
    defines  the program C_i,t for TPU i (i = 1,⋯, P) with function computation step t (t = 1,⋯, ζ) and  randomly separates  the data  
   x_j,1,1,⋯,x_j,1,P, such that x_j,1,1+ ⋯ +x_j,1,P = x_j for j = 1,⋯, v [Data share x_j,t,i is for TPU enclave i for data j of function computation step-t.].
After that, 
       the RU    builds a secure channel with TPU enclave  i, 
        remotely loads C_1,i,⋯,C_ζ,i,  x_1,1,i,⋯,x_v,1,i into the enclave i,  and securely seals     these data in the UnS.  After that,   TPU i release    enclaves i for all the i = 1,⋯, P.
      
            3) Secure  Computation Phase:  The goal of the phase is to achieve the secure computation among the TPUs according to the user-defined program C_t,i for function t (t = 1,⋯, ζ). Thus,  for each step    t, the   phase works as follows:
   
       

  * (3-1) Each TPU i generates an enclave i. After that, all the TPUs build a secure channel with each other.     Load  sealed   data  x_1,t,i,⋯,x_v,t,i, pk, sk_i, C_1,i,⋯,C_ζ,i  to enclave i from UnS,  and    put   them in a set E_t,i.

 


  * (3-2)  TPUs jointly compute  
        ( y_1,t,1,⋯,y_w,t,1:⋯: y_1,t,n,⋯,y_w,t,P ) ← (E_t,i:⋯:E_t,i), 
        according to the user-defined  program C_1,i,⋯,C_ζ,i.
        
  
  * (3-3)      All the TPUs   jointly  update the private key and data shares. If t =  ζ, the TPU i seals y_1,ζ,i,⋯,y_w,ζ,i  into the UnS,   release the enclave. Otherwise, move to  (3-4) for further computation. 

     
  
     


  * (3-4) Select  x_1,t+1,i,⋯,x_v,t+1,i from the  y_1,t,i,⋯,y_w,t,i for TPU i.  Then, the TPU i seals x_1,t+1,i,⋯,x_v,t+1,i  into the UnS,   release the enclave, and move to  (3-1) for next step computation.     
      After the t step is finished, the TPU i seals the set E_j   into the UnS, and releases the corresponding enclave.
         
             4) Data Retrieve  Phase:  
                After the computation, TPU i new an enclave i, opens the sealed  data y_1,ζ,i,⋯,y_w,ζ,i,  builds a secure channel with the RU, and sends these data back to  the RU. 
   Once all the TPU's data are sent, the RU computes the result   y_j,ζ = ∑_i=1^P y_j,ζ,i for step ζ (j = 1,⋯,w) to get the final results.
             
             
                      
        

 §.§ General Secure Function Computation Algorithm  (GenCpt)
   
        
      As the key component of the LightCom, the General Secure Function Computation Algorithm  () are proposed to achieve the  secure deterministic multiple-output multivariable function
     F computation which is introduced  in definition 1. Assume TPU i  (i = 1,⋯, P) holds x_1,i,⋯, x_v,i,  can securely output 
       y_1,i,⋯, y_w,i for each TPU i, such that (y_1,⋯, y_w) ←F(x_1,⋯,x_v), where x_j,1+⋯ + x_j,P = x_j and y_k,1+⋯ + y_k, P = y_k for j = 1,⋯, v; k = 1,⋯, w. The  can be classified into offline/online stages and constructed as follows:
        
    Offline Stage:  Each TPU i (i  = 1,⋯,  P) creates an
enclave i, loads the sealed   keys pk, sk_i and program C_i into the enclave from the UnS, builds a secure channel with the other TPUs.[As  offline stage of   the secure computations needs to do TPU enclave initialization,  we just omit the description in the rest of the section.]   
    With the help of homomorphic public key cryptosystem, all the  TPUs    collaboratively 
    generate the shares of random numbers   and put them into a set R_i. Note the     shares in set   R_i cannot be known by all the other TPUs during the generation. 
 After the above  computation, each TPU i seals the R_i into the UnS, respectively. 
     
   
     Online Stage[The input data x_1,i,⋯,x_v,i,,  public key pk,  private key shares sk_i,  and the program  C_i are loaded in the step of (3-I) of both section <ref>  and <ref>].  
   For each TPU i (i  = 1,⋯, P), loads the sealed   random numbers set R_i from offline stage into the enclave i. 
 All the TPUs cooperatively compute and output the results 
 

 (y_1,i,⋯, y_w,i) ← f_i(x_1,i,⋯,x_v,i, R_i), 
 where f_i is the  combination of +, × for ℤ_N and ⊕, for ℤ_2 with specific functionality according to the   program C_i.
 
 
 
 
 
   
     

 §.§ Private Key Share Update against Side-Channel Attack

   
 The private key shares are more sensitive and vulnerable, as the adversary can use the private key  to decrypt the RU's data in the untrusted storage if all shares of the private key are leaked by side channel attack.  Thus, we should frequently update the key shares in the TPU enclave. The intuitive idea is to let the  RU   choose a new private key, separate the new private key into different key shares,   update these key shares in the different individual enclaves, and update all the ciphertext with the new key.  However, the above strategy has the main drawback:  the RU has to be involved in the private/public key update phase which brings extra computation and communication cost. Thus, in this case,   the RU needs to generate and update the public/private keys frequently which is impractical. Thus, we bring the idea of proactive secret sharing into the LightCom: keeps the public/private key unchanged, the TPU will periodicity refresh the key shares without the participation of the RU. 
Mathematically,     to renew the shares at period t (t = 0, 1,2,⋯),  we need to update the shares  such that ∑^P_i=1 sk_i^(t+1)=     ∑^P_i=1  sk_i^(t) +  ∑^P_i=1∑^P_j=1δ^(t)_i,j, where ∑_j=1^Pδ_i,j =0, ∑_i=1^P  sk^(0)_i = sk and sk^(0)_i= sk_i for i = 1,⋯, P (See Fig. <ref> for example of private key update procedure with P=3).  The special  construction is as follows:
 
 
 
   
 
 
 

1) Each TPU i (i = 1,⋯, P) creates an enclave i. After that,  TPU i the  builds a secure channel with TPU j's enclave  (j = 1,⋯, P; j ≠ i).  

2) TPU i picks random numbers δ_i,1,⋯,δ_i,P∈𝔾 such that δ_i,1+⋯+δ_i, P = 0 under the group 𝔾, and then  sends δ_i,j to TPU  enclave j.

 3)  After received  δ_j,i, TPU   i 
   computes the new shares sk^(t+1)_i← sk^(t)_i + δ^(t)_1,i+ δ^(t)_2,i + ⋯+δ^(t)_P,i∈𝔾. After that, TPU i 
 erases all the variables which  it used, except for its
current secret key sk^(t+1)_i.


   
     

 §.§ Data Shares Update against Side-Channel Attack

   
   As data shares need to load to TPU for processing, the shares can be leaked to the adversary  
    by side channel attack, and reconstruct the RU's original data.   Thus, we also need to dynamically update data shares x^(t)_1,⋯, x^(t)_P at period t (t = 0,1,2,⋯),   such that ∑^P_i=1 x_i^(t+1)=     ∑^P_i=1 x_i^(t) +  ∑^P_i=1∑^P_j=1δ_i,j, where  ∑^P_i=1 x^(0)_i = x, x^(0)_i= x_i, and ∑^P_j=1δ_i,j =0 for i = 1,⋯, P.  The construction is same to the private key share update method in section   <ref>.
 
 

   
   
   

  
   
  
  

   
    
  
    
  
 
   
  
  

  
    
    
    
    
 


   
  
   
   
   

§ TPU-BASED BASIC DATA SHARES OPERATIONS

   In this section, we introduce some basic TPU-based  data shares operations which can be used as the basis of LightCom.  
   
      

 §.§ Data Domain and  Storage Format

   
   Here, we introduce three  the data group domain for LightCom:  ℤ_N = {0, 1, ⋯,N-1},      𝔻_N = {-⌊N/2⌋, ⋯,0,⋯, ⌊N/2⌋), and  ℤ_2 = {0,1}. As we use PCDD for offline processing and its plaintext domain is ℤ_N, we define the   operation ⌈ x ⌋_N which   transforms data x from group ℤ_N into the   group 𝔻_N, i.e., 
  
    ⌈ x ⌋_N ←{[         x,  0 ≤ x<N/2;       x-N, N/2 ≤ x<N.;            ].

  Moreover, the data ⌈ x ⌋_N in group 𝔻_N can be directly transformed into group ℤ_N with x = ⌈ x ⌋_N  N. It can be easily verified that group 𝔻_N and  ℤ_N are isomorphism. 
  
  To guarantee the security of secret sharing, two types of data shares are used in the LightCom, called integer share (belonged to ℤ_N) and binary share (belonged to ℤ_2). For the integer share separation, RU only needs to execute (m), such that m = m_1+⋯+m_P, where m, m_1,⋯,m_P∈𝔻_N. For the binary shares, RU    executes (𝔪), such that 𝔪 = 𝔪_1+⋯+ 𝔪_P, where 𝔪, 𝔪_1,⋯, 𝔪_P∈ℤ_2.  After that, RU securely sends integer share m_i or binary shares 𝔪_i to TPU i, and seals to UnS for securely storage. 


      

 §.§ System Initial and Key Distribution


The LightCom system should be initialized before  achieving the secure computation. Firstly,  
  the RU executes  algorithm,  output  public key pk=(N,g) and  private key is sk=θ. Then, use  to split key θ into P shares sk_i = θ_i (i = 1,⋯, P). After that, 
  for each TPU i in the cloud,    it initials an enclave i,  builds a secure channel, and 
   uploads the sk_i to the     enclave i securely. Beside, the RU's  PCDD public key  pk and   program C_i for the specific function F are needed to securely send to TPU i (i = 1,⋯, P).
   Finally, the TPU i securely seals the data     pk, sk_i, C_i into UnS.  
   As all the parameters need to load   to the TPU enclaves along with the data shares according the specific functionality, we will not specially  describe it in the rest of the section.
   

  
  
  
  
  
    
    
 



   
      

 §.§ Secure Distributed Decryption Algorithm ()

    Before constructing the  TPU-based operation, we need first to construct the algorithm called  Secure Distributed Decryption   () which allows all the TPUs decrypt PCDD's ciphertext. Mathematically, 
    if enclave in TPU χ contains the encryption [[x]], the goal of  is to output x which contains following steps:  
   1) The TPU enclave χ  establishes a secure channel with the other TPU
enclave i ( i ≠χ).  Then, enclave χ
  sends  [[x]] to all the other enclave i. 
 2)   Once received [[x]], the TPU i uses
      algorithm to get CT_i  and securely  send  CT_i to enclave χ. 3) Finally, the  TPU χ  securely     uses    CT_χ 
      with  algorithm to get x.  
    
    
      

 §.§ Secure TPU-based Data Seal & UnSeal

      
    As TPU enclaves are only provide an isolated  computing   environment during the secure processing, the data in the TPU enclave needs to seal to UnS for long-term storage. Thus, we propose two algorithms called  and  to achieve. 
 
 (x_i): The   TPU i encrypts the data share x into [[x_i]], then uses hash function H: {0,1}^* →ℤ_N with input   the [[x_i]] associated  with TPU t-time period private key share sk^(t)_i to compute 
 S_t,i← H([[x_i]] ||sk^(t)_i||ID_i||t), where ID_i is the transaction identity  for [[x_i]]. Then, TPU i sends [[x_i]] with S_t,i to UnS for storage. 
    
     ([[x]], S_t,i): The   TPU i loads [[x_i]] with S_t,i to the enclave i, and computes H([[x]] ||sk^(t)_i||ID_i||t) to test whether the result is equal to S_t,i. If the equation does not  holds, the algorithm stops and outputs ⊥. Otherwise, the TPU i uses  to get the share  x_i.
     
 
          
    
    
  

 §.§ Random  Shares Generation

The secret sharing based privacy computation requires one-time random numbers for processing. Before constructing the TPU-based computation, we design a protocol called       Random Tuple  Generation Protocol ().     
      The goal of  is to let TPUs  cooperatively generate random tuple 𝔯_i^(1),⋯, 𝔯_i^(ℓ)∈ℤ_2 and r_i ∈𝔻_N  for each TPU    i (i = 1,⋯, P), such that r = -𝔯^(ℓ)2^ℓ-1 + ∑_j =1^ℓ-1𝔯^(j) 2^j-1  and 𝔯^(j) =  𝔯_1^(j)⊕⋯⊕𝔯_P^(j) and r = r_1 +⋯+ r_P holds, where ℓ is the bit-length of random number r ∈𝔻_N. The  generates as follows:
     
1)  The TPU 1 randomly generates 𝔯_1^(1),⋯, 𝔯_1^(ℓ)∈ℤ_2,   encrypts them as [[𝔯^(1)_1]],⋯,[[𝔯^(ℓ)_1]],    denotes them as  [[𝔯^(1)]],⋯,[[𝔯^(ℓ)]], and sends these ciphertexts to TPU 2. 
 
2) The TPU i  (i=2,⋯, P) generates 𝔯_i^(1),⋯, 𝔯_i^(ℓ)∈ℤ_2  and computes 


[[𝔯^(j)]] ← [[𝔯^(j)]]^ (1- 𝔯_i^(j))·  ([[1]] · [[𝔯^(j)]]^N-1)^𝔯_i^(j) =  [[𝔯^(j)⊕𝔯_i^(j)]]. 


    If i ≠P, the TPU i
     sends [[𝔯^(1)]],⋯,[[𝔯^(ℓ)]] to  TPU i+1. 
     If i = P, the TPU P computes 
     

   [[r]] ←  [[𝔯^(ℓ)]]^N-2^ℓ-1·  [[𝔯^(ℓ-1)]]^2^ℓ-2·⋯·  [[𝔯^(1)]].
          

3)   
    For   TPU i (i =  P,⋯, 2),   randomly generates      r_i ∈𝔻_N  and computes  [[r]]  ←  [[r]]  · [[-r_i]], and sends [[r]] to TPU i-1. 
    Once TPU 1 gets  [[r]], uses  to get r, and denotes ⌈ r ⌋_N as r_1. After computation,  each TPU i (i = 1,⋯,  P) holds randomly bits 𝔯_i^(1),⋯, 𝔯_i^(ℓ)∈ℤ_2 and integer  r_i ∈𝔻_N.
    
   




 
 

  
  
   
    

  

 
 
 
  
   
   
    
    


  

     
    
         
   

 §.§ Share Domain Transformation


  

  §.§.§ Binary  Share to Integer Share Transformation  () 

 
    Suppose TPU i hold  a bit share 𝔞_i ∈ℤ_2, where 𝔞_1  ⊕⋯⊕𝔞_P =  𝔰∈ℤ_2, the   goal of the protocol is to generate  a random integer share b_i  ∈ℤ_N for each TPU i, such that b_1  + ⋯ +  b_P =  𝔰.  To execute ,  the TPU 1 randomly generates b_1  ∈ℤ_N, denotes  x =   b_1 and
   𝔰 =   𝔞_1,   encrypts x  as [[  x]],   𝔰 as [[ 𝔰]], and sends [[ x]]  and  [[𝔰]] to TPU 2.
   After that, the TPU i (i=2,⋯, P-1)
    generates b_i  ∈ℤ_N  and computes 
    

[[𝔰]] ← [[𝔰]]^ (1- 𝔞_i)·  ([[1]] · [[𝔰 ]]^N-1)^𝔞_i  =  [[𝔰⊕𝔞_i]], 
[[x]] ← [[x]] · [[b_i]],

 
   and sends  [[ x]] , [[ 𝔰]]  to TPU i+1.
Once received the [[ x]], [[ 𝔰]], TPU P computes 


[[𝔰]] ← [[𝔰]]^ (1- 𝔞_P)·  ([[1]] · [[𝔰 ]]^N-1)^𝔞_P =  [[𝔰⊕𝔞_P]], 
[[ b_P]] ← [[𝔰]]  · [[x]]^N-1, 


and uses the  to decrypt and gets b_P. 


  

  §.§.§ Integer Share to Binary  Share Transformation  () 

 
    Suppose TPU i hold  an integer share a_i ∈ℤ_N, where a_1  + ⋯ +  a_P =  𝔰∈ℤ_2, the   goal of the  protocol is to generate  a random bit share 𝔟_i  ∈ℤ_2 for each TPU i, such that 𝔟_1  ⊕⋯⊕𝔟_P =    𝔰.  To execute  ,  the TPU 1 lets y =    a_1,  encrypts y as [[  y]], and sends the ciphertext to TPU 2 for computation.  After that, the TPU i (i=2,⋯, P)
    uses the share to compute [[y]] ← [[y]] · [[a_i]]. If  i ≠P, TPU i sends [[y]] to TPU i+1.      After that, denote [[𝔰 ]]← [[ y ]], and each TPU i (i=P,⋯, 2)  generates 𝔟_i  ∈ℤ_2  and computes 
      
 
[[𝔰]] ← [[𝔰]]^ (1- 𝔟_i)·  ([[1]] · [[𝔰]]^N-1)^𝔟_i  =  [[𝔰⊕𝔟_i]], 

 
    and sends [[𝔰]] to TPU i-1. Once received [[𝔰]], TPU 1  uses the  to decrypt  [[𝔰]] and denotes the result 𝔰 as 𝔟_1.
    
    

   
  
   
     





    
   
      
     
   
   
       
     
       
    
    
       
       
   

§ TPU-BASED SECURE OUTSOURCED  COMPUTING TOOLKITS IN THE CLOUD

   
   In this section, we introduce and construct the commonly used  secure outsourced  binary and  integer   computation  sub-protocols for  a single cloud. 
 
      

 §.§ Secure Computation over Binary Shares

    
    
    
       

  §.§.§ Secure Bit Multiplication   Protocol ()

  
 
  
The       can achieve plaintext multiplication on bit shares and output are bit shares, i.e.,  given two shares 𝔵_i  ,    𝔶_i   ∈ℤ_2 (i = 1,⋯,P) for  TPU i as input,     securely outputs 𝔣_i   ∈ℤ_2 for TPU i, such that ⊕_i=1^P𝔣_i   = (⊕_i=1^P𝔵_i)     (⊕_i=1^P𝔶_i ).

Offline Stage:   All the TPUs  initialize  their enclaves and load the public parameters to UnS. For
 enclave  1,  generate 𝔞_1, 𝔟_1 ∈ℤ_2,  compute 𝔠 = 𝔞_1 ·𝔟_1 ∈ℤ_2. 
 Encrypt [[𝔞_1]],[[𝔟_1]] and [[𝔠]], and denote them as   [[𝔞]],[[𝔟]], [[𝔠]], respectively. After that, TPU enclave i (i = 1,⋯, P-1) sends [[𝔞]], [[𝔟]], [[𝔠]] to enclave i+1, TPU i+1 generates 𝔞_i+1, 𝔟_i+1 and compute 
 

 [[A]] ← [[𝔞]] · [[𝔠]]^N-1 = [[𝔞· (1-𝔟)]],
    

     

  [[B]] ← [[𝔟]] · [[𝔠]]^N-1 = [[𝔟· (1-𝔞)]],
      

     

      [[C]] ← [[1]] · [[𝔞]]^N-1· [[𝔟]]^N-1· [[𝔠]] = [[(1-𝔟)· (1-𝔞)]],
          

     
    [[𝔠]]    ← [[𝔠]]^(1-𝔞_i+1) (1-𝔟_i+1) · [[C]]^𝔞_i+1·𝔟_i+1·  [[A]]^(1-𝔞_i+1) 𝔟_i+1
       ·  [[B]]^𝔞_i+1(1-𝔟_i+1)=  [[(𝔞⊕𝔞_i+1)  (𝔟⊕𝔟_i+1) ]].

     

     [[𝔞]] ← [[𝔞]]^ (1- 𝔞_i+1)·  ([[1]] · [[𝔞]]^N-1)^𝔞_i+1 = [[𝔞⊕𝔞_i+1]],     

          

  [[𝔟]] ← [[𝔟]]^ (1- 𝔟_i+1)·  ([[1]] · [[𝔟]]^N-1)^𝔟_i+1 =  [[𝔟⊕𝔟_i+1]].
   

     
 
  
 
 
   
  After the above computation,       enclave i  (i = P,⋯, 2) randomly generates 𝔠_i∈ℤ_N and computes [[𝔠]] ← [[𝔠]]^ (1- 𝔠_i)·  ([[1]] · [[𝔠]]^N-1)^𝔠_i = [[𝔠⊕𝔠_i]]. 
When the TPU 2 sends   [[𝔠]] to TPU 1, 
 the TPU 1 uses  to get 𝔠 and denotes as 𝔠_1. 
 After the above computation, each enclave holds 𝔞_i, 𝔟_i, 𝔠_i,  which satisfies  𝔞_1⊕⋯⊕𝔞_P = 𝔞,  𝔟_1 ⊕⋯⊕𝔟_P = 𝔟, 𝔠_1 ⊕⋯⊕𝔠_P = 𝔠 and 𝔠 = 𝔞𝔟. Finally, each TPU i seals 𝔞_i, 𝔟_i,𝔠_i to UnS for storage individually. 







   
    
    Online Stage:  For each TPU   i (i = 1,⋯, P), load the   𝔞_i, 𝔟_i, 𝔠_i into the enclave i. Then, 
compute X_i =  𝔵_i ⊕𝔞_i and Y_i =  𝔶_i  ⊕𝔟_i. Securely send X_i and Y_i to other enclave j (j = 1,⋯,P; j ≠ i).
After receiving other X_j and Y_j,  each TPUs  computes  X = ⊕_i=1^PX_j and    Y = ⊕_i=1^P Y_j.
For TPU i (i = 1,⋯, P-1), compute 𝔣_i←𝔠_i ⊕ (𝔟_i  X) ⊕ (𝔞_i  Y). 
Then,  TPU P  
computes 𝔣_P←𝔠_P⊕(𝔟_P X) ⊕ (𝔞_P Y) ⊕ (X  Y).   Here, we denote the protocol as 
    ⟨𝔣⟩←(⟨𝔵⟩,⟨𝔶⟩ ).   
    
     

  §.§.§ Secure Bit-wise Addition Protocol ()

  The   describes as follows: 
  the TPU i holds bit shares 𝔞_i^(ℓ),⋯, 𝔞_i^(1) of ℓ bit-length integer a and 𝔯_i^(ℓ),⋯, 𝔯_i^(1) of ℓ bit-length integer r. The goal is to compute 𝔶_i^(ℓ),⋯, 𝔶_i^(1), such that y = a+r, where y = - 𝔶^(ℓ) 2^ℓ-1 + ∑_j=1^ℓ-1𝔶^(j) 2^j-1,  𝔞^(j) = 𝔞^(j)_1 ⊕𝔞^(j)_2 ⊕⋯⊕𝔞^(j)_P, 𝔶^(j) = 𝔶^(j)_1 ⊕𝔶^(j)_2 ⊕⋯⊕𝔶^(j)_P and  𝔯^(j)  = 𝔯^(j)_1 ⊕𝔯^(j)_2 ⊕⋯⊕𝔯^(j)_P. The idea is easy and simple:  use the binary addition circuit to achieve the addition, i.e,  compute  the integer addition as  𝔶^(j) = 𝔞^(j)⊕𝔯^(j)⊕𝔠^(j) and 𝔠^(j+1) = (𝔞^(j)𝔯^(j) ) ⊕ ((𝔞^(j)⊕𝔯^(j)) 𝔠^(j)) for j = 1,⋯,ℓ.
    The procedure of  works as follows:
    
   1)   For each TPU i (i = 1,⋯, P) and each bit position j = 1,⋯, ℓ, all the TPUs jointly  compute 
   𝔡_i^(j)←𝔞_i^(j)⊕𝔯_i^(j) and
  ⟨𝔢^(j)⟩←(⟨𝔞^(j)⟩, ⟨𝔯^(j)⟩).   After using  the computation of , it indeed computes 𝔢^(j) = 𝔞^(j)𝔯^(j). 
  
  
2)  Each TPU i  sets 𝔠_i^(1)← 0 and 𝔶_i^(1)←𝔡_i^(1).  Then,    for j = 2,⋯, ℓ, all TPUs jointly computes 
  
 
 ⟨𝔡^(j-1)⟩←(⟨𝔡^(j-1)⟩, ⟨𝔠^(j-1)⟩).
  
 
   Moreover, for each TPU i  locally computes
  

 𝔠_i^(j)←𝔡_i^(j-1)⊕𝔢_i^(j-1) and 
 𝔶_i^(j)←𝔡_i^(j)⊕𝔠_i^(j).    
 

 and outputs  𝔶_i^(j) for all j.
 
   
   
   

 
  
  
      

  §.§.§ Secure Bit Extraction  Protocol ()

  
  Suppose  TPU  i  (i=1,⋯,P) contains an integer share u_i, where  u = ∑_i=1^P u_i.
  The goal of  is to output the bit extraction  shares  𝔲^(ℓ)_i,⋯, 𝔲^(1)_i for each TPU i  (i = 1,⋯, P), where u = - 𝔲^(ℓ) 2^ℓ-1 + ∑_j=1^ℓ-1𝔲^(j) 2^j-1  and 𝔲^(j) = ⊕_i=1^P𝔲^(j)_i. The  also contains offline/online phase which describes as follows:
  
  
  Offline Phase: Execute  to get 𝔯_i^(ℓ),⋯, 𝔯_i^(1) and r_i for party i.
  Then,  all the TPUs need to jointly compute 𝔞^(ℓ),⋯, 𝔞^(1)∈ℤ_2, such that 𝔞^(ℓ)⊕⋯⊕𝔞^(1) = 0.
  Firstly, 
  TPU 1 randomly generates 𝔞_1^(ℓ),⋯, 𝔞_1^(1)∈ℤ_2 and let
   𝔱^(j) = 𝔞_1^(j) for j = 1,⋯,P. After that, the TPU i
    generates 𝔞_i^(ℓ),⋯, 𝔞_i^(1)∈ℤ_2, computes 
    

[[𝔱^(j)]] ← [[𝔱^(j)]]^ (1- 𝔞_i^(j))·  ([[1]] · [[𝔱^(j)]]^N-1)^𝔞_i^(j) =  [[𝔱^(j)⊕𝔞_i^(j)]], 


    and sends these ciphertexts to TPU i+1.
Once  the [[𝔱^(ℓ-1)]],⋯, [[𝔱^(0)]] are received, the TPU P   uses the  to decrypt, gets 𝔱^(ℓ),⋯, 𝔱^(1) and denotes them as 𝔞_P^(ℓ),⋯, 𝔞_P^(1).  After that, each TPU i seals 𝔯_i^(ℓ),⋯, 𝔯_i^(1) and r_i and 𝔞_i^(ℓ),⋯, 𝔞_i^(1) in UnS, respectively.
  
  
  
 Online Phase: The TPU  i computes v_i = u_i-r_i, encrypts v_i and  sends [[v_i]] to TPU P. After received all the encryptions, the TPU P
  computes [[v]]  ←∏_i=1^n [[v_i]] and executes  to get the 
   v, and computes ⌈ v ⌋_N.  Then,  TPU P generates its two’s complement binary representation 𝔳^(ℓ-1),⋯, 𝔳^(0),
  and computes 𝔳^(j)_P←𝔳^(j)⊕𝔞_P^(j), where j = 1,⋯, ℓ. Other TPU i (i = 1,⋯,P-1) keeps other 𝔳^(ℓ)_i ←𝔞^(ℓ)_i,⋯, 𝔳^(1)_i  ←𝔞^(1)_i unchanged. 
  
  
  After that, all the TPUs jointly compute  
  

  (𝔲⃗_1,⋯,𝔲⃗_P) ← (𝔳⃗_1,⋯,𝔳⃗_P; 𝔯⃗_1,⋯,𝔯⃗_P), 
    

  where     
  𝔲⃗_i = (𝔲_i^(ℓ) ,⋯, 𝔲_i^(1)), 𝔳⃗_i = (𝔳_i^(ℓ) ,⋯, 𝔳_i^(1)), 𝔯⃗_i = (𝔯_i^(ℓ) ,⋯, 𝔯_i^(1)). Finally, the  algorithm outputs
   𝔲⃗_i = (𝔲_i^(ℓ) ,⋯, 𝔲_i^(1)) for TPU i = 1,⋯, P.

       

 §.§ Secure Integer Computation 

       
   

  §.§.§ Secure Multiplication Protocol ()

  
 
  
The         achieves integer  multiplication over integer shares, i.e.,  given   shares x_i, y_i (i = 1,⋯, P) for  TPU i as input,     securely outputs f_i for TPU i, such that ∑_i=1^P f_i = x · y, where data shares x_i, y_i satisfy x = ∑_i=1^P y_i and y = ∑_i=1^P y_i.

   Offline Stage:    All the TPUs  initialize  their enclaves and load the public parameters to the UnS. Then, for the 
 enclave  1,  it generates a_1, b_1 ∈𝔻_N,  computes z = a_1 · b_1,  encrypts [[a_1]],[[b_1]], [[z]], and lets them be [[a]],[[b]], [[c]], respectively. After that, enclave i (i = 1,⋯,P-1) sends [[a]], [[b]], [[c]] to enclave i+1, TPU i+1 generates a_i+1, b_i+1 and computes 
 

 [[c]] ← [[c]] · [[a_i+1· b_i+1]] ·  [[a]]^b_i+1·  [[b]]^a_i+1,   


 [[a]] ← [[a]] · [[a_i+1]],   [[b]] ← [[b]] · [[b_i+1]].
  

  After the computation, for  i = P,⋯, 2,  TPU enclave i generates   c_i ∈𝔻_N
  and
  computes [[c]] = [[c]] · [[c_i]]^N-1. After the computation, the TPU   2 sends   [[c]] to TPU   1.
  Then, TPU 1 uses  to get c and denotes the final result ⌊ c ⌉_N as c_1. 
 After the above computation, each enclave hold a_i, b_i, c_i, such that ⌈ a_1+⋯ + a_P⌋_N
  =  ⌈ a ⌋_N,  ⌊ b_1 +⋯ + b_P⌉_N = ⌈ b ⌋_N, ⌈ c_1 + ⋯ + c_P⌋_N = ⌈ c ⌋_N and c = a· b  N. After the computation, each TPU enclave i seals a_i, b_i,c_i to UnS for storage individually. 
  
Online Stage:    TPU   i loads the   a_i, b_i, c_i into the enclave i. Then,  
compute X_i =  x_i - a_i and Y_i =  y_i  - b_i. Securely send X_i and Y_i to other enclave j (j = 1,⋯,P; j ≠ i).
After receiving  other X_j and Y_j, the each TPU i computes  X = ∑_i=1^PX_j and    Y = ∑_i=1^P Y_j.
After that, 
for each TPU i (i = 1,⋯, P-1), compute f_i←⌈ c_i + b_i X + a_i Y  ⌋_N. 
For  TPU P,  
 compute f_P←⌈ c_P + b_P X + a_P Y + X · Y  ⌋_N.   Here, we denote the protocol as 
   ⟨ f ⟩←( ⟨ x ⟩,⟨ y⟩ ).   
     
   

  §.§.§ Secure Monic Monomials Computation   ()

  
 The     protocol can achieve monic monomials  computation over integer shares, i.e.,  given   a share x_i (i = 1,⋯, P) and a public integer number k for  TPU i as input,     securely outputs f_i for TPU i, such that ∑_i=1^P f_i = x^k, where data shares x_i satisfy x = ∑_i=1^P x_i. The construction of the  is list as follows:
Denote k as binary form  𝔨_ℓ,⋯, 𝔨_1. Initialize the share f_i ← x_i for each TPU i.
For j = ℓ-1,⋯, 1, compute    ⟨ f^* ⟩←( ⟨ f ⟩,⟨ f ⟩ ). If 𝔨_j = 1, compute ⟨ f ⟩←( ⟨ f^* ⟩,⟨ x ⟩ ). Otherwise, let ⟨ f ⟩←⟨ f^* ⟩.  Here, the algorithm outputs ⟨ f ⟩ and  denotes the protocol as 
   ⟨ f ⟩←( ⟨ x ⟩, k ).   







   
    
    
     
      

  §.§.§ Secure Binary  Exponential Protocol (_2)

    The    _2   can achieve   exponential over binary  shares with a public base, i.e.,  given  a binary  share 𝔵_i ∈ℤ_2 (i = 1,⋯, P) and a public integer  β for  TPU i as input[β is   a small positive number which satisfies gcd(β, N) =1. ], _2   securely outputs an integer share f_i ∈ℤ_N for TPU i, such that ∑_i=1^P f_i = β^𝔵, where   𝔵 =   ⊕_i=1^P𝔵_i.
    
    
     Offline Stage:    All the TPUs  initialize  their enclaves and load the public parameters to the UnS. Then, for the 
 enclave  1,  it generates 𝔞_1∈ℤ_2,   encrypts 𝔞_1 as [[𝔞_1]], and lets it be [[𝔞]].
  After that, enclave i (i = 1,⋯,P-1) sends [[𝔞]] to enclave i+1, TPU i+1 generates 𝔞_i+1∈ℤ_2,  computes     

     [[𝔞]] ← [[𝔞]]^ (1- 𝔞_i+1)·  ([[1]] · [[𝔞]]^N-1)^𝔞_i+1 = [[𝔞⊕𝔞_i+1]],     

  
  Once    [[a]] is received, TPU computes  
   

 [[b]]= [[𝔞]]^ β·  ([[1]] · [[𝔞]]^N-1) = [[β·𝔞 +(1-𝔞)]] =  [[β^𝔞 ]]
   [[b^*]]= [[𝔞]] ·  ([[1]] · [[𝔞]]^N-1)^ β = [[   𝔞 + β(1-𝔞)]] =  [[β^1-𝔞 ]]
  

  
    
   After the computation, for  i = P,⋯, 2,  TPU   i generates   b_i, b^*_i  ∈𝔻_N
  and
  computes [[b]] = [[b]] · [[b_i]]^N-1 and [[b^*]] = [[b^*]] · [[b^*_i]]^N-1. After the computation, the TPU   2 sends   [[b]] and [[b^*]] to TPU   1, and TPU 1 uses  to get b, b^* and denote them as b_1 and b^*_1, respectively.
 After the above computation, each TPU i holds 𝔞_i, b_i, which satisfies  𝔞_1⊕⋯⊕𝔞_P  
  = 𝔞,  b_1+ ⋯ + b_P  
  = β^𝔞, b^*_1+ ⋯ + b^*_P  
  = β^1-𝔞. After the computation, each TPU   i seals 𝔞_i, b_i to UnS for storage individually. 







   
    
    Online Stage:   
     TPU   i loads the data share  𝔵_i and random shares 𝔞_i, b_i into the its enclave. Then, TPU i locally 
computes X_i =   𝔵_i ⊕𝔞_i. Securely send X_i  to other enclave j (j = 1,⋯,P; j ≠ i).
After receiving  other X_j,   each TPU i locally computes  X = ⊕_i=1^PX_i and   f_i←⌈     (b^*_i)^X· (b_i)^1-X⌋_N. We can easily verify that ∑_i=1^P f_i = β^(1-𝔞)(𝔵⊕𝔞)+ 𝔞(1-𝔵⊕𝔞)=  β^𝔵. 
   Here, we denote the protocol as 
   ⟨ f ⟩←_2( ⟨𝔵⟩, β ).   
     

    
   

  §.§.§ Secure Integer  Exponential Protocol ()

  
 
  
The        can achieve   exponential over integer  shares with a public base, i.e.,  given  an integer  share x_i ∈𝔻_N (i = 1,⋯, P) and a public integer  β for  TPU i as input ,    securely outputs shares f_i ∈𝔻_N for TPU i, such that ∑_i=1^P f_i = β^x, where data shares x_i satisfy x = ∑_i=1^P x_i and x is relative small positive number with ℓ bit-length.

i) Compute 
 (𝔵⃗_1,⋯,𝔵⃗_P) ← (x_1,⋯,x_P), 
  where 𝔵⃗_i = (𝔵_i^(ℓ) ,⋯, 𝔵_i^(1)) for TPU i = 1,⋯, P, and 𝔵^(j) =  ⊕_i=1^P𝔵_i^(j),  and x = ∑_j=1^ℓ𝔵^(j) 2^j-1.
  
ii) Execute ⟨𝔣⟩←_2 ( ⟨𝔵^(1)⟩, β). For j = 2,⋯, ℓ, compute ⟨f_j ⟩←_2 ( ⟨𝔵^(j)⟩, β), ⟨f^*_j ⟩← ( ⟨f_j⟩, 2^j-1),  and ⟨f⟩← ( ⟨f⟩, ⟨f^*_j  ⟩). The   outputs  ⟨f⟩, and we denote the protocol as 
   ⟨ f ⟩←( ⟨ x ⟩,β). 






 







   
    
     

    
        















 














 











  
     
    
 
  
  
    

  §.§.§ Secure Comparison  Protocol ()

 The  can securely compute the relationship between integer u and v, where 
  each TPU i holds shares u_i and v_i, where
u = u_1 + ⋯ + u_P, v = v_1 + ⋯ + v_P.  The construction of  is listed  as follows:

 i) Each TPU i (i =1,⋯, P) locally computes w_i = u_i - v_i.  After that,  all TPUs jointly compute  


 (𝔴⃗_1,⋯,𝔴⃗_P) ← (w_1,⋯,w_P). 
  
 
  
   ii)  As we use two’s complement binary representation, the most significant digit of u-v will reflect the relationship between the u and v. After the above computation, TPU i outputs 𝔴_i^(ℓ-1)∈𝔴⃗_i. The most significant digit 𝔴^(ℓ-1) of w = ∑_i=1^P w_i  decides the relationship of  u and v, specifically, 
   if  ⊕_i=1^P𝔴_i^(ℓ-1) = 0, it denotes  u≥ v. Otherwise, it denotes u < v.
  
  

  §.§.§ Secure Equivalent  Protocol  ()

The goal of secure equivalent  protocol  is to test whether the  two values u, v are equal or not by giving the  shares of the two values ⟨ u⟩ ,⟨ v ⟩. Mathematically, 
given  two  shares  ⟨ u⟩  and ⟨ v ⟩,   <cit.> outputs the  shares  𝔣_i for each TPU i (i=1,⋯, P) to determine whether the plaintext of the two   data are equivalent (i.e. test u?=v. If ⊕^P_i=1𝔣_i = 1, then u=v; otherwise, u ≠ v).  The   is described as follows: 

i) All the TPUs jointly calculate 

 
 












 
 



















 
 









  ⟨𝔱^*_1⟩← (⟨ u⟩ ,⟨ v ⟩); 
  ⟨𝔱^*_2⟩← (⟨ v ⟩ ,⟨ u⟩ ). 



ii) For each TPU i, it computes 𝔣_i = 𝔱^*_1,i⊕𝔱^*_2,i locally, and outputs 𝔣_i   ∈ℤ_2. 



   
   

  §.§.§ Secure   Minimum of Two Number Protocol (_2)

 
 
 The TPU i (i=1,⋯, P) stores shares  ⟨ x ⟩ and ⟨ y⟩ of two  numbers    x and     y,     The  _2 protocol outputs share ⟨ B ⟩ of   minimum       number  B, s.t.,  B = min(x,y ).  
 The   _2 is described as follows:
 
 i) All the TPUs can jointly compute
 

  ⟨𝔲⟩←( ⟨  x⟩ ,⟨ y⟩); 
  ⟨ u ⟩← (⟨𝔲⟩);
  ⟨ X ⟩← (⟨ x ⟩ ,⟨ u ⟩). 
  

   

    ⟨ Y ⟩← (⟨ y⟩ ,⟨ u⟩ ).
        

  
 
  
 



ii)    The TPU i  computes locally and outputs 
B_i = y_i - Y_i + X_i.   

 

  

  §.§.§ Secure   Minimum of H Numbers Protocol   (_H)

 
 
 
 
 The goal of _H is to get the  minimum number among H numbers. 
Given      the shares  x_1,i,  ⋯,  x_H,i for TPU i, the goal is to compute the  share  x^*_i for TPU i such that x^*   stores the minimum  integer value among  x_1,⋯,x_H, where x^* = ∑_i=1^P x^*_i, x_j = ∑_i=1^P x_i,j for j=1,⋯, H.
The _H  executes as follows: Each TPU i
puts   x_1,i ,⋯, x_H,i  into a set S_i. If L (S_i) = 1, the share remaining in L(S_i)  is  the final output. Otherwise, the protocol  is processed  according to the following  conditions.

∙ If   L(S_i)   2=0 and L(S_i)  > 1,  1) set S'_i ←∅;
2) for j = 1,⋯,    L(S_i) /2, 
compute 

    ⟨ x_j ⟩←_2( ⟨ x_2j-1⟩,  ⟨ x_2j⟩),

and add x_j,i to the set S'_i;
3) clear   set S_i and   let  S_i← S'_i.

∙ If L(S_i)   2 ≠ 0 and L(S_i)  > 1,   take out the last tuple  x_L(S_i)-1,i   from   set S_i s.t.,   L(S_i)   2=0. Run the above procedure (L(S_i)   2=0 and L(S_i)  > 1) to
 generate set S'_i.    Put x_L(S_i) -1,i    into a set S_i' and denote  S_i' ← S_i.
 
 After computation, each set S_i in TPU i only contains one element and we denote it as x^*_i. Thus, we 
 denote the algorithm as 
⟨ x^* ⟩←_H( ⟨ x_1⟩,  ⋯, ⟨ x_H⟩).
 
 


 

 

  






 
 














 
































 
 

 
  
	



  
   
      
 

 
  
  
  
 

  


  
  
  


 §.§ Security Extension of Integer Computation
  

The above the secure computation  only consider the data privacy. Two types of information can be leaked to the adversary: 1) the  access pattern  of function's input, and 2) the access pattern of RU's result retrieve. Here, we give two security extension to achieve access pattern hiding and private information retrieve, respectively. 

    

  §.§.§ Achieve Input Access pattern Hiding (APH)
  
    

 As data are directly sealed in the UnS, the adversary may analysis the access pattern of  UnS without knowing the function's input.  Suppose the system contains  H data  x^*_1,⋯,x^*_H ∈𝔻_N.  The data share x_j,i are hold by each TPU i   (j = 1,⋯,H; i = 1,⋯, P), such that x_j,1+⋯+x_j,P = x^*_j.  
  To achieve access pattern hiding, the homomorphic property of PCDD can be used. Specifically, 
    the RU uploads [[a_1]],⋯, [[a_H]] to each TPU i, s.t., for a specific  1 ≤γ≤ H, it has a_γ = 1, and other j ≠γ and  1≤ j≤ H, it holds a_j = 0. Then, the goal of the  algorithm is to securely select the shares of x_γ,j from the input shares, and constructs  as follows:
    
1) Obviously select encrypted shares. Each  TPU  initializes    an enclave.  Then, for each TPU i (i=1,⋯, P), compute


[[b_i]] ← [[a_1]]^x_1,i· [[a_2]]^x_2,i·⋯·[[a_H]]^x_H,i N^2.









  
   

  


 
 
2) Securely update share [[b_i]] for   TPU i. Without any share update, the adversary can still know the access pattern once the ciphertexts are decrypted. Thus, all the shares should be dynamically updated before the decryption.

 The TPU i picks random numbers δ_i,1,⋯,δ_i, P∈ℤ_N such that δ_i,1+⋯+δ_i, P = 0  N, and then encrypts  δ_i,j and  sends  [[δ_i,j]] to TPU  enclave j. Once all the update shares are received, TPU i computes 


[[b^*_i]] ←  [[b_i]] · [[δ_1,i]]· [[δ_2,i]]·⋯·[[δ_P,i]]   N^2.



Finally, each TPU i uses the  to get b^*_i and denotes   ⌈ b^*_i ⌋_N as the final share output.




 

  §.§.§ Achieve Private Information Retrieve (PIR)
  
 
If   the computation results is needed,  the RU will let the TPU to send the data shares back   via a secure channel. However, if one of the TPU has been compromised, even if the data cannot been known by the adversary, the retrieve access  pattern has been leaked to the adversary.  
Suppose the system contains  H data  x^*_1,⋯,x^*_H ∈𝔻_N.  The data share x_j,i are hold by each TPU i   (j = 1,⋯,H; i = 1,⋯, P), such that x_j,1+⋯+x_j,P = x^*_j.      
Thus, to achieve the private information retrieve, the RU uploads [[a_1]],⋯, [[a_H]] to each TPU, s.t., for a specific  1 ≤γ≤ H, it has a_γ = 1, and other j ≠γ, 1≤ j≤ H, it holds a_j = 0. The goal of  is to let RU privately  retrieve x_γ. Then, the algorithm computes among all TPUs as follows: 
 
  
  
  1)  For each TPU i, compute


[[b_i]] ← [[a_1]]^x_1,i· [[a_2]]^x_2,i·⋯·[[a_H]]^x_H,i N^2.









  
   

  


 
 
2) TPU 1 denotes [[b^*]] ← [[b_1]], and sends [[b^*]] to TPU 2. Then, each TPU i =2 ,⋯, P, computes  [[b^*]] ← [[b^*]] · [[b_i]]  N^2. If i =  P, then send [[b^*]]  to RU. Otherwise,   [[b^*]] is sent from TPU i to i+1.
Finally, RU  uses the  to get the  b^*, such that x_γ = ⌈ b^*_i ⌋_N is the output share.
  
   
   







      

 §.§ Secure  Floating Point Number Computation

   
   

  §.§.§ Data Format of Floating-Point Number

   
     To achieve the  real number storage and computation, we can  refer to  the IEEE 754 standard to use Floating-Point Number (FPN) for real number storage.  To support the LightCom, we change the traditional FPN and  describe the FPN  by four integers: 1) a radix (or base) β≥ 2; 2) a precision η≥ 2 (roughly speaking, η is the number of “significant digits” of the representation); 3)  two extremal exponents e_min and e_max such that   e_min < 0 < e_max. A finite FPN â in such a format is a number for which
there exists at least one representation triplet (m, e) with public parameters β,η,e_min,e_max, such that,
  
    â  =      m ·β^e-η+1.

  

  * m is an integer which -β^η + 1 ≤ m ≤β^η - 1. It is called
the integral significand of the representation of x;

  * e is an integer such that e_min≤ e ≤ e_max, called the exponent of the
representation of a.

 
As only the  significand and  exponent  contains sensitive information, we assume  all the FPNs have the same public base β = 10, and use   the fix bit-length to store the integer m. 
 Thus, 
 to achieve the secure storage, 
 the RU only needs to random share the â into â_1=(m_1,e_1),⋯, â_P= (m_P,e_P), and sends â_i to TPU i for storage, respectively.   

  For the secure FPN computation,  if  all the FPNs are transformed with the same exponential, we can directly use  secure integer computation method introduced in Section <ref>.   Thus, the key problem to achieve the secure FPN computation is  how to allow all the FPNs securely transformed with the same exponential.  Here, we first construct an algorithm called Secure Uniform Computation () and then achieve the commonly-used  FPN computations.   

    

  §.§.§ Secure Uniform Computation ()

    
  
     Assume each TPU i (i=1,⋯, P)  stores   into â_j,i=(m_j,i,e_j,i) , the goal of  is to output â^*_j,1=(m^*_j,1,e^*_j,1) for j = 1,⋯,H,
and  the construction of  can be described as follows: 
   
i) All the TPUs jointly  compute     
    ⟨ e^* ⟩←_H( ⟨ e_1⟩,  ⋯, ⟨ e_H⟩).

    
 ii)  Each TPUs locally computes ⟨ c_j⟩=   ⟨ e_j⟩ - ⟨ e^*_i⟩. As e_j- e^* is a relative small number,  TPUs jointly executes 
⟨ 10^  e_j - e^*  ⟩←( ⟨ c_j⟩, 10) and   
   ⟨  m^*_j ⟩← (⟨ 10^  e_j - e^*⟩,⟨ m_j ⟩).  
  
  After computation, all the ⟨ a_1⟩,⋯, ⟨ a_H⟩ will transform to ⟨ a^*_1⟩,⋯, ⟨ a^*_H⟩ which shares the same e^*, where ⟨â_j⟩ = (⟨ m^*_j ⟩, ⟨ e^* ⟩).
 



 

  §.§.§ Computation Transformation

 
  The secure floating-point number computation  can be transformed into the secure integer computation protocols with the usage of . Formally, given FPN shares   ⟨â_j⟩ =(⟨ m_j⟩, ⟨ e_j⟩), (for j = 1,⋯,H), we can first compute 
  

  (⟨â^*_1⟩,⋯, ⟨â^*_H ⟩) ←(⟨â_1⟩,⋯, ⟨â_H ⟩),
   

   where ⟨â^*_j⟩ = (⟨m^*_j⟩,⟨ê^*⟩). 
 Then, 
   

  ( ⟨ y^*_1 ⟩,⋯, ⟨ y^*_ζ⟩) ←SIF( ⟨ m^*_1 ⟩,⋯, ⟨ m^*_ξ⟩),
   

   where SIF denote secure integer computation protocol designed in Section <ref>,  and ⟨ y^*_1 ⟩,⋯, ⟨ y^*_ζ⟩  can be either integer shares or binary shares according to the function type. 
   If the SIF is the  and , then the SIF output the binary share ⟨ y^* ⟩ as the final output, and we denote these two algorithms as secure FPN comparison  () and secure FPN  equivalent  test protocol ().    If the SIF is the ,   , _2 and  _H, then the SIF outputs the integer  share ⟨y^*_1 ⟩, and denotes
   ⟨ŷ^* ⟩ = (⟨y^*_1 ⟩, ⟨ e^*⟩) as the secure FPN's output, and we denote above four algorithms as secure FPN multiplication   (), secure FPN monic monomials computation (), secure minimum of two FPNs protocol   (_2), and secure minimum of H FPNs protocol   (_H), respectively. 
   Specifically, for the multiple  FPN addition (), given FPN shares   ⟨â_j⟩ =(⟨ m_j⟩, ⟨ e_j⟩), (for j = 1,⋯,H), we can first compute  ⟨â^*_1⟩ ,⋯, ⟨â^*_H⟩ with the , 
   where ⟨â^*_j⟩ = (⟨m^*_j⟩,⟨e^*⟩). Then, compute ⟨y^*⟩←∑_j=1^H⟨m^*_j⟩ and denote the final FPN addition  result as ⟨ŷ⟩  =  (⟨y^*⟩, ⟨e^*⟩).
   
   

 
  
  

 
 


 
 
 
  

 



 
 
 


 






 
 
   
 
 
   
 
 
  
    

    
 
  
  
 
   
   
     
     
 
  
     
   
   





    
     

     
   
     
  


   
   
   
   
    
      


 



  
          
         
       
       
    
           

     
    
     
     
    
 
      
         
         
            
  
   
  
   
     
 
   

  














 
 

 
 
 
 


 

 

 
 

 
 
 
 
   
 





 
 
  
   
 
  
 
 




 
 




  §.§.§ Secure Extension  for FPN Computation
  
Similar to the secure integer computation, we have the three following extension for LightCom.


    Access Pattern Hiding: 
 As all the secure FPN  computation can be transformed in to secure integer computation with the  help of the , we can also use  the same  method   in section   <ref> to achieve  input access pattern hiding  for the secure FPN  computation.
 


 Achieve Private FPN Retrieve:  
In out LightCom, one floating point number can be securely stored as two    integer numbers.  Thus, we can use the method in section <ref> to  privately retrieve integer for twice to   achieve the private  FPN retrieve. 
  
  
  
     

 §.§ Functional Extension for LightCom
  
   

  §.§.§ Non-numerical Data Storage and Processing
  
   

   
   
   For the non-numerical data storage,   the   traditional character encodings with Unicode <cit.>   and its standard Unicode Transformation Format (UTF) schemes can be used  which maps a character into an integer.    
   Specifically, for secure storage,   use UTF-8 to map the character into 32-bit number x, randomly splits x into x_1,⋯,x_P, such that x_1 +⋯+x_P = x, and sends   a_i to TPU i for processing.   In this case, all the non-numerical data processing can be transformed into secure integer computation which can be found in section <ref>. For the secure storage, each TPU i securely seals the share a_i into the UnS with the algorithm  in Section <ref>.
   Once the data shares are needed for processing, TPUs needs to use  algorithm to recover the message from UnS.
   
     

  §.§.§ Extension of Multiple User Computation
  
     
All the secure  computations in the previous section are designed for the single user setting, i.e., all the data are encrypted under a same RU's public key.   If all RUs  want to jointly achieve a secure computation, each RU j (j=1,⋯,  ψ)  executes   to generate  public key pk_j and  private key is sk_j locally. Then, RU j uses  to split key sk_j into P shares ⟨ sk_j ⟩, and sends these shares to TPUs in the cloud.  Assume RU j's ciphertext [[x_j]]_pk_j is securely stored in UnS, TPUs  can  get data shares ⟨ x_j ⟩  with  and achieve the corresponding secure computations  in Section <ref> with these shares.

     
   
    

§ SECURITY ANALYSIS 

  
  In this section, we first analyze the security of the basic crypto primitives and the sub-protocols, before demonstrating the security of our LightCom framework.
  
  
  

 §.§ Analysis of  Basic Crypto Primitives


 
   

  §.§.§ The Security of   Secret Sharing Scheme

   Here, we give the following theorem to show the  security of the additive secret sharing scheme.
   
   
  A additive secret sharing scheme achieves an information theoretic secure when the  P participants can reconstruct the secret x ∈𝔾, while any smaller set cannot discover anything information about the secret.
     
     
     The   shares  X_1,⋯,X_P are selected with random uniform distribution  among P participants such that X_1+⋯+X_P = m ∈𝔾.  Even the attacker A holds P-1 shares, (s)he can only compute x' = ∑_i=1^P-1 X'_i, where X'_i is selected from  X_1,⋯, X_P. The element x is still protected due to the x = x' + X'_P. Since random value X'_P is unknown for A, it   leaks no information about the value x. 
       
       
          
   
  A proactive additive  secret
sharing  scheme achieves an information theoretic secure if satisfies the following properties:
I. Robustness: The new updated shares are corresponding  to the secret  x (i.e., all the new shares can reconstructed the secret  x). 
II. Secrecy: The adversary at any time period knows no more than P shares (possible a different shares in each time period) learns nothing about the secret.  
 
     
     
The data    shares  X^(t)_i in time period t are stored in party i, s.t.,   ∑_i=1^PX^(t)_1=x.
Each party i generates shares δ^(t)_i,1,⋯, δ^(t)_i,P which satisfies  δ^(t)_i,1+⋯+δ^(t)_i,P = 0  N. Thus, the new shares denote X^(t+1)_i = X^(t)_i + δ^(t)_1,i + ⋯ + δ^(t)_P,i, and satisfy ∑_i=1^P X_i^(t+1) = ∑_i=1^P X_i^(t+1) + ∑_i=1^P∑_i=1^Pδ^(t)_i,j = x which   the robustness property hold.

To guarantee the  secrecy property, the data shares in time period t  can achieve the  information theoretic secure according to the theorem    <ref>.  Even adversary can get P -1 shares in each time period t (t ≤ t^*), the adversary can compute x^(t) = x - X^(t)_P_t = ∑_i=1, i ≠P_t^P X_i^(t), where X^(t)_P_t is the non-compromised share  in  time period t. The adversary A^* still cannot get any information from x^(1),⋯,x^(t_*) as δ^(1)_P_1,P_1,⋯,δ^(t_*)_P_t_*,P_t_* are independently  and randomly generated and cannot be compromised by the adversary. Thus, the  secrecy property holds.
       
       
       
  

  §.§.§ The Security of PCDD



 

 
 
 The security of our PCDD is given by the following theorem.
  
  
  The  PCDD scheme described in Section <ref> is semantically secure, based on the assumed intractability of the DDH assumption over ℤ_N^2^*. 
  
The   security of   PCDD   has been proven to be  semantically  secure under the  DDH assumption over ℤ_N^2^* in the standard model  <cit.>.  
  
 
   

 §.§ Security of  TPU-based Basic Operation



The  can securely  generate random shares against adversary who can compromise at most P-1 TPUs, assuming the semantic security of the
PCDD cryptosystem.


For each TPU i  (0 ≤ i<P), only the PCDD encryption [[𝔯^(1)]],⋯,[[𝔯^(ℓ)]] are sent to TPU i+1.  After that, PCDD encryption  [[r]] is sent from TPU  i+1 to i. 
 According to   semantically secure of the PCDD  (theorem
  <ref>), the TPU i+1 cannot get any information  from the ciphertext sent from TPU i.
 Even the adversary can compromise at most P-1 TPUs and get the shares 𝔯_i^(1),⋯, 𝔯_i^(ℓ), r_i, (s)he cannot get the secret 𝔯^(1),⋯, 𝔯^(ℓ), r due to 𝔯^(1)_P,⋯, 𝔯^(ℓ)_P, r_P are unknown to adversary according to the security of Theorem <ref>.


  The security proof of the secure share domain transformation in section, secure binary shares operation in section, secure integer computation, and secure FPN computation are similar to the proof of theorem <ref>. The security of above operations are based on the semantic security of the
PCDD cryptosystem. Next, we will show that  and  can achieve its corresponding functionality. 
  
  

The  can securely achieve the access pattern hidden for the function input  under the semantic security of the
PCDD cryptosystem.


 In the select share phase,  all  a_1,⋯, a_H are selected and encrypted  by RU, and are sent to TPUs for processing.
 It is impossible for the adversary to know the plaintext of the ciphertext due to the semantic security of  
PCDD. Also, the shares are dynamically update by computing  
b^*_i ←  b_i + δ_1,i + δ_2,i+ ⋯ +δ_P,i N. As δ_j,i is randomly generated by TPU i and is sent from TPU j to TPU i, it is hard for the adversary to recover b_i even adversary compromise the other P-1 TPUs due to the secrecy of Theorem <ref>. Thus,  it is still impossible for the adversary to trace the original shares with the update shares which can achieve the  access pattern hidden.


  

The  can securely achieve the private information retrieve  under the semantic security of the
PCDD cryptosystem.


 In  , all  a_1,⋯, a_H are selected and encrypted  by RU, and sent to TPUs for processing.  After that, [[b^*]]
 is transmitted among TPUs. As all the computations in the    are executed in the ciphertext domain,
 it is impossible for the adversary to know the plaintext of the ciphertext due to the semantic security of  
PCDD, which can achieve the   private information retrieve.

  
  

 §.§ Security of LightCom

 
The LightCom is  secure against side-channel  attack   if t_c+t_p+t_d< P· t_a, where t_c, t_p  and t_d  are the runtime of secure computation , private key update, and data share update, respectively; t_a is the   runtime for attacker successfully compromising the  TPU enclave; P is the number of TPUs in the system. 


In the data upload phase, 
RU's data are randomly separated and uploaded to TPUs via secure channel. According to theorem <ref>, no useful information about the RU's data are leaked to the adversary with compromising  P-1   TPUs encalves.
For the  long-term storage, the data shares are securely sealed  in the UnS with PCDD crypto-system. With the theorem <ref>,  we can find the encrypted data shares are semantically secure stored in the UnS.


In the secure online computing phase, all the ciphertext are securely  load to the TPUs with . Then, all the TPUs   jointly achieves the secure computation with the  . During the computing phase, the system attacker can launch the following three types of attacks: 1)  compromise the TPU enclave: adversary can compromise a TPU enclave to get current data shares and private key shares
with the time t_a; 2) stores the old private key shares: the adversary  tries to  recover the RU's private key with current   and  old private key shares.
3) stores the old data shares and try to  recover the RU's original data: the adversary  tries to  recover the RU's data  with current   and  old data shares.  To prevent first type of attack, RU's data are separated  and  distributed among P TPUs. Unless adversary can compromise all the TPU enclaves at the same time, A can get nothing useful information from compromised shares according to theorem <ref>.  Thanks to the secrecy property of proactive additive secret sharing scheme in Theorem <ref>, it is impossible for the adversary to recover the private key and RU's data by getting P-1 TPUs   at each time period. As the TPU enclaves are dynamically     release after the computation, the attacker needs to restart to compromise the TPU enclaves after the enclaves are built for secure computation.

Thus, the adversary fails to attack our LightCom system   if the data shares are successfully seals in the UnS and  all the TPU enclaves are released before the adversary compromises all the   enclaves in the secure computation phase.  In this case, the LightCom is secure  against adversary side-channel attack   if t_c+t_p+t_d< P· t_a.


  

   



  


 

    
  
  




  
  

  
  
  
  
  



  
  
  


§ EVALUATIONS

In this section, we evaluate the performance of   LightCom. 



 §.§ Experiment Analysis

For evaluating the performance of the LightCom, we build  the framework with C code under the Intel^ Software Guard Extensions (SGX) environment as a special case of TPU, and the experiments are performed on a personal computer (PC) with 3.6 GHz single-core processor and 1 GB  RAM memory (single-thread program are used) on virtual machine with Linux operation system. 
  To test the efficiency of our LightCom, there are two types of metrics are considered, called runtime  and security level (associate with PCDD parameter N). The runtime refers to the secure  outsourced computation   executing duration on  server or user's side   in our testbed.  The security level is an indication of the security strength of a cryptographic primitive. Moreover, we use SHA-256 as the hash function H(·)
in LightCom. As the communication latency among CPUs is very low (use Intel^   UltraPath Interconnect (UPI) with 10.4 GT/s transfer speed and theoretical bandwidth is 20.8 GB/s)[https://www.microway.com/knowledge-center-articles/performance-characteristics-of-common-transports-buses/], we do not consider the communication overhead as a performance metric   in our LightCom.  






  §.§.§ Basic Crypto and System Primitive


   
       


We first evaluate   the  performance of  our basic operation of cryptographic primitive (PCDD cryptosystem) and basic system operations (,  and  protocol).  We first let N be 1024 bits to achieve 80-bit security <cit.> to test the basic crypto primitive and basic protocol. For PCDD,   it takes 1.153 ms to encrypt a message (), 1.171 ms for ,  1.309 ms to run , 5.209 μs to run .   For the basic system operations,   it takes 1.317 ms for , 1.523 ms for , and 1.512 ms for  (P=3).  Moreover,     ,  and   are affected by the PCDD parameter  N and  the number of TPUs P (See Fig. <ref> and Fig. <ref> respectively).
From the Figs. <ref> and   <ref>, we can that the parameter  N will affect greatly on the runtime and communication overhead of the protocols.












  §.§.§ Performance of TPU-based  Integer Computation


Generally, 
there are four factors that affect the performance of TPU-based  integer computation: 1) the number of TPUs P; 2) the PCDD  parameter N;  3) the bit-length  of the integer ℓ;  4) the number of encrypted data   H.  In Fig. <ref>-<ref>, we can see that   the runtime    of all the protocols  increase  with P.  It is because  more runtime are needed and more data in online phase and random numbers in offline phase are required to process with extra parties.
Also, 
we can see that   the runtime   of all the TPU-based integer computations  increase   with the bit-length of   N 
from Table <ref>. It is because the running time of the basic operations ( and  algorithms of PCDD)   increases  when N increases. Moreover, in Fig. <ref>-<ref>,  the  performance of , , , , ,    ,  ,  _2, _H,      are associated with ℓ. The computational  cost of above protocols are increased  with  ℓ, as more computation resources are needed to process when ℓ increase. Finally, we can  see that performance of   and   are increased with  H  in Fig.  <ref>. It is because more numbers of PCDD ciphertexts cost more energy with the homomorphic and 
module exponential operations.  

 



  





  §.§.§ Performance of TPU-based  FPN Computation

For the basic TPU-based FPN computation, 
there are four factors that affects    performance of LightCom: 
 1) the number of TPUs; 2) the PCDD  parameter N;  3) the bit-length  of the integer ℓ; 4) the number of encrypted data H.    The runtime trends of  FPN computation protocols  (e.g.  ,  , ,  ,  _2, _H)   are similar to the trends of corresponding  secure integer computation (e.g.  ,  , ,  ,  _2, _H), as the runtime of  FPN computation is equal to the runtime of corresponding  secure integer computation add the runtime of .
 
 

 
 
 




    

 §.§ Theoretical  Analysis

  
 
  
  Let  us  assume  that  one  regular  exponentiation  operation  with  an  exponent  of N requires 1.5 N multiplications <cit.>.  For PCDD, it takes 3N multiplications for , 1.5N multiplications for , 1.5N multiplications for , P multiplications for , 1.5N multiplications for . For the basic operation of LightCom, it takes 1.5 PN multiplications to run , 3N+t_hash multiplications for , 1.5PN+t_hash multiplications for , O ((ℓ+P)N) multiplications for ,  O (PN) multiplications for , . For the integer and binary  protocol in LightCom, it takes O (PN) multiplications for  offline phase of  and , O (ℓPN) multiplications for  offline phase of , , , , _2,  O (ℓPN) multiplications for both offline and online phase of ,   O (H PN) multiplications for   offline     phase of  and ,  O (⌈log_2H ⌉·ℓPN) multiplications for   offline     phase of _H. 
  For the FPN computation in LightCom, it takes O (H ℓPN) multiplications for  offline phase  and ,  O (ℓPN) multiplications for offline phase ,  , ,  ,  _2,   and O (⌈log_2H ⌉·ℓPN) multiplications for   offline     phase of _H.       All the above protocols only need   O(1) multiplications in online phase, which is greatly fit for fast processing. 
  
  
  
 


 
  
  
 












 
 


 



  
  
  
   
  
  
  
  
  
 




  
  
  
  
  
 
  
   
 







§ RELATED WORK


Homomorphic Encryption. Homomorphic encryption, allow third-party to do the computation on the ciphertext which reflected on the plaintext, is considered as the best solution to achieve the secure outsourced computation. The first construction of fully homomorphic encryption was proposed by Gentry in 2009 under the ideal lattices, which permits evaluation
of arbitrary circuits over the plaintext <cit.>. Later, some of the new hard problems (such as Learning With Errors (LWE) <cit.>,  Ring-LWE  <cit.>) are used to construct the FHE which can greatly reduce the storage overhead and increase the performance of the homomorphic operations <cit.>. 
However, the current FHE solutions and libraries  are still not practical enough for the real real-world scenarios <cit.>. 
Somewhat homomorphic encryption <cit.> can allow semi-honest  third-party to achieve the  arbitrary circuits with limited depth. The limited times of homomorphic operations are  restrict the   usage scope   of the    application.  Semi-homomorphic encryption (SHE) can only support additive <cit.> (or multiplicative <cit.>)  homomorphic operation. However, with the help of the extra semi-honest computation-aid server,  a new computation framework can be constructed to achieve commonly-used secure  rational number computation <cit.>, secure multiple keys computation <cit.>, and floating-point number computation <cit.>. The new framework can greatly balance the security and efficiency concerns, however, the extra server will still complex the system which brings more risk of information leakage. 



Secret Sharing-based Computation. The user's data in secret sharing-based (SS-based)  computation
 are separated into multiple shares with the secret sharing technique, and each shares are located in one server to guarantee the security.    Multiple parties can jointly together to securely achieve a computation without leaking the original data to the adversary.  
  Different from the heavyweight  homomorphic operation, the SS-based computation <cit.> can achieve the lightweight computation. Despite the theoretical construction, many real-word computation are constructed for practical usage, such as SS-based  set intersection <cit.> and    top-k computation <cit.>.  These basic computations can be used to  solve data security problem in data mining technique, such as deep learning <cit.>. 
  Emekçi  et al. <cit.> proposed a secure ID3 algorithm to construct a decision tree in a privacy-preserving manner. 
  Ma et al. <cit.> constructed a lightweight privacy-preserving    adaptive boosting (AdaBoost) for the face recognition. The new secure natural exponential and secure natural logarithm which can securely achieve the corresponding computation computation to balance accuracy and efficiency. Although many of the privacy-preserving  data mining techniques with secret sharing  are constructed <cit.>,  the SS-based computation still need to build secure channel among these parties. Moreover, the   high communication rounds among the computation parties   still   become an obstacle for a large-scale application.
  
Intel^ Software Guard Extensions.
Intel^ SGX is a kind of TEE which provides strong hardware-enforced confidentiality and integrity guarantees and protects  an application form the host OS, hypervisor, BIOS, and other software. 
Although an increasingly number of  real-world industry applications are securely executed in the untrusted remote platforms equipped with SGX, the SGX  still faces side-channel attack to expose the information during the computation.
Götzfried et al. <cit.> proposed a new attack called  root-level cache-timing attacks which can   obtain secret information
from an Intel^ SGX enclave. Lee et al. <cit.> gave a new side-channel attack cannled branch shadowing which reveals fine-grained control flows  in a SGX enclave.
Bulck  et al. <cit.>
constructed  two novel attack vectors that infer enclaved memory accesses. Chen  et al. <cit.> presented  a new attack call SGXPECTRE   that can learn secrets
inside the enclave memory or its internal registers.  Currently, three types of  solutions are used to protect the side-channel attack: hardware method <cit.>, system method <cit.>, and application method <cit.>. 
These   methods can only  guarantee some dimension of  protection, and cannot be used for all-directional protection even against the unknown side-channel attack. 

   
  


§ CONCLUSION


In this paper, we   proposed LightCom, a framework for practical   privacy-preserving      outsourced  computation framework, which allowed a user to outsource encrypted data to a single cloud service provider for securely data storage  and   process.  We designed two types of   outsourced computation toolkits  which can securely guarantee the achieve secure integer computation and floating-point computation against side-channel attack. 
  The utility and performance  of our LightCom framework  was then demonstrated using simulations. Compared with the existing  secure outsourced computation framework, our LightCom takes 
  fast, scalable, and  secure outsourced  data processing  into account.

As a future research effort, we plan to apply our   LightCom in a specific applications, such as e-health cloud system. It allows us to refine the framework to handle more complex real-world computations.

 

 

§ ACKNOWLEDGMENT


 The work   is supported by the National Natural Science Foundation of China (Grant No.61702105, No.61872091).
  
  

 
  
 
  

  
    
      
       
     
   
      

    
      
  
 



      
      
 
    
 
  
   
 


 
  

 
 
  
  
  
  
  
   
  
  
  
  
   
 




  
 
 
  
  
  
  
  


  


  


   


 
 
 


   
  

 
  
  
      
 

  







  

 


  
  
 

  
  

  


 
  


 
 

  
 
  
  
  







 

 
           


 







































































IEEEtran






[
    < g r a p h i c s >
]Ximeng Liu(S'13-M'16)
received the B.Sc. degree in electronic engineering from Xidian University, Xi’an, China, in 2010 and the Ph.D. degree in Cryptography from Xidian University, China, in 2015. Now he is the full professor in the College of Mathematics and Computer Science, Fuzhou University. Also, he is a research fellow at the School of Information System, Singapore Management University, Singapore. He has published more than 100 papers on the topics of cloud security and big
data security—including papers in IEEE Transactions on Computers, IEEE Transactions on Industrial Informatics, IEEE Transactions on Dependable and Secure Computing, IEEE Transactions on Service Computing, IEEE Internet of Things Journal, and so on.  He awards “Minjiang Scholars” Distinguished Professor, “Qishan Scholars” in Fuzhou University, and ACM SIGSAC China Rising Star Award (2018). His research interests include cloud security, applied cryptography and big data security. He is a member of the IEEE, ACM, CCF.




  [
    < g r a p h i c s >
]Robert H. Deng (F'16)
 is AXA Chair Professor of Cybersecurity and Professor of Information Systems in
the School of Information Systems, Singapore
Management University since 2004. Prior to this,
he was a principal scientist and a manager of
Infocomm Security Department, Institute for
Infocomm Research, Singapore.
His research
interests include data security and privacy,
multimedia security, network and system security.
He served/is serving on the editorial boards of many international journals, including the IEEE
Transactions on Information Forensics and
Security, and
IEEE Transactions on Dependable and Secure Computing.  



  [
    < g r a p h i c s >
]Pengfei Wu 
 received the B.Sc. degree in software engineering from Shandong University, Jinan, China, in 2016. He is currently pursuing the Ph.D. degree of Software Engineering in Peking University, Beijing, China. His research interests include cloud security and big data security.



  [
    < g r a p h i c s >
]
Yang Yang (M'17) received the B.Sc. degree from Xidian University, Xi'an,
China, in 2006 and Ph.D. degrees from Xidian University, China, in
2012. She is a research fellow (postdoctor) under supervisor Robert
H. Deng in School of Information System, Singapore Management
University. She is also an associate professor in the college of
mathematics and computer science, Fuzhou University. Her research
interests are in the area of information security and privacy
protection.
    

 
 




























  
   

§ SUPPLEMENTARY MATERIALS

    

 §.§ A. Deterministic Turing Machines

    
    Turing machines are a model of computation which anything   can
be computed that can be computed by a Turing Machine.  As all the function in our PVOA framework can be computed by Deterministic Turing Machine. 
The   rigorous definition is 
defined as follows
    
        
        
        A Deterministic Turing Machine contains  a tuple (Q, Σ, δ, s, h) where
1) Q is a finite set of states which contains the states s, q_acc, q_rej.
2) Σ is a finite alphabet which contains the symbol #.
 3) Transition function δ: Q -{q_acc, q_rej}×Σ→ Q  ×Σ∪{R, L}, where L is left shift, R is right shift.
4) s∈ Q is the start state, q_acc is the accept state, q_rej is the reject state.
  
    
    
  Suppose  M is a deterministic Turing machine that halts on all inputs. Time complexity function T_M: ℕ→ℕ is defined as
  
    T_M (n) = max{m | ∃ w ∈Σ^*
    ,|w| = n  
    such that the computation
    of M  on  w  takes m   moves},

    where numbers are coded in binary format. 
   We call  a Turing machine is polynomial if there exists a polynomial p(n), such that  T_M (n) ≤ p(n), for all n ∈ℕ.
    
    
   

 §.§ B. Hard Problem
 

(DDH assumption over ℤ_N^2^* <cit.>).
For every probabilistic
polynomial time algorithm A, there exists a negligible function negl(·) such that for
sufficiently large l.



    [
    [ A(N,X,Y,;  Z_b  N);       =b;  ]:[          pp← Sys(l/2);            N=pq, g ←𝔾; x,y,z ← [1, ord( 𝔾 )];            X=g^x  N^2;            Y=g^y  N^2;          Z_0=g^z  N^2;          Z_1=g^xy N^2;              b ←{0,1};                       ]] -1/2= negl(l).


Let N be a composite modulus product of two large primes.
Let 𝔾
be the cyclic group of quadratic residues modulo N^2. The  decisional Diffie-Hellman problem over ℤ_N^2^*  (in 𝔾)
cannot be harder than factoring.


The detailed proof can be found in <cit.>.







 §.§ C. Paillier Cryptosystem Distributed Decryption   (PCDD) 

 


In order to realize  LightCom, our previous Paillier Cryptosystem Distributed Decryption  (PCDD) <cit.> cryptosystem is  used and works as follows:

KeyGen:   Given a security parameter k and two large prime numbers p,q, where L(p)=L(q)=k, we have two strong primes p',q', s.t.,  p' = p-1/2 and  q' = q-1/2 (due to the property of the strong primes). We then compute N=pq  and λ=lcm(p-1, q-1), define a function L(x)=x-1/N, and choose a generator g of order (p-1)(q-1)/2.  The public key  is  pk=(N,g), and the corresponding   private key is sk= λ.  

 
Encryption (Enc): Input a message m ∈ℤ_N, the   chooses a random number r ∈ℤ^*_N^2, and output ciphertext  as [[m]] = g^m r^N  N^2.

Decryption (Dec): Input a ciphertext [[m]] ∈ℤ_N^2 and the private key sk, the   compute 
[[m]]^λ = (1+mNλ)  N^2. Since gcd(m, λ) =1, the plaintext m can be recovered as 
m = L([[m]]^λ) ·λ^-1 N^2.



Private Key Splitting (KeyS): Input  the private key λ, the  separates λ into n shares as λ^*_i  such that λ^*_1+⋯+λ^*_n ≡ 0 λ and λ^*_1+⋯+λ^*_n ≡ 1   N.


Partially decryption (PDec):  Once [[m]] is received, with partially private key λ_i^*, the partially decrypted ciphertext CT_i can be calculated as: 
  CT_i  = [[m]]^λ_i^* N^2.

Threshold decryption  (TDec):  
Once  n decrypted ciphertexts CT_1, ⋯ ,CT_n  are received, the   TDec algorithm  can   calculates
  T = ∏_i=1^n (CT_i)  N^2, and 
m = L(T  N^2).




   



 
 
 
 Given [[x_1]],⋯, [[x_n]] and a_1,⋯,a_n, we   show that our PCDD have the polynomial  homomorphism property (): 
 

 [[a_1 · x_1 + a_2 · x_2 + ⋯ a_n x_n ]]  ← [[x_1]]^a_1· [[x_2]]^a_2⋯ [[x_n]]^a_n
  


Homomorphic Properties of DT-PKC: Here,  we give three homomorphic properties of DT-PKC as follows:

1)  Additive homomorphism:  Given ciphertexts [[m_1]] and [[m_2]] under a same public key pk, the additive homomorphism can be achieved by ciphertext multiplication, i.e., compute
[[m_1]]_pk· [[m_2]]_pk = {(1+ (m_1+m_2) · N)· h^ r_1+r_2 N^2, g^r_1+r_2 N^2}
= [[m_1+m_2]]_pk.  


2) Scalar-multiplicative Homomorphism: Given ciphertexts [[m]]_pk  and a constant number c ∈ℤ_N, it has 
([[m]]_pk)^c  ={(1+m · N)^c · h^c r_1 N^2, g^cr_1  N^2}
= [[cm]]_pk. Specifically, let c = N+1 and we have
([[m]]_pk)^N-1  ={(1+(mN^2- m N)· h^(N-1)r_1 N^2, g^(N-1)r_1  N^2}
= [[-m]]_pk.

Without any ambiguity, all the ciphertexts below are encrypted under the same public key pk, and we use the notion [[x]] instead of [[x]]_pk.


    
     




