Relativistic quantum cryptography is a sub-field of

quantum cryptography Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution, which offers an information-theoretically secure soluti ...

, in which in addition to exploiting the principles of

quantum physics Quantum mechanics is the fundamental physical Scientific theory, theory that describes the behavior of matter and of light; its unusual characteristics typically occur at and below the scale of atoms. Reprinted, Addison-Wesley, 1989, It is ...

, the no-superluminal signalling principle of

relativity theory The theory of relativity usually encompasses two interrelated physics theories by Albert Einstein: special relativity and general relativity, proposed and published in 1905 and 1915, respectively. Special relativity applies to all physical phe ...

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 Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adversarial behavior. More gen ...

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 Quantum entanglement is the phenomenon where the quantum state of each Subatomic particle, particle in a group cannot be described independently of the state of the others, even when the particles are separated by a large distance. The topic o ...

shared between ''L₀'' and ''L₁''. This implies, in particular, that without the transmission of any physical systems between ''L₀'' and ''L₁'',

quantum correlation In quantum mechanics, quantum correlation is the expected value of the product of the alternative outcomes. In other words, it is the expected change in physical characteristics as one quantum system passes through an interaction site. In John Bel ...

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 Bell's theorem is a term encompassing a number of closely related results in physics, all of which determine that quantum mechanics is incompatible with local hidden-variable theories, given some basic assumptions about the nature of measuremen ...

. According to

, physical systems cannot travel faster than the

speed of light The speed of light in vacuum, commonly denoted , is a universal physical constant exactly equal to ). It is exact because, by international agreement, a metre is defined as the length of the path travelled by light in vacuum during a time i ...

. Thus, it follows from the no-signalling principle that information cannot travel faster than the

. 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 In physics, spacetime, also called the space-time continuum, is a mathematical model that fuses the three dimensions of space and the one dimension of time into a single four-dimensional continuum. Spacetime diagrams are useful in visualiz ...

, 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 Minkowski, Mińkowski or Minkovski (Slavic feminine: Minkowska, Mińkowska or Minkovskaya; plural: Minkowscy, Mińkowscy; , ) is a surname of Polish origin. It may refer to: * Minkowski or Mińkowski, a coat of arms of Polish nobility *Alyona Mink ...

. Importantly, this means that, near the Earth surface, physical systems and information cannot travel faster than the speed of light through

vacuum A vacuum (: vacuums or vacua) is space devoid of matter. The word is derived from the Latin adjective (neuter ) meaning "vacant" or "void". An approximation to such vacuum is a region with a gaseous pressure much less than atmospheric pressur ...

, which is approximately 300,000 km/s. In principle, relativistic cryptography can be applied with more general

spacetimes In physics, spacetime, also called the space-time continuum, is a mathematical model that fuses the three-dimensional space, three dimensions of space and the one dimension of time into a single four-dimensional continuum (measurement), continu ...

, as long as the parties can guarantee that there are no mechanisms allowing instant communication, like

wormholes A wormhole is a hypothetical structure that connects disparate points in spacetime. It can be visualized as a tunnel with two ends at separate points in spacetime (i.e., different locations, different points in time, or both). Wormholes are base ...

. Another requirement is that the parties have access to a common

reference frame In physics and astronomy, a frame of reference (or reference frame) is an abstract coordinate system, whose origin, orientation, and scale have been specified in physical space. It is based on a set of reference points, defined as geometric ...

, 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

. The agents of the same party may communicate via authenticated and

