[freehaven-cvs] r1771: Expanded examples, added the multiuser case (doc/trunk/pynchon-gate/bp-ringstwice)

[mlp@xxxxxxxx]

Author: mlp
Date: 2007-04-05 02:35:25 -0400 (Thu, 05 Apr 2007)
New Revision: 1771

Modified:
   doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex
Log:
Expanded examples, added the multiuser case


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-05 03:51:50 UTC (rev 1770)
+++ doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex	2007-04-05 06:35:25 UTC (rev 1771)
@@ -77,7 +77,7 @@
 
 \section{Example}
 
-\subsection{Subliminal channels in a Chor et al. PIR Service}
+\subsection{A simple subliminal channel in a Chor et al. PIR Service}
 Let us examine the simple \textsc{xor}-based PIR scheme presented in the seminal paper on PIR~\cite{pir}, and observe the potential for covert communication between nodes in a multiple-server PIR system.
 
 Suppose there are three servers: an honest server $A$ and Byzantine servers $B$ and  $C$ in collusion. 
@@ -111,7 +111,53 @@
 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$).
 
 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?
+
+Of course, 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.
+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.
+
+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.
+
+A worse problem, however, is the fact that each colluding server can only transmit a bit when its mark performs a \textsc{pir} request.
+In protocols like the Pynchon Gate~\cite{pynchon}, requests are rate-limited to a fixed number per cycle in order to reduce the effectiveness of long-term intersection attacks and other forms of traffic analysis.
+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?
+
+\subsection{Subliminal channels in Byzantine-robust PIR}
+
+
+\section{Byzantine-robustness among the Byzantines}
+
+This approach requires all colluding servers to be \emph{faithful} to each other, i.e., not interfere with other servers' marks and not alter the data they send to users beyond their manipulation of the request string.
+A Byzantine shill can produce spurious signals from $S_i$ by neglecting to flip its prearranged bits in a request from $M_i$, or by flipping random bits in the bit-string or the data sent to $M_i$.
+Furthermore, a Byzantine (or merely malfunctioning) server outside the colluding group can also produce a spurious signal.
+If the only means of determining whether a signal has been sent is whether a mark's request succeeds or fails, then if all colluding servers flip their bits as arranged and a server outside the group takes a Byzantine action, the mark will still have to retry its request or perform a \textsc{hard-recover} action, thus the mark's behaviour will indicate that a signal was sent.
+
+However, although servers within a collusion group should technically be considered Byzantine with respect to the \textsc{pir} system as a whole, the behaviour of faithful colluding servers differs from Byzantine servers outside a collusion group, and this behaviour lends itself to differentiation.
+
+%So, the general idea here is that Byzantine servers who are just looking to mess with someone's data are probably just going to flip a bit in whatever they send back to the user, whereas faithfully colluding servers will only flip bits in the bit-string. So, every response that a faithfully colluding server sends to a user is a valid XOR of some set of buckets. 
+
+%Two problems with this, though:
+%1. Nothing prevents a non-colluding Byzantine server from responding with a valid XOR of some set of buckets other than what the user had requested.
+%2. This doesn't help us detect a faithless colluding server, because a faithless colluding server can still send back the wrong buckets XORed together and cause a request to fail. 
+
+%(Also: What do we do about the scenario where two groups are using this channel and their set of marks overlaps? Collision becomes a problem again.)
+
 \section{Conclusion}
 
 \paragraph{Acknowledgements} 

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