\documentclass[landscape]{slides}

\newif\ifpdf
\ifx\pdfoutput\undefined
   \pdffalse
\else
   \pdfoutput=1
   \pdftrue
\fi

\begin{document}
\ifpdf
  \pdfcompresslevel=9
  \pdfpagewidth=\the\paperwidth
  \pdfpageheight=\the\paperheight
\fi

% slide 1
\begin{slide}
\begin{center}
Reliable MIX Cascade Networks through Reputation\\
\vspace{1in}
Roger Dingledine, Reputation Technologies\\
Paul Syverson, Naval Research Lab\\
\end{center}
\end{slide}

%slide 2
\begin{slide}
\begin{center}
The Problem
\end{center}
\begin{itemize}
\item The current remailer infrastructure is unreliable \\
\item This unreliability decreases anonymity
\begin{itemize}
\item many dropped/repeated messages
\item fewer users
\end{itemize}
\end{itemize}
\end{slide}

% slide 3
\begin{slide}
\begin{center}
Ways of Improving Reliability
\end{center}
\begin{itemize}
\item Build protocols with provable robustness guarantees
\item Provide economic incentives for reliability
\item Add reputation to ``improve'' reliability
\vspace{1in}
\item Distinction between reliability and robustness
\end{itemize}
\end{slide}

