Prof. Adrian Perrig receives four Test-of-Time awards at single conference

Nine papers, which have withstood the test of time, were awarded at the 41st IEEE Symposium on Security and Privacy, held from 18-20 May 2020. Prof. Adrian Perrig received awards for four of them - an unprecedented achievement.

Prof. Perrig co-authored these award-winning papers:

"Efficient Authentication and Signing of Multicast Streams Over Lossy Channels" (IEEE S&P 2000)
Authors: Adrian Perrig, Ran Canetti, J.D. Tygar and Dawn Song

The core contribution of this paper is TESLA, a system for authentication of broadcast messages (referred to as multicast streams in the paper's title). Fundamentally, some form of asymmetry is needed for secure broadcast authentication, such that the only the sender can create the authentication information, and all the receivers can verify (but not create) the authentication. Traditionally, this asymmetry was achieved with digital signatures, which unfortunately are about 10'000 times slower than a symmetric cryptographic scheme.

The main innovation of TESLA was to use time to achieve asymmetry, where a message is authenticated with a secret key that will be made public at a later point in time. TESLA utilises one-way functions, which can be constructed from efficient symmetric cryptography. As a result, TESLA is much more efficient than other proposed systems.

Over the past 20 years, the TESLA authentication system was used in a variety of real-world applications. Today, TESLA is being considered for the authentication of satellite navigation messages.

"Practical Techniques for Searches on Encrypted Data" (IEEE S&P 2000)
Authors: Dawn Song, David Wagner and Adrian Perrig

This paper presented the first efficient construction to enable an untrusted server to perform a search on encrypted data without leaking the search term. With the emergence of cloud computing, the paper inspired a wealth of follow-up research to further improve search operations, but also to support a variety of operations on encrypted data. With these systems, a user can perform operations on encrypted data in the cloud, without needing to trust the cloud operator.

"Random Key Predistribution Schemes for Sensor Networks" (IEEE S&P 2003)
Authors: Haowen Chan, Adrian Perrig and Dawn Song

The paper is set in the key distribution model proposed by Eschenauer and Gligor in their seminal CCS 2002 paper "A key-management scheme for distributed sensor networks". Their idea was to select a pool of symmetric cryptographic keys, and provide a subset of keys to individual sensor nodes. Two neighbouring nodes would then determine which keys of the key pool they had in common, and if they had at least one common key, they would use that to protect their communication.

This elegant approach was intensely intriguing. We extended the model of key distribution and established an approach for analysing the security of such schemes. By identifying 3 different ways of extending the resilience of the original key pooling scheme, we showed that key-pooling was not limited to just a single algorithm, but was in fact an exciting problem space admitting a large number of approaches with different properties and trade-offs.

Tremendous community interest arose, as many researchers started to embark and propose a series of ever-improved systems. This wave of research also helped to popularise the threat model of multiple node compromise in sensor networks and IoT. This threat model continues to be a fruitful source of research challenges today. We are grateful to have been part of this journey.

"Distributed Detection of Node Replication Attacks in Sensor Networks" (IEEE S&P 2005)
Authors: Bryan Parno, Adrian Perrig and Virgil Gligor

The paper observed that in some networks, an attacker can capture a legitimate node, extract its secrets, and then introduce many clones of that node back into the network. This gives the attacker significant influence over the network, allowing it to, for example, suppress legitimate alarms or subvert additional nodes. Detecting such a threat is quite difficult, since the clones have all of the access and authentication tokens the original trusted node did. To counter this threat, the paper introduces a pair of protocols designed to detect replication via "emergent algorithms”, which produce a network-level property via the independent actions of many nodes. This adversary model and problem formulation captured the community's interest, and led to some remarkable follow on work, both in sensor networks, and in other contexts, e.g., detecting fake accounts in social networks.

About Prof. Adrian Perrig

Adrian Perrig is a professor at the Department of Computer Science at ETH Zurich, Switzerland, where he leads the Network Security Group. He is also a distinguished fellow at CyLab, and an adjunct professor of Electrical and Computer Engineering at Carnegie Mellon University. From 2002 to 2012, he was a professor of electrical and computer engineering, engineering and public policy, and computer science (courtesy) at Carnegie Mellon University, becoming full professor in 2009. From 2007 to 2012, he served as the technical director for Carnegie Mellon's Cybersecurity Laboratory (CyLab). He earned his MS and PhD degrees in computer science from Carnegie Mellon University, and spent three years during his PhD at the University of California at Berkeley. He received his BSc degree in computer engineering from EPFL. Prof. Perrig's research revolves around building secure systems - in particular his group is working on the SCION secure Internet architecture.