In this paper, we present an efficient retrieval algorithm for encrypted speech based on an inverse fast Fourier transform and measurement matrix. Our approach improves query performance, as well as retrieval efficiency and accuracy, compared to existing content-based encrypted speech retrieval methods. Our proposed algorithm constructs a perceptual hash scheme using perceptual hash sequences from original speech files. By classifying the sequences and applying run-length compression, we decrease the cloud storage required for the hash index. We secure the speech database by encrypting it with Henon chaos scrambling, which offers excellent resistance to attacks. Experimental results show that the robustness, discrimination, and feature extraction efficiency of our proposed method are better than the existing alternatives, with good recall and precision ratios and with high retrieval efficiency and accuracy.