idnits 2.17.1 draft-hansen-privacy-terminology-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** There is 1 instance of too long lines in the document, the longest one being 1 character in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (August 11, 2010) is 5006 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'RFC2119' is defined on line 2219, but no explicit reference was found in the text == Unused Reference: 'Mart99' is defined on line 2305, but no explicit reference was found in the text Summary: 3 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group A. Pfitzmann, Ed. 3 Internet-Draft TU Dresden 4 Intended status: Informational M. Hansen, Ed. 5 Expires: February 12, 2011 ULD Kiel 6 H. Tschofenig 7 Nokia Siemens Networks 8 August 11, 2010 10 Terminology for Talking about Privacy by Data Minimization: Anonymity, 11 Unlinkability, Undetectability, Unobservability, Pseudonymity, and 12 Identity Management 13 draft-hansen-privacy-terminology-01.txt 15 Abstract 17 This document is an attempt to consolidate terminology in the field 18 privacy by data minimization. It motivates and develops definitions 19 for anonymity/identifiability, (un)linkability, (un)detectability, 20 (un)observability, pseudonymity, identity, partial identity, digital 21 identity and identity management. Starting the definitions from the 22 anonymity and unlinkability perspective and not from a definition of 23 identity (the latter is the obvious approach to some people) reveals 24 some deeper structures in this field. 26 Note: In absence of a separate discussion list please post your 27 comments to the IETF SAAG mailing list and/or to the authors. For 28 information about that mailing list please take a look at 29 https://www.ietf.org/mailman/listinfo/saag. 31 Status of This Memo 33 This Internet-Draft is submitted in full conformance with the 34 provisions of BCP 78 and BCP 79. 36 Internet-Drafts are working documents of the Internet Engineering 37 Task Force (IETF). Note that other groups may also distribute 38 working documents as Internet-Drafts. The list of current Internet- 39 Drafts is at http://datatracker.ietf.org/drafts/current/. 41 Internet-Drafts are draft documents valid for a maximum of six months 42 and may be updated, replaced, or obsoleted by other documents at any 43 time. It is inappropriate to use Internet-Drafts as reference 44 material or to cite them other than as "work in progress." 46 This Internet-Draft will expire on February 12, 2011. 48 Copyright Notice 49 Copyright (c) 2010 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents 54 (http://trustee.ietf.org/license-info) in effect on the date of 55 publication of this document. Please review these documents 56 carefully, as they describe your rights and restrictions with respect 57 to this document. Code Components extracted from this document must 58 include Simplified BSD License text as described in Section 4.e of 59 the Trust Legal Provisions and are provided without warranty as 60 described in the Simplified BSD License. 62 Table of Contents 64 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 65 2. Terminology and Requirements Notation . . . . . . . . . . . . 4 66 3. Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 67 4. Anonymity . . . . . . . . . . . . . . . . . . . . . . . . . . 8 68 5. Unlinkability . . . . . . . . . . . . . . . . . . . . . . . . 14 69 6. Anonymity in Terms of Unlinkability . . . . . . . . . . . . . 16 70 7. Undetectability and Unobservability . . . . . . . . . . . . . 19 71 8. Relationships between Terms . . . . . . . . . . . . . . . . . 24 72 9. Known Mechanisms for Anonymity, Undetectability, and 73 Unobservability . . . . . . . . . . . . . . . . . . . . . . . 25 74 10. Pseudonymity . . . . . . . . . . . . . . . . . . . . . . . . . 26 75 11. Pseudonymity with respect to accountability and 76 authorization . . . . . . . . . . . . . . . . . . . . . . . . 31 77 11.1. Digital pseudonyms to authenticate messages . . . . . . . 31 78 11.2. Accountability for digital pseudonyms . . . . . . . . . . 31 79 11.3. Transferring authenticated attributes and 80 authorizations between pseudonyms . . . . . . . . . . . . 32 81 12. Pseudonymity with respect to linkability . . . . . . . . . . . 32 82 12.1. Knowledge of the linking between the pseudonym and 83 its holder . . . . . . . . . . . . . . . . . . . . . . . 33 84 12.2. Linkability due to the use of a pseudonym across 85 different contexts . . . . . . . . . . . . . . . . . . . 34 86 13. Known mechanisms and other properties of pseudonyms . . . . . 37 87 14. Identity management . . . . . . . . . . . . . . . . . . . . . 39 88 14.1. Setting . . . . . . . . . . . . . . . . . . . . . . . . . 39 89 14.2. Identity and identifiability . . . . . . . . . . . . . . 39 90 14.3. Identity-related terms . . . . . . . . . . . . . . . . . 42 91 14.4. Identity management-related terms . . . . . . . . . . . . 46 92 15. Overview of main definitions and their opposites . . . . . . . 48 93 16. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 50 94 17. References . . . . . . . . . . . . . . . . . . . . . . . . . . 50 95 17.1. Normative References . . . . . . . . . . . . . . . . . . 50 96 17.2. Informative References . . . . . . . . . . . . . . . . . 50 98 1. Introduction 100 Early papers from the 1980ies about privacy by data minimization 101 already deal with anonymity, unlinkability, unobservability, and 102 pseudonymity and introduce these terms within the respective context 103 of proposed measures. 105 Note: 107 Data minimization means that first of all, the possibility to 108 collect personal data about others should be minimized. Next 109 within the remaining possibilities, collecting personal data 110 should be minimized. Finally, the time how long collected 111 personal data is stored should be minimized. 113 Data minimization is the only generic strategy to enable 114 anonymity, since all correct personal data help to identify if we 115 exclude providing misinformation (inaccurate or erroneous 116 information, provided usually without conscious effort at 117 misleading, deceiving, or persuading one way or another [Wils93]) 118 or disinformation (deliberately false or distorted information 119 given out in order to mislead or deceive [Wils93]). 121 Furthermore, data minimization is the only generic strategy to 122 enable unlinkability, since all correct personal data provide some 123 linkability if we exclude providing misinformation or 124 disinformation. 126 We show relationships between these terms and thereby develop a 127 consistent terminology. Then, we contrast these definitions with 128 newer approaches, e.g., from ISO IS 15408. Finally, we extend this 129 terminology to identity (as the the opposite of anonymity and 130 unlinkability) and identity management. Identity management is a 131 much younger and much less well-defined field - so a really 132 consolidated terminology for this field does not exist. 134 The adoption of this terminology will help to achieve better progress 135 in the field by avoiding that those working on standards and research 136 invent their own language from scratch. 138 This document is organized as follows: First, the setting used is 139 described. Then, definitions of anonymity, unlinkability, 140 linkability, undetectability, and unobservability are given and the 141 relationships between the respective terms are outlined. Afterwards, 142 known mechanisms to achieve anonymity, undetectability and 143 unobservability are listed. The next sections deal with 144 pseudonymity, i.e., pseudonyms, their properties, and the 145 corresponding mechanisms. Thereafter, this is applied to privacy- 146 enhancing identity management. To give an overview of the main terms 147 defined and their opposites, a corresponding table follows. Finally, 148 concluding remarks are given. In appendices, we (A1) depict the 149 relationships between some terms used and (A2 and A3) briefly discuss 150 the relationship between our approach (to defining anonymity and 151 identifiability) and other approaches. To make the document readable 152 to as large an audience as possible, we did put information which can 153 be skipped in a first reading or which is only useful to part of our 154 readership, e.g., those knowing information theory, in footnotes. 156 2. Terminology and Requirements Notation 158 Privacy: "Privacy is the claim of individuals, groups, or 159 institutions to determine for themselves when, how, and to what 160 extent information about them is communicated to others. Viewed 161 in terms of the relation of the individual to social 162 participation, privacy is the voluntary and temporary withdrawal 163 of a person from the general society through physical or 164 psychological means, either in a state of solitude or small-group 165 intimacy or, when among larger groups, in a condition of anonymity 166 or reserve.", see page 7 of [West67] 168 3. Setting 170 We develop this terminology in the usual setting of entities 171 (subjects and objects) and actions, i.e., subjects execute actions on 172 objects. In particular, subjects called that senders send objects 173 called messages to subjects called recipients using a communication 174 network, i.e., stations send and receive messages using communication 175 technology. 177 Note: 179 To keep the setting as simple as possible, usually, we do not 180 distinguish between human senders and the stations which are used 181 to send messages. Putting it the other way round, usually, we 182 assume that each station is controlled by exactly one human being, 183 its owner. If a differentiation between human communication and 184 computer communication is necessary or if the assumption that each 185 station is controlled by exactly one human being is wrong, the 186 setting has to be more complex. We then use sender and recipient 187 for human beings and message for their communication. For 188 computers and their communications, we use stations sending bit 189 strings. If we have to look even deeper than bits which are 190 "abstractions" of physical signals, we call the representation of 191 bit strings signals. 193 For other settings, e.g., users querying a database, customers 194 shopping in an e-commerce shop, the same terminology can be derived 195 by instantiating the terms "sender", "recipient", and "message". But 196 for ease of explanation, we use the specific setting here, see 197 Figure 1. For a discussion in a broader context, we speak more 198 generally about subjects, which might be actors (such as senders) or 199 actees (such as recipients). 201 Irrespective whether we speak of senders and recipients or whether we 202 generalize to actors and actees, we regard a subject as a human being 203 (i.e., a natural person), a legal person, or a computer. An 204 organization not acting as a legal person we neither see as a single 205 subject nor as a single entity, but as (possibly structured) sets of 206 subjects or entities. Otherwise, the distinction between "subjects" 207 and "sets of subjects" would completely blur. 209 If we make our setting more concrete, we may l it a system. For our 210 purposes, a system has the following relevant properties: 212 1. The system has a surrounding, i.e., parts of the world are 213 "outside" the system. Together, the system and its surrounding 214 form the universe. 216 2. The state of the system may change by actions within the system. 218 Senders Recipients 219 Communication Network 220 -- -- 221 | | ---- ----------- ---| | 222 -- ------ /---- ----\ ---- -- 223 ---- /// \\\ -- 224 // \\ 225 // \\ 226 / +-+ \ -- 227 | +-+ | ----| | 228 /-\ | +-+ +-+ |--- -- 229 | |---- | +-+ +-+ | 230 \-/ | | 231 | Messages | 232 | +-+ +-+ | 233 | +-+ +-+ | 234 | |-- -- 235 --- \ / --| | 236 -- ---- \\ // -- 237 | | -- \\ // 238 -- \\\ /// \ 239 \---- ----/ \\ 240 ----------- \ /-\ 241 | | 242 \-/ 244 Figure 1: Setting 246 All statements are made from the perspective of an attacker , who may 247 be interested in monitoring what communication is occurring, what 248 patterns of communication exist, or even in manipulating the 249 communication. The perspective describes the set of all possible 250 observations. In the following, a property holds "from an attacker's 251 perspective" iff it holds for all possible observations of that 252 perspective. The attacker's perspective depends on the information 253 the attacker has available. If we assume some limits on how much 254 processing the attacker might be able to do, the information 255 available to the attacker will not only depend on the attacker's 256 perspective, but on the attacker's processing (abilities), too. The 257 attacker may be an outsider tapping communication lines or an insider 258 able to participate in normal communications and controlling at least 259 some stations, cf. Figure 2. We assume that the attacker uses all 260 information available to him to infer (probabilities of) his items of 261 interest (IOIs), e.g., who did send or receive which messages. At 262 this level of description, intentionally we do not care about 263 particular types of IOIs. The given example would be an IOI which 264 might be a 3-tupel of actor, action, and object. Later we consider 265 attribute values as IOIs. Attributes (and their values) are related 266 to IOIs because they may be items of interest themselves or their 267 observation may give information on IOIs: An attribute is a quality 268 or characteristic of an entity or an action. Some attributes may 269 take several values. Then it makes sense to make a distinction 270 between more abstract attributes and more concrete attribute values. 271 Mainly we are interested in attributes of subjects. Examples for 272 attributes in this setting are "sending a message" or "receiving a 273 message". 275 Senders Recipients 276 Communication Network 277 -- -- 278 | | ---- ----------- ---| | 279 -- ------ /---- ----\ ---- -- 280 Alice ---- /// \\\ -- Carol 281 // \\ 282 // \\ 283 / Message \ 284 | by Alice | 285 /-\ | +-+ | 286 | |---- | +-+ | 287 \-/ | Malice's | 288 Bob | Message | 289 | +-+ | 290 | Bob's +-+ | 291 | Message |-- -- 292 --- \ +-+ / --| | 293 -- ---- \\ +-+ // -- 294 | | -- \\ // Complice 295 -- \\\ /// of 296 Malice \---- ----/ Malice 297 (the attacker) ----------- 299 Figure 2: Example of an attacker's domain within the setting 301 Throughout the subsequent sections we assume that the attacker is not 302 able to get information on the sender or recipient from the message 303 content. Of course, encryption of messages provides protection of 304 the content against attackers observing the communication lines and 305 end-to-end encryption even provides protection of the content against 306 all stations passed, e.g., for the purpose of forwarding and/or 307 routing. But message content can neither be hidden from the sender 308 nor from the recipient(s) of the message. Therefore, we do not 309 mention the message content in these sections. For most applications 310 it is unreasonable to assume that the attacker forgets something. 312 Thus, normally the knowledge of the attacker only increases. 313 "Knowledge" can be described by probabilities of IOIs. More 314 knowledge then means more accurate probabilities, i.e., the 315 probabilities the attacker assumes to be true are closer to the 316 "true" probabilities. 318 4. Anonymity 320 To enable anonymity of a subject, there always has to be an 321 appropriate set of subjects with potentially the same attributes . 322 Since sending and receiving of particular messages are special cases 323 of "attributes" of senders and recipients, this is slightly more 324 general than the setting in Section 3. This generality is very 325 fortunate to stay close to the everyday meaning of "anonymity" which 326 is not only used w.r.t. subjects active in a particular context, 327 e.g., senders and recipients of messages, but w.r.t. subjects passive 328 in a particular context as well, e.g., subjects the records within a 329 database relate to. This leads to the following definition: 331 Definition: Anonymity of a subject means that the subject is not 332 identifiable within a set of subjects, the anonymity set. 334 Note: 336 "not identifiable within the anonymity set" means that only using 337 the information the attacker has at his discretion, the subject is 338 "not uniquely characterized within the anonymity set". In more 339 precise language, only using the information the attacker has at 340 his discretion, the subject is "not distinguishable from the other 341 subjects within the anonymity set". 343 From [ISO99]: "Anonymity ensures that a user may use a resource or 344 service without disclosing the user's identity. The requirements 345 for anonymity provide protection of the user identity. Anonymity 346 is not intended to protect the subject identity. [...] Anonymity 347 requires that other users or subjects are unable to determine the 348 identity of a user bound to a subject or operation." Compared 349 with this explanation, our definition is more general as it is not 350 restricted to identifying users, but any subjects. 352 The anonymity set is the set of all possible subjects. The set of 353 possible subjects depends on the knowledge of the attacker. Thus, 354 anonymity is relative with respect to the attacker. With respect to 355 actors, the anonymity set consists of the subjects who might cause an 356 action. With respect to actees, the anonymity set consists of the 357 subjects who might be acted upon. Therefore, a sender may be 358 anonymous (sender anonymity) only within a set of potential senders, 359 his/her sender anonymity set, which itself may be a subset of all 360 subjects worldwide who may send a message from time to time. The 361 same for the recipient means that a recipient may be anonymous 362 (recipient anonymity) only within a set of potential recipients, his/ 363 her recipient anonymity set, cf. Figure 3. Both anonymity sets may 364 be disjoint, be the same, or they may overlap. The anonymity sets 365 may vary over time. Since we assume that the attacker does not 366 forget anything he knows, the anonymity set cannot increase w.r.t. a 367 particular IOI. Especially subjects joining the system in a later 368 stage, do not belong to the anonymity set from the point of view of 369 an attacker observing the system in an earlier stage. (Please note 370 that if the attacker cannot decide whether the joining subjects were 371 present earlier, the anonymity set does not increase either: It just 372 stays the same.) Due to linkability, cf. below, the anonymity set 373 normally can only decrease. 375 Anonymity of a set of subjects within an (potentially larger) 376 anonymity set means that all these individual subjects are not 377 identifiable within this anonymity set. In this definition, "set of 378 subjects" is just taken to describe that the anonymity property holds 379 for all elements of the set. Another possible definition would be to 380 consider the anonymity property for the set as a whole. Then a 381 semantically quite different definition could read: Anonymity of a 382 set S of subjects within a larger anonymity set A means that it is 383 not distinguishable whether the subject whose anonymity is at stake 384 (and which clearly is within A) is within S or not. 386 +----------+ +---------+ 387 | | Communication Network | | 388 | -- | | -- | 389 | | | ----| ----------- |---| | | 390 | -- +----- /---- ----\ ---+ -- | 391 | | ---- /// \\\ -- | | 392 | | // \\ | | 393 | | // \\ | | 394 | | / +-+ \ | -- | 395 | | | +-+ | | --| | | 396 | /-\ | | +-+ +-+ |+-- -- | 397 | | |-+-- | +-+ +-+ || | 398 | \-/ | | | | 399 | | | Messages | | 400 | | | +-+ +-+ || | 401 | | | +-+ +-+ || | 402 | | | |-+ -- | 403 | | --- \ / |----| | | 404 | -- --+- \\ // | -- | 405 | | | -- | \\ // | | 406 | -- | \\\ /// \ | | 407 | | \---- ----/ \\ | | 408 | | ----------- \| /-\ | 409 | | |\| | | 410 | | | \-/ | 411 +----------+ | | 412 +---------+ 413 Sender (1) & (2) 414 Anonymity Largest Possible Recipient 415 Set Anonymity Set Anonymity 416 (1) Set (2) 418 Figure 3: Anonymity sets within the setting 420 The definition given above for anonymity basically defines anonymity 421 as a binary property: Either a subject is anonymous or not. To 422 reflect the possibility to quantify anonymity in our definition and 423 to underline that all statements are made from the perspective of an 424 attacker (cf. Figure 4), it is appropriate to work with a slightly 425 more complicated definition in the following: 427 Definition: Anonymity of a subject from an attacker's perspective 428 means that the attacker cannot sufficiently identify the subject 429 within a set of subjects, the anonymity set. 431 In this revised definition, "sufficiently" underlines both that there 432 is a possibility to quantify anonymity and that for some 433 applications, there might be a need to define a threshold where 434 anonymity begins. 436 If we do not focus on the anonymity of one individual subject, called 437 individual anonymity, but on the anonymity provided by a system to 438 all of its users together, called global anonymity, we can state: All 439 other things being equal, global anonymity is the stronger, the 440 larger the respective anonymity set is and the more evenly 441 distributed the sending or receiving, respectively, of the subjects 442 within that set is. 444 Note: 446 The entropy of a message source as defined by Claude E. Shannon 447 [Shan48] might be an appropriate measure to quantify global 448 anonymity - just take who is the sender/recipient as the "message" 449 in Shannon's definition. For readers interested in formalizing 450 what we informally say: "No change of probabilities" means "no 451 change of knowledge" and vice versa. "No change of probabilities" 452 (or what is equivalent: "no change of knowledge") implies "no 453 change of entropy", whereas "no change of entropy" neither implies 454 "no change of probabilities" nor "no change of knowledge". In an 455 easy to remember notation: No change of probabilities = no change 456 of knowledge => no change of entropy. 458 The definition of anonymity is an analog to the definition of 459 "perfect secrecy" by Claude E. Shannon [Shan49], whose definition 460 takes into account that no security mechanism whatsoever can take 461 away knowledge from the attacker which he already has. 463 For a fixed anonymity set, global anonymity is maximal iff all 464 subjects within the anonymity set are equally likely. Since subjects 465 may behave quite distinct from each other (and trying to persuade 466 them to behave more equally may both fail and be not compatible with 467 basic human rights), achieving maximal anonymity or even something 468 close to it usually is impossible. Strong or even maximal global 469 anonymity does not imply strong anonymity or even maximal anonymity 470 of each particular subject. What maximal anonymity of one individual 471 subject (maximal individual anonymity, for short) means is unclear. 472 On the one hand, if her probability approaches zero, her Shannon 473 entropy (as a measure for anonymity) gets larger and larger. On the 474 other hand, if her probability gets zero, she is outside the 475 anonymity set. Even if global anonymity is strong, one (or a few) 476 individual subjects might be quite likely, so their anonymity is 477 weak. W.r.t. these "likely suspects", nothing is changed if the 478 anonymity set is made larger and sending and receiving of the other 479 subjects are, e.g., distributed evenly. That way, arbitrarily strong 480 global anonymity can be achieved without doing anything for the 481 "likely suspects" [ClSc06]. So there is need to define anonymity 482 measures not only for the system as a whole, but for individual 483 subjects (individual anonymity) or small sets of subjects. 485 +----------+ 486 | | Communication Network 487 | -- | -- 488 | | | ----| ----------- ----| | 489 | -- +----- /---- ----\ --- -- 490 | | ---- /// \\\ -- Attacker 491 | | // \\ 492 | +--------+ // \\ +---------+ 493 | | / +-+ \ | -- | 494 | | | +-+ | | --| | | 495 | | /-\ | +-+ +-+ |+-- -- | 496 | | | |-+-- | +-+ +-+ || | 497 | | \-/ | || | 498 | | Attacker | Messages || | 499 | | | +-+ +-+ || | 500 | +--------+ | +-+ +-+ || | 501 | | | |-+ -- | 502 | | --- \ / |----| | | 503 | -- --+- \\ // | -- | 504 | | | -- | \\ // | | 505 | -- | \\\ /// \ | | 506 | | \---- ----/ \\ | | 507 | | ----------- \| /-\ | 508 | | |\| | | 509 | | | \-/ | 510 +----------+ | | 511 +---------+ 512 Sender (1) & (2) 513 Anonymity Largest Possible Recipient 514 Set Anonymity Set Anonymity 515 (1) w.r.t. to attacker Set (2) 517 Figure 4: Anonymity sets w.r.t. attacker within the setting 519 From the above discussion follows that anonymity in general as well 520 as the anonymity of each particular subject is a concept which is 521 very much context dependent (on, e.g., subjects population, 522 attributes, time frame, etc). In order to quantify anonymity within 523 concrete situations, one would have to describe the system in 524 sufficient detail, which is practically not (always) possible for 525 large open systems (but maybe for some small data bases for 526 instance). Besides the quantity of anonymity provided within a 527 particular setting, there is another aspect of anonymity: its 528 robustness. Robustness of anonymity characterizes how stable the 529 quantity of anonymity is against changes in the particular setting, 530 e.g., a stronger attacker or different probability distributions. We 531 might use quality of anonymity as a term comprising both quantity and 532 robustness of anonymity. To keep this text as simple as possible, we 533 will mainly discuss the quantity of anonymity in the following, using 534 the wording "strength of anonymity". 536 The above definitions of anonymity and the mentioned measures of 537 quantifying anonymity are fine to characterize the status of a 538 subject in a world as it is. If we want to describe changes to the 539 anonymity of a subject if the world is changed somewhat, e.g., the 540 subject uses the communication network differently or uses a modified 541 communication network, we need another definition of anonymity 542 capturing the delta. The simplest way to express this delta is by 543 the observations of "the" attacker. 545 Definition: An anonymity delta (regarding a subject's anonymity) 546 from an attacker's perspective specifies the difference between 547 the subject's anonymity taking into account the attacker's 548 observations (i.e., the attacker's a-posteriori knowledge) and the 549 subject's anonymity given the attacker's a-priori knowledge only. 551 Note: 553 In some publications, the a-priori knowledge of the attacker is 554 called "background knowledge" and the a-posteriori knowledge of 555 the attacker is called "new knowledge". 557 As we can quantify anonymity in concrete situations, so we can 558 quantify the anonymity delta. This can be done by just defining: 559 quantity(anonymity delta) := quantity(anonymity_a-posteriori) - 560 quantity(anonymity_a-priori) If anonymity_a-posteriori and 561 anonymity_a-priori are the same, their quantification is the same and 562 therefore the difference of these quantifications is 0. If anonymity 563 can only decrease (which usually is quite a reasonable assumption), 564 the maximum of quantity(anonymity delta) is 0. 566 Since anonymity cannot increase, the anonymity delta can never be 567 positive. Having an anonymity delta of zero means that anonymity 568 stays the same. This means that if the attacker has no a-priori 569 knowledge about the particular subject, having no anonymity delta 570 implies anonymity. But if the attacker has an a-priori knowledge 571 covering all actions of the particular subject, having no anonymity 572 delta does not imply any anonymity at all. If there is no anonymity 573 from the very beginning, even preserving it completely does not yield 574 any anonymity. To be able to express this conveniently, we use 575 wordings like "perfect preservation of a subject's anonymity". It 576 might be worthwhile to generalize "preservation of anonymity of 577 single subjects" to "preservation of anonymity of sets of subjects", 578 in the limiting case all subjects in an anonymity set. An important 579 special case is that the "set of subjects" is the set of subjects 580 having one or several attribute values A in common. Then the meaning 581 of "preservation of anonymity of this set of subjects" is that 582 knowing A does not decrease anonymity. Having a negative anonymity 583 delta means that anonymity is decreased. 585 5. Unlinkability 587 Unlinkability only has a meaning after the system in which we want to 588 describe anonymity properties has been defined and the attacker has 589 been characterized. Then: 591 Definition: Unlinkability of two or more items of interest (IOIs, 592 e.g., subjects, messages, actions, ...) from an attacker's 593 perspective means that within the system (comprising these and 594 possibly other items), the attacker cannot sufficiently 595 distinguish whether these IOIs are related or not. , 597 Note: 599 From [ISO99]: "Unlinkability ensures that a user may make multiple 600 uses of resources or services without others being able to link 601 these uses together. [...] Unlinkability requires that users 602 and/or subjects are unable to determine whether the same user 603 caused certain specific operations in the system." In contrast to 604 this definition, the meaning of unlinkability in this text is less 605 focused on the user, but deals with unlinkability of "items" and 606 therefore takes a general approach. 608 As the entropy of a message source might be an appropriate measure 609 to quantify (global) anonymity (and thereafter "anonymity" might 610 be used as a quantity), we may use definitions to quantify 611 unlinkability (and thereafter "unlinkability" might be used as a 612 quantity as well). Quantifications of unlinkability can be either 613 probabilities or entropies, or whatever is useful in a particular 614 context. 616 Linkability is the negation of unlinkability: 618 Definition: Linkability of two or more items of interest (IOIs, 619 e.g., subjects, messages, actions, ...) from an attacker's 620 perspective means that within the system (comprising these and 621 possibly other items), the attacker can sufficiently distinguish 622 whether these IOIs are related or not. 624 For example, in a scenario with at least two senders, two messages 625 sent by subjects within the same anonymity set are unlinkable for an 626 attacker if for him, the probability that these two messages are sent 627 by the same sender is sufficiently close to 1/(number of senders). 628 In case of unicast the same is true for recipients; in case of 629 multicast it is slightly more complicated. 631 Definition: An unlinkability delta of two or more items of interest 632 (IOIs, e.g., subjects, messages, actions, ...) from an attacker's 633 perspective specifies the difference between the unlinkability of 634 these IOIs taking into account the attacker's observations and the 635 unlinkability of these IOIs given the attacker's a-priori 636 knowledge only. 638 Since we assume that the attacker does not forget anything, 639 unlinkability cannot increase. Normally, the attacker's knowledge 640 cannot decrease (analogously to Shannon's definition of "perfect 641 secrecy", see above). An exception of this rule is the scenario 642 where the use of misinformation (inaccurate or erroneous information, 643 provided usually without conscious effort at misleading, deceiving, 644 or persuading one way or another [Wils93]) or disinformation 645 (deliberately false or distorted information given out in order to 646 mislead or deceive [Wils93]) leads to a growing uncertainty of the 647 attacker which information is correct. A related, but different 648 aspect is that information may become wrong (i.e., outdated) simply 649 because the state of the world changes over time. Since privacy is 650 not only about to protect the current state, but the past and history 651 of a data subject as well, we will not make use of this different 652 aspect in the rest of this document. Therefore, the unlinkability 653 delta can never be positive. Having an unlinkability delta of zero 654 means that the probability of those items being related from the 655 attacker's perspective stays exactly the same before (a-priori 656 knowledge) and after the attacker's observations (a-posteriori 657 knowledge of the attacker). If the attacker has no a-priori 658 knowledge about the particular IOIs, having an unlinkability delta of 659 zero implies unlinkability. But if the attacker has a-priori 660 knowledge covering the relationships of all IOIs, having an 661 unlinkability delta of zero does not imply any unlinkability at all. 662 If there is no unlinkability from the very beginning, even preserving 663 it completely does not yield any unlinkability. To be able to 664 express this conveniently, we use wordings like "perfect preservation 665 of unlinkability w.r.t. specific items" to express that the 666 unlinkability delta is zero. It might be worthwhile to generalize 667 "preservation of unlinkability of two IOIs" to "preservation of 668 unlinkability of sets of IOIs", in the limiting case all IOIs in the 669 system. 671 For example, the unlinkability delta of two messages is sufficiently 672 small (zero) for an attacker if the probability describing his 673 a-posteriori knowledge that these two messages are sent by the same 674 sender and/or received by the same recipient is sufficiently 675 (exactly) the same as the probability imposed by his a-priori 676 knowledge. Please note that unlinkability of two (or more) messages 677 of course may depend on whether their content is protected against 678 the attacker considered. In particular, messages may be unlinkable 679 if we assume that the attacker is not able to get information on the 680 sender or recipient from the message content, cf. Section 3. Yet 681 with access to their content even without deep semantical analysis 682 the attacker can notice certain characteristics which link them 683 together - e.g. similarities in structure, style, use of some words 684 or phrases, consistent appearance of some grammatical errors, etc. 685 In a sense, content of messages may play a role as "side channel" in 686 a similar way as in cryptanalysis - i.e., content of messages may 687 leak some information on their linkability. 689 Roughly speaking, no unlinkability delta of items means that the 690 ability of the attacker to relate these items does not increase by 691 observing the system or by possibly interacting with it. 693 The definitions of unlinkability, linkability and unlinkability delta 694 do not mention any particular set of IOIs they are restricted to. 695 Therefore, the definitions of unlinkability and unlinkability delta 696 are very strong, since they cover the whole system. We could weaken 697 the definitions by restricting them to part of the system: 698 "Unlinkability of two or more IOIs from an attacker's perspective 699 means that within an unlinkability set of IOIs (comprising these and 700 possibly other items), the attacker cannot sufficiently distinguish 701 whether these IOIs are related or not." 703 6. Anonymity in Terms of Unlinkability 705 To describe anonymity in terms of unlinkability, we have to augment 706 the definitions of anonymity given in Section 4 by making explicit 707 the attributes anonymity relates to. This is best explained by 708 looking at an example in detail. In our setting, cf. Section 3, we 709 choose the attribute "having sent a message" as the example. Then we 710 have: 712 A sender s is anonymous w.r.t. sending, iff s is anonymous within the 713 set of potential senders, i.e., within the sender anonymity set. 715 This mainly is a re-phrasing of the definition in Section 3. If we 716 make the message under consideration explicit, the definition reads: 718 A sender s sends a message m anonymously, iff s is anonymous within 719 the set of potential senders of m, the sender anonymity set of m. 721 This can be generalized to sets of messages easily: 723 A sender s sends a set of messages M anonymously, iff s is anonymous 724 within the set of potential senders of M, the sender anonymity set of 725 M. 727 If the attacker's focus is not on the sender, but on the message, we 728 can define: 730 A message m is sent anonymously, iff m can have been sent by each 731 potential sender, i.e., by any subject within the sender anonymity 732 set of m. 734 Again, this can be generalized to sets of messages easily: 736 A set of messages M is sent anonymously, iff M can have been sent by 737 each set of potential senders, i.e., by any set of subjects within 738 the cross product of the sender anonymity sets of each message m 739 within M. 741 Of course, all 5 definitions would work for receiving of messages 742 accordingly. For more complicated settings with more operations than 743 these two, appropriate sets of definitions can be developed. 745 Now we are prepared to describe anonymity in terms of unlinkability. 747 We do this by using our setting, cf. Section 3. So we consider 748 sending and receiving of messages as attributes; the items of 749 interest (IOIs) are "who has sent or received which message". Then, 750 anonymity of a subject w.r.t. an attribute may be defined as 751 unlinkability of this subject and this attribute. In the wording of 752 the definition of unlinkability: a subject s is related to the 753 attribute value "has sent message m" if s has sent message m. s is 754 not related to that attribute value if s has not sent message m. 755 Same for receiving.Unlinkability is a sufficient condition of 756 anonymity, but it is not a necessary condition. Thus, failing 757 unlinkability w.r.t. some attribute value(s) does not necessarily 758 eliminate anonymity as defined in Section 4; in specific cases (i.e., 759 depending on the attribute value(s)) even the strength of anonymity 760 may not be affected. 762 So we have: Sender anonymity of a subject means that to this 763 potentially sending subject, each message is unlinkable. 765 Note: 767 The property unlinkability might be more "fine-grained" than 768 anonymity, since there are many more relations where unlinkability 769 might be an issue than just the relation "anonymity" between 770 subjects and IOIs. Therefore, the attacker might get to know 771 information on linkability while not necessarily reducing 772 anonymity of the particular subject - depending on the defined 773 measures. An example might be that the attacker, in spite of 774 being able to link, e.g., by timing, all encrypted messages of a 775 transactions, does not learn who is doing this transaction. 777 Correspondingly, recipient anonymity of a subject means that to this 778 potentially receiving subject, each message is unlinkable. 780 Relationship anonymity of a pair of subjects, the potentially sending 781 subject and the potentially receiving subject, means that to this 782 potentially communicating pair of subjects, each message is 783 unlinkable. In other words, sender and recipient (or each recipient 784 in case of multicast) are unlinkable. As sender anonymity of a 785 message cannot hold against the sender of this message himself nor 786 can recipient anonymity hold against any of the recipients w.r.t. 787 himself, relationship anonymity is considered w.r.t. outsiders only, 788 i.e., attackers being neither the sender nor one of the recipients of 789 the messages under consideration. 791 Thus, relationship anonymity is a weaker property than each of sender 792 anonymity and recipient anonymity: The attacker might know who sends 793 which messages or he might know who receives which messages (and in 794 some cases even who sends which messages and who receives which 795 messages). But as long as for the attacker each message sent and 796 each message received are unlinkable, he cannot link the respective 797 senders to recipients and vice versa, i.e., relationship anonymity 798 holds. The relationship anonymity set can be defined to be the cross 799 product of two potentially distinct sets, the set of potential 800 senders and the set of potential recipients or - if it is possible to 801 exclude some of these pairs - a subset of this cross product. So the 802 relationship anonymity set is the set of all possible sender- 803 recipient(s)-pairs. In case of multicast, the set of potential 804 recipients is the power set of all potential recipients. If we take 805 the perspective of a subject sending (or receiving) a particular 806 message, the relationship anonymity set becomes the set of all 807 potential recipients (senders) of that particular message. So fixing 808 one factor of the cross product gives a recipient anonymity set or a 809 sender anonymity set. 811 Note: 813 The following is an explanation of the statement made in the 814 previous paragraph regarding relationship anonymity: For all 815 attackers it holds that sender anonymity implies relationship 816 anonymity, and recipient anonymity implies relationship anonymity. 818 This is true if anonymity is taken as a binary property: Either it 819 holds or it does not hold. If we consider quantities of 820 anonymity, the validity of the implication possibly depends on the 821 particular definitions of how to quantify sender anonymity and 822 recipient anonymity on the one hand, and how to quantify 823 relationship anonymity on the other. There exists at least one 824 attacker model, where relationship anonymity does neither imply 825 sender anonymity nor recipient anonymity. Consider an attacker 826 who neither controls any senders nor any recipients of messages, 827 but all lines and - maybe - some other stations. If w.r.t. this 828 attacker relationship anonymity holds, you can neither argue that 829 against him sender anonymity holds nor that recipient anonymity 830 holds. The classical MIX-net (cf. Section 9) without dummy 831 traffic is one implementation with just this property: The 832 attacker sees who sends messages when and who receives messages 833 when, but cannot figure out who sends messages to whom. 835 7. Undetectability and Unobservability 837 In contrast to anonymity and unlinkability, where not the IOI, but 838 only its relationship to subjects or other IOIs is protected, for 839 undetectability, the IOIs are protected as such. Undetectability can 840 be regarded as a possible and desirable property of steganographic 841 systems (see Section 9). Therefore it matches the information hiding 842 terminology [Pfit96], [ZFKP98]. In contrast, anonymity, dealing with 843 the relationship of discernible IOIs to subjects, does not directly 844 fit into that terminology, but independently represents a different 845 dimension of properties. 847 Definition: Undetectability of an item of interest (IOI) from an 848 attacker's perspective means that the attacker cannot sufficiently 849 distinguish whether it exists or not. 851 Note: 853 From [ISO99]: "Unobservability ensures that a user may use a 854 resource or service without others, especially third parties, 855 being able to observe that the resource or service is being used. 856 [...] Unobservability requires that users and/or subjects cannot 857 determine whether an operation is being performed." As seen 858 before, our approach is less user-focused and insofar more 859 general. With the communication setting and the attacker model 860 chosen in this text, our definition of unobservability shows the 861 method how to achieve it: preventing distinguishability of IOIs. 862 Thus, the ISO definition might be applied to a different setting 863 where attackers are prevented from observation by other means, 864 e.g., by encapsulating the area of interest against third parties. 866 In some applications (e.g. steganography), it might be useful to 867 quantify undetectability to have some measure how much uncertainty 868 about an IOI remains after the attacker's observations. Again, we 869 may use probabilities or entropy, or whatever is useful in a 870 particular context. 872 If we consider messages as IOIs, this means that messages are not 873 sufficiently discernible from, e.g., "random noise". A slightly more 874 precise formulation might be that messages are not discernible from 875 no message. A quantification of this property might measure the 876 number of indistinguishable IOIs and/or the probabilities of 877 distinguishing these IOIs. 879 Undetectability is maximal iff whether an IOI exists or not is 880 completely indistinguishable. We call this perfect undetectability. 882 Definition: An undetectability delta of an item of interest (IOI) 883 from an attacker's perspective specifies the difference between 884 the undetectability of the IOI taking into account the attacker's 885 observations and the undetectability of the IOI given the 886 attacker's a-priori knowledge only. 888 The undetectability delta is zero iff whether an IOI exists or not is 889 indistinguishable to exactly the same degree whether the attacker 890 takes his observations into account or not. We call this "perfect 891 preservation of undetectability". 893 Undetectability of an IOI clearly is only possible w.r.t. subjects 894 being not involved in the IOI (i.e., neither being the sender nor one 895 of the recipients of a message). Therefore, if we just speak about 896 undetectability without spelling out a set of IOIs, it goes without 897 saying that this is a statement comprising only those IOIs the 898 attacker is not involved in. 900 As the definition of undetectability stands, it has nothing to do 901 with anonymity - it does not mention any relationship between IOIs 902 and subjects. Even more, for subjects being involved in an IOI, 903 undetectability of this IOI is clearly impossible. Therefore, early 904 papers describing new mechanisms for undetectability designed the 905 mechanisms in a way that if a subject necessarily could detect an 906 IOI, the other subject(s) involved in that IOI enjoyed anonymity at 907 least. The rational for this is to strive for data minimization: No 908 subject should get to know any (potentially personal) data - except 909 this is absolutely necessary. Given the setting described in 910 Section 3, this means: 1. Subjects being not involved in the IOI get 911 to know absolutely nothing. 2. Subjects being involved in the IOI 912 only get to know the IOI, but not the other subjects involved - the 913 other subjects may stay anonymous. Since in the setting described in 914 Section 3 the attributes "sending a message" or "receiving a message" 915 are the only kinds of attributes considered, 1. and 2. together 916 provide data minimization in this setting in an absolute sense. 917 Undetectability by uninvolved subjects together with anonymity even 918 if IOIs can necessarily be detected by the involved subjects has been 919 called unobservability: 921 Definition: Unobservability of an item of interest (IOI) means 923 * undetectability of the IOI against all subjects uninvolved in 924 it and 926 * anonymity of the subject(s) involved in the IOI even against 927 the other subject(s) involved in that IOI. 929 As we had anonymity sets of subjects with respect to anonymity, we 930 have unobservability sets of subjects with respect to 931 unobservability, see Figure 5. Mainly, unobservability deals with 932 IOIs instead of subjects only. Though, like anonymity sets, 933 unobservability sets consist of all subjects who might possibly cause 934 these IOIs, i.e. send and/or receive messages. 936 Sender unobservability then means that it is sufficiently 937 undetectable whether any sender within the unobservability set sends. 938 Sender unobservability is perfect iff it is completely undetectable 939 whether any sender within the unobservability set sends. 941 Recipient unobservability then means that it is sufficiently 942 undetectable whether any recipient within the unobservability set 943 receives. Recipient unobservability is perfect iff it is completely 944 undetectable whether any recipient within the unobservability set 945 receives. 947 Relationship unobservability then means that it is sufficiently 948 undetectable whether anything is sent out of a set of could-be 949 senders to a set of could-be recipients. In other words, it is 950 sufficiently undetectable whether within the relationship 951 unobservability set of all possible sender-recipient(s)-pairs, a 952 message is sent in any relationship. Relationship unobservability is 953 perfect iff it is completely undetectable whether anything is sent 954 out of a set of could-be senders to a set of could-be recipients. 956 All other things being equal, unobservability is the stronger, the 957 larger the respective unobservability set is, see Figure 6. 959 +----------+ +---------+ 960 | | Communication Network | | 961 | -- | | -- | 962 | | | ----| ----------- |---| | | 963 | -- +----- /----|+++++++++|----\ ---+ -- | 964 | | ---- ///++++++++++++++++++++ \\\ -- | | 965 | | // ++++++++++++++++++++++++++\\ | | 966 | | //+++++++++++++++++++++++++++++++\\ | | 967 | | |++++++++++++++++++++++++++++++++++|\ | -- | 968 | | |+++++++++++++++++++++++++++++++++++++| | --| | | 969 | /-\ | |+++++++++++++++++++++++++++++++++++++++|+-- -- | 970 | | |-+-- |+++++++++++++++++++++++++++++++++++++++|| | 971 | \-/ | |++++++++++++++++++++++++++++++++++++++++|| | 972 | | |++++++++++++++++++++++++++++++++++++++++|| | 973 | | |+++++++++++++++++++++++++++++++++++++++|| | 974 | | |+++++++++++++++++++++++++++++++++++++++|| | 975 | | ++++++++++++++++++++++++++++++++++++++|-+ -- | 976 | | --- \+++++++++++++++++++++++++++++++++++/ |----| | | 977 | -- --+- \\+++++++++++++++++++++++++++++++// | -- | 978 | | | -- | \\+++++++++++++++++++++++++++// | | 979 | -- | \|\+++++++++++++++++++++/// \ | | 980 | | \----+++++++++++----/ \\ | | 981 | | ----------- \| /-\ | 982 | | |\| | | 983 | | | \-/ | 984 +----------+ | | 985 +---------+ 986 Sender 987 Unobservability Largest Possible Recipient 988 Set Unobservability Set Unobservability 989 Set 991 Figure 5: Unobservability sets within the setting 993 +----------+ 994 | | -- 995 | -- | Communication Network ----| | 996 | | |-----| - -- 997 | -- +- ----------- Attacker 998 | | ---- /----|+++++++++|----\ -- 999 | | ---- ///++++++++++++++++++++ \\\ -- +---------+ 1000 | +--------+ // ++++++++++++++++++++++++++\\ | -- | 1001 | | //+++++++++++++++++++++++++++++++\\ | --| | | 1002 | | |++++++++++++++++++++++++++++++++++|\ |+-- -- | 1003 | | /-\ |+++++++++++++++++++++++++++++++++++++||| | 1004 | | | |--- |++++++++++++Observable+++++++++++++++++|| | 1005 | | \-/ -- |++++++++++++by attacker++++++++++++++++|| | 1006 | | Attacker |++++++++++++++++++++++++++++++++++++++++|| | 1007 | | |++++++++++++++++++++++++++++++++++++++++|| | 1008 | +--------+ |+++++++++++++++++++++++++++++++++++++++-+ -- | 1009 | | |+++++++++++++++++++++++++++++++++++++++ |----| | | 1010 | | ++++++++++++++++++++++++++++++++++++++| | -- | 1011 | -- --+---- \+++++++++++++++++++++++++++++++++++/ | | 1012 | | | -- | \\+++++++++++++++++++++++++++++++// | | 1013 | -- | \\+++++++++++++++++++++++++++// | | 1014 | | \|\+++++++++++++++++++++/// \ \| /-\ | 1015 | | \----+++++++++++----/ \\ |\| | | 1016 | | ----------- | \-/ | 1017 | | | | 1018 +----------+ +---------+ 1019 Sender Recipient 1020 Unobservability Largest Possible Unobservability 1021 Set Unobservability Set Set 1022 w.r.t. to attacker 1024 Figure 6: Unobservability sets w.r.t. attacker within the setting 1026 Definition: An unobservability delta of an item of interest (IOI) 1027 means 1029 * undetectability delta of the IOI against all subjects 1030 uninvolved in it and 1032 * anonymity delta of the subject(s) involved in the IOI even 1033 against the other subject(s) involved in that IOI. 1035 Since we assume that the attacker does not forget anything, 1036 unobservability cannot increase. Therefore, the unobservability 1037 delta can never be positive. Having an unobservability delta of zero 1038 w.r.t. an IOI means an undetectability delta of zero of the IOI 1039 against all subjects uninvolved in the IOI and an anonymity delta of 1040 zero against those subjects involved in the IOI. To be able to 1041 express this conveniently, we use wordings like "perfect preservation 1042 of unobservability" to express that the unobservability delta is 1043 zero. 1045 8. Relationships between Terms 1047 With respect to the same attacker, unobservability reveals always 1048 only a subset of the information anonymity reveals. [ReRu98] propose 1049 a continuum for describing the strength of anonymity. They give 1050 names: "absolute privacy" (the attacker cannot perceive the presence 1051 of communication, i.e., unobservability) - "beyond suspicion" - 1052 "probable innocence" - "possible innocence" - "exposed" - "provably 1053 exposed" (the attacker can prove the sender, recipient, or their 1054 relationship to others). Although we think that the terms "privacy" 1055 and "innocence" are misleading, the spectrum is quite useful. We 1056 might use the shorthand notation 1058 unobservability => anonymity 1060 for that (=> reads "implies"). Using the same argument and notation, 1061 we have 1063 sender unobservability => sender anonymity 1065 recipient unobservability => recipient anonymity 1067 relationship unobservability => relationship anonymity 1069 As noted above, we have 1071 sender anonymity => relationship anonymity 1073 recipient anonymity => relationship anonymity 1075 sender unobservability => relationship unobservability 1077 recipient unobservability => relationship unobservability 1079 With respect to the same attacker, unobservability reveals always 1080 only a subset of the information undetectability reveals 1082 unobservability => undetectability 1084 9. Known Mechanisms for Anonymity, Undetectability, and Unobservability 1086 Before it makes sense to speak about any particular mechanisms for 1087 anonymity, undetectability, and unobservability in communications, 1088 let us first remark that all of them assume that stations of users do 1089 not emit signals the attacker considered is able to use for 1090 identification of stations or their behavior or even for 1091 identification of users or their behavior. So if you travel around 1092 taking with you a mobile phone sending more or less continuously 1093 signals to update its location information within a cellular radio 1094 network, don't be surprised if you are tracked using its signals. If 1095 you use a computer emitting lots of radiation due to a lack of 1096 shielding, don't be surprised if observers using high-tech equipment 1097 know quite a bit about what's happening within your machine. If you 1098 use a computer, PDA, or smartphone without sophisticated access 1099 control, don't be surprised if Trojan horses send your secrets to 1100 anybody interested whenever you are online - or via electromagnetic 1101 emanations even if you think you are completely offline. 1103 DC-net [Chau85], [Chau88], and MIX-net [Chau81] are mechanisms to 1104 achieve sender anonymity and relationship anonymity, respectively, 1105 both against strong attackers. If we add dummy traffic, both provide 1106 for the corresponding unobservability [PfPW91]. If dummy traffic is 1107 used to pad sending and/or receiving on the sender's and/or 1108 recipient's line to a constant rate traffic, MIX-nets can even 1109 provide sender and/or recipient anonymity and unobservability. 1111 Broadcast [Chau85], [PfWa86], [Waid90] and private information 1112 retrieval [CoBi95] are mechanisms to achieve recipient anonymity 1113 against strong attackers. If we add dummy traffic, both provide for 1114 recipient unobservability. 1116 This may be summarized: A mechanism to achieve some kind of anonymity 1117 appropriately combined with dummy traffic yields the corresponding 1118 kind of unobservability. 1120 Of course, dummy traffic alone can be used to make the number and/or 1121 length of sent messages undetectable by everybody except for the 1122 recipients; respectively, dummy traffic can be used to make the 1123 number and/or length of received messages undetectable by everybody 1124 except for the senders. (Note: Misinformation and disinformation may 1125 be regarded as semantic dummy traffic, i.e., communication from which 1126 an attacker cannot decide which are real requests with real data or 1127 which are fake ones. Assuming the authenticity of misinformation or 1128 disinformation may lead to privacy problems for (innocent) 1129 bystanders.) 1131 As a side remark, we mention steganography and spread spectrum as two 1132 other well-known undetectability mechanisms. 1134 The usual concept to achieve undetectability of IOIs at some layer, 1135 e.g., sending meaningful messages, is to achieve statistical 1136 independence of all discernible phenomena at some lower 1137 implementation layer. An example is sending dummy messages at some 1138 lower layer to achieve, e.g., a constant rate flow of messages 1139 looking - by means of encryption - randomly for all parties except 1140 the sender and the recipient(s). 1142 10. Pseudonymity 1144 Having anonymity of human beings, unlinkability, and maybe 1145 unobservability is superb w.r.t. data minimization, but would prevent 1146 any useful two-way communication. For many applications, we need 1147 appropriate kinds of identifiers: 1149 Definition: A pseudonym is an identifier of a subject other than one 1150 of the subject's real names. 1152 Note: 1154 The term 'pseudonym' comes from the Greek word "pseudonumon" and 1155 means "falsely named" (pseudo: false; onuma: name). Thus, it 1156 means a name other than the 'real name'. To avoid the connotation 1157 of "pseudo" = false, some authors call pseudonyms as defined in 1158 this paper simply nyms. This is nice and short, but we stick with 1159 the usual wording, i.e., pseudonym, pseudonymity, etc. However 1160 the reader should not be surprised to read nym, nymity, etc. in 1161 other texts. 1163 An identifier is a name or another bit string. Identifiers, which 1164 are generated using random data only, i.e., fully independent of 1165 the subject and related attribute values, do not contain side 1166 information on the subject they are attached to, whereas non- 1167 random identifiers may do. E.g., nicknames chosen by a user may 1168 contain information on heroes he admires; a sequence number may 1169 contain information on the time the pseudonym was issued; an 1170 e-mail address or phone number contains information how to reach 1171 the user. 1173 In our setting 'subject' means sender or recipient. 1175 The term 'real name' is the antonym to "pseudonym". There may be 1176 multiple real names over lifetime, in particular the legal names, 1177 i.e., for a human being the names which appear on the birth 1178 certificate or on other official identity documents issued by the 1179 State; for a legal person the name under which it operates and 1180 which is registered in official registers (e.g., commercial 1181 register or register of associations). A human being's real name 1182 typically comprises their given name and a family name. In the 1183 realm of identifiers, it is tempting to define anonymity as "the 1184 attacker cannot sufficiently determine a real name of the 1185 subject". But despite the simplicity of this definition, it is 1186 severely restricted: It can only deal with subjects which have at 1187 least one real name. It presumes that it is clear who is 1188 authorized to attach real names to subjects. It fails to work if 1189 the relation to real names is irrelevant for the application at 1190 hand. Therefore, we stick to the definitions given in Section 4. 1191 Note that from a mere technological perspective it cannot always 1192 be determined whether an identifier of a subject is a pseudonym or 1193 a real name. 1195 We can generalize pseudonyms to be identifiers of sets of subjects - 1196 see below -, but we do not need this in our setting. 1198 Definition: The subject which the pseudonym refers to is the holder 1199 of the pseudonym. 1201 Definition: A subject is pseudonymous if a pseudonym is used as 1202 identifier instead of one of its real names. 1204 We prefer the term "holder" over "owner" of a pseudonym because it 1205 seems to make no sense to "own" identifiers, e.g., bit strings. 1206 Furthermore, the term "holder" sounds more neutral than the term 1207 "owner", which is associated with an assumed autonomy of the 1208 subject's will. The holder may be a natural person (in this case 1209 we have the usual meaning and all data protection regulations 1210 apply), a legal person, or even only a computer. 1212 Fundamentally, pseudonyms are nothing else than another kind of 1213 attribute values. But whereas in building an IT system, its 1214 designer can strongly support the holders of pseudonyms to keep 1215 the pseudonyms under their control, this is not equally possible 1216 w.r.t. attributes and attribute values in general. Therefore, it 1217 is useful to give this kind of attribute a distinct name: 1218 pseudonym. 1220 For pseudonyms chosen by the user (in contrast to pseudonyms 1221 assigned to the user by others), primarily, the holder of the 1222 pseudonym is using it. Secondarily, all others he communicated to 1223 using the pseudonym can utilize it for linking. Each of them can, 1224 of course, divulge the pseudonym and all data related to it to 1225 other entities. So finally, the attacker will utilize the 1226 pseudonym to link all data related to this pseudonym he gets to 1227 know being related. 1229 Defining the process of preparing for the use of pseudonyms, e.g., by 1230 establishing certain rules how and under which conditions civil 1231 identities of holders of pseudonyms will be disclosed by so-called 1232 identity brokers or how to prevent uncovered claims by so-called 1233 liability brokers (cf. Section 11), leads to the more general notion 1234 of pseudonymity, as defined below. 1236 Note: 1238 Identity brokers have for the pseudonyms they are the identity 1239 broker for the information who is their respective holder. 1240 Therefore, identity brokers can be implemented as a special kind 1241 of certification authorities for pseudonyms. Since anonymity can 1242 be described as a particular kind of unlinkability, cf. Section 6, 1243 the concept of identity broker can be generalized to linkability 1244 broker. A linkability broker is a (trusted) third party that, 1245 adhering to agreed rules, enables linking IOIs for those entities 1246 being entitled to get to know the linking. 1248 Concerning the natural use of the English language, one might use 1249 "pseudonymization" instead of "pseudonymity". But at least in 1250 Germany, the law makers gave "pseudonymization" the meaning that 1251 first personal data known by others comprise some identifiers for 1252 the civil identity and later these identifiers are replaced by 1253 pseudonyms. Therefore, we use a different term (coined by David 1254 Chaum: "pseudonymity") to describe that from the very beginning 1255 pseudonyms are used. 1257 Definition: Pseudonymity is the use of pseudonyms as identifiers. 1259 Note: 1261 From [ISO99]: "Pseudonymity ensures that a user may use a resource 1262 or service without disclosing its user identity, but can still be 1263 accountable for that use. [...] Pseudonymity requires that a set 1264 of users and/or subjects are unable to determine the identity of a 1265 user bound to a subject or operation, but that this user is still 1266 accountable for its actions." This view on pseudonymity covers 1267 only the use of digital pseudonyms. Therefore, our definition of 1268 pseudonymity is much broader as it does not necessarily require 1269 disclosure of the user's identity and accountability. 1270 Pseudonymity alone - as it is used in the real world and in 1271 technological contexts - does not tell anything about the 1272 strengths of anonymity, authentication or accountability; these 1273 strengths depend on several properties, cf. below. 1275 Quantifying pseudonymity would primarily mean quantifying the 1276 state of using a pseudonym according to its different dimensions 1277 (cf. Section 11 and Section 12), i.e., quantifying the 1278 authentication and accountability gained and quantifying the 1279 anonymity left over (e.g., using entropy as the measure). Roughly 1280 speaking, well-employed pseudonymity could mean in e-commerce 1281 appropriately fine-grained authentication and accountability to 1282 counter identity theft or to prevent uncovered claims using, e.g., 1283 the techniques described in [BuPf90], combined with much anonymity 1284 retained. Poorly employed pseudonymity would mean giving away 1285 anonymity without preventing uncovered claims. 1287 So sender pseudonymity is defined as the sender being pseudonymous, 1288 recipient pseudonymity is defined as the recipient being 1289 pseudonymous, see Figure 7. Providing sender pseudonymity and 1290 recipient pseudonymity is the basic interface communication networks 1291 have to provide to enhance privacy for two-way communications. 1293 Senders Recipients 1295 Pseudonyms Pseudonyms 1297 -- Communication Network 1298 | | ---- ------ 1299 -- \\ - ---- ---- 1300 \| |---- // \\ - -- 1301 - ---- // \\ ------| |-----| | 1302 / \ - -- 1303 / +-+ \ 1304 / +-+ \ 1305 /-\ - | | 1306 | |------- | |--- | +-+ +-+ | 1307 \-/ - --| +-+ +-+ | - /-\ 1308 | |--| |----| | 1309 | Messages | - \-/ 1310 | | 1311 | +-+ | 1312 - ---| +-+ | 1313 -- -----| |-- | +-+ |\\ - 1314 | | -- - \ +-+ / \| |--- -- 1315 -- \ / - --| | 1316 holder- \ / -- 1317 ship \\ // 1318 \\ // holder- 1319 ---- ---- ship 1320 ------ 1322 Sender 1323 Pseudonymity Recipient 1324 Pseudonymity 1326 Figure 7: Pseudonymity 1328 In our usual setting, we assume that each pseudonym refers to exactly 1329 one specific holder, invariant over time. 1331 Specific kinds of pseudonyms may extend this setting: A group 1332 pseudonym refers to a set of holders, i.e., it may refer to multiple 1333 holders; a transferable pseudonym can be transferred from one holder 1334 to another subject becoming its holder. 1336 Such a group pseudonym may induce an anonymity set: Using the 1337 information provided by the pseudonym only, an attacker cannot decide 1338 whether an action was performed by a specific subject within the set. 1339 Please note that the mere fact that a pseudonym has several holders 1340 does not yield a group pseudonym: For instance, creating the same 1341 pseudonym may happen by chance and even without the holders being 1342 aware of this fact, particularly if they choose the pseudonyms and 1343 prefer pseudonyms which are easy to remember. But the context of 1344 each use of the pseudonym (e.g., used by which subject - usually 1345 denoted by another pseudonym - in which kind of transaction) then 1346 usually will denote a single holder of this pseudonym. 1348 Transferable pseudonyms can, if the attacker cannot completely 1349 monitor all transfers of holdership, serve the same purpose, without 1350 decreasing accountability as seen by an authority monitoring all 1351 transfers of holdership. 1353 An interesting combination might be transferable group pseudonyms - 1354 but this is left for further study. 1356 11. Pseudonymity with respect to accountability and authorization 1358 11.1. Digital pseudonyms to authenticate messages 1360 A digital pseudonym is a bit string which, to be meaningful in a 1361 certain context, is 1363 o unique as identifier (at least with very high probability) and 1365 o suitable to be used to authenticate the holder's IOIs relatively 1366 to his/her digital pseudonym, e.g., to authenticate his/her 1367 messages sent. 1369 Using digital pseudonyms, accountability can be realized with 1370 pseudonyms - or more precisely: with respect to pseudonyms. 1372 11.2. Accountability for digital pseudonyms 1374 To authenticate IOIs relative to pseudonyms usually is not enough to 1375 achieve accountability for IOIs. 1377 Therefore, in many situations, it might make sense to either 1379 o attach funds to digital pseudonyms to cover claims or to 1381 o let identity brokers authenticate digital pseudonyms (i.e., check 1382 the civil identity of the holder of the pseudonym and then issue a 1383 digitally signed statement that this particular identity broker 1384 has proof of the identity of the holder of this digital pseudonym 1385 and is willing to divulge that proof under well-defined 1386 circumstances) or 1388 o both. 1390 Note: 1392 If the holder of the pseudonym is a natural person or a legal 1393 person, civil identity has the usual meaning, i.e. the identity 1394 attributed to that person by a State (e.g., a natural person being 1395 represented by the social security number or the combination of 1396 name, date of birth, and location of birth etc.). If the holder 1397 is, e.g., a computer, it remains to be defined what "civil 1398 identity" should mean. It could mean, for example, exact type and 1399 serial number of the computer (or essential components of it) or 1400 even include the natural person or legal person responsible for 1401 its operation. 1403 If sufficient funds attached to a digital pseudonym are reserved 1404 and/or the digitally signed statement of a trusted identity broker is 1405 checked before entering into a transaction with the holder of that 1406 pseudonym, accountability can be realized in spite of anonymity. 1408 11.3. Transferring authenticated attributes and authorizations between 1409 pseudonyms 1411 To transfer attributes including their authentication by third 1412 parties (called "credentials" by David Chaum [Chau85]) - all kinds of 1413 authorizations are special cases - between digital pseudonyms of one 1414 and the same holder, it is always possible to prove that these 1415 pseudonyms have the same holder. 1417 But as David Chaum pointed out, it is much more anonymity-preserving 1418 to maintain the unlinkability of the digital pseudonyms involved as 1419 much as possible by transferring the credential from one pseudonym to 1420 the other without proving the sameness of the holder. How this can 1421 be done is described in [Chau90] [CaLy04]. 1423 We will come back to the just described property "convertibility" of 1424 digital pseudonyms in Section 13. 1426 12. Pseudonymity with respect to linkability 1428 Whereas anonymity and accountability are the extremes with respect to 1429 linkability to subjects, pseudonymity is the entire field between and 1430 including these extremes. Thus, pseudonymity comprises all degrees 1431 of linkability to a subject. Ongoing use of the same pseudonym 1432 allows the holder to establish or consolidate a reputation. 1433 Establishing and/or consolidating a reputation under a pseudonym is, 1434 of course, insecure if the pseudonym does not enable to authenticate 1435 messages, i.e., if the pseudonym is not a digital pseudonym, cf. 1437 Section 11.1. Then, at any moment, another subject might use this 1438 pseudonym possibly invalidating the reputation, both for the holder 1439 of the pseudonym and all others having to do with this pseudonym. 1440 Some kinds of pseudonyms enable dealing with claims in case of abuse 1441 of unlinkability to holders: Firstly, third parties (identity 1442 brokers, cf. ) may have the possibility to reveal the civil identity 1443 of the holder in order to provide means for investigation or 1444 prosecution. To improve the robustness of anonymity, chains of 1445 identity brokers may be used [Chau81]. Secondly, third parties may 1446 act as liability brokers of the holder to clear a debt or settle a 1447 claim. [BuPf90] presents the particular case of value brokers. 1449 There are many properties of pseudonyms which may be of importance in 1450 specific application contexts. In order to describe the properties 1451 of pseudonyms with respect to anonymity, we limit our view to two 1452 aspects and give some typical examples: 1454 12.1. Knowledge of the linking between the pseudonym and its holder 1456 The knowledge of the linking may not be a constant, but change over 1457 time for some or even all people. Normally, for non-transferable 1458 pseudonyms the knowledge of the linking cannot decrease (with the 1459 exception of misinformation or disinformation, which may blur the 1460 attacker's knowledge.). Typical kinds of such pseudonyms are: 1462 Public pseudonym: The linking between a public pseudonym and its 1463 holder may be publicly known even from the very beginning. E.g., 1464 the linking could be listed in public directories such as the 1465 entry of a phone number in combination with its owner. 1467 Initially non-public pseudonym: The linking between an initially 1468 non-public pseudonym and its holder may be known by certain 1469 parties, but is not public at least initially. E.g., a bank 1470 account where the bank can look up the linking may serve as a non- 1471 public pseudonym. For some specific non-public pseudonyms, 1472 certification authorities acting as identity brokers could reveal 1473 the civil identity of the holder in case of abuse. 1475 Initially unlinked pseudonym: The linking between an initially 1476 unlinked pseudonym and its holder is - at least initially - not 1477 known to anybody with the possible exception of the holder 1478 himself/herself. Examples for unlinked pseudonyms are (non- 1479 public) biometrics like DNA information unless stored in databases 1480 including the linking to the holders. 1482 Public pseudonyms and initially unlinked pseudonyms can be seen as 1483 extremes of the described pseudonym aspect whereas initially non- 1484 public pseudonyms characterize the continuum in between. 1486 Anonymity is the stronger, the less is known about the linking to a 1487 subject. The strength of anonymity decreases with increasing 1488 knowledge of the pseudonym linking. In particular, under the 1489 assumption that no gained knowledge on the linking of a pseudonym 1490 will be forgotten and that the pseudonym cannot be transferred to 1491 other subjects, a public pseudonym never can become an unlinked 1492 pseudonym. In each specific case, the strength of anonymity depends 1493 on the knowledge of certain parties about the linking relative to the 1494 chosen attacker model. 1496 If the pseudonym is transferable, the linking to its holder can 1497 change. Considering an unobserved transfer of a pseudonym to another 1498 subject, a formerly public pseudonym can become non-public again. 1500 12.2. Linkability due to the use of a pseudonym across different 1501 contexts 1503 With respect to the degree of linkability, various kinds of 1504 pseudonyms may be distinguished according to the kind of context for 1505 their usage: 1507 Person pseudonym: A person pseudonym is a substitute for the 1508 holder's name which is regarded as representation for the holder's 1509 civil identity. It may be used in many different contexts, e.g., 1510 a number of an identity card, the social security number, DNA, a 1511 nickname, the pseudonym of an actor, or a mobile phone number. 1513 Role pseudonym: The use of role pseudonyms is limited to specific 1514 roles, e.g., a customer pseudonym or an Internet account used for 1515 many instantiations of the same role "Internet user". See 1516 Section 14.3 for a more precise characterization of the term 1517 "role". The same role pseudonym may be used with different 1518 communication partners. Roles might be assigned by other parties, 1519 e.g., a company, but they might be chosen by the subject himself/ 1520 herself as well. 1522 Relationship pseudonym: For each communication partner, a different 1523 relationship pseudonym is used. The same relationship pseudonym 1524 may be used in different roles for communicating with the same 1525 partner. Examples are distinct nicknames for each communication 1526 partner. In case of group communication, the relationship 1527 pseudonyms may be used between more than two partners. 1529 Role-relationship pseudonym: For each role and for each 1530 communication partner, a different role-relationship pseudonym is 1531 used. This means that the communication partner does not 1532 necessarily know, whether two pseudonyms used in different roles 1533 belong to the same holder. On the other hand, two different 1534 communication partners who interact with a user in the same role, 1535 do not know from the pseudonym alone whether it is the same user. 1536 As with relationship pseudonyms, in case of group communication, 1537 the role-relationship pseudonyms may be used between more than two 1538 partners. 1540 Transaction pseudonym: Apart from "transaction pseudonym" some 1541 employ the term "one-time-use pseudonym", taking the naming from 1542 "one-time pad". For each transaction, a transaction pseudonym 1543 unlinkable to any other transaction pseudonyms and at least 1544 initially unlinkable to any other IOI is used, e.g., randomly 1545 generated transaction numbers for online-banking. Therefore, 1546 transaction pseudonyms can be used to realize as strong anonymity 1547 as possible. In fact, the strongest anonymity is given when there 1548 is no identifying information at all, i.e., information that would 1549 allow linking of anonymous entities, thus transforming the 1550 anonymous transaction into a pseudonymous one. If the transaction 1551 pseudonym is used exactly once, we have the same strength of 1552 anonymity as if no pseudonym is used at all. Another possibility 1553 to achieve strong anonymity is to prove the holdership of the 1554 pseudonym or specific attribute values (e.g., with zero-knowledge 1555 proofs) without revealing the information about the pseudonym or 1556 more detailed attribute values themselves. Then, no identifiable 1557 or linkable information is disclosed. 1559 Linkability across different contexts due to the use of these 1560 pseudonyms can be represented as the lattice that is illustrated in 1561 the following diagram, see Figure 8. The arrows point in direction 1562 of increasing unlinkability, i.e., A -> B stands for "B enables 1563 stronger unlinkability than A". Note that "->" is not the same as 1564 "=>" of Section 8, which stands for the implication concerning 1565 anonymity and unobservability. 1567 linkable 1569 +-----------------+ * 1570 Person | | * 1571 / Pseudonym \ | decreasing | * 1572 // \\ | linkability | * 1573 / \ | across | * 1574 / \-+ | contexts | * 1575 +-/ v | | * 1576 v Role Relationship | | * 1577 Pseudonym Pseudonym | | * 1578 -- -- | | * 1579 -- --- | | * 1580 --- ---- | | * 1581 --+ +--- | | * 1582 v v | | * 1583 Role-Relationship | | |* 1584 Pseudonym | | * 1585 | | | * 1586 | | | * 1587 | | | * 1588 | | | * 1589 | | | * 1590 v | | * 1591 Transaction | * 1592 Pseudonym | v 1594 unlinkable 1596 Figure 8: Lattice of pseudonyms according to their use across 1597 different contexts 1599 In general, unlinkability of both role pseudonyms and relationship 1600 pseudonyms is stronger than unlinkability of person pseudonyms. The 1601 strength of unlinkability increases with the application of role- 1602 relationship pseudonyms, the use of which is restricted to both the 1603 same role and the same relationship. If a role-relationship 1604 pseudonym is used for roles comprising many kinds of activities, the 1605 danger arises that after a while, it becomes a person pseudonym in 1606 the sense of: "A person pseudonym is a substitute for the holder's 1607 name which is regarded as representation for the holder's civil 1608 identity." This is even more true both for role pseudonyms and 1609 relationship pseudonyms. Ultimate strength of unlinkability is 1610 obtained with transaction pseudonyms, provided that no other 1611 information, e.g., from the context or from the pseudonym itself, 1612 enabling linking is available. 1614 Anonymity is the stronger, ... 1616 o the less personal data of the pseudonym holder can be linked to 1617 the pseudonym; 1619 o the less often and the less context-spanning pseudonyms are used 1620 and therefore the less data about the holder can be linked; 1622 o the more often independently chosen, i.e., from an observer's 1623 perspective unlinkable, pseudonyms are used for new actions. 1625 The amount of information of linked data can be reduced by different 1626 subjects using the same pseudonym (e.g., one after the other when 1627 pseudonyms are transferred or simultaneously with specifically 1628 created group pseudonyms) or by misinformation or disinformation. 1629 The group of pseudonym holders acts as an inner anonymity set within 1630 a, depending on context information, potentially even larger outer 1631 anonymity set. 1633 13. Known mechanisms and other properties of pseudonyms 1635 A digital pseudonym could be realized as a public key to test digital 1636 signatures where the holder of the pseudonym can prove holdership by 1637 forming a digital signature which is created using the corresponding 1638 private key [Chau81]. The most prominent example for digital 1639 pseudonyms are public keys generated by the user himself/herself, 1640 e.g., using PGP. In using PGP, each user may create an unlimited 1641 number of key pairs by himself/herself (at this moment, such a key 1642 pair is an initially unlinked pseudonym), bind each of them to an 1643 e-mail address, self-certify each public key by using his/her digital 1644 signature or asking another introducer to do so, and circulate it. 1646 A public key certificate bears a digital signature of a so-called 1647 certification authority and provides some assurance to the binding of 1648 a public key to another pseudonym, usually held by the same subject. 1649 In case that pseudonym is the civil identity (the real name) of a 1650 subject, such a certificate is called an identity certificate. An 1651 attribute certificate is a digital certificate which contains further 1652 information (attribute values) and clearly refers to a specific 1653 public key certificate. Independent of certificates, attributes may 1654 be used as identifiers of sets of subjects as well. Normally, 1655 attributes refer to sets of subjects (i.e., the anonymity set), not 1656 to one specific subject. 1658 There are several other properties of pseudonyms related to their use 1659 which shall only be briefly mentioned, but not discussed in detail in 1660 this text. They comprise different degrees of, e.g., 1661 o limitation to a fixed number of pseudonyms per subject [Chau81], 1662 [Chau85], [Chau90]. For pseudonyms issued by an agency that 1663 guarantees the limitation of at most one pseudonym per individual 1664 person, the term "is-a-person pseudonym" is used. 1666 o guaranteed uniqueness [Chau81] [StSy00], e.g., "globally unique 1667 pseudonyms". 1669 o transferability to other subjects. 1671 o authenticity of the linking between a pseudonym and its holder 1672 (possibilities of verification/falsification or indication/ 1673 repudiation). 1675 o provability that two or more pseudonyms have the same holder. For 1676 digital pseudonyms having only one holder each and assuming that 1677 no holders cooperate to provide wrong "proofs", this can be proved 1678 trivially by signing, e.g., the statement " and 1679 have the same holder." digitally with respect to both 1680 these pseudonyms. Putting it the other way round: Proving that 1681 pseudonyms have the same holder is all but trivial. 1683 o convertibility, i.e., transferability of attributes of one 1684 pseudonym to another [Chau85], [Chau90]. This is a property of 1685 convertible credentials. 1687 o possibility and frequency of pseudonym changeover. 1689 o re-usability and, possibly, a limitation in number of uses. 1691 o validity (e.g., guaranteed durability and/or expiry date, 1692 restriction to a specific application). 1694 o possibility of revocation or blocking. 1696 o participation of users or other parties in forming the pseudonyms. 1698 o information content about attributes in the pseudonym itself. 1700 In addition, there may be some properties for specific applications 1701 (e.g., an addressable pseudonym serves as a communication address 1702 which enables to contact its holder) or due to the participation of 1703 third parties (e.g., in order to circulate the pseudonyms, to reveal 1704 civil identities in case of abuse, or to cover claims). 1706 Some of the properties can easily be realized by extending a digital 1707 pseudonym by attributes of some kind, e.g., a communication address, 1708 and specifying the appropriate semantics. The binding of attributes 1709 to a pseudonym can be documented in an attribute certificate produced 1710 either by the holder himself/herself or by a certification authority. 1711 The non-transferability of the attribute certificate can be somewhat 1712 enforced, e.g., by biometrical means, by combining it with individual 1713 hardware (e.g., chipcards), or by confronting the holder with legal 1714 consequences. 1716 14. Identity management 1718 14.1. Setting 1720 To adequately address privacy-enhancing identity management, we have 1721 to extend our setting: 1723 o It is not realistic to assume that an attacker might not get 1724 information on the sender or recipient of messages from the 1725 message content and/or the sending or receiving context (time, 1726 location information, etc.) of the message. We have to consider 1727 that the attacker is able to use these attributes for linking 1728 messages and, correspondingly, the pseudonyms used with them. 1730 o In addition, it is not just human beings, legal persons, or simply 1731 computers sending messages and using pseudonyms at their 1732 discretion as they like at the moment, but they use (computer- 1733 based) applications, which strongly influence the sending and 1734 receiving of messages and may even strongly determine the usage of 1735 pseudonym. 1737 14.2. Identity and identifiability 1739 Identity can be explained as an exclusive perception of life, 1740 integration into a social group, and continuity, which is bound to a 1741 body and - at least to some degree - shaped by society. This concept 1742 of identity distinguishes between "I" and "Me" [Mead34] : "I" is the 1743 instance that is accessible only by the individual self, perceived as 1744 an instance of liberty and initiative. "Me" is supposed to stand for 1745 the social attributes, defining a human identity that is accessible 1746 by communications and that is an inner instance of control and 1747 consistency (see [ICPP03] for more information). In this 1748 terminology, we are interested in identity as communicated to others 1749 and seen by them. Therefore, we concentrate on the "Me". 1751 Note: 1753 Here (and in Section 14 throughout), we have human beings in mind, 1754 which is the main motivation for privacy. From a structural point 1755 of view, identity can be attached to any subject, be it a human 1756 being, a legal person, or even a computer. This makes the 1757 terminology more general, but may lose some motivation at first 1758 sight. Therefore, we start in our explanation with identity of 1759 human beings, but implicitly generalize to subjects thereafter. 1760 This means: In a second reading of this paper, you may replace 1761 "individual person" by "individual subject" throughout as it was 1762 used in the definitions of the Section 3 through Section 13. It 1763 may be discussed whether the definitions can be further 1764 generalized and apply for any "entity", regardless of subject or 1765 object. 1767 According to Mireille Hildebrandt, the French philosopher Paul 1768 Ricoeur made a distinction between "idem and ipse. Idem 1769 (sameness) stands for the third person, objectified observer's 1770 perspective of identity as a set of attributes that allows 1771 comparison between different people, as well as unique 1772 identification, whereas ipse (self) stands for the first person 1773 perspective constituting a 'sense of self'.", see page 274 in 1774 [RaRD09]. So what George H. Mead called "I" is similar to what 1775 Paul Ricoeur called "ipse" (self). What George H. Mead called 1776 "Me" is similar to what Paul Ricoeur called "idem" (sameness). 1778 Motivated by identity as an exclusive perception of life, i.e., a 1779 psychological perspective, but using terms defined from a computer 1780 science, i.e., a mathematical perspective (as we did in the sections 1781 before), identity can be explained and defined as a property of an 1782 entity in terms of the opposite of anonymity and the opposite of 1783 unlinkability. In a positive wording, identity enables both to be 1784 identifiable as well as to link IOIs because of some continuity of 1785 life. Here we have the opposite of anonymity (identifiability) and 1786 the opposite of unlinkability (linkability) as positive properties. 1787 So the perspective changes: What is the aim of an attacker w.r.t. 1788 anonymity, now is the aim of the subject under consideration, so the 1789 attacker's perspective becomes the perspective of the subject. And 1790 again, another attacker (attacker2) might be considered working 1791 against identifiability and/or linkability. I.e., attacker2 might 1792 try to mask different attributes of subjects to provide for some kind 1793 of anonymity or attacker2 might spoof some messages to interfere with 1794 the continuity of the subject's life. 1796 Corresponding to the anonymity set introduced in the beginning of 1797 this text, we can work with an "identifiability set" [Hild03], which 1798 is the set is a set of possible subjects, to define "identifiability" 1799 and "identity". This definition is compatible with the definitions 1800 given in [HoWi03] and it is very close to that given by [Chi03]: "An 1801 identity is any subset of attributes of a person which uniquely 1802 characterizes this person within a community." 1803 Definition: Identifiability of a subject from an attacker's 1804 perspective means that the attacker can sufficiently identify the 1805 subject within a set of subjects, the identifiability set. 1807 Figure 9 contrasts anonymity set and identifiability set. 1809 Anonymity Identifiability 1810 within an within an 1811 -- -- 1812 -- -- -- -- 1813 / \ / \ 1814 / \ / \ 1815 / -- \ / --/ \ 1816 / | | \ / |//| \ 1817 / -- \ / /-- \ 1818 / \ / \ 1819 / \ / \ 1820 / -- \ / -- \ 1821 / | | \ / | | \ 1822 | -- | | -- | 1823 | | | | 1824 | | | | 1825 | -- | | --/ | 1826 \ | | / \ |//| / 1827 \ -- / \ /-- / 1828 \ / \ / 1829 \ / \ / 1830 \ -- / \ --/ / 1831 \ | | / \ |//| / 1832 \ -- / \ /-- / 1833 \ / \ / 1834 \ / \ / 1835 -- -- -- -- 1836 -- -- 1837 anonymity set identifiability set 1839 Figure 9: Anonymity set vs. identifiability set 1841 All other things being equal, identifiability is the stronger, the 1842 larger the respective identifiability set is. Conversely, the 1843 remaining anonymity is the stronger, the smaller the respective 1844 identifiability set is. 1846 Identity of an individual person should be defined independent of an 1847 attacker's perspective: 1849 Definition: An identity is any subset of attribute values of an 1850 individual person which sufficiently identifies this individual 1851 person within any set of persons. So usually there is no such 1852 thing as "the identity", but several of them. 1854 Note: 1856 Whenever we speak about "attribute values" in this text, this 1857 shall comprise not only a measurement of the attribute value, but 1858 the attribute as well. E.g., if we talk about the attribute 1859 "color of one's hair" the attribute value "color of one's hair" is 1860 not just, e.g., "grey", but ("color of one's hair", "grey"). 1862 An equivalent, but slightly longer definition of identity would 1863 be: An identity is any subset of attribute values of an individual 1864 person which sufficiently distinguishes this individual person 1865 from all other persons within any set of persons. 1867 Of course, attribute values or even attributes themselves may change 1868 over time. Therefore, if the attacker has no access to the change 1869 history of each particular attribute, the fact whether a particular 1870 subset of attribute values of an individual person is an identity or 1871 not may change over time as well. If the attacker has access to the 1872 change history of each particular attribute, any subset forming an 1873 identity will form an identity from his perspective irrespective how 1874 attribute values change. Any reasonable attacker will not just try 1875 to figure out attribute values per se, but the point in time (or even 1876 the time frame) they are valid (in), since this change history helps 1877 a lot in linking and thus inferring further attribute values. 1878 Therefore, it may clarify one's mind to define each "attribute" in a 1879 way that its value cannot get invalid. So instead of the attribute 1880 "location" of a particular individual person, take the set of 1881 attributes "location at time x". Depending on the inferences you are 1882 interested in, refining that set as a list ordered concerning 1883 "location" or "time" may be helpful. 1885 Identities may of course comprise particular attribute values like 1886 names, identifiers, digital pseudonyms, and addresses - but they 1887 don't have to. 1889 14.3. Identity-related terms 1891 Role: In sociology, a "role" or "social role" is a set of connected 1892 actions, as conceptualized by actors in a social situation (i.e., 1893 situation-dependent identity attributes). It is mostly defined as 1894 an expected behavior (i.e., sequences of actions) in a given 1895 social context. So roles provide for some linkability of actions. 1897 Partial identity: An identity of an individual person may comprise 1898 many partial identities of which each represents the person in a 1899 specific context or role. (Note: As an identity has to do with 1900 integration into a social group, on the one hand, partial 1901 identities have to do with, e.g., relationships to particular 1902 group members (or to be more general: relationships to particular 1903 subsets of group members). On the other hand, partial identities 1904 might be associated with relationships to organizations.) A 1905 partial identity is a subset of attribute values of a complete 1906 identity, where a complete identity is the union of all attribute 1907 values of all identities of this person. (Note: If attributes are 1908 defined such that their values do not get invalid, "union" can 1909 have the usual meaning within set theory. We have to admit that 1910 usually nobody, including the person concerned, will know "all" 1911 attribute values or "all" identities. Nevertheless we hope that 1912 the notion "complete identity" will ease the understanding of 1913 "identity" and "partial identity".) On a technical level, these 1914 attribute values are data. Of course, attribute values or even 1915 attributes themselves of a partial identity may change over time. 1916 As identities, partial identities may comprise particular 1917 attribute values like names, identifiers, digital pseudonyms, and 1918 addresses - but they don't have to, either. A pseudonym might be 1919 an identifier for a partial identity. If it is possible to 1920 transfer attribute values of one pseudonym to another (as 1921 convertibility of credentials provides for, cf. Section 13), this 1922 means transferring a partial identity to this other pseudonym. 1923 Re-use of the partial identity with its identifier(s), e.g., a 1924 pseudonym, supports continuity in the specific context or role by 1925 enabling linkability with, e.g., former or future messages or 1926 actions. If the pseudonym is a digital pseudonym, it provides the 1927 possibility to authenticate w.r.t. the partial identity which is 1928 important to prevent others to take over the partial identity 1929 (discussed as "identity theft" ). Linkability of partial 1930 identities arises by non-changing identifiers of a partial 1931 identity as well as other attribute values of that partial 1932 identity that are (sufficiently) static or easily determinable 1933 over time (e.g., bodily biometrics, the size or age of a person). 1934 All the data that can be used to link data sets such as partial 1935 identities belong to a category of "data providing linkability" 1936 (to which we must pay the same attention as to personal data 1937 w.r.t. privacy and data protection; "protection of individuals 1938 with regard to the processing of personal data" [DPD95]). Whereas 1939 we assume that an "identity" sufficiently identifies an individual 1940 person (without limitation to particular identifiability sets), a 1941 partial identity may not do, thereby enabling different quantities 1942 of anonymity. So we may have linkability by re-using a partial 1943 identity (which may be important to support continuity of life) 1944 without necessarily giving up anonymity (which may be important 1945 for privacy). But we may find for each partial identity 1946 appropriately small identifiability sets, where the partial 1947 identity sufficiently identifies an individual person, see 1948 Figure 10. For identifiability sets of cardinality 1, this is 1949 trivial, but it may hold for "interesting" identifiability sets of 1950 larger cardinality as well. The relation between anonymity set 1951 and identifiability set can be seen in two ways: 1953 1. Within an a-priori anonymity set, we can consider a-posteriori 1954 identifiability sets as subsets of the anonymity set. Then 1955 the largest identifiability sets allowing identification 1956 characterize the a-posteriori anonymity, which is zero iff the 1957 largest identifiability set allowing identification equals the 1958 a-priori anonymity set. 1960 2. Within an a-priori identifiability set, its subsets which are 1961 the a-posteriori anonymity sets characterize the a-posteriori 1962 anonymity. It is zero iff all a-posteriori anonymity sets 1963 have cardinality 1. 1965 As with identities, depending on whether the attacker has access 1966 to the change history of each particular attribute or not, the 1967 identifiability set of a partial identity may change over time if 1968 the values of its attributes change. 1970 -- 1971 -- -- 1972 / \ 1973 / \ 1974 / --/ \ 1975 / |//| \ -- 1976 / /-- \ -- -- 1977 / \ / \ 1978 / \ / \ 1979 / --/ \ / --/ \ 1980 / |//| \ -- / |//| \ 1981 | /-- | -- -- / /-- \ 1982 | | / \ / \ 1983 | | / \ / \ 1984 | --/ | / --/ \ / --/ \ 1985 | |//| | / |//| \ / |//| \ 1986 | /-- | / /-- \ | /-- | 1987 | | / \ | | 1988 | +-------------------------------------------+ | 1989 | | -- | / -- \ | -- (*)| | 1990 \ | | | / / | | \ | | | | | 1991 \ | -- / | -- | | -- | | 1992 \ +-------------------------------------------+ | 1993 \ / | | | | 1994 \ --/ / | --/ | | --/ | 1995 \ |//| / | |//| | \ |//| / 1996 \ /-- / | /-- | \ /-- / 1997 \ / | | \ / 1998 \ / | | \ / 1999 -- -- | --/ | \ --/ / 2000 -- \ |//| / \ |//| / 2001 \ /-- / \ /-- / 2002 \ / \ / 2003 \ / \ / 2004 \ --/ / -- -- 2005 \ |//| / -- 2006 \ /-- / 2007 \ / 2008 \ / 2009 -- -- 2010 -- 2012 *: Anonymity set of a partial identity given 2013 that the set of all possible subjects 2014 (the a-priori anonymity set) can be partitioned 2015 into the three disjoint identifiability sets 2016 of the partial identity shown. 2018 Figure 10: Relation between anonymity set and identifiability set 2020 Digital identity Digital identity denotes attribution of attribute 2021 values to an individual person, which are immediately 2022 operationally accessible by technical means. More to the point, 2023 the identifier of a digital partial identity can be a simple 2024 e-mail address in a news group or a mailing list. A digital 2025 partial identity is the same as a partial digital identity. In 2026 the following, we skip "partial" if the meaning is clear from the 2027 context. Its owner will attain a certain reputation. More 2028 generally we might consider the whole identity as a combination 2029 from "I" and "Me" where the "Me" can be divided into an implicit 2030 and an explicit part: Digital identity is the digital part from 2031 the explicated "Me". Digital identity should denote all those 2032 personal data that can be stored and automatically interlinked by 2033 a computer-based application. 2035 Virtual identity Virtual identity is sometimes used in the same 2036 meaning as digital identity or digital partial identity, but 2037 because of the connotation with "unreal, non-existent, seeming" 2038 the term is mainly applied to characters in a MUD (Multi User 2039 Dungeon), MMORPG (Massively Multiplayer Online Role Playing Game) 2040 or to avatars. For these reasons, we do not use the notions 2041 physical world vs. virtual world nor physical person vs. virtual 2042 person defined in [RaRD09] (pp. 80ff). Additionally, we feel that 2043 taking the distinction between physical vs. digital (=virtual) 2044 world as a primary means to build up a terminology is not helpful. 2045 First we have to define what a person and an identity is. The 2046 distinction between physical and digital is only of secondary 2047 importance and the structure of the terminology should reflect 2048 this fundamental fact. In other disciplines, of course, it may be 2049 very relevant whether a person is a human being with a physical 2050 body. Please remember Section 14.3, where the sociological 2051 definition of identity includes "is bound to a body", or law 2052 enforcement when a jail sentence has to be carried out. 2053 Generalizing from persons, laws should consider and spell out 2054 whether they are addressing physical entities, which cannot be 2055 duplicated easily, or digital entities, which can. 2057 14.4. Identity management-related terms 2059 Identity management Identity management means managing various 2060 partial identities (usually denoted by pseudonyms) of an 2061 individual person, i.e., administration of identity attributes 2062 including the development and choice of the partial identity and 2063 pseudonym to be (re-)used in a specific context or role. 2064 Establishment of reputation is possible when the individual person 2065 re-uses partial identities. A prerequisite to choose the 2066 appropriate partial identity is to recognize the situation the 2067 person is acting in. 2069 Privacy-enhancing identity management Given the restrictions of a 2070 set of applications, identity management is called privacy- 2071 enhancing if it sufficiently preserves unlinkability (as seen by 2072 an attacker) between the partial identities of an individual 2073 person required by the applications. Note that due to our 2074 setting, this definition focuses on the main property of Privacy- 2075 Enhancing Technologies (PETs), namely data minimization: This 2076 property means to limit as much as possible the release of 2077 personal data and for those released, preserve as much 2078 unlinkability as possible. We are aware of the limitation of this 2079 definition: In the real world it is not always desired to achieve 2080 utmost unlinkability. We believe that the user as the data 2081 subject should be empowered to decide on the release of data and 2082 on the degree of linkage of his or her personal data within the 2083 boundaries of legal regulations, i.e., in an advanced setting the 2084 privacy-enhancing application design should also take into account 2085 the support of "user-controlled release" as well as "user- 2086 controlled linkage". Identity management is called perfectly 2087 privacy-enhancing if it perfectly preserves unlinkability between 2088 the partial identities, i.e., by choosing the pseudonyms (and 2089 their authorizations, cf. Section 11.3) denoting the partial 2090 identities carefully, it maintains unlinkability between these 2091 partial identities towards an attacker to the same degree as 2092 giving the attacker the attribute values with all pseudonyms 2093 omitted. (Note: Given the terminology defined in Section 3 to 2094 Section 6, privacy-enhancing identity management is unlinkability- 2095 preserving identity management. So, maybe, the term "privacy- 2096 preserving identity management" would be more appropriate. But to 2097 be compatible to the earlier papers in this field, we stick to 2098 privacy-enhancing identity management.) 2100 Privacy-enhancing identity management enabling application design An 2101 application is designed in a privacy-enhancing identity management 2102 enabling way if neither the pattern of sending/receiving messages 2103 nor the attribute values given to subjects (i.e., human beings, 2104 organizations, computers) reduce unlinkability more than is 2105 strictly necessary to achieve the purposes of the application. 2107 User-controlled identity management Identity management is called 2108 user-controlled if the flow of this user's identity attribute 2109 values is explicit to the user and the user is in control of this 2110 flow. 2112 Identity management system (IMS) An identity management system 2113 supports administration of identity attributes including the 2114 development and choice of the partial identity and pseudonym to be 2115 (re-)used in a specific context or role. Note that some 2116 publications use the abbreviations IdMS or IDMS instead. We can 2117 distinguish between identity management system and identity 2118 management application: The term "identity management system" is 2119 seen as an infrastructure, in which "identity management 2120 applications" as components, i.e., software installed on 2121 computers, are co-ordinated. 2123 Privacy-enhancing identity management system (PE-IMS) A Privacy- 2124 Enhancing IMS is an IMS that, given the restrictions of a set of 2125 applications, sufficiently preserves unlinkability (as seen by an 2126 attacker) between the partial identities and corresponding 2127 pseudonyms of an individual person. 2129 User-controlled identity management system A user-controlled 2130 identity management system is an IMS that makes the flow of this 2131 user's identity attribute values explicit to the user and gives 2132 its user control of this flow [CPHH02]. The guiding principle is 2133 "notice and choice". 2135 Combining user-controlled IMS with PE-IMS means user-controlled 2136 linkability of personal data, i.e., achieving user-control based 2137 on thorough data minimization. According to respective situation 2138 and context, such a system supports the user in making an informed 2139 choice of pseudonyms, representing his or her partial identities. 2140 A user-controlled PE-IMS supports the user in managing his or her 2141 partial identities, i.e., to use different pseudonyms with 2142 associated identity attribute values according to different 2143 contexts, different roles the user is acting in and according to 2144 different interaction partners. It acts as a central gateway for 2145 all interactions between different applications, like browsing the 2146 web, buying in Internet shops, or carrying out administrative 2147 tasks with governmental authorities [HBCC04]. 2149 15. Overview of main definitions and their opposites 2150 o 2152 o 2154 +---------------------------------+---------------------------------+ 2155 | Definition | Negation | 2156 +---------------------------------+---------------------------------+ 2157 | Anonymity of a subject from an | Identifiability of a subject | 2158 | attacker's perspective means | from an attacker's perspective | 2159 | that the attacker cannot | means that the attacker can | 2160 | sufficiently identify the | sufficiently identify the | 2161 | subject within a set of | subject within a set of | 2162 | subjects, the anonymity set. | subjects, the identifiability | 2163 | | set. | 2164 | ------------------------------- | ------------------------------- | 2165 | Unlinkability of two or more | Linkability of two or more | 2166 | items of interest (IOIs, e.g., | items of interest (IOIs, e.g., | 2167 | subjects, messages, actions, | subjects, messages, actions, | 2168 | ...) from an attacker's | ...) from an attacker's | 2169 | perspective means that within | perspective means that within | 2170 | the system (comprising these | the system (comprising these | 2171 | and possibly other items), the | and possibly other items), the | 2172 | attacker cannot sufficiently | attacker can sufficiently | 2173 | distinguish whether these IOIs | distinguish whether these IOIs | 2174 | are related or not. | are related or not. | 2175 | ------------------------------- | ------------------------------- | 2176 | Undetectability of an item of | Detectability of an item of | 2177 | interest (IOI) from an | interest (IOI) from an | 2178 | attacker's perspective means | attacker's perspective means | 2179 | that the attacker cannot | that the attacker can | 2180 | sufficiently distinguish | sufficiently distinguish | 2181 | whether it exists or not. | whether it exists or not. | 2182 | ------------------------------- | ------------------------------- | 2183 | Unobservability of an item of | Observability of an item of | 2184 | interest (IOI) means | interest (IOI) means "many | 2185 | undetectability of the IOI | possibilities to define the | 2186 | against all subjects uninvolved | semantics". | 2187 | in it and anonymity of the | | 2188 | subject(s) involved in the IOI | | 2189 | even against the other | | 2190 | subject(s) involved in that | | 2191 | IOI. | | 2192 +---------------------------------+---------------------------------+ 2194 16. Acknowledgments 2196 Before this document was submitted to the IETF it already had a long 2197 history starting at 2000 and a number of people helped to improve the 2198 quality of the document with their feedback. The original authors, 2199 Marit Hansen and Andreas Pfitzmann, would therefore like to thank 2200 Adam Shostack, David-Olivier Jaquet-Chiffelle, Claudia Diaz, Giles 2201 Hogben, Thomas Kriegelstein, Wim Schreurs, Sandra Steinbrecher, Mike 2202 Bergmann, Katrin Borcea, Simone Fischer-Huebner, Stefan Koepsell, 2203 Martin Rost, Marc Wilikens, Adolf Flueli, Jozef Vyskoc, Thomas 2204 Kriegelstein, Jan Camenisch, Vashek Matyas, Daniel Cvrcek, Wassim 2205 Haddad, Alf Zugenmair, Katrin Borcea-Pfitzmann, Thomas Kriegelstein, 2206 Elke Franz, Sebastian Clauss, Neil Mitchison, Rolf Wendolsky, Stefan 2207 Schiffner, Maritta Heisel, Katja Liesebach, Stefanie Poetzsch, Thomas 2208 Santen, Maritta Heisel, Manuela Berg, Katrin Borcea-Pfitzmann, and 2209 Katie Tietze for their input. 2211 The terminology has been translated to other languages and the result 2212 can be found here: 2213 http://dud.inf.tu-dresden.de/Anon_Terminology.shtml. 2215 17. References 2217 17.1. Normative References 2219 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2220 Requirement Levels", BCP 14, RFC 2119, March 1997. 2222 17.2. Informative References 2224 [BuPf90] Buerk, H. and A. Pfitzmann, "Value Exchange Systems 2225 Enabling Security and Unobservability", Computers & 2226 Security , 9/8, 715-721, January 1990. 2228 [CPHH02] Clauss, S., Pfitzmann, A., Hansen, M., and E. Herreweghen, 2229 "Privacy-Enhancing Identity Management", IEEE Symposium on 2230 Research in Security and Privacy , IPTS Report 67, 8-16, 2231 September 2002. 2233 [CaLy04] Camenisch, J. and A. Lysyanskaya, "Signature Schemes and 2234 Anonymous Credentials from Bilinear Maps", Crypto , LNCS 2235 3152, Springer, Berlin 2004, 56-72, 2004. 2237 [Chau81] Chaum, D., "Untraceable Electronic Mail, Return Addresses, 2238 and Digital Pseudonyms", Communications of the ACM , 24/2, 2239 84-88, 1981. 2241 [Chau85] Chaum, D., "Security without Identification: Transaction 2242 Systems to make Big Brother Obsolete", Communications of 2243 the ACM , 28/10, 1030-1044, 1985. 2245 [Chau88] Chaum, D., "The Dining Cryptographers Problem: 2246 Unconditional Sender and Recipient Untraceability", 2247 Journal of Cryptology , 1/1, 65-75, 1988. 2249 [Chau90] Chaum, D., "Showing credentials without identification: 2250 Transferring signatures between unconditionally unlinkable 2251 pseudonyms", Auscrypt , LNCS 453, Springer, Berlin 1990, 2252 246-264, 1990. 2254 [Chi03] Jaquet-Chiffelle, D., "Towards the Identity", Presentation 2255 at the the Future of IDentity in the Information Society 2256 (FIDIS) workshop , http://www.calt.insead.edu/fidis/ 2257 workshop/workshop-wp2-december2003/, December 2003. 2259 [ClSc06] Clauss, S. and S. Schiffner, "Structuring Anonymity 2260 Metrics", in A. Goto (Ed.), DIM '06, Proceedings of the 2261 2006 ACM Workshop on Digital Identity Management, Fairfax, 2262 USA, Nov. 2006, 55-62, 2006. 2264 [CoBi95] Cooper, D. and K. Birm, "Preserving Privacy in a Network 2265 of Mobile Computers", IEEE Symposium on Research in 2266 Security and Privacy , IEEE Computer Society Press, Los 2267 Alamitos 1995, 26-38, 1995. 2269 [DPD95] European Commission, "Directive 95/46/EC of the European 2270 Parliament and of the Council of 24 October 1995 on the 2271 protection of individuals with regard to the processing of 2272 personal data and on the free movement of such data", 2273 Official Journal L 281 , 23/11/1995 P. 0031 - 0050, 2274 November 2005. 2276 [HBCC04] Hansen, M., Berlich, P., Camenisch, J., Clauss, S., 2277 Pfitzmann, A., and M. Waidner, "Privacy-Enhancing Identity 2278 Management", Information Security Technical Report 2279 (ISTR) , Volume 9, Issue 1, 67, 8-16, Elsevier, UK, 35-44, 2280 2004. 2282 [Hild03] Hildebrandt, M., "Same selves? Identification of identity: 2283 a social perspective from a legal-philosophical point of 2284 view", Presentation at the the Future of IDentity in the 2285 Information Society (FIDIS) workshop , http:// 2286 www.calt.insead.edu/fidis/workshop/ 2287 workshop-wp2-december2003/, December 2003. 2289 [HoWi03] Hogben, G., Wilikens, M., and I. Vakalis, "On the Ontology 2290 of Digital Identification", , in: Robert Meersman, Zahir 2291 Tari (Eds.): On the Move to Meaningful Internet Systems 2292 2003: OTM 2003 Workshops, LNCS 2889, Springer, Berlin 2293 2003, 579-593, 2003. 2295 [ICPP03] Independent Centre for Privacy Protection & Studio 2296 Notarile Genghini, "Identity Management Systems (IMS): 2297 Identification and Comparison Study", Study commissioned 2298 by the Joint Research Centre Seville, Spain , http:// 2299 www.datenschutzzentrum.de/projekte/idmanage/study.htm, 2300 September 2003. 2302 [ISO99] ISO, "Common Criteria for Information Technology Security 2303 Evaluation", ISO/IEC 15408 , 1999. 2305 [Mart99] Martin, D., "Local Anonymity in the Internet", PhD 2306 dissertation , Boston University, Graduate School of Arts 2307 and Sciences, http://www.cs.uml.edu/~dm/pubs/thesis.pdf, 2308 December 2003. 2310 [Mead34] Mead, G., "Mind, Self and Society", Chicago Press , 1934. 2312 [PfPW91] Pfitzmann, A., Pfitzmann, B., and M. Michael Waidner, 2313 "ISDN-MIXes -- Untraceable Communication with Very Small 2314 Bandwidth Overhead", 7th IFIP International Conference on 2315 Information Security (IFIP/Sec '91) , Elsevier, Amsterdam 2316 1991, 245-258, 1991. 2318 [PfWa86] Pfitzmann, A. and M. Michael Waidner, "Networks without 2319 user observability -- design options", Eurocrypt '85 , 2320 LNCS 219, Springer, Berlin 1986, 245-253; revised and 2321 extended version in: Computers & Security 6/2 (1987) 158- 2322 166, 1986. 2324 [Pfit96] Pfitzmann, B., "Information Hiding Terminology -- Results 2325 of an informal plenary meeting and additional proposals", 2326 Information Hiding , NCS 1174, Springer, Berlin 1996, 347- 2327 350, 1996. 2329 [RaRD09] Rannenberg, K., Royer, D., and A. Deuker, "The Future of 2330 Identity in the Information Society - Challenges and 2331 Opportunities", Springer, Berlin 2009. , 2009. 2333 [ReRu98] Reiter, M. and A. Rubin, "Crowds: Anonymity for Web 2334 Transactions", ACM Transactions on Information and System 2335 Security , 1(1), 66-92, November 1998. 2337 [Shan48] Shannon, C., "A Mathematical Theory of Communication", The 2338 Bell System Technical Journal , 27, 379-423, 623-656, 2339 1948. 2341 [Shan49] Shannon, C., "Communication Theory of Secrecy Systems", 2342 The Bell System Technical Journal , 28/4, 656-715, 1949. 2344 [StSy00] Stubblebine, S. and P. Syverson, "Authentic Attributes 2345 with Fine-Grained Anonymity Protection", Financial 2346 Cryptography , LNCS Series, Springer, Berlin 2000, 2000. 2348 [Waid90] Waidner, M., "Unconditional Sender and Recipient 2349 Untraceability in spite of Active Attacks", Eurocrypt 2350 '89 , LNCS 434, Springer, Berlin 1990, 302-319, 1990. 2352 [West67] Westin, A., "Privacy and Freedom", Atheneum, New York , 2353 1967. 2355 [Wils93] Wilson, K., "The Columbia Guide to Standard American 2356 English", Columbia University Press, New York , 1993. 2358 [ZFKP98] Zoellner, J., Federrath, H., Klimant, H., Pfitzmann, A., 2359 Piotraschke, R., Westfeld, A., Wicke, G., and G. Wolf, 2360 "Modeling the security of steganographic systems", 2nd 2361 Workshop on Information Hiding , LNCS 1525, Springer, 2362 Berlin 1998, 345-355, 1998. 2364 Authors' Addresses 2366 Andreas Pfitzmann (editor) 2367 TU Dresden 2369 EMail: pfitza@inf.tu-dresden.de 2371 Marit Hansen (editor) 2372 ULD Kiel 2374 EMail: marit.hansen@datenschutzzentrum.de 2375 Hannes Tschofenig 2376 Nokia Siemens Networks 2377 Linnoitustie 6 2378 Espoo 02600 2379 Finland 2381 Phone: +358 (50) 4871445 2382 EMail: Hannes.Tschofenig@gmx.net 2383 URI: http://www.tschofenig.priv.at