In many aspects of everyday life, from education to health care and from economics to homeland security, information exchange involving both companies and agencies has become a common everyday application. Locating same real world entities within this information however is not trivial at all due to insufficient identifying information, misspellings etc. The problem becomes even more complicated when privacy considerations arise. This description consists an informal approach to the privacy preserving record linkage problem. In this paper we provide a solution to this problem by examining the alternatives offered by Phonetic Codes, a range of algorithms which despite their age, are still used for record linkage purposes. The main contribution of our work, as our extensive experimental evaluation indicates, is that our methodology manages to offer privacy guarantees for performing Privacy Preserving Record Linkage without the need of computationally expensive cryptographic methods.