Professor

Applied Statistics Unit

Indian Statistical Institute

• Modes of operations
• Mathematics of symmetric cipher cryptanalysis
• Symmetric key broadcast encryption
• Design and analysis of collision resistant hash functions
• Design and analysis of symmetric key ciphers
• Analysis of time-memory trade-off attacks
• Cryptographic properties of Boolean functions and S-boxes
• Universal one-way hash functions
• Elliptic curve cryptography
• Pairing based cryptography
• Discrete logarithm computation
• Lattice based cryptography
• Code based cryptography
  
• Another look papers
• Blockchain and cryptocurrency

• Cryptographic properties of Boolean functions and S-boxes
• Analysis of Boolean functions
• Enumeration of Boolean function sub-classes
• Voting games

• Voting gamesOrder matching algorithm
• Inequality measurement
• Order matching algorithm
  

• Lays the theoretical foundation for multi-level almost universal hash function construction, where the hash functions for the different levels uses independent keys.
• This allows obtaining a trade-off between the collision probability and the key size of the multi-level hash function.

• Generalised a previous well-known construction of multi-linear universal hash function due to Gilbert, MacWilliams and Sloane (which has also been credited to Carter and Wegman).
• The generalisation results in constructions of universal hash function which are well suited for hardware implementation in resource constrained devices.
• Actual hardware implementations have been reported in a paper published in the IEEE Transactions on Computers in 2015.

• Provides the first non-recursive algorithm for the evaluation of BRW polynomials (introduced by Bernstein based on earlier work by Rabin and Winograd) along with a proof of correctness.
• Implementation over binary extension fields is reported and shown to be faster than the NIST standardised GHASH function as also the well known POLYVAL function.

• Describes a two-level almost universal hash function with BRW polynomial-based hashing at the first level and usual polynomial hashing at the second level.
• Implementation using binary extension fields on AMD architecture shows that the resulting hash functions are the fastest over such fields.
• In particular the instantiation over GF(2^{128}) provides a function which is faster than the NIST standardised GHASH function as also the well known POLYVAL function.

• Comprehensively builds the theory for combining BRW polynomials and usual polynomials to obtain almost universal hash functions over prime order fields.
• Extensive implementations are reported for the primes 2^{127}-1 and 2^{130}-5.
• This results in a new hash function which is significantly faster than the well known and de facto standard Poly1305 hash function.

• These two papers showed how to obtain new families of very efficient block cipher based parallelisable constructions of message authentication codes.
• The constructions are comparable in efficiency to the well known PMAC algorithm.

• Provides the first efficient and provable constructions of MAC schemes using a stream cipher supporting an initialisation vector.

• Provides the first formalisation of the problem of message authentication codes supporting variable tag lengths.
• The work showed how to modify the famous Wegman-Carter MAC to construct provable and practical MAC schemes supporting variable tag lengths which can be instantiated using off-the-shelf block ciphers and stream ciphers.

• These two papers showed how to obtain new families of very efficient block cipher based parallelisable constructions of authenticated encryption with associated data.
  
• The constructions are comparable in efficiency to the famous OCB3 algorithm.

Palash Sarkar. A Simple and Generic Construction of Authenticated Encryption With Associated Data. ACM Transactions on Information and Systems Security, 2010 (link).

• Shows how to generically incorporate associated data into an AE scheme.

• Provides the first efficient and provable constructions of AEAD schemes using a stream cipher supporting an initialisation vector.

• Shows how to obtain new families of very efficient block cipher based parallelisable constructions of deterministic authenticated encryption with associated data.
  

Palash Sarkar. A Simple and Generic Construction of Authenticated Encryption With Associated Data. ACM Transactions on Information and Systems Security, 2010 (link).

• Shows how to generically incorporate associated data into an AE scheme.

• Provides the first efficient and provable constructions of DAEAD schemes using a stream cipher supporting an initialisation vector.

• Proposed a new construction of tweakable enciphering scheme called HCH.

• The first work to propose the use of BRW polynomials in the construction of tweakable enciphering schemes which resulted in a number of new schemes.
• This work builds on a previous paper published in ICISC 2007 and another paper published in Information Processing Letters in 2008.

