Re: How much is Alice worth to Bob?
From: Nicol So (anonymous_at_no.spam.please)
Date: 03/28/04
- Next message: Colin Andrew Percival: "Re: Factorization: a new algorithm??"
- Previous message: Barry Fawthrop: "Re: MD5 Cracking"
- 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 03:29:27 GMT
David Wagner wrote:
> Nicol So wrote:
>
>>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?
>>
>>Alice and Bob split their strings into two segments of (almost) equal
>>length, according to an implicit rule. [...] If the
>>hash value of a segment of X matches that of its counterpart in S, Alice
>>assumes the two corresponding segments are identical. Alice recursively
>>applies the procedure to the mismatching segements until all d differing
>>positions are located.
>
> Ahh, yes, I see. I hadn't noticed this solution before. Very nice.
>
> Your approach requires O(n lg(n/d)) bits of communication. You may find
> it interesting to compare to the (trivial) case where both Alice and Bob
> know S. In the trivial case, there are C(n,d) = n!/d!(n-d)! possibilities
> for X, and Alice can just send an index into that set, so lg C(n,d) bits
> are enough. If we only care about the asymptotics, we have lg C(n,d)
> ~ n lg(n/d) + lower order terms. This is at most a constant factor
> smaller than your protocol. Hence, you've shown that Alice can transmit
> X just about as efficiently without knowing S as if she did know S.
> Pretty cool, eh?
That's an interesting observation. I think I'd point out that the two
cases differ not only in Alice's knowledge of S, but also in the error
probability.
> 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.
Fascinating.
After you told me that it's possible, a plausible solution strategy
based on error-correcting codes came to mind. I haven't worked out a
complete solution yet (so I don't know if it really works), but I find
it much easier to imagine a non-interactive solution now.
-- Nicol So Disclaimer: Views expressed here are casual comments and should not be relied upon as the basis for decisions of consequence.
- Next message: Colin Andrew Percival: "Re: Factorization: a new algorithm??"
- Previous message: Barry Fawthrop: "Re: MD5 Cracking"
- 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
|
