# Secure PAC Bayesian Regression via Real Shamir Secret Sharing

Jaron Skovsted Gundersen, Bulut Kuskonmaz⋆, Rafael Wisniewski⋆ Aalborg
University, Department of Electronic System, {jaron, bku<EMAIL_ADDRESS>
###### Abstract

Common approach of machine learning is to generate a model by using huge
amount of training data to predict the test data instances as accurate as
possible. Nonetheless, concerns about data privacy are increasingly raised,
but not always addressed. We present a secure protocol for obtaining a linear
model relying on recently described technique called real number secret
sharing. We take as our starting point the PAC Bayesian bounds and deduce a
closed form for the model parameters which depends on the data and the prior
from the PAC Bayesian bounds. To obtain the model parameters one need to solve
a linear system. However, we consider the situation where several parties hold
different data instances and they are not willing to give up the privacy of
the data. Hence, we suggest to use real number secret sharing and multiparty
computation to share the data and solve the linear regression in a secure way
without violating the privacy of data. We suggest two methods; an inverse
method and a Gaussian elimination method, and compare these methods at the
end.

##  1 Introduction

The main purpose of machine learning is to find a model based on data such
that the model generalizes to instances outside the data set. The more data we
possess the better is our foundation for constructing a good model. However,
the data may be sensitive meaning that we are not allowed to share the data
with others. This could be the case if the data regards the price of houses,
health, or bank account information. In this paper, we consider the case where
several parties hold a data set and each party wants to learn a model
trained/based on the data in all the data sets. In other words, we strive
learn the model without giving up the privacy of the data. For this we propose
to use techniques from secure multiparty computation (MPC). Originally, MPC is
carried out over a finite field, but recent research consider MPC over real
numbers Tjell and Wisniewski (2021) and we will make use of this approach.

One way to determine a model is to rely on the PAC Bayesian framework, which
can be used if some prior knowledge of the model is available. There are a lot
of PAC Bayesian bounds in the literature which assess the generalization error
with a high probability, see for instance Langford and Seeger (2001);
McAllester (2003); Catoni (2008); Alquier, Ridgway, and Chopin (2016). In this
paper, we use the PAC Bayesian framework to consider linear model estimation
together with a normally distributed prior. In this setup, one can show that
we can get a closed form solution for the estimation. However, with the
assumption that data is split between different parties, we show how one can
use MPC to compute the model without violating privacy.

##  2 Preliminaries

###  2.1 Notation

Let
$\mathcal{D}=\mathcal{D}_{1}\cup\mathcal{D}_{2}\cup\cdots\cup\mathcal{D}_{n}$
be a split data set and assume that party $i$ holds

$\mathcal{D}_{i}=\\{(\boldsymbol{\mathbf{x}}_{i1},y_{i1}),(\boldsymbol{\mathbf{x}}_{i2},y_{i2}),\ldots,(\boldsymbol{\mathbf{x}}_{in_{i}},y_{in_{i}})\\}$

Furthermore, we denote by $N=\sum_{i=1}^{n}n_{i}$ the number of elements in
$\mathcal{D}$ and assume that
$(\boldsymbol{\mathbf{x}}_{ij},y_{ij})\in\mathbb{R}^{d}\times\mathbb{R}$ where
$d$ is the dimension of data.

For a data point $(\boldsymbol{\mathbf{x}},y)\in\mathcal{D}$, the prediction
of $\boldsymbol{\mathbf{x}}$ based on a model $f$ is
$f(\boldsymbol{\mathbf{x}})$ and the loss is denoted by
$\ell(f(\boldsymbol{\mathbf{x}}),y)$. In this paper, we only consider the
squared loss function and we will use the notation
$\ell({f}(\boldsymbol{\mathbf{x}}),y)=(f(\boldsymbol{\mathbf{x}})-y)^{2}$. The
empirical loss is then denoted as

$\displaystyle\mathcal{L}_{N}(f)=\frac{1}{N}\sum_{i=1}^{n}\sum_{j=1}^{n_{i}}\ell(f(\boldsymbol{\mathbf{x}}_{ij}),y_{ij}).$

The generalization error is defined as the expected value of the loss
function, i.e. $\mathcal{L}(f)=E[\ell(f(\boldsymbol{\mathbf{x}}),y))]$, where
the expectation is taken over the joint distribution of
$\boldsymbol{\mathbf{x}}$ and $y$.

###  2.2 MPC

Secure multiparty computation deals with the situation where there are $n$
parties, each has an input to some function. The parties would like to learn
the output of the function without revealing their inputs to the other
parties. Many multiparty computation protocols are secret sharing-based
meaning that each party starts by sending a share of its input to all the
other parties. The share itself does not reveal information and in fact we say
that the secret sharing scheme has a privacy threshold on $t$, if $t$ shares
do not reveal anything about the secret. However, if more than $t$ shares are
collected we should be able to reconstruct the secret.

MPC can use properties for certain secret sharing scheme allowing us to do
computations on the shares. From these computations we end up with that the
parties having a share for the output. By broadcasting these shares, they can
by the reconstruction property in the secret sharing scheme compute the
output. For a comprehensive introduction to secret sharing and multiparty
computation, we refer the reader to Cramer, Damgård, and Nielsen (2015).

Typically MPC is carried out over a finite field and therefore it is only
shown how to securely carry out summation and multiplication. In this paper,
we would like to compute over the real numbers and therefore we need to be
able to carry out other computations as well. Some works embed secure
computations on real numbers into finite field operations by representing the
real numbers as fixed or floating points numbers. This is for instance the
case in the papers Catrina and Saxena (2010); Catrina and Dragulin (2009);
Aliasgari et al. (2013); Dimitrov et al. (2016). One of the main challenges
this approach faces is to carry out real number divisions in a secure way as
division in a finite field and integer division are completely different. As
an example consider the division $5/2$ in $\mathbb{F}_{11}$ and as integer
division. In the field the result is $8$ while as integer division we obtain
$2$. For this reason one cannot just carry out the division in the finite
field directly which implies that their division algorithms becomes further
complicated.

To obtain simpler protocols for the secure arithmetic over the real numbers we
take another approach in this paper. Instead of using secret sharing over a
finite field we base our secret sharing directly on the real numbers. This
idea has been introduced in Tjell and Wisniewski (2021). This comes with the
small drawback that a share might reveal a small amount of information. The
MPC over the real numbers uses some of the ideas from Shamir’s secret sharing
over a finite field. To secretly share a value $s\in\mathbb{F}$, where
$\mathbb{F}$ is a finite field, in Shamir’s scheme we choose $t$ coefficients,
$c_{i}\in\mathbb{F}$ uniformly at randomly and compute the polynomial

$f_{s}(x)=s+c_{1}x+c_{2}x^{2}+\cdots c_{t}x^{t}.$ (1)

The shares are evaluation points on this polynomial. For instance, if
$\alpha\in\mathbb{F}$ a share could be $f_{s}(\alpha)$. The privacy relies on
the uniform distribution in the finite field combined with Lagrange
interpolation arguments stating that $t+1$ points uniquely determines a
$t$-degree polynomial. From this we also obtain the reconstruction property.

###  2.3 MPC based on real number secret sharing

