34 views

Skip to first unread message

Feb 14, 2011, 8:19:34 AM2/14/11

to

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.

Feb 18, 2011, 9:54:06 PM2/18/11

to

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.)

Feb 18, 2011, 9:54:35 PM2/18/11

to

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.

Feb 18, 2011, 9:54:57 PM2/18/11

to

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

Feb 19, 2011, 2:39:15 PM2/19/11

to

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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu