Suppose we have three parties, Alice, Bob, and Carol. Alice can receive messages from Bob and Carol individually, but can only send messages to both simultaneously. Additionally, Alice cannot tell if Bob and Carol can send/receive messages to/from each other. This is what Alice wants to figure out

Bob and Carol are always both going to say that they can communicate, even if they can't. What challenge can Alice give to the two of them to ensure that they are not lying?

  • $\begingroup$ There is no such challenge. $\;$ $\endgroup$ – user991 Jun 17 '15 at 0:51
  • 1
    $\begingroup$ One can choose PRNG seeds for Bob and Carol independently and uniformly, then give them both to each of Bob and Carol, so they can use the resulting bit-streams as their "random bits" and know what would've been sent along a Bob-Carol communications channel if there was one. $\;$ $\endgroup$ – user991 Jun 17 '15 at 1:13
  • 1
    $\begingroup$ @TessellatingHeckler: "quote me a title or line from any famous song, book, movie or poem" is essentially the PRNG pre-agreement problem re-stated in a fuzzy way - it would work, perhaps just once, with actual humans, but it is a weak protocol if known. E.g. Bob to Carol prior to test: "When you send to Alice, work from this copy of Wikipedia, and reply with the first thing that matches Alice's request" $\endgroup$ – Neil Slater Jun 17 '15 at 16:50
  • 1
    $\begingroup$ @TessellatingHeckler: It's not a rigorous protocol, if it relies on humans behaving in a "common sense" way - you have stepped outside of cryptography mathematics really. Also, you cannot bring in timing information or any properties of the messaging channels, otherwise that is a essentially a back-channel breaking the assumptions about the nature of the links. For a robust protocol, you need to assume communications as described are perfect and instantaneous (or in a weaker sense, cannot be analysed or taken advantage of using restrictive times). $\endgroup$ – Neil Slater Jun 17 '15 at 18:05
  • 2
    $\begingroup$ @stonegrizzly the problem is, while it might work in practice, it doesn't work in theory ;). All the questions you can ask a machine boil down to "pick a random number" - and if Bob and Carol can briefly talk once ever, they can synchronise their random number generators and always get the same random number, and then lie about being able to communicate. Even with humans, you'd never know for certain that they were talking, you might find they both love the same book, the same song, the same tree, whatever, by agreement beforehand or by coincidence. $\endgroup$ – TessellatingHeckler Jun 17 '15 at 18:11

Designing such a challenge is Impossible.

If we assume that having a connection is equal to being able to exchange any piece of knowledge at any given time then the proof of impossibility of such challenge is as follows:

Proof. First assume that there is such a challenge and Alice is capable of querying such a challenge to correctly determine whether the connection exists.

We give Bob and Carol the exact same knowledge set $K$ prior to the start of the challenge. (Obviously this knowledge set could contain a random tape: an infinite sequence of random bits) Bob and Carol are going to give answers to Alice only based on the knowledge set $K$ and what they later learn from Alice during the challenge.

Since Bob and Carol share the exact same knowledge set both of them know exactly what would be the answer of the other one to any given question about anything they already knew (knowledge set $K$). Their answers to these questions would be either "I can't/don't know" (the question asks about information outside of the knowledge set $K$) or something that both of them are exactly aware of.

To elaborate more clearly, the answers to questions and challenge which require some sort of randomness such as "quote me a title or line from any famous song, book, movie or poem", "send me a ten digit prime number" or "name a tree" would be answered based on an already shared random tape. Which means that at any given time they know exactly which member of all possible correct answers in their knowledge set is the given answer of the other one.

To further clarify things, it should be mentioned that as Bob and Carol have the exact same knowledge set $K$ all questions and challenges that are related to each other in some form would have consistent answers. For example, if Alice asks Bob "Name all of your favorite supercars" and then asks Carol "Does Bob like to have a Ferrari?" should yield consistent answers.

Accordingly, there is no challenge that questions about the knowledge set $K$ which proves the "connection" since consistent answers do not require any "exchange" of information. So, the challenge should ask a question which at least partially assesses the information that Bob and Carol acquired during the challenge.

Assume that the knowledge set $K$ plus what Bob learned from Alice during the challenge is $K_B$ and for Carol it is $K_C$. For the challenge to prove the connection $K_B$ should not be equal to $K_C$ otherwise as discussed earlier both Bob and Carol would know exactly what would be the answer of the other one to any given question and the challenge cannot prove the "connection" since consistent answers do not require any "exchange" of information.

Thus, they should have learned different things from Alice which is impossible since they receive same messages simultaneously from Alice.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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