In this section, we will give a brief introduction to the ideas from Tjell and
Wisniewski (2021) and some of the obstacles they have to circumvent in order
to apply Shamir’s scheme over the real numbers. One of the obstacles is that
if the shares are constructed from the polynomial in (1) the information the
shares carry about the secret is dependent on how close the evaluation point
is to $0$. Furthermore, there is no uniform distribution on the real axis.

To circumvent the first obstacle the polynomial $f_{s}$ is constructed in
another way by using the Lagrange polynomial as a basis for all polynomial of
degree at most $t$ instead of the basis $\\{1,x,\ldots x^{t}\\}$. To be a bit
more formal let $\mathcal{P}=\\{\alpha_{i}\\}_{i=1,\ldots,n}$ and choose
randomly a subset $\mathcal{P}_{s}^{\prime}\subset\mathcal{P}$ of size $t$ and
let $\mathcal{P}_{s}=\mathcal{P}_{s}^{\prime}\cup\\{0\\}$. Consider the $t+1$
points $\mathcal{T}=\\{(\alpha_{i},\beta_{i})\\}_{i\in\mathcal{P}_{s}}$, where
we use $(\alpha_{0},\beta_{0})=(0,s)$. The $\beta_{i}$’s for $i>0$ are chosen
randomly according to a normal distribution with variance
$\sigma_{\beta}^{2}$. Define the Lagrange basis polynomials as
$L_{i}(x)=\prod_{j\in\mathcal{P}_{s}\setminus\\{i\\}}\frac{x-\alpha_{j}}{\alpha_{i}-\alpha_{j}}$.
Then we define

$\displaystyle f_{s}(x)=\sum_{i\in\mathcal{P}_{s}}\beta_{i}L_{i}(x).$ (2)

Since $L_{i}(\alpha_{j})=0$ when $i\neq j$ and $L_{i}(\alpha_{i})=1$ we obtain
that $f_{s}(x)$ is a polynomial of degree at most $t$ passing through the
points in $\mathcal{T}$. The shares are then evaluation points for this
polynomial in the elements in $\mathcal{P}$ meaning that the evaluation point
of party $i$ is $\alpha_{i}$. A share of the secret $s$ to the $i$’th party is
then $f_{s}(\alpha_{i})$. To denote that $s$ is secretly shared we write
$[s]$, which represents the vector
$(f_{s}(\alpha_{1}),f_{s}(\alpha_{2}),\ldots,f_{s}(\alpha_{n}))$ where the
$i$’th party knows the $i$’th entry.

We end this section with a description of how to compute on the shares. In the
paper Tjell and Wisniewski (2021) protocols for securely computing sums,
multiplications, and divisions over the real numbers are presented which are
generalizations of protocols and techniques for finite fields described in
Cramer, Damgård, and Nielsen (2015).

To carry out a secure sum, the parties locally add up the shares for the two
secrets. Specifically, assume that

$\displaystyle\begin{aligned}
&[x]=(f_{x}(\alpha_{1}),f_{x}(\alpha_{2}),\ldots,f_{x}(\alpha_{n}))\quad\text{and}\\\
&[y]=(f_{y}(\alpha_{1}),f_{y}(\alpha_{2}),\ldots,f_{y}(\alpha_{n}))\end{aligned}$
(3)

then by $[x]+[y]$ we mean that the parties locally sum up their shares. We
remark that $f_{x}(0)=x$ and $f_{y}(0)=y$ and the sum of the shares represents
a $t$-degree polynomial $f_{x+y}$ which evaluates to $x+y$ at zero. Hence, we
can write $[x]+[y]=[x+y]$. Similarly, we can add a known value to a secret
shared value by letting a single party add the value to its share and we can
multiply a known value to a secret shared value by letting each party multiply
its share by that given value. Thus, we also use the notation $a+[x]=[a+x]$
and $a\cdot[x]=[a\cdot x]$ to represent these computations.

We remark that all operations so far have not required any communication
between the parties if $[x]$ and $[y]$ is obtained beforehand. However, for
the multiplication and division protocols we require some communication. And
furthermore we require some preprocessed shares. Both of these subprotocols
require that some values are opened. This means that for a sharing $[x]$, we
reveal the value $x$ to the parties. This can be done by broadcasting the
shares to the other parties. Regarding multiplication we require a
preprocessed so-called Beaver triple $([a],[b],[c])$, where $a$ and $b$ are
normal distributed with variance $\sigma_{r}^{2}$ and $c=ab$. Then we can
compute $[d]=[x]-[a]$ and $[e]=[y]-[b]$ and open $d$ and $e$. If
$\sigma_{r}^{2}$ is large $a$ and $b$ masks $x$ and $y$ such that only
negligible information about $x$ and $y$ are revealed. By computing

$\displaystyle d\cdot[b]+e\cdot[a]+[c]+de=[xy]$

using the already described subprotocols for computing sums and adding and
multiplying scalars we obtain a share for the product.

At last, we describe how to invert real numbers securely since this combined
with multiplication is enough for division. Here we need a preprocessed random
value $[r]$, which again is normally distributed with variance
$\sigma_{r}^{2}$. We can then, using the multiplication protocol, compute
$[r]\cdot[x]=[rx]$ and open this value. Here $r$ masks the value $x$ such that
only negligible information about $x$ is revealed. By multiplying the constant
$\frac{1}{rx}$ to $[r]$ we obtain $[\frac{1}{rx}r]=[\frac{1}{x}]$.

We will also slightly abuse the notation and write $[X]$ for a matrix $X$ and
$[\boldsymbol{\mathbf{x}}]$ for a vector $\boldsymbol{\mathbf{x}}$. This means
that all the entries in $X$ or $\boldsymbol{\mathbf{x}}$ should be secret
shared. Furthermore, we sum secret shared matrices and vectors but here we
will simply use the secure summation protocol entrywise.

###  2.4 PAC Bayesian and linear regression

To use the PAC Bayesian framework we take as our starting point a bound on the
generalization error from Alquier, Ridgway, and Chopin (2016) and Germain et
al. (2016). It says that with probability more than $1-\delta$ the following
inequality is satisfied

$\displaystyle E_{f\sim\hat{\rho}}\mathcal{L}(f)$ $\displaystyle\leq
E_{f\sim\hat{\rho}}\mathcal{{L}}_{N}(f)+\frac{1}{\lambda}\left(KL(\hat{\rho},\pi)+\ln\frac{1}{\delta}+\Psi_{\ell,\pi}(\lambda,N)\right),$
(4)

where $\pi$ is considered as the prior distribution and $\hat{\rho}$ as the
posterior distribution of $f$, $\lambda$ is a tuning parameter which we return
to, and

$\Psi_{\ell,\pi}(\lambda,N)=\ln
E_{f\sim\pi}E_{(X,Y)}e^{\lambda(\mathcal{L}(f)-\mathcal{L}_{N}(f))}.$

The left-hand side of the inequality in (4) is the expected generalization
error, so the idea is to upper bound this with a high probability. For a given
data set, tuning parameters and prior, in order to minimize the right-hand
side, we need to choose a posterior $\hat{\rho}$ such that we minimize
$E_{f\sim\hat{\rho}}\mathcal{{L}}_{{N}}(f)+\frac{1}{\lambda}KL(\hat{\rho},\pi)$
since these are the only terms depending on $\hat{\rho}$. From Alquier,
Ridgway, and Chopin (2016) we know that the posterior which minimizes this
part is the Gibbs posterior

