Paper 2019/1215

Anonyma: Anonymous Invitation-Only Registration in Malicious Adversarial Model

Abstract

In invitation-based systems, a new user can register upon having a threshold number of invitations issued by the existing members. The newcomer hands his invitations to the system administrator who verifies whether the invitations are issued by legitimate members. This causes the administrator to be aware of who is invited by whom. However, the inviter-invitee relationship is privacy-sensitive information and can lead to inference attacks 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 as well as unforgeability of invitations against a malicious and adaptive adversary. Our design only incurs a constant cost to authenticate a new registration. This is significantly better than 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 credentials for the newcomer to be able to act as an inviter. We additionally design Anonymax, an anonymous cross-network invitation-based system empowering third-party authentication where the invitations issued by the members of one system can be used for registering to another system.