How can a client extract useful work from a server without trusting it to compute correctly? A modern motivation for this classic question is third party computing models in which customers outsource their computations to service providers (as in cloud computing). In principle, deep results in complexity theory and cryptography imply that it is possible to verify that an untrusted entity executed a computation correctly. For instance, the server can employ probabilistically checkable proofs (PCPs) in conjunction with cryptographic commitments to generate a succinct proof of correct execution, which the client can efficiently check. However, these theoretical solutions are impractical: they require thousands of CPU years to verifiably execute even simple computations. This dissertation describes the design, implementation, and experimental evaluation viiiof a system, called Pepper, that brings this theory into the realm of plausibility. Pepper incorporates a series of algorithmic improvements and systems engineering techniques to improve performance by over 20 orders of magnitude, relative to an implementation of the theory without our refinements. These include a new probabilistically checkable proof encoding with nearly optimal asymptotics, a concise representation for computations, a more efficient cryptographic commitment primitive, and a distributed implementation of the server with GPU acceleration to reduce latency. Additionally, Pepper extends the verification machinery to handle realistic applications of third party computing: those that interact with remote storage or state (e.g., MapReduce jobs, database queries). To do so, Pepper composes techniques from untrusted storage with the aforementioned technical machinery to verifiably offload both computations and state. Furthermore, to make it easy to use this technology, Pepper includes a compiler to automatically transform programs in a subset of C into executables that run verifiably. One of the chief limitations of Pepper is that verifiable execution is still orders of magnitude slower than an unverifiable native execution. Nonetheless, Pepper takes powerful results from complexity theory and verifiable computation a few steps closer to practicality / text

An integral component of modern computing is the ability to outsource data and computation to powerful remote servers, for instance, in the context of cloud computing or remote file storage. While participants can benefit from this interaction, a fundamental security issue that arises is that of integrity of computation: How can the end-user be certain that the result of a computation over the outsourced data has not been tampered with (not even by a compromised or adversarial server)? Cryptographic schemes for verifiable computation address this problem by accompanying each result with a proof that can be used to check the correctness of the performed computation. Recent advances in the field have led to the first implementations of schemes that can verify arbitrary computations. However, in practice the overhead of these general-purpose constructions remains prohibitive for most applications, with proof computation times (at the server) in the order of minutes or even hours for real-world problem instances. A different approach for designing such schemes targets specific types of computation and builds custom-made protocols, sacrificing generality for efficiency. An important representative of this function-specific approach is an authenticated data structure (ADS), where a specialized protocol is designed that supports query types associated with a particular outsourced dataset. This thesis presents three novel ADS constructions for the important query types of set operations, multi-dimensional range search, and pattern matching, and proves their security under cryptographic assumptions over bilinear groups. The scheme for set operations can support nested queries (e.g., two unions followed by an intersection of the results), extending previous works that only accommodate a single operation. The range search ADS provides an exponential (in the number of attributes in the dataset) asymptotic improvement from previous schemes for storage and computation costs. Finally, the pattern matching ADS supports text pattern and XML path queries with minimal cost, e.g., the overhead at the server is less than 4% compared to simply computing the result, for all our tested settings. The experimental evaluation of all three constructions shows significant improvements in proof-computation time over general-purpose schemes.

As the cloud computing paradigm has gained prominence, the need for verifiable computation has grown urgent. Protocols for verifiable computation enable a weak client to outsource difficult computations to a powerful, but untrusted, server. These protocols provide the client with a (probabilistic) guarantee that the server performed the requested computations correctly, without requiring the client to perform the computations herself. / Engineering and Applied Sciences

