[freehaven-cvs] r1774: expanding section 3 (doc/trunk/pynchon-gate/bp-ringstwice)

[mlp@xxxxxxxx]

Author: mlp
Date: 2007-04-16 03:51:47 -0400 (Mon, 16 Apr 2007)
New Revision: 1774

Modified:
   doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex
Log:
expanding section 3

Modified: doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex
===================================================================
--- doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex	2007-04-06 17:00:45 UTC (rev 1773)
+++ doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex	2007-04-16 07:51:47 UTC (rev 1774)
@@ -5,6 +5,8 @@
 \usepackage{amsmath}
 \usepackage{subfigure}
 \usepackage{epsfig}
+\usepackage{theorem}
+\newtheorem{observation}{Observation}
 
 % Cut down on whitespace above and below figures displayed at head/foot of
 % page.
@@ -122,28 +124,73 @@
 
 The \textsc{xor} of all three vectors, and thus the \textsc{xor} of the returned data, still unveils the contents of $b_1$. 
 More than two servers can collude in this fashion, although an odd number of colluding servers must flip bits for at least two buckets (e.g., $B$ and $C$ flip bits for bucket $j$ while $C$ and $D$ flip bits for bucket $k$).
+Observe that if it is desirable for each server to have a uniquely identifying set of bits to flip, then the length of the string describing which bits are flipped and which ones are not must be sufficiently long.
+In particular:
+\begin{observation}[Lower bound on flipped-bit string lengths]
+\label{obs-bound}
+If there are $n$ colluding servers, then the length of $B_n$, the set of bits which an individual server will flip or not flip, is bounded such that $|B_n| > \lceil \lg n \rceil$.
+\end{observation}
+\begin{proof}
+First, note that in order to assign a unique bitstring to each server, each string must be at least $\lceil \lg n \rceil$ bits long, otherwise there will be overlap.
+But it is not enough that the bitstrings be unique: they must also \textsc{xor} to the all-zero string.
+No server can be assigned an all-zero bitstring (otherwise, that server would be instructed to never flip any bits whether it was transmitting or not, and thus could never transmit anything).
+Thus there are actually $2^{\lceil \lg n \rceil} - 1$ strings from which to choose if each string is $\lceil \lg n \rceil$ bits long.
+If $n$ is a power of 2, then each bitstring \emph{must} be at least $(\lceil \lg n \rceil) + 1$ bits long, otherwise at least one string will have to overlap.
 
+Furthermore, suppose that $n = 2^{\lfloor \lg n \rfloor} + 1$. 
+Define the \emph{parity string} for each bit in the set of $n$ bitstrings as $P_m = B_{1m} \cdot B_{2m} \cdot \ldots \cdot B_{nm}$, where $m$ is the position of the bit.
+For example, the parity strings for the set of all 3-bit strings in increasing order, less the all-zero string, are $\{0001111\}, \{0110011\}, \{1010101\}$.
+In order for all $n$ strings to \textsc{xor} to 0, the result of \textsc{xor}ing the bits of each parity string must also be 0; this will always be the case when examining the parity strings for all $2^m$ strings of $m$ bits.
+There will be $m-1$ parity strings of parity 0 for $2^{m-1}$ strings (including the all-zero string); adding another string to the set requires the $m$th bit and thus the $m$th parity string. 
+In order to not throw off the first $m-1$ parity strings, the first $m-1$ bits of the $n$th string must be 0.
+However, an $m-1$-bit string of 0s is already present in the $n-1$ strings already selected.
+Since an $m$-bit all-zero string cannot be present, both the already-present string and the $n$th string being added must have a 1 as their $m$th bit, but then a string has been duplicated.
+It is further impossible to manipulate the set of $m$-bit strings such that the $m$ parity strings are all of parity 0.
+\end{proof}
+
 Through this channel, colluding servers could communicate potentially sensitive information even if the network channel were monitored for such communication.
 When one server flips its prearranged bit(s) and another does not, the data which the user retrieves consists of more than one bucket \textsc{xor}ed together, and thus in the case of non-Byzantine-robust \textsc{pir} protocols, the user must make another attempt to retrieve his data.
 (Byzantine-robust \textsc{pir} systems are discussed below.)
 Colluding servers can therefore use the user as an oracle which reveals the transmission of a single bit: if the user's request succeeds, a 0 has been transmitted, and if the request fails, a 1 has been transmitted.
 
-%Dead-man switch stuff here?
-
 One might ask why colluding servers would prearrange a set of bits to flip, as this is an additional step.
-Indeed, 
+Indeed, if all servers preserve the original bit-string to communicate a 0 and change a random bit to communicate a 1, the same effect is preserved.
+However, prearranging the flipped bits provides for some security against outside tampering: if the presence of servers using this channel has been detected by an adversary who subsequently changes the responses of one or more other servers to correct for the responses sent by the colluding servers, it will be easier for the colluding servers to detect this if they already know what variations to expect from the other parties on the subliminal channel. 
+In effect, the search space for the origin of an error decreases significantly when the set of flipped bits is prearranged.
+Later, when we address the multi-party use case, we will also demonstrate how a prearranged set can quickly pinpoint the identity of a malfunctioning or inoperative server within the channel participants.
 
