Relativistic quantum cryptography

Relativistic quantum cryptography is a sub-field of quantum cryptography, in which in addition to exploiting the principles of quantum physics, the no-superluminal signalling principle of relativity theory stating that information cannot travel faster than light is exploited too. Technically speaking, relativistic quantum cryptography is a sub-field of relativistic cryptography, in which cryptographic protocols exploit the no-superluminal signalling principle, independently of whether quantum properties are used or not. However, in practice, the term relativistic quantum cryptography is used for relativistic cryptography too.

History

In 1997 and 1998, some important tasks in mistrustful cryptography were shown to be impossible to achieve with unconditional security. Mayers and Lo and Chau showed that unconditionally secure quantum bit commitment was impossible. Lo showed that oblivious transfer and a broad class of secure computations were also impossible to achieve with unconditional security in quantum cryptography. Moreover, Lo and Chau showed that unconditionally secure ideal quantum coin tossing was impossible too. In this context, Kent provided in 1999 the first relativistic cryptographic protocols, for bit commitment and ideal coin tossing, which overcome the assumptions made by Mayers, Lo and Chau, and achieve unconditional security. Since then, other unconditionally secure relativistic protocols for bit commitment have been found by Kent and others, and other cryptographic tasks have been investigated in the setting of relativistic quantum cryptography.

Basics

No-signalling and no-superluminal signalling

The no-signalling principle of quantum theory states that information cannot be communicated between two distinct locations L₀ and L₁ without the transmission of any physical systems, despite any quantum entanglement shared between L₀ and L₁. This implies, in particular, that without the transmission of any physical systems between L₀ and L₁, quantum correlation between L₀ and L₁ cannot be used to transmit information between L₀ and L₁, even if they are non-locally causal and violate Bell inequalities. According to relativity theory, physical systems cannot travel faster than the speed of light. Thus, it follows from the no-signalling principle that information cannot travel faster than the speed of light. This is called the no-superluminal signalling principle.

The principle of no-superluminal signalling is the key physical principle exploited in relativistic cryptography. It guarantees that the outcome x of a random variable X obtained at some spacetime point P cannot influence the probability that a random variable Y takes some value y at a spacelike separated spacetime point Q. Thus, for example, if two parties Alice and Bob have each two agents, with the first agent of Bob sending a secret message x to a first agent of Alice at the spacetime point P, and with the second agent of Alice sending a secret message y to the second agent of Bob at the spacetime point Q, with P and Q spacelike separated, then Bob can be guaranteed that the message y received from Alice was chosen independently of the message x that he gave Alice, and vice versa. This is a useful mathematical property that is exploited to prove the security of cryptographic protocols in relativistic cryptography.

The setting

It is a fundamental requirement in relativistic cryptography that the parties implementing the cryptographic task have a good description of spacetime, at least within the region of spacetime where the task is implemented. For example, in protocols implemented near the Earth surface, it can be assumed that spacetime is close to Minkowski. Importantly, this means that, near the Earth surface, physical systems and information cannot travel faster than the speed of light through vacuum, which is approximately 300,000 km/s. In principle, relativistic cryptography can be applied with more general spacetimes, as long as the parties can guarantee that there are no mechanisms allowing instant communication, like wormholes. Another requirement is that the parties have access to a common reference frame, so that they can guarantee that some communication events are spacelike separated.

In relativistic cryptography, it is assumed that each party participating in the cryptographic task has various trusted agents that collaborate to implement the task. The agents implement the protocol by performing different actions at various points in spacetime. The agents of the same party may communicate via authenticated and secure channels, which can be implemented with previously shared secure keys, for example using one-time pads.

Various tasks investigated by relativistic cryptography consist in tasks of mistrustful cryptography, in which two or more mistrustful parties must collaborate to implement a cryptographic task while at the same time being guaranteed that other parties do not cheat. Examples of tasks in mistrustful cryptography are bit commitment, coin tossing, oblivious transfer and secure computations. Key distribution does not belong to mistrustful cryptography, because in this case the parties distributing the key trust each other. In relativistic cryptography, each participating party has various trusted agents, who collaborate with each other by performing different actions at various spacetime points. For example, Alice and Bob can be two companies with offices and laboratories at various locations in the Earth. Alice's offices and laboratories work in collaboration and trust each other. Similarly, Bob's offices and laboratories work in collaboration and trust each other. But Alice and Bob do not trust each other.

Tasks investigated in relativistic cryptography

Bit commitment

Main article: Bit commitment

