Probabilistic Anonymity

Mohit Bhargava, IIT New Delhi

Catuscia Palamidessi, INRIA Futurs & LIX

Probabilistic Anonymity

22

Plan of the talk

The concept of anonymity

Anonymity and nondeterminism

Example: the Dining Cryptographers

Conditional probability

Anonymity and randomization

The randomized Dining Cryptographers

Analysis and verification in probabilistic π-calculus

Generalized D.C.

Conclusion

Probabilistic Anonymity

22

The concept of anonymity

Goal:

To ensure that a certain part of an information becomes public while another part of it remains secret.

Typically, what we want to maintain secret is the identity of the agent involved

Examples:

Electronic elections

Delation

We will consider the case of in which the information to make public is whether or not a certain event has taken place, and the information to hide is the identity of the agent performing that event

Probabilistic Anonymity

22

Anonymity and nondeterminism (1/2)

Work by Schneider and Sidiropoulos, ESORICS 1996

Events are modeled as consisting of two components: the event itself, x, and the identity of the agent performing the event, a

ax

AnonyAgs: the agents who want to remain secret

Given x, define A = {ax | a AnonyAgs }

A protocol described as a process P provides anonymity if an arbitrary permutation r of the events in A, applied to the traces of P, does not change the traces

r(Traces(P)) = Traces(P)

Probabilistic Anonymity

22

Anonymity and nondeterminism (2/2)

In general, given P, consider the sets:

A = { ax | a AnonyAgs } : the actions that we want to know only partially (we want to know x but not a)

B : the actions that we want to observe

C = Actions – (B U A) : The actions we want to hide

B

C

A

The observables to consider for the Anonymity analysis must abstract wrt the

events in C.

Definition: The system is anonymous if an arbitrary permutation r of the events in A, applied to the traces of P, does not change the observables

r(Traces(P)) = Traces(P)

Probabilistic Anonymity

22

The dining cryptographers (1/6)

Problem and solution formulated originally by David Chaum, J. Cryptology, 1988

The Problem:

Three cryptographers share a meal

The meal is paid either by the organization (master) or by one of them. The master decides who pays

Each of the cryptographers is informed by the master whether or not he is has to pay

GOAL:

The cryptographers would like to know whether the meal is being paid by the master or by one of them, but without knowing who among them, if any, is paying. They cannot involve the master

Probabilistic Anonymity

22

The dining cryptographers (2/6)

Crypt(0)

Crypt(1)

Crypt(2)

Master

pays0

notpays0

Probabilistic Anonymity

22

The dining cryptographers (3/6)
A solution

Each cryptographer tosses a nondeterministic coin. Each coin is in between two cryptographers.

The result of each coin-tossing is visible to the adjacent cryptographers, and only to them.

Each cryptographer examines the two adjacent coins

If he is paying, he announces “agree” if the results are the same, and “disagree” otherwise.

If he is not paying, he says the opposite

Probabilistic Anonymity

22

The dining cryptographers (4/6):
A solution

Crypt(0)

Crypt(1)

Crypt(2)

Master

Coin(2)

Coin(1)

Coin(0)

pays0

notpays0

look20

agree1 /

disagree1

Probabilistic Anonymity

22

The dining cryptographers (5/6)
Properties of the solution

Proposition 1 (Public information): if the number of “disagree” is even, then the master is paying. Otherwise, one of them is paying.

Proposition 2 (Anonymity): In the latter case, if the coin is fair then the non paying cryptographers and the external observers will not be able to deduce whom exactly is paying

Probabilistic Anonymity

22

The dining cryptographers (6/6)
Automatic verification

Schneider and Sidiropoulos verified the anonymity of the solution to the dining cryptographers by using CSP.

The protocol : system P of parallel CSP processes (master, cryptographers, coins)

A (anonymous events): pays0, notpays0, …, notpays2

B (observable events): agree0, disagree0, …, disagree2

C (hidden events): results of coins

Observables : all traces of P with events from C removed

For every permutation rρ on A, we have

ρr(Traces(P)) = Traces(P)

Probabilistic Anonymity

22

Limitations of the nondeterministic approach

The nondeterministic components must be produced by random devices

nondeterministic coin  random coin

An observer may deduce info about the system from the probability distribution of the devices.

This possibility is not captured by the nondeterministic formulation: The nondeterministic definition is “too coarse”

For example, if we know that two adjacent coins are biased, we can deduce when the corresponding cryptographer is likely to be lying

The probability distribution of the devices may be guessed by testing the system

