Lower bounds and impossibility results for concurrent self composition (Q2425531)

Concurrent self composition is the execution of a communication protocol many times concurrently. In the unbounded case, the protocol is executed a polynomial number of times, in \(m\) -bounded concurrency the number of executions is fixed. Here it is shown that there exist large classes of two-party functionalities that cannot be securely computed under unbounded concurrent self composition by any protocol and there exists a large class of two-party functionalities with the property that any protocol that securely computes a functionality from this class under \(m\) -bounded concurrent self composition must have bandwith (number of bits sent by the parties during the execution) of at least \(m\).