Robust, short and sensitive authentication tags using secure sketch

Abstract

In order to apply cryptographic operations on noisy data, a recent approach employs some additional public data, known as secure sketch, to correct the noise so that consistent outcome can be obtained. This approach can be employed to extract authentication tags from noisy multimedia or biometric objects, by including the sketch in the tags. However, there are a few issues that need to be addressed. Firstly, those objects are typically represented in a continuous domain, and hence further quantization is required in order to obtain a short authentication tag. Secondly, for the purpose of authentication, forgery and preimage attacks are major concerns. However, such attacks are not considered in the notion of secure sketch. To handle the first issue, we give a construction using two levels of quantization. The second issue leads to the proposed additional requirement on sensitivity. We study how to choose the optimal parameters under the trade-off of robustness, size and sensitivity, and show that in many practical settings, the two-level quantization can be significantly more effective than a seemingly natural method of assigning one bit to each coefficient. Copyright 2006 ACM.