Abstract
The absolute privacy of the secret-keys associated with cryptographic algorithms has been the corner-stone of modern cryptography. Still, in practice, keys do get compromised at times for a variety or reasons. A particularly disturbing loss of secrecy is as a result of side channel attacks. These attacks exploit the fact that every cryptographic algorithm is ultimately implemented on a physical device and such implementations enable ‘observations’ which can be made and measured on secret data and secret keys. Indeed, side channel observations can lead to information leakage about secret keys, which in turn can and have lead to complete breaks of systems which have been proved mathematically secure, without violating any of the underlying mathematical principles or assumptions. Traditionally, such attacks have been followed by ad-hoc ‘fixes’ which make particular implementation invulnerable to particular attacks, only to potentially be broken anew by new examples of side-channel attacks.
In recent years, starting with the work on physically observable cryptography by [MR04] Micali and Reyzin, a new goal has been set to build a general theory of physical security against a large class of families of side channel attacks which one may call computational side-channel attacks. These include any side channel attack in which leakage of information on secrets occurs as a result of performing a computation on secrets. Some well-known examples of such attacks include Kocher’s timing attacks [Koc96] and power attacks [kJJ99]. A basic defining feature of a computational side-channel attack, as put forth by [MR04] is that computation and only computation leaks information. Namely, portions of memory which are not involved in computation do not leak information. A growing number of works [MR04, ISW03, PSP + 08, GKR08, DP08] have proposed cryptographic algorithms provably robust against computational side-channel attacks, by limiting in various ways the portions of the secret key which are involved in each step of the computation.
In the work on one time programs this is taken to an extreme [GKR08] . Goldwasser, Tauman-Kalai, and Rothblum show how by using a new proposed type of secure-memory which never touches any secrets or data which is not ultimately fully revealed, it is possible to perform any secure computations which is provably secure against all computational side channel attacks.
Memory-attacks proposed by Akavia, Goldwasser, and Vaikuntanathan [AGV09] are an entirely very different family of side-channel attacks that are not included in the computational side-channel attack family, as they violate the basic premise of [MR04] that only computation leaks information. This class of attacks was inspired by (although not restricted to) the memory-freezing attack introduced recently by Halderman et al. [HSH + 08] , where its is shown how to measure a significant fraction of the bits of secret keys if the keys were ever stored in a part of memory (e.g. DRAM), which could be accessed by an adversary even after the power of the machine has been turned off. Thus, information leaks about portions of the secret key which may have never been involved in any computation. A memory-attack leaks a bounded number of bits computed as a result of applying an arbitrary function of bounded length (smaller than than the size of the secret key) to the content of the secret key of a cryptographic algorithm. Naturally, this family of attacks is inherently parameterized and quantitative in nature, as if the attack would uncover the entire secret key at the outset, there would be no hope for any cryptography. The work of [AGV09] exhibits a public-key encryption algorithm which is especially robust against memory-attacks. Its security is based on the computationally intractability of the learning with errors (LWE) problem which is related to the intractability of approximating the length of the shortest vector in an integer lattice. Finally, a new interesting variant on the idea of memory attacks, had been proposed by Tauman-Kalai etal [DTKL09] in their work on security with auximlary-inputs. They propose to replace the restriction of revealing a length shrinking function of the secret, to revealing functions of the secret which are exponentially hard to invert.
In this talk we will survery this development, with special emphasis on the works of [GKR08, AGV09, DTKL09].
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-642-01001-9_35
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Akavia, A., Goldwasser, S., Vaikuntanathan, V.: Simulatneous hard-core bits and cryptography against memory attack. In: TCC (2009)
Dziembowski, S., Pietrzak, K.: Leakage-resilient stream ciphers. In: The IEEE Foundations of Computer Science (2008)
Dodis, Y., Tauman-Kalai, Y., Lovett, S.: Cryptography with auxilary input. In: STOC (2009)
Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: One-time programs. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 39–56. Springer, Heidelberg (2008)
Halderman, A., Schoen, S., Heninger, N., Clarkson, W., Paul, W., Calandrino, J., Feldman, A., Appelbaum, J., Felten, E.: Lest we remember: Cold boot attacks on encryption keys. In: Usenix Security Symposium (2008)
Ishai, Y., Sahai, A., Wagner, D.: Private circuits: Securing hardware against probing attacks. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 463–481. Springer, Heidelberg (2003)
Kocher, P.C., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)
Kocher, P.C.: Timing attacks on implementations of diffie-hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)
Micali, S., Reyzin, L.: Physically observable cryptography (extended abstract). In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 278–296. Springer, Heidelberg (2004)
Petit, C., Standaert, F.-X., Pereira, O., Malkin, T., Yung, M.: A block cipher based pseudo random number generator secure against side-channel key recovery. In: ASIACCS, pp. 56–65 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goldwasser, S. (2009). Cryptography without (Hardly Any) Secrets ?. In: Joux, A. (eds) Advances in Cryptology - EUROCRYPT 2009. EUROCRYPT 2009. Lecture Notes in Computer Science, vol 5479. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01001-9_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-01001-9_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01000-2
Online ISBN: 978-3-642-01001-9
eBook Packages: Computer ScienceComputer Science (R0)