11institutetext: Monash University Malaysia,
Jalan Lagoon Selatan, Bandar Sunway, 47500 Subang Jaya, Selangor
11email<EMAIL_ADDRESS>
# Secure Sketch for All Sources (Noisy)

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^{\prime}$
that is close to $w$. Therefore, it can be used to reliably reproduce any
error-prone secret (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 this kind of sources. This paper focuses on secure sketch. We
propose an explicit construction for secure sketch. We show correctness and
security to all sources with meaningful min-entropy at least a single bit.
Besides, 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 for random error. The above result offers
polynomial time solution to two NP-complete coding problems, suggesting P=NP.

###### Keywords:

Secure Sketch Information Theory Coding Theory Fuzzy Extractor

##  1 Introduction

Traditional cryptography systems rely on uniformly distributed and recoverable
random strings for secret. For example, random passwords, tokens, and keys.
These secrets must present exactly on every query for a user to be
authenticated and get accessed into the system. Besides, it must also consist
of high enough entropy, thus making it very long and complicated, further
resulted in the difficulty in memorizing it. On the other hand, there existed
plentiful non-uniform strings to be utilized for secrets in practice. For
instance, biometrics (i.e., human iris, fingerprint) which can be used for
human recognition/identification purpose. Similarly, long passphrase (S. N.
Porter, 1982 [1]), answering several questions for secure access (Niklas
Frykholm et al., 2001 [2]) or personal entropy system (Ellison et al., 2000
[3]), and list of favorite movies (Juels and Sudan, 2006 [4]), all are non-
uniformly distributed random strings that can be utilized for secrets.

The availability of non-uniform information prompted the generation of uniform
random string from non-uniform materials. Started by Bennett et al., (1988)
[5], identified two major steps in deriving a uniform string from noisy non-
uniform sources. The first one is information-reconciliation, by tolerating
the errors in the sources without leaking any information. The second one
refers to the privacy amplification, which converts high entropy input into a
uniformly random input. The information-reconciliation process can be
classified into interactive (includes multi messages) and non-interactive
(only includes single message) versions. For non-interactive line of work, it
has been first defined by Dodis et al., (2004) [6] called the fuzzy extractor.
Likewise, the fuzzy extractor used two steps to accomplish the task, which is
the secure sketch (for error tolerance), and randomness extractor (for uniform
string generation). Secure sketch is demanding because it enables information-
reconciliation, e.g., exact recovery of a noisy secret while offering security
assurance to it. Moreover, a secure sketch can be easily extended to fuzzy
extractor for uniform string generation by using a randomness extractor. The
generated random string can be used in independent security system for access
control, identification, digital signature, etc.

This work focuses on secure sketch. We reviewed the limitations of current
secure sketch constructions in Section 1.1. To overcome such limitations, we
adopted the usage of resilience vector (RV) in Section 5 to support better
understanding of the structure of the sources. We proposed an explicit
construction with included RV for sketching and recovery (secure sketch) in
Section 6 and 7 respectively. Our proposed recovery mechanism has shown to be
efficient in polynomial in the sketch size and allows error tolerance of error
rate arbitrary close to $1/2$ (Section 9). In the end, in Section 11 we
formalize the security of our construction and show security to all sources
with meaningful entropy at least single bit. We also compared our proposal
with existing secure sketch construction, showing our construction enjoys the
better lower bound of min-entropy requirement for a standard secure sketch
(Section 12).

###  1.1 Issues in Existing Secure Sketch Construction

Various secure sketch constructions can be found in the literature. Some
notable constructions involved the code-offset construction proposed by Juels
and Wattenberg (1999) [7] that operates perfectly over hamming matric space.
Besides, Juels and Sudan (2006) [4] have also proposed another construction
for metric other than hamming called the fuzzy vault. Besides, Dodis et al.,
(2004) [6] have proposed an improved version of the fuzzy vault, and also the
Pin-sketch construction that relies upon generic syndrome encoding/decoding
with $t$-error correcting BCH code $\cdv$, which works well for non-fixed
length input over a universe $\mathcal{U}$.

However, the above mentioned secure sketch construction only works for limited
sources. Briefly, given a point (some value) $w$, the sketch would allow the
acceptance of its nearby point $w^{\prime}$ within distance $t$ for exact
recovery of $w$. Therefore, if an adversary can predict an accepting
$w^{\prime}$ with noticeable probability, the sketch must reveal $w$ to the
adversary with noticeable probability as well. The tension between security
and error tolerance capability is very strong. Precisely, the security is
measured in terms of the residual (min-) entropy, which is the starting
entropy of $w$ minus the entropy loss. Given some non-uniform sources with low
min-entropy, especially, when the sources consist of more error than entropy
itself, deducting the entropy loss from the sources’ min-entropy always
outputs a negative value, hence, show no security. Because of this, correcting
$t$ errors regardless of the structure of the input distribution would have to
assume sufficient high min-entropy to the input sources. To show meaningful
security for standard secure sketch, the min-entropy must at least half of the
input length itself [8], hence, limiting the availability of secure sketch
construction for low entropy sources.

Through exploitation of the struction of the input distributions, Fuller et
al., (2013) [9] have show that the crude entropy loss over ‘more error than
entropy’ sources can be avoided by the measurement of fuzzy min-entropy, which
defined as the min-entropy with maximized chances for a variable of $W$ within
distance $t$ of $w^{\prime}$:

$\displaystyle\text{H}_{t,\infty}^{\text{fuzz}}{(W)}\overset{\text{def}}{=}-\log\left(\max\limits_{w^{\prime}}\prob{W\in{B_{t}}(w^{\prime})}\right)$

where $B_{t}(w^{\prime})$ denoted a hamming ball of radius $t$ around
$w^{\prime}$. Conceivably, the fuzzy min-entropy is equivalent to the residual
entropy, which is at least the min-entropy $\minentropy{W}$ minus the loss
signified by the hamming ball $B_{t}(w^{\prime})$ of radius $t$, s.t.

$\displaystyle{\text{H}_{t,\infty}^{\text{fuzz}}{(W)}}\geq{\minentropy{W}-\log(B_{t}(w^{\prime}))}.$

${\text{H}_{t,\infty}^{\text{fuzz}}{(W)}}$ is useful for security measurement
instead of $\minentropy{W}$ especially when the residual entropy shows
negative value (i.e. more error than entropy). However, due to the fact that
${\text{H}_{t,\infty}^{\text{fuzz}}{(W)}}$ depends upon the error tolerance
distance $t$, and it is not necessary referring to the worst-case distribution
for $W$, therefore, traditional way of showing security with
${\text{H}_{t,\infty}^{\text{fuzz}}{(W)}}$ measurement have to deal with such
distribution uncertainty by considering a family of distributions
$\mathcal{W}$ for different variables i.e.,
$\\{{W_{1},W_{2},\ldots}\\}\in{\mathcal{W}}$ rather than single distribution.
Viewed this way, ${\text{H}_{t,\infty}^{\text{fuzz}}{(W)}}$ measurement is
only sufficient for computational secure sketch construction [9], [10], which
means that the security property of such construction only hold for
computationally bounded attacker (i.e., polynomial time bounded) accompanies
with strong assumption on the user has a precise knowledge over $\mathcal{W}$.
However, it is unrealistic to assume every sources distribution can be
modelled precisely, especially for high entropy sources like human biometric.

##  2 Overview Results

We highlighted our main four results as follow.

It was believed that the exploitation of the input structure is necessary [11]
to construct a secure sketch for all sources. Follow in this way, our works
adopted the principle of Locality Sensitive Hashing (LSH) to generate a
resilient vectors pair (trivially, a pair of longer strings with resilience
property) for sketching and recovery. Details discussion on the resilient
vector (RV) is covered in Section 5. The RV pair possessing resilience
property, i.e., distance preserving that is useful for the exploitation of the
input sources structure. Our first result is the metric of correlation measure
between the RV pair and their input pair (Eq. 1 and Eq. 2).

Since the RV is used for sketching, such correlation measurement implies the
entropy loss from the input. Therefore, the minimum entropy loss from the
sketch reduced to the maximum correlation measured in between the RV pair,
conditioned on their inputs. We formalize such minimum entropy loss based on
the maximum tolerance distance $t_{\max}$ over any random input distribution,
which implies maximum probability in looking for a nearby (similar) point
within distance $t_{\max}$ (Corollary 1). This result is later being used for
our reduction from fuzzy minimum entropy to Shannon entropy, to show necessary
and sufficient condition for a system’s security (see Section 12.2).

Thirdly, we show that the minimum entropy loss of our construction could be at
least three bits with BCH error correction codes. A Tighter result is also
obtained by considering random error correction codes are used instead of BCH
codes (Proposition 3), revealing the minimum entropy loss could be at least
one bits (Eq. 15). This pushed the lower bound of minimum entropy requirement
of our secure sketch construction to accept any sources of entropy at least
one bit, which is much lower compared to existing constructions. Nonetheless,
above result is computational. It later is being used to derive the well-known
information-theoretical bound (Shannon bound) and shown to be coincided with
another computational bound commonly studied in coding theory research
(Gilbert-Varshamov bound) (see Section 12.1), lead us to the claim of
computational secure sketch implies information-theoretical sketch.

The last result we would like to highlight is the efficiency of the recovery
algorithm in our construction. Without the consideration of the computational
power in running the recovery algorithm, the recovery of the input from the
sketch can be done with high probability (close to one) given the sketch size
is large enough (Proposition 1). On the other hand, considering the
computational power in running the recovery algorithm, we noticed that higher
computational power, i.e., exponential time in the input (Eq. 9) is needed in
order to tolerate more errors. Nonetheless, such exponential computation time
can be formalized to polynomial time in the sketch size to ensure efficient
recovery while allowing more errors to be tolerated (Proposition 2). This
result shows deep connection in between a difficult decoding problem over
smaller metric space (of size $k^{*}$) could be reduced down to a more
manageable problem over larger metric space $n>k^{*}$, suggesting P=NP.

##  3 Preliminaries

There are some preliminaries to introduce the background of a standard secure
sketch, entropy, and error correction code.

Min-Entropy: For security, one is always interested in the probability for an
adversary to predict a random value, i.e., guessing a secret. For a random
variable $W$, $\max\limits_{w}\prob{W=w}$ is the adversary’s best strategy to
guess the most likely value, also known as the predictability of $W$. The min-
entropy thus defined as

$\displaystyle\minentropy{W}=-\log(\max\limits_{w}\prob{W=w})$

min-entropy also viewed as worst-case entropy.

Conditioned min-entropy: Given pair of random variable $W$, and $W^{\prime}$
(possible correlated), given an adversary find out the value $w^{\prime}$ of
$W^{\prime}$, the predictability of $W$ is now become
$\max\limits_{w}\condprob{W=w}{W^{\prime}=w^{\prime}}$. The conditioned min-
entropy of $W$ given $W^{\prime}$ is defined as

$\displaystyle\condminentropy{W}{W^{\prime}}=-\log\left(\expsub{w^{\prime}\leftarrow{W^{\prime}}}{\max\limits_{w}\condprob{W=w}{W^{\prime}=w^{\prime}}}$

Error correction code: [12] Let $q\geq{2}$ be an integer, let
$[q]=\\{{1,\ldots,q}\\}$, we called an $[n,k,d]_{q}$-ary code $\cdv$ consist
of following properties:

  * •

$\cdv$ is a subset of $[q]^{n}$, where $n$ is an integer referring to the
blocklength of $\cdv$.

  * •

The dimension of code $\cdv$ can be represented as $\abs{\cdv}=[q]^{k}=V$

  * •

The rate of code $\cdv$ to be the normalized quantity $\frac{k}{n}$

  * •

The min-distance between different codewords defined as
$\min\limits_{c,c^{*}\in{\cdv}}{\mathsf{dis}(c,c^{*})}$

It is convenient to view code $\cdv$ as a function
$\cdv:[q]^{k}\rightarrow{{[q]}^{n}}$. Viewed this way, the elements of $V$ can
be considered as a message $v\in{V}$ and the process to generate its
associated codeword $\cdv{(v)}=c$ is called encoding. Viewed this way,
encoding a message $v$ of size $k$, always adding redundancy to produce
codeword $c\in{[q]^{n}}$ of longer size $n$. Nevertheless, for any codeword
$c$ with at most $t=\lfloor{\frac{d-1}{2}}\rfloor$ symbols are being modified
to form $c^{\prime}$, it is possible to uniquely recover $c$ from $c^{\prime}$
by using certain function $\mathsf{f}$ s.t. $\mathsf{f}(c^{\prime})=c$. The
procedure to find the unique $c\in{\cdv}$ that satisfied
$\mathsf{dis}(c,c^{\prime})\leq{t}$ by using $\mathsf{f}$ is called as
decoding. A code $\cdv$ is said to be efficient if there exists a polynomial
time algorithm for encoding and decoding

Linear error correction code [12]: Linear error correction code is a linear
subspace of $\FF_{q}^{n}$. A $q$-ary linear code of blocklength $n$, dimension
$k$ and minimum distance $d$ is represented as $[{n,k,d}]_{q}$ code $\cdv$.
For a linear code, a string with all zeros $0^{n}$ is always a codeword. It
can be specified into one of two equivalent ways with a generator matrix
$G\in\FF_{q}^{n\times{k}}$ or parity check matrix
$H\in\FF_{q}^{(n-k)\times{n}}$:

  * •

a $[{n,k,d}]_{q}$ linear code $\cdv$ can be specified as the set
$\\{{Gv:v\in{\FF_{q}^{k}}}\\}$ for an $n\times{k}$ metric which known as the
generator matrix of $\cdv$.

  * •

a $[{n,k,d}]_{q}$ linear code $\cdv$ can also be specified as the subspace
$\\{{x:x\in{\FF_{q}^{n}}}$ and ${Hx=0^{n}}\\}$ for an $(n-k)\times{n}$ metric
which known as the parity check matrix of $\cdv$.

For any linear code, the linear combination of any codewords is also
considered as a codeword over $\FF_{q}^{n}$. Often, the encoding of any
message $v\in{\FF_{q}^{k}}$ can be done with $O(nk)$ operations (by
multiplying it with the generator matrix, i.e., $Gv$. The distance between two
linear codewords refers to the number of disagree elements between them, also
known as the hamming distance.

Sometime, we refer $[n,k,d]$ code $\cdv$ as $[n,k,t]$ code $\cdv$ if the error
tolerance distance $t$ is of interested rather than its minimum distance $d$.

Secure sketch: [6] An $(\mdv,m,\tilde{m},t)$-secure sketch is a pair of
randomized procedures “sketch” ($\mathsf{SS}$) and “Recover” ($\mathsf{Rec}$),
with the following properties:

  * $\mathsf{SS}$: takes input $w\in\mdv$ returns a secure sketch (e.g., helper string) $ss\in\bin^{*}$.

  * $\mathsf{Rec}$: takes an element $w^{\prime}\in\mdv$ and $ss$. If $\mathsf{dis}(w,w^{\prime})\leq{t}$ for some tolerance threshold $t$, then $\mathsf{Rec}(w^{\prime},ss)=w$ with probability $1-\beta$, where $\beta$ is some negligible quantity. If $\mathsf{dis}(w,w^{\prime})>{t}$, then no guarantee is provided about the output of $\mathsf{Rec}$.

The security property of secure sketch guarantees that for any distribution
$W$ over $\mdv$ with min-entropy $m$, the values of $W$ can be recovered by
the adversary who observes $ss$ with probability no greater than
$2^{-\tilde{m}}$. That is the residual entropy
$\condminentropy{W}{W^{\prime}}\geq\tilde{m}$.

##  4 Main Idea

We here highlight some common notation to be used in this work, and a brief
overview of our construction, focus on binary metric space.

###  4.1 Notations

Let $\mdv_{1}=\bin^{k^{*}}$, and $\mdv_{2}=\bin^{n}$ denote two different
sizes of metric spaces where $n>k^{*}$. The distance between different binary
string $w$ and $w^{\prime}$ denoted as $\mathsf{dis}(w,w^{\prime})$ is the
binary hamming distance (e.g., the number of disagree elements), i.e.,
${\mathsf{dis}}(w,w^{\prime})=\norm{w\xor{w^{\prime}}}$ where $\norm{.}$ is
the hamming weight that count the number of non-zero elements, and $\xor$ is
the addition modulo two operation (XOR). Besides, the error rate in between
the input $w$ $w^{\prime}\in{\mdv_{1}}$ is denoted as
$\norm{w\xor{w^{\prime}}}(k^{*})^{-1}$ which is simply their normalized
hamming distance.

Our construction used two linear codes. We called one of these as ‘inner’ code
$\cdv_{in}$, and another one called ‘outer’ code $\cdv_{out}$. Although not
necessary, it is convenient to refer both chosen linear codes to be BCH codes
[13] with parameter $[{n^{*},k^{*},t^{*}}]_{2}$ for $\cdv_{in}$ and
$[{n,k,t}]_{2}$ for $\cdv_{out}$, where $k^{*}\leq{n^{*}}<{k}\leq{n}$ holds.
This is because the family of BCH codes has been well-studied and formed a
large class of error correction code perfectly suit for binary input string.
Moreover, it accompanies with efficient decoding algorithm $\mathsf{f}$ namely
the syndrome decoding operates in $O(n^{t})$[13]. The tolerance rate of code
$\cdv_{in}$ and $\cdv_{out}$ are denoted as $\xi^{*}={t^{*}}/{n^{*}}$ and
$\xi={t}/{n}$ respectively.

###  4.2 Overview Construction

We here provide a brief overview of our sketching and recovery proposal for
one to conceal a random string (encoded codeword) $c^{*}\in\bin^{n^{*}}$ while
allows exact recovery of $c^{*}$ by using another noisy string
$w^{\prime}_{e^{\prime}}\in{\bin^{k^{*}}}$ that is close to the noisy string
$w_{e}$ used on sketching.

Sketching: The proposed sketching procedure can be viewed as a two steps
encoding process. First, one encodes $w$ using the ‘inner’ code $\cdv_{in}$ to
output a codeword $c^{*}$. Then, $c^{*}$ is randomly distorted by using some
noisy string $w_{e}$, where the corrupted codeword, viewed as a syndrome
vector $v_{syn}\in{\\{{0,1}\\}^{n^{*}}}$. The syndrome vector is then being
padded with zeros to form a longer bit string and encoded by the ‘outer’ code
$\cdv_{out}$ to output the final codeword $c\in{\cdv_{out}}$. The final sketch
is generated by concealing $c$ with an offset $\delta$ that is characterized
by a pair of resilient vectors $\phi,\phi^{\prime}\in{\bin^{n}}$. In different
to existing construction, our sketching proposal consists of additional
randomization with random noisy string $w_{e}$ used to distort the original
codeword $c^{*}$. Then, the distorted codeword is being encoded into larger
codeword $c$ and distorted again using RV to generate the final sketch. The
noisy string introduced during sketching phase facilitates our studies of any
random events potentially corrupting the codewords follows the random
distribution of the noisy string $w_{e}$.

Recovery: For recovery, we are more interested in the event when the person in
recovering $w$ does not know the distribution of the introduced noisy string
$w_{e}$ during sketching phase. Therefore our recovery procedure is defined to
be adversarial. Nevertheless, he/she can use some random noisy string
$w^{\prime}_{e^{\prime}}$ and its corresponding RV, $\phi^{\prime}$ to try to
decode the corrupted codeword from the sketch. The zero-padded in front of the
syndrome vector acts as an indicator to notify him/her the successfulness of
the decoding results (i.e., first few bits are all zeros). More formally, our
recovery procedure requires one to determine the distribution of noisy string
$w_{e}$ introduced during sketching, and look for the similar noisy string
$w^{\prime}_{e^{\prime}}$ (that viewed as the pre-image of $w_{e}$) i.e.,
$\norm{w^{\prime}_{e^{\prime}}\xor{w_{e}}}\leq{t^{\prime}}$ to achieve error
tolerance hence recover $w$ successfully.

##  5 Resilient Vector: Properties and Generation

Since RV is a core element of our construction, we here provide details
discussion on its properties and how it can be generated. The usage of RV into
cryptography is first introduced by Ronald L. Rivest [14] in 2016. Its main
concept is derived from Locality Sensitive Hashing (LSH) defined as below.

Locality Sensitive Hashing [15] Given that $P_{2}>P_{1}$, while
$w,w^{\prime}\in{\mdv}$, and $\mathcal{H}={h_{i}:\mdv\rightarrow}U$, where $U$
refers to the output metric space (after hashing), which comes along with a
similarity function $S$, where $i$ is the number of hash functions $h_{i}$. A
locality sensitive hashing can be viewed as a probability distribution over a
family $\mathcal{H}$ of hash functions follows
$P_{h\in{\mathcal{H}}}[{h(w)=h(w^{\prime})}]=S(w,w^{\prime})$. In particular,
the similarity function $S$ described the hashed collision probability in
between $w$ and $w^{\prime}$.

$\displaystyle P_{h\in{\mathcal{H}}}(h_{i}(w)=h_{i}(w^{\prime}))\leq{P_{1}},\
\ {\text{if}}\ S(w,w^{\prime})<R_{1}$ $\displaystyle
P_{h\in{\mathcal{H}}}(h_{i}(w)=h_{i}(w^{\prime}))\geq{P_{2}},\ \ {\text{if}}\
S(w,w^{\prime})>R_{2}$

LSH transforms input $w$ and $w^{\prime}$ to its output metric space $U$ with
property that ensuring similarity inputs render higher probability of
collision over $U$, and vice versa.

For RV generation, we only focus on a particular LSH family called hamming-
hash [16]. The hamming hash is considered as one of the easiest ways to
construct an LSH family by bit sampling technique.

Hamming hash strategy: Let $[{k^{*}}]=\\{{1,\ldots,{k^{*}}}\\}$. For Alice
with $w\in\bin^{k^{*}}$ and Bob with $w^{\prime}\in\bin^{k^{*}}$. Alice and
Bob agreed on this strategy as follow:

  1. 1.

They are told to each other a common random integer $N\in{[{k^{*}}]}$.

  2. 2.

They separately output ‘0’ or ‘1’ depend upon their private string $w$ and
$w^{\prime}$, i.e., Alice output ‘1’ if the $N$-th bit of $w$ is ‘1’, else
output ‘0’.

  3. 3.

They win if they got the same output, i.e., $w(N)=w^{\prime}(N)$.

Based on above strategy, we are interested in the probability for Alice and
Bob outputting the same value. This probability can be described by a
similarity function $S(w,w^{\prime})=P$ where $P\in{[{0,1}]}$.

###### Theorem 5.1

Hamming hash strategy is a LSH with similarity function
$S(w,w^{\prime})=1-{\norm{w\xor{w^{\prime}}}}({k^{*}})^{-1}$

The hamming hash strategy can also be operated in between Alice and Bob in an
non-interactive way. To do so, Alice and Bob simply repeat Step 1 and Step 2
for $n$ number of times with a set of pre-shared integers
$N=[N(1),N(2),\ldots,N(n)]\in{[k^{*}]^{n}}$ chosen randomly and uniformly over
${[k^{*}]^{n}}$. In the end, they can output a $n$ bits string $\phi$, and
$\phi^{\prime}$ respectively over ${\bin^{n}}$, which we have earlier named as
resilient vectors. We denote such non-interactive hamming-hash algorithm as
$\mathsf{\Omega}:\mdv_{1}\times{[{k^{*}}]^{n}}\rightarrow{\mdv_{2}}$, which
serves to sample the input binary string of size $k^{*}$ into a longer binary
string a.k.a resilient vector of size $n>{k^{*}}$.

Given input $w\in\bin^{k^{*}}$, and $N\in{[k^{*}]^{n}}$, algorithm
$\mathsf{\Omega}:\mdv_{1}\times{[{k^{*}}]^{n}}\rightarrow{\mdv_{2}}$ can be
described as follow:

[linenumbering]$\mathsf{\Omega}(w,N)$ϕ←∅ i=1,…,n x=w(N(i))$x$ is the $N(i)$-th
bits of $w$ ϕ=ϕx ϕ

###### Theorem 5.2

Suppose two resilient vectors $\phi,\phi^{\prime}\in\bin^{n}$ are generated
from $w,w^{\prime}\in{\bin^{k^{*}}}$ respectively using hamming hash algorithm
$\mathsf{\Omega}$ with a random integer string $N\in{[{{k^{*}}}]}^{n}$, then
$\expect{\norm{\phi\xor\phi^{\prime}}}=n\norm{w\xor{w^{\prime}}}({k^{*}})^{-1}$.

###  5.1 Correlation Measure in RVs

Let $\Phi$ and $\Phi^{\prime}$ be two random variables over $\bin^{n}$, and
$W$ and $W^{\prime}$ be two random variables over $\bin^{k^{*}}$. Given a
resilience vector $\phi\in{\Phi}$ generated from $w\in{W}$ with random string
$N$, it follows $\Phi$ must correlate with ${W}$ where the probability to look
for any random variable $\Phi\in{B_{t}(\phi^{\prime})}$ (also means similar
resilience vector s.t. $\norm{\phi\xor{\phi^{\prime}}}\leq{t}$) varies
conditioned on either ${W\not\in{B_{t^{\prime}}(w^{\prime})}}$ or
${W\in{B_{t^{\prime}}(w^{\prime})}}$. Note that
${W\in{B_{t^{\prime}}(w^{\prime})}}$ implies the inputs $w\in{W}$ and
$w^{\prime}\in{W^{\prime}}$ must similar within distance $t^{\prime}$ (e.g.
$\norm{w\xor{w^{\prime}}}\leq{t^{\prime}}$), while
${W\in{B_{t^{\prime}}(w^{\prime})}}$ means
$\norm{w\xor{w^{\prime}}}>{t^{\prime}}$. Such correlation can be measured by
using the conditional probability described as
${\condprob{\Phi\in{B_{t}(\phi^{\prime})}}{W\not\in{B_{t^{\prime}}(w^{\prime})}}}$
or
${\condprob{\Phi\not\in{B_{t}(\phi^{\prime})}}{W\in{B_{t^{\prime}}(w^{\prime})}}}$
respectively. In particular, we are more interested in the maximum
correlation, which can be expressed by the conditioned maximum probability in
looking for $\Phi\in{B_{t_{\max}}(\phi^{\prime})}$ given
${W\not\in{B_{t^{\prime}_{(+)}}(w^{\prime})}}$ for some maximum distances
$t_{\max}\geq{t}$ (over $\bin^{n}$) and $t^{\prime}_{(+)}>t^{\prime}$ (over
$\bin^{k^{*}}$) defined as:

$\displaystyle{\max\limits_{t=t_{\max}}{\condprob{\Phi\not\in{B_{t}(\phi^{\prime})}}{{W\not\in{B_{t^{\prime}_{(+)}}(w^{\prime})}}}}}.$
$\displaystyle\geq\expsub{w^{\prime}\leftarrow{W^{\prime}}}{\max\limits_{\phi^{\prime}}\condprob{\Phi\in{B_{t}(\phi^{\prime})}}{W\not\in{B_{t^{\prime}}(w^{\prime})}}}.$
(1)

On the other hand, the conditioned maximum probability in looking for
$\Phi\not\in{B_{t}(\phi^{\prime})}$ given ${W\in{B_{t^{\prime}}(w^{\prime})}}$
for some minimum distances $t_{\min}\leq{t}$ (over $\bin^{n}$) and
$t^{\prime}_{(-)}<t^{\prime}$ (over $\bin^{k^{*}}$) is defined as:

$\displaystyle{\max\limits_{t=t_{\min}}{\condprob{\Phi\not\in{B_{t}(\phi^{\prime})}}{{W\not\in{B_{t^{\prime}_{(-)}}(w^{\prime})}}}}}$
$\displaystyle\geq\expsub{w^{\prime}\leftarrow{W^{\prime}}}{\max\limits_{\phi^{\prime}}\condprob{\Phi\in{B_{t}(\phi^{\prime})}}{W\not\in{B_{t^{\prime}}(w^{\prime})}}}$
(2)

##  6 Sketching

We denote the sketching algorithm that employs the hamming-hash algorithm,
$\mathsf{\Omega}$, an $[{n^{*},{k^{*}},t^{*}}]_{2}$ ‘inner’ code $\cdv_{in}$
and an $[{n,k,t}]_{2}$ ‘outer’ code $\cdv_{out}$ as
$\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}}$. The sketching algorithm
$\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}}$ with random inputs $w,N$,
and $\epsilon_{ss}$ is described as follow:

[linenumbering]$\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}}(w,N,\epsilon_{ss})$E_ss
{0,1}^k^*initiate a random distribution $\mathcal{E}_{ss}$ with error
parameter $\epsilon_{ss}$ e E_sssample $e$ uniformly at random from
$\mathcal{E}_{ss}$, where $\norm{e}={{\floor{{{k^{*}}}\epsilon_{ss}}}}$
c^*=_in(w); encode $w$ w_e=we; v_syn=c^*(0^n^*-k^*w_e) v^*=0^k-n^*v_syn;
c=_out(v^*); encode $v^{*}$ ϕ←Ω(w_e,N) ss=cϕ; ss

Our sketching procedure consists of mainly two encoding stages. Given an
random input string $w\in{\bin^{k^{*}}}$, the first encoding stage used
$\cdv_{in}$ to encode a random string $w$ to generate a codeword
$c^{*}\in{\bin^{n^{*}}}$. Viewed this way, $c^{*}$ can be any random codeword
over $\cdv_{in}$, including the trivial codeword of all zeros i.e.
$c^{*}=0^{n^{*}}$. Then, we generate a noisy string $w_{e}$ and pad it with
zeros in front to generate a longer bit string, which can be viewed as the
syndrome vector denoted as
$v_{syn}={c^{*}}\xor{{(0^{n^{*}-k^{*}}\concat{w_{e}})}}$. The syndrome vector
itself is also a codeword $v_{syn}\in\cdv_{in}$. Clearly, $v_{syn}$ conceals
$c^{*}$ by using $w_{e}$, where the vector ${(0^{n^{*}-k^{*}}\concat{w_{e}})}$
acts as some random errors used to distort the original codeword $c^{*}$, lead
to at most $\norm{{(0^{n^{*}-k^{*}}\concat{w_{e}})}}=\norm{w_{e}}$ bits
flipped in $c^{*}$. Then, the second encoding stage used $\cdv_{out}$ to
encode $v^{*}=0^{k-n^{*}}\concat{v_{syn}}$ to generate the final code word
$c$. The $0^{k-n^{*}}$ zeros in front is used to notify the recovery algorithm
if the decoding is success. The final sketch is formed by hiding $c$ with RV
generated from $w_{e}$.

