Publications by Dr Sanjay Bhattacherjee

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.

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.