We demonstrate content-addressable holographic data storage with security using random phase encoding in the Fresnel domain. The phase-based data pages are encrypted using a random phase mask in the Fresnel domain, and recorded on a photorefractive LiNbO3:Fe crystal using angular multiplexing. While content searching through this database, the correct random phase mask and its position are critical for performing the search. Hence only an authentic user who has got the full key information can perform a search through the database. Apart from the security, the use of the random mask is most important in ensuring the fidelity of the search. The random mask ensures that the correlation peak intensity obtained is proportional to the inner product between the stored data page and the search argument. We have also studied the search capability by using partial search arguments of varying sizes. The lateral and the longitudinal shift sensitivities of the random phase mask while content searching have been studied. It has been found that an in-plane shift of 150 μm or an out-of-plane shift of 200 μm reduces the correlation peak intensity drastically so that no practical search is possible. We have carried out investigations on discrimination capabilities of the system, using the parameters discrimination ratio and SNR for various sizes of the search argument. © 2005 IOP Publishing Ltd.