In an interactive hashing protocol introduced by Naor et al. [16], the senderS transfers to the receiverR the “hash value”h(y) ofy, where the “hash function”h is chosen (at random) by the receiver from a predetermined function family. The protocol is required to bebinding in the sense thatS is bounded by the protocol to at most one value ofy. This binding requirement can hold is several ways: clearly, binding holds if after the interaction ends there is only a single elementy that is consistent with the hash value. Protocols with this strong binding property are known as “information theoretic” interactive hashing. In contrast, in the computational setting we are interested in the case where a randomhdoes induce many collisions. Thus, we only require the binding property to hold against efficient senders. Assuming thath is taken (at random) from a family of collision resistant hash functions,^Footnote1 the binding property is immediate. In this paper we do not rely on such families, as we do not want to assume their existence. Following [16], we enforce the binding by asking the sender to provide additional information abouty (typically, the honest sender gets this additional information as part of its input).

We formally define the computational binding property in Sect. 3, but in the meanwhile let us consider the following important example: letf be a one-way permutation and view the committed valuey as an image off. For the purpose of binding, we can now require the sender to providex such thaty=f(x) is consistent with the transcript (i.e.,h(y)=z, whereR’s output equals (h,z)). Thus, for breaking the binding of the protocol a cheating sender needs not only outputy₁≠y₂ such thath(y₁)=h(y₂)=z, but it is also required to outputx₁ andx₂ withf(x₁)=y₁ andf(x₂)=y₂. Indeed, using this additional requirement [16] constructs an interactive hashing protocol that allows collisions, but is nevertheless binding (see Sect. 1.1 for more details).

Connection to Statistically Hiding Commitments

Interactive hashing (in the flavor mentioned above) is closely related and to a large extent motivated by the fundamental notion of statistically hiding (and computationally binding) commitments. Statistically hiding commitment schemes are used as building blocks in constructions of statistical zero-knowledge arguments [1,16] and of certain coin-tossing protocols [14]. Naor et al. [16] use their interactive hashing protocol, hereafter the NOVY protocol, in order to construct statistically hiding commitments based on any one-way permutation. Haitner et al. [8] generalized their result by showing that the NOVY protocol can be used to construct statistically hiding commitments based on regular one-way functions (and also on the so called approximable-preimage-size one-way functions). Finally, Haitner et al. [9] constructed statistically hiding commitments based onany one-way function.^Footnote2 Not surprisingly, interactive hashing is heavily used in the underlying commitment scheme of [9].

A possible drawback of [9] is that their construction is rather inefficient and complex. Indeed, a major motivation for looking into interactive hashing is to simplify [9]. Such a simplification was recently given by Haitner et al. [10], critically using the results we present here.

Before discussing our results and their applications, let us have a closer look into the notion of interactive hashing.

1.1Interactive Hashing in the Setting of One-Way Permutations

Letf:{0,1}ⁿ↦{0,1}ⁿ be a one-way permutation and consider the following two-party protocol between a senderS, getting as inputx∈{0,1}ⁿ, and a receiverR. The receiver selects a random (almost) pairwise-independent two-to-one hash functionh:{0,1}ⁿ↦{0,1}ⁿ⁻¹,^Footnote3 and sends its description toS. In return,S sendsz=h(y) back toR, wherey=f(x). Note that if both parties follow the protocol, then the following binding property is guaranteed: it is not feasible forS to findx′∈{0,1}ⁿ such thatf(x′)≠f(x) buth(f(x′))=h(f(x))=z, although (exactly one) such elementx′ does exist. This is since the task of finding suchx′ can be shown (as firstly done in [15]) to be equivalent in hardness to invertingf on a random image (whereas the latter task is assumed to be hard by the one-wayness of f).

What happens, however, ifS selectsx onlyafter seeingh? In such a case, it is quite plausible thatS would be able to “cheat” by producingx,x′∈{0,1}ⁿ such thatf(x)≠f(x′) buth(f(x′))=h(f(x))=z.^Footnote4 The NOVY interactive hashing protocol prevents such cheating. For that, it employs a specific family of hash functions such that each one of its functionsh can be decomposed into (n−1) Boolean functionsh₁,…,h_n−1, whereh(x)=h₁(x),…,h_n−1(x). In the NOVY protocol, instead of sendingh at once as described above, the protocol proceeds in rounds such thatR sends a single Boolean functionh_i in each round, and in returnS sends a bitz_i, which is supposed to equalh_i(f(x)). Intuitively, a cheating sender has a significantly smaller leeway for cheating as it can no longer wait in selectingx till it receives the entire description of h. Still, it is highly non-trivial to argue that restricting the sender by adding interaction as above, is sufficient in order to prevent the sender from cheating. Nevertheless, Naor et al. [16] have shown that their protocol is binding even against a cheating sender (namely, even a cheating sender cannot producex,x′∈{0,1}ⁿ such thatf(x)≠f(x′), buth(f(x′))=h(f(x))=z).

1.1.1Application to Perfectly Hiding Commitments

Naor et al. [16] used their protocol to construct perfectly hiding commitment scheme from one-way permutations, by employing the protocol with a uniformly chosenx as the sender’s input. Lety₀<y₁ be the two preimages of the hash value determined by the protocol (i.e.,y₀,y₁∈h⁻¹(z)) and leti∈{0,1} be such thatf(x)=y_i. The sender commits to a bitb∈{0,1} by masking it withi (i.e., by sendingc=i⊕b to the receiver). In order to decommit, the sender sendsx to the receiver, who setsb=c⊕i, wherei is as above (e.g., the index off(x) in {y₀,y₁}). The above scheme is perfectly hiding since the hash functions used are two-to-one, where the binding property of the scheme easily follows by the binding of the NOVY protocol.

1.2Interactive Hashing in the “Sparse Case”

How about constructing statistically hiding commitments from, say, regular one-way functions (i.e., every possible output has the same number of preimages)? In such a case, we would like to interactively hash a valuey that is taken from\(\operatorname {Im}(f)\), the image off over {0,1}ⁿ, and not from {0,1}ⁿ as in the case of one-way permutations.

Notice that the NOVY theorem guarantees that when hashingy withh:{0,1}ⁿ↦{0,1}ⁿ⁻¹, the sender is committed to a single valuey (even though\(h^{-1}(h(y)) \cap \operatorname {Im}(f)\) might not be a singleton). In the case the\(\operatorname {Im}(f)\) is sparse (i.e.,\(\vert \operatorname {Im}(f)\vert /2^{n} =\operatorname{neg}(n)\)), however, whenh outputs so many bits then it is most likely thath(y)completely determines y. Hence, we cannot hope to use such protocol to get a statistically hiding commitment scheme.

Facing the aforementioned difficulty, Haitner et al. [8] made the following observation: the binding of the NOVY protocol holds for every functionf that it is hard to invert over the uniform distribution on\(\operatorname {Im}(f)\). Furthermore, some weak hiding is guaranteed for everyf such that\(\operatorname {Im}(f)\) is “dense” in {0,1}ⁿ (i.e., of order\(2^{n}/\operatorname{poly}(n)\)). Equipped with this observation, [8] employ the NOVY protocol with length-preserving poly-to-one one-way function (i.e., each output has at most polynomial number of preimages in the image set off) to get some weak form of statistically hiding commitments. which can later be amplified into a full-fledge statistically hiding commitments. To handle any regular one-way function, [8] applies additional layer of (non interactive) hashing to reduce to the dense case. This implies a construction of statistically hiding commitments from any regular one-way function with known image size. Interactive hashing in the sparse case arises in other works as well, most notably in the construction of statistical zero-knowledge arguments from any one-way function [10,17].

1.3Our Results

