1
$\begingroup$

Given a finite set $\Sigma$ and a positive integer $n$, a mechanism is a set $\{ \mu_x \vert x \in \Sigma^n \}$ such that $\mu_x$ is a probability measure on some $\sigma-$algebra for each $x$.

Now given a communication protocol $P$ between two privately coin-flipping parties $A$ and $B$ who start with the inputs $x$ and $y$ respectively one defines this quantity called the $VIEW^A_P(x,y)$ : ``a joint probability distribution over $x$, the transcript of the protocol $P$, private randomness of the party $A$, where the probability space is private randomness of both parties"

  • What does the stuff in the quotes mean?

  • Can someone help understand how is this $VIEW^A_P(x,y)$ a ``mechanism" as defined earlier? (For this to be a mechanism, $VIEW^A_P(x,y)$ for a fixed $x$, has to assign a probability to some set of outcomes and I am unable to see as to which set of outcomes is it assigning a probability and how)

A transcript of a protocol will be a sequence of private coin tosses and bits exchanged in every step. So if one fixes both $x$ and $y$ then I can imagine that a probability can be assigned to a protocol - which would be the probability for that sequences of coin tosses to have happened. But still whaht is an "event" here is not clear since I can't see a natural way to group together these "outcomes" (each of which is now a possible transcript when started with a $x$ and $y$).

But if one fixes only $x$ then nothing is clear to me..

Reference : http://www.cs.toronto.edu/~toni/Courses/CommComplexity2/Lectures/diffprivacy.pdf

Improve this question
$\endgroup$
1
  • $\begingroup$ The notation suggests that you are fixing both $x$ and $y$. If you're not sure, keep on reading and see how it's used. $\endgroup$
    – Yuval Filmus
    Jul 9, 2015 at 19:58

1 Answer 1

Reset to default
2
$\begingroup$

The view of Alice is what Alice gets to see; it is a probability distribution that depends on the inputs of both players $x,y$. It is a distribution over triples $(x,\tau,r_A)$, where $x$ is Alice's input, $\tau$ is the transcript of the protocol, and $r_A$ is Alice's private randomness. This probability distribution depends both on $x$ and on Bob's input $y$.

Here is how to generate this probability distribution, given a protocol $P$ and the inputs $x,y$ of both players. Generate the shared randomness $r$ according to its distribution, and Alice's private randomness $r_A$ according to its distribution. Run $P$, obtaining a transcript $\tau$. Output $(x,\tau,r_A)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ (1) What do you mean by "generate the shared randomness" ? (2) If I understand you right then what we have is this : $VIEW^A_P$ is a "mechanism" because it gives a family of probability distributions $\mu_y$ indexed by the string $y$ that $B$ has. And $\mu_y$ assigns a probability to the "outcomes" indexed by the triples $(x,\tau,r_A)$ which are consistent with $A$ and $B$ starting with $x$ and $y$ respectively. Am I right? $\endgroup$
    – user6818
    Jul 10, 2015 at 22:03
  • $\begingroup$ (1) Toss an infinite sequence of coins, which will be used as the shared randomness. (2) You might be right, though the notation suggests that VIEW is a function of both $x$ and $y$. On the other hand, since $x$ is part of the domain, your interpretation also makes sense. $\endgroup$
    – Yuval Filmus
    Jul 10, 2015 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.