CAREER: Encrypted Systems with Fine-Grained Leakage

Organizations and individuals outsource sensitive data from their own local systems to remote cloud services, making encryption necessary to maintain the privacy and security of the sensitive data. However, to preserve the usefulness of the outsourced data, the goal is to encrypt it so that users can still ask questions about their data without ever decrypting it on the cloud's premises.

Current end-to-end encrypted system approaches aimed at addressing this goal have converged to two extremes. In one case, the approaches leak (i.e., reveal) some information about the encrypted data records that are processed in answering a query, which gives a false sense of security since leaks may enable reconstruction of the underlying sensitive information by sophisticated adversaries.

In the other extreme, approaches do not reveal any information about the processed data, which requires significantly more computation and makes the overall performance too slow for practical use. The project's novelties are introducing a new paradigm for encrypted systems with carefully constructed, fine-grained leakage that is (1) scalable for practical use and (2) provides rigorous guarantees of protection against the reconstruction adversaries.

The project's broader significance and importance are in influencing practical designs and industry practices to create a safer deployment of encrypted systems. The project aims to enhance education by integrating security modules into the undergraduate and graduate curriculum, introducing interdisciplinary courses, broadening student engagement, and expanding pilot programs with local high schools.

This project introduces encrypted systems with fine-grained leakage and focuses on three interconnected areas: The first explores how specific query and update patterns can nullify leakage, providing provable guarantees of inapproximability or inability to reconstruct against adversarial reconstructions. The second thrust develops cryptographic designs for structured encryption, enabling context-informed leakage profiles that dynamically increase adversarial uncertainty.

The third thrust applies this paradigm to concrete real-world scenarios. The research team plans to share project results with industry collaborators.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.