A combinatorial problem in database security Original Research Article

Let A be a K-dimensional matrix of size d1 × … × dk. By a contiguous submatrix B of A we understand the matrix B = {ainil…ik}, il … ik ϵ Il × … × lk, where Is is an interval, Is ⊂ l, …, ds, s = l, …, 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 connection 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 all B in B does not enable one to calculate any of the elements of A? In this paper we show that, for all k, the largest set B is uniquely determined and equals the set of all contiguous submatrices with an even number of elements of A.