So I was thinking about variations on the Dining Cryptographers problem - In some cases, it's useful to be able to post a message without revealing the source, but with the additional constraint of not revealing the entire group to one another.
For instance - Let's say you have 20 members in a ring. Each single member knows the person to their left, and the person to their right, but none of them know the entire layout of the party.
An individual in this group wants to share a message, without revealing to the rest of the group that they are the original author.
Suppose each member were to generate a random string of the same length. This string must be GREATER than the size of the message to be shared.
Starting with one arbitrary member, each member would then talk to their neighbor in turn. Member1 would share his secret with Member2. [1] Member2 would then XOR the secrets together, and tell this XORed result to Member3. Member3 would then XOR his secret against this shared-message, and then pass it to Member4, and so on.
Each Member would XOR their own secret against the shared-message before passing it along.
At some point during this arrangement, the ring would pass to the member who intends to post. This member would then XOR the shared-message against both his secret, as well as the Message to post. He would then pass the shared-message as normal.
After the message made it all the way around, Member20 would pass it back to Member1. Member1 would then XOR by his key again, effectively removing it. He'd then pass the message to Member2, would would remove his key, then pass Member3, etc.
By the time it returned to Member20, and he removed his key from the set, only the secret message would remain.
There's a simple demonstration in Python
import random
# Create our initial string, and encode it to a series of bits.
# Pad the bits to be at exactly 1K.
initial = "This is the song that never ends - It just goes on and on my friends."
bytestr = initial.encode('utf-8')
intstr = int.from_bytes(bytestr,byteorder='big')
needed_bits = 1024 - intstr.bit_length()
padded_bitstr = intstr << needed_bits
working_str = 0
secret_machine = random.randrange(0,20)
# Create 20 virtual nodes, and give them each a random number.
nodes = []
for i in range(0,20):
rnd = random.SystemRandom().getrandbits(1024)
node = {}
node['randombits'] = rnd
working_str = working_str ^ rnd
if i == secret_machine:
working_str = working_str ^ padded_bitstr
nodes.append(node)
# Optionally shuffle.
random.shuffle(nodes)
for node in nodes:
working_str = working_str ^ node['randombits']
# Convert back to string
unpadded_str = working_str >> needed_bits
reformed = unpadded_str.to_bytes(int(unpadded_str.bit_length()/8)+1,byteorder='big').decode('utf-8')
print(reformed)
print(reformed == initial)
[1] - To avoid Member2 checking to see if Member1 was the poster, Member1 should use 2 secret keys, but only share 1. Essentially treating himself as 2 virtual members. But that's
