We present SlicedPIR, a distributed Private Information Retrieval (PIR) protocol. SlicedPIR efficiently alleviates the server's compute bottleneck by offloading its load across multiple untrusted client machines. In contrast to prior work, SlicedPIR induces only a modest network overhead when the server offloads its work. It achieves those communication savings by exploiting the polynomial encoding of homomorphic encryption schemes typically used in PIR protocols. This encoding lets the server make novel use of the Number Theoretic Transform (NTT) to distribute points on the polynomials as ''slices'' of its data rather than the polynomials themselves. Using NTT allows the clients to process recursive PIR queries on their slices and return a succinct result to the server. The server efficiently verifies the clients' results by leveraging the Schwartz-Zippel lemma, which we adapt to the PIR use case. We show how to integrate SlicedPIR into a private messaging system, where clients write messages to the server's database and then use PIR to secretly query for messages from their friends. We implement a prototype of SlicedPIR and run experiments to show that it scales well with the number of clients and database size. Concretely, SlicedPIR achieves better performance and cuts network usage by over 95% compared to the state-of-the-art.

This paper presents a new architecture for metadata-private messaging that counters scalability challenges by offloading most computations to the clients. At the core of our design is a distributed private information retrieval (PIR) protocol, where the responder delegates its work to alleviate PIR's computational bottleneck and catches misbehaving delegates by efficiently verifying their results. We introduce DPIR, a messaging system that uses distributed PIR to let a server storing messages delegate the work to the system's clients, such that each client contributes proportional processing to the number of messages it reads. The server removes clients returning invalid results, which DPIR leverages to integrate an incentive mechanism for honest client behavior by conditioning messaging through DPIR on correctly processing PIR requests from other users. The result is a metadata-private messaging system that asymptotically improves scalability over prior work with the same threat model. We show through experiments on a prototype implementation that DPIR concretely improves performance by 3.25× and 4.31× over prior work [3, 5] and that the performance gap grows with the user base~size.

Distributed systems are often designed to recover from downed nodes. Unfortunately, it is challenging to create recovery mechanisms that work in Byzantine networks, where the attacker controls some of the nodes and links. Often times an adversarial node can lie about an honest node being offline, and there is no way to verify this claim or detect the liar.

A high-level, technical summary of the Trusted Software Methodology (TSM) is provided in this paper. The trust principles and trust classes that comprise the TSM are presented and several engineering investigations and case studies surrounding the TSM are outlined. Appendices are included that highlight important areas of the TSM.

The authors have been involved in the development of an approach to measuring the trust of software, at some state in the software development life cycle. The primary emphasis has been on the use of well-known and generally accepted security and software engineering principles as a means for establishing software trust. A description of the critical issues related to software trust is provided here. A set of criteria classes consisting of various trust principle combinations is shown to provide a scale for measuring and comparing trust. The System V/MLS secure operating system development approach is used to demonstrate the effect of trust principles in a practical setting.>