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.

Creating reusable well-structured pdf as a sequence of component object graphic (cog) elements

Portable Document Format (PDF) is a page-oriented, graphically rich format based on PostScript semantics and it is also the format interpreted by the Adobe Acrobat viewers. Although each of the pages in a PDF document is an independent graphic object this property does not necessarily extend to the components (headings, diagrams, paragraphs etc.) within a page. This, in turn, makes the manipulation and extraction of graphic objects on a PDF page into a very difficult and uncertain process. The work described here investigates the advantages of a model wherein PDF pages are created from assemblies of COGs (Component Object Graphics) each with a clearly defined graphic state. The relative positioning of COGs on a PDF page is determined by appropriate "spacer" objects and a traversal of the tree of COGs and spacers determines the rendering order. The enhanced revisability of PDF documents within the COG model is discussed, together with the application of the model in those contexts which require easy revisability coupled with the ability to maintain and amend PDF document structure.

Discontinuous Galerkin Computation of the Maxwell Eigenvalues on Simplicial Meshes

This paper is concerned with the discontinuous Galerkin approximation of the Maxwell eigenproblem. After reviewing the theory developed in [5], we present a set of numerical experiments which both validate the theory, and provide further insight regarding the practical performance of discontinuous Galerkin methods, particularly in the case when non-conforming meshes, characterized by the presence of hanging nodes, are employed.

The MUSE Machine -- an Architecture for Structured Data Flow Computation

Computers employing some degree of data flow organisation are now well established as providing a possible vehicle for concurrent computation. Although data-driven computation frees the architecture from the constraints of the single program counter, processor and global memory, inherent in the classic von Neumann computer, there can still be problems with the unconstrained generation of fresh result tokens if a pure data flow approach is adopted. The advantages of allowing serial processing for those parts of a program which are inherently serial, and of permitting a demand-driven, as well as data-driven, mode of operation are identified and described. The MUSE machine described here is a structured architecture supporting both serial and parallel processing which allows the abstract structure of a program to be mapped onto the machine in a logical way.

Re-viewing history: antiquaries, the graphic arts and Scotland's lost geographies, c.1660-1820

This thesis examines topographical art depicting Scotland’s natural scenery and built environments, architecture, antiquities and signs of modern improvement, made during the period 1660 to 1820. It sets out to demonstrate that topography and topographical art was not exclusively antiquarian in nature, but ranged across various fields of learning and practice. It included the work of artists, geographers, cartographers, travel writers, poets, landscape gardeners, military surveyors, naturalists and historians who were concerned with representing the country’s varied, and often contentious, histories within an increasingly modernising present. The visual images that are considered here were forms of knowledge that found expression in drawings, paintings and engravings, elevations, views and plans. They were made on military surveys and picturesque tours, and were often intended to be included alongside written texts, both published and unpublished, frequently connecting with travels, tours, memoirs, essays and correspondence. It will also be argued that topography was a social practice, involving networks of artists, collectors, publishers and writers, who exchanged information in drawings and letters in a nationwide, and often increasingly commercial enterprise. This thesis will explore some of the strands of such a vast network of picture-making that existed in Scotland, and Britain, between 1660 and 1820, as visual images were circulated, copied, recycled and adapted, and topographical and antiquarian visual culture emerges as a complex, synoptic form of inquiry.

Graphic satire and the rise and fall of the First British Empire: political prints from the Seven Years' War to the Treaty of Paris, c. 1756-1783

This thesis examines the early stages of the transformation of emblematic political prints into political caricature from the beginning of the Seven Years' War (1756) to the Treaty of Paris, which ended the American Revolutionary War (1783). Both contextual and iconographical issues are investigated in relation to the debates occasioned by Britain's imperial project, which marked a period of dramatic expansion during the Seven Years' War, and ended with the loss of the American colonies, consequently framing this thesis as a study of political prints during the rise and fall of the so-called 'First British Empire'. Previous studies of eighteenth-century political prints have largely ignored the complex and lengthy evolutionary process by which the emblematic mode amalgamated with caricatural representation, and have consequently concluded that political prints excluded emblems entirely by the end of the 1770s. However, this study emphasizes the significance of the Wilkite movement for the promotion and preservation of emblems, and investigates how pictorial political argument was perceived and received in eighteenth-century British society, arguing that wider tastes and opinions regarding the utilization of political prints gradually shifted to accept both modes of representation. Moreover, the marketplace, legal status, topicality, and manufacturing methods of political prints are analyzed in terms of understanding the precarious nature of their consumption and those that endeavoured to engage in political printmaking. The evolution, establishment, and subsequent appropriation of pictorial tropes is discussed from the early modern period to the beginning of the so-called Golden Age of caricature, while tracing the adaptation of representational models in American colonial prints that employed emblems already entrenched in British pictorial political debate. Political prints from the two largest print collections, the British Museum and the Lewis Walpole Library at Yale are consulted, along with a number of eighteenth-century newspapers and periodicals, to develop the earlier research by M. Dorothy George, Charles Press, Herbert Atherton, Diana Donald, Amelia Rauser, and Eirwen Nicholson.

