Smartphones are becoming really popular nowadays. Manufacturers are integrating many-many services into their products for the users bigger convenience. Oure everyday activities are becoming more and more reliant on these functions. Most mobile operating system vendors provide these functios free to use. However, the price we have to pay for using these services is not monetary, we can’t use them for free. Using a Google Android smartphone, we pay with our privacy. Google is collecting every available private data from our Android-based devices. This paper introduces a new system, which can be used for protecting one of our most important private data, our contacts. This system mainly protects our data from Google, and reaches its goal with encryption. Furthermore, the system does this undetectably. This paper also reviews some cryptographic and graph theory problems. It also demonstrates how the contacts module works in the Android operating system. The phonebook encryptor achieves undetectable encryption by mapping the ciphertext to names using a limited size dictionary. This paper also describes how this feature has been designed and implemented.