Accurate indoor localization is a significant task for many ubiquitous and pervasive computing applications, with numerous solutions based on IEEE802.11, Bluetooth, ultrasound and infrared technologies being proposed. The inherent sparsity present in the problem of location estimation motivates in a natural fashion the use of the recently introduced theory of compressive sensing (CS), which states that a signal having a sparse representation in an appropriate basis can be reconstructed with high accuracy from a small number of random linear projections. In the present work, we exploit the framework of CS to perform accurate indoor localization based on signal-strength measurements, while reducing significantly the amount of information transmitted from a wireless device with limited power, storage, and processing capabilities to a central server. Equally importantly, the inherent property of CS acting as a weak encryption process is demonstrated by showing that the proposed approach presents an increased robustness to potential intrusions of an unauthorized entity. The experimental evaluation reveals that the proposed CS-based localization technique is superior in terms of an increased localization accuracy in conjunction with a low computational complexity when compared with previous statistical fingerprint-based methods.