^{1} Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University^{2} Department of Computer Science, Science and Technology, Aarhus University^{3} ETH Zurich^{4} Department of Computer Science, Science and Technology, Aarhus University

Abstract:

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.

Type:

Conference paper

Language:

English

Main Research Area:

Science/technology

Review type:

Undetermined

Conference:

45th Annual Allerton Conference on Communication, Control, and Computing, 2007