Showing 1–14 of 14 results for author: Ytrehus, O

Linearity of $\mathbb{Z}_{2^L}$-Linear Codes via Schur Product

Authors: Gustavo T. Bastos, Maiara F. Bollauf, Agnaldo J. Ferrari, Øyvind Ytrehus

Abstract: We propose an original approach to investigate the linearity of $\mathbb{Z}_{2^L}$-linear codes, i.e., codes obtained as the image of the generalized Gray map applied to $\mathbb{Z}_{2^L}$-additive codes. To accomplish that, we define two related binary codes: the associated and concatenated, where one could perform a straightforward analysis of the Schur product between their codewords and determ… ▽ More We propose an original approach to investigate the linearity of $\mathbb{Z}_{2^L}$-linear codes, i.e., codes obtained as the image of the generalized Gray map applied to $\mathbb{Z}_{2^L}$-additive codes. To accomplish that, we define two related binary codes: the associated and concatenated, where one could perform a straightforward analysis of the Schur product between their codewords and determine the linearity of the respective $\mathbb{Z}_{2^L}$-linear code. This work expands on previous contributions from the literature, where the linearity was established with respect to the kernel of a code and/or operations on $\mathbb{Z}_{2^L}$. The $\mathbb{Z}_{2^L}$-additive codes we apply the Gray map and check the linearity are the well-known Hadamard, simplex, and MacDonald codes. We also present families of Reed-Muller and cyclic codes that yield to linear $\mathbb{Z}_{2^L}$-linear codes and perform a computational verification of our proposed method applied to other $\mathbb{Z}_{2^L}$-additive codes. △ Less

Submitted 27 January, 2024; v1 submitted 21 September, 2023; originally announced September 2023.

Secrecy Gain of Formally Unimodular Lattices from Codes over the Integers Modulo 4

Authors: Maiara F. Bollauf, Hsuan-Yin Lin, Øyvind Ytrehus

Abstract: Recently, a design criterion depending on a lattice's volume and theta series, called the secrecy gain, was proposed to quantify the secrecy-goodness of the applied lattice code for the Gaussian wiretap channel. To address the secrecy gain of Construction $\text{A}_4$ lattices from formally self-dual $\mathbb{Z}_4$-linear codes, i.e., codes for which the symmetrized weight enumerator (swe) coincid… ▽ More Recently, a design criterion depending on a lattice's volume and theta series, called the secrecy gain, was proposed to quantify the secrecy-goodness of the applied lattice code for the Gaussian wiretap channel. To address the secrecy gain of Construction $\text{A}_4$ lattices from formally self-dual $\mathbb{Z}_4$-linear codes, i.e., codes for which the symmetrized weight enumerator (swe) coincides with the swe of its dual, we present new constructions of $\mathbb{Z}_4$-linear codes which are formally self-dual with respect to the swe. For even lengths, formally self-dual $\mathbb{Z}_4$-linear codes are constructed from nested binary codes and double circulant matrices. For odd lengths, a novel construction called odd extension from double circulant codes is proposed. Moreover, the concepts of Type I/II formally self-dual codes/unimodular lattices are introduced. Next, we derive the theta series of the formally unimodular lattices obtained by Construction $\text{A}_4$ from formally self-dual $\mathbb{Z}_4$-linear codes and describe a universal approach to determine their secrecy gains. The secrecy gain of Construction $\text{A}_4$ formally unimodular lattices obtained from formally self-dual $\mathbb{Z}_4$-linear codes is investigated, both for even and odd dimensions. Numerical evidence shows that for some parameters, Construction $\text{A}_4$ lattices can achieve a higher secrecy gain than the best-known formally unimodular lattices from the literature. Results concerning the flatness factor, another security criterion widely considered in the Gaussian wiretap channel, are also discussed. △ Less

Submitted 13 February, 2024; v1 submitted 14 March, 2023; originally announced March 2023.

Comments: arXiv admin note: text overlap with arXiv:2202.09236; Paper accepted for publication in IEEE Transactions on Information Theory

