Data structures for limited oblivious execution of programs while preserving locality of reference

ABSTRACT

We introduce a data structure for program execution under a limited oblivious execution model. For fully oblivious execution along the lines of Goldreich and Ostrovsky [2], one transforms a given program into a one that has totally random looking execution, based on some cryptographic assumptions and the existence of secure hardware. Totally random memory access patterns do not respect the locality of reference in programs to which the programs generally owe their efficiency. We propose a model that limits the obliviousness so as to enable efficient execution of the program; here the adversary marks a variable and tries to produce a list of candidate locations where it may be stored in after $T$-steps ofexecution. We propose a randomized algorithm based on splay trees,and prove a lower bound on such lists.

REFERENCES

• 1: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 2: Oded Goldreich , Rafail Ostrovsky, Software protection and simulation on oblivious RAMs, Journal of the ACM (JACM), v.43 n.3, p.431-473, May 1996 [doi>10.1145/233551.233553]
• 3: Nenad Dedic, Mariusz Jakubowski, Ramarathnam Venkatesan,A graph game model for software tamper protection, Lecture Notes in Computer Science, Proc of 9th Information Hiding, Brittany France, June 13-15, 2007
• 4: Boaz Barak , Oded Goldreich , Russell Impagliazzo , Steven Rudich , Amit Sahai , Salil P. Vadhan , Ke Yang, On the (Im)possibility of Obfuscating Programs, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.1-18, August 19-23, 2001
• 5: Bertrand Anckaert , Mariusz Jakubowski , Ramarathnam Venkatesan, Proteus: virtualization for diversified tamper-resistance, Proceedings of the ACM workshop on Digital rights management, October 30-30, 2006, Alexandria, Virginia, USA [doi>10.1145/1179509.1179521]
• 6: Jon Louis Bentley , Daniel D. Sleator , Robert E. Tarjan , Victor K. Wei, A locally adaptive data compression scheme, Communications of the ACM, v.29 n.4, p.320-330, April 1986 [doi>10.1145/5684.5688]
• 7: Susanne Albers , Marek Karpinski, Randomized splay trees: theoretical and experimental results, Information Processing Letters, v.81 n.4, p.213-221, 28 February 2002 [doi>10.1016/S0020-0190(01)00230-7]
• 8: Martin Fürer, Randomized splay trees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.903-904, January 17-19, 1999, Baltimore, Maryland, United States
• 9: Hovav Shacham , Matthew Page , Ben Pfaff , Eu-Jin Goh , Nagendra Modadugu , Dan Boneh, On the effectiveness of address-space randomization, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030124]
• 10: Xiaotong Zhuang , Tao Zhang , Hsien-Hsin S. Lee , Santosh Pande, Hardware assisted control flow obfuscation for embedded processors, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023873]
• 11: D. A. Osvik, A. Shamir, E. Tromer, Cache attacks and countermeasures: the case of AES, proc. RSA Conference Cryptographers Track (CT-RSA) 2006, to appear
• 12: Abramson, N. Information Theory and Coding. McGraw-Hill, New York, 1983.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  F. Theory of Computation
  F.m MISCELLANEOUS

General Terms:
Algorithms, Performance, Security, Theory

Keywords:
DRM, oblivious data structures, oblivious execution, secure data structures, secure hardware, software protection