We consider a variant of the NOVY protocol in which the special family of two-to-one hash functions used by [16] is replaced by any “product” of Boolean families of pairwise independent hash functions (i.e.,h(x)=(h₁(x),…h_k(x)), whereh₁…h_k are taken from such families). Our proof relies in part on the original proof due to [16], but still seems significantly simpler. The new theorem directly applies to the following “sparse case”: letf:{0,1}ⁿ↦{0,1}ⁿ be an efficiently computable function and let\({\mathcal{L}}\subseteq\{0,1\}^{n}\) be sparse. Our theorem applies when hashing to roughly\(s=\lfloor\log (|{\mathcal{L}} |)\rfloor\) bits. In particular, whenh is taken from a family of hash functions\({\mathcal{H}}^{s}\colon \{0,1\}^{n} \mapsto\{0,1\}^{s}\) that is a product ofs families of pairwise-independent Boolean hash functions, the above protocol possesses the following binding property: iff ishard to invert on the uniform distribution over\({\mathcal{L}}\), then no efficient senderS^∗ can find two elements\(x,x'\in f^{-1}({\mathcal{L}})\) such thatf(x)≠f(x′) buth(f(x))=h(f(x′))=z (wherez is the value determined by the protocol ash(y)). As an easy corollary, we use the new theorem to derive a direct construction of statistically hiding commitment based on regular one-way functions of known regularity (and thus reprove [8]).

Our new proof can be easily used to derive a new proof for a close variant of the NOVY protocol introduced by [9], which like the original NOVY protocol uses two-to-one hash functions.

We also note that a product family of pairwise-independent hash functions is not regular (i.e., a function is regular, over a given domain, if all its images have the same number of preimages). As a result, protocols using such families seem only to be useful for obtainingstatistically hiding commitments.

The parameters achieved by our proof are an improvement compared with the original ones: given an algorithmA that breaks the binding property with probabilityε_A(n), we get an algorithm that inverts the one-way permutation in comparable time and with inverting probability\(\varepsilon_{\mathsf{A}}^{2}(n)/\operatorname{poly}(n)\) (wheren is the hash function input length). This is an improvement over the\(\varepsilon_{\mathsf{A}}^{10}(n)/\operatorname{poly}(n)\) and the\(\varOmega(\varepsilon_{\mathsf{A}}(n)^{3}/\operatorname{poly} (n))\) reductions of [16] and [17], respectively, and is close to natural limitations of the proof technique (see discussion in Sect. 5).

Finally, we consider interactive hashing protocols that use hash functions of arbitrary output length, and not necessarily Boolean. Given a one-way function that is hard to invert over the uniform distribution by algorithms of running-time 2^ℓ, our approach yields an interactive hashing protocol ofn/ℓ rounds. When applied to one-way permutations, the resulting protocol matches the recent black-box lower bounds of Wee [21] and Haitner et al. [7], and generalizes the one-way permutation-basedO(n/logn)-round protocol of [13].

1.4Related Work

Independently of our work, Nguyen et al. [17] gave a new proof for the NOVY protocol. Their proof follows the proof of [16] more closely than ours, but still introduces various simplifications and parameter improvements. The main goal of their new proof was to generalize the protocol such that it allows hashing with a hash function that is poly-to-one (rather than two-to-one as in [16]). The result of [17] (and of [16]), however, do not extend to the sparse case settings we considered above, where this limitation seems inherent to their proof technique.

More recently, Haitner et al. [9] consider a variant of the NOVY protocol that uses a different type of two-to-one hash functions. Specifically, the functions induced by the families of full-rank matrices mapping {0,1}ⁿ to {0,1}ⁿ⁻¹, where the operationh(x) is interpreted ash×x. While such families provide the same hiding guarantee for the resulting protocol as the special two-to-one functions considered by [16,17], the advantage is that the binding property of the protocol can be easily reduced to that of a protocol using families of pairwise-independent hash functions. In particular, [9] show how to derive the security of this variant from our main result.

In this work we focus on security with respect to bounded senders and unbounded receivers. The setting where both the receiver and the sender are unbounded, calledinformation theoretic interactive hashing (also known as,interactive hashing for static sets), and its applications (cf., [4,18–20]) are not treated by this work. See [9, Sect. 3.2] for more details regarding information theoretic interactive hashing and its connection to the computational setting.

1.5Proof Idea

We outline our binding proof in the most basic setting wheref:{0,1}ⁿ↦{0,1}ⁿ is a one-way permutation and\({\mathcal {L}}= \{0,1\}^{n}\). Letx∈{0,1}ⁿ beS’s input and lety=f(x). Our protocol consists of (n−1) rounds, in each roundR selects a random Boolean pairwise-independent hash functionh_i andS replies with z_i=h_i(y).

Assume there exists an algorithmS^∗ that plays the sender’s role in the protocol and cheats with non-negligible probability. Namely, with such probabilityS^∗ outputs at the end of the protocol two elementsx₀,x₁∈{0,1}ⁿ such thaty₀=f(x₀) is different fromy₁=f(x₁), and bothy₀ andy₁ are consistent with the transcript. Consider the following naive way one may try to invertf usingS^∗: given an inputy, choose the hash functionsh₁,…,h_n−1 to be used byR at random, and return one of the two elements thatS^∗ outputs in the end of the interaction withR. In the case thaty is consistent withS^∗’s answer, then we are in good shape: there should be only few elements that are consistent withS^∗’s answers, and therefore with good probability eithery₀ ory₁ output byS^∗’s is equal toy. Unfortunately, the probability ofy to be consistent withS^∗’s answers is very small; at each round, the probability thaty is consistent withS^∗ is typically bounded by \(\frac{1}{2}\).

The above motivates the following reduction: in theith round feedS^∗ keep sampling a random hash functionh_i, until its answer is consistent withy. IfS^∗ behaves randomly, or acts according to the honest strategy with respect to some fixed inputy′, then no more than few such attempts are required for each round. For arbitrary adversaries, however, the above analysis seems to fail; as the process of choosing theh_i’s proceeds, the distribution ofy (chosen at random from the image off) gets further away from being uniform among the elements that are consistent withS^∗’s answers.

The actual reduction (following [16]) interpolates the two: we use the second reduction for the firstt rounds, and the first reduction for the lastn−t rounds, wheret=n−O(logn) is carefully chosen to circumvent both the above obstacles.^Footnote5 The novelty in our new proof, highlighted below, is in the way we analyze the success probability of this combined reduction.

Analyzing the Reduction Success Probability

Given a vector of Boolean hash functions\({\overline{h}}= (h_{1},\dots,h_{t} )\), let\({\mathrm{Consist}}({\overline{h}}) :=\{y'\in\{0,1\}^{n} \colon\forall i\in[t] \ h_{i}(y') = {{\mathsf{S}^{\ast}}}(h_{1},\dots ,h_{i})\}\). (I.e.,\({\mathrm{Consist}}({\overline{h}})\) is the subset of elements inside {0,1}ⁿ that are consistent withS^∗’s responses on\({\overline{h}}\).) LetD_Real be the distribution induced by the first part of the above reduction on the tuple\(({\overline{h}},y)\). That is,y is uniformly chosen in {0,1}ⁿ, and then\({\overline{h}}\) is chosen using rewinding so that\(y\in {\mathrm{Consist}}({\overline{h}})\). Given this formulation, the reduction success probability is simply the success probability of the following algorithm (hereafter, theInverter) overD_Real: given a tuple\(({\overline{h}},y)\), choose\({\overline{h}}' = (h_{t+1},\dots ,h_{n-1})\) at random, and returnf⁻¹(y) if it is one of the two outputs ofS^∗ on\(({\overline{h}},{\overline{h}}')\).

To analyze the above success probability we introduce the distributionD_Ideal: first\({\overline{h}}= (h_{1},\dots ,h_{t})\) is chosen at random, and only then a random elementy is uniformly drawn from\({\mathrm{Consist}}({\overline{h}})\). Since the distribution of\({\overline {h}}\) underD_Ideal is as induced by a random interaction ofS^∗ withR (i.e., uniform at random), it is easy to see thatInverter does well onD_Ideal (roughly\(\varepsilon/|{\mathrm{Consist}}({\overline{h}})|\), for a uniformly chosen\({\overline{h}}\)). We would then have concluded the proof if we could have proved that the statistical difference betweenD_Ideal andD_Real is small enough. It turns out, however, that such a strong bound is unlikely to hold as it would imply that one-way functions do not exist!^Footnote6

We do mange to prove, however, thatD_Ideal is almost “dominated” byD_Real: the mass thatD_Ideal assigns to most tuples is not too much larger (multiplicatively) than their mass underD_Real. This observation turns out to be sufficient, since when taking into account the full power ofS^∗ (i.e., that it finds two consistent outputs) we prove thatInverter does “well” on most tuples in the support ofD_Ideal. Combining the above observations, it follows thatInverter does well also onD_Real.

1.6Paper Organization

General notation and definitions used throughout the paper are given in Sect. 2. In Sect. 3, we formally define interactive hashing, present the NOVY paradigm for such protocols, and state our main theorem regarding the binding of such protocols. The proof of this theorem is given in Sect. 4, where discussion and further issues appear in Sect. 5. Finally, in Appendix A we show how to use our new theorem to derive a direct construction of statistically hiding commitment scheme based on regular one-way functions.

2.1Notation

We use calligraphic letters to denote sets, uppercase for random variables, and lowercase for values. Forn∈ℕ, let [n]={1,…,n}. Given a binary relation\({\mathcal {W}}\subseteq {\mathcal{D}}_{1} \times{\mathcal{D}}_{2}\) and\(y\in{\mathcal{D}}_{2}\), let\({\mathcal {W}}_{y} = \{x\in{\mathcal{D}}_{1} \colon(x,y) \in{\mathcal{W}}\}\). Letpptm denote a probabilistic algorithm (i.e., Turing machines) that runs instrict polynomial time and let\(\operatorname{poly}\) denote the family of polynomials (we sometimes abuse notation and view\(\operatorname{poly}\) as an arbitrary polynomial). Throughout we identify functions with their description, and assume without loss of generality that such a description is a binary string.

Given a random variableX, letx←X denote thatx is selected according toX. Similarly given a finite set\({\mathcal{S}}\), let\(s\gets{\mathcal{S}}\) denote thats is selected according to the uniform distribution on \({\mathcal{S}}\). We adopt the convention that when the same random variable occurs several times in an expression, all occurrences refer to a single sample. For example, Pr[f(X)=X] is defined to be the probability that whenx←X, we havef(x)=x. Given a distributionD over a set\({\mathcal{S}}\), the support ofD is defined as\(\operatorname{Supp}(\mathsf{D}) :=\{s\in{\mathcal{S}}\colon \mathsf{D}(s) > 0\}\) and its min entropy, denoted\(\operatorname{H_{\infty}}(\mathsf{D})\), is defined as\(\min_{x\in X} \log \frac{1}{\mathsf{D}(x)}\). Finally, the statistical distance of two distributionsP andQ over a final set\({\mathord {\mathcal{U}}}\), denotedSD(P,Q), is defined as\(\frac{1}{2} \sum_{u\in{\mathord{\mathcal{U}}}}|{\mathsf{P}}(u)- {\mathsf{Q}}(u)|\).

Aninteractive protocol (A,B) consists of two interactive algorithms (touring machines) that compute the next-message functions of the (honest) parties in the protocol. Let (A(a),B(b))(x) denote the random process obtained by havingA andB interact on common inputx, with (private) auxiliary inputsa andb toA andB, respectively, and with independent random coin tosses forA andB. The protocol (A,B) runs in polynomial time, if there is a polynomialp such thatA halts in (A(⋅),⋅)(x), and similarlyB halts in (⋅,B(⋅))(x), after at mostp(|x|) rounds for all possible inputx∈{0,1}^∗ (regardless of its private input and the other party strategy). Let\(\operatorname{view}_{\mathsf{A}}(\mathsf{A}(a),\mathsf {B}(b))(x)\) denotesA’sview of the interaction, i.e., its values are transcripts (γ₁,γ₂,…,γ_t;r), where theγ_i’s are all the messages exchanged andr isA’s coin tosses. Similarly,\(\operatorname{view}_{\mathsf{B}}(\mathsf {A}(a),\mathsf {B}(b))\) denotesB’s view.

