Re: Variation on prisoners dilemma


On Wed, 3 May 2006, Arthur J. O'Dwyer wrote:
On Wed, 4 May 2006, Phil Carmody wrote:
"Arthur J. O'Dwyer" <ajonospam@xxxxxxxxxxxxxx> writes:
But I have it on good authority that the corresponding problem in
the digital domain --- where Alice and Bob have two secrets they want
to exchange simultaneously, and can't resort to pulling on loops of
string --- is totally insoluble.)

Non-cryptographic idea for Alice and Bob exchanging 2 secret bits:

They each have two coins, a heavy '1' coin and a light '0' coin,
otherwise indistinguisahble. They slide one coin, corresponding to
their secret bit down a tube into the same pan of a balance.
They then slide the other coin into the other pan.

No information is revealed until the 4th coin reaches the pan.

Wow. How do you come up with these so quickly? :-O I do believe
that works.

Oh... except for the scenario in which Bob cheats by putting a random
coin in the pan, instead of the one corresponding to his "secret." He
learns Alice's secret, but Alice learns only the value of Bob's random
coin: nothing useful!
So I take back my praise of its security. But it's still a neat trick.

Which brings us to a big difference between exchanging real-life secrets
and exchanging single bits --- real-life secrets contain actual
information. For example, Bob could be giving Alice the factors of a
large number: that's something Alice can verify. If Bob gives Alice the
wrong coin, Alice won't find out that Bob cheated until /after/ Bob
has learned Alice's secret (if ever!).

In other words: To be useful, the coins-and-balance method must be
able to securely exchange /verifiable solutions to hard problems/, not
just bits or even big numbers (since Bob can make up an information-free big number just as easily as he can make up a single information-free
bit).

-Arthur
.

Relevant Pages

  • Re: Variation on prisoners dilemma
    ... the digital domain --- where Alice and Bob have two secrets they want ... They each have two coins, a heavy '1' coin and a light '0' coin, ... their secret bit down a tube into the same pan of a balance. ... learns Alice's secret, but Alice learns only the value of Bob's random ...
    (rec.puzzles)
  • Re: privacy amplification
    ... >> I understand that Bob and Alice randomly select a compression function ... >> gwhere W is the input string. ... she will be unable to deduce the secret K from the ...
    (sci.crypt)
  • Re: Truncated multiplication (is it secure???)
    ... | secret in Diffie-Hellman. ... But what if in the XEVRON scheme Eve ... Alice and Bob to choose an insecure "Sh"? ...
    (sci.crypt)
  • Re: QC-proof cipher?
    ... What has keeping a secret to do with authentication? ... In this case Bob gives Alice a secret - in order to authenticate herself to ... Bob at a later time, Alice proves that she knows the secret. ...
    (sci.crypt)
  • Re: Variation on prisoners dilemma
    ... They each have two coins, a heavy '1' coin and a light '0' coin, ... their secret bit down a tube into the same pan of a balance. ... learns Alice's secret, but Alice learns only the value of Bob's random ... Bob could have just picked ...
    (rec.puzzles)