% slide 4
\begin{slide}
\begin{center}
Related Work
\end{center}
\begin{itemize}
\item MIXes (Chaum)
\item Robust MIX-nets (Flash Mix, Universally Verifiable MIX) 
\item Deployed Remailer Systems (cypherpunks, Mixmaster)
\item Remailer statistics (Levien's statistics, Jack B Nymble 2)
%\item Network routing protocols (OSPF, etc)
\end{itemize}
\end{slide}

%slide 6
\begin{slide}
\begin{center}
Adversary Goals 
\end{center}
\begin{itemize}
\item Break Anonymity:
\begin{itemize}
\item Discover linkability between sender and receiver
\item Identify the sender or receiver of a given message
\item Trace a sender forward (or a receiver backward) to any messages. 
\end{itemize}
\item Break Reliability: deny service to users
\end{itemize}
\end{slide}

%slide 7
\begin{slide}
\begin{center}
Threat Model --- Adversary can:
\end{center}
\begin{itemize}
\item Passively read \emph{all traffic}
\item Compromise some fraction of the MIXes \\
(Insert, modify, delay, or drop messages)
\end{itemize}
\end{slide}

%slide 5
\begin{slide}
\begin{center}
Previous paper at Info Hiding 4
\end{center}
\begin{itemize}
\item MIXes write per-hop receipts to prove good service; witnesses verify
and tally failure claims.\\ \\ But:
\item Global witnesses are trust and communication \emph{bottlenecks}
\item Owning high reputation nodes means you own more paths? 
\end{itemize}
\end{slide}

%slide 8
\begin{slide}
\begin{center}
What's a MIX cascade? 
\end{center}
\begin{itemize}
\item Fixed path through the MIX network
\item Longer cascades $\Rightarrow$ lower chance all bad nodes $\Rightarrow$ \\
more anonymity
\item Longer cascades $\Rightarrow$ lower chance all good nodes $\Rightarrow$ \\
less reliability
\item Cascades provide more defense against \emph{intersection attack}.
\end{itemize}
\end{slide}

%slide 9
\begin{slide}
\begin{center}
Design Overview 
\end{center}
\begin{itemize}
\item Cascades rearrange periodically (e.g., daily)
\item A node fails its own cascade if it detects misbehavior 
\item Nodes send test messages to monitor their cascades
\item Senders can demonstrate decryptions to show failure
\item All nodes in cascade get $+1$ reputation if it succeeds\\
$-1$ if it fails.
\end{itemize}
\end{slide}

%slide 10
\begin{slide}
\begin{center}
Communal Randomness 
\end{center}
\begin{itemize}
\item Goal: collaborating nodes cannot predict the cascades
\item Centralized (but verifiable) for convenience
\item All nodes commit, then all reveal
\item But nodes can influence communal value by not revealing?
\item Solution is ``Temporarily secret commitment'' \\
can break with computation
%\item Xor might not work (maybe malleable). So concatenate and hash.
\end{itemize}
\end{slide}

%slide 11
\begin{slide}
\begin{center}
Heuristics for picking cascades 
\end{center}
\begin{itemize}
\item Increase cost of breaking anonymity \\
(pick randomly from all nodes)
\item Increase cost of breaking reliability \\
(pick only from high-reputation nodes) 
\end{itemize}
\end{slide}

%slide 12
\begin{slide}
\begin{center}
Attack: Creeping Death
\end{center}
\begin{itemize}
\item Adversary strategy: Fail cascade if more damage to good nodes than bad
\item Adversary can get to any point in reputation spectrum!
\item Works even with few nodes (10-20\%)
\end{itemize}
\end{slide}

%slide 13
\begin{slide}
\begin{center}
Need to limit number of bad nodes in network
\end{center}
\begin{itemize}
\item Proof of work, proof of bandwidth not strong enough
\item Advogato trust metric: \\
Number of bad nodes certified is based on number of \\
confused nodes (good nodes that might certify bad nodes)
\item Certify by trustworthiness, not expected performance
\end{itemize}
\end{slide}
 
%slide 14
\begin{slide}
\begin{center}
So how do we choose cascades?
\end{center}
\begin{itemize}
\item Pick a target safety factor $S$ (eg $1$ in $10^5$ paths bad)
\item Choose first cascade randomly from large enough pool of high-reputation nodes
\item Replace chosen nodes to maintain pool size
\item When pool contains all remaining nodes, just build remaining cascades randomly
\end{itemize}
\end{slide}
 
%slide 15
\begin{slide}
\begin{center}
How do we decide this pool size?
\end{center}
$p$ = Fraction of nodes that are bad, e.g. $20\%$ \\
$s$ = Scare factor: acceptable risk of bad path, e.g. $10^{-5}$ \\
$l$ = Length of a cascade, e.g. $4$ \\
$c$ = recommended number of Chained cascades, e.g. $3$ \\
$r$ = Range: size of pool from which cascades are chosen: \\
$$
\left(\frac{p}{r}\right)^{lc} =s \;\;\;\;\;\; r=
\frac{p}{s^{\frac{1}{lc}}} \;\;\;\;\;\; r = \frac{.2}{(10^{-5})^{\frac{1}{12}}} = 0.522
$$
\end{slide}
 
%slide 16
\begin{slide}
\begin{center}
Detecting Misbehavior
\end{center}
\begin{itemize}
\item Entry point: Incoming messages rejected?
\item Inside cascade: Messages replaced with dummy messages?
\item Exit point: Messages not delivered?
\end{itemize}
\end{slide}
 
%slide 17
\begin{slide}
\begin{center}
Detecting Misbehavior at Entry Point
\end{center}
\begin{itemize}
\item Alice can send into any node. They all deliver to the head.
\item Thus nodes can insert indistinguishable test messages
\item Alice gets a receipt (if not, she tries elsewhere)
\item Head publishes batch snapshot (hashes of messages)
\item If message not in snapshot, receipt proves misbehavior
\end{itemize}
\end{slide}
 
%slide 18
\begin{slide}
\begin{center}
Detecting Misbehavior Inside Cascade
\end{center}
\begin{itemize}
\item The head can publish message in batch snapshot, but silently drop it!
\item Alice might become suspicious and send a test message
\item If test message is dropped, Alice can demonstrate message decryption to any node
\item An honest node will check the batch snapshot and agree
\end{itemize}
\end{slide}
 
%slide 19
\begin{slide}
\begin{center}
Detecting Misbehavior at Exit Point
\end{center}
\begin{itemize}
\item Tail bounces traffic to all nodes. All nodes deliver.
\item If inserted test message doesn't arrive, somebody failed.
\item Optimize: if tail collects a delivery receipt, no broadcast.
\end{itemize}
\end{slide}
 
%slide 20
\begin{slide}
\begin{center}
Test messages
\end{center}
\begin{itemize}
\item Nodes reuse recipient addresses in test messages
\item Reusing addresses helps protect against time-based \\
intersection attack
%\item Plaintext is distinguishable --- \\
%sender must encrypt for reliability
\end{itemize}
\end{slide}
 
%slide 21
\begin{slide}
\begin{center}
Quality of Service, Resource Management
\end{center}
\begin{itemize}
\item Nodes send failure messages and hourly heartbeats to \\Reputation Servers
\item Users compare advertised QoS and reputation from each\\ cascade $\Rightarrow$ load balancing
\item Reputation Servers are redundant and static
\item Users must download \emph{all} heartbeats, or via MIX-net or PIR for anonymity
\end{itemize}
\end{slide}
 
%slide 22
\begin{slide}
\begin{center}
Future Directions 
\end{center}
\begin{itemize}
%\item Proof of bandwidth (like proof of work) to reduce reliance on web of trust
\item Better bandwidth use
\item More research on creeping death
\item Adapt to free-route MIX network
\item Figure out the details of the reputation servers
\item Reliability metric and model (same with Efficiency)
\end{itemize}
\end{slide}

\end{document}