Formally Unimodular Packings for the Gaussian Wiretap Channel

Authors: Maiara F. Bollauf, Hsuan-Yin Lin, Øyvind Ytrehus

Abstract: This paper introduces the family of lattice-like packings, which generalizes lattices, consisting of packings possessing periodicity and geometric uniformity. The subfamily of formally unimodular (lattice-like) packings is further investigated. It can be seen as a generalization of the unimodular and isodual lattices, and the Construction A formally unimodular packings obtained from formally self-… ▽ More This paper introduces the family of lattice-like packings, which generalizes lattices, consisting of packings possessing periodicity and geometric uniformity. The subfamily of formally unimodular (lattice-like) packings is further investigated. It can be seen as a generalization of the unimodular and isodual lattices, and the Construction A formally unimodular packings obtained from formally self-dual codes are presented. Recently, lattice coding for the Gaussian wiretap channel has been considered. A measure called secrecy function was proposed to characterize the eavesdropper's probability of correctly decoding. The aim is to determine the global maximum value of the secrecy function, called (strong) secrecy gain. We further apply lattice-like packings to coset coding for the Gaussian wiretap channel and show that the family of formally unimodular packings shares the same secrecy function behavior as unimodular and isodual lattices. We propose a universal approach to determine the secrecy gain of a Construction A formally unimodular packing obtained from a formally self-dual code. From the weight distribution of a code, we provide a necessary condition for a formally self-dual code such that its Construction A formally unimodular packing is secrecy-optimal. Finally, we demonstrate that formally unimodular packings/lattices can achieve higher secrecy gain than the best-known unimodular lattices. △ Less

Submitted 28 September, 2023; v1 submitted 28 June, 2022; originally announced June 2022.

Comments: Accepted for publication in IEEE Transactions on Information Theory. arXiv admin note: text overlap with arXiv:2111.01439

On the Secrecy Gain of Formally Unimodular Construction $\text{A}_4$ Lattices

Authors: Maiara F. Bollauf, Hsuan-Yin Lin, Øyvind Ytrehus

Abstract: Lattice coding for the Gaussian wiretap channel is considered, where the goal is to ensure reliable communication between two authorized parties while preventing an eavesdropper from learning the transmitted messages. Recently, a measure called secrecy gain was proposed as a design criterion to quantify the secrecy-goodness of the applied lattice code. In this paper, the theta series of the so-cal… ▽ More Lattice coding for the Gaussian wiretap channel is considered, where the goal is to ensure reliable communication between two authorized parties while preventing an eavesdropper from learning the transmitted messages. Recently, a measure called secrecy gain was proposed as a design criterion to quantify the secrecy-goodness of the applied lattice code. In this paper, the theta series of the so-called formally unimodular lattices obtained by Construction $\text{A}_4$ from codes over $\mathbb{Z}_4$ is derived, and we provide a universal approach to determine their secrecy gains. Initial results indicate that Construction $\text{A}_4$ lattices can achieve a higher secrecy gain than the best-known formally unimodular lattices from the literature. Furthermore, a new code construction of formally self-dual $\mathbb{Z}_4$-linear codes is presented. △ Less

Submitted 18 February, 2022; originally announced February 2022.

The Secrecy Gain of Formally Unimodular Lattices on the Gaussian Wiretap Channel

Authors: Maiara F. Bollauf, Hsuan-Yin Lin, Øyvind Ytrehus

Abstract: We consider lattice coding for the Gaussian wiretap channel, where the challenge is to ensure reliable communication between two authorized parties while preventing an eavesdropper from learning the transmitted messages. Recently, a measure called the secrecy function of a lattice coding scheme was proposed as a design criterion to characterize the eavesdropper's probability of correct decision. I… ▽ More We consider lattice coding for the Gaussian wiretap channel, where the challenge is to ensure reliable communication between two authorized parties while preventing an eavesdropper from learning the transmitted messages. Recently, a measure called the secrecy function of a lattice coding scheme was proposed as a design criterion to characterize the eavesdropper's probability of correct decision. In this paper, the family of formally unimodular lattices is presented and shown to possess the same secrecy function behavior as unimodular and isodual lattices. Based on Construction A, we provide a universal approach to determine the secrecy gain, i.e., the maximum value of the secrecy function, for formally unimodular lattices obtained from formally self-dual codes. Furthermore, we show that formally unimodular lattices can achieve higher secrecy gain than the best-known unimodular lattices from the literature. △ Less

