Update Recovery Attacks on Encrypted Database within Two Updates using Range Queries Leakage
Jianting Ning, Geong Sen Poh, Xinyi Huang, Robert Huijie Deng, Shuwei Cao, Ee‐Chien Chang · IEEE Transactions on Dependable and Secure Computing · 2020
Recently, reconstruction attacks on static encrypted database supporting range queries have been proposed. However, attacks on encrypted database within two updates in the similar setting have not been studied extensively. As far as we know, the only work is theupdate recovery attackpresented by Grubbset al.(CCS 2018). Following their seminal work, we present new update recovery attacks fordensedataset (i.e., at least one record corresponding to each value in the range), which enable a deeper understanding of the impact caused by leakages due to updates on dynamic encrypted database. Our first attack aims at recovering the value of a newly added record in the case of one database update. We further demonstrate that the attack can fully reconstruct thedatabase countsif the updated value is either the minimum or maximum in the range. We then consider a setting where two distinct records are added separately, which leads to our second attack. We next extend our attacks to the setting where the update operation is deletion. To the best of our knowledge, update recovery attack on database supporting deletion has not been considered before. We demonstrate practicality of our attack via extensive simulations using real dataset.