CWI Cryptology Group

Abstract: We provide formal definitions and efficient secure techniques for

• turning biometric information into keys usable for any cryptographic application, and
• reliably and securely authenticating biometric data.

Our techniques apply not just to biometric information, but to any keying material that, unlike traditional cryptographic keys, is (1) not reproducible precisely and (2) not distributed uniformly. We propose two new primitives. A *fuzzy extractor* extracts nearly uniform randomness R from its biometric input; the extraction is error-tolerant in the sense that R will be the same even if the input changes, as long as it remains reasonably close to the original. Thus, R can be used as a key in any cryptographic application. A *secure sketch* produces public information about its biometric input w that does not reveal w, and yet allows exact recovery of w given another value that is close to w. Thus, it can be used to reliably reproduce error-prone biometric inputs without incurring the security risk inherent in storing them.
In addition to formally introducing our new primitives, we provide nearly optimal constructions of both primitives for various measures of "closeness" of input data, such as Hamming distance, edit metric, permutation distance and set difference.
If time permits, some follow-up work will be mentioned. The talk will be introductory and self-contained. Original paper can be found at http://eprint.iacr.org/2003/235

Abstract: We present a generic SZK protocol for proving knowledge of a witness to generalized discrete-log relations. This gives a framework that allows such proofs of relations over mixed sets of groups of unknown (and known) orders. The tool allows automatic construction of SZK proofs from descriptions of groups, variable constraints and relations.
This primitive generalizes many previous instantiations that have appeared in the literature as ad-hoc SZK proofs (some of which had subtle mistakes in them (originally), and some are overly complex). The protocol is a powerful tool for building various cryptographic mechanisms. We demonstrate its power by presenting two new and efficient verifiable encryption protocols: one for full-domain hash RSA signatures, and one for the recent CL signatures.