1 c © SIAM J. C OMPUT 2009 Society for I ndustrial and Applied Mathematics . Vol. 39, No. 3, pp. 1153–1218 STATISTICALLY HIDING COMMITMENTS AND STATISTICAL ZERO-KNOWLEDGE ARGUMENTS FROM ANY ONE-WAY ∗ FUNCTION ‡ ‡ † § ,OMERREINGOLD IFTACH HAITNER , , MINH-HUYEN NGUYEN , SHIEN JIN ONG ‡ AND SALIL VADHAN Abstract. We give a construction of statistically hiding commitment schemes (those in which the hiding property holds against even computationally unbounded adversaries) under the minimal complexity assumption that one-way functions exist. Consequently, one-way functions suffice to give statistical zero-knowledge arguments for any NP statement (whereby even a computationally unbounded adversarial verifier learns nothing other than the fact that the assertion being proven is true, and no polynomial-time adversarial prover can convince the verifier of a false statement). J. Cryptology , 11 (1998), pp. 87–108]. These results resolve an open question posed by Naor et al. [ cryptography, statistically hiding commitments, statistical zero-knowledge argu- Key words. ment systems, one-way functions, interactive hashing AMS subject classifications. 94A60, 68P25, 68Q99 DOI. 10.1137/080725404 1. Introduction. As first discovered by Shannon [3] for the case of encryp- tion, most interesting cryptographic tasks are impossible to achieve with absolute, information-theoretic security. Thus, modern cryptography aims to design protocols that are computationally intractable to break. Specifically, following Diffie and Hell- man [4], this is typically done by showing that breaking the protocol is as hard as some intractable problem from complexity theory. Unfortunately, proving lower bounds of the sort needed seems beyond the reach of c urrent techniques in complexity theory and indeed would require at least proving P =NP. Given this state of affairs, research in the foundations of cryptography has aimed to design cryptographic protocols based on complexity assumptions that are as weak and general as possible. This project was enormously successful in the 1980s. In a beautiful sequence of works, it was shown that many cryptographic primitives, such as pseudorandom generators, pseudorandom functions, private-key encryption, au- thentication, digital signatures, (computationally hiding) commitment schemes, and (computational) zero-knowledge proofs, could be constructed from any one-way func- tion [5, 6, 7, 8, 9], and moreover this complexity assumption is minimal in the sense that each of these primitives (and indeed almost any cryptographic task) implies the ∗ Received by the editors November 5, 2007; accepted for publication (in revised form) February 24, 2009; published electronically September 2, 2009. Preliminary versions of this paper appeared as [1] and [2]. http://www.siam.org/journals/sicomp/39-3/72540.html † Microsoft Research, New England Campus, One Memorial Drive, Cambridge, MA 02142 ([email protected] microsoft.com). Most of this author’s research was done while the author was at Weizmann Institute of Science, supported by grant 1300/05 from the Israel Science Foundation. ‡ School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138 ([email protected], [email protected], sa [email protected] eecs.harvard.edu). The research of these authors was supported by NSF grant CNS-0430336, ONR grant N00014-04-1-0478, and US- Israel BSF grant 2006060. § Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, 76100, Israel ([email protected]). The research of this author was supported by grant 1300/05 from the Israel Science Foundation. 1153

2 1154 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN existence of one-way functions [10, 11]. Moreover, it was shown that many of the remaining primitives, such as public-key encryption, collision-resistant hashing, and oblivious transfer, could not be reduced to the existence of one-way functions in a “black-box” manner [12, 13]. However, a few important primitives resisted classification into the above cat- egories. That is, it was only known how to build these primitives from seemingly stronger assumptions than the existence of one-way functions, yet there was no black- box separation between these primitive s and one-way functions. In this work, we are interested in two such ex amples—statistically hidi ng commitment schemes and statistical zero-know ledge arguments for NP. A commitment scheme defines a 1.1. Statistically hiding commitments. two-stage interactive protocol between a sender S and a receiver R ; informally, after commit stage , the is bound to (at most) one value, which stays hidden from R ,and S in the R learns this value. The two security properties hinted at in this reveal stage binding S is bound to at most one informal description are known as (namely, that hiding (namely, that value after the commit stage) and does not learn the value to R which S commits before the reveal stage). As with most cryptographic primitives, each of these security properties comes in two main flavors— computational security, whereby a polynomial-time adversary cannot violate the property except with negligible probability, and the stronger notion of , whereby even a computationally unbounded adversary cannot statistical security violate the property except with negligible probability. (An even stronger notion is that of , in which we do not even allow a negligible probability of perfect security breaking the scheme.) Natura lly, statistical security, when achievable, is preferable to computational security. However, it can be shown that there do not exist commitment schemes that are simultaneously statistically hiding and statistically binding. Thus, at best we can hope for one of the two properties to be statistical and the other to be computational. statistically binding commitment schemes has been understood The complexity of for a long time; they can be constructed from any one-way function [8, 5], and con- versely, one-way functions are necessary for commitment schemes, even with both security properties comput ational [10]. In this work, however, we are interested in statistically hiding commitments, which have some advantages over statistically bind- ing commitments. Specifically, when commi tment schemes are use dinconstructing larger protocols, one typically needs the binding property to ensure the integrity of commitments that are opened during the protocol execution itself and the hiding property to ensure that the unopene d commitments remain secret even after the pro- tocol execution. Thus, for the binding property, we need only be concerned with the adversary’s current resources, and thus it may be safe for this property to be com- putational. For the hiding property, however, we need to consider resources that the adversary may gain far into the future, and thus statistical security is preferable. Some of the most important examples of cryptographic protocols based on com- mitments are the zero-knowledge protocols for proving membership in an arbitrary NP language [9, 14]. In the protocol of [9], the hiding property of the commitment scheme translates to the zero-knowledge property of the protocol (i.e., the verifier learns nothing other than the fact that the assertion being proven is true), and the binding property of the commitment translates to the soundness property of the pro- tocol, (i.e., the prover cannot convince the verifier of a false assertion). Thus, the existence of statistically hiding commitments implies that arbitrary NP statements

3 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1155 can be proven with statistical zero knowledge and computational soundness; that is, every language in NP has a statistical zero-knowledge argument system [14, 15, 16]. Using statistically hiding commitments and the resulting statistical zero-knowledge any arguments in known reductions [9, 17], one can actually transform two-party pro- tocol that is secure against passive (a.k.a. honest-but-curious) adversaries into one that is secure against malicious adversaries while preserving statistical security for one of the two parties . erfect zero-knowledge arguments for Perfectly hiding commitment schemes and p NP were first shown to exist based on specific number-theoretic assumptions [14, 15, 18, 19, 20] or, more generally, based on any collection of claw-free permutations [21, 22]. The assumption for statistically hiding commitment schemes and statistical zero- knowledge arguments was reduced further to collision-resistant hash functions [23, 24]. Even though it seems intuitive that the computational binding property of statistically hiding commitments should be closely related to collision resistance, the beautiful work of Naor et al. [16] showed that actually any one-way permutation can be used to construct a perfectly hiding commitment sch eme. Recently, Haitner et al. [25] reduced the assumption further by constructing statistically hiding commitments based on regular one-way functions with known preimage size, and more generally on one-way functions where the preimage sizes can be efficiently approximated. The question of whether an arbitrary, unstructured one-way function implies statistically hiding commitments or statistical zero-knowledge arguments for NP, however, was left open. 1.2. Our results. In this paper, we resolve the complexity of statistically hiding commitments. Theorem 1.1. If one-way functions exist, then statistically hiding commitment schemes exist. By Impagliazzo and Luby [10], the exist ence of commitment schemes implies the existence of one-way functions, and thus the above result is tight. As discussed above, combining Theorem 1.1 and standard constructions of zero- knowledge protocols from commitments (cf., [9, 14, 15, 16, 26]), we obtain our second main result. 1 has a then every language in NP If one-way functions exist, Theorem 1.2. statistical zero-knowledge argument system. The assumption that one-way functions exi st also seems to be essentially minimal here: Ostrovsky and Wigderson [27, 11] showed that a zero-knowledge argument system for a hard-on-average problem implies the existence of one-way functions, and it follows from [26] that a zero-knowledge argument system for a language outside of AM ∩ coAM (or even outside SZKP) implies the existence of “nonuniform” one-way functions, where both the efficiency and secu rity refer to polynomial-sized circuits (and security holds for infinitely many input lengths). To avoid a lengthy detour into zero knowledge, we omit the formal definitions and proofs needed for Theorem 1.2 and instea d refer the reader to [26], where our work plays a key role in proving unconditional results about zero-knowledge arguments. 1.3. Our techniques. We begin by using one-way functions to construct a vari- ant of commitment schemes called 2 -phase commitment schemes , recently introduced 1 The standard definitions of zero knowledge and soundness are nonuniform notions of security, and thus this theorem requires assuming the existence of one-way functions that are secure even against nonuniform adversaries.

4 1156 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN 2 by Nguyen and Vadhan [28]. We then use this 2-phase commitment scheme to- (whose existence is also implied by gether with universal one-way hash functions onstruct the desired statistically hiding the existence of one-way functions [7]) to c commitment scheme. 1.3.1. 2-phase commitments from any one-way function. 2-phase com- mitment schemes are commitment schemes with two phases, each consisting of a commit stage and a reveal stage. In the first phase, the sender commits to and re- , and subsequently, in the second phase, the sender commits to and veals one value v 1 hiding . We say that the 2-phase commitment is if both reveals a second value v 2 ) ( 2 - -out-of- -binding , symbolically written as phases are hiding and say that it is 1 2 1 , if the following holds: with high probability, the sender will be forced to binding reveal the correct committed value in at least one of the phases (but which of the two phases can be determined dynamically by the malicious sender?). More specifically, with high probability after the first-phase commit, there is a single value such that if the sender decommits to any other value, then the second commi tment is guaranteed to be binding (in the standard sense). Even though we draw upon [28] for the notion of 2-phase commitments, there are many differences between the contexts o f the two works and their constructions of 2-phase commitments. In [28], the goal was to prove unconditional results about specifically, that one can transform zero- prover efficiency in zero-knowledge proofs ( knowledge proofs with inefficient provers into ones with efficient provers). This was done by showing that every problem having a zero-knowledge proof has an “instance- dependent” 2-phase commitment scheme, where the sender and receiver get an in- stance x of the problem as auxiliary input and we only require hiding to hold when is a “yes instance” and binding when x x is a “no instance.” Here, we are giving conditional results (assuming the existence of one-way functions) and are obtaining standard (as opposed to instance-dependent) 2-phase commitments. Moreover, the focusin[28]ison statistically binding 2-phase commitments ; thus here we need to develop new formulations to work with the computational binding property. Our initial construction, which gives a 2-phase commitment scheme satisfying a “weak hiding” property, is inspired by the construction of [28]. Indeed, the second phase in [28] was also introduced to deal with nonregular functions (corresponding to “nonflat distributions” in their setting), and our construction can be seen as applying the same idea to a variant of the protocol of [25]. However, in [28], this construction immediately gives a “strong hiding” property, whereas much of the technical work in the current paper comes from amplifying the “weak hiding” property we obtain into astrongone. Like [28], another complication is that our initial construction does not provide ther polynomially many schemes, one of a single 2-phase commitment scheme, but ra ) ( 2 -binding. After applying our amplifica- which is weakly hiding and all of which are 1 tion procedure and the transformation dis cussed below to each of these schemes, we obtain polynomially many standard commitments, at least one of which is statistically hiding and all of which are computationally binding; these can then be combined into a single statistically hiding commitment scheme using standard techniques. 2 Using methods from [28], one can directly construct statistically zero-knowledge arguments for NP from 2-phase commitments and thereby prove Theorem 1.2. However, it is conceptually simpler to prove Theorem 1.1 and then deduce Theorem 1.2 using standard constructions.

5 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1157 mmitments to standard commitments. 1.3.2. From 1-out-of-2-binding co We would like to use a 2-phase commitment s cheme to construct a (standard) com- mply have the receiver randomly choose, mitment scheme. A naive attempt would si after the first commit phase, whether to stick with the first-phase commitment or to use the second-phase commitment as the actual commitment instead. The intuition ) ( 2 -binding, the sender cannot cheat in both phases is that since the commitment is 1 together and thus the receiver would catch a cheating sender with probability one half (which we can then boost using standard techniques). The problem is, however, that the sender can decide in which phase he will cheat after knowing the receiver’s ully in both cases without violating the choice. Hence, the sender can cheat successf ( ) 2 -binding of the underlying protocol. 1 Our additional idea is to use a universal one-way hash function in order to force knowing the receiver’s before the sender to decide in which phase it is about to cheat choice. Universal one-way hash functions are a relaxation of collision-resistant hash functions that were defined by Naor and Yung [23] and shown to be constructable from any one-way function by Rompel [7]. (See also [29].) We show that the above problem can be solved by having the sender provide a universal one-way hash of the secret he has committed to in the first phase. This turns out to (computationally) determine whether the first or second phase will be binding while leaving enough entropy in the first-phase secret to still achieve hiding. As the above suggests, our construction and its analy- 1.4. Subsequent work. sis are rather involved. Fortunately, a much simpler and more direct construction has recently been found [30]. Some of the techni ques we develop here (such as those for working with collision probability as a measure of hiding in section 6) may nevertheless still be useful for other purposes. 1.5. Outline. We present the basic notation and definitions in section 2. As a warm-up, we present constructions of statistically hiding commitments based on regular one-way permutations in section 3 and from one-way functions with known preimage size ow to construct 2-phase commit- in section 4. In section 5, we show h ments from regular one-way functions with unknown preimage size , and in section 6, we extend it to any one-way function. Finally, in section 7, we present our transfor- mation from 2-phase commitments to (standard) statistically hiding commitments. 2. Definitions. If X is a random variable taking values in a finite set U , 2.1. Basic notation. R then we write x ← to indicate that x is selected according to X .If S is a subset X R ← S means that x is selected according to the uniform distribution on of ,then x U S . When the universe U is clear from context, we write μ ( S )= | S | / |U| to denote the density of 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 R X ← ,wehave X x )= X ( f ] is defined to be the probability that when example, Pr[ ( x )= x .Wewrite U f to denote the random variable distributed uniformly over n n } 0 > ] . .The support of a random variable X is Supp( X )= { x :Pr[ X = x } 0 { , 1 flat if it is uniform over its support. If X and Y are random A random variable is X ⊗ Y denotes the random variable obtained by taking independent variables, then R R k ← X and y to X Y and outputting the pair ( x, y ). We write ⊗ ← x random samples denote the random variable consisting of k independent copies of X . For an event E , (also statistical difference .The denotes the random variable X conditioned on E | X E

6 1158 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN variation distance ) between random variables and Y taking values known as the X is defined to be Δ( U X, Y in )=max Pr [ | ∈ S ] − Pr [ Y ∈ S ] | .Wesaythat X X ⊂U S ) -close if Δ( X, Y are ≤ ε . Y ε and (1) ω − n .Weletneg( )denote negligible if ε ( n )= n → N : [0 ε 1] is called A function , ( ) < neg( n )wemeanthat f n an arbitrary negligible function (i.e., when we say that ε ( n ) such that for every n , f ( n ) <ε ( n )). Likewise, there exists a negligible function O (1) . ) denotes an arbitrary function )= n poly( ( n n f r A ( x ; A ) to denote the output of A on For a probabilistic algorithm ,wewrite x and coin tosses input .Inthiscase, A ( x ) is a random variable representing the r output of for uniformly selected coin tosses. PPT (probabilistic polynomial-time) A strict refers to probabilistic algorithms (i.e., Turing machines) that run in polynomial A, z ), where ̄ z = z PPT algorithm is a pair ( time. A nonuniform ̄ ,... ,z is an infinite 1 2 ), and | =poly( n A is a PPT algorithm that receives z | sequence of strings in which n pairs of inputs of the form ( x, z is called the advice string for A z ). (The string n | x | .) Nonuniform PPT algorithms are equivalent to (nonuniform) n for inputs of length families of polynomial-sized Boolean circuits. } computationally indistin- } are and { Y X { Two probability ensembles n n n ∈ N n N ∈ guishable D , there exists a negligible function ε such that for all if for every PPT ∈ , N n n n )=1] Pr [ ,X . )=1] − ) D (1 | ,Y x | |≤ ε ( D | Pr [ (1 n n Similarly, we say that { X if the above } and { Y statistically indistinguishable } are n n } and D { X (instead of only PPT is required for all functions ’s). Equivalently, D n Y { are statistically indistinguishable if X n and Y )-close for some negligible are ε ( } n n n and all n ∈ N . ε function interactive protocol ( ) consists of two algorithms that compute the next- An A, B ,..., A x, a, α message functions of the (honest) parties in the protocol. Specifically, ( 1 when the common input is ; r ) denotes the next message α , A sent by party x α k +1 k ’s auxiliary input is a A ’s coin tosses are r , and the messages exchanged so far are A , ,...,α halt . There is a special message, , which immediately halts the interaction, α 1 k . private output at which time each party can compute one more message, which is their , which is required to be a Sometimes we will refer to protocols with a joint output deterministic polynomial-time function of just the common input and transcript of messages exchanged (and not the parties’ auxiliary inputs or private coin tosses). We A (resp., say that party )is probabilistic polynomial-time (PPT) if its next-message B | + ··· + | α ). | | α | function can be computed in polynomial time (in x | + | a | + k 1 For an interactive protocol ( A, B ), we write ( A ( a ) ,B ( b ))( x ) to denote the random process obtained by having A interact on common input x , with (private) and B and B to A and a , respectively (if any), and with independent auxiliary inputs b A B .Wecall( A, B ) polynomially bounded if there is a random coin tosses for and p such that for all x, a, b , the total length of all messages exchanged in polynomial ∗ is any interactive x ) ,B ( b ))( x )isatmost p ( | ( | ) with probability 1. Moreover, if B A a ( ∗ ( b ))( x ) if the total length of the ) ,B algorithm, then A will immediately halt in ( A ( a messages ever exceeds p | x | ); we have the analogous requirement for B interacting ( ∗ A with any A, B )a polynomial time if ( . We call a protocol ( ) is polynomially A, B bounded and both A and B are PPT. The number of rounds in an execution of the protocol is the total number of mes- sages exchanged between and B , not including the final accept / reject message. A A A, B ) public coin for A (resp., B ) if all the messages sent by We call the protocol (

7 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1159 B ) are simply the output of its coin tosses (independent of the history), except (resp., message and for the final ’s) private output, which is computed as A ’s (resp., halt B a deterministic function of the transcript. ). The ,B ( ( ))( x ) a We associate several random variables with the interaction ( A b is denoted by output A private output of ( a ) ,B ( b ))( x ), and view ( ( A ( a ) ,B ( b ))( x ) A A A ,γ ), ,...,γ r ; denotes view of the interaction; i.e., its values are transcripts ( γ A ’s t 1 2 where the γ r is A ’s coin tosses. Similarly, ’s are all the messages exchanged and i ( A ( a ) ,B ( b ’s private output and view, x )andview B ( A ( a ) ,B ( b )) denote ))( output B B , if any, is denoted by output( A respectively. The joint output a ) ,B ( b ))( x ). ( 2.2. One-way functions. The most basic primitive of modern cryptography is easy to compute but . a one-way function, which is a function that is hard to invert ∗ → , N be any function. A function f : { 0 N 1 } s → Let : Definition 2.1. ∗ 1 } 0 { , s n ) -secure one-way function, or equivalently has security s ( n ) ,if f is an ( A , is computable in polynomial time and for every PPT n − 1 Pr ( /s 1 [ A (1 ( ,f ( y )) ∈ f ) n ( f < y ))] n ←{ } 1 , 0 y s n for all sufficiently large is a one-way function if f is .Function ( n ) -secure for f every polynomial s . If the above holds also for nonuniform PPT A , we say that f is nonuniformly secure. One-way function is a regular one-way function if there exists a function g : N → f n such that ∈ Supp( f ( U N z ∀ z y 0 , 1 } |{ )), f ( y )= ∈{ }| = g ( n ); g ( n ) is called the : n of f .Wesaythat f is known-regular if preimage size ( n ) can be computed in time g poly( ). n Without loss of generality, we can consider only one-way functions (regular or ∗ y | | = | .This , | f ( y ) } nonregular) that are length-preserving, that is, for all , y 0 ∈{ 1 be converted into ones that are length- is because general one-way functions can preserving (cf., [31, p. 39]). Another basic primitive of modern cryptography 2.3. Commitment schemes. (bit) commitment scheme is a , which is a two-stage protocol between a sender and a receiver. In the first stage, called the commit stage , the sender commits to a private bit b . In the second stage, called the reveal stage , the sender reveals b and proves that it was the bit to which she committed in the first stage. We require two properties of commitment schemes. The property says that the receiver learns nothing hiding b in the commit stage. The property says that after the commit stage, about binding ; that is, she cannot successfully open b the sender is bound to a particular value of the commitment to two different bits in the reveal stage. commitment scheme is a polynomial-time interactive protocol Definition 2.2. A S, R ) with the following properties: =( Com Scheme Com proceeds in two stages: a 1. and a reveal stage .In commit stage n S both stages, the receiver R receive a security parameter 1 sender and the as common input. 2. At the beginning of the commit stage, sender S receives a private input b ∈ { 0 , 1 } , which denotes the bit that S is supposed to commit to. The com- mitment stage results in a joint output, which we call the commitment c = n , and a private output for )) S ,whichwecallthe decom- b ) ,R )(1 ( S output(( n d = output mitment string )(1 S b ) ,R ( ( ) . Without loss of generality, c can S be taken to be the full transcript of the interaction between S and R ,and d to be the private coin tosses of S .

8 1160 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN In the reveal stage, sender 3. b, d ) ,where d is the decommit- S sends the pair ( R ,and b , d . Receiver c . ment string for bit b accepts or rejects based on 1 ) if both sender S and receiver R follow R 4. will always accept (with probability their prescribed strategy. if all messages sent by the receiver are indepen- A commitment scheme is public coin dent random coins. Next, we define the hiding and binding properties of commitment schemes. statistically (resp., S, R ) is Com Definition 2.3. =( Commitment scheme ∗ ∗ ,theensembles { , (0) view ( S R if for every (resp., PPT) computationally) hiding R ∗ n ∗ n ∗ R } )(1 and { view ) ) ( S (1) ,R } )(1 are statistically (resp., computationally) R N n ∈ N n ∈ ∗ ∗ ∗ ( b ) ( in the commit stage ) denotes the view of R S ,R view indistinguishable, where R S ( b ) . interacting with Commitment scheme Com =( S, R ) is statistically (resp., com- Definition 2.4. ∗ , there exists a negligible function if for every (resp., PPT) putationally) binding S ∗ S ε such that the malicious sender succeeds in the following game with probability at most ε ( n ) : ∗ n S interacts with R in the commit stage , 1 On security parameter ∗ .Then c obtaining commitment S ,d outputs pairs (0 and (1 ,d ) ) 1 0 . accept )= ,c ,d (1 ,c )= R and (0 R if in the reveal stage succeeds ,d 0 1 ∗ S If the above holds for every nonuniform PPT , we say that Com is computationally binding with nonuniform security . Naor [8] con- Constructing commitment schemes based on any one-way function. structed commitment schemes that are computationally hiding and statistically bind- ing from any , which in turn can be based on any one-way pseudorandom generator function [5]. The main result of this paper, Theorem 1.1, shows that commitment statistically hiding and computationally binding can be based on schemes that are any one-way function. 3. Statistically hiding commitments from one-way permutations. Con- n n } 1 , 0 . Naor et al. [16] obtained a statis- →{ } 1 0 { : f sider a one-way permutation , f interactive tically hiding commitment scheme based on by using a protocol called hashing as a subroutine. Our agenda for this section is as follows: we will first in- formally describe interactive hashing and state the two main properties that we want from it; then, in section 3.1 we give an informal description of the Naor et al. [16] he NOVY commitment scheme; and finally, in section 3.2, scheme, henceforth called t we give a formal definition of interactive hashing and a protocol satisfying that defi- nition. .The and a receiver R is a protocol between a sender S Interactive hashing IH IH sender begins with a private input z , and at the end both parties output z z and 0 1 ∈{ z ,z z } . Informally, an interactive hashing protocol has the following such that 0 1 two properties: Hiding : If the sender’s private input z is uniformly random, then every re- 1. ceiver, even computationally unbounded malicious ones, fails to learn which . or z z equals to z of 1 0 2. Binding : The sender, including PPT malicious ones, can only “control” the value of at most one of the two outputs; the value of the other output should be essentially uniformly distributed. 3.1. The NOVY commitment scheme. Using an interactive hashing pro- tocol as a subroutine, Naor et al. [16] constructed the following statistically hiding commitment scheme.

9 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1161 n S 0 , 1 } 1. chooses a uniform x ←{ f x ). = and computes z ( R engage in an interactive hashing protocol using z as S ’s private input. 2. S and d and . be the common outputs, and let z = z } for some 1 ∈{ 0 , z z Let 0 d 1 , S sends c = b ⊕ d to R . 3. To commit to bit b verifies the decommitment by sends d ,and x to R . R , b 4. To decommit, S = f ( x ). z checking if c = b ⊕ d and d Let us informally argue why the above scheme constitutes a statistically hiding and computationally binding commitment. First, we argue its hiding property. We n because f is a permutation and x is } z have mentioned that { 0 , 1 is uniform in n 0 , 1 } chosen uniformly in { . By the hiding property of interactive hashing, even a or z = z ,or computationally unbounded malicious receiver does not know if z = z 1 0 equivalently, it does not know if =0or d = 1. Therefore, the scheme is statistically d hiding. Next, we argue its binding property. By the binding property of interactive n } and outside the 0 , 1 , is uniform in { z hashing, at least one of the outputs, say, α sender’s control. Therefore, if the sender is able to decommit to both 0 and 1, it must ( U . This is equivalent to finding a preimage of f ), and this task z find a preimage of α n is computationally infeasible since f is a one-way permutation. Hence, the scheme is computationally binding. 3.2. Interactive hashing. Interactive hashing was introduced by Ostrovsky, Venkatesan, and Yung [32] in the context of oblivious transfer protocols. As men- tioned above, it was applied to the construction of statistically hiding commitments by Naor et al. [16], and it will also prove to be a powerful and useful tool in our result. For our application, we will need the sender to commit to multiple bits in one execution of interactive hashing. Consequently, we extend the notion of interac- tive hashing to allow multiple outputs (instead of just two output strings). Since the number of outputs could be possibly superpolynomial, we succinctly describe the set k q 0 , 1 } k ,where →{ of outputs as the image of a polynomial-sized circuit 0 , 1 } C : { and q are polynomially related to the security parameter. (We will not actually need superpolynomially many outputs in this paper but use this more general formulation because it may be useful in future work.) In addition to allowing for multiple outputs, our application of interaction hashing also requires a more refined notion of computational binding than the one provided 3 It is for this reason that we consider the notion of what it by Naor et al. [16]. means to be a witness for a given relation W as follows: For a relation W , define } )=1 z, x ( W = { x , and we naturally refer to any : as z for set of witnesses the W z ∈ x W as a witness for z . (A natural choice, utilized in the analysis of the NOVY z W = { ( z, x ): f ( x )= z } for a one-way commitment scheme described above, is f function/permutation .) An interactive hashing protocol with multiple outputs is a Definition 3.1. k q ,R 1 ) where both parties receive common inputs (1 ) , S ( polynomial-time protocol IH IH q and S z 0 , 1 } receives a private input . At the end of the interaction, the common ∈{ IH k q →{ 0 , 1 } , and the private output of output is a (polynomial-sized) circuit C : { 0 , 1 } k S d ∈{ 0 , 1 } k .Wecall q the input length and is a string the output length. The IH protocol S ( ,R ) has to satisfy the following security properties. IH IH ∗ q )= ( and all z ∈{ 0 , 1 } ,where , it is the case that C z d R 1. Correctness : For all ∗ q k ∗ C =( S ,R is the common output, and )(1 ) , 1 ( ) z d = output ) ,R ( S ) ( z IH IH S IH 3 Although the notion of interactive hashing was introduced by Ostrovsky, Venkatesan, and Yung [32], it was Naor et al. [16] who proved a computational binding property of interactive hashing that allows for its application to statistically hiding commitments based on any one-way permutation.

10 1162 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN 4 S is the private output of . IH ∗ ) ) and ( V, U , random variables V, D are identically dis- : For all R 2. Hiding ( k ∗ ∗ ∗ =view S V ( U ) ( is ) ,andthe ,R R tributed, where the view of receiver q IH R ∗ S private output of U ( S ( = output is ) ,R D ) . IH IH q S IH 3. Binding : There exists an oracle PPT algorithm such that for every A ∗ and any relation , denoting the common output as C = W S adversary ∗ ∗ k q ( S ,d )(1 ) , and private output of S ,R as (( x 1 , )) = ) , ( x ,d 1 1 0 0 IH ∗ ,R ( , if it is the case that ) S output ∗ IH S Pr[ x d ∧ >ε, ] d = ∧ x ∈ W ∈ W 0 0 1 1 C d ) ) C ( d ( 1 0 ∗ and S ,thenitisalso where the above probability is over the coins of R IH the case that ∗ k − k q S (1) O A [ . ( z, 1 ) , 1 ε/q ,ε ) ∈ W ( ] > 2 · Pr z q ←{ 1 z , } 0 3.2. Remark We make three remarks regarding Definition 3.1. ∗ 1. The security requirements should hold for computationally unbounded R (for ∗ . In addition, the S correctness and hiding) and computationally unbounded W need not be polynomial-time computable. relation ∗ ∗ S S q 2. To simplify notation, we often write A A ( z ), to denote A , ( ( z, 1 z ), or even k ). ,ε 1 S 3. Although the private output of the honest sender ,the is always a string d IH ∗ S private output of the cheating sender is arbitrary; hence, we can assume ∗ breaks binding by producing two pairs of without loss of generality that S x strings ( )and( x ,d ,d ). 1 1 0 0 The interactive hashing protocol given in [32, 16], henceforth called the NOVY =1. Toobtainaninter- Interactive Hashing protocol, satisfies Definition 3.1 with k 1), we simply k> active hashing protocol with multiple outputs (i.e., the case when end the NOVY Interactive Hashing protocol 1 rounds earlier. − k ( Protocol 3.3. Interactive hashing with multiple outputs S ,R ) . IH IH Inputs: q k 1. Input length 1 1 and output length , both given as common input. q S , given as private input to sender . } String , 0 z 1 ∈{ 2. IH Protocol: R ,h ,...,h h :Select such that each h is a random vector over GF[2] that − 1 1 IH i 0 q k − is outside the span of h { ,h } . ,...,h 1 0 i − 1 For j =0 ,...,q − k − 1 , do the following: S :Send h . → R j IH IH S 〈 :Send c = R h ,z 〉 . → IH IH j j Output: k q : { 0 , 1 } • C Common output is a circuit 0 , 1 } →{ computing an injective affine . } 1 − k − ,...,q ,z 〉 = c =0 ∀ j transformation whose image is 〈 : z { h j j k • Private output of S is a string d ∈{ 0 , 1 } ( such that C . d )= z IH There exists an interactive hashing protocol with multiple outputs, Theorem 3.4. namely, Protocol 3.3 . 4 The correctness property of protocols is typically defined for honest parties; in our setting this would be S and R . In our applications, however, it is convenient to have a stronger correctness IH IH ∗ property that also holds against malicious receivers R .

11 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1163 The correctness of Protocol 3.3 is easy to see. Hence, we divide the proof of this theorem into lemmas establishing the hiding and binding properties of Protocol 3.3. 3.1 .Inother Protocol Lemma 3.5. 3.3 satisfies the hiding property of Definition ∗ words, letting interactive hashing S ( , we have for all R ,R ) be as in Protocol 3.3 IH IH ∗ ∗ V, U that ( ,where V =view V, D ( S ( U ) ,R ) ) is the is distributed identically to ( ) IH R k q ∗ ∗ R view of receiver ,and D ( S . ( U S ) ,R = output ) is the private output of q IH IH S IH ∗ together will be the hash functions h ,h ,...,h R . The view of any Proof − − 1 q 1 0 k with S c ,c ’s responses . Conditioned on such a view, the sender’s ,...,c q 0 k − 1 1 IH − Z = U private input is uniformly distributed in the k -dimensional affine subspace q , and hence the value D 〉 = c ∀ j } ,z s.t. C ( D )= Z is uniformly distributed h 〈 z : { j j k , 1 } { in 0 . 3.3 satisfies the binding property of Definition 3.1 . That Lemma 3.6. Protocol S ( is, letting interactive hashing ,R ) be as in Protocol 3.3 , there exists an oracle IH IH A such that PPT algorithm ∗ W , denoting the common output as C = and any relation for every S ∗ q k ∗ ( S , 1 x ) , and private output of S )(1 as (( ,R )) = ,d ,d ) , ( x 1 1 0 IH 0 ∗ ) ( S , if it is the case that ,R output ∗ IH S k x Pr[ ∈ W >ε, ] } 1 ∧ x , ∈ W 0 ∈{ d = ∧ d 0 1 1 0 ( C d ) ) C d ( 1 0 ∗ and , S where the above probability is over the coin tosses of R IH then it is also the case that ∗ − k S 8 q k − 2 . ) ( z, 1 ) , 1 2 ,ε [ ∈ W q ]=Ω( ε A Pr z q ←{ 0 } 1 , z q 0 and that d } )and C ( 1 , ) are two distinct elements in { C .Notethat Proof ( d 0 1 S both elements are consistent with the transcript of the protocol; i.e., an honest IH ∗ getting each of these elements as input would have acted in the same way as S does in the interaction. Thus, we are in the setting of the recent interactive hashing theorem presented by Haitner and Reingold [33], and the proof follows by [33, Theorem 5 3.9]. We think of the string d k -bit 3.2.1. Information-theoretic bounds. as a k string commitment associated to one of the 2 ), outputs strings, namely, ( d z = C x ∈ W and a witness = W . Intuitively, the knowledge d as a decommitment to z ) ( C d x . The binding property, read in its d of gives the sender the ability to decommit to contrapositive, says that if it is hard to find a witness for a uniformly random string , then it is hard for a sender to successfully decommit to two different values. Note z that this hypothesis—that it is hard to find a witness for a uniformly random z —says succeeds in finding A ’s on which z of T that for every PPT , there is a negligible set A A may depend on the adversary . In several places, A T a witness. In general, the set A however, we will need only the special case of a static set as captured in the following lemma. binding for static sets ). For any protocol ( S Lemma 3.7 ( ,R ) satisfying the IH IH ∗ 3.1 , the following holds: For all S binding condition of Definition and any set ⊆ T 5 Actually, [33, Theorem 3.9] directly applies to the case that the h ’s are uniformly random i vectors rather than being constrained to be linearly independent as in Protocol 3.3. However, up to q uniformly random q -dimensional vectors will be linearly independent with at least constant ∗ probability. Thus, if S breaks Protocol 3.3 with probability greater than ε , then it also breaks the version with uniformly random vectors with probability Ω( ε ), and [33, Theorem 3.9] applies.

12 1164 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN q ∗ q k 0 C =( S } ,R { )(1 , , 1 , denoting the common output as ) , we have 1 IH 2 / 4 k 1 ∃ Pr[ d ( d ) ) ,C ( d ) ∈ T ]

13 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1165 of X is most often bits). For a worst-case measure of randomness, the min-entropy used and is defined as [ ] 1 H X ( )=min . ∞ x ] = X log Pr[ x X ) ≤ H( X ), but when X is flat (i.e., uniform on its support), ( In general, H ∞ X )=H then H( )=log | Supp( X ) | . ( X ∞ m n pairwise-independent } 1 , 0 →{ } is } , 0 { : h { = H A family of hash functions 1 ′ n ′ m = x ) if for any two 2 x strongly (a.k.a. -universal } and any two y, y ∈{ ∈{ 0 , 1 0 , 1 } ′ ′ − 2 m )= y and h ( x ←H )= y ,wehavePr[ ]=2 h ( x . when we randomly choose h n ≥ m is the An example of a pairwise-independent family of hash functions for n m ) b + : { 0 , 1 } h →{ 0 , 1 } , arithmetic is } ,where | x ( x )=( a · = H family h { a,b a,b m n done in the field GF(2 n, m bits. We define ( denotes taking the first ) ), and | m m to be the number of bits required to describe an element of the hash function family since both a n bits to describe each hash function H . In our example, it takes 2 h a,b n ); hence, a family of pairwise-independent hash functions are elements of GF(2 and b n -bit strings to m -bit strings exists with ( n, m )=2 n . We will use the H mapping following property of pairwise-independent hash functions to obtain an almost-uniform random variable from a random variable with sufficient min-entropy. Let random variable H denote a Leftover Hash Lemma [37, 5] Lemma 4.1 ( ). uniformly random hash function from a family of pairwise-independent hash functions n mapping m -bit strings, and let X be a random variable taking values H -bit strings to n ε> 0 ,if H is independent from ( X ) ≥ m + 2 log(1 /ε ) ,and H . For any in { 0 , 1 } ∞ X H, H ( X )) is ε -close in statistical distance to uniform. ( , then the random variable Let us return to our regular one-way 4.2. The commitment scheme. t − n n n and known security } , →{ 0 with known preimage size 2 1 } , 0 { : f function 1 ω (1) n { . Consider a family of pairwise-independent hash functions { h : = 0 , 1 } H n s ( n )= 1 t − Δ →{ 1 } } ,where t =H( f ( U , )) and Δ = 0 H log s ( n ). Let random variable n 2 . By the Leftover Hash Lemma, represent a random hash function selected from H Ω(1) n -close to uniform, )) ( /s ))) is (1 =( ( Z f H, H ( Lemma 4.1, random variable U n ω (1) s n )= n which statistically gives indistinguishability from uniform because ( .Soif z =( h, h ( f ( x ))) as the sender’s private input to the interactive hashing we designate .3), even an all-powerful recei protocol (Protocol 3 ver will not get more than a neg- z . This hints at the following ligible advantage to guess which one of the outputs is commitment scheme. Protocol 4.2. S, R ) is based on a regular one-way Commitment scheme ( n n n t − and known security } →{ 2 0 , with known preimage size 1 } , 0 { : f function 1 ω (1) . s n )= n ( Commit stage. } { Δ t − n U t =H( f ( ,where , 1 } Δ= →{ 0 )) and Let h : { 0 , 1 = } H 1. n 1 n s ( n ) . S selects a uniform x ←{ 0 , 1 } log and a hash function ←H h 2 z y f ( x ) and computes = =( h, h ( y )) . and 2. S and R engage in interactive hashing (Protocol 3.3 )with S acting as and q acting as R having , parameters k =1 R , = | z | ,and S S IH IH IH q , 0 . Their common output is a circuit { 0 , 1 }→{ : , 1 } z private input C and the sender receives a bit d ∈{ 0 , 1 } such that C ( d )= z . b 3. b , S sends c = d ⊕ To commit to the bit to R . The commitment of b is represented as the pair ( C, c ) .

14 1166 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN sends bits b and d ,string x , and hash function h to R . Reveal stage. To decommit, S = )=( ⊕ b and C ( d c h, h ( f ( x ))) . d R verifies the decommitment by checking if As we have argued previously, the sender’s private input z is statistically close to uniform, and hence by the hiding property of interactive hashing, this implies that the commitment scheme is statistically hiding. As for the binding property, the ∗ intuitively guarantees that the set T of ’s for which a sender S f one-wayness of w − 1 ( cancomputeanelementof /s ( n ) in the range of f ; f w ) is of density at most 1 log H( ) U n )) − f s ( ( n is at most 2 T that is, the size of , the fraction . Thus, for any fixed h n f U 1 )) − log s ( ( ) H( 2 t − Δ / − n T is at most 2 of z =( h, h ( w )) such that w ∈ n / s = 2 = ) ( ). By the binding property of interactive hashing stated in Lemma 3.7, the neg( n ∗ can force both C (0) ,C (1) ∈ T is negligible, and hence, the scheme probability that S is computationally binding. The complete argument to prove the binding property T is not actually fixed in advance, and so we is actually more subtle because the set need to employ the stronger binding property given in Definition 3.1. We omit the full mple to motivate our actual construction proof, because this is merely a warm-up exa and proof in subsequent sections. 5. 1-out-of-2-binding commitments from unknown-regular one-way Our next hurdle is to remove to the constraint on knowing (i.e., being functions. For this setting, let us consider a reg- able to efficiently compute) the preimage size. 6 t − n n n , for an 1 →{ 0 , with preimage size 2 } unknown { ular one-way function 1 , 0 } : f ω (1) 7 1 , 2 ,...,n } , but with known security s ( n )= n value of t . ∈{ Constructing sta- tistically hiding commitments even in this setting was still an open problem prior to our work. t Let us examine why we need to know the correct value of in the previous scheme )), then the scheme is t H( f ( U is too high, that is, t of Protocol 4.2. If the value of n no longer hiding (but would be binding). This is because the Leftover Hash Lemma, )) is too small f ( U Lemma 4.1, no longer applies, since in this case the min-entropy H( n . On the other hand, if the value of t is too low, that is, t H( f ( U relative to t )), then n the scheme is no longer binding (but would be hiding). To see this, at least intuitively, − t Δ { , 1 } )toaverysmallset ; 0 t is very small, we are hashing observe that when ( U f n in other words, h ( U collapses too many elements in f ). As a consequence, inverting n ) is hard), and this allows us to )) could be easy (even though inverting f ( U f ( h ( U n n break the binding property of our scheme. All hope, however, is not lost. We can still use Protocol 4.2, trying all values of t ∈{ 1 , 2 ,...,n } ,todoour first phase commitments. And to ov ercome the difficulty of ensuring both hiding and binding, we will introduce a second phase that will be < > t binding when f ( U U )) and hiding when t )); this is obtained by the H( H( f ( n n ∼ ∼ x sender using a hash of the preimage as an input to another execution of interactive )), both phases will be =H( f ( hashing. This means that for the right value of t U n hiding, but for any value of t , at least one phase is binding. What we are describing here is a 2 -phase commitment scheme with a 1 -out-of- 2 binding property, notions that we formally define in the next section. As mentioned previously, we will work 5.1. 2-phase commitment schemes. with 2-phase commitment schemes, an alter nate variant of commitments introduced 6 What we mean by unknown is that we are not able to compute the preimage size efficiently. 7 Like in section 4, we consider only length-preserving functions, that is, | f ( x ) | = | x | for all ∗ x ∈{ 0 , 1 } , to avoid introducing new parameters. Our construction can nevertheless be easily generalized to regular one-way functions that are not length-preserving.

15 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1167 and sequential re commitment schemes with two by Nguyen and Vadhan [28]. These a related stages such that in each stage, the sender commits to and reveals a value. ) A 2-phase commitment scheme ( Definition 5.1. , with security parame- S, R ter ( and message lengths n k ,k ( ( n )) , consists of four polynomial-time interactive n ) 2 1 1 1 1 1 ,R ) ( S ,R , the first reveal stage ) ,thesec- protocols: the first commitment stage ( S c c r r 2 2 2 2 ond commitment stage S ( ,R ( ,R , and the second reveal stage ) .(Wealsowrite ) S r c c r 2 2 1 1 S S =( =( R ,R ,S ) to denote the first and second phases of R and R , ) and S respectively.) For us, both reveal phases will always be noninteractive, consisting of a single message from the sender to the receiver. (1) 1 k 1 ∈{ receives a private input σ 1 } , 0 S 1. In the first commitment stage, c 1 1 . At the end of the interaction, both S and coin tosses output a r R and S c c (1) (1) c is the . (Without loss of generality, we can assume that commitment c transcript of the first commitment stage.) 1 1 2. S In the first (noninteractive) reveal stage, both and R receive as common r r 1 (1) S receives as private input its previous coin ,and input the commitment c r 1 1 (1) (1) (1) r tosses . interpreted as a decommit- apair ( σ S ,γ sends ) with γ R S r r (1) (1) k (1) 1 (1) 1 ment for σ . R , 1 accepts or rejects based on c } , σ ∈{ ,and γ 0 . r 1 1 and R . (Without loss of generality, we τ output a string After that, both S r r is the transcript of the first commitment stage and the first τ can assume that 1 ’s decision to accept or reject.) R reveal stage and includes r 2 2 In the second commitment stage, both S 3. and R receive as common input the c c 2 k (2) 2 string τ ,and S σ ∈{ , 1 } receives a private input 0 and its previous coin c 2 2 output a commitment and R S . At the end of the interaction, both tosses r S c c (2) (2) c c . (Without loss of generality, we can assume that is the concatenation and the transcript of the second commitment stage.) τ of 2 2 and R receive as com- In the second (noninteractive) reveal stage, both S 4. r r (2) 2 mon input the commitment c ,and S receives as private input its previous r (2) 2 2 (2) (2) with sends γ . ) apair ( σ interpreted as a de- ,γ S R r coin tosses S r r k 2 (2) (2) (2) 2 σ commitment for ∈{ . R 0 ,and , c 1 } σ accepts or rejects based on , r (2) γ . We insist that scheme ( • ) have perfect completeness . That is to say, if S, R both sender S and receiver R follow their prescribed strategies, then R will always accept in both phases (with probability ). 1 1 1 2 1 ,S , )=(( ) S ,S =( • S The sender and receiver’s algorithms, denoted by S c r 2 2 2 2 1 1 2 1 S ( ) R )=(( R and ,R )) =( , ( R ,S ,R R ,R )) , respectively, are com- c c c r r r putable in polynomial time. • S, R ) is public coin ( R to S are independent Scheme if all messages sent by random coins. 5.2 ( 2-phase commitment schemes ). We make several remarks regarding Remark Definition 5.1. 1. We generally consider schemes that have the same message length for both , we say our 2-phase = k k phases. When this is the case, namely, k = 2 1 commitment scheme has message length k . It is only in section 7 that we will use the feature of different message lengths. 2. Instead of providing sender S with decommitment values as private outputs of the commitment phases, we simply provide it with the same coin tosses r S throughout (so it can recompute any private state from the transcripts of the previous phases) . The receiver R , however, operates using independent coin tosses in each phase and does not need to keep a private state.

16 1168 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN As for standard commitment schemes, -phase commitment schemes. 2 Hiding for we define the security of the sender in terms of a hiding property. Stated informally, the hiding property for a 2-pha commitment both se commitment scheme says that phases are hiding. Note that since the phases are run sequentially, the hiding property to hold even given the receiver’s view of for the second commitment stage is required the first stage. S, R ) , with security parameter 2 -phase commitment scheme Definition 5.3. ( )) n ( , is statistically hiding if, for all adversarial re- ) ,k ( n k ( n and message lengths 2 1 ∗ , the following hold: ceivers R ∗ R 1. The views of when interacting with the sender in the first phase on any (1) (1) σ two messages are statistically indistinguishable. Namely, for all , ∈ ̃ σ } { n ∗ 1 k (1) 1 ∗ σ ( probability the ( view ) ,R , )(1 ensembles ) S } { 1 , 0 R c n N ∈ { } (1) ∗ n 1 ∗ and ( ̃ σ are statistically indistinguishable. ) ,R ( )(1 S ) view R c n ∈ N ∗ R 2. The views of when interacting with the sender in the second phase are sta- tistically indistinguishable no matter what the sender committed to in the first (2) (2) (1) k k 2 1 0 } 1 , , ̃ σ 0 ∈{ ,andall , 1 } ∈{ , the proba- σ σ phase. Namely, for all } { 2 (2) ∗ n 2 ∗ (2) ∗ ∗ ) )(T , 1 ,R ( σ ) ( ) and { view ) ,R ( S S σ ( ̃ view bility ensembles R R c c ∈ n N n n ∗ 1 (1) , (T 1 ,where T=transcript( S ) ( } σ ) ,R , are statistically indis- )(1 ) N ∈ n tinguishable. We stress that the second condition of the above hiding definition (Definition 5.3) requires that the view of receiver in the seco nd phase be indistinguishable for any two ∗ 1 n (1) S messages even given the transcript of the first phase, T = transcript( ) ,R σ )(1 ( ). 1 -out-of- binding for 2 -phase commitment schemes. The 1-out-of-2 binding prop- 2 at least erty, informally stated, says that one of the two commitment phases is binding. ∗ , at most one of the two phases is In other words, for every PPT malicious sender S ∗ S bad in that can decommit a given commitment to two different messages in that ∗ .Moreover,we phase. We allow this bad phase to be determined dynamically by S binding if the sender breaks the first require that the second phase be statistically phase. Our construction achieves this stronger property, and using it simplifies some of our proofs. -phase commitment scheme ( S, R ) 2 Definition 5.4. , with security parameter and message lengths ( k n ( n ) ,k computationally 1-out-of-2 binding ( n )) ,is if there 2 1 B of first phase transcripts such that for every function ( n )= exists a “binding set” ε poly( / ) , the following hold: 1 n ∗ 1. Every PPT S ε ( n succeeds in the following game with probability at most ) for all sufficiently large : n 1 ∗ (1) c and R interact and output a first-phase commitment . S (a) c ∗ ̃ (b) S λ =( τ, κ ) and ) λ =( ̃ τ, ̃ κ outputs two full transcripts of both phases with the following three properties: (1) ̃ . • λ both start with prefix c λ and Transcripts (1) (1) Transcript λ • contains a successful opening of c σ to the value ∈ 2 1 k 1 R and using a first-phase transcript τ not in B ,and R } 1 , { 0 r r both accept in λ . (1) (1) ̃ • c Transcript λ contains a successful opening of σ ̃ ∈ to the value 2 1 k 1 R and R using a first-phase transcript ̃ τ not in B ,and } , 0 { 1 r r ̃ both accept in . λ ∗ (1) (1) S (c) succeeds if all of the above conditions hold and = ̃ σ σ . ∗ , the first-phase tran- 2. For every (even computationally unbounded) sender S scripts in B make the second phase statistically binding. In other words, for

17 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1169 ∗ S all ∈B , and all sufficiently large , with probability at least 1 − ε ( n ) ,all τ n (2) ∗ 2 (2) k 2 c over ) , there is at most one value σ S ∈{ 0 , 1 } =( ,R such that )( τ c (2) 2 (2) (2) (2) c R ,σ ( ,γ . )= accept γ ∃ r Some remarks on this definition: 1. Note that we require condition 1 to hold against PPT adversaries, but condi- tion 2 must hold against all, even com putationally unbounded, adversaries. 2. Condition 2 has an equivalent reformulation that is more similar to condition ∗ ,all τ ∈B , and all sufficiently large S 1. Specifically, we can require for all ∗ ∗ succeeds in the following game with probability at most ε ( and ): S n , S n 2 ∗ (2) R nd-phase commitment interact to get a seco . After the interaction S c c ∗ ̃ λ and we say that S λ, succeeds if both λ outputs a pair of full transcripts (2) 2 ̃ (which in turn contains τ as a prefix), R accepts c λ and begin with prefix r ̃ ̃ contain decommitments to two distinct values ,and λ and λ λ and in both λ = ̃ σ . σ 3. Conversely, an equivalent reformulation of condition 1 says that for every PPT ∗ S and every ( n )=1 / poly( n ), the following holds for all sufficiently large n : ε R ∗ (1) 1 )over c − ( ε n with probability at least 1 S ( ), there is at most one value ← ,R c (1) k 1 σ ε ∈{ 0 1 for which there is at least an , ( n ) probability (conditioned on } (1) ∗ c S λ subsequently outputs a fu ll accepting transcript )that =( τ, κ )with (1) (1) (1) (1) ) ,σ as a commitment to this / ∈B .Thus,wethinkof c ,γ τ =( c (1) σ unique value of . ∗ to break condition 1 (or its equivalent formulation above), it S 4. Note that for 1 2 R must produce a full transcript that makes both and accept. Thus, the R r r not really be considered “complete” decommitment for the first phase should until a corresponding second-phase transcript is produced. The reason we do not have the honest sender provide such a “full decommitment” during the first-phase reveal is that this would compromise the hiding property of the second phase. 5. If a 2-phase commitment is both statistically hiding and computationally τ generated in the first-phase inter- 1-out-of-2 binding, then the transcripts 1 1 ) will lie outside ,R B with all but action between the honest sender ( S negligible probability. Indeed, the statistical hiding property of the second phase implies that the second phase cannot be statistically binding (except with negligible probability), and thus by condition 2 the first-phase transcript B must be outside of τ . 5.2. Our 2-phase commitment scheme. We now describe our 2-phase com- n n 0 , 1 } , not necessarily regular →{ : { 0 mitment scheme for general functions 1 } f , nor one-way—as we shall later see, it is the regularity condition that gives the hiding property and the one-wayness of the function that gives the binding property of our m n →{ 0 , 1 } } be a family of pairwise-independent hash = H { : { 0 , scheme. Let 1 } h functions. As shown in section 4.1, we have a family whose description of each element n, m n, m )=2 n bits. It will be convenient to make takes ( )+ m = q ( n )forsome ( n | ( | h, h y ) , = q ( n ). This can be y n ∈{ 0 , 1 } fixed polynomial q ), so that for every ( done by padding random bits to the description of h . In addition, it will be convenient to work with protocols where the sender has ) j ( j ) ( d at to be committed to, but rather privately receives an output σ no input ( j ) 1 , 2 } of the commitment. If we can ensure that d the end of each phase j ∈{ is close to uniform given the receiver’s view, such a protocol can be easily turned into ( j ) of its choice by sending a commitment scheme: the sender can commit to a σ

18 1170 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN ) ( j ( j ) at the end of the commit stage. σ ⊕ d n , } x On the other hand, it will be convenient to have a special private input 1 ∈{ 0 that corresponds to a portion of sender’s coin tosses. The reason for this is that later is chosen randomly from a we will want to discuss properties of the protocol when x n rather than uniformly from the entire space. 1 , 0 } subset Γ ⊆{ n S, R ) based on f : { 0 Protocol 5.5. 1 } 2 -phase commitment scheme ( , → n 0 , 1 } { . , } ,...,t 1 , 0 ∈{ Δ , } = k ,...,n = k ∈{ 1 , 2 , Integers } ,...,n 2 , 1 ∈{ t Parameters: k 1 1 2 Δ and 1 ,...,n − t , . 0 ∈{ } 2 n 0 , 1 } Sender’s (special) private input: String x ∈{ . (Again, this is not the value to which the sender is committing, but is rather part of its coins, which will be S unless otherwise specified.) chosen uniformly at random by First-phase commit: 1 sets y = f . x ) ( S 1. c n t − Δ 1 H 2. Let 0 , 1 } = →{ 0 { 1 } h , : { } be a family of pairwise-independent 1 1 1 chooses a random hash h and computes ←H hash functions. S 1 1 c q (1) z h ( y )) ∈{ 0 , 1 } =( . ,h 1 1 1 1 (1) q k S 3. ( ( S ) ( z ,R ) ,R , )(1 ) , 1 run the interactive hashing protocol IH IH c c 1 1 R S , respec- acting as and and R ,with 3.3 S given by Protocol IH IH c c (1) k q tively. Let circuit C , 1 } , →{ 0 : 1 } { be the common output and 0 (1) k (1) (1) (1) (1) (with C , ( d 1 )= z } )be 0 ∈{ ’s private output in ( S , ( z S ) d IH IH q k R , )(1 1 ) . IH k (1) First-phase sender’s private output: String d 1 } , . 0 ∈{ First-phase reveal: 1 (1) (1) γ . =( d sends the tuple ,y,h ) S 1 r 1 (1) (1) Receiver R C . ( d accepts if and only if )=( h )) ,h y ( 1 1 r Second-phase commit: 1 1 x ) ,R ( ) , S Second-phase common input: First-phase transcript =transcript( τ which in particular includes the string y . Δ n n − t − 2 { 0 } 1 , = →{ 0 , 1 } { h be a family of pairwise-indepen- : } H Let 1. 2 2 2 S dent hash functions. h ←H and computes chooses a random hash 2 2 c (2) q , h x )) ∈{ 0 ( 1 } =( . ,h z 2 2 2 2 q k S 2. ( run the interactive hashing protocol ( S ) ( w , given ,R ) )(1 ,R , 1 ) IH IH c c 2 2 S 3.3 ,with by Protocol R and acting as S R and , respectively. Let IH IH c c k (2) k q (2) , 1 } : →{ 0 , 1 } { be the common output and d 0 ∈{ 0 , 1 } C circuit (2) k q ’s private output in ( S ) ( z be ) ,R S )(1 . , 1 IH IH IH k (2) , 1 } . 0 ∈{ d Second-phase sender’s private output: String Second-phase reveal: 2 (2) (2) S =( d γ ,x,h sends the tuple ) . 2 r 2 (2) (2) accepts if and only if . ( )) )= y and C f ( d x )=( h ( ,h x R Receiver 2 2 r n n , { 0 Suppose 1 } f Theorem 5.6. : 0 , 1 } is a regular one-way function →{ ω (1) with (known) security ( n )= n s . Then for any setting of parameters such that 1 } t − t, n { max )) , H( f ( U ≤ )) + 1] , k = O (log n ) ,and Δ s =Δ log = , ( U f [H( ∈ t n n 2 1 4 Protocol 5.5 is a 2 -phase commitment scheme that is statistically hiding and computa- 2 tionally -out-of- 2 binding. Moreover, the computational 1 -out-of- 1 binding property holds regardless of the setting of t or the regularity of f .

19 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1171 t In order to apply the above theorem, it needs to be verified that if we set = 1 H( ( f U − s ≤ min { t, n ,then t } . This can be easily made to hold by padding log )) n 4 n n →{ 0 , 1 } ,the . Specifically, given a one-way function f the input of { 0 , 1 } f : ′ 3 n 3 n ′ f function { →{ 0 , 1 } 0 , defined by f 1 ( x, y, z )=( f ( x ) ,y )for | x | = | y | = | z | } : n ′ ′ ≤ 2 is a regular one-way function with security s and output entropy H( f U )) ∈ ( n 1 ′ ′ ′ t } n/ 4 < min { t, n − ≤ s ,where n =2 n is the input length of f . log n n, ], so 2 [ 4 t = Because we do not know how to efficie ntly compute the correct value of ,...,n )), we are forced to try out all values of t =1 , 2 to get a collection of H( ( U f n corollary. While having a collection of commitment schemes, as stated in the next schemes instead of a single scheme may s eem inconvenient, in section 7 we will show single commitment n of 2-phase commitments into a howtoconvertsuchacollectio scheme that is statistically hiding and computationally binding (in the standard sense of binding). n n } with , 0 →{ 1 } Corollary 5.7. 0 { : f Given a regular one-way function 1 , ω (1) ( )= n s known security n acollectionof , we can construct in time polynomial in n -phase commitment schemes COM = { Com public-coin 2 Com } , such that ,..., n 1 there exists an index i ∈{ 1 , 2 ,...,n } such that scheme Com • is statistically i hiding, and is computationally 1 -out-of- 2 , 2 ,...,n } , scheme Com • for every index i ∈{ 1 i binding. For notational convenience and generality, the above corollary and some of our n n } 1 , 0 for a →{ } 1 { : f subsequent results are stated in terms of finite functions , 0 of the security parameter. When we say that the function f fixed value n is “given,” (or, more f this can be interpreted as being giv en the boolean circuit computing Com f as an oracle), and “constructing” the commitment schemes generally, given i can be interpreted as co nstructing the boolean circuits (or, more generally, circuits with oracle gates for evaluating f ) that compute the next-message functions of the protocol. We divide the proof of Theorem 5.6 into Lemmas 5.8 and 5.9, which establish the statistical hiding and computational 1-out-of-2 binding properties of Protocol 5.5, respectively. n n is a regular function, then Protocol →{ } 1 , ,with 5.5 0 } 1 , 0 { : f If Lemma 5.8. t ∈ [H( f ( U any setting of parameters satisfying ( )) f ( U = )) + 1] , k

20 1172 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN 1 )) n ) , Δ setting of parameters such that =Δ k ≤ min { O , log( s ( = (log ,t,n − t } n 1 2 4 2 binding in the sense of Definition 5.4 is computationally -out-of- 1 . Intuitively, the proof of Lemma 5.9 will proceed as follows. We will show that with high probability the first commit phase binds the (cheating) sender to a unique ) is at least roughly f ( U “heavy” string y , i.e., a string whose probability mass under n − t . During the first reveal phase, the sender can choose to reveal either this heavy 2 string or a “light” string. In the former case, the first phase is computationally binding, and in the latter, the second phase is statistically binding. Formally, we define the binding set as follows: B = 1 , 2 ,...,n } , define the set of light strings to be L For every t ∈{ t n − t − Δ 3 ∈{ 0 , 1 } y { :Pr[ ] ≤ 2 f ( U y )= } for a parameter Δ that we 3 n to be the B will set at the end of the proof. Define the binding set . ∈ L ere the sender reveals y set of transcripts wh t Now, we break the proof of Lemma 5.9 into Claims 5.10 and 5.11 below, which establish the binding property for the first and second phases, respectively. ∗ that defined above, if there exists a PPT For the binding set S Claim 5.10. B 1 = ( ε ) in the game in condition ε of Definition 5.4 ,then succeeds with probability n B that can invert f with success probability at least there exists a PPT O ) (1) +Δ +Δ k ( − 3 1 ε 2 ) n poly( / 1 · . · We define a relation W as follows: Proof. { } (1) (1) = ( z W . h ,x such that both z ): =( h ∃ ,h L ( f ( x ))) and f ( x ) / ∈ 1 t 1 1 ∗ Suppose we have a PPT S ε that succeeds with probability greater than in the ∗ S game described in condition 1 of Definition 5.4. In particular, this means that after (1) R interacting with d will, with probability greater than ε ,x , produce pairs ( )and 0 IH 0 (1) (1) (1) (1) (1) ∈ .Bythe = d ) W ,( C ,x ( d ,x ) ,x ) ∈ W ,and( C d ( d ) ) such that d ( 0 1 1 0 1 1 1 0 binding property of interactive hashing (condition 3 of Definition 3.1), there exists a PPT A such that ( ) O (1) ε k (1) − [ A ( z , ) ∈ W > 2 ] · (1) Pr (1) z (1) q q 0 } , z 1 ←{ q . v ←{ 0 , 1 } where the above probability is taken over the coin tosses of A and ←H B that on input y picks a random hash function h Consider an algorithm 1 1 and outputs A ( h ) and compute the probability that ,h y ( B )). We let η = h ( y 1 1 1

21 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1173 f inverts as follows: − 1 f B Pr[ U ( ( ∈ ( f U )) ))] f ( n n ] [ ∑ )] ( Pr[ A ( U f h )= ( f ( U x ))) = x ∧ f ( ,h =E 1 n 1 n ←H h 1 1 x ⎤ ⎡ ∑ ⎦ ⎣ =E ] x )= ,η h ( A Pr[ · )] x Pr[ f ( U ( )= f n 1 h ←H 1 1 h )) = η s.t. η,x x ( ( f 1 ⎤ ⎡ ∑ ⎦ ⎣ ≥ E ] x )= ,η h ( A Pr[ · )] Pr[ f ( U x )= f ( n 1 h ←H 1 1 x ∈ W s.t. η,x ,η ( h ) 1 ⎡ ⎤ ∑ t − − Δ 3 ⎣ ⎦ E ≥ ⇒ ) 2 L ∈ ) x ( · Pr[ A ( h f ,η )= x ] / ∈ x ( W 1 t ( h ,η ) 1 h ←H 1 1 η,x s.t. x W ∈ h ) ( ,η 1 − Δ t − Δ t − 1 3 =2 ) · ] W ∈ 2 ,η · h ( A Pr [ 1 ( h ,η ) 1 t Δ − 1 ←H ) ,η 1 } , 0 ×{ ( h 1 1 ( ) (1) O ε − +Δ ) (Δ − k 1 3 > 2 · 2 (by (1)) · q ) O (1) +Δ +Δ k ( − 1 3 ε = =poly( 1 ) · n poly( (since q 2 n )) . / · For the binding set B defined above, condition 2 of Definition 5.4 Claim 5.11. 2 k/ ) Δ − Ω(Δ − 2 3 =poly( n 2 · ) ε is satisfied with . 2 · y ∈ L Proof .Let be the string sent in the first reveal phase. This means t ∣ ∣ t − n − Δ t − Δ 1 − − 3 3 ∣ ∣ ( y ) 2 ,orequivalently f 2 ≤ ] y )= = T . Define set ≤ that Pr[ f ( U n 1 − ( { h ) ( x ∈H . ,x ∈ f T ,h ( y h } ,andlet μ ( T ) denote the density of the subset )) : 2 2 2 2 Δ − t − n n 2 Since h { , 1 } , 0 to maps 1 } ,wehave { 0 2 ∣ ∣ − 1 − Δ n − t ∣ ∣ 3 f ) y ( 2 − Δ Δ 2 3 =2 . ≤ μ ) T ( ≤ n − t − Δ n − t − Δ 2 2 2 2 Applying Lemma 3.7, we have [ ] (2) (2) (2) (2) − ) 2 k/ Δ − Ω(Δ ∗ 3 2 Pr ( z poly( ∈ T , < 2 q ) · 2 )satisfies z ) = output( S ,z ,z ,R · IH 1 0 0 1 which then concludes our proof since q is a fixed polynomial in n . 1 ProofofLemma 5.9. Set Δ = log s ( n ), and we are given that k = O (log n ) 3 2 1 and Δ ≤ =Δ )). With this setting, Claim 5.11 shows that condition log( s ( n 1 2 4 − Ω(log s ( n )) 2 in Definition 5.4 is satisfied with ε ( n )=poly( n ) · 2 n ), since =neg( ω (1) . Condition 1 of Definition 5.4 is also satisfied with negligible probability ( n n s )= n ) because otherwise f can be inverted with probability ε ( O (1) ))) − ( k n ( +Δ s ) O (1) − ( O (log n )+(3 / 4) · (log +Δ 3 1 ε n ) · 2 / poly( n ) · 2 ≥ ε · 1 · 1 / poly( − O (1) 3 / 4 / poly( n ) · s ( n ) ε = · 1 , ε which is greater than 1 ( n )if /s is nonnegligible. 6. 1-out-of-2-binding commitmen ts from any one-way function. Our next hurdle is to remove the regularity assumption. It turns out that this is the

22 1174 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN lso need to remove the need for known secu- most technically challenging step. (We a rity, but this will follow as a byproduct of our approach to removing the regularity assumption.) Similar to our construction from regular one-way functions (with un- known preimage size) in section 5, our construction based on any one-way function commitments, as stated below. yields a collection of 2-phase n n ,wecanconstruct 0 } 1 , →{ { Theorem 6.1. } 1 , 0 f Given a one-way function : acollectionof m =poly( n in time polynomial in public-coin 2 -phase commitment n ) COM { Com schemes = ,k Com } with message lengths ,..., k , such that ) n, n )=( ( 2 m 1 1 there exists an index i ∈{ 1 , 2 ,...,m } • Com such that scheme is statistically i hiding, and • ∈{ 1 , 2 ,...,m } , scheme Com for every index i 1 is computationally 2 -out-of- i binding. Note that this theorem provides 2-phase commitment schemes for long messages, specifically those with length equal to the input length n of the one-way function . Essentially the same proof can provide schemes with message length k ( n ) for any f k desired polynomial . Alternatively, we can apply the above theorem to the function ′ ′ x and is one-way ,...,x n )=( f ( x · k ( ( x = )), which has input length n ) ,...,f f k 1 k 1 if f is. A collection of 2-phase co mmitment schemes as above turns out to suffice for ob- taining statistical zero-knowledge arguments for all of NP (see [28, 1]). Hence, Theo- rem 6.1 suffices to establish Theorem 1.2, which states that statistical zero-knowledge arguments for all of NP can be based on any one-way function. However, in sec- bove collection of 2 tion 7, we will show how to transform the a -phase commitment schemes into a single commitment scheme that is statistically hiding and computa- tionally binding (in the standard sense of binding). This proves Theorem 1.1, the main theorem of this paper, and gives a more modular proof of Theorem 1.2 (simply by plugging the commitments into [9]). We prove Theorem 6.1 in sections 6.1–6.3. We now present an overview of how we generalize our con- 6.1. Overview. struction for regular one-way functions with unknown preimage size (Protocol 5.5) to arbitrary one-way functions. As shown in Lemma 5.9, this protocol already achieves is any one-way function (for every value of t ). Thus the 1-out-of-2 binding when f challenge is the hiding property. (Another issue is that Protocol 5.5 requires a one- way function with known security. It turns out that our method for handling the es the need to know the security.) hiding property also eliminat As discussed in section 5, for regular one-way functions with unknown preimage < H( f ( U )) t size, Protocol 5.5 has a hiding first phase when the parameter t satisfies n ∼ > satisfies t t and has a hiding second phase when f ( U f )). Intuitively, when H( n ∼ )) with the dynamic value is not regular, we should replace the fixed value H( f ( U n def H ( y ) ) is the value chosen by the sender = log(1 / Pr[ f ( U x )= y ]), where y = f ( n f in the preprocessing step, because H ( ) can be viewed as measuring the amount of y f y .The entropy studied by Haitner in approximable preimage-size one-way functions ( y ), but for general et al. [25] come equipped with an algorithm that estimates H f one-way functions, this quantity may be infeasible to compute. A weakly hiding scheme (details in section 6.2 ). One natural approach is to have ). When we choose ( y the sender choose t at random and hope that it is close to H f too small, only the first phase will be hiding, and when we choose t too large, t only the second phase will be hiding. But we have a nonnegligible probability of y ( ), and thus both phases will be hiding. Thus we have a 1- that t ≈ H =1 δ /n f

23 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1175 weak hiding out-of-2-binding commitm property, where with ent scheme satisfying a /n =1 δ , both phases are hiding, and it is always the case that at least probability one phase is hiding. Actually, in order to simplify our analysis, we will include as t Then there exists a choice of such that the protocol a parameter to the protocol. t is weakly hiding in the sense above, and for all choices of t the protocol is 1-out-of-2 collection of , resulting in a t binding. At the end, we will enumerate over all values of commitment schemes as claimed in Theorem 6.1, albeit with a weak hiding property. Unfortunately, we do not know how to directly construct statistically hiding com- mitments from weakly hiding 1-out-of-2-binding commitments. Thus instead, much of the effort in this paper is devoted to amplifying the weak hiding property, where /n ,intoa δ property, where δ =1 − neg( n ), while maintaining the =1 strong hiding 8 1-out-of-2 binding property. 6.3 We do not amplify the Amplifying the hiding property (details in section ). =1 /n to δ =1 hiding probability from neg( n ) in one shot, but instead perform δ − n iterations, each one of which increases δ by roughly a factor of 2. a sequence of log δ = Ω(1), and then we are able to get δ =1 − neg( n )injustonemore This results in amplification step. How do we double δ ? A natural idea is to consider several executions of the = (1) executions, the m previous weakly hiding scheme. Specifically, if we take O · δ . probability that at least one of the executions has both phases hiding is roughly m − 1 executions have either the first phase hiding or Moreover, each of the remaining m the second phase hiding. Thus, for some value of β ,thereare β + 1 first phases that m − β second phases that are hiding. It turns out that we can choose β are hiding and β − β ) breakdown given that one execution has both phases +1 so that this exact ( ,m √ m ). Thus we are in the situation described with / hiding occurs with probability Ω(1 √ √ )=Ω( . m · δ ) > 2 δ for a large enough constant m m probability m · δ · Ω(1 / Now our aim is to combine the outcomes of the weakly hiding schemes in such a way that when the above-described situation occurs, which happens with probability k δ at least 2 , both phases are hiding. Notice that the secret values σ ∈{ 0 1 } ,...,σ , m 1 to which the sender commits in the first commit phases have entropy (even min- β +1) · k conditioned on the receiver’s view (because ( β +1) of entropy) at least ( them are hiding), and similarly the sender’s secrets in the second commit phases have entropy at least ( − β ) · k conditioned on the receiver’s view. Let us compare this m to the situation with binding. Since each execution is 1-out-of-2 binding, a cheating polynomial-time sender can break the binding property for either at most of the β or at most first phases − β − 1 of the second phases. Thus the number of possible m β m · k 2 · in the first phase values to which the sender can open in each case is at most 2 1) k · ( m − β − m at most 2 or ,wherethe2 factor in the first bound comes from the sender’s ability to choose which subset of executions to break (and it is this factor that limits us to taking m to be a constant). We can view these as strong forms of entropy upper bounds m + kβ and k · ( m − β − 1). In at least one phase, there will be an entropy gap k − m . of at least How can we exploit these entropy gaps? It turns out that interactive hashing, again, is a useful tool. Specifically, in the first phase we have the sender choose a ran- 8 One may wonder why we do not now apply the compiler of section 7, which converts strongly hiding 2-phase commitments into standard commitments. Even if that compiler could be made to work for weakly hiding 2-phase commitments (producing a weakly hiding standard commitment), an- other obstacle is that the compiler requires a 2-phase commitment with polynomial message length, whereas our weakly hiding commitment has only a logarithmic message length (similarly to Theo- rem 5.6). It turns out that our amplification procedure also increases the message length as needed.

24 1176 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN h dom pairwise-independent hash function +1) · k bits mapping to approximately ( β 1 h and use ( ,h ( σ ,...,σ )) as the input to the interactive hashing protocol, and anal- 1 1 1 m ogously for the second phase. By the Leftover Hash Lemma, this pairwise-independent hashing results in an almost-uniform distribution, so the interactive hashing hiding property applies. As for the binding property, the bound on the number of the sender’s choices gets translated to saying that the sender’s input (in the first phase) k − m − ) ( , so the interactive hashing binding property comes from a set Γ of density 2 applies. The analysis for the second phase is similar. Formalizing these ideas, we get a new 1-out-of-2-binding commitment scheme in which both phases are hiding with . probability at least 2 δ (log ) times, we run into a new O n When we try to iterate this amplification step difficulty. Specifically, the above sketch hides the fact that we pay entropy losses of ) in both the hiding and binding analyses. The entropy loss of ω (log n )in ω (log n the hiding property comes from the Leftover Hash Lemma in order to ensure that ,h ( σ )) has negligible statistical distance from uniform. The entropy ,...,σ h ( m 1 1 1 k (log n ) in the binding property comes from needing the μ (Γ) · loss of ω 2 factor to be negligible when applying Lemma 3.7. This forces us to go, in one step of amplification, from a commitment schem e for secrets of length k to a scheme for secrets of length − − (log m ). As in Lemma 5.9, we can take the initial secret to be of length ω k n (1) ω . )) = ω (log( n )) if the one-way function has known security s ( n )= n k =Θ(log s ( n ω (log n ) (i.e., at least ), we would need s ( n )= n n losses of But to tolerate log (log n ω quasi-polynomial security). To get around this difficulty, in the amplification, we work with more relaxed, average-case measures of entropy for both the hiding and binding analyses. Specif- ically, for hiding, we keep track of the expected collision probability of the sender’s secret, conditioned on the receiver’s view. (Actually, we use the expected square root of the collision probability.) For binding, we work with the expected number of values to which the sender can open. In both cases, we require only that these expectations − k and 1, respectively. to be within a constant factor of the ideal values, which are 2 With these measures, it turns out that we need only lose O ( m )= O (1) bits in the entropy gap with each amplification step. Moreover, once we amplify δ to a constant, we can afford to take the number of executions m to equal the security parameter n and get an Ω( )-bit entropy gap in the final amplification step. This allows us to n achieve exponentially strong statistical hiding even when we do not know the security = O (log ). k and start with secret length of n The hiding analysis of the above construction works only for certain values of t ’s in the amplification in the weakly hiding scheme, and for certain values of the β and steps. We try out all possible values of ’s, thus obtaining a collection of t β ) schemes, at least one of which is strongly hiding and all of which are 1-out-of- n poly( t and the β ’s is polynomial 2 binding. Notice that the number of possible choices of n since t ∈{ 1 , 2 ,...,n } ,the β ’s in the each step except for the last are in the range in , 0 1 ,...,m − 1 } for some constant m ,andthelast β is in the range { 0 , 1 ,...,n } . { As discussed 6.2. Weakly hiding and 1-out-of-2-binding commitments. in section 5, for the case of regular one-way functions with unknown preimage size, < )) and H( f ( U satisfies t Protocol 5.5 has a hiding first phase when the parameter t n ∼ > t t satisfies has a hiding second phase when H( f ( U )). When is not regular, then f n ∼ there will be one value of t ∈{ 1 2 ,...,n } such that H , /n ( y ) ≈ t with probability 1 f R def y over f ( U ]) measures the entropy in the ), where H y ( y ) = log(1 ← / Pr[ f ( U )= n f n specific output y ). Thisisthecasebecausethereareonly n possible choices for the

25 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1177 t value of . phase commitment scheme from general With this observation in mind, our 2- one-way functions will be the same as the scheme in Protocol 5.5, with setting of t = t parameters k = O (log n )andΔ . =Δ ,...,n =2log n ,forsome t , ∈{ 1 , 2 } 0 1 0 2 In other words, the same scheme—with slightly different setting of parameters—used in the case of regular one-way functions is also applicable to general one-way functions. This commitment scheme (using general one-way functions), as we will show, is computationally 1-out-of-2 binding, but only statistically hiding in both phases with (hence, called ). In order to obtain a tighter /n probability at least 1 weakly hiding analysis when we amplify this scheme, we depart from the standard measures of hiding and binding used in section 5. Instead, we measure the statistical hiding property of of expected square root of the collision probability our 2-phase commitments using the 1/2 , and defined in section 6.2.1. We measure the the sender’s secret, denoted as CP binding property by analyzing the to which an adversarial expected number of values sender can open. Later, in section 6.3, we show how to boost the statistical hiding probability to ) n − Ω( while maintaining the computational 1-out-of-2 binding property. 2 1 − 6.2.1. Properties of collision probability. Definition 6.2. , we define its collision probability A For any random variable are equal. In other words, as the probability that two independent samples from A ∑ def 2 = . = ]] [Pr[ a =E (Pr[ A = a ]) A ) A CP( A ← a a ) A Supp( ∈ Measuring the collision probability of a random variable is equivalent to measuring its 2, defined as Renyi entropy of order 1 1 H . =log A )=log ( 2 [Pr[ = a ]] A E CP( A ) a ← A Definition 6.3. For any random variable A , we denote the square root of its collision probability as √ def 1/2 A ) = ( CP( A ) . CP A and , we define the expected For any two (possibly correlated) random variables B square root of B A’s collision probability given as [ ] def 1/2 1/2 CP . =E ( A ) | B ) ( A | CP B b = ← b B √ 1/2 k We think of CP 2 ) ≤ ( | A as saying that A has conditional Renyi entropy B of at least k given B . We use the expected square root of the collision probability (as our measure of hiding) instead of just expected collision probability in order to ensure that conditioning on a random variable can only decrease the conditional Z ) bits. (See Lemma 6.7 below for details.) | Z Renyi entropy by at most log( | Supp( ) 1/2 behaves nicely as an entropy measure. The following lemmas show that CP Proofs are in the appendix. , ) ,Y X ( ,Y ,..., ) Lemma 6.4. ( For independent pairs of random variables X m m 1 1 m ∏ 1/2 1/2 Y ,...,X | ) | ( ) X ,...,Y ( )) = . (( X CP Y CP m 1 i m 1 i =1 i

26 1178 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN X Note that Y and can be correlated; it is required only that the pair ( X be ,Y ) i i i i independent from the other tuples. In terms of conditional Renyi entropy, Lemma 6.4 states that the entropy is additive for independent random variables. We will actually need a generalization of Lemma 6.4 to deal with somewhat dependent random variables, as stated in the next lemma. ) ,Y ,Y ,..., ) satisfy the follow- ( X X ( Lemma 6.5. Suppose random variables 1 m m 1 + α ing conditions for some values of ∈ R ,...,α and all i =1 , 2 ,...,m : m 1 ,...,y , ) ,Y ) ∈ Supp( Y ,...,Y ( y For every 1. − 2 i − 1 1 i 1 1 1/2 CP X . | α ≤ ) | Y | ( y i y ,...,Y i y Y = = ,...,Y = y = Y i − i i − 1 − i i − 1 1 1 1 1 1 1 Y +1 random variables ) ∈ Supp( ,...,y ,Y i ,...,Y ,the ) y ( 2. For every i 1 i 2 1 X ,X ,...,Y ,...,X y ,and Y = Y are independent after conditioning on +1 i i 1 2 i 1 1 y . = i Then, m ∏ 1/2 CP ) | ( (( X ,...,Y )) ≤ ,...,X α . Y m 1 i m 1 =1 i The next lemma shows that pairwise-independent randomness extraction ( h, h ( x )) 1/2 preserves the CP measure. Lemma 6.6 ( Let ( X, Y ) be any (possibly Randomness Ext ). raction Lemma denote a random correlated) pair of random variables, and let random variable H with range hash function from a family of pairwise-independent hash functions H α are represented by ( . Suppose the hash functions from − α ) -bit strings and H q , 1 } { 0 √ 1/2 ( − α +3) CP Y 2 | X ( ) .If H is independent from ( X, Y ) ,then ≤ √ 1/2 − ( q − 1) Y ) (( ≤ 2 H, H ( X )) | . CP X α + 3 bits of conditional Renyi entropy given Y , In other words, if has at least then we can extract bits from X that have conditional Renyi entropy at least α − 1. α Notice that this entropy loss is only 4 bits, as compared to 2 log(1 /ε )ifwerequirethat the output be ε -close to uniform as in the Leftover Hash Lemma (Lemma 4.1). This constant loss of conditional Renyi entropy allows us to do a tighter hiding analysis in section 6.3.1. X , Y ,and For any triple of (possibly correlated) random variables Lemma 6.7. Z , √ 1/2 1/2 1/2 Y ) ≤ CP . ( ( | ( Y, Z )) ≤ X | Supp( Z ) |· CP | ( X | Y ) X CP This says that conditioning on random variable Z can only decrease the con- ditional Renyi entropy, but does so by at most log( Supp( Z ) | ) bits. For Shannon | entropy, a stronger statement can be proven, namely, that conditioning on Z reduces entropybyatmostH( Z )bits: H( X | Z ) ≥ H( X ) − H( Z ) (omitting the random variable Z Y X, Z )=H( Z )+H( X | for simplicity). This follows from the chain rule H( ), noting that H( X, Z ) ≥ H( X ). However, the chain rule does not hold for conditional Renyi

27 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1179 9 entropy. The final lemma is a stronger variant of the previous Leftover Hash Lemma (Lemma 4.1), with its hypothesis stated in terms of collision probability. ). Leftover Hash Lemma, strengthened [37, 5] Let random variable Lemma 6.8 ( H denote a random hash function from a family of pairwise-independent hash functions α 2 − α ε ε> 0 ,if CP( H ) ≤ and is independent from · 2 X . For any , { } with range H 1 0 H, H ( X )) is ε -close in statistical distance to uniform. X , then random variable ( 6.2.2. Average-case hiding and bindi ng properties of interactive hash- We now analyze the interactive hashing protocol, namely, Protocol 3.3, in terms ing. 1/2 of measures. For hiding, we use the CP average-case measure introduced in the previous section. For the binding property, we present an average-case variant of number of outputs that lie in any set Γ, expected Lemma 3.7, where we look at the rather than bound the probability that there is more than one output in Γ. 1/2 ). Let ( S be measure ) ,R Lemma 6.9 ( hiding of interactive hashing in CP IH IH S .Ifthesender 3.3 the interactive hashing protocol in Protocol ’s input comes from IH q and W is any (possibly correlated) random variable 1 } Y a random variable { 0 , over ∗ R Y ), then for any receiver (representing the receiver’s a priori information about , √ 1/2 1/2 q − k | 2 | ( W, V · CP )) ( Y Z W ) , ( ≤ CP q ∗ k ∗ q k ∗ where Z = output ( )(1 . , 1 ) ) and V =view ( S ( S 1 ( Y ) ,R ) )(1 ,R , Y IH R IH S IH ∗ . Without loss of generality, we may assume that Proof R is deterministic. (The ∗ ∗ ’s coins.) Now that R is taking expectation over R randomized case then follows by ∗ h deterministic, the hash functions sent ,...,h R by are fully determined by 1 k − q 0 − ’s responses ,...,c c ∈{ 0 , 1 } (refer to Protocol 3.3). Hence, the number of S q IH k − 0 − 1 k ∗ − q − k q R possible different views of is bounded by 2 2 . Thisimpliesthat ) | , V |≤ Supp( ∗ k q ∗ =view V where ( Y ) ,R ( )(1 S , 1 ). By Lemma 6.7, IH R √ √ 1/2 1/2 1/2 q − k ≤ . | Supp( V ) |· CP · ( Y | W ) ≤ ( 2 Y | ( W, V CP )) ( Y | W ) CP W w and V = v , the distri- Observe that given any particular instantiation of = ∗ q k bution of output Y ) ,R 1 )(1 ( , S ( ) | has the same collision probability as w,V = v W IH = S IH 1/2 Y | )) = W, V (indeed, they are in bijective correspondence). Hence, CP ( ( Z | = W = w,V v √ 1/2 1/2 q − k )) ≤ ( 2 ( Y | · CP ( W, V Y | W ). CP Lemma 6.10 ( Let ( S binding of interactive hashing in expected measure ,R ). ) IH IH q 1 0 , . For any fixed subset } be the interactive hashing protocol in Protocol T ⊆{ 3.3 , ∗ ∗ q k S , setting ,R , we have )) C , 1 = output(( )(1 S and for any sender IH +1 k +1 k ( z ) ∈ T }| ] z max { 24 , 2 |{ : E[ C < ( T ) }≤ 24 + 2 · μ · μ ( T ) , ∗ R . and where the above expectation is taken over the coins of S IH This lemma and its proof are inspired by the work of Goldreich, Goldwasser, and Linial [38], who studied a protocol similar to interactive hashing for a different election protocols). purpose (namely, random s 9 1/2 1/2 1/2 )=CP In terms of collision probability, a chain rule would say CP ( Z ) · CP Z ( X | ( ). X, Z 1/2 1/2 2 This is not true in general, as can be observed by noting that (CP / CP = ( Z )) X, Z ( ) ˆ X, Z ) / CP( Z ) equals the expectation CP( X | CP( Z , )over z chosen according to the distribution z = Z 1/2 2 ˆ | X ( / while CP , ) (and any natural definition of conditional Z CP( Z ) ] z = Z ]=Pr[ z = Z where Pr[ ˆ Z . By choosing a random variable Z where Renyi entropy) is defined by taking an expectation over Z ,examplescanbe is very different from X | , and choosing appropriate conditional distributions Z z Z = 1/2 1/2 1/2 constructed where CP ). ( ( Z ) · CP X, Z ( X | Z ) is both much larger and much smaller than CP

28 1180 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN ∗ is deterministic. (Else, Proof. Without loss of generality, we may assume that S ,...,q − =0 j we can fix its coins to maximize the expectation.) Note that for iteration h , partitioning the set of possible outputs into two will send a random k R 1, − IH j ∗ { sets : h y } and { y : h } ( y )=1 ( ,and S y )=0 chooses a side of the partition by j j q sending a bit c h 0, let . For all = { y ∈{ 0 , 1 ≥ j : U denote the ( y )= c } ∀ i

29 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1181 μ Assume that the ’s are monotonically increasing (otherwise, we can make it j so). This gives us − k − 1 q √ ∑ j − q ( − ) μ · 2 μ ≤ μ + k j 0 q − j =0 q − k − 1 √ ∑ √ ( − q ) − j ( μ 2 ≤ μ + ’s are monotonically increasing) μ · k j 0 q − =0 j √ √ k <μ μ · 6 / 2 + q 0 k − μ q − k k − (if μ μ , ) ≤ ≥ 24 · 2 + k − q 0 2 k − giving us μ < 2 μ μ =2 is either less μ T )if μ . This means that 2 · ≥ 24 ( k q 0 k − q − k q − k − · than 24 2 ( μ T ). Therefore, we can conclude that or less than 2 [ ] k q k ∗ ) ∈ T }| E C : S |{ z : C ( z = output(( 1 )) , = μ )(1 · 2 ,R − q IH k k +1 < , 2 max 24 · μ ( T ) } . { 1/2 We are now ready to ana- 6.2.3. Protocol 5.5 is hiding in CP measure. 1/2 lyze the hiding property of Protocol 5.5 in terms of the CP measure. To do so, we 1/2 measure in Definition 6.11 saywhatitmeansforaschemetobe δ -hiding in CP below. But before going into that definition, we first establish some notation that is used throughout this part of the section. 1 ∗ ∗ x With the sender’s input being , we let random variable view ( )denote ( x ) ,R S R c ∗ 1 ∗ R the view of receiver in the first commit phase, random variable output S ( ( x ) ,R ) S c denote the sender’s private output in the first phase, and random variable ∗ 1 ,R ( ) denote the first (commit and reveal) phase transcript. ) x transcript( S x ,we Using similar notation, with the transcript being τ and sender’s input being 2 ∗ ∗ ∗ let random variable view ( x ) ,R ( )( τ ) denote the view of receiver R S in the second R c 2 ∗ S ,R τ ( x ) ) denote the sender’s private ( )( commit phase, random variable output S c 2 ∗ S output in the second phase, and random variable transcript( ) x )( τ )denotethe ,R ( ∗ 1 ∗ Γ second (commit and reveal) phase transcript. We write Γ ( in view ( ) ,R S )— 1 R 1 c and similarly for others—to mean that the sender’s private input is chosen uniformly . from a set Γ 1 For a parameter δ ∈ [0 , 1] Definition 6.11. 2 -phase commitment scheme ( S, R ) , n 1/2 } such measure if there exist two sets Γ 1 , Γ , ⊆{ 0 δ is said to be -hiding in CP 2 1 that the following three properties hold. n (H.1) Γ Γ . = { 0 , 1 } ∩ and μ (Γ δ ∪ Γ ≥ ) 2 2 1 1 ,thesender’s x Γ When the sender’s private input is chosen uniformly from (H.2) 1 private output in the first phase has low collision probability given the re- ∗ ceiver’s view. Formally, for any adversarial receiver R , √ 1/2 − k ( 1) − ≤ V | A ( 2 ) CP 1 ∗ ∗ 1 ∗ Γ ( . )) ( Γ for ) ,R ) = (output ) , view ,R A, V ( S ( ) ( S 1 R 1 S c c (H.3) When the sender’s private input x is chosen uniformly from Γ ,thesender’s 2 private output in the second phase has low collision probability given the re- ∗ and every τ ∈ ceiver’s view. Formally, for every adversarial receiver R

30 1182 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN 1 ∗ Supp(T) ( Γ T=transcript( ) ,R S ) , we have ,where 2 √ 1/2 − ( k − 1) CP 2 W ( ) ≤ | B τ τ 2 ∗ ∗ 2 ∗ S S ,W | ( Γ )) ) for ( ) , view ) = (output . ( B ( ,R ( Γ ) ,R 2 R 2 τ T= τ τ S c c 1/2 measure in Definition 6.11 roughly means Remark Being δ -hiding in CP 6.12. that the scheme is always hiding in at least one phase, and hiding in both phases . occurs with probability δ 1/2 n 0 f : measure ). , 1 } Let → { )-hiding in CP Protocol 5.5 is (1 /n Lemma 6.13 ( − 1 n 2 n 2 ) ( y | |∈ [2 n f 2 , /n be any function (not necessarily one-way) such that ] 0 } , { 1 n ∈{ y 1 } , for every 0 n 2 2log n , t ,...,n − 2log ∈{ } such . There exists an integer 0 5.5 , with setting of parameters t = t that Protocol , Δ ,andany =Δ = 2log n 2 0 1 1/2 measure. (1 /n ) -hiding in CP ,is ,...,q ∈{ } 1 k ∗ is deterministic since Without loss of generality, we may assume that Proof. R ∗ that maximize the above collision probabilities. We prove R we can fix the coins of that ( S, R ) satisfies the above three properties of Definition 6.11 as follows. . Define p ( y )=Pr[ f ( U Property (H.1) , y ∈{ 2log n t 2 ,...,n − ], and for )= n n − +1 t t n − A ,let } 2log n } p :2 = { ≤ y ( y ) < 2 ∈{ 0 , } .Since ∪ ), A 1 = f ( { 0 , 1 } t t t t there exists an index ( U ) ∈ A ] f such that Pr[ ≥ 1 /n . Define sets Γ and Γ as 1 0 2 n t 0 follows: − t +1 0 )) ( f ( x { = 2 < x : p } , Γ 1 − t 0 { x : p ( f ( x )) ≥ 2 . } = Γ 2 By the definition of Γ ∈ (Γ ∩ Γ )=Pr[ f ( U μ ,wehavethat A ] ≥ 1 /n , and Γ ) 1 2 1 t 2 n 0 n and also Γ 0 = { ∪ , 1 } Γ . 2 1 In the case when the sender’s private input x ∈ Γ Property (H.2) . , we bound 1 the collision probability of the first phase secret as follows: ( ) 2 ∑ p ) y ( )) = ( f CP( Γ 1 μ (Γ ) 1 ) (Γ f ∈ y 1 ⎞ ⎛ ( ) ∑ 1 ⎠ ⎝ p ( y ) · · ≤ max ) y ( p 2 μ ) (Γ f ) y (Γ ∈ 1 1 (Γ ) f ∈ y 1 − t +1 2 − 0 < (Γ · ) · μ (Γ 2 ) μ 1 1 ( t − log n − 1) − 0 ≤ 2 (since μ (Γ . ) ≥ 1 /n ) 1 t ( Δ − ( t − − +3) n − 1) − log 0 0 1 ( Γ f Observe that CP( 2 2 ≤ )) . Therefore, we can apply ≤ 1 √ (1) 1/2 q − ( − 1) the Randomness Extraction Lemma, Lemma 6.6, to get CP ≤ 2 Z , ( ) (1) where Z =( H ( f ( Γ ,H ))) and H is an independent random hash from H . 1 1 1 1 1 ∗ 1 S ( ( Γ S ) ,R ) denote the private output of the sender A Next, let = output 1 S c in the in the first phase of Protocol 5.5, which in turn is equal to the output of S IH ∗ (1) interactive hashing protocol, so equivalently A = output ,R S ( Z ). Similarly, ) ( IH S IH ∗ ∗ 1 ∗ =view V let ,R Γ ) R ( ) denote the view of the adversarial receiver S ( in the first 1 R c ∗ in the interactive hashing protocol, so phase, which in turn is equal to the view of R ∗ (1) ∗ equivalently V =view ,R S ( Z ( ) ). R IH The final step is to use the hiding property of interactive hashing given by Lemma 6.9 to bound the collision probability of A (the private output of the sender

31 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1183 ∗ (the view of the adversarial receiver R )given S V ) as follows: √ √ √ √ √ 1/2 − k (1) 1) q − k q ( q − − ( k − 1) − CP 2 Z 2 ) ≤ ≤ = A 2 ) 2 · V CP( . · | ( ,weanalyze In the case when the sender’s private input ∈ Γ x . (H.3) Property 2 the collision probability of the second phase secret as follows. First we observe that for ′ n ′ , 1 } ∈{ such that f ( x )= f ( x 0 ), the first phase transcripts for both x and x, x any 1 1 ′ ∗ ′ ∗ x ) ) transcript( S are identically distributed, that is, transcript( ( x ,R ≡ ,R ) ). x S ( 1 ∗ S Thus, if we fix a first-phase transcript τ ∈ transcript( ,R ) containing a value x ( ) − 1 Γ is equally likely to = ( y ) ⊆ f ) in the reveal phase, any element in Γ y = f ( x 2 ,y 2 . Also observe that the Γ τ have generated ’s form a partition of Γ . 2 ,y 2 t n − − − ) n ( t 0 0 Γ | Note that by definition, |≥ 2 , and hence CP( Γ ≤ ≤ ) 2 ,y ,y 2 2 Δ ( − t − − n +3) 2 0 2 . Therefore, we can apply Randomness Extraction Lemma, Lemma 6.6 √ (2) (2) 1/2 − ( q − 1) ( ) for Z 2 =( H Z ,H ( Γ )). ≤ to get CP ,y 2 2 2 2 ∗ B Next, let ( S = output τ ( Γ )( ) denote the private output of the sender ) ,R ,y 2 τ S c in the interactive S in the second phase, which in turn is equal to the output of S IH ∗ (2) B hashing protocol, so equivalently W ). Similarly, let ( S = ( Z = output ) ,R IH τ τ S IH ∗ 2 ∗ ∗ view )( ,R ( ( τ ) denote the view of the adversarial receiver R Γ in the second ) S ,y R 2 c ∗ in the interactive hashing protocol, so phase, which in turn is equal to the view of R ∗ (2) ∗ equivalently W ). ( Z S ) ,R =view ( R IH τ The final step is to use the hiding property of interactive hashing given by Lemma 6.9 to bound the collision probability of B (the private output of the sender τ ∗ (the view of the adversarial receiver ) as follows: R )given S W τ √ √ √ √ √ 1/2 (2) q − q − k k − ( q − 1) 1) − ( k − CP | · W 2 · ( CP( Z ) = ) 2 ≤ B 2 2 . ≤ τ τ 6.2.4. Protocol 5.5 is 1-out-of-2 binding in expected measure. The def- inition of 1-out-of-2 binding in Definition 5.4 considers the first phase (resp., second ∗ produces valid decommitments to two differ- phase) to be broken if the sender S p., second commit stage ). In this section entvaluesafterthefirstcommitstage(res ed notion where we simply bound the ex- and section 6.3, we will work with a relax pected number of values to which a cheating sender can open. To this end, we define 2 ∗ 1 ∗ ,R ) (resp., openings( S )) to be a random variable denoting the set ,R S openings( of values to which the sender successfully opens in phase 1 (resp., phase 2), where “successfully” opens is defined for each phase analogously to Definition 5.4. (Defini- tion 5.4 refers to sender strategies tha t produce decommitments to one or two values in each reveal phase; here we consider a natural generalization where the sender tries to decommit to many values in each phase.) More formally, for a 2-phase commitment 1 ∗ ) as follows: ,R B )( S, R , we define openings( B S scheme ( ) and a “binding” set ∗ 1 (1) • S and interact to get first-phase commitment c R . c (1) (1) ∗ outputs a sequence of values d ,...,d and cor- • S After the interaction, 1 λ responding full transcripts ,...,λ ), of both phases. Recall that λ ,κ =( τ i i i 1 are the first-phase and second-phase transcripts, respectively. κ and τ where i i (1) ∗ 1 We let openings( • S ) be the set of distinct values B whose opening ,R )( d i (1) λ contains begins with prefix c λ , is valid, where by valid we mean that λ i i i (1) (1) a decommitment of c d to the value , with first-phase transcript τ ∈B / i i 1 2 R and both R . λ accept in and i r r 2 ∗ S Analogously, we define openings( ,R )( τ ), where τ is a first-phase transcript, as follows:

32 1184 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN ∗ 2 (2) and interact to get seco nd-phase commitment c • . S R c (2) (2) ∗ S • After the interaction, and cor- d outputs a sequence of values ,...,d 1 ,...,λ . λ responding full transcripts 1 (2) 2 ∗ • We let openings( S d τ ,R whose opening )( ) be the set of distinct values i (2) λ is valid, where by valid we mean that c starts with prefix (which in λ i i (2) τ as a prefix), λ turn contains contains a decommitment of to the value c i (2) 2 ,and R accepts in λ . d i r i Now, we can describe the binding property of Protocol 5.5 in this language (even when the underlying one-way function has unknown security). Lemma 6.14 ( Protocol 5.5 is 1-out-of-2 binding in expected measure ). For every ∈{ 1 , 2 ,...,n } , k integer O (log n ) , Δ t = = (log n ) ,and Δ ,the O O (log n ) = 2 1 2 -phase commitment scheme ( S, R ) in Protocol 5.5 based on following holds for the n n →{ 0 , 1 } : } f , 0 1 : one-way function { for ( S, R ) where the following hold. B There exists a binding set ∗ can break the first-phase binding with S (B.1) No PPT adversary nonnegligible probability in the sense of Definition 5.4 . That ∗ 1 ∗ ) openings( | ,R , we have )( B S |≤ 1 with S is, for every PPT ∗ 1 neg( n ) over the coins of S probability 1 − R and . c ∗ , and every adversarial sender ∈B τ For al l (B.2) S ∣ ∣ ] [ ∗ 2 ∣ ∣ S openings( , < 2 E ,R ) )( τ ∗ S where the above expectation is taken over the coins of and 2 . R . We follow the proof of the binding property in Lemma 5.9, using both Proof n :Pr[ ] ( U ≤ )= y f } Claims 5.11 and 5.10 from that proof. Let B = { y ∈{ 0 , 1 n − Δ − t 3 } be the same binding set as defined in both claims. We set Δ =Δ + 2 2 3 Δ 2 − − k/ ) Ω(Δ 2 3 n ) · 2 (log O n ) to be large enough so that the binding parameter poly( · 2 k − k = in Claim 5.11 is at most 2 (log n ).) Now, . (Thiscanbedonesince O τ ∈B , then the second commitment phase is binding. Claim 5.11 states that if ∣ ∣ k ∗ − 2 ∣ ∣ ≥ 2 with probability at most 2 )( ,R ) .Since τ S openings( This implies that ∣ ∣ ∗ 2 k ∣ ∣ 2 ≤ openings( S ) )( (the commitment is to a k -bit string), taking expectations τ ,R we have ∣ ∣ ] [ k − ∗ k 2 k − ∣ ∣ ) . 2 ,R · 2 < ) +1 · (1 − 2 )( τ 2 ≤ E S openings( ε ( ε To see why property (B.1) holds, let n ) be the probability for which PPT = ∗ S breaks the first phase binding. Observe that the inversion success probability of f from Claim 5.10 is )) O (1) n (log O + +Δ +Δ k ( − ( k +Δ − +Δ (1) ) O 1 1 3 2 / poly( n ) · 2 ε 2 · ) · n 1 poly( / 1 · = ε O (1) ε , = n ) poly( since all Δ k, ) to be a negligible function. , Δ n = O (log n ). This forces ε ( 2 1 6.3. Converting weakly hiding to strongly hiding commitments. In the previous section, we established that Protocol 5.5, with appropriate choice of pa- 1/2 measure (hence, only weakly hiding ), and 1-out-of-2 /n -hiding in CP rameters, is 1 binding in expected measure. Our goal in this section is to show how to boost the

33 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1185 =1 − neg( n ), therefore making the scheme strongly hiding , hiding probability to δ while maintaining the 1-out-of-2 binding property. We first show how to double the hiding probability by combining a constant num- hen repeat this doubling amplification ber of schemes to obtain a new scheme. We t n (log to a constant c> 0, ) times to boost the hiding probability from 1 O process /n ) n hence obtaining an Ω(1)-hiding scheme. Finally, we boost it all the way to 1 − neg( by combining polynomially many Ω(1)-hiding schemes. This is all achieved via a hiding amplification procedure stated next. (See section 6.1 for an overview.) Algorithm 6.15. Hiding amplification procedure, denoted as Amplify . ) . S, R ( Input: 2 -phase commitment These are given in unary and are listed below: Additional Input Parameters: . Security parameter 1. n of schemes S, R ) to be combined. 2. ( Number m denoting S 3. Integer r ’s private input length. k denoting S ’s private output length. Integer 4. ′ denoting ’s private output length. S k Integer 5. α Integer thresholds 6. α and , for the first and second commit phases, 1 2 respectively. 6.16 R ) , as described by Protocol , . -phase commitment S ( Output: 2 To reduce unnecessary clutter, we write ( )= Amplify ( S, R ) when the rest of S , R ear from context. the parameters are cl ( S , Protocol 6.16. ) from hiding amplification of base Amplified scheme R ( ) . scheme S, R mr } . ,...,x 0 ) ∈{ 1 , x =( x Sender’s private input: 1 m First-phase commit: 1 1 1 1 1 ,using S ) do m sequential executions of ( S ’s private for ,R , x ) R S 1. ( i c c c c c 1 1 th execution. Let S input in the ( i x ,R ]( i [ ) ]) denote the i th execution [ i i c c 1 1 k 1 1 ]( ) a ,R = output ,andlet ( S , 0 [ i . Define x ) ,R ∈{ } [ i ]) 1 of ( S i i S c c c c a =( a ) . ,...,a m 1 α mk 1 Let H 2. , be a family of pairwise-independent , 1 } h →{ 0 0 1 } { = } { : 1 1 1 and computes h chooses a random hash ←H S hash functions. 1 1 (1) q y )) ,h . ( a =( ∈{ 0 , 1 } h 1 1 ′ 1 k 1 q (1) 1 1 S 3. ( S , R y , ) ,R ) ) )(1 run the interactive hashing protocol , 1 ( ( c c IH IH 1 1 1 1 acting as and R and R , respec- S given by Protocol ,with 3.3 S IH IH tively. ′ (1) q k ∈ } →{ d be the common output, and 0 , 1 } , 0 { : Let circuit C 1 ′ ′ k 1 1 (1) 1 q k } 0 , 1 { . ( y be ) ,R ’s private output in ) )(1 ( , 1 S S IH IH IH ′ (1) k First-phase sender’s private output: String d } . 0 , ∈{ 1 First-phase reveal: (1) (1) (1) 1 (1) (1) S sends tuple ,a,h is the first phase ) ◦ ( γ γ ) ,...,γ =( γ d ,where m 1 r 1 i 1 1 1 revelation string of S ] in the above execution of ( S [ . [ i ]( x ]) ) ,R i i [ i r r r 1 (1) 1 i accepts if and only if C ( d accepts )=( h [ ] ,h ( a )) and R R Receiver 1 1 r r (1) ( γ . ) for all i ∈{ 1 , 2 ,...,m ,a } i i Second-phase commit: Second-phase common input: Transcript containing ( τ τ ,...,τ ) ,where m 1 1 1 i =transcript( [ i ]( x S ) ,R . [ ]) each τ i i 2 2 2 2 2 S 1. ( m sequential executions of ( S ’s secret ,R , ) ) ,using x do for S R i c c c c 2 2 ]( th execution. Let ( S ,R [ i in the x denote ) ) i τ [ i ])( and transcript τ i i i c c 2 2 2 2 S the i th execution of ( x . Define ) = output τ ( S ) ])( [ i ]( b i ) ,R ,R [ ∈ i i i S c c

34 1186 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN k { ,andlet b =( b } ,...,b 0 ) . , 1 1 m mk α 2 H Let 2. = , 1 } { →{ 0 h 1 } 0 : } be a family of pairwise-independent { , 2 2 2 chooses a random hash h ←H and computes hash functions. S 2 2 q (2) y ,h b )) ∈{ 0 , ( } =( . h 1 2 2 ′ 2 2 2 (2) 2 q k S 3. ( R , ( y , ) ,R ) ) )(1 run the interactive hashing protocol , 1 ( S c c IH IH 2 2 2 2 , respec- and acting as S R R and given by Protocol 3.3 ,with S c c IH IH tively. ′ q (2) k be the common output and 0 d 1 ∈ } →{ , } Let circuit C : { 0 , 1 ′ ′ q k k 2 (2) 2 2 } 0 { 1 , y S ) ,R be ( )(1 S , 1 ’s private output in ( ) . IH IH IH ′ (2) k d Second-phase sender’s private output: String 0 } , . ∈{ 1 Second-phase reveal: (2) (2) (2) 2 (2) (2) S γ ,b,h is the second- ) ◦ ( γ sends tuple =( ,...,γ d γ ) ,where m 2 r 1 i 2 2 2 phase revelation string of S S ) [ [ i ]( x i ] ,R in the above execution of ( [ i ]) . i r r r 2 2 (2) (2) R Receiver )) d h ( ,h C ( b )=( and R accepts if and only if accepts [ i ] 2 2 r r (2) ,...,m ,b . ) for all i ∈{ 1 , 2 } ( γ i i Starting from a weakly hiding scheme ( S ) of Protocol 5.5, we iteratively apply ,R 0 0 the amplification process Amplify , as described by Algorithm 6.17 below, to achieve S , R ) that we will show to be statistically hiding. Let D> 1denotea anewscheme( large enough integer constant. We will set the number of schemes to be combined to be D in all but the last iteration, in which we set m = n . m = Algorithm 6.17. Iterative amplification procedure. n n D> 0 } →{ , constant integer 1 1 , and thresholds t ∈ , Input: } f : { Function 0 , 1 1 , 2 ,...,n } , β { 1 ,...,β ∈{ 0 , 1 ,...,D − 1 } , β . } ∈{ 0 , ,...,n 1 +1 -phase commitment =(16 D ) ) ,and ( S 2 ,R be the · = log n , k 1. Let 0 0 0 n n f , 1 } scheme based on function : { 0 1 , from Protocol 5.5 using →{ } 0 . n 2log ,and Δ = =Δ k = k , t parameters 2 0 1 j =1 , 2 ,..., , repeat the following: 2. For k Set (a) D k = . 8 8 − − j j 1 − m for settings of parameters ) ,R ,R ( )= Amplify = S S ( Set (b) j − 1 j 1 j j − j − 1 ′ D = , n · D r = k , 3 − , k , = k 1) , α − =( β k k +1)( j − 1 1 j 1 − j j α and =( D − β . )( k 3 − 1) − 1 − 2 j j n D , ) for settings of parameters m = ,R , r = n · Set ( S S ( , R )= Amplify 3. ⌊ ⌋ ⌊ ⌋ 1 1 ′ = k k , = , ( β k ) + k δn δn ) k = ,and α n = , ( n − β α + +1 2 +1 1 3 3 δ =1 /D . where -phase commitment scheme ( S , R ) Output: 2 . runs in polynomial time, ,R ) used by Algorithm 6.17 If scheme S Lemma 6.18. ( 0 0 then scheme ( S , R ) , the output of Algorithm 6.17 , also runs in polynomial time. O (log n ) D n = n · =poly( ) executions of n · D Proof , R S ) consists of .Scheme( ( S ,R ). In addition, each amplification procedure Amplify adds an overhead time of 0 0 n poly( ing interactive hashing. Since there ) since both the sender and receiver are do 1 − 2 ) amplification steps, the overhead n =poly( + ··· + D nD + + n are only 1 + nD S ) runs in polynomial time if ( R time is polynomial. Hence, scheme ( S , )does, ,R 0 0 too. The rest of this section, which is technica lly involved, is devoted to proving the hiding and binding properties of the final scheme ( S , R ). (In process, we also analyze ,R ).) the hiding and binding properties of intermediate schemes ( S j j 6.3.1. Hiding amplification. The following two lemmas, Lemmas 6.19 and 1/2 measure) 6.20, provide us with a way to understand the hiding property (in the CP of amplified scheme ( S , R ) in terms of its base scheme ( S, R ). Lemma 6.19 basically

35 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1187 says that the hiding probability doubles when we go from ( S )to( S ,R )= ,R 1 j 1 j j − − j S Amplify ( ,R ) (refer to step 2(b) in Algorithm 6.17). So if we start up with a 1 j j − − 1 )with ,R ,R S ), in =log n iterations, we will get a scheme ( S -hiding scheme ( 1 /n 0 0 Ω(1)-hiding. Lemma 6.20 essentially argues that the final amplification step boosts n ) (in both phases) when starting from the hiding probability all the way to 1 − neg( a scheme that is Ω(1)-hiding. With these two lemmas, we can establish that the final ,R ) is statistically hiding in both phases. S S )= , Amplify ( scheme ( R ). For every sufficiently Lemma 6.19 ( intermediate step hiding amplification + 1/2 , the following holds: If scheme ( S, R is δ -hiding in CP ) Z D large constant ∈ β 0 , 1 ,...,D − 1 } such that scheme ( S , R )= measure, then there exists an integer ∈{ ′ α ,and 3 − 1) − k +1)( = k − 8 D − 8 , β =( m S, R ( k , D = ) , with parameters Amplify 1 ′ 1/2 ′ α β )( k − 1) − 3 ,is δ { -hiding in CP =( measure for δ D =min − 2 δ, 1 /D } . 2 ∗ Proof. Without loss of generality, we may assume that R is deterministic since ∗ that maximize the collision probability. Throughout this R we can fix the coins of D m .Letthe will be fixed to proof, the value of , although we will keep writing m ) be (H.1), (H.2), and (H.3), δ -hiding properties, as stated in Definition 6.11, of ( S, R ′ .1), R ) satisfies Definition 6.11 with Properties (H , respectively. We will prove that ( S ′ ′ ′ (H .3) by showing that Property (H.1) implies (H .1), and so forth. .2), and (H ′ S, R .1) . Let Γ and Γ be the corresponding sets for ( ). (H Property (H.1) implies 2 1 ′ ′ Define the sets Γ and Γ β will be determined later): in terms as follows (the value of 2 1 ′ , = { ( x } ,...,x Γ ): ∃ i ∈ ,...,i ,...,x x such that Γ m β i +1 1 1 1 i 1 1 +1 β ′ . = { ( x } ,...,x Γ ): ∃ i ∈ ,...,i ,...,x x such that Γ β − m i i 1 2 1 m 1 β − m 2 ′ r ′ 0 together with the fact that Γ ∪ and Γ ,it = { } , 1 Γ By the way we defined Γ 1 2 1 2 ′ ′ mr is the case that Γ Γ are x = { 0 , 1 } ∪ . This is because either at least β +1 of the i 2 1 ′ )orelseatmost ) ∈ Γ (in which case, ( ,which ,...,x β of the x are in Γ x in Γ i 1 1 1 m 1 ′ m β of the x − implies that at least (in which case ( x ). ,...,x are in Γ ) ∈ Γ m 1 i 2 2 ′ We are given that μ (Γ . What we need to ) ≥ δ . Define δ ∩ Γ { δ, 1 / (2 m ) } =min 2 1 ′ ′ ′ ′ ∩ Γ δ S ) ≥ δ . )= S ⊆ Γ ( ∩ Γ μ such that . Choose any subset show is that (Γ μ 1 2 1 2 Hence, we have − m ′ − 1 1 m ′ ′ ( mδ x 1)) ∈ S ]= mδ − (1 − δ m ) [exactly one / 1 ≥ − (1 Pr i r 0 , 1 } ,...,x ←{ x 1 m ′ ) mδ . =Ω( x ∈ . S , assume without loss of generality that S ∈ Given that exactly one x m i ’s x 1 denote the conditional probability that exactly t of the rest of the m − p Let i t are in Γ \ β ∈ [0 ,m − 1] to maximize .Choose , i.e., β =argmax p Γ .Let I p 2 t 1 i t t i , 2 ,...,m − =1 x ∈ Γ for or 1 be a binary random variable indicating whether i 1 not; note that these are independent random variables conditioned on the fact that I .Let μ be the mean of the S ∈ ’s. By a Chernoff bound, x i m ∣ ∣ [ ] ∣ ∣ √ ∑ √ 2 ∣ ∣ / − (( m − 1) 1) 3) · (3 / m Pr − μ − 1 · ≤ 2 e ( m − 1) . 2 m < / I 1 3 > ∣ ∣ i ∣ ∣ i · μ m − This means that greater than half of the probability mass is in the interval ( √ ± 1) 3 − 1. Since we chose β =argmax m p in a maximal way, we have t t ( ) 1 √ ]=Ω S ∈ x \ | [exactly β of x S ’s are in Γ exactly one . Pr 1 i i r ,...,x , } ←{ 1 m x 0 1 m

36 1188 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN r { 0 , 1 } ∪ ,ifexactly Γ of x ’s in Γ \ S and exactly one = Knowing that Γ β 2 1 1 i x .Consequently, − 1 − β of x , then there must be at least ’s in Γ ∈ \ S m S i 2 i ( ) 1 ′ ′ ′ √ Pr [( x ,...,x Ω mδ ) ∈ Γ · ]=Ω( ∩ Γ ) m 1 2 1 r } 1 , 0 ←{ m x ,...,x m 1 √ ′ =Ω( mδ ) ′ =min 2 δ, 1 /m } , { 2 > δ = D is a large enough constant. where the last inequality holds when m ′ 1 ∗ (H Property implies (H.2) . ,R In the first commitment phase ( S .2) ), the cheat- c 1 ∗ ing receiver R sequential executions of S m . Herewemustanalyze interacts with c 1 ), ’s private input in these m executions, given by x =( x ,...,x S the case when 1 m c ′ is distributed uniformly in Γ .Welet A ( x ) denote the private output of the sender i 1 being the private input ( x ) the view of the receiver in the i th execution, for x and V i 1 S for i =1 ,...,m , .Thatis,for c 1 ∗ A ) = output )); ( S ,R ,...,V ( x V ) ( x ( i 1 − 1 i i S c 1 ∗ ∗ ( ( x ) S ,R ( V ,...,V x )) . ( )=view V 1 R i 1 i i − c th execution is independent of the pre- i Note that while the sender’s behavior in the vious executions, the cheating receiver may ts previous views. base its strategy on i ′′ ′′ ′ ′ 1/2 ′ ′′ ′ ′ We want to bound CP ( ( V )), where A | ( Γ ) )=( A ( Γ Γ Γ ) ,...,A )) ( Γ ( A m 1 1 1 1 1 1 ′′ ′ ( Γ )= senders, and V m represents the combined first-phase private outputs of the 1 ∗ ′ ′ ( V R ,...,V ( Γ Γ )) represents the view of ) ( when interacting with these m senders. m 1 1 1 ′ represents an independent random element from the Note that random variable Γ 1 ′ set Γ I ⊆ [ m ]ofsizeatleast β + 1, the ran- . To do this, we consider, for each 1 ′ ′ Γ dom variable S ,where for private input of the sender | | represents choos- Γ I I 1 1 Γ i/ i ∈ I , and uniformly in for . Togetabound for uniformly in Γ ∈ I ing x 1 i 1 1/2 ′′ ′ ′′ ′ on CP A )), we will have to refer to Lemma 6.5 and see why the | | ) | V ( ( Γ Γ ( I I 1 1 ( A )’s satisfy the two conditions of the lemma. ,V i i ′ ′ Γ ,...,V | | )= )= v Γ ( ( Conditioned on the any previous view—namely, V I 1 I − i 1 1 1 1 √ ′ ′ 1/2 − 1) − k ( v ≤ ( A —it is the case that CP ( Γ for any v | 2 ) | V )) ( Γ ,...,v | i 1 − 1 I i 1 − i i I 1 1 ∗ can incorporate . This follows from Property (H.2) because the receiver R ∈ I if i ∗ v the previous view is unbounded), and then the only R ,...,v as advice (since 1 − 1 i ′ randomness in the definition of A Γ is the sender’s coins x ,whichare V ( and ← ) | I i i i i 1 ). This shows that the first condition (even conditioned on v ,...,v uniform in Γ 1 − 1 1 i of Lemma 6.5 is satisfied. ′ )= Γ | ( V For the second condition, what we need to show is that conditioned on I 1 1 ′ ′ ′ ′ v Γ Γ )arein- | ,...,V )= v ( , the random variables A ,V ( Γ | ) | | ) ,...,A ( ( Γ i I 1 i +1 i I I 1 i I 1 1 1 1 i as follows. It is vacuously true for dependent. This can be seen by induction on = j − 1, we prove it for i = i as follows. First = 0. Assuming it is true for i j ,...,v . By inductive hypothesis, A ,...,A ,V are independent v condition on − j − 1 1 j 1 j 1 ′ Γ (omitting | from the notation for readability). Moreover, since we have conditioned I 1 ′ , the sender’s ,wehavethat ) and V are functions of only ( Γ | ,...,v A v on 1 j − 1 I j j j 1 coins in the A th execution, which is independent of j ,...,A (becausewehave 1 − j 1 ′ ′ A | v ) = ,..., , Γ remains | V ) so far). Thus, if we condition on ( Γ used only ( I j 1 1 j − j j I 1 1 independent of A A because now it is ,...,A . V ,...,A is independent of − +1 1 1 j j j 1 ′ Γ only a function of ( | , which has not been used yet. ) j I +1 1 Applying Lemma 6.5, we have √ 1/2 ′ ′′ ′ ′′ +1)( k − β ( 1) − | V Γ ( Γ A , | | )) ≤ ( 2 ) ( CP (3) I I 1 1

37 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1189 √ 1/2 1) − k ( − ,CP since from property (H.2) it is the case that for all ∈ i I ≤ A 2 V | ( ) i i | |≥ β +1. I (even conditioned on the previous views), and ′ ′′ ′ 1/2 ′ ′′ is uniform in Γ ) V Γ ( Γ ( ( )) where X | A ,weobservethat Now, to bound CP 1 1 1 ′ ′ Γ of size at least = | +1 given by ,where I is the random variable on subsets I Γ β I 1 1 = I ]= Pr I Pr [ x . ] I = } [ { i : Γ ∈ i 1 ′ ) ( Γ ← x ,...,x 1 m 1 ′ can be broken into two steps; first sampling an In other words, sampling from Γ 1 , and then sampling x I ←I Γ Γ for i ∈ ← ,and x . Therefore, we ← I ∈ for i/ I 1 1 i i have 1/2 ′ ′′ ′′ ′ ′′ ′ 1/2 ′ ′′ CP | Γ | V | )) ≤ CP ) ( A Γ ( Γ ( ( | ) | ( V A ( Γ ( (by Lemma 6.7) | ) , I )) I I I I 1 1 1 1 ] [ 1/2 ′′ ′ ′′ ′ Γ A )) | | ( | V ) ( Γ ( CP =E I I 1 1 ←I I √ β +1)( − − 1) k ( ≤ 2 (4) √ − ( α +3) 1 = , 2 with the last inequality following from (3). Therefore we can apply the Randomness √ 1/2 ′′ ′ ′′ ′ ( − q − 1) Extraction Lemma, Lemma 6.6, to get CP ,H )) | V , ( Γ ( A )) ≤ ( 2 ( H Γ 1 1 1 1 H where is an independent random hash from . H 1 1 1 ′ ∗ ′ S ( in = output ) ,R (Γ ) denote the private output of the sender S Next, let A S 1 S the first phase, which in turn is equal to the output of in the interactive hashing IH ′ ′ ∗ ′′ protocol, so equivalently A S = output ( Q ) ,R ))). Γ ), where Q =( H ( ,H ( ( A 1 IH 1 S 1 IH IH ′ ′ ∗ 1 ∗ ∗ =view R (Γ S ) denote the view of the adversarial receiver ) ,R ( V Similarly, let R 1 ∗ R in the first phase, which in turn is equal to the view of in the interactive hashing ′ ′′ ′′ ∗ ∗ protocol together with V ( ,V =(view ( Q ) ,R ,soequivalently S ) V )forthe R IH IH IH ′ ′′ ))). ( A ,H ( Γ same H =( Q 1 1 1 The final step is to use the hiding property of interactive hashing given by ′ (the private output of the sender A Lemma 6.9 to bound the collision probability of ′ ∗ )given S V ) as follows: R (the view of the adversarial receiver √ √ √ √ ′ ′ ′ 1/2 ′′ ′ ′ 1/2 − q − k k 1) q ( q − 1) − ( k − − CP 2 · A ( Q | V ) ) = ( 2 ≤ | 2 V · CP . ≤ 2 ′ ′ ′ (H.3) implies (H Property τ ∈ .3) Supp(T . ), where random Fix a transcript ∗ ′ 1 ′ ′ τ Γ ) ,R S ). Transcript contains first-phase transcripts ( =transcript( variable T 2 ( τ ,...,τ ). Similarly to the above proof of Property )forthe m executions of ( S, R m 1 ′ .2), we define the following random variables: (H 2 ∗ B , ( S τ ( ( x ) ,R x ( W ,...,W ) = output )( )) i i − 1 i 1 i S c 2 ∗ ∗ ,R S x , ( x ( )=view ( ( W ,...,W )( τ )) ) W − i R 1 i 1 i i c x where is the private input of the sender in the i th execution of the ( S, R ). As above, i ′′ ′′ ′′ 1/2 ′ ′ ′ B ) | W ( ( X ( X )), where random variable B )= ( X we want to bound CP τ τ τ ′ ′ ( B )) represents the combined second-phase private outputs of the ,...,B ) ( X ( X τ m τ 1 ′′ ′ ′ ′ senders, and random variable W m ,...,W )) represents the X X ) ( ( X ( W )=( 1 τ τ m τ ∗ ′ when interacting with these m senders, with X being a shorthand for R view of τ ′ ′ ′ Γ ⊆ ,the β − m | . To do this, we consider, for each subset J ]ofsizeatleast [ m Γ τ )= T( 2 2 represents choosing X ,where for private input of the sender S random variable X J J x J uniformly in Γ ∈ for i . J and uniformly in Γ i/ for ∈ 2 2 i

38 1190 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN ′ ′ )= It is important to note that even when we condition on T ,thecompo- τ ( X J ′ ′ X nents ( | X )of ,...,X remain independent, and the distribution of X m i J 1 τ X ( T )= J | X is equivalent to , where we condition only on the transcript of the i th ex- i )= T( τ X i i X ecution. (Similarly to the inductive proof above, it can be shown that ( ) ,...,X m 1 1 V are independent given the receiver’s view S . The only ad- of the m executions of m c ’s in the first phase is ( A ,...,A ), where ditional information revealed about the X i 1 m A X V once we condition on is a function only of .) m i i 1/2 ′ ′ ( B )) ( X ≤ X ) | W ( ,CP i J ∈ Thus from property (H.3), we have for all i J,τ i J,τ √ ′ 1) − ( k − ′ ′ ′ ′ X 2 | , and this holds even conditioned on the | Γ = ,where J,τ J ( | Γ )= τ T 2 J 2 previous views. Similarly to the first phase, we apply Lemma 6.5 to show that √ 1/2 ′′ ′′ 1) k − − ( m − β )( ′ ′ ( )) ≤ . 2 B ) | W X ( X ( CP J,τ J,τ ′ ′ Again, analogously to the first phase, we observe that X for an appro- = X τ J ,τ − β , and thus m J priate random variable on sets of size at least √ ′′ 1/2 ′′ β − 1) k m )( ( − − ′ ′ )) ) (5) 2 X ( W | ≤ X ( B ( CP τ τ √ +3) − ( α 2 . 2 = By the Randomness Extraction Lemma, Lemma 6.6, we get √ 1/2 ′′ ′′ q − − 1) ( ′ ′ CP 2 )) | W ,H ( X . ( )) ≤ B ( ( X H τ 2 2 τ The final step is to use the hiding property of interactive hashing given by (the private output of the sender Lemma 6.9 to bound the collision probability of B τ ∗ (the view of the adversarial receiver R ) as follows: )given S W τ √ √ √ ′ ′ 1/2 ′ ′ 1) − 1) − q ( k − q − k ( − CP · ≤ ) 2 . = W 2 | 2 ( B ′ ′ τ τ Lemma 6.20 ( final step hiding amplification ). The following statement holds 0 and every integer k ≥ 100 /δ : If scheme ( S, R ) is δ - for every constant δ> 1/2 such that scheme β ∈ [0 ,n ] measure, then there exists an integer CP hiding in ⌋ ⌊ 1 ′ δn ) + β ( k = α , n ,and = Amplify k ( = m , with parameters ) S, R ( , n )= R , S 1 3 ⌊ ⌋ 1 ( n − β + = 5.3 δn ) k . , is statistically hiding in the sense of Definition α 2 3 Proof .Letthe δ -hiding properties, as stated in Definition 6.11, of ( S, R )be(H.1), S , R ) is statistically hiding, it (H.2), and (H.3), respectively. To prove that scheme ( ′ ′ nr , such that the following hold for ⊆{ 0 , 1 } Γ suffices to show that there exist sets Γ 2 1 ∗ every adversarial receiver R : ′ ′ ′ − Ω( n ) (H (Γ μ (Γ ) ≥ 1 − 2 .1) Both . ) ,μ 1 2 ∗ ′ ′ 1 ′ ′ ′ ′ − Ω( n ) A -close to ( ), where A ,V = output U ( S )is2 ,V ( Γ .2) ( ) ) ,R (H n S 1 c in the first phase, and S denotes the private output of the sender ′ 1 ′ ∗ ∗ ( ) denotes the view of the adversarial re- =view Γ ( S ) ,R V R 1 c ∗ ceiver R in the first phase. ′ ′ ) ′ n Ω( ′ − ′ ′ (H -close to ( B ), .3) For all )is2 ), ( Supp(T ∈ τ ,W U ,W ′ ′ ′ n τ τ τ ′ ′ ∗ 2 ′ ( ,W ) = (output ) ( S ,R ) Γ , B where random variable ( ′ ′ S 2 c τ τ ∗ ′ 2 ′ ′ ′ ∗ view Γ ) ,R ( )) | = S , and random variable T ( τ T R = 2 c ′ ∗ 1 ′ S transcript( is the private output ,R Γ ). In other words, B ) ( ′ 2 τ S in the second phase given that the first-phase of the sender ′ ′ and W is the view of the adversarial receiver τ transcript is ′ τ ∗ in the second phase given that the first-phase transcript is R ′ τ .

39 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1191 ′ (H.1) (H implies Property .1) and Γ be the corresponding sets for ( S, R ), Let Γ . 1 2 ⌊ ⌋ ⌊ ⌋ 1 1 = μ and let (Γ p δn = , γ − = δn pn − pn n − ). Set β γ ) = (1 − p + δ ,and 2 1 1 12 2 1 ∈ β ∈ [0 ,n ]since p δn [ δ, 1]. .Notethat 12 ′ ′ Define the sets Γ and Γ as follows: 2 1 ′ Γ ( such that = ,...,x { ): ∃ i , ,...,i } Γ ∈ x x ,...,x 1 i 1 n 1 γ i 1 γ 1 1 1 ′ = { ( x . ,...,x } ): ∃ i Γ ,...,i ∈ ,...,x such that x Γ n i i 1 2 γ 1 1 γ 2 2 2 ⌋ ⌊ 1 1 ′ μ (Γ /n ) − γ δ /n = p − pn =Ω(1) ≥ ), note that δn − (Γ μ To lower bound 1 1 1 12 12 δ = Ω(1). Using a Chernoff bound, we get since ′ μ (Γ Pr )=1 ] ’s are in Γ − [fewer than γ of the x i 1 1 1 ( ,...,x x ) n 1 ) − Ω( n 2 − =1 . ⌋ ⌊ 1 ′ ≥ (Γ δn ) μ γ /n ), we note that (1 − p + δ ) − − /n − (1 − p + δ ) n To analyze (Γ μ 2 2 2 12 1 ′ − Ω( n ) ≥ . )=1 − 2 = Ω(1). Using ananalysis similar to that above, we get μ (Γ δ 2 12 ′ .2) Using the same notation and analysis as in the . implies (H (H.2) Property proof of Lemma 6.19, we let A ( x ) denote the private output of the sender and V ) ( x i i 1 x being the private input for i the view of the receiver in the th execution for S .That c i =1 ,...,n , is, for 1 ∗ ( V ( S ) )); x x ( ,R ) = output ( ,...,V A i 1 i i − 1 S c ∗ 1 ∗ ( )=view x ( S . )) ( x ,...,V ) ,R V ( V 1 − 1 R i i i c ′′ ′ ′ ′ Let A Γ ( ( ) ,...,A A ( Γ )=( )) represent the combined first-phase private out- Γ 1 n 1 1 1 ′′ ′ ∗ ′ ′ senders and V n puts of the V Γ ( Γ Γ R ) ,...,V )) represent the view of ( ( )=( 1 n 1 1 1 n senders before interactive hashing is done. From now when interacting with these ′′ ′′ ′ ′ ′′ ′′ A on, we simplify notation by making Γ V V )and ( A Γ = ). ( = 1 1 Similar to (4) and as in the proof of Lemma 6.19, we obtain √ 1/2 ′′ ′′ 1) − − k · ( γ 1 CP ) ≤ | 2 A ( . V − n And by a Markov bound, we know that with probability greater than 1 2 − over ′′ ′′ ← V , v ) n + ′′ α ( − n +3 δkn 24) / (1 − γ − ( k − 1) α − 2 n 1 1 1 ′′ ′′ A CP( (6) ≤ 2 2 ≤ | ) 2 2 · , ≤ = v V 100 /δ . with the last inequality following from k ≥ ′′ ′′ ′′ ,H =( H ∈ V such that (6) holds. Let ( A Q )), where H is v Consider 1 1 1 ′′ ′′ an independent random hash from H = is independent, Q | . Because H = 1 1 v V ′′ ′′ ′′ A | ( )), and we can apply the Leftover Hash Lemma, Lemma 6.8, to ,H H ( 1 V v = 1 − ) Ω( n ′′ ′′ Q | obtain that , the input to the interactive hashing protocol, is 2 -close to v = V uniform. 1 ′ ′ ∗ S ) denote the private output of = output Γ in the first S ) ,R ( ( Next, let A S 1 S phase, which in turn is equal to the output of in the interactive hashing protocol, IH 1 ′ ′ ∗ ∗ ∗ so equivalently A ( Q ) ,R ( ,R V = output =view ) S ( S ) Γ ( ). Similarly, let 1 R IH S c IH ∗ in the first phase, and let V = R denote the view of the adversarial receiver IH ∗ ∗ ∗ view ( S R ( Q ) ,R during the interactive hashing ) denote the view of receiver R IH IH IH ∗ ′ ′′ ′′ V R ,V is the view of ), recalling that V =( V execution only. Observe that IH when interacting with these n senders, before interactive hashing is done.

40 1192 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN − Ω( n ) ′′ ′′ Q | -close to uniform, we Because , the input to interactive hashing, is 2 v V = ′ ) − Ω( n ′′ ′′ ′′ ′′ ′′ ′′ A know that ( ,V ,V )is2 ), as guaranteed | U | -close to ( | n V IH = V IH = v v = V v ’s private by the hiding property of interactive hashing (see Definition 3.1). So S ′ ′′ ∗ ′′ ′′ ′′ | is hidden from V satisfying (6). Finally, note that for any v R ∈ output A v = V − n ′ ′ ′′ ′′ (6) is satisfied for all but a 2 V , so it follows that ( A v fraction of ,V )is ← − Ω( ) n ′ U ), as required. ,V -close to ( 2 n ′ . Using ideas similar to those in the proof of Lemma .3) (H Property (H.3) implies ′ 6.19, we can proceed as above and obtain that Property (H .3) holds assuming (H.3). In the execution of Algorithm 6.17, we obtained 6.3.2. Binding preservation. S intermediate commitment schemes [( )] , and one final commitment scheme ,R ≤ j ≤ j j 1 ( S R ). Our goal is to prove that the final scheme ( S , R ) satisfies the 1-out-of-2 binding , expected property of Definition 5.4. To achieve our goal, we inductively show that the number of openings a sender can produce in the intermediate schemes is bounded by some constant, namely, 32. (This is captured by Lemma 6.22 below.) Then in the final step, for scheme ( S , R ), we show how to shrink this expectation to a value that S , R ) satisfies the 1-out-of-2 binding is very close to 1, thereby proving that scheme ( property. (This in turn is captured by Lemma 6.24.) In the definition of the computational 1-out-of-2 binding property (Definition 5.4), we stipulated that the adversarial sender in the second phase can be computationally unbounded, whereas the adversarial sender in the first phase must be probabilistic polynomial time (PPT). It will be rather messy to work with PPT senders; hence we will abstract away the PPT requirement by showing, in the next section, how to convert any PPT sender violating the 1-out-of-2 binding property in the first phase unique binding property. A into a computationally unbounded sender with a special sender with the unique binding property, intuitively, will not break the (first-phase) ,R ) but might still break S binding property of any execution of the initial schemes ( 0 0 )). R , ,R S ) (or final scheme ( S the binding property of the intermediate schemes ( j j Intuitively, we can restrict our attention to such senders because of the computational S 1-out-of-2 binding property of the initial scheme ( ,R ). Once we have a sender 0 0 with the unique binding property, the analysis of the amplification steps is entirely information theoretic. To formally define the unique binding property for senders, we observe that R ,R , )] S and ( ) each contain multiple executions of initial scheme S schemes [( j 1 j j ≤ ≤ ∗ ( S interacts with S ,R ). Hence, when a cheating sender R , it is actually also in- j 0 0 i th execution of R teracting with the for each i , 2 ,... , which we will denote by =1 0 [ i ]. Formally, we define a (computationally unbounded) cheating sender strategy R 0 ∗ S i ] that interacts with this single execution of R i [ [ ] (more precisely, the first commit 0 1 on its own until the end of [ i ]) by simulating all of the other messages of R stage R j ,c 0 the first commit stage of R [ i ]. Then it enumerates over all choices for the subsequent 0 ∗ R messages of and outputs all of the resulting full transcripts of ’s interactions S j [ ] (including both phases). i with R 0 t . be the binding set guaranteed by Lemma 6.14 for ( S t ,R ) with parameter B Let 0 0 0 ∗ t 1 Then we define the random variable openings( S i ,R [ [ i ])( B ] ) as follows, analogously 0 0 to section 6.2.4: (1) ∗ 1 [ i ]and R . (According to c -phase commitment [ i ] interact to get first • S ,c 0 ∗ ∗ the definition of S above, [ i ] accomplishes this by simulating the rest of S ∗ R on its own.) and S the interaction of j (1) (1) ∗ ,...,d [ and ] outputs a sequence of values d i S After the interaction, • 1

41 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1193 λ corresponding full transcripts of both phases. Recall that λ = ,...,λ 1 i ( τ τ and κ are the first-phase and second-phase transcripts, ,κ ), where i i i i ∗ ∗ S [ i ] accomplishes above, S respectively. (According to the definition of ∗ this by enumerating over all possible continuations of the interaction of S and outputting all of the resulting transcripts of the interaction with and R j [ i ].) R 0 (1) 1 ∗ S • We let openings( [ [ i i ])( B whose open- ] d ,R ) be the set of distinct values 0 0 i (1) ing λ λ begins with prefix c , is valid, where by valid we mean that λ i i i (1) (1) d with first-phase transcript to the value c contains a decommitment of i t 1 2 . ,andboth R ∈B λ accept in and R / τ i i 0 ,r ,r 0 0 unique binding property of sender Definition 6.21 ( For an intermediate ). scheme S ( t ,R S , R ) with parameter ( , a (deterministic) sender or the final scheme ) j j ∗ t has the unique -binding property if for all i we have B S 0 ∗ t 1 S | openings( |≤ ,R [ i ])( B ] [ ) i 1 0 0 ∗ 10 1 ∗ ∗ i ] i and R [ [ [ i ] ), where S , [ i ] and openings( S ] (over the coins of 1 with probability S 0 t 1 R i ])( B [ ) are defined as above. 0 0 The following two lemmas, Lemmas 6.22 and 6.24, provide us with a way to S , R ), the amplified understand the binding property (in an average-case sense) of ( S, R ). We might occasionally hiding scheme as presented in Protocol 6.16, in terms of ( drop the superscripts 1 and 2 from the notation if it is clear which phase we are referring to. Lemma 6.22 ( intermediate step binding preservation ). For every sufficiently large constant D ∈ N , the following holds: For all integers t ∈ [1 ,n ] , j ∈ [1 , ] , 1 ,...,β 0 , 1 ,...,D − ∈{ } , letting ( S be the intermediate commitment schemes ,R ) β j 1 j j 11 D ,and t with parameters ( β obtained in the execution of Algorithm , 6.17 ) ,...,β , j 1 ( = B there exists a binding set B t, β such that the following two conditions ,...,β ) j 1 j j hold: t ∗ S For every deterministic sender (B.1) B -binding unique with the 0 property , ∣ ∣ ] [ ∗ 1 ∣ ∣ < , 32 S openings( )( ,R ) B E j j 1 R where the expectation is taken over the coin tosses of . j ∗ and for every deterministic sender S , For every τ ∈B (B.2) j ∣ ∣ ] [ ∗ 2 ∣ ∣ openings( S < 32 , E )( ) ,R τ j 2 where the expectation is taken over the coin tosses of R . j Proof . We proceed to prove by induction on j . In fact, we will start with a base ,R ) from section 6.2. By Definition 6.21, = 0; i.e., consider the scheme ( S j case of 0 0 S thescheme( ,R ) satisfies condition (B.1), and by Lemma 6.14, it satisfies condition 0 0 (B.2). ) satisfy both (B.1) and (B.2) and show ,R S For the inductive step, we assume ( j j that so does ( S ) is obtained by the amplification ,R ,R S ). Note that ( +1 j +1 +1 j +1 j j ,R ), i.e., procedure (Protocol 6.16) that combines sequential executions of ( S m j j 10 ∗ ∗ S i ] is probabilistic even if S Note that is deterministic, because it simulates all of the random [ choices of R ]. other than those of R i [ 0 j 11 Note that ( S ,...,β ,R β . ) does not depend on j j +1 j +1

42 1194 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN S ,R )= Amplify ( S ,R ). Hence, for convenience of notation we will denote ( j j j +1 j +1 S ( S ,R )as( S, R )and( )and( , R ), respectively. The i th execution of ,R S +1 j j +1 j j S ,R R ) is denoted as ( S [ i ] )in( [ i ]), which is not to be confused with the subscript ( S, R , ,R ). indexing notation of ( S j j D , although we will Also, throughout this proof, the value of m will be fixed to .Let B B keep writing m = ). We define our new binding be the binding set for ( S, R j ′ B set B S B , R )intermsof for ( and β = β as follows: = +1 j j +1 ′ B such that ,...,τ ): ∃ j ,...,j ( τ = τ ,...,τ { . ∈B} 1 1 β j +1 j m 1 +1 β ′ ′ τ ’s are ,...,τ τ ) ∈B β if and only if at least =( +1 of the That is, a transcript τ 1 m j ′ ′ B τ in .So, β if and only if at least m − / ∈B τ . ’s are not in B of the j ∗ t with the unique B -binding property (B.1) . Property Consider a deterministic S 0 1 1 R can be broken up into independent . The random coins of R interacting with 1 1 1 R random coins of [ m ]and R ,...,R , the receiver in the interactive hashing. [1] IH executions of ( S, R )in( S , R ) are sequential. We want to Recall that the m ∗ 1 focus on the interaction of S [ i ]. To do so, for each R with (the commit phase of) 1 1 r possible setting of the coin tosses − ,...,r R for [1] ,...,R 1], define a sender [ i 1 − i 1 ∗ 1 ∗ ,...,r ]]( r r ,...,r ]]( i [[ )thatinteractswith R [[ [ i ], as follows: S ) i S strategy 1 1 1 i − 1 i − ∗ 1 simulates S )andafter for all the previous r [ j using fixed coins j*i ,thecoinsof R [ R r ). Observe that S ) [[ i ]]( , and the coins of ,...,r 1 i 1 − IH t ∗ inherits the unique B S . -binding property from 0 ∣ ∣ 1 ∗ ∣ ∣ openings( S ;thiscountsthe Let X )= [ i ]( r r ,...,r ) ,...,r B ) ,R ( [ i ]( r ))( i − i 1 i 1 i 1 th execution, when the sender uses simulated number of valid decommitments in the i 1 coins r U ), where ,...,U and R [ denotes the i ,...,r r U .Let U =( ]usescoins i 1 m − i i 1 1 r uniform random variable on coins for R [ i ]; note that these are independent because i the honest receiver tosses independent coin s for each execution. We now consider the ,...,U U ( U )= X ( ). X random variables i i 1 i ∗ S By our induction hypothesis applied to i ]]( r ,..., ,...,r r ), for all fixed ( [[ − i 1 1 1 r ), we have i − 1 . 32 [ X < ( U ) | U )] = r ,U ,...,U ,...,r r ( = r X [ ]= E E 1 i i 1 − 1 i − − 1 1 i 1 i i U U i Because the previous X U ,wehavethat j
*

*43 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1195 Proof of Claim 6.23. Note that ] [ ··· ]= E ] | Y Y · y ··· E[ Y E[ y = y = ,...,Y y 1 1 Y − 1 1 1 1 − 1 − R ) Y ) y ,...,Y ← ,...,y ( ( 1 1 − 1 1 − E[ < Y · Y ] ··· α 1 − 1 , · E[ Y ] ··· Y α = − 1 1 and the claim follows by induction on . As noted above, it is always the case that E [ < 32, regardless of the instan- ] X i ’s for j
*

*44 1196 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN (B.2) . Property We use the same approach as above, except this time, we consider ∗ all deterministic S , as opposed to only those with the unique binding property. Also, ′ ,...,τ J ) ∈B be the set of indices .Let we need to fix a binding transcript =( τ τ 1 m τ such that . ∈B i ∗ S Analogously to the proof of Property (B.1), we define r )for ,...,r [[[ i ]]]( 1 1 i − 2 2 1], and we i of coin tosses for receivers R ,...,r [1] ,...,R − [ r every possible setting 1 − i 1 ∣ ∣ ∗ 2 ∣ ∣ openings( S . By our induction X set )= [[[ r ]]]( i ,...,r ,...,r ) τ ))( ) ,R ( [ i ]( r r i − i i 1 i 1 i 1 ∈ ,wehave hypothesis, for all J i [ ] E X 32 < | X ,...,X = = x i x i 1 − i 1 1 1 − ), where we define the random variables ,...,X X ) ∈ Supp( ,...,x x for any ( 1 − i − 1 i 1 1 U = X being uniform over the coin tosses ( U )with ,...,U ,...,U )and U =( U X 1 m 1 i i i i 2 r [ i ]. for R i = B U ) denote the set of values b =( b B Let random variable ( )forwhich ,...,b 1 m ∗ the sender S produces a valid opening in some continuation of the protocol. Noting k X that can be as large as 2 i/ ∈ J for indices ,wehave i [ ] ∏ ∏ k X 2 | ] ≤ | E E[ B i U ∈ i J i/ ∈ J ∏ ∏ k < 32 · (by Claim 6.23) 2 J i ∈ J ∈ i/ − β k 1 k +1 m β − ) (2 (because 32 < 2 · ) ≤ 32 m ( m − β )( ) − 1) − ( k − 6 k 2 ≤ m> (because 5) α − − ( k 3) 6 m − 2 =2 . Let random variable T ≤ = T ] ( U )= { ( h | ,h B ( b )) : b ∈ B, h | ∈H .SinceE[ } 2 2 2 2 2 2 α ( k − 6 m − 3) − 2 h and the range of is α ∈H , the expected density of T satisfies 2 2 2 2 2 6 3) − − α − m − ( k 2 E[ T ( μ | 2 B | ] · 2 )] ≤ E[ , where the expectations are taken over U = ≤ 2 2 ,...,U in the second-phase ). Note that T is independent of the coins of R U ( 2 m 1 IH 2 interactive hashing (though not independent of the coins of R ). Finally, we have ∣ ∣ [ ] ∣ ∣ [ ] ∣ ∣ (2) 2 (2) ∗ ′ (2) ∣ ∣ E openings( S , ) } T τ ) )( R , ≤ d ( E : C ∈ { d ∣ ∣ 2 2 2 ,coins T R coins R 2 IH (2) ∗ where, in the second expectation, C S T = openings( ) ,R ( ). By Lemma 6.10, 2 IH ∣ ∣ ] [ ′ ∣ ∣ (2) (2) (2) k +1 { d < 24 + 2 E ∈ T < } : )] C 32 ( d , ) · E[ μ ( T ∣ ∣ 2 2 2 ,T R coins 2 IH ′ with the last inequality following from k k − 8 m − 8. = final step binding preservation ). Lemma 6.24 ( For every sufficiently large con- ,n ∈ , the following holds: For all integers t D [1 N ] , β stant ∈ ,...,β − ∈{ 0 , 1 ,...,D 1 with parame- 6.17 ∈ [0 ,n be the final output of Algorithm , letting ( S , R ) ] } ,and β 1 +1 ′ t ( β , D ,and ters ) , there exists a binding set B ,...,β such that the following two 1 +1 conditions hold: ∗ t with the unique B -binding For every deterministic sender S (B.1) 0 − Ω( n ) 1 property ,withprobability 1 − 2 R , over the coins of ∣ ∣ ′ 1 ∗ ∣ ∣ S openings( . ≤ 1 )( B , R )*

45 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1197 ′ ∗ For every (B.2) ∈B τ ,with S and for every deterministic sender − ) Ω( 2 n − probability 1 2 , R over the coins of ∣ ∣ ∗ 2 ∣ ∣ openings( S ≤ 1 . R τ ) , )( S From Lemma 6.22, we have scheme ( Proof. ,R ) with an associated binding set , R )= satisfying both conditions (B.1) and (B.2) in Lemma 6.22. Scheme ( S B = B S ( Amplify ,R ), and hence we will need to show that the amplification boosts the ∣ ∣ ∣ ∣ 1 ′ 2 ∗ ∗ ∣ ∣ ∣ ∣ openings( S binding by making sure both 1and R S ≤ , R ) )( τ ) B )( ≤ , openings( Ω( n ) − 2 − 1 with probability 1 . will be fixed to n (as in step 3 of Algo- Throughout this proof, the value of m ′ . We define our new binding set m B rithm 6.17), although we will keep writing for , R )intermsof B ( β = β S and as follows: +1 ′ B { ( τ = ,...,τ . ): ∃ j ∈B} ,...,j ,...,τ τ such that +1 1 j β j m 1 1 +1 β ′ ′ That is, a transcript τ β ) ∈B =( if and only if at least τ +1 of the τ ,...,τ ’s are j m 1 ′ ′ . B ∈B / if and only if at least m − β of the τ ’s are not in .Thus, B in τ j Property (B.1) . Using the same analysis and notation as in the proof of Lemma 6.22, we have that +6 βk β k β − m m m E 2 ≤ ] | · (2 A ) | ≤ 2 [ 32 · , U where a =( a is the random variable denoting the set of values A ,...,a )forwhich m 1 ∗ ′ in some continuation of the B produces a valid opening with respect to S the sender 1 1 U U protocol and =( ) denotes coin tosses for R m [1] ,...,R ,...,U [ ]. m 1 ⌊ ⌋ 1 δ =Ω(1)and k Since k = n ,observethat α n = ω ( β + ) ( δn ) k ≥ = βk + log 1 3 ∈ ∈H { ( h ,h = ( a )) : h ,a n T for large enough values of . Let random variable 1 1 1 1 1 α 1 A } ). Since the range of h ∈H { , 1 } satisfies is , the density of Γ 0 1 1 1 n ( ω − )) n ( ω + βk ( − m +6 βk − α ) 1 E < · ] · 2 | A | E[ ≤ )] 2 T =2 ( μ [ , 2 1 U − n . Thus, with probability at least 1 m 2 since = n − U of over the coin tosses 1 1 ,...,R [ m ], we have that [1] R n 2 − n ) n − ω ( μ T ( 2 ) ≤ ≤ . 2 · 2 1 n 2 − T By Lemma 3.7, we can conclude that for such a (with ) ≤ 2 T ( μ ), 1 1 ∣ ∣ ] [ ′ ∣ ∣ 1 (1) − 2 ) / Ω( (1) n k n 2 − (1) poly( (2 > 1 · ≤ ) n { d ) } . T · 2 ∈ ) : d ( C =2 Pr ∣ ∣ 1 1 R coins IH Finally, we have ∣ ∣ [ ] 1 ∗ ∣ ∣ Pr , R ) > 1 openings( S 1 R coins ] [ n 2 − μ T ( 2 ) > ≤ Pr 1 1 1 coins ,R ··· , R 1 m ] [ ∣ n − 2 (1) (1) (1) ∣ |{ d μ : ∈ T 2 }| > 1 ( d ) ( T ≤ ) C +Pr 1 1 1 R coins IH − Ω( n ) =2 .

46 1198 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN ′ ′ (B.2) ∈B Fix any . Again, we use the same analysis and notation τ Property . as in the proof of Lemma 6.22 to get β 1 m +5 k ) β +1 − m k ( m − β − ≤ [ ) (2 · | 32 2 ] | , B ≤ E U ,...,b )forwhich b where is the random variable denoting the set of values B b =( m 1 ∗ S the sender produces a valid opening in some continuation of the protocol and 2 2 ,...,U R [1] ,...,R ) denotes coin tosses for [ m ]. U =( U 1 m ⌋ ⌊ 1 ≥ ,observethat α δ k Since =Ω(1)and n log β + = n δn ) k ( =( n − β ) k + − 2 3 { ( h h = ∈ ( b )) : ,h . Let random variable T ω ( n ) for large enough values of n 2 2 2 2 α 2 H B } . Since the range of h satisfies ∈H T is { 0 , 1 } ,b ∈ , the density of 2 2 2 2 m k ) n ( ω − )) n ( ω + k ) − α β − n ( m − β ) (( +5 − 2 | μ , 2 < · 2 · ] | B 2 E[ =2 ≤ )] ( T [ E 2 U − n n . Thus, with probability at least 1 − 2 since m = U of over the coin tosses 2 2 R ,...,R m ], we have that [1] [ 2 − ω ( n ) n − n ≤ 2 · 2 2 ≤ . ) ( μ T 2 n 2 − μ ( T ), ) ≤ 2 (with T By Lemma 3.7, we can conclude that for such a 2 2 ∣ ∣ ] [ ∣ ∣ ) n (2) Ω( − (2) (2) =2 1 > { d Pr . C T ∈ : ) d ( } ∣ ∣ 2 2 R coins IH Finally, we have ∣ ∣ ] [ ′ 2 ∗ ∣ ∣ S openings( > 1 Pr )( τ , R ) 2 R coins ] [ − n 2 ≤ Pr T μ ( > ) 2 2 2 2 ,R ··· , R coins n 1 ] [ ∣ (2) n (2) (2) 2 − ∣ μ ( T d |{ ∈ T 2 }| C ≤ ( d : ) ) +Pr 2 2 2 R coins IH Ω( n ) − =2 . 6.4. A collection of 1-out-of-2-binding commitments. In this section, we prove Theorem 6.1, which is restated below. n → : { 0 , 1 } Restatement of Theorem 6.1. Given a one-way function f n , we can construct in time polynomial in n acollectionof m =poly( n ) public- } { 0 , 1 coin 2 = { Com -phase commitment schemes COM Com } with message lengths ,..., 1 m ( k )=( n, n ) , such that ,k 2 1 there exists an index i ∈{ 1 , 2 ,...,m } such that scheme Com • is statistically i hiding, and 2 -out-of- 1 is computationally for every index , ,...,m } , scheme Com • 1 ∈{ i 2 i binding. 6.4.1. Proof of Theorem 6.1. To obtain the desired co llection of 2-phase com- mitment schemes, we apply Algorithm 6.17 to the weakly hiding scheme ( S ,R ), 0 0 n n , →{ 0 1 } .More { 0 : , 1 } which can be constructed based on any one-way function f ion of commitments by enumerating over all the polyno- precisely, we obtain a collect ∈ ,...,β ∈{ 2log n , 2 ,...,n − 2log n } , β mially many choices of the integers t 1 { 0 , 1 ,...,D − 1 } ,and β ∈{ 0 , 1 ,...,n } . Note that the number of choices is +1

47 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1199 · n D n · ), as D = O (1) and =log n . By Lemma 6.18, the re- +1) = poly( ( n sulting commitment schemes Com ,..., all run in polynomial time. The hiding Com m 1 and binding properties of these schemes are given by Lemmas 6.25 and 6.26, which together establish Theorem 6.1. N , the following holds: Lemma 6.25. For every sufficiently large constant D ∈ n 1 n − |∈ 0 →{ ) , 1 } y be any function (not necessarily one-way) such that | f ( } { , 0 : Let f 1 n 2 n 2 n [2 2 for every ] ∈{ 0 , 1 } /n . Then there exist integers t ∈{ 2log n , 2 ,...,n − , y , - 2 such that the } ,...,β ,...,n ∈{ 0 , 1 ,...,D − 1 } ,and β 1 0 ∈{ 2log β , } n 1 +1 with parameters S R ) produced by Algorithm 6.17 ( D , t , phase commitment scheme , ( β and ,...,β ) is statistically hiding in the sense of Definition 5.3 . 1 +1 f As we observed earlier with Theorem 5.6, the condition on the preimage sizes of . Specifically, given any function can be easily made to hold by padding the input of f n n ′ | = )=( →{ 0 , 1 } has input , the function f | ( x, y, z z f ( x ) ,y )with | x | = | y | } 1 , 0 { : f ′ ′ / 3 n n ′ / 3 2 and 2 n =3 ,andisone-wayif f , has all preimage sizes between 2 n length is. ,...,β such . We prove by induction on ,..., that there exist t, β =0 Proof j 1 j 1/2 j S that ( )is δ { -hiding in CP . The base case measure for δ 1 =min ,R 2 } /n, /D j j j j j = 0 is simply Lemma 6.13. The induction step is provided by the intermediate of step hiding amplification lemma, Lemma 6.19. Specifically, if by induction we choose δ ,...,β )is ,R S such that ( -hiding, the lemma tells us that there t, β j 1 − j − 1 1 1 j − 1 j − ′ ′ β exists 2 δ such that ( -hiding for δ )is =min { ,R δ , 1 /D } = δ . S − 1 j j j j j Finally, we apply the final step hiding amplification lemma, Lemma 6.20, to S such that ( , R ) is statistically hiding. The lemma applies because obtain a β +1 2 } /n, 1 /D =min = Ω(1) (recall that = { log n and D = O (1)), and k = δ D ) · − (8 D +8) · > 100 /δ (16 for sufficiently large . n D , the following holds: If f : Lemma 6.26. For every sufficiently large constant n n n 2log , →{ 0 , 1 } } is one-way, then for all integers t ∈{ 2log n , 2 ,...,n − } , 0 { 1 β ,...,β -phase commitment ∈{ 0 , 1 ,...,D − 1 } ,and β 2 ,the ∈{ 0 , 1 ,...,n } +1 1 is ,...,β ) , R ) produced by Algorithm 6.17 with parameters D , t ,and ( β scheme ( S +1 1 -out-of- binding in the sense of Definition 5.4 .(Herethefunction 1 computationally 2 f on which the scheme is based needs to be hard to invert.) ′ be the binding set given by Lemma 6.24. That lemma establishes B Proof .Let that the 2-phase commitment scheme ( S , R ) produced by Algorithm 6.17 satisfies the ′ second condition of Definition 5.4 with respect to B . In addition, it also satisfies ∗ with the unique binding property. Stated formally, for the first condition for all S ∗ t S every deterministic (and computationally unbounded) with the unique B -binding 0 property, ∣ ∣ ] [ n − Ω( ∗ ) ′ 1 ∣ ∣ )( B ≤ 1 R =1 − 2 ) , , (7) Pr S openings( 1 where the probability is taken over the coins of R . ∗ S Thus, it suffices to prove is that any PPT breaking the first condition of ′ ˆ ) with probability ε will either (i) yield a that PPT S B Definition 5.4 (with respect to violates the computational 1-out-of-2 binding property of ( S ,R ) with probability at 0 0 (1) O ˆ least ε n ), or (ii) yield a computationally unbounded S / that has the unique poly( t -binding property and violates (7). B 0 ∗ ε be the probability that S From now on, let breaks the second condition of S , R ). This probability is taken over the coin Definition 5.4 with respect to scheme ( ∗ ∗ )todenote r ( . We will write S S R tosses of both the receiver and the cheating sender

48 1200 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN ∗ r . By our definition of ( S , R ), it contains polynomially S withitscointossesfixedto S many executions of ( = n ). Let D N denote the number of such executions. ,R · 0 0 ∗ S denote a transcript of ( Let z z is also a first-phase commit- , R ). Contained in 1 i ]forthe i th execution of R z ment [ i , denoted [ i ](forall i =1 , 2 ,...,N ). Let ˆ z [ R ] 0 0 be the partial transcript of up to and including the first commit stage of R z [ i ]. Note 0 [ [ z [ i ], and ˆ z ]isasuffixofˆ i ]isaprefixof z . z i that ∈ [ N ], partial transcripts ˆ z [ i For all indices i ] ending with the first commit stage k ∗ 0 ]and d ∈{ 0 , 1 , define } [ , and coin tosses r for S i of R 0 , ]] i [ z begins with ˆ z =Pr | d ]tovalue i [ z contains a valid opening of z [ p ,d,r ] i [ z ˆ i, ∗ z ) r ( R S ( ← ) , (which includes coins of the where the probability is taken over the coin tosses of R ). As [ ], j>i , as well as coins for many executions of j R R subsequent executions IH 0 ∗ usual by a valid opening, we mean that S [ i ]=( τ [ i ] sends a full transcript [ i ]) of λ ,κ [ [ i ] such that λ [ i ] begins with z ]contains i ], λ [ i both phases of its interaction with R 0 t [ i ]tovalue d with a first-phase transcript τ [ i ] / ∈B a decommitment of z ,andboth 0 1 2 R i ]and i ]. [ i [ λ [ R ] accept in 0 0 k 0 Let K =2 k S is the message length in ( ,where ). We have two cases to ,R 0 0 0 consider. 1. There exists an i ∈ [ N ] such that, with probability at least ε/ 4 NK over Case ′ ′ with both p . NK 4 >ε/ ,p = d ˆ z [ i ]and r ,thereexists d ,d,r ] ˆ z [ i ] ,d i ,r [ z ˆ i, i, ) ,R S In this case, we violate the computational 1-out-of-2 binding property of ( 0 0 ˆ S R by considering the following sender interacting with [ i ]. 0 ∗ [ N ] and coin tosses r for S 1. Select a random i ← . ∗ S 2. Run )with internally , simulating all of the messages of R r ( R except for those of R [ i ]. Halting after the first commit stage of 0 i [ i ], we obtain a partial transcript ˆ z [ i ]. From ˆ z [ i ], z [ ], we get R 0 R the first-phase commitment of i ]. [ 0 ∗ S of ψ 3. Record the current state r )and R . ( ∗ twice using in- ( r )with R from ψ S 4. Continue the execution of . R dependent randomness for 5. Examine the transcripts to look for valid decommitments to two ′ . d, d different values Because our goal is to violate the computational 1-out-of-2 binding property of ′ ,R ), we succeed in the above algorithm if d = d and decommitments produced are S ( 0 0 valid. We calculate our success probability as follows: We guess the correct index i ∈ [ ] with probability 1 . Given that we guess the correct i , we get the desired ˆ z [ i ]and N /N ε/ . Now, when we do two independent continuations NK with probability at least r 4 [ ] we arrive at two different decommitted values with probability greater than z i of ˆ 2 . Consequently, we violate the computational 1-out-of-2 binding property ) ε/ 4 ( NK ) (i.e., win the game in condition 2 of Definition 5.4) with probability greater ,R S of ( 0 0 than ) ) ( ( O (1) 2 1 ε ε ε · · = , n N NK 4 NK 4 n (log k ) O O (log n ) 0 (1) n = n · D =poly( = n · O N =2 ). This n =poly( )and since K =2 forces ε to be a negligible function. Case 2. For all i ∈ [ N ], it holds that with probability greater than 1 − ε/ 4 NK over ˆ [ i ]and r , there is at most one d such that p z . NK 4 >ε/ i ] ,d,r [ z ˆ i,

49 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1201 ∗ Define d p )tobethevalueof d z i (ˆ . Taking a union [ ] ,r that maximizes ] ,d,r i, ˆ z [ i ′ ∗ d bound over other possible values ), we have that (ˆ [ i ] ,r z d = ∗ ∗ Pr ] i [ z (ˆ z d ] to a value other than [in )] , S ,r ( r )openssome z [ i ∗ ← ) r ( ) S ( , z r, R ( ) N [ ] ∑ ε ε exists more than one d such that p ≤ +Pr · K > ˆ z [ i ] ,d,r i, NK 4 NK 4 ,r ˆ z [ i ] =1 i ) ( ε ε · K +

50 1202 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN universal one-way hash functions (UOWHFs) in Our additional idea is to use knowing order to force the sender to decide in which phase it is about to cheat before . A family of universal one-way hash functions is a relaxation the value of phase of collision-resistant hash functions that were defined by Naor and Yung [23] and 12 A family of shown to be constructable from any one-way function by Rompel [7]. universal one-way hash functions is a family of compressing functions such that no efficient adversary can succeed in the following game with nonnegligible probability. . Then, on a uniformly selected hash The adversary should first announce a value x after it announces x ), it succeeds if it can find function f (given to the adversary ′ ′ x such that ( x = )= f ( x ). f x Our implementation is as follows: After the first-phase commit stage, the receiver and the sender sends back f selects a random (universal one-way) hash function f ( x ). The protocol proceeds essentially as y = the naive protocol above, where any ′ n the naive protocol revealing the value x time the first-phase reveal stage is executed i phase = first or in the commit-stage for phase (either in the reveal stage for second ), = ′ ( x the receiver also verifies that f y . )= is sufficiently compressing, the string remains Assuming the hash function x f ( x )issentto R quite unpredictable even though f (in the new variant of the protocol). phase = first , we can still use the “entropy” remaining in x to Thus, in the case that | x |−| f hide the sender’s secret (assuming it is sufficiently shorter than x ) | ). To show ( the statistical hiding in the complementary case when = second , it is sufficient phase f x ) does not compromise the hiding property of the second- to note that sending ( phase commitment. All in all, the protocol is statistically hiding for both choices of , and thus it is statistically hiding. phase To argue about the binding of the protocol, recall that the 1-out-of-2-binding property informally states that with high probability after the first-phase commit stage, there exists a single value ̃ x that allows the sender to cheat in the second- phase commitment. Now, if the sender sends y such that f ( ̃ x )= y ,theninorderto cheat in the case phase first , it will have to open the first-phase commitment to = ′ ′ = ̃ x such that f ( x )= y = f ( ̃ x ). This would imply the breaking of the avalue x f ( ̃ x ) = y universal one-way hash function. On the other hand, if , then in the case phase second the sender is forced to open the first-phase commitment to a value = ̃ . This guarantees that the sender cannot cheat in the second-phase different than x commitment, and thus in this case our protocol is binding. In conclusion, since y is sent before phase is chosen, we are guaranteed that our protocol is weakly binding phase (since intuitively there always exists a choice of that prevents the sender from cheating). We complete the construction by amplifying the above protocol into a full-fledged statistically hiding commitment scheme using standard techniques. 7.2. The transformation. We present the transformation algorithm using an arbitrary family of functions and will require only that F to be a universal one-way F hash family when we want to prove the hiding and binding security properties. Algorithm 7.1. The transformation, denoted as 2 -to- 1 - Tr a n s f or m . n , , 2-phase commitment scheme ( S R ) with message lengths 1 Input: security parameter ⋃ n } ,k 1 )=( n, 1) , and a family of functions F = → , F 0 = { f : { k ( n 1 2 n m { , 1 } 0 } . ) Output: ( S , R Commitment scheme as described by Protocol 7.2 . 12 A version of Rompel’s result [7] that holds also for uniform adversaries was recently written by Katz and Koo [29], who also added missing details and fixed some errors.

51 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1203 , Hence, we write the commitment scheme obtained as ( Transform (( S , R S )=2-to-1- F ) ). R , , R Protocol 7.2. from 2 -phase commitment S ( Standard commitment scheme ) , R ) . scheme ( S n Security parameter: 1 R . S , given as common input to both and ∈{ , b 1 } . 0 Bit Sender’s private input: Commit stage: n . ←{ 0 , 1 } S selects a uniform 1. σ 1 1 1 n acting as acting as S ( σ ) , R R S )(1 and ) ,with S S ( engage in R 2. and c c c (1) 1 1 1 R and be the common output of R S .Let after the interaction. c c c c R 3. ←F chooses f S . and sends it to n to y f ( 4. ) = R . sends S σ flips a random coin, represented by phase ←{ 1 , 2 } , and sends phase 5. R . to S phase =1 , then proceed as follows: If selects a random hash H ←H ,where S is a family of pairwise- (a) h n { 0 , 1 } , and range , 1 } independent hash functions with domain { 0 ( and sends h ( σ )) to R . ⊕ h, b (1) and R both output ( c S (b) =1 ,h,b ⊕ h ( σ )) as the com- ,f,y,phase mitment. If phase =2 , then proceed as follows: 1 (1) and first-phase to obtain the decommitment message γ S runs S (a) r (1) (1) S sends to σ, γ . ,τ ) ( transcript corresponding to both σ and c τ . R 2 2 n 2 S R (b) and engage in ( S , R and R )(1 ( ,τ ) ,with S acting as S b ) c c c 2 2 2 (2) c .Let be the common output of after the and R S acting as R c c c interaction. (1) (2) ,f,y,phase =2 ,c ) as the commitment. and R both output ( (c) S c Reveal stage: b , do the following depending the value of phase To decommit to bit . If phase =1 , then the following occur: 1. S sends ( b, σ ) to R . σ 2. f ( σ ) and the last component of the commitment equals b ⊕ h ( = ) , y If R accepts .Otherwise, R rejects . then phase =2 , then the following occur: If (2) 2 (2) to obtain the decommitment message γ , and sends ( b, γ ) S 1. runs S r to R . 1 (2) (2) (1) 2 (1) σ ) and both R 2. If y = f ( ( accept ) ,σ,γ R ) and c c and ,b,γ ( r r respectively, then R accepts .Otherwise, R rejects . 7.3. Analyzing the transformation. The hiding and binding security prop- erties of Protocol 7.2 will rely on properties of F being a universal one-way hash family. Our plan for the remainder of this section is as follows: (i) we present the definition of a universal one-way hash family due to Naor and Yung [23]; (ii) we separate the properties of a universal one-way hash family into two parts; and finally, (iii) we prove the hiding and binding properties of Protocol 7.2 based on these two separate properties. Universal one-way hash family. In order to define a universal one-way hash family, we need to understand what it means for a family of functions to be polynomial-time

52 1204 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN . computable ⋃ m n Definition 7.3. = A family of functions F , f { 0 , 1 { = →{ 0 : 1 } F } is } n n polynomial-time computable if the following hold. ) n is described by a bitstring of length for some p ( ∈F Every function • f n . By abuse of notation, we also denote this description by and polynomial p f R ) p ( n 0 , ←F } .(A to mean that it is chosen uniformly at random in { 1 f write n more general definition would allow the description of the function to be se- lected according to any polynomial-time samplable distribution, even one that requires private coin tosses. However, our stronger “public-coin” definition is achieved by existing constructions and can be useful in applications such as constructing public-coin zero-knowledge arguments.) There exists a deterministic polynomial-time algorithm • F such that for every , given the description of the function f and a string ∈F n f and every n n 1 } ∈{ x , 0 outputs the value of f ( x ) . , F ⋃ F = F = A polynomial-time computable family of functions Definition 7.4. n n n m 0 , : } { { f 1 , 1 } } →{ is a universal one-way hash family if m

53 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1205 Large preimages : Most of the preimages have a large size. This follows from the is much shorter m compressing nature of hash functions: the output length than the input length n . (Recall that we can get a universal one-way hash family with n/ ≤ m 2.) We formalize this property in Definition 7.6. Target collision resistance : It is hard to find collisions with a value x announced the hash function is given. We formalize this property in Definition 7.7 before ⋃ m n F 1 = { f : { 0 } 1 } } →{ 0 , , = F Definition 7.6. A family of functions n n property if for every ∈F most elements in the range of f f large preimages has the have large preimage sizes. Stated precisely, there exist a function )= ω (1) and a α ( n such that for all values of n , the following holds: negligible function ε ] [ ∣ ∣ 1 ) − α ( n ∣ ∣ f ≥ n ) n ε − 1 ( ≥ Pr )) x ( f ( n ←{ 0 , 1 } x ∈F f for every function . n ⋃ n m = { f : } 0 , 1 } F →{ 0 , 1 } has { A family of functions F = Definition 7.7. n n the property if for every statistical (resp., computational) target collision resistance n : (resp., every PPT) the following is negligible in A ∧ n ′ ′ ′ )= . ) ,f ←F )] ,x x ← A ( x, state ,f ): x ( = x f f ( x Pr[( ) state x, (1 A ← n 7.8. Remark In this paper we are using only families of functions that are com- putational target collision–resistant. Yet whenever possible we also state the results with respect to families with statistical target collision–resistant, because this gener- alization has proved useful in subsequent work [39]. Large preimages and target collision–resistance are opposing properties. Specifi- family of functions to have large preimages and have cally, it is impossible for a single target collision resistance. The power of a universal one-way hash family statistical comes from the fact that it has the large preimages property and has computational target collision resistance. ⋃ n m 2 = { f : { 0 , 1 } n/ →{ 0 , 1 } F } for m ≤ is a universal If F = Lemma 7.9. n n computational F one-way hash family, then has both the large preimages and the target collision–resistance property. The computational target collision resistance property follow directly from Proof. Definition 7.4. Hence, all we need to show is that the compressing nature of F ,when m ≤ n/ 2, implies the large preimages property. ∈ y and group the elements with small preimages into a set S = { f Fix ∈F n ∣ ∣ 3 − m m n − 1 ∣ ∣ 4 y ) has a preimage S < 2 ∈ f y/ : ( } .Since m ≤ n/ 2, every element } 1 , 0 { ∣ ∣ 3 (1) − 1 n/ m − 4 n ω ∣ ∣ 4 2 ≥ f ≥ ( = n y ) . To complete the proof, we bound the 2 of size S , by a union bound over the elements in S (for which there probability of landing in m ): are at most 2 Pr ] y )= U ( f with [ f ( x ) ∈ S ]=Pr[ ∃ y ∈ S n n , } 0 ←{ x 1 3 m − n 4 2 m − n/ 4 < =neg( =2 . ) · 2 n n 2 Hiding. Having separated the properties of a universal one-way hash family into those having large preimages and those having target collision resistance, we now show that the large preimages property of F translates to the hiding property of the commitment scheme ( S , ). )=2-to-1- Tr a n s f or m (( S , R ) , F R

54 1206 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN has the large preimages property, and Lemma 7.10. If the family of functions F , ( R ) is statistically hiding, then scheme ( S , R )= -phase commitment scheme the 2 S - Tr a n s f or m (( S , R ) , F ) is statistically hiding. 2 -to- 1 ∗ ∗ R in the views of Proof . We need to show that for any adversarial receiver R ∗ ∗ ,R (0) ( S )and( ) are statistically indistinguishable. (In this proof, we drop S (1) ,R n because it is clear from context.) We can, without the security parametrization of 1 ∗ loss of generality, consider only deterministic R because we can fix the adversary’s coin tosses to maximize its distinguishing advantage. In the rest of this proof, we use hiding to mean those of the statistical variant. indistinguishability and ∗ , and we break our hiding anal- denote the value of Let R P phase sent by P =1and = 2. To formalize this case analysis, we P ysis into cases in which Y are say that random variables E if for all D , X and indistinguishable on event D ( X )=1 ∧ E ] − Pr[ D ( Y )=1 ∧ E ] | is negligible (in the security parameter n ). | Pr[ ∗ ∗ ∗ ∗ ,R (0) )andview ( S ( S (1) ,R )are We will show that the random variables view R R P = 2, thus allowing us to conclude that indistinguishable on both events P =1and the scheme is hiding. = 2. Let the random variables Σ and First, we analyze the case when F P ∗ , respectively. Observe that ’s choice of f and the value of σ sent by R S denote ∗ 1 ∗ )and ,R ( S (Σ) =view V function of the random variables is a P deterministic 1 R c = (Σ). In turn, V F Y Y are deterministic functions of the first-phase transcript and 1 1 ∗ S T=transcript( ,R ), which includes both the commit and reveal stages. This is (Σ) ver from the first-phase transcript and because we can compute the view of the recei σ , from which we can compute the first-phase transcript also contains the value of 2 ∗ ∗ )(T), ,R S ( ) )=view b b ( ( ). For bit V 1 , 0 ∈{ b , let random variable σ ( f = y } R 2 c 1 ∗ recalling that T = transcript( S ,R (Σ) ). Because ( S , R ) is hiding, its second-phase commitment is hiding even given the first-phase transcript: this means that ( V , T) (0) 2 (1) T). Since P is a deterministic function of T, random , V is indistinguishable from ( 2 variables ( V T) and ( V (0) (1) , T) are indistinguishable on event P = 2. Finally, , 2 2 ∗ ∗ since view b ) ,R ( ) | is a deterministic function of ( V ( b ) , T) | ( for b ∈{ 0 , 1 } , S P P =2 =2 R 2 ∗ ∗ ∗ ∗ ( )andview (0) S ( S (1) ,R ,R ) are indistinguishable on event we have that view R R P =2. P = 1. The hiding property of the first phase Next,weanalyzethecasewhen gives us V Σ) ≈ ( , , ,U ) V ( n 1 s 1 n U where represents a uniform random variable over { 0 , 1 } and is independent from n ∗ V F denotes the function sent by R and Σ. Recall that the random variable . f 1 F Since V is a deterministic function of ,weget 1 ( V ,F,F (Σ) , Σ) ≈ . ( V ) ,F,F ( U ,U ) n s 1 1 n H Now, let the random variable h selected by S when represent the hash function ,so U ,Σ,and F , H =1. Notethat phase V is independent of 1 n , U ,F,Y,H,H (Σ)) ≈ )) V ,F,F ( U ) ,H,H ( ( V ( (8) 1 n n 1 s recalling that F (Σ). = Y ) is close to uniform so that we have hiding. The ( U We need to establish that H n next claim does this for us. ⋃ has the large preimages F = Claim 7.11. Suppose the family of functions F n n property. Let the random variable H denote a random hash function from a family

55 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1207 n { 1 } of pairwise-independent hash functions with domain 0 , 0 , 1 { and range ,letran- } ′ n U dom variable } U , let random variable denote a uniform string in { 0 denote a , 1 n 1 ′ ,and U all be independent. For every f ∈F , uniform string in { 0 , 1 } ,andlet H , U n n 1 ′ ( f ( U ( U . ) is indistinguishable from ( f ( U ) ) ,H,U ,H,H )) n n n 1 F guarantees that with proba- The large preimages property of ProofofClaim. n )over y bility 1 f ( U neg( − ← y ( U ), the min-entropy H | ). For n (log ω ≥ ) ∞ n n y )= U ( f n satisfying this condition, we apply the Leftover Hash Lemma, Lemma 4.1, to get that | ( )). y, H, H | )) is indistinguishable from ( U U ( y, H, H ( n n U )= y f f ( U ( )= y n n and U Because are independent from the rest of the random variables (and H n are independent from each other), Claim 7.11 states that ′ ) U , ) ,H,H ( U ≈ )) ,F,F ( ( V ,F,F ( U ,H,U ) ( V (9) n 1 1 n n s 1 ′ is an independent random variable representing a uniform random variable where U 1 { 0 , 1 } . Combining (8) and (9), we get over ′ ) (Σ)) ≈ , V ,F,Y,H,H ,F,F ( U ( ) ,H,U V ( n 1 s 1 1 which leads to ′ U ,F,Y,H, 0 ⊕ H (Σ)) ≈ ⊕ ( ) V ,F,F ( U ,H, ) 0 V ( 1 n 1 s 1 ′ ,H, ( ,F,F ) U U ) ⊕ 1 ( V ≡ n 1 1 ≈ . ( V (Σ)) ,F,Y,H, 1 ⊕ H 1 s Y , random variables ( V ,F,Y,H, 0 ⊕ and V Since is a deterministic function of P 1 1 ,F,Y,H, 1 ⊕ H (Σ)) are indistinguishable on event P =1. Since (Σ)) and ( V H 1 ∗ ∗ view ( b ) ,R ( ) | S for is a deterministic function of ( V | ,F,Y,H,b ⊕ H (Σ)) 1 =1 =1 R P P ∗ ∗ ∗ ∗ , } ,wehavethatview 0 ∈{ b 1 ,R ( )andview ) are indistinguishable S ( S (1) ,R (0) R R =1. P on event We show that the target collision resistance property of F translates to Binding. , R )=2-to-1- the binding property of the commitment scheme ( (( S , R ) , F ) S Transform Tr a n s f or m . Because we will be able to show only that ( S , R ) obtained from the 2-to-1- / 2, we first define what it means to for a scheme is binding with probability close to 1 δ for some δ ∈ [0 , 1]. to be binding with probability Commitment scheme ( S, R ) is statistically (resp., computa- Definition 7.12. ∗ δ ( n )-binding if, for every S tionally) (resp., every PPT) and every large enough ∗ succeeds in the following game with probability at most δ ( n ) : ,sender S value of n n ∗ On security parameter 1 interacts with R in the commit stage , S ∗ c .Then S obtaining commitment (0 ,d ) ) and (1 ,d outputs pairs 0 1 succeeds R (0 ,d and if in the reveal stage ,c )= R . ,d accept ,c )= (1 1 0 The standard notion of binding as given in Definition 2.4 corresponds to being computationally 1 /p ( n )-binding for every polynomial p . Lemma 7.13. If the family of functions is statistically (resp., computationally) F ) 2 ( S target collision–resistant, and the R -phase commitment scheme is statistically , ( ) 2 (resp., computationally) S -binding, then the scheme ( S , R )=2 -to- 1 - Transform (( , , R ) 1 F is statistically (resp., computationally) (1 / 2+1 ) ( n )) -binding for every polynomial /p p and sufficiently large n . Proof . We will focus on the case of computational binding. The statistical case will follow from the fact that the proof is “black-box.” Specifically, our proof will , M such that given any sender strategy (implicitly) give efficient reductions M 1 2

56 1208 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN ∗ ∗ S ( n ))-binding property of ( S , R ) as oracle, either M S /p that breaks the (1 / 2+1 1 with nonnegligible probability will break the target collision resistance property of F ) ( ∗ 2 S S ). If both -binding property of ( S , R )have F and ( R , will break the or M 2 1 statistical (resp., computational) security , then this is impossible for every strategy ∗ (resp., every PPT strategy) S , R ) must be statistically (resp., , and we deduce that ( S 2+1 /p n ))-binding. / computationally) (1 ( Unless stated otherwise, we take probabilities over the entire interaction between ∗ ∗ if it is in both the commit and reveal stages. We say that succeeds R and S S erent messages for commitment Υ in the able to produce decommitments to two diff reveal phase (recall that the reveal stage is noninteractive). We want to prove that ∗ ( succeeds] / 2+1 /p 1 n ). We will do this by breaking the probability space into ≤ Pr[ S events E corresponding to the various cases in the intuitive proof outline given ,...,E 5 1 ∨ ∗ in section 7.1. We will show that Pr[ ∧ ]=1,Pr[ E succeeds ]=1 / 2, and Pr[ S E 1 i i n 1 / 4 p ( ≤ )for i =2 ,..., 5, and this will suffice to prove the lemma. ] E i 1 ∗ ∗ E The first event, =view ( S C , R , will depend on the random variables ), S 1 c ∗ ’s view of the first-phase commit (this determines the entire state of representing S ∗ the interaction ( S ), since by Definition 5.1 the honest receiver maintains no private ,R Y state after the commit phase other than the commitment string); , denoting the hash ∗ P , representing the value of phase ;and after the first-phase commit; S value sent by R ←F . We would also like to consider f F , representing the choice of the function ∗ ∗ f (Σ Y equals whetherornot intuitively represents the value to which ), where Σ ∗ is a commitment, i.e., the “unique” value that will enable S C to break the binding ince the commitment scheme may be only property of the second phase. However, s ∗ is not defined information-theoretically. Thus, we define computationally binding, Σ ∗ will open the first-phase commitment (with a it as the most likely value to which S transcript not in B ). Formally, for each first-phase commit transcript c ∈ Supp( C ), we define (10) [ ] ∗ ( S ,R accepting full transcript λ =( τ, κ ) ) outputs an σ ]=Pr p c | [ , = C | c , contains an opening to τ and ∈B τ/ such that σ ∗ R , and we say full transcript and S where the probability is over the random coins of ∗ 1 2 c [ and R ]= accept in λ . With this measure, we define σ R accepting is λ if both r r argmax σ | c ], breaking ties arbitrarily (say, by choosing the lexicographic smallest p [ σ ∗ ∗ ). Then we define the random variable Σ σ = σ [ C ]. The intuition described in section 7.1 suggests a case analysis based on whether or ∗ ∗ = ). According to that intuition, the scheme will be binding if Y F (Σ ) Y F (Σ = not ∗ P = 1 (by target collision–resistance of F )orif Y = F (Σ and )and P =2(bythe1- / 2 (because out-of-2 binding property), and these events happen with probability 1 P ∗ , ,and Y are determined). This intuition can be turned F is randomly chosen after Σ directly into a proof in the case that has nonuniform target collision–resistance, F ∗ ) can be hardwired into the (which is determined before F since the value of Σ F adversary breaking . However, to prove our result for uniform adversaries as claimed, ∗ ∗ σ ] can be efficiently computed (before being given [ = C we need to ensure that Σ ∗ F , as per Definition 7.7). We observe that this is the case if p [Σ | C ] > 1 / 4 p ( n ), ∗ because then if we simulate a continuation of the execution of ( S )startingafter ,R ∗ being revealed. On the other hand, the C , we have a nonnegligible probability of Σ ∗ case that p [Σ | C ] ≤ 1 / 4 p ( n ) turns out to be analyzable similarly to the case that ∗ ∗ ); in both cases we simply use the fact that S is unlikely to produce a Y = F (Σ ∗ successful opening to Σ .

57 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1209 With the above in mind, we begin by analyzing the event in which we do not expect the scheme to be binding. For the event Claim 7.14. { } ∗ ∗ Y = F (Σ [( ( p [Σ ] | C )) > ∧ / 4 p ( n ))] ∧ [ P =2] 1 E = , 1 ∗ ∗ [ / )) ∨ ( p [Σ =1] | C ] ≤ 1 P 4 p ( n ))] ∧ (Σ [( Y ∨ F = E Pr[ we have / 2 . ]=1 1 ∗ { 1 , 2 } after C ,Σ Proof of Claim. P is chosen randomly in ,and are Y , F determined. Now we want to show that the scheme is binding on the complement of E .First 1 =1. we handle the case that P For the event Claim 7.15. ∗ ∗ E [ Y = F (Σ )] , = [ p [Σ { | C ] > 1 / 4 p ( n )] ∧ [ P =1] } ∧ 2 ∗ Pr[ S we have ( 4 ≤ 1 / succeeds p ] n ) . E ∧ 2 ∗ ∧ succeeds ); E n ] > 1 / 4 p ( S Suppose for contradiction that Pr[ ProofofClaim. 2 we will show that we can break the target collision–resistance property of F with before nonnegligible probability. In order to do so, we need to output an element x R ←F , we need to output f seeing the hash function, and then given a random function ′ ′ x such that f ( x )= f = x ). We do this as follows. First we simulate the interaction ( x ∗ between S R up to the end of the first-phase commitment and record c and as the sender’s view so far. Then we continue the interaction from to the end and set x c ∗ x in the protocol (if no valid value is given, we set to S to be the value of σ sent by ∗ some default value). (In case =1and S phase produces two values for σ in breaking the scheme, choose one of the two at random.) Now we output x ,store state = c , R . We now rerun the interaction between ←F f and receive a random hash function ∗ ′ ∗ S x and to be the value of σ sent by S , starting with the view ( in c, f ), and set R ∗ produces two values). =1and S phase the protocol (again choosing randomly if To see that this strategy breaks the target collision–resistance property with non- negligible probability, consider the second completed execution of the interaction be- ∗ and R (the one with the given, random, hash function f , which we now de- S tween ) ). By assumption, with probability greater than 1 4 p ( n F note as a random variable / ∗ ∗ ∗ Y = F (Σ ), and ), p [Σ | succeeds, C ] > 1 / 4 p ( n S in this execution, it holds that ∗ ∗ S =1. Since P succeeds and P = 1, it must be the case that produces two S successful openings Σ Σ to the first-phase commit. At least one of these is different , 2 1 ∗ ∗ F (Σ 2, we )= Y = F (Σ , yet both must satisfy ). With probability at least 1 / from Σ i ′ ∗ output Σ =Σ as x . Now, conditioned on all this, we argue that we had nonnegligi- i ∗ as x (prior to receiving F ). 4 p ( n )) of outputting Σ ble probability (of at least (1 / 2) · 1 / ∗ This follows because [Σ p p ] 1 C 4 > ( n ). Therefore, we break the target collision– | / / 4 p ( n )) · (1 / 2) · (1 / 2) · (1 / 4 p ( n )), which resistance property with probability at least (1 is a contradiction. =2,namely,theevent Now we turn to the complement of in case P E 1 ′ ∗ ∗ E [( Y = F (Σ = )) ∨ ( p [Σ { | C ] ≤ 1 / 4 p ( n ))] ∧ [ P =2] } . Since we are now restricted to = 2, there is a single first-phase decommitment value P ∗ produced by S which we denote by the random variable Σ. ∗ ∗ ′ that Σ =Σ (assuming S E First we argue that it is almost always the case in succeeds).

58 1210 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN For the event Claim 7.16. ∗ ′ E ∧ (Σ = Σ ) , = E 3 ∗ S Pr[ we have ) ] ≤ 1 / 4 p ( n succeeds . ∧ E 3 ∗ ∗ ′ = F ,eitherwehave ), in which case S Y cannot succeed (Σ Proof of Claim. E In ∗ ∗ ∗ =Σ unless Σ p C ] ≤ (1 / 4( p ( n ))), in which case S [Σ successfully opens | ,orwehave ∗ to value Σ with probability at most 1 p ( n ). 4 / ′ ∗ { [Σ E =Σ ] , we can focus on the event that [ P =2] } . So now, instead of ∧ For this, we have two cases, depending on whether the transcript T of the first-phase commitment (including the reveal) gives a binding second phase or not. For the event Claim 7.17. ∗ [T =Σ = ] ∧ [ P =2] ∧ [Σ ∈B ] } , { E 4 we have ∗ Pr[ S E succeeds ] ≤ 1 / 4 p ( n ) . ∧ 4 If T ∈B , then the second-phase commitment is binding. Since Proof of Claim. ∗ can succeed only with negligible probability. S P =2, For the event Claim 7.18. ∗ P [Σ =Σ , ] ∧ [ { =2] ∧ [T / ∈B ] } = E 5 we have ∗ Pr[ S ( ∧ . ] ≤ 1 / succeeds p E n ) 4 5 ∗ Proof of Claim. Assume for contradiction that Pr[ S succeeds ∧ E . ] > 1 / 4 p ( n ) 5 R p ( n )over c / By Markov bound, this implies that with probability at least 1 8 ,it ← C holds that ∗ (11) Pr[ S E | succeeds C = c ] ∧ 1 / 8 p ( n ) . > 5 ( ) 2 We will use this to break the -binding of ( S , R ). Similarly to the proof of Claim 7.15, 1 ∗ , R ) beginning with the same first-phase commit c . S we carry out two executions of ( 8 satisfies (11). Then, with some probability c c ] greater than 1 / q p ( n ), Assume that [ full transcript whose first phase is not in the first execution will produce an accepting ∗ ∗ c σ [ = ]. Note that conditioned on C = c , = σ σ ,withanopeningtosomevalue B the probability that a random execution produces an accepting full transcript with ′ σ is no more likely than = σ must also be at least q [ c ], since σ an opening to some ∗ 3 σ ]. It follows that with probability at least (1 / 8 p ( n )) · q [ c ] · q [ c ]=Ω(1 /p ( n [ c ), we ) ̃ and can output two transcripts λ such that the following hold: λ both transcripts are accepting and start with , • c the part of the first-phase commitment in both transcripts is not in B • , • the first-phase commitment in λ is decommitted to a different value than the ̃ . λ one in ) ( 2 S , R ) with nonnegligible probability. -binding of ( Namely, we break the 1 ∨ E With the above claims, we complete the proof. By inspection, we have Pr[ ]= i i 1, and thus 4 ∑ 1 1 ∗ ∗ , + succeeds ]+ Pr[ ≤ Pr[ S ≤ E ∧ E ] succeeds] S Pr[ 1 i 2 p ( n ) =1 i as desired.

59 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1211 The commitment scheme ( S R ) from Lemma 7.13 is only Boosting the binding. , 3 ( ))-binding. Nonetheless, by the following “folklore” claim, ( S , R ) implies a +neg( n 4 n commitment scheme that is neg( )-binding and preserves the same hiding property as the original scheme. There exists an efficient procedure that for any function ≥ Claim 7.19. δ δ converts a statistically (resp., computationally) 1 − / ( n )) -binding com- poly( n ) (1 , R ) into a commitment scheme mitment scheme S, R ) that is statistically (resp., ( S ( S R ) is statistically (resp., computation- computationally) binding. Furthermore, if ( , ) . ally) hiding, so is ( S, R S, R b , . The protocol ( Proof ) is defined as follows: in order to commit to a bit = n/δ the two parties run =poly( n ) independent executions of the commit stage t S b ) , R ) one after the other, where S and R act as S and R , respectively. In the of ( ( decommits, via the reveal stage of ( S R ), all the t commitments and R reveal stage, , S accepts if and only if all the commitments ar e opened successfully to the same value. The hiding of the above scheme follows by a straightforward hybrid argument. For ∗ be a PPT trying to break the binding of ( S, R ). We show the binding part, let S ∗ ∗ that S S breaks the binding of ( S, R ) only with negligible probability, and since ) is computationally binding. was arbitrarily chosen, it follows that ( S, R ∗ We say that S breaks the binding of the i th execution S , R ) if while trying of ( S, R ) it successfully opens the to break the binding of ( th commitment into two i , C different values. Notice that this event depends on several random variables: *i ∗ ( c ) ,c Supp( ∈ S ,C that ), we define q C ( c ) to be the probability over ,c C i i >i i bad if Pr[ i 1 − δ /p /p ( n ), and otherwise call c 1 n good . We will now show that 1 / 2 p ( n )] > 1 − δ +1 / 2 i i i ∗ n ( p 2 ) breaks the binding of ( S , R ) with probability 1 − δ +1 / − S n neg( − 1 ). Thus, ). n > 1 − δ +1 / 3 neg( ( n ) p Let E be the event that for some i , is bad. By the above and a union C 1 1 / ) p ( n )] up to an additive error 1 / 4 p ( n ). (In order to do so, we sample n · p 2 i i 1 / 2 p ( n )] > 1 − δ +1 / 2 p ( n ) by sampling n · i i 1 / 2 i i
*

*60 1212 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN Pr[ ] ≤ t/p ( n ). Finally, we have E 2 ∗ S Pr[ ∧¬ ] E ∧¬ breaks the binding E 2 1 ] [ t ∧ ))] [( C n good) ∧ ( q ( ( C /p ,C 1 ) > ≤ Pr 1 /p ( n )) ( C good) [( good) ∧ ( ∣ i ( /p ( n j *

*61 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1213 is statistically hiding and computationally binding. The statistical hiding property holds regardless of whether or not is secure (hard f f to invert). On the other hand, if is uniformly (resp., nonuniformly) secure, than ) R , S ( will be computationally binding with uniform (resp., nonuniform) security. ProofofTheorem 1.1. We start off by constructing a collection of 2-phase com- k ( n ) (which we will mitment schemes from f using Theorem 6.1. For any polynomial m choose below) we can construct in time polynomial in n ) n a collection of =poly( { = COM public-coin 2-phase commitment schemes Com ,..., Com } with message 1 m ( ) , 1) such that n lengths ( k i ∈{ 1 , 2 ,...,m } such that scheme Com • there exists an index is statistically i hiding, and ) ( 2 -binding. is computationally 2 ,...,m } ,scheme Com • for every index i ∈{ 1 , i 1 (As remarked after Theorem 6.1, we can obtain 2-phase commitments with message )) for any polynomial ) ,k ( k n k that we choose. Using only 1 bit of the lengths ( ( n − 1 zeros), we obtain message lengths ( k, 1).) second-phase message (padding with k we use [7, 29] to obtain a f Now in order to apply Theorem 7.20, from 2 / k ( ) ) k ( n n universal one-way hash family F { f : →{ 0 , 1 } { 0 , 1 } = } for some n polynomial k (which we use to determine the message length for the 2-phase com- ′ 14 Let the resulting (standard) commitment schemes be Com = mitment above). i ( Com 2-to-1- FullTransform F ). By Theorem 7.20 and Lemma 7.9, we know that , i ′ Com • is statistically hiding, is statistically hiding if Com i i ( ) ′ 2 • Com is computationally Com is computationally binding if -binding, and i i 1 ′ Com is public coin. is public coin if Com • i i This means that we now have a collection of public-coin (standard) commitment } { ′ ′ ′ m n ,where ), such that =poly( COM schemes ,..., Com = Com m 1 ′ i ∈{ 1 , 2 ,...,m } such that scheme Com • there exists an index is statistically i hiding, and ′ ∈{ 1 , 2 ,...,m } ,scheme i • for every index Com is computationally binding (in i the standard sense of binding). We are almost done, except that we are still left with a collection of commitments single commitment scheme. The followi ng claim states that the latter instead of a he desired commitment scheme. collection can be converted into t There is an efficient procedure that converts a polynomial collection of Claim 8.1. commitment schemes, at least one of which is statistically hiding and all of which are single commitment scheme that is statistically hiding computationally binding, into a and computationally binding. In addition, if we start off with public-coin schemes, we also end up with a public-coin scheme. and ⊕···⊕ b , we randomly secret-share b = b Proof . Tocommittoabit b m 1 b commit to share using the i th commitment scheme. Alternatively, the proposition i can be deduced from [25, Thm. 5.2]. The main theorem statement is now complete since we now have a single commit- ment scheme that is statistically hiding and computationally binding, and the only complexity assumption made is the existence of one-way functions. 14 x Since we are using here the uniform definition of universal one-way hash family (i.e., where is sampled by A ), we need to use the theorem of Katz and Koo [29]. In their theorem, however, it is not explicitly defined whether or not the adversary can encode additional information (i.e., state ) between the declaration of x and finding the collision (see Remark 7.5). Fortunately, the stronger version of this theorem required by our proof follows readily from their original proof.*

62 1214 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN es mentioned. By inspection, we ob- We now proceed to the additional properti serve that the statistical hiding properties throughout the construction hold regardless (see, e.g., Lemma 6.13). As for nonuniform security, we observe of the security of f that our construction is “fully black-box” in the sense of [40]; in particular, the com- a PPT p putational binding property is proven by specifying for every polynomial ∗ is any sender strategy (of arbitrary complexity) that reduction R such that if S ∗ S ), then R n /p breaks the binding property with probability 1 ( inverts f with nonneg- ∗ is a nonuniform PPT algorithm, then we obtain S ligible probability. In particular, if f a nonuniform PPT inverter for is nonuniformly secure. , which cannot exist if f Appendix. Collision probability lemmas. We prove the lemmas presented in section 6.2.1. ( X 6.4. Restatement of Lemma For independent pairs of random variables , ,Y ) 1 1 X ( ..., ) , ,Y m m m ∏ 1/2 1/2 CP ) | ( Y ) (( X )) = ,...,Y ,...,X Y | CP . ( X i i 1 m 1 m =1 i Note that X and Y ) can be correlated; it is required only that the pair be X ,Y ( i i i i independent from the other tuples. Proof. Since the X y ,...,y ’s are independent, for all ,wehave m 1 i m ∏ | ,...,X X ) | CP( ) . )= CP(( (12) X y = ,...,Y y = m i 1 Y = y Y m i 1 m i 1 =1 i This gives us 1/2 (( X )) ,...,X ,...,Y ) | ( Y CP 1 m 1 m [ ] 1/2 CP =E ,...,X ) | (( ) X 1 m ,...,Y Y 1 m ) Y ( ,...,Y 1 m ] [ m ∏ 1/2 ) | (by 12) CP X ( =E i Y i ) ,...,Y ( Y 1 m =1 i m ] [ ∏ 1/2 (by independence of | ’s) E ( X ) Y CP = Y i i i Y i i =1 m ∏ 1/2 = CP . ( X ) | Y i i i =1 ( 6.5. X Suppose random variables ,Y Restatement of Lemma ) ,..., ( X ) ,Y m m 1 1 + i = and all ∈ R ,...,α α satisfy the following conditions for some values of m 1 , 2 1 : ,...,m 1. For every ( y , ,...,y ) ,...,Y ,Y ) ∈ Supp( Y 1 1 − i − 2 i 1 1 1/2 CP ( X . | α ≤ ) | Y | y i y ,...,Y i y Y = = ,...,Y = y = Y i − i i − 1 − 1 i 1 1 1 1 i 1 1 − Y random variables +1 ,...,y i ) ∈ Supp( ,the ,Y ,...,Y ) ( 2. y For every 1 i 2 1 i Y ,X ,..., ,...,X y ,and Y = are independent after conditioning on X 2 +1 1 i i 1 1 Y = y . i i

63 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1215 Then, m ∏ 1/2 CP ) | ( Y (( ,...,Y . )) ≤ ,...,X X α m 1 1 m i =1 i By induction, it suffices to prove Proof. (13) 1/2 1/2 CP (( ) | ( Y , ,...,Y )) )) X α ,...,Y · CP ≤ (( X ,...,X ,...,X Y ( | ) 1 1 m 1 m m − 1 m 1 1 m − 1/2 and then by iteratively expanding CP | X ) ,...,X ( Y ,...,Y )) in terms of (( 1 m m − 1 1 1 − ′ α X = X | ’s, we get our result. To simplify notation, we write j Y m = y y ,...,Y = − 1 m − 1 1 1 m m ′ = Y Y | are clear from context. We prove and ,...,y y when 1 ,...,Y Y − m = y m 1 = y 1 1 m 1 − 1 − m m (13) as follows: 1/2 CP X (14) ,...,X (( ) | ( Y )) ,...,Y m m 1 1 [ ] 1/2 CP (15) ) ) (( X | ,...,X =E m Y ,...,Y 1 1 m ) ,...,Y Y ( m 1 ] [ ] [ 1/2 ′ =E (( | ) ) (16) X ,...,X CP E m ,...,Y 1 Y 1 m ′ Y ,...,Y Y ) ( m 1 − 1 m [ ] [ ] 1/2 1/2 ′ ′ CP =E | X (( X · ,...,X ) | ( ) ) CP E (17) ,...,Y Y Y ,...,Y m m − 1 1 1 1 m m ′ Y ) ,...,Y Y ( 1 m 1 − m [ ] [ ] 1/2 1/2 ′ CP (( X ,...,X E ) ) | X ( ) · | CP (18) =E m m − 1 ,...,Y 1 Y Y ,...,Y 1 − m 1 1 m ′ Y ) Y ( ,...,Y m 1 − 1 m [ ] 1/2 ′ ′ 1/2 CP (19) ,...,X ) | ) ( Y | (( ) · CP X X =E Y m − 1 1 ,...,Y 1 − m 1 m m Y ,...,Y ) ( 1 m 1 − [ ] 1/2 α ≤ CP ) (20) · ) (( X E ,...,X | ,...,Y m Y m − 1 1 1 m − 1 ) Y ,...,Y ( 1 − m 1 1/2 ≤ α CP (21) (( X · ,...,X . )) ,...,Y ) | ( Y 1 m − 1 − m 1 1 m X Equation (17) follows because conditioned on Y ,...,X = y ,...,Y y = m m m 1 1 1 and ,...,X are independent. Equation (18) follows because conditioned on Y X 1 1 m m − y = = y are independent. Finally, (20) follows from the assumption ,...,Y Y 1 1 m m 1 − 1 − y that for all ( ) ∈ ,...,y Y ,Y ,...,Y ), Supp( 1 1 2 i m − 1 − 1 1/2 ′ ′ 1/2 CP | Y X ≤ )=CP α ( X ) | . | ( Y | = y ,...,Y m = Y Y = y ,...,Y = y m m y 1 m − 1 1 m − 1 1 m m − 1 − 1 1 m m 6.6. Restatement of Lemma ) be (Randomness Extraction Lemma.) Let X, Y ( denote H any (possibly correlated) pair of random variables, and let random variable a random hash function from a family of pairwise-independent hash functions with H α are represented by H q − α ) -bit strings . Suppose the hash functions from ( range { 0 , 1 } √ 1/2 ( − +3) α CP and | 2 X ( Y ≤ .If H is independent from ( X, Y ) ,then ) √ 1/2 − q ( − 1) CP Y ≤ | 2 )) X ( H, H (( . ) 1/2 Proof. We bound the value of CP H, H ( X (( | Y ) as follows: )) 1/2 CP ( H, H ( X ) | Y ) [ ] 1/2 CP ( | H, H ( X ) ) =E Y = y ← Y y ) [ ]( √ ( ≤ H, H since CP( )) Z 1/2 − α · | H ) )+2 CP( X ( E ≤ CP y Y = − α ) Z · (CP( CP( )+2 H ) Y ← y )] [ ( √ 1/2 1/2 α − ≤ E (Cauchy–Schwarz/Jensen) CP ( CP ( H X | ) 2 · )+ y = Y ← Y y

64 1216 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN (( ) ) [ ] √ 1/2 1/2 α − CP E ( X | ( H 2 ) ) · =CP + Y y = y ← Y √ 1/2 1/2 − α =CP H | Y )+ · ( (CP 2 ) ) ( X √ √ 1/2 − ) ( q − − α α = | Y )+ · 2 (CP X )(since | h | ( q − α ) 2 = ( ) √ √ − α √ 2 α − q α ( ) − − + 2 · 2 ≤ 8 ) ( √ √ √ α ) − ( q − − α · 2 2 · 2 < √ 1) − ( q − 2 . = 6.7. For any triple of (possibly correlated) random Restatement of Lemma Y ,and Z variables , X , √ 1/2 1/2 1/2 ) ≤ CP X ( ( X ( Y, Z )) ≤ | | Supp( Z ) |· CP Y ( X | Y ) . | CP ) X Supp( Supp( Y z ∈ Supp( Z ), let v )and Proof .Foreach ∈ y R be the vector ∈ y,z ]. With this, we compute for y = Y ( x )=Pr[ X = x ∧ Z = z | v th entry is x whose y,z each y ∥ ∥ ∥ ∥ ∑ ∑ ∥ ∥ ‖ (triangle inequality) ‖ v ≤ v ∥ ∥ y,z y,z 2 ∥ ∥ z z 2 ( ) / 1 2 ∑ √ 2 Supp( ‖ Z ) ‖ · (Cauchy–Schwarz/Jensen) v ≤ y,z 2 z ( ) 1 2 / ∑ √ 2 = · x ) Z v ) ( Supp( y,z z,x ⎞ ⎛ 2 / 1 ) ( 2 ∑ ∑ √ ⎠ ⎝ x ) Z · ( ) ≤ Supp( (nonnegativity of v )) ( x v y,z y,z z x ∥ ∥ ∥ ∥ ∑ √ ∥ ∥ = . Z Supp( v ) · ∥ ∥ y,z ∥ ∥ z 2 ∑ ∑ 1/2 1/2 Since CP ‖ v )= ‖ X ‖ v ( ‖ X and CP | (( , | )) = | Z ) | ( y y Y = y Y Y = y,z = y,z z z 2 2 taking expectations over Y for both sides of the above inequalities yields the claim. Restatement of Lemma 6.8. Let random variable H denote a random hash α function from a family of pairwise-independent hash functions 0 , 1 } H with range { . 2 − α ε> For any ≤ ε ) ,if 0 CP( X and H is independent from X , then random · 2 ( H, H ( X )) is ε -close in statistical distance to uniform. variable − α q α =2 L . We bound the statistical distance of ( and H, H ( X )) Let D =2 Proof. from uniform as follows: √ DL 1 ( H, H ( X )) − U − )) X ( U | H, H ‖ ( | ‖ ≤ q q 2 1 2 2 √ √ DL q − · CP( H, H ( X )) − = 2 2 √ √ ) ( 1 DL 1 1 · ≤ X − )+ CP( L 2 D DL

65 STATISTICALLY HIDING COMMITMENTS FROM ONE-WAY FUNCTIONS 1217 √ CP( ) · L X = 2 ε . ≤ 2 We are grateful to the anonymous referees for their exten- Acknowledgments. sive comments and corrections. We also thank Oded Goldreich for helpful suggestions. REFERENCES M. Nguyen, S. J. Ong, and S. Vadhan , Statistical zero-knowledge arguments for NP from [1] any one-way function , in Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Washington, DC, 2006, pp. 3–14. I. Haitner and O. Reingold Statistically-hiding commitment from any one-way function , [2] , in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 2007. [3] , Communication theory of secrecy systems , Bell System Tech. J., 28 (1949), C. Shannon pp. 656–715. W. Diffie and M. E. Hellman [4] New directions in cryptography , IEEE Trans. Inform. Theory, , 22 (1976), pp. 644–654. ̊ J. H , A pseudorandom generator from any [5] astad,R.Impagliazzo,L.A.Levin,andM.Luby , SIAM J. Comput., 28 (1999), pp. 1364–1396. one-way function [6] , How to construct random functions ,J.ACM, O. Goldreich, S. Goldwasser, and S. Micali 33 (1986), pp. 792–807. J. Rompel , [7] , in Proceed- One-way functions are necessary and sufficient for secure signatures ings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990, pp. 387–394. [8] , Bit commitment using pseudorandomness , J. Cryptology, 4 (1991), pp. 151–158. M. Naor [9] , Proofs that yield nothing but their validity or O. Goldreich, S. Micali, and A. Wigderson all languages in NP have zero-knowledge proof systems , J. ACM, 38 (1991), pp. 691–729. [10] R. Impagliazzo and M. Luby , One-way functions are essential for complexity based cryptog- raphy , in Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Washington, DC, 1989, pp. 230–235. [11] One-way functions are essential for non-trivial zero- R. Ostrovsky and A. Wigderson , , in Proceedings of the 2nd Israel Symposium on Theory of Computing Systems, knowledge IEEE Computer Society, Washington, DC, 1993, pp. 3–17. [12] , Limits on the provable consequences of one-way permutations , R. Impagliazzo and S. Rudich in Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1989, pp. 44–61. D. Simon , Finding collisions on a one-way street: Can secure hash functions be based on gen- [13] , in Proceedings of Advances in Cryptology—EUROCRYPT ’98, Lecture eral assumptions? Notes in Comput. Sci. 1403, Springer-Verlag, New York, 1998, pp. 334–345. ́ [14] epeau , Minimum disclosure proofs of knowledge ,J. G. Brassard, D. Chaum, and C. Cr Comput. System Sci., 37 (1988), pp. 156–189. ́ [15] G. Brassard, C. Cr epeau, and M. Yung , Constant-round perfect zero-knowledge computa- tionally convincing protocols , Theoret. Comput. Sci., 84 (1991), pp. 23–52. [16] M. Naor, R. Ostrovsky, R. Venkatesan, and M. Yung Perfect zero-knowledge arguments , , J. Cryptology, 11 (1998), pp. 87–108. for NP using any one-way permutation O. Goldreich, S. Micali, and A. Wigderson , How to play any mental game or a complete- [17] ness theorem for protocols with honest majority , in Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1987, pp. 218–229. [18] J. F. Boyar, S. A. Kurtz, and M. W. Krentel , A discrete logarithm implementation of perfect zero-knowledge blobs , J. Cryptology, 2 (1990), pp. 63–76. ̊ [19] ard, and J. Graaf , Multiparty computations ensuring privacy of each D. Chaum, I. Damg party’s input and correctness of the result , in Proceedings of Advances in Cryptology— CRYPTO ’87, Lecture Notes in Comput. Sci. 293, Springer-Verlag, New York, 1987, pp. 87– 119. [20] T. P. Pedersen , Non-interactive and information-theoretic secure verifiable secret sharing ,in Proceedings of Advances in Cryptology—CRYPTO ’91, Lecture Notes in Comput. Sci. 576, Springer-Verlag, New York, 1991, pp. 129–140.

66 1218 HAITNER, NGUYEN, ONG, REINGOLD, AND VADHAN S. Goldwasser, S. Micali, and R. L. Rivest , [21] A digital signature scheme secure against adaptive chosen-message attacks , SIAM J. Computing, 17 (1988), pp. 281–308. [22] O. Goldreich and A. Kahan How to construct constant-round zero-knowledge proof systems , , J. Cryptology, 9 (1996), pp. 167–190. for NP M. Naor and M. Yung [23] Universal one-way hash functions and their cryptographic appli- , cations , in Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1989, pp. 33–43. ̊ ard, T. P. Pedersen, and B. Pfitzmann [24] Statistical secrecy and multibit commit- I. B. Damg , , IEEE Trans. Inform. Theory, 44 (1998), pp. 1143–1151. ments [25] I. Haitner, O. Horvitz, J. Katz, C. Koo, R. Morselli, and R. Shaltiel Reducing com- , plexity assumptions for statistically-hiding commitment , in Proceedings of Advances in Cryptology—EUROCRYPT 2005, Lecture Notes in Comput. Sci. 3494, Springer-Verlag, New York, 2005, pp. 58–77. S. J. Ong and S. Vadhan [26] Zero knowledge and soundness are symmetric , in Advances in , Cryptology—EUROCRYPT 2007, Lecture Notes in Comput. Sci. 4515, Springer-Verlag, New York, 2007, pp. 187–209. R. Ostrovsky , One-way functions, hard on average problems, and statistical zero-knowledge [27] proofs , in Proceedings of the 6th Annual Structure in Complexity Theory Conference, IEEE Computer Society, Washington, DC, 1991, pp. 133–138. M. Nguyen and S. Vadhan , Zero knowledge with efficient provers , in Proceedings of the [28] 38th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 2006, pp. 287–295. J. Katz and C. Koo On Constructing Universal One-Way Hash Functions from Arbitrary [29] , One-Way Functions , Cryptology ePrint Archive, http://eprint.iacr.org/2005/328, 2005. [30] , Inaccessible entropy , in Proceedings of I. Haitner, O. Reingold, S. Vadhan, and H. Wee the 41st Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, to appear. [31] O. Goldreich , Foundations of Cryptography: Basic Tools , Cambridge University Press, Cam- bridge, UK, 2001. R. Ostrovsky, R. Venkatesan, and M. Yung Fair games against an all-powerful adversary , [32] , in Advances in Computational Complexity Theory, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 13, AMS, Providence, RI, 1993, pp. 155–169. [33] , A new interactive hashing theorem , in Proceedings of the 22nd I. Haitner and O. Reingold Annual IEEE Conference on Computational Complexity, IEEE Computer Society, Wash- ington, DC, 2007, pp. 319–332. ́ C. Cachin, C. Cr , Oblivious transfer with a memory-bounded re- epeau, and J. Marcil [34] ceiver , in Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Washington, DC, 1998, pp. 493–502. Y. Z. Ding, D. Harnik, A. Rosen, and R. Shaltiel , Constant-round oblivious transfer in [35] , in Theory of Cryptography, First Theory of Cryptography the bounded storage model Conference, TCC 2004, Lecture Notes in Comput. Sci. 2951, Springer-Verlag, New York, 2004, pp. 446–472. ́ C. Cr [36] epeau and G. Savvides , Optimal reductions between oblivious transfers using interactive hashing , in Proceedings of Advances in Cryptology—EUROCRYPT 2006, Lecture Notes in Comput. Sci. 4004, Springer-Verlag, New York, 2006, pp. 201–221. [37] , Privacy amplification by public discussion , C. H. Bennett, G. Brassard, and J.-M. Robert SIAM J. Comput., 17 (1988), pp. 210–229. [38] O. Goldreich, S. Goldwasser, and N. Linial , Fault-tolerant computation in the full infor- mation model , SIAM J. Comput., 27 (1998), pp. 506–544. [39] , An equivalence between zero knowledge and commitments ,inPro- S. J. Ong and S. Vadhan ceedings of the Third Theory of Cryptography Conference (TCC ‘08), R. Canetti, ed., Lecture Notes in Comput. Sci. 4948, Springer-Verlag, New York, 2008, pp. 482–500. [40] O. Reingold, L. Trevisan, and S. Vadhan , Notions of reducibility between cryptographic primitives , in Proceedings of the First Theory of Cryptography Conference (TCC ‘04), M. Naor, ed., Lecture Notes in Comput. Sci. 2951, Springer-Verlag, New York, 2004, pp. 1–20.

∗ Efficient Lattice (H)IBE in the Standard Model † Shweta Agrawal Dan Boneh Xavier Boyen University of Texas, Austin Stanford University PARC Abstract We construct an efficient identity based encrypti...

More info »∗ The Complexity of Computing a Nash Equilibrium Constantinos Daskalakis Paul W. Goldberg Christos H. Papadimitriou Dept. of Computer Science, Computer Science Division, Computer Science Division, UC ...

More info »R © in Foundations and Trends Machine Learning Vol. 4, No. 2 (2011) 107–194 c © 2012 S. Shalev-Shwartz DOI: 10.1561/2200000018 Online Learning and Online Convex Optimization By Shai Shalev-Shwartz Con...

More info »R © in Foundations and Trends Theoretical Computer Science Vol. 10, No. 1-2 (2014) 1–157 c © 2014 D. P. Woodruff DOI: 10.1561/0400000060 Sketching as a Tool for Numerical Linear Algebra David P. Woodr...

More info »Replication Not Is Needed: Computationally-Priv Information Retriev al Single Database, ate (extendedabstra ct) y Rafail Ostro vsky Kushilevitz Ey al T ec hnion Bellcore the queries ask ed b y the u...

More info »