Generalized Reed-Solomon codes form the most prominent class of maximum distance separable (MDS) codes, codes that are optimal in the sense that their minimum distance cannot be improved for a given length and code size. The study of codes that are MDS yet not generalized Reed-Solomon codes, called non-generalized Reed-Solomon MDS codes, started with the work by Roth and Lemple (1989), where the first examples were exhibited. It then gained traction thanks to the work by Beelen et al. (2017), who introduced twisted Reed-Solomon codes, and showed that families of such codes are non-generalized Reed-Solomon MDS codes. Finding non-generalized Reed-Solomon MDS codes is naturally motivated by the classification of MDS codes. In this paper, we provide a generic construction of MDS codes, yielding infinitely many examples. We then explicit families of non-generalized Reed-Solomon MDS codes. Finally we position some of the proposed codes with respect to generalized twisted Reed-Solomon codes, and provide new view points on this family of codes.

We consider the design and analysis of quorum systems over erasure coded warm data (with low frequency of writes and accesses in general) to guarantee sequential consistency under a fail-stop model while supporting atomic read-modify-write operations by multiple clients. We propose a definition of asymmetric quorum systems that suit the framework of coded data by explicitly exploiting the structural properties of code and instantiate it over distinct families of coding strategies: maximum distance separable (MDS) codes and codes with locality, and we indicate a mechanism for synchronizing stale nodes using differential updates, which again exploits the code structures. The proposed quorum system's behavior is analyzed theoretically, exploring several aspects: viability of quorums under node unavailability; contention of resources between read and write operations; and quorum load. We complement these theoretical exploration with simulation based experiments to quantify the behavior of the proposed mechanism. The overall study demonstrates the feasibility and practicality of quorums over codes under practicable assumptions for achieving a stringent form of consistency, specifically, sequential consistency, while the stored data is being mutated by potentially multiple processes that might read and then modify the existing data. We achieve this in-place, without having to resort to store multiple versions of the data.

We consider oblivious transfer protocols performed over binary symmetric channels in a malicious setting where parties will actively cheat if they can. We provide constructions purely based on coding theory that achieve an explicit positive rate, the essential ingredient being the existence of linear codes whose Schur products are asymptotically good.

Summary Distinct transactions among different and unrelated users are combined together to create a single Bitcoin transaction (mixing transaction) to obfuscate the relationships among the actual participants (more specifically, the wallet addresses used for the transactions). We consider multi‐input multi‐output transactions with at least two inputs and three outputs as proxy, to analyze four characteristic periods of ∼50 days each, representing periods before the introduction of mixing, in its early days, during its growth, and after the volume of such multi‐input multi‐output transactions became more or less stabile. Structural properties and characteristics of the transaction and wallet address networks are computed and compared, through standard tools, but also via the introduction of two novel techniques that provide indicators of mixing‐like behaviors: (1) an entropy characterization to detect abnormally uniform inputs and/or outputs and (2) a connected component analysis of subgraphs formed by only multi‐input multi‐output transactions (showing cascades of such transactions). The contributions of this exploratory Bitcoin network analysis paper can thus be seen as two‐fold. At a macroscopic level, the growth and stabilization periods are shown to stand out with respect to most considered metrics, while at a microscopic level, chains of multi‐input multi‐output transactions, and transactions with outlier behavior in terms of input/output entropies are identified for further investigation.

This study considers a class of randomised encryption techniques, where the encrypted data suffers from noise through transmission over a communication channel. It focuses on the encoding–encryption framework, where the data is first encoded using error correction coding for reliability, then encrypted with a stream cipher. A dedicated homophonic encoder is added to enhance the protection of the stream cipher key, on which relies the security of all the system transmissions. This study presents a security evaluation of such systems in a chosen plaintext attack scenario, which shows that the computational complexity security is lower bounded by the related LPN (learning from parity with noise) complexity in both the average and worst cases. This gives guidelines to construct a dedicated homophonic encoder which maximises the complexity of the underlying LPN problem for a given encoding overhead. A generic homophonic coding strategy that fulfils the proposed design criteria is then given, which thus both enhances security while minimising the induced overhead. Finally, a comparison of encryption schemes based on the LPN problem with and without homophonic coding is considered.

Given a graph, the notion of entropic centrality was introduced by Tutzauer to characterize vertices which are important in the sense that there is a high uncertainty about the destination of an atomic flow starting at them, assuming that at each hop, the flow is equally likely to continue to any unvisited vertex, or to be terminated there. We generalize this notion of entropic centrality to non-atomic flows, and furthermore show that the case of a non-atomic flow splitting with equal probability across different subsets of edges results in the same entropic centrality as that of the atomic flow. This gives a new and more generalized interpretation to the original entropic centrality notion. Finally, we demonstrate using network graphs derived from Bitcoin transactions that depending on the graph characteristics, the presented entropy based centrality metric can provide a unique perspective not captured by other existing centrality measures - particularly in identifying vertices with relatively low out-degrees which may nevertheless be connected to hub vertices, and thus can have high spread in the network.