$\displaystyle\hat{\rho}^{*}(f)=\frac{1}{E_{f\sim\pi}e^{-\lambda{\mathcal{L}}_{N}(f)}}\pi(f)e^{-\lambda{\mathcal{L}}_{N}(f)}.$
(5)

Hence, the Gibbs posterior gives the best distribution on $f$ to minimize the
right-hand side. To choose an $f$ from $\hat{\rho}^{*}(f)$ we decide to choose
$f_{*}=\mathrm{argmax}_{f}~{}\hat{\rho}^{*}(f)$. Hence, we need to minimize
the following

$\displaystyle\lambda{\mathcal{L}}_{N}(f)-\ln\pi(f)$ (6)

with respect to $f$.

We now define our model space $\mathcal{F}$. We say that $\mathcal{F}$
consists of linear models, i.e.
$f(\boldsymbol{\mathbf{x}})=\boldsymbol{\mathbf{w}}\cdot\boldsymbol{\mathbf{x}}$
for some $\boldsymbol{\mathbf{w}}\in\mathbb{R}^{d}$. At last we put some
restrictions on our prior. Since $f$ is uniquely determined by
$\boldsymbol{\mathbf{w}}$ we define the prior on $\boldsymbol{\mathbf{w}}$. We
assume a normal distributed prior and restrict ourselves to positive definite
covariance matrices, i.e.,
$\pi(\boldsymbol{\mathbf{w}})=\mathcal{N}(\boldsymbol{\mathbf{\mu}}_{w};\Sigma_{w})$,
where $\Sigma_{w}$ is positive definite. With these assumptions (6) reduces to
that we have to minimize

$\displaystyle\frac{\lambda}{N}\sum_{i=1}^{n}\sum_{j=1}^{n_{i}}(\boldsymbol{\mathbf{w}}\cdot\boldsymbol{\mathbf{x}}_{ij}-y_{ij})^{2}+\frac{1}{2}(\boldsymbol{\mathbf{w}}-\boldsymbol{\mathbf{\mu}}_{w})^{T}\Sigma_{w}^{-1}(\boldsymbol{\mathbf{w}}-\boldsymbol{\mathbf{\mu}}_{w})$

with respect to $\boldsymbol{\mathbf{w}}$. This is a convex function, so
differentiating and setting equal to $\boldsymbol{\mathbf{0}}$ would yield the
minimum. Hence, to minimize it, we need to solve the following equation with
respect to $\boldsymbol{\mathbf{w}}$.

$\displaystyle\left(\frac{2\lambda}{N}\sum_{i=1}^{n}\sum_{j=1}^{n_{i}}\boldsymbol{\mathbf{x}}_{ij}\boldsymbol{\mathbf{x}}_{ij}^{T}+\Sigma_{w}^{-1}\right)\boldsymbol{\mathbf{w}}=\frac{2\lambda}{N}\sum_{i=1}^{n}\sum_{j=1}^{n_{i}}\boldsymbol{\mathbf{x}}_{ij}y_{ij}+\Sigma_{w}^{-1}\boldsymbol{\mathbf{\mu}}_{w}$
(7)

Setting $\lambda=0$ we obtain
$\boldsymbol{\mathbf{w}}=\boldsymbol{\mathbf{\mu}}_{w}$ meaning that the
posterior rely fully on the prior. On the other hand, letting $\lambda$ tend
to infinity we obtain that

$\boldsymbol{\mathbf{w}}=\left(\sum_{i=1}^{n}\sum_{j=1}^{n_{i}}\boldsymbol{\mathbf{x}}_{ij}\boldsymbol{\mathbf{x}}_{ij}^{T}\right)^{-1}\sum_{i=1}^{n}\sum_{j=1}^{n_{i}}\boldsymbol{\mathbf{x}}_{ij}y_{ij}$

meaning that the posterior fully rely on the data.

##  3 Distributed regression using PAC Bayes approach

We now focus on the distributed part, where the parties want to compute the
solution to (7) but without revealing the datapoints in $\mathcal{D}_{i}$ to
the other parties. We achieve this using tools from multiparty computation. We
first notice that the parties can compute the inner sums locally, i.e.

$\displaystyle{X}_{i}=\sum_{j=1}^{n_{i}}\boldsymbol{\mathbf{x}}_{ij}\boldsymbol{\mathbf{x}}_{ij}^{T},\quad{\boldsymbol{\mathbf{z}}}_{i}=\sum_{j=1}^{n_{i}}\boldsymbol{\mathbf{x}}_{ij}y_{ij},$

implying that (7) can be rewritten as

$\displaystyle\left(\frac{2\lambda}{N}\sum_{i=1}^{n}X_{i}+\Sigma_{w}^{-1}\right)\boldsymbol{\mathbf{w}}=\frac{2\lambda}{N}\sum_{i=1}^{n}\boldsymbol{\mathbf{z}}_{i}+\Sigma_{w}^{-1}\boldsymbol{\mathbf{\mu}}_{w}.$

What we need now is a secure way to compute the matrix on the left side of the
equality and the vector on the right side. Furthermore, we need a way to solve
a linear system $A\boldsymbol{\mathbf{w}}=\boldsymbol{\mathbf{b}}$ in a secure
way without revealing $A$ and $\boldsymbol{\mathbf{b}}$.

In the following, we describe two ways for computing this securely and compare
the two approaches. First, we notice that the terms in $X_{i}$ are positive
semidefinite matrices and hence the sum of the $X_{i}$’s is a positive
semidefinite matrix. Since we assume that $\Sigma_{w}$ is positive definite we
have that the matrix
$\frac{2\lambda}{N}\sum_{i=1}^{n}\sum_{j=1}^{n_{i}}\boldsymbol{\mathbf{x}}_{ij}\boldsymbol{\mathbf{x}}_{ij}^{T}+\Sigma_{w}^{-1}$
from (7) is positive definite. This also means that the matrix is invertible
and that the system in (7) has a unique solution.

Both methods we describe start with that the $i$’th party locally compute
$X_{i}$ and $\boldsymbol{\mathbf{z}}_{i}$ and secret share the entries between
all parties. Then by using the computations on shares described in Section 2.3
we can compute $[\frac{2\lambda}{N}\sum_{i=1}^{n}X_{i}+\Sigma_{w}^{-1}]$ and
$[\frac{2\lambda}{N}\sum_{i=1}^{n}\boldsymbol{\mathbf{z}}_{i}+\Sigma_{w}^{-1}\boldsymbol{\mathbf{\mu}}_{w}]$.
Now we have $A=\frac{2\lambda}{N}\sum_{i=1}^{n}X_{i}+\Sigma_{w}^{-1}$ and
$\boldsymbol{\mathbf{b}}=\frac{2\lambda}{N}\sum_{i=1}^{n}\boldsymbol{\mathbf{z}}_{i}+\Sigma_{w}^{-1}\boldsymbol{\mathbf{\mu}}_{w}$
secretly shared and we need a way to solve the system
$A\boldsymbol{\mathbf{w}}=\boldsymbol{\mathbf{b}}$. The complete protocol can
be found in Protocol 1 and it makes use of either the inverse method in
Protocol 2 or the Gaussian elimination method in Protocol 3.