secure channel In cryptography, a secure channel is a means of data transmission that is resistant to overhearing and tampering. A confidential channel is a means of data transmission that is resistant to overhearing, or eavesdropping (e.g., reading the conten ...

s, which can be implemented with previously shared secure

keys Key, Keys, The Key or The Keys may refer to: Common uses * Key (cryptography), a piece of information needed to encode or decode a message * Key (instrument), a component of a musical instrument * Key (lock), a device used to operate a lock * ...

, 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 Coin flipping, coin tossing, or heads or tails is using the thumb to make a coin go up while spinning in the air and checking obverse and reverse, which side is showing when it is down onto a surface, in order to randomly choose between two alter ...

oblivious transfer In cryptography, an oblivious transfer (OT) protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece (if any) has been transferred. The first fo ...

and secure computations.

Key distribution In symmetric key cryptography, both parties must possess a secret key which they must exchange prior to using any encryption. Distribution of secret keys has been problematic until recently, because it involved face-to-face meeting, use of a trust ...

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

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 In theoretical physics, a no-go theorem is a theorem that states that a particular situation is not physically possible. This type of theorem imposes boundaries on certain mathematical or physical possibilities via a proof by contradiction. Insta ...

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\

. 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 Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or logical inequality is a logical operator whose negation is the logical biconditional. With two inputs, XOR is true if and only if the inputs differ (one ...

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

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 In quantum mechanics, a quantum operation (also known as quantum dynamical map or quantum process) is a mathematical formalism used to describe a broad class of transformations that a quantum mechanical system can undergo. This was first discusse ...

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.

References

{{reflist, 30em, refs= {{cite journal , doi = 10.1103/PhysRevLett.78.3414 , last = Mayers , first = Dominic , date = 1997 , title = Unconditionally Secure Quantum Bit Commitment is Impossible , journal = Physical Review Letters , volume = 78 , issue = 17 , pages = 3414–3417 , bibcode=1997PhRvL..78.3414M , arxiv = quant-ph/9605044 , citeseerx = 10.1.1.251.5550 , s2cid = 14522232 {{cite journal , doi = 10.1103/PhysRevLett.78.3410 , last1 = Lo , first1 = Hoi-Kwong , last2 = Chau , first2 = H. F. , date = 1997 , title = Is Quantum Bit Commitment Really Possible? , journal = Physical Review Letters , volume = 78 , issue = 17 , pages = 3410–3413 , arxiv = quant-ph/9603004, bibcode = 1997PhRvL..78.3410L , s2cid = 3264257 {{cite journal , doi = 10.1103/PhysRevA.56.1154 , last = Lo , first = Hoi-Kwong , date = 1997 , title = Insecurity of quantum secure computations , journal = Physical Review A , volume = 56 , issue = 2 , pages = 1154–1162 , arxiv = quant-ph/9611031, bibcode = 1997PhRvA..56.1154L , s2cid = 17813922 {{cite journal , doi = 10.1016/S0167-2789(98)00053-0 , last1 = Lo , first1 = Hoi-Kwong , last2 = Chau , first2 = H. F. , date = 1998 , title = Why quantum bit commitment and ideal quantum coin tossing are impossible , journal = Physica D: Nonlinear Phenomena , volume = 120 , issue = 1–2 , pages = 177–187 , arxiv = quant-ph/9711065, bibcode = 1998PhyD..120..177L , s2cid = 14378275 {{cite journal , doi = 10.1103/PhysRevLett.83.1447 , last = Kent , first = Adrian , date = 1999 , title = Unconditionally Secure Bit Commitment , journal = Physical Review Letters , volume = 83 , issue = 7 , pages = 1447–1450 , arxiv = quant-ph/9810068, bibcode = 1999PhRvL..83.1447K , s2cid = 8823466 {{cite journal , doi = 10.1103/PhysRevLett.83.5382 , last = Kent , first = Adrian , date = 1999 , title = Coin Tossing is Strictly Weaker than Bit Commitment , journal = Physical Review Letters , volume = 83 , issue = 25 , pages = 5382–5384 , arxiv = quant-ph/9810067, bibcode = 1999PhRvL..83.5382K , s2cid = 16764407 {{cite journal , doi = 10.1007/s00145-005-0905-8 , last = Kent , first = Adrian , date = 2005 , title = Secure Classical Bit Commitment Using Fixed Capacity Communication Channels , journal = Journal of Cryptology , volume = 18 , issue = 4 , pages = 313–335 , arxiv = quant-ph/9906103, s2cid = 9732039 {{cite journal , doi = 10.1088/1367-2630/13/11/113015 , last = Kent , first = Adrian , date = 2011 , title = Unconditionally secure bit commitment with flying qudits , journal = New Journal of Physics , volume = 13 , issue = 11 , pages = 113015 , arxiv = 1101.4620, bibcode = 2011NJPh...13k3015K , s2cid = 12472004 {{cite journal , doi = 10.1103/PhysRevLett.109.130501 , last = Kent , first = Adrian , date = 2012 , title = Unconditionally Secure Bit Commitment by Transmitting Measurement Outcomes , journal = Physical Review Letters , volume = 109 , issue = 13 , pages = 130501 , pmid = 23030073 , arxiv = 1108.2879, bibcode = 2012PhRvL.109m0501K , s2cid = 15681144 {{cite journal , doi = 10.1103/PhysRevA.92.022315 , last1 = Adlam , first1 = Emily , last2 = Kent , first2 = Adrian , date = 2015 , title = Device-independent relativistic quantum bit commitment , journal = Physical Review A , volume = 92 , issue = 2 , pages = 022315 , arxiv = 1504.00944, bibcode = 2015PhRvA..92b2315A , s2cid = 16654172 {{cite journal , doi = 10.1103/PhysRevLett.115.030502 , last1 = Lunghi , first1 = T. , last2 = Kaniewski , first2 = J. , last3 = Bussières , first3 = F. , last4 = Houlmann , first4 = R. , last5 = Tomamichel , first5 = M. , last6 = Wehner , first6 = S. , last7 = Zbinden , first7 = H. , year = 2016 , title = Practical Relativistic Bit Commitment , journal = Physical Review Letters , volume = 115 , issue = 3 , pages = 030502 , pmid = 26230775 , arxiv = 1608.03398, s2cid = 20797497 {{Cite journal , arxiv = 1008.2147, last1 = Kent, first1 = A., title = Quantum Tagging: Authenticating location via quantum information and relativistic signalling constraints, journal = Physical Review A, volume = 84, issue = 1, pages = 012326, last2 = Munro, first2 = William J., last3 = Spiller, first3 = Timothy P., year = 2011, doi = 10.1103/PhysRevA.84.012326, bibcode = 2011PhRvA..84a2326K, s2cid = 1042757 {{cite patent , country=US , number=7075438, inventor1-first = A., inventor1-last = Kent, inventor2-first = W., inventor2-last = Munro, inventor3-first = T., inventor3-last = Spiller , inventor4-first = R., inventor4-last = Beausoleil, pubdate=2006-07-11, title=Tagging systems {{Cite journal , arxiv = 1009.2490, last1 = Buhrman, first1 = Harry, title = Position-Based Quantum Cryptography: Impossibility and Constructions, journal = SIAM Journal on Computing, volume = 43, issue = 1, pages = 150–178, last2 = Chandran, first2 = Nishanth, last3 = Fehr, first3 = Serge, last4 = Gelles, first4 = Ran, last5 = Goyal, first5 = Vipul, last6 = Ostrovsky, first6 = Rafail, last7 = Schaffner, first7 = Christian, year = 2014, doi = 10.1137/130913687, s2cid = 220613220 {{ Cite thesis , last=Colbeck , first=Roger , title=Quantum And Relativistic Protocols For Secure Multi-Party Computation , arxiv=0911.3814, date=December 2006 , publisher=University of Cambridge {{cite journal , doi = 10.1088/0264-9381/29/22/224013 , last = Kent , first = Adrian , date = 2012 , title = Quantum tasks in Minkowski space , journal = Classical and Quantum Gravity , volume = 29 , issue = 22 , pages = 224013 , arxiv = 1204.4022, bibcode = 2012CQGra..29v4013K , s2cid = 55127845 {{cite journal , doi = 10.1103/PhysRevLett.111.180504 , last1 = Lunghi , first1 = T. , last2 = Kaniewski , first2 = J. , last3 = Bussières , first3 = J. , last4 = Houlmann , first4 = R. , last5 = Tomamichel , first5 = M. , last6 = Kent , first6 = A. , last7 = Gisin , first7 = N. , last8 = Wehner , first8 = S. , last9 = Zbinden , first9 = H. , date = 2013 , title = Experimental Bit Commitment Based on Quantum Communication and Special Relativity , journal = Physical Review Letters , volume = 111 , issue = 18 , pages = 180504 , pmid = 24237497 , arxiv = 1306.4801, bibcode = 2013PhRvL.111r0504L , s2cid = 15916727 {{cite journal , doi = 10.1103/PhysRevLett.112.010504 , last1 = Liu , first1 = Yang , last2 = Cao , first2 = Yuan , last3 = Curty , first3 = Marcos , last4 = Liao , first4 = Sheng-Kai , last5 = Wang , first5 = Jian , last6 = Cui , first6 = Ke , last7 = Li , first7 = Yu-Huai , last8 = Lin , first8 = Ze-Hong , last9 = Sun , first9 = Qi-Chao , last10 = Li , first10 = Dong-Dong , last11 = Zhang , first11 = Hong-Fei , last12 = Zhao , first12 = Yong , last13 = Chen , first13 = Teng-Yun , last14 = Peng , first14 = Cheng-Zhi , last15 = Zhang , first15 = Qiang , last16 = Cabello , first16 = Adán , last17 = Pan , first17 = Jian-Wei , date = 2014 , title = Experimental Unconditionally Secure Bit Commitment , journal = Physical Review Letters , volume = 112 , issue = 1 , pages = 010504 , pmid = 24483878 , arxiv = 1306.4413, bibcode = 2014PhRvL.112a0504L , s2cid = 31546945 {{cite journal , doi = 10.1103/PhysRevLett.117.140506 , last1 = Verbanis , first1 = Ephanielle , last2 = Martin , first2 = Anthony , last3 = Houlmann , first3 = Raphaël , last4 = Boso , first4 = Gianluca , last5 = Bussières , first5 = Félix , last6 = Zbinden , first6 = Hugo , date = 2016 , title = 24-Hour Relativistic Bit Commitment , journal = Physical Review Letters , volume = 117 , issue = 14 , pages = 140506 , pmid = 27740788 , arxiv = 1605.07442, bibcode = 2016PhRvL.117n0506V , s2cid = 1992228 {{cite journal , doi = 10.1103/PhysRevA.73.032320 , last1 = Colbeck , first1 = Roger , last2 = Kent , first2 = Adrian , title = Variable-bias coin tossing , journal = Physical Review A , date = 2006 , volume = 73 , issue = 3 , pages = 032320 , arxiv = quant-ph/0508149, bibcode = 2006PhRvA..73c2320C , s2cid = 10583364 {{cite journal , doi = 10.1103/PhysRevA.76.062308 , last = Colbeck , first = Roger , title = Impossibility of secure two-party classical computation , journal = Physical Review A , date = 2007 , volume = 76 , issue = 6 , pages = 062308 , arxiv = 0708.2843, bibcode = 2007PhRvA..76f2308C , s2cid = 18745956 {{cite journal , doi = 10.1103/PhysRevA.84.022335 , last = Kent , first = Adrian , title = Quantum tagging for tags containing secret classical data , journal = Physical Review A , volume = 84 , date = 2011 , issue = 2 , pages = 022335 , arxiv = 1008.5380, bibcode = 2011PhRvA..84b2335K , s2cid = 17776740 {{cite journal , doi = 10.1103/PhysRevA.84.012328 , last = Kent , first = Adrian , title = Location-oblivious data transfer with flying entangled qudits , journal = Physical Review A , date = 2011 , volume = 84 , issue = 1 , pages = 012328 , arxiv = 1102.2816, bibcode = 2011PhRvA..84a2328K , s2cid = 14751282 Quantum information science Quantum cryptography