publications

2024

1. Information-theoretic Multi-server Private Information Retrieval with Client Preprocessing

   Jaspal Singh, Yu Wei, and Vassilis Zikas

   In Theory of Cryptography Conferenc (TCC), 2024

   Abs PDF

   A private information retrieval (PIR) protocol allows a client to fetch any entry from single or multiple servers who hold a public database (of size n) while ensuring no server learns any information about the client’s query. Initial works on PIR were focused on reducing the communication complexity of PIR schemes. However, standard PIR protocols are often impractical to use in applications involving large databases, due to its inherent large server-side computation complexity, that’s at least linear in the database size. Hence, a line of research has focused on considering alternative PIR models that can achieve improved server complexity. The model of private information retrieval with client prepossessing has received a lot of interest beginning with the work due to Corrigan-Gibbs and Kogan (Eurocrypt 2020). In this model, the client interacts with two servers in an offline phase and it stores a local state, which it uses in the online phase to perform PIR queries. Constructions in this model achieve online client/server computation and bandwidth that’s sublinear in the database size, at the cost of a one-time expensive offline phase. Till date all known constructions in this model are based on symmetric key primitives or on stronger public key assumptions like Decisional Diffie-Hellman (DDH) and Learning with Error (LWE). This work initiates the study of unconditional PIR with client prepossessing - where we avoid using any cryptographic assumptions. We present a new PIR protocol for 2t servers (where t ∈[2,\log_2n/2]) with threshold 1, where client and server online computation is \OO(\sqrtn)\footnotethe \OO(.) notation hides \poly\log factors - matching the computation costs of other works based on cryptographic assumptions. The client storage and online communication complexity are \OO(n^0.5+1/2t) and \OO(n^1/2) respectively. Compared to previous works our PIR with client preprocessing protocol also has a very concretely efficient client/server online computation phase - which is dominated by xor operations, compared to cryptographic operations that are orders of magnitude slower. As a building block for our construction, we introduce a new information-theoretic primitive called \textitprivately multi-puncturable random set (\pprs), which might be of independent interest. This new primitive can be viewed as a generalization of privately puncturable pseudo-random set, which is the key cryptographic building block used in previous works on PIR with client preprocessing.

2. Privacy-Preserving Regular Expression Matching Using TNFA

   Ning Luo, Chenkai Weng, Jaspal Singh, Gefei Tan, Mariana Raykova, and Ruzica Piskac

   In European Symposium on Research in Computer Security (ESORICS), 2024

   Abs PDF

   Motivated by the privacy requirements in network intrusion detection and DNS policy checking, we have developed a suite of protocols and algorithms for regular expression matching with enhanced privacy: (i) A new regular expression matching algorithm that is oblivious to the input strings, of which the complexity is only O(mn) where m and n are the length of strings and the regular expression respectively. It is achieved by exploiting the structure of the Thompson nondeterministic automata. (ii) A zero-knowledge proof of regular expression pattern matching in which a prover generates a proof to demonstrate that a public regular expression matches her input string without revealing the string itself. (iii) Two secure-regex protocols that ensure the privacy of both the string and regular expression. The first protocol is based on the oblivious stack and reduces the complexity of the state-of-the-art from O(mn2) to O(mn log n). The second protocol relies on the oblivious transfer and performs better empirically when the size of regular expressions is smaller than 2^12. We also evaluated our protocols in the context of encrypted DNS policy checking and intrusion detection and achieved 4.5X improvements over the state-of-the-art. These results also indicate the practicality of our approach in real-world applications.

2023

1. Malicious secure, structure-aware private set intersection

   Gayathri Garimella, Mike Rosulek, and Jaspal Singh

   In Annual International Cryptology Conference (CRYPTO), 2023

   Abs PDF

   Structure-Aware private set intersection is a variant of PSI where Alice’s input set A has some publicly known structure, Bob’s input B is an unstructured set of points, and Alice learns the intersection A ∩B. sa-PSI was recently introduced by Garimella et al. (Crypto 2022), who described a semi-honest protocol with communication that scales with the description size of Alice’s set, instead of its cardinality. In this paper, we present the first sa-PSI protocol secure against malicious adversaries. sa-PSI protocols are built from function secret sharing (FSS) schemes, and the main challenge in our work is ensuring that multiple FSS sharings encode the same structured set. We do so using a cut-and-choose approach.In order to make FSS compatible with cut-and-choose, we introduce a new variant of function secret sharing, called derandomizable FSS (dFSS). We show how to construct dFSS for union of geometric balls, leading to a malicious-secure sa-PSI protocol where Alice’s input is a union of balls. We also improve prior FSS constructions, giving asymptotic improvements to semi-honest sa-PSI.