Input: $P_{i}$ holds $D_{i}=\\{(\boldsymbol{\mathbf{x}}_{ij},y_{ij})\mid
j=1,2,\ldots,n_{i}\\}$, where $N=\sum_{i=1}^{n}n_{i}$ is known. Furthermore,
the parties have agreed on a tuning parameter $\lambda$ and a normally
distributed prior on $\boldsymbol{\mathbf{w}}$ determined by
$\boldsymbol{\mathbf{\mu}}_{w}$ and $\Sigma_{w}$, where $\Sigma_{w}$ is
positive definite.
Output: The parties should learn $\boldsymbol{\mathbf{w}}$ satisfying (7).
The protocol:

  1. 1.

$P_{i}$ computes locally
${X}_{i}=\sum_{j=1}^{n_{i}}\boldsymbol{\mathbf{x}}_{ij}\boldsymbol{\mathbf{x}}_{ij}^{T}$
and
${\boldsymbol{\mathbf{z}}}_{i}=\sum_{j=1}^{n_{i}}\boldsymbol{\mathbf{x}}_{ij}y_{ij}$

  2. 2.

$P_{i}$ secretly shares $X_{i}$ and $\boldsymbol{\mathbf{z}}_{i}$ such that
the parties holds $[X_{i}]$, $[\boldsymbol{\mathbf{z}}_{i}]$.

  3. 3.

Using the secure protocols for summation, multiplication by scalar, and adding
scalar, the parties can compute

$[A]=\frac{2\lambda}{N}\sum_{i=1}^{n}[X_{i}]+\Sigma_{w}^{-1}\text{ and
}[\boldsymbol{\mathbf{b}}]=\frac{2\lambda}{N}\sum_{i=1}^{n}[\boldsymbol{\mathbf{z}}_{i}]+\Sigma_{w}^{-1}\boldsymbol{\mathbf{\mu}}_{w}$

  4. 4.

Solve $A\boldsymbol{\mathbf{w}}=\boldsymbol{\mathbf{b}}$ in a secure way by
giving $[A]$ and $[\boldsymbol{\mathbf{b}}]$ as input to either Protocol 2 or
Protocol 3

List of Schemes 1 Secure Regression with prior

In the following, we describe these two methods for solving the linear system
securely and compare the two methods afterwards.

###  3.1 The inverse method

One way to solve the system is to compute the inverse of $A$ securely and
multiply it with $\boldsymbol{\mathbf{b}}$ in a secure way. To this end, we
need to preprocess a secret shared random matrix, $[R]$, beforehand.
Subsequently, we mask $A$ by computing $[R]\cdot[A]=[RA]$. and open $RA$. Here
we remark, that $[R]\cdot[A]$ is matrix multiplication but since we have
subprotocols for addition and multiplication we can also carry out matrix
multiplication using these subprotocols. A random matrix will with high
propability be invertible, so we can compute the inverse of $RA$ and multiply
it by $[R]$. i.e. $(RA)^{-1}\cdot[R]=[A^{-1}R^{-1}R]=[A^{-1}]$, where the
products again refer to matrix multiplications. The complete protocol for this
secure inverse method can be found in Protocol 2.

Input: $[A]$ and $[\boldsymbol{\mathbf{b}}]$
Output: $\boldsymbol{\mathbf{w}}$ satisfying
$A\boldsymbol{\mathbf{w}}=\boldsymbol{\mathbf{b}}$.

  1. 1.

Compute $[R]\cdot[A]=[RA]$ using the secure summation and multiplication
protocols. Afterwards open the matrix such that each party learns $RA$

  2. 2.

Locally the parties can invert $RA$.

  3. 3.

Compute $(RA)^{-1}[R]=[A^{-1}]$ locally (secure addition and multiplication by
scalars)

  4. 4.

Compute $[\boldsymbol{\mathbf{w}}]=[A^{-1}][\boldsymbol{\mathbf{b}}]$ using
secure multiplications and additions and open $\boldsymbol{\mathbf{w}}$

List of Schemes 2 Inverse method

###  3.2 Pivoting-free Gaussian elimination

Input: $[A]$ and $[\boldsymbol{\mathbf{b}}]$
Output: $\boldsymbol{\mathbf{w}}$ satisfying
$A\boldsymbol{\mathbf{w}}=\boldsymbol{\mathbf{b}}$.

  1. 1.

Denote by $[C]=\left[[A]~{}|~{}[\boldsymbol{\mathbf{b}}]\right]$ the
$d\times(d+1)$ total matrix with shared entries

  2. 2.

for $k=1\ldots d$ do

for $i=k+1\ldots d$ do

$[\mathrm{frac}]=[c_{ik}]\cdot\frac{1}{[c_{kk}]}$

for $j=k\ldots d+1$ do

Compute $[c_{ij}]=[c_{ij}]-[\mathrm{frac}]\cdot[c_{kj}]$

$C$ is now an upper triangular matrix with nonzero elements on the diagonal

  3. 3.

for $i=0\ldots d-1$ do

$[w_{d-i}]=\frac{[c_{d-i,d+1}]-\sum_{j=1}^{i}[c_{d-i,d-i+j}]w_{d-i+j}}{[c_{d-i,d-i}]}$

Open $w_{d-i}$ to all parties

List of Schemes 3 Gaussian elimination method

The other matrix inversion method makes use of the fact that a system
$A\boldsymbol{\mathbf{w}}=\boldsymbol{\mathbf{b}}$, where $A$ is a symmetric
positive definite matrix, can be solved by Gaussian elimination without
pivoting. To see this, we make use of Sylvester’s criterion, stating the
following.

######  Proposition 1 (Sylvester’s criterion)

A symmetric $d\times d$ matrix $A$ is positive definite if and only if it has
nonsingular submatrices $A_{(i)}$ for $i=1,2,\ldots,d$, where $A_{(i)}$ is the
upper left $i\times i$ submatrix of $A$.

This means that we never have to interchange two rows when row-reducing since
the diagonal entries will always be nonzero. After we obtain an upper-
triangular matrix, we solve the system with backward substitution. We remark
that we do the row operations securely since they consists of operations we
have defined securely in section 2.3. We present the secure Gaussian
elimination protocol for computing $\boldsymbol{\mathbf{w}}$ in protocol 3.

##  4 Comparison

In this section, we compare the amount of information the parties need to send
between each other depending on the size of the matrix. We remark that it is
only multiplications, inversions and opening of shared values which require
that parties need to send information. All other computations can be carried
out locally. Hence, we count the number of these operations in the Gaussian
approach and the inverse approach. There are many methods for computing matrix
multiplication which asymptotically requires less than $\mathcal{O}(d^{3})$
but the constants in this notation might be huge. Thus, for this comparison we
think the most fair approach is to use the standard way to carry out matrix
multiplication which requires exactly $d^{3}$ multiplications. Furthermore,
our protocol requires additional $d^{2}$ openings since we are opening the
matrix $RA$. Afterwards we need to compute the product
$[A^{-1}][\boldsymbol{\mathbf{b}}]$ which requires $d^{2}$ multiplications and
open $\boldsymbol{\mathbf{w}}$ which gives $d$ openings. This gives a total of
$d^{3}+d^{2}$ multiplications and $d^{2}+d$ additional openings.

