Cloud-based MPC with Encrypted Data
Andreea B. Alexandru Manfred Morari George J. Pappas


The effects of kinetic instabilities on the electron cyclotron emission from runaway electrons
    Max E. Austin
    December 30, 2023
==============================================================================================

plain
plain




This paper explores the privacy of cloud outsourced Model Predictive Control (MPC) for a linear system with input constraints. In our cloud-based architecture, a client sends her private states to the cloud who performs the MPC computation and returns the control inputs. In order to guarantee that the cloud can perform this computation without obtaining anything about the client's private data, we employ a partially homomorphic cryptosystem. We propose protocols for two cloud-MPC architectures motivated by the current developments in the Internet of Things: a  architecture and a  architecture. In the first case, a control input for the system is privately computed by the cloud server, with the assistance of the client. In the second case, the control input is privately computed by two independent, non-colluding servers, with no additional requirements from the client. We prove that the proposed protocols preserve the privacy of the client's data and of the resulting control input. Furthermore, we compute bounds on the errors introduced by encryption. We present numerical simulations for the two architectures and discuss the trade-off between communication, MPC performance and privacy.






§ INTRODUCTION


The increase in the number of connected devices, as well as their reduction in size and resources, determined a growth in the utilization of cloud-based services, in which a centralized powerful server offers on demand storage, processing and delivery capabilities to users. 

With the development of communication efficient algorithms, outsourcing computations to the cloud becomes very convenient. 

However, issues regarding the privacy of the shared data arise, as the users have no control over the actions of the cloud, which can leak or abuse the data it receives. 

Model Predictive Control (MPC) is a powerful scheme that is successfully deployed in practice <cit.> for systems of varying dimension and architecture, including cloud platforms. 

In competitive scenarios, such as energy generation in the power grid, domestic scenarios, such as heating control in smart houses, or time-sensitive scenarios, such as traffic control, the control scheme should come with privacy guarantees to protect from eavesdroppers or from an untrustworthy cloud. 

For instance, in smart houses,  setups can be envisioned, where a local trusted computer aggregates the measurements from the sensors, but does not store their model and specifications and depends on a server to compute the control input or reference. The server can also posses other information, such as the weather. 

In a heating application, the parameters of the system can be known by the server, i.e., the energy consumption model of the house, but the data measurements and how much the owner wants to consume should be private. 

In traffic control, the drivers are expected to share their locations, which should remain private, but are not expected to contribute to the computation. Hence, the locations are collected and processed only at a single server's level, e.g., in a  setup, which then sends the result back to the cars or to traffic lights. 

Although much effort has been dedicated in this direction, a universally secure scheme that is able to perform locally, at the cloud level, any given functionality on the users' data has not been developed yet <cit.>. 

For a single user and functionalities that can be described by boolean functions, fully homomorphic encryption (FHE) <cit.> guarantees privacy, but at high storage and complexity requirements <cit.>. 

For multiple users, the concept of functional privacy is required, which can be attained by functional encryption <cit.>, which was developed only for limited functionalities. 

More tractable solutions that involve multiple interactions between the participating parties to ensure the confidentiality of the users' data have been proposed. 

In  computations, where the users have a trusted machine, called the client, that performs computations of smaller intensity than the server, 
we mention partially homomorphic encryption (PHE) <cit.> and differential privacy (DP) <cit.>. 

In  computations, in which the users share their data to two  servers, the following solutions are available: secret sharing <cit.>, garbled circuits <cit.>, Goldreich-Micali-Wigderson protocol <cit.>, PHE <cit.>. 




 §.§ Contributions
 

In this paper, we discuss the implicit MPC computation for a linear system with input constraints, where we privately compute a control input, while maintaining the privacy of the state, using a cryptosystem that is partially homomorphic, i.e., supports additions of encrypted data. 

In the first case we consider, the control input is privately computed by a server, with the help of the client. In the second case, the computation is performed by two  servers. 

The convergence of the state trajectory to the reference is public knowledge, so it is crucial to not reveal anything else about the state and other sensitive quantitities. 

Therefore, we use a privacy model that stipulates that no computationally efficient algorithm run by the cloud can infer anything about the private data, or, in other words, an adversary doesn't know more about the private data than a random guess. 

Although this model is very strict, it thoroughly characterizes the loss of information.

This work explores fundamental issues of privacy in control: the trade-off between computation, communication, performance and privacy. We present two main contributions: proposing two privacy-preserving protocols for MPC and evaluating the errors induced by the encryption. 



 §.§ Related work


In control systems, ensuring the privacy of the measurements and control inputs from eavesdroppers and from the controller has been so far tackled with differential privacy, homomorphic encryption and transformation methods. 

Kalman filtering with DP was addressed in <cit.>, current trajectory hiding in <cit.>, linear distributed control <cit.>, and distributed MPC in <cit.>. 

The idea of encrypted controllers was introduced in <cit.> and <cit.>, using PHE, and in <cit.> using FHE. Kalman filtering with PHE was further explored in <cit.>. 

Optimization problems with DP are addressed in <cit.> and PHE in <cit.>. 