• Shows how to exploit inherent parallelism in the definition of BRW polynomials to obtain efficient hardware implementation and as a consequence the hardware implementations of TES and disk encryption schemes using such polynomials.

• Provides the presently known fastest provably secure algorithm for full disk encryption and much more general applications of tweakable enciphering schemes.
• This work builds upon a previous paper published in Information Processing Letters in 2011.

• Provides the first proposals and FPGA implementations of provably secure and efficient stream cipher based disk encryption schemes with very low hardware footprint.

• Shows that very efficient provably secure solutions for disk encryption can be obtained from DAEAD, provided the condition for length preservation can be relaxed.

• Pointed out various security problems in the IEEE standard disk encryption scheme called XCB.

• Shows attacks on six important tweakable enciphering schemes in the quantum computing model using Simon's algorithm.

Mathematics of symmetric cipher cryptanalysis

Subhabrata Samajder and Palash Sarkar. Another Look at Normal Approximations in Cryptanalysis. Journal of Mathematical Cryptology, 2016 (link).

• Takes a critical look at the use of normal approximations in symmetric key cryptanalysis.
• Concrete bounds on the errors in approximations are derived.
• Applying such error bounds to some well known previous analysis of certain important attacks invalidates those analysis.
• The work adopts the hypothesis testing methodology to analyse such attacks on a firm mathematical footing.

Subhabrata Samajder and Palash Sarkar. Rigorous Upper Bounds on Data Complexities of Block Cipher Cryptanalysis. Journal of Mathematical Cryptology, 2017 (link).

• Performs a rigorous statistical analysis using Chernoff and Hoeffding bounds to obtain data complexities of various methods for cryptanalysis.

• Performs a rigorous statistical analysis of multiple (truncated) differential cryptanalysis.

Subhabrata Samajder and Palash Sarkar. Success Probability of Multiple/Multidimensional Linear Cryptanalysis Under General Key Randomisation Hypotheses. Cryptography and Communications, 2018 (link).

• Performs a general and unified statistical analysis of attacks on block ciphers using several linear approximations.

Subhabrata Samajder and Palash Sarkar. Another Look at Success Probability of Linear Cryptanalysis. Advances in Mathematics of Communications, 2019 (link).

• Performs a comprehensive and unified analysis of the success probability of linear cryptanalysis using a single linear approximation under various key randomisation hypotheses.

Subhabrata Samajder and Palash Sarkar. Another Look at Key Randomisation Hypotheses.  Designs, Codes, and Cryptography, 2023 (link).

• Provides mathematical arguments and simulation results to show that the success probability of linear cryptanalysis is a monotone increasing function of the number of plaintext-ciphertext pairs even under the alternate key randomisation hypotheses.
• This settles the vexing issue of non-monotonic behaviour reported in several previous works.

Subhabrata Samajder and Palash Sarkar. Distinguishing Error of Nonlinear Invariant Attacks. Indocrypt, 2022 (link).

• Provides a rigorous derivation of the distinguishing error of nonlinear invariant attacks.

Symmetric key broadcast encryption (BE)

Sanjay Bhattacherjee and Palash Sarkar. Complete Tree Subset Difference Broadcast Encryption Scheme and its Analysis.  Designs, Codes and Cryptography, 2013. (link).

• Proposes and performs an extensive analysis of the complete tree subset difference method for broadcast encryption.
• The new method subsumes the subset difference method proposed by Naor, Naor and Lotspiech which had laid the foundation for the AACS standard.

Sanjay Bhattacherjee and Palash Sarkar. Tree Based Symmetric Key Broadcast Encryption.  Journal of Discrete Algorithms, 2015 (link).

• A paper published in Journal of Discrete Algorithms in 2015 proposed symmetric key broadcast encryption based on k-ary trees for any k greater than or equal to 2.

Sanjay Bhattacherjee and Palash Sarkar. Concrete Analysis and Trade-Offs for the (Complete Tree) Layered Subset Difference Broadcast Encryption Scheme. IEEE Transactions on Computers, 2014 (link).

• Formalises the idea of layered subset difference introduced by Halevy and Shamir as an optimisation problem and used dynamic programming to obtain optimal solutions.
• The resulting solutions provides BE schemes where the user key storage is the lowest among all known schemes. The trade-off is an increase in the header size.

