One-time Pad Encryption Model for Non-local Correlations

Bipartite no-signalling correlations are joint probability distributions of the form $P_{NS}(a,b|x,y)$ that satisfy the no-signalling (NS) conditions:

Here, $x\in X$, $y\in Y$, $a\in A$ and $b\in B$ are sample spaces of finite size and $P_{NS}(a|x,y):=\sum_{b}P_{NS}(a,b|x,y)$ & $P_{NS}(b|x,y):=\sum_{a}P_{NS}(a,b|x,y)$ are marginal distributions. These correlations are ‘Bipartite’ as they invoked two parties (say Alice and Bob) that are spatially separated, and the correlation in this context correspond to the joint probability distribution of outcomes $a$ and $b$ of experiments $x$ and $y$ performed by Alice and Bob, respectively. The no-signalling condition imposes the requirement that in such scenarios, Alice’s experimental settings should not influence Bob’s measurement statistics and vice-verse.

The classic example of such correlations are the joint probability distribution that violates the Bell’s inequality in the standard Bell scenario where local measurements are done by space-like separated parties on a common entangled state. In [26], it was shown that the set of no-signalling correlations is strictly larger than the set of quantum correlations and in particular that there are no-signalling correlations that are more non-local than quantum correlations. A notable example that will be used later on is the PR box, which is a bipartite no-signalling correlations defined as,

It can be easily verified that this correlation satisfies the NS condition and moreover it achieves the algebraic maximum value of Clauser-Horne-Shimony-Holt (CHSH) expression [15]. An important question to ask at this point is whether such correlations can be physical and if not why? An interesting approach in this direction is to look for principles that are physically or information theoretically motivated that we expect to hold. Towards this end, it turns out that the PR box violates an information theoretic principle called the principle of Information Causality (IC) [31] which will be explained in Section IV.3. The structure of the set of bipartite no-signalling (NS) correlations is also well known. In particular, the NS conditions being linear constraints on the probability imply that the set of NS correlations form a polytope called NS-polytope. The vertices of the set include deterministic local correlations and correlations that are non-local. For example, in the case of $2$-input, $2$-output correlations (where $a,b,x,y\in\{0,1\}$), all the non-local vertices are equivalent to the PR-box up-to local relabellings.

Bohm’s 1952 pilot-wave model for quantum mechanics [7, 8], which has roots to de Broglie’s 1927 work [6], is a hidden variable model of quantum mechanics where each particle is associated with an ontic position and it evolves ‘classically’ under a quantum potential which is related to the amplitude square of the wavefunction. As is famous, this model however allows for instantaneous signalling at the hidden variable level which is washed out by the inherent randomness in the theory (which is also related to the amplitude square of the wavefunction). The curious interplay between this instantaneous signalling and randomness was shown in [9], which proved that if the quantum potential deviates from the amplitude square of the wavefunction, the instantaneous signalling becomes operationally evident. However, the interplay between instantaneous signalling and noise can be more complicated than just one washing out the other as is suggested by the quantum advantages in information processing tasks. However, since the pilate-wave model is originally defined for continuous degrees of freedom, it obscures how signalling and randomness plays together. Moreover, since it is a model for quantum theory, there maybe further obfuscation associated with other features of quantum theory. In this paper, we present a hidden-variable model which is qualitatively similar to the pilate-wave theory but attempts to get around the problems aforementioned. More precisely, we present a model for a class of finite input-output non-local correlations which features the aforementioned interplay between instantaneous signalling and inherent randomness, but is nevertheless less obscured by the fact that it is finite dimensional and has less structure than a model for quantum theory. It goes without saying that this model is less powerful than quantum theory in information processing tasks, but we show that it is precisely the lack of structure than enables us to see the non-trivial ways in which noise and instantaneous signalling inter-plays for non-local advantages in information processing tasks.

