## CryptoDB

### Mike Burmester

#### Publications

Year
Venue
Title
2007
EPRINT
Security and privacy in RFID systems is an important and active research area. A number of challenges arise due to the extremely limited computational, storage and communication abilities of a typical RFID tag. This work describes two families of simple, inexpensive, and untraceable identification protocols for RFID tags. The proposed protocols involve minimal interaction between a tag and a reader and place low computational burden on the tag, requiring only a pseudo-random generator. They also impose low computational load on the back-end server. The paper also describes a universally composable security model tuned for RFID applications. By making specific setup, communication, and concurrency assumptions that are realistic in the RFID application setting, we arrive at a model that guarantees strong security and availability properties, while still permitting the design of practical RFID protocols. We show that our protocols are provably secure within the new security model. The security supports, availability, authentication, forward-secure anonymity and key exchange, and modularity. The last attribute is most appropriate for ubiquitous applications.
2007
EPRINT
Mobile ad hoc networks (MANETs) are collections of wireless mobile devices with restricted broadcast range and resources, and no fixed infrastructure. Communication is achieved by relaying data along appropriate routes. Discovering such routes however is a major task, both from an efficiency point of view and from a security point of view. In particular, it is important that the route discovered is not controlled by the adversary. Several route discovery protocols have been proposed in the literature that address the particular requirements of a MANET, but as we demonstrate in this paper their security is still analyzed in weak models and cannot tolerate certain classes of attack. Recently, a security framework tailored to the specific requirements of MANETs was presented and a route discovery algorithm, endairA, was proposed that was proven'' secure in this framework. In this paper we show that the security proof for endairA is flawed, and that the proposed route discovery algorithm is vulnerable to a {\em hidden channel} attack. We then analyze the security framework used for route discovery and argue that composability is an essential feature for ubiquitous applications. We conclude by discussing some of the main issues that must be addressed for secure route discovery.
2007
EPRINT
A considerable number of anonymous RFID authentication schemes have been proposed. However, current proposals either do not provide robust security guarantees, or suffer from scalability issues when the number of tags issued by the system is very large. In this paper, we focus on approaches that reconcile these important requirements. In particular, we seek to reduce the complexity of identifying tags by the back-end server in anonymous RFID authentication protocols---what we term the key-lookup problem. We propose a compiler that transforms a generic RFID authentication protocol (supporting anonymity) into one that achieves the same guarantees with constant key-lookup cost even when the number of tags is very large (billions of tags and beyond). This approach uses a lightweight one-way trapdoor function and produces protocols that are suitable for deployment into current tag architectures. We then explore the issue of minimal assumptions required, and show that one-way trapdoor functions are necessary to achieve highly scalable, robustly secure solutions. We then relax the requirement of unlinkable anonymity, and consider scalable solutions that are provably secure and for which the loss of privacy is minimal.
2007
EPRINT
We investigate an application of RFIDs referred to in the literature as the group scanning problem, in which several tags are simultaneously'' scanned by a reader. The security context of this application was first discussed by Ari Juels, who presented a protocol that allows pairs of RFID tags to provide evidence of having been simultaneous scanned---a yoking proof. Our goal is to study group scanning proofs in strong adversarial models. We describe a security model for RFID group scanning proofs, and consider versions of the problem that require privacy (anonymity) of the grouped tags, and/ or forward-security properties. Our security model is based on the Universal Composability framework and supports reusability (through modularity of security guarantees). We also introduce novel protocols that realize the security models, focusing on efficient solutions based on off-the-shelf components, such as highly optimized pseudo-random function designs that require fewer than 2000 Gate-Equivalents.
2006
EPRINT
This paper examines two unlinkably anonymous, simple RFID identification protocols that require only the ability to evaluate hash functions and generate random values, and that are provably secure against Byzantine adversaries. The main contribution is a universally composable security model tuned for RFID applications. By making specific setup, communication, and concurrency assumptions that are realistic in the RFID application setting, we arrive at a model that guarantees strong security and availability properties, while still permitting the design of practical RFID protocols. We show that the two previously proposed protocols are provably secure within the new security model. Our proofs do not employ random oracles---the protocols are shown to be secure in the standard model under the assumption of existence of pseudo-random function families.
2006
EPRINT
Task-specific groups are often formed in an ad-hoc manner within big structures, like companies. Take the following typical scenario: A high rank manager decides that a task force group for some project needs to be built. This order is passed down the hierarchy where it finally reaches a manager who calls some employees to form a group. The members should communicate in a secure way and for efficiency reasons symmetric systems are the common choice. To establish joint secret keys for groups, group key exchange (GKE) protocols were developed. If the users are part of e.g. a Public Key Infrastructure (PKI), which is usually the case within a company or a small network, it is possible to achieve authenticated GKE by modifying the protocol and particularly by including signatures. In this paper we recall a GKE due to Burmester and Desmedt which needs only $O(\log n)$ communication and computation complexity per user, rather than $O(n)$ as in the more well-known Burmester-Desmedt protocol, and runs in a constant number of rounds. To achieve authenticated GKE one can apply compilers, however, the existing ones would need $O(n)$ computation and communication thereby mitigating the advantages of the faster protocol. Our contribution is to extend an existing compiler so that it preserves the computation and communication complexity of the non-authenticated protocol. This is particularly important for tree based protocols.
2006
EPRINT
Protocols proven secure in universally composable models remain secure under concurrent and modular composition, and may be easily plugged into more complex protocols without having their security re-assessed with each new use. Recently, a universally composable framework has been proposed for Radio-Frequency Identification (RFID) authentication protocols, that simultaneously provides for availability, anonymity, and authenticity. In this paper we extend that framework to support key-compromise and forward-security issues. We also introduce new, provably secure, and highly practical protocols for anonymous authentication and key-exchange by RFID devices. The new protocols are lightweight, requiring only a pseudo-random bit generator. The new protocols satisfy forward-secure anonymity, authenticity, and availability requirements in the Universal Composability model. The proof exploits pseudo-randomness in the standard model.
2005
EPRINT
The anonymity provided by the threshold ring signature scheme proposed by Bresson et al (Crypto'02) is perfect. However, its complexity is prohibitively large even for relatively small sets of signers. We propose use of threshold schemes based on covering designs that are efficient for large groups of signers. The cost we pay is non-perfect anonymity.
2001
PKC
2000
PKC
1999
ASIACRYPT
1999
JOFC
1998
ASIACRYPT
1998
ASIACRYPT
1996
EUROCRYPT
1996
EUROCRYPT
1994
ASIACRYPT
1994
CRYPTO
1994
EUROCRYPT
1993
EUROCRYPT
1992
CRYPTO
1991
ASIACRYPT
1991
EUROCRYPT
1990
EUROCRYPT
1990
EUROCRYPT
1989
EUROCRYPT

Eurocrypt 2009
Eurocrypt 1999
Asiacrypt 1999
Eurocrypt 1997
Eurocrypt 1995
Auscrypt 1992