A combinatorial problem in database security

Let A be a k-dimensional matrix of size d(1) x ... x d(k). By a contiguous submatrix B of A we understand the matrix B = {a(i1...ik)}, i(1)...i(k) is an element of I-1 x ... x I-k, where I-s is an interval, I-s subset of {1,. ..,d(s)}, s = 1,...,k. For a contiguous submatrix B we denote by SUM(B) the sum of all elements of B. The following question has been raised in connec tion with the security of statistical databases. What is the largest family B of contiguous submatrices of A so that knowing the value of SUM(B) for a ll B in B does not enable one to calculate any of the elements of A? In thi s paper we show that, for all k, the largest set B is uniquely determined a nd equals the set of all contiguous submatrices with an even number of elem ents of A. (C) 1999 Elsevier Science B.V. All rights reserved.