This paper presents applicability of Strong Stationary Times (SST) techniques in the area of cryptography. The applicability is in three areas: (1) Propositions of a new class of cryptographic algorithms (pseudo-random permutation generators) which do not run for the predefined number of steps. Instead, these algorithms stop according to a stopping rule defined as SST, for which one can obtain provable properties: a) results are perfect samples from uniform distribution, b) immunity to timing attacks (no information about the resulting permutation leaks through the information about the number of steps SST algorithm performed). (2) We show how one can leverage properties of SST-based algorithms to construct an implementation (of a symmetric encryption scheme) which is immune to the timing-attack by reusing implementations which are not secure against timing-attacks. In symmetric key cryptography researchers mainly focus on constant time (re)implementations. Our approach goes in a different direction and explores ideas of input masking. (3) Analysis of idealized (mathematical) models of existing cryptographic schemes-i.e., we improve a result by Mironov [21].

We investigate a problem of maintaining a target population of mobile agents in a distributed system. The purpose of the agents is to perform certain activities, so the goal is to avoid overpopulation (leading to waste of resources) as well as underpopulation (resulting in a poor service). We assume that there must be no centralized control over the number of agents, since it might result in system's vulnerability. We analyze a simple protocol in which each node keeps at most one copy of an agent and if there is a single agent in a node, a new agent is born with a certain probability p. At each time step the agents migrate independently at random to chosen locations. We show that during a protocol execution the number of agents stabilizes around a level depending on p. We derive analytically simple formulas that determine probability p based on the target fraction of nodes holding an agent. The previous proposals of this type were based on experimental data only.

A cascade of mix servers is a crucial part of e-voting protocols and other schemes which aim for user's anonymity. We present kleptographic attacks on such cascades. In order to show interesting consequences, we focus on a cascade used as a building block of a Prêt à Voter e-voting protocol. However, the attacks might be generalized to any cascade of probabilistic mix servers.