A Hybrid of the prefix algorithm and the q-hidden algorithm for generating single negative databases

The negative database (NDB) is a complement of the corresponding database. The NDB could protect the privacy of the data, but it should be complete and hard-to-reverse. However, existent techniques cannot generate the complete and hard-to-reverse negative database. In this paper, a hybrid method is proposed to generate single negative databases. The proposed hybrid method includes two phases. Firstly, a complete negative database with a small size is generated by the transformation of the prefix algorithm. Secondly, a hard-to-reverse negative database, which is generated with the q-hidden method, is added into the small complete negative database. Therefore, the hybrid negative database is both complete and hard-to-reverse. Experiment results show that the NDB generated by the hybrid method is better than the NDB generated by the typical q-hidden method. Especially, the NDB generated by the q-hidden method can be reversed on average when the string length is 300. However, the NDB generated by the hybrid method cannot be reversed on average when the string length is 150.