Masking a PIN over a phone call.

[Flatlander]

So Alice is on the phone to Bob buying new cruncher for P95. Eve is sitting at Alice's restaurant table and is known to 'a bit dodgy'.

Alice needs to give Bob her Debit Card PIN whilst given away as little information to Eve as possible.

The conversation is as follows:
Alice: For the first digit guess a number from zero to nine.
Bob : Eight.
Alice: Add one to that and you have the first digit.
The conversations continues similarly for the other three digits of the PIN.

(Now if Alice says for example "add eight to that digit" then Eve will know the correct digit is 8 or 9.)

1)What is a better system? A system that reveals no information at all to Eve if possible. (Neither Alice or Bob have computing devices but they understand the terms prime, composite and co-prime. The PIN must be revealed to Bob verbally within a minute. A maximum of one command, one reply, and one adjustment per digit of the PIN. Alice is incapable of remembering her PIN beforehand.)

"Better" means for all possible PINs, 0000 through 9999.

If this problem is worded poorly then please rephrase for clarity.

:)

[ewmayer]

Since Eve is presumably privy to everything Bob is, the only secure system for obfuscation must rely on something Alice and Bob have previously exchanged in a fashion they are (reasonably) sure is secure. E.g. they have exchanged a secret word sequence, each word corresponding to a digit, which Alice uses.

Better of course is a public-key-based exchange: Bob gives Alice his public key which she uses to encrypt the data, but this is probably ill-suited for "live mental encryption" of simple short-length data strings.

The kinds of very-short-length secret-data exchanges made under the eyes of the Watchers have been solved in various ways by prisoners, drug gangs, spies and sports teams. Look at the intricate in-game signaling methods used by baseball teams, for example. For Alice and Bob some verbal adaptation of the next-pitch signals exchanged by the catcher & pitcher might serve.

[LaurV]

I think his point was that Eve hears everything Alice says, but she does NOT hear what Bob says (as Alice keeps the phone to her ear). Otherwise whole the conversation with "add one to it" makes no sense if Alice can hear the "eight".

If Eve eavesdrops on the phone line, then there is no way which could work without complicate encryption (as said, not suitable to "mental" calculus) or without some previous arrangement between Alice and Bob.

[axn]

Originally Posted by Flatlander

(Now if Alice says for example "add eight to that digit" then Eve will know the correct digit is 8 or 9.)

Not if they work modulo 10. In which case, bob's guesses constitute a one-time pad.

[TheMawn]

Originally Posted by axn

Not if they work modulo 10. In which case, bob's guesses constitute a one-time pad.

+1

If Alice and Bob are comfortable with Mod functions, she could ask for any number between 20 and 100 and say, for example, Mod 13, plus 3.

[TheMawn]

Or square it and add/subtract blah, take last digit.

[Batalov]

Originally Posted by TheMawn

Or square it and add/subtract blah, take last digit.

Won't work. Try squaring the ten digits and add/subtract blah, take last digit, and observe the result. Then tell us if this is a reversible function. Hint: it is not.

[LaurV]

Why does it have to be reversible?

Why is ANY complicated calculus better then a simple "add 1" or "substract 2" (mod 10) ???

All the thing relies on the fact that Eve does *NOT* hear Bob saying "8".

In this case, any calculus is as good as any other. Alice can say "subtract 3 and get the first digit", or she can say "square it, (mod 10 or not) add 1" bla bla, (both will give a "5") or "do some integrals and differentials with it, apply Nernst Transformation, bla bla", it makes NO DIFFERENCE...

If Eve hears Bob saying "8", again, it makes no difference what calculus is used, Eve is as clever as Bob and can do integrals fast in her head... You are all misogynists, and don't want poor Eve to know the pin code...

[axn]

Simple example. PIN to be conveyed: 7891. Conversation (excluding fluff) goes like this:

Bob: Four
Alice: Three (Bob does 4+3 = 7)
Bob: Six
Alice: Two (Bob does 6+2 = 8)
Bob: Zero
Alice: Nine (Bob does 0+9 = 9)
Bob: Seven
Alice: Four (Bob does 7+4 = 1)

OTP: 4607 (Eve doesn't know)
Encrypted Text: 3294 (Eve does know)

Without knowing the OTP, you can't decrypt.

EDIT:- http://en.wikipedia.org/wiki/One-time_pad

[science_man_88]

Originally Posted by axn

Simple example. PIN to be conveyed: 7891. Conversation (excluding fluff) goes like this:

Bob: Four
Alice: Three (Bob does 4+3 = 7)
Bob: Six
Alice: Two (Bob does 6+2 = 8)
Bob: Zero
Alice: Nine (Bob does 0+9 = 9)
Bob: Seven
Alice: Four (Bob does 7+4 = 1)

OTP: 4607 (Eve doesn't know)
Encrypted Text: 3294 (Eve does know)

Without knowing the OTP, you can't decrypt.

EDIT:- http://en.wikipedia.org/wiki/One-time_pad

when do they talk about addition being the operation to use ? this assumes that she can't here the other side.

[Mini-Geek]

Originally Posted by science_man_88

when do they talk about addition being the operation to use ? this assumes that she can't here the other side.

They can talk freely about addition mod 10 being the algorithm to use, his example just excluded "fluff" like that. They could explain the whole scheme to Eve in detail if they want. As long as Eve can only hear Alice's side of the conversation, the encryption works.