Randomized Data Partitioning with Efficient Search, Retrieval and Privacy-Preservation

We introduce a new data representation that serves mainly for privacy preserving data storage with efficient search and retrieval capabilities over the distributed systems. The cornerstone of the proposed scheme is based on a novel algorithm that splits an input bit sequence \(\mathtt {B[1..n]}\) into two as left and right partitions with well–control over the partition sizes, and the reconstruction of \(\texttt{B}\) in absence of either partition is hard to achieve. The algorithm processes the input bit stream in blocks of \(\texttt{d}\) –bits, where initially each block is replaced with another \(\texttt{d}\) –bit according to a randomly chosen permutation of the set \(\mathtt {\{0,1,..2^d{-}1\}}\) . Following the replacement, the leftmost bits of each block up until and including the \(\texttt{q}\) th set bit are appended to the left and the remaining bits to the right partition. We prove that the expected length of the left partition is \(\mathtt {\ell \approx {2qn}/{d}}\) bits and the right partition becomes of length \(\mathtt {|R| = n - \ell }\) bits. Therefore, there is no overhead on the new representation with respect to original input. We also show that due to the randomization step, the input data \(\texttt{B}\) is not required to follow any special probability distribution to have the mentioned partitioning ratio \(\mathtt {\rho = 2q{/}d}\) and it is possible to tune the parameters \(\texttt{d}\) and \(\texttt{q}\) to support any desired ratio \(\mathtt {\rho }\) on the input. We consider recursive application of that splitting algorithm on each partitions, which can be viewed as generating a full binary tree with \(\texttt{k}\) –leaves such that at each internal node the data is subject to the proposed splitting operation. Such a construction represents an input bit sequence \(\mathtt {B[1..n]}\) with \(\texttt{k}\) partitions as \(\mathtt {P_1, P_2, \ldots ,P_k}\) , where it is hard to reconstruct the original data in absence of any \(\mathtt {P_i}\) .