Dear Derek, this is a difficult question. Here is my $0.02 guess.

Alice : "Hello Bob"

Interlocutor : "That's not Bob, I am his son Charles"

Alice : "Hi Charles. In fact, I wanted to talk to you. I have lost the address you gave me yesterday. Can you give it to me again ?"

Here Alice has introduced a false information in her question because Charles had never talked to her yesterday. If the interlocutor is truly Charles, he will simply say so. On the other hand, if the interlocutor is Bob, he can never be sure of what to respond.

Historical Note: Interestingly....the same kind of things happen (around 12 years earlier)...my dad received a telephone call and the girl on the other side claimed to be his daughter. Dad asked her a question about a recent incidence happened to a close relative and she put the phone back.

Note: in those days there was not enough telephones lines in outskirts (in India) and one telephone used to handle many calls. The girl was actually the girlfriend of dad's colleague, for some reason she wanted to hide her identity.

The entangled states (of photon, electron....) may provide to catch a bluff if there is really one. This is my personal opinion. Let us see what other says.

@Mohammad. In our problem the case is different as the receiver maybe the correct person, but bluffing to be someone else. This is quite different from your case.

Derek, do we make any assumption on whether that question shall be answered correctly or any other subtlety related to this particular social situation?

Since charlse and bob are not the same voice but similar voice. There is a chance of knowing whether he is the one or not. Hence more accurate computation with shorter intervals can distinguish that. This should not be dependent on previous events or communications but uniqueness of identity that can hardly be known and be computionaly proven.

The point of the problem is to find a solution, given the case that voice is indistinguishable.

Few solutions came to my mind, and I'd like to share:

1. Make the phone call a bit longer, and try to figure out the speaking pattern of Bob. Since Alice knows Bob very well, she should know his speaking pattern and she should be able to figure out if he is Bob or not.

2. Trick the mind of the person on the phone. Like if the person on the phone is pretending to be Bob's son, and Alice want to know if he was Bob himself, she could ask him "How's your wife doing?". Such questions does not consume lots of intelligence to be answered, and chances are high that Charles - who is pretending to be his father - to answer "I'm not married!" or "You mean my mother?". But if Bob was on the phone and he's pretending to be his own son Charles, chances are high that he would answer "She's fine, thanks".

Anyway, it is an interesting problem.

There is usually an answer but it will depend on circumstances. If Alice knows Bob well, there are lots of things which are common knowledge between Alice and Bob which another person would not know. If she can trap "Charles" into revealing that in fact he has such information, then she would find him out.

In Columbo's episode 26, "An Exercise in Fatality," Columbo traps the killer Milo Janus by getting him to reveal some knowledge which only the killer would have had. Similarly, if Alice thinks that "Charles" is really Bob, then she can try to trap him into revealing direct or indirect knowledge of some information which Bob would have known but not Charles.

Muhamed, you are right of course that Bob could always pretend to be Charles. But not everyone is so quick on their feet.

There is a story about a man who was injured in a car accident and claimed that he could no longer raise his arms. He wanted a large settlement.

The defense attorney said, "Tell us how high you can raise your arms now," and the man raised his arms painfully, and only a little.

Then the defense attorney said, "And how high could you raise your arms before the accident?"

The man raised his arms very high, thereby destroying his case.

If Bob was "logically omniscient" he could surely do what you suggest. But it is well known that logical omniscience is not all that common.

Dear Derek, this is a difficult question. Here is my $0.02 guess.

Alice : "Hello Bob"

Interlocutor : "That's not Bob, I am his son Charles"

Alice : "Hi Charles. In fact, I wanted to talk to you. I have lost the address you gave me yesterday. Can you give it to me again ?"

Here Alice has introduced a false information in her question because Charles had never talked to her yesterday. If the interlocutor is truly Charles, he will simply say so. On the other hand, if the interlocutor is Bob, he can never be sure of what to respond.

Dear H.E.L., I do like your answer. It uses the correct principle and looks more compact than my answer.

In 2007, I also came up with the idea that you have to deliberately introduce incorrect information.

So my solution was that Alice should say: "Ah, so you are Charles! Do you remember we met at the bus stop last week and we got chatting and you told me you were Bob's son? Well, if you remember I was on the way to a fancy dress party and you commented on the loud colour of my hat. What was the colour?"

