Following Dwork, Naor, and Sahai (30th STOC, 1998),
we consider concurrent execution of protocols in a
semi-synchronized network. Specifically, we assume that each party
holds a local clock such that a constant bound on the relative rates
of these clocks is a-priori known, and consider protocols that
employ ... more >>>

The notion of efficient computation is usually identified in cryptography and complexity with probabilistic polynomial time. However, until recently, in order to obtain \emph{constant-round} zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledge-extractors to run in time which is only polynomial {\em on the average} (i.e., ... more >>>

This paper concerns the possibility of developing a coherent
theory of security when feasibility is associated
with expected probabilistic polynomial-time (expected PPT).
The source of difficulty is that
the known definitions of expected PPT strategies
(i.e., expected PPT interactive machines)
do not support natural results of the ... more >>>