Sanjay Bhattacherjee and Palash Sarkar. Reducing Communication Overhead of the Subset Difference Scheme.  IEEE Transactions on Computers, 2016 (link).

• Provides a scheme where the header size is the lowest among all known schemes. The trade-off is an increase in the user key size.

Design and analysis of collision resistant hash functions

Somitra Kumar Sanadhya and Palash Sarkar. A Combinatorial Analysis of Recent Attacks on Step Reduced SHA-2 Family. Cryptography and Communications, 2009 (link).

• Provided a unified and general analysis of till then known attacks on SHA-256 exhibiting colliding message pairs for up to 24 rounds.
• This paper built on earlier works including a paper at Indocrypt 2008, a paper at ISC 2008, a paper at ACISP 2008, a paper at ACNS 2008, and a paper at ICISC 2007.

Somitra Kumar Sanadhya and Palash Sarkar. A New Hash Family Obtained by Modifying the SHA-2 Family. ASIACCS, 2009 (link).

• Proposed modifications to SHA-2 to improve resistance to the till then known attacks.

Somindu C. Ramanna and Palash Sarkar. On Quantifying the Resistance of Concrete Hash Functions to Generic Multi-Collision Attacks. IEEE Transactions on Information Theory, 2011 (link).

• Generalised and analysed the notion of balance introduced by Bellare and Kohno for generic collision attacks to generic multi-collision attacks.

• Provides a new algorithm to extend the compression function to a collision resistant hash function.
• The number of bits that are required to be padded by the new algorithm is O(log|x|) which improves upon the O(|x|) bits that are required to be padded by the famous Merkle-Damgard algorithm. Here x is the message to be hashed.

• Provides a parallel algorithm for extending a compression function to a collision resistant hash function.
• Improves upon the Merkle-Damgard construction which is a sequential algorithm.

• Instantiates the Sarkar-Schellenberg composition principle with the compression function of SHA-256 to construct a hash function.

• Breaks concrete proposals for multi-word T-functions put forward by Klimov and Shamir.

• Puts forward a hardware proposal for efficient implementation of large stream cipher systems.

Analysis of time-memory trade-off (TMTO) attacks

Alex Biryukov, Sourav Mukhopadhyay and Palash Sarkar. Improved Time-Memory Trade-offs with Multiple Data. SAC, 2005 (link).

• Proposes improvements to time/memory trade-off attacks which utilise multiple data.

Jin Hong and Palash Sarkar. New Applications of Time Memory Data Tradeoffs. Asiacrypt, 2005 (link).

• Performs a comprehensive and unified analysis of various applications of TMTO attacks with multiple data.
• Puts forward the important observation that stream ciphers with IV shorter than the key are vulnerable to TMTO attacks.

Cryptographic properties of Boolean functions and S-boxes

Theory

Kishan Chand Gupta and Palash Sarkar. Computing Partial Walsh Transform from the Algebraic Normal Form of a Boolean Function. IEEE Transactions on Information Theory, 2009 (link).

• The algorithm is faster than the usual fast Fourier transform if the number of terms in the algebraic normal form is not too large.

Kishan Chand Gupta and Palash Sarkar. Towards a General Correlation Theorem. IEEE Transactions on Information Theory, 2005 (link).

• A general correlation theorem is proved (of which some earlier results proved by Nyberg are special cases) and applied to various constructions of cryptographic interest.

Claude Carlet and Palash Sarkar. Spectral Domain Analysis of Correlation Immune and Resilient Boolean Functions. Finite Fields and their Applications, 2002 (link).

• Provides refined weight divisibility results for the Walsh transform of correlation immune and resilient Boolean functions which results in refined non-trivial upper bounds on the non-linearity of such functions.

Palash Sarkar and Subhamoy Maitra. Cross-Correlation Analysis of Cryptographically Useful Boolean Functions and S-Boxes. Theory of Computing Systems, 2002 (link).

• Uses the cross-correlation theorem to build the basic theory and applies the theory to results of cryptographic interest.

Palash Sarkar. A note on the spectral characterization of correlation immune Boolean functions.  Information Processing Letters, 2000 (link).

