Search

Plateaued and bent functions play a significant role in cryptography, sequence theory, coding theory and combinatorics. In 1997, Coulter and Matthews redefined bent functions over any finite field F q where q is a prime power, and established their properties. The objective of this work is to redefine the notion of plateaued functions over F q , and to present several explicit characterizations of those functions. We first give, over F q , the notion of q -ary plateaued functions, which relies on the concept of the Walsh–Hadamard transform in terms of canonical additive character of F q . We then give a concrete example of q -ary plateaued function, that is not vectorial p -ary plateaued function. This suggests that the study of plateaued-ness is also significant for q -ary functions over F q . We finally characterize q -ary plateaued functions in terms of derivatives, Walsh power moments and autocorrelation functions.

We study the combinatorial function L(k, q), the maximum number of nonzero weights a linear code of dimension k over $${\mathbb {F}}_q$$ can have. We determine it completely for $$q=2,$$ and for $$k=2,$$ and provide upper and lower bounds in the general case when both k and q are $$\ge 3.$$ A refinement L(n, k, q), as well as nonlinear analogues N(M, q) and N(n, M, q), are also introduced and studied.

Since 1970, Boolean functions have been the focus of a lot of attention in cryptography. An important topic in symmetric ciphers concerns the cryptographic properties of Boolean functions and constructions of Boolean functions with good cryptographic properties, that is, good resistance to known attacks. An important progress in cryptanalysis areas made in 2003 was the introduction by Courtois and Meier of algebraic attacks and fast algebraic attacks which are very powerful analysis concepts and can be applied to almost all cryptographic algorithms. To study the resistance against algebraic attacks, the notion of algebraic immunity has been introduced. In this paper, we use a parameter introduced by Liu and al., called fast algebraic immunity, as a tool to measure the resistance of a cryptosystem (involving Boolean functions) to fast algebraic attacks. We prove an upper bound on the fast algebraic immunity. Using our upper bound, we establish the weakness of trace inverse functions against fast algebraic attacks confirming a recent result of Feng and Gong.

Let Gk,n be the family of all graphs on the same n vertices each having at least k connected components. We are interested in the largest cardinality of a subfamily in which the union of any two of the member graphs has at most k−2 connected components, and determine its exponential asymptotics.

In any connected, undirected graph G = (V, E), the distance d(x, y) between two vertices x and y of G is the minimum number of edges in a path linking x to y in G. A sphere in G is a set of the form S r (x) = {y ? V : d(x, y) = r}, where x is a vertex and r is a nonnegative integer called the radius of the sphere. We first address in this paper the following question: What is the minimum number of spheres with fixed radius r ? 0 required to cover all the vertices of a finite, connected, undirected graph G? We then turn our attention to the Hamming Hypercube of dimension n, and we show that the minimum number of spheres with any radii required to cover this graph is either n or n + 1, depending on the parity of n. We also relate the two above problems to other questions in combinatorics, in particular to identifying codes.

The notion of permutation capacities is motivated by and shows similarities with the Shannon capacity of graphs and its generalization to directed graphs called Sperner capacity. We show that families of oriented paths have a different behaviour with respect to these capacities than Shannon and Sperner capacities and their generalization to graph families do. The talk is based on the paper [Brightwell, G., G. Cohen, E. Fachini, M. Fairthorne, J. Korner, G. Simonyi, and A. Toth, Permutation capacities of families of oriented infinite paths, SIAM J. Discrete Math. 24 (2010), 441-456].

Let F^n be the binary n-cube, or binary Hamming space of dimension n, endowed with the Hamming distance. For r>=1 and x@?F^n, we denote by B"r(x) the ball of radius r and centre x. A set C@?F^n is said to be an r-identifying code if the sets B"r(x)@?C, x@?F^n, are all nonempty and distinct. We give new constructive upper bounds for the minimum cardinalities of r-identifying codes in the Hamming space.