For the Gaussian method we use $\frac{d^{2}-d}{2}$ inversions and
multiplications to compute $[\mathrm{frac}]$. Then we use
$\frac{2d^{3}+3d^{2}-5d}{6}$ multiplications in the inner for-loop, and at
last we do $d$ inversions, multiplications, and openings in the last for-loop.
This gives a total of $\frac{d^{3}}{3}+d^{2}-\frac{d}{3}$ multiplications,
$\frac{d^{2}+d}{2}$ inversions, and additional $d$ openings.

Since the information sent during the multiplication and inversion protocols
are actually openings we can collect these number which makes it easier to
compare the two protocols. A multiplication consists of $2$ openings (the $d$
and $e$ from section 2.3) and an inversion consists of a multiplication and an
additional opening (the $rx$ from Section 2.3), implying a total of $3$
openings. Thus, we get that the total amount of openings are
$2d^{3}+3d^{2}+d$. Similarly, for the Gaussian method the amount of openings
are $\frac{2}{3}d^{3}+\frac{7}{2}d^{2}+\frac{11}{6}d$.

##  5 Analysis on privacy leakage

The protocols should avoid leakage of the data in $\mathcal{D}_{i}$ to other
parties. We define an adversary as an collection of up to $t$ parties who
share all their information (this is also known as a passive or semi-honest
adversary). We need to ensure that an adversary excluding the $i$’th party
will not learn much about the $X_{i}$ matrix since the data of this party is
part of this matrix. We borrow the notion of view of an adversary from MPC and
use this notion to argue privacy for our protocol. Define the $\mathrm{View}$
of an adversary as everything the adversary receives through the protocol
since this is what can lead to leakage. Hence, what we need to ensure is that

$\displaystyle I(X_{i};\mathrm{View})$ (8)

is small where $I(\cdot;\cdot)$ is the mutual information. It is hard to
compute the mutual information in (8), consequently we make simplifications to
evaluate an upper bound on it. Remark that the only information sent in the
protocols are sharings of entries in $X_{i}$ and openings of values. Let $x$
be any entry in $X_{i}$, and focus on $I(x;\mathrm{View})$ from now on. We
remark that every time we do an opening it is on the form $y-r$ or $yr$ for
some value $y$ which we want to hide and a large variance on $r$ provide us
that. For simplicity, we will only assume that the openings consists of values
on the form $y-r$. However, each party has also received a share of $r$ and
this might leak some information about $y$ as well. Furthermore, it might not
be the case that the $y$’s possess any information about the $x$ but to
simplify the computation of an upper bound we assume that $y$ always equals
$x$. As a consequence, we assume that each time we open a value in the
protocol it is $x-r$ for some normally distributed $r$ with variance
$\sigma_{r}^{2}$. This gives of course a very pessimistic bound but it
simplifies the computations. Hence, we get the following

$\displaystyle I(x,\mathrm{View})\leq
I(x,x-r_{1},\ldots,x-r_{O},\\{f_{x}(\alpha_{i}),f_{r_{j}}(\alpha_{i})\\}_{i\in\mathcal{A},j=1,\ldots
O})$

where $f_{r_{j}}(\alpha_{i})$ is the share for $r_{j}$ for the $i$’th party,
$f_{x}(\alpha_{i})$ the $i$’th share for $x$, $\mathcal{A}$ consists of the
indices for the parties in the adversary, and $O$ is the total number of
openings. We have that

$\displaystyle\begin{aligned}
&I(x,x-r_{1},\ldots,x-r_{O},\\{f_{x}(\alpha_{i}),f_{r_{j}}(\alpha_{i})\\}_{i\in\mathcal{A},j=1,\ldots
O})\\\
=&h(x-r_{1},\ldots,x-r_{O},\\{f_{x}(\alpha_{i}),f_{r_{j}}(\alpha_{i})\\}_{i\in\mathcal{A},j=1,\ldots
O})\\\
&-h(-r_{1},\ldots,-r_{O},\\{f_{x}(\alpha_{i})|x,f_{r_{j}}(\alpha_{i})\\}_{i\in\mathcal{A},j=1,\ldots
O}),\end{aligned}$

where $h(\cdot)$ is the differential entropy. The last term is by assumption
the entropy of a multivariate normal distributed variable. So we can upper
bound the mutual information by giving an upper bound on the first term. The
distribution with maximal entropy is the normal distribution as well, so by
assuming the first term is normal we maximize the leakage. Hence, we get

$\displaystyle
I(x,x-r_{1},\ldots,x-r_{O},\\{f_{r_{j}}(\alpha_{i}),f_{x}(\alpha_{i})\\}_{i\in\mathcal{A},j=1,\ldots
O})\leq\frac{1}{2}\ln\left(\frac{\det(\mathrm{Cov}(\boldsymbol{\mathbf{v}}))}{\det(\mathrm{Cov}(\boldsymbol{\mathbf{u}}))}\right)$

where

$\displaystyle\begin{aligned}
&\boldsymbol{\mathbf{v}}=(x-r_{1},\ldots,x-r_{O},\\{f_{x}(\alpha_{i}),f_{r_{j}}(\alpha_{i})\\}_{i\in\mathcal{A},j=1,\ldots
O}),\\\
&\boldsymbol{\mathbf{u}}=(-r_{1},\ldots,-r_{O},\\{f_{x}(\alpha_{i})|x,f_{r_{j}}(\alpha_{i})\\}_{i\in\mathcal{A},j=1,\ldots
O})\end{aligned}$

To compute these determinants we write
$C_{x}=\mathrm{Cov}(x-r_{1},\ldots,x-r_{O},\\{f_{x}(\alpha_{i})\\}_{i\in\mathcal{A}})$
and similarly
$C_{x}^{\prime}=\mathrm{Cov}(-r_{1},\ldots,-r_{O},\\{f_{x}(\alpha_{i})|x\\}_{i\in\mathcal{A}})$.
Since the remaining entries in $\boldsymbol{\mathbf{u}}$ and
$\boldsymbol{\mathbf{v}}$ are not depending on $x$, the corresponding entries
in $\mathrm{Cov}(\boldsymbol{\mathbf{v}})$ and
$\mathrm{Cov}(\boldsymbol{\mathbf{u}})$ are identical. Thus, we can write

$\mathrm{Cov}(\boldsymbol{\mathbf{v}})=\begin{bmatrix}C_{x}&C_{x,r}\\\
C_{x,r}^{T}&C_{r}\end{bmatrix}\text{ and
}\mathrm{Cov}(\boldsymbol{\mathbf{u}})=\begin{bmatrix}C_{x}^{\prime}&C_{x,r}\\\
C_{x,r}^{T}&C_{r}\end{bmatrix},$

Remark, that
$\frac{\det(\mathrm{Cov}(\boldsymbol{\mathbf{v}}))}{\det(\mathrm{Cov}(\boldsymbol{\mathbf{u}}))}=\det(\mathrm{Cov}(\boldsymbol{\mathbf{v}})\mathrm{Cov}(\boldsymbol{\mathbf{u}})^{-1})$,
where the matrix inside the determinant equals

$\displaystyle\mathrm{Cov}(\boldsymbol{\mathbf{v}})\mathrm{Cov}(\boldsymbol{\mathbf{u}})^{-1}=\begin{bmatrix}(C_{x}-C_{x,r}^{T}C_{r}^{-1}C_{x,r})(C_{x}^{\prime}-C_{x,r}^{T}C_{r}^{-1}C_{x,r})^{-1}&E\\\
0&I\end{bmatrix}$

