Sam Kumar

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2023-194

July 18, 2023

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-194.pdf

Expressive cryptography, including Secure Multi-Party Computation (SMPC), Fully Homomorphic Encryption (FHE), and policy-based encryption, has the potential to enable transformative new applications. Unfortunately, it is often slow and resource-intensive, making those applications difficult to realize. For example, SMPC enables multiple organizations (e.g., hospitals) to run joint computations on their data (e.g., for better medical diagnosis and treatment) while keeping the inputs to the computation (e.g., patient data) secret. But SMPC can have high memory overhead, making it difficult to scale such applications to large problem sizes. As a result, while expressive cryptography has seen some notable real-world usage, such as Meta using SMPC in its advertising business, existing adoption is not widespread, limited to incipient and isolated deployments.

This dissertation studies how to design and build networked systems to enable expressive cryptography to reach its full transformative potential. We present six system design techniques for systems relating to expressive cryptography, classified into two high-level approaches. We validate our techniques by using them to design and implement four systems: MAGE, TCPlp, JEDI, and Ghostor.

Our first high-level approach is to make expressive cryptography generically more efficient by redesigning the underlying systems that expressive cryptography uses. For example, MAGE provides virtual memory for SMPC and FHE at nearly zero cost, allowing them to efficiently scale beyond the available memory to larger problem sizes. TCPlp is a performant TCP-based transport layer for low-power wireless networks, which allows the large ciphertexts and signatures associated with expressive cryptography to be efficiently transferred over the network.

Our second high-level approach approach is to make expressive cryptography practical for particular applications by rethinking how and when to use expressive cryptography. For example, we designed Ghostor, a data-sharing system, and JEDI, an end-to-end encryption protocol for publish-subscribe IoT deployments, using this approach. Ghostor uses a blockchain and JEDI leverages policy-based encryption, but they are carefully designed to use these components rarely and outside of the critical path of user-facing operations.

We further validate our techniques by using them to analyze related work, to identify existing work that applies our techniques and opportunities to improve existing systems using our techniques. Then, we discuss the impact of our work, including the adoption of TCPlp as the TCP implementation in OpenThread, an open-source network stack used in the smart home IoT industry, including by Amazon Eero and Google Nest. We hope that our techniques, and the systems we designed using them, will accelerate the widespread adoption of expressive cryptography, bringing stronger security to existing applications and enabling exciting new ones.

Advisors: David E. Culler and Raluca Ada Popa

---

BibTeX citation:

@phdthesis{Kumar:EECS-2023-194,
    Author= {Kumar, Sam},
    Title= {Rethinking System Design for Expressive Cryptography},
    School= {EECS Department, University of California, Berkeley},
    Year= {2023},
    Month= {Jul},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-194.html},
    Number= {UCB/EECS-2023-194},
    Abstract= {Expressive cryptography, including Secure Multi-Party Computation (SMPC), Fully Homomorphic Encryption (FHE), and policy-based encryption, has the potential to enable transformative new applications. Unfortunately, it is often slow and resource-intensive, making those applications difficult to realize. For example, SMPC enables multiple organizations (e.g., hospitals) to run joint computations on their data (e.g., for better medical diagnosis and treatment) while keeping the inputs to the computation (e.g., patient data) secret. But SMPC can have high memory overhead, making it difficult to scale such applications to large problem sizes. As a result, while expressive cryptography has seen some notable real-world usage, such as Meta using SMPC in its advertising business, existing adoption is not widespread, limited to incipient and isolated deployments.

This dissertation studies how to design and build networked systems to enable expressive cryptography to reach its full transformative potential. We present six system design techniques for systems relating to expressive cryptography, classified into two high-level approaches. We validate our techniques by using them to design and implement four systems: MAGE, TCPlp, JEDI, and Ghostor.

Our first high-level approach is to make expressive cryptography generically more efficient by redesigning the underlying systems that expressive cryptography uses. For example, MAGE provides virtual memory for SMPC and FHE at nearly zero cost, allowing them to efficiently scale beyond the available memory to larger problem sizes. TCPlp is a performant TCP-based transport layer for low-power wireless networks, which allows the large ciphertexts and signatures associated with expressive cryptography to be efficiently transferred over the network.

Our second high-level approach approach is to make expressive cryptography practical for particular applications by rethinking how and when to use expressive cryptography. For example, we designed Ghostor, a data-sharing system, and JEDI, an end-to-end encryption protocol for publish-subscribe IoT deployments, using this approach. Ghostor uses a blockchain and JEDI leverages policy-based encryption, but they are carefully designed to use these components rarely and outside of the critical path of user-facing operations.

We further validate our techniques by using them to analyze related work, to identify existing work that applies our techniques and opportunities to improve existing systems using our techniques. Then, we discuss the impact of our work, including the adoption of TCPlp as the TCP implementation in OpenThread, an open-source network stack used in the smart home IoT industry, including by Amazon Eero and Google Nest. We hope that our techniques, and the systems we designed using them, will accelerate the widespread adoption of expressive cryptography, bringing stronger security to existing applications and enabling exciting new ones.},
}

EndNote citation:

%0 Thesis
%A Kumar, Sam 
%T Rethinking System Design for Expressive Cryptography
%I EECS Department, University of California, Berkeley
%D 2023
%8 July 18
%@ UCB/EECS-2023-194
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-194.html
%F Kumar:EECS-2023-194