The idea of cryptography has been instrumental in the development of the current information era [37]. OTP is a symmetric encryption scheme where the sender and the receiver share the same key. The key here is a bit string which is long as of the message to be encrypted and is uniformly randomly sampled and, crucially, only used once. The encryption step is simply to ‘XOR’ the message with the key, i.e., $\rm{Encrypt}=\rm{Message}\oplus\rm{key}$. The encrypted message is then sent over to the receiver, who will decrypt the message again by ‘XOR’-ing with the same key, i.e., $\rm{Decrypt}=\rm{Encrypt}\oplus\rm{key}=\rm{Message}$. As analyzed by Shannon, the security of this protocol is ensured when the key is sampled uniformly randomly from the set of strings $\{0,1\}^{m}$, where $m$ is the bit-length of the message [38].

Importantly, as long as the receiver does not have the key, the OTP system is equivalent to a non-signaling scenario in the sense that the receiver gets no information about the message the sender intends to send. This is precisely the observation that prompted our model. In other words, nature can, in principle, perform ‘secure’ instantaneous signaling as long as no one has access to the key a priori. We note that this is analogous to oblivious embeddings used in Ref.[39]. To mathematically capture the connection between NS correlations and OTP-based crypto-system, we start with formally defining an OTP-box.

A quick inspection reveals the inspiration for the definition. In the language of OTP encryption, one may think of $\lambda\in\{0,1\}$ as the key in the encryption protocol. The OTP box does the following: depending on the input $x$, Alice receives the output $g(x)\oplus\lambda$. Since Alice knows $g(x)$, she effectively has access to the key. Bob’s output can be understood as the function $f(x,y)$, but encrypted according to $\lambda$ as $b=f(x,y)\oplus\lambda$ (see Fig.1). Within the black box, the information of Alice’s input is instantaneously communicated to Bob’s end, albeit inaccessible to Bob outside the box. As we will show now, such crypto-systems satisfy NS property for a particular key distribution.

Nonlocal correlations can significantly reduce the communication complexity of distributed computing [30]. Given an $m$-bit string $x$ to Alice and an $n$-bit string $y$ to Bob, any arbitrary binary function $f(x,y):\{0,1\}^{m}\times\{0,1\}^{n}\mapsto\{0,1\}$ can be computed by Bob with just $1$-bit of communication from Alice to Bob provided they have access to nonlocal correlations. However, the completion of a task demanding m-bit communication using only a 1-bit channel, aided by nonlocal correlations that are otherwise NS, lacks a straightforward, intuitive explanation.

The OTP model framework offers an innate explanation for this puzzle. Let as a resource Alice and Bob are given an OTP-box where $g(x)=0$ and $f(x,y)$ in Def.1 is precisely the function they are interested in computing. From Lemma 1, this simply means that they are given the appropriate NS correlation. Alice and Bob input $x$ and $y$ in their respective parts of the box. According to the symmetric encryption scheme of the OTP-box, Bob’s output is the encrypted version of the function $f(x,y)$, i.e., $b=f(x,y)\oplus\lambda$, whereas Alice output is the key $a=\lambda$. This solves the puzzle as to how Alice and Bob can compute a function that requires communication of $m$-bit with just $1$-bit of communication and a NS box. The information of $x$ reaches Bob’s end through superluminal signaling at the hidden variable level. The output of the box is, however, encrypted and hence useless to Bob. But Alice has the key. She now sends the key ($\lambda$) through a $1$-bit communication channel, which allows Bob to decrypt the value of the function $f(x,y)$, irrespective of the length of the string $x$. In summary, we can say that the key is used by the agents to unlock the power of superluminal signaling at the hidden variable (ontic) level.

Win van Dam has shown that PR correlation can trivialize communication complexity [28]. This is quite surprising when compared with quantum correlations. Quantum entanglement is known to reduce the amount of classical information that Alice and Bob need to exchange to evaluate certain distributed functions [47], whereas for other functions entanglement provides no advantage. An example of latter is the Inner Product function $\mathrm{IP}_{n}:\{0,1\}^{n}\times\{0,1\}^{n}\mapsto\{0,1\}$, which is defined as $\mathrm{IP}_{n}(x,y):=\oplus_{i=1}^{n}x_{i}\cdot y_{i}$ [48]. At this point we recall a cryptographic concept called homomorphic encryption [49]. Homomorphic encryption allows performing computations on encrypted data without decrypting it and hence without compromising the security of the data. Our next result provides a new outlook of Van Dam protocol from a homomorphic encryption point of view.

