Security and Trust in Distributed Computation

We propose three research problems to explore the relations between trust and security in the setting of distributed computation. In the first problem, we study trust-based adversary detection in distributed consensus computation. The adversaries we consider behave arbitrarily disobeying the consensus protocol. We propose a trust-based consensus algorithm with local and global trust evaluations. The algorithm can be abstracted using a two-layer structure with the top layer running a trust-based consensus algorithm and the bottom layer as a subroutine executing a global trust update scheme. We utilize a set of pre-trusted nodes, headers, to propagate local trust opinions throughout the network. This two-layer framework is flexible in that it can be easily extensible to contain more complicated decision rules, and global trust schemes. The first problem assumes that normal nodes are homogeneous, i.e. it is guaranteed that a normal node always behaves as it is programmed. In the second and third problems however, we assume that nodes are heterogeneous, i.e, given a task, the probability that a node generates a correct answer varies from node to node. The adversaries considered in these two problems are workers from the open crowd who are either investing little efforts in the tasks assigned to them or intentionally give wrong answers to questions. In the second part of the thesis, we consider a typical crowdsourcing task that aggregates input from multiple workers as a problem in information fusion. To cope with the issue of noisy and sometimes malicious input from workers, trust is used to model workers' expertise. In a multi-domain knowledge learning task, however, using scalar-valued trust to model a worker's performance is not sufficient to reflect the worker's trustworthiness in each of the domains. To address this issue, we propose a probabilistic model to jointly infer multi-dimensional trust of workers, multi-domain properties of questions, and true labels of questions. Our model is very flexible and extensible to incorporate metadata associated with questions. To show that, we further propose two extended models, one of which handles input tasks with real-valued features and the other handles tasks with text features by incorporating topic models. Our models can effectively recover trust vectors of workers, which can be very useful in task assignment adaptive to workers' trust in the future. These results can be applied for fusion of information from multiple data sources like sensors, human input, machine learning results, or a hybrid of them. In the second subproblem, we address crowdsourcing with adversaries under logical constraints. We observe that questions are often not independent in real life applications. Instead, there are logical relations between them. Similarly, workers that provide answers are not independent of each other either. Answers given by workers with similar attributes tend to be correlated. Therefore, we propose a novel unified graphical model consisting of two layers. The top layer encodes domain knowledge which allows users to express logical relations using first-order logic rules and the bottom layer encodes a traditional crowdsourcing graphical model. Our model can be seen as a generalized probabilistic soft logic framework that encodes both logical relations and probabilistic dependencies. To solve the collective inference problem efficiently, we have devised a scalable joint inference algorithm based on the alternating direction method of multipliers. The third part of the thesis considers the problem of optimal assignment under budget constraints when workers are unreliable and sometimes malicious. In a real crowdsourcing market, each answer obtained from a worker incurs cost. The cost is associated with both the level of trustworthiness of workers and the difficulty of tasks. Typically, access to expert-level (more trustworthy) workers is more expensive than to average crowd and completion of a challenging task is more costly than a click-away question. In this problem, we address the problem of optimal assignment of heterogeneous tasks to workers of varying trust levels with budget constraints. Specifically, we design a trust-aware task allocation algorithm that takes as inputs the estimated trust of workers and pre-set budget, and outputs the optimal assignment of tasks to workers. We derive the bound of total error probability that relates to budget, trustworthiness of crowds, and costs of obtaining labels from crowds naturally. Higher budget, more trustworthy crowds, and less costly jobs result in a lower theoretical bound. Our allocation scheme does not depend on the specific design of the trust evaluation component. Therefore, it can be combined with generic trust evaluation algorithms.

ADVERTISEMENT ALLOCATION AND TRUST MECHANISMS DESIGN IN SOCIAL NETWORKS