For the realization of the noisy string $w_{e}$, we parse additional error to
the original input $w$ using a random error vector $e\in\mathcal{E}_{ss}$
sampled uniformly at random follows some random distribution
$\mathcal{E}_{ss}$. Such error distribution is parametrized by an error
parameter $\epsilon_{ss}$ chosen within range
$\epsilon_{ss}\in{[(2k^{*})^{-1},1/4]}$. To be specific, all error vector
$e\in{{\mathcal{E}_{ss}}}$ is of weight
$\norm{e}={{\floor{{{k^{*}}}\epsilon_{ss}}}}$, and the generation of the noisy
string follows $w_{e}=w\xor{e}$. The error vector $e$ is leaving in clear
after it is parsed into the input $w$ to form $w_{e}$.

All steps on
$\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}}(w,N,\epsilon_{ss})$ can be
done in $O({n^{3}})$, and the size of $ss$ is now depend upon the blocklength
$n$ of the chosen ‘outer’ code $\cdv_{out}$.

Remark here the distribution for $w$ and $e$ are considered to be random in
our case. The random string $N\in{[k^{*}]^{n}}$ is chosen in random and
uniform over $[k^{*}]^{n}$. By LSH definition and Theorem 5.2, the generated
RV is i.i.d, where every single bit of the RV follows the distribution of the
noisy string $w_{e}$. Since the sketch $ss$ is generated by concealing $c$
using RV $\phi$, its distribution shall follows the generated RV, depends upon
the input noisy string $w_{e}\in\bin^{k^{*}}$. In such a case, the same random
string $N$ can be made public and reused, where the distribution of the
generated sketch is only input dependence, i.e., depends upon the distribution
of the noisy string $w_{e}$.

##  7 Recovery

We denote the recover algorithm that employed the hamming-hash algorithm,
$\mathsf{\Omega}$, an $[{n^{*},{k^{*}},t^{*}}]_{2}$ ‘inner’ code $\cdv_{in}$
and an $[{n,k,t}]_{2}$ ‘outer’ code $\cdv_{out}$ as
$\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}$. The recover
algorithm $\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}$
with inputs $ss$, $w^{\prime}$, $N$, $\epsilon_{rec}$ to recover $w$ is
described as follow:

[linenumbering]$\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}(ss,w^{\prime},N,\epsilon_{rec})$E_rec^k^*
initiate $\mathcal{E}_{rec}$ with error parameter $\epsilon_{rec}$
i=1,…,—supp(E_rec)— e’_iE_recsample $e^{\prime}_{i}$ differently at random,
where $\norm{e^{\prime}_{i}}={{{\floor{{k^{*}}\epsilon_{rec}}}}}$
w’_e’_i=w’e’_i ϕ’_i←Ω(w’_e’_i,N) c’_i=ssϕ’_i also
$ss\xor{\phi^{\prime}_{i}}=c\xor{(\phi\xor{\phi^{\prime}_{i}})}$
c←f(c’_i)first decoding set v^*=_out^-1(c) v^*[1],…,v^*[k-n^*]=0^k-n^* first
$k-n^{*}$ bits of $v^{*}$ are zeros set v’_syn  as the last $n^{*}$ elements
of $v^{\prime*}$ c’^*=v’_syn(0^n^*-k^*w’_e’_i) c^*←f(c’^*)second decoding
w=_in^-1(c^*) break

Our recovery process is defined to be adversarial s.t. the person in
recovering $w$ does not know the input error distribution $\mathcal{E}_{ss}$
introduced on sketching. Hence, different notation is used to denote the error
distribution used in the recovery phase, e.g., $\mathcal{E}_{ss}$ for
sketching, and $\mathcal{E}_{rec}$ for recovery. In particular, the non-
trivial case (noisy) where the input $w$ is distorted by
$e\in{\mathcal{E}_{ss}}$ is of our interest. Therefore it is good to set
$\epsilon_{rec}\geq{\epsilon_{ss}}\geq(2k^{*})^{-1}$ for the mean of
determining the error vector $e\in{\mathcal{E}_{ss}}$ (introduced during
sketching) for recovery of $w$.

The recovery algorithm consists of mainly two decoding stages. The first
decoding stage is designed to be an iterative decoding uses $\cdv_{out}$ and
$\mathsf{f}$. It can be conveniently viewed as a brute-force decoding
procedure of ${{|\mathsf{supp}(\mathcal{E}_{rec})|}}$ trials with recovery
error distribution ${\mathcal{E}_{rec}}$ (parametrized by $\epsilon_{rec}$),
means to recover the syndrome vector $v_{syn}$. For each iteration in the
first decoding stage, if the first $k-n^{*}$ bits of $v^{*}$ are all zeros,
the decoding is viewed as success and thus the recovery algorithm could
proceed to the second decoding stage to recover $c^{*}$ and so $w$ from
$v_{syn}$ using $\cdv_{in}$.

The second decoding stage uses $\cdv_{in}$ and $\mathsf{f}$ to decode the
corrupted syndrome vector (viewed as the corrupted codeword $c^{\prime*}$) to
recover $c^{*}$. The decoding itself must success if
$\norm{w_{e}\xor{w^{\prime}_{e^{\prime}_{i}}}}\leq{t^{*}}$, thus $w$ can be
recovered from $c^{*}$.

##  8 Distribution Hiding with Random Error Parsing

In this section, we provide a discussion over the action of random error
parsing is necessary to show security for a given source. In fact, the random
error parsing process can also be interpreted as any randomization and
perturbation process (i.e., hashing or encryption) applied to the input
$w\in{\mdv_{1}}$ with some random error distribution $\mathcal{E}_{ss}$.
Viewed this way, Step 4 of
$\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}}$ can be succinctly
replaced by some random function $f:\mdv_{1}\times\mdv_{1}\rightarrow\mdv_{1}$
with input $w$ and $e$, to output $w_{e}$ as a random noisy string. Same
function $f$ also applied on Step 4 of
$\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}$ with input
$w^{\prime}$ and different $e^{\prime}_{i}$ to output $w_{e^{\prime}_{i}}$.
Nonetheless, since our focus only on error tolerance, we would stick to the
simplest case where the random error parsing process is simply an addition
modulo two (XOR) process.

We start from the sketching algorithm, which accepts any random input $w$ in
some random distribution $W$ over $\mdv_{1}$. Such input would yield a random
RV $\phi\in{\Phi}$ in random distribution $\Phi$ over $\mdv_{2}$ via RV
generation using some public known random string $N$. Tolerating $t$ errors
using an $[n,k,t]$ error correction code eventually reveal $W$. This is
because the encoding process must ensure all random variable
$W\in{B_{t}(w^{\prime})}$ can be tolerated using decoding function
$\mathsf{f}$, therefore, for any input string $w\in{W}$, encoding $w$ must
store additional information that is manifested by the neighbourhood of $w$
within distance $t$. Doing so inevitably introduced $t$ information loss. When
$t$ is larger than the entropy of the source, the source is said to loss all
entropy and no security to show.

To resolve the above issue, a straightforward way is to hide $W$ before adding
redundancy to it. This can be done by parsing an error randomly and uniformly
chosen from a list
$\\{{e_{1},\ldots,e_{|\mathsf{supp}(\mathcal{E}_{ss})|}}\\}\in{\mathcal{E}_{ss}}$
into the input string $w$ during the sketching phase. Doing so means the
generated noisy string $w_{e}$ is now randomly and uniformly distributed over
a family of distributions $\mathcal{W}$, i.e.,
$w_{e}\in{\mathcal{W}}=\\{{W_{1},\ldots,W_{{|\mathsf{supp}(\mathcal{E}_{ss})|}}}\\}$.
Because the distribution of RV is input dependence, it follows the generated
RV
$\phi\in{\Psi}=\\{{\Phi_{1},\ldots,\Phi_{{|\mathsf{supp}(\mathcal{E}_{ss})|}}}\\}$
is also randomly and uniformly distributed in a family of i.i.d distribution
$\Psi$. Remark here when
$|\Psi|=|\mathcal{W}|=|\mathsf{supp}(\mathcal{E}_{ss})|=1$, it corresponds to
the trivial case when the error vector $e\in{\mathcal{E}}_{ss}$ is all zeros
(noiseless). This also means that the original distribution of the variable
$W$ is now hidden over $\mathcal{W}$ randomly and uniformly. Therefore, for
the non-trivial case, it is more appropriate to consider the family of
distributions in $\mathcal{W}$ and $\Psi$ rather than single distribution in
deriving the security of the sketch. Compared to the generic BCH encoding
procedure, our proposed sketching algorithm can be viewed as a more general
encoding procedure by considering a more general case where the error
parameter $\epsilon_{ss}>{0}$ (or $\norm{e}\geq{0}$) is introduced during the
sketching phase.

Because the sketch is generated by concealing the final codeword $c$ with an
RV $\phi$. It follows that the worst-case security of the sketch is manifested
by the maximum error tolerance distance over $\Psi$, where the probability to
find a random variable $\Phi\in{B_{t_{\max}}(\phi^{\prime})}$, i.e., similar
RV (given $\phi^{\prime}$) over $\Psi$ is maximum. In particular, we let
$\xi=t/n={\lVert{w_{e}\xor{w^{\prime}}}\rVert}({k^{*}})^{-1}$. For
$\xi\geq{\epsilon_{ss}}$, such maximum distance (over $\bin^{n}$) can be
described as

$t_{\max}=n(\xi-\epsilon_{ss})\geq{t}\geq{0}.$

