Now showing 1 - 10 of 91
  • Placeholder Image
    Publication
    Concentration and Tail Bounds for Missing Mass
    (01-07-2019)
    Chandra, Prafulla
    ;
    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.
  • Placeholder Image
    Publication
    Confidential messages to a cooperative relay
    (22-09-2008)
    Bloch, Matthieu
    ;
    We extend the broadcast channel with confidential messages to the situation where the receiver of the secret message also serves as a relay. We analyze the fundamental cooperation versus secrecy trade-offs for discrete memoryless channels and obtain the exact rate-equivocation region in this case. For the Gaussian channel, we consider various strategies leading to different levels of secrecy. Our study highlights the fundamental role of jamming as a means to increase secrecy rates, but also emphasizes the importance of carefully designed relaying strategies. ©2008 IEEE.
  • Placeholder Image
    Publication
    Robustness of physical layer security primitives against attacks on pseudorandom generators
    (01-01-2014)
    Vaidyanathaswami, Rajaraman
    ;
    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.
  • Placeholder Image
    Publication
    Effects of reader distortion on nonlinear transition shift measurements
    (01-01-2005)
    Prabhakar, A.
    ;
    ;
    Manikam, M.
    ;
    Louis, E.
  • Placeholder Image
    Publication
    Quasi-cyclic regenerating codes for distributed storage: Existence and near-MSR examples
    (19-12-2013)
    Vignesh, G.
    ;
    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.
  • Placeholder Image
    Publication
    Self-orthogonality of images and traces of codes with applications to quantum codes
    (01-12-2007)
    Sundeep, B.
    ;
    A code over GF(qm) can be imaged or expanded into a code over GF(q) using a basis for the extension field over the base field. In this work, a generalized version of the problem of self-orthogonality of the q-ary image of a qm-ary code has been considered. Given an inner product (more generally, a biadditive form), necessary and sufficient conditions have been derived for a code over a field extension and an expansion basis so that an image of that code is self-orthogonal. The conditions require that the original code be self-orthogonal with respect to several related biadditive forms whenever certain power sums of the dual basis elements do not vanish. The conditions are particularly simple to state and apply for cyclic codes. As a possible application, new quantum error-correcting codes have been constructed with larger minimum distance than previously known. ©2007 IEEE.
  • Placeholder Image
    Publication
    Codes on planar tanner graphs
    (01-05-2012)
    Srinivasan, Srimathy
    ;
    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.
  • Placeholder Image
    Publication
    Efficient Maximum-Likelihood Decoding of Reed-Muller RM(m-3,m) Codes
    (01-06-2020) ;
    Pfister, Henry D.
    Reed-Muller (RM) codes, a classical family of codes known for their elegant algebraic structure, have recently been shown to achieve capacity under maximum-likelihood (ML) decoding on the binary erasure channel and this has rekindled interest in their efficient decoding. We consider the code family RM(m-3,m) and develop a new ML decoder, for transmission over the binary symmetric channel, that exploits their large symmetry group. The new decoder has lower complexity than an earlier method introduced by Seroussi and Lempel in 1983.
  • Placeholder Image
    Publication
    Wiretap Polar Codes in Encryption Schemes Based on Learning with Errors Problem
    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.
  • Placeholder Image
    Publication
    NLHB: A light-weight, provably-secure variant of the HB protocol using simple non-linear functions
    (18-05-2010)
    Madhavan, Mukundan
    ;
    ;
    Viswanathan, Kapali
    ;
    Sankarasubramaniam, Yogesh
    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.