Power analysis attack resilient block cipher implementation based on 1-of-4 data encoding

Side-channel attacks pose an inevitable challenge to the implementation of cryptographic algorithms, and it is important to mitigate them. This work identifies a novel data encoding technique based on 1-of-4 codes to resist differential power analysis attacks, which is the most investigated category of side-channel attacks. The four code words of the 1-of-4 codes, namely (0001, 0010, 1000, and 0100), are split into two sets: set-0 and set-1. Using a select signal, the data processed in hardware is switched between the two encoding sets alternately such that the Hamming weight and Hamming distance are equalized. As a case study, the proposed technique is validated for the NIST standard AES-128 cipher. The proposed technique resists differential power analysis performed using statistical methods, namely correlation, mutual information, difference of means, and Welch's t-test based on the Hamming weight and distance models. The experimental results show that the proposed countermeasure has an area overhead of 2.3× with no performance degradation comparatively.     

Asymptotically Gaussian weight distribution and performance of multicomponent turbo block codes and product codes

It was suggested by Battail that a good long linear code should have a weight distribution close to that of random coding, rather than a large minimum distance, and a turbo code should be also designed using a random-like criterion. In this paper, we first show that the weight distribution of a high-rate linear block code is approximately Gaussian if the code rate is close enough to one, and then proceed to construct a low-rate linear block code with approximately Gaussian weight distribution by using the turbo-coding technique. We give a sufficient condition under which the weight distribution of multicomponent turbo block (MCTB) codes (multicomponent product (MCP) codes, respectively) can approach asymptotically that of random codes, and further develop two classes of MCTB codes (MCP codes) satisfying this condition. Simulation results show that MCTB codes (MCP codes) having asymptotically Gaussian weight distribution can asymptotically approach Shannon's capacity limit. MCTB codes based on single parity-check (SPC) codes have a far poorer minimum distance than MCP codes based on SPC codes, but we show by simulation that when the bit-error rate is in the important range of 10/sup -1/-10/sup -5/, these codes can still offer similar performance for the additive white Gaussian noise channel, as long as the code length of the SPC codes is not very short. These facts confirm in a more precise way Battail's inference about the "nonimportance" of the minimum distance for a long code.     

Space-time turbo codes with full antenna diversity

In attempting to find a spectrally and power efficient channel code which is able to exploit maximum diversity from a wireless channel whenever available, we investigate the possibility of constructing a full antenna diversity space-time turbo code. As a result, both three-antenna and two-antenna (punctured) constructions are shown to be possible and very easy to find. To check the decodability and performance of the proposed codes, we derive non-binary soft-decoding algorithms. The performance of these codes are then simulated and compared with two existing space-time convolutional codes (one has minimum worst-case symbol-error probability; the other has maximal minimum free distance) having similar decoding complexity. As the simulation results show, the proposed space-time turbo codes give similar or slightly better performance than the convolutional codes under extremely slow fading. When fading is fast, the better distance spectra of the turbo codes help seize the temporal diversity. Thus, the performance advantage of the turbo codes becomes evident. In particular, 10^-5 bit-error rate and 10^-3 frame-error rate can be achieved at less than 6-dB E_b/N₀ with 1 b/s/Hz and binary phase-shift keying modulation. The practical issue of obtaining the critical channel state information (CSI) is also considered by applying an iteratively filtered pilot symbol-assisted modulation technique. The penalty when the CSI is not given a priori is about 2-3 dB     

On multilevel block modulation codes

The multilevel technique for combining block coding and modulation is investigated. A general formulation is presented for multilevel modulation codes in terms of component codes with appropriate distance measures. A specific method for constructing multilevel block modulation codes with interdependency among component codes is proposed. Given a multilevel block modulation code C with no interdependency among the binary component codes, the proposed method gives a multilevel block modulation code C' that has the same rate as C, a minimum squared Euclidean distance not less than that of C, a trellis diagram with the same number of states as that of C, and a smaller number of nearest neighbor codewords than that of C . Finally, a technique is presented for analyzing the error performance of block modulation codes for an additive white Gaussian noise (AWGN) channel based on soft-decision maximum likelihood decoding. Error probabilities of some specific codes are evaluated by simulation and upper bounds based on their Euclidean weight distributions     

