The Negative DataBase (NDB) is inspired by artificial immune system. Different from the traditional DataBase (DB), the NDB stores the compressed representation of the complementary set of the DB to enhance the privacy. Although the existent q-hidden algorithm could generate hard-to-reverse single NDBs, the hardness level could be improved. In this paper, the p-hidden algorithm is proposed for generating single NDBs which could be more hard-to-reverse. This algorithm misguides the solvers with the local search strategy to the reverse direction, and such misguidance is controlled by two adjustable parameters rather than only one parameter in the q-hidden algorithm.