This is cryptocurrency related. Have a 24-word password.

We have 5 people. We want it such that no one person knows all 24 words, but any 3 of 5 people together can form the words.

What is the most efficient way to make this work?

Spitballing off the top of my head:

Person A: knows 1-11
Person B: knows 13-23
Person C: knows 1-6 and 13-18
Person D: knows 7-12 and 19-24
Person E: knows 2-6, 8-12

that obviously doesn't work. just trying to find out how to make this work. thanks.

Also a solution for 4 people would be appreciated too.

I never get these but I like it, I think though you are just looking for standard multisig, anyways an attempt with not really much formal skil...

We don't want 2 people to have all of the words. 3 people must have the 1st set otherwise (for example) CDE won't have the whole phrase if only A and B have the 1st set:

A: 1
B: 1
C: 1
D:
E:

If we ascribe the 2nd set of words to ABC:

A: 1 2
B: 1 2
C: 1 2
D:
E:

There is no way to resolve the third set because ABC can't have 3 or one of them has the whole set, but then then don't have whole passphrase:

A: 1 2
B: 1 2
C: 1 2
D: 3
E: 3

If you give one of ABC the 3rd set then one of ABC + D has the whole phrase:

A: 1 2
B: 1 2
C: 1 3
D: 2 3
E: 3

I think maybe its not possible this way, but maybe I skewed the question and rendered it unsolvable myself.

So regardless you would take that password and hash it into a 3 of 5 multsig I'm pretty sure. Maybe you know this, but it seems like you are doing it the hard/wrong way?

24 words of which there must be 5 subsets.
Any 3 of the 5 subsets must span the entire set
No mere 2 can span the entire set

Let's visualize this, makes it easier:



Looking at the above, I suspect this is impossible.

No person can have a unique area. Every area must be overlapped by at least 3 persons. Otherwise, there will be an area not covered in a set of 3. No two together can span the entire area.

Here's one attempt:



From this I think it is not possible. You'd need to get into set theory to prove this, but my weak instinct says this is not solvable.

This probably isn't the answer you want, but it works.

Person 1: 1-23
Person 2: 1, 3-24
Person 3: 1-2, 4-24
Person 4: 1-3, 5-24
Person 5: 1-4, 6-24

There's no single person who knows all 24 words. But any two people together have all the words. Which means that any three people would be able to do it.

This might help you put something together to make it more secure. I'd look at pulling different types of arithmetic sequences out.

For what it is worth, I did a quick and dirty computer search. Presuming part of the security comes from having no pair of people knowing all 24 words, and requiring that every trio of people know all 24 words, I coded up a simple simulation of distributing words at random to people where all people get the same number of words (this requirement could easily be relaxed later if desired).

Here is one solution set where each person receives exactly 16 words.
A: 2,5,7,9,11,12,13,14,15,16,17,18,19,21,22,24
B: 1,3,4,5,6,7,8,9,11,13,15,17,18,19,20,23
C: 1,2,4,5,6,7,8,10,12,13,14,15,16,19,20,23
D: 1,2,3,6,8,10,11,13,14,16,17,19,20,21,22,24
E: 2,3,4,5,9,10,12,14,17,18,19,20,21,22,23,24

Note that my program found three such solutions in a total of 150,000 random distributions which, of course, is one in every 50,000 distributions.

I re-ran the program searching for solutions in which each person receives exactly 15 words (the minimum possible under my assumptions) at random. The program has thus far tried over 2,000,000 distributions with none of them being a solution.

Amazing whosnext. Thanks. Free ether for you. Give me your address.

This problem is much simpler than it might appear if you consider a simple fact. Since you pick three guys out of five, any word must belong to at least 3 guys (if 2 guys or less had a specific word, you could select the other 3 and not achieve what you want). Since there are 24 words, the five guys must have a minimum of 24x3=72 words in total, which means that, if you want to distribute them as evenly as possible, 3 guys will have 14 words and other two 15 words.

Distributing your words is simple. Consider any combination of 3 out of 5 people:

You distribute the word 1 to people 1,2,3; word 2 to 1,2,4 and so on following the rows of the matrix above. Notice that this procedure can generalize any number of words if your requirement is that 3 people must be able to reconstruct all the words.

