Andrew Thangaraj

The missing mass of a sequence is defined as the total probability of the elements that have not appeared or occurred in the sequence. Estimation of missing mass is an important ingredient in many practical applications in language modeling and ecology. Exponential tail bounds have been known for missing mass, and improving them results in better confidence in estimation. In this work, we improve upon the best-known left and right tail bounds for missing mass. For the left tail, our proof method is arguably simpler than prior methods and provides a better bound for small sample sizes. For the right tail, we provide a new bounding method for the moment generating function of a generalized version of missing mass that results in a noticeable improvement in the tail bound.

Physical layer security protocols exploit inviolable physical laws at the signal level for providing guarantees on secrecy of communications. These protocols invariably involve randomized encoding at the transmitter, for which an ideal random number generator is typically assumed in the literature. In this work, we study the impact of using weak Pseudo Random Number Generators (PRNGs) in physical layer security protocols for coding and forward key distribution over Binary Symmetric and Gaussian wiretap channels. In the case of wiretap channel coding, we study fast correlation attacks that aim to retrieve the initial seed used in the PRNGs. Our results show that randomized coset encoding, which forms an important part of wiretap channel coding, provides useful robustness against fast correlation attacks. In the case of single-round or forward key distribution over a Gaussian wiretap channel, the bits from a PRNG are nonlinearly transformed to generate Gaussian-distributed pseudo random numbers at the transmitter. In such cases, we design modified versions of the fast correlation attacks accounting for the effects of the nonlinear transformation and soft input. We observe that, even for moderately high memory, the success probability of the modified fast correlation attacks become the same as that of a random guess in many cases. © 2014 IEEE.

Regenerating codes for distributed storage systems promise significant improvements in the cost and maintenance requirements of large-scale data centers. Research in this area continues to define important new parameters and requirements that have the biggest impact in practice. One of the simplest requirements for a regenerating code is the so-called MSR property, which minimizes the number of bits downloaded during repair. Quasi-cyclic MSR codes are of particular interest, mainly for reducing the encoding and decoding complexity. However, quasi-cyclic MSR codes have not been studied in detail in the existing literature. In this work, we prove the negative result that quasi-cyclic MSR codes with no symbol extension do not exist if the number of systematic nodes is greater than or equal to 4. We provide several examples of quasi-cyclic near-MSR codes, which could be useful for reducing implementation complexity. We point out some interesting connections between zeros of quasi-cyclic codes and the MSR requirement, which are useful in the study of quasi-cyclic regenerating codes with symbol extension. © 2013 IEEE.

Codes defined on graphs and their properties have been subjects of intense recent research. In this work, we are concerned with codes that have planar Tanner graphs. When the Tanner graph is planar, message-passing decoders can be efficiently implemented on chips without any issues of wiring. Also, recent work has shown the existence of optimal decoders for certain planar graphical models. The main contribution of this paper is an explicit upper bound on minimum distance d of codes that have planar Tanner graphs as a function of the code rate R for R ≥ 5/8. The bound is given by As a result, high-rate codes with planar Tanner graphs will result in poor block-error rate performance, because of the constant upper bound on minimum distance. © 2012 AIMS.

The Learning with Errors (LWE) problem has been extensively studied in cryptography due to its strong hardness guarantees, efficiency and expressiveness in constructing advanced cryptographic primitives. In this work, we show that using polar codes in conjunction with LWE-based encryption yields several advantages. To begin, we demonstrate the obvious improvements in the efficiency or rate of information transmission in the LWE-based scheme by leveraging polar coding (with no change in the cryptographic security guarantee). Next, we integrate wiretap polar coding with LWE-based encryption to ensure provable semantic security over a wiretap channel in addition to cryptographic security based on the hardness of LWE. To the best of our knowledge this is the first wiretap code to have cryptographic security guarantees as well. Finally, we study the security of the private key used in LWE-based encryption with wiretap polar coding, and propose a key refresh method using random bits used in wiretap coding. Under a known-plaintext attack, we show that non-vanishing information-theoretic secrecy can be achieved for the key. We believe our approach is at least as interesting as our final results: our work combines cryptography and coding theory in a novel 'non blackbox-way' which may be relevant to other scenarios as well.

In this paper, we propose a light-weight provably-secure authentication protocol called the NLHB protocol, which is a variant of the HB protocol [6]. The HB protocol uses the complexity of decoding linear codes for security against passive attacks. In contrast, security for the NLHB protocol is proved by reducing the provably hard problem of decoding a class of nonlinear codes to passive attacks. We demonstrate that the existing passive attacks([10],[3]) on the HB protocol family, which have contributed to considerable reduction in its effective key-size, do not work against the NLHB protocol. From the evidence, we conclude that smaller-key sizes are sufficient for the NLHB protocol to achieve the same level of passive attack security as the HB Protocol. Further, for this choice of parameters, we provide an implementation instance for the NLHB protocol for which the Prover/Verifier complexity is lower than the HB protocol, enabling authentication on very low-cost devices like RFID tags. ©2010 IEEE.

The problem of estimating the missing mass or total probability of unseen elements in a sequence of n random samples is considered under the squared error loss function. The worst-case risk of the popular Good-Turing estimator is shown to be between 0.6080/n and 0.6179/n. The minimax risk is shown to be lower bounded by 0.25/n. This appears to be the first such published result on minimax risk for estimation of missing mass, which has several practical and theoretical applications.

Binary-input memoryless channels with a run length constrained input are considered. Upper bounds to the capacity of such noisy run length constrained channels are derived using the dual capacity method with Markov test distributions satisfying the Karush-Kuhn-Tucker conditions for the capacity-Achieving output distribution. Simplified algebraic characterizations of the bounds are presented for the binary erasure channel and the binary symmetric channel. These upper bounds are very close to achievable rates, and improve upon previously known feedback-based bounds for a large range of channel parameters. For the binary-input additive white Gaussian noise channel, the upper bound is simplified to a small-scale numerical optimization problem. These results provide some of the simplest upper bounds for an open capacity problem that has theoretical and practical relevance.

Protograph doubly-generalized low-density parity-check (DGLDPC) codes, which allow for arbitrary component codes at the variable and check nodes of a protograph, are considered. Exact density evolution is derived over the binary erasure channel. Conditions on the protograph and component codes to ensure equality of block-error threshold and density evolution threshold for large-girth ensembles are established. Conditions for stability of density evolution are derived, and block-error threshold property is extended to binary-input symmetric channels. Optimized low-rate protographs for DGLDPC codes over the erasure channel are presented.

Interference in wireless networks results in interdependent communication links between the nodes. Therefore, cross-layer design is essential and makes optimization of wireless networks complicated. In this paper, we study the problem of maximizing the information flow for a multicast session over a wireless network. Different scheduling and coding strategies to handle the interference, including the commonly used interference avoidance strategy, are compared. Results in information theory on achievable rate regions for interference networks are incorporated in the flow optimization to achieve significant improvement. Numerical results illustrate that processing interference at the physical layer results in better information flow compared to interference avoidance. © 2011 IEEE.