We revisit a Renyi entropy based measure introduced originally for image clustering [1], and study its application to graph clustering. To effectuate Renyi entropy based graph clustering, we propose a simulated annealing algorithm. We explore our algorithm's efficacy and limitations with the Karate club graph [2], as well as some other real world network.

LCD (linear complimentary dual) codes are linear codes that trivially intersect their duals. We address the question of an equivalent concept for lattices. We observe basic properties of the intersection of a lattice with its dual, and consider the construction of lattices from LCD codes using Construction A. Lattices obtained from the intersection of a code with its dual via Construction A are further discussed.

We consider the Gaussian wiretap channel, where two legitimate players Alice and Bob communicate over an additive white Gaussian noise (AWGN) channel, while Eve is eavesdropping, also through an AWGN channel. We propose a coding strategy based on lattice coset encoding. We define the secrecy gain as a design criterion for wiretap lattice codes, expressed in terms of the lattice theta series, which characterizes Eve's confusion as a function of the channel parameters. The secrecy gain is studied for even unimodular lattices, and an asymptotic analysis shows that it grows exponentially in the dimension of the lattice. Examples of wiretap lattice codes are given.

In this work, we study the problem of storing reliably an archive of versioned data. Specifically, we focus on systems where the differences (deltas) between subsequent versions rather than the whole objects are stored - a typical model for storing versioned data. For reliability, we propose erasure encoding techniques that exploit the sparsity of information in the deltas while storing them reliably in a distributed back-end storage system, resulting in improved I/O read performance to retrieve the whole versioned archive. Along with the basic techniques, we propose a few optimization heuristics, and evaluate the techniques' efficacy analytically and with numerical simulations.

A wiretap channel is a communication channel between a transmitter Alice and a legitimate receiver Bob, in the presence of an eavesdropper Eve. The goal of communication is to achieve reliability between Alice and Bob, but also confidentiality despite Eve's presence. Wiretap channels are declined in all kinds of flavors, depending on the underlying channels used by the three players: discrete memoryless channels, additive Gaussian noise channels, or fading channels, to name a few. In this survey, we focus on the case where the three players use multiple-antenna channels with Gaussian noise to communicate. After summarizing known results for multiple-input-multiple-output (MIMO) channels, both in terms of achievable reliable data rate (capacity) and code design, we introduce the MIMO wiretap channel. We then state the MIMO wiretap capacity, summarize the idea of the proof(s) behind this result, and comment on the insights given by the proofs on the physical meaning of the secrecy capacity. We finally discuss design criteria for MIMO wiretap codes.

We propose a lattice construction from totally real and complex multiplication fields, which naturally generalizes Construction A of lattices from p-ary codes obtained from the cyclotomic field Q(ζp), p a prime, which in turn contains the so-called Construction A of lattices from binary codes as a particular case. We focus on the maximal totally real subfield Q(ζpr+ ζp-r) of the cyclotomic field Q(ζpr), r ≥ 1. Our construction has applications to coset encoding of algebraic lattice codes for block fading channels, and in particular for block fading wiretap channels.

We consider sums of inverse of algebraic norms as a code design criterion for fading wiretap channels. We study their behavior for small dimensional lattices built over the ring of integers of a number field, where the lattice points are taken from finite constellations, whose shaping is either cubic or spheric. Our analysis shows that unimodular lattices whose underlying number field has a small discriminant give the best performance so far.

We consider the design of codes for distributed storage systems that are amenable to repair. We introduce the notion of partial collaboration to capture the property that nodes participating in a repair process may collaborate to different extents, bringing more nuances to the known cases: no collaboration or full collaboration during repair. We compute for this scenario the storage (per node) when the repair bandwidth (per node) is minimal, and conversely the repair bandwidth when the storage is minimal. We provide a generic code construction that enables repair of several failures through partial collaboration.

There is a rich theory of relations between lattices and linear codes over finite fields. However, this theory has been developed mostly with lattice codes for the Gaussian channel in mind. In particular, different versions of what is called Construction A have connected the Hamming distance of the linear code to the Euclidean structure of the lattice. This paper concentrates on developing a similar theory, but for fading channel coding instead. First, two versions of Construction A from number fields are given. These are then extended to division algebra lattices. Instead of the Euclidean distance, the Hamming distance of the finite codes is connected to the product distance of the resulting lattices, that is the minimum product distance and the minimum determinant respectively.

