A Variation on Secure Sketches Sample Clauses

A Variation on Secure Sketches. So far, we have presented the error-correcting information that Xxxxx sends to Bob in the first message as a secure sketch. Informally, secure sketches (defined in [DORS08], although implicitly used in many prior protocols, such as [BBR88, BBCS91, Mau93, Cr´e97, JW99, FJ01, MTZ03, CT04, JS06]) allow the recovery of w from a close string wj. For this work, we actually need a slight variant on secure sketches, one that provides some resilience even when the sketch is modified. The requires a different definition than the definition of [DORS08], though it turns out that known constructions need to be modified only slightly to satisfy it. Secure sketches, defined in [DORS08], provide two algorithms: “generate” (Gen) that takes an input w and produces a sketch P and “recover” (Rec) that outputs w from the sketch P and any wj sufficiently close to w. Their security guarantees that some entropy remains in w even given P . Secure sketches provide no guarantees when P has been tampered with, while we need to make sure that the output of Rec still has entropy. Thus, we need to add a weak form of robustness (i.e., resilience to active attack) to secure sketches. At the same time, we do not need a full recovery of the original w: we will be satisfied if both Gen and Rec produce some string R that preserves some of the entropy of w. In that way, our new primitive is like a fuzzy extractor, except we do not require that R be uniform, merely that it have entropy. In keeping with extractor literature terminology [CRVW02], we call the primitive a weakly robust fuzzy conductor because it conducts entropy from w to R and is robust against active attacks on P . Because we no longer recover the original w but rather reproduce the same R, we rename Rec into Rep. Let M be a metric space with distance function dis. Suppose (Gen, Rep) are two procedures, where Gen(w), for w ∈ M, outputs an extracted string R ∈ {0, 1}∗ and a helper string P ∈ {0, 1}∗ , and Rep(wj,Pj), for wj ∈ M,P j ∈ {0, 1}∗ , outputs Rj ∈ {0, 1}∗ . M