## 3 Results
### Construction of DP-BCD
It is the multiplier of the loss with respect to the unperturbed case, where \(\mathbf{b}=\mathbf{0}\). The probability that two databases \(\mathbf{X}_{1},\mathbf{X}_{2}\) of full rank at a distance \(1\) of each other yield the same output vector \(\mathbf{v}_{out}=\mathbf{v}_{in}-\mathbf{X}_{1}\mathbf{\beta}^{*}_{1}=\mathbf{v}_{in}-\mathbf{X}_{2} \mathbf{\beta}^{*}_{2}\) is, according to (9), given by  
\[\frac{\mathbb{P}[\mathcal{A}_{l}(\mathbf{X}_{1})=\mathbf{v}_{out}]}{ \mathbb{P}[\mathcal{A}_{l}(\mathbf{X}_{2})=\mathbf{v}_{out}]}=\frac{\mathbb{P}[0=\mathbf{ X}_{1}^{T}(\mathbf{v}_{out}-\mathbf{b}_{1})]}{\mathbb{P}[0=\mathbf{X}_{2}^{T}(\mathbf{v}_{ out}-\mathbf{b}_{2})]}=\frac{\mathbb{P}[\mathbf{b}_{1}\in\ker(\mathbf{X}_{1}^{T})+\mathbf{v}_{out}]}{ \mathbb{P}[\mathbf{b}_{2}\in\ker(\mathbf{X}_{2}^{T})+\mathbf{v}_{out}]}\] \[\qquad=\frac{\mathbb{P}[\mathbf{b}_{1}\in\ker(\mathbf{X}_{1}^{T})+\mathbf{v} _{1,\perp_{1}}]}{\mathbb{P}[\mathbf{b}_{2}\in\ker(\mathbf{X}_{2}^{T})+\mathbf{v}_{2,\perp _{2}}]}\] \[\qquad=\frac{\exp[-\frac{\varepsilon}{2\xi^{2}}\|\mathbf{v}_{1,\perp _{1}}\|_{2}^{2}]}{\exp[-\frac{\varepsilon}{2\xi^{2}}\|\mathbf{v}_{2,\perp_{2}}\|_{ 2}^{2}]}\leq\varepsilon^{\varepsilon} \tag{14}\]  
Here, we have decomposed \(\mathbf{v}_{out}=\mathbf{v}_{1,\operatorname{ker}_{1}}+\mathbf{v}_{1,\perp_{1}}=\mathbf{v}_{2,\operatorname{ker}_{2}}+\mathbf{v}_{2,\perp_{2}}\) into parts inside the kernel and perpendicular to it. Note that the decomposition for \(\mathbf{X}_{1}\) is different from that for \(\mathbf{X}_{2}\). For the probabilities, it suffices that  
\[\exp[-\alpha(\mathbf{v}_{\perp}+\sum_{j}\lambda_{j}\mathbf{w}_{j})^{2}]=\exp[-\alpha \mathbf{v}_{\perp}^{2}]\cdot\prod_{j}\exp[-\alpha\lambda_{j}^{2}],\]  
where \(\{w_{j}\}\) is an orthonormal basis for the kernel. Note that the parts inside the kernel can only stem from \(\mathbf{v}_{in}\). Since both matrices are of full rank, their kernels have the same dimensions and selecting a vector out of them is equally likely. For the perpendicular parts, a standard argument can be used. Using (13), the final inequality follows from  
\[\|\mathbf{v}_{i,\perp}\|_{2}^{2}\leq\|\mathbf{v}_{out}\|_{2}^{2}=\|\mathbf{v}_{in}-\mathbf{X}_ {i}\mathbf{\beta}^{*}_{i}\|_{2}^{2}\leq\xi^{2}.\]  
For the revealing phase, a very similar argument works. Instead of the missing labels, it is now the weights that are communicated. The privacy loss for revealing a single \(\mathbf{\beta}^{*}_{(t)}\) is computed by \[\frac{\mathbb{P}[\mathcal{A}_{r}(\mathbf{X}_{1})=\mathbf{\beta}^{*}_{(t)}]}{ \mathbb{P}[\mathcal{A}_{r}(\mathbf{X}_{2})=\mathbf{\beta}^{*}_{(t)}]}=\frac{\mathbb{P}[ 0=\mathbf{X}_{1}^{T}(\mathbf{v}_{in,(t)}-\mathbf{X}_{1}\mathbf{\beta}^{*}_{(t)}-\mathbf{b}_{1,(t)} )]}{\mathbb{P}[0=\mathbf{X}_{2}^{T}(\mathbf{v}_{in,(t)}-\mathbf{X}_{2}\mathbf{\beta}^{*}_{(t)} -\mathbf{b}_{2,(t)})]}\] \[\qquad=\frac{\mathbb{P}[\mathbf{b}_{1,(t)}\in\ker(\mathbf{X}_{1}^{T})+( \mathbf{v}_{in,(t)}-\mathbf{X}_{1}\mathbf{\beta}^{*}_{(t)})_{\perp_{1}}]}{\mathbb{P}[\mathbf{ b}_{2,(t)}\in\ker(\mathbf{X}_{2}^{T})+(\mathbf{v}_{in,(t)}-\mathbf{X}_{2}\mathbf{\beta}^{*}_{(t)})_{ \perp_{2}}]}\] \[\qquad\leq\frac{\exp[-\frac{\epsilon}{2\epsilon_{(t)}^{2}}\|(\bm {v}_{in,(t)}-\mathbf{X}_{1}\mathbf{\beta}^{*}_{(t)})_{\perp_{1}}\|_{2}^{2}]}{\exp[- \frac{\epsilon}{2\epsilon_{(t)}^{2}}\|(\mathbf{v}_{in,(t)}-\mathbf{X}_{2}\mathbf{\beta}^{* }_{(t)})_{\perp_{2}}\|_{2}^{2}]}\leq\epsilon^{\epsilon}. \tag{15}\]  
From simple composition, Lemma 1, it follows that revealing the weights \(\sum_{t=1}^{T}\mathbf{\beta}^{*}_{(t)}\) consumes at most a privacy budget of \(T\epsilon\). To demand that observations should generate a full rank matrix is a minor demand. If it were not the case, a certain attribute could be predicted perfectly by the other attributes. Hence, it could be removed from the database to generate a full rank matrix again. Furthermore, it is not necessary for the proof to work with full rank matrices. They should only be of equal rank. The complete 2-party algorithm DP-BCD is shown in Algorithm 2.