Code-Based Masking (CBM) has been introduced to enhance high-order Boolean masking by increasing its resistance order via further decorrelating the coordinates of each symbol involved in the computation. Additionally, CBM enables cost amortization and fault detection. Notably, as demonstrated at CHES 2024, CBM facilitates the computation of provably masked operations under the Strong Non-Interference (SNI) security assumption with quasi-linear complexity. On the other hand, Threshold Implementation (TI) serves as an extension of Boolean masking, armoring it against combinational hazards. In this article, we show that merits of CBM and TI can be combined, paving the way to more secure hardware (high-order) masked implementations. We demonstrate CBM-TI, which is proven secure as well under SNI assumption and security when glitches worsen the leakage model.The security of CBM-TI is studied in a n-share setting, where n = 3 (minimal random splitting order required for TI). We analyzed CBM-TI in simulation and in real hardware (FPGA) to validate its security property. Leveraging high-order T-test leakage detection tool, we show that CBM-TI is endowed with higher-order security. Namely, TI leaks at order d = 3, whereas CBM-TI does not. We study several CBM-TI variants and show that the smallest leaking order of CBM-TI can be tuned to be as high as 7. This represents a significant progress over TI as each marginally improved order translates into exponentially more traces to attack the implementation.

This paper presents an explicit construction of multimedia codes with complete traceability resistant to the averaging attack and δ-noise. The obtained code is a combination of a class of signature codes together with a generalization of superimposed codes, for which existence lower bounds, using the Lovász Local Lemma, are obtained. The constructions are a consequence of the Moser-Tardos variable framework.

Let a binary Reed-Muller code RM(s;m) of length n be used on a memoryless channel with an input alphabet ±1 and a real-valued output ℝ. Given a received vector y in ℝn; we define its generalized distance T to any codeword c as the sum Σ|yj|taken over all positions j, in which vectors y, c have opposite signs. We then consider the list ℒTof codewords located within distance T from the received vector y and estimate the size LTof this list using the generalized Johnson bound. For any RM code RM(s,m) of fixed order s, the algorithm is proposed that performs list decoding beyond the error-correcting radius with linear complexity in length n and retrieves the code list ℒTwith complexity of order nsLTfor any decoding radius T within the generalized Johnson bound.

Codes with the identifiable parent property (IPP codes) are used in traitor tracing schemes that protect data broadcast by the publisher from unauthorized access or distribution. An n-word y over a finite alphabet is called a descendant of a set of t words x1, ..., xtif yiϵ {x1i, ..., xti} for all i = 1, ... n. A code C = {x1, ..., xM} is said to have the i-IPP property if for any n-word y that is a descendant of at most t parents belonging to the code it is possible to identify at least one of them. The existence of good i-IPP codes is known from earlier works. We introduce a robust version of IPP codes which allows unconditional identification of parents even if some of the coordinates in y can break away from the descent rule, i.e., can take arbitrary values from the alphabet, or become completely unreadable. By linking this problem to perfect hash functions and, more generally, to hash distances of a code, we prove initial results on the proportion of such coordinates that can be tolerated under the unconditional recovery requirement.

Let a biorthogonal Reed-Muller code RM (1,m) of length n = 2mbe used on a memoryless channel with an input alphabet plusmn1 and a real-valued output R. Given any nonzero received vector y in the Euclidean space Rnand some parameter epsiisin(0,1), our goal is to perform list decoding of the code RM (1, m) and retrieve all codewords located within the angle arccos e from y. For an arbitrarily small epsi, we design an algorithm that outputs this list of codewords with the linear complexity order of n [ln2isin] bit operations. Without loss of generality, let vector y be also scaled to the Euclidean length radic(n) of the transmitted vectors. Then an equivalent task is to retrieve all coefficients of the Hadamard transform of vector y whose absolute values exceed nisin. Thus, this decoding algorithm retrieves all ne-significant coefficients of the Hadamard transform with the linear complexity n [ln2isin] instead of the complexity n In2n of the full Hadamard transform.

Soft-decision decoding on a memoryless channel is considered for the first-order Reed-Muller codes RM (1, m) of length 2m. We assume that different positions j of the received binary vector y can be corrupted by the errors of varying weight wj. The generalized Hamming distance between vector y and any binary vector c is then defined as the sum of weighted differences wj|yj- cj| taken over all n positions. We obtain a tight upper bound LTon the number of codewords located within generalized Hamming distance T from vector y, and design a decoding algorithm that outputs this list of codewords with complexity O (n ln2LT). In particular, all possible error weights wjequal 1 if this combinatorial model is applied to a binary symmetric channel. In this case, the well known Green algorithm performs full maximum likelihood decoding of RM (1, m) and requires O (n ln2n) bit operations, whereas the Litsyn-Shekhovtsov algorithm operates within the bounded-distance decoding radius n/4-1 with linear complexity O(n). We close the performance-complexity gap between the two algorithms. Namely, for any fixed (0, ½), our algorithm outputs the complete list of codewords within the decoding radius n(½-) with linear complexity of order n ln2.

A new deterministic list decoding algorithm is proposed for general Reed-Muller codes RM(s,m) of length n = 2mand distance d = 2m-epsi. Given n and d, the algorithm performs beyond the bounded distance threshold of d/2 and has a low complexity order of nmepsi-1for any decoding radius T that is less than the Johnson bound

The maximum-length sequences, also called m-sequences, have received a lot of attention since the late 1960s. In terms of linear-feedback shift register (LFSR) synthesis they are usually generated by certain power polynomials over a finite field and in addition are characterized by a low cross correlation and high nonlinearity. We say that such a sequence is generated by a semi-bent function. Some new families of such function, represented by f(x)=/spl Sigma//sub i=1//sup (n-1)/2/c/sub i/Tr(x(2/sup i/)+1), n odd and c/sub i//spl isin/F/sub 2/, have recently (2002) been introduced by Khoo et al. We first generalize their results to even n. We further investigate the conditions on the choice of c/sub i/ for explicit definitions of new infinite families having three and four trace terms. Also, a class of nonpermutation polynomials whose composition with a quadratic function yields again a quadratic semi-bent function is specified. The treatment of semi-bent functions is then presented in a much wider framework. We show how bent and semi-bent functions are interlinked, that is, the concatenation of two suitably chosen semi-bent functions will yield a bent function and vice versa. Finally, this approach is generalized so that the construction of both bent and semi-bent functions of any degree in certain range for any n/spl ges/7 is presented, n being the number of input variables.