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
sss_split key.in share1 share2 share3 [share4 ...]
, andsss_combine key.out share1 share2 [share3 ...]
. Here: github.com/CarloWood/sss $\endgroup$ – Carlo Wood May 22 '20 at 5:26