We study the rank weight hierarchy, thus in particular the rank metric, of cyclic codes over the finite field Fqm, q a prime power, m ≤ 2. We establish the rank weight hierarchy for [n, n - 1] cyclic codes and characterize [n, k] cyclic codes of rank metric 1 when (1) k = 1, (2) n and q are coprime, and (3) the characteristic char(Fq) divides n. Finally, for n and q coprime, cyclic codes of minimal r-rank are characterized, and a refinement of the Singleton bound for the rank weight is derived.

The secrecy gain of a lattice is a lattice invariant used to characterize wiretap lattice codes for Gaussian channels. The secrecy gain has been classified for unimodular lattices up to dimension 23, and so far, a few sparse examples are known for l-modular lattices, with l = 2, 3. We propose some constructions of 5-modular lattices via the Construction A of lattices from linear codes, and study the secrecy gain of the resulting lattices.

A wiretap channel models a communication channel between a legitimate sender Alice and a legitimate receiver Bob in the presence of an eavesdropper Eve. Confidentiality between Alice and Bob is obtained using wiretap codes, which exploit the difference between the channels to Bob and to Eve. This paper discusses a first implementation of wiretap lattice codes using USRP (Universal Software Radio Peripheral), which focuses on the channel between Alice and Eve. Benefits of coset encoding for Eve's confusion are observed, using different lattice codes in small dimensions, and varying the position of the eavesdropper.

To achieve reliability in distributed storage systems, data has usually been replicated across different nodes. However the increasing volume of data to be stored has motivated the introduction of erasure codes, a storage efficient alternative to replication, particularly suited for archival in data centers, where old datasets (rarely accessed) can be erasure encoded, while replicas are maintained only for the latest data. Many recent works consider the design of new storage-centric erasure codes for improved repairability. In contrast, this paper addresses the migration from replication to encoding: traditionally erasure coding is an atomic operation in that a single node with the whole object encodes and uploads all the encoded pieces. Although large datasets can be concurrently archived by distributing individual object encodings among different nodes, the network and computing capacity of individual nodes constrain the archival process due to such atomicity. We propose a new pipelined coding strategy that distributes the network and computing load of single-object encodings among different nodes, which also speeds up multiple object archival. We further present RapidRAID codes, an explicit family of pipelined erasure codes which provides fast archival without compromising either data reliability or storage overheads. Finally, we provide a real implementation of RapidRAID codes and benchmark its performance using both a cluster of 50 nodes and a set of Amazon EC2 instances. Experiments show that RapidRAID codes reduce a single object's coding time by up to 90%, while when multiple objects are encoded concurrently, the reduction is up to 20%.

We consider the problem of communication over a block fading wiretap channel. It is known that coding for such a channel can be done using nested lattice codes constructed over totally real number fields. In this paper, we propose a method for encoding an integral lattice over the ring of integers of a totally real number field, and study in particular the case of Q(ζp+ζp-1) using a linear code over Fp. This generalizes the well-known Construction A and provides an efficient coset encoding for algebraic lattices.

Distributed storage systems need to store data redundantly in order to provide some fault-tolerance and guarantee system reliability. Different coding techniques have been proposed to provide the required redundancy more efficiently than traditional replication schemes. However, compared to replication, coding techniques are less efficient for repairing lost redundancy, as they require retrieval of larger amounts of data from larger subsets of storage nodes. To mitigate these problems, several recent works have presented locally repairable codes designed to minimize the repair traffic and the number of nodes involved per repair. Unfortunately, existing methods often lead to codes where there is only one subset of nodes able to repair a piece of lost data, limiting the local repairability to the availability of the nodes in this subset. In this paper, we present a new family of locally repairable codes that allows different trade-offs between the number of contacted nodes per repair, and the number of different subsets of nodes that enable this repair. We show that slightly increasing the number of contacted nodes per repair allows to have repair alternatives, which in turn increases the probability of being able to perform efficient repairs. Finally, we present pg-BLRC, an explicit construction of locally repairable codes with multiple repair alternatives, constructed from partial geometries, in particular from Generalized Quadrangles. We show how these codes can achieve practical lengths and high rates, while requiring a small number of nodes per repair, and providing multiple repair alternatives.

We address the question of constructing explicitly quasi-uniform codes from groups. We determine the size of the codebook, the alphabet and the minimum distance as a function of the corresponding group, both for abelian and some nonabelian groups. Potentials applications comprise the design of almost affine codes and non-linear network codes.

