Hidden undesired functionality is an unavoidable reality in any complex hardware or software component. Undesired functionality — deliberately introduced Trojan horses or accidentally introduced bugs — in any component of a system can be exploited by attackers to exert control over the system. This poses a serious security risk to systems — especially in the ever growing number of systems based on networks of computers. The approach adopted in this dissertation to secure systems seeks immunity from hidden functionality. Specifcally, if a minimal trusted computing base (TCB) for any system can be identifed, and if we can eliminate hidden functionality in the TCB, all desired assurances regarding the operation of the system can be guaranteed. More specifcally, the desired assurances are guaranteed even if undesired functionality may exist in every component of the system outside the TCB. A broad goal of this dissertation is to characterize the TCB for various systems as a set of functions executed by a trusted security kernel. Some constraints are deliberately imposed on the security kernel functionality to reduce the risk of hidden functionality inside the security kernel. In the security model adopted in this dissertation, any system is seen as an interconnection of subsystems, where each subsystem is associated with a security kernel. The security kernel for a subsystem performs only the bare minimal tasks required to assure the integrity of the tasks performed by the subsystem. Even while the security kernel functionality may be different for each system/subsystem, it is essential to identify reusable components of the functionality that are suitable for a wide range of systems. The contribution of the research is a versatile data-structure — Ordered Merkle Tree (OMT), which can act as the reusable component of various security kernels. The utility of OMT is illustrated by designing security kernels for subsystems participating in, 1) a remote fle storage system, 2) a generic content distribution system, 3) generic look-up servers, 4) mobile ad-hoc networks and 5) the Internet’s routing infrastructure based on the border gateway protocol (BGP).

The subject of this dissertation is the construction of privacy-enhancing technologies (PETs) for transparency logging, a technology at the intersection of privacy, transparency, and accountability. Transparency logging facilitates the transportation of data from service providers to users of services and is therefore a key enabler for ex-post transparency-enhancing tools (TETs). Ex-post transparency provides information to users about how their personal data have been processed by service providers, and is a prerequisite for accountability: you cannot hold a controller accountable for what is unknown. We present three generations of PETs for transparency logging to which we contributed. We start with early work that defined the setting as a foundation and build upon it to increase both the privacy protections and the utility of the data sent through transparency logging. Our contributions include the first provably secure privacy-preserving transparency logging scheme and a forward-secure append-only persistent authenticated data structure tailored to the transparency logging setting. Applications of our work range from notifications and deriving data disclosures for the Data Track tool (an ex-post TET) to secure evidence storage. / The subject of this dissertation is the construction of privacy-enhancing technologies (PETs) for transparency logging, a technology at the intersection of privacy, transparency, and accountability. Transparency logging facilitates the transportation of data from service providers to users of services and is therefore a key enabler for ex-post transparency-enhancing tools (TETs). Ex-post transparency provides information to users about how their personal data have been processed by service providers, and is a prerequisite for accountability: you cannot hold a controller accountable for what is unknown. We present three generations of PETs for transparency logging to which we contributed. We start with early work that defined the setting as a foundation and build upon it to increase both the privacy protections and the utility of the data sent through transparency logging. Our contributions include the first provably secure privacy-preserving transparency logging scheme and a forward-secure append-only persistent authenticated data structure tailored to the transparency logging setting. Applications of our work range from notifications and deriving data disclosures for the Data Track tool (an ex-post TET) to secure evidence storage.

This dissertation proposes an efficient representation of a sparse Merkle tree (SMT): an authenticated data structure that supports logarithmic insertion, removal, and look-up in a verifiable manner. The proposal is general in the sense that it can be implemented using a variety of underlying non-authenticated data structures, and it allows trading time for space by the use of an abstract model which represents caching strategies. Both theoretical evaluations and performance results from a proof-of-concept implementation are provided, and the proposed SMT is applied to another authenticated data structure referred to as Balloon. The resulting Balloon has preserved efficiency in the expected case, and is improved with respect to worst case scenarios.