Korner and Malvenuto asked whether one can find $\binom{n}{\lfloor n/2\rfloor}$ linear orderings (i.e., permutations) of the first $n$ natural numbers such that any pair of them places two consecutive integers somewhere in the same position. This led to the notion of graph-different permutations. We extend this concept to directed graphs, focusing on orientations of the semi-infinite path whose edges connect consecutive natural numbers. Our main result shows that the maximum number of permutations satisfying all the pairwise conditions associated with all of the various orientations of this path is exponentially smaller, for any single orientation, than the maximum number of those permutations which satisfy the corresponding pairwise relationship. This is in sharp contrast to a result of Gargano, Korner, and Vaccaro concerning the analogous notion of Sperner capacity of families of finite graphs. We improve the exponential lower bound for the original problem and list a number of open questions.

International audience; Fuzzy commitment schemes, introduced as a link between biometrics and cryptography, are a way to handle biometric data matching as an error-correction issue. We focus here on finding the best error-correcting code with respect to a given database of biometric data. We propose a method that models discrepancies between biometric measurements as an erasure and error channel, and we estimate its capacity. We then show that two-dimensional iterative min-sum decoding of properly chosen product codes almost reaches the capacity of this channel. This leads to practical fuzzy commitment schemes that are close to theoretical limits. We test our techniques on public iris and fingerprint databases and validate our findings.

Consider a connected undirected bipartite graph G=([email protected]?A,E), with no edges inside I or A. For any vertex [email protected]?V, let N(v) be the set of neighbours of v. A code [email protected]?A is said to be discriminating if all the sets N(i)@?C, [email protected]?I, are nonempty and distinct. We study some properties of discriminating codes in particular classes of bipartite graphs, namely trees and, more generally, (bipartite) planar graphs.

We investigate the packing and covering densities of linear and nonlinear binary codes, and establish a number of duality relationships between the packing and covering problems. Specifically, we prove that if almost all codes (in the class of linear or nonlinear codes) are good packings, then only a vanishing fraction of codes are good coverings, and vice versa: if almost all codes are good coverings, then at most a vanishing fraction of codes are good packings. We also show that any specific maximal binary code is either a good packing or a good covering, in a certain well-defined sense.

Since 2003, algebraic attacks have received a lot of attention in the cryptography literature. In this context, algebraic immunity quantifies the resistance of a Boolean function to the standard algebraic attack of the pseudo-random generators using it as a nonlinear Boolean function. A high value of algebraic immunity is now an absolutely necessary cryptographic criterion for a resistance to algebraic attacks but is not sufficient, because of more general kinds of attacks so-called Fast Algebraic Attacks. In view of these attacks, the study of the set of annihilators of a Boolean function has become very important. We show that studying the annihilators of a Boolean function can be translated into studying the codewords of a linear code. We then explain how to exploit that connection to evaluate or estimate the algebraic immunity of a cryptographic function. Direct links between the theory of annihilators used in algebraic attacks and coding theory are established using an atypical univariate approach.

Minimal linear codes are linear codes such that the support of every codeword does not contain the support of another linearly independent codeword. Such codes have applications in cryptography, e.g. to secret sharing. We pursue here their study and construct asymptotically good families of minimal linear codes. We also push further the study of quasi-minimal and almost-minimal linear codes, relaxations of the minimal linear codes.

Bent functions are maximally nonlinear Boolean functions. They are wonderful creatures introduced by O. Rothaus in the 1960's and studied firstly by J. Dillon since 1974. Using some involutions over finite fields, we present new constructions of bent functions in the line of recent Mesnager's works. One of the constructions is based on an arithmetical problem. We discuss existence of such bent functions using Fermat hypersurface and Lang-Weil estimations.

We study some combinatorial and algorithmic properties of discriminating codes in bipartite graphs. In particular, we provide bounds on minimum discriminating codes and give constructions. We also show that upperbounding the size of a discriminating code is NP-complete.

