Symmetric Disclosure: a Fresh Look at k-Anonymity
This addresses network efficiency for users of online communication systems, but it appears incremental as it builds on existing k-anonymity concepts.
The paper tackles the problem of high network overhead in k-anonymity systems due to sparse social relations by proposing symmetric disclosure, where both parties specify origin and target sets, reducing overhead by offsetting sparsity effects.
We analyze how the sparsity of a typical aggregate social relation impacts the network overhead of online communication systems designed to provide k-anonymity. Once users are grouped in anonymity sets there will likely be few related pairs of users between any two particular sets, and so the sets need to be large in order to provide cover traffic between them. We can reduce the associated overhead by having both parties in a communication specify both the origin and the target sets of the communication. We propose to call this communication primitive "symmetric disclosure." If in order to retrieve messages a user specifies a group from which he expects to receive them, the negative impact of the sparsity is offset.