Abstract: Decades of research have resulted in privacy-preserving theories to carry out any computational tasks but there is still a wide gap between theory and practice. This study presents a method for privately retrieving data from an unsecure server. The method used is based on a Private Information Retrieval (PIR) scheme that utilizes Euler’s Phi Hiding Assumption. The method is optimized to offer fuzzy search abilities while retaining user’s queries privacy. A pre-processing phase is added at the server to reorganize data into buckets. A locality sensitive hashing function is used to create clusters based on string approximation. Similar data are organized and stored into buckets. The PIR query is no longer the target keyword as in typical PIR algorithms but rather the bucket containing the targeted keyword. The method is tested using a prototype written in PHP and C++ to measure performance and accuracy. The result is a system that successfully and privately retrieves a cluster of approximate data matches rather than exact matches. The algorithm is computationally more efficient than the original scheme in the sense that bucketization reduce the number of items to be retrieved which makes the process much faster.