1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 Department of Computer Science, Science and Technology, Aarhus University3 ETH Zurich4 Department of Computer Science, Science and Technology, Aarhus University
The problem of asynchronous perfectly secure communication via one-time pads (OTP) has been recently introduced by Di Crescenzo and Kiayias. There, several players share the same OTP to be used in parallel but it is not known in advance which players will consume how many bits of the pad. Based on the common OTP and only partial local knowledge of how many key bits have already been used by each other player, the goal is to commonly consume as many key bits as possible without any overlap. In this paper, we consider a related problem with immediate implications to the previous model. We consider n players to share the same k keys of length ` bits. The goal is to assign a key sequence to each player such that, for as many keys as possible and independently of which player uses how many of them, it is guaranteed that all used keys are independent. Such an assignment is called loss-free if k keys can always be consumed independently. Note that, in contrast to the previous model, the players are ignorant of each other’s key consumptions. We first observe a simple loss-free solution for the case that the key is of certain (small) minimal length `. Furthermore, for the case of key length ` = 1 (the most general case), we show that loss-free assignments are possible if and only if the number of players is at most three. Our solutions directly apply to the model of Di Crescenzo and Kiayias. For the case n = 3, we strictly improve over their solution. For n > 3, we still partially improve over their solution despite the fact that our construction is simple and oblivious.
Main Research Area:
45th Annual Allerton Conference on Communication, Control, and Computing, 2007