Following the above algorithm in your case (24 words) you obtain:

Guess you can generalize the above to any condition. If you want 4 people to be able to have all the words, then each word must belong to at least 2 people. So you build the combos of 2 people out of 5 and assign words as above.

This is a well known problem. You are looking for what is called (t, n) secret sharing.

https://en.wikipedia.org/wiki/Secret_sharing

Apply that to get your answer.

Why were you banned, what happened? You were overall unnecessarily aggressive in some discussions and could have behaved better sometime making similar arguments better and some of your positions are hostile to proper behavior towards some groups even if they have sometimes some elements of truth in them that can risk placing you in positions intolerant people have that are thoroughly prejudiced but i dont think banning for life is a good choice given what else is going on in this site by "adorable" people everywhere! The moment we try to silence what we don't like or find offensive or uncomfortable we become what we dislike and eventually worse.

If you were trolling someone and its not as a cumulative result of overall behavior then some banning is correct but permanent? Granted i dont know the details. I know many in this site behave worse than you ever did to anyone i have seen you interact with here in SMP. But could be better.

I invite mods to lift the ban or change it and find a better way to deal with it and some of your positions that are hostile or insensitive at times to groups of people because the good outweigh the bad in this case and if such standards are applied in this site then the list of candidates for equivalent to be fair treatment is huge. Silencing unpopular and even wrong positions (the objective is instead to properly prove them wrong not shun them) is not how we become better.

To show solution to this problem (i mean before the work done above as a general problem) one needs to set up equations of 5 sets and their unions and intersections using inclusion exclusion relationships for example and setting all unions of 3 to 24 and all unions of 2 to less than that.

I take the problem to imply not 2 should be able to do it either. So that should be additional conditions.

In the general problems that a set of people k out of n must have a complete set that leaves for example a situation that any k-1 do not have a particular word or more words even. So ideally in the minimal case each word belongs to n-k+1 people, ie the others left out of of any set of k-1. That way it becomes impossible now to add one more of the rest ( to form a group of k people) and not get that word to belong to all of them k now. That must be true now for all number of words w. So start assigning each word to n-k+1 different people leaving always k-1 without it. On the next word make sure you leave out all who you have already given a word to and give it first to the others that have none etc on the next ones.

Damn, thought I finally made a proof of something. I used assumptions that made an ass out of just me.

I thought about it some more and posted this at #4 above yesterday, not sure why it was deleted. The whole thing is actually fairly simple. All 2s must overlap black but no threes can. Black = missing.



And there are C(5,2) numbers required, you don't need 24.

This looks pretty good to me.


PairTheBoard

If I were to program a search for solutions...

1) Start with all 5 people holding all 24 words
2) Randomly remove one of the words from one of the people.
3) Check to see if any combination of three people will have all 24 words.
4a) If so, go back to 2.
4b) If not, put the word back and try again. Give up after a few dozen repeated failures and take this list as a 'local minimum' for the problem of people holding the fewest number of words.

Do this a couple thousand times. See if anything interesting happens.

(But nick's solution is solid.)

At the time I entered the thread, the only firm and definitive opinion expressed was that no solutions were possible.

That seemed wrong to me and I had little time to think about or to develop an efficient algorithm to find solutions. So I quickly programmed a quick and dirty random search simply to show that solutions were possible.

I thought that showing existence would lead to others finding efficient solutions. It turned out that the problem was simpler than most people realized and that nickthegeek quickly found the optimal solution (undoubtedly not needing anything that I contributed to the thread).

Here an as fast as possible algorithm to solve the problem.

Let:

W = number of words;
P = number of players;
S = size of the subset of players that must have any words

be the input of the problem. We define:

M = P-S+1 as the number of players that must have a word
T = WM as the total number of words that must be distributed to the players.
N = the set of all natural numbers between 0 and T-1

Then, for x in N we can assign words to players in this way:

x(mod)P + 1 is the player index
x/M + 1 is the word index (/ here is the integer division)

That's it. Here an implementation in the R language.

And an example of usage for the case discussed: