Publications by Dr Sanjay Bhattacherjee

A practical searchable symmetric encryption (SSE) should allow users to privately store documents on untrusted servers with the abilities to (1) search with multiple keywords, and (2) add or delete documents dynamically. The oblivious cross tag (OXT) construction from Crypto'13 is the most efficient SSE scheme that allows conjunctive searches, but only for static databases. In NDSS'20, OXT was extended to ODXT supporting dynamic updates. However, ODXT is not forward private. In this work, we identify a commonly used setting for SSE where a document with its associated keywords can be dynamically added to or deleted from the database as a whole, but its set of keywords is not modified in between. In this setting, we propose a generic framework for designing conjunctive dynamic SSE, supporting conjunctive queries that allow dynamic updates while being forward and backward private at the same time. Our construction uses a generic dynamic single keyword SSE and the OXT scheme as modular black-boxes. Our scheme generalises ODXT. We provide new security definitions of forward and backward privacy for the new setting. Our generic construction (and hence ODXT) achieves forward and BPUP backward privacy in the new setting, even when the underlying single keyword SSE scheme is only WBP backward private. We analyse the precise leakages of our scheme to the adversarial server. We have instantiated our generic construction with three different single keyword schemes. Experiments show that our schemes are very efficient and practical. Our code is publicly available.

We introduce a new and general model for voting games with multiple weight vectors. Previously studied models are obtained as special cases of the new model. In comparison to earlier models, games have more compact representation in the new model. In particular, we show that a previously well known example of a game having dimension exponential in the number of players can be represented in the new model using only two weight vectors. Further, we identify a new sub-class of games, that we call hyperplane voting games, which are compactly expressible in the new model, but not necessarily so in the previous models. For games represented in the new model, we present dynamic programming algorithms for determining various quantities required for computing different voting power indices. Methods for computing the number of minimal winning coalitions under various restrictions were not previously known even for the earlier models.

LLL-style lattice reduction algorithms iteratively employ size reduction and reordering on ordered basis vectors to find progressively shorter, more orthogonal vectors. DeepLLL reorders the basis through deep insertions, yielding much shorter vectors than LLL. DeepLLL was introduced alongside BKZ, however, the latter has received greater attention and has emerged as the state-of-the-art. We first show that LLL-style algorithms work with a designated measure of basis quality and iteratively improves it; specifically, DeepLLL improves a sublattice measure based on the generalised Lovász condition. We then introduce a new generic framework X-GG for lattice reduction algorithms that work with a measure X of basis quality. X-GG globally searches for deep insertions that minimise X in each iteration. We instantiate the framework with two quality measures – basis potential (Pot) and squared sum (SS) – both of which have corresponding DeepLLL algorithms. We prove polynomial runtimes for our X-GG algorithms and also prove their output to be X-DeepLLL reduced. Our experiments on non-preprocessed bases show that X-GG produces better quality outputs whilst being much faster than the corresponding DeepLLL algorithms. We also compare SS-GG and the FPLLL implementation of BKZ with LLL-preprocessed bases. In small dimensions (40 to 210), SS-GG is significantly faster than BKZ with block sizes 8 to 12, while simultaneously also providing better output quality in most cases. In higher dimensions (250 and beyond), by varying the threshold for deep insertion, SS-GG offers new trade-offs between the output quality and runtime. On the one hand, it provides significantly better runtime than BKZ-5 with worse output quality; on the other hand, it is significantly faster than BKZ-21 while providing increasingly better output quality after around dimension 350.

The first observation of the paper is that methods for determining proportional representation in electoral systems may be suitable as alternatives to the pro-rata order matching algorithm used in stock exchanges. The main part of our work is to comprehensively consider various well known proportional representation methods and analyse in details their suitability for replacing the pro-rata algorithm. Our analysis consists of a theoretical study as well as simulation studies based on data sampled from a distribution which has been suggested in the literature as models of limit orders. Based on our analysis, we put forward the suggestion that the well known Hamilton's method is a superior alternative to the pro-rata algorithm for order matching applications.

