Score:0

Secret sharing scheme combined with probability theory results?

ua flag

As a sequel of my previous post I am writing a new one with respect to the secret sharing scheme. I will only cite here the answer because I want to make a question on it.

$\textbf{Answer:}$ To be honest, I'm not 100% familiar with the original presentation in RB89, but they introduced several techniques that have been used in multiple subsequent papers, and today there is a sort of simplified version (in modern terms) of the robust secret-sharing scheme there. For example, a high level description can be found in page 3 here.

In a nutshell, the goal is to take a secret $s\in\mathbb{F}$ and distribute it among $n$ parties $P_1,\ldots,P_n$ so that, at later point in time, the parties can reconstruct this secret to each other, while guaranteeing that even if some $t$ corrupt parties with $t<n/2$ send incorrect values, the honest (i.e. non-corrupted) parties can still obtain the underlying secret. This is achieved as follows:

  • The dealer uses traditional Shamir secret-sharing to obtain shares of the secret $(s_1,\ldots,s_n)$. If $t<n/2$, then these shares provide error detection, meaning that a party getting these shares, where $t$ of them might be modified due to adversarial behavior, can find out whether or not the secret has been tampered with, but, in case there are errors, the given party cannot "fix them" to reconstruct the correct secret. This is insufficient for robust secret-sharing.

  • The dealer samples uniformly random pairs $(\alpha_{ij},\beta_{ij})\in\mathbb{F}^2$ and computes $\tau_{ji} = \alpha_{ij}\cdot s_j + \beta_{ij}$ for every pair $i,j\in[n]$ (here $[n] = \{1,\ldots,n\}$). As we will see, the goal of this extra data is to ensure that a receiving party can not only detect if the shares were tampered with, but actually identify the incorrect ones, hence filtering out the ones that are correct, which leads to the right secret being reconstructed.

  • The dealer sends $\sigma_i = (s_i, \{(\alpha_{ij},\beta_{ij})\}_{j\in[n]}, \{\tau_{ij}\}_{j\in[n]})$ to each party $P_i$. In words: every $P_i$ gets a share $s_i$ plus a pair of keys $(\alpha_{ij},\beta_{ij})$ for each other party. In addition, $P_i$ gets an "authenticated version of $s_i$" using the keys of each other party.

Let's say that a party $P_j$ is supposed to learn the secret. To this end, the parties $P_i$ for $i\in[n]\setminus\{j\}$ send $P_j$ their values $(s_i',\tau_{ij}')$ (if $P_i$ is honest, then $s_i' = s_i$ and $\tau_{ij}' = \tau_{ij}$, but a corrupt party may send incorrect values), and $P_j$ checks, using his/her own key $(\alpha_{ji},\beta_{ji})$, that $\tau_{ij}' = \alpha_{ji}\cdot s_i' + \beta_{ji}$.

As an exercise, one can check that if $s_i'\neq s_i$, then the probability that this equation holds is at most $1/|\mathbb{F}|$ (this makes use of the fact that $P_i$ does not know the key $(\alpha_{ji}, \beta_{ji})$, which is random), so, as long as the field is large enough, $P_j$ will be able to filter out the wrong shares, and hence reconstruct the secret from the remaining correct ones.


Does this somehow help you with the concrete questions you had? Feel free to drop in any comment if you need clarification in certain direction.

$\textbf{Question:}$ Usually, many problems define $s$ as a uniformly distributed random variable over a field $\mathbb{F}$. The dealer, based on the answer distribute this $s$ among $n$ parties and every party $i$ learns $s_i$. Player $i$ learns $\sigma_i = (s_i, \{(\alpha_{ij},\beta_{ij})\}_{j\in[n]}, \{\tau_{ij}\}_{j\in[n]})$, where $(\alpha_{ij},\beta_{ij})$ denote a pair of keys for each other party $j\neq i$. Furthermore, $(\alpha_{ij},\beta_{ij})\in\mathbb{F}^2$ are uniformly random pairs and computes $\tau_{ji} = \alpha_{ij}\cdot s_j + \beta_{ij}$. My question is how can we ensure, that for every uniform random variable $s_i$ over $\mathbb{F}$, we can find a pair of other random variables $(\alpha_{ij},\beta_{ij})\in\mathbb{F}^2$ such that $s_j=(\tau_{ij}-\beta_{ij})\cdot\alpha_{ij}^{-1}$? Namely, is there some result from probability theory that ensures we can write every random variable $s_i$ to an equivalent formulation as a combination of other random variables if $+$ and $\cdot$ are defined over $\mathbb{F}$?

Hunger Learn avatar
ua flag
@Daniel with respect to my previous question for secure multiparty computation and taking into account your answer here https://crypto.stackexchange.com/questions/96637/can-anybody-explain-the-proof-of-rabin-and-ben-or-of-secure-multiparty-computati/96649#96649 I have some technical questions on the way that the encryption scheme can be defined.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.