# A New Algorithm for Privacy-Preserving Horizontally Partitioned Linear Programs

Authors: Chengxue Zhang; Debin Kong; Peng Pan; Mingyuan Zhou
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In a linear programming for horizontally partitioned data, the equality constraint matrix is divided into groups of rows. Each group of the matrix rows and the corresponding right-hand side vector are owned by different entities, and these entities are reluctant to disclose their own groups of rows or right-hand side vectors. To calculate the optimal solution for the linear programming in this case, Mangasarian used a random matrix of full rank with probability 1, but an event with probability 1 is not a certain event, so a random matrix of full rank with probability 1 does not certainly happen. In this way, the solution of the original linear programming is not equal to the solution of the secure linear programming. We used an invertible random matrix for this shortcoming. The invertible random matrix converted the original linear programming problem to a secure linear program problem. This secure linear programming will not reveal any of the privately held data.


---

## Body

## 1. Introduction

Recently, people have become interested in privacy-preserving classification and data mining [1–10] and have been involved in the field of optimization, especially in linear programming [11–15], where the data to be classified or mined belongs to different entities that are not willing to disclose the data. Mangasarian [13] proposed a random matrix which make the original linear programming problem into a secure linear programming problem. When the random matrix is not full rank [16], especially when the entities collide with each other, the original linear programming problem is not equivalent to the secure linear programming problem. We address this problem by using an invertible matrix multiplied by the two sides of the equality constraints of the linear program. This procedure converts the original linear program to an equivalent secure linear program, and this security linearity does not reveal any private data. This solution vector can be made public and applied by all entities. On the contrary, this algorithm prevents entities from colliding with each other.Here, we define some symbols. If a vector is not transposed to the row vector by the superscriptT, the vector will be a column vector. For a vector x∈Rn, the symbol xj will represent the jth component or jth block of the component. We will define the scalar (inner) product of two vectors x and y in the n-dimensional real space Rn as xTy. The symbol A∈Rm×n will represent a real m×n matrix. Similarly, AT will represent the transpose of A and Ai. will represent the i row or i block of rows of A and A.j the jth column or the jth block of columns of A. A zero vector in a real space of any dimension will be denoted by 0.


## 2. Privacy-Preserving Linear Programming for Horizontally Partitioned Data

Consider the following linear programming:(1)minz=cTx,s.t.Ax=bx≥0.Here,Ab consists of the matrix A∈Rm×n and the right-hand vector b∈Rm and is divided into p horizontal blocks. The number of rows of the p horizontal block is recorded as m1,m2,…,mp, where m1+m2+⋯+mp=m. An m order identity matrix E is divided into pvertical blocks. The number of columns of the p vertical block is recorded as m1,m2,…,mp, where m1+m2+⋯+mp=m. Each block of rows of [A b] corresponding to the index sets I1,I2,…,Ip, ∪i=1pIi=1,2,…,m, is owned by a distinct entity that is unwilling to make its block of data public or share it with the other entities. We will accomplish this goal by the following transformation.Each entityi,i=1,2,…,p, chooses its own private random matrix B.Ii∈Rm×mi, whose corresponding index set is Ii. The value of each element in B.Ii is in the interval0,1. The following decompositions can be obtained: A=AI1.AI2.⋮AIp. and b=bI1bI2⋮bIp. Define(2)B=B.I1+λE.I1B.I2+λE.I2⋯B.Ip+λE.Ip,λ∈R,λ≥n.Because the matrixB is an m order strictly diagonally dominant matrix, we can easily conclude that the matrix B is an invertible matrix [17]. Based on this fact, we define the following operation:(3)BA=B.I1+λE.I1B.I2+λE.I2⋯B.Ip+λE.IpAI1.AI2.⋮AIp.=B.I1+λE.I1AI1.+B.I2+λE.I2AI2.+⋯+B.Ip+λE.IpAIp.,Bb=B.I1+λE.I1B.I2+λE.I2⋯B.Ip+λE.IpbI1bI2⋮bIp=B.I1+λE.I1bI1+B.I2+λE.I2bI2+⋯+B.Ip+λE.IpbIp.According to the above discussion, the original linear programming (1) was converted into the following secure linear programming:(4)minz=cTx,s.t.,BAx=Bbx≥0.The linear programming (1) and the linear programming (4) have the same solution set since the matrix B is invertible. The linear programming (4) is quite safe since only the entity i knows B.Ii, i=1,2,…,p. Other entities cannot compute AIi. and bIi from B.Ii+λE.IiAIi. and B.Ii+λE.IibIi without knowing the random matrix B.Ii. We regard the linear programming (4) as a secure linear programming. Whether the linear programming (1) is equivalent to the linear programming (4) or not? Let us discuss next.Proposition 1.
If the matrixB is an m order invertible matrix; then, the secure linear program (4) is solvable if and only if the linear program (1) is solvable in case the solution sets of the two linear programs are identical.Proof.
As the matrixB is an m-order invertible matrix, the following relation holds:(5)Ax=b⇔BAx=Bb.
Therefore, the feasible regions of the two linear programs are the same. Again according to the objective functions of the linear programming (1) and the linear programming (4), we can conclude that the two linear programs have the same solution set.
The following algorithm can get the best solution of the linear programming (1) without revealing any private data.


