Pattern matching (PM) is the technique of identifying occurrences of a short pattern in a long text, where both, the pattern and text, are a string of characters. Since several applications demand the privacy of the pattern and the text in the process of identifying matches, designing secure solutions for PM is gaining popularity. Moreover, given the variety of applications that consider PM, we design secure solutions for three popular variants of PM---exact, wildcard and approximate. Our solutions are designed using the techniques of secure multiparty computation (MPC) in the two-party semi-honest setting. All of our solutions attain a fast response time, which is the time taken from submission of the input to obtaining the output, and forms a crucial parameter when analysing the performance of any protocol. Moreover, our protocols also provide an improved online communication complexity in comparison to prior works. Since determining if two secret-shared values are equal forms a crucial component in all the PM variants, we design a novel constant-round equality protocol in the two-party semi-honest setting. Our equality protocol outperforms all the prior works in the considered setting and can also be of independent interest. We implement all our protocols on the MPC framework of MOTION2NX to showcase the practicality of the designed solutions. In comparison to prior works that consider DNA matching (over 2-bit characters), our pattern matching protocols see improvements of up to 2 orders of magnitude in response time. Our equality protocol, too, excels over all existing constructions. To analyse the performance of our equality protocol in comparison to prior work, we benchmark it for varying input sizes. We observe that with increasing input sizes, the improvement in response time of our protocol keeps on increasing, with improvements of up to 9.7x for 256-bit inputs.

Graphs are a fundamental tool for modelling data in diverse real-world applications such as communication networks, traffic systems, and social networks. However, graph data is often distributed across multiple data owners and contains sensitive information, posing significant privacy concerns that impede collaborative analysis. This research aims to overcome these challenges by developing privacy-preserving solutions for graph analysis using the technique of secure multiparty computation (MPC). We review existing MPC-based approaches for privacy-preserving graph analysis, identifying their limitations in efficiency, scalability and adaptability. Furthermore, we present our results in enhancing privacy-preserving graph analysis and highlight the remaining challenges. We discuss potential strategies to overcome these challenges, including designing efficient primitives, leveraging different computational settings, and incorporating hardware accelerations to improve performance. Through these advancements, our research aims to make secure graph analysis both practical and widely applicable, ensuring privacy while enabling valuable insights from distributed graph data.

