Inference Attacks on Encrypted Databases Based on Order Preserving Assignment Problem

In ACM CCS 2015, Naveed et al. proposed attacks using plaintext auxiliary data for databases encrypted by ordered preserving encryption or more general property preserving encryptions. Their attacks are based on the Hungarian algorithm for solving the linear sum assignment problem (LSAP). In this work, we define a new assignment optimization problem with an additional condition of order structure and propose a search algorithm for finding its exact solution. We apply the new algorithm to attack an encrypted database in the same situation as Naveed et al. and found that our proposed method improves the success probability of the attacks compared with the attacks of Naveed et al.