Step Functions Abiding a Linear Code Sample Clauses

Step Functions Abiding a Linear Code. The question is now: how do we choose a suitable code C and how do we define a permutation ƒ that abides that code? The latter problem is the easier to break down: we define it as the iteration of a round function that abides C. That round function can in turn be defined as a sequence of steps that abide C. We target permutations that can be efficiently implemented in hardware and in software using bitwise Boolean instructions and (cyclic) shifts. With this in mind, we target codes that are linear over GF(2). In a linear [n, k, d]2-code, a codeword satisfies n k linear binary equations, the so-called parity equations. Encoding simply consists in taking the k-bit message and appending n k bits so that the result satisfies the parity equations. We call the appended bits the parity bits. Decoding consists in verifying whether the n-bit vector satisfies the parity equations and if so, truncating to the first k bits. If the parity equations are not satisfied, decoding will return an error message. We consider permutations having a state of b bits. To allow some flexibility in our choice of step functions, we apply a small code in parallel to parts of the state. We call those parts slices. Each slice is n bits wide and has n k bits of redundancy, i.e., its bits satisfy the n k parity equations. We denote the first k bits of a slice as its native part and its last n k bits as the parity part. We index the slices by j from 0 to b/n 1 and denote their number b/n by l, typically a power of two. Orthogonal to the slices, we partition the state in n equally sized limbs. A limb is an array of l bits that are indexed by j from 0 to l 1. In short, we arrange the b bits of the state in a two-dimensional array consisting of n limbs by l slices. As a consequence, we call the first k limbs the native ones and the last n k limbs the parity ones. We propose two types of step functions for the round function: limb adaptation. This modifies a native limb, say with index j, by bitwise adding to it a function φ of the state. It also adds the function φ to each parity limb that depends on native limb j. This is code-abiding as each parity equation remains satisfied. This operation is not inherently invertible and care must be taken in the function φ and the part of the state it operates on. For fault detection it is important to freshly compute φ for every adapted limb. Indeed, if φ would be computed once for all adapted limbs, one fault in its computation could lead to an incorrec...