Search

In this paper, a coding-theory construction of Cartesian authentication codes is presented. The construction is a generalization of some known constructions. Within the framework of this generic construction, several classes of authentication codes using certain classes of error-correcting codes are described. The authentication codes presented in this paper are better than known ones with comparable parameters. It is demonstrated that the construction is related to certain combinatorial designs, such as difference matrices and generalized Hadamard matrices. Index Terms--Authentication codes, coding theory, cryptography.

In this correspondence, we present a family of binary [2.sup.n] sequences of period 2([2.sup.n] - 1) where n is an integer, which can be seen as a generalization of nonlinear binary sequences obtained from [Z.sub.4] sequences and recently constructed GKW (Gold, Kasami, and Welch)-like sequences. The sequences have low correlations and are useful in code-division multiple-access (CDMA) communication systems and cryptography.

Recently, algebraic attacks have received a lot of attention in the cryptographic literature. It has been observed that a Boolean function f used as a cryptographic primitive, and interpreted as a multivariate polynomial over [F.sub.2], should not have low degree multiples obtained by multiplication with low degree onzero functions. In this paper, we show that a Boolean function having low nonlinearity is (also) weak against algebraic attacks, and we extend this result to higher order nonlinearities. Next, we present enumeration results on linearly independent annihilators. We also study certain classes of highly nonlinear resilient Boolean functions for their algebraic immunity. We identify that functions having low-degree subfunctions are weak in terms of algebraic immunity, and we analyze some existing constructions from this viewpoint. Further, we present a construction method to generate Boolean functions on n variables with highest possible algebraic immunity [n/2] (this construction, first presented at the 2005 Workshop on Fast Software Encryption (FSE 2005), has been the first one producing such functions). These functions are obtained through a doubly indexed recursive relation. We calculate their Hamming weights and deduce their nonlinearities; we show that they have very high algebraic degrees. We express them as the sums of two functions which can be obtained from simple symmetric functions by a transformation which can be implemented with an algorithm whose complexity is linear in the number of variables. We deduce a very fast way of computing the output to these functions, given their input. Index Terms--Algebraic attacks, annihilators, Boolean functions, nonlinearity, stream ciphers, Walsh spectrum.

We consider the Shannon cipher system in a setting where the secret key is delivered to the legitimate receiver via a channel with limited capacity. For this setting, we characterize the achievable region in the space of three figures of merit: the security (measured in terms of the equivocation), the compressibility of the cryptogram, and the distortion associated with the reconstruction of the plaintext source. Although lossy reconstruction of the plaintext does not rule out the option that the (noisy) decryption key would differ, to a certain extent, from the encryption key, we show, nevertheless, that the best strategy is to strive for perfect match between the two keys, by applying reliable channel coding to the key bits, and to control the distortion solely via rate-distortion coding of the plaintext source before the encryption. In this sense, our result has a flavor similar to that of the classical source-channel separation theorem. Some variations and extensions of this model are discussed as well. Index Terms--Cryptugraphy, eucryption, key distribution, Shannon cipher system, source-channel separation.