1
$\begingroup$

This question already has an answer here:

The previous part to this question is here.

As a family generally has no more 5 kids, and I want to generalise the situation in the previous question, I shall change the context a little:

There are a group of 9 people who own a vault containing a large sum of money. The vault must be unlocked with an alphanumeric password (of an arbitrary length).

None of the people in the group can trust anyone else to enter the vault on their own. However, they all feel that 2 or more people from the group can enter the vault at the same time. (In other words, they feel that although one person on their own cannot be trusted with all of the money, they feel that with 2 or more people around, the chances of skullduggery are much lower, and they can trust each other not to team up to steal the money).

To make it absolutely clear, they must devise a system which will not allow only one person to enter the vault on their own.

Therefore, they devise a system similar to the answer to the previous question in order to circumvent this problem. What is the least number of people which can be allowed to enter the vault at the same time?

What happens when this problem is generalised so that there are $n$ people in the group?

$\endgroup$

marked as duplicate by f'', Anthony Pham, Deusovi, bleh, Ken Y-N Apr 6 '16 at 3:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Yes! Part two... $\endgroup$ – Beastly Gerbil Apr 5 '16 at 20:42
  • $\begingroup$ Any two people? $\endgroup$ – Chris Cudmore Apr 5 '16 at 20:46
  • $\begingroup$ Any two (or more) people from the group. Note that it may/may not be possible for two. $\endgroup$ – Shuri2060 Apr 5 '16 at 20:46
  • 3
    $\begingroup$ en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing ? $\endgroup$ – Marius Apr 5 '16 at 20:57
  • $\begingroup$ @f'' - I can't quite see how it is a duplicate - can you explain? $\endgroup$ – Shuri2060 Apr 5 '16 at 21:00
6
$\begingroup$

This seems too simple, so I may be missing something.

Create a password and provide each person with it, but one letter/number listed as a blank space. If each person has a different one removed, then they just have to have the other person put in that single blank space.

This ensures that any combination of two people can enter, but not on their own.


Example:

The password is 123456789. Person 1 is told _23456789, Person 2 is told 1_3456789, Person 3 is told 12_456789, and so on. No matter who person 1 walks in with, they have that missing part. Likewise, no matter who walks in with person 1, they have the remainder of the code they are missing. For more people, increase the password length. Although you'd probably want a move complex password.

Let's make it a little more fun. I think you originally had mentioned requiring 3 people before you edited it. I solved it anyway.

You can do it in batches (so for three people you have 123 456 789). Make it so each person has a single batch missing AND a row (example person 1: _23 ___ _89). Now with two people, you're still guaranteed to be missing one space. If each person is missing a different batch and different row, then any third person will guaranteed fill it. For each additional person, add one more batch and one more row to each batch.

You can continue to make additional people another requirement by adding extra layers.

Do you want 4 people? Create a sets of codes and each person is missing a set. It gets pretty big pretty fast (yay exponential growth!), but it is a guaranteed solution.


Password Creation:

If you need two people to open it, you can also create it with two people. If they know the system that is being used to prevent single-user entry and everyone wants to enforce this, it should be simple.

Make the password length equal to 1 per person (in this example we have 9). Have the first person create all spaces except for the last (9). Give all of those to the ninth person, but remove the first space. Have the ninth person create the ninth space. Now have the first person give the everything but THEIR last space to person 2, everything but their last two spaces to person 3, etc. Have the last person give the second person their first one space, give the third person their first two spaces, the fourth their first 3 spaces etc.

You end up with everyone having their portion without having known the full combination at any time.


Example:

password is 123456789, person 1 supplied 12345678_, gives 2345678 to person 9, who makes it _23456789. Person 1 gives person 2 1234567__, person 9 gives person 2 ________9. Person 2 now has 1234567_9. Repeat with everyone else.

This can also be applied to the n person solution, but it requires three people to create the key, which they also will have to distribute.

Naturally, this requires a lot of trust in the initial two people, but it can be replicated by having each individual select a value and then show each other person, but that has it's own set of problems.

Changing it would just be restarting the process of password selection. You would need the two (or three) people to have the original, then you can have those two (or three) create a new password and distribute it.


Password Secrecy:

To make sure no one knows what the parts the others have, there are a few things to note.

The creators don't have to leave the first and last spaces blank when creating. So long as they provide accurate information when distributing, they can use any spaces they want. No one, besides them, will know which space the other is missing. When distributing, the creators can each provide their part, written down, and then present them to the others at random. Then the creators don't know which space each person is missing.

The difficulty is that there are overlaps in each person's knowledge and HAS to be shared between them somehow. So keeping what you know a secret from others while ALSO giving them their share of the information is impossible without having some kind of anonymous distribution.

An alternate option would be to have each person create a single space (or batch). They each write down their value on 8 papers and add one more blank paper . Each person draws a paper from the first pile. Then they repeat for each additional pile. Eventually you draw a marked paper that is blank. If you already have a blank (or you drew the blank for your own pile), you replace it into the pile and drawn again. Once everyone has their papers, each person will show that they have a blank paper. No one knows which space the others are missing, but you know they are missing a single space. Assuming you drew papers in order of the spaces, you have your sequence.

$\endgroup$
  • $\begingroup$ Not what I'd trust the keys to the kingdom to, but it works. $\endgroup$ – Chris Cudmore Apr 5 '16 at 20:53
  • $\begingroup$ This method works... but how is the password created in the first place as no one is allowed to know the whole thing? (once you've explained this, you're there) $\endgroup$ – Shuri2060 Apr 5 '16 at 20:57
  • $\begingroup$ Expanding on this, Make a long password of length k*n, k being an arbitrary integer. Person 1 is missing 1, n+1, 2n+1... Person 2 is missing 2, n + 2, 2n + 2, etc. $\endgroup$ – Chris Cudmore Apr 5 '16 at 20:57
  • 1
    $\begingroup$ @QuestionAsker You could have person 1 write the first n-1 characters, then have person 2 do the last. Then they fill in everyone else on the characters they need to know $\endgroup$ – StephenTG Apr 5 '16 at 21:01
  • $\begingroup$ However, what I originally had in mind was that whether if it was possible for each person to keep their segment completely private - which was why I thought it could be impossible for 2 to 8. $\endgroup$ – Shuri2060 Apr 5 '16 at 21:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.