2.2Efficient Function Families

To be useful in applications, ensembles of function families are typically required to be “efficient”. For our needs, efficiency means the following.

Definition 2.1

(Efficient ensembles of function families)

Let\({\mathcal{H}}= \{{\mathcal{H}}_{n}\}_{n\in{\mathbb{N}}}\) be an ensemble of function families mapping strings of lengthn to strings of lengthℓ(n). The ensemble\({\mathcal{H}}\) isefficient, if the following hold:

Samplable.:

There exists apptm that, given 1ⁿ, returns a uniform element in\({\mathcal{H}}_{n}\).

Efficient.:

There exists a polynomial-time algorithm that givenx∈{0,1}ⁿ and a description of\(h \in{\mathcal{H}}_{n}\), outputsh(x).

Verifiable.:

There exists a polynomial-time algorithm that givenh∈{0,1}^∗ and 1ⁿ, outputs ‘1’ iff\(h \in{\mathcal{H}}_{n}\).

Throughout we use the shorthand “efficient function families” for “efficient ensembles of function families”.

2.3Pairwise Independent Function Families

Definition 2.2

(Pairwise-independent families)

Let\({\mathcal{H}}\) be a function family mapping strings of lengthn to strings of lengthℓ. The family\({\mathcal{H}}\) ispairwise independent, if

for every distinctx₁,x₂∈{0,1}ⁿ and everyy₁,y₂∈{0,1}^ℓ.

It is well known Carter and Wegman [2] that for every polynomial-time computable\(\ell(n) \leq\operatorname{poly}(n)\), there exists anefficient family of pairwise-independent hash functions with description sizeO(max{n,ℓ(n)}).

The following standard lemma states that a random pairwise-independent hash function partitions a given set into (almost) equal size subsets.

Lemma 2.3

Let\({\mathcal{H}}\)be a pairwise-independent function family mapping strings of lengthnto strings of lengthℓ,let\({\mathcal{L}}\subseteq {\{0,1\}^{n}}\),let\(\mu= \vert {\mathcal{L}}\vert /2^{\ell}\)and letδ>0.Then

Proof

Fixy∈{0,1}^ℓ and letH be uniformly chosen in\({\mathcal{H}}\). For\(x\in {\mathcal{L}}\), define the indicatory random variableI_x to be one iffH(x)=y, and let\(X = \sum_{x\in{\mathcal{L}}} I_{x}\). Since E[I_x]=2^−ℓ for every\(x\in{\mathcal{L}}\), it follows that E[X]=μ.

Note that\(\operatorname{Var}[I_{x}]= {\mathrm{E}}[I_{x}^{2}]- {\mathrm{E}}[I_{x}]^{2} = {\mathrm{E}}[I_{x}](1 - {\mathrm{E}} [I_{x}]) \leq{\mathrm{E}}[I_{x}]\) for every\(x\in{\mathcal{L}}\), where the pairwise independence of theI_x’s^Footnote7 yields\(\operatorname{Var}[X] = \operatorname{Var}[\sum_{x\in{\mathcal{L}}} I_{x}] = \sum_{x\in {\mathcal{L}}} \operatorname{Var}[I_{x}] \leq\sum_{x\in{\mathcal{L}}} {\mathrm{E}}[I_{x}] = {\mathrm{E}}[X]\). Applying the Chebyshev inequality

and a union bound completes the proof. □

2.4Linear Transformations

Other function families of interest are those of a linear transformation.

Definition 2.4

(Linear transformations)

Givenn,ℓ∈ℕ,M∈{0,1}^ℓ×n andx∈{0,1}ⁿ, letM(x):=M×xmod2, and let Lin_ℓ,n be the function family defined by all matrices in {0,1}^ℓ×n with respect to the above operation. We let\(\operatorname{Full}_{\ell,n} \subseteq \mathrm{Lin}_{\ell ,n}\) be the function family defined by allfull-rank matrices in {0,1}^ℓ×n.

Note that both Lin_ℓ,n and\(\operatorname {Full}_{\ell,n}\), are efficient families for any polynomial-time computable\(\ell= \ell (n) < \operatorname{poly}(n)\). We use the following fact.

Fact 2.5

There exists a constantc>0such that\(\frac{\vert \operatorname {Full}_{\ell,n}\vert }{\vert \mathrm{Lin}_{\ell,n}\vert } > c\)for any integersℓ≤n.

Proof

The probability that a random vector in {0,1}ⁿ is in the span of somek<n vectors in {0,1}ⁿ (over\({\mathbb{F}}_{2}\)), is bounded by 2^k−n. It follows that

 □

2.5Piece-Wise Functions

In the interactive hashing protocols considered below, the receiver sends the function description in pieces, where each such piece suffices for evaluating the output it contributes.

Definition 2.6

Given a sequence of functions\({\overline{h}}= (h_{1},\dots,h_{s})\) defined over {0,1}ⁿ, let\({\overline{h}}(x) = h_{1}(x)\circ\dots \circ h_{s}(x)\), where ∘ denotes string concatenation. A family of lengths function sequences, is calleds-piece function family.

An ensemble\({\overline{{\mathcal{H}}}}= \{{\overline{{\mathcal {H}}}}_{n}\}\) ofs=s(n)-piece function families is calledprefix verifiable, if there exists a polynomial-time algorithm that given (1ⁿ,h₁,…,h_i) returns ‘1’ iff there existsh_i+1,…,h_s such that\((h_{1},\dots,h_{s}) \in{\overline {{\mathcal{H}}}}_{n}\).

In this paper we consider two kinds of prefix verifiable piece-wise family. The first type is a product family ensemble\({\mathcal{H}}^{s} \), where\({\mathcal{H}}\) is an efficient function family ands is polynomial-time computable integer-valued function. It is easy to verify that\({\mathcal{H}}^{s} \) is indeed an efficient prefix verifiables-piece family.

The second type is a variant of linear maps; given a subset\({\mathcal {H}}\) of Lin_ℓ,n and an index set\(\overline{i} = (i_{1},\dots ,i_{s} )\) with 1≤i₁<…<i_s=ℓ, let\({\mathcal {H}}_{\overline {i}}\) be thes-piece function family

letting

For polynomial-time computable index-set function\(\overline{i} = \overline{i}(n) = (i_{1}(n),\dots,i_{s(n)}(n))\) and integer-valued function\(\ell= \ell(n) < \operatorname{poly}(n)\), it is easy to verify that thes-piece function family ensemble\((\mathrm {Lin}_{\ell (n),n})_{\overline{i}(n)}\) and\((\operatorname{Full}_{\ell (n),n})_{\overline {i}(n)}\) are both efficient and prefix verifiable.

Following [17], we state our result in the language of binary relations, where these relations are not assumed to have efficient deciders. Since every functionf defines the binary relation {(x,f(x)):x∈{0,1}^∗}, our result yields an analogous result for functions.

Definition 3.1

(Interactive hashing protocols [16,17])

Let\({\mathcal{H}}\) be an ensemble of function families mapping strings of lengthn to strings of lengthℓ=ℓ(n). An\({\mathcal{H}} \)-interactive hashing protocol is a polynomial-time protocol (S,R) such that the following holds: the parties receive the security parameter 1ⁿ as a common input, andS getsy∈{0,1}ⁿ as a private input. At the end,R outputs\((h, z)\in{\mathcal{H}}\times\{0,1\}^{\ell}\).

We make the following correctness requirement: for alln∈ℕ,y∈{0,1}ⁿ and a pair (h,z) that may be output by (S(1ⁿ,y),R(1ⁿ)), it is the case thath(y)=z.

An interactive hashing protocol is said to be (T,δ)-binding if the following holds.

Definition 3.2

LetT:ℕ↦ℕ andδ:ℕ×ℝ×[0,1]↦[0,1]. An\({\mathcal{H}}\)-interactive hashing protocol (S,R) is said to be (T,δ)-binding, if there exists an oracle-aided algorithmpptm A such that the following hold for anyn∈ℕ and any adversaryS^∗. First, the running time of\(\mathsf{A}^{{\mathsf{S}^{\ast}}}(y)\) is bounded byT(|y|) (counting oracle calls as a single operation). Second, let (h,z) and ((x₀,y₀),(x₁,y₁)) denote the common output andS^∗’s private output in (S^∗,R)(1ⁿ), respectively, then for any set\({\mathcal{L}} \subseteq{\{0,1\}^{n}}\) and any binary relation\({\mathcal{W}}\subseteq\{0,1\}^{\ast}\times{\mathcal {L}}\), if

(1)

then

(2)

Note that the above definition isblack-box (i.e., the security reduction is a uniform algorithm that accesses the adversary as an oracle). By considering such a definition, however, we only strengthen our positive results. Also note that a\((\operatorname {poly}(n),\operatorname{poly}(\varepsilon )/\operatorname{poly} (n,\frac{\vert \mathcal{L}\vert }{2^{\ell}}))\)-binding protocol is “polynomially secure” for the set ensemble\({\mathcal{L}}= {\mathcal{L}}(n)\) with\(\frac{\vert \mathcal{L}\vert }{2^{\ell}} \in\operatorname{poly}(n)\)—on security parameter 1ⁿ, nopptm  breaks the binding with more than negligible probability.

The above correctness and binding definitions are oblivious to the actual implementation of the protocol. Since Definition 3.1 does not specify the amount of information that might leak to the (possibly cheating) receiver, stating a similar hiding property is more challenging. Thus, rather than giving a generic (and hard to digest) hiding definition, we separately analyze the hiding guarantee achieved by each of the different constructions considered below.

3.1The NOVY Paradigm

All the interactive hashing protocols considered in this paper follows the NOVY paradigm, which is a natural generalizations of the NOVY protocol. The NOVY paradigm instantiated with ans-piece family\({\overline{{\mathcal{H}}}}\) over strings of lengthn, denoted\({\operatorname{NOVY}\langle{\overline{{\mathcal{H}}}}\rangle}\), is defined as follows:

Protocol 3.3

\({\operatorname{NOVY}\langle{\overline{{\mathcal{H}}}}\rangle}\)

\(\mathbf{Common\ input}\)::

1ⁿ.

S’sinput::

y∈{0,1}ⁿ.

1. 1.

   Rchooses uniformly at random\({\overline{h}}= (h_{1},\dots ,h_{s}) \in{\overline{{\mathcal{H}}}}\).

2. 2.

   Do fori=1tos:

   1. (a)

      Rsendsh_itoS.

   2. (b)

      Saborts if (h₁,…,h_i)is not a prefix of some element in\({\overline{{\mathcal{H}}}}\).

      Otherwise,Ssendsz_i=h_i(y)back toR.

3. 3.

   Routputs\(({\overline{h}},\overline{z}= (z_{1},\dots,z_{s}))\).

Typically, we instantiated the NOVY paradigm with efficient, prefix-verifiable,s-piece families. It is straightforward that for such families, the resulting protocol is an\({\overline{{\mathcal {H}}}}\)-interactive hashing.

3.1.1Hiding of the NOVY Paradigm

The above definition stipulates that the only information a cheating receiver gets from an execution is (h,h(y)) for some\(h\in{\overline {{\mathcal{H}}}}\). While thish might be chosenadaptively by the cheating receiver, we still have the following guarantee.

Claim 3.4

Let\({\overline{{\mathcal{H}}}}\)be ans-piece function family mapping strings of lengthnto strings of lengthℓand let\((\mathsf{S},\mathsf{R}) = {\operatorname {NOVY}\langle{\overline{{\mathcal{H}}}}\rangle}\).Let\({\mathcal {L}}\subseteq{\{0,1\}^{n}}\)and let\(q = \lfloor\log \vert {\mathcal{L}}\vert \rfloor- \ell\).Then for any cheating adversaryR^∗andδ∈(0,1],we have

whereYis uniformly distributed over\({\mathcal{L}}\)and\(V_{\mathsf{R}^{\ast}}\)isR^∗’s view in (S(Y),R^∗).

Proof

SinceS refuses to send more thanℓ bits of information about its input, the proof follows using a straightforward counting argument. □

When limiting our attention to product of pairwise-independent function families and semi-honest receivers (ones that follow the prescribed protocol), we have the following guarantee:

Claim 3.5

Let\({\overline{{\mathcal{H}}}}\)be ans-piece pairwise-independent function family mapping strings of lengthnto strings of lengthℓ,and let\((\mathsf{S},\mathsf{R}) = {\operatorname{NOVY}\langle{\overline {{\mathcal{H}}}}\rangle }\).Let\({\mathcal {L}}\subseteq{\{0,1\}^{n}}\)and let\(q = \lfloor\log \vert {\mathcal{L}}\vert \rfloor- \ell \).Then

whereYis uniformly distributed over\({\mathcal{L}}\)andV_RisR’s view in (S(Y),R).

Proof

Immediately follows by Lemma 2.3 (taking\(\delta= \frac{1}{2}\)). □

Finally, for the family\(\operatorname{Full}_{\ell,n}\) and the set\({\mathcal {L}}= {\{0,1\}^{n}}\), we have the following “perfect” hiding guarantee (formally stated and proved below): (1) the inputy ofS is perfectly hidden among (at least) 2^n−ℓ other values in {0,1}ⁿ, and (2) the “index” ofy among these values is efficiently computable fromy. In the interesting case ofn−ℓ=1, it follows that the index ofy is a uniform bit from the receiver point of view. Such an hiding guarantee is equivalent to that achieved by the NOVY protocol, and in particular can be use to construct perfectly hiding commitment schemes from one-way permutations.

Claim 3.6

There exists a deterministic polynomial-time computable mappingMsuch that the following holds:let\((\operatorname{Full}_{\ell ,n})_{\overline {i}}\)be ans-piece function family,and let\((\mathsf{S},\mathsf {R}) = {\operatorname{NOVY}\langle(\operatorname{Full}_{\ell ,n})_{\overline{i}} \rangle}\).Then for any cheating adversaryR^∗,the distributions\((V_{\mathsf{R}^{\ast}}(y),\mathsf{M}(\ell ,T(y),y) )_{y\gets{\{0,1\}^{n}}}\)and\((V_{\mathsf{R}^{\ast}}(y),z )_{y\gets {\{0,1\}^{n}},z\gets \{0,1\} ^{n-\ell}}\)areidentical,where (the jointly distributed)T(y)and\(V_{\mathsf{R}^{\ast}}(y)\),are the transcript andR^∗’s view,respectively,in (S(y),R^∗).

Proof

We assume for ease of notation thatR^∗ never causes the sender to abort. Given a transcript\(t= ({\overline{h}},\overline{z})\in(\operatorname{Full}_{\ell ,n})_{\overline{i}} \times\{0,1\}^{\ell}\) of (S,R^∗) and an inputy∈{0,1}ⁿ, algorithmM finds\({\overline{h}}' \in\mathrm{Lin}_{n-\ell,n}\) such that the matrix\(\big( \begin{array}{c} \scriptstyle {\overline{h}}\\[-3pt] \scriptstyle {\overline{h}}' \end{array}\big)\) is of full rankn,^Footnote8 and outputs\({\overline{h}}'(y)\). Conditioned onR^∗’s view, the sender’s input (i.e.,y) is uniformly distributed in the (n−ℓ)-dimensional affine subspace\(\{y' \colon{\overline {h}}(y) = \overline{z}\}\). Hence,M(ℓ,t,y) is uniformly distributed in {0,1}^n−ℓ. □

3.1.2Binding of the NOVY Paradigm

The following theorem, whose proof is given in Sect. 4, is the main contribution of this paper.

Theorem 3.7

Let\({\mathcal{H}}\)be an efficient pairwise-independent function family mapping strings of lengthnto strings of lengthℓ=ℓ(n),and lets=s(n)be a polynomial-time computable function.Then\({\operatorname{NOVY}\langle{\mathcal{H}}^{s} \rangle }\)is (T,δ)-binding,whereT(n)=p(n)⋅2^ℓfor some\(p\in\operatorname{poly}\)and\(\delta (n,r,\varepsilon) \in\varOmega (\varepsilon^{2} \cdot\min \{1,1/r\} \cdot \frac{1}{2^{10\ell}\cdot n^{8}} )\).

Theorem 3.7 also holds for function families of weaker independence guarantee.

Definition 3.8

(XOR-universal function families)

Let\({\mathcal{H}}\) be a function family mapping strings of lengthn to strings of lengthℓ. We say that\({\mathcal{H}}\) isXOR-universal if

for any distinctx₁,x₂∈{0,1}ⁿ and anyy∈{0,1}^ℓ.

We note that while not pairwise independent (maps 0ⁿ to 0^ℓ), the family Lin_ℓ,n is XOR-universal for every choice of ℓ and n.

Corollary 3.9

LetT,δ,sandℓbe as in Theorem 3.7.Then the following protocols are (T,δ)-binding:

1. 1.

   \({\operatorname{NOVY}\langle{\mathcal{H}}^{s} \rangle}\),where\({\mathcal{H}}\)is an efficient XOR-universal function mapping strings of lengthnto strings of lengthℓ=ℓ(n).

2. 2.

   \({\operatorname{NOVY}\langle(\operatorname{Full}_{s\cdot\ell ,n})_{\ell,2\ell,\dots,s\cdot\ell} \rangle}\),wheres⋅ℓ≤n.

Proof

The proof of the first part readily follows from the proof of Theorem 3.7. Yet for the sake of completeness we prove it below by reducing it to (the statement of) Theorem 3.7. LetS^∗ be an algorithm that breaks the binding of\({\operatorname{NOVY}\langle{\mathcal{H}}^{s} \rangle}\) with probabilityε (according to Eq. (1)) and let\({\mathcal{H}}'\) be the pairwise independent family\(\{(h,\overline{b}) \colon h\in{\mathcal{H}}, \overline{b}\in{\{0,1\}^{\ell }}\}\), where\((h,\overline{b})(x) :=h(x) \oplus \overline {b}\). Consider the following algorithm that usesS^∗ to break the binding of\({\operatorname{NOVY}\langle({\mathcal{H}}')^{s} \rangle}\): upon receiving the function\((h,\overline{b})\in{\mathcal{H}}'\) fromR, it sendsh toS^∗, XORs the answer ofS^∗ with\(\overline{b}\) and sends the result back toR. It is immediate that the above algorithm breaks the binding of\({\operatorname{NOVY}\langle{{\mathcal{H}}'}^{s} \rangle}\) with probabilityε, and thus the proof of this part follows from Theorem 3.7.

Fact 2.5 yields the following any algorithm that breaks the binding of\({\operatorname{NOVY}\langle(\operatorname{Full}_{s \cdot\ell,n})_{\ell,2\ell,\dots,s\cdot\ell} \rangle}\) with probabilityε, breaks that of\({\operatorname{NOVY}\langle(\mathrm{Lin}_{\ell,n})_{\ell,2\ell ,\dots,s\cdot\ell} \rangle}\) with probabilityΩ(ε) (i.e., conditioned on an event of constant probability over the execution of\({\operatorname{NOVY}\langle (\mathrm{Lin}_{s\cdot\ell,n})_{\ell,2\ell,\dots,s\cdot\ell} \rangle}\), the receiver’s messages in\({\operatorname{NOVY}\langle(\mathrm{Lin}_{s\cdot\ell ,n})_{\ell,2\ell,\dots,s\cdot\ell} \rangle}\) are distributed exactly as the receiver’s messages in\({\operatorname{NOVY}\langle(\operatorname{Full}_{\ell,n})_{\ell ,2\ell,\dots,s\cdot\ell} \rangle}\)). Since (Lin_s⋅ℓ,n)_{ℓ,2ℓ,…,s⋅ℓ} is XOR-universal, the first part of Corollary 3.9 shows that\({\operatorname{NOVY}\langle(\mathrm{Lin}_{\ell ,n})_{\ell,2\ell,\dots,s\cdot\ell} \rangle}\) is (T,δ)-binding, and therefore so is\(\operatorname{NOVY}\langle(\operatorname{Full}_{s\cdot\ell },n)_{\ell,2\ell,\dots,s\cdot\ell} \rangle\). □