Blockchains address trust through cryptography and consensus. Bitcoin is the first digital currency without trusted agents. Ethereum extends this technology by enabling agents on a blockchain, via smart contracts. However, a systemic trust model for smart contracts in blockchains is missing. This thesis describes the ecosystem of smart contracts as an open multi-agent system. A trust model introduces social control through deposits and review agents. Trust-related attributes are quantified in 2,561 smart contracts from GitHub. Smart contracts employ a mean of three variables and functions and one in ten has a security-related issue. Moreover, blockchains restrict computation tasks. Resolving these restrictions while maintaining trust requires verifiable computation. An algorithm for verifiable computation is developed and implemented in Solidity. It uses an arbiter enforcing the algorithm, computation services providing and verifying solutions, and a judge assessing solutions. Experiments are performed with 1000 iterations for one to six verifiers with a cheater prior probability of 30%, 50%, and 70%. The algorithm shows linear complexity for integer multiplication. The verification depends on cheater prior probability and amount of verifiers. In the experiments, six verifiers are sufficient to detect all cheaters for the three prior probabilities. / Blockchains adresserar tillit genom kryptografi och konsensus. Bitcoin är den första digitala valutan utan betrodda agenter. Ethereum utökar denna teknik genom att möjliggöra agenter i blockchain, via smart contracts. En systemisk förtroende modell för smart contracts i blockchains saknas emellertid. Denna avhandling beskriver ekosystemet för smarta kontrakt som ett öppet multi-agent system. En förtroendemodell introducerar social kontroll genom inlåning och granskningsagenter. Tillitrelaterade attribut kvantifieras i 2,561 smart contracts från GitHub. De använder ett medelvärde av tre variabler och funktioner med en av tio som har en säkerhetsre-laterad fråga. Dessutom blockchains begränsa beräkningsuppgifter. Att lösa dessa begränsningar samtidigt som du behåller förtroendet kräver kontrollerbar beräkning. En algoritm för verifierbar beräkning utvecklas och implementeras i Solidity. Den använder en arbiter som tillämpar algoritmen, computation services som tillhandahåller och verifierar lösningar och en judge som bedömer lösningar. Experiment utförs med 1000 iterationer för en till sex verifierare med en snyggare sannolikhet för 30%, 50% och 70%. Algoritmen visar linjär komplexitet för heltalsmultiplicering. Verifieringen beror på fuskans tidigare sannolikhet och antal verifierare. I experimenten är sex verifierare tillräckliga för att detektera alla cheaters för de tre tidigare sannolikheterna.

Approved for public release, distribution is unlimited / A dynamic subversion attack on the Windows XP Embedded operating system is demonstrated to raise awareness in developers and consumers of the risk of subversion in commercial operating systems that may be safety critical. SCADA (Supervisory Control and Data Acquisition) systems that monitor and control our critical infrastructure depend on embedded systems. The attack can be loaded onto a fielded system that has been subverted with a small software artifice. The artifice could be inserted into the system at any time in the system's lifecycle. The attack provides a flexible method for the attacker, who may not be the same individual who inserted the artifice, to gain total control of the subverted system. Due to the dynamic loading property of this subversion, the attacker does not have to decide the aspect of the system to be targeted until a time of her choice. The attack does not exploit an existing flaw in the target module but is possible because the initial artifice is inserted into the kernel of an operating system where adversaries have access to source code. This thesis discusses certain aspects of known methods for developing systems free from subversion. Several projects that utilized these methods are presented. / Civilian, Naval Postgraduate School

Many organizations today are seeking to improve security by implementing multi-factor authentication, i.e. authentication requiring more than one independent mechanism to prove one's identity. One-time passwords in the form of hardware tokens in combination with conventional passwords have emerged as the predominant means in high security environments to satisfy the independent identification criteria for strong authentication. However, current popular public one-time passwords solutions such as HOTP, mOTP, TOTP, and S/Key depend on the computational complexity of breaking encryption or hash functions for security. This thesis will present an efficient and information-theoretically secure one-time password system called Shamir-OTP that is based upon secret sharing techniques.

