Every system has certain actors who perform particular actions. Anonymity seeks to "mask" the perpetrator of a given action in a "crowd" of actors. Anonymity contends with more rigorous definitions of privacy like Information Theoretic or Computational Privacy. While being weaker than either, Anonymity affords simpler/efficient solutions.
The following roadmap can be used for reasoning about Anonymity-based solutions.
Identify the actors, actions and entities in D. For example, in a Communication Channel domain, {senders, recipients, routers} are actors, {generate, receive, forward} are actions the actors can do, and {message, address, key pairs} are entities.
Decide the particular actors whose actions are to be anonymized. For example, in a Communication Channel domain, we might wish to enable Sender Anonymity: a sender should be able to send a message to a recipient without other actors in the domain knowing the sender's identity.
Think.
Identify the adversaries that are relevant in D and their abilities. The abilities may depend on the roles that adversaries can assume. For example, a network administrator can only look at messages on the wire, a database administrator can only look at data in tables, an insurance company can only query for data, and so on. Apart from such role-specific actions, adversaries can also be assumed to have "traits" as shown in the table below.
Honest But Curious | := | Passive | Local | Independent |
Deliberate And Malicious | := | Active | Global | Colluding |
The Crowds paper presents a probabilistic scale to quantify the degree of anonymity observed. The important probability ranges are shown below, with a special "Beyond Suspicion" label associated with probability 1/n where n is the number of actors in D.
Absolute Privacy | Probable Innocence | Possible Innocence | Provable Exposure |
0.0 | |-----------------------0.5-----------------------| | 1.0 |
A moderator poses a question Q to a set of participants. The question Q has an enumerable set of answers (e.g., Yes/No). Each participant has an answer (opinion) to Q. Devise a scheme that allows the moderator to send a message m to only those participants that answered in a particular way to Q(e.g., all participants who voted Yes).
The privacy desired is "Opinion Anonymity". It should not be possible for an adversary (moderator/other participants) to realize that a participant answered a certain way.
The scheme relies on the Discrete Log is Hard assumption and is inspired from Oblivious Transfer protocols.
A hospital has a relation R(A1, A2, ..., An) in which each tuple corresponds to a person. A set of attributes (A1, A2, ..., Ai) uniquely identify the corresponding person. Devise a scheme to allow the hospital to export R in as precise a form as possible, without compromising the privacy of the persons ("Record Anonymity").
For example, R might be HealthRecords(SSN, Sex, YearOfBirth, Zip, Race, Symptoms) in which both {SSN} and {Sex, YearOfBirth, Zip, Race} uniquely identify a person.
The scheme relies on generalizing values of (A1,...,Ai) for each tuple such that there are at least k-1 other tuples with identical values of the i attributes.
Precision for each value can be measured by the number of times the generalizing function was applied to it. Precision for a table is then the sum of precision values for all (row, column) cells.