Privacy-preserving graph analysis allows performing computations on graphs that store sensitive information while ensuring all the information about the topology of the graph, as well as data associated with the nodes and edges, remains hidden. The current work addresses this problem by designing a highly scalable framework, Graphiti, that allows securely realising any graph algorithm. Graphiti relies on the technique of secure multiparty computation (MPC) to design a generic framework that improves over the state-of-the-art framework of GraphSC by Araki et al. (CCS'21). The key technical contribution is that Graphiti has round complexity independent of the graph size, which in turn allows attaining the desired scalability. Specifically, this is achieved by (i) decoupling the Scatter primitive of GraphSC into separate operations of Propagate and ApplyE, (ii) designing a novel constant-round approach to realise Propagate, as well as (iii) designing a novel constant-round approach to realise the Gather primitive of GraphSC by leveraging the linearity of the aggregation operation. We benchmark the performance of Graphiti for the application of contact tracing via BFS for 10 hops and observe that it takes less than 2 minutes when computing over a graph of size 10^7. Concretely it improves over the state-of-the-art up to a factor of 1034× in online run time. Similar to GraphSC by Araki et al., since Graphiti relies on a secure protocol for shuffle, we additionally design a shuffle protocol secure against a semi-honest adversary in the 2-party with a helper setting. Given the versatility of shuffle protocol, the designed solution is of independent interest. Hence, we also benchmark the performance of the designed shuffle where we observe improvements of up to 1.83× in online run time when considering an input vector of size 10^7, in comparison to the state-of-the-art in the considered setting.

Consider the problem of securely identifying$\tau$-heavy hitters, where given a set of client inputs, the goal is to identify those inputs which are held by at least$\tau$clients in a privacy-preserving manner. Towards this, we design a novel system$\mathsf {Vogue}$, whose key highlight in comparison to prior works, is that it ensures complete privacy and does not leak any information other than the heavy hitters. In doing so,$\mathsf {Vogue}$aims to achieve as efficient a solution as possible. To showcase these efficiency improvements, we benchmark our solution and observe that it requires around 14 minutes to compute the heavy hitters for$\tau$= 100 on 256-bit inputs when considering 400 K clients. This is in contrast to the state of the art solution that requires over an hour for the same. In addition to the static input setting described above,$\mathsf {Vogue}$also accounts for streaming inputs and provides a protocol that outperforms the state-of-the-art therein. The efficiency improvements witnessed while computing heavy hitters in both, the static and streaming input settings, are attributed to our new secure stable compaction protocol, whose round complexity is independent of the size of the input array to be compacted.

The rising issues of harassment, exploitation, corruption and other forms of abuse have led victims to seek comfort by acting in unison against common perpetrators. This is corroborated by the widespread #MeToo movement, which was explicitly against sexual harassment. Installation of escrow systems has allowed victims to report such incidents. The escrows are responsible for identifying the perpetrator and taking the necessary action to bring justice to all its victims. However, users hesitate to participate in these systems due to the fear of such sensitive reports being leaked to perpetrators, who may further misuse them. Thus, to increase trust in the system, cryptographic solutions are being designed to realize web-based secure allegation escrow (SAE) systems.

Identifying a cluster around a seed node in a graph, termed local clustering, finds use in several applications, including fraud detection, targeted advertising, community detection, etc. However, performing local clustering is challenging when the graph is distributed among multiple data owners, which is further aggravated by the privacy concerns that arise in disclosing their view of the graph. This necessitates designing solutions for privacy-preserving local clustering and is addressed for the first time in the literature. We propose using the technique of secure multiparty computation (MPC) to achieve the same. Our local clustering algorithm is based on the heat kernel PageRank (HKPR) metric, which produces the best-known cluster quality. En route to our final solution, we have two important steps: (i) designing data-oblivious equivalent of the state-of-the-art algorithms for computing local clustering and HKPR values, and (ii) compiling the data-oblivious algorithms into its secure realisation via an MPC framework that supports operations over fixed-point arithmetic representation such as multiplication and division. Keeping efficiency in mind for large graphs, we choose the best-known honest-majority 3-party framework of SWIFT (Koti et al., USENIX'21) and enhance it with some of the necessary yet missing primitives, before using it for our purpose. We benchmark the performance of our secure protocols, and the reported run time showcases the practicality of the same. Further, we perform extensive experiments to evaluate the accuracy loss of our protocols. Compared to their cleartext counterparts, we observe that the results are comparable and thus showcase the practicality of the designed protocols.

Secure shuffle is an important primitive that finds use in several applications such as secure electronic voting, oblivious RAMs, secure sorting, to name a few. For time-sensitive shuffle-based applications that demand a fast response time, it is essential to design a fast and efficient shuffle protocol. In this work, we design secure and fast shuffle protocols relying on the techniques of secure multiparty computation. We make several design choices that aid in achieving highly efficient protocols. Specifically, we consider malicious 3-party computation setting with an honest majority and design robust ring-based protocols. Our shuffle protocols provide a fast online (i.e., input-dependent) phase compared to the state-of-the-art for the considered setting. To showcase the efficiency improvements brought in by our shuffle protocols, we consider two distinct applications of anonymous broadcast and secure graph computation via the GraphSC paradigm. In both cases, multiple shuffle invocations are required. Hence, going beyond standalone shuffle invocation, we identify two distinct scenarios of multiple invocations and provide customised protocols for the same. Further, we showcase that our customized protocols not only provide a fast response time, but also provide improved overall run time for multiple shuffle invocations. With respect to the applications, we not only improve in terms of efficiency, but also work towards providing improved security guarantees, thereby outperforming the respective state-of-the-art works. We benchmark our shuffle protocols and the considered applications to analyze the efficiency improvements with respect to various parameters.

Consider a set of N clients, each of which holds a private input string. An input string that is held by at least τ clients is defined as a τ-heavy hitter. In various application scenarios, data-aggregation servers are interested in learning τ-heavy hitters. To ensure that the servers do not learn anything about client input in the process, the problem of identifying heavy hitters privately is gaining popularity. Towards this, we design a novel system called Vogue, which provides improved efficiency as well as security guarantees over the state-of-the-art system of Poplar. Concretely, Vogue provides up to 27x efficiency improvement over Poplar when considering 400,000 clients who hold 256-bit input strings. Moreover, Vogue overcomes intermediate information leakages present in Poplar and guarantees full security in the presence of a malicious adversary. In the process of designing Vogue, we also design secure and efficient protocols for stable compaction and shuffle, each of which improves over its respective state-of-the-art.

Secure multiparty computation (MPC) is increasingly being used to address privacy issues in various applications. The recent work of Alon et al. (CRYPTO'20) identified the shortcomings of traditional MPC and defined a Friends-and-Foes (FaF) security notion to address the same. We showcase the need for FaF security in real-world applications such as dark pools. This subsequently necessitates designing concretely efficient FaF-secure protocols. Towards this, keeping efficiency at the center stage, we design ring-based FaF-secure MPC protocols in the small-party honest-majority setting. Specifically, we provide (1,1)-FaF secure 5 party computation protocols (5PC) that consider one malicious and one semi-honest corruption and constitutes the optimal setting for attaining honest-majority. At the heart of it lies the multiplication protocol that requires a single round of communication with 8 ring elements (amortized). To facilitate having FaF-secure variants for several applications, we design a variety of building blocks optimized for our FaF setting. The practicality of the designed (1,1)-FaF secure 5PC framework is showcased by benchmarking dark pools. In the process, we also improve the efficiency and security of the dark pool protocols over the existing traditionally secure ones. This improvement is witnessed as a gain of up to 62x in throughput compared to the existing ones. Finally, to demonstrate the versatility of our framework, we also benchmark popular deep neural networks.