Abstract Biometrics make human identification possible with a sample of a biometric trait and an associated database. Classical identification techniques lead to privacy concerns. This paper introduces a new method to identify someone using his biometrics in an encrypted way. Our construction combines Bloom Filters with Storage and Locality‐Sensitive Hashing. We apply this error‐tolerant scheme, in a Hamming space, to achieve biometric identification in an efficient way. This is the first non‐trivial identification scheme dealing with fuzziness and encrypted data. Copyright © 2010 John Wiley & Sons, Ltd.

Starting from a practical use of Reed-Solomon codes in a cryptographic scheme published in Indocrypt'09, this paper deals with the threshold of linear q-ary error-correcting codes. The security of this scheme is based on the intractability of polynomial reconstruction when there is too much noise in the vector. Our approach switches from this paradigm to an Information Theoretical point of view: is there a class of elements that are so far away from the code that the list size is always superpolynomial? Or, dually speaking, is Maximum-Likelihood decoding almost surely impossible? We relate this issue to the decoding threshold of a code, and show that when the minimal distance of the code is high enough, the threshold effect is very sharp. In a second part, we explicit lower-bounds on the threshold of Maximum-Distance Separable codes such as Reed-Solomon codes, and compute the threshold for the toy example that motivates this study.

Identification codes were introduced by Ahlswede and Dueck more than twenty years ago. There is today a lot of studies to identify objects such as contactless devices (for instance RFID tags) but, surprisingly, no one has considered the use of this kind of codes in the literature for that purpose until the recent work of Bringer et al. at Indocrypt '09. We here show how the security of these new identification protocols is related to some well-known problems in coding theory. We also extend the original proposal to a new problem.

In this paper, we describe a new primitive for error-tolerant searchable encryption and a security model for it. This generic scheme permits to make searches on encrypted data with only an approximation of some keyword. It enables to efficiently query secure databases in order to get the exact data with a close estimation of it. An application to biometric identification arises from this construction. This is the first construction both for error-tolerant searchable encryption and for a biometric identification protocol over encrypted personal data.

Fuzzy commitment schemes, introduced as a link between biometrics and cryptography, are a way to handle biometric data matching as an error-correction issue. We focus here on finding the best error-correcting code with respect to a given database of biometric data. We propose a method that models discrepancies between biometric measurements as an erasure and error channel, and we estimate its capacity. We then show that two-dimensional iterative min-sum decoding of properly chosen product codes almost reaches the capacity of this channel. This leads to practical fuzzy commitment schemes that are close to theoretical limits. We test our techniques on public iris and fingerprint databases and validate our findings.

Desktop grids use the idle cycles of desktop PC’s to provide huge computational power at low cost. However, because the underlying desktop computing resources are volatile, achieving performance guarantees such as task completion rate is difficult. We investigate the use of buffering to ensure task completion rates, which is essential for soft real-time applications. In particular, we develop a model of task completion rate as a function of buffer size. We instantiate this model using parameters derived from two enterprise desktop grid data sets, evaluate the model via trace-driven simulation, and show how this model can be used to ensure application task completion rates on enterprise desktop grid systems.