Q: reliable estimate of message loss probability
mockturtle
Dear all,
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
undesirable.
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.
Thank you
R.B.
Ben Goldberg
On Feb 14, 8:19=A0am, mockturtle <framefri...@gmail.com> wrote:
> Dear all,
>
> I stumbled across the following problem. =A0Before 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 probabil=
ity
> that Bob receives a message. =A0The easiest solution is to ask Bob, but A=
lice
> does not trust Bob since Bob has some interest in lying by claiming a lar=
ger
> reception probability. =A0(Explaining why Bob could want to do such a thi=
ng
> would take us too far...)
>
> A possibility for Alice to be sure about the answer of Bob is to add to e=
ach
> message M_n a random b-bit number C_n. =A0Bob, in his reply, will include=
a list
> of the number of the received messages together with the XOR of the
> corresponding C_n values. =A0This works fine, but it requires to Bob addi=
tional
> bandwidth for sending back the message list and requires to Alice to keep=
the
> list of past C_n values. =A0Depending on the applicative context, this co=
uld be
> undesirable.
Start with Alice sending those messages, along with those random b-bit
numbers,
to Bob.
Whenever Alice wants to know how many messages got through to Bob, she
sends him
a challenge; the challenge consists of a randomly selected subset of
the indices
of all of the messages. Bob's response is a list of which messages
specified by
the challenge he has received, together with the XOR of the
corresponding C_n
values.
As in your original scheme, Bob can't claim to have gotten a message
that he didn't.
Alice doesn't know the precise fraction of messages Bob received in
total, but
she does know the fraction of messages specified in her challenge that
Bob
received. Since Alice knows how many messages she sent, and how many
were
asked about in the challenge, she can calculate the statistical
significance
of the Bob's response.
So Alice might send a billion messages, then a challenge consisting of
a thousand
randomly selected message indices. Bob sends back the list of nine
hundred
indices of the messages he got, with that XOR, and thus Alice knows
that he's
getting 90% of the messages with X% probability.
(I don't know enough about statistics to calculate X.)
Ilmari Karonen
On 2011-02-14, mockturtle <frame...@gmail.com> wrote:
>
> 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.
It's not a well known problem to me, but that doesn't really tell
anything except that I'm not a professional cryptographer.
Hmm... one simple approach would be for Alice to send a C_n value for
only some fraction of the messages. As long as Bob can't choose which
messages he receives, Alice can be fairly sure that if, say, she sends
100 marked messages and 9900 unmarked ones, and Bob confirms receiving
10 of the marked messages, then he's probably also received around 990
of the unmarked ones.
Another idea that comes to my mind would be to use Shamir's secret
sharing. If Alice picks a random secret and includes one k-th order
share of it in each message, Bob will only be able to send back the
correct secret if he's received at least k messages.
Of course, this means that Alice needs to pick the threshold k
_before_ sending the messages (although she could always include
several shares, with different thresholds and secrets, in each
message). Still, this might be sufficient for some scenarios.
Note that, in this scheme, Alice doesn't actually have to tell Bob
what the threshold is, although Bob will have a pretty good change of
guessing whether he's received more than k messages or not based on
the order of the polynomial he gets. Still, it means that, if Alice
chooses k somewhat randomly, Bob can't always safely claim to have
received exactly k-1 messages.
--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
Peter Fairbrother
mockturtle wrote:
> Dear all,
>
> 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.
Don't know of a name for your problem, but take a look at anonymous
digital cash, it's very similar - Bob wants to convince Alice (or the
bank) that he has lots of tokens, and Alice wants to be sure the ones
she accepts are all real.
-- Peter Fairbrother
Greg Rose
In article <8rsof6...@mid.individual.net>,
mockturtle <frame...@gmail.com> wrote:
>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...)
Have a look at Rivest's "Peppercoin" system for
micropayments. While not directly relevant, it may
help you think in the right direction.
Greg.