Deterministic History-Independent Strategies for Storing Information on Write-Once Memories

by Tal Moran, Moni Naor, and Gil Segev

Theory of Computing, Volume 5(2), pp. 43-67, 2009

Bibliography with links to cited articles

[1]   Noga Alon and Michael R. Capalbo: Explicit unique-neighbor expanders. In Proc. 43rd FOCS, pp. 73–79. IEEE Comp. Soc. Press, 2002. [doi:10.1109/SFCS.2002.1181884].

[2]   Noga Alon and Rani Hod: Optimal monotone encodings. In Proc. the 35th Internat. Colloquium on Automata, Languages and Programming (ICALP’08), pp. 258–270. Springer, 2008. [doi:10.1007/978-3-540-70575-8_22].

[3]   Readers ‘declassify’ US document. BBC News, May 2005.

[4]   John Bethencourt, Dan Boneh, and Brent Waters: Cryptographic methods for storing ballots on a voting machine. In Proc. 14th Network and Distributed System Security Symp. (NDSS’07), pp. 209–222, 2007.

[5]   Guy E. Blelloch and Daniel Golovin: Strongly history-independent hashing with applications. In Proc. 48th FOCS, pp. 272–282. IEEE Comp. Soc. Press, 2007. [doi:10.1109/FOCS.2007.36].

[6]   Niv Buchbinder and Erez Petrank: Lower and upper bounds on obtaining history-independence. Inform. and Comput., 204(2):291–337, 2006. [doi:10.1016/j.ic.2005.11.001].

[7]   Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, and Srinivasan Venkatesh: Are bitvectors optimal? SIAM J. Comput., 31(6):1723–1744, 2002. [doi:10.1137/S0097539702405292].

[8]   J. Capetanakis: Generalized TDMA: The multi-accessing tree protocol. IEEE Trans. Commun., 27(10):1479–1484, 1979.

[9]   J. Capetanakis: Tree algorithms for packet broadcast channels. IEEE Trans. Inform. Theory, 25(5):505–515, 1979.

[10]   AT&T leaks sensitive info in NSA suit. CNET News, May 2006.

[11]   Paul Erd~o  s, Péter Frankl, and Zoltán Füredi: Families of finite sets in which no set is covered by the union of r others. Israel J. Math., 51:79–89, 1985. [doi:10.1007/BF02772959].

[12]   Zoltán Füredi: On r-cover-free families. J. Combin. Theory Ser. A, 73(1):172–173, 1996. [doi:10.1006/jcta.1996.0012].

[13]   Albert G. Greenberg and Shmuel Winograd: A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels. J. ACM, 32(3):589–596, 1985. [doi:10.1145/3828.214125].

[14]   Venkatesan Guruswami, Christopher Umans, and Salil Vadhan: Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. In Proc. 22nd Annual IEEE Conference on Computational Complexity (CCC’07), pp. 96–108. IEEE Comp. Soc. Press, 2007. [doi:10.1109/CCC.2007.38].

[15]   Jason D. Hartline, Edwin S. Hong, Alexander E. Mohr, William R.Pentney, and Emily Rocke: Characterizing history independent data structures. Algorithmica, 42(1):57–74, 2005. [doi:10.1007/s00453-004-1140-z].

[16]   Sandy Irani, Moni Naor, and Ronitt Rubinfeld: On the time and space complexity of computation using write-once memory — or — is pen really much worse than pencil? Mathematical Systems Theory, 25(2):141–159, 1992. [doi:10.1007/BF02835833].

[17]   W. H. Kautz and R. C. Singleton: Nonrandom binary superimposed codes. IEEE Trans. Inform. Theory, 10(4):363–377, 1964.

[18]   János Komlós and Albert G. Greenberg: An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels. IEEE Trans. Inform. Theory, 31(2):302–306, 1985.

[19]   Daniele Micciancio: Oblivious data structures: Applications to cryptography. In Proc. 29th STOC, pp. 456–464. ACM Press, 1997. [doi:10.1145/258533.258638].

[20]   David Molnar, Tadayoshi Kohno, Naveen Sastry, and David Wagner: Tamper-evident, history-independent, subliminal-free data structures on PROM storage — or — how to store ballots on a voting machine. In Proc. IEEE Symp. on Security and Privacy (SP’06), pp. 365–370. IEEE Comp. Soc. Press, 2006. [doi:10.1109/SP.2006.39].

[21]   Moni Naor, Gil Segev, and Udi Wieder: History-independent cuckoo hashing. In Proc. 35th Internat. Colloquium on Automata, Languages and Programming (ICALP’08), pp. 631–642. Springer, 2008.

[22]   Moni Naor and Vanessa Teague: Anti-persistence: History independent data structures. In Proc. 33rd STOC, pp. 492–501. ACM Press, 2001. [doi:10.1145/380752.380844].

[23]   Noam Nisan and Amnon Ta-Shma: Extracting randomness: A survey and new constructions. J. Comput. System Sci., 58(1):148–173, 1999. [doi:10.1006/jcss.1997.1546].

[24]   Ronald L. Rivest and Adi Shamir: How to reuse a “write-once” memory. Information and Control, 55(1-3):1–19, 1982.

[25]   Miklós Ruszinkó: On the upper bound of the size of the r-cover-free families. J. Combin. Theory Ser. A, 66(2):302–310, 1994. [doi:10.1016/0097-3165(94)90067-1].

[26]   Michael Sipser: Expanders, randomness, or time versus space. J. Comput. System Sci., 36(3):379–383, 1988. [doi:10.1016/0022-0000(88)90035-9].

[27]   Amnon Ta-Shma: Storing information with extractors. Information Processing Letters, 83(5):267–274, 2002. [doi:10.1016/S0020-0190(02)00206-5].

[28]   Amnon Ta-Shma, Christopher Umans, and David Zuckerman: Lossless condensers, unbalanced expanders, and extractors. Combinatorica, 27(2):213–240, 2007. [doi:10.1007/s00493-007-0053-2].