Security of erasable memories against adaptive adversaries

ABSTRACT

We study cryptographic modeling and encryption-based design techniques for guaranteeing privacy of data that is first stored in some type of computer memory and then deleted. We continue the investigation started in [3] by presenting an enhanced privacy notion that captures practical scenarios of adversaries repeatedly and adaptively attacking the memory to inspect its entire content before trying to obtain information about deleted data. We prove that the new notion is strictly stronger than the previous one considered in [3] (allowing the adversary a single intrusion), and show then that the efficient protocol in [3] still satisfies the new notion. One question implicitly raised by the previous work was whether it is indeed possible to define one meaningful and applicable notion of security even against adversaries that can repeatedly and adaptively obtain total control of the memory. Perhaps unexpectedly, our paper affirmatively answers this question.

REFERENCES

• 1: William Aiello , Mihir Bellare , Giovanni Di Crescenzo , Ramarathnam Venkatesan, Security Amplification by Composition: The Case of Doubly-Iterated, Ideal Ciphers, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.390-407, August 23-27, 1998
• 2: D. Boneh, and R. Lipton, A revocable backup system, Proc. of USENIX 97.
• 3: G. Di Crescenzo, N. Ferguson, R. Impagliazzo, and M. Jakobsson, How to forget a secret, in Proceedings of the 17th Symposium on Theoretical Aspects of Computer Science (STACS 2000), Lecture Notes in Computer Science, Springer Verlag.
• 4: Whitfield Diffie , Paul C. Van Oorschot , Michael J. Wiener, Authentication and authenticated key exchanges, Designs, Codes and Cryptography, v.2 n.2, p.107-125, June 1992 [doi>10.1007/BF00124891]
• 5: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 6: P. Gutmann, Secure Deletion of Data from Magnetic and Solid-State Memory, in Proceedings of 6th USENIX Security Symposium, 1996.
• 7: P. Gutmann, Data Remanence in Semiconductor Devices, in Proceedings of 10th USENIX Security Symposium, 2001.
• 8: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 9: D. Dagon, W. Lee, and R. Lipton, Protecting Secret Data from Insider Attacks, in Proc. of 9th International Conference on Financial Cryptography and Data Security, (FC 2005), Lecture Notes in Computer Science, Springer-Verlag.
• 10: Michael Luby , Charles Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM Journal on Computing, v.17 n.2, p.373-386, April 1988 [doi>10.1137/0217022]
• 11: B. Yee and D. Tygar, Secure coprocessors in electronic commerce applications, in Proceedings of USENIX 95.
• 12: S. Weingart, Physical Security for the μABYSS System, Proceedings of the IEEE Computer Society Conference on Security and Privacy, 1987.
• 13: S. White, S. Weingart, W. Arnold, and E. Palmer, Introduction to the Citadel Architecture: Security in Physically Exposed Environments, Version 1.3, Distributed security systems group, IBM Thomas J. Watson Research Center.
• 14: D. Tygar and B. Yee, Strongbox: A System for Self Securing Programs, CMU Computer Science: 25th Anniversary Commemorative, Addison-Wesley, 1991.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Security, Theory

Keywords:
erasable memory, secure data deletion, storage security