[freehaven-cvs] r1772: most of the Byzantine-server subsection is done (doc/trunk/pynchon-gate/bp-ringstwice)

[mlp@xxxxxxxx]

Author: mlp
Date: 2007-04-05 09:42:38 -0400 (Thu, 05 Apr 2007)
New Revision: 1772

Modified:
   doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex
Log:
most of the Byzantine-server subsection is done


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 06:35:25 UTC (rev 1771)
+++ doc/trunk/pynchon-gate/bp-ringstwice/byzantine-postman-rings-twice.tex	2007-04-05 13:42:38 UTC (rev 1772)
@@ -117,6 +117,9 @@
 
 %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, 
+
 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.
@@ -139,8 +142,23 @@
 % 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}
+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.
+If $t+1$ servers must collude in order to compromise the privacy of a query, the system is termed $t$-private $k$-out-of-$\ell$.
+If some $v$ of the $k$ responding servers can return an incorrect answer but the user can still reconstruct the correct response, the system is also called $v$-Byzantine-robust.
+$v$-Byzantine-robust protocols such as that presented in Goldberg~\cite{goldberg-2007} rely on polynomial interpolation to reconstruct the contents of the response to a query.
+When some servers are Byzantine, the set of returned values may correspond to more than one possible polynomial and therefore more than one ``valid'' data block.
+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 
+
 \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.
@@ -156,6 +174,8 @@
 %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. 
 
+% Len, however, mentions error coding, and that makes things a lot easier...
+
 %(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}

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