An electronic government (e-government) can be viewed as a large distributed information system consisting of interconnected heterogeneous subsystems through which government agencies, citizens, and public and private sectors interact to facilitate exchange and sharing of huge volumes of information. Such large scale information sharing and interoperation are geared towards streamlining decision-making processes through an efficient flow of information and execution of government’s transactions to facilitate easy access to improved services. Key scenarios of system interactions in an e-government include: government to citizen/employee (G2C/E), government to business (G2B), and government to government (G2G), (OMB, 2004). G2C (or G2E) activities cover the interactions and information exchange between government agencies and citizens (or its employees), for instance, while filing government taxes. G2B refers to activities related to interactions between government and public and private sectors, for instance, when a government agency engages in a supplier-consumer or a buyer-seller relationship with a public/private sector business. G2G refers to activities involving interactions between two government entities. An interaction between a state office and a related federal office is an example of a G2G interaction. A critical issue related to these interactions is the need to integrate system components under disparate administrative domains with distinct policies and mechanisms. Crucial goals of an e-government infrastructure also include increasing internal efficiency and effectiveness (IEE) and streamlining common lines of business (CLoB) (OMB, 2004). For instance, if each of the federal agencies has its own payroll system, the IEE activities may involve consolidating the payroll function of multiple agencies into one system. This makes the payroll function a logical part of different agencies, thus, processing different sets of payroll information, under possibly different security policies. Similarly, if the agencies have CLoBs, the e-government infrastructure would need to remove unwarranted redundancy in service components and information processing activities. Although emerging IT solutions provide intriguing opportunities for supporting the design and implementation of an e-government infrastructure, use of these technologies, the highly sensitive nature of information it maintains, critical transactions it processes, and the national security issues the government processes bring forth, create significant infrastructure security challenge (GAO, 2004; Joshi, et al., 2001b). The recent GAO report indicates that while interconnectivity of heterogeneous domains is a basic need for an efficient e-government system, it significantly raises the potential for unauthorized access to personal and confidential data and exposes the critical infrastructures to new vulnerabilities (GAO, 2004). A significant challenge is thus, to provide an integrated e-government infrastructure that ensures secure integration of services and information sources, fosters security assured partnerships among public and private sectors, and securely manage government resources.