Catálogo de publicaciones - libros

Since the introduction of the notions of nonlinearity in the mid-70’s (the term has been in fact introduced later), of correlation immunity and resiliency in the mid-80’s, and of algebraic immunity recently, the problem of efficiently constructing Boolean functions satisfying, at high levels, one or several of these criteria has received much attention. Only few primary constructions are known, and secondary constructions are also necessary to obtain functions achieving or approaching the best possible cryptographic characteristics. After recalling the background on cryptographic criteria and making some general observations, we try to give a survey of all these constructions and their properties. We then show that a nice and simple property of Boolean functions leads to a general secondary construction building an -variable function from three known -variable functions. This construction generalizes secondary constructions recently obtained for Boolean bent functions and also leads to secondary constructions of highly nonlinear balanced or resilient functions, with potentially better algebraic immunities than the three functions used as building blocks.

An ordinary parity-check is an extra bit appended to a block (, ..., ) of information bits such that the resulting codeword (, ..., ,) is capable of detecting one error. The choices for are

 =  + ... +  ( 2) ()

 =  + ... +  + 1 ( 2) ()

In this paper we consider defining a parity-check if the underlying alphabet is nonbinary. The obvious definition is of course

 =  + ... +  + ().

We shall show that this obvious choice is the only choice for =2, and up to a natural equivalence the only choice for =3. For ≥ 4, however, the situation is much more complicated.

The bilinear mapping technique that uses the (Weil and Tate) pairings over elliptic (or hyperelliptic) curves represents a great breakthrough in cryptography. This paper surveys this new trend in cryptography, and emphasizes the design of efficient cryptographic primitives that are provably secure in the standard model (i.e., without the random oracle model).

Binary sequences with small aperiodic correlations play an important role in many applications ranging from radar to modulation and testing of systems. In 1977, M. Golay introduced the as a measure of the goodness of the sequence and conjectured an upper bound for this. His conjecture is still open. In this paper we survey the known results on the Merit Factor problem and comment on the recent experimental results by R.A.Kristiansen and M. Parker and by P. Borwein,K.-K.S.Choi and J. Jedwab.

We consider the problem of determining the period of a binary sequence. For sequences with small autocorrelation we prove the existence of a polynomial time quantum algorithm for the above problem based on an algorithm of Hales and Hallgren. We apply this result to several concrete examples for which the autocorrelation can be estimated using known bounds on character sums.

We introduce the vector key equation for cyclic codes with more than one set of consecutive roots. Using the lattice basis reduction multisequence shift register synthesis algorithm [7, 8], we find the minimal solution to the vector equation key and also give an important parameter of the multiple sequences, that is, characteristic sequence. Using it, we give a simpler sufficient and necessary condition for the uniqueness of the minimal polynomial of multiple sequences than that in [7]. The new approach enables us not only to decode cyclic codes up to HT and Roos bounds and but also to find out certain error patterns which can be decoded beyond the two bounds.

We show herein that a pattern based on FGLM techniques can be used for computing Gröbner bases, or related structures, associated to linear codes. This Gröbner bases setting turns out to be strongly related to the combinatorics of the codes.

Highly nonlinear functions are important as sources of low-correlation sequences, high-distance codes and cryptographic primitives, as well as for applications in combinatorics and finite geometry.

We argue that the theory of such functions is best seen in terms of splitting factor pairs. This introduces an extra degree of freedom, through the pairing of a normalised function : → between groups with a homomorphism .

From this perspective we introduce a new definition of equivalence for functions, relative to , and show it preserves their difference distributions. When it includes CCZ and generalised linear equivalence, as well as planar and linear equivalence.

More generally, we use splitting factor pairs to relate several important measures of nonlinearity. We propose approaches to both linear approximation theory and bent functions, and to difference distribution theory and perfect nonlinear functions, which encompass the current approaches.

We will completely describe the solutions of the equation ( + 1) =  + 1 in the field (), where  =  and is of Niho type, i.e.,  ≡ 1 ( − 1). Our results have applications in the theory of cross-correlation functions of -sequences and in the theory of cyclic codes.

The standard construction of linear error-correcting codes on algebraic curves requires determining a basis for the Riemann-Roch space (  associated to a given divisor , often a hard problem. Here we consider the problem of constructing the code without any knowledge of such a basis. We interpret the columns of a generator matrix as points on an embedded copy of the curve, and show that in certain cases these points can be realized in principle as the images of a set of vector bundles under a standard map to a class of repartitions.