Remark 3.10

(Further extensions and the original NOVY protocol)

Consider ans-piece function family\({\overline{{\mathcal{H}}}}\) over {0,1}ⁿ, where each piece outputsℓ bits. For\(\overline{z}\in\{0,1\}^{k\ell}\) and ak-element vector\({\overline{h}}\) that is a prefix of some element in\({\overline{{\mathcal{H}}}}\), define\({\mathrm {Consist}}_{{\overline{h}},\overline{z}} :=\{x\in{\{0,1\}^{n}}: {\overline{h}}(x) = \overline{z}\}\). Assume that for any possible such pair, the family\({\mathcal{H}}_{\overline{h}}= \{h\colon({\overline{h}},h) \mbox{ is a prefix of some element in } {\overline{{\mathcal{H}}}}\}\) is an efficient XOR-universal over\({\mathrm{Consist}}_{{\overline {h}},\overline {z}}\),^Footnote9 then the proof of Theorem 3.7 readily extends to the family \({\overline{{\mathcal{H}}}}\).

The above extension is of interest since it applies to the function family used by the original NOVY protocol. Since protocol\({\operatorname{NOVY}\langle(\operatorname{Full}_{s\cdot\ell },n)_{\ell,2\ell,\dots,s\cdot\ell} \rangle}\) achieves the same hiding guarantee as the NOVY protocol does, we do not formally prove the above observation.

Let\({\mathcal{H}}= \{{\mathcal{H}}_{n}\}_{n\in{\mathbb{N}}}\) be an efficient function family mapping strings of lengthn to strings of lengthℓ(n), whereℓ(n) is an arbitrary integer-valued function, and let\((\mathsf {S},\mathsf{R} ) = {\operatorname{NOVY}\langle{\mathcal{H}}^{s(n)} \rangle}\), wheres is a polynomial-time computable integer-valued function. For integer-valued functiont(n)≤s(n) to be determined by the analysis, we define the following oracle-aided algorithm.

Algorithm 4.1

(A)

Input: :

y∈{0,1}ⁿ.

Oracle: :

S^∗.

1. 1.

   Let\({\overline{h}}\gets\mathsf{Searcher}^{{\mathsf{S}^{\ast}}}(y)\).

2. 2.

   Return\(\mathsf{Inverter}^{{\mathsf{S}^{\ast}}}({\overline{h}})\).

The oracle-aided algorithmsSearcher andInverter are defined as follows:

Algorithm 4.2

(Searcher)

Input: :

y∈{0,1}ⁿ.

Oracle: :

S^∗.

1. 1.

   Fork=1 tot(n) do:

   Do the following for ⌈2^ℓ(n)⋅lnt(n)⌉ times:

   1. (a)

      Let\(h_{k} \gets{\mathcal{H}}_{n}\).

   2. (b)

      Break the inner loop ifS^∗(1ⁿ,h₁,…,h_k)=h_k(y), whereS^∗(1ⁿ,h₁,…,h_k) stands forS^∗ answer on input 1ⁿ and receiver’s messagesh₁,…,h_k.

   If the end of the inner loop has reached, output “Fail” andabort the execution.

2. 2.

   Return (h₁,…,h_t).

Algorithm 4.3

(Inverter)

Input: :

\({\overline{h}}\in{\mathcal{H}}^{t(n)}_{n}\).

Oracle: :

S^∗.