For example in if the cryptographers are more than 3, we can deduce that two coins are biased by looking at the results several times

Probabilistic Anonymity

22

Conditional probability (1/3)

We propose a notion of anonymity based on conditional probability

A brief recall of the notion of conditional probability

Puzzle:

A king offers to a guest to pick one of three closed boxes. One contains a diamond, the other two are empty

After the guest has picked a box, the king opens one of the other two boxes and shows that it is empty

Then the king offers to the guest to exchange the box he picked with the other (closed) one

Question: should the guest exchange?

Probabilistic Anonymity

22

Conditional probability (2/3)

Answer: it depends on whether the king opens intentionally an empty box, or not.

In the first case, the guest should better change his choice since the other box has now probability 2/3 to contain the ring

In the second case, it does not matter. Both the remaining closed boxes have now probability ½ to contain the ring

Probabilistic Anonymity

22

Conditional probability (3/3)

pb(X|Y)	= conditional probability of X given Y

= pb(X and Y) / pb(Y)

Let us consider again the puzzle in Case 2

Bi = Box i contains the ring

Initially: pb(B1) = pb(B2) = pb(B3) = 1/3

After opening one box, say Box 1, if it turns out to be empty, we have:

pb(B2)	= pb(B2 | not B1)

= pb(B2 and not B1) / pb(not B1)

= pb(B2)/pb(not B1)

= (1/3) / (2/3)

= 1 / 2

Probabilistic Anonymity

22

Anonymity and randomization (1/2)

Remember that, given P, we consider the sets:

A = { ax | a AnonyAgs } : the actions that we want to know only partially (we want to know x but not a)

B : the actions that we want to observe (it may include x but not a)

C = Actions – (B U A) : The actions we want to hide

B

C

A

Probabilistic Anonymity

22

Anonymity and randomization (2/2)

The observables must abstract wrt C

Definition: The system is anonymous if for every nonderministic choice, for every observations O1,O2 in which x happens, and for every action ax  A, we have

pb(ax | O1) = pb(ax | O2)

i.e. the observables do not allow to deduce anything about the identity of the agent

Equivalently: for every O, a and b, we have

pb(O | ax) = pb(O | bx)

namely, the probability of an observable does not depend on the identity of the agent

Note that the second formulation can be regarded as the probabilistic version of the definition of Schneider/ Sidiropoulos

Note that in general pb(ax | O) =/= pb(bx | O), hence the latter cannot be a good definition of probabilistic anonymity

Probabilistic Anonymity

22

The randomized dining cryptographers

Each cryptographer tosses a probabilistic coin

The master is probabilistic

All the rest is the same as before

Probabilistic Anonymity

22

Verification in probabilistic -calculus

We have verified the anonymity of the randomized solution to the dining cryptographers by using the probabilistic -calculus.

The protocol : system P of parallel processes:

Master: probabilistic (blind)

Coins: probabilistic (blind)

Cryptographers: deterministic

A (anonymous events): pays0, notpays0, …, notpays2

combination chosen nondeterministically

C (hidden events): results of coins

chosen probabilistically

B (observable events): agree0, disagree0, …, disagree2

Determined by the choice of the master and of the coins

Observables : all traces of P with events from C removed

For every i,k, and for every combination O of agree/disagree, we have

pb(O | paysi) = pb(O | paysk)

Probabilistic Anonymity

22

The generalized dining philosophers

In general, given an arbitrary graph, where the nodes represent the cryptographers, and the arcs the coins, we can extend the protocol as follows:

bi = 0 if cryptographer i does not pay,

bi = 1 otherwise

coink = 0 if coin k gives head,

coink = 1 otherwise

crypti = output of cryptographer i,

calculated as follows:

crypti = k adjacent i coink + bi

where the sums are binary

Crypti

Coink

Probabilistic Anonymity

22

The protocol in the general case

Proposition: there is a payer iff

i crypti = 0

Proof: just observe that in this sum each coink is counted twice. Furthermore there is at most one k s.t. bk = 1. Hence the result is 0 iff there is no k s.t. bk = 1.

Proposition: If all the coins are fair, and the graph is connected, then

the system is anonymous for every external observer

the system is anonymous for any node j such that, if we remove j and all its adjacent arcs, the rest of the graph is still connected

Probabilistic Anonymity

22

Conclusion

Notion of probabilistic anonymity

Extending the classic one of Schneider-Sidiropoulos

Application to the example of the generalized dining cryptographers

Verification using the probabilistic -calculus

Concurrency 5

catuscia

2003-10-30T00:17:22