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.

SEQUENTIAL DECISIONS AND PREDICTIONS IN NATURAL LANGUAGE PROCESSING

Natural language processing has achieved great success in a wide range of ap- plications, producing both commercial language services and open-source language tools. However, most methods take a static or batch approach, assuming that the model has all information it needs and makes a one-time prediction. In this disser- tation, we study dynamic problems where the input comes in a sequence instead of all at once, and the output must be produced while the input is arriving. In these problems, predictions are often made based only on partial information. We see this dynamic setting in many real-time, interactive applications. These problems usually involve a trade-off between the amount of input received (cost) and the quality of the output prediction (accuracy). Therefore, the evaluation considers both objectives (e.g., plotting a Pareto curve). Our goal is to develop a formal understanding of sequential prediction and decision-making problems in natural language processing and to propose efficient solutions. Toward this end, we present meta-algorithms that take an existent batch model and produce a dynamic model to handle sequential inputs and outputs. Webuild our framework upon theories of Markov Decision Process (MDP), which allows learning to trade off competing objectives in a principled way. The main machine learning techniques we use are from imitation learning and reinforcement learning, and we advance current techniques to tackle problems arising in our settings. We evaluate our algorithm on a variety of applications, including dependency parsing, machine translation, and question answering. We show that our approach achieves a better cost-accuracy trade-off than the batch approach and heuristic-based decision- making approaches. We first propose a general framework for cost-sensitive prediction, where dif- ferent parts of the input come at different costs. We formulate a decision-making process that selects pieces of the input sequentially, and the selection is adaptive to each instance. Our approach is evaluated on both standard classification tasks and a structured prediction task (dependency parsing). We show that it achieves similar prediction quality to methods that use all input, while inducing a much smaller cost. Next, we extend the framework to problems where the input is revealed incremen- tally in a fixed order. We study two applications: simultaneous machine translation and quiz bowl (incremental text classification). We discuss challenges in this set- ting and show that adding domain knowledge eases the decision-making problem. A central theme throughout the chapters is an MDP formulation of a challenging problem with sequential input/output and trade-off decisions, accompanied by a learning algorithm that solves the MDP.

Three Voices in the Wilderness: Foote, Bloch, and Korngold in the Early Twentieth-Century America

Barbara Hanning points out in her book Concise History of Western Music, that "Twentieth-century American music was in large measure an extension of European music" (Hanning 1998, 515). My dissertation/perforrnance project features cello works written by three contemporary composers who lived in America but were connected to the European heritage in different ways; each contributed significantly to the development of American classical concert life, music education, and even popular culture. Programs of my performances are intended to illustrate their unique compositional styles. The first recital consists of five cello compositions of Massachusetts-born Arthur Foote (1853 - 1937): Drei Stucke fur Pianoforte und Violoncello, Op. 1; Scherzo, Op.22; Romanza, Op.33; Aubade, Op.77; and Sonata for Violoncello and Piano, Op.78. Foote was influenced by the German-trained John Knowles Paine at Harvard University; he composed music famous for its extensive chromaticism in both harmony and melodic line, and for clearly-defined formal structure. The second recital explores the music of Swiss-American composer Ernest Bloch (1880-1959): a short Meditation Hebraique, a Suite No. I for Violoncello Solo and the famous rhapsody Schelomo. Born in Geneva, Switzerland, and settling in the United States in 1916, Bloch is a composer deeply influenced by the European late-Romantic tradition and is also well-known for employing "Hebraic" elements into his works. The final performance comprises two other of Bloch's cello works and one cello concerto by the Austrian-American composer, Erich Wolfgang Korngold (1897- 1957). Bloch's Voice in the Wilderness is a symphonic poem for orchestra and cello (accompanied by piano in this performance), consisting of six movements performed without pause. His Suite No.3 for Cello Solo is shorter and has a simpler style than the first Suite. Korngold was recognized as a child prodigy in his native Austria. After a Nazi-induced exile, he immigrated to America and became a film music composer in Hollywood. The Cello Concerto was used in the movie "Deception" (1 946), for which Korngold provided the film score. The impassioned harmonic language and lavish melodic lines inherited from the high-romanticism make this work one of comparative discordant beauty among other compositions of his time.

IMPROMPTU: FROM PUBLISHER'S IMPULSE TO AN ESTABLISHED SMALL­ SCALE GENRE IN PIANO LITERATURE

The word 'impromptu' began to appear in music literature in the early 19th century, specifically as title for a relatively short composition written for solo piano. The first impromptus appear to have been named so by the publishers. However, the composers themselves soon embraced the title to indicate, for the most part, fairly short character pieces. Impromptus do not follow any specific structural pattern, although many are cast in ternary form. The formal design ranges from strict compound ternary in the early impromptus to through-composed and variation forms. The peak of impromptu's popularity undoubtedly came during the middle and late19th century. However, they are still being composed today, albeit much less frequently. Although there have been many variants of impromptus in relation to formal design and harmonic language over the years, the essence of impromptu remains the same: it is still a short character piece with a general feeling of spontaneity. Overall, impromptus may be categorized into several different groups: some appear as part of a larger cycle, such as Dvorak's G minor Impromptu from his Piano Pieces, B. 110; many others use an element of an additional genre that enhances the character ofthe impromptu, such as Liszt's Valse-Impromptu and Antonio Bibalo's Tango Impromptu; yet another group consists of works based on opera themes, such as Liszt's Impromptu Brillant sur des themes de Rossini et Spontini and Czerny's Impromptus et variations sur Oberon, Op. 134. My recording project includes well-known impromptus, such as Schubert's Op. 142 and the four by Chopin, as well as lesser known works that have not been performed or recorded often. There are four impromptus that have been recorded here for the first time, including those written by Leopold Godowsky, Antonio Bibalo, Altin Volaj, and Nikolay Mazhara. I personally requested the two last named composers to contribute impromptus to this project. My selection represents works by twenty composers and reflects the different types of impromptus that have been encountered through almost three hundred years of the genre's existence, from approximately 1817 (VoriSek) to 2008 (Volaj and Mazhara).