Recall the generated RV is input dependence (depends upon the noisy string
$w_{e}$), thus, $\Phi$ is conditioned on the original distribution of the
variable $W$. To look for $t_{\max}$, we first define a maximum tolerance
distance (over $\bin^{k^{*}}$) as

$t^{\prime}_{(+)}={(\xi+\epsilon_{ss}){k^{*}}},$

for all distribution of $W\in{\mathcal{W}}$ after random error parsing, which
is distributed (hidden) randomly and uniformly over $\mathcal{W}$. Remark here
$t$ is now denoted to be input dependence. The original distribution of the
variable $W$ may be different for different input string $w\in{W}$ before
random error parsing. This means the distance
${\lVert{w_{e}\xor{w^{\prime}}}\rVert}({k^{*}})^{-1}$ shall be different and
so for the value of $t$ (or $\xi$) as well. Nevertheless, for
$\epsilon_{ss}\geq{(2k^{*})^{-1}}>0$, the defined maximum distance
$t^{\prime}_{(+)}$ would imply error rate of $\xi+\epsilon_{ss}$, which is
always larger than $\xi$. Therefore, $t^{\prime}_{(+)}$ is always maximum for
any original distribution of the variable $W$, hold for all input string
$w\in{W}$.

The Corollary below characterized the worst-case security of RVs. Such
security is measured in terms of conditioned maximum probability in getting
similar RV within a maximum tolerance distance $t_{\max}\geq{t}\geq{0}$ over
$\Psi$ given a noisy string $w^{\prime}\in{W^{\prime}}$ over some random
distribution $W^{\prime}\in{\mdv_{1}}$.

###### Corollary 1

Given any random variable $W\in{\mathcal{W}}$, and a random string
$w^{\prime}\in{W^{\prime}}$. For all RV over a family of distributions
${\Psi}$, the conditioned maximum probability to look for any similar RV
$\phi$ in any random distribution $\Phi\in{B_{t_{\max}}(\phi^{\prime})}$ over
$\Psi$ (i.e. $\norm{\phi\xor{\phi^{\prime}}}=\norm{\delta}\leq{t_{\max}}$ for
all $\phi\in{\Phi}$) when ${W}\not\in{B_{t^{\prime}_{(+)}}(w^{\prime})}$ is
measured to be

$\displaystyle=\expsub{w^{\prime}\leftarrow{W^{\prime}}}{\max\limits_{\phi^{\prime}}\condprob{\Phi\in{B_{t}(\phi^{\prime})}}{{W}\not\in{B_{t^{\prime}_{(+)}}(w^{\prime})}}}$
$\displaystyle\leq{\max\limits_{t=t_{\max}}{\condprob{\norm{\delta}\leq{t}}{\norm{w_{e}\xor{w^{\prime}}}\geq{t^{\prime}_{(+)}}}}}$
$\displaystyle=\condprob{\norm{\delta}\leq{n(\xi-\epsilon_{ss})}}{\norm{w_{e}\xor{w^{\prime}}}\geq{t^{\prime}_{(+)}}}\leq{\exp{(-2n{\epsilon_{ss}^{2})}}}$
(3)

###### Proof

$W\not\in{B_{t^{\prime}_{(+)}}(w^{\prime})}$ means
${\lVert{w_{e}\xor{w^{\prime}}}\rVert}({k^{*}})^{-1}\geq{\xi+\epsilon_{ss}}$.
For $\xi={\lVert{w_{e}\xor{w^{\prime}}}\rVert}({k^{*}})^{-1}$, and
$t_{\max}=n(\xi-\epsilon_{ss})$. It follows that $n\xi\geq{t}+n\epsilon_{ss}$
can be yielded by multiplying both sides of the inequality with $n$, yielded
$t_{\max}\geq{t}$. Then the probability for ${\norm{\delta}}\leq{t_{\max}}$
given
${\lVert{w_{e}\xor{w^{\prime}}}\rVert}({k^{*}})^{-1}\geq{\xi+\epsilon_{ss}}$
can be computed by Hoeffding’s inequality follows the last line of Eq. 3.

By Corollary 1, the conditioned min-entropy of RV over $\Psi$ measured to be

$\displaystyle\condminentropy{\Psi}{\mathcal{W}}=-\log\bigg{(}{\expsub{W\leftarrow{\mathcal{W}}}{\condprob{\Psi=\Phi}{\mathcal{W}=W}}}\bigg{)}$
$\displaystyle\geq{-\log\bigg{(}\expsub{w^{\prime}\leftarrow{W^{\prime}}}{\max\limits_{\phi^{\prime}}\condprob{\Phi\in{B_{t_{\max}}(\phi^{\prime})}}{W\not\in{B_{t^{\prime}_{(+)}}(w^{\prime})}}}\bigg{)}}$
$\displaystyle\geq{\log(1/\exp{(-2n{\epsilon_{ss}^{2})}})}$ (4)

##  9 Correctness with Regardless Computational Power

Formally, the correctness characterizes the success rate of the recovery of
the original codeword $c^{*}$ from a sketch generated by
$\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}}$. In this section, we
study the correctness theoretically without relying on any efficiency argument
over the algorithm pair
$\langle\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}},\mathsf{Rec}_{{\mathsf{\Omega}},\cdv_{in},\cdv_{out},\mathsf{f}}\rangle$
itself.

Since $\cdv_{in}(w)=c^{*}$, given $\cdv_{in}$, revealing the value of $w$
implies the knowledge on $c^{*}$. Therefore, it is desired to show that the
probability of success in revealing $w$ using algorithm pair
$\langle\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}},\mathsf{Rec}_{{\mathsf{\Omega}},\cdv_{in},\cdv_{out},\mathsf{f}}\rangle$
is at least (minimum) $1-\beta$ with some negligible probability $\beta>0$. It
can be expressed in Eq. 5 below for all $\epsilon_{rec}\geq{(2k^{*})^{-1}}$

$\displaystyle\prob{\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}(\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}}(w,N,\epsilon_{ss}),w^{\prime},N,\epsilon_{rec})=w}={1-\beta}.$
(5)

To measure the minimum probability for Eq. 5, the maximum value of $\beta$
have to be computed, which also referring to the maximum error in recovering
$c^{*}$ from a sketch with
$\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}$.

To maximize such error for maximum value of $\beta$, one shall use a minimum
distance

${t_{\min}}=n(\xi+\epsilon_{ss})\leq{t}$

for any random variable $\Phi\in{\Psi}$ in looking for a distinct RV (given
$\phi^{\prime}$), i.e., $\Phi\notin{B_{t_{\min}}(\phi^{\prime})}$.

Recall the distribution of RV is input dependence, hence, $\Phi$ is
conditioned on the original distribution of the variable $W$. To look for
$t_{\min}$, we first define a minimum tolerance distance as

$t^{\prime}_{(-)}={(\xi-\epsilon_{ss}){k^{*}}}$

for any distributions of the variable $W\in{\mathcal{W}}$ after random error
parsing. Clearly, for $\epsilon_{ss}\geq{(2k^{*})^{-1}}>0$, the defined
minimum distance $t^{\prime}_{(-)}$ would imply error rate of
$\xi-\epsilon_{ss}$, which is always smaller than $\xi$. At same point, one
always need $t^{\prime}_{(-)}\leq{t^{*}}<t$ holds so that $t^{\prime}_{(-)}$
is minimum for any original distribution of the variable $W$ (before random
error parsing), which hold for all $w\in{W}$. The following Corollary
revealing $\beta\leq{\exp(-2n\epsilon^{2}_{ss})}$.

###### Corollary 2

Given any random variable ${W}\in{\mathcal{W}}$, and a random string
$w^{\prime}\in{W^{\prime}}$. For all RV over a family of distributions
${\Psi}$, the conditioned maximum probability to look for any distinct RV
$\phi$ in any random distribution $\Phi\not\in{B_{t_{\min}}(\phi^{\prime})}$
over $\Psi$ (i.e. $\norm{\phi\xor{\phi^{\prime}}}=\norm{\delta}\geq{t_{\min}}$
for all $\phi\in{\Phi}$) when $W\in{B_{t^{\prime}_{(-)}}(w^{\prime})}$ is
measured to be

$\displaystyle\expsub{w^{\prime}\leftarrow{W^{\prime}_{0}}}{\max\limits_{\phi^{\prime}}\condprob{\Phi\not\in{B_{t_{\min}}(\phi^{\prime})}}{W\in{B_{t^{\prime}_{(-)}}(w^{\prime})}}}$
$\displaystyle\leq{\max\limits_{t=t_{\min}}{\condprob{\norm{\delta}\geq{t}}{\norm{w_{e}\xor{w^{\prime}}}\leq{t^{\prime}_{(-)}}}}}$
$\displaystyle=\condprob{\norm{\delta}\geq{n(\xi+\epsilon_{ss})}}{\norm{w_{e}\xor{w^{\prime}}}\leq{t^{\prime}_{(-)}}}\leq{\exp{(-2n{\epsilon_{ss}^{2})}}}.$
(6)

###### Proof

$W\in{B_{t^{\prime}_{(-)}}(w^{\prime})}$ means
${\lVert{w_{e}\xor{w^{\prime}}}\rVert}({k^{*}})^{-1}\leq{\xi-\epsilon_{ss}}$.
For $\xi={\lVert{w_{e}\xor{w^{\prime}}}\rVert}({k^{*}})^{-1}$, and
$t_{\min}=n(\xi+\epsilon_{ss})$, then $n\xi\leq{t}-n\epsilon_{ss}$ can be
yielded by multiplying both sides of the inequality with $n$, yielded
${t_{\min}}\leq{t}$. The probability for ${\norm{\delta}}\geq{t_{\min}}$ given
${\lVert{w_{e}\xor{w^{\prime}}}\rVert}({k^{*}})^{-1}\leq{\xi-\epsilon_{ss}}$
can be computed by Hoeffding’s inequality follows the last line of Eq. 6.

The following Proposition can be obtained by comparing Eq. 5 and Eq. 6.

###### Proposition 1

For all $\epsilon_{ss}\in{[(2k^{*})^{-1},1/4]}$,
$\epsilon_{rec}\geq{(2k^{*})^{-1}}$, and
$\norm{w_{e}\xor{w^{\prime}}}\leq{t^{\prime}_{(-)}}\leq{t^{*}}$,

$\displaystyle\prob{\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}(\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}}(w,N,\epsilon_{ss}),w^{\prime},N,\epsilon_{rec})=w}$
$\displaystyle\geq{{1-{\exp{(-2n{\epsilon_{ss}^{2})}}}}}$

Above result showed the recovery of $c^{*}$ and so $w$ will success with high
probability when $n$ is sufficiently large without considering the efficiency
of the algorithm pair
$\langle\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}},\mathsf{Rec}_{{\mathsf{\Omega}},\cdv_{in},\cdv_{out},\mathsf{f}}\rangle$.

##  10 Correctness with Regard to Computational Power

This section provided details discussion over the correctness of the algorithm
pair
$\langle\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}},\mathsf{Rec}_{{\mathsf{\Omega}},\cdv_{in},\cdv_{out},\mathsf{f}}\rangle$
as well as their efficiency in term of computation complexity. Since
$k^{*}<n$, we use $n$ as upper bound and define both
$\langle\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}},\mathsf{Rec}_{{\mathsf{\Omega}},\cdv_{in},\cdv_{out},\mathsf{f}}\rangle$
to be efficient if they can run in polynomial time $\poly$ in the input sketch
size $n$ to show correctness. Clearly, all steps on
$\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}}$ can be done in $\poly$,
our efficiency arguments would therefore only focus on the recovery algorithm
$\mathsf{Rec}_{{\mathsf{\Omega}},\cdv_{in},\cdv_{out},\mathsf{f}}$ itself.

###  10.1 Computational Reduction of Correctness

Recall our correctness claim in Section 9 comes with bounded probability of
error such that the recovery would success with probability at least
$1-\exp(-2n\epsilon_{ss}^{2})$ given $\norm{\delta}\leq{t_{\max}}$ holds. In
this subsection, we show that the above derived error bound can be reduced to
merely depends upon the algorithm itself, parametrized by the number of zero
padding in front of $v_{syn}$.

To show this, recall
$\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}$ will only
proceed to the second decoding if the first decoding return $v^{*}$ with the
first $k-n^{*}$ bits are all zeros. Because the selection of the error vector
$e^{\prime}\in{\mathcal{E}_{rec}}$ is random, every iteration of the first
decoding should return a random codeword $c\in{\cdv_{out}}$, hence its first
$k-n^{*}$ bits of $v_{syn}$ are random over $\bin^{k-n^{*}}$. Such argument
holds much stronger when random generator matrices are used for both
$\cdv_{in}$ and $\cdv_{out}$ (see coming Subsection 10.3). In this regard, the
probability for first $k-n^{*}$ bits of $v_{syn}$ are all zeros can be
described as $2^{-{(k-n^{*})}}$. Once the error vector $e^{\prime}$ is found
(or first decoding is viewed as succeed), it follows
$\norm{w_{e}\xor{w^{\prime}}}\leq{t^{\prime}_{(-)}}\leq{t^{*}}$, where the
second decoding must success to recover $c^{*}$ with probability
$1-2^{-{(k-n^{*})}}$ with error revealed by the number of zeros padding to the
syndrome vector $v_{syn}$. Nevertheless, a necessary condition for above
argument to hold would be the case when

