What Information is Leaked under Concurrent Composition?: Abishek Jain

11:00 am on Wednesday, February 20, 2013
1:00 pm on Wednesday, February 20, 2013
MCS 137
Abstract: Achieving security under concurrent composition is notoriously hard. Indeed, in the plain model, far reaching impossibility results for concurrently secure computation are known. On the other hand, some positive results have also been obtained according to various weaker notions of security (such as by using a super-polynomial time simulator). This suggest that somehow, "not all is lost in the concurrent setting". Yet, our understanding of what exactly is it that goes wrong in the concurrent setting, and, to what extent is currently quite unsatisfactory. In this work, we ask what and exactly how much private information can the adversary learn by launching a concurrent attack? "Can he learn all the private inputs in all the sessions? Or, can we preserve the security of some (or even most) of the sessions fully while compromising (a small fraction of) other sessions? Or is it the case that the security of all (or most) sessions is (at least partially) compromised? If so, can we restrict him to learn an arbitrarily small fraction of input in each session?". We believe the above questions to be fundamental to the understanding of concurrent composition. Towards that end, we take a knowledge-complexity based approach (Goldreich-Petrank, STOC'91) to concurrently secure computation by allowing the ideal world adversary (a.k.a simulator) to query the trusted party for some leakage on the honest party inputs. We obtain both positive and negative results, depending upon the nature of the leakage queries available to the simulator. Informally speaking, our results imply the following: in the concurrent setting, "significant loss" of security (translating to high leakage in the ideal world) in some of the sessions is unavoidable. However on the brighter side, one can make the fraction of such sessions to be an arbitrarily small polynomial (while fully preserving the security in all other sessions). Our results also have an interesting implication on secure computation in the bounded concurrent setting: we show there exist protocols which are secure as per the standard ideal/real world notion in the bounded concurrent setting. However if the actual number of sessions happen to exceed the bound, there is "graceful degradation" of security (as the number of sessions increase). In order to obtain our positive result, we take a "cost-based" approach to rewinding in the current setting. In particular, we model concurrent rewinding as a set-covering problem and develop what we call "sparse rewinding strategies", which yield to other applications as well, including improved constructions of precise concurrent zero-knowledge. Joint work with Vipul Goyal and Divya Gupta.