Seminars

View all Seminars  |  Download ICal for this event

Making Secure Computation Scalable for Data-Intensive Analytics

Series: Ph.D. Colloquium

Speaker: Bhavish Raj Gopal, Ph.D (Engg.) student, Dept. of CSA

Date/Time: Oct 22 15:30:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Faculty Advisor: Prof. Arpita Patra

Abstract:
Data-intensive analytics extracts useful information from large collections of records, sequences, and relationships. In many applications, these data are sensitive and distributed across mutually distrustful owners. Secure multiparty computation (MPC) enables joint analysis while protecting private inputs beyond the information disclosed by the prescribed outputs. However, its communication, interaction, and computational overheads can limit its scalability. This thesis addresses these challenges through two complementary approaches: designing efficient, secure primitives for operations central to analytical tasks and designing algorithms tailored to the application and computational setting. We apply these approaches to analytics over sequences, collections and graphs. We next elaborate on the specific analytics considered in the thesis and the contributions therein.

Sequences and collections: We first consider identifying patterns and frequently occurring values in private data.

Secure pattern matching. Pattern matching identifies occurrences of a pattern within a longer sequence. For example, a research organisation may wish to locate a proprietary genetic marker within genomic data held by a hospital, while protecting both the marker and the patient data. Towards this, we present �??MatchQuest�?�, a system for secure exact, wildcard, and approximate pattern matching. We design an efficient equality-testing primitive that reduces comparisons of long private values to zero tests on substantially shorter values, and combine it with specialised matching algorithms to reduce online communication and interaction. In the evaluated settings, our exact- and approximate-matching protocols improve response time by approximately 100x and 10x, respectively, over the compared prior work.

Private heavy-hitter computation. Heavy-hitter computation identifies values occurring at least a specified number of times across client inputs. A browser vendor, for example, may wish to discover popular homepages without collecting individual users browsing preferences. Towards this, we present �??Vogue�?�, which replaces a central data aggregator with computing servers that jointly identify heavy hitters over static and streaming inputs. We design an efficient, secure, stable compaction primitive and use it to avoid intermediate disclosures in static computation and reduce sequential interaction in streaming updates. For 400,000 static inputs of 256 bits and threshold �?=900, Vogue requires approximately 14 minutes of online time, compared with approximately 86 minutes for prior work. Further, our streaming construction achieves response-time improvements of up to 3.5x over the compared protocol.
Graphs: We next consider useful analytics over private relationships and their associated data. For example, banks may jointly analyse transaction networks to propagate risk or identify suspicious connections. Such analysis must protect both transaction attributes and graph topology, since the existence of a relationship can itself reveal confidential information. Our contributions address efficient message passing, direct collaboration, dynamic updates, and malicious behaviour.

Scalable outsourced graph computation. We first study graph analytics in the outsourced computation setting, where data owners delegate storage and computation to a set of servers by secret-sharing their graphs among them. This setting allows owners with limited computational resources to obtain analytical results without disclosing their private graphs to any individual server. We present �??Graphiti�?�, which achieves round complexity independent of graph size and communication linear in graph size, after a one-time initialisation. In our evaluation, ten-hop contact tracing on a graph containing 10^7 vertices and edges takes under two minutes of online time. Across the evaluated configurations, Graphiti achieves running-time improvements of up to 106x over prior work.

Secure graph processing in direct computation. We then consider the direct computation setting, where data owners themselves execute MPC to analyse their combined graph. This setting enables organisations with computational resources to collaborate without relying on external computing servers. However, applying existing outsourced frameworks in this setting incurs expensive initialisation and interaction that grows with the number of participants. We present �??GraSP�?�, which exploits each owners knowledge of its local graph through a Decompose--Compute--Combine paradigm. Our design eliminates secure sorting from initialisation and achieves online round complexity independent of graph size and the number of parties for initialisation and subsequent computations, while tolerating semi-honest collusion among all but one participant. For ten iterations of PageRank, including initialisation, GraSP achieves running-time improvements of up to 88.24x and communication reductions of up to 51.95x over the instantiation of Graphiti in the direct computation setting.

Dynamic graph processing. We next address outsourced analytics over evolving graphs, where vertices, edges, and their associated data change over time. Supporting repeated analysis requires maintaining the private graph representation efficiently, without requiring clients to resubmit their entire graphs after each update. We present �??Grapharo�?�, which uses client-side structural knowledge to eliminate secure sorting from initialisation and support vertex and edge insertions, deletions, and data modifications. Client communication is proportional to the number of updated records, while the servers maintain the representation required for subsequent computation. For a graph with 100,000 vertices and one million edges, Grapharo reduces the online time for initialisation and ten iterations of PageRank from 226.97 seconds with Graphiti to 40.74 seconds while also supporting efficient updates.

Malicious security. Finally, we consider graph analytics in which participants may deviate arbitrarily from the prescribed protocol, requiring protection against attempts to expose private data or invalidate the computation. We present �??MaGE�?�, which extends the graph-processing designs of Graphiti and GraSP to malicious adversaries in both the outsourced and direct computation settings, with security with abort. For ten iterations of breadth-first search, the outsourced construction incurs approximately 3x overhead compared to Graphiti, while the direct computation setting incurs approximately 3�??4x overhead compared GraSP.
These contributions show how designing secure primitives and analytical algorithms around data structures and the computation model can improve scalability across private sequence analysis, aggregate statistics analysis, and graph processing.