Algorithms for Reconstructing Databases and Cryptographic Secret Keys in Entropic Settings

Abstract

A small amount of information leakage can undermine the security of a design that is otherwise considered secure. Many studies demonstrate how common leakages such as power consumption, electromagnetic emission, and the time required to perform certain operations can reveal information, such as the secret key of a cryptosystem. As a first contribution, in this work, we explore the possibility of cache attacks, a type of timing side-channel attack, in a new setting, namely, data processing. Later we show an improved attack on Learning Parity with Noise problems with a sparse secret. We propose two algorithms that are asymptotically faster than state-of-the-art. Finally, we show that the structure presented in RLWE constructions, in contrast to LWE constructions, opens up new attacks. Constructions based on LWE can be proven secure as long as the secret retains enough entropy. We show, however, that constructions based on RLWE can be completely broken even if the secret key retains 3/4 of its entropy.