mockturtle

2011-02-14 13:19:34 UTC

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.

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.