Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Olya Ohrimenko

I am a researcher in Constructive Security and Programming Principles and Tools groups at MSR Cambridge, UK. I am also the Microsoft Fellow at Darwin College, Cambridge University. Before MSR I was a Ph.D. student at Brown University working with Roberto Tamassia.

I am interested in security and data privacy of cloud storage and computation including private access to remote storage, verification of outsourced computation and data integrity protocols. My other interests include algorithms, data structures and theory.

Recent work:

Observing and Preventing Leakage in MapReduce, with M. Costa, C. Fournet, C. Gkantsidis, M. Kohlweiss, and D. Sharma (pdf). To appear in CCS 2015.

Verifiable Member and Order Queries on a List in Zero-Knowledge, with E. Ghosh and R. Tamassia (pdf). In ACNS 2015, Best Student Paper Award. Article in Brown CS news. Presentation at CRYPTO'14 rump session. Dynamic extension and applications to trees (pdf).

Sorting and Searching Behind the Curtain, with F. Baldimtsi (pdf). In Financial Crypto 2015. Blog entry.

Verifying the Consistency of Remote Untrusted Services, with Commutative Operations, with C. Cachin (pdf). In OPODIS 2014.

The Melbourne Shuffle: Improving Oblivious Storage in the Cloud, with M. T. Goodrich, R. Tamassia and E. Upfal (pdf) in ICALP 2014. In the media: ACM Tech News, The Register, Business Cloud News, CloudPro and Bruce Schneier's blog.

Haze: Privacy-Preserving Real-Time Traffic Statistics, with J. Brown and R. Tamassia in SIGSPATIAL/GIS (full version pdf) 2013.


Private Access to Outsourced Storage:

  • Graph Drawing in the Cloud: Privately Visualizing Relational Data using Small Working Storage, with M. Goodrich and R. Tamassia in GD 2012: International Symposium on Graph Drawing (pdf).

  • Practical Oblivious Storage, with M. Goodrich, M. Mitzenmacher and R. Tamassia in CODASPY 2012: ACM Conference on Data and Application Security and Privacy (pdf).

  • Privacy-Preserving Group Data Access via Stateless Oblivious RAM Simulation, with M. Goodrich, M. Mitzenmacher and R. Tamassia in SODA 2012: Symposium on Discrete Algorithms (pdf).

  • Oblivious RAM Simulation with Efficient Worst-Case Access Overhead, with M. Goodrich, M. Mitzenmacher and R. Tamassia in CCSW 2011: ACM Cloud Computing Security Workshop at CCS (pdf).

Authentication of Search Results:

  • Efficient Verification of Web-Content Searching Through Authenticated Web Crawlers, with M. Goodrich, D. Nguyen, C. Papamanthou, R. Tamassia, N. Triandopoulos and C. Lopes in PVLDB 2012: Research Track for Very Large Data Bases (pdf) (Journal).

  • Authenticating Email Search Result, with H. Reynolds and R. Tamassia STM 2012 International Workshop on Security and Trust Management at ESORICS.

In theory:

  • Lower Bounds for Randomized Algorithms for Online Chain Partitioning, with C. Mathieu IPL 2012: Information Processing Letters Volume 112 (pdf) (Journal).

My Honors project at Melbourne University was in Constraint Programming and I was lucky to be advised by Peter Stuckey:

  • Propagation via Lazy Clause Generation, with P. Stuckey and M. Codish in Constraints 2009: Constraints Journal, Volume 14 (pdf) (Journal).

  • Propagation = Lazy Clause Generation (Best Student Paper Award), with P. Stuckey and M. Codish in CP 2007: Principles and Practice of Constraint Programming (pdf).

  • Modelling for Lazy Clause Generation, with P. Stuckey in CATS 2008: Computing: the Australasian Theory Symposium (pdf).

In 2006 I was an RA in Aaron Harwood's peer-to-peer group:

  • Mean Field Models of Message Throughput in Dynamic Peer-to-Peer Systems, with A. Harwood (pdf).

Professional Activity

PC member: CCS Workshop on Privacy in the Electronic Society (WPES 2015), AsiaCCS Workshop on Security in Cloud Computing (AsiaCCS-SCC 2015), WPES 2014.


2008-2013 Sc.M., Ph.D. Brown University
2004-2007 B.CS. (Hons) Melbourne University


2012 IBM Research Zurich with Christian Cachin
2012 MSR Redmond with Seny Kamara
2010 Google NYC, Search team
2009 Google CA, AdSense
2008 Optiver, Australia


- Trusted Cloud at MSR.
- I participated in Heidelberg Laureate Forum.
- On judge panel of Codess Hackathon.
- My Erdős number is 3 (times 3 from Claire Mathieu, Michael Mitzenmacher and Eli Upfal).

Email: oohrim microsoft com