## 3. Formulation of the Privacy-Preserving Algorithm

As shown in Section2, the linear program (1) is divided among p entities. We put forward the following algorithm:Step 1. All entities choose a suitable real number λ, λ≥n together.Step 2. Suppose the matrix AIi.bIi has mi rows, where i=1,2,…,p. A random matrix B.Ii is generated by the entity possessing the matrix AIi.bIi, where B.Ii∈Rm×mi. The value of each element in B.Ii is in the interval (0,1), and B.Ii is not public.Step 3. The entity that owns the matrix AI1.bI1 is responsible to compute B.I1+λE.I1AI1. and B.I1+λE.I1bI1, and the result is passed to the entity that owns the matrix AI2.bI2. Then, the entity that owns the matrix AI2.bI2 is responsible to compute B.I1+λE.I1AI1.+B.I2+λE.I2AI2. and B.I1+λE.I1bI1+B.I2+λE.I2bI2, and the result is passed to the entity that owns the matrix AI3.bI3. And, finally, the entity that owns the matrix AIp.bIp is responsible to compute the following:(6)BA=B.I1+λE.I1AI1.+B.I2+λE.I2AI2.+⋯+B.Ip+λE.IpAIp.,(7)Bb=B.I1+λE.I1bI1+B.I2+λE.I2bI2+⋯+B.Ip+λE.IpbIp.Step 4. Utilizing the linear programming (4) to calculate the minimum value and the optimal solution of the objective function, which is the minimum value and the optimal solution of the objective function of the linear programming (1).Remark 1.
Through this algorithm, the solution vectorx can be used publicly. However, it does not reveal any entity’s data.


## 4. Numerical Experiments

A linear programming:(8)minz=−3x1−5x2,s.t.x1+x3=8,2x2+x4=12,3x1+4x2+x5=36,xi≥0,i=1,…,5.We can find that the optimal solution of (8) is x∗=4,6,4,0,0T.Let I1=1,2,I2=3, AI1.=1010002010,AI2.=34001, bI1=812,bI2=36, and λ=5.Entity 1 generates a random matrixB.I1 which is not published. Note that(9)B.I1=0.95010.76210.23110.76210.60680.7621.Entity 1 makes public its matrix productB.I1+λE.I1AI1. and B.I1+λE.I1bI1.Entity 2 generates a random matrixB.I2 which is not published. Note that(10)B.I2=0.76210.76210.7621.Entity 2 makes public its matrix productB.I2+λE.I2AI2. and B.I2+λE.I2bI2.These products do not reveal any private data, but it can be used to calculate the constraint matrixBA and the right-hand side Bb of the secure linear programming. Next, we derive a linear programming (11) from the linear programming (4), which is equivalent to linear programming (8):(11)minz=−3x1−5x2,s.t.8.2364x1+4.5726x2+5.9501x3+0.7621x4+0.7621x5=84.1816,2.5174x1+14.5726x2+0.2311x3+5.7621x4+0.7621x5=98.4296,17.8931x1+24.5726x2+0.6068x3+0.7621x4+5.7621x5=221.4352,xi≥0i=1,…,5.The solution of this secure linear programming (11) is the same as that of the linear programming (8). This solution can be made public without revealing any private data.If we use Mangasarian’s study [13] which proposed the algorithm of privacy-preserving horizontally partitioned linear programs, the linear programming (8) needs to be converted into the following linear programming:(12)minz=−3x1−5x2,s.t.3.2364x1+4.5726x2+0.9501x3+0.7621x4+0.7621x5=44.1816,2.5174x1+4.5726x2+0.2311x3+0.7621x4+0.7621x5=38.4296,2.8931x1+4.5726x2+0.6068x3+0.7621x4+0.7621x5=41.4352,xi≥0i=1,…,5.The optimal solution to secure linear program (12) is x∗′=8,4,0,0,0T. This is not consistent with the optimal solution for the original linear programming (8). The reason for this error is that the random matrix B.I1B.I2=0.95010.76210.76210.23110.76210.76210.60680.76210.7621 is not a full rank matrix. In this way, the original linear programming (8) is not equivalent to the secure linear program (12).



---

*Source: 6651480-2021-02-11.xml*