A combinatorial problem in database security

Abstract

<p>Let A be a K-dimensional matrix of size <i>d₁ × … × d_k</i>. By a contiguous submatrix <i>B</i> of <i>A</i> we understand the matrix <i>B = {a_i₁…i_k}, i_l … i_k ϵ I_l × … × l_k</i>, where <i>I_s</i> is an interval, <i>I_s ⊂ {l, …, d_s, s = l, …, k</i>. For a contiguous submatrix <i>B</i> we denote by SUM(<i>B</i>) the sum of all elements of <i>B</i>. The following question has been raised in connection with the security of statistical databases. What is the largest family <i><b>B</b></i> of contiguous submatrices of <i>A</i> so that knowing the value of SUM(<i>B</i>) for all <i>B</i> in <i><b>B</b></i> does not enable one to calculate any of the elements of <i>A</i>? In this paper we show that, for all <i>k</i>, the largest set <i><b>B</b></i> is uniquely determined and equals the set of all contiguous submatrices with an even number of elements of <i>A</i>.</p>