• A direct combinatorial proof of the spectral characterisation of correlation immune Boolean functions.

Subhamoy Maitra and Palash Sarkar. Enumeration of Correlation Immune Boolean Functions. ACISP, 1999 (link).

• Provides upper and lower bounds on the number of correlation immune Boolean functions.

Palash Sarkar and Subhamoy Maitra. Balancedness and Correlation Immunity of Symmetric Boolean Functions. Discrete Mathematics, 2007 (link).

• Identifies sub-classes of symmetric Boolean functions which are balanced and/or correlation immune.

Subhamoy Maitra, Palash Sarkar. Hamming Weights of Correlation Immune Boolean Functions.  Information Processing Letters, 1999 (link).

• Shows that number of correlation immune functions is monotone in the Hamming weights of the functions.

Subhamoy Maitra and Palash Sarkar. Maximum Nonlinearity of Symmetric Boolean Functions on Odd Number of Variables. IEEE Transactions on Information Theory, 2002 (link).

• Establishes the upper bound on the nonlinearity of symmetric Boolean functions and characterises the functions for which the upper bound is achieved.

Subhamoy Maitra and Palash Sarkar. Characterization of Symmetric Bent Functions -- An Elementary Proof. Journal of Combinatorial Mathematics and Combinatorial Computing, 43 (2002), 227-230.

• Provides a direct and elementary proof characterising the set of symmetric bent functions.

Boolean function construction

Palash Sarkar and Subhamoy Maitra. Construction of Nonlinear Resilient Functions Using ``Small'' Affine Functions. IEEE Transactions on Information Theory, 2004 (link).

• Provides refined techniques to construct cryptographically useful Boolean functions using small affine functions.

Subhamoy Maitra and Palash Sarkar. Cryptographic Modifications of Patterson-Weidemann Functions. IEEE Transactions on Information Theory, 2002 (link).

• Answers some open questions about Boolean functions by modifying bent and Patterson-Wiedemann functions to achieve cryptographically useful properties.

Enes Pasalic, Subhamoy Maitra, Thomas Johansson, and Palash Sarkar, New Constructions of Resilient and Coorelation Immune Boolean Functions Achieving the Upper Bound on Nonlinearity. Electronic Notes in Discrete Mathematics, 2001 (link).

• Constructs correlation immune and resilient functions on 5, 6 and 7 variables achieving optimal trade-off between several parameters.

Palash Sarkar and Subhamoy Maitra. Nonlinearity Bounds and Constructions of Resilient Boolean Functions. Crypto, 2000 (link).

• Obtains the first weight divisibility results on the Hamming weights of resilient functions.
• Provides new constructions of resilient functions achieving optimal or near-optimal trade-off between several parameters.

Palash Sarkar and Subhamoy Maitra. Construction of Nonlinear Boolean Functions with Important Cryptographic Properties. Eurocrypt, 2000 (link).
Subhamoy Maitra and Palash Sarkar. Highly Nonlinear Resilient Functions Optimizing Siegenthaler's Inequality. Crypto, 1999 (link).

• Both the above papers provided new constructions of cryptographically interesting Boolean functions.

S-box construction

Kishan Chand Gupta and Palash Sarkar. Improved Construction of Nonlinear Resilient S-Boxes. IEEE Transactions on Information Theory, 2005 (link).

• Provides new constructions of S-boxes which result in functions possessing properties superior to till-then known functions.
• Use of the Griesmer bound for linear codes.

Kishan Chand Gupta and Palash Sarkar. Construction of Perfect Nonlinear and Maximally Nonlinear Multi-Output Boolean Functions Satisfying Higher Order Strict Avalanche Criteria. IEEE Transactions on Information Theory, 2004 (link).

• New constructions of S-boxes satisfying desirable cryptographic criteria.
• Use of bilinear forms, symplectic matrices and one-factorisation of a complete graph.

Kishan Chand Gupta and Palash Sarkar. Construction of High Degree Resilient S-boxes With Improved Nonlinearity. Information Processing Letters, 2005 (link).

Implementation

• The first work to describe a hardware architecture for implementing large Boolean functions of cryptographic interest.

• The first work to propose algorithms for the the software implementation of resilient Maiorana-McFarland S-Boxes.

