1 Concurrent Non-malleable Commitments from Any One-way Function Huijia Lin Rafael Pass Muthuramakrishnan Venkitasubramaniam Cornell University, } { huijia,rafael,vmuthu @cs.cornell.edu Abstract. We show the existence of concurrent non-malleable commit- ments based on the existence of one-way functions. Our proof of security only requires the use of black-box techniques, and additionally provides an arguably simplified proof of the existence of even stand-alone secure non-malleable commitments. 1 Introduction Often described as the “digital” analogue of sealed envelopes, commitment sender schemes enable a to commit itself to a value while keeping it secret from the . For some applications, however, the most basic security guarantees receiver of commitments are not sufficient. For instance, the basic definition of commit- ments does not rule out an attack where an adversary, upon seeing a commitment v , is able to commit to a related value (say, v to a specific value 1), even though − it does not know the actual value of v . This kind of attack might have devas- tating consequences if the underlying application relies on the independence of committed values (e.g., consider a case in which the commitment scheme is used for securely implementing a contract bidding mechanism). The state of affairs is even worsened by the fact that many of the known commitment schemes are actually susceptible to this kind of attack. In order to address the above con- non-malleable cerns, Dolev, Dwork and Naor (DDN) introduced the concept of commitments [6]. Loosely speaking, a commitment scheme is said to be non- malleable if it is infeasible for an adversary to “maul” a commitment to a value into a commitment of a related value ̃ v . v The first non-malleable commitment protocol was constructed by Dolev, Dwork and Naor [6]. The security of their protocol relies on the existence of one-way functions and requires O (log n ) rounds of interaction, where n ∈ N is the length of party identifiers (or alternatively, a security parameter). A more recent result by Barak presents a constant-round protocol for non-malleable commitments whose security relies on the existence of trapdoor permutations and hash functions that are collision-resistant against sub-exponential sized cir- cuits [2]. Even more recently, Pass and Rosen present a constant-round protocol, assuming only collision resistant hash function secure against polynomial sized circuits [12].

2 1.1 Concurrent Non-Malleable Commitments The basic definition of non-malleable commitments only considers a scenario in which two executions take place at the same time. A natural extension of this scenario (already suggested in [6]) is one in which more than two invoca- tions of the commitment protocol take place concurrently. In the concurrent , scenario, the adversary is receiving commitments to multiple values v , . . . , v 1 m while attempting to commit to related values ̃ v ̃ v . As argued in [6], non- , . . . , m 1 malleability with respect to two executions can be shown to guarantee individual independence of any ̃ v from any v . However, it does not rule out the possibility j i joint dependencies between more than a single individ- of an adversary creating ual pair (see [6], Section 3.4.1 for an example in the context of non-malleable encryption). Resolving this issue has been stated as a major open problem in [6]. Partially addressing this issue, Pass demonstrated the existence of commit- ment schemes that remain non-malleable under bounded concurrent composi- tion [10]. That is, for any (predetermined) polynomial p ( · ), there exists a non- malleable commitment that remains secure as long as it is not executed more than ( n ) times, where n ∈ N is a security parameter. More recently, Pass p and Rosen [12] constructed a commitment scheme that remains non-malleable also under an unbounded number of concurrent executions. Their construction uses only a constant number of rounds and is based on the existence of (certi- fied) claw-free permutations. The protocol—which is a variant of the protocol of [11]—relies on the message-length technique of [10], which in turn relies on the non-black box zero-knowledge protocol of Barak [1]. As such, it seems that practical implementations of this approach currently are not within reach. In contrast, the original construction of Dolev, Dwork and Naor (which is only stand-alone secure) relied on the minimal assumption of one-way functions and had a black-box security proof. Natural questions left open are thus: Can concurrent non-malleable commitments be based solely on the exis- tence of one-way functions? Does there exist concurrent non-malleable commitments with black-box proofs of security? A partial answer to the second question was provided by Pass and Vaikun- tanathan [13], demonstrating the existence of concurrent non-malleable com- mitments with black-box security proofs; their construction, however, relies on a new (and non-standard) hardness assumption with a strong non-malleability 1 flavor. 1.2 Our Results In this work, we fully resolve both of the above questions. Namely, we show the following theorem using only black-box techniques. 1 More precisely, they assume the existence of, so called, adaptive one-way permuta- tions —namely permutations which remain one-way even when the adversary has access to an inversion oracle.

3 Main Theorem If one-way functions exist, then there exists a statistically-binding commitment scheme that is concurrent non-malleable. Our protocol, which is a variant of the protocol of [6] (and in particular relies on the same scheduling techniques as in [6]), uses n ) number of communi- O ( cation rounds. Moreover, it seems that by relying on specific (number theo- Σ retic) hardness assumptions (and appropriate -protocols [4]), one can obtain an “implementable” instantiation of our protocol (without going through Cook’s reductions). Additional results. All previous constructions of non-malleable commitments require complex and subtle proofs. As an additional contribution, our protocol and its proof provide the arguably simplest proof of existence of non-malleable commitments (let alone the question of concurrency); more precisely, it provides a new (and arguably simpler) proof of the feasibility result of [6]. Furthermore, by relying on the concurrent security of our protocol, we also obtain a simple (and self-contained) proof of the existence of log n -round (stand- alone secure) non-malleable commitment schemes based on only the existence of one-way functions. As far as we know, a complete proof of this statement (which appeared only with a proof sketch in [6]) has never appeared before. Finally, we mention that our protocols satisfy a notion of non-malleability strict called liberal ) non-malleability—this notion, which was (as opposed to defined (but not achieved) in [6], requires simulation to be performed by a strict polynomial-time machine (as opposed to an expected polynomial-time machine). Our results provide the first construction of strictly non-malleable commitments based on one-way functions, or using a black-box security proof. 1.3 Overview Section 2 contains basic notation and definitions of commitment schemes and concurrent non-malleability. In Section 3, we present our O n )-round commit- ( ment scheme, and in Section 4, we prove that the commitment scheme is con- current non-malleable. In Section 5, we additionally provide the construction of O a n )-round (stand-alone secure) non-malleable commitment scheme based (log on any ( n )-round concurrent non-malleable commitment scheme. O 2 Definitions and Notations We let N denote the set of all integers. For any integer m ∈ N , denote by [ m ] ∗ | , 2 , . . . , m } . For any x ∈{ 0 , 1 } the set , we let 1 x | denote the size of x (i.e., the { A number of bits used in order to write it). For two machines M, A , we let M ( x ) denote the output of machine M on input x and given oracle access to A . The term is used for denoting functions that are (asymptotically) smaller negligible than one over any polynomial. More precisely, a function ν ( · ) from non-negative integers to reals is called negligible if for every constant c > 0 and all sufficiently − c n ν ( n ) < n large , it holds that .

4 2.1 Witness Relations We recall the definition of a witness relation for an language [8]. NP (Witness relation). Definition 1 for a language L ∈NP is A witness relation that is polynomially bounded, polynomial time recognizable R a binary relation L by L = { x : ∃ y s.t. ( x, y ) ∈ R and characterizes } L L y x ∈ L if ( x, y is a witness for the membership ∈ R We say that . We will also ) L ) = x ( x ) denote the set of witnesses for the membership x ∈ L , i.e., R ( R let L L y : ( x, y ) ∈ L } . In the following, we assume a fixed witness relation R { for each L language ∈NP . L 2.2 Interactive Proofs We use the standard definitions of interactive proofs (and interactive Turing machines) [9] and arguments (a.k.a computationally-sound proofs) [3]. Given a P and V , we denote by 〈 P, V 〉 ( x ) the random pair of interactive Turing machines, V P variable representing the (local) output of when interacting with machine x , when the random input to each machine is uniformly and on common input independently chosen. Definition 2 A pair of interactive machines (Interactive Proof System). P, V 〉 is called an interactive proof system for a language L if for every proba- 〈 V there is a negligible function ν ( · ) such bilistic polynomial time machine (PPT) that the following two conditions hold : – Completeness: For every x ∈ L , Pr [ 〈 P, V 〉 ( x ) = 1] = 1 – Soundness: x 6∈ L , and every interactive machine B , For every 1 〈 〉 ( x ) = 1] ≤ Pr [ B, V ( | x | ) ν In case that the soundness condition is required to hold only with respect to a computationally bounded prover, the pair P, V 〉 is called an interactive argument 〈 system. Special-sound proofs. A 3-round public-coin interactive proof for the language ∈NP with witness relation R , if for any L special-sound with respect to R is L L ′ ′ ′ ′ α , β , γ α, β, γ ) such that the initial messages α, α two transcripts ( are ) and ( ′ β, β are different, there is a deterministic procedure the same but the challenges to extract the witness from the two transcripts and runs in polynomial time. WI proofs for languages in NP can be based on the existence Special-sound of non-interactive commitment schemes, which in turn can be based on one- way permutations. Assuming only one-way functions, 4-round special-sound WI 2 proofs for NP exist. For simplicity, we use 3-round special-sound proofs in our protocol though our proof works also with 4-round proofs. 2 A 4-round protocol is special sound if a witness can be extracted from any two ′ ′ ′ ′ ′ ′ τ,α,β,γ ,β ) and ( ,γ τ ) such that τ transcripts ( τ , α = α . and β 6 = β ,α =

5 2.3 Indistinguishability Definition 3 Let X and Y be ((Computational) Indistinguishability). { countable sets. Two ensembles } A are said to } B { and ∈ Y X,y x ∈ X,y x,y Y ∈ x,y ∈ x x ∈ X , if for every probabilistic “distin- be computationally indistinguishable over whose running time is polynomial in its first input, there guishing” machine D X, y ( ) so that for every exists a negligible function ∈ · ∈ Y : ν x Pr [ a ← A ) : D ( x, y, a ) = 1] − Pr [ b ← B | : D ( x, y, b ) = 1] | < ν ( | x | x,y x,y 2.4 Witness Indistinguishability witness indistinguishable ( WI ) if the verifier’s An interactive proof is said to be output is “computationally independent” of the witness used by the prover for proving the statement. In this context, we focus on languages with a L ∈ NP corresponding witness relation R . Namely, we consider interactions in which L the prover is given a witness in R ( on common input x ). By saying that the x L output is computationally independent of the witness, we mean that for any two possible NP -witnesses that could be used by the prover to prove the statement x ∈ L , the corresponding outputs are computationally indistinguishable. (Witness-indistinguishability). Let 〈 P, V 〉 be an interactive Definition 4 L . We say that proof system for a language 〈 P, V 〉 is ∈ NP for , if for every probabilistic polynomial-time inter- R witness-indistinguishable L 1 ∗ 2 w { and for every two sequences , such that } } V active machine and { w L x x ∈ L ∈ x x 1 2 , the probability ensembles , w w L ∈ R ∈ ( x ) for every x L x x 1 ∗ 2 ∗ ∗ ∗ ( w ( z ) 〉 ( x ) } P } ) x ( 〉 {〈 z are com- and {〈 P ( w ) ( ) , V , V ) } , 0 ∈{ L,z ∈ x 1 L,z ∈{ 0 , 1 } x ∈ x x x L putationally indistinguishable over . ∈ 2.5 Commitment Schemes Commitment schemes are used to enable a party, known as the , to com- sender mit itself to a value while keeping it secret from the receiver (this property is hiding ). Furthermore, the commitment is called , and thus in a later stage binding when the commitment is opened, it is guaranteed that the “opening” can yield only a single value determined in the committing phase. In this work, we con- sider commitment schemes that are statistically-binding , namely while the hiding property only holds against computationally bounded (non-uniform) adversaries, the binding property is required to hold against unbounded adversaries. More precisely, a pair of PPT machines 〈 C, R 〉 is said to be a commitment scheme if the following two properties hold. ∗ R Computational hiding: , it holds that, For every (expected) PPT machine n { , 1 } . the following ensembles are computationally indistinguishable over 0 ∗ R ∗ n sta ( v { , z ) } – 1 1 v , ,v 0 ∈{ 0 , 1 } N,z ,n ∈ } ∈{ 2 1 〉 C,R 〈 ∗ R n ∗ sta { – ( v , z ) } 2 1 v , ,v 0 ∈{ 0 , 1 } } ,n ∈ N,z ∈{ 2 1 〈 〉 C,R

6 ∗ R where sta ) denotes the random variable describing the output of ( v, z 〉 〈 C,R ∗ v C, R 〉 . 〈 R after receiving a commitment to using Informally, the statistical-binding property asserts that, Statistical binding: R with overwhelming probability over the coin-tosses of the receiver , the transcript of the interaction fully determines the value committed to by the sender. We refer to [8] for more details. 2.6 Concurrent Non-Malleable Commitments Our definition of concurrent non-malleable commitments is very similar to that of [11], but different in two aspects: first, our definition of non-malleability is 3 w.r.t identities (in analogy with DDN [6]) ; second, our definition considers not 4 only the values the adversary commits to, but also the view of the adversary. C, R 〉 be a commitment scheme, and let n ∈ N be a security parameter. Let 〈 Consider man-in-the-middle adversaries that are participating in left and right interactions in which n ) commitments take place. We compare be- m = poly( and a simulated execution. In the man-in-the-middle tween a man-in-the-middle A is simultaneously participating in m left and right execution, the adversary A interactions. In the left interactions the man-in-the-middle adversary interacts receiving commitments to values , . . . , v , using identities id , . . . , id with C v 1 m 1 m interacts with A attempting to commit of its choice. In the right interaction R v ̃ v to a sequence of related values ̃ , again using identities of its choice , . . . , m 1 ̃ ̃ id , . . . , id . If any of the right commitments are invalid, or undefined, its value m 1 ̃ is set to . For any such that ⊥ id = id i for some j , set ̃ v = ⊥ —i.e., any commit- i j i ment where the adversary uses the same identity as one of the honest committers A is considered invalid. Let mim ( v , . . . , v , z ) denote a random variable that 1 m C,R 〉 〈 v , in the above experiment. , . . . , ̃ v describes the values ̃ and the view of A m 1 S directly interacts with R . Let In the simulated execution, a simulator S n com- v sim (1 , z ) denote the random variable describing the values ̃ ̃ , . . . , v 1 m 〈 〉 C,R mitted to by S , and the output view of S ; again, whenever view contains a right interaction i v where the identity is the same as any of the left interactions, ̃ is i set to . ⊥ A commitment scheme Definition 5. C, R 〉 is said to be concurrent 〈 non-malleable (with respect to commitment) if for every polynomial p ( · ) , and every probabilistic polynomial-time man-in-the-middle adversary that partic- A ipates in at most m = p ( n ) concurrent executions, there exists a probabilistic 3 That is, we disallow even copying of commitment as long as the adversary uses a different identity (than all the committers he receives commitments from). In contrast, [11] defined non-malleability w.r.t content; i.e., the adversary allowed copy commitments. This difference is inconsequential as any commitment non-malleable w.r.t content can be turned into one that is non-malleable w.r.t identities, and vice versa. 4 This point is particularly important when considering our definition w.r.t compos- ability; see Proposition 1 and Section 5.

7 polynomial time simulator S such that the following ensembles are computation- n 0 { : ally indistinguishable over , 1 } } { A v , . . . , v , z ) ( mim m 1 〉 C,R 〈 ∗ n 1 } v ,n ∈ N,z ∈{ 0 , 1 } ∈{ 0 ,...,v , m 1 } { S n (1 sim , z ) C,R 〉 〈 n ∗ ∈{ ,n ∈ N,z 0 , 1 } ∈{ } ,...,v 0 , 1 v m 1 We also consider relaxed notions of concurrent non-malleability: one-many, many- one and one-one secure non-malleable commitments. In a one-one (i.e., a stand- that alone secure) non-malleable commitment, we consider only adversaries A participates in participate in one left and one right interaction; in one-many, A A participates in many left and one one left and many right, and in many-one, right. Dolev, Dwork and Naor [6] argued that one-one commitments are also many- one secure. Pass and Rosen [11] additionally showed that one-many non-malleability implies (many-many) concurrent non-malleability if the com- mitment protocol is “natural”. Given our stronger definition, which also con- siders the view of the adversary, we prove that any protocol that is one-many non-malleable is also concurrent non-malleable. Namely, Let 〈 C, R 〉 be a one-many concurrent non-malleable commit- Proposition 1. 〈 ment. Then, is also a concurrent non-malleable commitment. C, R 〉 A Proof. = be a man-in-the-middle adversary that participates in at most Let m S ) concurrent executions. Below, we provide a simulator n A . S proceeds p ( for n z as follows on input 1 S . A ( z ) and internally emulates all the and incorporates n A . Messages left interactions for by simply honestly committing to the string 0 outputs S from the right interactions are instead forwarded externally. Finally A . the view of We show that the values that S commits to are indistinguishable from the A commits to. Suppose, for contradiction, that this is not the case. values that D p ( n ) such Then, there exists a polynomial-time distinguisher and a polynomial ∗ n v , , . . . , v that for infinitely many ∈ { 0 , 1 } n , z ∈ { 0 , there exist strings 1 } m 1 A n S (1 D ( v distinguishes such that , z , z ) and sta mim ) with proba- , . . . , v m 1 C,R 〉 〈 〉 C,R 〈 1 bility for which this happens. Consider the hybrid simulator . Fix a generic n n p ) ( n ′ , z , with the exception = v that on input 1 , . . . , v S , z , proceeds just as S m i 1 i , it instead commits to v . It directly follows that j ≤ that in left interactions j S S A ′ S ′ n n n 0 m sta , z ( (1 v , . . . , v (1 ). , z mim ) and sta , z sta ) = , z (1 ) = m 1 〈 C,R 〉 〈 〉 C,R 〈 〈 〉 〉 C,R C,R By a standard hybrid argument there exists an ∈ [ m ] such that i ∣ ] [ ∣ S i − 1 ′ n n ′ , z , a (1 (1 , z ) = 1 ) : D Pr sta ← a ∣ C,R 〈 〉 ∣ ] [ 1 ∣ S ′ n n ′ i ≥ sta , z − Pr D (1 ) : , z b , b ) = 1 ← (1 ∣ 〉 〈 C,R ( n ) m p ′ n ) and , z Note that the only difference between the executions by (1 S 1 i − n ′ n (1 , z ) is that in the former A receives a commitment to 0 S in session i , i

8 whereas in the latter it receives a commitment to v . Consider the one-many i ′ n ′ ̃ A , n, i executes S adversary z = (1 z , z that on input ̃ ) with the excep- 1 i − ’th left interaction is forwarded externally. Consider, the function tion that the i ̃ A n ′ ′ v , ̃ z ), i.e. values reconstruct (0 , and the view of , . . . , v mim that on input m com 1 ′ ̃ ̃ of A A , and sets ̃ v A = v , reconstructs the view in the emulation by if view i 1 A did not copy the identity of any of the left interactions, and ⊥ otherwise, and ̃ v , view . By construction, it follows that , . . . , v finally outputs ̃ 1 m ̃ S A i − 1 ′ n n , ̃ z )) = sta mim ) reconstruct (0 , z ( (1 〉 C,R 〈 〉 C,R 〈 ̃ S A ′ n i , v , z ) ̃ z )) = sta (1 ( mim reconstruct ( i 〉 C,R 〈 〉 C,R 〈 reconstruct Since is polynomial-time computable, this contradicts the one-many non-malleability of 〈 C, R 〉 . 3 The Protocol Our protocol is based on Feige-Shamir’s zero-knowledge protocol [7] while relying on the of Dolev, Dwork and Naor[6]. For simplicity message scheduling technique of exposition, our description below relies on the existence of one-way functions with efficiently recognizable range, but the protocol can be easily modified to work with any arbitrary one-way function (by simply providing a witness hiding proof that an element is in the range of the one-way function). The protocol l id 0 , 1 } proceeds in the following three stages on common input the identity ∈{ n of the committer, and security parameter . n r ∈ { 1. , 1 } In Stage 1, the Receiver picks a random string , and sends its 0 image s = f ( r ) through a one-way function f with an efficiently recognizable range to the Committer. The Committer checks that s f is in the range of and aborts otherwise. 2. c = com ( v ), where com ( · ) is any commit- In Stage 2, the Committer sends ment scheme that is statistically-binding. 3. c is a valid commitment for v or In Stage 3, the Committer proves that s is in the image set of f . This is proved by 4 l invocations of a special-sound WI proof where the messages are scheduled based on the id (very similar to the scheduling presented in [6]). More precisely, there are l rounds, where in i , the schedule round design is followed by design (See Figure 1). id 1 − id i i We remark that the scheduling (essentially identical to [6]) in Stage 3 of the protocol is the key in achieving concurrent non-malleability. Loosely speaking, the purpose of the scheduling is to guarantee that for each of the commitments that a man-in-the-middle adversary gives, there exists a point at which the adversary cannot answer the challenge from the receiver simply by “mauling” the commitments on the left (provided that the identity of the commitment is different from any of the commitments on the left). One important difference between our protocol and the protocol of [6] is that the designs we use consist of two three-round protocols, whereas the protocol in

9 [6] uses more rounds; this makes the analysis clearer. An additional simplification is the use of only proofs (instead of zero-knowledge proofs as in [6]). WI design design 0 1 α α 1 2 β α 1 1 β γ 1 1 γ α 1 2 β β 2 2 γ γ 2 2 Fig. 1. Description of the schedules used in Stage 3 of the protocol C, R 〉 is a statistically-binding commitment scheme. Claim 1 〈 We show that the 〈 C, R 〉 scheme satisfies the binding and hiding proper- Proof. ties. Protocol ConcNMCom l } 0 , 1 ∈ { An identifier . Common Input: id n v ∈ { 0 , 1 } . Auxiliary Input for Committer: A string Stage 1: n ∈ { 0 , 1 } R uniformly chooses . r → C: s = f ( r ). R C aborts if s not in the range of f . Stage 2: ′ poly ( n ) 1 } C uniformly chooses ∈ { 0 , . r ′ → c C com ( v,r = ). R: Stage 3: → R: 4 l special-sound WI proofs of the statement C ′ ′ v , r ) s.t c = com ( v,r either there exists values ( or s.t s = f r r ) there exists a value with verifier query of length 2 n , in the following schedule: For j = 1 to l do: Execute design design followed by Execute id − id 1 j j Non-Malleable String Commitment Scheme 〈 C,R 〉 Fig. 2. Binding: The binding property follows directly from the binding property of com . Hiding: The hiding property essentially follows from the hiding property of com and the fact that Stage 3 of the protocol is WI (since WI proofs are closed

10 under concurrent composition [7]). For completeness, we provide the proof. ∗ We show that any adversary that violates the hiding property of 〈 C, R 〉 R com . More precisely, given any can be used to violate the hiding property of ∗ adversary (without loss of generality, deterministic) that distinguishes R ′ 〉 C, R that distin- 〈 , we construct a machine a commitment made using R be the first message sent by . Let com guishes a commitment made using s ∗ ′ . r such that s = f ( r ), proceeds as R R on auxiliary-input a “fake” witness ∗ and forwards the external commitment R follows. It internally incorporates ∗ ′ R in Stage 2. In Stage 3, R com gives WI proofs using made using to ∗ . Finally, it outputs whatever outputs. From the WI R r the “fake witness” ′ distinguishes the commitment made R property of Stage 3, it follows that ∗ R using distinguishes the commitment made using com C, R 〉 . , if 〈 4 Proof of Security C, R 〉 is one-many concurrent non-malleable. 〈 Theorem 1 A be a man-in-the-middle adversary that participates in one execution Let Proof: S such in the left and many executions in the right. We construct a simulator ∗ { , 1 } 0 . that the following ensembles are computationally indistinguishable over } { A ( v, z ) mim C,R 〈 〉 n ∗ 1 } ,n v ∈ N,z ∈{ 0 , 1 } ∈{ 0 , } { S n sim (1 ) , z 〉 〈 C,R n ∗ , 1 } v ,n ∈ N,z ∈{ 0 , 1 } ∈{ 0 n S The simulator , z ) proceeds as follows. S incorporates A ( z ) and on input (1 n internally emulates the left interaction by honestly . committing to the string 0 S Messages in the right interactions are instead forwarded externally. Finally, A . We show that the values that S commits to combined outputs the view of with the output view are indistinguishable from the values that A commits to combined with its view. Since S honestly emulates the left interaction by n , this is equivalent to showing that committing to 0 { } { } A A n (0 ) ≈ , z mim ( mim ) v, z C,R 〉 〈 C,R 〉 〈 ∗ n n ∗ 0 , 1 } v ,n ∈ N,z ∈{ 0 , 1 ∈{ } , 1 } v ,n ∈ N,z ∈{ 0 , 1 } ∈{ 0 ˆ ˆ C, Towards this goal, we define a new commitment scheme R 〉 (much like the 〈 〈 〉 where the receiver can adaptor scheme in DDN [6]), which is a variant of C, R WI designs in Stage 3. Further- ask for an arbitrary number of special-sound ˆ ˆ C, 〈 R more, does not have a fixed scheduling in Stage 3; the receiver instead 〉 gets to choose which design to execute in each iteration (by sending bit i to select design can be emulated by ). Note that, clearly, any execution of 〈 C, R 〉 i ˆ ˆ 〈 R 〉 by simply requesting the appropriate designs. an execution of C, ˆ ˆ C, R 〉 is hiding, i.e. 〈 Using the same proof as in Claim 1, it follows that M , For every (expected) PPT machine Lemma 1 { { } } M M n ≈ sta sta v, z ) ( ) , z (0 ˆ ˆ ˆ ˆ R C, 〉 〈 〉 R C, 〈 ∗ ∗ n n } , 0 ∈{ N,z ∈ ,n } 1 , 0 ∈{ v 1 0 , 1 } v ,n ∈ N,z ∈{ 0 , 1 } ∈{

11 Below, in Lemma 2, we show that for every adversary A , there exists an ∗ PPT machine R non-uniform expected whose output, upon receiving a com- ˆ ˆ C, to v R values com- 〉 〈 mitment using , is indistinguishable from the view and the ( z ) when receiving a commitment to v using 〈 C, R 〉 ; by the hiding mitted to by A A A n ˆ ˆ R mim (0 〉 ) are , z ( v, z ) and mim C, we then conclude that 〈 property of C,R 〉 C,R 〉 〈 〈 ∗ 〈 C, R 〉 for R indistinguishable. On a high-level, will emulate an execution of ˆ ˆ C, R 〉 ) and then will attempt to (by requesting the appropriate design in A 〈 ∗ R extract the values committed to by to extract only A . In fact, it suffices for the left execution starts (as all values committed after the values committed to ∗ R ). to before-hand can be non-uniformly given to ( of ) denote the distribution of all joint views τ Γ A and the receivers A, z Let sends its first message in the left interaction directly A in the right, such that ∗ ∗ ∗ : { 0 , 1 } , ×{ 0 , 1 } after receiving the messages in →{ 0 τ 1 } . Let the function Z where ̃ Z z ‖ τ ‖ ̃ v be such that, ‖ . . . ‖ ̃ v z, τ ) = v ] are the values . . . ̃ v m , ` ∈ [ ( ` 1 ` 1 ( z ) in τ (using com ). committed to by A The main technical content of Theorem 1 is in proving the following lemma. For every PPT adversary , there exists an expected PPT adversary A Lemma 2 ∗ ∗ 0 , 1 R } . such that the following ensembles are indistinguishable over { { } ∗ ′ R ′ ) , z τ ←Z ( z, τ ) : sta – ← Γ ( ) A, z v, z ( ˆ ˆ 〉 C, R 〈 n ∗ , 1 } , ,n ∈ N,z ∈{ 0 v 1 } ∈{ 0 { } A – ( ) mim v, z 〉 C,R 〈 n ∗ 0 , 1 } v ,n ∈ N,z ∈{ 0 , 1 } ∈{ Before proceeding to the proof of lemma 2, note that by lemma 1, it holds that the following ensembles are indistinguishable { } ∗ R ′ – ) sta v, z ( ˆ ˆ 〉 C, R 〈 n ′ ∗ } v ∈{ ∈ N,z,τ,z 0 ∈{ 0 , 1 } , 1 ,n { } ∗ R ′ n ) – , z (0 sta ˆ ˆ 〉 C, 〈 R n ′ ∗ } v ∈{ ∈ N,z,τ,z 0 ∈{ 0 , 1 } , 1 ,n It thus follows that the following ensembles also are indistinguishable { } ∗ R ′ ′ , z Γ ←Z ( z, τ ) : sta A, z τ ( ← ) ( v, z ) – ˆ ˆ R 〉 C, 〈 ∗ n 1 , 0 ∈{ } ,n ∈ N,z } 1 ∈{ v , 0 { } ∗ ′ n ′ R sta ←Z Γ z, τ ) : ← ( A, z ) , z – τ ( (0 , z ) ˆ ˆ 〉 C, 〈 R n ∗ 0 1 } ∈{ ,n ∈ N,z ∈{ 0 , 1 } , v By lemma 2, we thus conclude that the following ensembles are indistinguishable, { } A mim – ) v, z ( 〉 〈 C,R n ∗ , 1 } , ,n ∈ N,z ∈{ 0 v 1 } ∈{ 0 { } A n mim – (0 , z ) 〉 〈 C,R n ∗ ∈ , 1 } v ,n ∈{ N,z ∈{ 0 , 1 } 0 which concludes the proof of theorem 1.

12 ∗ Description of R ∗ ′ z R = z ‖ τ ‖ ̃ v Input: ‖ ... ‖ ̃ v receives auxiliary input . 1 ` ∗ ˆ ˆ C, interacts externally as a receiver using R 〉 . Internally it incorpo- 〈 Procedure: R ( z ) and emulates a one-many man-in-the-middle execution by simulating all rates A C,R interaction by requesting the appropriate 〈 right receivers and emulating the left 〉 ˆ ˆ ) using 〈 ( C, A R 〉 z designs expected by from outside. Feed the view in τ to A and all right receivers. Emulate Main Execution Phase: τ and complete the execution with A . Let all the interactions from be the ∆ transcript of messages obtained. k For +1 to m , if interaction ` is convincing and its identity k = Rewinding Phase: is different from the left interaction, do: ∆ , find the first point ρ that is a safe-point for interaction k ; let the asso- – In ,β ,γ ). α ciated proof be ( ρ ρ ρ ′ ′ ) is obtained: ,β Repeat until a second-proof transcript ( – ,γ α ρ ρ ρ Emulate the left interaction as in the Main-Execution Phase. For the left interaction: If A expects to get a new proof from the external committer (case (i) • design from outside in Figure 5): Emulate the proof, by requesting for 0 committer. Forward one of the two proofs internally. If A sends a challenge for a proof whose first message occurs in • : Cancel ρ the execution, rewind to ρ and continue. ′ ′ ′ ,γ extract witness w from ( α ,β ,β ,γ ). Otherwise halt ) and ( α β – 6 = If β ρ ρ ρ ρ ρ ρ ρ ρ . and output fail w = ( v,r ) is valid commitment for interaction k , i.e. – ( v,r ) = c If , where com k c is the Stage 2 message in interaction k , then set ˆ v . Otherwise halt = v k k fail . and output ` +1 to all have their Stage 2 and 3 occurring Note that, since right interactions n τ A request a new commitment from the after , none of the rewinding can make external committer. For every interaction k that is not convincing or if the identity of the Output Phase: ,..., v = ⊥ . Output (ˆ v ) v ˆ right interaction is the same as the left interaction, set ˆ m 1 k and the view from the Main Execution Phase. n Finally, if it runs for more than 2 steps, halt and output . fail ∗ The construction of Fig. 3. R ′ Recall that by the definition of Proof it holds that z (of lemma 2). = Z z ‖ τ ‖ ̃ v ) ‖ . . . ‖ ̃ v z where ̃ v ( . . . ̃ v A , ` ∈ [ m ], are the values committed to by ` 1 1 ` ∗ ′ , internally . On a high-level, R com on auxiliary input using τ in the view z incorporates A ( z ) and emulates the left and the right executions for A . First, however, it starts by feeding A its part of the joint view τ . It, then, emulates ˆ ˆ (by 〈 the left interaction for C, by externally forwarding messages using R 〉 A appropriately choosing the “right” designs); the right interactions are instead dealt with internally by first honestly emulating the receivers on the right, from the view in τ —this is called the main execution . In a second phase, it then at- tempts to extract all the values committed to on the right—this is called the

13 rewinding phase . Finally, in the , it outputs the view of A and all output phase the values extracted, including the ones received as auxiliary input (additionally, if τ , or if it uses A fails in completing one of the commitments that started in ). The core the same identity as the left interaction, that value is replaced by ⊥ of the proof is to show that extraction during the rewinding phase is successful. Towards this goal, we need to ensure that there exist some point where we can A on the right interaction, without rewinding on the left rewind ; this is possible in two cases: (1) if rewinding on the right does not cause A to request any new to only request a messages on the left, or (2) if rewinding on the right causes A ∗ new special-sound proof—in this case R can perfectly emulate this new proof ˆ ˆ C, R 〉 . 〈 by simply requesting another design from safe-points —in each We show below that there exist certain points—called execution, from which it will be possible to perform extraction by simply rewind- ing until we obtain a second proof transcript, without rewinding on the left (and A requests a message on the left which would aborting all rewindings where require us to rewind also the left execution). (Actually, to simplify our analysis n this extraction procedure is cut-off if it runs “too long” (2 steps) in which case ∗ halts and outputs .) fail R ∗ R safe-points (which Below we provide a definition of . A formal description of safe-points ) is found in Figure 3. relies on the notion of ρ Intuitively, a safe point ∆ which has the is a prefix of some transcript ρ uses the same “scheduling” of A property that if during a rewinding from , ∆ messages as in , then the left execution can be perfectly emulated without rewinding (on the left). As we show later, if we rewind only from such points we ensure that the expected running time is polynomially bounded (even if A adaptively schedule the messages on the left). Definition 6. A prefix ρ of a transcript ∆ is called a safe-point for interaction th , β right interaction, such , γ ) in the k k α ( , if there exists an accepting proof r r r that: α β occurs in ρ , but not 1. γ (and ). r r r in the left interaction, if for any proof α , β 2. ) ( α occurs in ρ , then β , γ l l l l l occurs after γ . r 5 If safe-point , let ( α , β is a ρ , γ ) denote the canonical “safe” right proof. ρ ρ ρ Note that the only case a right-interaction proof does not have a safe-point is if it is “aligned” with a left execution proof (such that A can forward messages between the left and the right interactions); see Figure 4. In contrast, in all other safe-point . In Figure 5, we present the three cases, a right-interaction proof has a 5 We remark that our definition of safe-points is analogous to the “safe” rewinding points inside exposed triplets defined in DDN [6]. Loosely speaking, for every exposed triplet , there is a “safe” rewinding point that one can rewind to extract the committed value on the right without “affecting” the left interaction. Defining safe-point this way, avoids the complication of finding the “safe” rewinding point in each type of the exposed triplet .

14 characteristic types of . Note that in the first case (see Figure 5 (i)), safe-point ∗ R can emulate the left proof by requesting a new design ρ when rewinding from , ∗ ˆ ˆ R 〉 ; in the second case (Figure 5 (ii)), R 〈 can simply re-send the third C, from message of the left proof (since it is determined by the first two messages in the A proof); and in the last case (Figure 5 (ii)), no new message is requested by , so the left interaction can be “trivially” emulated (by doing nothing). α l ρ α r β r β l γ l γ r Prefix ρ that is not a safe point. Fig. 4. α α α l r l ρ ρ α α r r ρ β α l l β β r r β γ β r r l γ γ β l l l γ γ γ r r l (ii) (i) (iii) Fig. 5. safe-point s. Three characteristic ∗ ∗ R Running-time analysis of We show that R is expected PPT. Note that the . ∗ R n in the Main Execution Phase is poly ( n ) (where time spent by is the security parameter), since A is a strict polynomial time machine. We show below that ∗ R in the Rewinding Phase is poly ( n ). To bound the expected time spent by ∗ R does not check the the expected running time, we assume for simplicity that n fail conditions and may run for more than 2 steps (since this only increases the running time). ∗ R from all rewinds A Recall that in the Rewinding Phase, safe points . Let T ( i ) be the random variable that describes the time spent in rewinding a proof k in interaction k after i messages have been exchanged. We show that E [ T ≤ ( i )] k poly ( n ) and then by linearity of expectation, we conclude that the expected time

15 ∗ spent by in the Rewinding phase is R m m ∑ ∑ ∑ ∑ T , ( i )] ≤ [ E ) n ( poly poly ( n ) ≤ k i i =1 k =1 k is poly ( n ). where the total number of messages exchanged and m ρ [ Bounding ( i )] . Given a (partial) transcript of messages E , let Pr [ ρ ] denote T k the probability that ρ occurs as a prefix of the execution emulated in the Main p safe-point denote the probability that ρ is a Execution phase. Furthermore, let ρ and is rewound—i.e. p is the probability that, conditioned on the prefix ρ occur- ρ ring, the right interaction ρ is a safe-point for interaction k . k is convincing and ∗ rewinds until it finds another transcript for the proof ( α Recall that , β ) R , γ ρ ρ ρ associated ρ , cancelling each rewinding for which A requests the second message of with ρ . We claim that a proof in the left-interaction whose first message occurs in ρ − p since ρ is the probability of cancelling a rewinding from , is at most 1 ρ safe-point for every rewinding that is cancelled, and conditioned on ρ , the not a ρ probability of a view occurring in a rewinding from is same as occurring in the Main Execution phase (as the emulated receiver picks uniformly random messages in Stage 3 of the protocol). Thus, the expected number of rewindings 1 Therefore, the expected number of rewindings from ρ is at most is at most p ρ 1 = 1 and each rewinding takes at most poly ( n ) steps, i.e. · p ρ p ρ [ T i ( E ) | ρ ] ≤ poly ( n ) k Thus, ∑ ∑ ( poly ≤ ] ρ ) Pr [ n ρ E ( i ) | ρ ] Pr [ T ] ≤ poly ( n ) × [ E [ T ( i )] = k k of length ρ i ρ i of length ∗ R is correct. We proceed to show that the output dis- Output distribution of ∗ tribution of is correct. This follows from the following two claims: R ∗ Assume that R does not output fail , then except with negligible prob- Claim 2 ability, its output is identical to the values committed to by A in the right inter- actions combined with its view. ∗ R feeds A messages We first note that since in the Main Execution Phase, Proof. ∗ in the simulation by R is according to the correct distribution, the view of A A in a real interaction. We show in Lemma 3 that there identical to the view of is a safe point for every right interaction that has an identity different from the left interaction. Hence, for every convincing right interaction k > ` that has a ∗ R different identity, rewinds that interaction and eventually will either output ∗ fail R . Conditioned on or a witness is extracted from the rewinding phase of ∗ , by the statistical-binding property of not outputting fail R com , except with ∗ negligible probability the witnesses extracted by R are the values committed to by A .

16 Lemma 3 (Safe-point Lemma) In any one-many man-in-the-middle execu- right interactions, for any right interaction tion with k ∈ [ m ] , such that k m , it has a different identity from the identity of the left interaction, there exists a k for interaction . safe-point , where the identities Proof. Consider a one-many man-in-the-middle execution ∆ in the left and right interaction are different. Assume for contradiction, that there which does not have a safe-point , i.e. every prefix of k is some right interaction safe-point for interaction k ∆ is not a . α , β Consider any proof ( , γ be the prefix ) in the right interaction k . Let ρ r r r is sent immediately. By assumption, β ρ is not a safe-point . This after which r α , β , γ ) in the left interaction, such that α occurs means there exists a proof ( l l l l ρ before , occurs after ρ and before γ β , as depicted in Figure 4. That is, β l l r and β γ occurs in between ; we say a left proof is associated with a right proof r r in this case. Note that each left proof can be associated with at most one right to not have a safe-point proof. For the interaction k , the proofs in the left and i th proof in the left right interactions must match up each other one by one: the i th proof in the right. is associated with the Since the identities in the left and right interactions are different, there must be a position j th bit in the left be b and that in the j they differ at. Let the th b . Recall that, in the j round of Stage 3 of the protocol, the right be 1 − design left interaction has followed by design ; and the right interaction has − b 1 b design followed by design . Since all the proofs are “matched up”, it must be 1 − b b the case that there is a design on the left that is matched with a design on 1 0 l l l 2, be the two proofs = 1 i , ), , γ , β α the right, as depicted in Figure 6. Let ( i i i r r r , design = 1 . In 2, be the ones on the right in ), i , γ , β design α , and ( in 1 0 i i i l . ρ this case, consider β to be the prefix that includes all the message up until 1 r r r ); there is no proof on the left having its , γ , β Consider the second proof ( α 2 2 2 r at the same time. Hence, we ρ and its challenge before γ first message before 2 safe-point for that arrive at a contradiction to our assumption that there is no right interaction. l α 1 r α 2 r α 1 ρ r β 1 l β 1 l γ 1 r γ 1 l α 2 r β 2 l β 2 l γ 2 r γ 2 Fig. 6. A . design matches up with design 0 1

17 ∗ Claim 3 outputs fail with negligible probability. R ∗ R fail only in the following cases: Proof. outputs ∗ n steps: We know that the expected running time 2 R runs for more than ∗ poly ( n ). Using Markov inequality, we conclude that the probability R of is n ( poly ) ∗ n steps is at most R that runs more than 2 . n 2 safe-point : This case The same proof transcript is obtained from some ∗ picks some challenge β R occurs if in the Rewinding Phase that appeared ∗ n R runs for at most 2 steps, as a challenge in the Main Execution Phase. As n challenges. Furthermore, the length of each challenge is it picks at most 2 n 2 β is . By applying the union bound, we obtain that the probability that a n 2 picked twice is at most . Since there are at most polynomially many chal- 2 n 2 lenges picked in the Main Execution Phase, using the union bound again, we conclude that the probability that it outputs fail in this case is negligible. Suppose, the wit- The witness extracted is not a valid decommitment: ness extracted is not the decommitment information, then by the special- r such that f ( r ) = s . We sound property it follows that it must be a value show that if this happens with non-negligible probability, then we can invert ∗ . More precisely, given A, z and v, we construct A the one-way function f ∗ τ that inverts f on input y , picks ; uniformly at random from Γ ( A, z ) (by A ∗ A ( R emulating an execution of z ) internally) and proceeds identically as ′ ′ z . . . = z ‖ τ ‖⊥‖⊥‖ τ, z with the exception that it picks a with inputs where , and feeds k as the Stage 1 message in that random right interaction, say y v interaction. On the left interaction it honestly commits to the string using ′ ˆ ˆ R 〉 . Finally, if the value r C, output for interaction k is the inverse image of 〈 ′ ∗ ′ ), then f ( r w.r.t ) = y f A ( outputs r i.e. . (Notice that it is not necessary y ′ ∗ ′ according to the definition of to compute , since R z uses the values in z Z only in the output phase and not in its extraction procedure). Therefore, the ∗ ∗ inverts f is identical to the probability that R probability that inverts A which is non-negligible; this contradicts the one-wayness of . f f Since each of the above cases occur with negligible probability, using the ∗ union bound, we conclude that R fail with negligible probability. outputs 5 A log n -round Non-Malleable Commitment Scheme In this section, we show how to construct a O (log n )-round commitment scheme that is stand-alone non-malleable using any ( n )-round commitment scheme O that is one-many non-malleable. In particular, using the scheme 〈 C, R 〉 described in the previous section, we obtain a O (log n )-round commitment scheme that is stand-alone non-malleable. The idea for this construction is almost identical to )-round protocol constructed in [6], except that our construction is O (log n the more general, as it can be applied to any commitment scheme that satisfies our notion of one-many non-malleability; we here rely on the fact that our definition considers not only the values committed to by the adversary but also its view.

18 n ̃ ̃ Description of the Protocol R 〉 : To commit to value v ∈{ 0 , 1 } C, , choose ran- 〈 n l r is ∈ { 0 , 1 } id , such that v = r , . . . , r ⊕ . . . ⊕ r } . If dom shares ∈ { 0 , 1 l n 1 1 ̃ ̃ C, 〈 R 〉 interaction, then for each i , commit to r the identity of the (in parallel) i id . ), where id is the i th bit of C, R 〉 with identity ( i, id using 〈 i i In the full version of the paper, we show the following claim. ̃ ̃ 〈 C, R 〉 is stand-alone non-malleable. Claim 4 6 Acknowledgement We are very grateful to Danny Dolev for helpful conversations and for his con- tagious enthusiasm. We are also grateful to Cynthia Dwork and Moni Naor for helpful clarifications. References 1. B. Barak. How to go Beyond the Black-Box Simulation Barrier. In 42nd FOCS , pages 106–115, 2001. 2. B. Barak. Constant-Round Coin-Tossing or Realizing the Shared-Random String 43rd FOCS , pages 345-355, 2002. Model. In G. Brassard, D. Chaum and C. Cr ́epeau. Minimum Disclosure Proofs of Knowledge. 3. , Vol. 37, No. 2, pages 156–189, 1988. Preliminary version by Brassard and JCSS 27th FOCS Cr ́epeau in , 1986. 4. R. Cramer, I. Damg ̊ard and B. Schoenmakers. Proofs of Partial Knowledge and Crypto94 , Springer LNCS 839, Simplified Design of Witness Hiding Protocols. In pages. 174–187, 1994. 5. G. di Crescenzo, G. Persiano and I. Visconti. Constant-Round Resettable Zero Knowledge with Concurrent Soundness in the Bare Public-Key Model. In Crypto04 , Springer LNCS 3152, pages. 237–253, 2004. 6. D. Dolev, C. Dwork and M. Naor. Non-Malleable Cryptography. SIAM Journal on , Vol. 30(2), pages 391–437, 2000. Computing A. Feige and A. Shamir. How to Prove Yourself: Practical Solutions to Identification 7. Crypto86 , Springer LNCS 263, pages 181–187, 1987. and Signature Problems. In 8. Foundations of Cryptography – Basic Tools . Cambridge University O. Goldreich. Press, 2001. 9. S. Goldwasser, S. Micali and C. Rackoff. The Knowledge Complexity of Interactive Proof Systems. SIAM Jour. on Computing , Vol. 18(1), pp. 186–208, 1989. 10. R. Pass. Bounded-Concurrent Secure Multi-Party Computation with a Dishonest Majority. In 36th STOC , pages 232–241, 2004. 11. R. Pass and A. Rosen. Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds. In 44th FOCS , 2003. 12. R. Pass and A. Rosen. New and Improved Constructions of Non-Malleable Cryp- tographic Protocols. In 37th STOC , pages 533–542, 2005. 13. R. Pass, V. Vaikuntanathan. New-Age Cryptography. Manuscript .

FREQUENTLY ASKED QUE STIONS ABOUT FREE AN D MEALS REDUCED PRICE SCHOOL Dear Parent/Guardian: Children need healthy meals to learn offers h ealthy meals every school day. Breakfast Howland Local School...

More info »UM1850 User manual Description of STM32F1 HAL and Low - layer drivers Introduction TM is an STMicroelectronics original initiative to make developers' lives easier by reducing STMCube development effo...

More info »DoD Warrior Care Military Caregiver Support Caregiver Resource Directory 2 018

More info »The United States Postal Service An American History 1775 – 2006

More info »ORDER JO 7340.2H Air Traffic Organization Policy Effective Date: March 29, 2018 Contractions SUBJ: contractions used by ed word and phrase This handbook contains the approv personnel of the Federal Av...

More info »K2SN-MSS: An Efficient Post-Quantum Signature (Full Version) ∗ Reihaneh Safavi-Naini Sabyasachi Karati School of Computer Sciences Department of Computer Science National Institute of Science Educatio...

More info »Black-Box Non-Black-Box Zero Knowledge Vipul Goyal Alessandra Scafuro Rafail Ostrovsky UCLA Microsoft Research UCLA USA INDIA USA [email protected] [email protected] [email protected] Ivan Viscon...

More info »Journey to Success: Employment Tools for Veterans with Disabilities Social Security Administration | December 2018

More info »A publication of the National Wildfire agency Inter Coordinating Group Prescribed Fire Planning and Implementation Procedures Guide PMS 484 JULY 2017

More info »ANTI-GAY CURRICULUM LAWS ord Rosky Cli * ff marriage laws, Since the Sup reme Court’s invalidati on of anti-gay ates have been debating the LGBT movement ’s near- scholars and advoc ategies and priori...

More info »