Method and system for spacetime-constrained oblivious transfer
10715319 · 2020-07-14
Assignee
Inventors
Cpc classification
G06N10/00
PHYSICS
H04L9/0858
ELECTRICITY
International classification
H04L9/08
ELECTRICITY
Abstract
A method for performing spacetime-constrained oblivious transfer between a party A and a party B. The method includes imposing relativistic signaling constraints on a cryptographic task of one out-of-m oblivious transfer involving parties A and B. The method further includes using quantum systems for the one-out of-m oblivious transfer. The method guarantees unconditional security of the spacetime-constrained oblivious transfer, based on the imposed relativistic signaling constraints and based on using quantum systems for the one-out of-m oblivious transfer.
Claims
1. A method for performing spacetime-constrained oblivious transfer between a party A and a party B, the method comprising: synchronizing a plurality of agents A, B, A.sub.i, B.sub.i to a common reference frame F in a spacetime that is at least approximately Minkowski, wherein i{0, 1, . . . , m1}, wherein m corresponds to a cardinality of a plurality of messages x.sub.i from which spacetime-constrained oblivious transfer is to be performed, wherein the agents A and A.sub.i of the plurality of agents are associated with the party A, and wherein the agents B and B.sub.i of the plurality of agents are associated with the party B; specifying output spacetime regions R.sub.0, R.sub.1, . . . , R.sub.m1, wherein no connection by a causal curve in spacetime exists for any pair of output spacetime regions selected from the output spacetime regions R.sub.0, R.sub.1, . . . , R.sub.m1; generating random numbers r.sub.outcome and s.sub.basis by the agent A, wherein different elements s of a set .sub.basis label different orthogonal bases of a Hilbert space, and wherein, for any fixed s.sub.basis, different elements r of a set .sub.outcome label different orthogonal quantum states |.sub.r.sup.s from an orthogonal basis s; generating a quantum state |.sub.r.sup.s
of a quantum system, by the agent A; transmitting the quantum state to the agent B, by the agent A; transmitting the random numbers r and the random numbers s to the agent A.sub.i, by the agent A, wherein i{0, 1, . . . , m1}; obtaining an associated message x.sub.i.sub.outcome by the agent A.sub.i, wherein i{0, 1, . . . , m1}; encoding, by the agent A.sub.i, the plurality of messages x.sub.i using the random numbers r to obtain an encoded t.sub.i, wherein i{0, 1, . . . , m1}; transmitting, by the agent A.sub.i, the encoded t.sub.i and the random numbers s to the agent B.sub.i at a spacetime point that is in the causal past of at least one spacetime point of an output spacetime region R.sub.i and that is not causally connected to any spacetime point of output spacetime region R.sub.k for any k{0, 1, . . . , m1}/{i}, wherein i{0, 1, . . . , m1}; obtaining, by the agent B, a selector input b{0, 1, . . . , m1}; forwarding, by the agent B, the quantum state to an agent B.sub.b; measuring, by the agent B.sub.b, the quantum state in the orthogonal basis s to obtain outcome r.sub.outcome; and computing a received message y.sub.b.sub.outcome by decoding an encoded x.sub.b using r and t.sub.b, in output spacetime region R.sub.b.
2. The method of claim 1, wherein obtaining the selector input b is performed in a spacetime region G, wherein the spacetime region G is the intersection of causal pasts of all spacetime points of all of the output spacetime regions R.sub.0, R.sub.1, . . . , R.sub.m1.
3. The method of claim 1, wherein obtaining, by the agent A.sub.i, the associated message x.sub.i is performed in an associated spacetime region E.sub.i, wherein the associated spacetime region E.sub.i is the intersection of causal pasts of all spacetime points of the output spacetime region R.sub.i, and wherein i{0, 1, . . . , m1}.
4. The method of claim 1, wherein the received message y.sub.b differs no more than a specified threshold from x.sub.b.
5. The method of claim 1, wherein the common reference frame F in the spacetime that is at least approximately the Minkowski applies in at least one selected from a group consisting of Earth's surface, regions near the Earth's surface, and Earth orbits of satellites.
6. The method of claim 1, wherein .sub.outcome={0, 1}.sup.n; wherein then is a specified natural number; wherein encoding the associated message x.sub.i using the random numbers r comprises an operation t.sub.i=x.sub.i.Math.r; wherein decoding the encoded x.sub.b using r comprises an operation y.sub.b=t.sub.br; and wherein the .Math. denotes bit-wise sum modulo 2.
7. The method of claim 6, wherein the quantum state |.sub.r.sup.2 is a tensor product of n qubit quantum states |.sub.r.sub.
; wherein j{0, 1, . . . , n1}; wherein .sub.basis={0, 1}.sup.n; wherein r.sup.j is the jth bit entry of the random numbers r; wherein s.sup.j is the jth bit entry of the random numbers s; wherein the orthogonal basis s corresponds to n-qubit basis in which a basis of the jth qubit is a qubit orthogonal basis D.sub.0 if s.sup.j=0, or a qubit orthogonal basis D.sub.1 if s.sup.j=1; wherein D.sub.0 and D.sub.1 are two qubit orthogonal bases that are not mutually orthogonal.
8. The method of claim 1, further comprising storing the quantum state by at least one of the plurality of agents A, B, A.sub.i, B.sub.i.
9. The method of claim 8, wherein storing the quantum state by at least one of the plurality of agents A, B, A.sub.i, B.sub.i applies in at least one selected from a group consisting of storing the quantum state by the agent A before the quantum state is transmitted, storing the quantum state by the agent B before the quantum state is forwarded, and storing the quantum state by at least one of the plurality of agents A, B, A.sub.i, B.sub.i before the quantum state is measured.
10. The method of claim 1, further comprising verifying whether a message y.sub.i obtained by the party B correctly represents the associated message x.sub.i provided by the party A, for i{0, 1, . . . , m1}, by: providing, by the party A, the associated message x.sub.i to a verification device C.sub.i, at the intersection of the causal pasts of spacetime points in the output spacetime region R.sub.i; providing, by the party B, the message y.sub.i to the verification device C.sub.i in a spacetime region R.sub.i; and determining, by the verification device, whether the message y.sub.i correctly represents the associated message x.sub.i.
11. The method of claim 10, wherein determining whether the message y.sub.i correctly represents the associated message x.sub.i comprises: making a first determination that the spacetime region R.sub.i is contained in the output spacetime region R.sub.i; making a second determination that the message y.sub.i is sufficiently close to the associated message x.sub.i; and based on the first and the second determinations, concluding that the message y.sub.i correctly represents the associated message x.sub.i.
12. The method of claim 10, wherein determining whether the message y.sub.i correctly represents the associated message x.sub.i comprises concluding that the message y.sub.i does not correctly represent the associated message x.sub.i based on one selected from a group consisting of: making a first determination that R.sub.i is contained in the output spacetime region R.sub.i and making a second determination that the message y.sub.i is not sufficiently close to the associated message x.sub.i, making a first determination that R.sub.i is not contained in the output spacetime region R.sub.i and making a second determination that the message y.sub.i is sufficiently close to the associated message x.sub.i, and making a first determination that R.sub.i is not contained in the output spacetime region R.sub.i and making a second determination that the message y.sub.i is not sufficiently close to the associated message x.sub.i.
13. The method of claim 1 where the different elements s from the set .sub.basis label different bases that are mutually unbiased.
14. The method of claim 1, wherein at least one of the plurality of agents A, B, A.sub.i, B.sub.i is a satellite orbiting the Earth.
15. A system for performing spacetime-constrained oblivious transfer between a party A and a party B, the system comprising: a laboratory L.sup.A, associated with the party A, the laboratory L.sup.A comprising: a random number generator configured to generate random numbers r.sub.outcome and random numbers s.sub.basis; a quantum state source configured to generate quantum state |.sub.r.sup.2, wherein different elements s of a set .sub.basis label different orthogonal bases of a Hilbert space, and wherein, for any fixed s.sub.basis, different elements r of a set .sub.outcome label different orthogonal quantum states |.sub.r.sup.2
from an orthogonal basis s; a preparation device that is communicatively connected to a laboratory L.sup.B using a quantum channel, and configured to transmit the quantum state to the laboratory L.sup.B; and a first communication module that is communicatively connected to a plurality of laboratories L.sub.0.sup.A, L.sub.1.sup.A, . . . L.sub.m1.sup.A using a plurality of secure classical channels, and configured to transmit the random numbers r and the random numbers s to the plurality of laboratories L.sub.0.sup.A, L.sub.1.sup.A, . . . L.sub.m1.sup.A; the plurality of laboratories L.sub.0.sup.A, L.sub.1.sup.A, . . . , L.sub.m1.sup.A, associated with the party A, wherein each laboratory L.sub.i.sup.A, i{0, 1, . . . , m1}, comprises: a second communication module that is communicatively connected to laboratory L.sup.A using one of the plurality of secure classical channels, and that is communicatively connected to a laboratory L.sub.i.sup.B of a plurality of laboratories L.sub.0.sup.B, L.sub.1.sup.B, . . . , L.sub.m1.sup.B using a classical channel, and wherein the second communication module is configured to receive r and s; a computing device configured to: obtain a message x.sub.i .sub.outcome; and encode the message x.sub.i using r to obtain an encoded t.sub.i; and wherein the second communication module is further configured to transmit the encoded t.sub.i and the random numbers s to laboratory L.sub.i.sup.B using the classical channel; the laboratory L.sup.B, associated with the party B, comprising: a redirection unit that is communicatively connected to laboratory L.sup.A using the quantum channel, and configured to receive the quantum state from laboratory L.sup.A; a computing device configured to obtain a selector input b{0, 1, . . . , m1}; a quantum communication module that is communicatively connected to the plurality of laboratories L.sub.0.sup.B, L.sub.1.sup.B, . . . L.sub.m1.sup.B using a plurality of secure quantum channels, wherein the quantum communication module is configured to forward the quantum state to laboratory L.sub.b.sup.B; a laboratory L.sub.b.sup.B of the plurality of laboratories a L.sub.0.sup.B, L.sub.1.sup.B, . . . , L.sub.m1.sup.B, associated with the party B, comprising: a third communication module that is communicatively connected to laboratory L.sub.b.sup.A using one of a plurality of classical channels, and configured to receive t.sub.b and s; a quantum measurement device communicatively connected to laboratory L.sup.B using one of the plurality of secure quantum channels, and configured to measure the quantum state in basis s to obtain outcome r.sub.outcome; and a computing device configured to compute a received message y.sub.b .sub.outcome by decoding an encoded x.sub.b using r and t.sub.b, in output spacetime region R.sub.b; wherein a plurality of laboratories L.sup.A, L.sup.B, L.sub.i.sup.A and L.sub.i.sup.B is synchronized to a common reference frame F in a spacetime that is at least approximately Minkowski, wherein i{0, 1, . . . , m1}, wherein m corresponds to a cardinality of a plurality of messages x.sub.i from which spacetime-constrained oblivious transfer is to be performed, and wherein output spacetime regions R.sub.0, R.sub.1, . . . , R.sub.m1 are specified, wherein no connection by a causal curve in spacetime exists for any pair of output spacetime regions selected from the output spacetime regions R.sub.0, R.sub.1, . . . , R.sub.m1, and wherein the transmission of the encoded t.sub.i and the random numbers s by laboratory L.sub.i.sup.A occurs at a spacetime point that is in the causal past of at least one spacetime point of an output spacetime region R.sub.i and that is not causally connected to any spacetime point of output spacetime region R.sub.k for any k{0, 1, . . . , m1}/{i}, wherein i{0, 1, . . . , m1}.
16. The system of claim 15, wherein the plurality of classical channels and the plurality of secure classical channels comprise at least one selected from a group of electrical and optical network links.
17. The system of claim 15, wherein the quantum state is encoded in a quantum system represented by one selected from a group consisting of polarization degrees of freedom of photons, time-bin degrees of freedom of photons, spin degrees of freedom of electrons, spin degrees of freedom of atoms, spin degree of freedom of nucleus, spin degrees of freedom of molecules.
18. The system of claim 15, wherein each of the plurality of laboratories L.sup.A, L.sup.B, L.sub.i.sup.A and L.sub.i.sup.B comprises and atomic clock, used for synchronization to the common reference frame F.
19. The system of claim 15, further comprising a plurality of verification devices C.sub.0, C.sub.1, . . . , C.sub.m1, wherein each of the plurality of verification devices C.sub.i, with i{0, 1, . . . , m1}, is configured to verify whether a message y.sub.i obtained by the party B correctly represents the message x.sub.i provided by the party A, for i{0, 1, . . . , m1}, by: obtaining, from laboratory L.sub.i.sup.A, the message x.sub.i, at the intersection of the causal pasts of spacetime points in the output spacetime region R.sub.i; obtaining, from laboratory L.sub.i.sup.B, the message y.sub.i in a spacetime region R.sub.i; and determining, by the verification device, whether the message y.sub.i correctly represents the message x.sub.i.
20. The system of claim 19, wherein determining whether the message y.sub.i correctly represents the message x.sub.i comprises: making a first determination that the spacetime region R.sub.i is contained in the output spacetime region R.sub.i; making a second determination that the message y.sub.i is sufficiently close to x.sub.i; and based on the first and the second determinations, concluding that the message y.sub.i correctly represents the message x.sub.i.
Description
BRIEF DESCRIPTION OF DRAWINGS
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
DETAILED DESCRIPTION
(13) Specific embodiments of the invention will now be described in detail with reference to the accompanying figures. Like elements in the various figures are denoted by like reference numerals for consistency.
(14) In the following detailed description of embodiments of the invention, numerous specific details are set forth in order to provide a more thorough understanding of the invention. However, it will be apparent to one of ordinary skill in the art that the invention may be practiced without these specific details. In other instances, well-known features have not been described in detail to avoid unnecessarily complicating the description.
(15) Throughout the application, ordinal numbers (e.g., first, second, third, etc.) may be used as an adjective for an element (i.e., any noun in the application). The use of ordinal numbers is not to imply or create any particular ordering of the elements nor to limit any element to being only a single element unless expressly disclosed, such as by the use of the terms before, after, single, and other such terminology. Rather, the use of ordinal numbers is to distinguish between the elements. By way of an example, a first element is distinct from a second element, and the first element may encompass more than one element and succeed (or precede) the second element in an ordering of elements.
(16) Further, although the description includes a discussion of various embodiments of the invention, the various disclosed embodiments may be combined in virtually any manner. All combinations are contemplated herein.
(17) In general, embodiments of the invention provide a method and a system for spacetime-constrained oblivious transfer. Spacetime-constrained oblivious transfer (SCOT) is a variant of the cryptographic task of one-out-of-m oblivious transfer in which relativistic signaling constraints are imposed. From the imposition of relativistic signaling constraints and the use of quantum systems, the method of our invention guarantees unconditional security.
(18) One-out-of-m oblivious transfer is useful in transactions between mistrustful parties A (Alice) and B (Bob), where Alice has a secret database with m entries and Bob requests one of the m entries. More specifically, Alice has m messages x.sub.0, x.sub.1, . . . x.sub.m1 initially secret to Bob, for some integer m2. Bob has a number b{0, 1, . . . , m1} initially secret to Alice. As a result of the one-out-of-m oblivious transfer protocol Bob obtains x.sub.b. Bob is guaranteed the secrecy of his choice, and Alice is guaranteed that Bob can only obtain one entry of her database. In other words, two security conditions must be fulfilled by a one-out-of-m oblivious transfer protocol. First, Alice cannot learn Bob's input b, and second, Bob can only obtain one of Alice's messages. One-out-of-m oblivious transfer may, thus, be useful in transactions between mistrustful parties Alice and Bob, where Alice has a secret database with m entries. One-out-of-m oblivious transfer enables the implementation of other complex cryptographic tasks such as secure multi-party computation.
(19) Methods to implement one-out-of-m oblivious transfer generally fall in two broad categories. One category is based on protocols in which Alice and Bob process classical information and communicate classical messages between near laboratories, one controlled by Alice, and the other one controlled by Bob. These protocols are denoted as classical non-relativistic. Another category is based on protocols in which in addition to classical information, Alice and Bob process quantum systems and transmit quantum systems between near laboratories, again, one controlled by Alice, and the other one controlled by Bob. These protocols are denoted as quantum non-relativistic.
(20) The security of classical non-relativistic implementations of one-out-of-m oblivious transfer is based on the assumed difficulty of solving some mathematical problems, for example, the problem of finding the factors of large integer numbers. With the progressive development of more powerful computers, solving mathematical problems that once were thought difficult may become less difficult, thereby potentially making these implementations vulnerable. In particular, the eventual development of a universal quantum computer may make these types of protocols insecure, as a quantum computer may be able to obtain the factors of large numbers in a time that is exponentially smaller than the time taken by the most powerful classical computer. Further, the security of quantum non-relativistic protocols is based on the assumptions that the parties participating in the protocols have limited quantum technologies. For example, it is assumed that the storage of the quantum states of quantum systems is noisy, which means that the quantum states cannot be reliably decoded after storage; or that the storage of the quantum states of quantum systems is bounded, which means that only a limited number of qubits can be stored in a quantum memory.
(21) Accordingly, these methods to implement one-out-of-m oblivious transfer can only guarantee security if some technological assumptions are imposed on dishonest users, and the methods, thus, do not achieve unconditional security. Unconditional security of a method to implement one-out-of-m oblivious transfer is achieved if the method can be guaranteed to be secure even if one of the two parties implementing the method does not follow the method honestly, without assuming any technology limitations.
(22) Lo's no-go theorem states that there cannot be any classical or quantum non-relativistic protocol for one-out-of-m oblivious transfer that achieves unconditional security (H.-K. Lo, Phys. Rev. A, 56, 1154 (1997) (Lo) is hereby incorporated by reference in its entirety). Lo's no-go theorem states in particular that if a protocol to implement one-out-of-m oblivious transfer is unconditionally secure against Alice, meaning that Alice cannot obtain any information about Bob's input b, then, with sufficiently advanced quantum technology, Bob can obtain the desired message x.sub.b by following the protocol honestly and then by implementing a quantum operation on his quantum systems that allows him to obtain also Alice's message x.sub.k, for any k{0, 1, . . . , m1}\{b}.
(23) Spacetime-constrained oblivious transfer (SCOT) is a cryptographic task where relativistic signaling constraints are imposed on the cryptographic task of one-out-of-m oblivious transfer. SCOT is implemented by two mistrustful parties A (Alice) and B (Bob). Alice and Bob synchronize to a reference frame F in a spacetime that is at least approximately Minkowski, and specify in output spacetime regions R.sub.0, R.sub.1, . . . , R.sub.m1 in the frame F, with the property that every pair of output spacetime regions is spacelike separated, i.e., there is not any pair of output spacetime regions that is connected by any causal curve in spacetime. Alice has m messages x.sub.0, x.sub.1, . . . x.sub.m1 initially secret to Bob, for some integer m2. Bob has a number b{0, 1, . . . , m1} initially secret to Alice. As a result of the SCOT protocol Bob obtains x.sub.b in the output spacetime region R.sub.b. Two security conditions must be fulfilled by a SCOT protocol. First, Alice cannot learn Bob's input b anywhere in spacetime and second, Bob cannot obtain x.sub.i in R.sub.i for more than one i from the set {0, 1, . . . , m1}.
(24) By defining SCOT in such a way that Bob must not obtain x.sub.i in R.sub.i for more than one i from the set {0, 1, . . . , m1}, where every pair from the output spacetime regions R.sub.0, R.sub.1, . . . , R.sub.m1 is spacelike separated, SCOT evades Lo's no-go theorem.
(25) Implementing SCOT with unconditional security is in no contradiction with Lo's no-go theorem because if Bob obtains Alice's message x.sub.b in the output spacetime region R.sub.b by following the protocol honestly then, in agreement with Lo's theorem, with sufficiently advanced quantum technology, Bob can implement a quantum operation on his quantum systems that allows him to obtain also Alice's message x.sub.k in some spacetime region R.sub.k, for any k{0, 1, . . . , m1}\{b}. However, due to the causality of spacetime, and in particular due to the causality of the approximately-Minkowski spacetime near the surface of the Earth, the spacetime region R.sub.k, where the quantum operation that allows Bob to obtain x.sub.k is completed, must necessarily be in the causal future of R.sub.b, which is consistent with the definition of SCOT, stating that the output spacetime regions R.sub.b and R.sub.k, where the respective messages x.sub.b and x.sub.k must be obtained by Bob, are spacelike separated, i.e., R.sub.b and R.sub.k are not causally connected, hence, R.sub.k is not in the causal future of R.sub.b, for any k{0, 1, . . . , m1}\{b}.
(26) SCOT can have applications where, with high levels of security, a party Bob wants to learn an entry of a database from another party Alice, in some specific region of spacetime (e.g., at a specific location and at a specific time), while keeping his entry choice private from Alice, and by guaranteeing to Alice that only one entry of her database is accessible to Bob in the corresponding spacetime region. For example, potential applications of SCOT are in high frequency trading strategies (HFT) in the stock market, where transactions require high levels of security, and where transactions must be completed within half a millisecond. Other potential applications of SCOT correspond to situations where Alice and Bob own moving objects traveling at high speeds for which they want to keep their locations and trajectories secret from the other party, even though some information on their future trajectories must be disclosed in some situations, for example, if there is danger of collision.
(27) One or more embodiments of the invention include an unconditionally secure method to implement spacetime-constrained oblivious transfer, where unconditional security is guaranteed from the physical laws of quantum theory and relativity.
(28) One or more embodiments of the invention are based on one or more of the fields of quantum mechanics, quantum information theory, quantum cryptography, relativity theory and more specifically on the field of relativistic quantum cryptography. The fundamental concepts of quantum mechanics, quantum information theory and quantum cryptography that are related to embodiments of the invention, may be obtained, for example, from M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, UK, 2000) (Nielsen), which is hereby incorporated by reference in its entirety. Specifically, Nielsen provides information about the properties of qubits, non-orthogonal quantum states, the Bennett-Brassard 1984 (BB84) states, quantum measurements, the no-cloning theorem of quantum physics, the non-perfect distinguishability of non-orthogonal quantum states, and the properties of quantum entanglement. Furthermore, Nielsen familiarizes the reader with the notation used in the fields of quantum information and quantum cryptography. Further, an introduction to relativity theory, which describes the concepts and ideas of relativity, may be obtained from J. Hartle, Gravity: An Introduction to Einstein's General Relativity (Addison-Wesley, San Francisco, Calif., 2003) (Hartle), which is hereby incorporated by reference in its entirety. Hartle includes a description of Minkowski spacetime, curved spacetime, spacetime diagrams, the causality of spacetime, curves in spacetime, causal curves, timelike worldlines, null curves, reference frames, inertial reference frames, and the invariance of the speed of light in different inertial reference frames. An introduction to the field of relativistic quantum cryptography, and in particular to the setting and concepts used in the present invention, is provided below. In addition, a more extensive introduction to the field may be obtained from A. Kent, Class. Quantum Grav. 29, 224013 (2012) (Kent) and D. Pitala-Garca, Phys. Rev. A 93, 062346 (2016) (Pitala-Garca), both of which are hereby incorporated by reference in their entirety.
(29) Embodiments of the invention are based on the discipline of relativistic quantum cryptography. Relativistic quantum cryptography investigates cryptographic tasks and protocols whose security is guaranteed from the laws of quantum physics and relativity. Since according to the theory of relativity, spacetime is approximately Minkowski near the surface of the Earth, the speed of light has a finite value near the Earth and physical systems and information cannot travel faster than light. This no-superluminal signaling principle, which is satisfied by quantum physics, is considered a security resource in relativistic quantum cryptography. Additionally, the principles of quantum information, like the no-cloning theorem, the non-perfect distinguishability of non-orthogonal quantum states, the monogamy of quantum entanglement, and the existence of quantum correlations that violate Bell inequalities, may also be relied upon in relativistic quantum cryptography to guarantee security.
(30)
(31) In one or more embodiments of the invention, each agent participating in the cryptographic task controls a secure laboratory (laboratories L.sup.A (122A), L.sup.B(122B), L.sub.0.sup.A (124A.0), L.sub.0.sup.B (124.B.0), L.sub.1.sup.A (124A.1), L.sub.1.sup.B (124B.1), L.sub.2.sup.A (124A.2), L.sub.2.sup.B (124B.2), L.sub.m1.sup.A (124A.m1), and L.sub.m1.sup.B (124B.m1), in
(32) A secure laboratory, in accordance with one or more embodiments of the invention, guarantees the agent controlling the laboratory that any information that is generated within the laboratory remains secret from all other agents, unless this information is explicitly communicated outside the laboratory by the transmission of physical systems from the interior to the exterior of the laboratory. Exemplary secure laboratories are discussed in detail below, with reference to
(33) A secure classical channel between a first and a second agent allows the communication of classical messages between these agents by keeping the communicated messages secret to a third party, in accordance with one or more embodiments of the invention. A secure classical channel may be implemented, for example, via secure physical transportation, or via one-time pad methods using previously distributed secret keys.
(34) A secure quantum channel between a first and a second agent allows the transmission of quantum states between these agents by keeping the identity of the transmitted quantum states secret to a third party, in accordance with one or more embodiments of the invention. A secure quantum channel may be implemented, for example, if the first and second agents each have quantum systems that are in a quantum entangled state, and the quantum state that is to be transmitted is quantum teleported, with the transmission of the classical information required to complete teleportation being done through an authenticated classical channel. Alternatively the secure quantum channel may be based on physical transportation of a quantum system which encodes the quantum state to be transmitted, through a secure laboratory, the secure laboratory being extended from the location of the first to the second agent, or the secure laboratory being displaced from the locations between the first and the second agents.
(35) Continuing with the discussion of the system (100), shown in
(36) In one or more embodiments of the invention, Alice and Bob agree in advance on integer numbers m2, N=2.sup.n with n1. The value of n is chosen large enough in order to guarantee a desired level of security, as further discussed below. In one or more embodiments of the invention, for i{0, 1, . . . , m1}, Alice and Bob agree in advance that the output spacetime region R.sub.i corresponds to the set of spatial coordinates of the laboratory L.sub.i.sup.B of Bob's agent B.sub.i within a short interval of time .sub.i=[h.sub.i, h.sub.i+v.sub.i], for some small v.sub.i>0, with h.sub.i>d.sub.i, that is, R.sub.i={(t, x, y, z)|t.sub.i (x, y, z)L.sub.i.sup.B}. The values of h.sub.i and v.sub.i are chosen by Alice and Bob in order to satisfy that the output spacetime regions R.sub.0, R.sub.1, . . . , R.sub.m1 are pairwise spacelike separated (i.e., there is not any causal curve in spacetime connecting any pair of the output spacetime regions), as further discussed below with reference to
(37) Alice's agent A.sub.i may generate her input x.sub.i randomly as an n-bit string x.sub.i=(x.sub.i.sup.0, x.sub.i.sup.1, . . . , x.sub.i.sup.n-1) with bit entries x.sub.i.sup.0, x.sub.i.sup.1, . . . , x.sub.i.sup.n-1 within her laboratory L.sub.i.sup.A. Alice's agent A.sub.i generates her input x.sub.i sufficiently before the time h.sub.i, more precisely before the time h.sub.i.sub.i.sub.i, for small time intervals .sub.i>0 and .sub.i>0 agreed in advanced by Alice and Bob in consideration of the functioning of the devices within their laboratories and their communication channels, as specified below. The values of .sub.i and .sub.i are chosen small enough so that h.sub.i.sub.i.sub.i>.sub.i, where .sub.i the greatest time at which a light signal, by following any null curve in spacetime, can leave the laboratory L.sub.i.sup.A and reach another laboratory L.sub.k.sup.B at, or before, the time h.sub.k+v.sub.k, for all ki with k{0, 1, . . . , m1}.
(38) The input x.sub.i may be generated in various ways. For example, Alice's agent A.sub.i may generate input x.sub.i entirely within her laboratory, or she may compute it from information received by her laboratory before the time h.sub.i-.sub.i-.sub.i, which may include information from Alice's agent A, or from other of Alice's agents, in which case it may be obtained via one or more of the secure classical channels between Alice's laboratories, or from the exterior of any of Alice's laboratories. In one or more embodiments of the invention, the spacetime region where x.sub.i is generated by Alice is contained in E.sub.i, which is the intersection of the causal pasts of all the spacetime points of R.sub.i. In spacetime-constrained oblivious transfer, the input x.sub.i consists of one out of m messages, x.sub.0, x.sub.1, . . . , x.sub.m1, for i{0, 1, . . . , m1}. Additional details are provided below with reference to
(39) In one or more embodiments of the invention, Bob's agent B generates his input b randomly from the set {0, 1, . . . , m1} in his laboratory L.sup.B before the time t=0, in the frame F. Bob's agent B may generate b in various ways, For example, he may generate b entirely in his laboratory, or he may compute b from information that he receives in his laboratory before the time t=0. We note that since h.sub.i>d.sub.i, where d.sub.i is the shortest time that light takes to travel from L.sup.B to L.sub.i.sup.B, for i{0, 1, . . . , m1}, Bob's input b is generated within the spacetime region G, which is the intersection of the causal pasts of all the spacetime points of all the output spacetime regions R.sub.0, R.sub.1, . . . , R.sub.m1, as specified above. In a SCOT task, the input b is a selector input that specifies one of the m messages to be received by Bob in the corresponding output spacetime region. Additional details are provided below with reference to
(40)
(41)
(42) The system of
(43) In particular, as illustrated in the spacetime diagram of
(44) The spacetime region R.sub.i can be, for example, the set of spacetime points R.sub.i={(t,x,y,z)|h.sub.ith.sub.i+v.sub.i,(x,y,z)L.sub.i.sup.B}, where h.sub.i>0, v.sub.i>0 and L.sub.i.sup.B is a set of points in three-dimensional space that defines the space coordinates of one of Bob's laboratories, for i{0, 1, . . . , m1}; that is, R.sub.i corresponds to the set of all spacetime events that occur within Bob's laboratory having three-dimensional space coordinates L.sub.i.sup.B within the period of time [h.sub.i, h.sub.i+v.sub.i], for i{0, 1, . . . , m1}. In the simple example that h.sub.i=h and v.sub.i=v for all i{0, 1, . . . , m1}, in order to satisfy the spacelike separation of every pair of output spacetime regions R.sub.i and R.sub.k, it is required that the shortest time that light takes to travel between any spatial point in L.sub.i.sup.B and any spatial point in L.sub.k.sup.B is greater than v, for all i, k{0, 1, . . . , m1} with ik; for example, by setting the pair of Bob's laboratories whose sets of spatial coordinates are L.sub.i.sup.B and L.sub.k.sup.B with a straight line distance separation of at least 150 km, for all i, k{0, 1, . . . , m1} with ik, and considering that the speed of light through vacuum is approximately 300 000 km/s, by setting the value of the time interval v to be not greater than 0.5 ms, spacelike separation of every pair of output spacetime regions can be guaranteed. Small corrections in the values of the time coordinates h.sub.i, the time intervals v.sub.i, and the sets of spatial coordinates L.sub.i.sup.B, for i{0, 1, . . . , m1}, must be considered in the case of small spacetime curvatures, for example near the surface of the Earth, in order to guarantee that light signals leaving the output spacetime region R.sub.i cannot arrive to the output spacetime region R.sub.k and vice versa, for all i, k{0, 1, . . . , m1} with ik. Those skilled in the art will appreciate that these conditions hold for various environments, e.g., near the surface of the Earth, but also in regions that are somewhat more remote from the Earth's surface such as satellite orbits.
(45) The SCOT method in accordance with one or more embodiments of the invention may be extended to arbitrary curved spacetime, where the curvature of spacetime must be considered when setting the values of the output spacetime regions R.sub.0, R.sub.1, . . . , R.sub.m1 in order to guarantee that light signals leaving one of the output spacetime regions cannot reach any other output spacetime region.
(46) Turning to
(47) The subsequently described
(48) Turning to . Then, the quantum state is sent through the quantum channel (138) to the laboratory L.sup.B, controlled by Bob's agent B.
(49) In one or more embodiments of the invention, the quantum state that is prepared at L.sup.A is
(50)
where a=a.sup.0, a.sup.1, . . . , a.sup.n-1 represents the quantum system of n qubits and a.sup.j represents the jth qubit, for j{0, 1, . . . , n1}. For j{0, 1, . . . , n1}, the state of the jth qubit may be the BB84 state |.sub.r.sub., where the value of the bit s.sup.j indicates whether the state is prepared in the computational basis {|0
, |1)}, if s.sup.i=0, or in the Hadamard basis {|+
), |
)}, if s.sup.i=1, and where r.sub.i indicates the encoded outcome, i.e., where |.sub.r.sub.
=|r.sup.j
, for r.sup.j{0, 1}, |.sub.0.sup.1
=|+
and |.sub.1.sup.1
=|
.
(51) The quantum state of the n-qubits system may be prepared at a specific time and within a short interval of time, as controlled by the computer (404) with the value of the time provided by the atomic clock (402), in such a way that, after passing through the quantum channel (138), the quantum state arrives at the laboratory L.sup.B within the time interval .sub.P=[0, ], for some small >0. The value of may have previously been agreed upon by Alice and Bob, taking into account the functioning of all the relevant devices for the preparation and transmission of the quantum state from L.sup.A to L.sup.B and the precision of the atomic clocks in L.sup.A and L.sup.B. Thus, since the spacetime coordinates of the laboratory L.sup.B includes the origin, in the frame F, the quantum state is received by Bob's agent B near the spacetime point P=(0, 0, 0, 0), more precisely within the spacetime region P={(t, x, y, z)|t.sub.P, (x, y, z)L.sup.B}.
(52) In one or more embodiments of the invention, the time at which the messages r and s are sent by L.sup.A is controlled by the computer (404) using the time value provided by the atomic clock (402) so that the messages arrive at L.sub.i.sup.A before the time h.sub.i.sub.i.sub.i, which is previously agreed upon by Alice and Bob, with h.sub.i>d.sub.i+, .sub.i>0, and .sub.i>0, for i{0, 1, . . . , m1}. The values of the parameters .sub.i, .sub.i, and .sub.i, with 0<.sub.i<v.sub.i, may be chosen by Alice and Bob in such a way that, after passing through L.sup.B, the quantum state prepared at L.sup.A can arrive at L.sub.i.sup.B, via the quantum channel between L.sup.B and L.sub.i.sup.B, not earlier than the time h.sub.i and not later than the time h.sub.i+v.sub.i.sub.i, and in such a way that by reception of the messages r and s by L.sub.i.sup.A not later than the time h.sub.i.sub.i.sub.i, the processing and communication of the messages s and t.sub.i=rx.sub.i to the laboratory L.sub.i.sup.B can be completed not later than the time h.sub.i.sub.i, for i{0, 1, . . . , m1}. The transmission of the message s by L.sub.i.sup.A to L.sub.i.sup.B must begin after the time .sub.i, which is the greatest time at which a light signal can leave the laboratory L.sub.i.sup.A and reach any other laboratory L.sub.k.sup.B at, or before, the time h.sub.k+v.sub.k, for all ki with i, k{0, 1, . . . , m1}. This condition guarantees, based on the causality of spacetime, that no information about s can be received by Bob's agent B.sub.k in the output spacetime region R.sub.k, for all ki with i, k{0, 1, . . . , m1}, hence, the security proof described further below applies. The parameters .sub.i and .sub.i must be chosen small enough, compared to the smallest times that light takes to travel between the laboratories L.sub.i.sup.A and L.sub.k.sup.B for all ki, in order to satisfy that h.sub.i.sub.i-.sub.i>.sub.i, for i{0, 1, . . . , m1}.
(53) Turning to
(54) Turning to
(55) Turning to
(56) Turning to
(57) The computer (802) may use the signals received from L.sub.i.sup.A and L.sub.i.sup.B, and the time of arrival of the signal received from Bob's laboratory L.sub.i.sup.B as measured by the atomic clock (804) and may compute whether the following two conditions are satisfied: 1) Bob's message y.sub.i is sufficiently close to x.sub.i, according to a threshold d(y.sub.i, x.sub.i)n previously agreed by Alice and Bob and known by the computer, where d(a, a) denotes the Hamming distance between two n-bits strings a and a, which is the number of bit entries in which a and a differ; and 2) Bob's signal is received within the time interval .sub.i. Depending on whether conditions 1) and 2) are satisfied, the computer may changes the internal state of the verification device to correct or incorrect, as further discussed below with reference to the method shown in
(58)
(59) Turning to
(60) In Step 900, party A's (Alice) agents A, A.sub.0, A.sub.1, . . . , A.sub.m1 synchronize to a reference frame F in a spacetime that is at least approximately Minkowski. An equivalent step is performed by party B's (Bob) agents B, B.sub.0, B.sub.1, . . . , B.sub.m1, as described below in Step 950 of
(61) In Step 902, party A's and party B's agents agree on m output spacetime regions R.sub.0, R.sub.i, . . . , R.sub.m1 having the property of being spacelike separated, i.e., with no causal curve in spacetime connecting R.sub.i with R.sub.k, for any pair of different numbers i, k, from the set {0, 1, . . . , m1}. Step 902 is performed in conjunction with Step 952 of
(62) In Step 904, within her laboratory L.sup.A, Alice's agent A generates random numbers r, s{0, 1}.sup.n in the past of the spacetime point P=(0, 0, 0, 0).
(63) In Step 906, agent A uses the numbers r and s to prepare n qubits in Bennett-Brassard 1984 (BB84) quantum states, where the number s indicates on which bases the states of the qubits are prepared, and where r indicates the encoded outcomes. The prepared state for the n-qubits system is denoted by |.sub.r.sup.s. This state encodes the number r in the basis labeled by s.
(64) In Step 908, the qubits are transmitted to the laboratory L.sup.B of Bob's agent B.
(65) In Step 910, r and s are sent to agent A.sub.i, through a secure classical channel by agent A. Alternatively, if, at the moment of sending the messages, agent A has the input x.sub.i, t.sub.i=rx.sub.i (with denoting bit-wise sum modulo 2) may be sent, rather than r.
(66) In Step 912, the input or message x.sub.i is obtained by agent A, if it is not already available. x.sub.i may be obtained by generating x.sub.i (e.g., if x.sub.i is a random number), or by retrieving it from elsewhere, e.g., from a database.
(67) In Step 914, t.sub.i=rx.sub.i is computed by agent A.sub.i. r is received from agent A in the past of the spacetime point Q.sub.i=(h.sub.i,{right arrow over ()}.sub.i), where {right arrow over ()}.sub.iL.sub.i.sup.B, i.e., Q.sub.i is a spacetime point of R.sub.i, for i{0, 1, . . . , m1}. The computation of t.sub.i may be unnecessary if agent A has provided t.sub.i rather than r.
(68) In Step 916, Alice's agent A.sub.i sends s and t.sub.i to Bob's agent B.sub.i through a classical channel. The sending occurs at a spacetime point such that the messages arrive at the laboratory L.sub.i.sup.B slightly in the past of the spacetime point Q.sub.i, for i{0, 1, . . . , m1}. In particular, the transmission of s from L.sub.i.sup.A to L.sub.i.sup.B, must begin after the time .sub.i, which is the greatest time at which a light signal following any null curve in spacetime can leave the laboratory L.sub.i.sup.A and reach another laboratory L.sub.k.sup.B at, or before, the time h.sub.k+v.sub.k, for all ki with i, k{0, 1, . . . , m1}. This means that the spacetime event consisting in the transmission of s from L.sub.i.sup.A to L.sub.i.sup.B is not causally connected to any spacetime point of any output spacetime region R.sub.k, for all ki with i, k{0, 1, . . . , m1}.
(69) Turning to
(70) In Step 950, party B's (Bob) agents B, B.sub.0, B.sub.1, . . . , B.sub.m1 synchronize to a reference frame F in a spacetime that is at least approximately Minkowski. An equivalent step is performed by party A's agents A, A.sub.0, A.sub.1, . . . , A.sub.m1, as previously described below in Step 900 of
(71) In Step 952, party A's and party B's agents agree on m output spacetime regions R.sub.0, R.sub.1, . . . , R.sub.m1 having the property of being spacelike separated, i.e., with no causal curve in spacetime connecting R.sub.i with R.sub.k, for any pair of different numbers i, k, from the set {0, 1, . . . , m1}. As said above, in the description of Step 902 of
(72) In Step 954, the selector input b{0, 1, . . . , m1} is obtained in the past of the spacetime point P=(0, 0, 0, 0) by Agent B.
(73) In Step 956, the qubits are received by the laboratory L.sup.B of Bob's agent B, with reception occurring near the spacetime point P=(0, 0, 0, 0) (as previously discussed with reference to the system shown in
(74) In Step 958, s and t.sub.b=rx.sub.b, are received by Agent B.sub.b from Agent A.sub.b slightly in the past of the spacetime point Q.sub.b.
(75) In Step 960, immediately after reception of s in his laboratory L.sub.b.sup.B, Bob's agent B.sub.b sets up the quantum measurement device within L.sub.b.sup.B to measure the approaching n-qubits system in the basis labeled by s, on which it was initially prepared by Alice's agent A. The n-qubits system arrives to the laboratory L.sub.b.sup.B near the spacetime point Q.sub.b and is then measured in the basis s, giving as outcome a number r. Ideally, if there were not any errors in the implementation, the outcome r would be exactly equal to the number r encoded by Alice's agent A, but in practice r will be only approximately equal to r.
(76) In Step 962, using r and the message t.sub.b=x.sub.br received from agent A.sub.b, agent B.sub.b computes y.sub.b=r t.sub.b, which equals x.sub.b or is close to x.sub.b, and outputs it in the output spacetime region R.sub.b.
(77) In the above described methods, various parameters, including the parameters , .sub.i, .sub.i, and .sub.i for i{0, 1, . . . , m1}, may be chosen in advance by Alice and Bob, together with the output spacetime regions R.sub.0, R.sub.1, . . . , R.sub.m1, by considering the functioning of the devices within their laboratories, the precision of their atomic clocks, and the functioning of their quantum channels. In particular, the speed at which the quantum states are transmitted depends on the type of quantum channels used. For example, if the quantum systems encoding the qubits are photons, the quantum channels can be, for example, optical fibers through which the photons are transmitted, or they may be free space links, for example; the transmission of the quantum systems being slower in the former case than in the latter case.
(78) The subsequent discussion shows that the method to implement SCOT described above in
(79) First, a dishonest Alice could try to perform some cheating strategy that deviates from her actions described above in order to guess Bob's input b somewhere in spacetime. However, in the method described above, Bob does not give any physical systems to Alice, the laboratories of Bob's agents and the quantum channels among them are secure. Thus, independently of Alice's actions, no information about Bob's input b can escape from Bob's laboratories to Alice's laboratories. This means that Alice cannot obtain any information on b, or in other words, the probability that Alice guesses b equals the probability of a random guess, which is 1/m, anywhere in spacetime. Thus, the SCOT method is unconditionally secure against Alice.
(80) Second, a dishonest Bob could perform a cheating strategy that deviates from his actions described above in order to obtain l messages x.sub.i.sub.
(81)
(82) for any l with 2lm. Thus, the described SCOT method is unconditionally secure against Bob. Eq. (2) indicates that Alice and Bob must agree in advance on a value of n that is large enough in order to guarantee a desired level of security.
(83) Next, it is shown that the security of the SCOT method, as represented by Eq. (2), follows from the laws of quantum physics and relativity. In a general cheating strategy by Bob, Bob's goal is that his agent B.sub.i.sub.
(84) In a cheating strategy by Bob, Bob's agent B may try, for example, to copy the received quantum state and send one copy to his agent B.sub.0 and another copy to his agent B.sub.1, who receiving these copies near the respective spacetime points Q.sub.0 and Q.sub.i could then proceed to obtain the number r in R.sub.0 and in R.sub.1, by measuring the copied quantum states in the basis labeled by s on which Alice's agent A initially prepared the quantum state, and then output x.sub.0 in R.sub.0 and x.sub.1 in R.sub.1, respectively. However, this cheating strategy cannot succeed with high probability because the no-cloning theorem of quantum physics states that unknown quantum states cannot be cloned perfectly. In fact, whatever copies Bob send to his agents, their fidelity with respect to the original state will decrease exponentially with the number of qubits n, leading to a success probability p.sub.n that satisfies Eq. (2).
(85) In another cheating strategy that Bob may perform, Bob's agent B applies a quantum measurement on the received n-qubits system near the spacetime point P in order to obtain a guess of the encoded number r. Bob's agent B sends this guess of r to his agents B.sub.0 and B.sub.1, who receive these messages near the spacetime points Q.sub.0 and Q.sub.i, respectively. Then, using the messages received from agents B and A.sub.i near the spacetime point Q.sub.i, Bob's agent B.sub.i outputs his guess of x.sub.i in R.sub.i, for i{0, 1}. This cheating strategy cannot succeed with high probability because the BB84 quantum states have the physical property that they cannot be distinguished with unit probability if the basis on which they are prepared is unknown. Thus, the probability that Bob's agent B decodes r correctly by measuring the n-qubits system received from Alice's agent A cannot be unity, and in fact satisfies the bound of Eq. (2), leading to a success probability p.sub.n for this cheating strategy that also satisfies Eq. (2).
(86) More generally, in an arbitrary cheating strategy by Bob, since the spacetime regions R.sub.0 and R.sub.1 at which Bob's agents B.sub.0 and B.sub.1 must produce their outputs are spacelike separated, and since the transmission of s from Alice to Bob near the spacetime point Q.sub.0 in R.sub.0 (Q.sub.1 in R.sub.1) is spacelike separated from R.sub.1 (R.sub.0), it follows from the causality of spacetime that B.sub.0 and B.sub.1 must obtain their guess of r from quantum measurements on disjoint systems, which could have only interacted in the intersection of the causal past of some spacetime point in R.sub.0 and some spacetime point in R.sub.1. This means that in a general cheating strategy by Bob, Bob's agent B applies an arbitrary quantum operation on the received n-qubits system together with some extra ancillary quantum systems near the spacetime point P; agent B then partitions the total system into 2 subsystems, which can be in an arbitrary quantum entangled state, and distribute these systems to his agents B.sub.0 and B.sub.1, who receive them near the spacetime points Q.sub.0 and Q.sub.1, respectively; then, agents B.sub.0 and B.sub.1 apply quantum measurements on the received systems using the number s, which indicates the basis on which the initial quantum state was prepared by Alice's agent A, in order to obtain guesses of r and then output the corresponding guesses of the messages x.sub.0 in R.sub.0 and x.sub.1 in R.sub.1, respectively. However, a physical property of quantum physics, called the monogamy of quantum entanglement, states that if a first and a second quantum systems are in a quantum state that is highly entangled then a third quantum system cannot be very entangled to the first and second systems. This property implies that if the outcome of a quantum measurement on a quantum system held by Bob's agent B.sub.0 (B.sub.1) is highly correlated with the number r encoded by Alice's agent A in the original n-qubits system prepared by her, then the outcome of a quantum measurement applied by Bob's agent B.sub.1 (B.sub.0) on a quantum system held by him cannot be highly correlated to r. In other words, the probability that both agents B.sub.0 and B.sub.1 guess r cannot be very high, and in fact, it decreases exponentially with n, as given by Eq. (2).
(87) In practice, the preparation, transmission and measurement of the BB84 states, as discussed with reference to
(88) Turning to
(89) In practice, there may be errors during the preparation, transmission and measurement of the quantum state |.sub.r.sup.s. This implies that Bob's agent B.sub.b does not obtain the value of r perfectly, but an approximate number r. As a way of example, below we consider embodiments of the SCOT method in which the number r is a string of n bits and the encoding t.sub.i of Alice's agent A.sub.i using r is given by t.sub.i=x.sub.ir, where denotes bit-wise sum modulo 2, for i{0, 1, . . . , m1}. In these embodiments, Bob's agent B.sub.b obtains a string r of n bits, which is approximately equal to r. Thus, Bob obtains some output y.sub.b=rt.sub.b, which differs from x.sub.b in the bit entries in which r and r differ. The number of bit entries d(a, a) in which the n-bit strings a and a differ is denoted the Hamming distance between a and a. Taking into account the experimental errors of their devices and quantum channels, Alice and Bob may agree on some small threshold >0, for which they can guarantee that d(r, r)n, which implies that d(y.sub.b, x.sub.b)n, since d(y.sub.b, x.sub.b)=d(r, r). If is sufficiently small, then security against a dishonest Bob can still be guaranteed. For >0, security against Bob means that the probability that Bob obtains a n-bits string y.sub.i in R.sub.i satisfying d(y.sub.i, x.sub.i)n and also a n-bits string y.sub.k in R.sub.k satisfying d(y.sub.k, x.sub.k)n goes to zero as some security parameter, n in this case, goes to infinity, for any pair of different numbers i and k from the set {0, 1, . . . , m1}. For example, it is shown in Pitala-Garca that for <0.015, security against Bob is guaranteed for the embodiments of the SCOT method described in
(90) The SCOT method, in accordance with one or more embodiments of the invention, may include a method to verify whether Bob has output the message x.sub.i, or a message y.sub.i that is close enough to x.sub.i according to a previously agreed threshold, in the output spacetime region R.sub.i, for i{0, 1, . . . , m1}. The verification may be performed as follows.
(91) Turning to
(92) In Step 1000, the message x.sub.i from Alice is obtained by the verification device C.sub.i at the intersection of the causal pasts of the spacetime points in R.sub.i. Further, the message y.sub.i from Bob is obtained by the verification device C.sub.i in some spacetime region R.sub.i.
(93) In Step 1002, a determination is made about whether y.sub.i was received within the time interval .sub.i to ensure that the spacetime region R.sub.i is part of the spacetime region R.sub.i. If y.sub.i is found to be outside the time interval .sub.i, the method may proceed to Step 1004.
(94) In Step 1004, a determination is made about whether y.sub.i is sufficiently close to x.sub.i based on a threshold agreed to a priori by Alice and Bob. If y.sub.i is found to be beyond the threshold, the method may proceed to Step 1006.
(95) In Step 1006, the internal state of C.sub.i is set to incorrect, and in Step 1008, the internal substrate is set to output region incorrect & message incorrect.
(96) Returning to Step 1004, if a determination is made that y.sub.i does not exceed the threshold, the method may proceed to Step 1010.
(97) In Step 1010, the internal state of C.sub.i is set to incorrect, and in Step 1012, the internal substrate is set to output region incorrect & message correct.
(98) Returning to Step 1002, If y.sub.i is found to be within the time interval .sub.i, the method may proceed to Step 1014.
(99) In Step 1014, a determination is made about whether y.sub.i is sufficiently close to x.sub.i based on a threshold agreed to a priori by Alice and Bob. If y.sub.i is found to be beyond the threshold, the method may proceed to Step 1016.
(100) In Step 1016, the internal state of C.sub.i is set to incorrect, and in Step 1018, the internal substrate is set to output region correct & message incorrect.
(101) Returning to Step 1014, if a determination is made that y.sub.i does not exceed the threshold, the method may proceed to Step 1020.
(102) In Step 1020, the internal state is set to correct.
(103) Multiple variations of the above described systems and methods in accordance with one or more embodiments of the invention exist. For example, information may be encoded in qubits implemented in quantum systems in various ways, including the polarization degrees of freedom of photons, the time-bin degrees of freedom of photons, or the spin degrees of freedom of electrons, atoms, nucleus, molecules, etc. Further, while the above described systems and methods do not rely on quantum memory, alternatives that include quantum memories may be implemented without departing from the invention. Alice's and Bob's laboratories may contain quantum memories, which allow the generated quantum states by Alice to be stored in Alice's and Bob's laboratories at different steps of the above described method. The use of quantum memory may, thus, enable implementations with flexibility regarding the time of reception of the message s by Bob's agent B.sub.b in his laboratory L.sub.b.sup.B, for b{0, 1, . . . , m1}, as in this case, Bob's agent B.sub.b can store the received quantum state until s is received and then the quantum measurement device within his laboratory is set to measure the stored quantum state in the basis labeled by s. Further, the use of quantum memories in Alice's and Bob's laboratories may enable embodiments in which the respective numbers of Alice's and Bob's agents can be reduced from m+1 to m, by setting Alice's and Bob's respective agents A and B to be the respective agents A.sub.0 and B.sub.0, for example, where the step of the transmission of the quantum state from Alice's agent A to Bob's agent B and then to Bob's agent B.sub.0 in the embodiment described above is replaced by a step in which agent B.sub.0 receives the quantum state from agent A.sub.0 and then stores the quantum state in his laboratory until the spacetime region R.sub.0, where it is measured.
(104) In one or more embodiments of the invention, some or all of Alice's and Bob's laboratories may be moving in the reference frame F. In these embodiments, the laboratories may have GPS devices that allow the laboratories to track their locations. The various steps of the method to implement SCOT of the above described method can be straightforwardly adapted for embodiments in which the laboratories are moving. These embodiments include, for example, the case in which all or some of the laboratories are installed in satellites orbiting the Earth, and in which some other laboratories are fixed on the surface of the Earth. Finally, one or more embodiments of the invention may be designed to be suitable for use under general curved spacetime conditions, i.e., where Minkowski may not serve as a reasonable approximation. To operate under curved spacetime, the curvature of spacetime must be considered by Alice and Bob when agreeing on the output spacetime regions R.sub.0, R.sub.1, . . . , R.sub.m1 and the spacetime points Q.sub.0, Q.sub.1, . . . , Q.sub.m1 where Alice's agents communicate the basis s to Bob's agents, in order to guarantee that no signal leaving from the spacetime region R.sub.i, and in particular from the spacetime point Q.sub.i, can arrive to the spacetime region R.sub.k, for all ki with i, k{0, 1, . . . , m1}.
(105) The method of spacetime constrained oblivious transfer (SCOT), in accordance with one or more embodiments of the invention is applicable when a party Bob wants to learn an entry of a database from another party Alice, in some region of spacetime, while keeping his entry choice private from Alice, and by guaranteeing to Alice that only one entry of her database is accessible to Bob in the corresponding spacetime region. SCOT may be useful in situations where Bob must learn the information within specific locations and within specific short time intervals. For example, in high frequency trading, it is very important to learn information on the market on real time. Another example corresponds to situations where Alice and Bob own moving objects and they want to keep their locations and trajectories secret from the other party, however, some information on their future trajectories must be disclosed in some situations, for example, if there is danger of collision.
(106) The use case scenario described below is intended to provide an example of the method spacetime constrained oblivious transfer. The described methods and system are not limited to the use case scenario.
(107) One application of SCOT is related to the avoidance of satellite collisions. In the use case scenario, assume that the owners of two satellites want to keep their satellite trajectories secret while avoiding collisions of the satellites.
(108) Consider that Bob owns a satellite that, within a short interval of time is in one of m locations. Alice owns another satellite. Alice and Bob perform a SCOT protocol. Bob inputs an integer number b having one of m possible values. Each possible value of b may indicate, for example, a continuous region of three-dimensional space where Bob's satellite could be within the time interval , or it could indicate a trajectory within the time interval or within a longer time interval. Consider for now that b indicates a continuous region of three-dimensional space L.sub.b.sup.B where Bob's satellite could be within the time interval , for b{0, 1, . . . , m1}. Alice inputs m messages x.sub.0, x.sub.1, . . . , x.sub.m1 of n bits. We consider here that the output spacetime region R.sub.j of the SCOT protocol, in the frame F agreed by Alice and Bob, is the continuous region of three dimensional space L.sub.j.sup.B at time interval , which is slightly in the past of time interval , for j{0, 1, . . . , m1}. We take each of the pairs from the locations L.sub.0.sup.B, L.sub.1.sup.B, . . . , L.sub.m1.sup.B, to be sufficiently far apart and sufficiently small so that the spacetime regions R.sub.0, R.sub.1, . . . , R.sub.m1 are pair-wise spacelike separated. We take to be slightly in the past of .
(109) If the trajectory of Alice's satellite is programmed to pass by L.sub.k.sup.B in the future of , within the time interval , then Alice's input x.sub.k indicates its planed trajectory for the time interval (with the precision of the trajectory increasing with the number of bits n). The other inputs x.sub.j with jk and j, k{0, 1, . . . , m1} may be the string (0, 0, . . . , 0) or random and independent strings. Alice's satellite sends the encoding of her input x.sub.k to the region of three-dimensional space L.sub.k.sup.B so that it arrives just before the beginning of the time interval , i.e., within a time interval , which is slightly in the past of . If Bob's input is b=k then Bob's satellite receives Alice's encoding messages s and t.sub.b and can thus decodes the value of x.sub.k, since Bob has input b=k. Thus, Bob's satellite can then adapt its trajectory for the time interval to avoid collision with Alice's satellite.
(110) In the described scenario, various security conditions are met, providing security against Alice and security against Bob, as subsequently discussed.
(111) In the described scenario, Alice never learns Bob's input b, as this is a property satisfied by the SCOT method in accordance with one or more embodiments of the invention. Alice, thus, never knows in which of the in locations L.sub.0.sup.B, L.sub.1.sup.B, . . . , L.sub.m1.sup.B Bob's satellite is within the time interval .
(112) Bob learns the message x.sub.b of his choice within the corresponding spacetime region R.sub.b, i.e., within the continuous region of three dimensional space L.sub.b.sup.B at time interval . However, Bob cannot learn x.sub.1 in R.sub.j for any other jb, for j{0, 1, . . . , m1}. Accordingly, Bob's satellite learns Alice's satellite future trajectory for the time interval only if there is risk of collision, that is, if b=k. In principle, Bob could learn the trajectory of Alice's satellite even if bk, but Bob would not be able to learn this in the spacetime region R.sub.b, that is at the location L.sub.b.sup.B at time interval . Bob could learn the trajectory of Alice's satellite for the time only in the future, after the time interval , but in order to do so, Bob may need to have many more satellites being able to receive Alice's messages x.sub.1 and then send these to a common satellite or Bob's ground receptor. This could be impractical for a large m, in which case the trajectory of Alice's satellite for the time remains secret (except if b=k).
(113) Alternatively, if Bob has resources in space that are sufficiently powerful to allow him to recover all signals emitted by Alice's satellite, and hence decode its trajectory for the time interval , Bob could only do this at times after the time . For example, if =1 ms, the spatial separation between the three-dimensional space regions L.sub.j.sup.B and L.sub.i.sup.B needs to be at least 300 km, for ji and i,j{0, 1, . . . , m1}. Accordingly, in this case, Bob can learn the past trajectory of Alice's satellite, with a delay of at least 1 ms, but Bob cannot learn its future trajectory. As mentioned before, in order to learn the trajectory of Alice's satellite with a delay of 1 ms, Bob would need to be able to recover the signal from Alice's satellite almost immediately after its transmission, which might not be practical for Bob, unless Bob has satellites at all locations L.sub.0.sup.B, L.sub.1.sup.B, . . . , L.sub.m1.sup.B, or Bob's satellite is following Alice's satellite, hence it is always close to Alice's satellite. Thus, in practical scenarios where this would not happen, Bob does not even learn the past trajectory of Alice's satellite. Instead, Bob only learns its future trajectory for the time interval in case that there is risk of collision.
(114) The above use case may be generalized by repeatedly performing the method several times after each time interval to make the method available for large continuous time intervals. The use case may further be extended for the case in which Alice and Bob have several satellites. For example, if Alice has N.sub.A<m satellites and Bob has N.sub.B<m satellites, the SCOT method could be extended such that Bob inputs N.sub.B numbers from the set {0, 1, . . . , m1}, indicating the locations of his satellites. N.sub.A of the m inputs x.sub.0, x.sub.1, . . . , x.sub.m1 by Alice may be such that they indicate the future trajectories of Alice's satellites for the time interval .
(115) Embodiments of the invention may be implemented on a computing system. Any combination of mobile, desktop, server, router, switch, embedded device, or other types of hardware may be used. For example, as shown in
(116) The computer processor(s) (1102) may be an integrated circuit for processing instructions. For example, the computer processor(s) may be one or more cores or micro-cores of a processor. The computer processor(s) may further be a field programmable gate array (FPGA) or an application specific integrated circuit (ASIC). The computer processor may further be a system on a chip that may include components in addition to the processor, such as memory, I/O interfaces, etc. The computing system (1100) may also include one or more input devices (1110), such as a touchscreen, keyboard, mouse, microphone, touchpad, electronic pen, or any other type of input device.
(117) The communication interface (1112) may include an integrated circuit for connecting the computing system (1100) to a network (not shown) (e.g., a local area network (LAN), a wide area network (WAN) such as the Internet, mobile network, or any other type of network) and/or to another device, such as another computing device.
(118) Further, the computing system (1100) may include one or more output devices (1108), such as a screen (e.g., a liquid crystal display (LCD), a plasma display, touchscreen, cathode ray tube (CRT) monitor, projector, or other display device), a printer, external storage, or any other output device. One or more of the output devices may be the same or different from the input device(s). The input and output device(s) may be locally or remotely connected to the computer processor(s) (1102), non-persistent storage (1104), and persistent storage (1106). Many different types of computing systems exist, and the aforementioned input and output device(s) may take other forms.
(119) Software instructions in the form of computer readable program code to perform embodiments of the invention may be stored, in whole or in part, temporarily or permanently, on a non-transitory computer readable medium such as a CD, DVD, storage device, a diskette, a tape, flash memory, physical memory, or any other computer readable storage medium. Specifically, the software instructions may correspond to computer readable program code that, when executed by a processor(s), is configured to perform one or more embodiments of the invention.
(120) The computing system (1100) in
(121) Although not shown in
(122) The nodes (e.g., node X (1122), node Y (1124)) in the network (1120) may be configured to provide services for a client device (1126). For example, the nodes may be part of a cloud computing system. The nodes may include functionality to receive requests from the client device (1126) and transmit responses to the client device (1126). The client device (1126) may be a computing system, such as the computing system shown in
(123) The computing system or group of computing systems described in
(124) Based on the client-server networking model, sockets may serve as interfaces or communication channel end-points enabling bidirectional data transfer between processes on the same device. Foremost, following the client-server networking model, a server process (e.g., a process that provides data) may create a first socket object. Next, the server process binds the first socket object, thereby associating the first socket object with a unique name and/or address. After creating and binding the first socket object, the server process then waits and listens for incoming connection requests from one or more client processes (e.g., processes that seek data). At this point, when a client process wishes to obtain data from a server process, the client process starts by creating a second socket object. The client process then proceeds to generate a connection request that includes at least the second socket object and the unique name and/or address associated with the first socket object. The client process then transmits the connection request to the server process. Depending on availability, the server process may accept the connection request, establishing a communication channel with the client process, or the server process, busy in handling other operations, may queue the connection request in a buffer until server process is ready. An established connection informs the client process that communications may commence. In response, the client process may generate a data request specifying the data that the client process wishes to obtain. The data request is subsequently transmitted to the server process. Upon receiving the data request, the server process analyzes the request and gathers the requested data. Finally, the server process then generates a reply including at least the requested data and transmits the reply to the client process. The data may be transferred, more commonly, as datagrams or a stream of characters (e.g., bytes).
(125) Shared memory refers to the allocation of virtual memory space in order to substantiate a mechanism for which data may be communicated and/or accessed by multiple processes. In implementing shared memory, an initializing process first creates a shareable segment in persistent or non-persistent storage. Post creation, the initializing process then mounts the shareable segment, subsequently mapping the shareable segment into the address space associated with the initializing process. Following the mounting, the initializing process proceeds to identify and grant access permission to one or more authorized processes that may also write and read data to and from the shareable segment. Changes made to the data in the shareable segment by one process may immediately affect other processes, which are also linked to the shareable segment. Further, when one of the authorized processes accesses the shareable segment, the shareable segment maps to the address space of that authorized process. Often, only one authorized process may mount the shareable segment, other than the initializing process, at any given time.
(126) Other techniques may be used to share data, such as the various data described in the present application, between processes without departing from the scope of the invention. The processes may be part of the same or different application and may execute on the same or different computing system.
(127) Rather than or in addition to sharing data between processes, the computing system performing one or more embodiments of the invention may include functionality to receive data from a user. For example, in one or more embodiments, a user may submit data via a graphical user interface (GUI) on the user device. Data may be submitted via the graphical user interface by a user selecting one or more graphical user interface widgets or inserting text and other data into graphical user interface widgets using a touchpad, a keyboard, a mouse, or any other input device. In response to selecting a particular item, information regarding the particular item may be obtained from persistent or non-persistent storage by the computer processor. Upon selection of the item by the user, the contents of the obtained data regarding the particular item may be displayed on the user device in response to the user's selection.
(128) By way of another example, a request to obtain data regarding the particular item may be sent to a server operatively connected to the user device through a network. For example, the user may select a uniform resource locator (URL) link within a web client of the user device, thereby initiating a Hypertext Transfer Protocol (HTTP) or other protocol request being sent to the network host associated with the URL. In response to the request, the server may extract the data regarding the particular selected item and send the data to the device that initiated the request. Once the user device has received the data regarding the particular item, the contents of the received data regarding the particular item may be displayed on the user device in response to the user's selection. Further to the above example, the data received from the server after selecting the URL link may provide a web page in Hyper Text Markup Language (HTML) that may be rendered by the web client and displayed on the user device.
(129) Once data is obtained, such as by using techniques described above or from storage, the computing system, in performing one or more embodiments of the invention, may extract one or more data items from the obtained data. For example, the extraction may be performed as follows by the computing system in
(130) Next, extraction criteria are used to extract one or more data items from the token stream or structure, where the extraction criteria are processed according to the organizing pattern to extract one or more tokens (or nodes from a layered structure). For position-based data, the token(s) at the position(s) identified by the extraction criteria are extracted. For attribute/value-based data, the token(s) and/or node(s) associated with the attribute(s) satisfying the extraction criteria are extracted. For hierarchical/layered data, the token(s) associated with the node(s) matching the extraction criteria are extracted. The extraction criteria may be as simple as an identifier string or may be a query provided to a structured data repository (where the data repository may be organized according to a database schema or data format, such as XML).
(131) The extracted data may be used for further processing by the computing system. For example, the computing system of
(132) The computing system in
(133) The user, or software application, may submit a statement or query into the DBMS. Then the DBMS interprets the statement. The statement may be a select statement to request information, update statement, create statement, delete statement, etc. Moreover, the statement may include parameters that specify data, or data container (database, table, record, column, view, etc.), identifier(s), conditions (comparison operators), functions (e.g. join, full join, count, average, etc.), sort (e.g. ascending, descending), or others. The DBMS may execute the statement. For example, the DBMS may access a memory buffer, a reference or index a file for read, write, deletion, or any combination thereof, for responding to the statement. The DBMS may load the data from persistent or non-persistent storage and perform computations to respond to the query. The DBMS may return the result(s) to the user or software application.
(134) The computing system of
(135) For example, a GUI may first obtain a notification from a software application requesting that a particular data object be provided within the GUI. Next, the GUI may determine a data object type associated with the particular data object, e.g., by obtaining data from a data attribute within the data object that identifies the data object type. Then, the GUI may determine any rules designated for displaying that data object type, e.g., rules specified by a software framework for a data object class or according to any local parameters defined by the GUI for presenting that data object type. Finally, the GUI may obtain data values from the particular data object and render a visual representation of the data values within a display device according to the designated rules for that data object type.
(136) Data may also be provided through various audio methods. In particular, data may be rendered into an audio format and provided as sound through one or more speakers operably connected to a computing device.
(137) Data may also be provided to a user through haptic methods. For example, haptic methods may include vibrations or other physical signals generated by the computing system. For example, data may be provided to a user using a vibration generated by a handheld computer device with a predefined duration and intensity of the vibration to communicate the data.
(138) The above description of functions presents only a few examples of functions performed by the computing system of
(139) While the invention has been described with respect to a limited number of embodiments, those skilled in the art, having benefit of this disclosure, will appreciate that other embodiments can be devised which do not depart from the scope of the invention as disclosed herein. Accordingly, the scope of the invention should be limited only by the attached claims.