Re: How much is Alice worth to Bob?
From: Nicol So (anonymous_at_no.spam.please)
Date: 03/28/04
- Next message: privacy.at Anonymous Remailer: "Sassaman remop, make your SPONSORING public"
- Previous message: privacy.at Anonymous Remailer: "Sassaman remop, make your SPONSORING public"
- In reply to: David Wagner: "Re: How much is Alice worth to Bob?"
- Next in thread: David Wagner: "Re: How much is Alice worth to Bob?"
- Reply: David Wagner: "Re: How much is Alice worth to Bob?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Sun, 28 Mar 2004 13:31:08 GMT
David Wagner wrote:
>>>Alice holds a n-bit string X. Bob holds some string S that is known
>>>to differ from X in at most d bit positions, where d is significantly
>>>smaller than n. Alice doesn't know S, and Bob doesn't know X, but they
>>>both know d and n. How can Alice communicate X to Bob using as few bits
>>>as possible?
>
> Note that your protocol is interactive. You might find it fascinating to
> learn that it is possible to build an elegant protocol that also achieves
> (asymptotically) the same performance, but without any interaction
> (Alice sends a single message to Bob, and that is all). Alice doesn't
> need to know S; just knowing that Bob knows S is as good as knowing S.
> I find that seriously mind-blowing.
How about this: Alice hashes X down to ceiling(m) + k bits using a
suitable hash function and send the value to Bob. 'm' is the number of
bits needed to encode C(n,0) + C(n,1) + ... + C(n,d) possibilities, and
'k' is a chosen amount of redundancy.
Starting from S, Bob checks all strings at Hamming distance d or less
from S, based on their hash values. The amount of redundancy, as
determined by k, affects the probability of Bob encountering a false
positive.
I handwaved a little with the hash function. In the worst case, Alice
can use a randomly chosen member of a universal class of hash functions
and communicate her choice to Bob, at additional bit expense.
-- Nicol So Disclaimer: Views expressed here are casual comments and should not be relied upon as the basis for decisions of consequence.
- Next message: privacy.at Anonymous Remailer: "Sassaman remop, make your SPONSORING public"
- Previous message: privacy.at Anonymous Remailer: "Sassaman remop, make your SPONSORING public"
- In reply to: David Wagner: "Re: How much is Alice worth to Bob?"
- Next in thread: David Wagner: "Re: How much is Alice worth to Bob?"
- Reply: David Wagner: "Re: How much is Alice worth to Bob?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