$\displaystyle\beta\leq{\exp(-2n\epsilon^{2}_{ss})}\leq{2^{-(k-n^{*})}},$ (7)

which yielded a tighter upper bound for the derived recovery error $\beta$.
Without the exact knowledge of $\epsilon_{ss}$, there is no straightforward
way to determine the value of $n$ which often yield a meaningful computational
reduction to describe the maximum error exactly as $\beta=2^{-(k-n^{*})}$.
Nonetheless, since $\epsilon_{ss}\in{[(2k^{*})^{-1},1/4]}$, the minimum value
of $n$ can be set to $n={2{(k^{*})}^{2}}$, it follows (for $k-n^{*}=1$)

$\beta\leq{\exp(-2n\epsilon_{ss}^{2})}=\exp(-4k^{2}\epsilon_{ss}^{2})={\exp(-1)}<2^{-(k-n^{*})}=2^{-1}.$

Doing so can ensure Eq. 7 holds for any
$\epsilon_{ss}\in{[(2k^{*})^{-1},1/4]}$ and the recovery error is maximum
which can be described exactly as $\beta=2^{-(k-n^{*})}=1/2$. To achieve lower
$\beta$, higher value of $n\geq{2{(k^{*})}^{2}}$ is needed. This suggested
that reducing the recovery error $\beta$ always need sufficient large
$n\geq{2{(k^{*})}^{2}}$ and there is no straightforward way of deducing it
given the value of $\epsilon_{ss}$ is unknown.

Above reasoning showed the dependency of our correctness derived previously in
Section 9 reduced to the number of zeros padding in the sketching phase,
measured as $k-n^{*}$, conditioned on the value of $n$ is sufficient large.
Noting that such reduction is computational. It means our derived correctness
now holds for any chosen parameters for $\cdv_{in}$ and $\cdv_{out}$ with
$\epsilon_{ss}\in{[(2k^{*})^{-1},1/4]}$ as long as $n$ is sufficiently large
where $k^{*}\leq{n^{*}<k\leq{n}}$ follows.

For instance, under the designation of an BCH code [17], its correctness is
defined using some positive integer $m^{\prime}\geq{3}$. Given a desired value
of tolerance distance $t<2^{m^{\prime}-1}$, one can construct an $[{n,k,t}]$
BCH code $\cdv_{out}$ with parameters $n=2^{m^{\prime}}-1$,
$n-k\leq{m^{\prime}t}$ and minimum distance $d\geq{2t-1}$. Then, for
sufficiently large $n$, it is succinct to express

$-\log(1/\beta)={k-n^{*}}=m^{\prime}\geq{3}.$

Doing so means that once the first decoding is success, its error is bounded
by $\beta\leq{0.125}$ corresponds to the number of zeros padding in front of
$v_{syn}$, i.e., at least three zeros. Eventually, the second decoding stage
shall success with probability at least $1-\beta\geq{0.875}$ where
$\norm{w_{e}\xor{w^{\prime}}}\leq{t^{\prime}_{(-)}}\leq{t^{*}}$ follows.

###  10.2 Tolerating More Error Computationally

So far, our derived correctness theoretically demonstrating at most
$t^{\prime}_{(-)}\leq{t^{*}}$ of errors (or error rate of at most
$\xi-\epsilon_{ss}$) can be tolerated over any random distribution
$W\in\mathcal{W}$. It is natural to ask whether one can tolerate more error
(more than $t‘_{(-)}$) and what is the maximum achievable error tolerance rate
of our construction.

In fact, it is showed in Corollary 1 it is infeasible to tolerate more than
$t^{\prime}_{(+)}$ errors because the probability to look for similar RVs is
exponentially small if $\norm{w_{e}\xor{w^{\prime}}}\geq{t^{\prime}_{(+)}}$.
However, it remains possible for one to tolerate
$t_{(+)}=\floor{t^{\prime}_{(+)}}\leq{t^{\prime}_{(+)}}$ number of errors,
significantly more than some minimum value
$t_{(-)}=\floor{{t^{\prime}_{(-)}}}\leq{{t^{\prime}_{(-)}}}$ computationally.

To show this, for any error (distance) described as
${\lVert{w_{e}\xor{w^{\prime}}}\rVert}={t_{(+)}}$. By using an error parameter
$\epsilon_{rec}\in{[\epsilon_{ss},2\epsilon_{ss}]}$, the final error can be
described as
${\lVert{w_{e}\xor{w^{\prime}_{e^{\prime}}}}\rVert}={t_{(+)}}\pm\floor{k^{*}\epsilon_{rec}}$.
In view of this, given high enough value of $\epsilon_{rec}$, i.e.
$\epsilon_{rec}=2\epsilon_{ss}$ is used for recovery, any error of
${\lVert{w_{e}\xor{w^{\prime}}}\rVert}=t_{(+)}$ is possible to be reduced down
to ${\lVert{w_{e}\xor{w^{\prime}_{e^{\prime}}}}\rVert}=t_{(-)}$. Eventually,
the remaining errors
$\norm{w_{e}\xor{w^{\prime}_{e^{\prime}}}}={t_{(-)}}\leq{t^{\prime}_{(-)}}$
can be tolerated with high probability follows Proposition 1.

To do so, suppose one does not know the value of $\epsilon_{ss}$, he/she can
try to choose some value of $\epsilon_{rec}\in[(2k^{*})^{-1},1/2]$ (since
$\epsilon_{ss}\in[(2k^{*})^{-1},1/4]$) during recovery. Doing so allow him/her
to generate a list of possible error vectors
$\\{{{e^{\prime}_{1}},\ldots,{e^{\prime}_{|\mathsf{supp}(\mathcal{E}_{rec})|}}}\\}\in{\mathcal{E}_{rec}}$,
which corresponds to a list of possible noisy strings
$w^{\prime}_{e_{i}}\in{W^{\prime}_{i}}$ (for
$i=1,\ldots,|\mathsf{supp(\mathcal{E}_{rec})}|$) over another family of
distributions
$\mathcal{W^{\prime}}=\\{{{W^{\prime}_{1}},\ldots,W^{\prime}_{{|\mathsf{supp}(\mathcal{E}_{rec})|}}}\\}$.
For each chosen value of $\epsilon_{rec}$, one shall have
$\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}$ runs in
${{|\mathsf{supp}(\mathcal{E}_{rec})|}}$ iterations to try all possible
$\\{{{e^{\prime}_{1}},\ldots,{e^{\prime}_{|\mathsf{supp}(\mathcal{E}_{rec})|}}}\\}\in{\mathcal{E}_{rec}}$
until he/she found a noisy string $w^{\prime}_{e^{\prime}}$ s.t.
$\norm{w_{e}\xor{w^{\prime}_{e^{\prime}}}}={t_{(-)}}\leq{{t^{\prime}_{(-)}}}$
holds. Note that our recovery process generally covered the trivial case as
well when $\floor{k^{*}\epsilon_{rec}}=\floor{k^{*}\epsilon_{ss}}=0$
(noiseless case).

More precisely, let $d^{\prime}=\floor{k^{*}\xi}$ denotes the original
distance $\norm{w\xor{w^{\prime}}}={d^{\prime}}$. Parsing an error
$e\in{\mathcal{E}_{ss}}$ of weight $\floor{k^{*}\epsilon_{ss}}$ to the input
$w\in{W}$ yields $w_{e}$. It follows there should be a resultant worst-case
error (described in terms of maximum distance) where

$\norm{w_{e}\xor{w^{\prime}}}={\floor{k^{*}\xi}}\pm\floor{k^{*}\epsilon_{ss}}={d^{\prime}\pm\floor{k^{*}\epsilon_{ss}}}={d^{\prime}+\floor{k^{*}\epsilon_{ss}}}=t_{(+)}.$

Note that when
$\norm{w_{e}\xor{w^{\prime}}}={d^{\prime}-\floor{k^{*}\epsilon_{ss}}}={t_{(-)}}\leq{t^{\prime}_{(-)}}$
(refers to ‘-’ sign), such errors is trivial which can be tolerated with
probability at least $1-2^{-(k-n^{*})}$ with sufficiently large $n$. Our goal
is to tolerate the worst-case error, described as
$t_{(+)}={d^{\prime}+\floor{k^{*}\epsilon_{ss}}}$ (refers to the ‘+’ sign).
For some random value of $\epsilon_{ss}$ introduced in sketching, it follows
the worst-case error concerning the case when the value $\epsilon_{rec}$ is
maximum, i.e. $\epsilon_{rec}={2\epsilon_{ss}}$. To be specific, there must
have a solution for $e^{\prime}$ in the worst-case (when
$\epsilon_{rec}={2\epsilon_{ss}}$) described as:

$\displaystyle\norm{w_{e}\xor{w^{\prime}_{e^{\prime}}}}=\norm{(w\xor{e})\xor({w^{\prime}\xor{e^{\prime}}})}=\norm{(w\xor{w^{\prime})}\xor{(e\xor{e^{\prime}}})}$
$\displaystyle={(d^{\prime}}+\floor{k^{*}\epsilon_{ss}})-\floor{2k^{*}\epsilon_{ss}}={d^{\prime}-\floor{k^{*}\epsilon_{ss}}}={t_{(-)}}.$
(8)

Clearly,
${t_{(-)}}=\floor{t^{\prime}_{(-)}}\leq{t^{\prime}_{(-)}}\leq{t^{*}}$, the
error would therefore be tolerated with high probability given sufficiently
large $n$.

Nevertheless, to achieve such goal without the knowledge of $\epsilon_{ss}$,
one has to trial $e^{\prime}\in{\mathcal{E}_{rec}}$ of different weights for
Eq. 8 to hold. Hence, the recovery complexity is always bounded by the maximum
brute-force trials with maximum tolerate distance $t_{(+)}$. In view of this,
ones have to deal with the issue of computational power in running
$\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}$, where the
maximum number of iteration $|\mathsf{supp}(\mathcal{E}_{rec})|$ has to be
identified to determine maximum recovery complexity for efficiency
investigation.

With $\epsilon_{rec}=2\epsilon_{ss}$, by Stirling approximation, the value
${|\mathsf{supp}(\mathcal{E}_{rec})|}$ can be bounded as

$\displaystyle{{|\mathsf{supp}(\mathcal{E}_{rec})|}}={{{k^{*}}\choose{\floor{k^{*}\epsilon_{rec}}}}}={{{k^{*}}\choose{\floor{2k^{*}\epsilon_{ss}}}}}\leq{2^{{k^{*}{h_{2}(2\epsilon_{ss})}}}},$
(9)

where $h_{2}(x)=-x\log(x)-(1-x)\log(1-x)$ is the binary entropy function with
input error rate of $x$.

Although it remains feasible for one to have the recovery algorithm run in
parallel with all possible value of $\epsilon_{rec}\in[(2k^{*})^{-1},1/2]$
using different computational machine. The overall brute-force complexity is
still bounded by the order of $O(2^{{k^{*}{h_{2}(2\epsilon_{ss})}}})$ for
$\epsilon_{ss}\in{[(2k^{*})^{-1},1/4]}$.

###  10.3 Choosing the Best Code for Difference Sources

Recall that $d^{\prime}=\floor{k^{*}\xi}$, where
$\xi=\norm{w_{e}\xor{w^{\prime}}}(k^{*})^{-1}$. It is obvious that the value
of $t_{(+)}$ defined in our construction strictly depends upon the input noisy
string’s distribution $w_{e}\in{\mathcal{W}}$ (or the value of $\xi$). In such
a case, the maximum value for $\xi$ reveals the maximum achievable distance
$t_{(+)}$ for worst-case error tolerance. Such achievable tolerance distance
does not necessary restricted by a particular choice of error correction code,
rather, it is input dependence, i.e. depends upon the value of $d^{\prime}$.

Nonetheless, it is straightforward for one to simply choose a code with
specified tolerance rate $\xi=t/n$ for $\cdv_{out}$. In such a case, the value
of $d^{\prime}=\floor{k^{*}\xi}$ can be determined exactly and so the
achievable tolerance distance for worst-case error $t_{(+)}=\floor{2k^{*}\xi}$
is set immediately depends upon the chosen code for $\cdv_{out}$. However,
doing so is not always a good practice in reality. This is because if the
error rate introduced during sketching phase is larger than the error
tolerance rate of the chosen code, i.e., $\epsilon_{ss}>\xi$, the correctness
of the recovery algorithm might not hold. On the other hand, if
$\epsilon_{ss}<\xi$, it may lead to over error tolerance (i.e., tolerating
more error than necessary), hence cannot show security to more error than
entropy sources. In view of this, the best one can do is to look for the
minimum solution of $\xi=\epsilon_{ss}$ (recall $\xi\geq{\epsilon_{ss}}$).
Note that doing so is equivalent to look for the minimum distance $d^{\prime}$
for the input pair $(w,w^{\prime})$ where the error rate $\epsilon_{ss}$
introduced during the sketching phase has to be identified. Once such minimum
solution is found, it follows that the knowledge on $t_{(+)}$ is immediate.

Since $\xi\geq{\epsilon_{ss}}$, it follows $t_{(-)}\geq{0}$. Therefore, the
required minimum distance for $w$ and $w^{\prime}$ in our construction can be
simply described with $\epsilon_{ss}$ as

$\displaystyle\norm{w\xor{w^{\prime}}}=d^{\prime}=\floor{k^{*}\xi}\geq{{\floor{k^{*}\epsilon_{ss}}}}\geq{0}.$
(10)