We treat the problem of bounding components of the possible distance distributions of codes given the knowledge of their size and possibly minimum distance. Using the Beckner inequality from harmonic analysis, we derive upper bounds on distance distribution components which are sometimes better than earlier ones due to Ashikhmin, Barg, and Litsyn. We use an alternative approach to derive upper bounds on distance distributions in linear codes. As an application of the suggested estimates we get an upper bound on the undetected error probability for an arbitrary code of given size. We also use the new bounds to derive better upper estimates on the covering radius, as well as a lower bound on the error-probability threshold, as a function of the code's size and minimum distance.

Let C be a code of length n over an alphabet of q letters. For a pair of integers 2 ≤ t > u, C is (t,u)-hashing if for any two subsets T, U ⊂C, satisfying T ⊂ U, |T| = t, |U| = u, there is a coordinate 1 ≤ i ≤ n such that for any x ∈ T, y ∈ U - x, x and y differ in the ith coordinate. This definition, generalizing the standard notion of a t-hashing family, is motivated by an application in designing the so-called parent identifying codes, used in digital fingerprinting. In this paper, we provide lower and upper bounds on the best possible rate of (t, u)-hashing families for fixed t, u and growing n. We also describe an explicit construction of (t, u)-hashing families. The obtained lower bound on the rate of (t, u)-hashing families is applied to get a new lower bound on the rate of t-parent identifying codes.

In this note, we give a simple proof of the combinatorial conjecture proposed by Tang, Carlet and Tang, based on which they constructed two classes of Boolean functions with many good cryptographic properties. We also give more general properties about the generalisation of the conjecture they propose.

Let τ be a code of length n. Then x is called a descendant of the coalition of codewords a, b, …, ei fxi ∈ {ai, bi…, ei} for i = 1,…, n. We study codes with the following property: any two non intersecting coalitions of a limited size have no common descendant. We present constructions based on linear intersecting codes.

We show that the maximum size of a B2-sequence of binary n-vectors for large enough n is at most 20.5753n, thus improving on the previous bound 20.6n due to B. Lindström.

If C is a p-ary code of length n and a(1) and a(2) are two codewords, then a(3) is called a descendant of a(1) and a(2) if ai(3) ∈ {ai(1), ai(2)} for i = 1,…, n. We are interested in codes C with the property that either any two nonintersecting coalitions of size 2 have no common descendant or the descendant of any coalition of size 3 does not belong to the code. We construct such codes based on Hadamard matrices.

Let C be a code of length n over an alphabet of q letters. An n-word y is called a descendant of a set of t codewords x1, . . . ,xt if $y_i\in\{x^1_i,\dots,x^t_i\}$ for all i=1, . . . ,n. A code is said to have the t-identifying parent property if for any n-word that is a descendant of at most t parents it is possible to identify at least one of them. We prove that for any $t\le q-1$ there exist sequences of such codes with asymptotically nonvanishing rate.

The paper studies self-orthogonal codes over GF (3). The state complexities of such codes of lengths ⩽20 with efficient coordinate ordering are found.

Binary linear codes with length at most one above the Griesmer bound were proven to satisfy the chain condition by Helleseth et al. [1]. Binary linear projective codes with length two above the Griesmer bound which satisfy the chain condition are found. Necessary conditions for binary linear codes for which the two-way chain condition holds are derived.

We estimate the maximum cardinality of binary codes (linear and nonlinear) when arbitrary restrictions are imposed on the set of distances between codewords. We focus in particular on the case when a single distance is forbidden.

A necessary and sufficient condition for a q-ary code to satisfy the two-way chain condition (TCC) is found. A known construction of q-ary codes is shown to yield codes satisfying the TCC. Some q-ary codes of dimension k \leq 6 meeting the Griesmer bound are proved to satisfy the TCC.

