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.

Between Nation and State: Albanian Associations from Ottoman Origins to a Communist Party, 1880 - 1945

This dissertation addresses the broader antecedents of the Communist Party of Albania (CPA) as one of a number of associations whose experience was central to Albanian political history. This long experience dates back to the informal national associations formed in the Ottoman Empire of the late nineteenth century. The dissertation examines the role of these associations which, pursuing language rights and political representation through imperial state reforms, set a pattern that struggled to connect nation and state, rather than asserting the territorial demands for a nation-state familiar across the region. Starting out in the Ottoman Empire, but then maturing in the Albanian diaspora in Romania, Bulgaria, Egypt and the United States, this dissertation shows politically significant processes of longer-term adaptation that created informal associations as institutional structures able to channel collective action. It then traces the reframing of these patterns through their destruction in the Balkan Wars and the First World War to the emergence of communist associations in the interwar period and beyond. This dissertation is a sustained study that traces long-term Ottoman imperial political legacies in the Albanian successor state. The story of the associations, based on hitherto unexamined archival documents, shows that the Albanians possessed a far greater capacity for political mobilization that previously acknowledged by historians. Moreover, the dissertation successfully challenges the conventional wisdom that portrays the Albanians as irreparably divided along sectarian and regional faultlines. It finds that Albanian national activism was civic in character rather than ethnic as elsewhere in the Balkans. The Albanians fought to remain within a multinational framework because this afforded them political security, social advancement and potential economic growth. In the late Ottoman period, this political objective was manifested in the acceptance of the supranational imperial order whereas during the Second World War, in the aspiration to become members of the Comintern internationalist movement. Another important find, is the newly-discovered evidence concerning the founding of the CPA and its wartime conduct as an organization created and led by the Albanians themselves, albeit with Yugoslav ideological assistance under the transnational umbrella of the Comintern.