Many works proposed privacy through transformation methods that use multiplicative masking. While the computational efficiency of such methods is desirable, their privacy cannot be rigorously quantified, as required by our privacy model, since the distribution of the masked values is not uniform <cit.>.

Recent work in <cit.> has tackled the problem of privately computing the input for a constrained linear system using explicit MPC, in a  setup. 

There, the client performs the computationally intensive trajectory localization and sends the result to the server, which then evaluates the corresponding affine control law on the encrypted state using PHE. 

Although explicit MPC has the advantage of computing the parametric control laws offline, the evaluation of the search tree at the cloud's level is intractable when the number of nodes is large, since all nodes have to be evaluated in order to not reveal the polyhedra the in which the state lies, and comparison cannot be performed locally on encrypted data. 

Furthermore, the binary search in explicit MPC is intensive and requires the client to store all the characterization of the polyhedra, which we would like to avoid. Taking this into consideration, we focus on implicit MPC.

The performance degradation of a linear controller due to encryption is analyzed in <cit.>. In our work, we investigate performance degradation for the nonlinear control obtained from MPC. 





§ PROBLEM SETUP


We consider a discrete-time linear time-invariant system:


    x(t+1) = Ax(t) + Bu(t),


with the state x∈ X⊆ℝ^n and the control input u∈ U⊆ℝ^m. The optimal control receding horizon problem with constraints on the states and inputs can be written as:



    J_N^∗(x(t)) =   min_u_0,…,N-11/2(x_N^⊺ P x_N + ∑_k=0^N-1 x_k^⊺ Q x_k + u_k^⊺ R u_k )
    
    	s.t.     x_k+1 = Ax_k + Bu_k, k=0,…,N-1		
        x_k∈ X, u_k∈ U, k=0,…,N-1
        x_N ∈ X_f,  x_0 = x(t),

where N is the length of the horizon and P,Q,R≻ 0 are cost matrices. 

For reasons related to error bounding, explained in Section <ref>, in this paper, we consider input constrained systems: , 0∈ U = {-l_u≼ u≼ h_u}, and impose stability without a terminal state constraint, i.e. X_f = ℝ^n, but with appropriately chosen costs P,Q,R and horizon N such that the  system has robust performance to bounded errors due to encryption, which will be described in Section <ref>. 

A survey on the conditions for stability of MPC is given in <cit.>. 

Through straightforward manipulations, (<ref>) can be written as a quadratic program (see details on obtaining the matrices H and F in <cit.>) in the variable . 


    U^∗(x(t)) = _U∈ U1/2U^⊺ H U + U^⊺ F^⊺ x(t)


For simplicity, we keep the same notation for the augmented constraint set U. 

After obtaining the optimal solution, the first m components of U^∗(x(t)) are applied as input to the system (<ref>): . 

This problem easily extends to the case of following a reference.



 §.§ Solution without privacy requirements


The constraint set U is a hyperbox, so the projection step required for solving (<ref>) has a simple closed form solution and the optimization problem can be efficiently solved with the projected Fast Gradient Method (FGM) <cit.>, given in Algorithm <ref>. 

The objective function is strongly convex, since , therefore we can use the constant step sizes  and , where κ(H) is the condition number of H. 

Warm starting can be used at subsequent time steps of the receding horizon problem by using part of the previous solution U_K to construct a feasible initial iterate of the new optimization problem.

[Projected Fast Gradient Descent] 





 §.§ Privacy objectives


The unsecure cloud-MPC problem is depicted in Figure <ref>. 

The system's constant parameters A,B,P,Q,R,N are public, motivated by the fact the parameters are intrinsic to the system and hardware, and could be guessed or identified; however, the measurements, control inputs and constraints are not known and should remain private. 

The goal of this work is to devise private cloud-outsourced versions of Algorithm <ref> such that the client obtains the control input u^∗(t) for system (<ref>) with only a minimum amount of computation. 

The cloud (consisting of either one or two servers) should not infer anything else than what was known prior to the computation about the measurements x(t), the control inputs u^∗(t) and the constraints U. 

We tolerate  servers, meaning that they correctly follow the steps of the protocol but may store the transcript of the messages exchanged and process the data received to try to learn more information than allowed.
 
 
 
To formalize the privacy objectives, we introduce the privacy definitions that we want our protocols to satisfy, described in <cit.>, <cit.>. In what follows, {0,1}^∗ defines a sequence of bits of unspecified length. Given a countable index set I, an ensemble X = {X_i}_i∈ I, indexed by I, is a sequence of random variables X_i, for all i∈ I. 



The ensembles X={X_n}_n∈ℕ and Y={Y_n}_n∈ℕ are statistically indistinguishable, denoted s≡, if for every positive polynomial p and all sufficiently large n, the following holds, where Ω = Supp(X)∪Supp(Y): 

    1/2∑_α∈Ω|Pr[X_n = α] - Pr[Y_n = α]|< 1/p(n).






Two ensembles are called computationally indistinguishable if no efficient algorithm can distinguish between them. This is a weaker version of statistical indistinguishability. 



