[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Changes throughout. Mostly a little more on strategy.
Update of /home/freehaven/cvsroot/doc/alpha-mixing
In directory moria:/tmp/cvs-serv8092
Modified Files:
alpha-mixing.bib alpha-mixing.tex
Log Message:
Changes throughout. Mostly a little more on strategy.
Index: alpha-mixing.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/alpha-mixing/alpha-mixing.bib,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- alpha-mixing.bib 10 Mar 2006 07:32:56 -0000 1.2
+++ alpha-mixing.bib 10 Mar 2006 21:54:13 -0000 1.3
@@ -122,6 +122,18 @@
www_ps_gz_url = {http://www.esat.kuleuven.ac.be/~cdiaz/papers/DS03.ps.gz},
+@inproceedings{SM05,
+ title = {Message Splitting Against the Partial Adversary},
+ author = {Andrei Serjantov and Steven J. Murdoch},
+ booktitle = {Proceedings of Privacy Enhancing Technologies workshop (PET 2005)},
+ year = {2005},
+ month = {May},
+ editor = {George Danezis and David Martin},
+ publisher = {Springer-Verlag},
+ www_pdf_url = {http://www.cl.cam.ac.uk/users/sjm217/papers/pet05msgsplit.pdf},
+ www_section = {Anonymous communication},
+}
+
@inproceedings{minion-design,
title = {Mixminion: Design of a Type {III} Anonymous Remailer Protocol},
author = {George Danezis and Roger Dingledine and Nick Mathewson},
@@ -231,6 +243,7 @@
author = {Dogan Kesdogan and Jan Egner and Roland B\"uschkes},
booktitle = {Proceedings of Information Hiding Workshop (IH 1998)},
year = {1998},
+ editor = {David Aucsmith},
publisher = {Springer-Verlag, LNCS 1525},
www_pdf_url = {http://www.uow.edu.au/~ldn01/infohide98.pdf},
}
Index: alpha-mixing.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/alpha-mixing/alpha-mixing.tex,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -d -r1.8 -r1.9
--- alpha-mixing.tex 10 Mar 2006 07:32:56 -0000 1.8
+++ alpha-mixing.tex 10 Mar 2006 21:54:13 -0000 1.9
@@ -73,7 +73,7 @@
strong security against a global attacker by adding high variance
in latency, but this latency has crippled adoption --- which in turn
decreases the security that the network can provide, discouraging even
-the users who need high security.~\cite{econymics}
+the users who need high security~\cite{econymics}.
Here we design a hybrid batching strategy for mixes that combines users
with different anonymity and performance goals into the same network.
@@ -146,7 +146,7 @@
about the rate of incoming messages. On the other hand, minimum
anonymity properties that threshold mixes have may not be satisfied
for timed mixes (without assumptions about the rate of incoming
-messages.
+messages).
As we will eventually see, one of the virtues of alpha mixing is that
the timed/threshold distinction for mixes can somewhat break down, and it
@@ -185,7 +185,7 @@
decremented-to-($\alpha = 0$) messages are all sent together even if
there were more than the threshold of messages already in the stack at
$\alpha = 1$. Note that many messages with $\alpha > 0$ may be waiting
-in a mix before a threshold number of $\alpha = 0$ arrive. This is
+in a mix before a threshold number of $\alpha = 0$ accumulate. This is
akin to the fact that many mixes in a free-route threshold-mix net may be
waiting and nearly full while messages are being accumulated at
relatively empty mixes.
@@ -368,7 +368,7 @@
In this section we deal with the problem of distributing the security
parameter over the route (i.e. the mixes which constitute the route)
-which the message takes. There are two problems. First, if a bad mix
+that the message takes. There are two problems. First, if a bad mix
observes one of the alphas, it should get as little information as
possible about the other alphas of this message\footnote{Note the
similarity between picking an alpha and message splitting \cite{SM05}
@@ -379,8 +379,9 @@
is concerned about security for the reasons mentioned in the previous
section.
-One possible solution for picking a sequence of $alpha_i$ is precisely
-to pick from a uniform distribution over the partitions of $\Sigma
+One possible solution for picking a sequence of $\alpha^{(i)}$ (where
+the `$(i)$' represents the $i^{th}$ mix in the route) is precisely to
+pick from a uniform distribution over the partitions of $\Sigma
\alpha$ into $l$ buckets where the buckets themselves are
indistinguishable. The number of such partitions are given by
@@ -393,12 +394,14 @@
is possible, for instance, using the algorithm described in
\cite{Devroye}. This seems to deal with the first problem (the
analysis to show this is beyond the scope of this paper). For the
-second part, we need to decide whether both the sender and the
-recipient care about having an estimate of the security parameter
-associated with them, or just the sender. Note that if the first and
+second part, we need to decide whether the sender cares
+about having an estimate of the security parameter
+associated with just herself, with herself and the recipient,
+or just the recipient. Note that if the first and
the last mixes are bad and can observe a 'higher security' message
-passing through each of them, they can conjecture that it was in fact
-one message. There are a variety of properties to explore in this
+passing through each of them, they can conjecture that it is one
+of a relatively small set of sensitive messages.
+There are a variety of properties to explore in this
area; we merely observe that by reordering our value which we have
obtained from the uniform distribution over partitions, we can make
sure that the minimum values in that partition are sent to the first
@@ -406,19 +409,21 @@
distribution is uniform over:
$\{5,0,0,0\}\{4,1,0,0\},\{3,2,0,0\},\{3,1,1,0\},\{2,1,1,1\}$. Supposing
we draw the partition $\{3,1,1,0\}$, we reorder it into $\{0,3,1,1\}$
-and hence oftain a sequence of alphas to insert into the message.
+and hence obtain a sequence of alphas to insert into the message.
-A simpler deterministic alternative\footnote{This is somewhat inferior
-to the probabilistic alternative above as any of the two mixes are able
-to compute the overall security parameter} is as follows: given a
-message with a cumulative $A = \sum \alpha_0$, a path with alpha
-distribution given by $0$, $1$, $\lceil A/2 -2 \rceil$, $\lceil A/2 -2
-\rceil$, $1$, $0$ should both hide the sensitivity of the endpoints
-and diffuse the trust so that an adversary comprising a single bad mix
-and a global passive observer will still have some difficulty linking
-endpoints or even identifying them as associated with any sensitive
-message.
-
+If we wish to guarantee that neither the first nor the last mix can
+locally know anything about sensitivity level of a message, we can
+simply stipulate for message $M$ that $\alpha^{(0)}_{M,0} =
+\alpha^{(n)}_{M,0} = 0$ (for a path length of $n+1$. Similarly we
+could stipulate that $\alpha^{(1)}_{M,0} = \alpha^{(n-1)}_{M,0} \leq
+1$, etc. The tradeoff is that with each such move we are reducing
+what an adversary observing just the endpoints can learn about
+sensitivity of messages, but fewer nodes in the center learn more
+about the sensitivity of messages. Against an adversary of the central
+node(s) combined with, e.g., a global passive observer, our protection
+is diminished. We can gain advantage against both types of adversaries
+by increasing path length, with the usual concomitant risk to
+robustness of delivery that comes with increased path length.
%Non-Uniform Random Variate Generation
%(originally published with Springer-Verlag, New York, 1986)
@@ -490,15 +495,15 @@
network can be initialized with a default expected distribution
averaged from one or more mixes already in the network. If the network
is uninitialized, individual mixes can be initialized with a uniform
-strategy (as above), or better a weighted one, e.g., add a dummy at
+strategy (as above), or better a geometric one, e.g., add a dummy at
level $\alpha$ with probability $1/2^{\alpha+1}$. Dummy policy can
then be periodically shifted to reflect the distribution of alphas for
actual traffic through the mix.
If active attacks are suspected, the amount of dummy traffic added to
the alpha stack can be increased according to the expected duration of
-and strength of the blocking (for timed deterministic-alpha mixes,
-there is no point in flooding) and the anonymity one intends to
+and strength of the blocking (assuming timed deterministic-alpha mixes,
+for which there is no point in flooding) and the anonymity one intends to
maintain for messages so attacked.
The easiest way to disguise dummies from others in the network is to
@@ -513,7 +518,7 @@
\section{Strategic Choice of Alpha}
-As observed in section~\ref{passive-adversary-anonymity}, the
+As observed in section~\ref{sec:passive-adversary-anonymity}, the
anonymity of any message can be improved by greater uncertainty about
the alpha level of \emph{other} messages. Since Alice benefits from
the fact that other people might choose non-zero $\alpha_0$ for their
@@ -538,12 +543,15 @@
constraints of one's own messages increases the autonomy and control
over one's own security and utility. Indeed, if an adversary can make
reasonable guesses about a choice of alpha range for a message, then
-increased alpha for other messages in a mix might not increase
-anonymity for a target message, e.g., if that increased alpha would
-only vary the range that is after the target message is expected to
-have left the mix.
+increased alpha for other messages in a mix might actually decrease
+anonymity for a target message. For example, assume a mix containing a
+target message with low alpha and an ancillary message that is from
+about the same alpha range or from a much larger alpha range than the
+target message. If the adversary can guess which is the case, then
+his uncertainty about the target message decreases when the ancillary
+message is assigned alpha from a larger range.
-More significantly, however, security is hard to get right when it
+Even more significantly, however, security is hard to get right when it
doesn't depend on the strategic behavior of others. Users of the
system are not likely to have such finetuned knowledge of the system,
the behavior of others, and their own needs. Thus if we can prescribe
@@ -558,44 +566,31 @@
Initial recommendations can be guided by existing anonymity networks.
Traffic that must arrive in realtime obiously must have $\sum \alpha =
0$. For more sensitive traffic, we might initially try to follow
-networks such as Mixminion. But how to do that since mixing*****
-
-
-some of the users favor performance and some favor anonymity. Three
-factors are most important here:
-
- - their interest in anonymity.
-
- - their willingness to accept delay.
-
- - their guess at (expectation of) the current alpha levels
-
- in the network.
-
-
-C.f. Andrei's complaints about stop-and-go -- in that design you had
-to anticipate the network load to get good anonymity, and in this
-design you need to anticipate the other users' anonymity/latency
-requirements to get what you want.
+networks such as Mixminion and Mixmaster. But how can we do that?
+Thes use a dynamic batching strategy in which messages are chosen
+for the current batch randomly by the mix from a collective pool
+while alpha mixing is based on individual choices made by the sender.
+We now turn to how to combine these features.
+\section{Dynamic-Alpha Mixes}
-To help people guess current alpha levels, we could run a node and use
-that to estimate the average $\Sigma \alpha$ in use in the network.
-We could publish it to the users, which would cause some sort of
-feedback loop.
+The prior work that is probably most similar to alpha mixing is
+stop-and-go mixing~\cite{stop-and-go}. In stop-and-go mixes, the sender
+gives to each mix in the path a time interval. If the message arrives
+within the interval, it is sent at the end of the interval, otherwise
+it is discarded. This is similar to the timed deterministic-alpha mix
+described above. One important difference is that delivery through the
+mixnet depends on it being entirely synchronized. Alpha mixes offer
+predictable delivery times, but will still mix and deliver messages
+even if some nodes in the path are not adequately synchronized.
-Speaking of which, how does the network bootstrap? See the econymics
-paper where we argue that people who don't care about anonymity will
-be the early adopters, since the people who do care won't be willing
-to use it with no cover users. Similarly the first users will all
-choose $\alpha$ of 0, and then sometime later the users willing to try
-a non-zero $\alpha$ will arrive?
+Both timed deterministic-alpha mixes and stop-and-go mixes have the
+vulnerability of all purely timed mixes: they provide no anonymity
+if others are not sending through them at the same time. This can
+be addressed in part by padding, and we have introduced a relatively
+lightweight padding scheme above. But,
-The attacker's a priori expectation of Alice's paranoia improves his
-attack.
-
-\section{Dynamic Alpha Mixes}
Here's a design. Assign alphas as we have been thinking, except instead
of them deterministically decreasing one after each firing, there is
a probabilistic function.\\
@@ -617,6 +612,44 @@
\section{Conclusion}
+%%%% Stuff with 4s is stuff from alpha strategy section
+%%%% that I didn't want to toss just yet
+
+%4 some of the users favor performance and some favor anonymity. Three
+%4 factors are most important here:
+%4
+%4 - their interest in anonymity.
+%4
+%4 - their willingness to accept delay.
+%4
+%4 - their guess at (expectation of) the current alpha levels
+%4
+%4 in the network.
+%4
+%4
+%4 C.f. Andrei's complaints about stop-and-go -- in that design you had
+%4 to anticipate the network load to get good anonymity, and in this
+%4 design you need to anticipate the other users' anonymity/latency
+%4 requirements to get what you want.
+%4
+%4
+%4 To help people guess current alpha levels, we could run a node and use
+%4 that to estimate the average $\Sigma \alpha$ in use in the network.
+%4 We could publish it to the users, which would cause some sort of
+%4 feedback loop.
+%4
+%4 Speaking of which, how does the network bootstrap? See the econymics
+%4 paper where we argue that people who don't care about anonymity will
+%4 be the early adopters, since the people who do care won't be willing
+%4 to use it with no cover users. Similarly the first users will all
+%4 choose $\alpha$ of 0, and then sometime later the users willing to try
+%4 a non-zero $\alpha$ will arrive?
+%4
+%4
+%4 The attacker's a priori expectation of Alice's paranoia improves his
+%4 attack.
+%4
+
%***************\\
%Where Paul stopped on Wednesday. Below is unchanged from before today.
%***************\\
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/