-Of course, if multiple colluding servers attempt to transmit simultaneously, they are guaranteed to fail in the case of a two-party collusion.
+\subsubsection{A simple use-case: the dead-man switch}
+Suppose that $N$ individuals living in a police state are unable to communicate regularly without fear of letting the authorities know that they are in communication. 
+They all wish to keep the others apprised of their safety, so they agree to announce their status to one another every day by means of a dead-man switch over the subliminal channel described above. 
+Each participant runs a \textsc{pir} database server modified such that flipping bits is a manual operation (i.e., requires some approval input from the server's operator in order to occur). 
+Suppose that one of the participants is then picked up by the secret police. 
+He will be unable to approve any subsequent bit-flips---in effect, his hand has fallen off the switch---so all subsequent \textsc{pir} queries will fail and the other participants will know that something has happened to one of their number.\\
+
+However, if multiple colluding servers attempt to transmit simultaneously, they are guaranteed to fail in the case of a two-party collusion.
 If $A$ and $B$ both attempt to signal each other by not flipping their prearranged bits, then the user's original set of bit vectors is used unmodified and the user's request succeeds.
-When simultaneous transmissions occur in multi-party collusions, transmission failure is not guaranteed---if $A$ and $C$ are not supposed to flip the same bits, then the \textsc{pir} request fails as planned---but it is also impossible to determine who initiated the transmission.
+When simultaneous transmissions occur in multi-party collusions, transmission failure is not guaranteed---if $A$ and $C$ are not supposed to flip the same bits, and both fail to perform the bit-flip, then the \textsc{pir} request fails as planned---but it is also impossible to determine who initiated the transmission.
 Thus, we extend this approach to remove the possibility of collision and enable colluding servers to identify which party is sending a signal.
 
 \subsection{A multi-party subliminal channel}
 In addition to choosing a set of bits to flip, let each colluding server $S_i$ also choose a particular user $M_i$ from the userbase of the \textsc{pir} system.
 We refer to $M_i$ as the $mark$ for $S_i$, and every $S \in \{S \setminus S_i\}$ as the $shills$ for $S_i$.
 Server $S_i$ will always perform its bit-flip operation for every $M_j \in \{M \setminus M_i\}$, and will fail to flip a bit in its mark's request when $S_i$ wants to transmit a 1.
-$S_i$'s shills receive $S_i$'s signal by observing $UM_i$'s behaviour, as in the single-user case.
+$S_i$'s shills receive $S_i$'s signal by observing $M_i$'s behaviour, as in the single-user case. 
 
+Now, instead of a simple on-off signal shared by all participants in the channel, each server controls a stream of bits. 
+Note, however, that if one participant suddenly drops out of the channel (``falls off the dead-man switch'', as above), then \emph{all} streams will produce failing \textsc{pir} requests, and it will not immediately be evident which server has dropped out.
+We address this problem with a systematic approach for constructing the bit-strings and rotating their usage so that this failure mode can be detected.
+We assume an \emph{atomic broadcast} paradigm for \textsc{pir} requests; that is, for a set of servers $S$ and a set of marks $M$, every server receives the requests from the marks in the same order.
+
+\subsubsection{Failure detection in the multi-party model}
+Note that the \emph{entire} set of flipped bits must \textsc{xor} to the all-zero string so that a normal \textsc{pir} transaction is not interrupted.
+When one colluding server stops communicating, the \textsc{xor} of the remaining participants' strings will contain some 1s and the transaction will fail.
+Thus, we design the sets of bits to flip such that the bitstrings describing these sets can be systematically truncated and rotated through in order to identify the failed server.
+Recall from Observation \ref{obs-bound} that for $n$ servers, each bitstring must be at least $\lceil \lg n \rceil + 1$ bits long.
+
+(describe rotating bitstrings thing here)
+
+
 One drawback to this approach is that every colluding server must observe as many marks as there are colluding servers.
 % I need to read the paper on how this latency stuff is detected, but I suspect the consequence of the observation above is that network traffic increases by a factor of n^2 because of all the extra pings going back and forth.
 
@@ -152,7 +199,7 @@
 If each colluding server can only transmit a few bits per day, the latency of this channel becomes so high as to be useless.
 (Furthermore, since \textsc{pir} requests are user-initiated, a colluding server can be silenced if its mark goes offline for a few days.)
 Fortunately, this problem is easy to address: partition the userbase into sets of marks, such that $S_i$'s set of marks, $M_{S_i}$, is disjoint with $\bigcup M_{S_j}$, $\forall j \neq i$.
-% Oh, but there's a problem here too, related to atomic broadcast. Suppose there are three servers, S1, S2 and S3, and S1 has two marks, M and M'. M and M' start sending PIR requests at the same time. There's no guarantee that the requests will get to S1, S2 and S3 in the same order, so how do S2 and S3 know what the right order to reassemble the bits is?
+% mention atomic broadcast again here?
 
 \subsection{Subliminal channels in Byzantine-robust PIR}
 A \textsc{pir} system which consists of $\ell$ servers, any $k$ of which need to respond to a client's query, is referred to as a $k$-out-of-$\ell$ system.

***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs       in the body. http://freehaven.net/