Bit commitment is an important cryptographic task that has been widely investigated in relativistic cryptography. In bit commitment, Alice commits to a bit b at some time t, and at some later time t’ > t Alice unveils her committed bit b to Bob. A bit commitment is said to be "hiding" if Bob cannot know b before Alice unveils. It is said to be "binding" if after the commitment time t, Alice cannot choose the value of b and successfully unveil b to Bob. A bit commitment protocol is "secure" if it is hiding and binding. The Mayers-Lo-Chau no go theorem states that unconditionally secure bit commitment is impossible based only on the laws of quantum physics. It was shown by Kent that the Mayers-Lo-Chau theorem is not general enough because it excludes protocols that exploit the principle of no-superluminal signalling. Kent provided the first unconditionally secure bit commitment protocol in the setting of relativistic cryptography. Various protocols for bit commitment have been devised by Kent and others. Experimental demonstrations of relativistic bit commitment have been implemented.

Coin tossing

In strong coin tossing, Alice and Bob are at different locations and they wish to toss a coin in such a way that Alice is guaranteed that Bob cannot bias the outcome, and Bob is guaranteed that Alice cannot bias the outcome either. It was shown by Lo and Chau that ideal strong coin tossing is impossible to achieve with unconditional security based only on the laws of quantum physics. However, Kent overcame this no-go theorem by providing a relativistic protocol for strong coin tossing that is unconditionally secure. This protocol is conceptually very simple and is illustrated here as an example of a protocol in relativistic cryptography.

In Kent's coin tossing protocol, Alice has two agents A₀ and A₁, and Bob has two agents B₀ and B₁. A_i and B_i are at location L_i, for $i\in \{0,1\}$. Let L₀ and L₁ have a distant separation D. Let us assume that spacetime is Minkowski. Thus, the minimum time that light takes to travel between L₀ and L₁ is t = D/c, where c is the speed of light through vacuum. A₀ generates a random bit $a$ in a secure laboratory and gives it to B₀ at a time t₀. B₁ generates a random bit b in a secure laboratory and gives it to A₁ at a time t₁. B₀ and B₁ communicate $a$ and b through a secure and authenticated channel. Similarly, A₀ and A₁ communicate $a$ and b through a secure and authenticated channel. Alice and Bob agree that the output of the toss d is the xor of the bits $a$ and b, $d=a\oplus b$. Alice and Bob agree on advance on the values of t₀ and t₁ in a common reference frame, in such a way that |t₀ - t₁| < t. Thus, from the principle of no superluminal signalling, at receiving $a$ from A₀, B₀ cannot send any signal that arrives to B₁ before B₁ gives b to A₁. Therefore, Alice is guaranteed that the bit b is chosen by Bob independently of the bit $a$ chosen by her. Since Alice chooses $a$ randomly, and since b is independent of $a$, Alice is guaranteed that the bit $d=a\oplus b$ is random. With similar arguments, Bob is also guaranteed that the bit d is random.

Variations of coin tossing have been investigated in relativistic cryptography by Colbeck and Kent.

Oblivious transfer and secure computations

Lo showed that oblivious transfer and other secure computations cannot be achieved with unconditional security based only on the laws of quantum physics. This impossibility result by Lo extends to the more general setting of relativistic quantum cryptography. Colbeck showed that various secure computations are impossible to achieve with unconditional security in relativistic quantum cryptography.

Position-based quantum cryptography

Position-based quantum cryptography consists in cryptographic tasks whose security exploit the location of a party, the principle of no-superluminal signalling and the laws of quantum physics. For example, in the problem of quantum location authentication, a prover wants to demonstrate his location L to a set of verifiers using quantum systems. A protocol for quantum location authentication works as follows. A set of verifiers at various locations that surround the location L send classical messages and quantum states towards the location L. If the prover is at the location L then he can receive the signals at specific times and reply to the verifiers with requested classical messages and/or quantum states, which must be received by the verifiers at specific times.

Quantum location authentication was first investigated by Kent in 2002, which he called ‘quantum tagging’, resulting in a filed US patent by Kent et al. in 2007, and a publication in the academic literature in 2010, after a paper on position-based quantum cryptography was published by Buhrman et al. There is a no-go theorem for quantum location authentication proved by Buhrman et al. stating that it is impossible for a set of verifiers to authenticate the location of a prover with unconditional security. This is because for any quantum location authentication protocol, a set of dishonest provers sharing a sufficient amount of entanglement and positioned between the verifiers and the location L can intercept all communications from the verifiers, including all transmitted quantum states, and then apply a non-local quantum operation which allows them to reply correctly and at the correct times to the verifiers. Since the dishonest provers do not need to be at the location L to do this, the quantum location authentication protocol is insecure. This no-go theorem assumes that the location L of the honest prover is his only credential. Kent showed that if the prover shares secret keys with the verifiers then location authentication can be implemented securely.