Score:2

Secure multiparty scheme in key (splitting) distribution among the players

ua flag

Suppose that we have a game with $I$ players and each of them has a private secret say $e_i$. Every player wants to share her secret with the rest of the players but in such a way that she will not be cheated. We have the following formulation

$$p_i:E_i\times Y_i\to X_i$$ where $|Y_i|\geq|E_i|$ and $p_i(\cdot,y_i)$ is bijective so that every pair $(x_i,y_i)$ is associated with exactly one $e_i$. More precisely, $p_i$ is a cipher mapping, $x_i$ is a code and $y_i$ is a private key uniformly distributed over $Y_i$. Let us further assume that $z_i(e_i)$ is a permutation of the information $e_i$. With the help of the following lemma we have

$\textbf{Lemma:}$ If $z_i$ is a random variable with support on $\{1,2,\dots,n_i\}$, and $y_i$ is uniformly distributed over $\{1,2,\dots,n_i\}$ indepedent of $z_i$, then the random variable $x_i$ defined as $x_i=z_i\ominus_{n_i}y_i$ (where $z_i\ominus_{n_i}y_i=z_i-y_i(mod{n}_i)$) is also uniformly distributed over $\{1,2,\dots,n_i\}$.

Could I use a secret sharing scheme based on this encryption-decryption scheme, that could be multiparty in the sense that player $i$ could somehow share the key $y_i$ splitting it in parts and how could I formulate this? Suppose that we want to share the key $y_i$ in a way such that after all the players will communicate each other will obtain $y_i$. Namely, player $i$ will only say a part of the key $y_i$, for example, player $j=-i$ learns $\tau_{ij}=a_{ij}y_j$ and if for any $j\in I-\{i\}$ we take the sum of $\tau_{ij}$ we learn $y_i=\sum_{j\in I-\{i\}}\tau_{ij}$ (in other words $x_i=z_i\ominus_{n_i}\sum_{j\in I-\{i\}}\tau_{ij}$).

How could I do this? Should I define $p_i$ differently and what should be the conditions to find a set that is copy of $Y_i$ such that $\tau_{ij}=a_{ij}y_j$, where $j=-i$?

$\textbf{The goal is the following:}$ There are $I$ players and each of them has a secret say $e_i$. Instead of sharing $e_i$, every player uses a cipher which is defined as $p_i$ and $x_i$ is the code that is generated from the encryption scheme. Also $y_i$ denotes the key. Let as assume that $z_i(e_i)$ is a permutation of $e_i$ such that $z_i(e_i)=x_i\oplus_{n_i}y_i$. I want each player when she shares her secret to split her key $y_i$ to all the other players $j∈I−{i}$ so as to prevent from cheating, in such a way that every player will take $x_i$, but only a part of $y_i$. In essence, $y_i$ is splitted in $|I|−1$ parts, with the other players taking each of them one part. Hence, they will need to further communicate to obtain $y_i$ and hence learn the information $z_i(e_i)$

Sam Jaques avatar
us flag
Is the $j$ in the last half of your last sentence the same as $j=-i$ or a different $j$ (could you use a different letter in that case)? Can you explain more clearly what you are trying to accomplish that standard secret-sharing schemes (e.g., Shamir secret-sharing) do not accomplish?
Hunger Learn avatar
ua flag
@SamJaques yes, $j=-i$ in every part of the text above. However, whatever assumption my definition needs to define the secret sharing scheme you are very welcome to mention in. I wrote this so as anyone could help me, because cryptography is not my field and of course I would appreciate it to tell me if I have to make any adjustments to the text that I wrote above.
Hunger Learn avatar
ua flag
In other words the meaning of $\tau_{i,j}$ is that player $i$ sends to every other player $j$, $a_{j}$ shares of the secret $y_i$, right?
Hunger Learn avatar
ua flag
well, I think that this notation $a_{i,j}$ is the standard way to say that player $i$ shares with every other player $j$ only a part of her secret $y_i$ and this is written $a_{ij}s_j=\tau_{ij}$. But my question is, if this is the right notation, If I need to make any further assumptions about $a_{ij}$ and $y_j$ and how are they related? Furthermore, could we modify the definition of $p_i:E_i\times Y_i\to X_i$ since we use the scheme of secret sharing after $y_i$ is known to player $i$? I think the latter is not necessary...but in case it is....
fgrieu avatar
ng flag
I get lost when the $e_i$ become "events", and $z_i(e_i)$ become "information about" such events; I fail to get a mental picture of these $z_i$ (are they functions or elements?), and why $z_i$ and $e_i$ get the same index. Also the overall goal is unclear to me: player $i$ wants to share their secret $y_i$? Into what (edit: that is, what variables in the Q form the information that together allows reconstructing $y_i$, or is it the transformation $y_i$ enables) / with who?
Hunger Learn avatar
ua flag
@fgrieu taking into account your comments I re-edited again my question. Take a look and tell me if it is clear, or I need to make further clarifications. say that $e_i$ is the private information of player $i$ and $z_i(e_i)$ is a permutation of $e_i$. By saying ``player i wants to share their secret yi? Into what or with who" is neither clear to me as a question...
Hunger Learn avatar
ua flag
@SamJaques take a look in my question again. I edit it again.
Sam Jaques avatar
us flag
I'm still not clear on the intention. I think the issue is that the "goals" should be what security properties you want to hold: what players are involved, what data does each player have, what do you want them to compute with that data, and what data does each player want to keep secret? At this level, forget about the cryptography. Once that is settled, then it's easier to decide what kind of cryptographic tools you need.
Sam Jaques avatar
us flag
For example, you say that $z_i(e_i)$ is a permutation of $e_i$ - is this a fixed, public permutation, or an encryption of $e_i$ with some secret key? If it's an encryption with a secret key, then I'm not sure why $x_i$ and $y_i$ are necessary, as player $i$ could simply publish $z_i(e_i)$ (unless there is some other reason to keep this value secret). If it's a public permutation, what's the benefit of using $z_i(e_i)$ instead of $e_i$ directly, e.g., why not have $e_i = x_i\oplus y_i$?
Hunger Learn avatar
ua flag
ok, every player has a private information that is $e_i$. He wants to share this information with the rest of the players. Let's suppose that there is a copy of $E_i$ say $L_i$ and z_i is a permutation such that $z_i(e_i)=l_i$ has an equivalent translation from the one space to its copy. Player $i$ then encodes $z_i(e_i)$ following the scheme above s.t. $z_i(e_i)=x_i\oplus y_i$, so players $j=-i$ will only learn $z_i(e_i)$ the translated information instead of the direct information. For example if player $i$ learns $e_i$, then she could send the message $z_i$ that is translated like
Hunger Learn avatar
ua flag
I know the information indexed by $i$ which is informative enough to the other players, but she does not wish to say explicitly that I learned $e_i$.
Hunger Learn avatar
ua flag
The only information that could be considered to be public could be $x_i$
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.