Identifying Codes and Covering Problems

The identifying code problem for a given graph involves finding a minimum set of vertices whose neighborhoods uniquely overlap at any given graph vertex. Initially introduced in 1998, this problem has demonstrated its fundamental nature through a wide variety of applications, such as fault diagnosis, location detection, and environmental monitoring, in addition to deep connections to information theory, superimposed and covering codes, and tilings. This work establishes efficient reductions between the identifying code problem and the well-known set-covering problem, resulting in a tight hardness of approximation result and novel, provably tight polynomial-time approximations. The main results are also extended to $r$ -robust identifying codes and analogous set $(2r+1)$-multicover problems. Finally, empirical support is provided for the effectiveness of the proposed approximations, including good constructions for well-known topologies such as infinite two-dimensional grids.      

Studying the locator polynomials of minimum weight codewords of BCHcodes

Primitive binary cyclic codes of length n=2^m are considered. A BCH code with designed distance δ is denoted B(n,δ). A BCH code is always a narrow-sense BCH code. A codeword is identified with its locator polynomial, whose coefficients are the symmetric functions of the locators. The definition of the code by its zeros-set involves some properties for the power sums of the locators. Moreover, the symmetric functions and the power sums of the locators are related to Newton's identities. An algebraic point of view is presented in order to prove or disprove the existence of words of a given weight in a code. The principal result is the true minimum distance of some BCH codes of length 255 and 511. which were not known. The minimum weight codewords of the codes B(n2^h -1) are studied. It is proved that the set of the minimum weight codewords of the BCH code B(n,2^m-2-1) equals the set of the minimum weight codewords of the punctured Reed-Muller code of length n and order 2, for any m     

Interleaver design for serially concatenated convolutional codes: theory and application

This paper addresses the problem of interleaver design for serially concatenated convolutional codes (SCCCs) tailored to the constituent codes of the SCCC configuration. We present a theoretical framework for interleaver optimization based on a cost function closely tied to the asymptotic bit-error rate (BER) of the block code C/sub s/ resulting from proper termination of the constituent codes in the SCCC code. We define a canonical form of the interleaving engine denoted as the finite state permuter (FSP) and using its structural property, develop a systematic iterative technique for construction of interleavers. The core theoretical results focus on the asymptotic behavior of a class of cost functions and their martingale property, which is then used to develop an order recursive interleaver optimization algorithm. We address the issue of the complexity of the interleaver growth algorithm presented in the paper and demonstrate that it has polynomial complexity. Subsequently, we provide details about the application of the proposed technique and present a modification of the algorithm that employs error pattern feedback for improved performance at a reduced complexity. Sample experimental results are provided for an SCCC code of rate 1/3 and information block length 320 that achieves a minimum distance of d/sub min/=44.     

On constructing embedded multilevel trellis codes

A design technique to reduce the search time for trellis codes with multilevel phase modulation is presented. Codes are constructed by connecting trellis diagrams for codes with fewer states in parallel. For example, an N-state code can be constructed by connecting two N/2-state codes. The way in which the embedded codes are connected increases the upper limit on minimum free distance otherwise imposed by parallel transitions between states. In some cases, this technique can reduce the number of codes in a code search by a factor of approximately 2^ν, the number of coder states. A computer search incorporating this technique for eight-level amplitude modulation (8-AM) codes having 2¹¹ and 2¹² states produced codes with greater minimum free distance than reported previously (i.e. greater than 6 dB coding gain). New eight-level phase-shift-keying (8-PSK) codes, which have a different structure from previously reported codes, are also presented     

A Decomposition Theory for Binary Linear Codes

The decomposition theory of matroids initiated by Paul Seymour in the 1980s has had an enormous impact on research in matroid theory. This theory, when applied to matrices over the binary field, yields a powerful decomposition theory for binary linear codes. In this paper, we give an overview of this code decomposition theory, and discuss some of its implications in the context of the recently discovered formulation of maximum-likelihood (ML) decoding of a binary linear code over a binary-input discrete memoryless channel as a linear programming problem. We translate matroid-theoretic results of Grotschel and Truemper from the combinatorial optimization literature to give examples of nontrivial families of codes for which the ML decoding problem can be solved in time polynomial in the length of the code. One such family is that consisting of codes for which the codeword polytope is identical to the Koetter-Vontobel fundamental polytope derived from the entire dual code C^perp. However, we also show that such families of codes are not good in a coding-theoretic sense-either their dimension or their minimum distance must grow sublinearly with code length. As a consequence, we have that decoding by linear programming, when applied to good codes, cannot avoid failing occasionally due to the presence of pseudocode words.     