As a first step towards distributed computations in a wireless network, we introduce ideal lattices, that is lattices built over an ideal of a ring of integers in a number field, as a tool for constructing lattice codes at the physical layer. These lattices are not only additive groups as all lattices, but they are also equipped with a multiplication, which enables polynomial operations at each node of the wireless network. In this paper, we show how some of these ideal lattices can be constructed from polynomial codes (generalization of cyclic codes) via Construction A, and illustrate how these lattices enable multiplication.

We consider MIMO (Multiple Input Multiple Output) wiretap channels, where a legitimate transmitter Alice is communicating with a legitimate receiver Bob in the presence of an eavesdropper Eve, and communication is done via MIMO channels. We suppose that Alice's strategy is to use an infinite lattice codebook, which then allows her to perform coset encoding. We analyze Eve's probability of correctly decoding the message Alice meant to Bob, and from minimizing this probability, we derive a code design criterion for MIMO lattice wiretap codes. The case of block fading channels is treated similarly, and fast fading channels are derived as a particular case. The Alamouti code is carefully studied as an illustration of the analysis provided.

Lattice coding over a Gaussian wiretap channel, where an eavesdropper listens to transmissions between a transmitter and a legitimate receiver, is considered. A new lattice invariant called the secrecy gain is used as a code design criterion for wiretap lattice codes since it was shown to characterize the confusion that a chosen lattice can cause at the eavesdropper: the higher the secrecy gain of the lattice, the more confusion. In this paper, secrecy gains of extremal odd unimodular lattices as well as unimodular lattices in dimensionn, 16 ≤n≤ 23, are computed, covering the four extremal odd unimodular lattices and all the 111 nonextremal unimodular lattices (both odd and even), providing thus a classification of the best wiretap lattice codes coming from unimodular lattices in dimensionn, 8n≤ 23. Finally, to permit lattice encoding via Construction A, the corresponding error correction codes of the best lattices are determined.

We propose a full-rate iterative space-time code construction, which uses an algebraic space-time code in order to design a new space-time code of double the code rank. We give a condition for determining whether the resulting codes satisfy the full diversity property, and study their maximum likelihood decoding complexity with respect to sphere decoding. Particular emphasis is given to the asymmetric multiple input double output codes. In the process, we derive an interesting way of obtaining division algebras, and study their centers and maximal subfields.

Lattice coding over a Gaussian wiretap channel is considered with respect to a lattice invariant called the secrecy gain, which was introduced in [1] to characterize the confusion that a chosen lattice can cause at the eavesdropper: the higher the secrecy gain of the lattice, the more confusion. In this paper, secrecy gains of several 2- and 3-modular lattices are computed. Most are shown to have a secrecy gain larger than the best unimodular lattices can achieve.

We present an iterative construction of algebraic space-time codes. Starting from a division algebra D, we show how to embed it into a larger ring A = A(D) and give conditions for A to be a new division algebra. Starting from a quaternion division algebra D1, we thus obtain a sequence D1⊂ D2⊂... of division algebras where Di= A(Di-1). Each of the Dican be used as an underlying structure to build a space-time Ci. Furthermore, the iteration step is done such that fast-decodability of the original code is preserved. We illustrate our technique by creating an iterative version of the Silver code.

We consider lattice coding over a Gaussian wiretap channel with respect to the secrecy gain, a lattice invariant introduced in [1] to characterize the confusion that a chosen lattice can cause at the eavesdropper. The secrecy gain of the best unimodular lattices constructed from binary self-dual codes in dimension n, 24 ≤ n ≤ 32 are calculated. Numerical upper bounds on the secrecy gain of unimodular lattices in general and of unimodular lattices constructed from binary self-dual codes in particular are derived for all even dimensions up to 168.

Nonassociative division algebras have been recently proposed as an alternative way to design fully-diverse space-time codes. In particular, nonassociative cyclic algebras provide division algebras more easily than their associative counter-part. In this paper, we propose a few space-time code constructions coming from both associative and nonassociative cyclic algebras of degree 4, suitable for 4 transmit and 2 receive antennas, which furthermore exhibit good fast-decodability.

It is known that, for transmission over quasi-static MIMO fading channels with n transmit antennas, diversity can be obtained by using an inner fully diverse space-time block code while coding gain, derived from the determinant criterion, comes from an appropriate outer code. When the inner code has a cyclic algebra structure over a number field, as for perfect space-time codes, an outer code can be designed via coset coding, more precisely, by taking the quotient of the algebra by a two-sided ideal which leads to matrices over finite alphabets for the outer code. In this paper, we show that the determinant criterion induces various metrics on the outer code, such as the Hamming and Bachoc distances. When n = 2, partitioning the 2×2 Golden code by using an ideal above the prime 2 leads to consider codes over either M2(F2) or M2(F2[i]), both being noncommutative alphabets. By identifying them as algebras over a finite field or a finite ring respectively, we establish an unexpected connection with classical error-correcting codes over F4and F4[i]. Matrix rings of higher dimension, suitable for 3×3 and 4×4 perfect codes, give rise to more complex examples.