By minimum $d^{\prime}=\floor{k^{*}\xi}=\floor{k^{*}\epsilon_{ss}}=0$, it
follows

$\displaystyle{t_{(-)}}=0\leq\norm{w_{e}\xor{w^{\prime}_{e^{\prime}}}}\leq{t^{*}}$
(11)

must hold in order for the second decoding with $\cdv_{in}$ to success. Hence,
one can always choose the parameters $t^{*}\geq{0}$ for $\cdv_{in}$ which is
trivial for any $[n^{*},k^{*},t^{*}]$ linear code.

Same thing applied to the outer code $\cdv_{out}$. Given such minimum solution
is found (means $\xi=\epsilon_{ss}$). One shall have
$t_{\max}=n(\xi-\epsilon_{ss})=0$. Therefore, one can simply choose
$\cdv_{out}$ to be any trivial linear code with $t=t_{\max}=0$. For the most
easiest way, simply choose two random generator matrices for $\cdv_{in}$ and
$\cdv_{out}$ with $t^{*}=0$ and $t=0$ respectively. Doing so means no error
tolerance thus $c^{*}={c^{*}}^{\prime}$ and $c=c_{i}^{\prime}$ are assumed. In
such a case, one can skip both of the decoding steps (relies on $\mathsf{f}$)
and replace it with Gaussian elimination which can be done efficiently in
$O(n^{3})$.

Focusing on the worst-case error when $\epsilon_{rec}=2\epsilon_{ss}$ (follows
Eq. 8), the first affirmative decoding result (first $k-n^{*}$ bits of
${v^{*}}$ are zeros) would mean

$\displaystyle\norm{w_{e}\xor{w^{\prime}_{e^{\prime}}}}={(d^{\prime}}+\floor{k^{*}\epsilon_{ss}})-\floor{k^{*}\epsilon_{rec}}={0}.$

Thus, one shall have the worst-case solution for $\epsilon_{rec}$, i.e.,
$\epsilon_{rec}=2\epsilon_{ss}$, coincides with the minimum solution when
$\xi=\epsilon_{ss}$ s.t.

$\displaystyle\epsilon_{rec}=\epsilon_{ss}=\xi.$ (12)

For sufficiently large $n$, the recovery of $c^{*}$ would success with
probability $1-2^{-(k-n^{*})}$ and the maximum tolerance distance
$t_{(+)}=d^{\prime}+\floor{k^{*}\epsilon_{ss}}=\floor{2k^{*}\epsilon_{ss}}$
can also be determined. Since $\epsilon_{ss}\in{[(2k^{*})^{-1},1/4]}$, it
means the solution $\xi\leq{1/4}$ follows. Thus, one able to tolerate at most

$\displaystyle
t_{(+)}=d^{\prime}+\floor{k^{*}\epsilon_{ss}}=\floor{k^{*}\xi}+\floor{k^{*}\epsilon_{ss}}\leq\floor{2k^{*}\epsilon_{ss}}=\floor{k^{*}/2}$
(13)

number of errors in the worst-case using our construction with maximum error
rate $\epsilon_{ss}=1/4$ introduced in sketching phase.

###  10.4 Computational Hardness of Recovery: The NP-Complete problems

Nonetheless, Eq. 9 suggesting exponential computation time in the input size
$k^{*}$ for all $\epsilon_{rec}\in[(2k^{*})^{-1},1/2]$, which is highly
inefficient for large $k^{*}$. This result is not suprised because determining
the minimum distance of an error correction code or the minimum distance
problem is indeed NP-complete [18]. Besides, looking for such nontrivial error
vector $e^{\prime}\in{\mathcal{E}_{rec}}$, which viewed as the minimum-weight
solution to Eq. 8 is another NP-complete problem [19], commonly refer to the
maximum likelihood decoding problem for a linear code [20]. Clearly, if the
later one can be solved easily, then the former problem can also be solved
easily by trying $\floor{k^{*}\epsilon_{rec}}=1,2\ldots$ (parametrized by
$\epsilon_{rec}$) with different random string $w^{\prime}$ to yield a
polynomial length of yes/no solutions. More formally, the corresponding
decision version of maximum likelihood decoding problem can be formalized as
follow:

Problem: Maximum likelihood decoding  Instance: A $\alpha\times{n}$ binary
matrix $H$, a vector $y\in\FF_{2}^{\alpha}$, and integer $z>0$ Question: Is
there a vector $x\in{\FF_{2}^{n}}$ of weight $\leq{z}$, such that $Hx=y$
Clearly, the answer for above question would be ‘yes’ if one able to find $x$,
which can be viewed as the solution for $e^{\prime}\in{\mathcal{E}_{rec}}$
where Eq. 8 holds. More explicitly, let $H$ be the parity check matrix of
$\cdv_{out}$, so $\alpha=n-k$. Note that
$Hc\Leftrightarrow{\mathsf{syn}}(c)=0^{\alpha}$, where ${\mathsf{syn}}(c)$ is
the syndrome of the encoded codeword $c\in{\cdv_{out}}$. Given the corrupted
codeword $c^{\prime}$, the RV $\phi^{\prime}$ and $H$, the syndrome decoding
algorithm $\mathsf{f}$ computes

$\displaystyle\mathsf{f}(c^{\prime})=H\cdot{(c\xor{(\phi^{\prime}\xor\phi)}})=Hc\xor{H\delta}=0^{\alpha}\xor{\mathsf{syn}(\delta)}={\mathsf{syn}(\delta)}$

yields the syndrome of $\delta$. Given the distance
$\norm{\phi\xor\phi^{\prime}}=\norm{\delta}$ is small, i.e.,
$\norm{\delta}\leq{t}$, knowing $\mathsf{syn}(\delta)$ is enough to determine
the offset $\delta$, which can be done via $\mathsf{f}$ in $\poly$ running
time.

In our case, by treating $x=\delta$ follows the constrain of
$\norm{\delta}\leq{t_{\max}}$ (see the proof in Corollary 1), the hardness of
looking for $\delta$ (of size $n$) is as hard as the above mentioned decision
problem related to the maximum likelihood decoding. Nevertheless, recall
results in Section 10.1 showed that if $e^{\prime}\in{\mathcal{E}_{rec}}$ can
be found s.t.
$\norm{w_{e}\xor{w^{\prime}_{e^{\prime}}}}\leq{t_{(-)}}\leq{t^{*}}$ holds,
then $\norm{\delta}\leq{t_{\max}}$ can be achieved with probability at least
$1-2^{-(k-n^{*})}$ (conditioned on sufficiently large $n$). Viewed this way,
efficient searching process for $e^{\prime}$ immediately implies efficient
maximum likelihood decoding algorithm, hence resolve the NP-complete problem
discussed above in an efficient manner.

More precisely, the searching process for the error vector $e^{\prime}$ can be
formalized by the algorithm
$\langle\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}},\mathsf{Rec}_{{\mathsf{\Omega}},\cdv_{in},\cdv_{out},\mathsf{f}}\rangle$
to start and end within
$\floor{k^{*}\epsilon_{rec}}=0,1,2,\ldots,\floor{2k^{*}\epsilon_{ss}}$
corresponds to the worst-case error rate $\epsilon_{ss}$ introduced during
sketching. Because the recovery process is defined adversarial, the actual
value of $\epsilon_{ss}$ might not known. Nonetheless, we have
$\epsilon_{ss}\in{[(2k^{*})^{-1},1/4]}$, hence, the maximum number of trial
would be bounded at most $\floor{2k^{*}\epsilon_{ss}}=\floor{k^{*}/2}$ for a
given value of $k^{*}$.

###  10.5 Deterministic Polynomial Time Recovery

In the last subsection, we have studied that the successful recovery of the
original codeword $c^{*}$ using our proposed recovery algorithm is
computational hard in the sense that the process in looking for the nontrivial
error vector $e^{\prime}$ is NP-complete. This subsection provided more
details discussion on the efficiency of our proposed recovery algorithm. More
precisely, we would show that certain minimum requirement (bound) is required
to be satisfied in order to claim efficiency of our proposed algorithm, hence
resolved the above mentioned NP-complete problems.

Note that the efficiency of our proposed recovery algorithm
$\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}$ strongly
depends upon the brute-force complexity itself, which is proportional to the
value of ${|\mathsf{supp}(\mathcal{E}_{rec})|}$. Given one any chosen values
of $n^{*}$ and $k$ for $\cdv_{in}$ and $\cdv_{out}$ respectively s.t.
${{{k^{*}{h_{2}(2\epsilon_{ss})}}}}\leq{k-n^{*}}$, such complexity can be
bounded in terms of the sketch size $n$ described as:

$\displaystyle|{{\mathsf{supp}(\mathcal{E}_{rec})|}}\leq{2^{{k^{*}{h_{2}(2\epsilon_{ss})}}}}\leq{2^{k-n^{*}}}={2^{m^{\prime}}}=n+1.$
(14)

Then, by summing all the necessary operation steps (complexity in term of
$n$), i.e., $\text{Step 1}+\text{Step 2}+....+\text{Step
16}=1+n+1+...+1=\poly$ over the recovery algorithm
$\mathsf{Rec}_{{\mathsf{\Omega}},\cdv_{in},\cdv_{out},\mathsf{f}}$. The
overall complexity of the recovery algorithm can be expressed as some
polynomial function $\poly$ using $n$.

###  10.6 Efficiency in Average-case and Worst-case scenarios

Our efficient result discussed in previous section suggested padding more
zeros in front of $v_{syn}$ means greater value of $n$, hence higher recovery
complexity. It is natural for one to question on whether expressing the number
of iterations in term of $n+1$ is meaningful. More formally, one may ask

“Does such expression really help in reducing our effort in solving the given
problem?”

In this subsection, we will discuss the controversy mentioned above and show
that such expression is necessary for large class error rate but not all,
i.e., $\epsilon_{rec}<1/2$.

To start the discussion, it is good to recall the prerequisite bound of our
efficiency claim showed in Eq. 14. Noting that the number of zeros padding
$k-n^{*}=m^{\prime}$ shall increase proportional to the value of
$h_{2}(2\epsilon_{ss})$ for it to hold. This can be argued in the sense that
given any recovery error parameter
$\epsilon_{rec}\in{[(2k^{*})^{-1},2\epsilon_{ss}]}$, one have to try
$2^{k^{*}h_{2}(\epsilon_{rec})}$ iterations to look for the solution of error
vector $e^{\prime}\in{\mathcal{E}_{rec}}$ of weight
$\floor{k^{*}\epsilon_{rec}}$. Since $\cdv_{in}(w)=c^{*}$, the total number of
possible value for $c^{*}$ must be bounded by the possible values of
$w\in{W}$, which is at most $2^{k^{*}}$. In other words, if there are total
number of $2^{m^{\prime}}$ possible values for $c^{*}$, at least
$2^{m^{\prime}}\leq{2^{k^{*}}}$ number of random guesses are needed to ensure
one can always reveal $c^{*}$ exactly.

Under the average-case scenario when $\epsilon_{ss}\in{[(2k^{*})^{-1},1/4)}$
(or equivalently $\epsilon_{rec}\in{[(2k^{*})^{-1},1/2)}$), one shall have the
recovery algorithm to try maximally $2^{k^{*}h_{2}(2\epsilon_{ss})}$
iterations to search for $e^{\prime}$ in recovering $c^{*}$ from the worst-
case error. Since the number of possible value for $c^{*}$ is denoted as
$2^{m^{\prime}}$, the searching for $e^{\prime}$ shall stop at most
$2^{k^{*}h_{2}(2\epsilon_{ss})}<{2^{k^{*}}}={2^{m^{\prime}}}-1$ iterations to
yield a meaningful efficiency claim in the sense that it can always do better
than random guesses of at least $2^{m^{\prime}}=2^{k-n^{*}}$ trials manifested
by the number of zero paddings in front of $v_{syn}$.

In fact, it is practically more efficient to express
$2^{m^{\prime}}=\poly+1\leq{2^{k^{*}}}$ rather than $n+1$. This is because
despite Eq. 14 holds with linear size of complexity $O(n)$ (by expressing
$2^{m^{\prime}}=n+1$), large value of $n$ would lead to longer operation time
(practically) for the remaining step of
$\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}$, which are
bounded in $O(n^{3})$. Even if expressing
$2^{m^{\prime}}=\poly+1\leq{2^{k^{*}}}$ is suffice to show our recovery
algorithm should operate in $\poly$ polynomial time in the sketch size.
Keeping the value $n$ small indeed offers better efficiency guaranty both in
term of complexity and practice, since small $n$ implies both $O(n^{3})$ and
$\poly$ are small. Therefore, meaningful efficiency claim implies at most

$2^{k^{*}h_{2}(2\epsilon_{ss})}=2^{m^{\prime}}-1=2^{-(k-n^{*})}-1=\poly\leq{2^{k^{*}}}-1$

iteration in searching $e^{\prime}$ over larger class of worst-case error rate
which can be precisely described as

$\displaystyle
2\epsilon_{ss}\leq{h_{2}^{-1}\bigg{(}\frac{\log(2^{m^{\prime}}-1)}{k^{*}}\bigg{)}}=h_{2}^{-1}\bigg{(}\frac{\log(\poly)}{k^{*}}\bigg{)}$
$\displaystyle=h_{2}^{-1}\bigg{(}\frac{\log(2^{(k-n^{*})}-1)}{k^{*}}\bigg{)}<h_{2}^{-1}\bigg{(}\frac{k-n^{*}}{k^{*}}\bigg{)}\leq{1/2}.$

