Multiple Encrypted Random Forests using Compressed Sensing for Private Classification

A novel privacy preserving classification approach is proposed in this paper which employs multiple encrypted random forests with two compressed sensing encryption levels. At the first level, each feature vector is CS-encrypted using a different random matrix for each forest. At query time, the user selects one matrix randomly from a set of R different matrices, and gets R encrypted results of which only one will be used. At the second level, the class-label information at each tree leaf is encrypted using a different CS matrix for each tree. During recognition, the cloud adds all the encrypted leaf CS vectors for each of the R forests and sends to the user, where only one of them goes through sparse recovery to find the class label. Experiments on COREL1K and CIFAR10 image classification tasks show that the proposed approach achieves classification accuracy similar or better than nearest neighbour classifier with plaintext features. Also, correlation-based results show that the multiple-forest approach offers good level of security between the feature vectors while the class-label CS encryption approach achieves privacy to prevent the cloud from knowing the classification outcome.