Multiple-input double-output (MIDO) codes are important in the near-future wireless communications, where the portable end-user device is physically small and will typically contain at most two receive antennas. Especially tempting is the 4$\,\times\,$2 channel due to its immediate applicability in the digital video broadcasting (DVB). Such channels optimally employ rate-two space-time (ST) codes consisting of$(4\times 4)$matrices. Unfortunately, such codes are in general very complex to decode, hence setting forth a call for constructions with reduced complexity. Recently, some reduced complexity constructions have been proposed, but they have mainly been based on different ad hoc methods and have resulted in isolated examples rather than in a more general class of codes. In this paper, it will be shown that a family of division algebra based MIDO codes will always result in at least 37.5% worst-case complexity reduction, while maintaining full diversity and, for the first time, the nonvanishing determinant (NVD) property. The reduction follows from the fact that, similarly to the Alamouti code, the codes will be subsets of matrix rings of the Hamiltonian quaternions, hence allowing simplified decoding. At the moment, such reductions are among the best known for rate-two MIDO codes,. Several explicit constructions are presented and shown to have excellent performance through computer simulations.

Erasure codes provide a storage efficient alternative to replication based redundancy in (networked) storage systems. They however entail high communication overhead for maintenance, when some of the encoded fragments are lost and need to be replenished. Such overheads arise from the fundamental need to recreate (or keep separately) first a copy of the whole object before any individual encoded fragment can be generated and replenished. There has recently been intense interest to explore alternatives, most prominent ones being regenerating codes (RGC) and hierarchical codes (HC). We propose as an alternative a new family of codes to improve the maintenance process, called self-repairing codes (SRC), with the following salient features: (a) encoded fragments can be repaired directly from other subsets of encoded fragments by downloading less data than the size of the complete object, ensuring that (b) a fragment is repaired from a fixed number of encoded fragments, the number depending only on how many encoded blocks are missing and independent of which specific blocks are missing. These properties allow for not only low communication overhead to recreate a missing fragment, but also independent reconstruction of different missing fragments in parallel, possibly in different parts of the network. The fundamental difference between SRCs and HCs is that different encoded fragments in HCs do not have symmetric roles (equal importance). Consequently the number of fragments required to replenish a specific fragment in HCs depends on which specific fragments are missing, and not solely on how many. Likewise, object reconstruction may need different number of fragments depending on which fragments are missing. RGCs apply network coding over (n, k) erasure codes, and provide network information flow based limits on the minimal maintenance overheads. RGCs need to communicate with at least k other nodes to recreate any fragment, and the minimal overhead is achieved if only one fragment is missing, and information is downloaded from all the other n-1 nodes. We analyze the static resilience of SRCs with respect to erasure codes, and observe that SRCs incur marginally larger storage overhead in order to achieve the aforementioned properties. The salient SRC properties naturally translate to low communication overheads for reconstruction of lost fragments, and allow reconstruction with lower latency by facilitating repairs in parallel. These desirable properties make SRC a practical candidate for networked distributed storage systems.

Multiple Input Double Output (MIDO) asymmetric space-time codes for 4 transmit antennas and 2 receive antennas can be employed in the downlink from base stations to portable devices. Previous MIDO code constructions with low Maximum Likelihood (ML) decoding complexity, full diversity and the non-vanishing determinant (NVD) property are mostly based on cyclic division algebras. In this paper, a new family of MIDO codes with the NVD property based on crossed-product algebras over ℚ is introduced. Fast decodability follows naturally from the structure of the codewords which consist of four generalized Alamouti blocks. The associated ML complexity order is the lowest known for full-rate MIDO codes (O(M10) instead of O(M16) with respect to the real constellation size M). Numerical simulations show that these codes have a performance from comparable up to 1dB gain compared to the best known MIDO code with the same complexity.

We consider lattice coding over a Gaussian wiretap channel, where an eavesdropper listens to the transmissions between a transmitter and a legitimate receiver. In [1], a new lattice invariant called the secrecy gain was introduced as a code design criterion for wiretap lattice codes, shown to characterize the confusion that a chosen lattice code can cause at the eavesdropper: the higher the secrecy gain of the lattice, the more confusion. In this paper, a formula for the secrecy gain of unimodular lattices is derived. Secrecy gains of extremal odd unimodular lattices as well as unimodular lattices in dimension 16 are computed and compared. Finally, best wiretap lattice codes coming from unimodular lattices in dimension n, 8 ≤ n ≤ 16 are classified.