The Goods and Services Tax (GST) Council of India has a non-conventional weighted voting procedure having a primary player who is a blocker and a set of secondary players. The voting weights are not fixed and are determined based on the subset of players which participate in the voting. We introduce the notion of voting schema to formally model such a voting procedure. Individual voting games arise from a voting schema depending on the subset of secondary players who participate in the voting. We make a detailed formal study of the trade-off between the minimal sizes of winning and blocking coalitions in the voting games that can arise from a voting schema. Finally, the GST voting procedure is assessed using the theoretical results leading to suggestions for improvement.

In Broadcast Encryption (BE) systems like Pay-TV, AACS, online content sharing and broadcasting, reducing the header length (communication overhead per session) is of practical interest. The Subset Difference (SD) scheme due to Naor-Naor-Lotspiech (NNL) is the most popularly used BE scheme. We introduce the (a,b,γ) augmented binary tree subset difference ( (a,b,γ) -ABTSD) scheme which is a generalization of the NNL-SD scheme. By varying the parameters (a,b,γ) , it is possible to obtain O(nlogn) different schemes. The average header length achieved by the new schemes is smaller than all known schemes having the same decryption time as that of the NNL-SD scheme and achieving non-trivial trade-offs between the user storage and the header size. The amount of key material that a user is required to store increases. For the earlier mentioned applications, reducing header size and achieving fast decryption is perhaps more of a concern than the user storage.

