Masking a PIN over a phone call.

[axn]

Originally Posted by Flatlander

but just before Bob needs the PIN Alice and Bob are struck down with Stupiditis and are only able to comprehend integers 0 through 9, ...

Originally Posted by Flatlander

but they understand the terms prime, composite and co-prime

I am guessing the onset of stupiditis still leaves these intact?

[retina]

Originally Posted by retina

I know how that feels. I get struck be that very frequently. As for solving this new modified puzzle I feel an attack of Stupiditis coming on now. :(

One of my minions suggested this procedure:

Bob says integers at random and Alice says "yes" when Bob say the correct integer. Bob must say the integers in random order to eliminate a timing attack from Eve. In the worst case Bob must say forty numbers (all integers four times over) which could be done in the 30 second limit. In the average case it would take 20 numbers. And in the best case only four numbers.

[wblipp]

Originally Posted by retina

Bob says integers at random and Alice says "yes" when Bob say the correct integer.

Revertive Pulsing! Panel telephone switching systems used this method to signal the called number from one telephone office to the next. Panel was Bell System's biggest Central Office Switching System in the 1930's, surviving in the field until the 1970's. (Not to random part - but there was no need secrecy)

[retina]

Originally Posted by retina

In the average case it would take 20 numbers.

Make that 22 numbers.

I was about to give him a gold star but that little error means no star for him. And my sharks are looking a bit hungry so perhaps ...

[Mini-Geek]

Originally Posted by retina

One of my minions suggested this procedure:

Bob says integers at random and Alice says "yes" when Bob say the correct integer. Bob must say the integers in random order to eliminate a timing attack from Eve. In the worst case Bob must say forty numbers (all integers four times over) which could be done in the 30 second limit. In the average case it would take 20 numbers. And in the best case only four numbers.

Originally Posted by retina

Make that 22 numbers.

I was about to give him a gold star but that little error means no star for him. And my sharks are looking a bit hungry so perhaps ...

Actually, observe that if Alice answers "no" for the first 8 numbers, there are two numbers remaining. When Alice answers "yes" or "no" for the next guess, Bob knows the answer with certainty without needing to ask any more questions. Thus, the maximum number of numbers that must be said is 36, and the average is 21.6. (this follows from the fact that the probability of Bob needing to ask 1-8 times is 10% each, and the probability of him needing to ask 9 times is 20%; since 1+2+..+8+9+9 is 54, the average guesses per number is 5.4, so the average is 5.4*4=21.6)

A binary search ("is the number greater than or equal to 5?") would improve this average, but would open up the algorithm to timing attacks from Eve. I'm not sure whether a binary search with randomized index might help without revealing anything to Eve...

[retina]

Originally Posted by Mini-Geek

A binary search ("is the number greater than or equal to 5?") would improve this average, but would open up the algorithm to timing attacks from Eve. I'm not sure whether a binary search with randomized index might help without revealing anything to Eve...

Bob could randomly ask whether the number if greater or lesser than the next pivot value. I think that leaves Eve with no information to work with.

[Mini-Geek]

Originally Posted by Flatlander

(Or some other restriction to make it more interesting.)

What if Eve can overhear some (say, with probability p) of the words Bob says? E.g. let's say for any given word, regardless of the word length, there is a 95% (p=.95) chance that Eve can hear it, and a 5% chance that she cannot (and suppose these are independent events: if Eve misses a word, the probability of hearing the next word is still p). Alice and Bob don't know what words Eve did and did not hear. How can they minimize the probability that she will get the PIN? Would the solution be different depending on p, where 0 < p < 1, e.g. p=.05 or p=.5?

[ewmayer]

I suggest the OP is ill-posed, since it omits vital details:

o Can Eve hear only what Alice says, or possibly also Bob's replies? If the former, see "public key crypto" or some variant of the "Bob begins reciting random digits, Alice says yes or no to each" method, done.

o Is Alice using a voice-only phone, or multimode? If the latter, can Eve see the keypad?

[Brian-E]

Originally Posted by ewmayer

I suggest the OP is ill-posed, since it omits vital details:

o Can Eve hear only what Alice says, or possibly also Bob's replies? If the former, see "public key crypto" or some variant of the "Bob begins reciting random digits, Alice says yes or no to each" method, done.

o Is Alice using a voice-only phone, or multimode? If the latter, can Eve see the keypad?

o Does Eve work for the NSA? (If so, just forget it, the problem is insoluble.)

[chalsall]

Originally Posted by Brian-E

o Does Eve work for the NSA? (If so, just forget it, the problem is insoluble.)

You have read Neal Stephenson?

Cryptonomicon is when he got serious.

[Brian-E]

Originally Posted by chalsall

You have read Neal Stephenson?

Cryptonomicon is when he got serious.

No, and thanks for the literary tip.