Reducing set cover to finding good adversaries

This web page illustrates a construction described in the paper "On the Security of Protocols with Logarithmic Communication Complexity" by Michael Backes and Dominique Unruh, namely how to construct an adversary-polytope that is an $\varepsilon$ -set cover polytope. If you have not read that paper, this page will probably not be self-explanatory.

All figures in this example are interactive. Use the mouse to rotate them.

We consider two set cover instances. The first instance (in the following called instance I) has the parameters $n:=3$ , $m:=3$ , $d:=2$ and the sets $S_1:=\{1,2\}$ , $S_2:=\{2,3\}$ and $S_3:=\{1\}$ . In other words, we are asked to choose two sets from $S_1,S_2,S_3$ such that their union is $\{1,2,3\}$ . Obviously this instance has two witnesses, namely $S_1\cup S_2$ and $S_2\cup S_3$ .

The second instance (in the following called instance II) differs from instance I only by having $d:=1$ . So in this case we have to choose one set out of $S_1,S_2,S_3$ such that set already contains all elements $\{1,2,3\}$ . Obviously, this is impossible, so instance II is a no-instance.

A yes-instance

Let us first consider instance I. We assume that we already succeeded in constructing protocols $\pi_D$ , $\pi_{S^1}$ , $\pi_{S^2}$ , and $\pi_{S^3}$ , that have the adversary-polytopes $D$ , $S^1$ , $S^2$ and $S^3$ . Here $D:=\{v\in[0,1]^3:\lVert v\rVert _1\leq 2\}$ corresponds to the condition that at most $d=2$ sets may be selected. Further, we have $S^1:=\{v\in[0,1]^3:v_1+v_3\geq 1\}$ representing the requirement that to cover the element $1$ we have to include set $S_1$ or set $S_3$ . It is $S^2:=\{v\in[0,1]^3:v_1+v_2\geq 1\}$ , since to cover the element $2$ we need to include set $S_1$ or $S_2$ . And finally $S^3:=\{v\in[0,1]^3:v_2\geq 1\}$ since to cover the element $3$ we need to include the set $S_2$ .

The polytopes $D$ , $S^1$ , $S^2$ , $S^3$ are shown in the following figures. Each polytope is embedded into a transparent unit cube $[0,1]^3$ so that the dimensions of the polytopes are clear.

$D$	$S^1$
$S^2$	$S^3$

We are now going to combine these four polytopes into an $\varepsilon$ -set cover polytope for instance I. In the paper, $\varepsilon:=\frac1{nm+1}=\frac1{10}$ is used. However, for illustration purposes we choose $\varepsilon:=\frac15$ since for this value the details of the pictures are easier to see.

According to the paper, by setting $P_\varepsilon:=(1-3\varepsilon)D+\varepsilon S^1+\varepsilon S^2+\varepsilon S^3$ we get an $\varepsilon$ -set cover polytope. Then we can easily construct a protocol $\pi$ such that the adversary-polytope of $\pi$ is $P_\varepsilon$ : The protocol $\pi$ chooses an $i\in\{0,1,2,3\}$ . The probability for $i=0$ is $1-3\varepsilon$ , the probability for $i=1,2,3$ is $\varepsilon$ each. Then $i$ is sent to the adversary and the for $i=1,2,3,4$ the protocol $\pi_D,\pi_{S^1},\pi_{S^2},\pi_{S^3}$ is executed, respectively (this construction was called the sum-construction in the paper).

We will now examine the resulting polytope $P_\varepsilon$ . The scaled polytopes $(1-3\varepsilon)D$ , $\varepsilon S^1$ , $\varepsilon S^2$ , and $\varepsilon S^3$ are depicted in the following figures:

$(1-3\varepsilon)D$	$\varepsilon S^1$
$\varepsilon S^2$	$\varepsilon S^3$

The sum $P_\varepsilon$ of these polytopes looks as follows (we urge the reader to examine this figure in detail and try to understand why the sum $P_\varepsilon$ has the form it has):

The definition of an $\varepsilon$ -set cover polytope was approximately that $P_\varepsilon$ should be contained in the unit cube $[0,1]^3$ , and that the vertices that $P_\varepsilon$ has in common with the unit cube $[0,1]^3$ correspond to the witnesses of the set cover instance.