Cette thèse est consacrée au domaine de l’utilisabilité de la sécurité, en particulier dans le contexte de l’authentification en ligne et du vote vérifiable.Le rôle toujours plus important de nos identifiants en ligne, qu’ils soient utilisés pour accéder aux réseaux sociaux, aux services bancaires ou aux systèmes de vote, a débouché sur des solutions faisant plus de mal que de bien. Le problème n’est pas juste technique mais a une forte composante psycho-sociale, qui se révèle dans l’usage des mots de passe --- objet central d'étude de cette thèse. Les utilisateurs font quotidiennement face à des compromis, souvent inconscients, entre sécuriser leurs données et dépenser les ressources mentales limitées et déjà trop sollicitées. Des travaux récents ont montré que l'absence de règles communes, les contraintes ad-hoc si fréquentes et les recommandations contradictoires compliquent ce choix, mais ces recherches sont généralement ignorées, victimes d'une probable incompréhension entre chercheurs, développeurs et utilisateurs. Cette thèse vise à résoudre ces problèmes avec des solutions inspirées par la cryptographie, la psychologie, ainsi que sept études utilisateurs, afin d'obtenir des outils simplifiés non seulement pour l'utilisateur final mais aussi pour le développeur.La première partie des contributions se concentre sur le fournisseur de service, avec deux outils permettant d'améliorer l'expérience utilisateur sans effort de sa part. Nous commençons par une étude sur la facilité de transcription de différents types de codes, afin d'obtenir un design réduisant les erreurs tout en augmentant la vitesse de frappe. Nous montrons aussi comment accepter les fautes de frappe dans les mots de passe peut améliorer la sécurité, en offrant un protocole compatible avec les méthodes de hachage standard.La deuxième partie offre des outils directement aux utilisateurs, avec un gestionnaire de mot de passe mental qui ne nécessite que la mémorisation d'une phrase et d'un code PIN, avec des garanties sur la sécurité des mots de passe si certains sont compromis. Nous proposons aussi une méthode de création de phrase de passe à la fois plus facile et sécurisée, et terminons en montrant empiriquement des failles dans le principal modèle de calcul mental utilisé aujourd'hui dans le domaine.Enfin, nous nous consacrons aux nouveaux protocoles de vote, en commençant par les difficultés à les faire accepter en pratique. Nous répondons à une demande pour des systèmes non-électroniques en proposant plusieurs implémentations de vote vérifiable en papier, une panoplie de primitives et un protocole de vote pour les très petites élections. / This dissertation deals with the field of usable security, particularly in the contexts of online authentication and verifiable voting systems.The ever-expanding role of online accounts in our lives, from social networks to banking or online voting, has led to some initially counterproductive solutions. As recent research has shown, the problem is not just technical but has a very real psychosocial component. Password-based authentication, the subject of most of this thesis, is intrinsically linked to the unconscious mechanisms people use when interacting with security systems. Everyday, users face trade-offs between protecting their security and spending valuable mental resources, with a choice made harder by conflicting recommendations, a lack of standards, and the ad-hoc constraints still frequently encountered. Moreover, as recent results from usable security are often ignored, the problem might stem from a fundamental disconnect between the users, the developers and the researchers. We try to address those problems with solutions that are not only simplified for the user's sake but also for the developer's. To this end, we use tools from cryptography and psychology, and report on seven usability experiments.The first part of the contributions uses a service provider's point of view, with two tools to improve the end-user's experience without requiring their cooperation. We start by analysing how easily codes of different structures can be transcribed, with a proposal that reduces error rates while increasing speed. We then look at how servers can accept typos in passwords without changing the general hashing protocol, and how this could improve security. The second part focuses on end-users, starting by a proposed mental password manager that only depends on remembering only a single passphrase and PIN, with guarantees on the mutual security of generated passwords if some get stolen. We also provide a better way to create such passphrases. As mental computing models are central to expanding this field, we finish by empirically showing why the main model used today is not adapted to the purpose.In the third part, we focus on voting protocols, and investigate why changing the ones used in practice is an uphill battle. We try to answer a demand for simple paper-based systems by providing low-tech versions of the first paper-based verifiable voting scheme. To conclude, we propose a set of low-tech primitives combined in a protocol that allows usable verifiable voting with no electronic means in small elections.

Tor hidden services are anonymous servers of unknown location and ownership who can be accessed through any Tor-enabled web browser. They have gained popularity over the years, but still suer from major usability challenges due to their cryptographicallygenerated non-memorable addresses. In response to this difficulty, in this work we introduce the Onion Name System (OnioNS), a privacy-enhanced distributed DNS that allows users to reference a hidden service by a meaningful globally-unique veriable domain name chosen by the hidden service operator. We introduce a new distributed self-healing public ledger and construct OnioNS as an optional backwards-compatible plugin for Tor on top of existing hidden service infrastructure. We simplify our design and threat model by embedding OnioNS within the Tor network and provide mechanisms for authenticated denial-of-existence with minimal networking costs. Our reference implementation demonstrates that OnioNS successfully addresses the major usability issue that has been with Tor hidden services since their introduction in 2002.