Universal one-way hash function (UOWHF)

• Presents a binary tree based parallel algorithm for extending the domain of a universal one-way hash function

• Shows a lower bound on the number of masks required by any correct masking-based domain extender for UOWHF which leads to key expansion optimality of several known algorithms.
• Present a new parallel domain extender for UOWHF which achieves asymptotically optimal speedup over the sequential algorithm and the key expansion is almost everywhere optimal.
• Builds on a previous paper published at Asiacrypt 2004.
  

Elliptic curve cryptography

• Proposes new pairs of Montgomery-Edwards curves at the 128-bit and 224-bit security level.
• Provides extensive hand optimised implementations of the Diffie-Hellman computations.
• Implementation results show that computations over the new curve at the 128-bit security level is faster than those over the de facto standard Curve25519.

• Proposes new pairs of Montgomery-Edwards curves for efficient elliptic curve cryptography at the 256-bit security level.
• Provides extensive hand optimised implementations of the Diffie-Hellman computations.

Kummer lines

Kaushik Nath and Palash Sarkar. Kummer versus Montgomery Face-off over Prime Order Fields. ACM Transactions on Mathematical Software, 2022 (link).

• Proposes new Kummer lines at high security levels.
• Provides extensive hand optimised implementations of the Diffie-Hellman computations.
• Shows that for vectorised implementations Diffie-Hellman computations on Kummer lines are faster than those on Montgomery curves.

Sabyasachi Karati and Palash Sarkar. Kummer for Genus One over Prime Order Fields. Journal of Cryptology, 2020 (link).

• The first work to propose concrete Kummer lines at the 128-bit security level.
• Perform SIMD implementations to demonstrate the advantage of Kummer lines over Montgomery form curves for vectorised implementations.
• Builds on an earlier paper published at Asiacrypt 2017 (which was recommended by the program chairs of the conference for invitation to the Journal of Cryptology.)

Sabyasachi Karati and Palash Sarkar. Connecting Legendre with Kummer and Edwards. Advances in Mathematics of Communications, 2019 (link).

• Shows how to translate a Kummer line to Edwards form curve which is useful for digital signature protocol.

Palash Sarkar. Computing square roots faster than the Tonelli-Shanks/Bernstein algorithm. Advances in Mathematics of Communications, 2024 (link).

• Provides both asymptotic as well as concrete improvements in counts of field multiplications and squarings.

Kaushik Nath and Palash Sarkar. Efficient 4-way Vectorizations of the Montgomery Ladder. IEEE Transactions on Computers, 2022 (link).

• Provides new and the fastest known algorithms for 4-way vectorisation of Montgomery ladder computation and their SIMD implementations.

Kaushik Nath and Palash Sarkar. Reduction Modulo 2^{448}-2^{224}-1. Mathematical Cryptology, 2020 (link).

• Provides detailed algorithm and proof of correctness of reduction modulo the prime 2^{448}-2^{224}-1. The importance of this prime arises from its use in defining the standard Curve448.

Kaushik Nath and Palash Sarkar. Efficient Arithmetic in (pseudo-)Mersenne Prime Order Fields. Advances in Mathematics of Communications, 2022 (link).

• Describes algorithms accompanied by formal statements and detailed proofs of correctness for modulo reduction for primes of certain forms which are of interest to elliptic curve cryptography.
• Provides extensive hand optimised assembly implementations of the relevant field arithmetic operations.

Pradeep Kumar Mishra, Pinakpani Pal and Palash Sarkar. Towards Minimizing Memory Requirement for Implementation of Hyperelliptic Curve Cryptosystems. ISPEC, 2007 (link).

• Proposes the first memory efficient explicit formulas for arithmetic in the Jacobian of hyperelliptic curves.

Palash Sarkar, Pradeep Kumar Mishra and Rana Barua. A Parallel Algorithm for Computing Simultaneous Inversions with Application to Elliptic Curve Scalar Multiplication. IEEE MSCAS, 2003 (link).

• Proposes a parallel algorithm for performing simultaneous inversions of several field elements.

Pradeep Kumar Mishra and Palash Sarkar. Parallelizing Explicit Formula for Arithmetic in the Jacobian of Hyperelliptic Curves. Asiacrypt, 2003 (link)