2022

1. Structure-aware private set intersection, with applications to fuzzy matching

   Gayathri Garimella, Mike Rosulek, and Jaspal Singh

   In Annual International Cryptology Conference (CRYPTO), 2022

   Abs PDF

   In two-party private set intersection (PSI), Alice holds a set X, Bob holds a set Y, and they learn (only) the contents of X ∩Y. We introduce structure-aware PSI protocols, which take advantage of situations where Alice’s set X is publicly known to have a certain structure. The goal of structure-aware PSI is to have communication that scales with the description size of Alice’s set, rather its cardinality. We introduce a new generic paradigm for structure-aware PSI based on function secret-sharing (FSS). In short, if there exists compact FSS for a class of structured sets, then there exists a semi-honest PSI protocol that supports this class of input sets, with communication cost proportional only to the FSS share size. Several prior protocols for efficient (plain) PSI can be viewed as special cases of our new paradigm, with an implicit FSS for unstructured sets. Our PSI protocol can be instantiated from a significantly weaker flavor of FSS, which has not been previously studied. We develop several improved FSS techniques that take advantage of these relaxed requirements, and which are in some cases exponentially better than existing FSS. Finally, we explore in depth a natural application of structure-aware PSI. If Alice’s set X is the union of many radius-δballs in some metric space, then an intersection between X and Y corresponds to fuzzy PSI, in which the parties learn which of their points are within distance δ. In structure-aware PSI, the communication cost scales with the number of balls in Alice’s set, rather than their total volume. Our techniques lead to efficient fuzzy PSI for l_∞and l_1 metrics (and approximations of l_2 metric) in high dimensions. We implemented this fuzzy PSI protocol for 2-dimensional l_∞metrics. For reasonable input sizes, our protocol requires 45–60% less time and 85% less communication than competing approaches that simply reduce the problem to plain PSI.

2021

1. Large message homomorphic secret sharing from DCR and applications

   Lawrence Roy, and Jaspal Singh

   In Annual International Cryptology Conference (CRYPTO), 2021

   Abs PDF

   We present the first homomorphic secret sharing (HSS) construction that simultaneously (1) has negligible correctness error, (2) supports integers from an exponentially large range, and (3) relies on an assumption not known to imply FHE — specifically, the Decisional Composite Residuosity (DCR) assumption. This resolves an open question posed by Boyle, Gilboa, and Ishai (Crypto 2016). Homomorphic secret sharing is analogous to fully-homomorphic encryption, except the ciphertexts are shared across two non-colluding evaluators. Previous constructions of HSS either had non-negligible correctness error and polynomial-size plaintext space or were based on the stronger LWE assumption. We also present two applications of our technique: a two server ORAM with constant bandwidth overhead, and a rate-1 trapdoor hash function with negligible error rate

2. Private set operations from oblivious switching

   Gayathri Garimella, Payman Mohassel, Mike Rosulek, Saeed Sadeghian, and Jaspal Singh

   In International Conference on Public-Key Cryptography (PKC), 2021

   Abs PDF

   Private set intersection reveals the intersection of two private sets, but many real-world applications require the parties to learn only partial information about the intersection. In this paper we introduce a new approach for computing arbitrary functions of the intersection, provided that it is safe to also reveal the cardinality of the intersection. In the most general case, our new protocol provides the participants with secret shares of the intersection, which can be fed into any generic 2PC protocol. Certain computations on the intersection can also be done even more directly and efficiently, avoiding this secret-sharing step. These cases include computing only the cardinality of intersection, or the “cardinality-sum” application proposed in Ion et al. (ePrint 2017). Compared to the state-of-the-art protocol for computing on intersection (Pinkas et al., Eurocrypt 2019), our protocol has about less communication, and has faster running time on slower (50 Mbps) networks. Our new techniques can also be used to privately compute the union of two sets as easily as computing the intersection. Our protocol concretely improves the leading private set union protocol (Kolesnikov et al., Asiacrypt 2020) by a factor of , depending on the network speed. We then show how private set union can be used in a simple way to realize the “Private-ID” functionality suggested by Buddhavarapu et al. (ePrint 2020). Our protocol is significantly faster than the prior Private-ID protocol, especially on fast networks. All of our protocols are in the two-party setting and are secure against semi-honest adversaries.

2020

