English subtitles

← 03-03 Pairwise Distribution Solution

Get Embed Code
1 Language

Showing Revision 1 created 05/04/2012 by Amara Bot.

  1. The answer is 4851,
  2. so suppose we have 100 people, and I'm not going to try and draw 100 people,
  3. but here we have N people.
  4. In order to be able to communicate with everyone else,
  5. the first person will need a shared key with every other person,
  6. so that's going to be N-1 key shared between Alice
  7. and the N-1 other people.
  8. The second person already has a shared key with Alice
  9. but needs a shared key with everyone else.
  10. That is N-2 additional keys.
  11. The third person that has keys shared with Alice and Bob
  12. needs a key with everyone else, and this continues until
  13. the next to last person, who needs a key shared with the last person.
  14. That means we need the summation from N-1 down to 1,
  15. or we can think of that going forward 1+2+...up to N-1,
  16. and that simplifies to N-1 times N-2 divided by 2.
  17. For 100 people, this would be 99 times 98 divided by 2,
  18. which is 4851, which might not sound too bad,
  19. but 100 people is a pretty small number.
  20. If we think of doing this for the billion or so people on the internet,
  21. then we would need around 10 to the 18 keys.
  22. This isn't really a solution, both because of the huge number of keys that are needed
  23. and the need to establish all of these pairwise keys.
  24. We haven't really solved our problem.