In invitation-based systems, a new user can register upon having a certain number of invitations (i.e., t) issued by the existing members. The newcomer hands his invitations to the system administrator to be authenticated, who verifies that the invitations are issued by legitimate members. This causes the administrator being aware of who is invited by whom. However, the inviter-invitee relationship is privacy-sensitive information whose exposure can lead to an inference attack where the invitee's profile (e.g., political view or location) can be extracted through the profiles of his inviters. Addressing this problem, we propose Anonyma, an anonymous invitation-based system where a corrupted administrator who may even collude with a subset of existing members is not able to figure out who is invited by whom. We formally define and prove the inviter anonymity and unforgeability of invitations against a malicious adversary. Our design only incurs constant cost to authenticate a new registration. This is significantly better than the similar works where the generation of invitations and verification of new registration cause an overhead linear in the total number of existing members. Besides, Anonyma is efficiently scalable in the sense that once a user joins the system, the administrator can instantly, and without re-keying the existing members, issue credential for the newcomer to be able to act as an inviter. We additionally design AnonymaX, an anonymous cross-network invitation-based system where the invitations issued by the members of one system can be used for registering to another system.