Quantum Computation,
Control and Privacy
Elaborato di Laurea Specialistica
Corso di Laurea Specialistica in Fisica Teorica
Quantum Computation,
Control and Privacy
Candidato:
Davide Orsucci
Relatore interno:
Prof. Pasquale Calabrese . . . .
Relatore esterno:
Prof. Vittorio Giovannetti . . . .
Candidato:
Davide Orsucci . . . .
Sessione di Laurea 22 Maggio 2014 Anno Accademico 2013-2014
1 Introduction to classical cryptography 7
1.1 Basic cryptographic notions . . . 8
1.2 Information theoretic secrecy . . . 9
1.3 Man in the Middle attack . . . 11
2 Blind Quantum Computation 13 2.1 Classical Blind Computation . . . 13
2.2 Blind Quantum Computation motivation . . . 15
2.3 Programmable gates . . . 16
2.4 Blind Quantum Computation protocols . . . 18
2.4.1 Childs protocol . . . 19
2.4.2 Giovannetti & al. protocol . . . 22
2.4.3 Broadbent, Fitzsimons & Kashefi protocol . . . 24
2.4.4 Morimae & Fujii protocol . . . 27
2.5 Cost analysis . . . 28
3 Cryptographic primitives 37 3.1 Different forms of secrecy . . . 38
3.2 Overview of cryptographic primitives . . . 39
3.2.1 Quantum Key Distribution . . . 40
3.2.2 Private Information Retrieval . . . 41
3.2.3 Symmetrical Private Information Retrieval . . . 42
3.2.4 Quantum Private Queries . . . 42
3.2.5 Oblivious Transfer . . . 43
3.2.6 Bit Commitment . . . 43
3.2.7 Coin Flipping . . . 44
3.3 Cryptographic primitives against unbounded quantum adversaries . . 45
3.3.1 Impossibility of Bit Commitment . . . 46
3.3.2 Results on Coin Flipping . . . 46
3.3.3 PIR has linear communication cost . . . 47
3.3.4 An algorithm for QPQ . . . 48
3.4 Cryptographic primitives against weaker quantum adversaries . . . 50
3.4.1 Ideal CF and BC with special relativity . . . 50
3.4.2 Secure SPIR protocol when Alice has a short quantum memory 52 3.5 Classical implications among cryptographic primitives . . . 57
3.5.3 SPIR implies Key Distribution . . . 60
3.5.4 QPQ on non-deterministic database implies BC . . . 61
4 Control theory 65 4.1 Quantum Zeno Dynamics . . . 66
4.2 Blind control in Zeno Dynamics . . . 69
4.3 Hamiltonian purification . . . 70
4.3.1 Lower bounds on dE . . . 71
4.4 Optimal purification for a small number of operators . . . 72
4.4.1 Purification of 2 operators with dE= 2 · d . . . 73
4.4.2 Purification of m operators with dE = m · d . . . 73
4.4.3 Optimal purification for 2 operators on a qubit . . . 74
4.4.4 Lower bound on the optimal purification for 2 operators . . . . 75
4.4.5 Optimal purification for 2 operators on a qutrit . . . 76
4.5 Optimal purification for direct complete control . . . 78
4.5.1 Complete control of qubits . . . 78
4.5.2 Complete control of k-qubits . . . 80
4.5.3 Complete control of d-level systems . . . 80
A Information theoretic security requires a key with high entropy 89
B Introduction to Measurement Based Quantum Computation 91
C The quantum One-Time Pad cipher 97 D Bell pairs and Super-dense Coding 99
Quantum Information theory is a subject which includes ideas from different disci-plinary areas, ranging from physics, to theoretic informatics, to cryptography. In this thesis we explore the field from all these perspectives.
The cryptographers are interested to quantum theory since - in 1984 - Bennett and Brassard illustrated a quantum protocol (known as Quantum Key Distribution) which attains the Holy Grail of cryptography: an encryption scheme that allows distant allies to exchange classical information - but sent through a quantum channel - where an arbitrarily powerful eavesdropper has a vanishing probability of recovering any of this information. Spurred by this success the cryptographic community has set out to find other cryptographic protocols that could be devised in a quantum mechanical context.
From the computer scientist’s point of view, Quantum Information pledges to give rise to a new computational paradigm, in which the laws of quantum mechanics will allow to operate quantum computers capable of solving efficiently some problems which are deemed to be intractable with classical computers.
For a physicist, there are too many good reasons to study Quantum Information to state them here. In this work the connection with physics comes from the ex-perimental side. We investigate the state of the art of the exex-perimental control of quantum systems, in order to achieve - at least at the level of a proof of concept - a physical implementation of quantum protocols arising in quantum cryptography and quantum computation.
In the introduction, we review some important concepts from classical cryptog-raphy. Then we set out to investigate Blind Quantum Computation. Consider the following scenario: in the (near) future some quantum computers will be built, but few institutions will have enough funds to operate one of them; so a client (which we will call customarily Alice), that has only limited quantum resources, wants the server (say Bob) to perform a computation on her behalf, but in such a way that the server can not access neither the algorithm, nor the data processed. We compare some of the existing protocols and show that Blind Quantum Computation can be performed with very little resources on Alice’s side: it is sufficient that she can create single qubit states or perform single qubit unitary transformations or perform single qubit measurements. This can be most easily done with the so called Measurement Based Quantum Computation.
Afterward we review some Cryptographic Primitives: these are logically elemen-tary cryptographic functions upon which more complex cryptographic protocols can be built. While in Blind Quantum Computation the focus is on the computational
to recover one element from it, while Bob does not want her to discover more than one element for each query. No computational restrictions are imposed to Alice and Bob in this case. It turns out that, despite much hope inspired by the existence of efficient Key Distribution schemes, many of the analyzed Cryptographic Primitives turn out to be impossible under standard assumptions. This motivates for the search of a different set of assumptions, which however must be physically realistic, which allow to extend the class of implementable cryptographic functions. We find that if Alice has a short time quantum memory, SPIR is indeed possible. We give also a detailed explanation of how to do it in quantum optics.
In the last section we analyze innovative techniques that exploit the Quantum Zeno Effect in the context of quantum Control Theory. In Control Theory the ex-perimenter has a classical control over a quantum system - for example through a classical electromagnetic field - which can be depicted as the possibility to turn on at will some interaction Hamiltonians, depending on the external controls. In Zeno Dynamics one performs a fixed projective measurement on the quantum system at very high rate, which effectively confines the dynamics of the state on a subspace given by the eigenspace of the measurement operator corresponding to the measured value. It turns out that in this way the possibility to control the dynamics of the system is highly enhanced. This study is motivated by the search for an alternative paradigm of quantum computation, which exhibits some peculiarities that closely re-sembles the ones investigated in the previous chapters. Then, to further investigate the physical properties of such systems, and ultimately to foster their experimental implementation, we consider the problem of Hamiltonian purification. This consists in finding, given a set of interaction Hamiltonians that implement a complete con-trol over the Zeno subsystem, a set of extended Hamiltonians on the overall system which are commutative (and so easily implementable). Many original and non trivial results are found in this context.
Preliminaries on Quantum Information
Quantum Information is a vast and rapidly expanding field, so that it is already impossible to master it entirely. Even so there is a core of subjects which by now can be considered as standard knowledge; these include the Gate Array Model for quantum computation, fidelity measures among states, properties of entanglement, quantum channels, and so on. It would be very time demanding even to give a short introduction to each of these topics, each of which however will turn out to be an indispensable tool in the exposition of this work. Therefore it will be assumed a basic knowledge of the most common topics in Quantum Information, referencing to the textbook of Nielsen and Chuang [1] for a thorough explanation of all the necessary background material.
Introduction to classical
cryptography
The field of quantum computation has been interwoven, since the very beginning of its rather brief history, with the concepts derived from cryptography and cryptanalysis. These came in a twofold way, providing a whole new set of tools both for code-breaking and for cypher design.
On the one hand, quantum computers will allow, once we have learned how to build working specimens, to break the presently adopted public-private key cryp-tographic protocols, such as RSA 1 or elliptic curve cryptography [2] (via Shor’s factorization algorithm or slight variation of it [3]) thus seriously undermining the possibility of secure communications among remote parties. This of course would be disastrous! Just to mention it, all web services that require secure access, or even the debit card authentication protocol, entail some kind of public-private key cryptog-raphy. So it seems that from the Quantum Information field comes a deathly threat to currently widespread cryptographic algorithms2.
On the other hand, Quantum Information comes with the promise of a definitive solution for obtaining private and secure communication. The Quantum Key Dis-tribution (QKD) protocol developed by Bennett and Brassard back in 1984 (BB84) [5] is the first instance of a procedure that, upon the use of a quantum channel for exchange qubits among distant parties (which can be physically implemented, e.g., with a polarization encoding of photons sent along an optical fiber), can demonstra-bly attain an unbreakable encryption of the message sent. This seems to be the Holy Grail of cryptography, after which no further development of cryptography could be possible. However the security proofs need some physical and mathematical as-sumptions, which may not always be satisfied in practical implementations. On the physical side, when information is sent along as photons along an optical fiber, it has
1RSA is named by the initials of its inventors: Ron Rivest, Adi Shamir and Leonard Adleman. 2In view of an era in which quantum computers are widespread, some authors have already
studied classical encryption algorithms which relies on problems that are thought to be difficult to solve even for quantum computers, and some positive results are known; these studies of classical algorithms resilient to quantum computing brute force attack go under the name of Post-Quantum Cryptography [4].
been shown that a strong laser pulses can burn the receiver, forcing it to respond in a predetermined way [6]. On the mathematical side, it is supposed to exist a classical public unjammable channel, on which both parties can prove with certainty that they are indeed who they declare to be. If this were not true, QKD protocols would be subject to a Man in the Middle attack, as explained below. Anyhow much technological effort has still to be done for obtaining reliable, efficient and low cost quantum channel, on which the QKD protocol can be performed routinely.
1.1
Basic cryptographic notions
The first cryptographic methods were devised in ancient times, for allowing distant allies to send messages to each other, preserving the secrecy of the content even in the unfortunate circumstance that the missive fell in the enemy’s hands. The first instance probably is an encryption used in 1900 BC in Egypt, while the first monoalphabetical substitution ciphers was devised by the Hebrews in 600 BC. These methods at the beginning were successful; the secrecy was attained mainly through obfuscation of the message, rather than by strong cryptographic means: back to those times nobody had the linguistic and mathematical resources necessary to de-cipher such cryptograms. Indeed, the first cryptanalyst is deemed to be Ibn ’Adlan (1187–1268 CE), who had discovered and written a book on how to decipher monoal-phabetical substitution codes - via a method now called frequency analysis. From that moment onward, for centuries new cryptographic algorithms were invented and new attack strategies were found 3.
This naturally leads to the question whether a cryptographic code is secure, or if a sufficiently wit analysis can reveal the original text. To pose this question on a more solid mathematical ground, it is important first to point out the difference between the secrecy of the cryptographic protocol and the secrecy of the key. A cryptographic protocol consists of an encryption algorithm and of a decryption algorithm: the first algorithm takes in two inputs, the plain text and the encryption key, and gives out a single output, the cypher-text ; the second algorithm takes in the cypher-text and the decryption key and gives out the original plain text. When the encryption and decryption key are equal, we talk of symmetric-key cryptography, when they are different (and in general one cannot easily deduce one from the other) we talk of asymmetric-key cryptography, or also of public-private key cryptography.
The most basic assumption, and also a most natural one, goes under the name of Kerchoff ’s principle, formulated by Auguste Kerchoff in the 19th century: it states that the security of a cryptosystem should be preserved even when the enemy knows all about the cryptographic algorithm, except for the keys that are being used. Summarizing: keep secret the key, not the algorithm. While this is not so important when a single message has to be exchanged (in this case, the choice of the algorithm adopted can be considered as a part of the key), it is essential when two or more parties have to keep in constant communication and need to exchange a large quantity of encrypted messages; devising a secure cryptographic algorithm is a difficult and time consuming effort, so it would be intolerable to have to choose a new
3For a very clear, simple and enjoyable introduction to cryptography, also containing an
one every time that the privacy of the communication is compromised. Instead, in the Kerchoffian scenario, it suffices for the parties to choose a new random set of keys, which can be done most easily, and keep using the same algorithm. There is a second important reason for adopting the Kerchoff principle: as the cryptanalytic methods become more and more sophisticated, it becomes increasingly difficult to assess the effective security of an algorithm; it is often much more secure to rely on a widely used and applied algorithm, which has passed all the cryptanalytic tests posed by the international community, rather then an obscure and unknown one, which may easily entail some major flow which makes it completely unreliable. For addressing this issue, in the last decades some international encryption standards have been chosen, such as DES (Data Encryption Standard, now obsolete) and AES (Advanced Encryption Standard) for symmetric-key cryptography, and RSA for asymmetric key cryptography.
Intuitively, a cryptosystem is secure if the attacker have no practical methods for finding out the key and/or the message, given realistic assumptions on the resources and the time he has at disposal. More formally, a cryptosystem is defined to be secure if there is no way for obtaining the key (or the keys) which is easier then brute force attack. There are many possible types of attacks which may be considered and many partial results or incomplete information that the attacker may succeed to recover, but for simplicity let’s stick to the following scenario: the attacker knows a plain text (which he may have guessed or stolen) and the corresponding cypher-text, and he wants to recover the encryption key (or, better still, all the possible keys which output the given cypher-text when the given plain text is processed with the encryption algorithm). Alas, given the intrinsic intricacy of the cryptographic protocols, it is rarely possible to mathematically prove that one is indeed secure, and so it is in principle possible that tomorrow someone will come out with a clever attack strategy which will make it useless, and retroactively allowing anybody to decipher all the messages sent in the past. Moreover, assuming that the Moore law, which empirically observes that computers double their computational power each 18 month (see Fig. 1.1) carries on to be valid indefinitely (which we know to be physically impossible, but for the moment we still see no deviation from it), in a foreseeable future all present communication could be broken also by brute force. And, as already mentioned, if Quantum Computers will be built many asymmetric-key cryptosystems will become insecure.
1.2
Information theoretic secrecy
The previous discussions motivates the use of a stronger definition of secrecy: it would be desirable that a cryptosystem is not only practically unbreakable at present, given the limited computational power and analytical methods at disposal of the attacker, but is provably impossible to recover the plain text, however intelligent or powerful the attacker is. In this case one talks of semantic secrecy. A solution is known to exist: One-Time Pad encryption 4. This procedure is provably secure: when the
4The procedure is extremely simple. Firstly a sequence of m completely random bits (the
One-Time Pad) is generated. A copy of the pad is given to the sender and one to the receiver. Then to encrypt a m bit long message the sender performs a XOR operation between the j-th bit of the
Figure 1.1: This graphic shows in semi-logarithmic scale the computational power, expressed in GFLOPS (= 109 FLoating-point Operations per Second) of the top supercomputer (red), of the 500th ranked supercomputer (yellow), and of the top 500 supercomputers combined (blue), in the year range 1993 − 2013.
attacker is given a m bit long cypher-text C, then he might try any random pad R to recover the message. But the setM of all possible messages, given the cypher-text C, is just the set of all possible N bit long messages; and, if the pad R is generated truly randomly (and is used only once! 5), then all messages are equally likely; i.e., the posterior probability distribution for the messages is equal to the prior probability. This has been rigorously proved by Shannon in 1949 [8], while founding the field of classical information theory.
The question that now arises is if exists a protocol which is less resource con-suming: in this scenario the sender and the receiver must share a secret key of the same dimension of the message to be sent, which may be undesirable if many long messages have to be transmitted. Moreover, generating completely random bits is not as simple as it might seem: classical computers are intrinsically deterministic and so also pseudo-random generators are deterministic (and have a periodicity which is at most equal to 2s− 1, where s is the number of bits in the seed). The answer
to this question is a no-go: using a deterministic encryption algorithm, to attain entropic security a key with at least as much entropy as the transmitted message has to be used. In App. A is proved that if a message with m bits of information is
plain text and the j-th bit of the pad, for j = 1, .., m. To recover the message, the receiver performs the same operation on the cypher-text.
5Reusing a One-Time Pad key can be a costly mistake. As part of the VENONA project the
USA secret services were able to decipher part of the messages exchanged by the Russian army in the period 1942-1945, because some pages of the One-Time Pads were used twice.
deterministically encrypted with a key with k bits of information, then at least m − k bits will leak into the cypher-text [9]. However, if non deterministic algorithms and approximate entropic security are allowed, then it is still possible to achieve security against adversaries with unbounded resources even with a shorter key [10].
1.3
Man in the Middle attack
To get a feeling of how cryptographers have to reason and the assumptions that have to make, we describe the most basic and still the most powerful of all attack strategies - the Man in the Middle attack. Suppose that two parties, which we will call as customary Alice and Bob, want to send and receive encrypted messages and that they share only a single communication line, on which they don’t have full control; moreover they had not time to share any secret key in the past. In this situation, they have no mean to attain privacy at all, however powerful is the encryption algorithm they are going to use! In fact the eavesdropper, the mischievous Eve, can simply put herself in between them, pretending to be Bob with Alice and to be Alice with Bob (she is the Man in the Middle). At some point Alice will have to send, if she want to set up an encrypted communication, the public key KALICE(the one which allows Bob to send encrypted messages to her), keeping the private key for herself (and then Bob will be able to send his keys already in encrypted form to Alice). But then Eve can simply choose at will a private key and extract the corresponding public key KEVE, and replace KALICE with KEVE in the message sent to Bob. At this point, Eve acts as a repeater: when Bob sends a message to Alice, he actually uses KEVE; Eve uses her private key to decipher the message and then uses KALICE to send it back to Alice. The same procedure can be performed for the messages sent in the other direction.
This attack allows Eve to have full control on the messages which are being sent, i.e. it even allows her to arbitrarily change the messages, without that neither Alice nor Bob can a priori detect it. However, in practical implementations, this techniques presents some flaws. Firstly, the ping time (the time for a signal to travel from Alice to Bob and backward) will be inevitably increased, and this may lead in the end to a detectable effect, which may render Alice and Bob suspicious. Secondly, and most importantly, if at a certain time Alice and Bob open a second communication line, Eve has to get control also of this line, otherwise Alice and Bob could cross check their keys on this secondary line, consequently unveiling Eve’s mischief.
Now suppose that the second line is a radio broadcasting in which Alice reads out her public key; suppose moreover that Bob knows her voice and that Eve is not able to fake it: this is an example of an unjammable channel, a channel which cannot be obstructed or faked. Then, thank to the existence of this unjammable channel, Bob can send encrypted messages to Alice using the public key broadcast to Alice, now knowing for sure that only Alice will be able to decrypt her message with her private key (as long as the cryptographic encryption is secure). This shows the essential role of the unjammable channel for establishing a secure ciphered communication.
This unjammable channel is used as a device to ensure that the association be-tween a public key and its owner is correct, i.e. to perform the authentication. In the real world (e.g. internet) the authentication is done by protocols implementing
a public key infrastructure, which allow the validity of the association to be formally verified by reference to a trusted third party. In this case the association between a public key and its owner is ultimately a matter of subjective judgment, since the key is a mathematical entity, while the owner, and the connection between owner and key, are not. On the other hand, Alice and Bob may also as well question their trust in each other, on which cryptography can say nothing.
Blind Quantum Computation
The general setting of Blind Computing (also known as Trusted Computing) is the following. Suppose that Alice has only limited computational power and that she wants Bob, who has much more powerful resources, to perform a computation on her behalf. But Alice (a.k.a. the client ) wants also to keep secret her computation from Bob (a.k.a. the server ): this entails keeping secret the algorithm performed, the data that have to be elaborated, or both. This general setting can be applied to both classical and quantum domain, but in the latter there are far more possibilities, as is elucidated below.
2.1
Classical Blind Computation
In the classical domain, the question that has been more thoroughly investigated is that of computation with encrypted data. In this scenario, Alice wants to compute a publicly known function f on her private data x and recover the private result y = f (x). She however does not have enough computational power to calculate f (x), and so she has to rely on Bob. However, before sending the data to him, she performs an (easy to compute) encryption on the input G : x 7→ x0; then Bob applies the function on the encrypted data and outputs the encrypted result y0 = f (x0); finally Alice gets the correct result by inverting the encryption H : y0 7→ y. If this operations can be performed, we say that the function f is encryptable, and that G and H are the encryption functions.
The answer to the feasibility of this scheme, in the context of complexity theory, depends on what exactly the computational resources of Bob are assumed to be. Many interesting results have been found in this field (some of which rather recently). If we assume that Bob has unlimited computational power and we ask for perfect encryption of the data, then we get substantially a no go result. It turns out that there is a link between encryptability and complexity of a function: the functions that can be encrypted in polynomial time (i.e. efficiently) are exactly those which can be computed in expected polynomial time [11]. Even if some small leakage of information is allowed, the situation does not get better. If we allow the leakage of a logarithmic quantity of information, with respect to the length of the data (for
example, this is the amount of information leakage that one has when Bob comes to know the length |x| of the encrypted data), then no N P -hard function can be encrypted in polynomial time, unless the polynomial-time hierarchy collapses at the third level 1.
Another possibility, which maybe is more similar to the real-world cases, is that also Bob is computationally bounded, and Alice can assume that he cannot perform N P -hard computation on sufficiently large inputs, on which however she can perform some polynomial time encryption. In this context it is customary to talk of homo-morphic encryption. The idea is that Alice’s encryption and decryption functions preserve some algebraic operations, and so they happen to be an homomorphism for this operation. As an illustrative example, take the RSA encryption of the data instances x1, x2: H(x) = xe mod N , where the RSA public key is given by the
ex-ponent e and the number N which is product of two (large) prime numbers. Then we have that this encryption is an homomorphism for the product operation:
H(x1) · H(x2) = xe1 x e
2mod N = (x1x2)e mod N = H(x1· x2) (2.1)
In the decryption algorithm the same kind of operations are performed, so the RSA natively incorporates homomorphic encryption of products. Similarly, encryption that preserve the sum can be easily found. However such a kind of encryption would be really interesting if it were a homomorphism for both the sum and the multiplication. With such a scheme, any circuit or boolean function can be evaluated thus allowing universal computation on fully encrypted data. In this case we talk of fully homomorphic encryption: this precisely accomplishes the task of performing computation with encrypted data.
For almost 30 years, since the very beginning of public-private key cryptography, it has been unknown whether fully homomorphic encryption was even theoretically feasible [12]. Then in 2009 it was found the first algorithm which implements a fully homomorphic encoding on ideal lattices [13] [14], finally giving a positive answer to the issue. At present there is intense work undergoing to simplify the original work, for which there was a high computational overhead, and make it applicable in real-world applications [15].
There is another paradigm of Blind Computing, the so called Secure Multiparty Computing, which may be declined as Secure Distributed Computing, or as Trusted Cloud Computing for a more practically-oriented view of the subject, and which is a stand-alone field of study. Many different flavours of Secure Multiparty Computing exist, but usually it is intended in a symmetric way, in which all the parties collab-orate for computing a certain function. In this context the function to be computed is not necessarily a particularly difficult one, but all parties possess some private data that are not willingly to reveal. A famous example is the millionaire problem: two millionaires want to determine who is the richer (evaluate the boolean condi-tion a ≤ b), without revealing the real amount of their estate (the values of a, b)
1The infinite hierarchy of complexity classes P ⊆ N P ≡ N P∅ ⊆ N PN P ⊆ N PN PN P ⊆ ...,
where N PC stands for problems solvable in non-deterministic polynomial time plus an oracle for
solving problem in the class C, is called the polynomial-time hierarchy. It is strongly believed that each level is strictly included in the next one; however, proving this statement would be a major breakthrough in complexity theory, and so it is customary to give proofs conditioned on the truth of this fact.
[16]. There are algorithms that allow to solve this problem efficiently and securely, premised the existence of a secure way of implementing oblivious transfer (defined in Sec. 3.2.5). The general scheme may entails N different parties, each of which has some secret piece of information x1, ..., xN, and they want to compute some function
of the data f (x1, ..., xN) without ever revealing each other the value of their private
data (see Sec. 3.2). Many different assumptions can be made. One could ask for an unconditionally secure protocol, or for one based on some computational assumptions on the difficulty of solving certain types of problems; the adversary may be collabora-tive - but still curious to know the opponents data - or uncollaboracollabora-tive; there may be or not external entities which try to gather information on data transmitted, includ-ing the result f (x1, ..., xN), and which may or not alter the data flow; finally, may
be introduced some asymmetry in the computational power of the parties. Usually, the algorithms turn out to have substantial - sometimes exponential - cost increase, which make them of difficult application in realistic circumstances. In Cloud Trusted Computing the focus is shifted toward a more efficient implementation, in which a community of users can certify, with high probability, that their data is not being sneaked. Given the remarkable intricacy of Secure Multiparty Computing, and the existence already of partial positive results in the classical counterpart, we will not deal with its generalization to the quantum regime (an example can be found in [17]). Notice that insofar it has not been addressed the problem of hiding the function f to be computed from Bob, who actually performs the computational operation. This is indeed a subtle issue. This task is customarily accomplished by code obfusca-tion, transforming the algorithm in an equivalent one which however is of much more difficult interpretation for a human interpreter. However, from a theoretic perspec-tive, this is not a satisfactory answer, and can be hardly considered a cryptographic procedure at all. To clarify, we consider two limiting cases. Suppose that Alice has no computational power at all, so she has to specify to Bob the input data and all the operations that have to be performed. In this case, Bob can just write down all the operations he is performing, and this will turn up to be exactly a specification of the algorithm. On the other hand, if Alice has high computational power (and a fast communication line with Bob), she can use her computer to perform part of the algorithm and actively obfuscate it. But ultimately, given enough computational resources, Alice could perform the computation all on her own, thus completely ex-cluding Bob from accessing the data and the algorithm. Somewhere in between these limits, it may still be possible for Alice to hide her computation from Bob, but it seems difficult to obtain any exact result.
2.2
Blind Quantum Computation motivation
In the quantum domain the computational difference in the computational power of Alice and Bob is neater. It is assumed that Bob has a fully operational quantum computer, while Alice has only classical computational resources, plus very limited quantum resources [18]. To be more specific, it could be assumed that Bob can effi-ciently solve problems in the BQP class (Bounded-error Quantum Polynomial-time problems) while Alice can solve problems in the P class (Polynomial Time problems) Still the problem is somewhat arbitrary, as it depends on the exact specification of
Alice’s quantum resources; but anyhow Alice must necessarily have some quantum resources and a quantum channel to Bob, to interface them with Bob’s quantum computer, otherwise the problem can be re-conduced to the classical case studied in [11]. Some very minimal assumption can be made: for instance Alice could be able to perform only single qubit preparation or single qubit unitary transformation or single qubit projective measurements.
From an heuristic information-theoretic approach, one could expect that in the quantum context it is easier for Alice to hide the computation from Bob. In fact, in Bob’s quantum computer the data is stored as quantum states in a quantum register, and this is done in the densest possible way. Intuitively, the number of linearly independent states of a quantum register is finite, and so it follows that the amount of information that is possible to store in the register is also finite. In other words, all the possible configuration of the register are used to store the data, and no other information can be obtained from it: there are no hidden internal degrees of freedom which allow to store any other information. If some of this information in the register flows out (e.g. because of thermal noise, or because Bob is trying to read this information), then the register itself must have lost the same amount of information, thus disrupting the computation itself.
More formally, Bob is prevented from reading what is happening in his quantum computer by the no-cloning theorem [20] if the state of his computer is unknown to him, for example because it was initialized by Alice, then he cannot copy it elsewhere (in another quantum register) without erasing the original one. In a dual way, he cannot make any POVM measurement on it which allows to reconstruct this state with perfect certainty [1]. This seems to imply that the computer, to work correctly, has to be kept well isolated from the environment and that no information can be extracted until the end on the computation. This picture is qualitatively correct, although actually there are models of quantum computation that require the quantum computer to be in a well controlled pre-determined interaction with the environment (Quantum Zeno Dynamics, see Sec. 4.1) and other which require to measure part of the register state at each step in order to proceed in the computation (Measurement Based Quantum Computation, see App. B). We will see how these model also have an important role for achieving Blind Quantum Computation.
Summarizing, from a very heuristic analysis it seems that there are better perspec-tives for achieving Blind Computation in the quantum regime than in the classical one, also when Alice has very little quantum resources. The next section however shows why the most naive approach is doomed to fail, following the article in refer-ence [21].
2.3
Programmable gates
To attain Blind Quantum Computation, the first idea which may come up is that of using programmable quantum gates. This is implemented as a standard quantum gate which takes in two input states, one of which is identified as the program |PUi
and the other as the data |Di. Then a fixed unitary operation G is applied to both the program and the data; this unitary operation G is such that a unitary gate U is applied to the data state |Di accordingly to the program specification |PUi. Then a
Figure 2.1: Schematics of a unitary gates G that takes in two unentangled states and outputs two unentangled states. G should implement a unitary action U on the data state |Di in function of a program state |PUi.
Adapted from [21].
superposition of different programs should result also in a superposition of different outputs. The output of the gate G is assumed to be generic, except for the fact that the outputted states U |Di and |PU0 i are separable - the program and the data states are still unentangled after the application of the gate. Fig. 2.1 gives an illustration of the gate G.
If one could identify an appropriate set of programmable gates, then this would allow a very simple implementation of Blind Quantum Computation. In fact, it would be sufficient for Alice to send the program specification to Bob in non orthogonal states and ask him to send back the outputted program states |P0
Ui to check that
they have not been altered. Bob then would face the problem that, each time he wants to know the operation that is being performed, he would have to measure the program state |PUi to recover some information about U ; but in doing so he would
always have some chance of altering the program state, and consequently Alice could detect it with a non zero probability. In the long run, Bob’s attempted spying would certainly be discovered. However, this type of programmable quantum gates cannot be realized, as we shall now show.
We assume that the program and the data enter in the separable form:
|Di ⊗ |PUi (2.2)
end exit from the programmable gate as:
G(|Di ⊗ |PUi) = (U |Di) ⊗ |PU0 i. (2.3)
A priori, it is possible that |PU0 i depends upon D. We see that this is not the case considering two different inputs D1, D2, from which we have:
G(|D1i ⊗ |PUi) = (U |D1i) ⊗ |PU0 (1)i
G(|D2i ⊗ |PUi) = (U |D2i) ⊗ |PU0 (2)i. (2.4)
Taking the scalar product of these two equations, we obtain on the left-hand side hD1|D2i and on the right hand side hD1|D2ihPU0 (1)|P
0
U(2)i, and therefore we have
hP0
U(1)|PU0 (2)i = 1. Now suppose that two states P and Q implement two different
unitary gates Up and Uq. Hence:
G(|Di ⊗ |Pi) = (Up|Di) ⊗ |P0i
and again, taking the scalar product of the two equations we obtain
hP|Qi = hP0|Q0ihD|Up†Uq|Di. (2.6)
Now suppose that hP0|Q0i 6= 0; then we can divide both sides by it and get
hP|Qi
hP0|Q0i= hD|U †
pUq|Di. (2.7)
Notice that the left hand side is a number λ independent from D, and to fulfill the equality the only possibility is Up†Uq = λI, which however implies that Uq and Up
are the same up to an irrelevant phase, contrary to the hypothesis that they are different. So the only way to satisfy (2.6) is to take hP0|Q0i = 0. But then (2.6)
implies also that hP|Qi = 0.
Conclusion: to synthesize different unitary gates on a programmable gate we need an orthogonal set of program states, one for each unitary operation to be implemented. As orthogonal states are perfectly distinguishable, this means that the gate programming is effectively a classical programming, and so Bob can merrily read off all the commands Alice is sending to him. If approximate or probabilistic operations for the programmable gate are allowed, we have that the program states have no more to be orthogonal; but also in this case, if two programs states are not orthogonal, the corresponding programmed unitary gates have to be very similar (e.g. they have very small trace distance [1]), and so they do not make a good resource for Blind Quantum Computation [22].
These consideration then spurs the research of a way for circumventing this lim-itation, also appealing to other computational models, in which for example the output state does not have to come out unentangled. Indeed, since when the prob-lem was stated in 2003 [18], a number of good solutions have been found, for different specifications of Alice’s apparatus.
2.4
Blind Quantum Computation protocols
Here we give a review of four algorithms, two based on the circuit model for quantum computing and two based on the paradigm of Measurement Based Quantum Com-putation (MBQC). For a brief review to this topic, see App. B; for a more thorough introduction, see [25].
For each of the following Blind Quantum Computation protocols, we schemati-cally show that it is correct (it gives the correct output with high probability), that it is secure (either, it is impossible for Bob to recover any information at all, or Al-ice can discover if he is trying to eavesdrop the computation with high probability) and that it allows universal quantum computation (any quantum algorithm can be made blind: this was not the case for the first blind quantum protocol devised, which applied only to random verifiable functions [18]).
Notice however that Bob always comes to know at least a minimal amount of information, which consists of the number of qubits in the state register (n) and the length of the computation (m). These only give an upper bound on the real dimensions of the computation, as Alice may have padded the computation with idle qubits and idle operations. In the following, when stating that a protocol is
unconditionally secure, it will mean that only information that is leaking are the values of n and m.
Moreover, just as happens in the classical setting, Bob may be dishonest in dif-ferent ways. For example, he may willingly help Alice in performing correctly the computation, but still he may desire to know what algorithm is being performed (honest-but-curious adversary in classical context, specious adversary in quantum context 2); the specious adversary is in some way the weakest possible adversary. Otherwise Bob may want to recover Alice’s data even at the expense of disrupting the computation (malicious adversary). Our Blind computation protocols will be shown to be robust against this stronger kind of adversary.
2.4.1
Childs protocol
This protocol is based on the circuit model paradigm. It is assumed that exists a bidirectional quantum channel between Alice and Bob, and that Alice can perform only Pauli X, Z operations (single qubit operations), along with their composition (the total set is given by I, X, Z, XZ), and swap operations; if for example the qubits are encoded in the polarization of some photons, each travelling in a different optical fiber, then the X and Z gates are implemented with optical plates and the swap operation is implemented by physically exchanging the optical fibers, so they are reasonably simple to implement. Notice that Alice’s computational power is very limited and she cannot create entanglement among different qubits. On the other hand Bob has a quantum computer with a set of universal gates, which for concreteness may be a single qubit Hadamard (H), a controlled NOT (C-X) and a π/8 shift gate (T ). Composing these three basic gates it is possible to build quantum circuits that can perform any possible quantum computation [1].
The computational state is initialized in a fiduciary state, say ρ(n)0 ≡ (|0ih0|)⊗n
by Bob (as Alice in general may not be able to generate the qubits). Then at each computational step t all the n qubits of the computational state ρ(n)t are bounced
back and forth from Alice to Bob. We split up each step in three parts: (1) Alice’s encoding, (2) Bob’s computation and (3) Alice’s correction.
1. For each qubit j = 1, ..., N , Alice tosses two coins with output rj, sj. Then she
accordingly performs the operation XrjZsj on the j-th qubit of the quantum
register ρ. Then Alice performs a permutation of the qubits of the register, in order to specify the computation, as detailed in the paragraph below, and sends the resulting state to Bob. The operation performed by Alice, from Bob’s perspective, is equivalent to applying a completely depolarizing channel on all the qubits; this because Bob does not know which of the four operations I, X, Z, XZ has been applied, and this completely erases out any information on the state. This is detailed in App. C, about the quantum One-Time Pad cipher. If Bob didn’t apply any gate and bounced the state back to Alice, this
2In the classical context, the honest-but-curious adversary performs the algorithm correctly,
but copies the information in order to extract information later; in quantum context, this is not possible, in virtue of the no-cloning theorem. However, a specious adversary may still deviate from the protocol, e.g. skipping measurements operations and continuing in superposition, performing the measurement only when Alice asks for the result [19].
Figure 2.2: Scheme for implementation of a Hadamard gate with data privacy. The double lines represent the classical control performed by Alice over the X and Z gates, the single line represents a qubit of the register state. The dashed box highlights the gate that is performed by Bob.
operation would be equivalent to one in which Alice is sending a quantum state to herself via Bob, who now plays the role of the eavesdropper. As she knows which operation she had done at the previous step, she can easily recover the initial state. Bob instead always receives a state that, from his point of view, is indistinguishable from the completely mixed state, and so he can never recover any information on the computational state.
2. When the quantum state is on Bob’s side, he activates a fixed (independent from the time step), predetermined set of gates on the qubits on the system, which is known also to Alice; this set of gates must be engineered in such a way that conveniently swapping the qubits after each operation allows to perform any possible computation. For example, Bob may constantly apply a Hadamard gate to the first qubit, a phase shift to the second qubit and a controlled NOT between the third and the fourth qubit; then it is Alice’s task to swap the computational qubits to bring them in the position of the register where the gate is operated. Suppose that in general at each step a certain number of non-trivial gates (G 6= I) act on a total of L qubits, containing at least one instance for each of the three fundamental gates (i.e. H, C-X and T ); then this task can be accomplished putting in the register state up to L − 1 idle qubits, which never contribute to the intended computation and on which can be vented all the unwanted operations. However notice that, a priori, Bob’s operation are not correct, as they are not applied to the computational state ρ, but to a ciphered version of it.
3. When the quantum register comes back to Alice, she can choose Pauli X and Z operations in such a way that they correct the output of the computational step, just as if Bob had applied his gate directly to the unciphered quantum register ρ. This is shown explicitly in Figs. 2.2 2.3 and 2.4, respectively for the H, C-X and T gate (taken from [26]). Notice that the scheme for the H gate works because the identity HX = ZH holds, and so we have also XHZ = ZHX = H. For similar reasons, also the other two circuits can be shown to be correct.
For sake of clarity, in this exposition part (1) and part (3) have been split up, but in a real implementation the third part of a computational step and the first part of the next computational step would be meshed up in a single random choice of X and Z operations. Notice moreover that for encoding the T gate are necessary two
Figure 2.3: Scheme for implementation of a C-X gate with data privacy.
Figure 2.4: Scheme for implementation of a π/8 shift gate with data privacy. Here S = T2is a π/4 shift gate, the vertical line with two × symbols repre-sents a swap gate. Notice that an auxiliary idle qubit has to be used, the one initialized to |0i on the second line.
computational steps; this can be stated as the fact that the T gate belongs to the second Gottesman-Chuang hierarchy class, and this fact can be understood in terms of stabilizer formalism [23].
It is easy to see that the above specified protocol is cryptographically secure, allows to perform universal quantum computation and is correct. Notice in fact that the specification of the algorithm entirely depends on the choice of the swap operations on Alice’s side, while the ciphering depends only on the random choice of the operations XrjZsj. The cryptographic security depends on the fact that,
whatever attack strategy Bob will adopt, he will always get back from Alice a state which will be indistinguishable from the completely mixed state. The universality depends on the fact that the given set of gates (H, C-X and T ) is universal for quantum computation [1], and from the fact that at each step Alice can address one of these gates on a qubit of her choice, while venting all other unwanted gate operations on the idle qubits (moreover, this protocol easily allows to perform many operations at each step). The correctness is proved by direct inspection of the circuit diagrams shown for implementing the universal set of gates.
Notice that the basic version of the protocol does not allow Alice to know whether Bob is collaborative or not, nor even if the computation is proceeding correctly or if the noise has overthrown the state control. This can be easily addressed if we allow Alice to perform also quantum measurements and to introduce some decoy qubits, which does not actively enter the computation, that can measured at randomized
time steps to verify that the register state has not been corrupted. We will further elaborate on this topic in the description of the next protocol.
2.4.2
Giovannetti & al. protocol
This protocol (for the original article, see [28]) is based on the circuit model paradigm. It is assumed that exists a bidirectional quantum channel between Alice and Bob, and that Alice can perform single qubit state preparation and single qubit projective measurements. Bob has a quantum computer with a set of universal gates (take as usual H, C-X and T ), each of which can be applied to any qubit, if it is a single qubit gate, or to any pair of qubits, if it is a two qubit gate. If, for example, there are n qubits in the register, then Bob’s computer has n instances of H, n instances of T and n(n − 1)/2 instances of C-X, for a total of n(n + 3)/2 gates. So in general, we have a number of gates G (n), polynomial in the number of register qubits n, and we suppose that these gates are progressively numbered, and these numbers correspond to their addresses. It is assumed that these gates are addressable via a quantum Multiplexer (qMUX). A qMUX is a device which, as a quantum analog of the classical multiplexer, takes in a binary specification of a number k (in which the computational basis |0i, |1i is specified as the basis in which this binary encoding is performed), with 1 ≤ k ≤ G (n), and consequently activates the k-th gate, thus applying the operation Uk; plus, when a linear superposition of two binary encoding
of two number are sent in, say α|k1i + β|k2i, then a coherent linear superposition
of the gates is activated, αUk1 + βUk2; in short, Bob always applies the unitary
operationP
k|kihk| ⊗ Uk on the composite systemHaddress⊗Hregister. Namely, if
the address is in a state
|φiaddress=
X
j
αj|kjiaddress (2.8)
and the register is in a generic state |ψiregister, Bob performs the mapping
|φiaddress⊗ |ψiregister 7→
X
j
αj|kjiaddressUkj|ψiregister. (2.9)
Lastly, for this protocol we also need that the basic gates are a root of the identity (that is Ua
= I for some a ∈ N, and the smallest a > 0 for which the relation is satisfied is the order of the gate). This is indeed the case for our reference universal set of gates, as H and C-X have order 2 and T has order 8.
Now at each computational step Alice has to send only R = dlogG (n)e qubits (where the d e parenthesis mean integer approximation by excess), which form the address state which specifies the gate that has to be activated. Then Bob bounces back the address state to Alice, in order to allow her to check for the coherence of the algorithm and to verify that Bob has not attempted to read it.
If Alice uses only computational states, she will activate just a single gate at each step, thus encoding plain instructions which give a classical specification of the algorithm. To achieve blindness, Alice must intersperse her instructions with decoy queries. Decoy queries are obtained sending an address in a factorized state |ki = |b1i|b2i...|bRi in which each qubit, instead of being in the form |bji ∈ {|0i, |1i}
can also be states of the rotated basis |bji ∈ {|+i, |−i} (e.g. |ki = |1, +, −, 0, +i).
This allows Alice to obtain some possibility of superimposing queries corresponding to different classical addresses (e.g. |ki = |1, +, −, 0, +i is a superposition of 8 = 23
different addresses with equal amplitudes). Now the problem is, when she does this operation she entangles the address state she has sent with the register state, which would spoil the successive computation. To avoid this, Alice has to feed back the state 2 times, if the involved gates are only Hadamard or controlled NOT, or 8 times, if also phase shift gates are involved (and in general the least common multiple of the orders of the gates involved); at the end the overall operation (2 or 8 repetitions) is the identity on both the address and the register state.
The need of bouncing back the same address state multiple times does not weaken the security of the scheme. In fact, from Bob’s point of view this is just equivalent for him to seeing such states for a longer time: any coherent cheating strategy he can apply to the successive iterations of such states is equivalent to a strategy that he applies the first time he sees them. In other words, he does not gain any advantage from the fact that Alice is sending them multiple times. Bob may become entangled with Alice’s register during the protocol, but, importantly, he must be disentangled before Alice measures: he cannot retain any information by the time the computation ends.
Summarizing, if Alice knows that the qubits she received back from Bob are factorized from his computation qubits, she measures them and checks whether they match the decoy address state she had sent him. If, instead, she does not know it, she bounces back to Bob the address state (either twice or 8 times depending on the gates involved) and then she measures it. If her measurements disagree with the state she had originally sent him, she is certain that Bob is trying to extract information from her queries. So the privacy is obtained via cheat sensitivity, rather than via (cryptographically secure) encoding of the data.
The correctness and the universality of the algorithm entirely depends upon the choice of a universal set of gates. The protocol security is based on the fact that Bob does not know whether each single register sent by Alice is a decoy or a plain in-struction, and these are encoded into states belonging to non-orthogonal subspaces. Accordingly, any information that Bob extracts from the computational basis will disturb the superpositions of the decoy states [29], giving Alice a nonzero probabil-ity of identifying his cheat. This observation can be made rigorous by exploiting a formal connection between this scheme and the BB84 quantum key-distribution protocol, in a variant in which significantly different probabilities are assigned to the complementary coding bases {|0i, |1i} and {|+i, |−i} [30]. Specifically, this protocol can be recast as an instance of a non-balanced BB84 where Alice sends a secret key to herself using Bob as a quantum channel: she is transmitting and recovering sequences of |0i, |1i and of |±i states (sometimes plain instructions and sometimes decoys). Since Alice already knows the key she is sending to herself, she can easily determine whether Bob is disturbing the channel by reading the key, but Bob cannot do the same without having a non null probability of changing the register state. In the limit of a long computation (the number m of the steps tends to infinity), the probability that Bob has of passing all the tests will go to zero exponentially.
Notice however that in the unbalanced BB84 protocol found in reference [30], during the protocol only a random key is being exchanged along the quantum channel,
while in this Blind Computation protocol the relevant computational instruction are being encoded directly. The unbalanced BB84 protocol is guaranteed to work only if Alice’s sequence of {|0i, |1i, |+i, |−i} appears to Bob to be completely random, (except for the choice of the unbalance parameter between the computational basis {|0i, |1i} and the diagonal basis {|+i, |−i}), which in this context purports that Bob has no a priori information at all on which commands Alice will send him. However this is a very strong assumption in a cryptographic context and the security of the protocol breaks down if this condition is not met3.
2.4.3
Broadbent, Fitzsimons & Kashefi protocol
This protocol was first introduced in [31]; here the reference model is the Measure-ment Based Quantum Computation (MBQC). A pedagogical introduction to this topic is given in App. B. We assume moreover that the computation is performed on the brickwork graph state, also introduced in App. B. The computation, when no blindness constraints are imposed, is performed by initializing all the n × m qubits (n register qubits with m computational steps) in the |+i state (this is the qubit initial-ization); then entangling them pairwise via C-Z operations (this is the graph state initialization); and then performing n single qubit measurements at each computa-tional step (on all the qubits in a single layer of the graph state); the measurements are done by projecting each qubit, say in position (i, j), on the orthonormal basis states |+φ0
i,ji and |−φ0i,ji, where in general we define
|±αi ≡
1 √
2(|0i ± e
iα|1i) (2.10)
and conventionally we say that the measurement result is si,j = 0 if a |+φ0
i,ji state is
obtained, and is si,j= 1 if a |−φ0
i,ji is obtained (and this is the actual computation).
The real parameter φ0i,jis called the (corrected) measurement angle; these angles have to be chosen adaptively, depending on the previous measurements results (given by formula (B.16) in App. B), but for understanding the blind computing protocol all we need is that the angles φ0
i,j are deterministically obtained so that the desired
computation is carried out.
In this Blind Quantum Computing protocol, Alice must be able to prepare single qubits in arbitrary states, to perform (a modest amount of) classical computation, to generate true random numbers and to exchange classical information with Bob.
Now, to attain blindness, we assume that Alice performs the qubit initialization in states of the form |+θi,ji, where θi,j is chosen uniformly and randomly in [0, 2π)
for each qubit (i, j), and sends all these qubits to Bob. After that Bob performs the graph state initialization by applying all the needed C-Z operations. Notice that Alice’s initialization is equivalent to applying a Z rotation of angle θi,j to the
fiduciary states |+i; these operations all commute with Bob’s application of C-Z gates; as a consequence we have that all these random rotations can be compensated in the measurement phase, by simply adding θi,jto the measurement angles. Namely,
3For example, if Bob suspects that Alice wants to perform a specific computation, it may be
enough to check a small number of operations to prove or disprove the hypothesis with a high confidence level. So Bob can test his hypothesis with a reasonably small probability of being caught.
if {φ0i,j}i,jare the measurement angles which are used to perform the algorithm when
Alice has applied no random Z rotations, we have that using the measurement angles φ00i,j≡ φ0
i,j+ θi,j (2.11)
the same algorithm is effectively performed on the randomly Z rotated states. More-over we notice that the logical encoding:
(
|+θi,ji ↔ 0
|−θi,ji ↔ 1
(2.12)
can be inverted, by using a measurement angle with a π flip. It is customary (in informatics) to talk of positive and negative logical encoding. Explicitly the negative logical encoding corresponds to the assignment:
(
|+θi,ji ↔ 1
|−θi,ji ↔ 0.
(2.13)
Therefore performing measurements in the basis
δi,j≡ φ0i,j+ θi,j+ πri,j (2.14)
with θi,j ∈ [0, 2π) and ri,j ∈ {0, 1} holds the same computation as before, premised
that one knows the rotations of the initialized qubits and the logical encoding of the measurement results si,j ∈ {0, 1}. So to proceed with the computation, at each
computational step j ∈ {1, ..., m} (involving n register qubits) we have that: 1. Alice computes the measurement angles φ0i,j (for all register qubits 1 ≤ i ≤ n)
which may depend upon the previous measurement results sk,l, with l < j;
2. (∀i) Alice chooses n random bits ri,j ∈ {0, 1} and computes
δi,j≡ φ0i,j+ θi,j+ πri,j;
3. (∀i) Alice transmits the δi,j angles to Bob; Bob measures in the basis
{|+δi,ji, |−δi,ji};
4. (∀i) Bob transmits to Alice the result si,j∈ {0, 1};
5. if ri,j= 1 in step (2), then Alice flips the result si,j;
else, she keeps it as it is.
The protocol now delineated is correct and universal. The measurement angles are chosen so that they compensate the random initial Z rotations, while the π random rotation does not affect the computation as Alice can also compensate them (they just account to saying that Bob doesn’t know if the measurement outcomes have to be interpreted in the normal or in the reversed logical encoding). So its correctness and universality have been reduced to the correctness and universality of non-blind MBQC.
Moreover we have that the protocol above delineated is cryptographically secure. For the security proof, we notice that the unitary transformation U Alice wishes to
perform is encoded with a vector of angles ~φ = φ(1,1), ..., φ(n,m). In general, it
is reasonable to consider the scenario where Bob has prior information about the transformation U . Bob’s prior knowledge can be expressed as a non-uniform a priori probability distribution P (~φ) and, protocol is unconditionally secure, then the pos-terior distribution for Bob is equal to the prior one.
We will adopt the shorthand ι ≡ (i, j) for the following proof. Consider Bob as a malicious adversary which is not willingly to follow the protocol. This means that Bob is not forced to perform the prescribed measurements, and that he can fake the measurement results s0ι he has to send to Alice. However, Bob cannot make a
coherent superimposed attack strategy as he is forced to send classical information to Alice, and to receive other classical information (the angles δι) from her.
The Blind Computation protocol seems difficult to characterize, because it is adaptive. However, as far as blindness is concerned, the reported outcomes s0ι do not matter, as they only affect the correctness of the protocol. In fact, after that the pre-rotated qubits have been sent to Bob (assuming that the θι rotations are
fixed), the possible transcripts of the communication between Alice and Bob depend on two sequences of parameters: the (possibly faked) measurement results s0ι sent by Bob, and the (random) parameters rι chosen by Alice. The classical information
Bob is sending depends on rι⊕ s0ι; but since the parameters rι are random and
unknown to him, so are the values rι⊕ s0ι. Hence the responses Alice recovers are
independent from the choice of Bob’s reporting strategy s0ι. So we may fix, without loss of generality for the security proof
s0ι= 0. (2.15) Also, since the random parameters rι can be chosen in advance, the adaptive
struc-ture can be ignored, and we may set
φ0ι= φι. (2.16)
We can proceed in our analysis considering only one qubit at a time. In fact, it is clear that to infer the value of φιat a specific site ι, no information can be extracted
about it from the measurement angle δκ and the state qubit |+θκi for any κ 6= ι
4.
Now, depending on the value of rι, for each ι ∈G Alice has sent to Bob one of the
following two states:
1. rι = 0 ⇒ δι= φι+ θι and so Alice has sent to Bob the state:
|+θιi ≡ 1 √ 2(|0i + e iθι|1i) = √1 2(|0i + e i(δι−φι)|1i) (2.17)
2. rι = 1 ⇒ δι= φι+ θι+ π and so Alice has sent to Bob the state:
|+θιi ≡ 1 √ 2(|0i + e iθι|1i) = √1 2(|0i − e i(δι−φι)|1i). (2.18)
4Notice however that if Bob has some a priori information on the algorithm that Alice may
be performing, i.e. on the measurement angles, then by bayesian updating it is possible that the posterior probabilities assigned on the angle φιis changed by information acquired on the angle φκ,
as they are no more independent random variables. This however does not affect the correctness of the proof.
But rι is uniformly random and unknown to Bob; so as far as he knows, his state
is given by the equally weighted classical mixture of the above two states, which is the completely mixed state. Hence Bob cannot recover any information from it, and this completes the proof.
Many interesting features can be achieved within this framework of Blind Quan-tum Computation. First, it is possible to attain universal quanQuan-tum computation even if the protocol is restricted to modulo 8 angles, both in qubit preparation and in projective measurements. Second, the protocol can be made fault tolerant, by implementing an error correcting code upon it; this is remarkable, it means that Bob is able to detect errors even without knowing which computation he is performing [31]. Third, the notion of cryptographic security can be refined to account also for approximate security, which then allows to perform the computation also in a realis-tic scenario where Alice cannot prepare single qubits, but only weak coherent pulses, as happens with most-real world photon emitters [32].
2.4.4
Morimae & Fujii protocol
Now we come to the simplest, most versatile and economical Blind Computation protocol, first proposed in [33]. In this protocol, also based on the MBQC paradigm, it is only needed that Alice can perform single qubit measurements. The whole point of the protocol is that Bob prepares the graph state in a standard fiduciary form (the difficult task in this model resides in performing the C-Z entangling gates), sends it to Alice, who then performs the required single qubit measurements, without ever telling anything to Bob.
There are several reasons why this protocol is much stronger than any of the previous ones:
1. In this protocol Blindness is guaranteed by the no-signaling principle. In fact Alice only transmits to Bob, at the beginning of the protocol, the space and the time required for the computation (i.e. the dimensions of the graph state). After that Bob does not get a single bit of information from Alice; so, as far as he knows, Alice could even dump all the qubits received, and he would not be able to tell the difference. It is important to stress that having such a simple proof of security allows it to be more easily applicable; protocols which involve complicate proofs of security may always bear errors or hidden assumptions, which would make it inapplicable in a realistic scenario. In this case even a layman, unaware of the laws of quantum mechanics, may trust that this protocol is blind, as long as he believes in the no-signaling principle.
2. Indeed this protocol works even against a server which is allowed to perform operations prohibited by the laws of of quantum mechanics! Even if Bob is able to clone a single quantum state, or to discern perfectly non orthogonal quantum states, he still cannot recover information as long as the no-signaling principle is valid (and Bob has not put a bug in Alice’s laboratory!); in general, this principle is more fundamental than quantum theory [34].
3. It can be immediately applied to any variant of MBQC as long as it uses a fixed graph state which supports universal quantum computation. If a particularly
good configuration for the graph state is found out, this protocol will be ap-plicable to it. Any error correcting code could be applied directly by Alice, as they require only small classical communication capacity, without any further modifications (in contrast to the scheme of [31], in which the error correcting codes have to be modified to apply them to a Blind computation).
4. The graph state has not to be entirely prepared in advance and stored for a long time (which may be difficult, in presence of noise-induced decoherence). In fact, the graph state can be produced by Bob storing at most two layers (cor-responding to two computational steps) at any time, performing entanglement operations among them, and then sending half of them to Alice.
5. In all the previous protocol, Alice and Bob had to wait for the answer of the other party at each time step to proceed with the protocol. If they happen to be very distant, or the transfer line happens to be very slow, this may amount to an unsustainable amount of time that has to be waited for receiving the an-swers. In this case, Alice is never asked to send any feedback, so Bob can simply stream his data to Alice, making the communication much more straightfor-ward (anyway, if too many qubits are lost along the quantum channel, Alice may wish to ask Bob for more supplies, but also this problem can be easily accommodated).
6. This is arguably the most economical protocol, regarding the resources that Al-ice is asked: she is not asked to have a cryptographically secure random number generators; and she does not have to own a reliable source of single qubits. For example, at present in experimental quantum optics, photo detectors are more efficient and easier to operate than photo emitters.
7. Lastly, in this scenario Alice can perform the computation in a secure manner even when the measurement device has not been produced by her and is not guaranteed to be secure; as a matter of fact the measurement apparatus may have been provided even by Bob! As long as there is a firewall which blocks all the information routed outside the laboratory, even if the measurement device is mischievously collecting information, it will not be able to transfer it to its programmer.
2.5
Cost analysis
Now we address the question of what are the resources required in order to perform a Blind Quantum Computation Protocol. We specifically ask what additional resources are necessary, in contrast to the case where no Blindness requirement is imposed, and compare the strength and the efficiency of the Blind Quantum Computation Protocols introduced in Sec. 2.4.
First, the protocols assume different quantum devices on Alice’s side. The greater the quantum operational power she is granted, the easier is for her to hide the com-putation; at limit, if she had a fully operational quantum computer, she would not need Bob’s help. So this is a very relevant property of a protocol. But there is only a partial ordering (and no total ordering is possible), in assessing the computational
