2011-02-14 13:19:34 UTC
I stumbled across the following problem. Before trying to solve it by myself
(with the risk of reinventing the wheel), I would like to know if it is a
known problem and, if yes, what is its "standard" name.
The problem is very simple: suppose that Alice sends several messages to Bob.
Some messages can get lost Alice wants to get an estimate of the probability
that Bob receives a message. The easiest solution is to ask Bob, but Alice
does not trust Bob since Bob has some interest in lying by claiming a larger
reception probability. (Explaining why Bob could want to do such a thing
would take us too far...)
A possibility for Alice to be sure about the answer of Bob is to add to each
message M_n a random b-bit number C_n. Bob, in his reply, will include a list
of the number of the received messages together with the XOR of the
corresponding C_n values. This works fine, but it requires to Bob additional
bandwidth for sending back the message list and requires to Alice to keep the
list of past C_n values. Depending on the applicative context, this could be
I would like a scheme where Alice still sends values C_n with each message,
Bob processes the received values C_n to obtain a value K that sends back with
the computed reception probability P. Alice should be able to verify that K
is compatible with P without knowing which messages were actually received. I
have few ideas about this, but before reinventing the wheel I would like to
know if some work about this was already done. Unfortunately, I do not even
know which "name" to "google".
Please note that since Alice wants just an estimate of P, it does not really
matter if Bob "cheats just a bit," that is, it is not a big deal if Bob
received 998 messages out of 10,000 and claims he received 1,000 messages;
however we do not want accept the claim of Bob of receiving, say, 9,000
messages. Of course, it is even better if Alice can get the _exact_ number of
received messages, but in the applicative context of interest even the "fuzzy"
version is OK.