A fine-grained algorithm for generating hard-toreverse negative databases

The negative database (NDB) is a new technique for privacy preserving and information hiding. It hides information by storing the complementary set instead of the original data. In order to protect the hidden information, NDBs should be hard-to-reverse. In this paper, we propose the K-hidden algorithm for generating hard-to-reverse NDBs (called K-hidden-NDBs). The K-hidden algorithm could be controlled in a more fine-grained manner than existing NDB generation algorithms. Moreover, in terms of the SAT solvers based on the local search strategy, we formally prove that the K-hidden-NDBs could be more hard-to-reverse than the NDBs generated by the typical p-hidden algorithm. Furthermore, we show that the K-hidden-NDB could be more hard-to-reverse (against the local search strategy) than the q-hidden-NDB (NDBs generated by the q-hidden algorithm) when the sizes of NDBs are the same. Finally, as for the Unit Clause heuristic solvers, we prove that the K-hidden-NDB could be the same hard-to-reverse as the q-hidden-NDB.