Asymptotically dense spherical codes .II. laminated spherical codes

For pt. I see ibid., vol.43, no.6, p.1774-85, 1997. New spherical codes called laminated spherical codes are constructed in dimensions 2-49 using a technique similar to the construction of laminated lattices. Each spherical code is recursively constructed from existing spherical codes in one lower dimension. Laminated spherical codes outperform the best known spherical codes in the minimum distance sense for many code sizes. The density of a laminated spherical code approaches the density of the laminated lattice in one lower dimension, as the minimum distance approaches zero. In particular, the three-dimensional laminated spherical code is asymptotically optimal, in the sense that its density approaches the Fejes Toth (1959) upper bound as the minimum distance approaches zero. Laminated spherical codes perform asymptotically as well as wrapped spherical codes in those dimensions where laminated lattices are optimal sphere packings     

Performance of a general decoding technique over the class ofrandomly chosen parity check codes

The paper extends a general decoding technique developed by Metzner and Kapturowski (1990) for concatenated code outer codes and for file disagreement location. That work showed the ability to correct most cases of d-2 or fewer erroneous block symbols, where d is the outer code minimum distance. Any parity check code can be used as the basis for the outer codes, and yet decoding complexity increases at most as the third power of the code length. In this correspondence, it is shown that, with a slight modification and no significant increase in complexity, the general decoding technique can be applied to the correction of many other cases beyond the code minimum distance. By considering average performance over all binary randomly chosen codes, it is seen that most error patterns of t_M or fewer block errors can be corrected, where: 1) t_M in most cases is much greater than the code minimum distance, and 2) asymptotically, the ratio of t_M to the theoretical maximum (the number of parity symbol blocks) approaches 1. Moreover, most cases of noncorrectable error block patterns are detected     

A Fault Detection Scheme for the FPGA Implementation of SHA-1 and SHA-512 Round Computations

The Secure Hash Algorithm is the most popular hash function currently used in many security protocols such as SSL and IPSec. Like other cryptographic algorithms, the hardware implementation of hash functions is of great importance for high speed applications. Because of the iterative structure of hash functions, a single error in their hardware implementation could result in a large number of errors in the final hash value. In this paper, we propose a novel time-redundancy-based fault diagnostic scheme for the implementation of SHA-1 and SHA-512 round computations. This scheme can detect permanent as well as transient faults as opposed to the traditional time redundancy technique which is only capable of detecting transient errors. The proposed design does not impose significant timing overhead to the original implementation of SHA-1 and SHA-512 round computation. We have implemented the proposed design for SHA-1 and SHA-512 on Xilinx xc2p7 FPGA. It is shown that for the proposed fault detection SHA-1 and SHA-512 round computations, there are, respectively, 3% and 10% reduction in the throughput with 58% and 30% area overhead as compared to the original schemes. The fault simulation of the implementation shows that almost 100% fault coverage can be achieved using the proposed scheme for transient and permanent faults.     

Hard- and soft-decision decoding beyond the half minimum distance---An algorithm for linear codes (Corresp.)

A decoding algorithm for linear codes that uses the minimum weight words of the dual code as parity checks is defined. This algorithm is able to correct beyond the half minimum distance and has the capability of including soft-decision decoding. Results on applying this algorithm to quadratic residue (QR) codes, BCH codes, and the Golay codes (with and without soft-decision decoding) are presented.     

Tailbiting codes obtained via convolutional codes with large active distance-slopes

