Security Sleuths: UC San Diego Computer Scientists’ Solutions to Security Issues Withstand the Test

Five Test of Time awards from leading computer science organizations have been bestowed this year to the UC San Diego researchers and their teams for leaving a lasting impact in security and cryptography.

“UC San Diego has tremendous strengths in cybersecurity as five prestigious awards have been earned by members of our Security and Cryptography group this year, and eight have been earned in the last four years,” said CSE Department Chair Sorin Lerner. “The collaborative environment here fosters breakthrough research in this important field. I am excited to see what our researchers will come up with next.”

The papers, teams and impact are as follows, in order of award date:

1. Professor Daniele Micciancio won the 2022 Test of Time Award at the 63rd IEEE Symposium on Foundations in Computer Science for his 2002 paper, “Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions.” 

Micciancio’s paper transformed the field of lattice-based cryptography – an important area of post-quantum cryptography designed to protect classical computers against attacks by quantum computers. Micciancio’s paper was key for proving that lattice-based cryptography has immense theoretical and practical impact. It showed that cryptography based on lattices can be both efficient and secure under worst-case complexity assumptions, a feat never reached by number-theory based cryptography.

With remarkable foresight, the paper first boldly put forward a conjecture on the worst-case hardness of "algebraically structured" lattices, then rigorously proved that such hardness gives rise to similarly structured average-case hardness, and finally convincingly argued that this structure admits fast implementation on modern microprocessors. The techniques introduced in this paper have evolved and grown to an immense body of work, shaping many future results in the area.

2. Associate Professor Deian Stefan and his collaborators were awarded a Test of Time award at the 2022 ACM International Conference of Functional Programing for his 2012 paper, "Addressing Covert Termination and Timing Channels in Concurrent Information Flow Systems.” This paper develops a framework – LIO – that makes it possible for developers to build secure applications that preserve the confidentiality of user data, even in the presence of malicious code that can exploit covert and side channels.

In computer security, attackers can exploit different abstractions – from programming language features to hardware caches – to covertly leak sensitive information. For example, if a program terminates based on secret data, an attacker can learn if that secret is true (the program terminated) or false (the program did not terminate). Stefan’s paper is “among the first to describe covert channels caused by termination and timing,” according to the award committee. The LIO system the researchers built to eliminate these covert channels both led the pathway towards new directions for information flow security and new ways to build secure systems.

3. Associate Professor Nadia Heninger was recognized for her paper "Mining your Ps and Qs: Detection of widespread weak keys in network devices.” This 2012 paper found that random number generation algorithms – which are used to generate cryptographic secret keys – were flawed and had led to widespread use of compromised keys in the wild.

Heninger and her co-authors were able to compute the secret keys for half a percent of all of the Transport Layer Security servers they could observe on the Internet using an efficient algorithm that exploited the shared common prime factors in their RSA public keys. RSA is a public-key cryptosystem that is widely used to secure data transmission. They were also able to compute the secret keys for one percent of visible SSH servers who used poor randomness to generate keys and digital signatures.  The Secure Shell (SSH) protocol allows remote computers to make encrypted connections to servers.

Importantly, this paper also illustrated that active network measurement could be used to find previously unknown cryptographic vulnerabilities in the wild. This resulted in an immediate patch to the Linux kernel to fix entropy collection in the random number generation system, and over the years has contributed to a rethinking of the entire design of the random number generator.

4. Eleven years ago, CSE Professors Stefan Savage and Geoff Voelker, along with colleagues, published a comprehensive analysis of the spam criminal value chain titled, “Click Trajectories: End-to-End Analysis of the Spam Value Chain.” Its impact – a holistic quantification of the full set of resources employed to monetize spam email— was also celebrated with a Test of Time award, presented at the 2022 IEEE Security and Privacy conference. 

The paper outlined the ways spam can be monetized, including naming, hosting, payment and fulfillment. Savage’s and Voelker’s team used this data to characterize the relative prospects for defensive interventions at each link in the spam value chain. Notably, they provided the first strong evidence of payment bottlenecks in the spam value chain, concluding that 95 percent of spam-advertised pharmaceutical, replica and software products are monetized using merchant services from just a handful of banks.This bottleneck was later used successfully by major brand holders to disrupt spam-advertised counterfeit sites.

5. Professor Mihir Bellare has– again– received the International Association for Cryptologic Reseearch’s Test of Time award for the second year in a row, this time for his 2007 paper "Deterministic and Efficiently Searchable Encryption." Bellare and his co-authors made it possible to perform searches on encrypted data without compromising security, and also made it possible to retain security in the face of  compromises of random number generation processes.

They suggested database encryption methods that permit fast (i.e. sub-linear time) search while also providing privacy that is as strong as possible. Their approach ultimately led to RSA-DOAEP, the first example of a public-key cipher. They also proposed efficiently searchable encryption schemes, which permit more flexible privacy to search-time trade-offs via a technique called bucketization.