Title: A system-wide anonymity metric with message multiplicities

Authors: Rajiv Bagai; Bin Tang; Ahsan A. Khan; Abdus Samad

Addresses: Department of Electrical Engineering and Computer Science, Wichita State University, Wichita, KS 67260-0083, USA ' Computer Science Department, California State University, Dominguez Hills, Carson, CA 90747, USA ' Juniper Networks, Sunnyvale, CA 94089, USA ' Juniper Networks, Sunnyvale, CA 94089, USA

Abstract: An important goal of an anonymity system is to hide the level of communication between two users, i.e., the number of messages one user sent to another. We construct an anonymity metric that measures the extent to which the system-wide communication pattern of all users of an anonymity system is hidden, among other possible patterns, in the aftermath of an attack. Our model allows users to send or receive multiple messages via the anonymity system, and our metric handles attacks that are capable of determining infeasibility of some of the system's input-output message combinations. We also analyse two earlier attempts in the literature at arriving at such a metric, and show that one of those attempts is limited to only a small class of such attacks, while the other fails to take any attack into account. In comparison, our metric is comprehensive, as it is applicable to all attacks mentioned above.

Keywords: system-wide anonymity; multiple messages; privacy; anonymity measures; anonymity metrics; infeasibility attacks; graph theory; combinatorial matrix theory; Shannon entropy; security.

DOI: 10.1504/IJSN.2015.068391

International Journal of Security and Networks, 2015 Vol.10 No.1, pp.20 - 31

Received: 07 Feb 2013
Accepted: 07 Jan 2014
Published online: 01 Apr 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article