1. Activity-selection behavior and optimal user-distribution in Q&A websites

   Anamika Chhabra, SRS Iyengar, Jaspal Singh Saini, and Vaibhav Malik

   In International Conference on Computational Collective Intelligence (ICCCI), 2020

   Abs PDF

   Based on various factors such as experience, interest, and motivation, users in any system choose to perform certain activities more than the others. In this study, we investigate a similar behavior and its dynamics in the websites of StackExchange. We find that most of the users in these websites tend to contribute predominantly to one of the activities available on these websites. Such a behavior yields a high-level distribution of users across the activities, referred to as User-distribution. We find that this distribution varies for different websites of StackExchange. We also observe that the users contributing to different activities trigger each other to provide more contribution. Using these insights, we build a model that explains the effect of change in user-distribution on the amount of knowledge produced on these websites. The model shows that one can formulate an optimal ecosystem by motivating the right kind of users, which leads to the maximum fostering of knowledge on these websites.

2017

1. Secure Multiparty Construction of a Distributed Social Network

   Varsha Bhat Kukkala, Jaspal Singh, and SRS Iyengar

   In International Conference on Distributed Computing and Networking (ICDCN), 2017

   Abs PDF

   The advancement in technology has resulted in a better connected society. These connections foster social interactions that result in an emergent structure. This structure is popularly termed as a social network and is an integral component of study, in the field of network science. However, the study of these social networks is limited to the availability of data on the underlying social interactions. Privacy concerns restrict the access to network data with sensitive information. Networks that capture the relations such as trust, enmity, sexual contact, are a few examples of sensitive networks. A study of these sensitive networks is important in unraveling the behavioral aspects of the concerned individuals. The current paper proposes a multiparty computation algorithm that allows the construction of an unlabeled random isomorphic version of a distributedly held network. The protocol is proven to be secure in the presence of the extended arithmetic black-box, which supports the operations of addition, multiplication, comparison and equality checks.

2016

1. Privacy preserving network analysis of distributed social networks

   Varsha Bhat Kukkala, Jaspal Singh, and SRS Iyengar

   In International Conference on Information Systems Security (ICISS), 2016

   Abs PDF

   Social network analysis as a technique has been applied to a diverse set of fields, including, organizational behavior, sociology, economics and biology. However, for sensitive networks such as hate networks, trust networks and sexual networks, these techniques have been sparsely used. This is majorly attributed to the unavailability of network data. Anonymization is the most commonly used technique for performing privacy preserving network analysis. The process involves the presence of a trusted third party, who is aware of the complete network, and releases a sanitized version of it. In this paper, we propose an alternative, in which, the desired analysis can be performed by the parties who distributedly hold the network, such that : (a) no central third party is required; (b) the topology of the underlying network is kept hidden. We design multiparty protocols for securely performing few of the commonly studied social network analysis algorithms. The current paper addresses a secure implementation of the most commonly used network analysis measures, which include degree distribution, closeness centrality, PageRank algorithm and K-shell decomposition algorithm. The designed protocols are proven to be secure in the presence of an arithmetic black-box extended with operations like comparison and modulo.

2. Secure multiparty graph computation

   Varsha Bhat Kukkala, SRS Iyengar, and Jaspal Singh

   In International Conference on Communication Systems and Networks (COMSNETS), 2016

   Abs PDF

   The recent explosion of online networked data and the discovery of universal topological characteristics in real world networks has led to the emergence of a new domain of research, namely, social networks. However, much research in this domain remains unexplored due to the inaccessibility of data of sensitive networks, which include hate networks, trust networks and sexual relationship networks. This paper proposes a secure multiparty protocol which allows a set of parties to compute the underlying network on them. The proposed protocol is information theoretically secure, and its security is further enhanced by a list of security tests, which includes k-anonymity test, check for self loops and weighted edges. Although some solutions have been proposed for this problem earlier, the practicality of each one of those is questionable.

3. Shifting behaviour of users: Towards understanding the fundamental law of social networks

   Yayati Gupta, Jaspal Singh, Nidhi Sridhar, and SRS Iyengar

   In International Conference on Communication Systems and Networks (COMSNETS), 2016

   Abs PDF

   Social Networking Sites (SNSs) are powerful marketing and communication tools. There are hundreds of SNSs that have entered and exited the market over time. The coexistence of multiple SNSs is a rarely observed phenomenon. Most coexisting SNSs either serve different purposes for its users or have cultural differences among them. The introduction of a new SNS with a better set of features can lead to the demise of an existing SNS, as observed in the transition from Orkut to Facebook. The paper proposes a model for analyzing the transition of users from one SNS to another, when a new SNS is introduced in the system. The game theoretic model proposed considers two major factors in determining the success of a new SNS. The first being time that an old SNS gets to stabilise. We study whether the time that a SNS like Facebook received to monopolize its reach had a distinguishable effect. The second factor is the set of features showcased by the new SNS. The results of the model are also experimentally verified with data collected by means of a survey.