Paper 2018/701

Secure Sketch for All Noisy Sources

Yen-Lung Lai

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 a secret sources (i.e., biometrics) 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 kind of sources. This paper focuses on secure sketch. We propose a concrete construction for secure sketch. We show security to all noisy sources, including the trivial source with zero min-entropy. In addition, our construction comes with efficient recovery algorithm operates in polynomial time in the sketch size, which can tolerate high number of error rate arbitrary close to 1/2. Above result act in conjunction to our derivation on the solution to a well-known NP-complete coding problem, implying $P=NP$.

Note: .

Metadata
Available format(s)
-- withdrawn --
Category
Applications
Publication info
Preprint.
Keywords
Secure SketchError CorrectionCoding TheoryFuzzy Extractor
Contact author(s)
yenlung lai @ monash edu
History
2019-11-16: withdrawn
2018-08-01: received
See all versions
Short URL
https://ia.cr/2018/701
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.