14 research outputs found
Zorro: Valid, sparse, and stable explanations in graph neural networks
No full textWith the ever-increasing popularity and applications of graph neural networks, several proposals have been made to explain and understand the decisions of a graph neural network. Explanations for graph neural networks differ in principle from other input settings. It is important to attribute the decision to input features and other related instances connected by the graph structure. We find that the previous explanation generation approaches that maximize the mutual information between the label distribution produced by the model and the explanation to be restrictive. Specifically, existing approaches do not enforce explanations to be valid, sparse, or robust to input perturbations. In this paper, we lay down some of the fundamental principles that an explanation method for graph neural networks should follow and introduce a metric RDT-Fidelity as a measure of the explanation's effectiveness. We propose a novel approach Zorro based on the principles from rate-distortion theory that uses a simple combinatorial procedure to optimize for RDT-Fidelity. Extensive experiments on real and synthetic datasets reveal that Zorro produces sparser, stable, and more faithful explanations than existing graph neural network explanation approaches.Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.Multimedia ComputingWeb Information System
Recommended from our members
Narratives of the 1658 War of Succession for the Mughal Throne, 1658-1707
No full textThis dissertation studies certain Hindi and Persian narratives of the War of Succession (1658) to succeed Shah Jahan (r.1627-1658). All the narratives under study were written during the reign of Aurangzeb (r.1658-1707), the successor of Shah Jahan. The study evaluates the significance of the War as a landmark moment in the social history of India, especially in the formation and inter-relationships between religious communities. The dissertation demarcates the larger epistemological and ontological canvas on which these communities took shape and interacted with each other. The research outlines the ways and the contexts in which terms such as Hindu, momin, musalman, Islam, din and Rajput were deployed in literary texts. It asks whether Hinduism and Islam were two disparate traditions, as previous histories of the War and Mughal India had contended. The dissertation argues that social communities of Hindus and Muslims were mutually and similarly circumscribed within an Islamic worldview and concept of din. Hindu traditions could portray Muslims in concepts and terms borrowed from Indian epics but within an over-arching Islamic cultural dispensation. The War was not a moment of evolution between two independent Hindu and Muslim traditions. Rather, the War was a moment that saw the evolution, even if it be of an antagonistic kind, of Hindu and Muslim traditions within a larger Islamic framework. Besides the above primary focus, the dissertation provides the reader with important insights and overviews regarding allied subjects such as the literary histories of Persian and of Hindi/Urdu, especially in the Dingal and Khari Boli dialects, the political culture of Hindu India, Rajput political culture, Mughal political culture, patronage networks in Mughal India, notions of soldierly duty in seventeenth century India, language and status, preaching in the Hindu and Islamic traditions, the sociological ideas of acculturation and Islamisation, and twentieth century history-writing.Release 24-Aug-2030Originally embargoed through 11-Aug-2017; updated embargo through 24-Aug-2021 per author request, 10-Aug-2017, Kimberly; updated embargo through 24-Aug-2030 per author request, 17-Aug-2021, Kimberl
CrypTFlow2: Practical 2-Party Secure Inference
No full textWe present CrypTFlow2, a cryptographic framework for secure inference over realistic Deep Neural Networks (DNNs) using
secure 2-party computation. CrypTFlow2 protocols are both correct -- i.e., their outputs are bitwise equivalent to the cleartext execution -- and efficient -- they outperform the state-of-the-art protocols in both latency and scale. At the core of CrypTFlow2, we have new 2PC protocols for secure comparison and division, designed carefully to balance round and communication complexity for secure inference tasks. Using CrypTFlow2, we present the first secure inference over ImageNet-scale DNNs like ResNet50 and DenseNet121. These DNNs are at least an order of magnitude larger than those considered in the prior
work of 2-party DNN inference. Even on the benchmarks considered by prior work, CrypTFlow2 requires an order of magnitude less communication and 20x-30x less time than the state-of-the-art
SIRNN: A Math Library for Secure RNN Inference
No full textComplex machine learning (ML) inference algorithms like recurrent neural networks (RNNs) use standard functions from math libraries like exponentiation, sigmoid, tanh, and reciprocal of square root.
Although prior work on secure 2-party inference provides specialized protocols for convolutional neural networks (CNNs), existing secure implementations of these math operators rely on generic 2-party computation (2PC) protocols that suffer from high communication. We provide new specialized 2PC protocols for math functions that crucially rely on lookup-tables and mixed-bitwidths to address this performance overhead; our protocols for math functions communicate up to 423x less data than prior work. Some of the mixed bitwidth operations used by our math implementations are (zero and signed) extensions, different forms of truncations, multiplication of operands of mixed-bitwidths, and digit decomposition (a generalization of bit decomposition to larger digits). For each of these primitive operations, we construct specialized 2PC protocols that are more communication efficient than generic 2PC, and can be of independent interest.
Furthermore, our math implementations are numerically precise, which ensures that the secure implementations preserve model accuracy of cleartext. We build on top of our novel protocols to build SIRNN, a library for end-to-end secure 2-party DNN inference, that provides the first secure implementations of an RNN operating on time series sensor data, an RNN operating on speech data, and a state-of-the-art ML architecture that combines CNNs and RNNs for identifying all heads present in images. Our evaluation shows that SIRNN achieves up to three orders of magnitude of performance improvement when compared to inference of these models using an existing state-of-the-art 2PC framework
ELSA: Secure Aggregation for Federated Learning with Malicious Actors
No full textFederated learning (FL) is an increasingly popular
approach for machine learning (ML) in cases where the train-
ing dataset is highly distributed. Clients perform local training
on their datasets and the updates are then aggregated into
the global model. Existing protocols for aggregation are either
inefficient, or don’t consider the case of malicious actors in the
system. This is a major barrier in making FL an ideal solution
for privacy-sensitive ML applications. We present ELSA, a
secure aggregation protocol for FL, which breaks this barrier -
it is efficient and addresses the existence of malicious actors at
the core of its design. Similar to prior work on Prio and Prio+,
ELSA provides a novel secure aggregation protocol built out of
distributed trust across two servers that keeps individual client
updates private as long as one server is honest, defends against
malicious clients and is efficient end-to-end. Compared to prior
works, the distinguishing theme in ELSA is that instead of the
servers generating cryptographic correlations interactively, the
clients act as untrusted dealers of these correlations without
compromising the protocol’s security. This leads to a much
faster protocol while also achieving stronger security at that ef-
ficiency compared to prior work. We introduce new techniques
that retain privacy even when a server is malicious at a small
added cost of 7-25% in runtime with negligible increase in
communication over the case of semi-honest server. Our work
improves end-to-end runtime over prior work with similar
security guarantees by big margins - single-aggregator RoFL
by up to 305x (for the models we consider), and distributed
trust Prio by up to 8
Private Analytics via Streaming, Sketching, and Silently Verifiable Proofs
No full textWe present Whisper, a system for privacy-preserving collection of aggregate statistics. Like prior systems, a Whisper deployment consists of a small set of non-colluding servers; these servers compute aggregate statistics over data from a large number of users without learning the data of any individual user. Whisper’s main contribution is that its server- to-server communication cost and its server-side storage costs scale sublinearly with the total number of users. In particular, prior systems required the servers to exchange a few bits of information to verify the well-formedness of each client submission. In contrast, Whisper uses silently verifiable proofs, a new type of proof system on secret-shared data that allows the servers to verify an arbitrarily large batch of proofs by exchanging a single 128-bit string. This improvement comes with increased client-to-server communication, which, in cloud computing, is typically cheaper (or even free) than the cost of egress for server-to-server communication. To reduce server storage, Whisper approximates certain statistics using small-space sketching data structures. Applying randomized sketches in an environment with adversarial clients requires a careful and novel security analysis. In a deployment with two servers and 100,000 clients of which 1% are malicious, Whisper can improve server-to-server communication for vector sum by three orders of magnitude while each client’s communication increases by only 10%
Waldo: A Private Time-Series Database from Function Secret Sharing
No full textApplications today rely on cloud databases for storing and querying time-series data. While outsourcing storage is convenient, this data is often sensitive, making data breaches a serious concern. We present Waldo, a time-series database with rich functionality and strong security guarantees: Waldo supports multi-predicate filtering, protects data contents as well as query filter values and search access patterns, and provides malicious security in the 3-party honest-majority setting. In contrast, prior systems such as Timecrypt and Zeph have limited functionality and security: (1) these systems can only filter on time, and (2) they reveal the queried time interval to the server. Oblivious RAM (ORAM) and generic multiparty computation (MPC) are natural choices for eliminating leakage from prior work, but both of these are prohibitively expensive in our setting due to the number of roundtrips and bandwidth overhead, respectively. To minimize both, Waldo builds on top of function secret sharing, enabling Waldo to evaluate predicates without client interaction. We develop new techniques for applying function secret sharing to the encrypted database setting where there are malicious servers, secret inputs, and chained predicates. With 32-core machines, Waldo runs a query with 8 range predicates over records in 3.03s, compared to 12.88s for an MPC baseline and 16.56s for an ORAM baseline. Compared to Waldo, the MPC baseline uses 9 − 82× more bandwidth between servers (for different numbers of records), while the ORAM baseline uses 20 − 152× more bandwidth between the client and server(s) (for different numbers of predicates)
Private Graph Extraction via Feature Explanations
No full textPrivacy and interpretability are two important ingredients for achieving trustworthy machine learning. We study the interplay of these two aspects in graph machine learning through graph reconstruction attacks. The goal of the adversary here is to reconstruct the graph structure of the training data given access to model explanations. Based on the different kinds of auxiliary information available to the adversary, we propose several graph reconstruction attacks. We show that additional knowledge of post-hoc feature explanations substantially increases the success rate of these attacks. Further, we investigate in detail the differences between attack performance with respect to three different classes of explanation methods for graph neural networks: gradient-based, perturbationbased, and surrogate model-based methods. While gradient-based explanations reveal the most in terms of the graph structure, we find that these explanations do not always score high in utility. For the other two classes of explanations, privacy leakage increases with an increase in explanation utility. Finally, we propose a defense based on a randomized response mechanism for releasing the explanations, which substantially reduces the attack success rate. Our code is available at https://github.com/iyempissy/graphstealing- attacks-with-explanation.Multimedia Computin
CrypTFlow: Secure TensorFlow Inference
No full textWe present CrypTFlow, a first of its kind system that converts TensorFlow inference code into Secure Multi-party Computation (MPC) protocols at the push of a button. To do this, we build three components. Our first component, Athos, is an end-to-end compiler from TensorFlow to a variety of semi-honest MPC protocols. The second component, Porthos, is an improved semi-honest 3-party protocol that provides significant speedups for TensorFlow like applications. Finally, to provide malicious
secure MPC protocols, our third component, Aramis, is a novel technique that uses hardware with integrity guarantees to convert any semi-honest MPC protocol into an MPC protocol that provides malicious security. The malicious security of the
protocols output by Aramis relies on integrity of the hardware and semi-honest security of MPC. Moreover, our system matches the inference accuracy of plaintext TensorFlow.
We experimentally demonstrate the power of our system by showing the secure inference of real-world neural networks such as ResNet50 and DenseNet121 over the ImageNet dataset with running times of about 30 seconds for semi-honest security and under two minutes for malicious security. Prior work in the area of secure inference has been limited to semi-honest security of small networks over tiny datasets such as MNIST or CIFAR. Even on MNIST/CIFAR, CrypTFlow outperforms prior work