Submitted 2 November, 2021; originally announced November 2021.

Tiling of Constellations

Authors: Maiara F. Bollauf, Øyvind Ytrehus

Abstract: Motivated by applications in reliable and secure communication, we address the problem of tiling (or partitioning) a finite constellation in $\mathbb{Z}_{2^L}^n$ by subsets, in the case that the constellation does not possess an abelian group structure. The property that we do require is that the constellation is generated by a linear code through an injective mapping. The intrinsic relation betwe… ▽ More Motivated by applications in reliable and secure communication, we address the problem of tiling (or partitioning) a finite constellation in $\mathbb{Z}_{2^L}^n$ by subsets, in the case that the constellation does not possess an abelian group structure. The property that we do require is that the constellation is generated by a linear code through an injective mapping. The intrinsic relation between the code and the constellation provides a sufficient condition for a tiling to exist. We also present a necessary condition. Inspired by a result in group theory, we discuss results on tiling for the particular case when the finer constellation is an abelian group as well. △ Less

Submitted 12 May, 2021; v1 submitted 10 May, 2021; originally announced May 2021.

Proceedings of the 11th Asia-Europe Workshop on Concepts in Information Theory

Authors: A. J. Han Vinck, Kees A. Schouhamer Immink, Tadashi Wadayama, Van Khu Vu, Akiko Manada, Kui Cai, Shunsuke Horii, Yoshiki Abe, Mitsugu Iwamoto, Kazuo Ohta, Xingwei Zhong, Zhen Mei, Renfei Bu, J. H. Weber, Vitaly Skachek, Hiroyoshi Morita, N. Hovhannisyan, Hiroshi Kamabe, Shan Lu, Hirosuke Yamamoto, Kengo Hasimoto, O. Ytrehus, Shigeaki Kuzuoaka, Mikihiko Nishiara, Han Mao Kiah , et al. (2 additional authors not shown)

Abstract: This year, 2019 we celebrate 30 years of our friendship between Asian and European scientists at the AEW11 in Rotterdam, the Netherlands. Many of the 1989 participants are also present at the 2019 event. This year we have many participants from different parts of Asia and Europe. It shows the importance of this event. It is a good tradition to pay a tribute to a special lecturer in our community.… ▽ More This year, 2019 we celebrate 30 years of our friendship between Asian and European scientists at the AEW11 in Rotterdam, the Netherlands. Many of the 1989 participants are also present at the 2019 event. This year we have many participants from different parts of Asia and Europe. It shows the importance of this event. It is a good tradition to pay a tribute to a special lecturer in our community. This year we selected Hiroyoshi Morita, who is a well known information theorist with many original contributions. △ Less

Submitted 26 June, 2019; originally announced July 2019.

Eliminating Variables in Boolean Equation Systems

Authors: Bjørn Møller Greve, Håvard Raddum, Gunnar Fløystad, Øyvind Ytrehus

Abstract: Systems of Boolean equations of low degree arise in a natural way when analyzing block ciphers. The cipher's round functions relate the secret key to auxiliary variables that are introduced by each successive round. In algebraic cryptanalysis, the attacker attempts to solve the resulting equation system in order to extract the secret key. In this paper we study algorithms for eliminating the auxil… ▽ More Systems of Boolean equations of low degree arise in a natural way when analyzing block ciphers. The cipher's round functions relate the secret key to auxiliary variables that are introduced by each successive round. In algebraic cryptanalysis, the attacker attempts to solve the resulting equation system in order to extract the secret key. In this paper we study algorithms for eliminating the auxiliary variables from these systems of Boolean equations. It is known that elimination of variables in general increases the degree of the equations involved. In order to contain computational complexity and storage complexity, we present two new algorithms for performing elimination while bounding the degree at $3$, which is the lowest possible for elimination. Further we show that the new algorithms are related to the well known \emph{XL} algorithm. We apply the algorithms to a downscaled version of the LowMC cipher and to a toy cipher based on the Prince cipher, and report on experimental results pertaining to these examples. △ Less

