Abstract: Presents a listing of the editorial board, board of governors, current staff, committee members, and/or society editors for this issue of the publication. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Abstract: Presents a listing of the editorial board, board of governors, current staff, committee members, and/or society editors for this issue of the publication. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Maiara F. Bollauf;Ram Zamir;Sueli I. R. Costa;
Pages: 7669 - 7681 Abstract: Lattice and special nonlattice multilevel constellations constructed from binary codes, such as Constructions A, C, and D, have relevant applications in Mathematics (sphere packing) and in Communication (multi-stage decoding and efficient vector quantization). In this work, we explore some properties of Construction C, in particular its geometric uniformity. We then propose a new multilevel construction, inspired by bit interleaved coded modulation (BICM), that we call Construction $C^star $ . We investigate the geometric uniformity, latticeness, and minimum distance properties of Construction $C^star $ , and discuss its superior packing efficiency when compared to Construction C. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Ryan Gabrys;Olgica Milenkovic;
Pages: 7682 - 7696 Abstract: The problem of reconstructing strings from their substring spectra has a long history and in its most simple incarnation asks for determining under which conditions the spectrum uniquely determines the string. We study the problem of coded string reconstruction from multiset substring spectra, where the strings are restricted to lie in some codebook. In particular, we consider binary codebooks that allow for unique string reconstruction and propose a new method, termed repeat replacement, to create the codebook. Our contributions include algorithmic solutions for repeat replacement and constructive redundancy bounds for the underlying coding schemes. We also consider extensions of the problem to noisy settings in which substrings are compromised by burst and random errors. The study is motivated by applications in DNA-based data storage systems that use high throughput readout sequencers. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Nicolas Aragon;Philippe Gaborit;Adrien Hauteville;Olivier Ruatta;Gilles Zémor;
Pages: 7697 - 7717 Abstract: We introduce a new family of rank metric codes: Low Rank Parity Check codes (LRPC), for which we propose an efficient probabilistic decoding algorithm. This family of codes can be seen as the equivalent of classical LDPC codes for the rank metric. We then use these codes to design cryptosystems Ã la McEliece: more precisely we propose two schemes for key encapsulation mechanism (KEM) and public key encryption (PKE). Unlike rank metric codes used in previous encryption algorithms -notably Gabidulin codes - LRPC codes have a very weak algebraic structure. Our cryptosystems can be seen as an equivalent of the NTRU cryptosystem (and also to the more recent MDPC code-based cryptosystem) in a rank metric context, due to the similar form of the public keys. The present paper is an extended version of the article introducing LRPC codes, with important new contributions. We have improved the decoder thanks to a new approach which allows for decoding of errors of higher rank weight, namely up to $frac {2}{3}(n-k)$ when the previous decoding algorithm only decodes up to $frac {n-k}{2}$ errors. Our codes therefore outperform the classical Gabidulin code decoder which deals with weights up to $frac {n-k}{2}$ . This comes at the expense of probabilistic decoding, but the decoding error probability can be made arbitrarily small. The new approach can also be used to decrease the decoding error probability of previous schemes, which is especially useful for cryptography. Finally, we introduce ideal rank codes, which generalize double-circulant rank codes and allow us to avoid known structural attacks based on folding. To conclude, we propose different parameter sizes for our schemes and we obtain a public key of 3337 bits for key exchange and 589- bits for public key encryption, both for 128 bits of security. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Hermann Tchatchiem Kamche;Christophe Mouaha;
Pages: 7718 - 7735 Abstract: In this paper, it is shown that some results in the theory of rank-metric codes over finite fields can be extended to finite commutative principal ideal rings. More precisely, the rank metric is generalized and the rank-metric Singleton bound is established. The definition of Gabidulin codes is extended and it is shown that its properties are preserved. The theory of Gröbner bases is used to give the unique decoding, minimal list decoding, and error-erasure decoding algorithms of interleaved Gabidulin codes. These results are then applied in space-time codes and in random linear network coding as in the case of finite fields. Specifically, two existing encoding schemes of random linear network coding are combined to improve the error correction. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Ángel Luis Muñoz Castañeda;José M. Muñoz-Porras;Francisco J. Plaza-Martín;
Pages: 7736 - 7741 Abstract: The performance of Rosenthal’s decoding algorithm is measured when it is applied to certain family of 1-dimensional MDS convolutional codes. It is shown that the performance of this algorithm depends on the algebraic structure of the convolutional code we are working with. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Tianqiong Luo;Vaneet Aggarwal;Borja Peleato;
Pages: 7742 - 7755 Abstract: Content delivery networks store information distributed across multiple servers, so as to balance the load and avoid unrecoverable losses in case of node or disk failures. Coded caching has been shown to be a useful technique which can reduce peak traffic rates by pre-fetching popular content at the end users and encoding transmissions so that different users can extract different information from the same packet. On one hand, distributed storage limits the capability of combining content from different servers into a single message, causing performance losses in coded caching schemes. But, on the other hand, the inherent redundancy existing in distributed storage systems can be used to improve the performance of those schemes through parallelism. This paper designs coded caching and delivery schemes tailored towards systems where the library is distributed across multiple servers, possibly with some redundancy in the form of maximum distance separable (MDS) erasure codes. Different schemes are proposed based on the capacity of the users’ caches, as well as the number of parity servers. The main focus is on scenarios with one (RAID-4) or two (RAID-6) parity servers, but the paper also includes simple extensions for cases with more than two or no parity servers at all. The proposed schemes are shown to reduce the worst case latency, or equivalently the peak transmission rate from any server, below that of state-of-the-art algorithms. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Saeid Sahraei;Pierre Quinton;Michael Gastpar;
Pages: 7756 - 7770 Abstract: A new scheme for the problem of centralized coded caching with non-uniform demands is proposed. The distinguishing feature of the proposed placement strategy is that it admits equal sub-packetization for all files while allowing the users to allocate more cache to the files which are more popular. This creates natural broadcasting opportunities in the delivery phase which are simultaneously helpful for the users who have requested files of different popularities. For the case of two files, we propose a new delivery strategy based on interference alignment which enables each user to decode his desired file following a two-layer peeling decoder. Furthermore, we extend the existing converse bounds for uniform demands under uncoded placement to the nonuniform case. To accomplish this, we construct $N!$ auxiliary users, corresponding to all permutations of the $N$ files, each caching carefully selected sub-packets of the files. Each auxiliary user provides a different converse bound. The overall converse bound is the maximum of all these $N!$ bounds. We prove that our achievable delivery rate for the case of two files meets this converse, thereby establishing the optimal expected memory-rate trade-off for the case of $K$ users and two files with arbitrary popularities under uncoded placement. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
N. Prakash;V. Lalitha;S. B. Balaji;P. Vijay Kumar;
Pages: 7771 - 7789 Abstract: Codes with locality are a class of codes introduced by Gopalan et al. to efficiently repair a failed node, by minimizing the number of nodes contacted during repair. An $[n,k]$ systematic code is said to have information locality $r$ , if each message symbol can be recovered by accessing $leq r$ other symbols. An $[n,k]$ code is said to have all-symbol locality $r$ , if each code symbol can be recovered by accessing $leq r$ other symbols. In this paper, we consider a generalization of codes with all-symbol locality to the case of handling two erasures. We study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. We refer to these codes as sequential-recovery locally repairable codes (denoted by 2-seq LR codes). Earlier approaches to handling multiple erasures considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. We derive an upper bound on the rate of 2-seq LR codes. We provide constructions based on regular graphs which are rate-optimal with respect to the derived bound. We also characterize the structure of any rate-optimal code. By studying the Generalized Hamming Weights of the dual code, we derive a recursive upper bound on the minimum distance of 2-seq LR codes. We also provide constructions of a family of codes based on Turán graphs, that are optimal with respect to this bound. We also present explicit distance-optimal Turán graph-based constructions of 2-seq LR codes for certain parameters. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Umberto Martínez-Peñas;Frank R. Kschischang;
Pages: 7790 - 7805 Abstract: Locally repairable codes (LRCs) are considered with equal or unequal localities, local distances, and local field sizes. An explicit two-layer architecture with a sum-rank outer code is obtained, having disjoint local groups and achieving maximal recoverability (MR) for all families of local linear codes (MDS or not) simultaneously, up to a specified maximum locality $r $ . Furthermore, the local linear codes (thus the localities, local distances, and local fields) can be efficiently and dynamically modified without global recoding or changes in architecture or outer code, while preserving the MR property, easily adapting to new configurations in storage or new hot and cold data. In addition, local groups and file components can be added, removed or updated without global recoding. The construction requires global fields of size roughly $g^{r} $ , for $g $ local groups and maximum or specified locality $r $ . For equal localities, these global fields are smaller than those of previous MR-LRCs when $r leq h $ (global parities). For unequal localities, they provide an exponential field size reduction on all previous best known MR-LRCs. For bounded localities and a large number of local groups, the global erasure-correction complexity of the given construction is comparable to that of Tamo–Barg codes or Reed–Solomon codes with local replication, while local repair is as efficient as for the Cartesian product of the local codes. Reed–Solomon codes with local replication and Cartesian products are recovered from the given construction when $r=1 $ and $h = 0 $ , respectively. The given construction can also be adapted to provide hierarchical MR-LRCs for all types of hierarchies and parameters. Finally, subextension subcodes and sum-rank alternant codes are introduced to obtain further exponential field size reductions, at the expense of lower information rates. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Justin Kong;
Pages: 7806 - 7828 Abstract: Permutation and multipermutation codes in the Ulam metric have been suggested for use in non-volatile memory storage systems such as flash memory devices. In this paper we introduce a new method to calculate permutation ball sizes in the Ulam metric using Young Tableaux and prove the non-existence of non-trivial perfect permutation codes in the Ulam metric. We then extend the study to multipermutations, providing upper and lower bounds on multipermutation Ulam ball sizes and resulting upper and lower bounds on the maximal size of multipermutation codes in the Ulam metric. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Yang Liu;Ruihu Li;Guanmin Guo;Junli Wang;
Pages: 7829 - 7839 Abstract: Let $q$ be a prime power and $mgeq 3$ be odd. Suppose that $n=frac {q^{2m}-1}{a}$ with $a (q^{m}+1)$ and $3leq a leq 2(q^{2}-q+1)$ . This paper mainly determines the actual maximum designed distance of Hermitian dual-containing Bose-Chaudhuri-Hocquenghem (BCH) codes over $mathbb {F}_{q^{2}}$ of length $n$ . Firstly, we give the maximum designed distance $delta _{m,a}^{R}$ of narrow-sense Hermitian dual-containing BCH codes. Secondly, we show that there are also non-narrow-sense ones of designed distance up to $delta _{m,a}^{R}$ . It is worth mentioning that our maximum designed distance $delta _{m,a}^{R}>lceil frac {a}{2}rceil delta _{m}^{A}$ , where $delta _{m}^{A}$ is given by Aly et al. (IEEE Trans. Inf. Theory, vol. 53, no. 3, pp. 1183-1188, 2007). Thus, many families of Hermitian dual-containing BCH codes with relatively large designed distance are obtained. Using the Hermitian construction to them, we can subsequently construct different classes of nonprimitive quantum codes, which are new in the sense that their parameters are not covered in the literature. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Weijun Fang;Fang-Wei Fu;
Pages: 7840 - 7847 Abstract: It is an important task to construct quantum maximum-distance-separable (MDS) codes with good parameters. In the present paper, we provide six new classes of $q$ -ary quantum MDS codes by using generalized Reed–Solomon (GRS) codes and Hermitian construction. The minimum distances of our quantum MDS codes can be larger than $frac {q}{2}+1$ . Three of these six classes of quantum MDS codes have longer lengths than the ones constructed in [1] and [2], hence some of their results can be easily derived from ours via the propagation rule. Moreover, some known quantum MDS codes of specific lengths can be seen as special cases of ours and the minimum distances of some known quantum MDS codes are also improved as well. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

