International Journal of Foundations of Computer Science

A function F from F_pⁿ to itself is planar if for any the function F(x+a)-F(x) is a permutation. CCZ-equivalence is the most general known equivalence relation of functions preserving planar property. This paper considers two possible extensions of CCZ-equivalence for functions over fields of odd characteristics, one proposed by Coulter and Henderson and the other by Budaghyan and Carlet. We show that the second one in fact coincides with CCZ-equivalence, while using the first one we generalize one of the known families of PN functions. In particular, we prove that, for any odd prime p and any positive integers n and m, the indicators of the graphs of functions F and F' from F_pⁿ to F_p^m are CCZ-equivalent if and only if F and F′ are CCZ-equivalent.

We also prove that, for any odd prime p, CCZ-equivalence of functions from F_pⁿ to F_p^m, is strictly more general than EA-equivalence when n ≥ 3 and m is greater or equal to the smallest positive divisor of n different from 1.

The nonlinearity profile of Boolean functions is a generalization of the most important cryptographic criterion, called the (first order) nonlinearity. It is defined as the sequence of the minimum Hamming distances nl_r(f) between a given Boolean function f and all Boolean functions in the same number of variables and of degrees at most r, for r ≥ 1. This parameter, which has a close relationship with the Gowers norm, quantifies the resistance to cryptanalyses by low degree approximations of stream ciphers using the Boolean function f as combiner or as filter. The nonlinearity profile can also be defined for vectorial functions: it is the sequence of the minimum Hamming distances between the component functions of the vectorial function and all Boolean functions of degrees at most r, for r ≥ 1. The nonlinearity profile of the multiplicative inverse functions has been lower bounded in a previous paper by the same author. No other example of an infinite class of functions with unbounded nonlinearity profile has been exhibited since then. In this paper, we lower bound the whole nonlinearity profile of the (simplest) Dillon bent function (x,y) ↦ xy^2n/2-2, x, y ∈ 𝔽_2^n/2 and we exhibit another class of functions, for which bounding the whole profile of each of them comes down to bounding the first order nonlinearities of all functions.

In this paper we generalize two remarkable results on cryptographic properties of Boolean functions given by Tu and Deng [8] to the vectorial case. Firstly we construct vectorial bent Boolean functions with good algebraic immunity for all cases 1 ⩽ m ⩽ n, and with maximum algebraic immunity for some cases (n,m). Then by modifying F, we get vectorial balanced functions with optimum algebraic degree, good nonlinearity and good algebraic immunity for all cases , and with maximum algebraic immunity for some cases (n,m). Moreover, while Tu-Deng's results are valid under a combinatorial hypothesis, our results (Theorems 4 and 5) are true without this hypothesis.

Rabbit is a stream cipher proposed by M. Boesgaard et al., and has been selected into the final portfolio after three evaluation phases of the ECRYPT Stream Cipher Project (eSTREAM). So far only a few papers studied its security besides a series of white papers by the designers of Rabbit. Recently we presented a new idea to evaluate the security of a word-oriented stream cipher algorithm from a smaller data granularity instead of its original data granularity and applied it successfully to the stream cipher SOSEMANUK. In this work we apply the same idea to the Rabbit algorithm and analyze its security in resistance against the guess and determine attack from the view point of byte units. As a result, we present two new approaches of solving all x_j,t+1's and g_j,t's from the next-state function and the extraction scheme of Rabbit, whose complexities are 2¹⁶⁶ and 2^140.68 respectively, which are dramatically lower than those proposed by Lu et al. (2¹⁹² and 2¹⁷⁴ resp.) at ISC 2008. Finally based on the above new results we propose a byte-based guess and determine attack on Rabbit, which only needs a small segment of known keystream to recover the whole internal state of Rabbit with time complexity 2²⁴². Though the complexity of our attack is far higher than that of a brute force (2¹²⁸), we believe that some new techniques adopted in this paper are of interest for future work on Rabbit.

In this paper we study arithmetic correlations of sequences. Arithmetic correlations are the with-carry analogs of classical correlations. We analyze the arithmetic autocorrelations of non-binary ℓ-sequences, showing that they are nearly optimal. We analyze the expected auto- and cross-correlations of sequences with fixed shift, averaged over all sequences with a fixed period. We analyze the expected autocorrelations of a fixed sequence, averaged over all shifts.

Grain and Trivium are the hardware-oriented finalists of the eSTREAM. They are both based on nonlinear feedback shift registers. In this paper, we study their generalized classes of nonlinear feedback shift registers with time varying feedback functions, namely, Grain-like and Trivium-like structures. Some interesting results regarding their periods are obtained.

It is a difficult task to compute the r-th order nonlinearity of a given function with algebraic degree strictly greater than r > 1. Though lower bounds on the second order nonlinearity are known only for a few particular functions, the majority of which are cubic. We investigate lower bounds on the second order nonlinearity of cubic Boolean functions , where , d_l = 2^il + 2^jl + 1, m, i_l and j_l are positive integers, n > i_l > j_l. Furthermore, for a class of Boolean functions we deduce a tighter lower bound on the second order nonlinearity of the functions, where , d_l = 2^i_lγ + 2^j_lγ + 1, i_l > j_l and γ ≠ 1 is a positive integer such that gcd(n,γ) = 1.

