Christopher W. Fletcher

Intersections of Applied Cryptography and Systems Bibliography

This page contains a list of papers that are good reading if you are interested in encrypted/data oblivious computation. The crypto papers are good starting points. I try to keep the circuit abstraction papers ("Running Programs in the Circuit Model" and below) up to date as new papers come out.

Non-Homomorphic Encryption

  1. Identity-based Encryption
    Identity-Based Encryption from the Weil Pairing
    Dan Boneh and Matthew Franklin

  2. Broadcast Encryption
    Collusion Resistant Broadcast Encryption With Short Ciphertexts and Private Keys
    Dan Boneh and Craig Gentry

  3. Attribute-based Encryption
    Attribute-Based Encryption for Fine-Grained Access Control of Encrypted Data
    Vipul Goyal, Omkant Pandey, Amit Sahai and Brent Waters

  4. Order-preserving Encryption
    An Ideal-Security Protocol for Order-Preserving Encoding
    Raluca Ada Popa, Frank H. Li and Nickolai Zeldovich

Homomorphic Encryption

  1. The Damgard-Jurik cryptosystem, a generalization of the Pallier additive HE scheme with constant ciphertext blowup
    A Generalisation, a Simplification and some Applications of Paillier's Probabilistic Public-Key System
    Ivan Damgard and Mads Jurik

  2. Homomorphic encryption allowing additions plus a single multiplication
    Evaluating 2-DNF Formulas on Ciphertexts
    Dan Boneh, Eu Jin Goh and Kobbi Nissim

  3. The first Gen-III (modern) FHE scheme
    Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
    Craig Gentry, Amit Sahai and Brent Waters

  4. Low latency bootstrapping
    FHEW: Bootstrapping Homomorphic Encryption in less than a second
    Leo Ducas and Daniele Micciancio

For a more complete list, see Vinod Vaikuntanathan's FHE resource page.

Oblivious RAM

  1. A simple and efficient Tree-based ORAM
    Path ORAM: An Extremely Simple Oblivious RAM Protocol
    Emil Stefanov, Marten van Dijk, Elaine Shi, T-H. Hubert Chan, Christopher Fletcher, Ling Ren, Xiangyao Yu and Srinivas Devadas

Proofs of Retrievability

  1. An efficient PoR based on Hierarchical ORAM
    Practical Dynamic Proofs of Retrievability
    Elaine Shi, Emil Stefanov and Charalampos Papamanthou

Running Programs in the Circuit Model for x86

The circuit model, a.k.a. data oblivious, "constant time", is a pervasive programming abstraction used by theoretical and applied cryptographers as well as systems programmers for writing code that does not leak privacy. The below papers detail efforts in this space when the "backend" is x86 running on a commercial machine. Here, the privacy threat is microarchitectural side channel attacks.

  1. Cryptography
    Curve25519: New Diffie-Hellman Speed Records
    Daniel J. Bernstein

  2. General purpose code (1)
    Practical Mitigations for Timing-Based Side-Channel Attacks on Modern x86 Processors
    Bart Coppens, Ingrid Verbauwhede, Koen De Bosschere and Bjorn De Sutter

  3. General purpose code (2)
    Raccoon: Closing Digital Side-Channels through Obfuscated Execution
    Ashay Rane, Calvin Lin and Mohit Tiwari

  4. Machine learning
    Oblivious Multi-Party Machine Learning on Trusted Processors
    Olga Ohrimenko, Felix Schuster, Cedric Fournet, Aastha Mehta, Sebastian Nowozin, Kapil Vaswani and Manuel Costa

  5. Databases
    Opaque: An Oblivious and Encrypted Distributed Analytics Platform
    Wenting Zheng, Ankur Dave, Jethro G. Beekman, Raluca Ada Popa, Joseph E. Gonzalez and Ion Stoica

  6. Memory (1)
    ZeroTrace: Oblivious Memory Primitives from Intel SGX
    Sajin Sasy, Sergey Gorbunov and Christopher W. Fletcher

  7. Memory (2)
    Oblix: An Efficient Oblivious Search Index
    Pratyush Mishra, Rishabh Poddar, Jerry Chen, Alessandro Chiesa and Raluca Ada Popa

  8. Memory (3)
    Obliviate: A Data Oblivious Filesystem for Intel SGX
    Adil Ahmad, KyungTae Kim, Muhammad Ihsanulhaq Sarfaraz and Byoungyoung Lee

  9. System utilities
    On the Trade-Offs in Oblivious Execution Techniques
    Shruti Tople and Prateek Saxena

  10. Floating point
    On Subnormal Floating Point and Abnormal Timing
    Marc Andrysco, David Kohlbrenner, Keaton Mowery, Ranjit Jhala, Sorin Lerner and Hovav Shacham

Data Structures and Algorithms Written in the Circuit Model

  1. An Oblivious RAM with client logic optimized for the Circuit Model
    Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound
    Xiao Wang, Hubert Chan and Elaine Shi

  2. Sorting
    Bitonic sorting
    Ken Batcher

  3. Sparse graphs
    GraphSC: Parallel Secure Computation Made Easy
    Kartik Nayak, Xiao Shaun Wang, Stratis Ioannidis, Udi Weinsberg, Nina Taft and Elaine Shi

  4. Breadth first search
    Data-oblivious Graph Algorithms for Secure Computation and Outsourcing
    Marina Blanton, Aaron Steele and Mehrdad Alisagari

  5. Stable matching
    Secure Stable Matching at Scale
    Jack Doerner, David Evans and abhi shelat

  6. Maps, sets, lists, graphs, trees
    Oblivious Data Structures
    Xiao Shaun Wang, Kartik Nayak, Chang Liu, T-H. Hubert Chan, Elaine Shi, Emil Stefanov and Yan Huang

  7. Stacks, queues, associative maps
    Circuit Structures for Improving Efficiency of Security and Privacy Tools
    Samee Zahur and David Evans

Frameworks Supporting Circuit Model Computation

  1. Compiling/languages for constant time programming
    FaCT: A DSL for timing-sensitive computation
    Sunjay Cauligi, Gary Soeller, Brian Johannesmeyer, Fraser Brown, Riad S. Wahby, John Renner, Benjamin Gregoire, Gilles Barthe, Ranjit Jhala and Deian Stefan

  2. ISA extensions for programming in the circuit model
    Data Oblivious ISA Extensions for Side Channel-Resistant and High Performance Computing
    Jiyong Yu, Lucas Hsiung, Mohamad El Hajj and Christopher W. Fletcher

  3. Compiling to the circuit model, programming abstractions, oblivious depth first search
    ObliVM: A Programming Framework for Secure Computation
    Chang Liu, Xiao Shaun Wang, Kartik Nayak, Yan Huang and Elaine Shi

  4. Memory-efficient circuit model computation
    TinyGarble: Highly Compressed and Scalable Sequential Garbled Circuits
    Ebrahim M. Songhori, Siam U. Hussain, Ahmad-Reza Sadeghi, Thomas Schneider and Farinaz Koushanfar