Is this a good way of splitting a private key into a 2 of 3 scheme?

Question

Basically the idea is to split a key into three parts ($key_a, key_b, key_c$) of which any 2 of the 3 parts can be used to recreate the original key

• $key_a$: a random number smaller then our original key
• $key_b$: another number which when added to $key_a$ will result in the original key
• $key_c$: two components:
  • $xor_a$: xor of the original key and $key_a$
  • $xor_b$: xor of the original key and $key_b$

Is this a good way of splitting a private key into a 2 of 3 scheme?

---

Here's a Github gist showing a Python example of what I described above.

Answer 1

The proposed sharing scheme does allow reconstruction of key $K$ from any two of the three shares $K_A$, $K_B$, $K_C=(X_A,X_B)$, because:

• $K=K_A+K_B$ from $K_A$ and $K_B$
• $K=K_A\oplus X_A$ from $K_A$ and $K_C$
• $K=K_B\oplus X_B$ from $K_B$ and $K_C$

Problem is, the scheme leaks information about key $K$: always less than 1 bit worth to participants $A$ and $B$; but over 1 bit to participant $C$, growing up to the whole of $K$ if there is enough redundancy in $K$ (see below). While the proposed sharing scheme might leak acceptably little information about the private exponent of an RSA or ECDSA key, which are close enough to uniformly random, it is not recommendable in general.

---

As an extreme example, if it is shared a key $K$ of a single bit, that is $K\in\{0,1\}$, then:

• if $K=0$ then $K_A=0$, $K_B=0$, $K_C=(X_A,X_B)=(0,0)$
• if $K=1$ then either
  • $K_A=0$, $K_B=1$, $K_C=(X_A,X_B)=(1,0)$
  • $K_A=1$, $K_B=0$, $K_C=(X_A,X_B)=(0,1)$

It follows that $C$ always learns $K=X_A\oplus X_B$, and $A$ or $B$ seeing its $K_i=1$ learns $K$; also, if $K$ is uniform, $A$ and/or $B$ seeing its $K_i=0$ can bet that $K=0$ with better than even odds.

---

For large $K$, $A$ and $B$ learn some information about the order of magnitude of $K$ (less than 1 bit worth on average, regardless of the distribution of $K$).

But $C$ gains more information about $K$. The low-order bit of $X_A\oplus X_B$ is always the low-order bit of $K$, and the high order bit of $X_A\oplus X_B$ tends to match the corresponding bit in $K$ for uniform distribution of $K$.

Worse, redundancy known to exist in $K$ allows $C$ to gain even more information about $K$. For example, if it is known that the representation of $K$ consists entirely of the digits 0 and 1 in some base $2^j$ with $j\ge3$ including hexadecimal or octal, then $C$ can fully reconstruct $M$ by computing $(X_A+X_B)\oplus(2(X_A+X_B))$ and masking to keep the bits that could be set in $K$.

---

A simple scheme that works and leaks no information is to share each bit $k$ of $K$ by assigning a uniformly random integer $x$ in $\{0,1,2\}$ to $A$ ; $x+k\bmod3$ to $B$ ; $x+2k\bmod3$ to $C$. If two parties have the same value assigned, then $k=0$, otherwise $k=1$.

Further, by writing $K$ in base three, thus with $k\in\{0,1,2\}$ , and with the parties knowing who received $x$, $x+k\bmod3$, or $x+2k\bmod3$, the capacity of the scheme is increased and each of the three shares has the same size as $K$.

Of course, the generic method is Shamir's secret sharing, which allows a flexible number of shares and threshold for reconstructing $K$.