Submitted 23 October, 2017; originally announced October 2017.

Comments: 21 pages, 3 figures, Journal paper

ML and Near-ML Decoding of LDPC Codes Over the BEC: Bounds and Decoding Algorithms

Authors: Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek, Eirik Rosnes, Øyvind Ytrehus

Abstract: The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. The theoretical average spectrum of the Gallager ensemble is computed by using a recurrent procedure and compared to the empirically found average spectrum for the same ensemble as well as to the empirical average spectrum o… ▽ More The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. The theoretical average spectrum of the Gallager ensemble is computed by using a recurrent procedure and compared to the empirically found average spectrum for the same ensemble as well as to the empirical average spectrum of the Richardson-Urbanke ensemble and spectra of selected codes from both ensembles. Distance properties of the random codes from the Gallager ensemble are discussed. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average spectrum is presented. A new upper bound on the ML decoding performance of LDPC codes from the Gallager ensemble based on computing the rank of submatrices of the code parity-check matrix is derived. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the upper bounds on the ML decoding performance. △ Less

Submitted 20 November, 2018; v1 submitted 5 September, 2017; originally announced September 2017.

Comments: To appear in IEEE Transactions on Communications

Rate $(n-1)/n$ Systematic MDS Convolutional Codes over $GF(2^m)$

Authors: Ángela Barbero, Øyvind Ytrehus

Abstract: A systematic convolutional encoder of rate $(n-1)/n$ and maximum degree $D$ generates a code of free distance at most ${\cal D} = D+2$ and, at best, a column distance profile (CDP) of $[2,3,\ldots,{\cal D}]$. A code is \emph{Maximum Distance Separable} (MDS) if it possesses this CDP. Applied on a communication channel over which packets are transmitted sequentially and which loses (erases) packets… ▽ More A systematic convolutional encoder of rate $(n-1)/n$ and maximum degree $D$ generates a code of free distance at most ${\cal D} = D+2$ and, at best, a column distance profile (CDP) of $[2,3,\ldots,{\cal D}]$. A code is \emph{Maximum Distance Separable} (MDS) if it possesses this CDP. Applied on a communication channel over which packets are transmitted sequentially and which loses (erases) packets randomly, such a code allows the recovery from any pattern of $j$ erasures in the first $j$ $n$-packet blocks for $j<{\cal D}$, with a delay of at most $j$ blocks counting from the first erasure. This paper addresses the problem of finding the largest ${\cal D}$ for which a systematic rate $(n-1)/n$ code over $GF(2^m)$ exists, for given $n$ and $m$. In particular, constructions for rates $(2^m-1)/2^m$ and $(2^{m-1}-1)/2^{m-1}$ are presented which provide optimum values of ${\cal D}$ equal to 3 and 4, respectively. A search algorithm is also developed, which produces new codes for ${\cal D}$ for field sizes $2^m \leq 2^{14}$. Using a complete search version of the algorithm, the maximum value of ${\cal D}$, and codes that achieve it, are determined for all code rates $\geq 1/2$ and every field size $GF(2^m)$ for $m\leq 5$ (and for some rates for $m=6$). △ Less

Submitted 29 May, 2017; originally announced May 2017.

Near-Field Passive RFID Communication: Channel Model and Code Design

Authors: Ángela I. Barbero, Eirik Rosnes, Guang Yang, Øyvind Ytrehus

