Portrait of Olya Ohrimenko

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. In CCS 2015.

Verifiable Member and Order Queries on a List in Zero-Knowledge, with E. Ghosh and R. Tamassia. 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. In Financial Crypto 2015. Blog entry.

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

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


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 2012ACM 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 2012Research 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 2012Information 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 (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).



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


I was lucky to work with bright interns Divya Sharma (Carnegie Mellon University) in 2014 and Esha Ghosh (Brown University) in 2015.

On the program committee of CCS Workshop on Privacy in the Electronic Society (WPES 2014, WPES 2015), AsiaCCS Workshop on Security in Cloud Computing (AsiaCCS-SCC 2015), Conference on Distributed Computing Systems (ICDCS 2016).