E-government systems aim to transition traditional paper-based systems to “paperless” digital information systems to automate and streamline government operations and services. This transformation to digital form raises daunting challenges related to protecting identity and privacy of the citizens. Electronic fraud and identity theft are among the biggest risks to an e-government system that may potentially undermine its success. The CSI/FBI 2005 (Gordon, Loeb, Lucyshyn, & Richardson, 2005) Computer Crime and Security Survey reports more than $30 million in losses attributed to theft of proprietary information and more than a $31 million dollars loss related to unauthorized accesses. According to the data collected by the Consumer Sentinel and Identity Theft Data Clearing House, identity theft accounts for almost 40% of the fraud complaints (FTC, 2005). It is estimated that billions of records are available in both private and government databases describing each citizen’s finances, interests, and demographics. For instance, personal healthcare information about the diseases and health cases inflicting the general population are available in different places including insurance companies and pharmacies. While accessing such data is important for detecting epidemics and bio-terrorism, such accesses can easily encroach into citizen privacy. This demands a balancing act in dealing with issues related to privacy, accountability, national security, and/or good governance. Because of the heterogeneity of an e-government system, the task of protecting identity information as citizens interact with different sub-systems becomes exacerbated. Users typically may need to maintain multiple identities or complete anonymity while interacting with multiple interoperating systems raising severe privacy and identity management problems. For an e-government system to be reliable, and hence successfully deployed, the privacy and identity management issues need to be properly addressed and incorporated in its infrastructure design. Privacy may be defined as “the right of individuals, groups, or institutions to determine for themselves when, how, and to what extent information about them is communicated” (Jajodia, 1998). Thus, unlike security, which is organization-centric, privacy is a person-centric concept and refers to the control that an individual has over the use of his or her personal information. One aspect of the privacy problem is the anonymity of the users, which is aimed at protecting the identity of the users. The identity of an individual is a collection of personal data associated with the individual that uniquely identifies him or her. Associated with each identity is a set of attribute-value pairs, also known as credentials, typically representing a user’s qualifications and personal attributes including sensitive personal information such as name, age, and social security number. The capability to identify entities (subjects, objects, and resources) is essential in order to know what to protect from whom. Depending upon the context, a subset of the identity may be used to signify an individual. Such a “partial identity” is typically bound to the individual with a pseudonym (Köhntopp & Berthold, 2000), and may or may not uniquely identify the individual. Typically, multiplicity of identities for individual entities becomes necessary because of the requirements of anonymity, personal data protection, and controlled access to resources in multidomain e-government systems. Moreover, the notion of privacy and identity is inherently complex and may often be contradictory; furthermore, each stakeholder could have a different perspective on them. In large multidomain e-government system, identity management would typically aim towards providing mechanisms that ensure identity dependability to build and maintain trust and confidence between the interacting entities.