Abstract: This paper discusses a new channel model and code design for the reader-to-tag channel in near-field passive radio frequency identification (RFID) systems using inductive coupling as a power transfer mechanism. If the receiver resynchronizes its internal clock each time a bit is detected, the bit-shift channel used previously in the literature to model the reader-to-tag channel needs to be modifie… ▽ More This paper discusses a new channel model and code design for the reader-to-tag channel in near-field passive radio frequency identification (RFID) systems using inductive coupling as a power transfer mechanism. If the receiver resynchronizes its internal clock each time a bit is detected, the bit-shift channel used previously in the literature to model the reader-to-tag channel needs to be modified. In particular, we propose a discretized Gaussian shift channel as a new channel model in this scenario. We introduce the concept of quantifiable error avoidance, which is much simpler than error correction. The capacity is computed numerically, and we also design some new simple codes for error avoidance on this channel model based on insights gained from the capacity calculations. Finally, some simulation results are presented to compare the proposed codes to the Manchester code and two previously proposed codes for the bit-shift channel model. △ Less

Submitted 21 March, 2014; v1 submitted 20 September, 2013; originally announced September 2013.

Comments: Submitted to IEEE Transactions on Communications. Accepted March 5, 2014

Improved Delay Estimates for a Queueing Model for Random Linear Coding for Unicast

Authors: Mohammad Ravanbakhsh, Angela I. Barbero Diez, Oyvind Ytrehus

Abstract: Consider a lossy communication channel for unicast with zero-delay feedback. For this communication scenario, a simple retransmission scheme is optimum with respect to delay. An alternative approach is to use random linear coding in automatic repeat-request (ARQ) mode. We extend the work of Shrader and Ephremides, by deriving an expression for the delay of random linear coding over field of infi… ▽ More Consider a lossy communication channel for unicast with zero-delay feedback. For this communication scenario, a simple retransmission scheme is optimum with respect to delay. An alternative approach is to use random linear coding in automatic repeat-request (ARQ) mode. We extend the work of Shrader and Ephremides, by deriving an expression for the delay of random linear coding over field of infinite size. Simulation results for various field sizes are also provided. △ Less

Submitted 26 May, 2009; v1 submitted 26 January, 2009; originally announced January 2009.

Comments: 5 pages, 3 figures, accepted at the 2009 IEEE International Symposium on Information Theory

An efficient centralized binary multicast network coding algorithm for any cyclic network

Authors: Angela I. Barbero Diez, Oyvind Ytrehus

Abstract: We give an algorithm for finding network encoding and decoding equations for error-free multicasting networks with multiple sources and sinks. The algorithm given is efficient (polynomial complexity) and works on any kind of network (acyclic, link cyclic, flow cyclic, or even in the presence of knots). The key idea will be the appropriate use of the delay (both natural and additional) during the… ▽ More We give an algorithm for finding network encoding and decoding equations for error-free multicasting networks with multiple sources and sinks. The algorithm given is efficient (polynomial complexity) and works on any kind of network (acyclic, link cyclic, flow cyclic, or even in the presence of knots). The key idea will be the appropriate use of the delay (both natural and additional) during the encoding. The resulting code will always work with finite delay with binary encoding coefficients. △ Less

Submitted 1 May, 2007; originally announced May 2007.

Turbo Decoding on the Binary Erasure Channel: Finite-Length Analysis and Turbo Stopping Sets

Authors: Eirik Rosnes, Øyvind Ytrehus

Abstract: This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation (BP) decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of stopping sets. We describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of st… ▽ More This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation (BP) decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of stopping sets. We describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum-size turbo stopping set which is also a subset of the set of erased positions. Furthermore, we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results. Finally, we give an expression for the turbo stopping set size enumerating function under the uniform interleaver assumption, and an efficient enumeration algorithm of small-size turbo stopping sets for a particular interleaver. The solution is based on the algorithm proposed by Garello et al. in 2001 to compute an exhaustive list of all low-weight codewords in a turbo code. △ Less

Submitted 20 February, 2006; originally announced February 2006.

Comments: 28 pages, 5 figures, submitted to IEEE Transactions on Information Theory

Journal ref: IEEE Trans. Inf. Theory, vol. 53, no. 11, pp. 4059-4075, Nov. 2007