Back up an information as $n$ pieces and require exactly $n-1$ to recover it

Question

Let $X\in \Bbb F_2^p$ be some information.

How do I create $Y_1,\dots,Y_n \in \Bbb F_2^q$ so that having less than $n-1$ of the $Y_i$s gives you no information on $X$ but having $n-1$ of them allows you to recover $X$?

---

I first though of error correcting codes, but I don't think those would be able to ensure that having less than $n-1$ of the $Y_i$s would give no information.

My second thought was to use some kind of one time pad. For a given $r\in\{1,\dots,n\}$ (which is the index of the $Y_i$ we won't use to recover $X$), you could let $Y_r=0$, let $n-2$ of the remaining $Y_i$s be random elements of $\Bbb F_2^p$ and let the last $Y_i$ be the sum (meaning XOR) of the other ones and $X$. Then you could concatenate that for every $r\in\{1,\dots,n\}$. In other words, you use $n-2$ of the $Y_i$s to create a one time pad and use it to encrypt $X$ in the last $Y_i$. But that seems a bit brutal to me. You would need $q=np$.

I was wondering of there was a way to do it so that $q=\mathcal O(p)$ (meaning it doesn't depend on $n$).

The first thing that comes to mind is to make the $Y_r$ with three elements: its index, one random element of $\Bbb F_2^p$ and the sum of $X$ and the $n-1$ $Y_i$s that after this one including it (so $Y_r,\dots,Y_{r+(n-2)}$, where you reduce the indices modulo $p$ in the obvious way). This way, when you have $n-1$ of the $Y_i$s, you can find which index $r$ which is missing and then sum the third part of $Y_r$ with the second part of $Y_r,\dots,Y_{r+(n-2)}$ and recover $X$. That would be $\mathcal O(p\log n)$ (because of the index) which is acceptable. But I feel like you could recover part of the message with less than $n-1$ of the $Y_i$s because you kind of used the one time pad several times.

---

Edit: I'll use it in https://github.com/xavierm02/combine-keys

Answer 1

What you describe is known as Threshold-secret-sharing, for which a good candidate is the threshold version of shamir-secret-sharing.

In particular, for your use case I would recommend implementing an "n-1 out of n threshold sharing scheme".

---

Shamir Secret Sharing $(n,k)$-threshold scheme.

Shamir's $k$ of $n$ threshold sharing scheme is based on the observation that a $k-1$ polynomial over a field is determined by $k$ points, and yet cannot be determined with fewer than $k$ points. If we let $k=n$ then this reduces to Shamir's original sharing scheme.

1. Choose $q$ such that $\mathbb F_q$ be a finite field (the size of $q$ will specify how secure the scheme is).
2. Sample $a_1,\dots,a_{k-1}$ uniformly from $\mathbb F_q$.
3. Let $a_0=s$ be the secret you wish to share.
4. Let $f(x)=\sum_{i=0}^{k-1} a_i x^i$.
5. For each of the $n$ people, let share $i$ be the pair $(i,f(i))$.

To decrypt, we use polynomial interpolation to reconstruct the polynomial $f$, which requires at least $k$ shares, and then simply read off the coefficient $a_0$.

Security: No information about the $a_0$ coefficient is leaked until the polynomial is completely recovered, the scheme is informationally secure. As such, the size of the finite field will be the same as the security margin presented, because the best attack will be to directly guess the secret. nb: This assumes that an adversary must treat the secret as if it were uniformly sampled from all possible field elements - obviously if your secret $s\in\{0,1\}$ your security is bounded by that!