$b$+
-Symbol+Distances+of+Repeated-Root+Constacyclic+Codes&rft.title=IEEE+Transactions+on+Information+Theory&rft.issn=0018-9448&rft.date=2019&rft.volume=65&rft.spage=7848&rft.epage=7867&rft.aulast=Sidana;&rft.aufirst=Anuradha&rft.au=Anuradha+Sharma;Tania+Sidana;">On $b$
-Symbol Distances of Repeated-Root Constacyclic Codes

Authors:
Anuradha Sharma;Tania Sidana;
Pages: 7848 - 7867 Abstract: Let $p$ be a prime, $s$ be a positive integer, and let $b$ be an integer satisfying $2 leq b < p^{s}$ . In this paper, we obtain $b$ -symbol distances of all repeated-root constacyclic codes of length $p^{s}$ over finite fields. Using this result, we determine $b$ -symbol distances of all repeated-root constacyclic codes of length $p^{s}$ over finite commutative chain rings. We also list all MDS $b$ -symbol repeated-root constacyclic codes of length $p^{s}$ over finite fields, and all MDS $b$ -symbol repeated-root constacyclic codes of length $p^{s}$ over finite commutative chain rings in general. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Hikmet Yildiz;Babak Hassibi;
Pages: 7868 - 7875 Abstract: We consider the problem of designing optimal linear codes (in terms of having the largest minimum distance) subject to a support constraint on the generator matrix. We show that the largest minimum distance can be achieved by a subcode of a Reed–Solomon code of small field size and with the same minimum distance. In particular, if the code has length $n$ , and maximum minimum distance $d$ (over all generator matrices with the given support), then an optimal code exists for any field size $qgeq 2n-d$ . As a by-product of this result, we settle the GM–MDS conjecture in the affirmative. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Dabin Zheng;Mu Yuan;Nian Li;Lei Hu;Xiangyong Zeng;
Pages: 7876 - 7883 Abstract: An involution over finite fields is a permutation polynomial whose inverse is itself. Owing to this property, involutions over finite fields have been widely used in applications, such as cryptography and coding theory. Following the idea by Wang to characterize the involutory behavior of the generalized cyclotomic mappings, this paper gives a more concise criterion for $x^{r}h(x^{s})in {mathbb F} _{q}[x]$ being involutions over the finite field ${mathbb F}_{q}$ , where $rgeq 1$ and $s, , (q-1)$ . By using this criterion, we propose a general method to construct involutions of the form $x^{r}h(x^{s})$ over ${mathbb F}_{q}$ from given involutions over some subgroups of ${mathbb F}_{q}^{*}$ by solving congruent and linear equations over finite fields. Then, many classes of explicit involutions of the form $x^{r}h(x^{s})$ over ${mathbb F}_{q}$ are obtained. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Sihem Mesnager;Longjiang Qu;
Pages: 7884 - 7895 Abstract: Two-to-one (2-to-1) mappings over finite fields play an important role in symmetric cryptography. In particular they allow to design APN functions, bent functions and semi-bent functions. In this paper we provide a systematic study of two-to-one mappings that are defined over finite fields. We characterize such mappings by means of the Walsh transforms. We also present several constructions, including an AGW-like criterion, constructions with the form of $x^{r}h(x^{(q-1)/d})$ , those from permutation polynomials, from linear translators and from APN functions. Then we present 2-to-1 polynomial mappings in classical classes of polynomials: linearized polynomials and monomials, low degree polynomials, Dickson polynomials and Muller-Cohen-Matthews polynomials, etc. Lastly, we show applications of 2-to-1 mappings over finite fields for constructions of bent Boolean and vectorial bent functions, semi-bent functions, planar functions and permutation polynomials. In all those respects, we shall review what is known and provide several new results. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Ali Bereyhi;Ralf R. Müller;Hermann Schulz-Baldes;
Pages: 7896 - 7934 Abstract: The large-system performance of maximum-a-poste-rior estimation is studied considering a general distortion function when the observation vector is received through a linear system with additive white Gaussian noise. The analysis considers the system matrix to be chosen from the large class of rotationally invariant random matrices. We take a statistical mechanical approach by introducing a spin glass corresponding to the estimator, and employing the replica method for the large-system analysis. In contrast to earlier replica based studies, our analysis evaluates the general replica ansatz of the corresponding spin glass and determines the asymptotic distortion of the estimator for any structure of the replica correlation matrix. Consequently, the replica symmetric as well as the replica symmetry breaking ansatz with $b$ steps of breaking is deduced from the given general replica ansatz. The generality of our distortion function lets us derive a more general form of the maximum-a-posterior decoupling principle. Based on the general replica ansatz, we show that for any structure of the replica correlation matrix, the vector-valued system decouples into a bank of equivalent decoupled scalar systems followed by maximum-a-posterior estimators. The structure of the decoupled system is further studied under both the replica symmetry and the replica symmetry breaking assumptions. For $b$ steps of symmetry breaking, the decoupled system is found to be an additive system with a non-Gaussian noise term given as the sum of an independent Gaussian random variable with $b$ non-Gaussian impairment terms which depend on the input symbol. The general decoupling property of the maximum-a-posterior estimator leads to the idea of a replica simulator wh-ch represents the replica ansatz through the state evolution of a transition system described by its corresponding decoupled system. As an application of our study, we investigate large compressive sensing systems by considering the $ell _{p}$ norm minimization recovery schemes. Our numerical investigations show that the replica symmetric ansatz for $ell _{0}$ norm recovery fails to give an accurate approximation of the mean square error as the compression rate grows, and therefore, the replica symmetry breaking ansätze are needed in order to assess the performance precisely. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Holger Boche;Ullrich J. Mönich;
Pages: 7935 - 7949 Abstract: The tone reservation method can be used to reduce the peak to average power ratio (PAPR) in orthogonal frequency division multiplexing (OFDM) transmission systems. In this paper, the tone reservation method is analyzed for OFDM with a restricted carrier set, where only the positive carrier frequencies are used. Performing a fully analytical analysis, we give a complete characterization of the information sets for which the PAPR problem is solvable. To derive our main result, we connect the PAPR problem with a geometric functional analytic property of certain spaces. Furthermore, we present applications of our theory that give guidelines for choosing the information carriers in the finite setting and discuss a probabilistic approach for selecting the carriers. In addition, it is shown that if there exists an information sequence for which the PAPR problem is not solvable, then the set of information sequences for which the PAPR problem is not solvable is a residual set. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Vladislav Z. B. Tadić;Arnaud Doucet;
Pages: 7950 - 7975 Abstract: The analyticity of the entropy and relative entropy rates of continuous-state hidden Markov models is studied here. Using the analytic continuation principle and the stability properties of the optimal filter, the analyticity of these rates is established for analytically parameterized models. The obtained results hold under relatively mild conditions and cover several useful classes of hidden Markov models. These results are relevant for several theoretically and practically important problems arising in statistical inference, system identification and information theory. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Soham Jana;Ayanendranath Basu;
Pages: 7976 - 7984 Abstract: Divergence measures have been used for a long time for different purposes in information theory and statistics. In particular, density-based minimum divergence estimation is a popular tool in the statistical literature. Given the sampled data and a parametric model, we estimate the model parameter by choosing the member of the model family that is closest to the data distribution in terms of the given divergence. In the absolutely continuous set up, when the distributions from the model family and the unknown data generating distribution are assumed to have densities, the application of kernel based non-parametric smoothing is sometimes unavoidable to get an estimate of the true data density. The use of kernels (or other non-parametric smoothing techniques) makes the estimation process considerably more complex, as now one has to impose necessary conditions not just on the model but also on the kernel and its bandwidth. In higher dimensions the efficiency of the kernel density estimator (KDE) often becomes too low for the minimum divergence procedure to be practically useful. It can, therefore, lead to a significant advantage to have a divergence which allows minimum divergence estimation bypassing the use of non-parametric smoothing. For the same reason, characterizing the class of such divergences would be a notable achievement. In this work, we provide a characterization of the class of divergences that bypasses the use of non-parametric smoothing in the construction of divergences, providing a solution to this very important problem. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