Social network sites (SNS), such as Facebook, Google+ and Twitter, have attracted hundreds of millions of users daily since their appearance. Within SNS, users connect to each other, express their identity, disseminate information and form cooperation by interacting with their connected peers. The increasing popularity and ubiquity of SNS usage and the invaluable user behaviors and connections give birth to many applications and business models. We look into several important problems within the social network ecosystem. The first one is the SNS advertisement allocation problem. The other two are related to trust mechanisms design in social network setting, including local trust inference and global trust evaluation. In SNS advertising, we study the problem of advertisement allocation from the ad platform's angle, and discuss its differences with the advertising model in the search engine setting. By leveraging the connection between social networks and hyperbolic geometry, we propose to solve the problem via approximation using hyperbolic embedding and convex optimization. A hyperbolic embedding method, \hcm, is designed for the SNS ad allocation problem, and several components are introduced to realize the optimization formulation. We show the advantages of our new approach in solving the problem compared to the baseline integer programming (IP) formulation. In studying the problem of trust mechanisms in social networks, we consider the existence of distrust (i.e. negative trust) relationships, and differentiate between the concept of local trust and global trust in social network setting. In the problem of local trust inference, we propose a 2-D trust model. Based on the model, we develop a semiring-based trust inference framework. In global trust evaluation, we consider a general setting with conflicting opinions, and propose a consensus-based approach to solve the complex problem in signed trust networks.

A MEMETIC/PARTICIPATORY APPROACH FOR CHANGING SOCIAL BEHAVIORS AND PROMOTING ENVIRONMENTAL STEWARDSHIP IN JALISCO, MEXICO

This dissertation addressed the issue of sustainable development at the level of individual behaviors. Environmental perceptions were obtained from people living around the biosphere reserve Chamela-Cuixmala in Jalisco, Mexico. Several environmental issues were identified by the people, such as garbage and grey water on the streets, burning plastics, and the lack of usage of recreational areas. All these issues could be addressed with a change in behavior by the villagers. Familiarization activities were conducted to gain people's trust in order to conduct a community forum. These activities included giving talks to school children and organizing workshops. Four different methodologies were generated using memetics and participation to test which would ameliorate those environmental issues identified by the people through a change in behavior. The methodologies were 1) Memes; 2) Participation and Memes; 3) Participation; 4) Neither Participation nor Memes. A meme is an idea expressed within a linguistic structure or architecture that provides it with self-disseminating and self-protecting characteristics within and among the minds of individuals congruent with their values, beliefs and filters. Four villages were chosen as the treatments, and one as the control, for a total of five experimental villages. A different behavior was addressed in each treatment village (garbage, grey-water, burning plastics, recreation.) A nonequivalent control-group design was established. A pretest was conducted in all five villages; the methodologies were tested in the four treatment villages; a posttest was conducted on the five villages. The pretest and posttest consisted in measuring sensory specific indicators which are manifestations of behavior that can either be seen, smelled, touched, heard or tasted. Statistically significant differences in behavior from the control were found for two of the methodologies 1) Memes (p=0.0403) and 2) Participation and Memes (p=0.0064). For the methodologies of 3) Participation alone and 4) Neither, the differences were not significant (p=0.8827, p=0.5627 respectively). When using memes, people's behavior improved when compared to the control. Participation alone did not generate a significant difference. Participation aided in the generation of the memes. Memetics is a tool that can be used to establish a linkage between human behavior and ecological health.

Studies on Understanding Individual Willingness to Disclose Genetic Information to Public and Private Stakeholders

While technologies for genetic sequencing have increased the promise of personalized medicine, they simultaneously pose threats to personal privacy. The public’s desire to protect itself from unauthorized access to information may limit the uses of this valuable resource. To date, there is limited understanding about the public’s attitudes toward the regulation and sharing of such information. We sought to understand the drivers of individuals’ decisions to disclose genetic information to a third party in a setting where disclosure potentially creates both private and social benefits, but also carries the risk of potential misuse of private information. We conducted two separate but related studies. First, we administered surveys to college students and parents, to determine individual attitudes toward and inter-generational influences on the disclosure decision. Second, we conducted a game-theory based experiment that assessed how participants’ decisions to disclose genetic information are influenced by societal and health factors. Key survey findings indicate that concerns about genetic information privacy negatively impact the likelihood of disclosure while the perceived benefits of disclosure and trust in the institution receiving the information have a positive influence. The experiment results also show that the risk of discrimination negatively affects the likelihood of disclosure, while the positive impact that disclosure has on the probability of finding a cure and the presence of a monetary incentive to disclose, increase the likelihood. We also study the determinants of individuals’ decision to be informed of findings about their health, and how information about health status is used for financial decisions.

