Skip to content
Quilibrium

About Quilibrium and Components

Level 1: Communication

We've got a group of friends who like to meet once a week and catch up on the latest gossip, but you've all got really busy schedules with extra curriculars, so finding the right time to meet, and know if it's even worth meeting (last time Dave just wanted to drone on about his breakup and it was a huge bummer and totally his fault anyway) is challenging. Teachers are really strict, and if a cellphone is confiscated they're reading the conversation out loud, which was super embarrassing for Dave (man he's gotta stop it with the TMI).


One of the friends, Sally, is a math genius and heard about this crazy trick using the formulas we just learned about in algebra – those equations that go y = 18x + 2 and so on. Basically, if we all come up with our own random coefficients for the equation (the 18 and 2 in the equation), and each one of us is assigned a unique number that we plug in for x (and we all know each other's unique number for x), then we can share the y value for each person's x value to each person, individually (e.g. if my x = 4, everyone is going to give me their y value when x = 4).


Once everyone has their specific y values (samples), then we add up all of the ones we got to a single y value, and can team up, where any two of us can share our y values and find out what y equals when x is zero (because we're just solving the equation to find that last coefficient):

y = Bx + C

y = 372, x = 4 :: 372=4B + C :: B = (372-C)/4

y = 182, x = 2 :: 182=2B + C :: B = (182-C)/2

(182-C)/2 = (372-C)/4

182-C = 184-(C/2)

-2 = C/2

C = -4 :: y = B(0) - 4 :: **y = -4, x = 0 **


Now that we all know what y is when x is zero, we have a secret number to encrypt our group messages with that nobody else knows.(This is not actually safe, you need proper cryptography to do this right, but this is the underlying math concept that makes distributed key generation work)


Of course, what if a teacher finds out the number? So we bump the secret number with every message, coming up with a new random non-zero number. If we get messages out of order, we can try the multiplication in a different order to figure what the message order was supposed to be, and so long as nobody keeps every previous message, there is no way for someone stealing our phone to figure out what the past messages were (Forward Secrecy). But once they have it, how do we stop them from learning our new messages?


We do that same math trick again, frequently. This provides something out of band that makes future messages unable to be decrypted by prying eyes that snagged a phone (Future Secrecy). Sally's math skills are scary.


But what if you wanted to just talk to one person, and you didn't want the rest of the group to know? This is where there's even more safety in numbers. The group conversation gives you a place to do an envelope technique, where you create a unique number for the pair of you to talk and encrypt it just for them, mark the message with the recipient, then take that whole message, encrypt it for someone else, mark it with their unique number, then take that whole message again, encrypt it for someone else, and mark it with their unique number, and send it to the outer-most recipient. (Envelope Encryption/Onion Routing) Each envelope has to be decrypted and sent before the recipient message is available to the recipient in the group, but it gives you a few degrees of removal before it appears in the group, and only the recipient can decrypt the final message.


Of course, if anyone watches the group activity, it wouldn't take much to figure out you're talking to that one person given who is sending messages around the same time as they appear in the group, especially if you end up using the same first hop by random chance, so you need one more indirection. Messages cannot make it to the group conversation until a specific number of them have been received by a final hop. In other words, the last hop has to batch them all and send them all at once. That final hop also has a responsibility to scramble the order of those messages when they relay them to the group chat. Thankfully, our algebra class just learned about matrices, and a square matrix equal to the number of messages with only one 1 at any given combination of row and column, rest are zeroes, will let you scramble the order efficiently (Random Permutation Matrix, extremely simplified). With this trick, there's no way to figure out who's talking to who by watching the timing of the group chat.

Reference