Vinod Vaikuntanathan

Cryptography against Memory Attacks

Adi Akavia, Shafi Goldwasser, Vino Vaikuntanathan (Proc. of TCC 2009)

The absolute privacy of the secret keys associated with
cryptographic algorithms has been the corner-stone of
modern cryptography. Still, there is ample evidence in
practice that keys do get compromised at times, by
various means. In a particularly devastating side-channel
attack proposed recently, termed the ``memory attack'', a
significant fraction of the bits of the secret key can be
measured if the secret key is {\em ever stored} in a part
of memory which can be accessed. Such an attack has
been shown to completely compromise the security of
various crypto-systems in use, including RSA and AES.

We show two *public-key encryption schemes* secure
against memory attacks that leak upto (1-\epsilon) bits of
information about the secret-key (for any constant
epsilon>0). The first of these is the lattice-based encryption
scheme of Regev, and the second is a DDH-based
encryption scheme recently proposed by Boneh, Halevi,
Hamburg and Ostrovsky.  This is done without increasing
the size of the secret key, and without introducing any
complication of the natural encryption and decryption routines.