Privacy via the Johnson-Lindenstrauss Transform

Understand

Suppose that party A collects private information about its users, where each user's data is represented as a bit vector.

• Suppose that party B has a proprietary data mining algorithm that requires estimating the distance between users, such as clustering or nearest neighbors.
• We ask if it is possible for party A to publish some information about each user so that B can estimate the distance between users without being able to infer any private bit of a user.
• Our method involves projecting each user's representation into a random, lower-dimensional space via a sparse Johnson-Lindenstrauss transform and then adding Gaussian noise to each entry of the lower-dimensional representation.