Relativistic protocols have been proposed to overcome impossibility results in classical and quantum cryptography. In such a setting, one takes the location of honest players into account, and uses the impossibility of superluminal signalling to limit the abilities of dishonest agents. Various relativistic bit commitment protocols have been proposed, and although bit commitment has been shown to be sufficient to construct oblivious transfer, composing specific relativistic protocols in this way is known to be insecure. A composable framework is required to perform such a modular security analysis, but no known frameworks can handle models of computation in Minkowski space. By instantiating the systems model from the Abstract Cryptography framework with Causal Boxes, we obtain such a composable framework, in which messages are assigned a location in Minkowski space (or superpositions thereof). This allows us to analyse relativistic protocols and to derive novel possibility and impossibility results. We show that (1) coin flipping can be constructed from the cryptographic primitive, channel with delay, (2) composably secure bit commitment, biased coin flipping and channel with delay are all impossible without set-up assumptions, and (3) it is impossible to securely increase the delay time of a channel with delay. Our impossibility results also hold in the computational and bounded storage settings and apply to protocols involving quantum messages sent/received at a superposition of space-time locations. This implies in particular, the non-composability of all proposed relativistic bit commitment protocols, of bit commitment in the bounded storage model, and of biased coin flipping, and opens the avenue for exploring further cryptographic implications of spatio-temporal quantum correlations.
Tue, 02.11.2021 14:00