Free and fair elections are the basis for democracy, but conducting elections is not an easy task. Different groups of people are trying to influence the outcome of the election in their favor using the range of methods, from campaigning for a particular candidate to well-financed lobbying. Often the stakes are too high, and the methods are illegal. Two main properties of any voting scheme are the privacy of a voter’s choice and the integrity of the tally. Unfortunately, they are mutually exclusive. Integrity requires making elections transparent and auditable, but at the same time, we must preserve a voter’s privacy. It is always a trade-off between these two requirements. Current voting schemes favor privacy over auditability, and thus, they are vulnerable to voting fraud. I propose two novel voting systems that can achieve both privacy and verifiability. The first protocol is based on cryptographical primitives to ensure the integrity of the final tally and privacy of the voter. The second protocol is a simple paper-based voting scheme that achieves almost the same level of security without usage of cryptography.

Past few years have witnessed a dramatic shift for IT infrastructures from a self-sustained model to a centralized and multi-tenant elastic computing paradigm -- Cloud Computing, which significantly reshapes the landscape of existing data utilization services. In truth, public cloud service providers (CSPs), e.g. Google, Amazon, offer us unprecedented benefits, such as ubiquitous and flexible access, considerable capital expenditure savings and on-demand resource allocation. Cloud has become the virtual ``brain" as well to support and propel many important applications and system designs, for example, artificial intelligence, Internet of Things, and so forth; on the flip side, security and privacy are among the primary concerns with the adoption of cloud-based data services in that the user loses control of her/his outsourced data. Encrypting the sensitive user information certainly ensures the confidentiality. However, encryption places an extra layer of ambiguity and its direct use may be at odds with the practical requirements and defeat the purpose of cloud computing technology. We believe that security in nature should not be in contravention of the cloud outsourcing model. Rather, it is expected to complement the current achievements to further fuel the wide adoption of the public cloud service. This, in turn, requires us not to decouple them from the very beginning of the system design. Drawing the successes and failures from both academia and industry, we attempt to answer the challenges of realizing efficient and useful secure data services in the public cloud. In particular, we pay attention to security and privacy in two essential functions of the cloud ``brain", i.e. data storage and processing. Our first work centers on the secure chunk-based deduplication of encrypted data for cloud backup and achieves the performance comparable to the plaintext cloud storage deduplication while effectively mitigating the information leakage from the low-entropy chunks. On the other hand, we comprehensively study the promising yet challenging issue of search over encrypted data in the cloud environment, which allows a user to delegate her/his search task to a CSP server that hosts a collection of encrypted files while still guaranteeing some measure of query privacy. In order to accomplish this grand vision, we explore both software-based secure computation research that often relies on cryptography and concentrates on algorithmic design and theoretical proof, and trusted execution solutions that depend on hardware-based isolation and trusted computing. Hopefully, through the lens of our efforts, insights could be furnished into future research in the related areas. / Ph. D. / Past few years have witnessed a dramatic shift for IT infrastructures from a self-sustained model to a centralized and multi-tenant elastic computing paradigm – Cloud Computing, which significantly reshapes the landscape of existing data utilization services. In truth, public cloud service providers (CSPs), e.g. Google, Amazon, offer us unprecedented benefits, such as ubiquitous and flexible access, considerable capital expenditure savings and on-demand resource allocation. Cloud has become the virtual “brain” as well to support and propel many important applications and system designs, for example, artificial intelligence, Internet of Things, and so forth; on the flip side, security and privacy are among the primary concerns with the adoption of cloud-based data services in that the user loses control of her/his outsourced data. Encryption definitely provides strong protection to user sensitive data, but it also disables the direct use of cloud data services and may defeat the purpose of cloud computing technology. We believe that security in nature should not be in contravention of the cloud outsourcing model. Rather, it is expected to complement the current achievements to further fuel the wide adoption of the public cloud service. This, in turn, requires us not to decouple them from the very beginning of the system design. Drawing the successes and failures from both academia and industry, we attempt to answer the challenges of realizing efficient and useful secure data services in the public cloud. In particular, we pay attention to security and privacy in two essential functions of the cloud “brain”, i.e. data storage and processing. The first part of this research aims to provide a privacy-preserving data deduplication scheme with the performance comparable to the existing cloud backup storage deduplication. In the second part, we attempt to secure the fundamental information retrieval functions and offer effective solutions in various contexts of cloud data services.