The ensembles X={X_n}_n∈ℕ and Y={Y_n}_n∈ℕ are computationally indistinguishable, denoted c≡, if for every probabilistic polynomial-time algorithm D:{0,1}^∗→{0,1}, called the distinguisher, every positive polynomial p, and all sufficiently large n, the following holds:

    |Pr_x← X_n [D(x) = 1] - Pr_y← Y_n[D(y) = 1] | < 1/p(n).






The definition of  privacy says that a protocol privately computes the functionality it runs if all information obtained by a party after the execution of the protocol, while also keeping a record of the intermediate computations, can be obtained only from the inputs and outputs of that party. 



 Let f:({0,1}^∗)^2→({0,1}^∗)^2 be a func-tionality, and f_i(x_1,x_2) be the ith component of f(x_1,x_2), i=1,2. 
Let Π be a  protocol for computing f. The view of the ith party during an execution of Π on the inputs (x_1,x_2), denoted by V^Π_i (x_1,x_2), is (x_i,coins,m_1,…,m_t), where coins represents the outcome of the ith party's internal coin tosses, and m_j represents the jth message it has received. For a deterministic functionality f, we say that Π privately computes f if there exist probabilistic polynomial-time algorithms, called simulators, denoted by S_i, such that:

 
    {S_i(x_i,f_i(x_1,x_2)) }_x_1,2∈{0,1}^∗c≡{V_i^Π (x_1,x_2)}_x_1,2∈{0,1}^∗.


When the privacy is , i.e., only the part of the protocol executed by party 2 has to not reveal any information, the above equation has to be satisfied only for i=2.
 
 

 
The purpose of the paper is to design protocols with the functionality of Algorithm <ref> that satisfy Definition <ref>. 

To this end, we use the encryption scheme defined in Section <ref>. Furthermore, we discuss in Section <ref> how we connect the domain of the inputs in Definiton <ref> with the domain of real numbers needed for the MPC problem. 

In Sections <ref> and <ref>, we address two private cloud-MPC solutions that present a  between the computational effort at the client and the total time required to compute the solution u^∗(t), which is analyzed in Section <ref>.

  
The MPC literature has focused on reducing the computational effort through computing a suboptimal solution to implicit MPC <cit.>. 

Such time optimizations, i.e., stopping criteria, reveal information about the private data, such as how far is the initial point from the optimum or the difference between consecutive iterates. 

Therefore, in this work, we consider a given fixed number of iterations K. 



§ PARTIALLY HOMOMORPHIC CRYPTOSYSTEM


Partially homomorphic encryption schemes can support additions between encrypted data, such as Paillier <cit.> and Goldwasser-Micali <cit.>, DGK <cit.>, or multiplications between encrypted data, such as El Gamal <cit.> and unpadded RSA <cit.>. 

In this paper, we use the Paillier cryptosystem <cit.>, which is an asymmetric additively homomorphic encryption scheme. 

The message space for the Paillier scheme is ℤ_N_σ, where N_σ is a large integer that is the product of two prime numbers p,q. 

The pair of keys corresponding to this cryptosystem is (pk,sk), where the public key is pk= (N_σ,g), with g∈ℤ_N_σ^2 having order N_σ and the secret key is sk = (γ,δ):


    γ = lcm(p-1,q-1), δ = ((g^γ mod N_σ^2 -1)/N_σ)^-1 mod N_σ.


For a message a∈ℤ_N_σ, called plaintext, the Pailler encryption primitive is defined as: 


    [[a]]:= g^ar^N_σ N_σ^2,  with r random value in ℤ_N_σ.
 

The encrypted messages are called ciphertexts.

A probabilistic encryption scheme, i.e., that takes random numbers in the encryption primitive, does not preserve the order from the plaintext space to the ciphertext space.

Intuitively, the additively homomorphic property states that there exists an operator ⊕ defined on the space of encrypted messages, with:


    [[a]]⊕[[b]] = [[a+b]],  ∀ a,b∈ℤ_N_σ,


where the equality holds in modular arithmetic, w.r.t. N_σ^2. 

Formally, the decryption primitive is a homomorphism between the group of ciphertexts, with the operator ⊕ and the group of plaintexts with addition +. 

The scheme also supports subtraction between ciphertexts, and multiplication between a plaintext and an encrypted message, obtained by adding the encrypted messages for the corresponding (integer) number of times: . 

We will use the same notation to denote encryptions, additions and multiplication by vectors and matrices. 

Proving privacy in the  model of a protocol that makes use of cryptosystems involves the concept of semantic security. 

Under the assumption of decisional composite residuosity <cit.>, the Paillier cryptosystem is semantically secure and has indistinguishable encryptions, which, in essence, means that an adversary cannot distinguish between the ciphertext [[a]] and a ciphertext [[b]] based on the messages a and b <cit.>.



