Transcript ppt - ALADDIN Center - Carnegie Mellon University

Explorations in
Anonymous Communication
Andrew Bortz
with
Luis von Ahn
Nick Hopper
Aladdin Center, Carnegie Mellon University, 8/19/2003
What is it?


Imagine Alice wants to send a message
to Bob, but doesn’t want anyone,
including Bob himself, to know she sent
it
Imagine Bob wants to receive
messages, but doesn’t want anyone,
including the sender, to know he
received it
Anonymous Communication


Study of how to facilitate
communication while hiding who is
talking to whom.
Applicable to:




Privacy in e-Commerce and in general
Anonymous Bulletin Boards, i.e. AA
Music Trading
Freedom of speech
The Problem

Really two different problems:



Sender anonymity – hiding the honest
sender (originator) of a message
Receiver anonymity – hiding the intended
recipient of a message sent by an honest
sender
Intuitively hard:

Underlying network is not anonymous,
even if it is secure
Hiding from whom?

Many possibilities, but here are some
common ones:






Honest-but-curious users
Passive, global eavesdropping (secure channels)
Honest-but-curious group of users
Malicious group of users
Malicious group of users with eavesdropping
Malicious group of users with eavesdropping and
the ability to drop packets
Not Easy…

How do you show that someone can’t
do something?



As is typical in cryptography…
…show that if they can, they can also do
something that we think/know is really
hard – a reduction
Assumed adversary is normally very
powerful
Scenario


Anonymous service provider
Anonymous communications network



Sender and receiver anonymity, as
described before
A request comes in for service
Considering the need for anonymity, do
you respond?
Scenario 1 Response


No!
Why?


Sender and receiver anonymity don’t
protect you
If sender is an adversary, and he was able
to make it so that you are the only honest
user to receive that request, then by
responding, you reveal your identity
New Definition

This particular attack motivates the search for
a new property:


For lack of a better name, receiver anonymity2
It is a protection for the receiver:


There are always x honest receipients of every message,
for definition of x
Not a necessary property, but it seems
important for an anonymous communications
protocol to be intuitively “useful” – i.e. twoway communication
A Reduction

Byzantine Agreement:



Authenticated Byzantine Agreement:



Essentially a protocol for reliable broadcast
At the end, every participant has the same value sent by the
sender
Same problem, but now we can sign messages
Result: If a protocol is receiver anonymous2, then it
is at least as hard as Authenticated Byzantine
Agreement.
BA and ABA are well-studied “hard” problems, and
have many well-known characteristics, including
lower bounds, that make this reduction very useful.
Break time! Any questions?
And now for something
completely different…
Non-Participation

The most evil of all adversarial
strategies:


Equivalent to pretending to be deaf when
someone is talking to you -- very rude, but
very effective at stopping communication
Apparently fatal to several attempts at
anonymous communication
Why is it so evil?

Because it is non-localized:



Non-participation problems are between
pairs of users
Impossible to tell which user is bad
Protocols that are resistant are so
because they show adaptivity

They modify themselves to no longer
require those users to communicate, while
not losing anonymity or gaining complexity
Tricks and Tips

Important facts:



Two honest users will never not participate,
so they will always communicate
Every pair that no longer communicates
has at least one adversary
If we look at the connection graph, we
see interesting properties
Connection Graph
Red adversary users
form an arbitrary
connected subgraph


Blue honest users
form a complete subgraph
We assume intially a complete connection
graph
This is just an example connection graph of 4
honest users and 5 adversary users
Tricks and Tips 2



The complexity of a protocol can
typically be tied to properties of the
connection graph
In some situations it is possible that the
adversary has to or can be forced to
mimic this behavior
This places constraints on his ability to
interfere
Example:
Non-Participation in k-AMT


Problem: How to broadcast a message
to a group of users when some of them
want to prevent it
Adversary wants to:



Prevent it if possible, but
Slow it down if not
Solutions?
Solution



After every broadcast, if you were
expecting a message and didn’t get it,
complain!
Everyone who got it sends it to the
complainer
Because we assume a reliable network,
he must have gotten it now!
Solution Analysis

Works well, but seems to introduce
additional communication complexity:


An adversary (or a set of them) can
complain every round
Since this forces everyone to send the
broadcast to him, he receives multiple
copies => Bit inefficiency
Another Way



Use the connection graph!
If you don’t get a message, complain.
Everyone removes that edge in the
connection graph, and redefines the
broadcast patterns to not use that edge


If the graph is connected, it is always possible and
easy to do optimally
Problem: an adversary can make the
diameter of the connection graph really big,
thus making broadcast take many rounds
Neat Trick



Require that every node
be part of a complete
subgraph of size k
Since honest users
always will be, then it
doesn’t hurt them
Result: By requiring
the adversary to do it as
well, we can bound the
maximum diameter of
the connection graph at
3n/k
versus
Consequences


Only works because we consider
anonymity to be broken anyway if there
are less than k honest users in a group
(k-anonymity)
Efficiency:


No additional bit complexity
Possibly additional rounds, but bounded by
a small constant dependant on the size of
the group and k
Just the beginning

Just scratches the surface of anonymity:





Formal models
Different techniques
Parallels to data anonymity
Extensions of the idea itself
In other words, lots of fun left… 
Thank you for your time!
That’s it! Any questions?