In this paper, we propose a privacy-preserving framework for outsourced media search applications. Considering three parties, a data owner, clients and a server, the data owner outsources the description of his data to an external server, which provides a search service to clients on the behalf of the data owner. The proposed framework is based on a sparsifying transform with ambiguization, which consists of a trained linear map, an element-wise nonlinearity and a privacy amplification. The proposed privacy amplification technique makes it infeasible for the server to learn the structure of the database items and queries. We demonstrate that the privacy of the database outsourced to the server as well as the privacy of the client are ensured at a low computational cost, storage and communication burden.