Almost \(k\)-wise independent sample spaces and their cryptologic applications (Q5950639)

The focus is on the close interdependence of various notions which arose in statistics, computer science, coding theory and discrete mathematics. They all have in common that they describe certain uniformity properties. One basic such structure is a \(k\)-wise independent sample space. This is equivalent to the design-theoretic concept of an orthogonal array and, in the linear case, it is the dual of a linear error-correcting code. It is a fruitful idea to relax the condition of statistical \(k\)-wise independence and to demand instead that the corresponding distribution should be close to the uniform distribution in a statistical sense. These are almost \(k\)-wise independent sample spaces. Another basic concept is an \(\varepsilon\)-biased array. As only the binary case is considered in the paper, it should have been mentioned that binary weakly biased arrays are equivalent to binary linear error-correcting codes containing the repetition code. The paper starts from an important construction of binary \(\varepsilon\)-biased arrays and almost \(k\)-wise independent sample spaces due to \textit{N. Alon, O. Goldreich, J. Håstad} and \textit{R. Peralta} [Random Struct. Algorithms 3, 289-304 (1992; Zbl 0755.60002)] and explores its impact on a variety of applications, most notably in cryptography. In particular it is shown that almost \(k\)-wise independent sample spaces are essentially equivalent to certain families of universal hash functions, which in turn yield authentication codes. This leads to new families of multiple authentication codes with record-breaking parameters. In this context a new bound on almost strongly universal hash families and on almost \(k\)-independent sample spaces is derived. The bound is design theoretic in nature and uses elementary means. It is the first bound known on almost \(k\)-independent sample spaces. Another useful notion introduced in the paper is that of an almost resilient function. This is a relaxation of the concept of a resilient function (of some strength). A basic observation describes almost resilient functions as large sets of almost independent sample spaces (meaning a partition of the ambient space into such sample spaces). This allows effective constructions of almost resilient functions to be carried out. Another basic ingredient needed to carry out this construction is the famous Weil-Carlitz-Uchiyama bound. Another cryptographic application concerns pseudorandom functions. Almost \(k\)-wise independent sample spaces can be used to construct pseudorandom functions, which are almost indistinguishable from truly random functions by a distinguisher limited to \(k\) oracle queries. Such pseudorandom functions can potentially be used in the construction of block ciphers, which offer resistance to correlation attacks.