Self-Repairing Codes (SRC) are codes designed to suit the need of coding for distributed networked storage: they not only allow stored data to be recovered even in the presence of node failures, they also provide a repair mechanism where as little as two live nodes can be contacted to regenerate the data of a failed node. In this paper, we propose a new instance of self-repairing codes, based on constructions of spreads coming from projective geometry. We study some of their properties to demonstrate the suitability of these codes for distributed networked storage.

Recent years have witnessed a slew of coding techniques custom designed for networked storage systems. Network coding inspired regenerating codes are the most prolifically studied among these new age storage centric codes. A lot of effort has been invested in understanding the fundamental achievable trade-offs of storage and bandwidth usage to maintain redundancy in presence of different models of failures, showcasing the efficacy of regenerating codes with respect to traditional erasure coding techniques. For practical usability in open and adversarial environments, as is typical in peer-to-peer systems, we need however not only resilience against erasures, but also from (adversarial) errors. In this paper, we study the resilience of generalized regenerating codes (supporting multi-repairs, using collaboration among newcomers) in the presence of two classes of Byzantine nodes, relatively benign selfish (non-cooperating) nodes, as well as under more active, malicious polluting nodes. We give upper bounds on the resilience capacity of regenerating codes, and show that the advantages of collaborative repair can turn to be detrimental in the presence of Byzantine nodes. We further exhibit that system mechanisms can be combined with regenerating codes to mitigate the effect of rogue nodes.

We consider the MIMO wiretap channel, that is a MIMO broadcast channel where the transmitter sends some confidential information to one user which is a legitimate receiver, while the other user is an eavesdropper. Perfect secrecy is achieved when the transmitter and the legitimate receiver can communicate at some positive rate, while insuring that the eavesdropper gets zero bits of information. In this paper, we compute the perfect secrecy capacity of the multiple antenna MIMO broadcast channel, where the number of antennas is arbitrary for both the transmitter and the two receivers. Our technique involves a careful study of a Sato-like upper bound via the solution of a certain algebraic Riccati equation.

Systems exploiting network coding to increase their throughput suffer greatly from pollution attacks, which consist of injecting malicious packets in the network. The pollution attacks are amplified by the network coding process, resulting in a greater damage than under traditional routing. In this paper, we address this issue by designing an unconditionally secure authentication code (that is, which does not rely on computational assumptions) suitable for multicast network coding, where the keying material is initially computed and distributed by a trusted authority to the destinations and intermediate nodes. The proposed scheme allows not only destinations, but also intermediate nodes, to verify the integrity and origin of the packets received without having to decode, and thus detect and discard the malicious messages in transit that fail the verification. This way, the pollution is canceled out before reaching the destinations. The proposed scheme is robust against pollution attacks from outsiders, as well as coalitions of malicious insider nodes, which have the ability to perform the integrity check, but instead get corrupted and use their knowledge to themselves attack the network. We analyze the performance of the scheme in terms of both throughput and goodput and show that the price to pay for tolerating inside attackers is a high decrease in throughput (it is inversely proportional to the number of insider attackers that can collude). We finally discuss applications to file distribution.

The goal of this paper is to design fast-decodable space-time codes for four transmit and two receive antennas. The previous attempts to build such codes have resulted in codes that are not full rank and hence cannot provide full diversity or high coding gains. Extensive work carried out on division algebras indicates that in order to get, not only non-zero but perhaps even non-vanishing determinants (NVD) one should look at division algebras and their orders. To further aid the decoding, we will build our codes so that they consist of four generalized Alamouti blocks which allows decoding with reduced complexity. As far as we know, the resulting codes are the first having both reduced decoding complexity, and at the same time allowing one to give a proof of the NVD property.

We propose the notion of secrecy gain as a code design criterion for wiretap lattice codes to be used over an additive white Gaussian noise channel. Our analysis relies on the error probabilites of both the legitimate user and the eavesdropper. We focus on geometrical properties of lattices, described by their theta series, to characterize good wiretap codes.

In this paper, we present a coding strategy for half duplex wireless relay networks, where we assume no channel knowledge at any of the transmitter, receiver, or relays. The coding scheme uses distributed space-time coding, that is, the relay nodes cooperate to encode the transmitted signal so that the receiver senses a space-time codeword. It is inspired by noncoherent differential techniques. The proposed strategy is available for any number of relays nodes. It is analyzed, and shown to yield a diversity linear in the number of relays. We also study the resistance of the scheme to relay node failures, and show that a network withRrelay nodes anddof them down behaves, as far as diversity is concerned, as a network withR-dnodes. Finally, our construction can be easily generalized to the case where the transmitter and receiver nodes have several antennas.

