AbstractFingerprint biometric authentication has particular advantages in a highly mobile environment. We investigate design issues involved in building authentication systems using minutia‐based fingerprint templates, where the template is protected during comparison as well as storage. Two popular bio‐cryptographic schemes based on the set difference metric, the Fuzzy Vault and PinSketch, are analysed with regard to theoretical bounds on the template sizes and decision thresholds. We define six different minutiae‐based templates and for each, quantisation parameters are determined that yield the best matching performance at a threshold where the probability of false match is zero. We then determine which, if any, of the representations satisfy the theoretical bounds proposed for each bio‐cryptographic construct. We implement a PinSketch‐based authentication system that uses a combination of a commonality and a set difference measure to securely compare two fingerprint templates, with negligible deterioration in accuracy. Our results indicate that to securely correct the degree of intra‐sample error observed in minutiae‐based templates, efficient commonality‐based error tolerant cryptographic constructs will be more suited than set difference based constructs. Copyright © 2010 John Wiley & Sons, Ltd.