(This is all fake, Alice did not really meet Charles or have a hat).

Now if it really is Charles on the telephone, he will say: "I do not remember meeting you, I think you were mistaken."

If it is Bob pretending to be Charles he will say: "Actually you caught me out because I am really Bob and so I don't actually know about the colour of your hat." Or Bob might bluff and just say "the hat was green," in which case you have caught him out, because you know there was no green hat or any hat at all.

So this is a great problem because it shows how misinformation can actually help you. It also shows that problems with asymmetric information are tricky. In this case, the way to break the problem is to introduce your own misinformation asymmetry ....that is the principle. Interesting that you can attack information asymmetry with misinformation asymmetry :-)

Thanks Derek, I think that this is a beautiful problem and one i hadn't seen before.

I must confess I don't like the solutions posted above since they essentially seem to revolve around the ability of Bob to create a convincing lie or spoof Alice, and such an ability is going to be a function of factors such as psychology, shared past knowledge etc, and hence will not admit (IMO) a rigorous mathematical/physical solution.

So I've been wondering about the approach based on shared information. It seems to me relatively straightforward to generate a solution based on a trusted authority, or shared randomness (i.e. keys) between Alice and Bob and Alice and Charlie, but such solutions seem inelegant to me and contrary to the spirit of the problem as originally posed.

If I restate the problem in a slightly different way, it may help (but I'm not convinced as I haven't solved it yet!).

Alice and Bob share some a priori knowledge, measured by some set of bits/qubits, but Alice and Charlie share no a priori knowledge. How can Alice confirm the difference between Charlie and Bob pretending to be Charlie (i.e. pretending to have no shared knowledge).

Alternatively, we could try and model some of the comments above by assuming that Alice and Bob have say, n shared bits of data (think n challenge questions and responses) and Alice and Charlie have m shared bits. The above discussion about the hat, for example, then would be equivalent to determining how many questions were required to ensure that there was noise, so that Bob could not pretend to be Charlie. Again, this becomes a more standard authentication problem.

Coming back to the original idea (i.e. no shared knowledge), it is not obvious how to solve this problem at all. Typically we are looking to maximise shared information, here our task is to maximise information whilst one participant is adversarial.

I can only think of a few ways to start at present.

The first is to ensure that to answer his phone, Bob must verify who he is without being able to know who is talking to him. So we would have a protocol where first the phone rings (no caller ID though), then Bob must verify his identity first, then Alice can talk. I would imagine that an asymmetric key protocol might well be possible here.

Another way would be to come up with a game theoretic type approach where there was a cost function associated with hiding bits (this would be presumably up your alley, Derek!) and then a solution could be determined where it would cost Bob a certain amount of bits, and he could hide if he was prepared to pay the cost. So I'm thinking about a scheme where the a priori shared randomness between Alice and Bob is being consumed by Alice, but Bob denies he is Bob, but then loses the correlated bits. The problem here is that if it really were Charlie, then the shared randomness is still lost by Alice broadcasting the bits to Charlie, so i don't that that works either.

Anyway, an interesting problem.

OK, here is another start at the problem.

Assume that Alice shares n random bits with Bob, and m random bits with Charlie. (Note that I think that this is going to be vital, because in any protocol without any knowledge of Charlie, Bob can simply return random answers/null answers)

Alice phones Bob and challenges the receiver by giving challenge questions, but we have the problem that as m \neq n, and presumably m < n, we have to worry about how to set up a protocol that doesn't convey the sizes of m and n (which would presumably alert the receiver to the fact that Alice is suspicious). So presumably the questions can be posed as challenges to random questions chosen modulo the number of shared bits. One can imagine here a reductio ad absurdum where Alice and Charlie share one bit, but Alice and Bob share many. Alice poses a challenge question as asking the solution to question (x mod y) where x is a randomly chosen question and y is the number of shared bits, which the correct Charlie would always respond the same way (there is only one bit), but if Bob didn't know that, would presumably need to provide random answers. This would seem to enable this level of privacy to be hidden.

Of course, there are issues here relating to eavesdropping and in an adversarial setting, knowing how the keys were maintained, so I am not saying that this is the solution, but perhaps a start?

