[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[freehaven-cvs] current draft, econymics paper
Update of /home/freehaven/cvsroot/doc/fc03
In directory moria.seul.org:/home/arma/work/freehaven/doc/fc03
Added Files:
econymics.bib econymics.tex llncs.cls
Log Message:
current draft, econymics paper
--- NEW FILE: econymics.bib ---
@InProceedings{Diaz02,
author = {Claudia Diaz and Stefaan Seys and Joris Claessens
and Bart Preneel},
title = {Towards measuring anonymity},
booktitle = {Privacy Enhancing Technologies (PET 2002)},
year = 2002,
editor = {Paul Syverson and Roger Dingledine},
publisher = {Springer Verlag, LNCS (forthcoming)}
}
@Article{fudenberg88,
author = {Drew Fudenberg and David K. Levine},
title = {Open-Loop and Closed-Loop Equilibria in Dynamic
Games with Many Players},
journal = {Journal of Economic Theory},
year = 1988,
volume = 44,
number = 1,
pages = {1--18},
month = {February}
}
@InProceedings{Serj02,
author = {Andrei Serjantov and George Danezis},
title = {Towards an Information Theoretic Metric for Anonymity},
booktitle = {Privacy Enhacing Technologies (PET 2002)},
year = 2002,
editor = {Paul Syverson and Roger Dingledine},
publisher = {Springer Verlag, LNCS (forthcoming)}
}
@InProceedings{trickle02,
author = {Andrei Serjantov and Roger Dingledine and Paul Syverson},
title = {From a Trickle to a Flood: Active Attacks on Several
Mix Types},
booktitle = {Information Hiding, 5th International Workshop (IH 2002)},
year = 2002,
editor = {Fabien Petitcolas},
publisher = {Springer-Verlag, LNCS (forthcoming)},
note = {\url{http://www.freehaven.net/papers.html}}
}
@InProceedings{syverson_2000,
author = {Paul F. Syverson and Gene Tsudik and Michael G. Reed
and Carl E. Landwehr},
title = {Towards an Analysis of Onion Routing Security},
booktitle = {Designing Privacy Enhancing Technologies: Workshop
on Design Issue in Anonymity and Unobservability},
year = 2000,
month = {July},
pages = {96--114},
editor = {H. Federrath},
publisher = {Springer Verlag, LNCS 2009},
note = {\url{http://citeseer.nj.nec.com/syverson00towards.html}}
}
--- NEW FILE: econymics.tex ---
%\documentclass{article}
\documentclass{llncs}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{amsmath}
%\textwidth16cm
%\textheight21cm
%\topmargin0mm
%\oddsidemargin2.5mm
%\evensidemargin2.5mm
%\textwidth=7in
%\textheight=10in
%\topmargin=-1.2in
%\oddsidemargin .35in
%\evensidemargin .35in
\begin{document}
%\newcounter{axiomctr}
%\newcounter{axiomctrx}
%\newenvironment{observation}{
%\begin{list}
%{{\addtocounter{axiomctrx}{1}} Observation \arabic{axiomctr}.}
%{\usecounter{axiomctr}} {\setcounter{axiomctr}{\arabic{axiomctrx}}}}
%{\end{list}}
\newcommand{\paulcomment}[2][\textwidth]{
% \par%
% \noindent%
\framebox[#1]{\parbox{0.9#1}{*******************Begin Paul's
Comment*****************
\setlength{\parskip}{\baselineskip}
\par #2
\\
\\
*******************End Paul's
Comment*****************} }
}
\newcommand{\alessandrocomment}[2][\textwidth]{
% \par%
% \noindent%
\framebox[#1]{\parbox{0.9#1}{*******************Begin Alessandro's
Comment*****************
\setlength{\parskip}{\baselineskip}
\par #2
\\
\\
*******************End Alessandro's
Comment*****************} }
}
\newcommand{\rogercomment}[2][\textwidth]{
% \par%
% \noindent%
\framebox[#1]{\parbox{0.9#1}{*******************Begin Roger's
Comment*****************
\setlength{\parskip}{\baselineskip}
\par #2
\\
\\
*******************End Roger's
Comment*****************} }
}
\newcommand{\workingnote}[1]{} % The version that hides the note.
%\newcommand{\workingnote}[1]{(**#1)} % The version that makes the note visible.
\title{Towards an Econymics ;-)}
%\title{Open Issues in the Economics of Anonymity}
%\title{Issues in the Economics of Anonymity}
%\title{Topics in the Economics of Anonymity}
%\title{The Economics of Anonymity}
%\title{On the Economics of Anonymity}
\author{Alessandro Acquisti\inst{1} \and Roger Dingledine\inst{2} \and Paul Syverson\inst{3}}
\institute{SIMS, UC Berkeley
\email{(acquisti@sims.berkeley.edu)}
The Free Haven Project
\email{(arma@mit.edu)}
\and
Naval Research Lab
\email{(syverson@itd.nrl.navy.mil)}}
\maketitle
\workingnote{
\documentclass[10pt,a4paper]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{amsmath}
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{LastRevised=Mon Sep 09 11:35:19 2002}
%TCIDATA{<DEFANGED_META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=article.cst}
\input{tcilatex}
\begin{document}
\title{Open Issues in the Economics of Anonymity - Some formal comments}
\author{}
\maketitle
}
\section{General view}
We study the incentives for agents to send messages anonymously through
mix-net like systems.
\begin{itemize}
\item Agents value their privacy, hence they have an interest in using a
mix-net system. This interest might be related to profits they will make by
keeping their messages anonymous or losses they will avoid by not having
their messages tracked. Different agents might value anonymity differently.
\item The strategy space $S$ for each agent $i$ in the mix-net includes
strategies $s$ that are based on the following actions $a$s:
\begin{itemize}
\item act simply as user of the system, by:
\begin{itemize}
\item sending messages through the system, $a_{s}$,
\item or/and agreeing to receive dummy traffic\footnote{We make here
the assumption users of the system are interested in sending
information anonymously; receiving valid traffic from the system
is not an action of `using the system'. This might not always be
the case, e.g., for remailer mixes with reply blocks or for
bidirectional connections as in Crowds or Onion Routing. And, it may
have costs and/or benefits.} through the system, $a_{r}$;
\end{itemize}
\item act as honest nodes, $a_{h}$, which can involve:
\begin{itemize}
\item receiving and forwarding traffic,
\begin{itemize}
\item (and in particular, act as exit nodes),
\end{itemize}
\item keeping messages secret,
\item and, possibly creating dummy traffic;
\end{itemize}
\item act as dishonest node, $a_{d}$, which can involve:
\begin{itemize}
\item pretending to forward traffic but not doing so,
\item or, possibly pretending to create dummy traffic but not doing so, or
sending dummy traffic easily recognizable as such,
\item or, possibly using the traffic which passes to compromise the
anonymity of the system;
\end{itemize}
\item send messages through conventional, non anonymous channels, $a_{n}$.
\end{itemize}
\item The payoffs $U$ for the agents come from:
\begin{itemize}
\item subjective value of sending messages anonymously. This is
function of the subjective value of the information successfully
arriving at its destination, $v_{r}$, the subjective value of the
information remaining anonymous, $v_{a}$, the perceived level of
anonymity in the system, $p_{a}$ (i.e., the probability that sender
and message will remain anonymous)\footnote{Simple probability may
not be the ultimate best measure of anonymity. For example, it is
likely that information theoretic metrics as in
\cite{Serj02,Diaz02} are better. However, probabilities are
typically simpler and also better than the common ``anonymity set''
representation of anonymity. Detailed discussion of such issues
are beyond the scope of this paper.}, the perceived level of
reliability in the system, $p_{r}$ (i.e., the probability that the
message will be delivered). The subjective value of the information
being sent is possibly correlated to potential profits the agent
expects to make by keeping certain messages anonymous or potential
losses that the agents expects to avoid by keeping certain messages
anonymous. The level of anonymity in the system is function of
traffic (number of agents sending messages in the system, $n_{s}$)
and mixes (number of agents acting as honest nodes, $n_{h}$;
however, at parity of traffic, sensitive agents might want fewer
nodes in order to maintain high anonymity sets). The level of
reliability in the system is inverse function of the number of
dishonest nodes in the system, $n_{d}$. However, it must be noted
that different users might value reliability and anonymity
differently. In particular, even if agents agree on a metrics for
reliability and a metrics for anonymity, some might care more about
anonymity than reliability, some viceversa.
\item benefits of acting as a node (e.g., nodes might be retributed
for forwarding traffic or for creating dummy traffic), $b_{h}$;
\item benefits of acting as dishonest node (e.g., dishonest node might
benefit from disrupting the service or might make use of the
information that passes through them), $b_{d}$;
\item costs of using the system by:
\begin{itemize}
\item sending messages:
\begin{itemize}
\item through the mix-net system, $c_{s}$,
\item or through the conventional, non anonymous system, $c_{n}$;
\end{itemize}
\item receiving dummy traffic, $c_{r}$;
\end{itemize}
\item costs of acting as honest node, $c_{h}$ by:
\begin{itemize}
\item receiving and forwarding traffic,
\item creating dummy traffic,
\item being exit node (which involves potential exposure to
liabilities or abuses);
\end{itemize}
(we might note that there might be both fixed and variable costs in
being a node, the fixed costs related to the investment necessary to
setup the software, the variables being most likely related to
traffic passing through the node);
\item costs of acting as dishonest node, $c_{d}$ (e.g., being exposed
as a dishonest node carries a monetary penalty).
\item In addition to the above costs and benefits, there might be also
\textit{reputation} costs and benefits from:\
\begin{itemize}
\item using the system to send messages (e.g., there can be a
reputation cost of being exposed as a sender of anonymous messages
even though the sent messages themselves do remain anonymous),
\item acting as perceivably honest node (e.g., there can be a
reputation benefit by acting as node),
\item acting as perceivably dishonest node (e.g., there can be a
reputation cost by being exposed as a dishonest node, and the
costs here will be also function of the probability of being
exposed as a bad node);
\end{itemize}
These reputation costs and benefits might be simply ``internal'' to
the system (e.g., being perceived as a honest node brings that node
more traffic, and therefore more possibilities to hide that node's
messages; similarly, being perceived as a dishonest node might bring
traffic away from that node), in which case they will not enter
directly the utility functions of the agents, but will enter
indirectly through the changes they provoke in the behavior of the
agents.
\end{itemize}
\item Agents want to maximize their expected utility, which is some
function of expected benefits minus expected costs. We can start
representing the utility\ for a generic agent $i$ in the following
compact form:
\begin{equation*}
u_{i}=u\left( \gamma \left( v_{r},p_{r}\right) \partial \left(
v_{a},p_{a}\right) +b_{d,h}-c_{s,h,d,n,r}\right)
\end{equation*}
\end{itemize}
where $u$ is for the moment an unspecified functional form. This
function includes the costs and benefits for all the possible actions
of the agents, including \textit{non} using the mix-net and sending
the messages through a non anonymous channel (in which case, for
example, the probability of remaining anonymous, $p_{a}$, will be
equal to zero and the only cost in the function will be $c_{n}$). Note
that $\gamma $ and $\partial \ $represents functions of the
probability of a message being delivered and a message remaining
anonymous respectively. These probabilities are weighted with the
values $v_{r,a}$ because different $i$s might value anonymity and
reliability differently.
\section{Application}
The above system is a very general overview of economic issues related
to the \textit{actual} use of \textit{actual} anonymous systems. As it
is, such overview is however unmanageable for economic analysis, but
it can be used as a framework for the study of limited scenarios given
specific assumptions.
Hence, a possible starting model based on the latter simplification is
the following. We consider a set of $n_{s}$ agents interested in
sending anonymous communications. They come in two types - those with
high sensitivity to privacy and those with a lower (but not zero)
sensitivity. There is only one system which can be used to send
anonymous messages, and one another system to send non anonymous
messages. Each user has three options: only send her own messages
through the mix-net, or send her messages but also act as node
forwarding other users' messages, or send a message without using the
mix-net. This means that initially we do not consider the strategy of
choosing to be a bad node or additional honest strategies like
creating and receiving dummy traffic.
\subsection{Adversary}
We do not consider our strategic agents as potentially choosing to be
bad nodes; nonetheless we do consider that there may be a percentage
of bad nodes and that agents respond to this possibility. Specifically
we assume a global passive adversary (GPA) that can observe all
traffic on all links (between users and nodes, between nodes, and
between nodes or users and recipients). Additionally, the adversary is
assumed to include some percentage of mix-nodes. In choosing
strategies agents will attach a subjective probability to arbitrary
nodes being compromised, i.e., all nodes not run by the agent are
assigned the same probability of being compromised by that agent. This
will be a factor in their assessment of the probability of the
anonymity of messages they send. For our purposes, it will not matter
whether the set of compromised nodes is static or dynamic (as in
\cite{syverson_2000}). In general, we assume that all agents will
attach the same probability of compromise to all nodes (except for
nodes that an agent herself owns). A purely passive adversary is
unrealistic in most settings, e.g., it assumes that hostile users
never selectively send messages at certain times or routes, and
neither nodes nor links ever selectively trickle or flood messages
\cite{trickle02}. Nonetheless, a \emph{global} passive adversary is
still quite strong, indeed unrealistically so, and a typical starting
point of anonymity analyses.
\subsection{(Honest) Strategic Agents}
If a user only sends her messages, the cost of using the anonymous
service is slightly higher than using the non anonymous channel. If a
user decides to be a node, costs increase with the traffic. The
traffic depends on the number of users in the system (but, as
mentioned above, the traffic also affects the level of anonymity).
Given that there are no actively bad nodes (and assuming that the only
possible failures are hostile ones), reliability is deterministically
complete ($p_{r}=1$). Even if all messages are assumed to arrive, they
may take much longer to arrive through the anonymity system than if
sent without it. Perception of this can be reflected in the difference
of $c_s$ and $c_n$. We also assume that all agents know the number of
agents using the system and the number of them acting as nodes, and
that each specific agent's actions are observable. Furthermore, we
assume that the type of an agent is publicly known (i.e. a high
sensitivity type cannot pretend to be a low type). As already noted,
we also assume that all agents perceive anonymity the same way.
These assumptions let us reformulate the framework above in a simpler
way. Imagine that both agent types use the system because they want
to avoid potential losses from not being anonymous. The types differ
in their sensitivity to those losses: high, $v_{H}$, and low, $v_{L}$.
Then, the utility function above can be written in a simpler form:
\begin{equation*}
u_{i}=-v_{i}\left( 1-p_{a}\left( n_{s},n_{h},d_{i}\right) \right)
-c_{s}-c_{h}\left( n_{s}\right) -c_{n}
\end{equation*}
The above function reads in the following way: each agent $i$ tries to
\textit{minimize} the costs of sending messages and the risk of them
being tracked. $1-p_{a}\left( n_{s},n_{h},d_{i}\right) $ is the
probability that the anonymity will be lost given the number of agents
sending messages, the number of them acting as nodes, and the action
$d$ of agent $i$ itself. For example, suppose that there are a
thousand agents sending messages at regular intervals (no more than
one message per agent is sent to any incoming node at a time), that
the probability of any node being compromised is $0.1$, and that
messages pass through three nodes before exiting the network. If an
agent runs a mix node with firing threshold of 50, then the worst
probability of anonymity loss a message he sends can have is $.02
\times .1 \times .1 = .0002$. If he does not run a node, then the
worst probability is five times that. $v_{i}$ is the disutility an
agent derives
from its message being exposed; we assume that $v_{i}=\left[ v_{L},v_{H}%
\right] $. $c_{s},c_{h}\left( n_{s}\right) ,c_{n}$ are the costs of
sending a message through the mix-net system, acting as node when
there are $n$ agents sending messages, and sending messages through a
non anonymous system respectively. Given that the strategy space
discussed in this section is only composed of 3 possible actions (only
send her own messages through the mix-net, $a_{s}$, or send her
messages but also act as node forwarding other users' messages,
$a_{h}$, or send a message without using the mix-net, $a_{n} $), it
must compare the disutility coming from those three actions:
\begin{equation*}
\begin{tabular}{cc}
Action & Payoff \\
$a_{s}$ & $-v_{H,L}\left( 1-p_{a}\left( n_{s},n_{h}\right) \right) -c_{s}$
\\
$a_{h}$ & $-v_{H,L}\left( 1-p_{a}\left( n_{s},n_{h},d_{i}\right) \right)
-c_{s}-c_{h}\left( n_{s}\right) $ \\
$a_{n}$ & $-v_{H,L}-c_{n}$%
\end{tabular}
\end{equation*}
which means, for example, that when $-v_{H,L}\left( 1-p_{a}\left(
n_{s},n_{h},d_{i}\right) \right) -c_{s}-c_{h}\left( n_{s}\right)
<\left[
-v_{H,L}\left( 1-p_{a}\left( n_{s},n_{h}\right) \right) -c_{s},-v_{H,L}-c_{n}%
\right] $, the agents will choose to become a node in the mix-net.
Note that we do not allow the agent to choose not to send a message at
all, which would of course mimize the risk of anonymity compromise.
Rather, she can only choose amongst the three given actions. Note also
that since message delivery is guaranteed, a node might always choose
a longer route to reduce risk. We could assign a higher $c_s$ to
longer routes to reflect the cost, e.g., of additional delay; however,
to keep things simple, we assume that all messages pass through the
mix-net system in fixed length free routes.
Can this be represented in a game theoretical matrix form? -
\textit{such as, for example}:
\begin{equation*}
\begin{tabular}{cccc}
Player 1/All other players & $a_{s}$ & $a_{h}$ & $a_{n}$ \\
$a_{s}$ & payoff player 1, payoff other player & ... & ... \\
$a_{h}$ & ... & ... & ... \\
$a_{n}$ & ... & ... & ...
\end{tabular}
\end{equation*}
The problem in representing the above problem is that each agent is
playing with a large, but not infinite number of other players.
Fudenberg and Levine \cite{fudenberg88} have a model where each player
plays a set of identical player each of which is ``infinitesimal'',
i.e. its actions cannot affect the payoff of the first player - and it
is already a very complicated model indeed. In this setup what we want
to study is, instead, the concatenated interactions in a large but not
infinite set of players, which are not identical (we are considering
two types).
The goal here is to study what dynamics arise as the agents are faced
with the various choices in a repeated-game setup. Imagine such
repeated setup and the high sensitivity agents start by collaborating,
i.e. acting as nodes. ``Defection'' would be, for example, acting as
user only and refusing to be a node. This would happen because the
agents start realizing that there is enough anonymity in the system
and they do not need to be a node any longer. But if too many agents
act this way, the system might break down for lack of nodes, after
which everybody would have to resort to non anonymous channels. Can
there be equilibria where the high sensitivity keep on acting as nodes
and the low sensitivity keep on using the system? There might be,
possibly in 3 scenarios:
\begin{enumerate}
\item Simply out of the analysis of the game as it is, some
cooperative equilibria are enforceable even in non infinite horizons
when the actions of the players are detectable: in these cases the
strategy spaces for the ``high'' agents will be something like,
cooperate until everybody cooperates (i.e., act as node), then
defect forever (i.e., do not use the system). This might be
enforceable especially if the trigger strategy is particularly
painful (in other words, if the players \textit{really} need some
form of anonymous channel). The problem however is that this also
might strongly rely on the fact that the type of the agent must be
known, i.e. the agents cannot misrepresent themselves (maybe not,
but this has to be studied).
\paulcomment{Can't there be an equilibrium in which the enhanced
anonymity of running your own node will mean that ``high'' agents
will want to do so, even if all the other high agents already do.
That strikes me as a natural possibility depending on the initial
conditions and other assumptions. Also, in this case the
assumption that agent type is known goes away.}
\item Having a ``special agent'' whose utility function has been
modified to consider the social value of having an anonymous system,
or which is being paid for or supported to provide such service
(this, however, practically brings the analysis back to square one,
as again the high type might decide to rely only on the special
agent and not provide their services as nodes).
\item Bilateral contracts (see also below, ``Extensions'') between
agents to agree on cooperation and punishments for breaching
cooperation.
\item Reputation: We already had a bunch of stuff about reputation in
the paper that prompted this work. We should mine that for here. It
can play a role in various forms
\begin{itemize}
\item mojonation: fill in the details
\item high performing high volume ``high'' nodes can attract more
traffic, get more cover for their highly sensitive anonymous
communication
\item related to the ``special agent'' above. Some nodes will attach
a value to having good mix-nets available. Altruistic self interest
or some such. They want the world to be a better place. We
shouldn't ignore that as a factor in such things. Similarly, one
could imagine government services for same (even if most of the
current community can't imagine such a thing ;-)
\end{itemize}
\end{enumerate}
\section{Extensions}
\begin{itemize}
\item Dummy traffic increases costs but it also increases anonymity.
Here we can study bilateral or multilateral contracts between
agents, forcing contractually each agent to send to another agent(s)
a certain number of messages in each period - this means that if the
sending agent has not enough real messages going through its node,
it will have to generate them as dummy traffic.
\item Assume strategic bad node can exist: reliability goes down, and
anonymity goes down.
\item The type of the agent is not know (i.e., there is a certain
probability it is an high sensitivity vs. a low sensitivity type).
\item Compare mix-net system to other systems.
\item Consider costs of being exit nodes.
\item The ``application'' considered in the previous section and the
above ``extensions'' might be studied in an agent-based simulation
framework, where a certain number of agents of the various types
(high sensitivity, low sensitivity, etc.) might be created and then
``launched'' onto the mix-net arena with a set of predefined
strategies (e.g., always cooperate, always defect, tit-for-tat,
etc.). Similar agent-based studies have been done in economics to
study, for example, Hal Varian's model of sales.
\end{itemize}
\bibliographystyle{alpha}
\bibliography{econymics}
\end{document}
--- NEW FILE: llncs.cls ---
% LLNCS DOCUMENT CLASS -- version 2.8
% for LaTeX2e
%
\NeedsTeXFormat{LaTeX2e}[1995/12/01]
\ProvidesClass{llncs}[2000/05/16 v2.8
^^JLaTeX document class for Lecture Notes in Computer Science]
% Options
\let\if@envcntreset\iffalse
\DeclareOption{envcountreset}{\let\if@envcntreset\iftrue}
\DeclareOption{citeauthoryear}{\let\citeauthoryear=Y}
\DeclareOption{oribibl}{\let\oribibl=Y}
\let\if@custvec\iftrue
\DeclareOption{orivec}{\let\if@custvec\iffalse}
\let\if@envcntsame\iffalse
\DeclareOption{envcountsame}{\let\if@envcntsame\iftrue}
\let\if@envcntsect\iffalse
\DeclareOption{envcountsect}{\let\if@envcntsect\iftrue}
\let\if@runhead\iffalse
\DeclareOption{runningheads}{\let\if@runhead\iftrue}
[...976 lines suppressed...]
\def\sectionmark##1{}%
\def\subsectionmark##1{}}
\def\ps@titlepage{\let\@mkboth\@gobbletwo
\let\@oddfoot\@empty\let\@evenfoot\@empty
\def\@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}%
\hfil}
\def\@oddhead{\normalfont\small\hfil\hspace{\headlineindent}%
\llap{\thepage}}
\def\chaptermark##1{}%
\def\sectionmark##1{}%
\def\subsectionmark##1{}}
\if@runhead\ps@headings\else
\ps@empty\fi
\setlength\arraycolsep{1.4\p@}
\setlength\tabcolsep{1.4\p@}
\endinput
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/