Paper 2018/701

Secure Sketch: How to Correct More Errors Without Entropy Loss

Lai Yen Lung

Abstract

Secure sketch produces public information of its input $w$ without revealing it, yet, allows the exact recovery of $w$ given another value $w'$ that is close to $w$. Therefore, it can be used to reliably reproduce any error-prone secret sources (i.e., biometric) stored in secret storage. However, some sources have lower entropy compared to the error itself, formally called ``more error than entropy", a standard secure sketch cannot show its security promise perfectly to these kinds of sources. Besides, when the same input is reused for multiple sketches generation, the complex error process of the input further results to security uncertainty, and offer no security guarantee. Fuller et al., (Asiacrypt 2016) defined the fuzzy min-entropy is necessary to show security for different kind of sources over different distributions. This paper focuses on secure sketch. We propose a new technique to generate re-usable secure sketch. We show security to low entropy sources and enable error correction up to Shannon bound. Our security defined information theoretically with Shannon entropy over a noise distribution adding to the input source. In particular, our new technique offers security guarantee for all family of input distributions with min-entropy at least single bit.

Note: revised correctness and efficiency of decoding algo.