In this paper, we study code constructions over the finite ring M2(F2), the ring of 2times2 matrices with coefficients in the finite field F2. We show how they can be related to classical codes over F4. We provide as application the design of outer codes for 2 times 2 space-time coded modulation, when the inner code is the so-called Golden code.

Perfect space-time codes are codes for the coherent multiple-input multiple-output (MIMO) channel. They have been called so since they satisfy a large number of design criteria that makes their performances outmatch many other codes. In this correspondence, we discuss the existence of such codes (or more precisely, the existence of perfect codes with optimal signal complexity).

We consider a wireless relay network with no channel information, which implements differential distributed space-time coding. We propose a coding strategy based on Cayley codes, which yields high data rate codes available for an arbitrary number of relay nodes.

We consider the MIMO wiretap channel, that is a MIMO broadcast channel where the transmitter sends some confidential information to one user which is a legitimate receiver, while the other user is an eavesdropper. Perfect secrecy is achieved when the transmitter and the legitimate receiver can communicate at some positive rate, while insuring that the eavesdropper gets zero bits of information. In this paper, we compute the perfect secrecy capacity of the multiple antenna MIMO broadcast channel, where the number of antennas is arbitrary for both the transmitter and the two receivers. Our technique involves a careful study of a Sato-like upper bound via the solution of a certain algebraic Riccati equation.

We propose a coding strategy for wireless relay networks with no channel information based on Cayley differential unitary codes. While satisfying the requirements for differential distributed space-time coding, our scheme furthermore inherits of the advantages of Cayley codes, namely high rate, efficient encoding, and a linearized sphere decoder.

Cyclic codes are diagonal codes originally proposed for differential space-time coding, available in small dimensions (that is small number of antennas). Motivated by the problem of designing codes for wireless relay networks with no channel information, we revisit cyclic codes in an algebraic setting, and propose new constructions with higher rate and in higher dimensions (that is number of relay nodes in the network).

We consider the problem of information-theoretically secure string commitment using a channel with additive white Gaussian noise. While the current results in the literature mainly present existence results for such schemes, we present here a practical scheme using lattice codes and analyze its security parameters for finite code lengths.

In this paper, we present a coding strategy for wireless relay networks where the relay nodes are small devices with few resources, while the source and sink are equipped with multiple antennas to increase the transmission rate. We assume no channel knowledge at all, and the receiver decodes knowing none of the channel paths. This coding scheme uses distributed space-time coding techniques and is inspired by noncoherent differential space-time coding. It is shown to yield a diversity linear in the minimum number of transmit/receive antennas times the number of relays.

This paper considers an orthogonal amplify-and-forward (OAF) protocol for cooperative relay communication over Rayleigh-fading channels in which the intermediate relays are permitted to linearly transform the received signal and where the source and relays transmit for equal time durations. The diversity-multiplexing gain (D-MG) tradeoff of the equivalent space-time channel associated to this protocol is determined and a cyclic-division-algebra-based D-MG optimal code constructed. The transmission or signaling alphabet of this code is the union of the QAM constellation and a rotated version of QAM. The size of this signaling alphabet is small in comparison with prior D-MG optimal constructions in the literature and is independent of the number of participating nodes in the network.

We investigate cyclic algebras for coding over the differential noncoherent channel. Cyclic algebras are an algebraic object that became popular for coherent space-time coding, since it naturally yields linear families of matrices with full diversity. Coding for the differential noncoherent channel has a similar flavor in the sense that it asks for matrices that achieve full diversity, except that these matrices furthermore have to be unitary. In this work, we give a systematic way to find infinitely many unitary matrices inside cyclic algebras, which holds for all dimensions. We show how cyclic algebras generalize previous families of unitary matrices obtained using the representation of fixed-point-free groups. As an application of our technique, we present families of codes for three and four antennas that achieve high coding gain.

Cayley space–time codes have been proposed as a solution for coding over noncoherent differential multiple-input multiple-output (MIMO) channels. Based on the Cayley transform that maps the space of Hermitian matrices to the manifold of unitary matrices, Cayley codes are particularly suitable for high data rate, since they have an easy encoding and can be decoded using a sphere-decoder algorithm. However, at high rate, the problem of evaluating if a Cayley code is fully diverse may become intractable, and previous work has focused instead on maximizing a mutual information criterion. The drawback of this approach is that it requires heavy optimization which depends on the number of antennas and rate. In this work, we study Cayley codes in the context of division algebras, an algebraic tool that allows to get fully diverse codes. We present an algebraic construction of fully diverse Cayley codes, and show that this approach naturally yields, without further optimization, codes that perform similarly or closely to previous unitary differential codes, including previous Cayley codes, and codes built from Lie groups.

