Concurrent Secure Computation via Non-Black Box Simulation Vipul Goyal Divya Gupta Microsoft Research India University of California, Los Angeles [email protected] and Center for Encrypted Functionalities [email protected] Amit Sahai University of California, Los Angeles and Center for Encrypted Functionalities [email protected] November 13, 2015 Abstract Recently, Goyal (STOC’13) proposed a new non-black-box simulation techniques for fully concurrent zero knowledge with straight-line simulation. Unfortunately, so far this technique is limited to the setting of concurrent zero knowledge. The goal of this paper is to study what canbeachievedinthesettingofconcurrentsecurecomputationusingnon-black-boxsimulation techniques, building upon the work of Goyal. The main contribution of our work is a secure computation protocol in the fully concurrent setting with a straight-line simulator, that allows us to achieve several new results: • Wegivefirstpositiveresultsforconcurrentblindsignaturesandverifiablerandomfunctions in the plain model as per the ideal/real world security definition. Our positive result is somewhatsurprisinginlightoftheimpossibilityresultofLindell(STOC’03)forblack-box simulation. We circumvent this impossibility using non-black-box simulation. This gives us a quite natural example of a functionality in concurrent setting which is impossible to realize using black-box simulation but can be securely realized using non-black-box simulation. • Moreover, we expand the class of realizable functionalities in the concurrent setting. Our main theorem is a positive result for concurrent secure computation as long as the ideal worldsatisfiestheboundedpseudo-entropycondition (BPC)ofGoyal(FOCS’12). TheBPC requires that in the ideal world experiment, the total amount of information learnt by the adversary (via calls to the ideal functionality) should have “bounded pseudoentropy”. • We also improve the round complexity of protocols in the single-input setting of Goyal (FOCS’12) both qualitatively and quantitatively. In Goyal’s work, the number of rounds depended on the length of honest party inputs. In our protocol, the round complexity depends only on the security parameter, and is completely independent of the length of the honest party inputs. Our results are based on a non-black-box simulation technique using a new language (which allowsthesimulatortocommittoanOracleprogramthatcanaccessinformationwithbounded pseudoentropy), and a simulation-sound version of the concurrent zero-knowledge protocol of Goyal (STOC’13). We assume the existence of collision resistant hash functions and constant round semi-honest oblivious transfer. 1 Introduction Secure computation protocols enable a set of mutually distrustful parties to securely perform a task by interacting with each other. Traditional security notions for secure computation [Yao86, GMW87] were defined for the stand-alone setting where security holds only if a single protocol session is executed in isolation. In today’s connected world (and especially over internet), many instances of these protocols may be executing concurrently. In such a scenario, a protocol that is secure in the classical stand-alone setting may become completely insecure [Lin03b, BPS06]. Ambitious efforts have been made to generalize the results for the stand-alone setting, starting with concurrently-secure zero-knowledge protocols [DNS98, RK99, CKPR01, KP01, PRS02]. However, in the plain model, the effort to go beyond the zero-knowledge functionality were, un- fortunately, less than fully satisfactory. In fact, for the plain model far reaching unconditional im- possibility results were shown in a series of works [CKL03, Lin03b, Lin08, BPS06, Goy12, AGJ+12, GKOV12]. Two notable exceptions giving positive results in the plain model are the works on bounded concurrency [Lin03a, PR03, Pas04] (where there is an a-priori fixed bound on the total number of concurrent sessions in the system and the protocol in turn can depend on this bound), and, the positive results for a large class of functionalities in the so called “single input” setting [Goy12]. In this setting, there is a server interacting with multiple clients concurrently with the restriction that the server (if honest) is required to use the same input in all sessions. There is a large body of literature on getting concurrently secure computation in weaker models such as using a super-polynomial time simulator, or a trusted setup. A short survey of these works is given later in this section. We emphasize that in this work, we are interested in concurrently secure computation protocols with no trusted set up assumptions where the security holds according to standard ideal/real paradigm. Anintriguingfunctionalitythatcannotberealizedinthefullyconcurrentsettingbytheseresults is blind signatures in the plain model. The blind signature functionality, introduced by [Cha82], allowsuserstoobtainunforgeablesignaturesonmessagesoftheirchoicewithoutrevealingthe mes- sagebeingsignedtothesigner(blindnessproperty). Thequestionofwhetheraconcurrently-secure protocol for this functionality can be constructed as per the ideal/real model simulation paradigm has been open so far. Moreover, given the impossibility result for concurrent blind signatures for black box simulation by Lindell [Lin03b], it is clear that we need to use non-black box techniques. Until recently, no non-black box technique was known which applies to full concurrency with poly- nomial time simulation. However, Goyal [Goy13] recently proposed new non-black box simulation techniques for (fully) concurrent zero-knowledge with straight line simulation. Unfortunately, the result of Goyal is limited to the setting of concurrent zero-knowledge. We ask the question: Can we construct non-box black techniques for (fully) concurrent secure computation, building upon the work of Goyal [Goy13]? Our Contributions. The main contribution of our work is a secure computation protocol in the fully concurrent setting with a straight-line simulator, that allows us to achieve several new results. In short, we expand the class of realizable functionalities in the concurrent setting and give the first positive results for concurrent blind signatures and verifiable random functions in the plain model as per the ideal/real world security definition. Moreover, the round complexity of our protocol depends only on the security parameter and hence, improves the round complexity of [Goy12] both qualitatively and quantitatively. Finally, our work can be seen as a unifying framework, which essentially subsumes all the previous work on positive results for concurrent secure computation achieving polynomial time simulation based security in the plain model. For detailed description of our results, see Section 1.1. Other models. In order to circumvent the above mentioned impossibility results in the plain model, there has been quite some work studying various trust assumptions such as common ref- erence string (CRS) model and tamper proof hardware tokens [CLOS02, BCNP04, Kat07]. An- other interesting line of work has studied weaker security definitions [GM00, Pas03, PS04, MPR06] while still remaining in the plain model, and most notably obtains positive results in models like super polynomial time simulation [PS04, BS05, CLP10, GGJS12] and input indistinguishable se- curity [MPR06, GGJS12]. Notethatthesetrustassumptionsandtheserelaxednotionsofsecurityaresometimesrestrictive and are not applicable to many situations. We again emphasize that the focus of this work is concurrent secure computation in the plain model achieving polynomial time simulation. In the plain model, there are point to point authenticated channels between the parties, but there is no global trusted third party. What goes wrong in concurrent setting in plain model? A well established approach to constructing secure computation protocols is to use the GMW compiler: take a semi-honest secure computation protocol and “compile” it with zero-knowledge arguments. The natural starting point in the concurrent setting is to follow the same principles: somehow compile a semi-honest secure computationprotocolwithaconcurrent zero-knowledgeprotocol(actuallycompilewithconcurrent non-malleable zero-knowledge [BPS06]). Does such an approach (or minor variants) already give us protocols secure according to the standard ideal/real world definition in the plain model? There is a fundamental problem with this approach which poses a key bottleneck in a number of previous works (see [GS09, GJO10, GM11, GGJS12, Goy12, GGJ13]). All known concurrent zero-knowledgesimulatorsinthefullyconcurrentsettingworkbyrewindingtheadversarialparties. Such an approach is highly problematic for secure computation in the concurrent setting, where the adversary controls the scheduling of the messages of different sessions. For instance, consider the following scenario: Due to nesting of sessions by the adversary, a rewinding based simulator may need to execute some sessions more than once. Since the adversary can choose a different input in each execution (e.g. based on transcript so far), the simulator would have to query the ideal functionality for than once. However, for any session, the simulator is allowed at most one query! Indeed, such problems are rather inherent as indicated by various impossibility results [Lin08, BPS06]. Tryingtosolvethisbottleneckof“handlingextraqueries”invariouswayshasinspiredanumber of different works which revolve around a unified theme: first construct a protocol where the simulator requires multiple queries per session in the ideal world, and then, somehow manage to either eliminate or answer these extra queries by exploiting some property of the specific setting in question. Examples of these include Resettable and Stateless computation [GS09, GM11], Multiple Ideal Query model [GJO10, GJ13, GGJ13], Single-Input setting [Goy12], Leaky Ideal Query model [GGJ13], etc1. Indeed, as is natural to expect, there are limitations on how much one can achieve using the above paradigm of constructing protocols. A very natural question that arises is whether there 1For a detailed survey of these works, see Appendix G exists a different approach which allows us to construct concurrent secure computation protocols in the plain model without the need of additional output queries? Moreover, if such a different approach does exist, we know that due to impossibility results[CKL03, Lin03b, Lin08, BPS06, Goy12, AGJ+12, GKOV12], there will be some limitations on the scope of its applicability. This leads to some more natural questions. What all can we achieve using this approach? In particular, can we expand the class of realizable functionalities in the concurrent setting? Can we improve the parameters (e.g. round complexity) of the protocols which exist in the plain model? 1.1 Our Results The key contribution of this work is a new way of approaching the problem of concurrent secure computation in the plain model facilitated by recent advances in concurrent non-black box sim- ulation [Goy13]. We give a protocol with non-black box and straightline simulator. Since, very informally, our simulator does not rely on rewinding at all, we are able to avoid the key bottleneck of additional output queries to the ideal functionality during the rewinds. However,oursimulatorhastoovercomeanumberofadditionalobstaclesnotpresentin[Goy13]. Note that unlike secure computation, an adversary in concurrent zero-knowledge does not receive any outputs. Dealing with the outputs given to the adversary in each session is a key difficulty we have to overcome. In particular, one might think that a straightline simulator for concurrent zero- knowledge should give a concurrently secure computation protocol trivially for all functionalities and in particular for concurrently secure oblivious transfer. Note that this cannot be true given unconditionalimpossibilityresultsforoblivioustransfer. Formoreonsuchtechnicalhurdles, please refer to the technical overview (Section 1.2). Informally stated, our main theorem is a general positive result for concurrent secure compu- tation as long as the ideal world satisfies our so called bounded pseudo-entropy condition (BPC). Very informally, the bounded pseudoentropy condition requires that in the ideal world experiment, the total amount of information learnt by the adversary (via calls to the trusted party) should have “bounded pseudoentropy”. The origin of the bounded pseudoentropy condition comes from a conjecture of Goyal [Goy12]. More precisely, the bounded pseudoentropy condition says the following: Definition 1 (Bounded Pseudoentropy Condition (BPC)) An ideal world experiment sat- isfies bounded pseudoentropy condition if there exists B ∈ N and a PPT algorithm T such that for all m = m(n) concurrent sessions, for all adversarial input vectors I(cid:126) (where an element of the vector represents the input of the adversary in that session), there exists a set S of possible output vectors such that the following conditions are satisfied • All valid output vectors corresponding to the input vector I(cid:126) of the adversary are contained in S. Observe that for a given I(cid:126), for different honest party input vectors, the output vectors may be different. We require that any such output vector be contained in S. Furthermore, |S| ≤ 2B. • For every O(cid:126) ∈ S, T(I(cid:126),O(cid:126)) = 1, and for every O(cid:126) ∈/ S, T(I(cid:126),O(cid:126)) = 0. That is, the set S is efficiently recognizable. Intuitively, this condition says the following: The adversary might be scheduling an unbounded polynomialnumberofsessionsandgaininginformationfromeachoftheoutputsobtained. However for any vector of adversarial inputs, the number of possible output vectors is bounded (and hence so is the information that adversary learns). Further note that this condition places a restriction only on the ideal world experiment, which consists of the functionality being computed and the honest party inputs. There is no restriction on the ideal world adversary, which may follow any (possibly unbounded state) polynomial time strategy. Itcanbeseenthatinconcurrentzero-knowledge,aswellas,intheboundedconcurrencysetting, the BPC is satisfied. Also note that the class of ideal worlds which satisfy BPC is significantly more general compared to the single input setting of [Goy12]. For a formal proof of this claim, refer to Appendix C. In our work, we prove the following main theorem. Theorem 1 Assume the existence of collision resistant hash functions and constant-round semi- honest oblivious transfer. If the ideal world for the functionality F satisfies the bounded pseudoen- tropy condition in Definition 1, then for any constant (cid:15), there exists a O(n(cid:15)) round real world protocol Π which securely realizes the ideal world for functionality F. To understand the power of our result, a positive result for all ideal worlds satisfying BPC allows us to get the following “concrete” results: • Resolving the bounded pseudoentropy conjecture. Goyal [Goy12] considered the so called “single input setting” and obtained a positive result for many functionalities in the plain model. Goyal further left open the so called bounded pseudoentropy conjecture which if resolved would give a more general and cleaner result (see [Goy12] for the exact statement). Our BPC is inspired from this conjecture (and can be seen as one way of formalizing it). Thus, Theorem 1 allows us to resolve the bounded pseudoentropy conjecture in the positive. Our positive result for the BPC subsumes most known positive results for concurrent secure computation in the plain model such as for zero-knowledge [RK99, KP01, PRS02], bounded concurrent computation [Lin03a, PR03, Pas04], and the positive results in the single input setting [Goy12]. • Improving the round complexity of protocols in the single input setting. The round complexity of the construction of Goyal [Goy12] in the single input setting was a large polynomial depending not only upon the security parameter but also on the length of the input and the nature of the functionality. For example, for concurrent private information retrieval, the round complexity would depend multiplicatively of the number of bits in the database and the security parameter. Our construction only has n(cid:15) rounds, where n is the security parameter. Therefore, we obtain a significant qualitative improvement in the round complexity for protocols in the single input setting. • Expanding the class of realizable functionalities, and, getting blind signatures. Theblindsignaturefunctionalityisaninterestingcaseintheparadigmofsecurecomputation both from theoretical as well as practical standpoints. The question of whether concurrent blind signatures (secure as per the ideal/real model simulation paradigm) exist is currently unresolved. Lindell [Lin03a, Lin08] showed an impossibility result for concurrent blind signa- ture based on black-box simulation. This result has also been used as a motivation to resort to weaker security notions (such as game based security) or setup assumptions in various subsequent works (see e.g., [Fis06, Oka06, KZ06, HKKL07, GRS+11, GG14]). We show that a positive result for BPC directly implies a construction of concurrent blind signatures secure in the plain model as per the standard ideal/real world security notion. Prior to our work, the only known construction of concurrently secure blind signatures was according to the weaker game based security notion due to Hazay et al. [HKKL07]. This implies that concurrent blind signatures is a “natural” example of a functionality which isimpossibletorealizeusingblack-boxsimulationbutcanbesecurelyrealizedusingnon-black boxsimulationintheconcurrentsetting.2 Theonlyprevioussuchexampleknown[GM11]was for a reactive (and arguably rather contrived) functionality. Another concrete (and related) example of a new functionality that can be directly realized using our techniques is that of a secure verifiable random function. It would also be interesting to see what our approach yields in the plain model for different settings and security notions where the previous rewinding based approach has been useful (such as resettable computation, super-polynomial simulation, etc). We leave that as future work. 1.2 Our Techniques Our protocol and analysis for the concurrent secure computation is admittedly quite complex and we face a number of hurdles on the way. Below, we try to sketch the main difficulties and our ideas to circumvent them at a high level. To construct concurrent secure computation, we roughly follow the [GMW87] strategy of first constructing an appropriate zero-knowledge protocol, and then “somehow compiling” a semi honest secure computation protocol using that. In our concurrent setting, in order to avoid the multiple output queries per session, we need a concurrently secure protocol for zero-knowledge with a straightline simulator. Recently, the first such protocol was given by Goyal [Goy13] based on non-black box techniques3. Another property of the zero-knowledge protocol which is crucial for compilation is simulation- soundness. Our first (and arguably smaller) technical hurdle is to construct a simulation-sound version of Goyal’s protocol. This is necessary because the simulator would rely on the soundness of the proofs given by the adversary while simulating the proofs where it is acting as the prover. Another issue is that in our protocol for concurrent secure computation, the adversary is allowed to choose the statement proved till a very late stage in the protocol. Hence, we need simulation- soundness to hold even when the statements to prove are being chosen adaptively by the adversary. We note that this issue is somewhat subtle to deal with. Our construction of simulation-sound concurrent zero-knowledge relies on the following ingredients: Goyal’s concurrent simulation strat- egy, a robust non-malleable commitment scheme [LP09], and a special language to be used in the universal arguments. The final construction along with a description of the main ideas is given in Section 3. The next (and arguably bigger) difficulty is the following. In secure computation, the adversary receives an output in each session (this is unlike the case of zero-knowledge). It turns that that it is not clear how to handle these outputs while performing non-black box simulation. Note that 2Previous separations between the power of black-box and non-black box simulation are known only if we place additionalconstraintsonthedesignoftherealworldprotocol(e.g.,itshouldbepubliccoin,orconstantrounds,etc.) 3Before this, all the (fully) concurrent zero-knowledge protocols were based on rewinding techniques, while, the construction of [Bar01] (which had a non-rewinding simulator) worked only in the bounded concurrent setting. The main result in [Goy13] was the first public-coin concurrent zero-knowledge protocol where the non-rewinding nature of the simulation technique was not crucial. However in the current work, we would crucially exploit the fact that the simulation strategy was straightline. some such challenge is inherent in the light of the long list of general impossibility results known [Lin08, BPS06]. Before we describe the challenge faced in detail, it would be helpful to recall how the non-black box techniques based on [Bar01] work at a high level. • Non-black box technique. In each session, the simulator has to commit to a program Π, which has to generate the adversary’s random string r in that session. In the transcript between the commitment to Π and r, there may be messages of other sessions, which Π has to regenerate. Even if the program Π consists of the entire state of the simulator and the adversary at the point of the commitment, it runs into a problem in the case of secure computation (where the adversary is getting non-trivial output in each session). • Keychallenge. NotethattoreachfromthecommitmentofΠtothemessager,thesimulator makes use of some external information: namely the outputs it learns by querying the ideal functionality as it proceeds in the simulation. This information, however, is not available with the program Π (since the simulator may query the ideal functionality after the program Π was committed to). Also, note that the number of outputs learnt could be any unbounded polynomial. Hence, it is not clear how to regenerate the transcript. The first obvious solution, which does not work, is to allow the program Π to take inputs of unbounded length. This would allow the simulator to pass all the outputs obtained to the program Π. But now the soundness of the protocol seems to be completely compromised. On the other hand, if Π does not receive all the outputs, it cannot regenerate the transcript! To resolve this issue, we use the idea of “Oracle programs” due to Deng, Goyal, and Sahai [DGS09]. TheprogramΠ,whilerunning,isallowedtomakeany(polynomiallyunbounded)number ofqueries(tobeansweredbythesimulator)aslongasthetheresponsetoeachqueryisinformation theoretically fixed by the query. The soundness is still preserved: an adversarial prover still cannot communicate any information about the verifier’s random string r to Π. However, the program Π can still access a potentially unbounded length string using such an “Oracle interface”. Unfortunately, the above idea is still not sufficient for our purpose: the outputs given by the ideal functionality are not fixed given the adversary’s input in the session. Here we rely on the fact that we are only considering the ideal worlds which satisfy the bounded pseudoentropy condition. Very roughly, it is guaranteed that the entire output vector has only bounded pseudoentropy (B), given the input of the adversary. Moreover, given the adversary’s input vector, all possible output vectors are efficiently testable by the PPT algorithm T. In other words, for every vector of queries, there is only a bounded (although potentially exponential) number of response vectors accepted by T. We allow the program Π to make any number of queries such that the response vector is accepted by T. More details regarding our precise language for non-black box simulation may be found in Figure 1. This idea allows the simulator to supply the entire output vector (learnt from the ideal functionality) to Π while still preserving soundness. The soundness proof relies on the fact that the queries only allow for communication of up to B-bit string to Π, which is still not sufficient for communicating the string r. Finally, there are additional challenges due to the requirement of straightline extraction. To- wards that end, we rely on input indistinguishable computation introduced by Micali, Pass, and Rosen [MPR06]. Challenges also arise with performing hybrid arguments in the setting where the code of the simulator itself is committed (because of non-black box simulation). The full construc- tion along with the main ideas is given in Appendix 4. Other Related Work: Though Goyal et al. [Goy13] gave the first protocol for concurrent zero- knowledgewithastraightlinesimulator,recently,Chungetal. [CLP13b]gaveaconstant round con- currentzero-knowledgeprotocolforuniformadversariesbasedonanewassumptionofP-certificates, which is also straightline simulatable. Their protocol represents an exciting idea which opens an avenue for getting constant round concurrently secure computation protocols (albeit for uniform adversaries only, and, based on a new assumption). We believe that our techniques could also be applicableinconstructingconcurrentsecurecomputationprotocolsusingtheprotocolof[CLP13b]. 2 Concurrently Secure Computation: Our Model In this section, we begin by giving a brief sketch of our model. Formal description is given in Appendix B (building upon the model of [Lin08]). In this work, we consider a malicious, static and probabilistic polynomial time adversary that chooses whom to corrupt before the execution of the protocol and controls the scheduling of the concurrent executions. Additionally, the adversary can choose the inputs of different sessions adaptively. We denote the security parameter by n. We give a real world/ideal world based security definition. There are k parties Q ,Q ,...,Q , where each 1 2 k party may be involved in multiple sessions with possibly interchangeable roles. In the ideal world, there is a trusted party for computing the desired two-party functionality F : {0,1}r1 ×{0,1}r2 → {0,1}s1 × {0,1}s2. Let the total number of executions be m = m(n). Note that there is no a- priori bound on the number of sessions m and the adversary can start any (possibly unbounded) polynomial number of sessions. On the other hand, in the real world there is no trusted party and the two parties involved in a session, say P and P , execute a two party protocol Π for computing 1 2 F. Our security definition (see Definition 3, Appendix B) requires that any adversary in the real model can be emulated by an adversary in the ideal model. 2.1 Our Result and its Applications. As mentioned in the introduction, our main result (see Theorem 1, Section 1.1) is a general positive result for concurrent secure computation as long as the ideal world satisfies the bounded pseudo- entropy condition (Definition 1, Section 1.1). Next, we show that our theorem not only subsumes the positive results of [Goy12] in the single input setting but also improves the round complexity. Comparing our results with [Goy12]. In[Goy12], Goyalshowedthatiftheidealworldsatisfies the “key technical property” (KTP), then there exists a real world protocol which securely realizes this ideal world. The key technical property, taken verbatim from [Goy12], is as follows: Definition 2 (Key technical Property (definition 3, [Goy12])) The key technical property (KTP) of an ideal world experiment requires the existence of a PPT predictor P satisfying the following conditions. For all sufficiently large n, there exists a bound D such that for all adversaries and honest party inputs, (cid:12)(cid:110) (cid:111)(cid:12) (cid:12) j : P({I[(cid:96)]} ,{O[(cid:96)]} ) (cid:54)= O[j] (cid:12) < D (cid:12) (cid:96)≤j (cid:96)<j (cid:12) For the ideal worlds which satisfy KTP, [Goy12] gave a O(n3D2) round secure protocol which realizes the functionality, where D is the parameter in Definition 2. We show that if an ideal world experiment satisfies the key technical property, then it also satisfies the bounded pseudoentropy condition. Lemma 1 If an ideal world experiment satisfies the key technical property (Definition 2), then it also satisfies the bounded pseudoentropy condition (Definition 1). For the proof of this lemma refer to Appendix C. As mentioned before, the round complexity of Goyal [Goy12] is O(n3D2) which is a polynomial in security parameter n as well as D (which depends upon length of single input as well as nature of functionality). Our Theorem 1 and Lemma 1 imply a quantitative and qualitative improvement in round complexity. This leads to lower round protocols for applications like private database search, secure set intersection, computing kth ranked element etc. For details see Appendix D. Moreover, [Goy12] only gave a positive result for functionalities with hardness free ideal world, i.e. in the ideal world the trusted party is not required to perform any cryptographic operations. There is no such restriction in our setting. In fact, we show that blind signatures and verifiable random functions satisfy the bounded pseudoentropy condition. More interestingly, they do not satisfy the key technical property. We next describe our results for these functionalities. Blind Signatures. Blind signatures, introduced by [Cha82], allow users to obtain signatures on messages of their choice without revealing the message being signed to the signer (blindness property). In addition, they also need to satisfy the unforgeability property of the digital signature schemes. In this work, we give the following positive result for concurrent blind signatures. Theorem 2 Assume the existence of collision resistant hash functions and constant-round semi- honest oblivious transfer. Then for any constant (cid:15), there exists a O(n(cid:15)) round secure protocol which realizes the ideal world for concurrent blind signature functionality. We prove this theorem by using unique signatures [GO92] as the underlying signature scheme and showing that blind signatures satisfy the bounded pseudoentropy condition when the underlying signature scheme is unique. (Note that Lindell’s black box impossibility result also holds in this setting.) A signature scheme is said to be unique if for each public key and each message, there exists at most one valid signature which verifies. We can model blind signature as a two party computation between the signer and the user for the circuit for generating signatures. Note that the circuit will have the verification key vk hardcoded. At the end of the protocol, the user outputs a valid signature σ if obtained, and signer always outputs ⊥. Now we show that this functionality satisfies BPC for B = 0 and T algorithm which is same as the signature verification algorithm. Note that if the adversary is playing the role of the user, its output is unique and is completely determined by its input message since vk is fixed by the function being computed. If the adversary is playing the role of the signer, its output is always ⊥. Hence, set S will contain only one output vector, which is information theoretically fixed by the adversary inputs and the ideal world experiment (which fixes the verification keys for all the sessions). The algorithm T simply verifies the user’s signatures w.r.t. corresponding vk and ensures that signer’s outputs are ⊥. Finally note that blind signatures will not satisfy the key technical property. Consider the case when the adversary is acting as the user in all the sessions. By the unforgeability property of the scheme, any PPT predictor which receives k valid input/output (message/signature) pairs cannot predictthesignatureonthenextmessagewithnon-negligibleprobability. Also, notethatblindsig- natures will not satisfy the generalized key technical property discussed in the full version [Goy11] for the same reason. For more formal description see Appendix D.1. Verifiable Random Functions. Verifiable random functions (VRFs) were introduced by Micali, Rabin, and Vadhan [MRV99]. They combine the properties of pseudo-random functions with the verifiability property. Intuitively, they are pseudo-random functions with a public key and proofs for verification. Along with pseudo-randomness, they are required to satisfy uniqueness, i.e., given the public key, for any input x, there is a unique y which can verify. In this work, we show the following: Theorem 3 Assume the existence of collision resistant hash functions and constant-round semi- honest oblivious transfer. Then for any constant (cid:15), there exists a O(n(cid:15)) round concurrent real world protocol which realizes the ideal world experiment for verifiable random functions. We again prove this theorem by showing that VRFs satisfy BPC for B = 0 and T algorithm which is same as verification algorithm. Here, we again rely on the uniqueness property. Finally, notethatVRFstoowillnotsatisfythekeytechnicalpropertyduetopseudo-randomnessguarantee. For details see Appendix D.2. 3 Our Simulation-Sound Non-Black Box Zero-knowledge Protocol Constructing a family of polynomially many zero-knowledge protocols which are simulation-sound with respect to each other under (unbounded polynomially many) concurrent executions is one of the difficulties in constructing protocols for fully concurrent multi-party computation (MPC). Simulation-soundness, introduced by Sahai [Sah99], means that the soundness of each of the proofs givenbytheadversaryshouldholdevenwhentheadversaryisgettingunboundedpolynomialnum- ber of simulated proofs. To avoid the problem of providing multiple outputs due to a rewinding based simulator for concurrent MPC, we need to construct simulation-sound zero-knowledge proto- cols which are straight-line simulatable. Note that Pass [Pas04] also gave a construction of polyno- miallymanyprotocolswhichareconcurrentzero-knowledgeandsimulation-soundw.r.t. eachother in the restricted setting of bounded concurrency. In this work, we construct such simulation-sound zero-knowledge protocols building upon the non-black box public coin concurrent zero-knowledge protocol of Goyal [Goy13]. First,wegiveabriefoverviewof[Goy13]. Someofthetexthasbeentakenverbatimfrom[Goy13]. One of the main technical ideas in [Goy13] is to have N = n(cid:15) non-black box slots, for any constant (cid:15) (each consisting of a commitment to a machine and a verifier challenge string). Each slot is followed by a universal argument (UA) execution. Any of the UA’s in a session may be picked for simulation. If a UA is picked for simulation, to make the analysis go through, the simulator could choose of any of the previously completed slots and prefer the slots which are computationally lighter. In a UA execution, the prover proves that in one of the completed slots, the machine com- mitted successfully outputs the verifier challenge string. Other main idea was to have encrypted executions of the UAs (using its public coin property) to hide the location of the convincing UA executions in the transcript. Finally there is an execution of a witness-indistinguishable argument of knowledge (WIAOK), where the prover proves that either the statement x ∈ L or there exists a decryption of one of the UAs which is accepting. In the subsequent discussion, we will refer to the