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 solutio ...

, in which in addition to exploiting the principles of

quantum physics Quantum mechanics is a fundamental theory in physics that provides a description of the physical properties of nature at the scale of atoms and subatomic particles. It is the foundation of all quantum physics including quantum chemistry, q ...

, the no-superluminal signalling principle of

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

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 grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

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 Quantum theory may refer to: Science *Quantum mechanics, a major field of physics *Old quantum theory, predating modern quantum mechanics * Quantum field theory, an area of quantum mechanics that includes: ** Quantum electrodynamics ** Quantum ch ...

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 that occurs when a group of particles are generated, interact, or share spatial proximity in a way such that the quantum state of each particle of the group cannot be described independently of the state o ...

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

, physical systems cannot travel faster than the

speed of light The speed of light in vacuum, commonly denoted , is a universal physical constant that is important in many areas of physics. The speed of light is exactly equal to ). According to the special theory of relativity, is the upper limit fo ...

. 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 is a mathematical model that combines the three dimensions of space and one dimension of time into a single four-dimensional manifold. Spacetime diagrams can be used to visualize relativistic effects, such as why diffe ...

, 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; he, מינקובסקי, russian: Минковский) is a surname of Polish origin. It may refer to: * Minkowski or Mińko ...

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

vacuum A vacuum is a space devoid of matter. The word is derived from the Latin adjective ''vacuus'' for "vacant" or " void". An approximation to such vacuum is a region with a gaseous pressure much less than atmospheric pressure. Physicists often di ...

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

spacetimes In physics, spacetime is a mathematical model that combines the three dimensions of space and one dimension of time into a single four-dimensional manifold. Spacetime diagrams can be used to visualize relativistic effects, such as why differen ...

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

wormholes A wormhole (Einstein-Rosen bridge) is a hypothetical structure connecting disparate points in spacetime, and is based on a special solution of the Einstein field equations. A wormhole can be visualized as a tunnel with two ends at separate po ...

. 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 (mathematics), origin, orientation (geometry), orientation, and scale (geometry), scale are specified by a set of reference point ...

, 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 or The Key may refer to: Common meanings * Key (cryptography), a piece of information that controls the operation of a cryptography algorithm * Key (lock), device used to control access to places or facilities restricted by a lock * Key (ma ...

, for example using

one-time pads In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked, but requires the use of a single-use pre-shared key that is not smaller than the message being sent. In this technique, a plaintext is paired with a ...

. 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 A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later. Oded Goldreich (2001). Foundations of Cryp ...

coin tossing A coin is a small, flat (usually depending on the country or value), round piece of metal or plastic used primarily as a medium of exchange or legal tender. They are standardized in weight, and produced in large quantities at a mint in order to ...

, oblivious transfer 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 A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later. Oded Goldreich (2001). Foundations of Cryp ...

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\

. 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 or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , , ...

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.

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