Criteria for graphic representation in musical scores: Visual elements in musical scores

A interdisciplinaridade entre a música e as artes visuais tem sido explorado por conceituados teóricos e filósofos, embora não exista muito na área da interpretação visual do grafismo de partituras musicais. Este estudo investiga como os grafismos na notação e símbolos musicais afectam o intérprete na sua transformação em som, com referência especial a partituras contemporâneas, que utilizam notação menos convencional para a criação de uma interpretação por sugestão. Outras relações entre o som e o visual são exploradas, incluindo a sinestesia, a temporalidade e a relação entre obra de arte e público. O objectivo desta dissertação é a de constituir um estudo inovativo sobre partituras musicais contemporâneas, simultaneamente do ponto de vista musical e visual. Finalmente, também vai mais longe, incluindo desenhos da própria autora inspirados e motivados pela música. Estes já não cumprem uma função de notação convencional para o músico, embora existe uma constante possibilidade de uma reinterpretação. ABSTRACT; The inter-disciplinarity between music and visual art has been explored by leading theorists and philosophers, though very little exists in the area of the visual interpretation of graphic musical scores. This study looks at how the graphics of musical notation and symbols affect the performer in transforming them into sound, with particular reference to contemporary scores that use non¬conventional notation to create an interpretation through suggestion. Other sound-visual relationships are explored, including synaesthesia, temporality and the interconnection between work of art and audience or public. This dissertation aims to be an innovative study of contemporary musical scores, from a musical as well as visual perspective. Finally, it takes a step further with drawings of my own, directly inspired and motivated by the music. These no longer fulfil a conventionally notational function for the musician, yet the potential for a re-interpretation is ever-present.

Efficient Secure Computation for Real-world Settings and Security Models

Secure computation involves multiple parties computing a common function while keeping their inputs private, and is a growing field of cryptography due to its potential for maintaining privacy guarantees in real-world applications. However, current secure computation protocols are not yet efficient enough to be used in practice. We argue that this is due to much of the research effort being focused on generality rather than specificity. Namely, current research tends to focus on constructing and improving protocols for the strongest notions of security or for an arbitrary number of parties. However, in real-world deployments, these security notions are often too strong, or the number of parties running a protocol would be smaller. In this thesis we make several steps towards bridging the efficiency gap of secure computation by focusing on constructing efficient protocols for specific real-world settings and security models. In particular, we make the following four contributions: - We show an efficient (when amortized over multiple runs) maliciously secure two-party secure computation (2PC) protocol in the multiple-execution setting, where the same function is computed multiple times by the same pair of parties. - We improve the efficiency of 2PC protocols in the publicly verifiable covert security model, where a party can cheat with some probability but if it gets caught then the honest party obtains a certificate proving that the given party cheated. - We show how to optimize existing 2PC protocols when the function to be computed includes predicate checks on its inputs. - We demonstrate an efficient maliciously secure protocol in the three-party setting.

Processing of laser Doppler flowmetry signals from healthy subjects and patients with varicose veins: information categorization approach based on intrinsic mode functions and entropy computation

International audience

A MATLAB program for the computation of the confluent hypergeometric function Φ2

We here present a sample MATLAB program for the numerical evaluation of the confluent hypergeometric function Φ2. This program is based on the calculation of the inverse Laplace transform using the algorithm suggested by Simon and Alouini in their reference textbook [1].

Remembering the Vietnam War in Graphic Narratives

This project discusses the relation between memory and graphic novels, mainly focusing on the ongoing narration of the Vietnam War. It adopts a diachronic and philological approach to reconstruct the history of the medium and its entanglement with war, be it as instrument of propaganda or as a memory project. It follows the development of the medium in Hearst and Pulitzer newspapers, analyzing how mass culture helped consolidating a persuasive ‘war mentality’. It reflects on the role that comics played in the creation of the myth of the ‘good war’. It also shows how the ‘god war’ pattern became increasingly contested during the Vietnam War, following the questioning of the traditional “American values” promoted by the counterculture of the time. Finally, it explores how the narration (and memory) of the Vietnam War has changed after September 11, 2001, and it describes the emergence of graphic narratives written by diasporic Vietnamese graphic artists.