Casting Van Dam’s protocol as homomorphic encryption thus provides a better understating of distributed computations with nonlocal correlations. Accordingly, the puzzling feature of the breakdown of communication complexity with PR box can be better appreciated in the OTP framework.

While nonlocality in PR correlation is quite strong, making communication complexity trivial, nonlocality in quantum theory is docile enough to ensure ‘nontrivial communication complexity’ [29]. Lately, a novel principle called Information Causality (IC) was proposed, which can capture this limited nonlocality of quantum theory and can identify post-quantum nonlocal correlations. IC limits Bob’s information gain about a previously unknown to him dataset of Alice to be at most $m$ bits when Alice communicates $m$ classical bits to Bob, and he is allowed to use local resources that might be correlated with Alice [31]. A necessary condition of IC can be obtained by considering random access code (RAC) task [50, 51, 52], where Alice receives a random string $x\in\{0,1\}^{n}$, and Bob randomly aims to guess $y^{th}$ bit $x_{y}$ of Alice’s string. In the presence of an NS correlation, if Alice communicates $m$-cbits to Bob, then according to IC the efficiency of the aforesaid task is upper bounded by $I_{n}\leq m$, where $I_{n}:=\sum_{k=1}^{n}I(x_{k}=\beta|y=k)$. Here, $I(x_{k}=\beta|y=k)$ denotes Shannon’s mutual information between the $k^{th}$ bit of Alice, and Bob’s guess $\beta$. Interestingly, IC reproduces the Cirel’son bound [27], i.e., any nonlocal correlation yielding CHSH [15] value more than $2\sqrt{2}$ violates IC.

A natural question is: how is this limited nonlocal feature of quantum correlation captured in our OTP model framework? Nonlocality, in our model, is achieved by a careful interplay between ontic-level signaling and randomness. Consequently, limited nonlocality can be accounted for in two ways: (i) either messing around with the randomness, which boils down to noisy encryption, or (ii) reducing the amount of ontic-level signaling. We will examine both these approaches in reproducing quantum correlations, particularly focusing on the class of isotropic correlations.

(i) Quantum correlations as noisy encryption: As shown in Theorem 3, isotropic correlations in $2,2$-input & $2,2$-output scenario allow an N-OTP model. As motivated in the definition of the N-OTP box, the limited non-locality found in nature can be explained through noisy encryption. More precisely, we can interpret it as follows: there is a well-defined value of the encryption key $\lambda$ within the box, but nature is ‘peculiar’ in such a way that it does not provide perfect access to the key to the agent outside the box (in this case Alice). The key $\lambda^{\prime}$ accessed by Alice is not identical to the key $\lambda$ within the box; rather, they are correlated. A simple calculation ensures that the necessary condition of IC is satisfied when the mutual information between the true key $\lambda$ and the obtained key $\lambda^{\prime}$ is upper bounded by $0.5$ bit. Although this could be a way of obtaining quantum-realizable nonlocal correlation, the approach might look rather arbitrary and ad hoc.

(ii) Quantum correlations through limited ontic-level signalling: A more natural approach to explain limited nonlocality would be to limit the extent of instantaneous signaling at the ontic level. After all, the idea of instantaneous signaling itself sounds far too radical. Let us try to come to terms with it by making it less powerful. For this, we may model the instantaneous communication within the box as a classical binary bit-flip channel, with flipping probability $(1-\mu)$. The remainder of the OTP-box remains the same. In this case, the input-output correlation obtained by the agents outside the box reads as: $P(ab|xy)=\mu\frac{1}{2}[\sum_{\lambda}\delta(a,\lambda)\delta(b,xy\oplus\lambda)]+(1-\mu)\frac{1}{2}[\sum_{\lambda}\delta(a,\lambda)\delta(b,(x\oplus 1)y\oplus\lambda)]$. We can now use the standard RAC protocol to verify that OTP boxes of this kind always violate the IC principle, except when $\mu=0.5$, corresponding to no communication at all. In other words, perfect encryption, with noisy ontic-level signaling, violates IC. By perfect encryption, we mean that Alice has perfect access to the key that is used to encrypt the function $f(x,y)$ at Bob’s end. A more explanatory analysis is provided in Appendix.