[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] early thoughts on the alpha mixing design and analys...
Update of /home/freehaven/cvsroot/doc/alpha-mixing
In directory moria:/home/arma/work/freehaven/doc/alpha-mixing
Added Files:
alpha-mixing.tex
Log Message:
early thoughts on the alpha mixing design and analysis.
--- NEW FILE: alpha-mixing.tex ---
\documentclass{llncs}
\usepackage{url}
\usepackage{amsmath}
\usepackage{epsfig}
\renewcommand\url{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url}
\newcommand\emailaddr{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url}
\newcommand\XXXX[1]{{\small\bf [XXXX #1]}}
\newcommand{\workingnote}[1]{} % The version that hides the note.
%\newcommand{\workingnote}[1]{(**#1)} % The version that makes the note visible.
\hyphenation{mix-net mix-nets}
\newenvironment{tightlist}{\begin{list}{$\bullet$}{
\setlength{\itemsep}{0mm}
\setlength{\parsep}{0mm}
% \setlength{\labelsep}{0mm}
% \setlength{\labelwidth}{0mm}
% \setlength{\topsep}{0mm}
}}{\end{list}}
% Cut down on whitespace above and below figures displayed at head/foot of
% page.
%\setlength{\textfloatsep}{3mm}
% Cut down on whitespace above and below figures displayed in middle of page
%\setlength{\intextsep}{3mm}
\begin{document}
\title{Blending different latency traffic with alpha-mixing}
%\title{Alpha-mixing or Getting Personal with the Adversary}
\author{Roger Dingledine\inst{1} \and Andrei Serjantov\inst{2} \and Paul Syverson\inst{3}}
\institute{The Free Haven Project \email{(arma@xxxxxxxxxxxxx)} \and
The Free Haven Project \email{(aas23@xxxxxxxxxxxxx)} \and
Naval Research Lab \email{(syverson@xxxxxxxxxxxxxxxx)}}
\maketitle
\pagestyle{empty}
%======================================================================
\begin{abstract}
\end{abstract}
\section{Introduction}
\label{sec:intro}
Motivation:
Tor exists with its low latency, but not very good security.
Mixminion exists with its high latency, but no users.
Here we design a hybrid batching strategy that tries to put both user
bases into the same network but still let them achieve their goals.
Overview (the new mixes).
Alice gives each message an alpha (number of rounds) delay to each mix
in a route. Once a threshold number of messages with alpha 0 enter the
mix all messages that are alpha 0 get fired off, including any that
were buffered and decremented to 0 last time decrementing occurred.
Then all messages in the buffers get alpha decremented by 1. Any
messages that enter with alpha $>0$ get put into the buffer with alpha
of that number.
Here we also need to say that the attacker does not have complete
knowledge of the alphas in the messages, and this is what we are
relying on, see the analysis section.
\subsection{Outline}
1. Deterministic-alpha mixes\\
Prove anonymity against a local passive adversary\\
2. Strategy: (or a subsec of above section)\\
How to distributed the $\sum \alpha$ across the path \\
Add dummy traffic \\
3. Game Theory and Free-riding
4. Dynamic-alpha mixing
\section{Deterministic-alpha mix}
Perhaps the simplest version of alpha mixing is one in which mixes
fire at regular intervals. This is also most naturally in keeping with
the motivation to include traffic for which timeliness matters, since
this cannot be satisfied for threshold mixes (mixes that fire only when a
sufficient number of messages have arrived) without assumptions 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.
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
becomes more a distinction for firing strategies of individual
messages than of mixes. Also, for our initial analysis we can assume
a steady-state network for which the timed/threshold distinction will be
moot for a passive adversary.
``Deterministic'' here refers to the algorithm by which messages
change $\alpha$ after each mix firing. Later we will consider
algorithms that will change alpha probabilistically, possibly based on
the number of messages at certain alphas in the mix. For now we expect
all messages to simply drop one alpha level after each mix firing.
\paragraph{Timed deterministic-alpha mix:}
The mix fires every $t$ seconds. All messages for which $\alpha = 0$
are sent out. (We do not describe the reordering of messages or
changing of their appearance in this paper. We assume that messages
emerging from a mix have an appearance that cannot be correlated with
their appearance upon entering the mix and that the order of all
$\alpha=0$ messages is randomly permuted before they are sent.) All
remaining messages have their $\alpha$ decremented by one. New
messages that arrive before the next firing are labeled with some
$\alpha$ and are placed at the according $\alpha$ level.
\paragraph{Threshold deterministic-alpha mix:}
This is the same as the timed version just described, except that the
mix fires when at least a threshold number of messages with $\alpha =
0$ are in the mix. Note that since the number of messages with $\alpha
= 1$ may be above the firing threshold, there may be more than the
threshold number of messages in a batch. Also we assume that the input
buffer of the mix is read after the alpha stack is decremented but
always before firing, so the received $\alpha = 0$ messages and the
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
akin to the fact that many mixes in a free-route batch mix net may be
waiting and nearly full while messages are being accumulated at
relatively empty mixes.
It is also possible to have a threshold-or-timed alpha mix in which
all messages are decremented in the alpha stack if either $t$ seconds
have passed or a threshold number of messages have arrived. (Messages
are actually sent only when the $\alpha = 0$ messages attain a
threshold however.) Similarly, one can have a threshold-and-timed mix
to reduce the effective rate of flooding attacks~\cite{batching-taxonomy}.
\subsection{Deterministic-alpha mix:\\
anonymity against a local passive adversary}
We will describe anonymity for a threshold mix. As we have already
noted, we assume a steady-state network in which messages arrive at
the different alphas for the mix at a regular rate, and the mix fires
at regular intervals. Thus the threshold mix is indestinguishable by a
local external passive adversary from a timed mix.
We assume the adversary does not know the specific alpha of any
message entering the mix, e.g., that this is provided to the mix
encrypted together with the message. However we do allow that the
adversary might know the strategy by which alpha was chosen. What
should that strategy be? It would seem that choosing higher alphas
would correspond to greater anonymity for messages. We now make this
more precise.
\begin{claim}
Given any set of other messages in a threshold determistic-alpha
mix, a message has greater anonymity if it is assigned an alpha from
a broader range (chosen uniformly) than from a narrower range.
\end{claim}
\begin{proof}
Suppose messages occur with some distribution of alphas in a mix
with firing threshold $n$. A sender will assign to message $M$ an
initial $\alpha_{M,0}$ for a particular mix in a given position in the
message's path. Suppose the adversary knows the strategy chosen by
the sender. Assume the choice of strategies are between choosing
$\alpha_{M,0}$ from either a range of $0$ to $j$ or a range of
$0$ to $k > j$. The anonymity set size increases by $n(k-j)$ if the
broader range is chosen. (In information-theoretic terms, the
entropy has increased by $\log(n(k-j)$.) If the adversary does not
know the strategy, then we cannot put a precise number on the
uncertainty. However, the less predictable the range is to the
adversary, the greater the uncertainty is even if we cannot say how
much. She can either guess too small a range and risk not seeing the
output message at all, or guess too large and include many other
batches in the anonymity set for the message. (These points carry
over mutatis mutandis when we reason probabilistically rather than
just possibilistically.)
\end{proof}
If the adversary knows the strategy (although not the actual
$\alpha_0$) for each message, then the anonymity of a message is
unaffected by the strategy for choosing $\alpha_0$ for other messages
in a steady-state network. However, if the strategies are not know,
then choosing $\alpha_0$ from a broader range increases the anonymity
for other messages in the mix as well, although it is difficult to say
by how much. If the distribution of strategies across all
messages in the mix at any time is known to the adversary, however,
then it is clear that increasing the range from which $\alpha_0$ is
chosen for any unknown one of those messages increases the uncertainty
about the future batch in which any of the messages still in the mix
will emerge. Thus,
\begin{claim}
Assume a set of messages in a steady-state deterministic-alpha mix.
Assume the $\alpha_{M,0}$ for any message $M$ is chosen uniformly
at random from the range
given by $0 \leq \alpha_{M,0} \leq k_{M,0}$.
Then anonymity increases for any message $M$ in the mix if any
$k_{M',0}$ increases.
\end{claim}
In sum, for threshold mixes or steady-state timed mixes, choosing
$\alpha$ from a broader range improves the anonymity for a message
whether the adversary knows one's strategy or not. And, if the
adversary knows nothing about the strategies of choosing alphas or
knows simply the distribution of strategies, then increasing the
$alpha$-range for any message improves anonymity for all messages.
\subsection{Distributing $\sum \alpha$ against a distributed adversary}
\label{sec:distributing-alpha}
While a rising alpha seems to lift all boats, and one's own against
even knowledgeable adversaries, it is not unequivocally better to
simply choose from a higher range of alphas. First, this has a cost in
message delivery. Since to some extent one's anonymity is improved by
messages from others chosen with higher alpha, there is some incentive
to allow others to improve your anonymity for you. We will return to
this issue below. Second, both theory~\cite{econymics} and experience
have indicated that lower latency systems like Tor, JAP, and Freedom
have far more users than higher latency systems like Mixmaster and
Mixminion. Thus, higher alpha messages will be more rare and will
stand out more as messages the sender was trying harder to protect.
This has both the negative effect of being better mixed but in a much
smaller anonymity set and the negative effect of advertising to
participating mixes that the message is more sensitive.
This tradeoff is not entirely avoidable, however, it is possible to
move where the higher alphas occur within a messages path. If the mix
adjacent to the sender (and receiver if that is also sensitive) is
always given relatively low alpha messages, then the mixes that can
tell a message is more sensitive will not be the ones knowing the
ultimate source or destination. For example, given a message with a
cumulative $A = \sum \alpha$, 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.
\subsection{Dummies}
Our focus so far has been on steady-state networks with passive
adversaries. However, we want to provide uncertainty even in edge
cases~\cite{batching-taxonomy,generalized-mixes}. An active attacker
can arrange an edge case via blending attacks, but a passive attacker
can also simply wait for an edge case to occur. For timed mixes there
will be occasions when only single messages enter and leave the mix in
a single round. Alpha mixes have a clear advantage here since there is
no guarantee that the message that exited the mix is the same message
that entered. The attack is never exact (guaranteed to recognize
a target message as it exits the mix) unless the adversary can
bound the range of $\alpha_0$ with certainty for a given message.
A very lightweight dummy policy can guarantee that no exact attack is
possible against an alpha mix, even for active attackers. Simply
initialize the mix with a single dummy message set at an arbitrary
alpha. Before firing, always check the mix for the presence of a
dummy somewhere in the alpha-stack. If none is present, add one.
What do we mean by ``arbitrary alpha''? Obviously it must occur within
some finite range. It could be uniformly chosen between $0$
and the maximum expected $\alpha_0$. If a message is ever received
with a higher $\alpha_0$, then the maximum should be raised to this
level. Such a strategy will prevent any exact attack, but it will
still allow most practical attacks that dummies are intended to
counter (active or passive) because most traffic will not have high
alpha. Thus, a single message entering and a single message exiting
a timed mix in a single firing interval are much more likely to be
the same message than a dummy.
A strategy that should maximize uncertainty at least in the edge cases
would be to insert dummies according to the expected distribution of
$\alpha_{M,0}$ for messages $M$ entering the mix. The expected
distribution can be determined by observation. Mixes joining the
network can be initialized with a default expected distribution
averaged from one or more mixes already in the network. If the network
is uninitialized, a uniform strategy (as above), or better a weighted
one, e.g., add a dummy at level $\alpha$ with probability
$1/2^{\alpha+1}$, and then periodically shifted to reflect the
distribution 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 maintain
for messages so attacked.
The easiest way to disguise dummies from others in the network is to
route them in a circuit leading back to the mix that generates them.
The length of the path should be randomly chosen as suggested
in~\cite{batching-taxonomy}. Obviously the alphas chosen for the dummy
message at other mixes in the path should be distributed to minimize
recognition of the message as a dummy; hence some dummies should
follow an alpha pattern as if they had entered the network at that mix
and others should appear to be in mid path as they emerge from the mix
(cf.\ Section~\ref{sec:distributing-alpha}).
***************\\
Where Paul stopped on Wednesday. Below is unchanged from before today.
***************\\
\section{Assumptions}
Assume that in most cases we are analyzing a steady-state network.
(Our benefits are most easily seen in this light.) In section
\ref{sec-defense-against-blending-attacks} we discuss relaxing this
assumption and our how well we resist blending attacks.
Assume the single-message model. There are two pieces to this
assumption. First, we want to know about the level of protection we
can provide to one message from Alice to Bob. We acknowledge that in
reality there are probably long-term trends that make us vulnerable to
statistical disclosure attacks, regardless of how good our batching
strategy is. So we're not paying attention to that here. Second, we
assume a message-based protocol rather than stream-based. This has bad
implications on our user base, but hey, low-latency stream-based
anonymity is hard, so one step at a time.
Also state some assumptions about practical attackers and all the
things they can do. We can't solve all of them but we are at least a
step forward.
Assume users with differing goals. See section
\ref{sec-economic-model} for more discussion.
AAS: Perhaps this goes into the analysis section and we want to just
give a flavour?
The key difference of this model to the more traditional anonymity
schemes (which is actually an additional but, we argue, realistic
assumption) is that the users have an additional security parameter
which is \emph{not known} to the attacker. As expected, we expect the
attacker to have some knowledge of the overall distribution of the
security parameter (can try to figure out the users' utility function,
etc, etc), but no more than that for any particular attack he is
trying to mount. If he does, the additional properties of the
``alpha'' mixing collapse and we get back to a timed/threshold mix
scenario, which, note, is worse than the pool/dynamic pool/generalised
mix, so we are relying on the fact that the attacker does not know
alpha. On the other hand, in practice even relatively few dummy
messages fix this problem. We will illustrate this better in the
analysis section.
PFS: It doesn't have to collapse to something weaker than pool. there
is no reason that we couldn't have alpha pools that one stipulates.
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.\\
$x_{\alpha,i+1} = f(x_{\alpha,i}, \mathit{Pool}(x_{\alpha,i}))$ where
$\mathit{Pool}(x_{\alpha,i}) = | \{x : 1 \leq x_{\alpha ',i-1} \leq
x_{\alpha,i-1} \} | $
My assumption is that f is monotonically nonincreasing, but maybe not.
This should get us something like generalized mixes only a bit more
general because, like the alphas, the $f$ is not set by the mix but by
the individuals. (This is maybe where you were trying to go when
observing that you couldn't add timestamps in the generalized mix
paper?) Idea is that alphas decrease but only as a function of where
they are and how many messages are in the pool below them (and were
above 0 at some point, since I figured those messages shouldn't
count). This gives
us a dynamic alpha pool (either timed or threshold depending).\\
By the way, I'm following the subsequent notation of $x_\alpha$ but I
think it is exactly backwards. It should be $\alpha_x$.
Note that the most important thing is that we can have timed $\alpha = 0$
messages, higher alpha messages, and dynamic pool messages all living
in the same mix.
\section{Related work}
Traditional mixes.
Traditional onion routers.
Batching taxonomy. Pool mixes.
Stop-and-go.
Econymics and usability-is-a-security-parameter.
\section{Analysis}
In this section we look at the two mixes in more detail, their
properties and compare them against existing designs.
Description of the operation of the timed alpha mix:
Alice gives each message an alpha (number of rounds) delay to each mix
in a route. Once $t$ seconds have passed, all messages that are alpha
0 get fired off, including any that were buffered and decremented to 0
last time decrementing occurred. Then all messages in the buffers get
alpha decremented by 1. Any messages that enter with alpha $>0$ get
put into the buffer with alpha of that number.
The \emph{possibility} of setting $\alpha > 0$ improves anonymity in
all cases (under the assumptions in Section \ref{sec-assumptions}),
both for the sender \emph{and} for others.
AAS: Improves anonymity compared to what? Threshold mix? That's really
easy to show!
PFS: Yes but significant (and we were thinking timed, but in steady
state what's the diff). The point is that this little change is a win
all around.
The properties here, of course, depend on what the attacker knows
about the security parameter of the users.
Sender anonymity, one mix, illustrated on two rounds only (equivalently,
suppose maximum alpha is 1 just to illustrate the idea)
Round 1: $I_1 = i_{1,1} \ldots i_{n,1}$ came in, messages $o_{1,1} \ldots
o_{x,1}$ came out.
Round 2: $I_2 = i_{1,2} \ldots i_{m,2}$ came in, messages $o_{1,2} \ldots
o_{y,2}$ came out.
$\alpha(x)$ is the set of possible alphas of message $x$ as known by
the attacker. Note that if the attacker knows nothing, then $\forall x
\alpha(x) = {0,1}$
Our target message is $o_{1,2}$. Anonymity set (in messages):
\[
\{x | x \in I_1 \wedge 1 \in \alpha(x)\} \cup \{y | y \in I_2 \wedge 0
\in \alpha(y)\}
\]
Hence (almost) any knowledge of alphas by the attacker degrades
anonymity. Note that complete knowledge of alphas by the attacker
\emph{may} leave the message with no anonymity, however, this is
extremely unlikely (or amounts to a variant of the trickle attack, a
rather stupid one when you come to think of it).
Now, the anonymity probability distribution is also an easy thing to
work out, but first we need a little more formalization of the
assumptions. Essentially, where we allowed the attacker possibilistic
knowledge about the alphas of the messages, we now allow him (better)
probabilistic knowledge.
Notation: call $x_{\alpha}$ the alpha in message $x$. Hence the
attacker knows the probability distributions $P(x_{\alpha}=y)$ for
every message $x$, y ranging from 0 to $y_max$, [PFS: huh?] in our case 1.
Now, the anonymity probability distribution in the case above is:
\[
\mbox{Normalise}(\{p | x \in I_1 \wedge p = P(x_{\alpha}=0)\} \cup
\{p | x \in I_2 \wedge p = P(x_{\alpha}=1))
\]
AAS: Paul, what's the notation for a finite probability distribuiton
like this??? Can't think off hand.
Clearly, there is an easy generalisation to N rounds. (To be inserted)
Show by equations:
part one: anonymity gotten by all users when every $\alpha is 0.$
(AAS: depends what the attacker knows, done above, in a steady state,
unless the attacker can show it > threshold)
part two: anonymity gotten by Alice when she sets her $\alpha to 1$.
(AAS: ditto)
part three: anonymity gotten by Alice when $\exists$ some other
sender's message of $\alpha 1$.
(AAS: ditto)
(AAS: actually, I don't think the above 3 cases are what we want, I
think the examples ought to be rather different.
---------------------------------
If the attacker's knowledge about the users' security parameters is
limited, the alpha mix closely resembles pool mixes
\cite{SD01,SDS02}. For instance, if the users draw $\alpha$ from a
geometric distribution and this is known to the attacker, with
parameter $p$ (i.e. the probability of $\alpha=0,1,2,\ldots$ is $q,
pq, ppq, \ldots$) then the anonymity of the threshold alpha mix is
simply equivalent to a threshold pool mix with a pool/(threshold +
pool) = $p$. Curiously, if the attacker knows nothing about the
distribution of $\alpha$, he may still perform a similar analysis
based on the number of incoming and outgoing messages from a mix. The
anonymity derived in this way is an easy exercise for the reader (or
see \cite{Diaz_thesis}, Chapter 4.6)
---------------------------
AAS curious aside:
\subsection{Correlating Offensiveness with Security}
Now let us study an interesting example which has long been known
intuitively... Suppose the attacker knows that sender $S$ only sends
with a high security parameter (let's say alpha of 5). He now sees a
message from sender $S$ at round 0, and a message with a death threat
at round 5. Suppose further that all other messages have an alpha of
0. Our definitions (naturally) give the offensive message the
anonymity set of all the sender of round 5 union S. Nevertheless, we
conjecture the jury (AAS: can we cite a case???) will tend to suspect
that $S$ sent the message. How can we reconcile the opinion of the
jury with our formalism above and how can we design the system to
avoid such a judgement?
The jury is, of course, correct -- what we ignore here is the fact
that the choice of the security parameter is likely \emph{conditional}
on the offensiveness of the message and the attacker has used this
fact to form his judgement. In order to avoid this, we must
(paradoxically!!) ignore this fact completely and pick alphas from a
distribution which is independent of the receiver (this distribution,
of course, is allowed to be conditional on the utility
function!). Indeed, one must convince the jury that the sender *could
not* have picked the alphas any other way (otherwise those with high
latency/security tradeoff will be more likely to be suspected of dodgy
things as is indeed the case in practice as no dobt every anonymity
researcher has experienced :)
--------------------------------------
We also need to convince the reader than larger values of 1 are even
better. The key is that raising $\alpha$ is increasing the variance.
This matches the intuition described in \cite{e2e-traffic}.
A timed alpha mix is also equivalent to the hint in sync-batching that
you can get better anonymity by "hopping" batches.
Flooding does not work against timed alpha mixes, but trickling still
does.
Next, let's look at threshold alpha mixes. The same reasoning as above
still applies about how the possibility of a non-zero $\alpha$ improves
anonymity all-around. Flooding works now, and trickling doesn't.
Performance is a function of network load. No guaranteed minimum delays --
but guaranteed minimum anonymity sets, assuming no blending attacks?
\section{Dummies}
Just as with batching-taxonomy and generalized-batching, we want to
provide uncertainty even in edge cases.
The active attacker can arrange an edge case via blending attacks, but
a passive attacker can also simply wait for an edge case to occur.
We need to always apply the dummy strategy because we can't know
if we're under attack. Dummies should be routed back to ourselves,
a la heartbeat-traffic.
What fraction of the traffic is dummies, then? We can graph this for
various strategies. Paul says (for timed): always send out at least
2 messages, and always add at least one dummy. In this case the dummy
overhead is bounded: between NL and 2NL for N mixes. (This sounds
suspicious now that I see it again -- is it wrong? -RD)
Note that we can achieve Andrei's goal of strict uncertainty with
way more efficiency just by having a single dummy anywhere in the
buckets.
\section{Game theory}
Since Alice benefits from the fact that other people might choose non-zero
$\alpha$, she has an incentive to take advantage of this by choosing a
lower $\alpha$ to get better performance but still have good security. In
the limit, it's a commons: everybody will hope that somebody else takes
the latency hit.
Did our equations in sec-analysis show that Alice gets better anonymity
if she's the one who chooses the higher alpha? If so then we're more ok.
Mixminion and Tor are in some sense the two extremes of the goal spectrum.
More generally, the senders in our mixnet have utility functions U that
describe what $\Sigma\alpha$ they will pick. Our whole design works because
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.
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.
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?
The attacker's a priori expectation of Alice's paranoia improves his
attack.
\section{Distributing your alphas over the path}
The first node (or second, or...) can learn about Alice's paranoia
level. So given $\Sigma \alpha$ which represents Alice's concern for
this message's anonymity, we need an algorithm for allocating which
$\alpha$ goes where in the path.
If we allocate all the $\alpha$'s uniformly, each node can compute the
expected $\Sigma \alpha$ for that message. If we allocate them
non-uniformly, we're in better shape. Need high expected variance for
better uncertainty too.
AAS: Any knowledge of alpha degrades anonymity.... So agree with all
the above. Note the similarity between picking an alpha and message
splitting \cite{SM05} -- in both cases they are distributions over
partitions. The best you can do 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
\[
\sum_k=1^l Q(\Sigma \alpha, k)
\]
where $Q(n,k)$ denotes the number of ways of partitioning $n$ into
exactly $k$ distinct parts.
\section{Example scenarios}
Work a couple of examples scenarios with sample numbers of types of
users, etc. Show that users with different utility functions all
benefit.
%======================================================================
\bibliographystyle{plain}
\bibliography{alpha-mixing}
\end{document}
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/