Then, follows Eq. 7, the recovery error can be described exactly as

$\beta=2^{-(k-n^{*})}=2^{-m^{\prime}}=1/(\poly+1)\leq{1/\poly}.$

Above results demonstrated that the recovery error is at most $1/\poly$, hence
tighter upper bound can be used to describe $\beta=1/\poly$. This means that
the recovery error $\beta$ is also $\poly$ reducible. It follows sufficiently
large value of $n$ accompanies with correctness in reducing the error itself
described as $\beta=1/\poly$. In such a case, it is succinct to describe
$k-n^{*}$ using some polynomial function $\poly\leq{2^{k^{*}}}-1$ to show
efficient error tolerance for large class of worst-case error, arbitrary close
to fraction of $1/2$.

On the other hand, under the worst-case scenario when $\epsilon_{ss}=1/4$ (or
equivalent $\epsilon_{rec}=1/2$), one would need
$2^{k^{*}h_{2}(1/2)}=2^{k^{*}}$ number of iterations in searcing for
$e^{\prime}$. Therefore, no any advantages can be gained by using our recovery
algorithm to recover the exact value of $c^{*}$ compared to random guessing of
$2^{k^{*}}$ trials for all possible values of $c^{*}$. Hence, meaningful
efficiency claim cannot achieve in this case. Above scenario can be well
described using the notion of perfect secrecy, first studied by C. Shannon
(1949) [21].

Based on the above discussion, one can conclude that expressing the number of
iterations in term of $k-n^{*}=\log(\poly+1)\leq{k^{*}}$ is always necessary
for average-case scenario but not for worst-case scenario to achieve
meaningful recovery efficiency claim with $\poly$ complexity. This result lead
to the refined Eq. 14 and yield the requirement (bound) of meaningful
efficiency claim over large class of worst-case error for
$\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}$ described as

$\displaystyle k^{*}h_{2}(\epsilon_{rec})\leq{{k-n^{*}}},$ (15)

where

$k-n^{*}=\log(\poly+1)\leq{k^{*}},$

holds for average-case scenario.

##  11 Propositions Formalisation

This section provide summary of our derived results of correctness and
efficiency for
$\langle\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}},\mathsf{Rec}_{{\mathsf{\Omega}},\cdv_{in},\cdv_{out},\mathsf{f}}\rangle$.
In particular, we formalized them into two major Propositions in the following
paragraphs.

By Eq. 7 \- 15, we can formalise the following Proposition to characterize the
correctness of
$\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}$ for $t_{(+)}$
number of error in efficient manner with BCH codes.

###### Proposition 2

Let $k^{*}\geq{k-n^{*}}\geq{3}$ where $k-n^{*}=\log(\poly+1)$. Given any error
rate $\epsilon_{ss}\in{[(2{k^{*}})^{-1},1/4)}$,
$\epsilon_{rec}\in{[(2k^{*})^{-1},2\epsilon_{ss}]}$, and
$\norm{w\xor{w^{\prime}}}\geq{0}$ s.t.

$\displaystyle{{{k^{*}h_{2}{(\epsilon_{rec})}}}}\leq{k-n^{*}}$

Then, for sufficiently large $n$, there exits BCH codes for
$\cdv_{in}\in{\bin^{k^{*}}}$ and $\cdv_{out}\in{\bin^{n}}$ where

$\prob{\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}(\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}}(w,N,\epsilon_{ss}),w^{\prime},N,\epsilon_{rec})=w}\geq{0.875}$

can be achieved efficiently operating in time $\poly$ and the maximum
achievable error tolerance rate is $2\epsilon_{ss}<{1/2}$.

It is natural to ask whether the bound for $k-n^{*}\geq{3}$ can be generalized
to $k-n^{*}\geq{1}$, thus one obtains a tighter bound for $m^{\prime}$ derived
in Eq. 7. Noting that a tighter bound for $m^{\prime}\geq{k-n^{*}}\geq{1}$
implies the existence of larger class of $[n,k,t]$ linear codes which can be
determined using our construction (by looking the most suitable value of
$\xi$) for any sources $w$ (given $w^{\prime}$) of minimum distance at least
$\norm{w\xor{w^{\prime}}}={\floor{k^{*}\xi}}\geq{\floor{k^{*}\epsilon_{ss}}}\geq{0}$.

Nonetheless, we will show that the answer for this question is positive which
allow one to simply choose two random generator matrices for $\cdv_{in}$ and
$\cdv_{out}$ given some error parameter
$\epsilon_{ss}\in{[(2k^{*})^{-1},1/4)}$. In such a case, the selection of
$\cdv_{in}$ and $\cdv_{out}$ no longer necessary to be BCH codes. Simply
making sure the value of $n$ is sufficiently large to show correctness with
proper number of zeros padding to form $v_{syn}$ and $v^{*}$, it follows that
if $\exp(-2n\epsilon^{2}_{ss})\leq{1/2}$, then Eq. 7 should hold for
$k-n^{*}\geq{1}$. Thus,
$\prob{\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}(\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}}(w,N,\epsilon_{ss}),w^{\prime},N,\epsilon_{rec})=w}\geq{0.5}$.
One could also run the recovery with different value of
$\epsilon_{rec}\in[(2k^{*})^{-1},1/2)$ or try
$\floor{k^{*}\epsilon_{rec}}=0,1,2,\ldots,\floor{k^{*}/2}$ until the first
affirmative answer is obtained to determine the most suitable tolerable error
$t_{(+)}$ as discussed in the last section. The recovery procedure can always
done better than random guessing and its complexity can be bounded by some
polynomial function $\poly$ follows the efficiency argument discussed in
Section 10.6. Based on above reasoning, we shall have the following
proposition to formalize
$\langle\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}},\mathsf{Rec}_{{\mathsf{\Omega}},\cdv_{in},\cdv_{out},\mathsf{f}}\rangle$
as an efficient sketching and recovery algorithm for all inputs of minimum
distance $\norm{w\xor{w^{\prime}}}\geq{0}$.

###### Proposition 3

Let $k^{*}\geq{k-n^{*}}\geq{1}$ where $k-n^{*}=\log(\poly+1)$. Given
$\epsilon_{ss}\in{[(2{k^{*}})^{-1},1/4)}$,
$\epsilon_{rec}\in[(2k^{*})^{-1},2\epsilon_{ss}]$, and
$\norm{w\xor{w^{\prime}}}\geq{0}$ s.t.

$\displaystyle{{k^{*}h_{2}{(\epsilon_{rec})}}}\leq{{k-n^{*}}}$

Then, for sufficiently large $n$, there exits $[n,k,t]_{2}$ linear codes for
$\cdv_{in}\in{\bin^{k^{*}}}$ and $\cdv_{out}\in{\bin^{n}}$ where

$\prob{\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}(\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}}(w,N,\epsilon_{ss}),w^{\prime},N,\epsilon_{rec})=w}\geq{0.5}$

can be achieved efficiently operating in time $\poly$ and the maximum
achievable error tolerance rate is $2\epsilon_{ss}<{1/2}$.

The results in Proposition 2 and 3 have also suggested the NP-complete
problems mentioned in [18] and [19] can be solved efficiently in polynomial
time by using algorithm pair
$\langle\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}},\mathsf{Rec}_{{\mathsf{\Omega}},\cdv_{in},\cdv_{out},\mathsf{f}}\rangle$.
Follows the work in [22] stated, if any NP-complete problem possesses a
polynomial time algorithm to solve, then so does every NP-problem, and hence
we shall have P=NP.

##  12 Security

Recall the minimum information required to show correctness using
$\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}$ could be
expressed as the number of zeros padding to $v_{syn}$, which is $k-n^{*}$ as
long as $n$ is sufficiently large. Any adversary should be able to gain
certain minimum information due to the zeros padding. This minimum information
leakage is independent of how liberal or conservative is the selection of the
input string $w$. Rather, it is a limit (lower bound), which required to be
set in before constructing any error tolerance system, to satisfy certain
minimum requirement of correctness. Formally, follows Eq. 4 and Eq. 7, such
minimum information leakage can be used to express the conditioned min-entropy
of RV:

$\displaystyle\condminentropy{\Psi}{\mathcal{W}}\geq{\floor{\log(1/\exp{(-2n{\epsilon_{ss}^{2})}})}}\geq{m^{\prime}}={k-n^{*}}\geq{3}.$

Noting that the result in Proposition 3 would give tighter result, leads to

$\displaystyle\condminentropy{\Psi}{\mathcal{W}}\geq{\floor{\log(1/\exp{(-2n{\epsilon_{ss}^{2})}})}}\geq{m^{\prime}}={k-n^{*}}\geq{1}.$
(16)

Above results showed a tight lower bound min-entropy requirement for any
sources of at least bit $(m\geq{1})$. Note that such entropy measurement is
computational in the sense that it merely depends upon how the user
parametrize the algorithm pair
$\langle\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}},\mathsf{Rec}_{{\mathsf{\Omega}},\cdv_{in},\cdv_{out},\mathsf{f}}\rangle$
for $\cdv_{in}$ and $\cdv_{out}$ with $k^{*}\leq{n^{*}}<{k\leq{n}}$.

###  12.1 Computational Secure Sketch Implies Information-Theoretic Secure
Sketch

This section gives a more general discussion on the implication of a standard
secure sketch is in fact computational derivable.

Fuller et al., [9] have showed negative result on computational relaxation of
information-theoretical secure sketch requirement. In particular, for hamming
metric space, computational secure sketch assumed to retain high Hill entropy
(pseudo-random entropy) implies error correction code with approximately
$2^{m^{\prime}}$ points that correct $t$ random error. Their proof relies on
the existence of Shannon code, which can correct arbitrary random errors
$t^{\prime}\leq{t}$. The same result has first implicitly stated by Dodis et
al., (see Section 8.2 in [6]) where the main idea is by the conversion of
worst-case error into random error by using random permutation function $\pi$
which being part of the public sketch. Nevertheless, the proof itself is non-
constructive because it was still an open question on how to construct an
efficient Shannon code.

It is not difficult to verify that our findings agreed on above argument with
explicit construction of the algorithm pair
$\langle\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}},\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}\rangle$
viewed as an efficient Shannon code. More precisely, the sketching algorithm
$\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}}$ serves to encode any
noisy input $w$ and the recovery algorithm
$\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}$ can be used
for decoding.

We now show that our construction meets the well-studied computational bound
(Gilbert-Varshamov (GV) Bound) and coincides with the info-theoretic bound
(Shannon bound) as an optimal error correction code.

To do so, we shall use the derived computational bound for
$\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}$ to be
efficient and correct with probability at least $1-1/\poly$ is given as (see
Proposition 3 and Eq. 15):

$\displaystyle{{{k^{*}h_{2}{(\epsilon_{rec})}}}}\leq{k-n^{*}}\
(computational).$ (17)

Let $(k-n^{*})/k^{*}=\log(\poly+1)/k^{*}=1-R$ where $R$ is of rate
$0\leq{R}\leq{1-1/k^{*}}$ (since $\log(\poly+1)\leq{k^{*}}$ and
$k-n^{*}\geq{1}$). Apply such result to Eq. 17, we obtain:

$\displaystyle
R\leq{1-h_{2}(\epsilon_{rec})}\leq{1-h_{2}(\epsilon_{ss})}\leq{1-h_{2}(1/2k^{*})}<{1}\
\textit{(Shannon Bound)},$ (18)

which is indeed the Shannon bound with any source of size $k^{*}\geq{2}$
(where $k\geq{3}$) for it to be meaningful. Same thing applied for the upper
bound which attained the GV bound for $R$ in average-case scenario (i.e.,
$\epsilon_{ss}\in{[(2k^{*})^{-1},1/4)}$) described as:

$\displaystyle R\geq{1-h_{2}({2\epsilon_{ss}})}>{0}\ (GV-Bound).$ (19)

Note that when the number of zero padding $k-n^{*}>k^{*}$, the rate $R$
becomes negative. Therefore, restricting the number of zero padding
$k-n^{*}\leq{k^{*}}$ is necessary to ensures the achievable rate $R$ is
positive. Note that the value of $R$ is inversely proportional to the order of
$\poly$ and the sketch size $n$. Given the sketch size $n$ is decreased, it
follows $\poly$ is decreased thus the rate $R$ should be increased.

Observe that both Eq. 18 (Shannon bound) and Eq. 19 (GV bound) can achieve
rate $R<1$ arbitrary close to one given $k^{*}$ is sufficiently large. Applied
this result into our construction, this implies for any input of size
$k^{*}\geq{2}$, for sufficiently large $n$, there exist a good encoding and
decoding function which can be characterized by algorithm pair
$\langle\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}},\mathsf{Rec}_{\mathsf{\Omega},\cdv_{in},\cdv_{out},\mathsf{f}}\rangle$
where $k^{*}\leq{n^{*}}<{k}\leq{n}$ follows. Nonetheless, these two bound are
subjected to the same minimum rate $R>0$, where same upper bound of source
entropy loss can be described using $\log(\poly)\leq{\log(2^{k^{*}}}-1)$ for
the average-case scenario and $\log(\poly+1)=\log(2^{k^{*}})=k^{*}$ for the
worst-case scenarios.

Based on above reasoning, computational secure sketch implies information
theoretic secure sketch, where both of them are subjected to the same upper
bound and lower bound (where $R\in{(0,1)}$) with entropy loss at most $k^{*}$.