The most influential broadcast encryption (BE) scheme till date was introduced in 2001 by Naor, Naor and Lotspiech (NNL) and is based on binary trees. This paper generalizes the ideas of NNL to obtain BE schemes based on k-ary trees for any k ≥ 2. The treatment is uniform across all k and essentially provides a single scheme which is parameterized by the arity of the underlying tree. We perform an extensive analysis of the header length and user storage of the scheme. It is shown that for a k-ary tree with n users out of which r are revoked, the maximum header length is min(2r − 1, n − r, dn/ke). An expression for the expected header length is obtained and it is shown that the expression can be evaluated in O(r log n) time. Experimental results indicate that for values of r one would expect in applications such as pay TV systems, the average header length decreases as k increases. The number of keys to be stored by any user is shown to be at most (χ k −2)` 0 (` 0 +1)/2, where ` 0 = dlog k ne and χ k is the number of cyclotomic cosets modulo 2 k −1. In particular, when the number of users is more than 1024, we prove that the user storage required for k = 3 is less than that of k = 2. For higher values of k, the user storage is greater than that for binary trees. The option of choosing the value of k provides a designer of a BE system with a wider range of trade-offs between average header length and user storage. The effect of layering on the k-ary tree SD scheme is also explored.

Two key parameters of broadcast encryption (BE) schemes are the transmission size and the user storage. Naor-Naor-Lotspiech (2001) introduced the subset difference (SD) scheme achieving a good trade-off between these two parameters. Halevy-Shamir (2002) introduced the idea of layering to reduce user storage of the NNL scheme at the cost of increased transmission overhead. Here, we introduce several simple ideas to obtain new layering strategies with different trade-offs between user storage and transmission overhead. We define the notion of storage minimal layering and describe a dynamic programming algorithm to compute layering schemes for which the user storage is the minimum attainable using layerings. Further, the constrained minimization problem is considered. A method is described which yields BE schemes whose transmission overhead is not much more than the SD scheme but, whose user storage is still significantly lower. Finally, an O(r log 2 n) algorithm is obtained to compute the average transmission overhead for any layering-based scheme where r out of n users are revoked. This algorithm works for any layering strategy and also for arbitrary number of users. The algorithm has been used here to generate all data for the average transmission overhead.

The Subset Difference (SD) method proposed by Naor, Naor and Lotspiech is the most popular broadcast encryption (BE) scheme. It is suitable for real-time applications like Pay-TV and has been suggested for use by the AACS standard for digital rights management in Blu-Ray and HD-DVD discs. The SD method assumes the number of users to be a power of two. We propose the Complete Tree Subset Difference (CTSD) method that allows the system to support an arbitrary number of users. In particular, it subsumes the SD method and all results proved for the CTSD method also hold for the SD method. Recurrences are obtained for the CTSD scheme to count the number, $N(n,r,h)$, of possible ways $r$ users in the system of $n$ users can be revoked to result in a transmission overhead or header length of $h$. The recurrences lead to a polynomial time dynamic programming algorithm for computing $N(n,r,h)$. Further, they provide bounds on the maximum possible header length. A probabilistic analysis is performed to obtain an $O(r \log{n})$ time algorithm to compute the expected header length in the CTSD scheme. Further, for the SD scheme we obtain an explicit limiting upper bound on the expected header length.

In a weighted majority voting game, the weights of the players are determined based on some socio-economic parameter. A number of measures have been proposed to measure the voting powers of the different players. A basic question in this area is to what extent does the variation in the voting powers reflect the variation in the weights? The voting powers depend on the winning threshold. So, a second question is what is the appropriate value of the winning threshold? In this work, we propose two simple ideas to address these and related questions in a quantifiable manner. The first idea is to use Pearson's Correlation Coefficient between the weight vector and the power profile to measure the similarity between weight and power. The second idea is to use standard inequality measures to quantify the inequality in the weight vector as well as in the power profile. These two ideas answer the first question. Both the weight-power similarity and inequality scores of voting power profiles depend on the value of the winning threshold. For situations of practical interest, it turns out that it is possible to choose a value of the winning threshold which maximises the similarity score and also minimises the difference in the inequality scores of the weight vector and the power profile. This provides an answer to the second question. Using the above formalisation, we are able to quantitatively argue that it is sufficient to consider only the vector of swings for the players as the power measure. We apply our methodology to the voting games arising in the decision making processes of the International Monetary Fund (IMF) and the European Union (EU). In the case of IMF, we provide quantitative evidence that the actual winning threshold that is currently used is sub-optimal and instead propose a winning threshold which has a firm analytical backing. On the other hand, in the case of EU, we provide quantitative evidence that the presently used threshold is very close to the optimal.

In this paper, we present a game theoretical and an epistemic logical approach to fact-checking. Game theory is the study of strategic reasoning whereas epistemic logic is the formal study of reasoning about and with knowledge. Fact-checking is strategic because the process involves more than one agent. It is epistemic as the process is all about verifying the correctness of one or more pieces of information – hence checking whether it is indeed "knowledge". We discuss a variety of typical fact-checking scenarios and present game theoretical and epistemic logical analysis for them.

Our fight against false information is spearheaded by fact-checkers. They investigate the veracity of claims and document their findings as fact-checking reports. With the rapid increase in the amount of false information circulating online, the use of automation in factchecking processes aims to strengthen this ecosystem by enhancing scalability. Datasets containing fact-checked claims play a key role in developing such automated solutions. However, to the best of our knowledge, there is no fact-checking dataset at the ecosystem level, covering claims from a sufficiently long period of time and sourced from a wide range of actors reflecting the entire ecosystem that admittedly follows widely-accepted codes and principles of fact-checking. We present a new dataset FACTors, the first to fill this gap by presenting ecosystem-level data on fact-checking. It contains 118,112 claims from 117,993 fact-checking reports in English (co-)authored by 1,953 individuals and published during the period of 1995-2025 by 39 fact-checking organisations that are active signatories of the IFCN (International Fact-Checking Network) and/or EFCSN (European Fact-Checking Standards Network). It contains 7,327 overlapping claims investigated by multiple fact-checking organisations, corresponding to 2,977 unique claims. It allows to conduct new ecosystem-level studies of the fact-checkers (organisations and individuals). To demonstrate the usefulness of our dataset, we present three example applications. They include a first-of-its-kind statistical analysis of the fact-checking ecosystem, examining the political inclinations of the fact-checking organisations, and attempting to assign a credibility score to each organisation based on the findings of the statistical analysis and political leanings. Our methods for constructing FACTors are generic and can be used to maintain a live dataset that can be updated dynamically.

This work is the first study on the perceptions of social media users about cryptocurrency attacks. The doublespending or 51% attack being the most fundamental attack on cryptocurrencies, it is the focus of this study. As a first step, we create a first-of-its-kind comprehensive list of 31 events of 51% attacks on various proof-of-work cryptocurrencies, showing that these events are quite common. This list contradicts the general perception about the security of cryptocurrencies, particularly portrayed in the Executive Order establishing a Strategic Bitcoin Reserve and a Digital Asset Stockpile in the US. We design the methodologies for our new study of user perceptions around these attacks. We create datasets containing tweets from the time of the attack events, and compare them with benchmark data from normal times. We define parameters for profiling these datasets based on user perceptions – sentiments and emotions. We study the variation of these perception profiles, when a cryptocurrency is under attack and the benchmark otherwise, between multiple attack events of the same cryptocurrency, and between different cryptocurrencies. Our results confirm some expected overall behaviour and reactions while providing nuanced insights that may not be obvious or may even be considered surprising. Our code and datasets are publicly accessible.

We model the protocol stability and the security of proof-of-work cryptocurrencies using voting games. The first game, which we call the Rule Game, pertains to the scenario where the cryptocurrency miners engage in a voting procedure to accept or reject a proposal for change of the cryptocurrency protocol. The second game, which we call the Attack Game, refers to the scenario where a group of miners can form a coalition to launch a 51% attack on the system and consequently change a portion of the history of the underlying blockchain, thus defeating its promise of immutability. For the Attack Game, we define progressively granular notions of security all of which are based on the key concept of minimal winning coalitions from voting game theory. For both the Rule Game and the Attack Game, we show practical applicability of tools from voting game theory using a snapshot of real world data for Bitcoin. In particular, this highlights the fragile nature of the security of Bitcoin with respect to 51% attacks.

We provide efficient constructions for trace-and-revoke systems with public traceability in the black-box confirmation model. Our constructions achieve adaptive security, are based on standard assumptions and achieve significant efficiency gains compared to previous constructions. Our constructions rely on a generic transformation from inner product functional encryption (IPFE) schemes to trace-and-revoke systems. Our transformation requires the underlying IPFE scheme to only satisfy a very weak notion of security -- the attacker may only request a bounded number of random keys -- in contrast to the standard notion of security where she may request an unbounded number of arbitrarily chosen keys. We exploit the much weaker security model to provide a new construction for bounded collusion and random key IPFE from the learning with errors assumption (LWE), which enjoys improved efficiency compared to the scheme of Agrawal et al. [CRYPTO'16]. Together with IPFE schemes from Agrawal et al., we obtain trace and revoke from LWE, Decision Diffie Hellman and Decision Composite Residuosity.

The Subset Difference (SD) method is the most popular of Broadcast Encryption schemes due to its use in AACS standard for video discs. The scheme assumes the number of users $n$ to be a power of two. In this paper, we relax this and consider arbitrary values of $n$. In some applications, this leads to substantial savings in the transmission overhead. Our analysis consists of the following aspects: (1) A recurrence to count $N(n,r,h)$ - the number of revocation patterns for arbitrary values of $n$ and $r$ (number of revoked users) resulting in a header length of $h$. The recurrence allows us to generate data and hence to completely analyze it for larger $n$ than the brute force method. (2) We do a probabilistic analysis of the subset cover finding algorithm of the SD method and find an expression to evaluate the expected header length $E[X_{n,r}]$ for arbitrary values of $n$ and $r$. Using this, $E[X_{n,r}]$ can be evaluated in $O(r \log n)$ time using constant space. (3) While concluding, we suggest a similar method for finding $E[X_{n,r}]$ for the Layered Subset Difference (LSD) scheme of Halevy and Shamir. (4) In the SD method, for $n$ being a power two, we find asymptotic values of the expected header length.