• Develops a general methodology for identifying parallelism in explicit formulas for arithmetic in the Jacobian of hyperelliptic curves.
• Applies the methodology to best known explicit formulas to obtain parallel versions of such formulas.

Top

Pairing based cryptography


Pairing computation

M. Prem Laxman Das and Palash Sarkar. Pairing Computation on Twisted Edwards Form Elliptic Curves. Pairing, 2008 (link).

• The first work to systematically consider pairing computation over twisted Edwards form Elliptic curves.

Sanjit Chatterjee, Palash Sarkar and Rana Barua. Efficient Computation of Tate Pairing in Projective Coordinate Over General Characteristic Fields. ICISC, 2004 (link).

• The first paper to propose encapsulated point and line computation for Tate pairing.

Identity-based encryption

Somindu C. Ramanna, Palash Sarkar. Efficient Adaptively Secure IBBE from the SXDH Assumption. IEEE Transactions on Information Theory, 2016 (link).

• Describes the first constructions of identity-based broadcast encryption using Type-3 pairings, which can be proved secure against adaptive-identity attacks based on the Symmetric eXternal Diffie-Hellman assumption achieving a security degradation which is not exponential in the size of the target identity set.

Somindu C. Ramanna, Sanjit Chatterjee and Palash Sarkar.  Variants of Waters' Dual System Primitives Using Asymmetric Pairings. PKC, 2012 (link).
Sanjit Chatterjee and Palash Sarkar. Practical hybrid (hierarchical) identity-based encryption schemes based on the decisional bilinear Diffie-Hellman assumption. International Journal of Applied Cryptography, 2013 (link).
Sanjit Chatterjee and Palash Sarkar. Trading Time for Space: Towards an Efficient IBE Scheme with Short(er) Public Parameters in the Standard Model. ICISC, 2005 (link).

• The above papers provide constructions of best known identity-based encryption schemes under various conditions.

Hierarchical identity-based encryption

Somindu C. Ramanna and Palash Sarkar. Efficient (Anonymous) Compact HIBE From Standard Assumptions. ProvSec, 2014 (link).
Somindu C. Ramanna and Palash Sarkar. Anonymous Constant-Size Ciphertext HIBE From Asymmetric Pairings. IMACC, 2013 (link).
Palash Sarkar and Sanjit Chatterjee. Construction of a Hybrid Hierarchical Identity Based Encryption Protocol Secure Against Adaptive Attacks (Without Random Oracle). ProvSec, 2007 (link).
Sanjit Chatterjee and Palash Sarkar. HIBE with Short Public Parameters Without Random Oracle. Asiacrypt, 2006 (link).
Sanjit Chatterjee and Palash Sarkar. New Constructions of Constant Size Ciphertext HIBE Without Random Oracle. ICISC, 2006 (link).
Sanjit Chatterjee and Palash Sarkar. Generalization of the Selective-ID Security Model for HIBE Protocols. PKC, 2006 (link).

• The above papers provide constructions of best known hierarchical identity-based encryption schemes under various conditions.

Multi-party key agreement

Ratna Dutta, Rana Barua and Palash Sarkar. Provably Secure Authenticated Tree Based Group Key Agreement. ICICS, 2004 (link).
Rana Barua, Ratna Dutta and Palash Sarkar. Extending Joux's Protocol to Multiparty Key Agreement. Indocrypt, 2003 (link).

• The above papers extend Joux's 3-party key agreement scheme to a multiparty key agreement scheme.

Top

Discrete logarithm computation

Function field sieve

• Performs a new record discrete logarithm computation over a 1051-bit field having a 22-bit characteristic.
• Reported in the list of discrete logarithm computations.
  

• The initial splitting algorithm is highly parallelisable.

• Introduces new ideas supported by detailed asymptotic as well as concrete analysis to improve the efficiency and coverage of the function field sieve algorithm for the medium prime case.
• Performed two record discrete logarithm computations which are reported in the list of discrete logarithm computations.
  

• Presents a unified polynomial selection method for discrete logarithm computation using the number field sieve algorithm.
• The new method subsumes all previously known methods.
• For certain classes of primes the new method provides the best known complexity.

