Paper 2015/1107

Concurrent Secure Computation via Non-Black Box Simulation

Vipul Goyal, Divya Gupta, and Amit Sahai

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 can be achieved in the setting of concurrent secure computation using non-black box simulation 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: \begin{itemize} \item We give first positive results for concurrent blind signatures and verifiable random functions in the plain model \emph{as per the ideal/real world security definition}. Our positive result is somewhat surprising in light of the impossibility result of Lindell (STOC'03) for black-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. \item 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 world satisfies the \emph{bounded pseudo-entropy condition} (BPC) of Goyal (FOCS'12). The BPC 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". \item 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. \end{itemize} Our results are based on a non-black-box simulation technique using a new language (which allows the simulator to commit to an Oracle program that can access information with bounded 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.