$L_p$+
-Norms&rft.title=IEEE+Transactions+on+Information+Theory&rft.issn=0018-9448&rft.date=2019&rft.volume=65&rft.spage=7985&rft.epage=8004&rft.aulast=Aref;&rft.aufirst=Mohammad&rft.au=Mohammad+Mahdi+Mojahedian;Salman+Beigi;Amin+Gohari;Mohammad+Hossein+Yassaee;Mohammad+Reza+Aref;">A Correlation Measure Based on Vector-Valued $L_p$
-Norms

Authors:
Mohammad Mahdi Mojahedian;Salman Beigi;Amin Gohari;Mohammad Hossein Yassaee;Mohammad Reza Aref;
Pages: 7985 - 8004 Abstract: In this paper, we introduce a new measure of correlation for bipartite quantum states. This measure depends on a parameter $alpha $ , and is defined in terms of vector-valued $textit {L}_{textit {p}}$ -norms. The measure is within a constant of the exponential of $alpha $ -Rényi mutual information, and reduces to the trace norm (total variation distance) for $alpha =1$ . We will prove some decoupling type theorems in terms of this measure of correlation, and present some applications in privacy amplification as well as in bounding the random coding exponents. In particular, we establish a bound on the secrecy exponent of the wiretap channel (under the total variation metric) in terms of the $alpha $ -Rényi mutual information according to Csiszár’s proposal. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Shirin Jalali;Xin Yuan;
Pages: 8005 - 8024 Abstract: Snapshot compressed sensing (CS) refers to compressive imaging systems in which multiple frames are mapped into a single measurement frame. Each pixel in the acquired frame is a noisy linear mapping of the corresponding pixels in the frames that are combined together. While the problem can be cast as a CS problem, due to the very special structure of the sensing matrix, standard CS theory cannot be employed to study such systems. In this paper, a compression-based framework is employed for theoretical analysis of snapshot CS systems. It is shown that this framework leads to two novel, computationally-efficient and theoretically-analyzable compression-based recovery algorithms. The proposed methods are iterative and employ compression codes to define and impose the structure of the desired signal. Theoretical convergence guarantees are derived for both algorithms. In the simulations, it is shown that, in the cases of both noise-free and noisy measurements, combining the proposed algorithms with a customized video compression code, designed to exploit nonlocal structures of video frames, significantly improves the state-of-the-art performance. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Hao Wang;Lisa Vo;Flavio P. Calmon;Muriel Médard;Ken R. Duffy;Mayank Varia;
Pages: 8025 - 8042 Abstract: We study the central problem in data privacy: how to share data with an analyst while providing both privacy and utility guarantees to the user that owns the data. In this setting, we present an estimation-theoretic analysis of the privacy-utility trade-off (PUT). Here, an analyst is allowed to reconstruct (in a mean-squared error sense) certain functions of the data (utility), while other private functions should not be reconstructed with distortion below a certain threshold (privacy). We demonstrate how chi-square information captures the fundamental PUT in this case and provide bounds for the best PUT. We propose a convex program to compute privacy-assuring mappings when the functions to be disclosed and hidden are known a priori and the data distribution is known. We derive lower bounds on the minimum mean-squared error of estimating a target function from the disclosed data and evaluate the robustness of our approach when an empirical distribution is used to compute the privacy-assuring mappings instead of the true data distribution. We illustrate the proposed approach through two numerical experiments. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Jiachun Liao;Oliver Kosut;Lalitha Sankar;Flavio du Pin Calmon;
Pages: 8043 - 8066 Abstract: We introduce a tunable measure for information leakage called maximal $alpha $ -leakage. This measure quantifies the maximal gain of an adversary in inferring any (potentially random) function of a dataset from a release of the data. The inferential capability of the adversary is, in turn, quantified by a class of adversarial loss functions that we introduce as $alpha $ -loss, $alpha in [1,infty) cup {infty }$ . The choice of $alpha $ determines the specific adversarial action and ranges from refining a belief (about any function of the data) for $alpha =1$ to guessing the most likely value for $alpha = infty $ while refining the $alpha ^{text {th}}$ moment of the belief for $alpha $ in between. Maximal $alpha $ -leakage then quantifies the adversarial gain under $alpha $ -loss over all possible functions of the data. In particular, for the extremal values of $alpha =1$ and $alpha =infty $ , maximal $alpha $ -leakage simplifies to mutual information and maximal leakage, respectively. Fo- $alpha in (1,infty)$ this measure is shown to be the Arimoto channel capacity of order $alpha $ . We show that maximal $alpha $ -leakage satisfies data processing inequalities and a sub-additivity property thereby allowing for a weak composition result. Building upon these properties, we use maximal $alpha $ -leakage as the privacy measure and study the problem of data publishing with privacy guarantees, wherein the utility of the released data is ensured via a hard distortion constraint. Unlike average distortion, hard distortion provides a deterministic guarantee of fidelity. We show that under a hard distortion constraint, for $alpha>1$ the optimal mechanism is independent of $alpha $ , and therefore, the resulting optimal tradeoff is the same for all values of $alpha>1$ . Finally, the tunability of maximal $alpha $ -leakage as a privacy measure is also illustrated for binary data with average Hamming distortion as the utility measure. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Jingbo Liu;Mohammad Hossein Yassaee;Sergio Verdú;
Pages: 8067 - 8083 Abstract: A fundamental tool in network information theory is the covering lemma, which lower bounds the probability that there exists a pair of random variables; among a given number of independently generated candidates, falling within a given set. We use a weighted sum trick and Talagrand’s concentration inequality to prove new mutual covering bounds. We identify two interesting applications: 1) when the probability of the set under the given joint distribution is bounded away from 0 and 1, the covering probability converges to 1 doubly exponentially fast in the blocklength, which implies that the covering lemma does not induce penalties on the error exponents in the applications to coding theorems; and 2) using Hall’s marriage lemma, we show that the maximum difference between the probability of the set under the joint distribution and the covering probability equals half the minimum total variation distance between the joint distribution and any distribution that can be simulated by selecting a pair from the candidates. Thus we use the mutual covering bound to derive the exact error exponent in the joint distribution simulation problem. In both applications, the determination of the exact exponential (or double exponential) behavior relies crucially on the sharp concentration inequality used in the proof of the mutual covering lemma. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Axel Flinth;Sandra Keiper;
Pages: 8084 - 8094 Abstract: This paper treats the recovery of sparse, binary signals through box-constrained basis pursuit using biased measurement matrices. Using a probabilistic model, we provide conditions under which the recovery of both sparse and saturated binary signals is very likely. In fact, we also show that under the same condition, the solution of the boxed-constrained basis pursuit program can be found using boxed-constrained least squares. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
I Eli Chien;Chung-Yi Lin;I-Hsiang Wang;
Pages: 8095 - 8118 Abstract: Community detection in hypergraphs is explored. Under a generative hypergraph model called “ $d$ -wise hypergraph stochastic block model” ( $d$ - $mathtt {hSBM}$ ), which naturally extends the stochastic block model ( $mathtt {SBM}$ ) from graphs to $d$ -uniform hypergraphs, the fundamental limit of the misclassification ratio (the loss function in the community detection problem) is studied. For the converse part, a lower bound of the minimax risk, that is, the minimax expected misclassification ratio, is derived. Asymptotically, it decays exponentially fast to zero as the number of nodes tends to infinity, and the rate function is a weighted combination of several divergence terms, each of which is the Rényi divergence of order 1/2 between two Bernoulli distributions. The Bernoulli distributions involved in the characterization of the rate function are those governing the random instantiation of hyperedges in $d$ - $mathtt {hSBM}$ . For the achievability part, we propose a two-step polynomial-time algorithm which, with high probability, has a misclassification ratio with a decaying exponent that is asymptotically greater than or equal to that of our proposed lower bound. The first step of the algorithm is a hypergraph spectral clustering method, which achieves partial recovery to a certain precision level. The second step is a local refinement method, which leverages the underlying probabilistic model along with pa-ameter estimation from the outcome of the first step. To characterize the asymptotic performance of the proposed algorithm, we first derive a sufficient condition for attaining weak consistency in the hypergraph spectral clustering step. Then, under the guarantee of weak consistency in the first step, we upper bound the loss (with high probability) attained in the local refinement step by an exponentially decaying function of the size of the hypergraph and characterize the decaying rate. Compared to existing works in $mathtt {SBM}$ , the main technical challenge lies in the complex structure of error events since community relations become much more complicated. The experimental results on both the synthetic data and real-world datasets validate our theoretical finding that the refinement step is critical in achieving the optimal statistical limit. For the special case $d=3$ , it is further shown by analyzing the performance of MLE that the proposed lower bound of the minimax risk is tight, and hence, the exponential decaying rate of the asymptotic minimax risk is characterized. We conjecture that this continues to hold for general $d$ as well. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Aditya Siripuram;William D. Wu;Brad Osgood;
Pages: 8119 - 8130 Abstract: We study the problem of finding unitary submatrices of the $N times N$ discrete Fourier transform matrix, in the context of interpolating a discrete bandlimited signal using an orthogonal basis. This problem is related to a diverse set of questions on idempotents on $mathbb {Z}_{N}$ and tiling $mathbb {Z}_{N}$ . In this work, we establish a graph-theoretic approach and connections to the problem of finding maximum cliques. We identify the key properties of these graphs that make the interpolation problem tractable when $N$ is a prime power, and we identify the challenges in generalizing to arbitrary $N$ . Finally, we investigate some connections between graph properties and the spectral-tile direction of the Fuglede conjecture. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Asger Kjærulff Jensen;
Pages: 8131 - 8139 Abstract: This paper studies the majorization of high tensor powers of finitely supported probability distributions. Taking two probability distributions $P$ and $Q$ to the $n$ ’th and $m$ ’th tensor power, respectively, in such a way that the power of $Q$ majorizes the power of $P$ , we ask how large the ratio $m/n$ can become. It is shown that the supremum of such ratios is equal to the minimal ratio of the $alpha $ -Rényi entropies of $P$ and $Q$ for $alpha in [0,infty]$ . Consideration of this ratio of tensor powers is motivated, to the author, by the resource theory of quantum entanglement, where the supremum of these ratios corresponds to the asymptotic conversion rate of bipartite pure quantum states under exact, deterministic LOCC transformations. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Roy Timo;Badri N. Vellambi;Alex Grant;Khoa D. Nguyen;
Pages: 8140 - 8163 Abstract: We consider the problem of tracking, in realtime, an unstable autoregressive (AR) source over a discrete memoryless channel (DMC). We present computable achievable bounds on the optimal tracking error for general DMCs, and we particularize these bounds to the binary erasure, packet erasure, and binary symmetric channels. The achievable bounds in this paper are proved using a partially separate source quantization and channel coding architecture. We do not use complete or strict separation in usual Shannon sense: 1) the quantiser’s resolution is optimized against the error-correction capabilities of the channel code and the channel code is optimized against an AR Hamming distortion function matched to the source (a weighted Hamming distortion function that provides unequal error protection to different parts of the AR source). The achievability results for general DMCs are proved by combining the AR Hamming distortion function with new realtime (streaming) versions of the random coding union and dependence testing bounds. When applied to erasure channels, these general bounds combine with simple converses to demonstrate that the channel’s cutoff rate plays an important role in realtime tracking. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Neri Merhav;
Pages: 8164 - 8179 Abstract: The error exponent of the typical random code is defined as the asymptotic normalized expectation of the logarithm of the probability of error, as opposed to the traditional definition of the random coding exponent as the normalized logarithm of the expectation of the probability of error with respect to a given ensemble of codes. For a certain ensemble of independent codewords, with a given power spectrum, and a generalized stochastic mismatched decoder, we characterize the error exponent of the typical random codes (TRC) for the colored Gaussian channel, with emphasis on the range of low rates, where the TRC error exponent differs in value from the ordinary random coding error exponent. The error exponent formula, which is exponentially tight at some range of low rates, is presented as the maximum of a certain function with respect to one parameter only (in the spirit of Gallager’s formulas) in the case of matched decoding, and two parameters in the case of mismatched decoding. Several aspects of the main results are discussed. These include: general properties, a parametric representation, critical rates, phase transitions, optimal input spectrum (water pouring), and comparison to the random coding exponent. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Ohad Elishco;Farzad Farnoud Hassanzadeh;Moshe Schwartz;Jehoshua Bruck;
Pages: 8180 - 8193 Abstract: We study random string-duplication systems, which we call Pólya string models. These are motivated by a class of mutations that are common in most organisms and lead to an abundance of repeated sequences in their genomes. Unlike previous works that study the combinatorial capacity of string-duplication systems, or in a probabilistic setting, various string statistics, this work provides the exact entropy rate or bounds on it, for several probabilistic models. The entropy rate determines the compressibility of the resulting sequences, as well as quantifying the amount of sequence diversity that these mutations can create. In particular, we study the entropy rate of noisy string-duplication systems, including the tandem-duplication, end-duplication, and interspersed-duplication systems, where in all cases we study duplication of length 1 only. Interesting connections are drawn between some systems and the signature of random permutations, as well as to the beta distribution common in population genetics. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Ryo Nomura;
Pages: 8194 - 8206 Abstract: Lossless variable-length source coding with codeword cost is considered for general sources. The problem setting, where we impose on unequal costs on code symbols, is called the variable-length coding with codeword cost. In this problem, the infimum of average codeword cost have already been determined for general sources. On the other hand, the overflow probability, which is defined as the probability of codeword cost being above a threshold, have not been considered yet. In this paper, we first determine the infimum of achievable threshold in the first-order sense and the second-order sense for general sources with additive memoryless codeword cost. Then, we compute it for some special sources such as i.i.d. sources and mixed sources. A generalization of the codeword cost is also discussed. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Stephan Foldes;Douglas Stott Parker;Sándor Radeleczki;
Pages: 8207 - 8212 Abstract: An alternative proof is given of the existence of greatest lower bounds in the imbalance order of binary maximal instantaneous codes of a given size. These codes are viewed as maximal antichains of a given size in the infinite binary tree of 0–1 words. The proof proposed makes use of a single balancing operation within the same imbalance poset of codes of the same fixed size, instead of moving back and forth between posets of codes corresponding to two different code sizes using expansion and contraction, as in the previous proofs of the existence of glb. It also makes use of a new combinatorial characterization of the imbalance order. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Ryo Nomura;Hideki Yagi;
Pages: 8213 - 8221 Abstract: The variable-length source coding problem allowing the error probability up to some constant is considered for general sources. In this problem, the optimum mean codeword length of variable-length codes has already been determined. On the other hand, in this paper, we focus on the overflow (or excess codeword length) probability instead of the mean codeword length. The infimum of overflow thresholds under the constraint that both of the error probability and the overflow probability are smaller than or equal to some constant is called the optimum overflow threshold. In this paper, we first derive finite-length upper and lower bounds on these probabilities so as to analyze the optimum overflow thresholds. Then, by using these bounds, we determine the general formula of the optimum overflow thresholds in both of the first-order and second-order forms. Next, we consider another expression of the derived general formula so as to reveal the relationship with the optimum coding rate in the fixed-length source coding problem. Finally, we apply the general formula derived in this paper to the case of stationary memoryless sources. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Yi-Peng Wei;Karim Banawan;Sennur Ulukus;
Pages: 8222 - 8231 Abstract: We consider the problem of private information retrieval (PIR) of a single message out of $K$ messages from $N$ replicated and non-colluding databases where a cache-enabled user (retriever) of cache-size $M$ possesses side information in the form of full messages that are partially known to the databases. In this model, the user and the databases engage in a two-phase scheme, namely, the prefetching phase where the user acquires side information and the retrieval phase where the user downloads desired information. In the prefetching phase, the user receives $m_{n}$ full messages from the $n$ th database, under the cache memory size constraint $sum _{n=1}^{N} m_{n} leq M$ . In the retrieval phase, the user wishes to retrieve a message (which is not present in its memory) such that no individual database learns anything about the identity of the desired message. In addition, the identities of the side information messages that the user did not prefetch from a database must remain private against that database. Since the side information provided by each database in the prefetching phase is known by the providing database and the side information must be kept private against the remaining databases, we coin this model as partially known private side information. We characterize the capacity of the PIR with partially known private side information to be $C=left ({1+frac {1}{N}+cdots +frac {1}{N^{K-M-1}}}right)^{-1}=frac {1-frac {1}{N}}{1-left({frac {1}{N}}right)^{K-M}}$-. Interestingly, this result is the same if none of the databases knows any of the prefetched side information, i.e., when the side information is obtained externally, a problem posed by Kadhe et al. and settled by Chen-Wang-Jafar recently. Thus, our result implies that there is no loss in using the same databases for both prefetching and retrieval phases. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Karim Banawan;Sennur Ulukus;
Pages: 8232 - 8249 Abstract: We consider the problem of noisy private information retrieval (NPIR) from $N$ non-communicating databases, each storing the same set of $M$ messages. In this model, the answer strings are not returned through noiseless bit pipes, but rather through noisy memoryless channels. We aim at characterizing the PIR capacity for this model as a function of the statistical information measures of the noisy channels such as entropy and mutual information. We derive a general upper bound for the retrieval rate in the form of a max-min optimization. We use the achievable schemes for the PIR problem under asymmetric traffic constraints and random coding arguments to derive a general lower bound for the retrieval rate. The upper and lower bounds match for $M=2$ and $M=3$ , for any $N$ , and any noisy channel. The lower and upper bounds show a separation between channel coding and retrieval scheme except for adapting the traffic ratio from the databases. We refer to this as almost separation. Next, we consider the private information retrieval problem from multiple access channels (MAC-PIR). In MAC-PIR, the database responses reach the user through a multiple access channel (MAC) that mixes the responses together in a stochastic way. We show that for the additive MAC and the conjunction/disjunction MAC, channel coding and retrieval scheme are inseparable unlike in NPIR. We show that the retrieval scheme depends on the properties of the MAC, in particular on the linearity aspect. For both cases, we provide schemes that achieve the full capacity without any loss due to the pr-vacy constraint, which implies that the user can exploit the nature of the channel to improve privacy. Finally, we show that the full unconstrained capacity is not always attainable by determining the capacity of the selection channel. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Ali Haghi;Neda Mohammadizadeh;Amir K. Khandani;
Pages: 8250 - 8272 Abstract: Delay, guaranteeing causality, is inevitable in cooperative communication systems. Traditionally, delay granularity has been limited to one symbol; however, channel delay is in fact governed by channel memory and can be shorter. For example, the delay requirement in orthogonal frequency-division multiplexing, captured in the cyclic prefix, is typically much shorter than the symbol itself. This perspective is used to study the two-user Gaussian interference channel with full-duplex transmitters. By superimposing the signal from the other node onto its own signal, each transmitter cancels the interference at its receiver. Among other results, it is proved that under a mild condition, the maximum multiplexing gain of this channel is in fact two, rather than the limit of one, previously shown under the traditional constraint of causal delay. Further, the optimal power allocation among orthogonal sub-carriers, which maximizes the achievable sum-rate, is shown to be a generalization of the well-known water filling. Simulation results are included to demonstrate the improvement in the achievable sum-rate when full-duplex transmitters are used. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Xiaojun Yuan;Haiyang Xin;Soung-Chang Liew;Yong Li;
Pages: 8273 - 8304 Abstract: This paper studies the transceiver design of the Gaussian two-pair two-way relay channel (TWRC), where two pairs of users exchange information through a common relay in a pairwise manner. Our main contribution is to show that the capacity of the Gaussian two-pair TWRC is achievable to within $frac{1}{ 2}$ bit for arbitrary channel conditions. For the outer bound, we derive a genie-aided bound of the Gaussian two-pair TWRC, which is tighter than the cut-set bound. For the inner bound, we develop a hybrid coding scheme involving Gaussian random coding, nested lattice coding, superposition coding, and network-coded decoding. We further present a message-reassembling strategy to decouple the coding design for the user-to-relay and relay-to-user links, so as to provide flexibility to fully exploit the channel randomness. We show that judicious power allocation at the users and at the relay is necessary to approach the channel capacity under various channel conditions. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Yoshiaki Inoue;Hiroyuki Masuyama;Tetsuya Takine;Toshiyuki Tanaka;
Pages: 8305 - 8324 Abstract: This paper considers the stationary distribution of the age of information (AoI) in information update systems. We first derive a general formula for the stationary distribution of the AoI, which holds for a wide class of information update systems. The formula indicates that the stationary distribution of the AoI is given in terms of the stationary distributions of the system delay and the peak AoI. To demonstrate its applicability and usefulness, we analyze the AoI in single-server queues with four different service disciplines: first-come first-served (FCFS), preemptive last-come first-served (LCFS), and two variants of non-preemptive LCFS service disciplines. For the FCFS and the preemptive LCFS service disciplines, the GI/GI/1, M/GI/1, and GI/M/1 queues are considered, and for the non-preemptive LCFS service disciplines, the M/GI/1 and GI/M/1 queues are considered. With these results, we further show comparison results for the mean AoI’s in the M/GI/1 and GI/M/1 queues under those service disciplines. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

