Note: [**] Research partially supported by an individual NSERC research grant (Canada) of the author.
Abstract: It is customary to view the scheduler as an intruder when modelling security protocols by means of process calculi that express both nondeterministic and probabilistic behavior. It has been established that traditional schedulers need to be carefully calibrated in order to more accurately reflect an intruder's real power. We propose such a class of schedulers through a variant of the Probabilistic Poly-time Calculus (PPC) of Mitchell et al. (Theoretical Computer Science 353 (2006), 118–164) called PPCνσ. We define two levels of schedulers: adversarial schedulers which schedule a class of indistinguishable actions i.e. actions that we do not want an attacker to distinguish, and internal schedulers, called task schedulers, which resolve the remaining nondeterminism within a chosen class. We also show how to apply them in order to design schedulers for the analysis of cryptographic protocols that accurately reflect an intruder's capacity for controlling communication networks, without allowing it to control the internal reactions of the protocol under attack. We give a new characterization of the asymptotic observational equivalence of Mitchell et al. (Theoretical Computer Science 353 (2006), 118–164) that is more suited for taking into account any observable trace rather than just one single action. This asymptotic observational equivalence is a congruence in accordance with these new schedulers. We illustrate the aptness of our approach by an extensive study of the Dining Cryptographers (DCP) (J. Cryptology 1 (1988), 65–75) protocol.
Keywords: Process algebra, observational equivalence, probabilistic scheduling, analysis of cryptographic protocols
