[freehaven-cvs] r1786: Klaus's final changes. (doc/trunk/pingers)

[rabbi@xxxxxxxx]

Author: rabbi
Date: 2007-06-10 19:21:41 -0400 (Sun, 10 Jun 2007)
New Revision: 1786

Modified:
   doc/trunk/pingers/echolot.tex
Log:
Klaus's final changes.


Modified: doc/trunk/pingers/echolot.tex
===================================================================
--- doc/trunk/pingers/echolot.tex	2007-06-10 19:54:21 UTC (rev 1785)
+++ doc/trunk/pingers/echolot.tex	2007-06-10 23:21:41 UTC (rev 1786)
@@ -547,6 +547,7 @@
 
 We will denote with $y= $ {\em mult\_BA($x$)} the invocation of a multivalued Byzantine
 Agreement protocol with input $x$, yielding the output $y$.
+
 \subsubsection{Broadcast protocols.}
 
 Broadcast protocols~\cite{ckps01} are used to send messages from one
@@ -606,6 +607,8 @@
 \subsubsection{Update set of mixes.}
 
 The main functionality of our protocols is to maintain a consistent
+% kku
+view about the
 set of mixes. Furthermore, a client should easily be able to obtain
 that set, i.e., each pinger can prove that he gives out the correct
 set. This is where the threshold signatures are used; there is only
@@ -616,7 +619,7 @@
 
 As an input for the protocol, each pinger $P_i$ has its own set
 ${\cal L}_i$ of mixes it considers valid. The protocol then has
-2 phases; in the amplicifaction phase, each party collects the
+2 phases. In the amplicifaction phase, each party collects the
 signed input of $n-t$ of other parties, and thus --- as less than a third
 of all parties are corrupt --- of at least $t+1$ uncorrupted parties.
 
@@ -630,7 +633,7 @@
 each mix in the set of lists proposed by only $t$ pingers is removed; thus,
 only pingers proposed by at least one honest pingers remain. As the final list
 contains the input of at least $t+1$ pingers, every mix that is in the list
-of all uncorrupted pingers will be in the final set. 
+of all uncorrupted pingers is guaranteed to be in the final set. 
 The final list is then signed by a combined signature, allowing a party to
 prove that it is the proper list resulting from the protocol.
 
@@ -656,16 +659,22 @@
  \item wait for ($n-t$) such shares $\sigma_{j_1,}..., \sigma{j_{n-t}}$.
  \item $\sigma$ = {\em tsign\_combine}($\sigma_{j_1},...,\sigma_{j_{n-t}}$).
 \end{revpar}
-output (${\cal L}'''$, $\sigma$)
+% kku
+output ({\em date}$, {\cal L}'''$, $\sigma$)
 \end{algorithm}
 
+All subprotocols used in above protocol require a (expected) constant number of rounds
+and have an overal (expected) message complexity in $O(n^2)$, i.e., $O(n)$ messages to be
+send by each pinger. Consequently, the update protocol also
+terminates in (expected) constant rounds with a similar message complexity.
 
 \subsubsection{Update set of pingers.}
 
-The protocol that updates the set of pingers is similar to the one that
+%kku
+The protocol that updates the set of pingers is essentially the same as the one that
 updates the set of mixes. However, for this protocol it is important to
-also update the shared keys, so that the old parties cannot participate
-in any signing process anymore, while the new parties get shares that
+also update the shared keys. This is to prevent the old parties from participating
+in any signing process, while the new parties need to get shares that
 allow them to participate. An appropriate re-sharing protocol is described
 in~\cite{CachinKLS02}.
 
@@ -677,7 +686,7 @@
 to determine a common value that has been proposed by at least one honest
 party. To avoid communication overhead, the agreements needed for all data
 on all mixes can be bundled; this leads to a protocol with message size
-linear in the total number of data items, and a running time logarithmic
+linear in the total number of data items, and a running time and message complexity logarithmic
 in the number of pingers.
 
 
@@ -697,7 +706,7 @@
 parties can be assured to receive all updates in the same order; due to the
 properties of the {\em r-broadcast} protocol, all pingers will eventually receive
 all update requests from the mix, so malicious manipulation of the serial numbers can 
-only lead to a temporary inconsistency.Note that
+only lead to a temporary inconsistency. Note that
 there exist protocols that can also enforce that all pingers receive all
 update requests in the same order; however, the those protocols
 are rather complex, so implementing this here may be

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