The slope of the active distances is an important parameter when investigating the error-correcting capability of convolutional codes and the distance behavior of concatenated convolutional codes. The slope of the active distances is equal to the minimum average weight cycle in the state-transition diagram of the encoder. A general upper bound on the slope depending on the free distance of the convolutional code and new upper bounds on the slope of special classes of binary convolutional codes are derived. Moreover, a search technique, resulting in new tables of rate R=1/2 and rate R=1/3 convolutional encoders with high memories and large active distance-slopes is presented. Furthermore, we show that convolutional codes with large slopes can be used to obtain new tailbiting block codes with large minimum distances. Tables of rate R=1/2 and rate R=1/3 tailbiting codes with larger minimum distances than the best previously known quasi-cyclic codes are given. Two new tailbiting codes also have larger minimum distances than the best previously known binary linear block codes with same size and length. One of them is also superior in terms of minimum distance to any previously known binary nonlinear block code with the same set of parameters.     

Difference set codes: codes with squared Euclidean distance of sixfor partial response channels

We present a new construction of block codes for the (1-D)-PR (partial response) channel. The codewords in the code correspond to constant-sum subsets of a difference set. It is shown that at the output of a noiseless (1-D)-PR channel; the minimum squared Euclidean distance of such a code is at least six, compared to two for the uncoded system. This construction yields larger code rates than previously known codes with the same minimum distance for large code lengths. The construction technique also imposes upper bounds on the decoding complexity of the codes     

一种构造BCM码的新方法

由Imai与Hirakawa提出的多级编码方法,可用来构造具有任意大最小平方欧氏距离的分组调制(BCM)码.一个BCM码的性能主要取决于构成它的各个成分码,恰当地选择成分码是构造一个好的BCM码的关键.文章给出了一种新方法,通过选用不同长度的成分码来构造BCM码.仿真结果表明用此方法构造出的BCM码较传统的BCM码在性能与复杂度上有明显的改善.     

Shadow bounds for self-dual codes

Conway and Sloane (1990) have previously given an upper bound on the minimum distance of a singly-even self-dual binary code, using the concept of the shadow of a self-dual code. We improve their bound, finding that the minimum distance of a self-dual binary code of length n is at most 4[n/24]+4, except when n mod 24=22, when the bound is 4[n/24]+6. We also show that a code of length a multiple of 24 meeting the bound cannot be singly-even. The same technique gives similar results for additive codes over GF(4) (relevant to quantum coding theory)     

几种LDPC码的最小汉明距离的计算

本文提出一种计算LDPC码的真实最小汉明距离的方法．该方法能够用来计算多种LDPC码方案的真实最小汉明距离，比如准循环LDPC码、pi-旋转LDPC码等．该方法是通过计算码的环长间接地找到LDPC码最小距离，由于计算环长的计算量要远比直接计算最小汉明距离来得低，因而该算法能够在有限时间内找到LDPC码的真实最小距离．通过仿真表明，用目前主流的个人计算机利用该方法找出一个有最小距离24的码率为1／4的准循环LDPC码最小距离大概需要花77分钟。     

Iterative Decoding Convergence and Termination of Serially Concatenated Codes

In this paper, we demonstrate that the previously proposed arrangements of serially concatenated codes have extrinsic-information-transfer (EXIT) functions that intersect each other at points that are near but not at the (1, 1) point in the top-right-hand corner of the EXIT chart, which is typically associated with elevated error floors. We propose a novel arrangement having EXIT functions that do not intersect before the (1, 1) point, which is typically associated with approaching the maximum-likelihood (ML) bit-error-ratio (BER) performance. Our method employs an inner recursive code that is terminated using specifically designed termination sequences, which have a minimum Hamming distance of at least two between each other. Additionally, we provide optimal termination sequences for a range of inner code designs. Finally, we demonstrate that our novel approach can facilitate useful BER reductions in the challenging application scenario when employing short frame lengths on the order of 100 bits, which are typical in wireless sensor networks, for example.      

Multidimensional M-PSK trellis codes for fading channels

This paper investigates the code search problem for trellis-coded multidimensional phase modulation for Rayleigh fading channels. New set partitionings for multiple phase-shift keying (M-PSK) are proposed using the effective code length (ECL) and the minimum product distance (PD) as the code design criteria. By using these set-partitionings rules, new multidimensional codes which are optimum for Rayleigh fading channels are constructed. The proposed codes compare favorably with the existing multidimensional trellis codes on fading channels in terms of bit error performance. The bit error performance is evaluated by simulation