1. 1.

   Let\({\overline{h}}' \gets{\mathcal{H}}^{s(n) - t(n)}_{n}\).

2. 2.

   Let ((x₀,y₀),(x₁,y₁)) be the final output of\({{\mathsf {S}^{\ast}} }(1^{n},({\overline{h}},{\overline{h}}'))\).

3. 3.

   Returnx₀ with probability\(\frac{1}{2}\), andx₁ otherwise.

It is straightforward that\(\mathsf{A}^{{\mathsf{S}^{\ast}}}\) runs in time\(\operatorname{poly}(n) \cdot2^{\ell(n)}\) (counting an oracle call as a single operation). In the following we fixn∈ℕ, a set\({\mathcal {L}}\subseteq{\{0,1\}^{n}} \) and a binary relation\({\mathcal{W}}\subseteq\{0,1\}^{\ast}\times{\mathcal {L}}\). We also fix a cheating senderS^∗ that breaks the binding of\({\operatorname {NOVY}\langle{\mathcal{H}}^{s} \rangle}\) with probabilityε with respect to\({\mathcal{W}}\) and\({\mathcal {L}}\) (according to Definition 3.2). Namely,

(3)

We assume without loss of generality thatS^∗ is deterministic (the generalization to randomized adversaries is standard) and prove the theorem showing that

(4)

for a universal constantc>0.

Throughout the proof we omitn from the notations, and letA,Searcher andInverter, stand for\(\mathsf {A}^{{\mathsf{S}^{\ast}}}\),\(\mathsf{Searcher}^{{\mathsf{S}^{\ast}}}\) and\(\mathsf {Inverter}^{{\mathsf{S}^{\ast}}}\), respectively. We assume without loss of generality thatS^∗ always replies with valid messages (i.e., elements inside {0,1}^ℓ). First time readers are encouraged to focus on the case whereℓ=1,s=n and\({\mathcal{L}}= {\{0,1\}^{n}}\).

Following the intuition given in the introduction, we consider the success probability ofS^∗ with respect to the following distributions:

• \(\mathsf{D}_{\mathrm{Real}}:= ({\overline{h}},y )_{y\gets{\mathcal{L}}, {\overline{h}}\gets\mathsf{Searcher}(y)}\), and

• \(\mathsf{D}_{\mathrm{Ideal}}:= ({\overline{h}},y )_{{\overline {h}}\gets{\mathcal{H}}^{t},y \gets{\mathrm{Consist}}({\overline{h}})}\),

where\({\mathrm{Consist}}({\overline{h}}):=\{y\in{\mathcal {L}}{\ : \ }{\overline{h}}(y) = {{\mathsf{S}^{\ast}}}({\overline{h}})\}\) (i.e.,\({\mathrm {Consist}}({\overline{h}})\) is the set of elements that are consistent withS^∗’s answers on\({\overline{h}}\)).

SinceD_Real is the distribution a random execution ofA (over a randomy) induces on the values ofy and\({\overline{h}}\), the success probability ofA, in satisfying\({\mathcal {W}}\), equals the success probability ofInverter overD_Real (i.e., to\(\Pr_{({\overline{h}},y) \gets\mathsf{D}_{\mathrm{Real}}}[\mathsf{Inverter} ({\overline{h}}) \in{\mathcal{W}}_{y}]\)). We lowerbound the latter probability by relating it to the success probability ofInverter overD_Ideal. Specifically, we first show (Lemma 4.4) thatD_Real andD_Ideal assign similar mass tomost elements in the support ofD_Ideal, and then prove (Lemma 4.5) thatInverter’s success probability overD_Ideal (in the task of satisfying\({\mathcal{W}}\)) is not only high but also “well spread”. Namely, even if we ignore the contribution to the success probability of some sufficiently small number of values in the support ofD_Ideal, this success probability remains high. Therefore, we are guaranteed that the success probability ofInverter is high with respect toany distribution that assigns about the same mass tomost elements in the support ofD_Ideal, and in particular with respect toD_Real.

Fork∈{0,…,s} let\(\mu_{k} :=|{\mathcal{L}} |/2^{k\ell}\).

Lemma 4.4

Assumingt≥4then

where\({\mathrm{Dominated}}=\{({\overline{h}},y) \in \operatorname{Supp} (\mathsf{D}_{\mathrm{Ideal}}) \colon\mathsf{D}_{\mathrm {Real}}({\overline{h}},y) \geq\frac{1}{2^{8}} \cdot\mathsf {D}_{\mathrm{Ideal}} ({\overline{h}},y)\}\).

Namely, with high probability over the choice of\({\overline{h}}\gets {\mathcal{H}}^{t}\), the number of elements that are consistent with\({\overline {h}}\) and whose weight according toD_Ideal is much larger than their weight according toD_Real, is limited.

Lemma 4.5

Assumet≥4and\(\mu_{t-1} \geq\frac{12 t^{3}\cdot 2^{2\ell}}{\varepsilon}\),and let Secludedbe an arbitrary subset of\(\operatorname{Supp}(\mathsf{D}_{\mathrm{Ideal}})\)with

Then

Namely, if\(|({\overline{h}},{\mathrm{Consist}}({\overline {h}})) \cap {\mathrm{Secluded}}|\) is not too large on the average, thenInverter does well onD_Ideal even when ignoring the contribution of Secluded.

The proof of Lemmas 4.4 and 4.5 is given below, but first let us use them for proving Theorem 3.7.

Proof of Theorem 3.7

Let\(q := \lfloor\frac{1}{\ell} (\min \{\log|{\mathcal {L}} |, s\ell\} + \log\varepsilon- 8\log n - 6\ell- 9 ) \rfloor\). We first prove the theorem for the caseq<4, and then complete the proof by handling the caseq≥4.

Assumeq<4 and consider the success ofA when settingt=0. To lowerboundA’s success probability in this case, we compute

(5)

Since by assumptionq<4, we have\(\min \{|{\mathcal {L}}|,2^{s \ell}\} \leq2^{4\ell-\log\varepsilon+ 8\log n + 6\ell+ 9} = \frac{2^{9} \cdot2^{10\ell}\cdot n^{8}}{\varepsilon}\). It follows that\(\Pr_{y \gets L}[\mathsf{A}(y)\in W_{y}]\geq\frac{\varepsilon^{2}}{2^{10} \cdot 2^{10\ell }\cdot n^{8}} \cdot\min \{1,\frac{2^{s\ell}}{ \vert \mathcal {L}\vert }\}\), concluding the proof for the caseq<4.

Assumeq≥4 and lett=q. We start by showing thatμ_t−1 is large enough, so we can later invoke Lemma 4.5 with parametert. Indeed,

(6)

where the last inequality holds sincet≤n.

Let Dominated be the set defined in Lemma 4.4. We have

(7)

The first inequality holds since\(2^{(s- t)\ell-3}\geq2^{s \ell- (s\ell+ \log\varepsilon- 8\log n - 6\ell- 9) - 3} \geq \frac{1}{\varepsilon}\cdot n^{8} \cdot2^{6\ell}\cdot2^{6} \geq\frac{1}{\varepsilon}\cdot (8t^{4} \cdot2^{3\ell} )^{2}\) (note thatt≤n), the second one by Lemma 4.4 and the third one by the definition oft. Applying Lemma 4.5 for\({\mathrm{Secluded}}:=\operatorname{Supp}(\mathsf{D}_{\mathrm {Ideal}}) \setminus {\mathrm {Dominated}}\), yields

(8)

It follows that

concluding the proof for the caseq≥4. □

Remark 4.6

(Knowingt)

The value oft in the above proof depends onε and\(\vert {\mathcal{L}}\vert \). This seems to contradict our binding formalism (see Definition 3.2) whereA does not knowε and\({\mathcal{L}}\). However, selectingt at random only decreaseA’s success probability by a factor s. More interestingly, settingt=s guarantees thatA success probability is as claimed in the theorem; the effect of settingt tos is analogous to settingt arbitrarily and changingInverter to select\({\overline{h}}'\) using the rewinding method ofSearcher rather than uniformly at random. For every value\({\overline{h}}'\) that satisfies\(y\in{\mathrm {Consist}}({\overline {h}},{\overline{h}}')\), the probability of selecting it with the rewinding technique is only larger than the probability of uniformly selecting it. Where a value of\({\overline{h}}'\) such that\(y\not\in{\mathrm{Consist}}({\overline {h}},{\overline{h}}')\), does not contribute in our analysis to the success probability ofA. It follows that the distinction betweenSearcher andInverter is not necessary for the proof (but is only used for presentation reasons).

4.1Bounding the Size of\({\mathrm{Consist}}({\overline{h}})\)

The following simple observation plays an important role in the proofs of Lemmas 4.5 and 4.4.

Claim 4.7

\(\Pr_{{\overline{h}}\gets{\mathcal{H}}^{k}}[\frac{1}{4} \cdot\mu_{k} \leq |{\mathrm{Consist}}({\overline{h}})| \leq4 \cdot\mu_{k}] \geq1 - \frac{3k^{3} \cdot2^{2\ell}}{\mu_{k-1}}\),for everyk∈{2,…,s}.

Proof

Fixk∈{2,…,s}. We call\({\overline{h}}\in{\mathcal{H}}^{j}\)balanced if\((1-\frac{1}{k})^{j} \cdot\mu_{j} \leq \vert {\mathrm{Consist}} ({\overline{h}})\vert \leq(1+\frac{1}{k})^{j} \cdot\mu_{j}\) and prove the claim showing that

(9)

for everyj∈{0,…,k}, lettingμ₋₁=μ₀. Equation (9) holds trivially forj=0. In the following we assume forj≥0, and prove forj+1.

We say that\(h\in{\mathcal{H}}\)well partitions the set\({\mathrm{Consist}} ({\overline{h}})\), where\({\overline{h}}\in{\mathcal{H}}^{j}\), if\((1 - \frac{1}{k}) \cdot \vert {\mathrm{Consist}}({\overline{h}})\vert \leq 2^{\ell}\cdot \vert {\mathrm{Consist}}({\overline{h}},h)\vert \leq(1 + \frac{1}{k}) \cdot \vert {\mathrm{Consist}}({\overline{h}})\vert \). Lemma 2.3 yields

(10)

for every\({\overline{h}}\in{\mathcal{H}}^{j}\), and it follows that

 □

4.2Proving Lemma 4.4

In this section we prove Lemma 4.4.

Lemma 4.8

(Lemma 4.4, restated)

Assumingt≥4then

where\({\mathrm{Dominated}}=\{({\overline{h}},y) \in \operatorname{Supp} (\mathsf{D}_{\mathrm{Ideal}}) \colon\mathsf{D}_{\mathrm {Real}}({\overline{h}},y) \geq\frac{1}{2^{8}} \cdot\mathsf {D}_{\mathrm{Ideal}} ({\overline{h}},y)\}\).

We bridge betweenD_Ideal andD_Real via the following hybrid distributions: fork∈{0,…,t−1} and\({\overline {h}}\in{\mathcal{H}}^{k}\), define

• \(\mathsf{D}_{\mathrm{Real}}^{{\overline{h}}} := (h,y )_{y\gets{\mathrm{Consist}} ({\overline{h}}),h \gets(\mathsf{Searcher}^{{\overline {h}}}(y))_{k+1}}\) and

• \(\mathsf{D}_{\mathrm{Ideal}}^{{\overline{h}}} := (h,y )_{h\gets{\mathcal{H}} ,y\gets{\mathrm{Consist}}({\overline{h}},h)}\),

where\(\mathsf{Searcher}^{{\overline{h}}}(y)\) is the hybrid algorithm that first fixes its firstk hash functions to\({\overline{h}}\), and then continues as (the non-hybrid) originalSearcher would with respect to this fixing.

For (h₁,…,h_i,y)∈H^t×{0,1}ⁿ, let\(\gamma^{h_{1},\dots ,h_{i-1}}(h_{i},y) :=\frac{\mathsf{D}_{\mathrm{Ideal}}^{h_{1},\dots ,h_{i-1}}(h_{i},y)}{\mathsf{D}_{\mathrm{Real}}^{h_{1},\dots ,h_{i-1}}(h_{i},y)}\). Hence, for\(({\overline{h}}= (h_{1},\dots,h_{t}),y) \in\operatorname{Supp}(\mathsf {D}_{\mathrm{Ideal}})\) we can write

(11)

where in aboveλ stands for the zero length vector.

Equation (11) yields the following characterization of the set Dominated.

Claim 4.9

\({\mathrm{Dominated}}\supseteq \{((h_{1},\dots,h_{t}),y) \in \operatorname{Supp}(\mathsf{D}_{\mathrm{Ideal}} ) \colon\ \forall i\in[t] \ \ (1- \frac{3}{t}) \cdot\mathsf{D}_{\mathrm{Ideal}}^{h_{1},\dots ,h_{i-1}}(h_{i},y) \leq\mathsf{D}_{\mathrm{Real}}^{h_{1},\dots ,h_{i-1}}(h_{i},y)\}\).

Proof

Fix\(({\overline{h}}= (h_{1},\dots,h_{t}),y) \in\operatorname {Supp}(\mathsf {D}_{\mathrm{Ideal}})\) with\((1- \frac{3}{t}) \cdot\mathsf{D}_{\mathrm{Ideal}}^{h_{1},\dots ,h_{i-1}}(h_{i},y) \leq \mathsf{D}_{\mathrm{Real}}^{h_{1},\dots,h_{i-1}}(h_{i},y)\) for everyi∈[t]. Equation (11) yields\(\mathsf{D}_{\mathrm {Ideal}}({\overline{h}},y) \leq (\frac{1}{1- \frac{3}{t}} )^{t}\cdot \mathsf{D}_{\mathrm {Real}}({\overline {h}},y)\). Since\((\frac{1}{1- \frac{3}{t}})^{t}\leq2^{8}\) fort≥4, it follows that\(({\overline{h}},y)\in{\mathrm{Dominated}}\). □

Recall that in order to prove Lemma 4.4, we need to show that Dominated is large. By Claim 4.9, it suffices to lowerbound the number of pairs\(({\overline{h}}=(h_{1},\dots ,h_{t}),y) \in\operatorname{Supp}(\mathsf{D}_{\mathrm{Ideal}})\) for which\((1- \frac{3}{t}) \cdot \mathsf{D}_{\mathrm{Ideal}}^{h_{1},\dots,h_{i-1}}(h_{i},y) \leq \mathsf{D}_{\mathrm{Real}}^{h_{1},\dots,h_{i-1}}(h_{i},y)\) for everyi∈[t], a task that we do using the next lemma.

Lemma 4.10

For\({\overline{h}}\in{\mathcal{H}}^{k}\),wherek∈{0,…,t−1},there exists a set\({\mathrm{NonTypY}}({\overline{h}}) \subseteq {\mathrm{Consist}} ({\overline{h}})\)of size less than 8t³⋅2^3ℓsuch that the following holds:let\({\mathrm{BadH}}({\overline{h}}) := \{h\in{\mathcal{H}}\colon\exists y\in{\mathrm {Consist}}({\overline{h}}) \setminus{\mathrm{NonTypY}}({\overline {h}}) \colon(1 - \frac{3}{t}) \cdot\mathsf{D}_{\mathrm{Ideal}}^{\overline{h}}(h,y) > \mathsf{D}_{\mathrm{Real}}^{\overline {h}}(h,y)\}\),then\(\Pr_{h\gets{\mathcal{H}}}[h \in{\mathrm{BadH}}({\overline{h}})] < \frac {t^{2} \cdot2^{2\ell}}{|{\mathrm{Consist}}({\overline{h}})|}\).

Namely, Lemma 4.10 bounds the number ofy’s inside\({\mathrm{Consist}}({\overline{h}})\) for which the event\((1 - \frac{3}{t}) \cdot \mathsf{D}_{\mathrm{Ideal}}^{\overline{h}}(H,y) > \mathsf {D}_{\mathrm{Real}}^{\overline{h}}(H,y)\) is likely to happen. Before proving Lemma 4.10, we first use it to prove Lemma 4.4.

Proof of Lemma 4.4

For\({\overline{h}}\in{\mathcal{H}}^{k}\), let\({\mathrm {NonTypY}}({\overline {h}})\) be the set guaranteed by Lemma 4.10 (assuming for ease of notation that there exists asingle such set; in case there are several of them, we arbitrarily choose one). Let\({\mathrm {Bad\overline{H}}}:=\{{\overline{h}}= (h_{1},\dots,h_{t}) \in {\mathcal{H}}^{t}\colon\exists i\in[t] \colon h_{i} \in{\mathrm {BadH}}(h_{1},\dots,h_{i-1})\}\), and for\({\overline{h}}= (h_{1},\dots ,h_{t}) \in{\mathcal{H}}^{t}\) let\({\mathrm{All}{\mathrm{NonTypY}} }({\overline{h}}) :=\bigcup_{i\in[t]} {\mathrm{NonTypY}}(h_{1},\dots,h_{i-1})\).

Claim 4.9 yields\(\{({\overline{h}}, y) \in\operatorname{Supp}(\mathsf {D}_{\mathrm{Ideal}}) \colon y \in ({\mathrm{Consist}}({\overline{h}})\setminus {\mathrm{All}{\mathrm{NonTypY}} }({\overline{h}}) ) \land\ {\overline{h}}\notin{\mathrm{Bad\overline{H}}}\}\subseteq{\mathrm {Dominated}}\), and therefore

(12)

where for the first inequality observe that if the number of\(y \in {\mathrm{Consist}}({\overline{h}})\) with\(({\overline{h}}, y) \not \in{\mathrm{Dominated}}\) is at least 8t⁴⋅2^3ℓ, then there exists at least one\(y \in{\mathrm{Consist}}({\overline{h}}) \setminus{\mathrm{All}{\mathrm{NonTypY}}}({\overline{h}})\) with\(({\overline{h}},y) \notin{\mathrm{Dominated}}\) (note that\(|{\mathrm {All}{\mathrm{NonTypY}}}({\overline{h}})| < 8t^{4} \cdot 2^{3\ell}\)).

We conclude the proof showing that\(\Pr_{{\overline{h}}\gets {\mathcal {H}}^{t} }[{\overline{h}}\in{\mathrm{Bad\overline{H}}}]\) is small. Forq>0 compute

(13)

where the second inequality is by Lemma 4.10. Taking\(q = \frac{\mu_{t-1}}{4}\), Claim 4.7 yields

(14)

yielding that

(15)

Combining Eqs. (12), (15), yields\(\Pr_{{\overline{h}}\gets{\mathcal{H}}^{t}} [|\{y \in {\mathrm{Consist}} ({\overline{h}})\colon({\overline{h}},y) \notin {\mathrm{Dominated}}\}|\allowbreak > 8t^{4} \cdot2^{3\ell} ] \leq\Pr_{{\overline{h}}\gets{\mathcal {H}}^{t} }[{\overline{h}}\in{\mathrm{Bad\overline{H}}}] < \frac{10t^{3} \cdot2^{2\ell}}{\mu_{t-1}}\). □

4.2.1Proving Lemma 4.10

As a warmup we start by focusing on the Boolean case (i.e.,ℓ=1). Consider the Boolean matrix\(M \in\{0,1\}^{|{\mathrm {Consist}}({\overline {h}})|\times|{\mathcal{H}}|}\) withM(y,h)=1 iff\(y\in {\mathrm{Consist}} ({\overline{h}},h)\), where we identify the indices intoM with the set\({\mathrm {Consist}}({\overline{h}}) \times{\mathcal{H}}\). The distribution\(\mathsf{D}_{\mathrm {Ideal}}^{{\overline{h}}}\) can be described in relation toM as: choose a random column ofM and draw the index of a random 1-entry from this column (where a “1-entry” is an entry of the matrix that is assigned the value 1). The distribution\(\mathsf {D}_{\mathrm{Real}}^{{\overline{h}}}\) can also be described in relation toM: choose a random row ofM and keep drawing random entries from this row until a 1-entry is picked. Then return its index and stop drawing (where in case of ⌈2logt⌉ failed attempts, return ⊥).

Compare the matrixM with the matrix\({\widehat{M}}\in\{0,1\}^{|{\mathrm {Consist}} ({\overline{h}})|\times|{\mathcal{H}}|}\), where\({\widehat{M}}(y,h)= h(y)\). Note thatM can be derived from\({\widehat{M}}\) by flipping all values in some of its columns (specifically, the column corresponding toh is flipped in case\(y \notin{\mathrm{Consist}}({\overline{h}},h)\)). The pairwise independence of\({\mathcal{H}}\) shows that mostcolumns of\({\widehat{M}}\) are balanced (i.e., have about the same number of 1-entries), and thus the same holds forM. Hence, the mass that\(\mathsf{D}_{\mathrm{Ideal}}^{{\overline{h}}} \) assigns to most of the 1-entries ofM is close to\(\frac{2}{\vert {\mathcal {H}}\vert }\cdot \frac{1}{|{\mathrm{Consist}}({\overline{h}})|}\). The pairwise independence of\({\mathcal{H}}\) also shows that mostrows ofM are also balanced. SinceD_Real=⊥ only with small probability, the mass that\(\mathsf{D}_{\mathrm{Real}}^{{\overline{h}}}\) assigns to most 1-entries inM is also close to\(\frac{2}{|{\mathcal{H}}|}\cdot\frac{1}{\vert {\mathrm{Consist}} ({\overline{h}})\vert }\). We conclude that the 1-entries in a random row ofM (a random\(h\in{\mathcal{H}}\)) get about the same mass in\(\mathsf{D}_{\mathrm {Real}}^{{\overline{h}}}\) and in\(\mathsf{D}_{\mathrm{Ideal}}^{{\overline{h}}} \), and the proof of the lemma follows. Formal proof is given below.

Proof of Lemma 4.10

We take\({\mathrm{NonTypY}}({\overline{h}})\) as the set\(\{y\in {\mathrm{Consist}} ({\overline{h}})\colon\alpha_{\overline{h}}(y) >\frac{1}{2^{\ell}}\cdot(1 + \frac{1}{t})\}\), for\(\alpha_{\overline{h}}(y) :=\Pr_{h \gets{\mathcal{H}}}[y \in {\mathrm{Consist}} ({\overline{h}},h)]\). The proof that\({\mathrm{NonTypY}}({\overline{h}})\) has the two properties stated in Lemma 4.10 (i.e., bounded size, and dominance ofD_Real overD_Ideal) is carried via the next two claims.

Claim 4.11

\(|{\mathrm{NonTypY}}({\overline{h}})| < 8t^{3} \cdot2^{3\ell}\).

Proof

In the following letH be uniformly distributed over\({\mathcal {H}}\), and for\(h\in{\mathcal{H}}\) let\(X_{h} :=\vert {\mathrm {NonTypY}}({\overline{h}}) \setminus{\mathrm{Consist}}({\overline {h}},h)\vert \). The definition of\({\mathrm{NonTypY}} ({\overline{h}})\) shows that

(16)

for\(\nu= \frac{|{\mathrm{NonTypY}}({\overline{h}})|}{2^{\ell}}\). On the other hand,

(17)

where the last inequality is by Lemma 2.3. We conclude that

(18)

Assume towards a contradiction that\(|{\mathrm {NonTypY}}({\overline{h}})| \geq8t^{3} \cdot2^{3\ell}\) (and hence,ν≥8t³⋅2^2ℓ), Eq. (18) yields\({\mathrm{E}}[X_{H}] \geq |{\mathrm{NonTypY}}({\overline{h}})| - (1 + \frac{1}{2t} + \frac{4t^{2} \cdot2^{2\ell}}{8t^{3}\cdot2^{2\ell}} )\nu= |{\mathrm{NonTypY}} ({\overline{h}})| - (1 + \frac{1}{t})\nu\), in contradiction to Eq. (16). Hence, we have proved that\(|{\mathrm {NonTypY}} ({\overline{h}})| < 8t^{3} \cdot2^{3\ell}\). □

The next claim completes the proof of Lemma 4.10, showing that\({\mathrm{NonTypY}}({\overline{h}})\) indeed contains all the “non typical”y’s.

Claim 4.12

\(\Pr_{h\gets{\mathcal{H}}}[\exists y\in{\mathrm {Consist}}({\overline {h}}) \setminus {\mathrm{NonTypY}}({\overline{h}}) \colon(1 - \frac{3}{t}) \cdot \mathsf {D}_{\mathrm{Ideal}}^{\overline{h}}(h,y) > \mathsf{D}_{\mathrm{Real}}^{\overline {h}}(h,y)] < \frac{t^{2} \cdot2^{2\ell}}{|{\mathrm{Consist}}({\overline{h}})|}\).

Proof

By definition,\(\mathsf{D}_{\mathrm{Ideal}}^{\overline{h}}(h,y) = \frac{1}{|{\mathcal{H}}|} \cdot\frac{1}{|{\mathrm{Consist}}({\overline{h}},h)|}\) for every\(h\in{\mathcal{H}} \) and\(y \in{\mathrm{Consist}}({\overline{h}},h)\). In addition, the mass that\(\mathsf{D}_{\mathrm{Real}}^{\overline{h}}\) assigns to every such pair (h,y), is the probability thaty is chosen (i.e.,\(\frac{1}{|{\mathrm {Consist}}({\overline {h}})|}\)) times the probability thath is chosen in one of the ⌈2^ℓ⋅lnt⌉ sampling attempts done bySearcher(y) (i.e.,\(\sum_{i=1}^{ \lceil2^{\ell}\cdot\ln t \rceil} \Pr_{\mathcal{H}}[h] \cdot \Pr[\mbox{first $(i-1)$ attempts failed}] = \sum_{i=1}^{ \lceil 2^{\ell}\cdot\ln t \rceil} \frac{1}{|{\mathcal{H}}|} \cdot(1- \alpha_{\overline{h}}(y))^{i-1}\)). All in all,

(19)

Assuming that\(y\in{\mathrm{Consist}}({\overline{h}},h) \setminus {\mathrm{NonTypY}} ({\overline{h}})\), Eq. (19) yields

(20)

where for the last inequality we use the fact that\((1- \frac{1}{x})^{x} \leq e^{-1}\) forx≥1.

Let\({\mathrm{NonTypH}}({\overline{h}}):=\{h\in{\mathcal {H}}\colon \vert {\mathrm{Consist}} ({\overline{h}},h)\vert < (1 - \frac{1}{t})\cdot\frac{|{\mathrm{Consist}} ({\overline {h}})|}{2^{\ell}}\}\). Observe that

(21)

where the second inequality is by Lemma 2.3. We conclude the claim’s proof, showing that\((1 - \frac{3}{t}) \cdot \mathsf{D}_{\mathrm{Ideal}}^{\overline{h}}(h,y) \leq\mathsf {D}_{\mathrm{Real}}^{\overline{h}}(h,y)\) for every pair (h,y) with\(h\in{\mathcal{H}}\setminus{\mathrm{NonTypH}} ({\overline{h}})\) and\(y\in{\mathrm{Consist}}({\overline{h}},h)\setminus {\mathrm{NonTypY}}({\overline{h}})\). Indeed (by Eq. (20))\(\mathsf{D}_{\mathrm{Real}}^{\overline{h}}(h,y) \geq\frac{1- \frac{1}{t}}{1+ \frac{1}{t}} \cdot\frac{2^{\ell}}{|{\mathrm{Consist}} ({\overline {h}})|} \cdot\frac{1}{|{\mathcal{H}}|}\) and (by the definition of\({\mathrm{NonTypH}}({\overline{h}})\))\(\mathsf {D}_{\mathrm {Ideal}}^{\overline {h}}(y,h) \leq\frac{1}{(1- \frac{1}{t})}\cdot \frac{1}{\vert {\mathcal{H}}\vert } \cdot\frac{2^{\ell}}{|{\mathrm {Consist}}({\overline {h}})|}\) for every such pair, yielding that\(\frac{\mathsf {D}_{\mathrm{Real}}^{\overline {h}}(h,y)}{\mathsf{D}_{\mathrm{Ideal}}^{\overline{h}}(h,y)} \geq \frac{(1- \frac{1}{t} )^{2}}{1+ \frac{1}{t}} > 1 - \frac{3}{t}\). □

4.3Proving Lemma 4.5

In this section we prove Lemma 4.5.

Lemma 4.13

(Lemma 4.5, restated)

Assumet≥4and\(\mu_{t-1} \geq\frac{12 t^{3}\cdot 2^{2\ell}}{\varepsilon}\),and let Secludedbe an arbitrary subset of\(\operatorname{Supp}(\mathsf{D}_{\mathrm{Ideal}})\)with

Then

Proof

For\({\overline{h}}\in{\mathcal{H}}^{t}\), let\(\varepsilon_{\overline{h}}\) be the probability thatS^∗ breaks the binding of\({\operatorname {NOVY}\langle{\mathcal{H}}^{s} \rangle}\) with respect to\({\mathcal{W}}\) and\({\mathcal{L}}\) (according to Definition 3.2), conditioned on\({\overline{h}}\) being the firstt functions sent by theR. Note that\({\mathrm{E}}_{{\overline {h}}\gets{\mathcal{H}}^{t}}[\varepsilon_{\overline{h}}] = \varepsilon\).

Let\({\mathrm{Typical}}:=\{{\overline{h}}\in{\mathcal{H}}^{t}{\ : \ }|{\mathrm {Secluded}}_{\overline{h}}| \leq q_{{\overline{h}}} \ \land\ |{\mathrm{Consist}} ({\overline{h}})|\leq4\mu_{t}\}\), where\(q_{\overline{h}}= \lfloor\sqrt{2^{(s-t)\ell-1} \cdot\varepsilon_{\overline {h}}} \rfloor\). Note that

(22)

where the second inequality is by Claim 4.7 and the guarantee about Secluded (as given in the lemma statement). Letχ_Typical be the characteristic function of Typical. Equation (22) yields

(23)

We define the “weight” of\(y\in{\mathrm{Consist}}({\overline{h}})\) with respect to\({\overline{h}}\in{\mathcal{H}}^{t}\), as\(w_{\overline{h}}(y) :=\Pr [\mathsf{Inverter}({\overline{h}}) \in{\mathcal{W}}_{y}]\). It is easy to verify that

(24)

The following claim shows that for\({\overline{h}}\in{\mathrm {Typical}}\), the above sum remains high even when ignoring the contribution of\({\mathrm{Secluded}}_{\overline{h}}\).

Claim 4.14

Let\({\overline{h}}\in{\mathcal{H}}^{t}\)and let\({\mathcal {V}}\subseteq{\mathrm{Consist}} ({\overline{h}})\)be of size at most\(q_{\overline{h}}\),then\(\sum_{y \in{\mathrm{Consist}}({\overline{h}}) \setminus{\mathcal{V}}} w_{\overline{h}}(y) \geq\varepsilon_{\overline{h}}/4\).

Proof

The pairwise independence of\({\mathcal{H}}\) yields

(25)

Lety₀ andy₁ be the pair of elements returned byS^∗ on a successful cheat. Equation (25) yields that the probability that bothy₀ andy₁ are inside\({\mathcal{V}}\) is at most\(\varepsilon_{\overline {h}}/2\). It follows that the probability thatS^∗ cheats successfully while at least one ofy₀ andy₁ isoutside\({\mathcal{V}}\) is at least\(\varepsilon_{\overline{h}}/2\). Note that each event whereS^∗ cheats successfully and outputs an elementy_i=y, contributes half its probability to the total weight ofy. Thus, the sum of weights of the elements in\({\mathrm{Consist}}({\overline{h}}) \backslash{\mathcal {V}}\) is at least\(\varepsilon_{\overline{h}}/4\). □

We conclude that

where the penultimate inequality is by Claim 4.14, and the last one by Eq. (23). □

An interesting open question regards the optimality of the binding guarantee given in Theorem 3.7. Particularly, is there a linear-preserving reduction from the security of an interactive hashing protocol to satisfying the underlying relation?^Footnote10 There are three possible directions for improvement: (1) use a different interactive hashing protocol than the one considered in Theorem 3.7, (2) use a different implementation for\(\mathsf{A}^{{\mathsf{S}^{\ast}}}\) to satisfy the relation, or (3) improve the analysis of\(\mathsf{A}^{{\mathsf{S}^{\ast}}}\) success probability.

We mention that our improvement in parameters over the NOVY proof is mainly in the third item (i.e., the analysis of the reduction). In the following we show that our analysis cannot be pushed to show a linear reduction. Namely, we present a (non-efficient) adversaryS^∗ that breaks the binding of\({\operatorname {NOVY}\langle{\mathcal{H}}^{n} \rangle}\) with probabilityε (in the meaning of Eq. (1)), where\({\mathcal{H}}\) is a family of Boolean pairwise-independent hash functions, but\(\mathsf {A}^{{\mathsf{S}^{\ast}}}\) only breaks the underlying relation (in this case a relation imposed by a permutation) with probabilityO(ε^1.4).

For a fixedε>0 consider the following cheating senderS^∗ for\({\operatorname{NOVY}\langle{\mathcal{H}}^{n} \rangle}\): the cheating senderS^∗ answers the first\((n - \log\frac{1}{\varepsilon})\) questions with arbitrary Boolean answers, then it randomly selects two distinct elementsy₁,y₂∈{0,1}ⁿ that are consistent with the protocol so far and answers the remaining hash functions as follows: on\(h\in{\mathcal{H}}\), it checks whetherh(y₁)=h(y₂), if positive it sendsh(y₁) back to the receiver; otherwise, it raises a flag and answers at random. At the end of the protocol, if the flag was not raisedS^∗ invertsf on bothy₁ andy₂ (in a brute force manner) and outputs the result.

The pairwise independence of\({\mathcal{H}}\) yields thatS^∗ breaks the binding of\({\operatorname{NOVY}\langle{\mathcal{H}}^{n} \rangle}\) with provabilityε. Where in order for\(\mathsf{A}^{{\mathsf{S}^{\ast}}}(y)\) to find\(x\in{\mathcal {W}}_{y}\), it first has to be the case thaty∈{y₁,y₂}; since the number of elements consistent with the protocol after\((n - \log\frac{1}{\varepsilon})\) steps is concentrated around 1/ε (see Claim 4.7), the latter happens with probabilityO(ε). Assuming thaty is one of {y₁,y₂} (say thaty=y₁), for succeeding\(\mathsf {A}^{{\mathsf{S}^{\ast}} }\) has to choose in each step a hash functionh withS^∗(h)=h(y)=h(y₂). The pairwise independence of\({\mathcal{H}}\) yields that\(\Pr_{h\gets{\mathcal{H}}}[{{\mathsf {S}^{\ast}}}(h) \neq h(y_{2}) \mid{{\mathsf{S}^{\ast}} }(h) = h(y)] = \frac{1}{4}\). Therefore, the probability thatS^∗(h)=h(y)=h(y₂) in each of the last\(\log \frac{1}{\varepsilon}\) steps, is at most\((\frac{3}{4})^{\log\frac{1}{\varepsilon}} < \varepsilon^{0.4}\) (note thatA has no clue whaty₂ is). We conclude that the\(\mathsf{A}^{{\mathsf{S}^{\ast}}}\)’s overall success probability isO(ε⋅ε^0.4)=O(ε^1.4).

Yet, the existence of more security preserving reductions for\({\operatorname{NOVY}\langle{\mathcal{H}}^{n} \rangle}\) (or more generally, to any protocol that follows the NOVY paradigm), not to mention the existence of different protocols with better security preserving reductions, remains an interesting open question.