In this work, we construct a unified family of cooperative diversity coding schemes for implementing the orthogonal amplify-and-forward and the orthogonal selection-decode-and-forward strategies in cooperative wireless networks. We show that, as the number of users increases, these schemes meet the corresponding optimal high-SNR outage region, and do so with minimal order of signaling complexity. This is an improvement over all outage-optimal schemes which impose exponential increases in signaling complexity for every new network user. Our schemes, which are based on commutative algebras of normal matrices, satisfy the outage-related information theoretic criteria, the duplex-related coding criteria, and maintain reduced signaling, encoding and decoding complexities

This paper studies the design of distributed space-time codes for use in wireless relay networks. Earlier work suggested that a suitable family of codes can be obtained by using linear dispersion codes, provided the basis matrices were unitary. In this paper we construct an explicit algebraic family of such codes where full diversity is proved. The construction uses cyclotomic field theory and yields basis matrices that are indeed unitary. Simulation results show that the codes have better performance than codes designed earlier by ad hoc and random methods, and thus with less encoding complexity

In this work, we give a bound on performance of any full-diversity lattice constellation constructed from algebraic number fields. We show that most of the already available constructions are almost optimal in the sense that any further improvement of the minimum product distance would lead to a negligible coding gain. Furthermore, we discuss constructions, minimum product distance, and bounds for full-diversity complex rotated Z[i]/sup n/-lattices for any dimension n, which avoid the need of component interleaving.

In this paper, we introduce the notion of perfect space-time block codes (STBCs). These codes have full-rate, full-diversity, nonvanishing constant minimum determinant for increasing spectral efficiency, uniform average transmitted energy per antenna and good shaping. We present algebraic constructions of perfect STBCs for 2, 3, 4, and 6 antennas

This paper presents an algebraic construction of families of unitary matrices that achieve full diversity. They are obtained as subsets of cyclic division algebras

Two subspaces of a vector space are here called "nonintersecting" if they meet only in the zero vector. Motivated by the design of noncoherent multiple-antenna communications systems, we consider the following question. How many pairwise nonintersecting M/sub t/-dimensional subspaces of an m-dimensional vector space V over a field F can be found, if the generator matrices for the subspaces may contain only symbols from a given finite alphabet A/spl sube/F? The most important case is when F is the field of complex numbers C; then M/sub t/ is the number of antennas. If A=F=GF(q) it is shown that the number of nonintersecting subspaces is at most (q/sup m/-1)/(q/sup Mt/-1), and that this bound can be attained if and only if m is divisible by M/sub t/. Furthermore, these subspaces remain nonintersecting when "lifted" to the complex field. It follows that the finite field case is essentially completely solved. In the case when F=C only the case M/sub t/=2 is considered. It is shown that if A is a PSK-configuration, consisting of the 2/sup r/ complex roots of unity, the number of nonintersecting planes is at least 2/sup r(m-2)/ and at most 2/sup r(m-1)-1/ (the lower bound may in fact be the best that can be achieved).

In this work, we give a bound on performance of any full-diversity lattice constellation constructed from algebraic number fields. We show that most of the already available constructions are almost optimal in the sense that any further improvement of the minimum product distance would lead to a negligible coding gain.

This paper describes the construction of codewords and subspaces are nonintersecting over the finite field. When the alphabet is a finite field, constructions are lifted to the complex field to obtain maximal diversity differential space-time codes for the noncoherent multiple antenna problems. The construction of codewords (i.e. nonintersecting subspaces) subjects to the constraint that the elements of the codewords use symbols from a fixed, small PSK constellation.

In this correspondence, we present various families of full diversity rotated Z/sup n/-lattice constellations based on algebraic number theory constructions. We are able to give closed-form expressions of their minimum product distance using the corresponding algebraic properties.

We present new algebraic constructions of rotated cubic lattice constellations of prime dimension based on cyclic fields. The resulting constellations have full diversity and can be ranked according to the minimum product distance, a relevant performance parameter for transmission over the Rayleigh fading channel.

We consider the problem of designing codes for the problem of delay-constrained communication in packet networks. We show how good codes for this problem can be characterized as the solution of a pair of semidefinite programs plus a rank constraint. Using this characterization, we formulate the design problem as one of finding suitable graph embeddings into Euclidean space, for a certain family of graphs which represent constraints that these codes most satisfy. In the case of codes in dimension 1, our formulation results in a good approximation algorithm for the classical problem of graph bandwidth, which may be of independent interest.