Classically impossible cryptography

Daniel J. Rogers

Lorenzo Laneve, Lídia del Rio

We study the cryptographic primitive Oblivious Transfer; a composable construction of this resource would allow arbitrary multi-party computation to be carried out in a secure way, i.e. to compute functions in a distributed way while keeping inputs from different parties private. First we review a framework that allows us to analyze composability of classical and quantum cryptographic protocols in special relativity: Abstract Cryptography implemented with Causal Boxes. We then (1) explore and formalize different versions of oblivious transfer found in the literature, (2) prove that their equivalence holds also in relativistic quantum settings, (3) show that it is impossible to composably construct any of these versions of oblivious transfer from only classical or quantum communication among distrusting agents in relativistic settings, (4) prove that the impossibility also extends to multi-party computation, and (5) provide a mutual construction between oblivious transfer and bit commitment.

Mariana Costiuc, Diana Maimuţ, George Teşeleanu

Huiqin Xie, Li Yang

Traditional cryptography is facing great challenges with the development of quantum computing. Not only public-key cryptography, the applications of quantum algorithms to symmetric cryptanalysis has also drawn more and more attention. In this paper, we apply quantum algorithms to the miss-in-the-middle technique and propose a quantum algorithm for finding impossible differentials of general block ciphers. We prove that, as long as the attacked block cipher satisfies certain algebraic conditions, the outputs of the quantum algorithm will be impossible differentials of it except for a negligible probability. The proposed quantum algorithm has polynomial quantum complexity and does not require any quantum or classical query to the encryption oracle of the block cipher. Compared with traditional miss-in-the-middle technique, which is difficult to find impossible differentials as the number of rounds increases, the quantum version of miss-in-the-middle technique proposed in this paper is more conducive to find impossible differentials when the block cipher has a large number of rounds.

Elette Boyle, Mohammad Mahmoody

V. Vilasini, Christopher Portmann, Lídia del Rio

Abstract Relativistic protocols have been proposed to overcome certain impossibility results in classical and quantum cryptography. In such a setting, one takes the location of honest players into account, and uses the signalling limit given by the speed of light to constraint the abilities of dishonest agents. However, composing such protocols with each other to construct new cryptographic resources is known to be insecure in some cases. To make general statements about such constructions, a composable framework for modelling cryptographic security in Minkowski space is required. Here, we introduce a framework for performing such a modular security analysis of classical and quantum cryptographic schemes in Minkowski space. As an application, we show that (1) fair and unbiased coin flipping can be constructed from a simple resource called channel with delay; (2) biased coin flipping, bit commitment and channel with delay through any classical, quantum or post-quantum relativistic protocols are all impossible without further setup assumptions; (3) it is impossible to securely increase the delay of a channel, given several short-delay channels as ingredients. Results (1) and (3) imply in particular the non-composability of existing relativistic bit commitment and coin flipping protocols.