Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage
Abstract
In recent years, there has been a major effort to design cryptographic schemes that remain secure even when arbitrary information about the secret key is leaked (e.g., via side-channel attacks). We explore the possibility of achieving security under \emph{continual} leakage from the \emph{entire} secret key by designing schemes in which the secret key is updated over time. In this model, we construct public-key encryption schemes, digital signatures, and identity-based encryption schemes that remain secure even if an attacker can leak a constant fraction of the secret memory (including the secret key) in each time period between key updates. We also consider attackers who may probe the secret memory during the updates themselves. We stress that we allow unrestricted leakage, without the assumption that ``only computation leaks information''. Prior to this work, constructions of public-key encryption schemes secure under continual leakage were not known even under this assumption.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Shops and families often lack security awareness and protection skills, which makes web cameras and monitors vulnerable.
“shops and families often lack security awareness and protection skills, which makes web cameras and monitors (most of the time, the monitor is just a normal personal computer) vulnerable [33,34].”
From Secure Video Surveillance Framework in Smart City (2021) · cites this paper as [33]
Cites
Kocher, P. C., Jaffe, J. S., & Jun, B. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48405-1_25 · Cited by 7,569 · see citing works
Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems
Kocher, P. C. (1996) · Lecture notes in computer science · doi:10.1007/3-540-68697-5_9 · Cited by 4,446 · see citing works
Boneh, D., Boyen, X., & Shacham, H. (2004) · Annual International Cryptology Conference · doi:10.1007/978-3-540-28628-8_3 · Cited by 2,258 · see citing works
Private Circuits: Securing Hardware against Probing Attacks
Ishai, Y., Sahai, A., & Wagner, D. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45146-4_27 · Cited by 1,082 · see citing works
Lossy Trapdoor Functions and Their Applications
Peikert, C., & Waters, B. R. (2008) · SIAM Journal on Computing · doi:10.1137/080733954 · Cited by 640 · see citing works
Leakage-Resilient Cryptography
Dziembowski, S., & Pietrzak, K. (2008) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.56 · Cited by 506 · see citing works
Simultaneous Hardcore Bits and Cryptography against Memory Attacks
Akavia, A., Goldwasser, S., & Vaikuntanathan, V. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-00457-5_28 · Cited by 492 · see citing works
Self-citationLest we remember: cold boot attacks on encryption keys
Halderman, J. A., Schoen, S. D., Heninger, N., et al. (2008) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 437 · see citing works
Micali, S. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795284959 · Cited by 424 · see citing works
Public-Key Cryptosystems Resilient to Key Leakage
Naor, M., & Segev, G. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03356-8_2 · Cited by 403 · see citing works
All-or-nothing encryption and the package transform
Rivest, R. L. (1997) · Lecture notes in computer science · doi:10.1007/bfb0052348 · Cited by 399 · see citing works
Physically Observable Cryptography
Micali, S., & Reyzin, L. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24638-1_16 · Cited by 378 · see citing works
A Forward-Secure Public-Key Encryption Scheme
Canetti, R., Halevi, S., & Katz, J. I. (2007) · Journal of Cryptology · doi:10.1007/s00145-006-0442-5 · Cited by 284 · see citing works
Self-citationA Leakage-Resilient Mode of Operation
Pietrzak, K. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-01001-9_27 · Cited by 261 · see citing works
Signature Schemes with Bounded Leakage Resilience
Katz, J. I., & Vaikuntanathan, V. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10366-7_41 · Cited by 257 · see citing works
Self-citationUniversal Arguments and their Applications
Barak, B., & Goldreich, O. (2003) · Proceedings - IEEE Conference on Computational Complexity/Proceedings · doi:10.1109/ccc.2002.1004355 · Cited by 244 · see citing works
Cryptography against Continuous Memory Attacks
Dodis, Y., Haralambiev, K., López-Alt, A., et al. (2010) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.56 · Cited by 239 · see citing works
Boldyreva, A., Fehr, S., & O’Neill, A. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85174-5_19 · Cited by 229 · see citing works
On cryptography with auxiliary input
Dodis, Y., Kalai, Y. T., & Lovett, S. (2009) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1536414.1536498 · Cited by 228 · see citing works
Self-citationPublic-Key Encryption in the Bounded-Retrieval Model
Alwen, J., Dodis, Y., Naor, M., et al. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13190-5_6 · Cited by 206 · see citing works
Public-Key Encryption Schemes with Auxiliary Inputs
Dodis, Y., Goldwasser, S., Kalai, Y. T., et al. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-11799-2_22 · Cited by 198 · see citing works
Self-citationExposure-Resilient Functions and All-or-Nothing Transforms
Canetti, R., Dodis, Y., Halevi, S., Eyal Kushilevitz, Z., & Sahai, A. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45539-6_33 · Cited by 192 · see citing works
Private Circuits II: Keeping Secrets in Tamperable Circuits
Ishai, Y., Prabhakaran, M., Sahai, A., et al. (2006) · Lecture notes in computer science · doi:10.1007/11761679_19 · Cited by 176 · see citing works
Correcting errors without leaking partial information
Dodis, Y., & Smith, A. (2005) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1060590.1060688 · Cited by 172 · see citing works
Faust, S., Kiltz, E., Pietrzak, K., et al. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-11799-2_21 · Cited by 145 · see citing works
Protecting Circuits from Leakage: the Computationally-Bounded and Noisy Cases
Faust, S., Rabin, T., Reyzin, L., Tromer, E., & Vaikuntanathan, V. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13190-5_7 · Cited by 125 · see citing works
Self-citationOn the (Im)possibility of Cryptography with Imperfect Randomness
Dodis, Y., Ong, S. J., Prabhakaran, M., & Sahai, A. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.44 · Cited by 106 · see citing works
A block cipher based pseudo random number generator secure against side-channel key recovery
Petit, C., Standaert, F., Pereira, O., et al. (2008) · ACM Symposium on Information, Computer and Communications Security · doi:10.1145/1368310.1368322 · Cited by 70 · see citing works
Brakerski, Z., & Kalai, Y. T. (2010) · IACR Cryptology ePrint Archive · Cited by 60 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Secure Video Surveillance Framework in Smart City
Li, H., Xiezhang, T., Yang, C., Deng, L., & Yi, P. (2021) · Sensors · doi:10.3390/s21134419 · Cited by 31 · see citing works
- Authors
- Brakerski, Z., Kalai, Y. T., Katz, J., & Vaikuntanathan, V.
- Affiliations
- Weizmann Institute of Science (IL)
- Microsoft (United States) (US)
- University of Maryland, College Park (US)
- Microsoft Research (United Kingdom) (GB)
- Venue
- 2010 IEEE 51st Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE
- Published
- 2010-10
- Volume
- 2010
- Pages
- 501-510
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W1987129710
- Cited by
- 242
- References
- 30
- Citations by year
- 2026: 1 · 2025: 19 · 2024: 5 · 2023: 3 · 2022: 13 · 2021: 6 · 2020: 13 · 2019: 10 · 2018: 16 · 2017: 13 · 2016: 17 · 2015: 25 · 2014: 23 · 2013: 30 · 2012: 25
- FWCI
- 20.17
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- Annual Symposium on Foundations of Computer Science (publishedVersion)
- IACR Cryptology ePrint Archive (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptographic Implementations and Security
- Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
- Keywords
- public-key encryption, digital signatures, identity-based encryption, leakage-resilient cryptography, side-channel attacks, key update, secret key leakage
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
