The ACM CCS Test-of-Time Award honors research with long-lasting influence, which have had significant impacts on systems security and privacy. The 2023 award in respect of a paper by Marten van Dijk and others about Path ORAM was made at the recent ACM Conference on Computer and Communications Security held in Copenhagen, Denmark.

ACM Special Interest Group on Security, Audit and Control (SIGSAC) ACM CCS The Test-of-Time Award 2023 The test-of-time award winners for CCS 2023 are as follows: Emil Stefanov, Marten van Dijk, Elaine Shi, T-H. Hubert Chan, Christopher Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas: Path ORAM: An Extremely Simple Oblivious. Pages 299-310, In Proceedings of the 20th ACM Conference on Computer and Communications Security, CCS 2013, Berlin, Germany. ACM 2013, ISBN: 978-1-4503-2477-9

When originally presented at the 2013 ACM Conference on Computer and Communications Security held in Berlin, Germany this paper received a best student paper award.

The lead author of the paper Emil Stefanov, a Ph.D. candidate in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley, died in 2014, before the paper was selected as a 2018 Top Pick in Hardware and Embedded Security. In 2023 it was one of the two papers that led to the IEEE CS Edward J. McCluskey Technical Achievement Award for Marten van Dijk for:

contributions to oblivious and encrypted computation

So what is the Path ORAM algorithm? Why is it needed,  how did it evolve, and why it is called "Path ORAM"?

A web memorial to Emil Stefanov states:

Emil is well-known for his innovative work on obfuscating access patterns to sensitive data. Among his numerous novel inventions, he proposed the Path Oblivious RAM algorithm, which is by far one of the most simple, elegant, and efficient solutions known to date. Path ORAM has enabled the first ORAM-capable secure processors to be prototyped, including Ascend and Phantom. 

The problem tackled is that data encryption alone is often not enough to protect users’ privacy in outsourced storage applications. The sequence of storage locations accessed by the client (the access pattern) can leak a significant amount of sensitive information about the unencrypted data through statistical inference.

Oblivious RAM algorithms, first proposed by Goldreich and Ostrovsky, allow a client to conceal this access pattern to the remote storage by continuously shuffling and re-encrypting data as they are accessed. An adversary can then observe the physical storage locations accessed, but the ORAM algorithm ensures that this adversary has negligible probability of learning anything about the true (logical) access pattern.

The Path ORAM algorithm was at the time the most practical ORAM construction under small client storage. Stephanov, together with van Dijk, who is now head of the Computer Secuiruty research Group at CWI, Netherlands, and five other researchers proved theoretical bounds on its performance and also presented matching experimental results.

The core of their construction is called Path ORAM because data on the server is always accessed in the form of tree paths.

More Information

Marten van Dijk and co-authors win ACM CCS 2023 Test of Time Award

Remembering Emil

Related Articles

Inaugural STOC Test Of Time Awards

Test Of Time Award For Classic Paper On Bow-Tie Structure Of The Web

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info