In an undirected graph G=(V,E), a subset $C \subseteq V$ is called an identifying code if the sets $B_1(v) \cap C$ consisting of all elements of C within distance one from the vertex v are nonempty and different. We take G to be the infinite hexagonal grid and show that the density of any identifying code is at least 16/39 and that there is an identifying code of density 3/7.

Binary linear codes with length at most one above the Griesmer bound were proven to satisfy the chain condition by Helleseth et al. [T. Helleseth, T. Klove, O. Ytrehus, IEEE Transactions on Information Theory 38 (1992) 1133–1140]. Binary linear projective codes with length two above the Griesmer bound which satisfy the chain condition are found. Necessary conditions for binary linear codes for which the the two-way chain condition holds are derived.

New constructions of binary linear intersecting codes are presented. Some codes with high distances are shown to be intersecting.

A Uniquely Decodable (UD) Code is a code such that any vector of the ambient space has a unique closest codeword. In this paper we begin a study of the structure of UD codes and identify perfect subcodes. In particular we determine all linear UD codes of covering radius \leq 2.

Recently, Steane (1998) proposed an enlargement of the Calderbank-Shor-Steane construction. Here we further improve on the parameters obtained from his construction, present examples of new codes, and analyze asymptotical non-constructive bounds.

Le temporel de l'abbaye benedictine Sainte-Croix de Bordeaux est fortement eprouve par la guerre de Cent Ans, principalement dans son domaine rural. Pour le maintenir, celle-ci use de moyens juridiques nouveaux dans son systeme de perception des redevances et multiplie les constitutions de rentes. Les immeubles urbains font l'objet de soins accrus, les baux a cens sont multiplies. Mais, en depit de plus-values importantes, en raison de la hausse des loyers due a la guerre et de l'accroissement demographique, Sainte-Croix doit se defendre contre la convoitise des bourgeois bordelais qui y effectuent, a partir du debut du XVI e siecle, des placements refuges. Cet essai de reconstitution du patrimoine est mis a mal par les guerres de Religion, l'obligation de payer les decimes, la crise d'autorite seigneuriale, la politique d'alienation de l'abbe Salviati, enfin par des empietements et meme des usurpations conduits par les Jurats de la ville. Seuls les vignobles echappent a ces agressions qui ne connaitront un terme qu'avec l'arrivee des Mauristes a la tete de l'abbaye.

We study a wide class of problems in coding theory for which we consider two different formulations: in terms of incidence matrices and in terms of hypergraphs. These problems are dealt with using a greedy algorithm due to Stein (1974) and Lovasz (1975). Some examples, including constructing covering codes, codes for conflict resolution, separating systems, source encoding with distortion, etc., are given a unified treatment. Under certain conditions derandomization can be performed, leading to an essential reduction in the complexity of the constructions.

