Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.sysarc.2006.09.007 Byline: Konrad J. Kulikowski, Mark G. Karpovsky, Alexander Taubin Keywords: Side-channel attacks; Robust codes; Fault attacks; Advanced Encryption Standard Abstract: Hardware implementations of cryptographic algorithms are vulnerable to fault analysis attacks. Methods based on traditional fault-tolerant architectures are not suited for protection against these attacks. To detect these attacks we propose an architecture based on robust nonlinear systematic error-detecting codes. These nonlinear codes are capable of providing uniform error detecting coverage independently of the error distributions. They make no assumptions about what faults or errors will be injected by an attacker. Architectures based on these robust constructions have fewer undetectable errors than linear codes with the same n, k. We present the general properties and construction methods of these codes as well as their application for the protection of a cryptographic devices implementing the Advanced Encryption Standard. Author Affiliation: Reliable Computing Laboratory, Boston University, 8 Saint Mary's Street, Boston, MA 02215, United States Article History: Received 2 May 2006; Revised 24 August 2006; Accepted 5 September 2006

A subset C of vertices in an undirected graph G = (V, E) is called a 1-identifying code if the sets I(v) : {u [member of] C : d(u, v) [less than or equal to] 1}, v [member of] V, are nonempty and no two of them are the same set. It is natural to consider classes of codes that retain the identification property under various conditions, e.g., when the sets I (v) are possibly slightly corrupted. We consider two such classes of robust codes. We also consider dynamic identifying codes, i.e., walks in G whose vertices form an identifying code in G. Index Terms--Code, dynamic agent, fault tolerance, graph, grid, hypercube identifying code, multiprocessor architecture.

We consider the problem of data reconciliation, which we model as two separate multisets of data that must be reconciled with minimum communication. Under this model, we show that the problem of reconciliation is equivalent to a variant of the graph coloring problem and provide consequent upper and lower bounds on the communication complexity of reconciliation. Further, we show by means of an explicit construction that the problem of reconciliation is, under certain general conditions, equivalent to the problem of finding error-correcting codes for a general class of errors. Under this equivalence, reconciling with little communication is linked to codes with large size, and vice versa. We show analogous results for the problem of multiset verification, in which we wish to determine whether two multisets are equal using minimum communication. As a result, a wide body of literature in coding theory may be applied to the problems of reconciliation and verification. Index Terms--Data reconciliation and verification, error-correcting codes, graph coloring.

A code C detects error e with probability 1 - Q(e), if Q(e) is a fraction of codewords y such that y, y + e [member of] C. We present a class of optimal nonlinear q-ary systematic (n, [q.sup.k])-codes (robust codes) minimizing over all (n, [q.sup.k])-codes the maximum of Q(e) for nonzero e. We also show that any linear (n, [q.sup.k])-code V with n [less than or equal to] 2k can be modified into a nonlinear (n, [q.sup.k])-code [C.sub.v] with simple encoding and decoding procedures, such that the set E = {e|Q(e) = 1} of undetected errors for [C.sub.v] is a (k - r)-dimensional subspace of V (|E| = [q.sup.k-r] instead of [q.sup.k] for V). For the remaining [q.sup.n] - [q.sup.k-r] nonzero errors, Q(e) [less than or equal to] [q.sup.-r] for q [greater than or equal to] 3 and Q(e) [less than or equal to] [2.sup.-r+1] for q = 2. Index Terms--Minimax criterion for error detection, nonlinear systematic error detecting codes, robust error detection.

In this study, the authors propose a new group testing based (GTB) error control codes (ECCs) approach for improving the reliability of memory structures in computing systems. Compared with conventional single‐ and double‐bit error correcting codes, the GTB codes provide higher reliability at the multi‐byte error correction granularity. The proposed codes are cost‐efficient in their encoding and decoding procedures. Instead of requiring multiplication or inversion over Galois finite field like most multi‐byte ECC schemes, the proposed technique only involves bitwise XOR operations, therefore, significantly reducing the computation complexity and latency. For instance, to correct m errors in a Q‐ary codeword of length N, where Q≥2, the compute complexity is mere O(mNlog⁡Q). The GTB codes trade redundancy for encoding and decoding simplicity, and are able to achieve better code rate than other ECCs of the same trade‐off. The proposed GTB codes lend themselves well to designs with high reliability and low computation complexity requirements, such as storage systems with strong fault tolerance, or compute systems with straggler tolerance, and so on. [ABSTRACT FROM AUTHOR]