What Information Is Leaked under Concurrent Composition?

A long series of works have established far reaching impossibility results for concurrently secure computation. 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.”

In this work, we ask what and exactly how much private information can an adversary learn by launching a concurrent attack? Inspired by the recent works on leakage-resilient protocols, we consider a security model where the ideal world adversary (a.k.a simulator) is allowed to query the trusted party for some “leakage” on the honest party inputs. (Intuitively, the amount of leakage required by the simulator upper bounds the security loss in the real world).

We show for the first time that in the concurrent setting, it is possible to achieve full security for “most” of the sessions, while incurring significant loss of security in the remaining (fixed polynomial fraction of total) sessions. We also give a lower bound showing that (for general functionalities) this is essentially optimal. Our results also have interesting implications to bounded concurrent secure computation [Barak- FOCS’01], as well as to precise concurrent zero-knowledge [Pandey et al.-Eurocrypt’08] and concurrently secure computation in the multiple ideal query model [Goyal et al.-Crypto’10]

At the heart of our positive results is a new simulation strategy that is inspired by the classical set covering problem. On the other hand, interestingly, our negative results use techniques from leakage-resilient cryptography [Dziembowski-Pietrzak-FOCS’08].