We define and estimate the threshold probability /spl theta/ of a linear code, using a theorem of Margulis (1974) originally conceived for the study of the probability of disconnecting a graph. We then apply this concept to the study of the erasure and Z-channels, for which we propose linear coding schemes that admit simple decoding. We show that /spl theta/ is particularly relevant to the erasure channel since linear codes achieve a vanishing error probability as long as p/spl lesspl theta/, where p is the probability of erasure. In effect, /spl theta/ can be thought of as a capacity notion designed for codes rather than for channels. Binomial codes haven the highest possible /spl theta/ (and achieve capacity). As for the Z-channel, a subcapacity is derived with respect to the linear coding scheme. For a transition probability in the range ]log (3/2); 1[, we show how to achieve this subcapacity. As a by-product we obtain improved constructions and existential results for intersecting codes (linear Sperner families) which are used in our coding schemes. >

The average radius of a block code is a parameter that occurs naturally in quantization and steganography. We give asymptotic upper and lower bounds on this parameter. In particular we show that for almost all long codes the normalized average radius equals the normalized covering radius. We survey some special graph-theoretic lower bounds.

Given a set C of q-ary n-tuples and c 2 C, how many symbols of c suffice to distinguish it from the other elements in C ? This is a generalization of an old combinatorial problem, on which we present (asymptotically tight) bounds and variations.

Kloosterman sums have recently become the focus of much research, most notably due to their applications in cryptography and their relations to coding theory. Very recently Mesnager has showed that the value 4 of binary Kloosterman sums gives rise to several infinite classes of bent functions, hyper-bent functions and semi-bent functions in even dimension. In this paper we analyze the different strategies used to find zeros of binary Kloosterman sums to develop and implement an algorithm to find the value 4 of such sums. We then present experimental results showing that the value 4 of binary Kloosterman sums gives rise to bent functions for small dimensions, a case with no mathematical solution so far.

We extensively investigate the link between the semi-bentness property of some Boolean functions in polynomial forms and Kloosterman sums.

A write-isolated memory (WIM) is a binary storage medium on which no change of two consecutive positions is allowed when updating the information stored. We prove that the optimal rate for writing on a WIM is log 2 (1+ 5 ) 2 =0.69 . We give asymptotic constructions achieving 0.6.

Fault diagnosis of multiprocessor systems motivates the following graph-theoretic definition. A subset C of points in an undirected graph G=(V, E) is called an identifying code if the sets B(v)/spl cap/C consisting of all elements of C within distance one from the vertex v are different. We also require that the sets B(v)/spl cap/C are all nonempty. We take G to be the infinite square lattice with diagonals and show that the density of the smallest identifying code is at least 2/9 and at most 4/17.

Identification codes were introduced by Ahlswede and Dueck more than twenty years ago. There is today a lot of studies to identify objects such as contactless devices (for instance RFID tags) but, surprisingly, no one has considered the use of this kind of codes in the literature for that purpose until the recent work of Bringer et al. at Indocrypt '09. We here show how the security of these new identification protocols is related to some well-known problems in coding theory. We also extend the original proposal to a new problem.

Motivated by certain recent problems in asynchronous communication, we introduce and study B(n, d, w), defined as the maximum number of length n binary sequences with minimum distance d, and such that each sequence has weight at least w. Specifically, we investigate the asymptotic exponential growth rate of B(n, d, w) with respect to n and with fixed ratios δ = d/n and ω = w/n. For ω ∈ [0, 1/2], this growth rate function b(δ, ω) is shown to be equal to a(δ), the asymptotic exponential growth rate of A(n, d) — the maximum number of length n binary sequences with minimum distance d. For ω ∈ (1/2, 1], we show that b(δ, ω) ≤ a(δ, ω) + f(ω), where a(δ, ω) denotes the asymptotic exponential growth rate of A(n, d, w), the maximum number of length n binary sequences with minimum distance d and constant weight w, and where f(w) is a certain function that satisfies 0 ω→1 f(ω) = lim ω→1/2 f(ω) = 0. Based on numerical evidence, we conjecture that b(δ, ω) is actually equal to a(δ, ω) for ω ∈ (1/2, 1]. Finally, lower bounds on B(n, d, w) are obtained via explicit code constructions.

Starting from a practical use of Reed-Solomon codes in a cryptographic scheme published in Indocrypt'09, this paper deals with the threshold of linear $q$-ary error-correcting codes. The security of this scheme is based on the intractability of polynomial reconstruction when there is too much noise in the vector. Our approach switches from this paradigm to an Information Theoretical point of view: is there a class of elements that are so far away from the code that the list size is always superpolynomial? Or, dually speaking, is Maximum-Likelihood decoding almost surely impossible? We relate this issue to the decoding threshold of a code, and show that when the minimal distance of the code is high enough, the threshold effect is very sharp. In a second part, we explicit lower-bounds on the threshold of Maximum-Distance Separable codes such as Reed-Solomon codes, and compute the threshold for the toy example that motivates this study., Comment: Sumitted to ISIT 2010