for some matrix $E$. Hence,

$\displaystyle\begin{aligned}
\frac{\det(\mathrm{Cov}(\boldsymbol{\mathbf{v}}))}{\det(\mathrm{Cov}(\boldsymbol{\mathbf{u}}))}=\frac{\det((C_{x}-C_{x,r}^{T}C_{r}^{-1}C_{x,r})}{\det(C_{x}^{\prime}-C_{x,r}^{T}C_{r}^{-1}C_{x,r})}.\end{aligned}$
(9)

One can regard $C_{r}$ as a diagonal matrix with block matrix
$C_{r_{j}}=\mathrm{Cov}({f_{r_{j}}(\alpha_{i})}_{i\in\mathcal{A}})$ on its
$j$’th diagonal entry since shares for $r_{j}$ are independent on shares for
$r_{k}$ when $j\neq k$. We remark that $C_{r_{j}}=C_{r_{k}}$ for all $j$ and
$k$. Furthermore, since $f_{r_{j}}(\alpha_{i})$ is independent of
$f_{x}(\alpha_{i})$, $C_{x,r}$ has $t=|\mathcal{A}|$ zero rows at the end.
Hence, $C_{x,r}^{T}C_{r}^{-1}C_{x,r}$ is a $(O+t)\times(O+t)$ diagonal matrix
with the last $t$ diagonal entries 0. The other entries are all identical and
equal to
$\gamma=L_{0}(\boldsymbol{\mathbf{\alpha}})^{T}C_{r_{j}}^{-1}L_{0}(\boldsymbol{\mathbf{\alpha}})$,
where
$L_{0}(\boldsymbol{\mathbf{\alpha}})=(L_{0}(\alpha_{i}))_{i\in\mathcal{A}}$.
Since $C_{x}^{\prime}$ is also a diagonal matrix, with $\sigma_{r}^{2}$ on the
first $O$ diagonal entries and
$\sum_{j=1}^{t}L_{j}(\alpha_{k})^{2}\sigma_{\beta}^{2}$ for $k\in\mathcal{A}$
on the last $t$ diagonal entries, the denominator in (9) is:

$(\sigma_{r}^{2}-\gamma)^{O}\prod_{k\in\mathcal{A}}\sum_{j=1}^{t}L_{j}(\alpha_{k})^{2}\sigma_{\beta}^{2}.$
(10)

For the numerator we compute the following. We write

$C_{x}-C_{x,r}^{T}C_{r}C_{x,r}=\begin{bmatrix}\tilde{C}_{x}-\gamma
I&\tilde{C}_{x,r}\\\ \tilde{C}_{x,r}^{T}&C_{x_{s}}\end{bmatrix},$ (11)

where $\tilde{C}_{x}=\mathrm{Cov}(x-r_{1},\ldots,x-r_{O})$. Note that
$\tilde{C}_{x}-\gamma I$ has $\sigma_{x}^{2}$ on all elements off the
diagonals and the diagonal entries are $\sigma_{x}^{2}+\sigma_{r}^{2}-\gamma$.
We can compute the determinant of the block matrix in the following way

$\displaystyle\det(\begin{bmatrix}\tilde{C}_{x}-\gamma I&\tilde{C}_{x,r}\\\
\tilde{C}_{x,r}^{T}&C_{x_{s}}\end{bmatrix})=\det(C_{x}-\gamma
I)\det(C_{x_{s}}-\tilde{C}_{x,r}^{T}(\tilde{C}_{x}-\gamma
I)^{-1}\tilde{C}_{x,r}).$

Because of the nice structure of $\tilde{C}_{x}-\gamma I$ we have that

$\det(\tilde{C}_{x}-\gamma
I)=(\sigma_{r}^{2}-\gamma)^{O-1}(\sigma_{r}^{2}-\gamma+\sigma_{x}^{2}O)$ (12)

and

$(\tilde{C}_{x,r}^{T}(\tilde{C}_{x}-\gamma
I)^{-1}\tilde{C}_{x,r})_{ij}=\frac{OL_{0}(\alpha_{i^{\prime}})L_{0}(\alpha_{j^{\prime}})\sigma_{x}^{4}}{\sigma_{r}^{2}-\gamma+O\sigma_{x}^{2}},$
(13)

where $i^{\prime}$ and $j^{\prime}$ is the $i$’th and $j$’th element in
$\mathcal{A}$. Using the same notation below, we furthermore have that

$(C_{x_{s}})_{ij}=\begin{cases}L_{0}(\alpha_{i^{\prime}})^{2}\sigma_{x}^{2}+\sum_{j=1}^{t}L_{j}(\alpha_{i^{\prime}})^{2}\sigma_{\beta}^{2}&\text{
if }i=j\\\
L_{0}(\alpha_{i^{\prime}})L_{0}(\alpha_{j^{\prime}})\sigma_{x}^{2}&\text{ if
}i\neq j\end{cases}$ (14)

Hence, we have a closed form formula for the matrix in the second determinant
so all we need to compute is the determinant of this matrix. We remark that
this is a $t\times t$ matrix, which is a very small matrix compared to
$\mathrm{Cov}(\boldsymbol{\mathbf{v}})$ and
$\mathrm{Cov}(\boldsymbol{\mathbf{u}})$ which are $(O(t+1)+t)\times(O(t+1)+t)$
matrices. To sum up, we have

$\displaystyle\begin{aligned}
&I(x;\mathrm{View})\leq\frac{1}{2}\ln\left(\frac{(\sigma_{r}^{2}-\gamma+\sigma_{x}^{2}O)\det(C_{x_{s}}-B)}{(\sigma_{r}^{2}-\gamma)\prod_{k\in\mathcal{A}}\sum_{j=1}^{t}L_{j}(\alpha_{k})^{2}\sigma_{\beta}^{2}}\right),\end{aligned}$
(15)

where $B=\tilde{C}_{x,r}^{T}(\tilde{C}_{x}-\gamma I)^{-1}\tilde{C}_{x,r}$, and
formulas for $B$ and $C_{x_{s}}$ can be found in (13) and (14).

##  6 Experiments

###  6.1 Boston data set

In our experiments, we used Boston house price data set, a copy of UCI ML
housing data set, that is contained in sklearn library Pedregosa et al.
(2011); Dua and Graff (2017). This data set contains 506 data instances with
13 feature targeting the median value of the prices of the homes in $1000’s.
Before we applied our models to this data, we normalized it between $0$ and
$1$. The reason we choose this data set is that it is suitable for regression
problems.

###  6.2 Experimental setup

In our experiments, we used the mean square error (MSE) metric to evaluate our
regression method. To make our experiments trustworthy, we held 10 differently
evaluations for each parameter combination. The data set is divided into train
set and test set. 80% of the data set is preserved for training while the rest
of it is used for testing. We shuffle the data set for each 10 evaluations. We
also divide the training test into $n$ subsets whenever we use secure
computations for privacy preserving algorithms as mentioned in 2.1. Mean MSE
results are reported across 10 different evaluations along with the
corresponding standard deviations.

###  6.3 Results

In our results, we evaluated four different matrix inverse calculation for our
regression method which are Gaussian Elimination with and without secure
computation, Secure Inverse Method for matrix inversion, and regular inverse
calculation (without secure computation). We used linear Support Vector
Regression (SVR) Chang and Lin (2011), which is also implemented using
Pedregosa et al. (2011), as a benchmark algorithm for comparison. The reason
we used SVR is to have a robust linear regression method to compare with. We
tune the $C$ parameter of SVR from the set $\\{0.01,0.1,1,10,100\\}$ using
grid search. In Table 1, we report the mean square error (MSE) for each
algorithm using different $\lambda$ values from the set
$\\{0.01,0.1,1,10,100,1000\\}$.

$\lambda$ | 0.01 | 0.1 | 1 | 10 | 100 | 1000
---|---|---|---|---|---|---
| Secure Gaussian
---
Elimination ($n=3,t=2$)
0.17014 $\pm$ 0.02349 | 0.08442 $\pm$ 0.01782 | 0.03167 $\pm$ 0.00817 | 0.01736 $\pm$ 0.00384 | 0.01555 $\pm$ 0.00238 | 0.01614 $\pm$ 0.00223
| Secure Gaussian
---
Elimination ($n=5,t=3$)
0.16619 $\pm$ 0.02727 | 0.08433 $\pm$ 0.01783 | 0.03168 $\pm$ 0.00819 | 0.01736 $\pm$ 0.00384 | 0.01555 $\pm$ 0.00238 | 0.01614 $\pm$ 0.00223
| Secure Gaussian
---
Elimination ($n=7,t=5$)
0.15644 $\pm$ 0.04219 | 0.09486 $\pm$ 0.04157 | 0.03153 $\pm$ 0.00833 | 0.01738 $\pm$ 0.00383 | 0.01555 $\pm$ 0.00238 | 0.01721 $\pm$ 0.00350
| Insecure Gaussian
---
Elimination
0.17014 $\pm$ 0.02350 | 0.08442 $\pm$ 0.01782 | 0.03167 $\pm$ 0.00817 | 0.01736 $\pm$ 0.00384 | 0.01555 $\pm$ 0.00238 | 0.01614 $\pm$ 0.00223
| Secure Inverse Method
---
($n=3,t=2$)
0.17059 $\pm$ 0.02353 | 0.09418 $\pm$ 0.01873 | 0.03676 $\pm$ 0.00979 | 0.01785 $\pm$ 0.00476 | 0.01220 $\pm$ 0.00304 | 0.01194 $\pm$ 0.00285
| Secure Inverse Method
---
($n=5,t=3$)
0.17058 $\pm$ 0.02352 | 0.09419 $\pm$ 0.01871 | 0.03675 $\pm$ 0.00979 | 0.01860 $\pm$ 0.00514 | 0.01220 $\pm$ 0.00304 | 0.01194 $\pm$ 0.00285
| Secure Inverse Method
---
($n=7,t=5$)
0.17159 $\pm$ 0.03104 | 0.09423 $\pm$ 0.01871 | 0.03988 $\pm$ 0.01454 | 0.01784 $\pm$ 0.00477 | 0.01226 $\pm$ 0.00300 | 0.01194 $\pm$ 0.00285
Insecure Inverse Method | 0.17059 $\pm$ 0.02352 | 0.09418 $\pm$ 0.01873 | 0.03676 $\pm$ 0.00979 | 0.01785 $\pm$ 0.00476 | 0.01220 $\pm$ 0.00304 | 0.01194 $\pm$ 0.00285
SVR | 0.01183 $\pm$ 0.00322

Table 1: MSE results for different $\lambda$ with prior $\Sigma_{{w}}=I$ and
$\boldsymbol{\mathbf{\mu}}_{{w}}=\boldsymbol{\mathbf{0}}$. We use security
parameters $\sigma_{r}=10^{4}$ and $\sigma_{\beta}=10^{5}$

The results in Table 1 show that our regression model with the Secure Inverse
Method is very close to SVR’s performance for the $\lambda=1000$ and it is
identical with the Insecure Inverse Method. There is a slight deviation
(around 0.005) when we apply the Gaussian Elimination when compared with SVR.
Another observation is that as we increase the $\lambda$, our model improves
in terms of reducing the MSE. We can interpret this as we rely on data more,
our model operates better which might be due to the prior is chosen
arbitrarily. We experience an issue that increase in $t$ and $n$ may produce
tiny deviations in MSE score for both Inverse method and Gaussian Elimination
method. For example, when we used secure Gaussian Elimination with $n=7,t=5$,
data becomes more unstable for our model. Increase in $\lambda$ may also cause
deviations in error metric.

$\lambda$ | 0.01 | 0.1 | 1 | 10 | 100 | 1000 |
---|---|---|---|---|---|---|---
| Secure Gaussian
---
Elimination ($\sigma_{r}^{2}=10^{4},\sigma_{\beta}^{2}=10^{5}$)
0.16619 $\pm$ 0.02727 | 0.08433 $\pm$ 0.01783 | 0.03168 $\pm$ 0.00819 | 0.01736 $\pm$ 0.00384 | 0.01555 $\pm$ 0.00238 | 0.01614 $\pm$ 0.00223 |
| Secure Inverse Method
---
($\sigma_{r}^{2}=10^{4},\sigma_{\beta}^{2}=10^{5}$)
0.17058 $\pm$ 0.02352 | 0.09419 $\pm$ 0.01871 | 0.03675 $\pm$ 0.00979 | 0.01860 $\pm$ 0.00514 | 0.01220 $\pm$ 0.00304 | 0.01194 $\pm$ 0.00285 |
| Secure Gaussian
---
Elimination ($\sigma_{r}^{2}=10^{5},\sigma_{\beta}^{2}=10^{6}$)
0.16004 $\pm$ 0.04418 | 0.08046 $\pm$ 0.02163 | 0.03383 $\pm$ 0.01056 | 0.01789 $\pm$ 0.00423 | 0.02361 $\pm$ 0.02377 | 0.01616 $\pm$ 0.00222 |
| Secure Inverse Method
---
($\sigma_{r}^{2}=10^{5},\sigma_{\beta}^{2}=10^{6}$)
0.16976 $\pm$ 0.02741 | 0.10665 $\pm$ 0.04403 | 0.05566 $\pm$ 0.05871 | 0.01799 $\pm$ 0.00478 | 0.01266 $\pm$ 0.00292 | 0.01199$\pm$ 0.00279 |
| Secure Gaussian
---
Elimination ($\sigma_{r}^{2}=10^{6},\sigma_{\beta}^{2}=10^{7}$)
5451.53691 $\pm$ 16351.67036 | 2.51021 $\pm$ 6.07267 | 60.85163 $\pm$ 168.82382 | 0.06829 $\pm$ 0.14313 | 0.02403 $\pm$ 0.02214 | 0.06570 $\pm$ 0.09102 |
| Secure Inverse Method
---
($\sigma_{r}^{2}=10^{6},\sigma_{\beta}^{2}=10^{7}$)
2.02348 $\pm$ 3.35909 | 2.32574 $\pm$ 5.90800 | 14.08060 $\pm$ 41.99243 | 0.19091 $\pm$ 0.36676 | 0.19987 $\pm$ 0.33934 | 0.72764 $\pm$ 1.30291 |

Table 2: MSE results for different $\sigma_{r}^{2}$ and $\sigma_{\beta}^{2}$
values when $n=5$ and $t=3$. The second and the third rows are from Table 1

In Table 2, we investigate the effect of the security parameters,
$\sigma_{r}^{2}$ and $\sigma_{\beta}^{2}$ to the accuracy-privacy trade-off to
the error metric. We observe that as we increase the $\sigma_{r}^{2}$ and
$\sigma_{\beta}^{2}$, our secure computations become more unstable and result
in huge deviations.

###  6.4 Privacy analysis for computing on the Boston data set

We exemplify the privacy leakage bound from (15) with the computations we
carry out on the Boston data set in the case for $n=5$ and $t=3$. In our
experiments the $\alpha_{i}$’s are chosen uniformly at random in the interval
$[0,1)$ so for this analysis we use $\alpha_{i}=0.2\cdot i-0.1$ for
$i=1,\ldots,5$ and $\alpha_{0}=0$. We use $\alpha_{0}$ to $\alpha_{3}$ to
construct $L_{j}$ and consider the leakage to the adversary
$\mathcal{A}=\\{3,4,5\\}$. We remark that this is the worst-case adversary
since it has the maximum number of allowed corruptions and it includes all the
indices not used for constructing the $L_{j}$’s, which corresponds to the
shares which might leak some information. For the inverse method the total
number of openings in our experiments are $O=2d^{3}+3d^{2}+d=6090$ since
$d=13+1$. Similarly, for the Gaussian method
$O=\frac{2}{3}d^{3}+\frac{7}{2}d^{2}+\frac{11}{6}d=2541$ with this $d$. We
need to argue about the distribution of $x$ which we try to hide. Since $x$ is
an entry in $X_{i}$, $x$ is a sum of $n_{i}$ elements where the terms are
products of two numbers between $0$ and $1$. We assume, that these two numbers
are uniformly distributed in this interval giving us that they have variance
$\frac{1}{12}$. The variance of the product would then be $\frac{7}{144}$ and
since we sum $n_{i}\approx 80$ of these terms to obtain $x$ the variance
$\sigma_{x}^{2}\approx 80\frac{7}{144}\approx 4$. The leakage bounds are
presented in Table 3 for the same $\sigma_{r}^{2}$ and $\sigma_{\beta}^{2}$ as
in Table 2.

$(\sigma_{r}^{2},\sigma_{\beta}^{2})=$ | $(10^{4},10^{5})$ | $(10^{5},10^{6})$ | $(10^{6},10^{7})$
---|---|---|---
Inverse method | $0.6243$ | $0.1110$ | $0.0123$
Gaussian method | $0.3558$ | $0.0493$ | $0.005$
Table 3: Upper bounds from (15) on privacy leakage in nats

To interpret what the numbers in Table 3 says about the leakage we mention
that the mutual information between two continuous random variables is a
number between $0$, meaning that the variables are independent, and $\infty$,
when one of the variables determines the other. For comparison we also state
that if $X$ and $R$ are independent and normal distributed with variances
$\sigma_{x}^{2}$ and $\sigma_{r}^{2}$ respectively, then
$I(X;X-R)=\frac{1}{2}\ln(1+\frac{\sigma_{x}^{2}}{\sigma_{r}^{2}})$. So for
instance if we obfuscate an $X$ with variance $1$ by an $R$ with variance $1$
the leakage about $X$ is $0.3466$ nats.

##  7 Conclusion

We have described two methods to securely obtain a linear model based on a
number of data sets. We have illustrated that carrying out the computations
using MPC techniques based on real number secret sharing we can obtain the
model with only a small amount of leakage which is upper bounded by (15). The
analysis indicates that there might be more leakage in the inverse method
compared to the Gaussian method due to the bigger amount of openings we needed
to carry out in this method. That we need to open more values in the inverse
method also implies more communication even though the number of openings is
$\mathcal{O}(d^{3})$ in both methods. However, our experiments indicate that
the MSE are lower in the inverse method than in the Gaussian method as shown
in Table 1. We also see in this table that there are no significant difference
in performance by using the secure versions compared to the insecure versions
when the variance of the security parameters are not too high. However, it
seems like the methods become unstable when $\sigma_{r}^{2}$ and
$\sigma_{\beta}^{2}$ are increased.

## References

  * Aliasgari et al. (2013) Aliasgari, M.; Blanton, M.; Zhang, Y.; and Steele, A. 2013.  Secure Computation on Floating Point Numbers.  In _NDSS_.
  * Alquier, Ridgway, and Chopin (2016) Alquier, P.; Ridgway, J.; and Chopin, N. 2016.  On the properties of variational approximations of Gibbs posteriors.  _Journal of Machine Learning Research_ , 17(236): 1–41.
  * Catoni (2008) Catoni, O. 2008.  Pac-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning.  _IMS Lecture Notes Monograph Series_.
  * Catrina and Dragulin (2009) Catrina, O.; and Dragulin, C. 2009.  Multiparty Computation of Fixed-Point Multiplication and Reciprocal.  In _2009 20th International Workshop on Database and Expert Systems Application_.
  * Catrina and Saxena (2010) Catrina, O.; and Saxena, A. 2010.  Secure Computation with Fixed-Point Numbers.  In _Financial Cryptography and Data Security_ , 35–50.  ISBN 978-3-642-14576-6.
  * Chang and Lin (2011) Chang, C.-C.; and Lin, C.-J. 2011.  LIBSVM: a library for support vector machines.  _ACM transactions on intelligent systems and technology (TIST)_ , 2(3): 1–27.
  * Cramer, Damgård, and Nielsen (2015) Cramer, R.; Damgård, I. B.; and Nielsen, J. B. 2015.  _Secure Multiparty Computation and Secret Sharing_.  Cambridge University Press.
  * Dimitrov et al. (2016) Dimitrov, V.; Kerik, L.; Krips, T.; Randmets, J.; and Willemson, J. 2016.  Alternative Implementations of Secure Real Numbers.  In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , CCS ’16. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450341394.
  * Dua and Graff (2017) Dua, D.; and Graff, C. 2017.  UCI Machine Learning Repository.
  * Germain et al. (2016) Germain, P.; Bach, F.; Lacoste, A.; and Lacoste-Julien, S. 2016.  PAC-Bayesian Theory Meets Bayesian Inference.  In _Neural Information Processing Systems (NIPS 2016)_ , Proceedings of the Neural Information Processing Systems Conference. Barcelone, Spain.
  * Langford and Seeger (2001) Langford, J.; and Seeger, M. 2001.  Bounds for Averaging Classifiers.
  * McAllester (2003) McAllester, D. 2003.  Simplified PAC-Bayesian Margin Bounds.  In _Learning Theory and Kernel Machines_ , 203–215. Berlin, Heidelberg: Springer Berlin Heidelberg.
  * Pedregosa et al. (2011) Pedregosa, F.; Varoquaux, G.; Gramfort, A.; Michel, V.; Thirion, B.; Grisel, O.; Blondel, M.; Prettenhofer, P.; Weiss, R.; Dubourg, V.; Vanderplas, J.; Passos, A.; Cournapeau, D.; Brucher, M.; Perrot, M.; and Duchesnay, E. 2011.  Scikit-learn: Machine Learning in Python.  _Journal of Machine Learning Research_ , 12: 2825–2830.
  * Tjell and Wisniewski (2021) Tjell, K.; and Wisniewski, R. 2021.  Privacy in Distributed Computations based on Real Number Secret Sharing.  arXiv:2107.00911.