The ith coordinate of an [n, k] code is said to have locality r and availability t if there exist t disjoint groups, each containing at most r other coordinates that can together recover the value of the ith coordinate. This property is particularly useful for codes for distributed storage systems because it permits local repair of failed nodes and parallel access of hot data. In this paper, for any positive integers r and t, we construct a binary linear code of length equation which has locality r and availability t for all coordinates. Although it only achieves the trivial minimum distance (i.e. t + 1), its information rate attains equation, which is higher than that of the direct product code, the only known construction that can achieve arbitrary locality and availability.

The multiplicative property is important for a linear secret sharing scheme (LSSS) to be used in constructing a multiparty computation (MPC) protocol. In general, an LSSS has to expand its share size to obtain the multiplicative property. In this paper, with respect to an MPC problem based on connectivity of graphs we devise an ideal multiplicative LSSS, that is, the LSSS is of the multiplicative property without expanding its share size. Moreover, it provides a new class of access structures that have ideal multiplicative LSSSs.

We give a series of constructions of correlation-immune function over finite fields. We prove that F/sub 2/ and F/sub 3/ are the only finite fields F/sub q/ with the property that every (n-1)th correlation-immune function in n>2 variables over F/sub q/ is linear. We also show that by choosing larger finite fields one can alleviate the tradeoff between the length of the linear equivalent and the order of correlation immunity. This is useful for the design of various cryptosystems.

The structure of linear recurring m-arrays is studied. It is proved that any linear recurring m-array can be obtained by "folding" an m-sequence. The properties of translation-addition, sampling and correlation of linear recurring m-arrays are also discussed.>