Department of Computer Science and Technology

Technical reports

On using fuzzy data in security mechanisms

Feng Hao

April 2008, 69 pages

This technical report is based on a dissertation submitted April 2007 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Queens’ College.


Under the microscope, every physical object has unique features. It is impossible to clone an object, reproducing exactly the same physical traits. This unclonability principle has been applied in many security applications. For example, the science of biometrics is about measuring unique personal features. It can authenticate individuals with a high level of assurance. Similarly, a paper document can be identified by measuring its unique physical properties, such as randomly-interleaving fiber structure.

Unfortunately, when physical measurements are involved, errors arise inevitably and the obtained data are fuzzy by nature. This causes two main problems: 1) fuzzy data cannot be used as a cryptographic key, as cryptography demands the key be precise; 2) fuzzy data cannot be sorted easily, which prevents efficient information retrieval. In addition, biometric measurements create a strong binding between a person and his unique features, which may conflict with personal privacy. In this dissertation, we study these problems in detail and propose solutions.

First, we propose a scheme to derive error-free keys from fuzzy data, such as iris codes. There are two types of errors within iris codes: background-noise errors and burst errors. Accordingly, we devise a two-layer error correction technique, which first corrects the background-noise errors using a Hadamard code, then the burst errors using a Reed-Solomon code. Based on a database of 700 iris images, we demonstrate that an error-free key of 140 bits can be reliably reproduced from genuine iris codes with a 99.5% success rate. In addition, despite the irrevocability of the underlying biometric data, the keys produced using our technique can be easily revoked or updated.

Second, we address the search problem for a large fuzzy database that stores iris codes or data with a similar structure. Currently, the algorithm used in all public deployments of iris recognition is to search exhaustively through a database of iris codes, looking for a match that is close enough. We propose a much more efficient search algorithm: Beacon Guided Search (BGS). BGS works by indexing iris codes, adopting a “multiple colliding segments principle” along with an early termination strategy to reduce the search range dramatically. We evaluate this algorithm using 632,500 real-world iris codes, showing a substantial speed-up over exhaustive search with a negligible loss of precision. In addition, we demonstrate that our empirical findings match theoretical analysis.

Finally, we study the anonymous-veto problem, which is more commonly known as the Dining Cryptographers problem: how to perform a secure multiparty computation of the boolean-OR function, while preserving the privacy of each input bit. The solution to this problem has general applications in security going way beyond biometrics. Even though there have been several solutions presented over the past 20 years, we propose a new solution called: Anonymous Veto Network (AV-net). Compared with past work, the AV-net protocol provides the strongest protection of each delegate’s privacy against collusion; it requires only two rounds of broadcast, fewer than any other solutions; the computational load and bandwidth usage are the lowest among the available techniques; and our protocol does not require any private channels or third parties. Overall, it seems unlikely that, with the same underlying technology, there can be any other solutions significantly more efficient than ours.

Full text

PDF (1.6 MB)

BibTeX record

  author =	 {Hao, Feng},
  title = 	 {{On using fuzzy data in security mechanisms}},
  year = 	 2008,
  month = 	 apr,
  url = 	 {},
  institution =  {University of Cambridge, Computer Laboratory},
  number = 	 {UCAM-CL-TR-715}