Towards a logical foundation of randomized computation

This dissertation investigates the relations between logic and TCS in the probabilistic setting. It is motivated by two main considerations. On the one hand, since their appearance in the 1960s-1970s, probabilistic models have become increasingly pervasive in several fast-growing areas of CS. On the other, the study and development of (deterministic) computational models has considerably benefitted from the mutual interchanges between logic and CS. Nevertheless, probabilistic computation was only marginally touched by such fruitful interactions. The goal of this thesis is precisely to (start) bring(ing) this gap, by developing logical systems corresponding to specific aspects of randomized computation and, therefore, by generalizing standard achievements to the probabilistic realm. To do so, our key ingredient is the introduction of new, measure-sensitive quantifiers associated with quantitative interpretations. The dissertation is tripartite. In the first part, we focus on the relation between logic and counting complexity classes. We show that, due to our classical counting propositional logic, it is possible to generalize to counting classes, the standard results by Cook and Meyer and Stockmeyer linking propositional logic and the polynomial hierarchy. Indeed, we show that the validity problem for counting-quantified formulae captures the corresponding level in Wagner's hierarchy. In the second part, we consider programming language theory. Type systems for randomized \lambda-calculi, also guaranteeing various forms of termination properties, were introduced in the last decades, but these are not "logically oriented" and no Curry-Howard correspondence is known for them. Following intuitions coming from counting logics, we define the first probabilistic version of the correspondence. Finally, we consider the relationship between arithmetic and computation. We present a quantitative extension of the language of arithmetic able to formalize basic results from probability theory. This language is also our starting point to define randomized bounded theories and, so, to generalize canonical results by Buss.

Bounded Arithmetic and Randomized Computation

In this work, we develop a randomized bounded arithmetic for probabilistic computation, following the approach adopted by Buss for non-randomized computation. This work relies on a notion of representability inspired by of Buss' one, but depending on a non-standard quantitative and measurable semantic. Then, we establish that the representable functions are exactly the ones in PPT. Finally, we extend the language of our arithmetic with a measure quantifier, which is true if and only if the quantified formula's semantic has measure greater than a given threshold. This allows us to define purely logical characterizations of standard probabilistic complexity classes such as BPP, RP, co-RP and ZPP.

SUV: proposta di traduzione e analisi di una Graphic Novel russa

Il fumetto, spesso definito come “arte sequenziale” o “letteratura disegnata”, ha appassionato e appassiona tuttora i lettori di tutto il mondo, a partire dai comics statunitensi fino ad arrivare ai manga giapponesi. Ma quali sono invece le principali tendenze russe nella fumettistica? Il presente elaborato, suddiviso in tre capitoli, parte da un excursus sul fumetto e i suoi albori negli Stati Uniti e in Italia. Proseguendo si propone un approfondimento del panorama fumettistico russo, con un particolare riguardo per “ŠUV” dell’artista Olga Lavrenteva, una Graphic Novel investigativa ambientata negli anni ’90 e pubblicata nel 2016 dalla casa editrice Bumkniga. L’obiettivo principale dell’elaborato è quello di definire a livello teorico i principali aspetti della traduzione dei fumetti, sia da un punto di vista grafico sia linguistico. Inoltre ambisce a identificare a livello pratico attraverso un’analisi metodologica le difficoltà testuali e grafiche e le strategie adottate nella stesura della traduzione di “ŠUV”. In particolar modo dall’analisi viene confermata una peculiarità imprescindibile del fumetto, che non può essere trascurata nel corso della traduzione: l’indissolubilità della componente verbale e della componente visiva. Nell’appendice si può trovare la traduzione integrale della Graphic Novel e l’estratto dello scambio di messaggi con la fumettista Olga Lavrenteva, contenente domande e risposte relative a “ŠUV”.

Biased Random-key Genetic Algorithms For The Winner Determination Problem In Combinatorial Auctions.

Abstract In this paper, we address the problem of picking a subset of bids in a general combinatorial auction so as to maximize the overall profit using the first-price model. This winner determination problem assumes that a single bidding round is held to determine both the winners and prices to be paid. We introduce six variants of biased random-key genetic algorithms for this problem. Three of them use a novel initialization technique that makes use of solutions of intermediate linear programming relaxations of an exact mixed integer-linear programming model as initial chromosomes of the population. An experimental evaluation compares the effectiveness of the proposed algorithms with the standard mixed linear integer programming formulation, a specialized exact algorithm, and the best-performing heuristics proposed for this problem. The proposed algorithms are competitive and offer strong results, mainly for large-scale auctions.