[freehaven-cvs] r1777: finished section 2 entirely (doc/trunk/pynchon-gate/bp-ringstwice)

[mlp@xxxxxxxx]

Author: mlp
Date: 2007-04-17 08:47:00 -0400 (Tue, 17 Apr 2007)
New Revision: 1777

Modified:
   doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex
Log:
finished section 2 entirely

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-16 12:48:23 UTC (rev 1776)
+++ doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex	2007-04-17 12:47:00 UTC (rev 1777)
@@ -124,6 +124,7 @@
 
 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]
@@ -184,22 +185,60 @@
 
 \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.
+When one colluding server stops communicating, the \textsc{xor} of the remaining participants' strings will contain some 1s and all subsequent transactions will fail.
+Since each server has a mark allocated to it, however, a server can easily identify that queries for which it did not intend to transmit a 1 are failing anyway.
 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.
+Again, an atomic broadcast paradigm is assumed.
+\begin{example}[A three-party approach]
+For servers A, B and C, assign the initial set of strings describing which bits to flip as follows: \\
 
-(describe rotating bitstrings thing here)
+\begin{tabular}[c]{|c|ccc|}
+\hline
+$A$ & 1 & 1 & 0 \\
+\hline
+$B$ & 1 & 0 & 1 \\
+\hline
+$C$ & 0 & 1 & 1 \\
+\hline
+\end{tabular} \\
+(In this example, buckets beyond the third are disregarded.)
 
+For the first \textsc{pir} query that the servers receive, each uses the bit-string that was first assigned to it, e.g., server $A$ uses bit-string $A$.
+For the second query, each server uses the bit-string assigned to the next server in the list, e.g., server $A$ uses bit-string $B$.
+For the third query, each server uses the following bit-string (server $A$ uses string $C$); for the fourth, the rotation returns to the top of the queue; and so on and so forth.
 
+Now, suppose that server $B$ fails.
+In order to initiate the failure-detection process, each of the remaining servers must be aware that a failure has occurred somewhere on the channel (i.e., each server must notice that it transmitted a 1 when it did not intend to) \emph{and} they must recognise that the other servers are aware of the failure, so that they can synchronize their efforts.
+As soon as a server recognises that a failure has occurred, it immediately stops flipping any bits.
+So long as any servers continue to flip bits, however, all transactions will continue to fail.
+Once $A$ and $C$ have both recognised this, subsequent queries will succeed; thus, once the marks assigned to $A$, $B$ and $C$ have performed successful queries, recovery can begin.
+
+As the first step, for the next query, all remaining servers revert to their initially assigned bit-strings, but truncate the last bit.
+Thus $A$ uses $\langle 1\,1 \rangle$ and $C$ uses $\langle 0\,1 \rangle$.
+This query fails.
+Each server rotates to the next string in the queue ($A$ uses string $B$ and $C$ uses string $A$), truncated; i.e., $A$ uses $\langle 1\,0 \rangle$ and $C$ uses $\langle 1\,1$.
+This still fails.
+On the third rotation, $A$ uses $\langle 0\,1 \rangle$ and $C$ uses $\langle 1\,0 \rangle$.
+This also fails, so another bit is dropped.
+In round 4, $A$ uses $\langle 1 \rangle$ and $C$ uses $\langle 0 \rangle$.
+This fails as well.
+In round 5, $A$ uses $\langle 1 \rangle$ and $C$ uses $\langle 1 \rangle$.
+This query succeeds, indicating that $B$ has failed (since during round 4, $B$ was supposed to flip the first bit in its string, and both $A$ and $C$ know this.
+
+Developing a systematic method of producing bit-strings suitable for failure detection in larger multi-party models is an obvious avenue for further work.
+Prefix coding may present useful techniques for constructing such bit-strings quickly.
+\end{example}
+
+
 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.
+Network traffic between the colluding servers and the marks must therefore increase by a factor of $n^2$, though in a sufficiently noisy system this increase may well go unnoticed.
 
 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 systems 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~\cite{statistical-disclosure}.
 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$.
-% 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.
@@ -210,14 +249,17 @@
 Goldberg proposes a list-decoding algorithm which recovers all possible blocks for the values returned, and does so in polynomial time.
 However, the additional processing time is significant---seconds or even minutes---and thus the user can still function as an oracle for a group of colluding servers.
 
-%describe latency stuff here
-
 Note that a colluding server only gets one chance per user to transmit a signal, as once a Byzantine-robust client detects a Byzantine action, it does not request any more blocks from that server.
 Partitioning the userbase again comes into play here.
 Overall bandwidth goes down, because a server can only use a mark to transmit a $1$ once, and once a server has done so, it cannot use that mark again.
 However, a server can easily pass an expended mark to another colluding server; i.e., once $S_i$ has transmitted a 1 using mark $M_i$, all the colluding servers revise their list of marks, assigning $M_i$ to $S_{i+1}$ modulo $n$, the number of colluding servers.
 
-As a final note, observe that $v$-Byzantine-robust protocols need not (and, in practice, probably should not) prearrange alternate 
+As a final note, observe that servers establishing a subliminal channel over a $v$-Byzantine-robust protocol need not (and, in practice, probably should not) prearrange their incorrect answers.
+Since the colluding servers do not know what seed values have been sent to the non-colluding servers in the network, it is extremely difficult to construct a set of responses which will still interpolate to only one valid polynomial.
+Thus, servers should always transmit correct responses to their shills' marks, and only transmit incorrect responses to their own marks when they wish to transmit a 1.
+A $v$-Byzantine-robust system can still be used as a dead-man switch if a server is configured to require approval to transmit a correct response, and send an incorrect response if no approval is given, but detecting who tripped the switch requires a different (and far simpler) procedure.
+Since Byzantine-robust clients stop requesting blocks from servers which have taken Byzantine actions, a server which has fallen off the switch will eventually end up blacklisted by all clients in the system.
+Participants in the channel could simply generate their own dummy traffic and use their own clients' Byzantine-recovery capabilities to determine which server has stopped transmitting valid traffic.
 
 \section{Byzantine-robustness among the Byzantines}
 
@@ -246,7 +288,7 @@
 
 \paragraph{Acknowledgements} 
 
-Meredith L. Patterson's would like to thank the COSIC group at K.U. Leuven, for its hospitality during her visit to Leuven, and for the discussions which lead in part to this work.
+Meredith L. Patterson would like to thank the COSIC group at K.U. Leuven, for its hospitality during her visit to Leuven, and for the discussions which led in part to this work.
 
 Len Sassaman's work was supported was supported in part by the Concerted Research Action
 (GOA) Ambiorics 2005/11 of the Flemish Government, by the IAP Programme P6/26 BCRYPT of the Belgian State (Belgian Science Policy), and by the EU within the PRIME Project under contract IST-2002-507591. 

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