Language-based Techniques for Practical and Trustworthy Secure Multi-party Computations

Secure Multi-party Computation (MPC) enables a set of parties to collaboratively compute, using cryptographic protocols, a function over their private data in a way that the participants do not see each other's data, they only see the final output. Typical MPC examples include statistical computations over joint private data, private set intersection, and auctions. While these applications are examples of monolithic MPC, richer MPC applications move between "normal" (i.e., per-party local) and "secure" (i.e., joint, multi-party secure) modes repeatedly, resulting overall in mixed-mode computations. For example, we might use MPC to implement the role of the dealer in a game of mental poker -- the game will be divided into rounds of local decision-making (e.g. bidding) and joint interaction (e.g. dealing). Mixed-mode computations are also used to improve performance over monolithic secure computations. Starting with the Fairplay project, several MPC frameworks have been proposed in the last decade to help programmers write MPC applications in a high-level language, while the toolchain manages the low-level details. However, these frameworks are either not expressive enough to allow writing mixed-mode applications or lack formal specification, and reasoning capabilities, thereby diminishing the parties' trust in such tools, and the programs written using them. Furthermore, none of the frameworks provides a verified toolchain to run the MPC programs, leaving the potential of security holes that can compromise the privacy of parties' data. This dissertation presents language-based techniques to make MPC more practical and trustworthy. First, it presents the design and implementation of a new MPC Domain Specific Language, called Wysteria, for writing rich mixed-mode MPC applications. Wysteria provides several benefits over previous languages, including a conceptual single thread of control, generic support for more than two parties, high-level abstractions for secret shares, and a fully formalized type system and operational semantics. Using Wysteria, we have implemented several MPC applications, including, for the first time, a card dealing application. The dissertation next presents Wys*, an embedding of Wysteria in F*, a full-featured verification oriented programming language. Wys* improves on Wysteria along three lines: (a) It enables programmers to formally verify the correctness and security properties of their programs. As far as we know, Wys* is the first language to provide verification capabilities for MPC programs. (b) It provides a partially verified toolchain to run MPC programs, and finally (c) It enables the MPC programs to use, with no extra effort, standard language constructs from the host language F*, thereby making it more usable and scalable. Finally, the dissertation develops static analyses that help optimize monolithic MPC programs into mixed-mode MPC programs, while providing similar privacy guarantees as the monolithic versions.

THERE GOES THE ELECTORAL NEIGHBORHOOD: LOCAL NETWORKS, ATTRIBUTION OF RESPONSIBILITY, AND THE (UN) FAIRNESS OF ELECTIONS

During the last two decades there have been but a handful of recorded cases of electoral fraud in Latin America. However, survey research consistently shows that often citizens do not trust the integrity of the electoral process. This dissertation addresses the puzzle by explaining the mismatch between how elections are conducted and how the process is perceived. My theoretical contribution provides a double-folded argument. First, voters’ trust in their community members (“the local experience”) impacts their level of confidence in the electoral process. Since voters often find their peers working at polling stations, negative opinions about them translate into negative opinions about the election. Second, perceptions of unfairness of the system (“the global effect”) negatively impact the way people perceive the transparency of the electoral process. When the political system fails to account for social injustice, citizens lose faith in the mechanism designed to elect representatives -and ultimately a set of policies. The fact that certain groups are systematically disregarded by the system triggers the notion that the electoral process is flawed. This is motivated by either egotropic or sociotropic considerations. To test these hypotheses, I employ a survey conducted in Costa Rica, El Salvador, Honduras, and Guatemala during May/June 2014, which includes a population-based experiment. I show that Voters who trust their peers consistently have higher confidence in the electoral process. Whereas respondents who were primed about social unfairness (treatment) expressed less confidence in the quality of the election. Finally, I find that the local experience is predominant over the global effect. The treatment has a statistically significant effect only for respondents who trust their community. Attribution of responsibility for voters who are skeptics of their peers is clear and simple, leaving no room for a more diffuse mechanism, the unfairness of the political system. Finally, now I extend analysis to the Latin America region. Using data from LAPOP that comprises four waves of surveys in 22 countries, I confirm the influence of the “local experience” and the “global effect” as determinants of the level of confidence in the electoral process.