In online social networks (OSNs), interest groups are becoming increasingly popular due to thegrowth of social networking sites and their users. These groups can serve various purposes includingpolitical, professional, and religious interests. These interest group formation procedures involve thedisclosure of user identities and interests, which can be considered as a violation of privacy. To date,no significant and effective research has addressed this issue so that the OSN users can form groupssecurely. This study proposes a cryptography-based privacy-preserving solution that will allow usersto form groups by disclosing neither their identities nor their interests. Even users within the groupwill enjoy the privacy-preserving communication if they want. This study also show that this fullyhomomorphic encryption-based proposed solution is secure against some possible attacks.