• Provides improved polynomial selection methods for variants of the number field sieve algorithm.

• Performs an extensive concrete analysis of improvements in number field sieve based discrete logarithm computation over finite fields and provides recommendations for field sizes to be chosen for pairing-based cryptography.

• Identifies special cases where obtaining relations does not require solving a multi-variate system of polynomial equations, as is required by Nagao's and Joux-Vitse's methods.

• Provides practical efficiency improvement upon a 17-year old method due to Gaudry.

Lattice based cryptography

• Performs a detailed concrete analysis of the seminal worst-to-average case reduction by Lyubashevsky, Peikert, and Regev from approximate SIVP to DLWE problem in ideal lattices.
• Concrete analyses of a number of other related reductions are also performed.
• All of these concrete analyses show that such reductions do not provide any security assurance for practical cryptosystems based on ideal lattices.

• Performs a concrete analysis and shows that the tightness gap is very large.

• Peforms a concrete analysis of an important step of Regev's seminal reduction.

• Discusses nontightness of security reductions in connection with complexity leveraging, HMAC, lattice-based cryptography, identity-based encryption, and hybrid encryption.
• The first paper to perform a concrete analysis of Regev's seminal work on worst-to-average case reduction.
• Recipient of the best paper award

• The first work to systematically examine problems with nontight security reductions arising in the multi-user setting.
• Problematic issues are highlighted for deterministic MAC schemes, network authentication, aggregate MACs, authenticated encryption schemes, disk encryption schemes, and stream ciphers.

Top

• Proposes a new blockchain protocol which supports multi-stage proof-of-work and works in a manner similar to pipelining in hardware architectures.
• Alleviates the scaling problem of the Bitcoin cryptocurrency.

• Models protocol stability and security using the formalism of voting games and identifies security notions arising out of such formalism.

• Provides the first non-trivial lower bound on the universal constant in the Fourier Min-Entropy/Influence Conjecture.

• Introduces and extensively analyses the definition of influence of a set of variables on a Boolean function based on the auto-correlation function.

• Fully settles the ``Majority is Least stable'' Conjecture.

• Uses the notion of influence to show separation between several important Boolean function classes.

Top

• Provides counts of various sub-classes of unate and monotone Boolean functions.

Top

• The first paper to use voting games to model security and protocol stability of proof-of-work cryptocurrencies.

• Uses the formalism of voting games to perform a comprehensive analysis of the voting procedure in the Goods and Services Tax Council of India, and provides suggestions for improving the voting procedure.

• Introduces the idea of measuring inequality in voting power profile and using such measurement to design more meaningful voting games for international voting bodies.

• Provides a two-axiom characterisation.

• Uses Walsh transform to analyse voting power and obtain upper and lower bounds on the number of swings of a player.

Top

• Introduces the idea of minimising inequality in post-tax income distribution and characterises the tax distribution which achieves such minimum inequality.

• Introduces the idea of constructing income distributions which achieve a target inequality and provides methods for constructing such distributions.

• Identifies Simpson like paradox exhibited by the Gini and Bonferroni indices of inequality.

• Shows that the value of the Bonferroni index is always at least as much as that of the Gini index.

Top

• Provides efficient construction of such squares using techniques from network flow analysis.

• Provides simple constructions of such designs using one-factorisation of a graph.

Top

• Provides a general algorithm to compute the shifts between the sequences produced by any two cells of such automata.

• Performs an extensive algebraic analysis of sigma-automata on multidimensional grids.

• Shows that the set of all strings which encode reversible 90/150 cellular automata forms a regulare language.

• Obtains algebraic conditions related to the reversibility of such automata.

• Points out several statistical procedures whose justification lies in inductive inference.

• Shows that the core of some important modern philosophical ideas can be traced to Carvaka philosophy.

• Performs an extensive and unified analysis of Simpson's paradox in 2x2 contingency tables and relates the paradox to broader philosophical issues.

Top

• Uses the extended SIR model and symbolic computations using SAGE to show that in theory efficient detection and isolation can control an epidemic.

• Introduces a new class of pushdown automaton and identifies an infinite hierarchy of languages from the class of context-free languages to the class of recursively enumerable languages.

Top