Until recently, most research on the topic of secure computation focussed on the stand-alone model, where a single protocol execution takes place. In this paper we construct protocols for the setting of bounded-concurrent self-composition, where a (single) secure protocol is run many times concurrently, and there is a predetermined bound on the number of concurrent executions. In short, we show that any two-party functionality can be securely computed unde bounded-concurrent self-composition in the plain model (where the only setup assumption made is tha the aprties communicate via authenticated channels). Our protocol provides the first feasibility result for general two-party communication in the plain model for any model of concurrency. All previous protocols assumed a trusted setup phase in order to obtain a common reference string. On the downside, the number of rounds of communication in our protocol is super-linear in the bound on the number of concurrent executions. Subsequent to this work, constant-round protocol, and protocols for the multiparty case were presented by Pass and Rosen (FOCS 2003) and by Pass (STOC 2004). We remark that this paper contains the full version of the upper-bound portion of the extended abstract presented by the author on STOC 2003 [29] (the lower bound from [29] appears in [33], together with other lower bounds from [32])

We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states. We show that the optimal measurement for solving this problem is the so-called pretty good measurement. We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density nu=klog_2 N, where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group. In particular, for nu<1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N, while for nu>1 the optimal measurement identifies the hidden subgroup with a probability of order unity. Thus the dihedral group provides an example of a group G for which Omega(log|G|) hidden subgroup states are necessary to solve the hidden subgroup problem. We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold. Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems. In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.