Follows the correctness formalized in Proposition 3, and the security
reasoning above, the Proposition below is given to characterize our
construction as a efficient secure sketch for average-case scenario.

###### Proposition 4

For $m^{\prime}\geq{1}$. Algorithm pair
$\langle\mathsf{SS}_{\mathsf{\Omega},\cdv_{in},\cdv_{out}},\mathsf{Rec}_{{\mathsf{\Omega}},\cdv_{in},\cdv_{out},\mathsf{f}}\rangle$
is an efficient $(\mdv_{1},m,m^{\prime},t_{(+)})$-secure sketch with parameter
$k^{*}\leq{n^{*}}<{k}\leq{n}$ (for sufficiently large $n$). It can correct
fraction of worst-case errors arbitrary close to $1/2$ (i.e.,
$t_{(+)}<\floor{k^{*}/2}$).

###  12.2 Reduction from Fuzzy min-entropy to Shannon entropy

As computational secure sketch implies information theoretic ones, it is
natural to ask how our construction related to the usage of fuzzy min-entropy
in defining the system security. Nonetheless, we here show that Shannon
entropy is indeed a necessary and sufficient condition to show security for
any sources with non-zero min-entropy.

To support our claim that Shannon entropy is necessary and sufficient, we
recall the statement saying that a list of possible RVs in different
distributions
$\\{{\Phi_{1},\ldots,\Phi_{{|\mathsf{supp}(\mathcal{E}_{ss})|}}}\\}\in{\Psi}$
can be generated from a list of possible noisy strings over a family of
distributions
$\\{{W_{1},\ldots,W_{{|\mathsf{supp}(\mathcal{E}_{ss})|}}}\\}\in{\mathcal{W}}$
after the random error parsing. Meanwhile, the original distribution of random
variable $W$ where $w\in{W}$ is concealed in $\mathcal{W}$. Looking for $w$ is
equivalent to look for $W$ over $\mathcal{W}$, which means meaningful security
can be claimed by measuring the minimum fuzzy min-entropy of every possible
distribution for $W$ over $\mathcal{W}$ (after random error parsing). However,
we argued that it is difficult to precisely model all possible distribution,
especially for large entropy distributions. This is because large entropy
sources usually accompany with large input size $k^{*}$ and large number of
points $2^{m^{\prime}}$. Modelling individual distribution of large number of
points $2^{m^{\prime}}$ require high computational cost and computationally
inefficient.

Arguing that the worst-case security should offer maximum probability in
getting similar RVs within maximised tolerance $t_{\max}$ (see Section 8). We
therefore characterize the maximum probability using the conditioned minimum
entropy of the RVs (given the noisy strings). Such result can easily derived
using Hoeffding bound described in Eq. 4, we restate it here:

$\displaystyle\condminentropy{\Psi}{\mathcal{W}}=-\log\bigg{(}{\expsub{W\leftarrow{\mathcal{W}}}{\condprob{\Psi=\Phi}{\mathcal{W}=W}}}\bigg{)}$
$\displaystyle\geq{-\log\bigg{(}\expsub{w^{\prime}\leftarrow{W^{\prime}}}{\max\limits_{\phi^{\prime}}\condprob{\Phi\in{B_{t_{\max}}(\phi^{\prime})}}{W\not\in{B_{t^{\prime}_{(+)}}(w^{\prime})}}}\bigg{)}}$
$\displaystyle\geq{\log(1/\exp{(-2n{\epsilon_{ss}^{2})}})}.$

It is not difficult to see that above equation computes the minimum fuzzy min-
entropy among all possible RVs distributions (over $\Psi$) concerning to
maximum tolerance distance $t_{\max}$ (conditioned on $t^{\prime}_{(+)}$).
Such result yielded a reduction from fuzzy min-entropy to minimum entropy
measurement over the original distribution of the variable $W$ concerning
$t^{\prime}_{(+)}$, hold for all input string $w\in{W}$.

However, merely showing reduction from fuzzy min-entropy to min-entropy is not
enough, our goal is to reduce min-entropy to Shannon entropy. Such reduction
is in fact done with the formalization of Proposition 2 and 3 with
sufficiently $n$ and number of zeros padding $k-n^{*}$. These result
eventually lead us to the derivation of the Shannon bound and GV bound in
computational manner (Eq. 18 and 19). Noting that the derived bounds on Eq. 18
and 19 have removed the $o(1)$ term compared to the actual bounds derived in
[23] [24] [25]:

$\displaystyle R\leq{1-h_{2}(p)}-o(1)\ (actual\ Shannon\ bound)$
$\displaystyle R\geq{1-h_{2}(2p)}-o(1)\ (actual\ GVbound),$

this is mainly because of the exact bound we used for
$p=\epsilon_{ss}\in{[(2k)^{-1},1/4]}$ (for both average and worst-case
scenarios) rather than limiting $p\in{(0,1/4)}$. In light of this, Shannon
entropy is necessary and sufficient condition to show meaningful security for
a standard secure sketch.

##  13 Comparison

Security Bound for Secure Sketch
---
Computational /Info-theoretic |  Best possible security derived in [11] |  $\minentropy{W}\geq{m}\geq\text{H}_{t,\infty}^{\text{fuzz}}{(W)}-\log(1-\beta)$
Computational /Info-theoretic |  FRS sketch(universal hash functions) [11] |  $\minentropy{W}\geq{m}\geq\text{H}_{t,\infty}^{\text{fuzz}}{(W)}-\log(1/{\beta})-\log\log(\mathsf{supp}(W))-1$
Computational /Info-theoretic |  Layer hiding hash (strong universal hash function)[10] |  $\minentropy{W}\geq{m}\geq\text{H}_{t,\infty}^{\text{fuzz}}{(W)}-\log({1}/{\beta})-1$
Info. theoretic |  Fuzzy commitment with generic syndrome decoding [7] |  $\minentropy{W}\geq{t\log(n)}$ (when $t\ll{n}$)
Info. theoretic |  Fuzzy vault [4] |  $\minentropy{W}\geq{t\log(n)}$
Info. theoretic |  Improved Fuzzy vault [6] |  $\minentropy{W}>{t\log(n)+2}$
Info. theoretic |  Pinsketch [6] |  $\minentropy{W}\geq{t\log(n+1)}$
Computational /info-theoretic |  Proposed |  $\minentropy{W}\geq{m}\geq{{{{k^{*}h_{2}{(\epsilon_{rec})}}}}}=H(\mathcal{E}_{rec})$

Table 1: Summary of security bound of existing secure sketch in terms of
fuzzy-min entropy (with $\beta>0$), min-entropy, and Shannon entropy.

Table 1 depicted the security bound (upper bound min-entropy requirement) for
existing secure sketch construction. Compared to the existing secure sketch
constructions our construction is capable of claiming computational security
for all sources with min-entropy $m\geq{1}$.

An important highlight, we showed reduction from fuzzy-min entropy to Shannon
entropy, hence our security can be simplified into merely depends upon the
input error distribution defined using Shannon entropy, i.e.,
$m\geq{H(\mathcal{E}_{rec})}$. More precisely, by definition of min-entropy,
$m$ never larger than $H(\mathcal{E}_{rec})$, thus $m=H(\mathcal{E}_{rec})$ to
be exact, which means Shannon entropy is necessary and sufficient to describe
$m$. Besides, it can be verified easily our derived security bound covered the
best possible security stated in [11] with fuzzy min-entropy
$\text{H}_{t,\infty}^{\text{fuzz}}{(W)}\geq{1}$ (for $m\geq{1}$).

##  14 Conclusion

Existing secure sketch constructions have shown limitation in providing
security for sources with low entropy, i.e., lower than half of its input
size. To overcome such limitation, recent approaches [9], [10] suggested to
construct a secure sketch where its security property only holds for
computationally bounded attacker. Such computational construction relies on
fuzzy min-entropy measurement, accompanies with stringent requirement s.t. the
user must have precise knowledge over the sources distribution. However, under
the practical scenario, many sources, for instance biometric (human face,
iris, and fingerprint) are difficult to model, hence assuming precise
knowledge over such sources is unrealistic.

In this work, we proposed an explicit construction for secure sketch. We
adopted the usage of RV for sketching to facilitate the understanding of the
input distribution. Besides, the noisy environment of any source with minimum
entropy $m\geq{1}$ is stimulated by parsing random error to it. Our
construction supports efficient recovery with bounded probability of error
parametrized by the number of zero padding to the syndrome vector $v_{syn}$.
The recovery algorithm works adversarially and efficiently under an event
where the distribution of the random error $e\in\mathcal{E}_{ss}$ parsed into
the input source is unknown.

For security, we showed reduction from the usage of fuzzy min-entropy to
Shannon entropy to claim security over any sources of min-entropy
$m\geq{H(\mathcal{E}_{rec})}\geq{1}$. Our results allow the computational
derivation of info-theoretic bound (Shannon bound), lead us to the calm over
computational secure sketch implies info-theoretical secure sketch.

## References

  * [1] S. N. Porter, “A password extension for improved human factors,” _Computers & Security_, vol. 1, no. 1, pp. 54–56, 1982.
  * [2] N. Frykholm and A. Juels, “Error-tolerant password recovery,” in _Proceedings of the 8th ACM conference on Computer and Communications Security_. ACM, 2001, pp. 1–9.
  * [3] C. Ellison, C. Hall, R. Milbert, and B. Schneier, “Protecting secret keys with personal entropy,” _Future Generation Computer Systems_ , vol. 16, no. 4, pp. 311–318, 2000.
  * [4] A. Juels and M. Sudan, “A fuzzy vault scheme,” _Designs, Codes and Cryptography_ , vol. 38, no. 2, pp. 237–257, 2006.
  * [5] C. H. Bennett, G. Brassard, and J.-M. Robert, “Privacy amplification by public discussion,” _SIAM journal on Computing_ , vol. 17, no. 2, pp. 210–229, 1988\.
  * [6] Y. Dodis, L. Reyzin, and A. Smith, “Fuzzy extractors: How to generate strong keys from biometrics and other noisy data,” in _International conference on the theory and applications of cryptographic techniques_. Springer, 2004, pp. 523–540.
  * [7] A. Juels and M. Wattenberg, “A fuzzy commitment scheme,” in _Proceedings of the 6th ACM conference on Computer and communications security_. ACM, 1999, pp. 28–36.
  * [8] Y. Dodis and D. Wichs, “Non-malleable extractors and symmetric key cryptography from weak secrets,” in _Proceedings of the forty-first annual ACM symposium on Theory of computing_. ACM, 2009, pp. 601–610.
  * [9] B. Fuller, X. Meng, and L. Reyzin, “Computational fuzzy extractors,” in _International Conference on the Theory and Application of Cryptology and Information Security_. Springer, 2013, pp. 174–193.
  * [10] J. Woodage, R. Chatterjee, Y. Dodis, A. Juels, and T. Ristenpart, “A new distribution-sensitive secure sketch and popularity-proportional hashing,” in _Annual International Cryptology Conference_. Springer, 2017, pp. 682–710.
  * [11] B. Fuller, L. Reyzin, and A. Smith, “When are fuzzy extractors possible?” in _Advances in Cryptology–ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I 22_. Springer, 2016, pp. 277–306.
  * [12] V. Guruswami, _List decoding of error-correcting codes: winning thesis of the 2002 ACM doctoral dissertation competition_. Springer Science & Business Media, 2004, vol. 3282.
  * [13] E. R. Berlekamp, _Algebraic coding theory_. World Scientific Publishing Co, 2015.
  * [14] R. L. Rivest, “Symmetric encryption via keyrings and ecc,” 2016.
  * [15] M. S. Charikar, “Similarity estimation techniques from rounding algorithms,” in _Proceedings of the thiry-fourth annual ACM symposium on Theory of computing_. ACM, 2002, pp. 380–388.
  * [16] A. Gionis, P. Indyk, R. Motwani _et al._ , “Similarity search in high dimensions via hashing,” in _Vldb_ , vol. 99, no. 6, 1999, pp. 518–529.
  * [17] W. W. Peterson and E. J. Weldon, _Error-correcting codes_. MIT press, 1972.
  * [18] A. Vardy, “The intractability of computing the minimum distance of a code,” _IEEE Transactions on Information Theory_ , vol. 43, no. 6, pp. 1757–1766, 1997.
  * [19] R. McEliece and H. Van Tilborg, “On the inherent intractability of certain coding problems(corresp.),” _IEEE Transactions on Information Theory_ , vol. 24, no. 3, pp. 384–386, 1978.
  * [20] V. Guruswami and A. Vardy, “Maximum-likelihood decoding of reed-solomon codes is np-hard,” in _Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms_. Society for Industrial and Applied Mathematics, 2005, pp. 470–478.
  * [21] C. E. Shannon, “Communication theory of secrecy systems,” _Bell system technical journal_ , vol. 28, no. 4, pp. 656–715, 1949.
  * [22] R. M. Karp, “Reducibility among combinatorial problems,” in _Complexity of computer computations_. Springer, 1972, pp. 85–103.
  * [23] R. Varshamov, “Estimate of the number of signals in error correcting codes,” _Docklady Akad. Nauk, SSSR_ , vol. 117, pp. 739–741, 1957.
  * [24] E. N. Gilbert, “A comparison of signalling alphabets,” _The Bell system technical journal_ , vol. 31, no. 3, pp. 504–522, 1952.
  * [25] C. E. Shannon, “A mathematical theory of communication,” _Bell system technical journal_ , vol. 27, no. 3, pp. 379–423, 1948.