1
$\begingroup$

I have been unable to find any proofs (for my own reference) that demonstrate that Shamir's secret sharing scheme does (or does not) satisfy the definition of $\textbf{differential privacy}$ as provided below:

$\mathbb{D}$ denotes the set of possible databases. $\textbf{Q}$ denotes the set of possible queries on the databases. Let $\textbf{M}$ denote a mechanism such that: \begin{equation} \label{mechanism_definition} \textbf{M}: \mathbb{D} \times \textbf{Q} \mapsto \mathbb{R}^p \end{equation}

A mechanism $\textbf{M}$ as defined above is said to satisfy differential privacy if: \begin{equation} \label{differential_privacy_equation} \frac{\mathbb{P}[\textbf{M}(D,q) \in S]}{\mathbb{P}[\textbf{M}(D',q) \in S]} = 1 \end{equation}

$\forall$ D $\in$ $\mathbb{D}$ and $\forall$ q $\in$ $\textbf{Q}$.

$\forall$ S $\subset$ Range ($\textbf{M}$).

This is the reference I used for the definition provided.

I would appreciate some guidance in this regard.

$\endgroup$
  • $\begingroup$ Can you cast shamir secret sharing into this framework as an exercise? $\endgroup$ – kodlu Jan 21 at 22:27
  • $\begingroup$ The definition you have given for differential privacy is with privacy parameter $\varepsilon=0$. No interesting algorithms satisfy this definition. $\endgroup$ – Thomas Jan 21 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.