Integration of Secure Hardware and Lattice-based Cryptography

Hardware-enforced security and cryptographic methods for privacy-preserving computation have largely been considered separate fields of research. Seeded by a grant from IARPA (see below), the DSP-Lab has conducted investigation into the effective combination of Trusted Execution Environments (TEEs) and homomorphic lattice-based cryptographic construction, aiming to use each method to mitigate the weaknesses of the other. Our general strategy is to use the TEE for functionality difficult for lattice-based cryptography, while letting homomorphic computation at scale take place outside the TEE. This has been applied for large-scale multi-stage aggregative computations, general polynomial aggregation, and fault-tolerance in private stream aggregation.

GPS: Integration of Graphene, PALISADE, and SGX for Large-scale Aggregations of Distributed Data:

Cryptonomial: A Framework for Private Time-Series Polynomial Calculations: (preprint, published at Securecomm 2021)

Cryptonite: A Framework for Flexible Time-Series Secure Aggregation with Non-interactive Fault Recovery: (preprint, published at Securecomm 2021)

(More papers forthcoming!)

COVID Contact Tracing

The DSP-Lab has received a grant from The Intelligence Advanced Research Projects Activity (IARPA) to work on securely and privately performing automated contact tracing and other computations related to public health. Privacy-preserving protocols that allow contact tracing without disclosing users’ location and movement patterns will encourage participation in contact tracing programs.

Provably Secure Contact Tracing with Conditional Private Set Intersection:

CryptoGram: Fast Private Calculations of Histograms over Multiple Users’ Inputs: (preprint, published in IEEE DCOSS 2021)

Press Release:

Grant announcement:

Private Stream Aggregation

Private Stream Aggregation (PSA) aims to allow for secure and private aggregation of time-stream data from many different users by a single untrusted aggregator. Many preexisting solutions have drawbacks such as small plaintext spaces, needless complexity, large ciphertexts, or a lack of quantum security. My work in PSA adapts ideas from lattice-based cryptography and homomorphic encryption. By building new cryptographic primitives instead of using preexisting primitives (e.g. homomorphic encryption) as black-box building blocks, we can create new PSA schemes that are more efficient, quantum-secure, and simpler.

TERSE: Tiny Encryptions and Really Speedy Execution for Post-Quantum Private Stream Aggregation (preprint, to be published at Securecomm 2022):

SLAP: Simple Lattice-based Aggregation Protocol (preprint):

SLAP Implementation:

(More papers forthcoming!)

Acceleration of Homomorphic Encryption with Specialized Hardware

One line of research I am pursuing is in improving the efficiency of homomorphic encryption (HE). HE allows computations to be performed over encrypted data, but with a great computational cost inherent in the mathematics behind HE cryptosystems. Modern quantum-secure HE cryptosystems deal with operands that are ring polynomials with thousands of coefficients, where each coefficient may be hundreds of bits wide. My work in this area focuses on using unconventional techniques including hardware paradigms and parameter-based algorithmic optimizations to accelerate the polynomial operations underlying HE.

Algorithmic Acceleration of B/FV-like Somewhat Homomorphic Encryption for Compute-Enabled RAM (preprint, published in SAC 2020):

Computing-in-Memory for Performance and Energy Efficient Homomorphic Encryption (IEEE TVLSI):

(More papers forthcoming!)

Secure Data Deduplication

Deduplication is the process of identifying similar or identical data so as to conserve storage and bandwidth by not needlessly storing duplicates. Deduplication schemes are very diverse, differing in their goals, methods, and assumptions. Performing deduplication securely presents a natural conflict: users wish to safeguard their data, but information about the data must be used to detect duplicates. My work in deduplication asks: how much functionality can a deduplication scheme achieve in a highly adversarial scenario, using minimal cryptographic assumptions? It turns out you can do a lot: without even a single trusted party, secure nearly-identical deduplication can be achieved even against fully malicious adversaries.

Secure Single-Server Nearly-Identical Image Deduplication (IEEE ICCCN 2020):

Proof-of-concept implementation of Secure Single-Server Nearly-Identical Image Deduplication:

Secure Hardware

My labmate and good friend Ryan Karl (now at Carnegie Mellon) carries out research that seeks to utilize the cryptographic capabilities of Trusted Execution Environments – secure hardware systems providing a trusted environment to programs even against a malicious operating system. I have had the pleasure of working alongside Ryan in implementing protocols applying TEEs to secure multiparty computation and machine learning.

Additionally, I conducted research on using TEEs for privacy-preserving advertising at Meta. This work is not currently publicly available.

Template Project for Intel SGX Applications:

WiP: Using Intel SGX to improve private neural network training and inference (published at HotSoS 2020):

Non-Interactive MPC with Trusted Hardware Secure Against Residual Function Attacks (preprint, published in proceedings of SecureComm 2019):

Proof-of-concept implementation of Non-Interactive MPC with Trusted Hardware Secure Against Residual Function Attacks:

(More papers forthcoming!)

Beyond the 12-tone System

Western music theory utilizes a 12-tone system, with the interval between each octave divided into 12 semitones. Previous work applied group theory to extend the mathematical framework underlying the 12-tone system to systems with 8k+4 semitones (for positive integers k). My senior thesis work under Dr. Mark Bollman explored continuing this line of research. Counterpoint, the style and rules of music defining the Baroque era, depends heavily on intervals between different melodic lines. Thus in order to be able to write contrapuntal music in systems of 8k+4 tones, a concept of “interval” is needed for these higher-order systems. My research showed that the traits of intervals in a 12-tone system can be used to derive an algorithm for classifying intervals in higher-order systems, and that the algorithm’s results are coherent and consistent with both the 12-tone system and higher-order systems. A warning to anyone wanting to continue this line of research: though the mathematics are fascinating, a conclusion of previous work is that music in higher-order systems will sound unpalatably dissonant.

Classification of Consonance in Generalized Tonal Systems (published in The Pentagon, Vol 76, No. 2):

Implementation of Classification of Consonance in Generalized Tonal Systems: