Probabilistic and Information-Theoretic Approaches to Anonymity
Spécification et vérification des protocoles de sécurité probabilistes
Abstract
The concept of anonymity comes into play in those cases in which we want to keep secret the identity of the agents participating to a certain event. There is a wide range of situations in which this property may be needed or desirable; for instance: voting, web surfing, anonymous donations, and posting on bulletin boards. Anonymity is often formulated in more general way as an information-hiding property, namely the property that a part of information relative to a certain event is kept secret. One should be careful, though, not to confuse anonymity with other properties that the same description, notably confidentiality (aka secrecy). Let us emphasize the difference between the two concepts with respect to sending messages: confidentiality refers to situations in which the content of the message is to be kept secret; in the case of anonymity, on the other hand, it is the identity of the originator, or of the recipient, that has to be kept secret. Analogously, in voting, anonymity means that the identity of the voter associated with each vote must be hidden, and not the vote itself or the candidate voted for. Other notable properties in this class are privacy and noninterference. Privacy refers to he protection of certain data, such as the credit card number of a user. Noninterference means that a low user will not be able to acquire information about the activities of a high user. A discussion about the difference between anonymity and other information-hiding properties can be found in [HO03, HO05]. An important characteristic of anonymity is that it is usually relative to the capabilities of the observer. In general the activity of a protocol can be observed by diverse range of observers, di?ering in the information they have access to. The anonymity property depends critically on what we consider as observables. For example, in the case of an anonymous bulletin board, a posting by one member of the group is kept anonymous to the other members; however, it may be possible that the administrator of the board has access to some privileged information that may allow him to infer the identity of the member who posted it. In general anonymity may be required for a subset of the agents only. In order to completely define anonymity for a protocol it is therefore necessary to specify which se (s) of members have to be kept anonymous. A further generalization is the concept of anonymity with respect to a group: the members are divided into a number of sets, and we are allowed to reveal to which group the user responsible for the action belongs, but not the identity of the user himself. Various formal definitions and frameworks for analyzing anonymity have been developed in literature. They can be classied into approaches based on process-calculi ([SS96, RS01]), epistemic logic ([SS99, HO03]), and function views ([HS04]). Most of these approaches are based on the so-called principle of confusion : a system is anonymous if the set of possible observable outcomes is saturated with respect to the intended anonymous users. More precisely, if in one computation the culprit (the user who performs the action) is i and the observable outcome is o, then for every other agent j there must be a computation where j is the culprit and the observable is still o. This approach is also called possibilistic, and relies on nondeterminism. In particular, probabilistic choices are interpreted as nondeterministic. We refer to RS01] for more details about the relation of this approach to the notion of anonymity.
Le concept de l'anonymat entre en jeu dans les cas où nous voulons garder le secret sur l'identité des agents qui participent à un certain événement. Il existe un large éventail de situations dans lesquelles cette propriété peut être nécessaire ou souhaitable, par exemple: web de vote surf, les dons anonymes, et l'affichage sur les babillards. L'anonymat est souvent formulées de manière plus générale comme une propriété de dissimulation d'informations, à savoir la propriété qu'une partie des informations relatives à un certain événement est tenu secret. Il faut être prudent, cependant, de ne pas confondre anonymat avec d'autres propriétés que la même description, notamment la confidentialité (secret aka). Laissez-nous insister sur la différence entre les deux concepts en ce qui concerne l'envoi de messages: la confidentialité se réfère aux situations dans lesquelles le contenu du message doit être gardée secrète, dans le cas de l'anonymat, d'autre part, c'est l'identité de l'expéditeur ou du destinataire, qui doit être gardée secrète. De la même façon, en votant, l'anonymat signifie que l'identité de l'électeur associés à chaque vote doit être caché, et non pas le vote lui-même ou le candidat a voté pour. D'autres propriétés remarquables de cette catégorie sont la vie privée et la non-ingérence. Protection des renseignements personnels, il se réfère à la protection de certaines données, telles que le numéro de carte de crédit d'un utilisateur. Non-ingérence signifie qu'un utilisateur bas ne seront pas en mesure d'obtenir des informations sur les activités d'un utilisateur élevés. Une discussion sur la différence entre l'anonymat et d'autres propriétés de dissimulation d'informations peuvent être trouvées dans HO03 [, HO05]. Une caractéristique importante de l'anonymat, c'est qu'il est généralement relative à la capacité de l'observateur. En général, l'activité d'un protocole peut être observé par divers observateurs, di? Vrant dans les informations qu'ils ont accès. La propriété anonymat dépend essentiellement de ce que nous considérons comme observables. À titre d'exemple, dans le cas d'un babillard anonyme, une annonce par un membre du groupe est maintenue anonymes aux autres membres, mais il peut être possible que l'administrateur du conseil d'administration a accès à une information privilégiée qui peut lui permettre de déduire l'identité du membre qui l'a publié. Dans l'anonymat peut être exigée pour un sous-ensemble des agents uniquement. Afin de définir complètement l'anonymat d'un protocole, il est donc nécessaire de préciser ce qui se (s) des membres ont de garder l'anonymat. Une généralisation est le concept de l'anonymat à l'égard d'un groupe: les membres sont divisés en un certain nombre de séries, et nous sommes autorisés à révéler à quel groupe l'utilisateur responsable de l'action appartient, mais pas l'identité de l'utilisateur lui-même. Plusieurs définitions formelles et les cadres d'analyse anonymat ont été développés dans la littérature. Elles peuvent être classifiées en ed approches fondées sur les processus de calculs ([SS96, RS01]), la logique épistémique ([SS99], HO03), et des vues de fonction ([HS04]). La plupart de ces approches sont fondées sur le principe dit de confusion: un système est anonyme si l'ensemble des résultats possibles observable est saturé pour les utilisateurs prévus anonymes. Plus précisément, si dans un calcul le coupable (l'utilisateur qui exécute l'action) est i et le résultat observable est o, alors pour tout autre agent j il doit y avoir un calcul où j est le coupable et l'observable est encore o. Cette approche est aussi appelée possibiliste, et s'appuie sur non-déterminisme. En particulier, les choix probabilistes sont interprétés comme non déterministe. Nous nous référons à RS01] pour plus de détails sur la relation de cette approche à la notion d'anonymat.
Domains
Computer Science [cs]
Loading...