Access Pattern Hiding Aggregation over Encrypted Databases

Outsourcing storage and computation to cloud service providers is becoming increasingly more popular for enterprises. Multiple secure aggregation schemes, such as CryptDB, Seabed, and SAGMA, have been proposed to protect enterprise data while allowing function evaluation over the data. However, multiple leakage-abuse attacks on the access pattern have been published that can also be used to attack these existing schemes. On top of that, without pre-computation these schemes allow only for additive aggregation functions. We propose and implement a secure aggregation scheme based on leveled-fully homomorphic encryption that is not vulnerable to leakage-abuse attacks that exist for the current secure aggregation schemes, and can evaluate both additive and multiplicative aggregation functions. We compare our scheme against SAGMA, and with a security level of 112 bits, multiplicative depth of 13 and plaintext space of 58 bits, we achieve between 2x and 8x better query evaluation wall-time.