Lower bounds on the second order nonlinearity of cubic monomial Boolean functions, represented by f_μ(x) = Tr(μx^2i+2j+1), , i and j are positive integers such that i > j, were obtained by Gode and Gangopadhvay in 2009. In this paper, we first extend the results of Gode and Gangopadhvay from monomial Boolean functions to Boolean functions with more trace terms. We further generalize and improve the results to a wider range of n. Our bounds are better than those of Gode and Gangopadhvay for monomial functions f_μ(x). Especially, our lower bounds on the second order nonlinearity of some Boolean functions F(x) are better than the existing ones.

The purpose of this paper is to present extended definitions and characterizations of the classical notions of APN and maximum nonlinear Boolean functions to deal with the case of mappings from a finite group K to another one N with the possibility that one or both groups are non-Abelian.

A conference key distribution is a protocol that allows designated subset of users to calculate a shared private key. We consider unconditionally secure conference key distribution systems where the adversary has unlimited computational power, and focuses on a stronger and more realistic adversary model, proposed by Safavi-Naini and Jiang, in which the adversary in addition to corrupting subsets of users and obtaining their private keys, can access the conference keys of a number of uncorrupted conferences. We consider alternative definitions of security with this adversary model and show the relationship between them. An important efficiency parameter for conference key distribution systems is the size of the users' private keys. We derive lower bounds on the size of this key and discuss the results in comparison with the known bounds. We also consider one-round Interactive Conference Key Distribution Systems (ICKDS) in the new adversarial model where the adversary in addition to learning the private keys of the corrupted users and a number of conference keys, has access to the transcripts of some conferences. We show that under this new adversary model, the previously proposed one round protocol of Blundo et. al. is no longer secure and we construct an ICKDS with provable security in the new adversarial model.

The design of rational cryptographic protocols is a recently created research area at the intersection of cryptography and game theory. In this paper, we propose a new m-out-of-n rational secret sharing scheme requiring neither the involvement of the dealer (except during the initial share distribution) nor a trusted mediator. Our protocol leads to a Nash equilibrium surviving the iterated deletion of weakly dominated strategies for m ≥ 4. Our construction is information theoretically secure and it is immune against backward induction attacks. Contrary to Kol and Naor who used a specific cryptographic primitive in their TCC'08 paper (namely, meaningful/meaningless encryption), the immunity of our scheme is based on the use of bivariate polynomials and one-time pads. To the best of our knowledge, it is the first time that such polynomials have been used for rational secret sharing. Our scheme is efficient and does not require any physical assumptions such as envelopes or ballot boxes. As most of existing rational protocols, our construction requires simultaneous broadcast channels. However, our proposed scheme does not require any computational assumption and it provides information theoretical security.

In this paper, we establish a general connection between authentication codes and difference balanced functions. Consequently, we present three new classes of authentication codes without secrecy from difference balanced functions. This is the first time that the difference balanced functions, which were used in literature mainly to construct sequences with good correlations, have been used to construct authentication codes.

In this paper, we study the nonexistence of bent functions in the class of Boolean functions without monomials of degree less than d in their algebraic normal forms (ANF). We prove that n-variable Boolean functions in such class are not bent when there are not more than n + d - 3 monomials in their ANFs. We also show that an n-variable Boolean function is not bent if it has no monomial of degree less than ⌈3n/8 + 3/4⌉ in its ANF.

In this paper, we present techniques and algorithms for processing an offline sequence of update and query operations and for related problems. The update can be either all insertions or all deletions. The types of query include min-gap, max-gap, predecessor, and successor. Most problems we consider are solved optimally in linear time by our algorithms, which are based on new geometric modeling and interesting techniques. We also discuss some applications to which our algorithms and techniques can be applied to yield efficient solutions. These applications include an offline horizontal ray shooting problem and a shortest arc covering problem on a circle.

We use the concept of trie (prefix tree) representation of a prefix-closed finite language L to design a simple nondeterministic automaton. Each computation of this trie automaton corresponds to a subword occurrence of a word from L in the input word. The matrix representation of the trie automaton leads to a fairly general extension of the original concept of the Parikh matrix from [7].

Heterogeneity complicates the use of multicomputer platforms. Can it also enhance their performance? How can one measure the power of a heterogeneous assemblage of computers ("cluster"), in absolute terms (how powerful is this cluster) and relative terms (which cluster is more powerful)? Is a cluster that has one super-fast computer and the rest of "average" speed more/less powerful than one all of whose computers are "moderately" fast? If you can replace just one computer in a cluster with a faster one, should you replace the fastest? the slowest? A result concerning "worksharing" in heterogeneous clusters provides a highly idealized, yet algorithmically meaningful, framework for studying such questions in a way that admits rigorous analysis and formal proof. We encounter some surprises as we answer the preceding questions (perforce, within the idealized framework). Highlights: (1) If one can replace only one computer in a cluster by a faster one, it is (almost) always most advantageous to replace the fastest one. (2) If the computers in two clusters have the same mean speed, then the cluster with the larger variance in speed is (almost) always more productive (verified analytically for small clusters and empirically for large ones.) (3) Heterogeneity can actually enhance a cluster's computing power.