${mathsf{OCB}}$+
&rft.title=IEEE+Transactions+on+Information+Theory&rft.issn=0018-9448&rft.date=2019&rft.volume=65&rft.spage=8325&rft.epage=8344&rft.aulast=Gupta;&rft.aufirst=Ashwin&rft.au=Ashwin+Jha;Cuauhtemoc+Mancillas-López;Mridul+Nandi;Sourav+Sen+Gupta;">On Random Read Access in ${mathsf{OCB}}$

Authors:
Ashwin Jha;Cuauhtemoc Mancillas-López;Mridul Nandi;Sourav Sen Gupta;
Pages: 8325 - 8344 Abstract: Offset codebook or ${mathsf {OCB}}$ mode is a popular block cipher mode of operation for authenticated encryption. The latest version of this cipher, called ${mathsf {OCB3}}$ , is one of the finalists in CAESAR. In this paper, we explore the scope of random read access and out-of-sequence decryption in ${mathsf {OCB}}$ . We observe that the current versions of ${mathsf {OCB}}$ are inefficient in this respect owing to the ineptness of the underlying mask generating function (MGF). We propose new candidates for MGF based on ${mathsf {AES}}$ round function, which are efficient in direct computation and provide comparable performance in the usual setting. Our schemes are not the obvious choices for MGF in conventional sense as they do not have optimal almost XOR universal (AXU) bound. In existing ${mathsf {OCB}}$ designs, the MGFs are required to have $ 2^{-n} $ , i.e. optimal, AXU bound in order to upper bound the distinguishing advantage to $ O(sigma ^{2}/2^{n}) $ , where $ n $ is the block size of the underlying block cipher and $ sigma $ is the total number of blocks among all queries. We find this specific requirement too restrictive. We abstract the ${mathsf {OCB}}$ desi-n, termed as ${mathsf {GOCB}}$ , to look into the universal notion required from the underlying MGF. We propose a relaxed notion of AXU, called locally imperfect XOR universal (LIXU) hash, which can be of independent interest. Using LIXU as the underlying MGF, we recover reasonable security bounds for our schemes. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)

Authors:
Konstantinos Limniotis;Nicholas Kolokotronis;
Pages: 8345 - 8356 Abstract: The error linear complexity spectrum constitutes a well-known cryptographic criterion for sequences, indicating how the linear complexity of the sequence decreases as the number of bits allowed to be modified per period increases. In this paper, via defining an association between $2^{n}$ -periodic binary sequences and Boolean functions on $n$ variables, it is shown that the error linear complexity spectrum also provides useful cryptographic information for the corresponding Boolean function $f$ - namely, it yields an upper bound on the minimum Hamming distance between $f$ and the set of functions depending on fewer number of variables. Therefore, the prominent Lauder-Paterson algorithm for computing the error linear complexity spectrum of a sequence may also be used for efficiently determining approximations of a Boolean function that depend on fewer number of variables. Moreover, it is also shown that, through this approach, low-degree approximations of a Boolean function can be also obtained in an efficient way. PubDate:
Dec. 2019
Issue No:Vol. 65, No. 12 (2019)