The committee of the 41st IEEE Symposium on Security and Privacy has honoured Prof. Adrian Perrig with four Test-of-Time awards for papers published in the 12-year period between 1995 and 2006 of which he was an author.
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.
The ZISC center congratulates Prof. Perrig for the excellent achievement!