This paper considers game-theoretic security of bit commitment protocols under a realistic cost model. Higo et. al (IWSEC 2013) proved equivalence of game-theoretic security and cryptographic security of bit commitment protocols under an ideal cost model. Their model assumes that there is no cost for communication and computation. Under a realistic model that cost for communication and computation is non-negligible, this paper shows that conventional bit commitment protocols are not game-theoretically secure, and abort detection property is necessary for bit commitment protocols to achieve game-theoretic security.

This paper proposes a return route information encryption scheme for onion-based e-mail systems and mix-nets. Our scheme has the following two properties. (1) It allows any node on the message route to send reply messages to the sender of the message. This property is necessary for sending error replies. (2) It allows the replying node to send multiple reply messages from one piece of return route information. This property is necessary when responding with large amounts of data using multiple messages. In order to construct a return route information scheme, we must consider a new type of attack, namely the replace attack. A malicious node obtains information about the route by replacing secret information that only the node can read. This paper describes the new type of attack and shows that previous schemes are vulnerable to it. Our scheme prevents replace attacks. In addition, we show that by slightly modifying our scheme malicious nodes cannot distinguish whether a message is a forward message or a reply message, thus improving the security of the routing scheme.

A distributed coordinated checkpointing algorithm for distributed mobile systems is presented. A consistent global checkpoint is a set of states in which no message is recorded as received in one process and as not yet sent in another process. It is used for rollback when process failure occurs. A consistent global checkpoint must be obtained for any checkpoint initiation by any process. This paper shows a checkpoint algorithm in which the amount of information piggybacked on program messages does not depend on the number of mobile processes. The number of checkpoints is minimized under two assumptions: (1) one consistent global checkpoint is taken for concurrent checkpoint initiations and (2) a checkpoint is initiated at each handoff by mobile processes. This algorithm is thus optimal among the generalizations of Chandy and Lamport's distributed snapshot algorithm under the latter assumption.

h-out of-k mutual exclusion is a generalization of 1-mutual exclusion problem, where there are k limits of shared resources and each process requests h(1/spl les/h/spl les/k) units at the same time. Though the k-arbiter has been shown to be a quorum-based solution to this problem, quorums in the k-arbiter are much larger than these in the 1-coterie for 1-mutual exclusion. Thus, the algorithm based on the k-arbiter needs many messages. This paper defines two (h, k)-arbiters for h-out of-k mutual exclusion: a uniform (h, k)-arbiter and a (k+1)-cube (h, k)-arbiter. The quorums in each (h, k)-arbiter are not larger than the ones in the corresponding k-arbiter; consequently using the (h, k)-arbiters is more efficient than using the k-arbiters. Uniform (h, k)-arbiter is an optimal generalization of the majority coterie for 1-mutual exclusion. (k+1)-cube (h, k)-arbiter is a quasi-optimal generalization of square grid coterie for 1-mutual exclusion.

In recent autonomous decentralized systems, every node might not execute the same algorithm because it might have its own local policy and follow that policy rather than the common principle. We model these systems as a multi-policy distributed system. We introduce a new type of failure, a truant failure, on multi-policy distributed systems, which is considered to be the simplest local policy. A truant failure node does nothing for the other nodes' requests selected by its local policy. The paper shows a condition to be able to defect a truant failure and presents a distributed truant failure detection algorithm for that case.>