Storage requirements for visual data have been increasing in recent years, following the emergence of many new highly interactive, multimedia services and applications for both personal and corporate use. This has been a key driving factor for the adoption of cloud-based data outsourcing solutions. However, outsourcing data storage to the Cloud also leads to new challenges that must be carefully addressed, especially regarding privacy. In this paper we propose a secure framework for outsourced privacy-preserving storage and retrieval in large image repositories. Our proposal is based on a novel cryptographic scheme, named IES-CBIR, specifically designed for media image data. Our solution enables both encrypted storage and querying using Content Based Image Retrieval (CBIR) while preserving privacy. We have built a prototype of the proposed framework, formally analyzed and proven its security properties, and experimentally evaluated its performance and precision. Our results show that IES-CBIR is provably secure, allows more efficient operations than existing proposals, both in terms of time and space complexity, and enables more realistic, interesting and practical application scenarios.