An encryption scheme with encryption primitive E(·) is semantically secure if for every probabilistic polynomial-time algorithm, A, there exists a probabilistic polynomial-time algorithm A' such that for every two polynomially bounded functions f,h:{0,1}^∗→{0,1}^∗ and for any probability ensemble {X_n}_n∈ℕ, |X_n|≤ poly(n), for any positive polynomial p and sufficiently large n: 

    Pr   [ A(E(X_n),h(X_n)) = f(X_n)] < 
    Pr   [ A'(h(X_n)) = f(X_n)] + 1/p(n).






Cloud-based Linear Quadratic Regulator: 

We provide a simple example of how the Paillier encryption can be used in a private control application. If the problem is unconstrained, i.e., U=ℝ^m, a stabilizing controller can be computed as a linear quadratic regulator <cit.>. 

Such a controller can be computed only by one server. The client sends the encrypted state [[x(t)]] to the server, which recursively computes the plaintext control gain and solution to the Discrete Riccati Equations, with P_N = P:


    F_k = -(B^⊺ P_k+1B + R)^-1 B^⊺ P_k+1A,   k=N-1,…,0
       P_k = A^⊺ P_k+1A + Q + A^⊺ P_k+1 B F_k,
       [[u^∗(t)]] = F_0⊗[[x(t)]].


The server obtains the encrypted control input and returns it to the client, which decrypts and inputs it to the system.

To summarize, PHE allows a party that does not have the private key to perform linear operations on encrypted integer data. 

For instance, a cloud-based Linear Quadratic Controller can be computed entirely by one server, because the control action is linear in the state. 

Nonlinear operations are not supported within this cryptosystem, but can be achieved with communication between the party that has the encrypted data and the party that has the private key, and we will use this in Sections <ref> and <ref>. 





§ CLIENT-SERVER ARCHITECTURE


To be able to use the Paillier encryption, we need to represent the messages on a finite set of integers, parametrized by N_σ, i.e., each message is an element in ℤ_N_σ. 

Usually, the values less than N_σ/3 are interpreted to be positive, the numbers between 2N_σ/3 and N_σ to be negative, and the rest of the range allows for overflow detection. 

In this section and Section <ref>, we consider a  representation of the values and perform implicit multiplication steps to obtain integers and division steps to retrieve the true values. 

We analyze the implications of the  representation over the MPC solution in Section <ref>.

Notation: Given a real quantity x∈ℝ, we use the notation x̅ for the corresponding quantity in  representation on one sign bit, l_i integer and l_f fractional bits. 

We introduce a  model, depicted in Figure <ref>. 

We present an interactive protocol that privately computes the control input for the client, while maintaining the privacy of the state in Protocol <ref>. 

The Paillier encryption is not order preserving, so the projection operation cannot be performed locally by the server. 

Hence, the server sends the encrypted iterate [[t_k]] for the client to project it. Then, the client encrypts the feasible iterate and sends it back to the cloud.



We drop the (̅·̅)̅ from the iterates in order to not burden the notation.

[Encrypted projected Fast Gradient Descent in a  architecture] 






	Protocol <ref> achieves privacy as in Definition <ref> with respect to a semi-honest server.




The initial value of the iterate does not give any information to the server about the result, as the final result is encrypted and the number of iterations is a priori fixed. 

The view of the server, as in Definition <ref>, is composed of the server's inputs, the messages received {[[U_k]]}_k=0,…,K, which are all encrypted, and no output. 

We construct a simulator which replaces the messages with random encryptions of corresponding length. 

Due to the semantic security (see Definition <ref>) of the Paillier cryptosystem, which was proved in <cit.>, the view of the simulator is computationally indistinguishable from the view of the server.






§ TWO-SERVER ARCHITECTURE
 

Although in Protocol <ref>, the client needs to store and process substantially less data than the server, the computational requirements might be too stringent for large values of K and N_σ. 

In such a case, we outsource the problem to two servers, and only require the client to encrypt x(t) and send it to one server and decrypt the received the result [[u^∗]]. 

In this setup, depicted in Figure <ref>, the existence of two  servers is assumed. 

In Figure <ref> and in Protocol <ref>, we will denote by [[·]] a message encrypted with pk_1 and by [{·}] a message encrypted by pk_2. 

The reason we use two pairs of keys is so the client and support server do not have the same private key and do not need to interact.



As before, we need an interactive protocol to achieve the projection. We use the DGK comparison protocol, proposed in <cit.>, such that, given two encrypted values of l bits [[a]],[[b]] to S_1, after the protocol, S_2, who has the private key, obtains a bit (β = 1)≡(a≤ b), without finding anything about the inputs. 

Moreover, S_1 finds nothing about β. We augment this protocol by introducing a step before the comparison in which S_1 randomizes the order of the two values to be compared, such that S_2 does not know the significance of β with respect to the inputs. 

Furthermore, by performing a blinded exchange, S_1 obtains the minimum (respectively, maximum) value of the two inputs, without any of the two servers knowing what the result is. The above procedure is performed in lines 11–16 in Protocol <ref>. More details can be found in <cit.>.

The comparison protocol works with inputs that are represented on l bits. 

The variables we compare are results of additions and multiplications, which can increase the number of bits, thus, we need to ensure that they are represented on l bits before inputting them to the comparison protocol. 

This introduces an extra step in line 10 in which S_1 communicates with S_2 in order to obtain the truncation of the comparison inputs: S_1 adds noise to t_k and sends it to S_2 which decrypts it, truncates the result to l bits and sends it back. S_1 then subtracts the truncated noise. 

In order to guarantee that S_2 does not find out the private values after decryption, S_1 adds a sufficiently large random noise to the private data. 

The random numbers in lines 13 and 19 are chosen from (0,2^l+λ_σ)∩ℤ_N_σ, which ensures the statistical indistinguishability between the sum of the random number and the private value and a random number of equivalent length <cit.>, where λ_σ is the statistical security parameter.

[Encrypted projected Fast Gradient Descent in a  architecture] 







Protocol <ref> achieves privacy as in Definition <ref>, as long as the two  servers do not collude.





The view of S_1 is composed by its inputs and exchanged messages, and no output. All the messages the first server receives are encrypted (the same holds for the subprotocol DGK). 

Furthermore, in line 14, an encryption of zero is added to the quantity S_1 receives such that the encryption is re-randomized and S_1 cannot recognize it. 

Due to the semantic security of the cryptosystems, the view of S_1 is computationally indistinguishable from the view of a simulator which follows the same steps as S_1, but replaces the incoming messages by random encryptions of corresponding length.

The view of S_2 is composed by its inputs and exchanged messages, and no output. Apart from the comparison bits, the latter are always blinded by noise that has at least λ_σ bits more than the private data being sent. 

For λ_σ chosen appropriately large (e.g. 100 bits <cit.>), the following is true: a+rs≡ r', where a is a value of p bits, r is the noise chosen uniformly at random from (0,2^p+λ_σ)∩ℤ_N_σ and r' is a value chosen uniformly at random from (0,2^p+λ_σ+1)∩ℤ_N_σ. In the DGK subprotocol, a similar blinding is performed, see <cit.>.

Crucially, the noise selected by S_1 is different at each iteration. Hence, S_2 cannot extract any information by combining messages from multiple iterations, as they are always blinded by a different large enough noise. 

Moreover, the randomization step in line 11 ensures that S_2 cannot infer anything from the values of β_k, as the order of the inputs is unknown. 

Thus, we construct a simulator that follows the same steps as S_2, but instead of the received messages, it randomly generates values of appropriate length, corresponding to the blinded private values, and random bits corresponding to the comparison bits. 

The view of such a simulator will be computationally indistinguishable from the view of S_2.





One can expand Protocols <ref> and <ref> over multiple time steps, such that U_0 is obtained from the previous iteration and not given as input, and formally prove their privacy. 

The fact that the state will converge to a neighborhood of the origin is public knowledge, and is not revealed by the execution of the protocol. A more detailed proof that explicitly constructs the simulators can be found in <cit.>. 



Through communication, encryption and statistical blinding, the two servers can privately compute nonlinear operations. However, this causes an increase in the computation time due to the extra encryptions and decryptions and communication rounds, as will be pointed out in Section <ref>.




§  ARITHMETICS MPC


The values that are encrypted or added to or multiplied with encrypted values have to be integers. We consider  representations with one sign bit, l_i integer bits and l_f fractional bits and multiply them by 2^l_f to obtain integers. 


Working with  representations can lead to overflow, quantization and arithmetic  errors. 

Thus, we want to compute the deviation between the fixed-point solution and optimal solution of Algorithm <ref>. 

The bounds on this deviation can be used in an offline step prior to the online computation to choose an appropriate  precision for the performance of the system. 

Consider the following assumption:



The number of fractional bits l_f and constant c≥ 1 are chosen large enough such that:


	
  (i) U̅⊆ U: the  precision solution is still feasible. 
	
  (ii) The eigenvalues of the  representation H̅_f are contained in the set (0, 1], where 
	
    H_f := H̅/ (cL̅)  and L̅ := λ_max(H̅).

	The constant c is required in order to overcome the possibility that (1/L̅)H̅ has the maximum eigenvalue larger than 1 due to  arithmetic errors.
	
  (iii) The  representation of the step size satisfies:
	
    0≤(√(κ(H̅))-1)/(√(κ(H̅))+1) ≤η̅< 1.






Item (i) ensures that the feasibility of the  precision solution is preserved, item (ii) ensures that the strong convexity of the  objective function still holds and item (iii) ensures that the  step size is such that the FGM converges.



Overflow errors: 
Bounds on the infinity-norm on the  dynamic quantities of interest in Algorithm <ref> were derived in <cit.> for each iteration k, and depend on a bounded set X_0 such that x(t)∈ X_0 and x̅(t) ∈X̅_̅0̅:


    ||U̅_k+1||_∞   ≤max{||l̅_u||_∞, ||h̅_u||_∞} = R_U̅
    
    ||z̅_k+1||_∞   ≤ (1+ 2η̅)  R_U̅: = ζ,
    
    ||t̅_k||_∞   ≤ ||I_Nm - H̅_f||_∞ζ + ||F̅_f||_∞ R_X̅_̅0̅,


where F_f = F̅/(cL̅) and R_ S represents the radius of a set S w.r.t. the infinity norm. 

We select from these bounds the number of integer bits l_i such that there is no overflow. 




 §.§ Difference between real and  solution


We want to determine a bound on the error between the  precision solution and the real solution of the MPC problem (<ref>). The total error is composed of the error induced by having  coefficients and variables in the optimization problem, and by the round-off errors. 

Specifically, denote by U_K the solution in exact arithmetic of the MPC problem (<ref>) obtained after K iterations of Algorithm <ref>. 

Furthermore, denote by Ũ_K the solution obtained after K iterations but with H,F,x(t), U,L,η replaced by their  representations. 

Finally, denote by U̅_K the solution of Protocols <ref> and <ref> after K iterations, where the iterates [[t_k]],[[U_k]] have  representation, i.e, truncations are performed. 

We obtain the following upper bound on the difference between the solution obtained on the encrypted data and the nominal solution of the implicit MPC problem (<ref>) after K iterations:


    ||U̅_K - U_K||_2 ≤ ||Ũ_K - U_K||_2+ ||U̅_K - Ũ_K||_2.




  §.§.§ Quantization errors


We will use the following observation to investigate the quantization error bounds. Define ϵ_a = a̅ - a and ϵ_b = b̅ - b. Then: 


    a̅b̅ - ab = a̅b̅ - a̅ b + a̅ b - ab = ϵ_a b + a̅ϵ_b.


Consider problem (<ref>) where the coefficients are replaced by the  representations of the matrices H/(cL),F/(cL), of the vector x(t) and of the set U, but otherwise the iterates Ũ_k,t̃_k, z̃_k are real values. 

Now, consider iteration k of the projected FGM. The errors induced by quantization of the coefficients between the original iterates and the approximation iterates will be:


    t̃_k - t_k =    -ϵ_H_fz_k + ( I_Nm-H̅_f)ϵ_z,k-ϵ_Fx
    ξ^q_k+1 :=    Ũ_k+1 - U_k+1 = D_k^q(t̃_k - t_k)	
    z̃_k+1 - z_k+1 =    ϵ_ηΔ U_k + (1+η̅)ξ^q_k+1 - η̅ξ^q_k,


where we used the notation: 

Δ U_k = U_k+1-U_k; ; ϵ_H_f =  H̅_f - H/(cL); 
ϵ_Fx = F̅_f^⊺x̅(t)-F^⊺ x(t)/(c L) = ϵ_F_f^⊺ x(t) + F̅_f ϵ_x; 
ϵ_x = x̅(t) - x(t); ϵ_F_f = F̅_f - F/(cL). 

The error between Ũ_k+1 and U_k+1 is reduced from t̃_k - t_k due to the projection on the hyperbox. Hence, to represent ξ^q_k+1 in (<ref>), we multiply t̃_k - t_k by the diagonal matrix D_k^q that has positive elements at most one. 

We set ξ^q_-1=ξ^q_0. From (<ref>), we derive a recursive iteration that characterizes the error of the primal iterate, for k=0,…,K, which we can write as a linear system:


    Ã(D_k^q):=   [ (1+η̅)D_k^q( I_Nm  - H̅_f)     -η̅D_k^q( I_Nm  - H̅_f)
     I_Nm    0_Nm]
    B̃(D_k^q):=   [ -ϵ_H_fD_k^q    ϵ_η D_k^q( I_Nm - H̅_f)
     0_Nm    0_Nm] 
    [ ξ^q_k+1
    ξ^q_k] =   Ã(D_k^q) [ ξ^q_k
    ξ^q_k-1] + B̃(D_k^q)[ z_k
    Δ U_k-1] - ϵ_Fx.


We choose this representation in order to have a relevant error bound in Theorem <ref> that shrinks to zero as the number of fractional bits grows. 

In the following, we find an upper bound of the error using Ã := Ã( I_Nm) and B̃ := B̃( I_Nm).



Under Assumption <ref>, the system defined by (<ref>) is bounded. Furthermore, the norm of the error between the primal iterates of the original problem and of the problem with quantized coefficients is bounded by:


    ||ξ^q_k||_2 ≤||EÃ^k ||_2 ||[ ξ^q_0
    ξ^q_-1] ||_2
     + γ∑_l=0^k-1|| EÃ^k-1-lB̃||_2 + 
       + ζ∑_l=0^k-1|| EÃ^k-1-l||_2 =: ϵ_1;  γ = (3+2η̅)√(Nm) R_U̅,
       ζ = ||ϵ_F_f||_2  R^2_ X_0 + 2^-l_f√(n)||F̅_f||_2,


where E = [ I_Nm  0_Nm], R^2_ X_0 is the radius of the compact set X_0 w.r.t. the 2-norm and R_U̅=max{||l_u||_∞, ||h_u||_∞}.





	The inner stability of the system is given by the fact that Ã has spectral radius ρ(Ã)<1 which is proven in Lemma 1 in <cit.>. The same holds for Ã(D_k^q). Since we want to give a bound of the error in terms of computable values, we use the fact that ||Ã(D_k^q)||_2≤ ||Ã||_2 (resp., ||B̃(D_k^q)||_2≤ ||B̃||_2) and express the bounds in terms of the latter.
	
	From (<ref>), one can obtain the following expression for the errors at time k and k-1, for k=0,…,K-1:

    [ ξ^q_k
    ξ^q_k-1]    ≤Ã^k[ ξ^q_0
    ξ^r_-1] + 
    	∑_l=0^k-1Ã^k-1-l(B̃[ z_l
    Δ U_l-1] - ϵ_Fx),

and the first term goes to zero as k→∞. 
We multiply this by E = [ I_Nm 0_Nm] to obtain the expression of ||ξ^q_k||.

	Subsequently, for any 0≤ k≤ K-1:


    |  | [ z_k^⊺  Δ U_k-1^⊺]^⊺| |_2 = ||z_k ||_2 + ||Δ U_k-1||_2,
       ≤ ||U_k + η̅Δ U_k-1||_2 + ||Δ U_k||_2 ≤ R_U̅ + 2(1+η̅) R_U̅
       ≤ (3+2η̅)√(Nm (max_i {l_u^i,h_u^i})^2) :=γ
       ||ϵ_Fx||_2 ≤  ||ϵ_F_f||_2 || x(t)||_2 + ||F̅_f||_2 || ϵ_x||_2
       ≤  ||ϵ_F_f||_2  R^2_ X_0 + 2^-l_f√(n)||F̅_f||_2 :=ζ.




One can eliminate the initial error ξ^q_0 and its effect by choosing in both exact and  coefficient-FGM algorithms the initial iterate to be represented on l_f fractional bits. Therefore, only the persistent noise counts. 



In primal-dual algorithms, the maximum values of the dual variables corresponding to the complicating constraints cannot be bounded a priori, i.e., we cannot give overflow or coefficient quantization error bounds. This justifies our focus on a problem with only simple input constraints. 

The work in <cit.> considers the bound on the dual variables as a parameter that can be tuned by the user. 







  §.§.§ Arithmetic round-off errors


Let us now investigate the error between the solution of the previous problem and the solution of the  FGM corresponding to Protocols <ref> and <ref>. 

The encrypted values do not necessarily maintain the same number of bits after operations, so we will consider round-off errors where we perform truncations. This happens in line 10 in both protocols. 

In this case, we obtain similar results to <cit.>, where the quantization errors were not analyzed, i.e., as if the nominal coefficients of the problem were represented with l_f fractional bits from the problem formulation. Consider iteration k of the projected FGM. 

The errors due to  between the primal iterates of the two solutions will be:


    t̅_k - t̃_k =    ( I_Nm - H̅_f)(z̅_k - z̃_k) + ϵ'_t,k
    ξ^r_k+1 :=   U̅_k+1 - Ũ_k+1 = D_k^r(t̅_k - t_k)      
    z̅_k+1 - z̃_k+1 =    (1+η̅)ξ^r_k+1 - η̅ξ^r_k.


Again, the projection on the hyperbox reduces the error, so D_k^r is a diagonal matrix with positive elements less than one. For Protocol <ref>, the  error due to truncation is , i=1,…,Nm. 

The encrypted truncation step in Protocol <ref> introduces an extra term due to blinding, making .

We set set ξ^r_-1=ξ^r_0. From (<ref>), we can derive a recursive iteration that characterizes the error of the primal iterate, which we can write as a linear system, with Ã(·) as before:


    [ ξ^r_k+1
    ξ^r_k] =   Ã(D_k^r) [ ξ^r_k
    ξ^r_k-1] + D_k^r ϵ'_t,k.




Under Assumption <ref>, the system defined by (<ref>) is bounded. Furthermore, the norm of the error of the primal iterate is bounded by:


    ||ξ^r_k||_2 ≤   ||EÃ^k ||_2 ||[ ξ^r_0
    ξ^r_-1] ||_2 + γ'∑_l=0^k-1|| EÃ^k-1-l||_2 =: ϵ_2,
    γ_CS'=    2^-l_f(Nm)^3/2; γ_SS'=2^-l_f√(Nm)(1+Nm).






The proof is straightforward. 

As before, one can eliminate the initial error ξ^r_0 and its effect by choosing the same initial iterate represented on l_f fractional bits for both problems. 



As l_f→∞, ϵ_1→ 0 and ϵ_2→ 0. The persistent noise in (<ref>) and (<ref>), which is composed by quantization errors and round-off errors, becomes zero when the number of fractional bits mimics a real variable. This makes systems (<ref>) and (<ref>) input-to-state stable.





 §.§ Choice of error level


For every instance of problem (<ref>), the error bound ϵ:=ϵ_1+ϵ_2 can be computed as a function of the number of fractional bits l_f. 

We can incorporate these errors as a bounded disturbance d(·) in system (<ref>): d(t) = Bξ(t), where ξ(t) = u^∗(t) - u̅(t). 

Then, we can design the terminal cost as described in <cit.>, such that the controller achieves inherent robust stability to process perturbations ||d(t)||_2≤δ, and choose: ϵ≤δ/||B||. 

Alternatively, we can incorporate the error in the suboptimality of the cost and assume that we obtain a cost , and compute ϵ such that asymptotic stability is achieved as in <cit.>.

In the offline phase, the  precision of the variables (the number of integer bits l_i and the number of fractional bits l_f) is chosen such that there is no overflow and one of the conditions on ϵ is satisfied. Note that these conditions can be overly-conservative. This ensures that the MPC performance is guaranteed with a large margin, but the computation is slower because of the large number of bits.



Instead of the FGM, we can use the simple gradient descent method, where fewer errors accumulate, and less memory is needed, but more iterations are necessary to reach to the optimal solution.



Once l_i and l_f have been chosen, we can pick N_σ such that the there is no overflow in Protocol <ref> and Protocol <ref>, respectively. 

In Protocol <ref>, truncation cannot be done on encrypted data by the server, thus, the multiplications by 2^l_f are accumulated between z_k and t_k, which means that t_k is multiplied by 2^3l_f. Hence, we choose N_σ such that l_i+3l_f + 2 < log_2 (N_σ/3) holds. 

For Protocol <ref> we pick N_σ such that l_i+3l_f + 3 + λ_σ < log_2 (N_σ/3) holds, where λ_σ is the statistical security parameter. 

If the N_σ that satisfies these requirements is too large, one should use the simple gradient method, which will have multiplications up to 2^2l_f. 





§ NUMERICAL RESULTS AND TRADE-OFF
 

The number of bits in the representation is crucial for the performance of the MPC scheme. At the same time, a more accurate representation slows down the private MPC computation. 

In Figure <ref>, for a toy model of a spacecraft from <cit.> and based on <cit.>, we compare the predicted theoretical error bounds from Theorems <ref> and <ref> and the norm of the actual errors between the control input obtained with the  protocol and the control input of the unencrypted MPC. 

The simulation is run for a time step of MPC with 18 iterations, with three choices of the number of fractional bits: 16, 24 and 32 bits. The results are similar for the  protocol. 

We can observe that the predicted errors are around two orders of magnitude larger than the real errors caused by the encryption, and even for 16 bits of precision, the actual error is small.



Furthermore, we implemented the above two protocols for various problem sizes. Table <ref> shows the computation times for Protocols <ref> and <ref> for l_i = 16 integer bits and l_f∈{16,32} fractional bits. We fix the number of iterations to 50. 

The times obtained vary linearly with the number of iterations, so one can approximate how long it would take to run a different number of iterations. The size of the N_σ for the encryption is chosen to be 512 bits. The computations have been effectuated on a 2.2 GHz Intel Core i7.



The larger the number of fractional bits, the larger is the execution time, because the computations involve larger numbers and more bits have to be sent from one party to another in the case of encrypted comparisons. 

Communication is the reason for the significant  observed in the  architecture compared to the  architecture. 

Performing the projection with PHE requires l communication rounds, where l is the number of bits of the messages compared. 

Privately updating the iterates requires another communication round. 

However, the assumption is that the servers are powerful computers, and the execution time can be greatly improved using parallelization and more efficient data structures.

To summarize, privacy comes at the price of complexity: hiding the private data requires working with large encrypted numbers, and the computations on private data require communication. 

Furthermore, the more parties that need to be oblivious to the private data (two servers in the second architecture compared to one server in the first architecture), the more complex the private protocols become.






§ CONCLUSION


In this paper, we have presented two methods to achieve the private computation of the solution to cloud-outsourced implicit MPC, through additively homomorphic encryption. 

The client, which is the owner of a linear-time discrete system with input constraints, desires to keep the measurements, the constraints and the control inputs private. 

The cloud, which can be composed by one or two servers, knows the parameters of the system and has to relieve the computation, i.e., solving the optimization problems, from the client in a private manner. 

The first method proposes an architecture where the computation is split between the client and one server. The client encrypts the current state with a PHE scheme, and performs the nonlinear operations (the projection on the constraints), while the server performs the rest of the computations needed to solve the optimization problem via the fast gradient method. 

Secondly, we propose a  architecture, in which the client is exempt from any computations apart from encrypting the state and decrypting the input. The two servers engage in a protocol to solve the optimization problem and use communication to perform the nonlinear operations on encrypted data. We prove that both protocols are private for  servers.

In order to use encryptions, we map the real values to rational  values. We analyze the errors introduced by the associated quantization and  errors and give upper bounds which can be used to choose an appropriate precision that corresponds to performance requirements on the MPC. Furthermore, we implement the two proposed protocols and perform numerical tests.

The two architectures proposed in this paper offer insights for a more common architecture met in practice of multiple clients and one server, which we will consider in future work.






§ ACKNOWLEDGEMENTS

This work was supported in part by ONR N00014-17-1-2012, and by NSF CNS-1505799 grant and the Intel-NSF Partnership for Cyber-Physical Systems Security and Privacy.






IEEEtran