Thanks Derek for your kind comment and thank you all for your kind upvotes. I really didn't think that my guess would end-up being the correct answer. I was not too satisfied with my answer because I could not figure out how to make use of the complete information that had been given in the original question; namely :

(a) Alice knows Bob very well

(b) Alice knows almost nothing of Charles

It seems to me that my answer would still apply even if (a) and (b) are not verified. Because of that, I was pretty sure to be wrong.

Nevertheless, Derek, your questions are never easy. In fact, I am still waiting for your complete response on a different thread concerning another question of yours about the detection problem for bodies in thermal equilibrium with the detector.

Thanks again.

.

Hi Derek,

Quite interesting in fact, the question and the answers. However, unless Bob is below an average person (average intelligence), he could easily and safely maneuver over the fake interrogation. Example-quoted from H.E. Lehtihet's comment:

Alice : "Hello Bob"

Interlocutor : "That's not Bob, I am his son Charles"

Alice : "Hi Charles. In fact, I wanted to talk to you. I have lost the address you gave me yesterday. Can you give it to me again ?" - Alice here is 50-50 skeptical about the true identity of the other person. Thus, among few other responds :

Interlocutor : "Yes sure, here it is" - and gives her an address-any address. Fake question or fake info? This is 50-50 situation, still. In fact, Alice might be the one confused at this point. Besides, if Bob was planning to lie about his ID (major lie), why he should be honest about some address or any other info (minor lie)? Logically he will not stop doing so.

OR

"Of course, just remind me again what address you meant? Because yesterday you asked for TWO addresses. Right?" - Answer a question with a question, this is 90-10 in favor of Bob since he can, by that, decide if the question was fake or not, and can get some clues about the correct (true) answer, among other possible (exit doors).

Similar stories can go for the bus situation.

The above is based on an assumption that Alice did not actually met Charles, but is trying to trap the person on the other side.

If she did, however, and if she had a question based on a true info, then she can easily distinguish between the two persons; no need for tricks. And if she knew his son and Bob knew about this fact, logically Bob wouldn't try to pretend to be his son, he'd try being someone Alice didn't saw ever, perhaps his brother.

Logically, she can instead ask him about some information that only Bob knew - not Charles. If the answer was true then he is Bob, this is 100-0 game. If the answer was not true, she returns to the 50-50 state. The sum of chances here is better than the above... perhaps. :)

If Alice knows Bob well, how come she doesn't nothing about his son?

That's true Muhamed. It is like a case where we need to test a system with an unknown state named A, and we suspect that this system's nature might give us a fictitious state named B. Since information from a system with an unknown state can not be trusted, thus the only method is to compare the state A to the properties of the state A itself. This will not give a full solution, but will indicate which is the more probable to pick, state A or B.

The solutions given above suggest that the system is to be projected to another false state, C, then if the system satisfies C then the system is B, if not it is A; while in fact this solution only complicates the problem. This is because the system might choose the other false state C and adopt it (it is in its nature), so instead of being worried about two states of the system A and B, we'll have 3 states to choose from!

I think the specifics of the question and answers assume psychological reaction of the subjects; a case where logical probabilities are with no use at all when we know that the tested system didn't have a (psychological space)-sort of.

This question reminds me of Merkle's puzzles, a crypto-system based on knowing the right question to answer more than the right answer (which is easy to compute). The solutions given above represent to the speaker that Alice and Charles have previously agreed on a puzzle to share as a key, and asks the speaker to use that information. If they try, they must not be Charles since no such agreement was made.

But suppose Bob knows everything about Charles, including that Charles knows nothing about Alice. Then Bob can simply act as Charles would--"Sorry, I don't remember meeting you or giving you an address." Even without sure knowledge, Bob may guess this is the case, and so the determination could only work in a probabilistic sense--the speaker answers as Charles would more than 90% of the time over N queries, so is likely Charles.

It seems difficult to come up with a single question unless you know the extent of the asymmetry that exists, and even then, you're still open to guessing on the imposter's part.

But I can see a use for this tactic in protecting web sessions--suppose every server asks the browser to return a previously issued cookie in response to a challenge. A thief might steal this cookie and play it back. But suppose the server asks for a random number of different cookie-challenges, all of which are valid. Does the thief question whether he got them all? Does he return the right cookie with the right challenge? Seems like there might be a way to trip up some proportion of attacks this way.