In a Public Safety (PS) situation, agents may require critical and personally identifiable information. Therefore, not only does context and location-aware information need to be available, but also the privacy of such information should be preserved. Existing solutions do not address such a problem in a PS environment. This paper proposes a framework in which anonymized Personal Information (PI) is accessible to authorized public safety agents under a PS circumstance. In particular, we propose a secure data storage structure along with privacy-preserving mobile search framework, suitable for Public Safety Networks (PSNs). As a result, availability and privacy of PI are achieved simultaneously. However, the design of such a framework encounters substantial challenges, including scalability, reliability of the data, computation and communication and storage efficiency, etc. We leverage Secure Indexing (SI) methods and modify Bloom Filters (BFs) to create a secure data storage structure to store encrypted meta-data. As a result, our construction enables secure and privacy-preserving multi-keyword search capability. In addition, our system scales very well, maintains availability of data, imposes minimum delay, and has affordable storage overhead. We provide extensive security analysis, simulation studies, and performance comparison with the state-of-the-art solutions to demonstrate the efficiency and effectiveness of the proposed approach. To the best of our knowledge, this work is the first to address such issues in the context of PSNs.