In our case, it is easy to see that $P_\varepsilon$ is contained in the unit cube (depicted transparently in the previous figure). Furthermore, the only vertices $P_\varepsilon$ has in common with the unit cube are, as an inspection of the figure shows, at the coordinates $(1,1,0)$ and $(0,1,1)$ . The first of these vertices has bits $1$ and $2$ set, which corresponds to the witness $S_1\cup S_2$ . The second vertex has bits $2$ and $3$ set, corresponding to the witness $S_2\cup S_3$ . As seen above, these are exactly the witnesses of instance I.

We now try to identify these vertices with good adversaries. Let $\varrho$ be a protocol whose adversary-polytope has the form $X:=\{v\in\mathbb{R}^3:\lVert v\rVert _1\leq \frac n2-\delta\}+(\frac12,\frac12,\frac12)$ for a suitably chosen $\delta>0$ . Then $X$ has the following form (where we chose $\delta:=\frac15$ ):

$X$

We included the unit cube $[0,1]^3$ in the previous figure to show the size of $X$ . Note that the unit cube's vertices (and a neighbourhood of size $\delta$ of these vertices) look out of $X$ , but the rest of the cube is hidden within $X$ . So if we overlay $X$ with $P_\varepsilon$ , we may expect (if we chose a small enough $\delta$ ) that only those vertices of $P_\varepsilon$ look out of $X$ that coincide with vertices of the unit cube. This can be verified in the following figure:

$P_\varepsilon$ and $X$

Thus the only vertices of $P_\varepsilon$ that look out of $X$ are the vertices $(1,1,0)$ and $(0,1,1)$ which--as we saw above--correspond to the witnesses of instance I. An adversary $A$ is good for $(\pi,\varrho)$ if and only if the distribution $\mu$ of $\pi$ when running with $A$ lies outside the adversary-polytope $X$ of $\pi$ . So given a good adversary $A$ , we simply sample $\mu$ and get a point near $(1,1,0)$ or near $(0,1,1)$ . By rounding the coordinates of that point, we get one of the witnesses of instance I.

A no-instance

For comparison, we now examine instance II. Since $n,m$ and the sets $S_1,S_2,S_3$ are the same as with instance I, the polytopes $S^1,S^2,S^3$ for instance II are the same as those for instance described above. However, since with instance II we have $d=1$ , i.e., we may choose only one set to cover $\{1,2,3\}$ , the polytope $D$ now has a different definition: $D:=\{v\in[0,1]^3:\lVert v\rVert _1\leq 1\}$ (for instance I we have $\lVert v\rVert _1\leq 2$ and not $\lVert v\rVert _1\leq 1$ ). The following figure shows the polytope $D$ :

$D$

Using again $\varepsilon:=\frac15$ , we get the following scaled polytopes $(1-3\varepsilon)D$ , $\varepsilon S^1$ , $\varepsilon S^2$ , and $\varepsilon S^3$ which are depicted in the following figures:

$(1-3\varepsilon)D$	$\varepsilon S^1$
$\varepsilon S^2$	$\varepsilon S^3$

The sum of these polytopes gives us the following polytope $P_\varepsilon$ :

$P_\varepsilon$

We notice that this time, although the border of $P_\varepsilon$ touches the border of the unit cube $[0,1]^3$ in many places, no vertex of $P_\varepsilon$ coincides with the vertices of the unit cube. This corresponds to the fact that instance II is a no-instance of set cover and therefore has no witnesses.

If we again construct $\varrho$ as above to have the adversary-polytope $X:=\{v\in\mathbb{R}^3:\lVert v\rVert _1\leq \frac n2-\delta\}+(\frac12,\frac12,\frac12)$ and overlay $X$ with $P_\varepsilon$ , we get the following result:

$P_\varepsilon$ and $X$

This time, the adversary-polytope $P_\varepsilon$ of the real protocol $\pi$ is completely contained in the adversary-polytope $X$ of the ideal protocol $\varrho$ , so there exists no good adversary. This matches the fact that instance II is a no-instance.