Jump to Content
William Lam

William Lam

Most recently working on privacy. Specialized in heuristic search for graphical models during grad school.
Authored Publications
Google Publications
Other Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
    A General Purpose Transpiler for Fully Homomorphic Encryption
    Shruthi Gorantala
    Rob Springer
    Sean Purser-Haskell
    Asra Ali
    Eric P. Astor
    Itai Zukerman
    Sam Ruth
    Phillipp Schoppmann
    Sasha Kulankhina
    Alain Forget
    David Marn
    Cameron Tew
    Rafael Misoczki
    Bernat Guillen
    Xinyu Ye
    Damien Desfontaines
    Aishe Krishnamurthy
    Miguel Guevara
    Yurii Sushko
    Google LLC (2021)
    Preview abstract Fully homomorphic encryption (FHE) is an encryption scheme which enables computation on encrypted data without revealing the underlying data. While there have been many advances in the field of FHE, developing programs using FHE still requires expertise in cryptography. In this white paper, we present a fully homomorphic encryption transpiler that allows developers to convert high-level code (e.g., C++) that works on unencrypted data into high-level code that operates on encrypted data. Thus, our transpiler makes transformations possible on encrypted data. Our transpiler builds on Google's open-source XLS SDK (https://github.com/google/xls) and uses an off-the-shelf FHE library, TFHE (https://tfhe.github.io/tfhe/), to perform low-level FHE operations. The transpiler design is modular, which means the underlying FHE library as well as the high-level input and output languages can vary. This modularity will help accelerate FHE research by providing an easy way to compare arbitrary programs in different FHE schemes side-by-side. We hope this lays the groundwork for eventual easy adoption of FHE by software developers. As a proof-of-concept, we are releasing an experimental transpiler (https://github.com/google/fully-homomorphic-encryption/tree/main/transpiler) as open-source software. View details
    Differentially Private SQL with Bounded User Contribution
    Celia Yuxin Zhang
    Damien Desfontaines
    Daniel Simmons-Marengo
    Proceedings on Privacy Enhancing Technologies Symposium (2020) (to appear)
    Preview abstract Differential privacy (DP) provides a theoretical promise to users and analysts limiting the ability to determine a user’s contribution (if any) to the results of analysis. While there have been many theoretical explorations into the design of DP algorithms, few generically practical implementations of end-to-end DP engines exist. This paper presents a practical SQL-based engine that provides privacy guarantees with respect to groups of records, possibly spanning multiple tables, owned by a single entity. To date there has been little work to provide this type of protection for multiple rows in the same table or joins more generally. The engine utilizes a novel algorithm that evaluates query aggregations using a two-step process to enforce DP per owning entity. We limit the query sensitivity impact of joins by restricting and propagating a row-owner identifier at all steps, which allows us to limit row-owner contribution. For testing, we present a semi-decidable stochastic model-checking system, used to ensure privacy for the engine’s full range of statistical functions. This model provides stronger guarantees on privacy than existing systems with comparable accuracy. The result is a general purpose SQL engine, capable of answering typical analysis questions with little or no modification to existing queries. View details
    Subproblem Ordering Heuristics for AND/OR Best-First Search
    Kalev Kask
    Javier Larrosa
    Rina Dechter
    Journal of Computer and System Sciences, vol. 94 (2018), pp. 41-62
    Residual Guided Look-ahead in AND/OR Search for Graphical Models
    Kalev Kask
    Javier Larrosa
    Rina Dechter
    Journal of Artificial Intelligence Research, vol. 60 (2017), pp. 287-346
    Beyond Static Mini-Bucket: Towards Integrating with Iterative Cost-Shifting Based Dynamic Heuristics
    Kalev Kask
    Rina Dechter
    Alexander Ihler
    Proceedings of SoCS (2014)