Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
2  
Can you please elaborate on the trust relationships within this group? For example, it's very easy for two cooporating members to find out the secret key of a member in between them. And unless I'm mistaken only Member20 has the message in the end - not everyone. –  nightcracker Aug 31 '13 at 13:36
    
Given it's only a thought-experiment there isn't any inherent relationship between users, but exploring the vulnerabilities is the reason I posted, so I'd certainly appreciate any thoughts. Given that each secret number is only ever used for passing one message, and people don't get to choose their position in the chain, is that still a concern? They might be able to gang-up to reveal another secret, but it wouldn't give them any useful information unless they could use that to reveal who was the original source of the message. –  Curious Coder Aug 31 '13 at 15:22
    
I suggest editing your question to make clearer what the question is. It's important to have a clear, focused question, but right now the body of the question doesn't contain any questions (just statements). –  D.W. Sep 1 '13 at 3:51
    
Anonymity in this ring is not very strong: If the attacker controls two parties of the ring, he can separate the ring into two segments and distinguish in which segment the protocol started. This is independent of the number of participiants, and if he controls more parties, he can distinguish between even more ring segments. Most commonly you want MPC protocols to hold their guarantees for up to $N/2$ corrupted parties. –  tylo Sep 2 '13 at 12:27
add comment

2 Answers

So a fundamental property of multi-party anonymous systems is you are only anonymous out of the number of honest participants in the system. If the Stasi control everyone else at the dinner table and know they didn't send the message, then they know you did no matter what protocol you use.

In your case with this ring topology, because only your two adjacent neighbors in the group know about you and therefore you only interact with them, they only need to be malicious. Specifically, if the member's before and after you collude by cutting you out of the real network and putting you in one that just involves the two of them, then they will know you sent the message when you complete the protocol and remove your key.

share|improve this answer
    
That makes a lot of sense, thanks! I'm curious, though, if the neighbors on either side of you were colluding, wouldn't they be able to verify you were lying about your bit in a classic DCnet just as easily? –  Curious Coder Aug 31 '13 at 22:26
add comment

Collusion is a concern but unlikely in very large ad-hoc ring networks where each ring is a one-shot random walk of a suitably large and mostly trustworthy membership pool. Collision and congestion are problems though; read below.

If the opponent(s) can determine where the message or the key to decipher the message came from, the poster is done for. Shrinking the problem down to three members, an opponent has to believe the other two members are equally likely originators for the communication method to be secure.

Consider three members A, B and C without collusion:

Syntax: [Member][Round] = [data] [[+/- as XOR operator] [data]] [...]

Member A originates anonymous message:

A1 = secret_a + message
B1 = A1 + secret_b = secret_a + secret_b + message
C1 = B1 + secret_c = secret_a + secret_b + secret_c + message
A2 = C1 - secret_a = secret_b + secret_c + message
B2 = A2 - secret_b = secret_c + message
C2 = B2 - secret_c = message
A3 = C2 = message
B3 = A3 = message
C3 = C2 = <discard further rotation>

Member B originates anonymous message:

A1 = secret_a
B1 = A1 + secret_b + message = secret_a + secret_b + message
C1 = B1 + secret_c = secret_a + secret_b + secret_c + message
A2 = C1 - secret_a = secret_b + secret_c + message
B2 = A2 - secret_b = secret_c + message
C2 = B2 - secret_c = message
A3 = C2 = message
B3 = A3 = message
C3 = C2 = <discard further rotation>

Member C originates message:

A1 = secret_a
B1 = A1 + secret_b = secret_a + secret_b
C1 = B1 + secret_c + message = secret_a + secret_b + secret_c + message
A2 = C1 - secret_a = secret_b + secret_c + message
B2 = A2 - secret_b = secret_c + message
C2 = B2 - secret_c = message
A3 = C2 = message
B3 = A3 = message
C3 = C2 = <discard further rotation>

Steps from C1 onwards are indentical in all cases. Hence originator is unknown. Three cycle rounds are sufficient for any amount of members. Member location in chain is irrelevant providing it doesn't change during a cycle. In fact the ordering of the cycle 2 should differ from cycle 1 to reduce collusion.

All secrets should be discarded after the three-cycles "dispatch coil" is complete. Dispatch coils should occur on regular intervals and with consistent bandwidth regardless of anyone actually communicating anything. Thus the solution has flat bandwidth cost per day/week/month regardless of communication use.

Problem

No congestion control. If two or more members add anonymous messages to the same dispatch coil, the messages can not be separated by members. The addition of a collision or congestion flag would indicate the message origin as either upstream (flag set) or downstream (flag unset) of opponent.

Member A and B both send anonymous messages:

A1 = secret_a + message_a
B1 = A1 + secret_b + message_b = secret_a + secret_b + message_a + message_b
C1 = B1 + secret_c = secret_a + secret_b + secret_c + message_a + message_b
A2 = C1 - secret_a = secret_b + secret_c + message_a + message_b
B2 = A2 - secret_b = secret_c + message_a + message_b
C2 = B2 - secret_c = message_a + message_b? <C will assume no message injected for this dispatch coil>
A3 = C2 - message_a = message_b; but pass through (message_a + message_b)?
B3 = A3 - message_b = message_a; but pass through (message_a + message_b)?
C3 = C2 = <discard further rotation>

With two messages, only two people get deciphered messages. Three or more messages, no one gets deciphered messages.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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