Puzzle Time
The women of Delta Epsilon were a popular bunch, but a smart bunch too--smart enough to want more from the dating scene at their state U. First of all they were sick of that determined, smooth-talking type, the guy who'd hit on one sorority sister after another until one finally expressed an interest--unaware, perhaps, that she was number seven on his list.
Then, too, there were those shy, sensitive boys out there (frequently mathematicians); this kind of guy could be a real mensch, but it took him forever and a day to declare his affections.
The first type was learning too much about the feelings of women he didn't really care for; the second type was held back by his own fear of self-disclosure. It seemed clear that, in principle, both problems could be solved by a single mechanism: some way for a particular boy to inquire about one, and only one, sister's feelings about him (presumably his favorite; and we assume her feelings can be sumarized as like/dislike), without the sisters learning whom he asked about.
There was no third party on campus the sisters trusted to help carry out this function, and it seemed like a pipe dream. But one day, one of them read an intruiging ad for a company called Discreet Dachshunds, Inc. An inquiry revealed that they sold dogs trained in a special skill: their owner could whisper 'yes' or 'no' into each of the dog's ears, and then send it into another room to meet with a visitor. The visitor could reach out to shake the dog's left or right paw (visitor's choice); the dog would shake its head yes or no to repeat to the visitor what had been whispered into its corresponding ear by the owner. After one such transaction, the dog would scamper back to its owner, immediately forgetting what had transpired.
This dog would be perfect if there were only two sorority sisters, A and B: if a boy wanted to make a discreet inquiry, A would whisper her feelings about him into the dog's left ear, while B used the right ear, and the boy could learn exactly one of these pieces of information in his session with the dog.
However, Delta Epsilon had a sizeable and growing membership. The sisters asked about dogs capable of carrying more information at once, but Discreet Dachshunds replied that sadly, two bits was the upper limit with these animals--and anyways, dogs have only two paws for shaking.
Nevertheless, after careful deliberation, the sisters bought a dachshund from the company and used it cleverly to implement their system. They reaped the romantic benefits, and the dog was treated like royalty.
How did they do it?
Notes
i) Apologies for heteronormativity.
ii) I'm not sure how difficult readers will find this puzzle. A 3-woman sorority is the place to start experimenting.
iii) The dachshund in this puzzle corresponds to a functionality called '1-out-of-2 oblivious transfer (OT)' in the cryptographic literature; the result alluded to by the puzzle is '1-out-of-2 OT simulates 1-out-of-k OT'. In fact, OT can do much, much more than this, composing to form more complex cryptographic protocols in much the way {AND, OR, NOT} compose to form all boolean functions; and complexity theory offers hypotheses under which it's possible to do OT without the dog. See the Wiki page for history and references.
Extra credit 1: The sisters decide that instead of like/dislike, they need to express their feelings about a guy using b > 1 bits each. Once again, he can only learn about one sister's feelings, the others must be completely inviolate. Of course, the dog's abilities are unchanged.
Extra credit 2: Best physical realization of the OT mechanism? Quantum mechanics offers one, but that's cheating.
Then, too, there were those shy, sensitive boys out there (frequently mathematicians); this kind of guy could be a real mensch, but it took him forever and a day to declare his affections.
The first type was learning too much about the feelings of women he didn't really care for; the second type was held back by his own fear of self-disclosure. It seemed clear that, in principle, both problems could be solved by a single mechanism: some way for a particular boy to inquire about one, and only one, sister's feelings about him (presumably his favorite; and we assume her feelings can be sumarized as like/dislike), without the sisters learning whom he asked about.
There was no third party on campus the sisters trusted to help carry out this function, and it seemed like a pipe dream. But one day, one of them read an intruiging ad for a company called Discreet Dachshunds, Inc. An inquiry revealed that they sold dogs trained in a special skill: their owner could whisper 'yes' or 'no' into each of the dog's ears, and then send it into another room to meet with a visitor. The visitor could reach out to shake the dog's left or right paw (visitor's choice); the dog would shake its head yes or no to repeat to the visitor what had been whispered into its corresponding ear by the owner. After one such transaction, the dog would scamper back to its owner, immediately forgetting what had transpired.
This dog would be perfect if there were only two sorority sisters, A and B: if a boy wanted to make a discreet inquiry, A would whisper her feelings about him into the dog's left ear, while B used the right ear, and the boy could learn exactly one of these pieces of information in his session with the dog.
However, Delta Epsilon had a sizeable and growing membership. The sisters asked about dogs capable of carrying more information at once, but Discreet Dachshunds replied that sadly, two bits was the upper limit with these animals--and anyways, dogs have only two paws for shaking.
Nevertheless, after careful deliberation, the sisters bought a dachshund from the company and used it cleverly to implement their system. They reaped the romantic benefits, and the dog was treated like royalty.
How did they do it?
Notes
i) Apologies for heteronormativity.
ii) I'm not sure how difficult readers will find this puzzle. A 3-woman sorority is the place to start experimenting.
iii) The dachshund in this puzzle corresponds to a functionality called '1-out-of-2 oblivious transfer (OT)' in the cryptographic literature; the result alluded to by the puzzle is '1-out-of-2 OT simulates 1-out-of-k OT'. In fact, OT can do much, much more than this, composing to form more complex cryptographic protocols in much the way {AND, OR, NOT} compose to form all boolean functions; and complexity theory offers hypotheses under which it's possible to do OT without the dog. See the Wiki page for history and references.
Extra credit 1: The sisters decide that instead of like/dislike, they need to express their feelings about a guy using b > 1 bits each. Once again, he can only learn about one sister's feelings, the others must be completely inviolate. Of course, the dog's abilities are unchanged.
Extra credit 2: Best physical realization of the OT mechanism? Quantum mechanics offers one, but that's cheating.
posted by Andy D at
12:20 AM
0 Comments:
Post a Comment
<< Home