2
$\begingroup$

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)$

$\endgroup$
12
  • $\begingroup$ 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? $\endgroup$
    – Sam Jaques
    Jan 3, 2022 at 11:54
  • $\begingroup$ @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. $\endgroup$ Jan 3, 2022 at 12:10
  • 1
    $\begingroup$ 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.... $\endgroup$ Jan 3, 2022 at 12:57
  • 1
    $\begingroup$ @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... $\endgroup$ Jan 4, 2022 at 9:38
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sam Jaques
    Jan 7, 2022 at 9:14

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.