Formale Si herheit in der QuantenkryptologieFormal Se urity in Quantum CryptographyStudienarbeit von Dominique UnruhInstitut für Algorithmen und Kognitive Systeme (IAKS)Universität KarlsruheBetreuer: Prof. Dr. Thomas BethDr. Jörn Müller-Quade

CONTENTSContentsContents 31 Introdu tion 51.1 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Abstra t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 toki lili . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.4 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.6 An intuitive approa h to se urity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.7 Quantum se urity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Notation and elementary de�nitions 92.1 General onventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 Linear operators and ve tor spa es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.3 Density matri es and probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4 Indistinguishability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.5 Symbols and tapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Quantum Ma hine Models 143.1 Intera tive Quantum Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.2 Exe ution trans ripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.3 Running time of an IAQS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.3.1 Running time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.3.2 Polynomial IAQS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.3.3 Terminating IAQS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.3.4 Relative polynomial running time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.4 Classi al Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.5 Turing ma hines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.5.1 Intera tive quantum Turing ma hines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253.5.2 Intera tive lassi al Turing ma hines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.5.3 Classi al interfa es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.6 ITM and partial ITM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 Quantum Network Models 314.1 Quantum networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.2 Time evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.3 Classi al quantum networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 Adversarial Communi ation 355.1 Adversarial quantum network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355.2 S heduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355.3 Adversary types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.4 Proto ols and adversarial ommuni ation frameworks . . . . . . . . . . . . . . . . . . . . . . . . 405.5 Output of an AQN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416 Basi Se urity Model 437 Extensions 457.1 Multi-phase proto ols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457.2 Temporary assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457.2.1 Available primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467.2.2 Corruption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467.2.3 Computational power . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467.2.4 Known algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477.3 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497.4 Passive orruption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503

CONTENTS7.5 Cheat Dete tion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507.6 Se urity with Partial Abort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517.7 Pliable Se urity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517.8 Adjustable Se urity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527.9 Corruption noti� ation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527.9.1 Adaptive vs. stati se urity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 538 Relation of lassi al and quantum se urity 559 Composability 579.1 Simple Composability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579.2 Con urrent Composability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599.3 Universal Composability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62A Formal details 63A.1 Lemma 3.15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63A.2 Sto hasti vs. hard relative polynomial running time (se tion 3.3.4) . . . . . . . . . . . . . . . . 66A.3 Stri t polynomial running time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66A.4 Time evolution of a quantum network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67A.5 �MG �U �MG = �MG �U (se tion 5.5) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71A.6 Lemma 3.30 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71B Keyword Index 74C Symbol Index 78D Referen es 80

4

1 INTRODUCTION1 Introdu tion1.1 ZusammenfassungDas Ziel dieser Arbeit ist es, das Konzept der formalen Si herheit in die Quantenkryptologie einzuführen. Zudiesem Zwe k stellen wir ein neues Si herheitsmodell vor, wel hes u. a. ein Modell für die Kommunikation inQuantennetzen enthält. Wir werden dabei verstärkt Wert auf formale Details legen, um aufzuzeigen, wel heProbleme bei einer formalen De�nition von Si her in der Quantenkryptologie auftreten können.Auf diesem Modell aufbauend werden wir einige grundlegende Eigens haften von Quantenprotokollen ana-lysieren:� Lassen si h Quantenprotokolle modular zusammensetzen?� Bleiben klassis h si here klassis he Protokolle si her, wenn man sie in einem Quanten-Umfeld betra htet?Beide Fragen werden wir im groÿen und ganzen positiv beantworten. Die Diskussion dieser Themen (undinsbesondere die dabei vorkommenden Beweise) werden weniger formal sein, da die zugrundeliegenden Kom-munikationsprozesse so komplex sind, daÿ dies den Rahmen dieser Arbeit bei weitem sprengen würde.1.2 Abstra tThe obje tive of this work is to introdu e the notion of formal se urity into quantum omputation. In orderto a hieve this, we introdu e a new se urity model, ontaining a quantum ommuni ation model. We will laysome stress on formal details to show whi h are the problems arising in a formal de�nition of quantum se urity.Based on this model we will analyse some basi aspe ts of quantum proto ols:� Are quantum proto ols omposable?� Do lassi ally se ure lassi al proto ols stay se ure in a quantum environment?Both questions we will answer by and large positively. This dis ussion (and espe ially the proofs) will be lessformal, be ause of the omplex nature of the underlying ommuni ation pro esses.1.3 toki liliwan li ken lukin lon pali ni e ni: sona pi lukin ala pi wan lili li pona ala.taso tenpo la toki pali li pona, en toki pali ante li pona, kama la toki pali tu pi kama wan li kin pona.tenpo la wan lili ala la toki pali pi wan lili ala li pona, kama la wan lili la toki pali ni li kin pona.1.4 ResumoLa elo de tiu � i laboro estas la enkonduko de formala kon epto de sekure o en kvantuma kriptogra�o. Tiu eleni prezentos novan sekure modelon, kiu enhavas i. a. modelon de kvantuma komunikado. En nia diskuto niforte ak entos formalajn detalojn por montri, kiaj estas la problemoj aperantaj je formala de�no de kvantumasekure o.Uzante tiun modelon, ni esploros kelkajn elementajn e ojn de kvantumaj protokoloj:� �Cu kvantumaj protokoloj estas kunmeteblaj?� �Cu klasike sekuraj protokoloj restas sekuraj en kvantuma � irka�uajo?Al amba�u demandoj ni respondos pli malpli jese. Tiuj lastaj diskutoj estos malpli formalaj pro la kompleksanaturo de la bazaj komunikadpro esoj.1.5 OverviewIn the �rst hapter (this one) we give an overview of this work and introdu e our modelling of se urity togetherwith an intuitive approa h for its justi� ation.In the se ond hapter we dis uss some mathemati al notation and elementary de�nitions. This hapteris not dire tly related to ryptologi al issues, but gives us some basi tools to operate with in the following hapters. 5

1.6 An intuitive approa h to se urity 1 INTRODUCTIONThe third hapter introdu es the quantum ma hine model used throughout this work. We introdu e somemost abstra t ma hine model, and thereafter present intera tive quantum Turing ma hines. We will dis uss runtime and termination issues with a view to the intera tive nature of these ma hines. Finally we will introdu e lassi al ma hines and ma hines with lassi al interfa es (i.e. ma hines whi h are internally quantum, butrestri ted to do lassi al ommuni ation).In the fourth hapter the quantum networks are introdu ed. These are rather general network models,we do not even give a spe i� s heduling me hanism there. We do however already implement primitives formessage transfer and orruption there.This simple model is then extended in the �fth hapter, where we introdu e the adversarial quantum net-work. Here issues like s heduling, adversaries, environments, fun tionalities and primitives are implemented.We will give some simple de�nitions like that of proto ols and ommuni ation frameworks to simplify formu-lations later on. Further several types of adversaries are dis ussed, like well-formed and non-blo king ones. Atthe end, we show how the environment in a quantum network generates an overall output bit.In the sixth hapter the se urity model is then �nally presented. It omes in di�erent �avours, like absoluteor approximative se urity (depending on whether we allow no or only negligible distinguishability probabilities),polynomial se urity, se urity with bounded risk (where we an give a pre ise bound on the probability ofdistinguishability).The seventh hapter then introdu es extensions to the se urity model in a less formal way. These aremulti-phase proto ols, temporary assumptions on available primitives, orruptibility, omputational powerand knowledge of algorithms, onstraints on the se urity, heat dete tion, proto ols with partial abort, pliablese urity, adjustable se urity and orruption noti� ation.In the eighth hapter we prove, that a lassi al proto ol, whi h is proven to be se ure when assuming lassi al ommuni ation, is also se ure assuming quantum ommuni ation.The ninth hapter handles omposability issues. Simple and on urrent omposability is dis ussed andproven, and put together to a notion of universal omposability.In appendix A some rather formal de�nitions and proofs are given, whi h would have enlarged the mainbody of this work unne essarily.1.6 An intuitive approa h to se urityWhen talking about se urity, we mostly do not exa tly (i.e. formally) know, what this means. In parti ular ases, e.g. en ryption, we have spe ialised de�nitions, but in the most general ase there where for a long timeonly an ever growing list of properties a se ure system had to provide, e.g. priva y, fairness, and many others.There do however exist more general approa hes, whi h are based on the omparison of some real proto oland an ideal one, the latter being per de�nition assumed to be se ure. Su h a system we will introdu e, basedon the ideas in [Can00b℄.The basi idea is a follows: Assume, that we have some given ryptographi appli ation, and we an spe ifysome referen e proto ol or fun tionality F , whi h does implement the wanted behaviour in a se ure way. Of ourse, we do now have to design that fun tionality, but this is usually easier than designing the proto ol, sin ewe do not have to bother with details like inse ure ommuni ation, or who should arry out omputations et .,sin e F an be regarded as some trusted party.Then if we a ept, that the fun tionality is se ure (though not ne essarily feasible), we an de�ne, thatsome proto ol � is as se ure as F , if repla ing F in any situation does not result in any disadvantage forany person (ex ept the adversary, of ourse). But how do we formalise situations and how do we formalisedisadvantages? We simply introdu e the on ept of the environment and the adversary. The environmentis something, whi h does intera t with the proto ol and the adversary as a bla k box and at the end mayde ide, whether some harmful thing has happened. When we quantify over all possible environments (possiblerestri ting the omputational power), and for no environment (i.e. in no situation) some harm has happenedusing � whi h would not have happened using F , too, then repla ing F by � is learly a sensible ourse ofa tion, at least it will surely do no harm, thus � an be onsidered as se ure.The pre eding explanation still has some great drawba k: An adversary (for whi h the proto ols internalsare no bla k box, of ourse) ould simply vary its output depending on whether we use � or F . Then theenvironment would simply onsider the output �� is in use� as harmful, and suddenly � would be inse ure.But, when onsidering our requirement, that everything harmful, whi h an happen using �, an also happenusing F , we an reasonably interpret it as everything harmful, whi h an happen using � with some adversaryA, an also happen using F with some (other) adversary S. If we a ept this formulation, whi h implies, thatin any situation the adversary may freely hoose its strategy to be as �harmful� as possible, we get the se urityde�nition whi h we will develop and examine in this work.6

1 INTRODUCTION 1.7 Quantum se urityOne simpli� ation we will still introdu e: So far we have required, that using �, we get at most thatmu h harm as when using F . In fa t, we an hange this de�nition su h, that we require that we get thesame amount of harm. This simpli�es the de�nition and is in fa t equivalent, sin e if one environment de�nessomething as harm, then some other environment ould de�ne the inverse as harm, su h bounding the amountof harm from both sides and resulting in a laim of equality. After introdu ing this simpli� ation, the word�harm� is of ourse inadequate, so we will use the more neutral notion of the output bit of the environment.So if we put these onsiderations together, we get a �rst de�nition sket h, we runs in the following lines:For any adversary A, there is some adversary S, su h that for any environment E , the one-bit output of Ewhen running with A and � is indistinguishable from that of E running with S and F .Here of ourse the notion of indistinguishability leaves us some s ope of interpretation, we an e.g. requirethe distributions of the outputs to be identi al, or we an require them to be just very lose to ea h other. Inthe latter ase, if we do not want to introdu e some �xed and arbitrary bounds, we need to introdu e somese urity parameter k, whi h is given to all parti ipants in the above experiment, and whi h may than be aparameter to some negligible fun tion bounding the statisti al distan e of the two distributions.We an now take the above de�nition and try to generalise it: In the real proto ol we might have a essto some primitives, and instead of the ideal fun tionality, we might want to use a whole referen e proto ol %(the ideal proto ol), with whi h we want to ompare �. This leads to the following framework: When runningour experiment, we do not only have environment, adversary and proto ol or fun tionality, but we haveenvironment, adversary, proto ol, and fun tionalities. Here the environment an ommuni ate only with theadversary and the proto ol, the proto ol's parties may ommuni ate with everyone ex ept dire tly with ea hother (for this purpose, fun tionalities must be used, whi h possibly may leak information to the adversary orhave other expli itly designed drawba ks), the fun tionalities may ommuni ate with the adversary and theproto ol, and the adversary may �nally ommuni ate with everyone. The ase previously dis ussed, wherewe ompare � with a fun tionality F is realised by using a dummy proto ol %0, whi h simply passes any ommuni ation with the environment to and from F . As we an see, we do not need a spe ial de�nition ofprimitives, the notion of fun tionalities is reused instead. Therefore we will use the words fun tionality andprimitive synonymously throughout this work.Some point whi h we have not yet justi�ed, is why the adversary may not depend on the hoi e of theenvironment. For this, we do not have any intuitive justi� ation, but our hoi e is justi�ed by two fa ts:First, it is the stri ter one, se ondly it seems ne essary for our proof of omposability, whi h represents a veryuseful feature, and without whi h a se urity model might even be onsidered worthless (see the introdu tionof hapter 9).1.7 Quantum se uritySin e we are going to onsider quantum se urity in this work, we have to spe ify, what kind of quantum omputation and ommuni ation we allow. The following points are to be lari�ed:� What kind of messages an be transmitted?� Is the s heduling of quantum nature?� Is the fa t, whether a message has been send or not, quantum?� What about erasure?What kind of messages an be transmitted? In this work we will allow any superposition of tape ontentsto be transmitted. This means espe ially, that for an in oming message we do not know without measuring,how long it is, taking any �nite part of the message might introdu e some information loss. We use thismodelling due to the fa t, that e.g. some harmoni os illator has an in�nite number of base states, thoughhigher ones usually have rapidly de reasing amplitude. Therefore en oding the os illator's state in a �nitenumber of qubits ne essarily involves a measurement.Is the s heduling of quantum nature? We have two options here. Either the transmission of the token tosome ma hine may be lassi al, or several ma hines may have the token at the same time in superposition.The latter ase is of ourse more general, but it would make the model mu h more ompli ated, espe ially theproofs in hapter 8 and hapter 9 make use of the lassi al nature of the s heduling.1 Therefore we hoose a lassi al s heduling.1Though we do not know, whether modelling the s heduling quantumly would invalidate the results in those hapters.7

1.7 Quantum se urity 1 INTRODUCTIONIs the fa t, whether a message has been send or not, quantum? Here we model the simpler fa t, wheresending a message is a lassi al event. The ase, where a message may be sent and unsent in superposition,may however be simulated by introdu ing a spe ial message ?, meaning �no message�.What about erasure? Often it is required, that a proto ol is se ure, even if the parties are not able to erasedata, i.e. the adversary learns all past states upon orruption. In the quantum ase, however, this is not soeasy to model, sin e making a opy of the ma hine's state after ea h time step would violate the impossibilityto lone quantum states. So we may try to get some weaker ondition, where we want to disallow the parties tounne essarily loose information, i.e. the states should only underly reversible transformations or measurements,whose out omes are stored and a essible to the adversary after orrupting the party. We have taken are toimplement this ondition in our model, but it nevertheless seems to be of no use, sin e a ma hine an alwaysdo the following to erase information: Let's say it has a lassi al bit. Then it applies a Hadamard transformto it and afterwards de ides whether to pass the token to the next party depending on the value of that bitin the standard basis. Sin e the transmission of the token is a measured event, the state of the qubit is now ompletely random and its prior state lost. Possibly some more useful notion of impossibility of erasure ouldbe formulated, if we would model the transmission of the token to a quantum event, but this is�a ording tothe opinion of the author�improbable.

8

2 NOTATION AND ELEMENTARY DEFINITIONS2 Notation and elementary de�nitions2.1 General onventionsThis se tion is intended to avoid some possible onfusion resulting from di�erent onventions in the use ofelementary mathemati al notation. It is probably unne essary to read it unless there is some onfusion aboutformal details. When an un lear symbol appears in the text, please onsult the symbol index in se tion A.6.The set N onsists of the natural numbers without zero (i.e. N = f1; 2; 3; : : :g), while N0 onsists of thenatural numbers in luding zero (i.e. N0 = N [ f0g = f0; 1; 2; : : :g). The real numbers are denoted R, thenon-negative real numbers are R�0, the positive real numbers R+, and the omplex numbers C.When writing a produ t in non- ommuting semigroups using forms like e.g. Qni=0 or Q1i=0 or some otherform implying some ordering, we will assume that the fa tors oming �rst in that ordering appear leftmostin the produ t, e.g. Q5i=1 Ui = U5U4U3U2U1. We use this onvention, sin e when writing the su essiveappli ation of some operators, we do not want to write Q1i=5 Uiji, but Q5i=1 Uiji.2.2 Linear operators and ve tor spa esWhen talking about operators, we always assume linear ones, when talking about proje tions, we assumeorthogonal ones. Bases are always orthonormal throughout this work.Let 1 denote the identity.When an operator M operates on some ve tor spa e AB, we say M operates read-only on A, if for anyj�i 2 A, ji 2 B it is Ajij�i = jij�i for some j�i 2 B.We say, an operator M on A B operates on A as the identity, if M has the form M = 1 ~M , where 1operates on A and ~M on B.2.3 Density matri es and probabilitiesIn this se tion we will re all the on ept of density matri es and also introdu e the generalised density matri es,the latter just being a formal tool to fa ilitate notation.De�nition 2.1: Density matrixA density matrix % in a Hilbert spa e H is an operator whi h an be de omposed as follows:2% =Xi2I jiihijwith some ountable set I and ve tors jii 2 H satisfyingXi2I jii 2 = 1 (1)A density matrix is often also alled a mixed state, while a pure state designates the spe ial ase of jihj(ji 2 H).For onvenien e, we further de�ne %(ji) := jihj. �A density matrix an be thought as a dis rete probability distribution over states in H, sin e all informationwhi h ould be extra ted about that probability distribution an also be extra ted from a density matrix byperforming measurements (even if we have an in�nite number of samples). To onvert a probability distributiongiven by some probabilities p(jii) to a density matrix, simply de�ne % :=Pi p(jii)jiihij.You an then extra t the probability of the out ome of a measurement on % = Pi2I jiihij given by aproje tion P by al ulatingPi2IkP jiihijk2. Note that though the de omposition is not unique, the resultsof that al ulation are independent of the parti ular de omposition.If you have an observable M , whi h is given by M = Pj mjPj , you an get the expe tation value E ofM -measuring % without �nding a de omposition, simply as E = trM%.For onvenien e, we introdu e the generalised density matri es, whi h are density matri es without ondi-tion (1). Thus we have:De�nition 2.2: Generalised density matrixWe all % a generalised density matrix if there is a density matrix ~% and non-negative real number �, su h that% = �~%.2Note that this de omposition is not ne essarily unique. 9

2.3 Density matri es and probabilities 2 NOTATION AND ELEMENTARY DEFINITIONSThen we all � the intensity of %, and if � 6= 0 we say ~% is the normalised density matrix of %. �Note that � = tr % and ~% = %� , so the intensity and the normalised density matrix are well-de�ned. Ageneralised density matrix is a density matrix if and only if its intensity is 1.The idea behind this generalised density matri es is to model states, whi h appear only with a givenprobability. E.g. if you have a polarised photon, whi h is emitted with a probability �, you ould model itusing a density matrix over a spa e ontaining basis ve tors jli, j$i and jno photoni. This does also modelthe possibility, that there may be transformations on that spa e whi h e.g. swap the amplitude of jli andjno photoni. If we want to model the simpler ase, that the fa t whether the photon is present or absentis lassi al, we write down the probability � of that photon being present, together with its density matrix~%. Or we simply write % = �~%. This form has the advantage, that we an now simply al ulate on thematri es, e.g. when there is probability �1 for a photon with density matrix %1, and a probability �2 foranother indistinguishable photon with density matrix %2, then the overall generalised density matrix is simplygiven by �1%2 + �2%2.By using the following de�nition we an even reuse the above inter onne tions between probabilities anddensity matri es.De�nition 2.3: Generalised probability distributionA generalised (dis rete) probability distribution p on I is a mappingp : I ! R�0;where I must be a ountable set, and Pi2I p(i) 6= 0. �Note that for Pi2I p(i) = 1, a generalised probability distribution is a (dis rete) probability distribution.Like with the generalised density matri es before, we have a natural addition on generalised probabilitydistributions.To fa ilitate writing, we further introdu e the following fun tion:De�nition 2.4: Density matrix operatorIf X is a proje tor P or an observable M or a measurement3 fPi; i 2 Ig, or a unitary transformation U ,operating on the Hilbert spa e H, then we de�ne the density operator �X operating on the generalised densitymatrixes in H to be respe tively given by� in ase of a proje tor P : �X% := P%P y,� in ase of an observable M = Pi �iPi with proje tions Pi onto the di�erent eigenspa es of M : �X% :=Pi Pi%P yi ,� in ase of a measurement fPi; i 2 Ig: �X% :=Pi Pi%P yi ,� and in ase of a unitary transformation U : �X% := U%U y. �Note that one has to know here, of what type a given matrix X is before being able to al ulate �X , e.g. X :=( 1 00 0 ) ould be a proje tion or an observable, in both ases yielding di�erent results for �X .If % is a density matrix and X is not a proje tion, then �X% is a density matrix again.The density matrix operator �X an be interpreted as giving the generalised density matrix, that is obtainedwhen applying X to the state and ignoring an eventual measurement out ome. For proje tions, the intensityis multiplied with the probability that the state is measured to be in the image of that proje tion, in the other ases the intensity is not hanged. E.g. if we have a photon polarised in a random dire tion (i.e. having densitymatrix 1), then measuring in the fjli; j$ig-basis yields the mixed state 12 jlihlj+ 12 j$ih$j, whi h is exa tlywhat gives �M1, where M shall be our measurement.3That is a ountable set of proje tors Pi with PiPj = 0 (i 6= j), ea h asso iated with some other measurement out ome i.10

2 NOTATION AND ELEMENTARY DEFINITIONS 2.4 Indistinguishability2.4 IndistinguishabilityIn this se tion we will introdu e the notion of the indistinguishability of two families of sto hasti variables.We begin by de�ning what fun tions (of the se urity parameter) are so small, that they are�for pra ti al onsiderations�virtually zero:De�nition 2.5: NegligibilityWe say some fun tion " : N ! R�0 is negligible, if for any 2 R+ there is an k0 2 N, s.t. "(k) � k� for allk � k0. �And an alternative and stri ter de�nition isDe�nition 2.6: Exponential negligibilityWe say some fun tion " : N! R�0 is exponentially negligible, if there is a 2 R+ and a k0 2 N, s.t. "(k) � �kfor all k � k0. �Of ourse, exponential negligibility implies negligibility.We �rst de�ne indistinguishability with respe t to a given lass of bounds:De�nition 2.7: Sto hasti indistinguishability with respe t to BIf B is a set of fun tions N! R�0, then we say two sequen es of sto hasti variables (Xk)k2N, (Yk)k2N havingvalues in some ountable set A are sto hasti ally indistinguishable with respe t to B, if it is there is an " 2 B,s.t. 12Xa2AjP (Xk = a)� P (Yk = a)j < "(k)for all k 2 N. �Note that we require the statisti al distan e (the left hand side of the equation) to be bounded by " for all k,not only for su� iently large ones. So if it is needed to relax this onstraint only to hold for su� iently largek, just de�ne ~B onsisting of all fun tions whi h are almost everywhere equal to some fun tion in B and thentalk about ~B-indistinguishability instead of B-indistinguishability.De�nition 2.8: Sto hasti indistinguishabilitySto hasti indistinguishability means sto hasti indistinguishability with respe t to B, where B is the set of allnegligible fun tions. �De�nition 2.9: Exponential sto hasti indistinguishabilityExponential sto hasti indistinguishability means sto hasti indistinguishability with respe t to B, where B isthe set of all exponentially negligible fun tions. �Again exponential sto hasti indistinguishability is stronger than sto hasti indistinguishability, but we will usesto hasti indistinguishability throughout this work, due to the following reasoning: The indistinguishabilityis used e.g. to model the fa t, that we annot distinguish some probability distributions with some given prob-ability using a reasonable number of samples. Sin e a reasonable number usually means a polynomial one, weget polynomial bounds for the statisti al distan e, i.e. indistinguishability, not exponential indistinguishability.2.5 Symbols and tapesIn modelling the on�gurations or our ma hines and networks, we will work very mu h with symbols andtapes. In this se tion we will de�ne them and give a short list of some elementary operations on them.The most elementary data type is the symbol, it is an element out of some set �, of whi h we only spe ify,that it ontains at least the symbols #, 0, 1. We all # the blank symbol or simply the blank. We assumefurther, that there is some numbering of the symbols, i.e. that ea h symbol is asso iated with some number inf0; : : : ;#�� 1g. We further assume that # is asso iated with the number 0.A tape does, of ourse, not only hold a single symbol, but sequen es of those. There are two importantsets of su h symbol sequen es:De�nition 2.10: Tape ontentA tape ontent t is a fun tion t : Z! �, where t = # almost everywhere.The empty tape ontent # is that tape ontent t, whi h is # everywhere.The set of all tape ontents we write �Z�n. �De�nition 2.11: StringA string s onsists of a length l 2 N0 together with a fun tion s : f1; : : : ; lg ! � n f#g.11

2.5 Symbols and tapes 2 NOTATION AND ELEMENTARY DEFINITIONSIf l = 0, we talk about the empty string #.The set of all strings we write ��. �The strings have a natural embedding into the tape ontents. A string s of length l an be onsidered as atape ontent t with t = s on f1; : : : ; lg and t = # on Z n f1; : : : ; lg.At some points in this paper we will expli itly spe ify some strings ontaining the symbols a�z (they arere ognisable as string literals, be ause they are typeset with a typewriter font). These literals stand for somearbitrary but �xed strings, whi h do not ontain the symbol 0.When talking about tapes in this paper, we mean variables whi h an ontain tape ontents or strings, itis therefore always ne essary to spe ify, what kind of data a given tape may hold.On tape ontents we have an operationY to interleave an unbounded number of tape ontents into a singleone. (We interleave an in�nite number, but almost all of them must be empty, otherwise the resulting tape ontent will have an in�nite number of non-empty ells.)This is done by dove-tailing the ells of the tape ontents a; b; ; d; : : : into one tape ontentY(a; b; ; d; : : :)whi h looks as follows (spa es are for legibility only):: : : ; d�1; �2; b�3; a�4; �1; b�2; a�3; b�1; a�2; a�1; a0; a1; b0; a2; b1; 0; a3; b2; 1; d0; : : :Here a0 is at index 0.Formally this is:De�nition 2.12: Interleaving tape ontents (mapping Y)Let (t(n))n2N be a family of tape ontents with t(n) = # for almost all n 2 N. Then the interleaved tape ontents ( i)i2Z :=Y(t(1); t(2); t(3); : : :) is a tape ontent de�ned by f(n;i) := t(n)i , wheref(n; i) := ( (n+i)(n+i�1)2 + n� 1; if i � 0;� (n�i�1)(n�i�2)2 � n; if i < 0: �Note that Y is bije tive, and that the index f is e� iently omputable and its value polynomial in its inputs.For strings we have a similar operation, the stru tured on atenation. It on atenates a �nite number ofstrings, together with information allowing to extra t those strings from the result again.De�nition 2.13: Stru tured on atenation (mapping Æ)Let s1; : : : ; sn (n � 0) be some strings. Then the stru tured on atenation Æ(s1; : : : ; sn) of these strings isde�ned as follows:For any string s with length l it isÆ(s) := s � 01l and for strings s1; : : : ; sn it isÆ(s1; : : : ; sn) :=Æ(s1) �Æ(s2) � � �Æ(sn);where � denotes the normal on atenation of strings, i.e. writing the strings dire tly one after another. �Note that the on atenation is inje tive, from any image the number of inputs and the i-th input an bee� iently al ulated. The output is guaranteed to have at least one 0 in it, i.e. it an be distinguished fromstrings over � n f#; 0g, in parti ular from string literals.The stru tured on atenation is not asso iative, we annot get results likeÆ(a; b; ) =Æ(Æ(a; b); );so we need some operation N that has the following property:N(Æ(s1; : : : ; sn); sn+1) =Æ(s1; : : : ; sn; sn+1) (2)This ondition ompletely spe i�es N on imÆ���, but we will need a de�nition on the whole domain �����,whi h now follows:De�nition 2.14: Stru tured append (mapping N)Let s; t be strings. Then let the stru tured append be de�ned byN(s; t) := s �Æ(t);where � is, as before, the normal on atenation. �12

2 NOTATION AND ELEMENTARY DEFINITIONS 2.5 Symbols and tapesThis de�nition satis�es (2) andN is inje tive. Note that it is important that we have de�nedÆ(s) := s�01l, notÆ(s) := 1l0 � s, sin e in the se ond ase we would only have inje tivity on imÆ���, e.g. N(111101110; 0) =N(11110; 100) = 111101110100.It an be e� iently he ked, whether s 2 N(imÆ���).Though there is a natural embedding of strings into the set of tape ontents, there is no su h in the otherdire tion. From time to time however we need to regard some tape ontent as a string, i.e. we need a fun tionK : �Z�n ! ��, whi h satis�es K(s) = s for s 2 ��. We ould de�ne K always to yield some �xed value fornon-strings, but then K ould not be implemented by Turing ma hines any more, sin e this would imply to he k, whether a tape ontent is a string, whi h is impossible for Turing ma hines. So we hoose the followingapproa h, whi h is easily implementable using Turing ma hines:De�nition 2.15: String extra tion (mapping K)For any tape ontent (ti), let l � 0 be minimal with tl+1 = #. Then K((ti)) is the string t1; : : : ; tl. �Due to the reversible nature of quantum omputation, the XOR operation is used very often, be ause of thefollowing properties� Asso iativity: (a� b)� = a� (b� )� Commutativity: a� b = b� a� Neutrality of 0: a� 0 = 0� a = a� Annulment: a� a = 0� Reversibility: The equations x� a = b and a� x = b have a unique solution x.4We would like to have su h an operation for symbols, strings and tape ontents, too (with # as the neutralelement). Unfortunately, it is not possible on every domain to have an operation ful�lling all �ve properties.5So we will de�ne two operations � and instead, where � satis�es the asso iativity, ommutativity, neutralityof 0 and the reversibility, while has the annulment and the reversibility. You an al ulate with � and aswith + and �.De�nition 2.16: Operations �, Let n : �! f0; : : : ;#�� 1g be the numbering of �. Then we de�ne � and on ��� vian(a� b) � n(a) + n(b) mod #�;n(a b) � n(a)� n(b) mod #�:On �Z�n ��Z�n we de�ne (ai)i � (bi)i := (ai � bi)i and (ai)i (bi)i := (ai bi)iLet ~n0 : �� ! N0 be de�ned as ~n0(s) = l(s)Xi=1 n(si)(#� � 1)i�1where l(s) is the length of s, and let n0 : �� ! Z ben0(s) = ( ~n0(s)+12 ; if ~n0(s) odd;� ~n0(s)2 ; if ~n0(s) even:Then let �, be on �� ��� as follows: n0(a� b) = n0(a) + n0(b);n0(a b) = n0(a)� n0(b): �The details of these operations are only given for ompleteness. In this paper we only need their aforementionedproperties, and the fa t, that they an be e� iently omputed.Finally we need some way to represent integers. For our needs the following very simple de�nition is su� ient:De�nition 2.17: Representing integers as strings (mapping u)Let u : Z! �� be de�ned by u(n) := 1n for n � 0, u(n) := 01�n for n < 0. �4The reversibility follows from the annulment and the asso iativity, of ourse.5Assume su h an operation on f0; 1; 2g. It is 1 � 2 � 2 = 1, therefore 1 � 2 6= 0 and 1 � 2 6= 1. Further 2 � 1 � 1 = 2, thus1� 2 = 2� 1 6= 2. So su h an operation is impossible. �13

3 QUANTUM MACHINE MODELS3 Quantum Ma hine Models3.1 Intera tive Quantum SystemsThe most general type of quantum ma hines we will dis uss in this work is the intera tive quantum system.We will give the formal de�nition �rst and then dis uss its properties in detail.De�nition 3.1: Intera tive quantum system (IAQS)An intera tive quantum system M onsists of the following obje ts:� a unitary time evolution operator UM operating on HQ;M,� an end on�guration proje tion PF;M operating on HQ;M,� a unitary frame send operator UFS;M operating on HQ;M HF ,� a unitary send operator US;M operating on HQ;M HC ,� a unitary re eive operator UR;M operating on HQ;M HF HC with imUR;M � HQ;M j#i j#i,� a unitary orruption operator U orr;M operating on HQ;M HC ,� and a start on�guration j0;Mi 2 HQ;M,where HQ;M is the on�guration spa e!of an IAQS HC the ommuni ation tape spa e and HF the frame tapespa e. It is HQ;M �= C�Z�n ; HC �= C�Z�n ; HF �= C�� :The set of all IAQS is alled IAQS. �The time evolution operator de�nes one single al ulation step of the IAQS M. It operates on the whole on�guration of the ma hine (unlike e.g. the state transition fun tions of Turing ma hines whi h operates onthe state and a �nite part of the tape) whi h is modelled by the ountable dimensional Hilbert spa e HQ;M.We have arbitrarily hosen HQ;M �= C�Z�n , sin e the similar stru ture of the on�guration spa e and the ommuni ation tape spa e will simplify the de�nition of parti ular orruption operations later on. Sin e allinput of the ma hine will be of ountable dimension, only a ountable-dimensional part of the on�gurationspa e will be populated in a �nite number of steps, so an un ountable-dimensional on�guration spa e wouldnot give more generality. Sin e all ountable-in�nite-dimensional Hilbert spa es are isomorphi , our hoi e isof maximal generality.Be ause we have imposed no restri tions on UM (ex ept to be unitary), and our on�guration spa e is largeenough, our ma hines an evaluate any lassi al fun tion (i.e. a permutation of base on�gurations) dependingon all past inputs in a single step. Moreover any quantum me hani al operation on ountable-dimensionalHilbert spa es an be modelled.In order to model al ulations we also need the notion of an end on�guration. Sin e we want mostgenerality, we just give a measurement proje tion PF;M. The 1-eigenspa e E1 should be the subspa e of allend on�gurations. Normally E1 is the span of a set of base ve tors, though this must not ne essarily apply.Note that in the de�nition of the quantum network (see se tion 4.1) this measurement will be applied afterea h time step, so the on�guration of the IAQS will always be in E0 [E1 and no interferen es between pathswhi h pass through E1 at di�erent times will o ur. Note that the end on�guration does not denote the �nalend of the al ulation, the IAQS may be rea tivated later. Mostly M goes into the end on�guration to senda message (see below).We want to model ommuni ation pro esses, therefore we need some way to intera t. In our model we havesplit this operation into three di�erent operations. The �rst one is writing on the frame tape. This is donevia the frame send operator UFS;M. This operator is a tivated wheneverM rea hes an end on�guration. Itsfun tion is to transfer some output generated by M, whi h is still stored internally, onto the frame tape. Wemay assume that when a tivating the operator the frame tape spa e HF is ooled. The frame tape will bemeasured (see se tion 4.1) after appli ation of UFS;M. The information output this way is intended for ontrolinformation as e.g. the target of a message transmission, the request to orrupt a party, et ., i.e. a tions whi hare measured anyway in our model (see se tion 1.7).Let us larify the usage of UFS;M by example: If we implement M e.g. as a multi-tape Turing ma hine6,we ould have a distin t frame tape inside, and UFS;M would opy (or swap) the data from the internal frametape to the external one.6I.e. we think of HQ;M as a set of tapes, of head positions and a state of the �nite automate of the Turing ma hine.14

3 QUANTUM MACHINE MODELS 3.2 Exe ution trans riptsThe se ond operation is sending data. This is done via the send operator US;M. It will be applied wheneverM has requested sending a message. Control data like the message re ipient must be given in the frame. Asdoes UFS;M, the send operator transfers data to be sent from inside the ma hine to the outside. It an relyon HC to be ooled before a tivation, but it must not rely one the fa t that HC will be measured, sin e this hannel is intended for sending quantum data.To ontinue our example: US;M would swap an internal ommuni ation tape with the external one. Notethat opying is not possible in this ase, sin e the data should not be measured.The third operation is re eiving data. Here frame and data transmission are not separated, sin e the IAQSdoes not have to request the re eption of a message; whenever a message arrives, the operator UR;M is exe uted(but it is guaranteed that this will only happen while M is in the end on�guration). To be able to ensurethat HF and HC are ooled before the frame sending resp. the data sending operation, UR;M must leave HFand HC in the ooled state after operation.In our example: UR;M appends the data from the frame tape onto some internal tape (appending is noproblem, sin e the frame tape ontains lassi al data, so we may measure its length), erases the frame tape(possible, sin e we have made a opy), and then moves the frame tape into some reservoir of internal tapes ofM, repla ing it by a ooled tape, approximately like this:j ommi jtape1i jtape2i jtape3i � � � 7�! j#i j ommi jtape1i jtape2i � � �Note that this operation is unitary, though not surje tive.The last operator appearing in the de�nition of the IAQS is the orruption operator U orr;M. When a orruption o urs, this operator extra ts the on�guration from M and writes it onto the ommuni ationtape to be transfered to the orrupting ma hine. This may destroyM in the sense that further a tivations ofany operators have an unde�ned meaning. U orr;M should not opy the information, sin e this might reateadditional and unwanted entanglement between the adversary and the � orpse� of M. In the simplest (andmost important) ase U orr;M just swaps HQ;M and HC . We will however need more sophisti ated orruptionoperators when modelling lassi al ma hines (see de�nition 3.14).The meaning of the start on�guration is�as its name suggests�the on�guration in whi h the IAQS isat the beginning of its exe ution.3.2 Exe ution trans riptsIn order to de�ne some properties like polynomial running time et ., we need to be able to formulate statementslike �for any external intera tion, the IAQS M behaves in su h and su h a way with a probability of. . . � Toa hieve this, we will in this se tion de�ne exe ution trans ripts.De�nition 3.2: Quantum intera tionA quantum intera tion for the IAQS M is a sequen e of linear operators (Oi) operating on HQ;M HF HC CZC2, together with some proje tions (P (i)k )i2N;k2frun;send;re ;worldg, where ea h operator Oi is of theform: Oiji jframei j ommi jni j1i 7�! P {F;MUMji jframei j ommi jni j1i (3)+ UFS;M(PF;MUMji jframei) j ommi jni j0i (4)Oiji jframei j ommi jni j0i 7�! P {F;MUMji jframei j ommi P (i)runjni j1i (5)+ UFS;M(PF;MUMji jframei) j ommi P (i)runjni j0i (6)+ US;M(ji jframei j ommi) P (i)sendjni j0i (7)+ UR;M(ji jframei j ommi) P (i)re jni j0i (8)+ ji U (i)(jframei j ommi P (i)worldjni) j0i; (9)and where P (i)k are proje tions operating on CZ, satisfyingPk P (i)k = 1, and U (i) 2 U(HF HC CZ). �The idea behind this sequen e of operators is to model any intera tion of M with the exterior world. Thestate of the world in luding M is modelled by HQ;M HF HC CZ C2, where HQ;M, HF , and HCrepresent the state, frame tape and ommuni ation tape of M, CZ is the state of the external world, and C2is a qubit denoting whether M is running.So the �rst equation (3; 4) says, that ifM is running, Oi shall apply the time evolution UM, then measure,whether the ma hine has rea hed an end on�guration, store this result in C2, and, if yes, let the frame sendoperator UFS;M operate on M. 15

3.2 Exe ution trans ripts 3 QUANTUM MACHINE MODELSIf however the ma hine is not running (as denoted by having j0i in C2), we distinguish four ases, dependingon the result whi h is yielded by measuring whether the ontent of CZ (the state of the world) falls into thesubspa e of Prun, Psend, Pre or Pworld. In ase of Psend (5,6), we do the same things as in the �rst equation,i.e. we let the ma hine run one step.In ase of Psend (7) and Pre (8), we apply the send operator US;M resp. the re eive operator UR;M.In ase of Pworld (9), some arbitrary unitary transformation is done on the state of the world and theexternal tapes of M.Note that the Oi, as de�ned above, are unitary.The above de�nition of quantum intera tions still has one problem: It may happen, that the operatorsUFS;M and US;M are invoked while jframei or j ommi are not ooled. The behaviour of the IAQS may beunpredi table in this ase, sin e our spe i� ation promises that those two tapes are ooled on appli ation ofUFS;M and US;M.De�nition 3.3: Well-formedness of an quantum intera tionWe say that a quantum intera tion � is well-formed, if(1 (P# P#){ (P (n+1)run + P (n+1)send ) 1) nYi=1(OiPriPfiP (i)ki )(j0;Mi j#i j#i j0i j0i) = 0for all n 2 N0 and all ri 2 f0; 1g, fi 2 ��, ki 2 frun; send; re ;worldg, where P# is the proje tion onto j#i,P (i)k with k 2 frun; send; re ;worldg are the proje tions from the quantum intera tion, Pri is the proje tion ofC2 onto jrii and Pfi the proje tion of HF onto jfii. This equation lives in HQ;M HF HC CZ C2.Throughout this work, we will always impli itly assume well-formedness when talking about quantumintera tions. �In this de�nition, we start with the initial state j0;Mi j#i j#i j0i j0i of the system, whi h onsistsof the start on�guration of M and of ooled tapes. Then we apply the n-steps of the quantum intera tion,and measure afterwards, whether we are in the run or send state (whi h may involve the frame send operatoror the send operator), and jframei or j ommi are not ooled. The probability for this to happen after n stepsshould be 0 for any n.We will now de�ne the exe ution trans ript, whi h is formalises the lassi al behaviour of a ma hine inresponse to some quantum intera tion. Sin e the system is of quantum and therefore after measurementprobabilisti nature, the exe ution trans ript is a probability distribution of sequen es of output events. Ea houtput event an be one of� (run;#): The ma hine is running in this time step.� (stop; f): The ma hine stops in this time step and�after appli ation of the frame send operator�outputssome frame f .� (re ; f): The ma hine re eives some data and a frame f . The message's data is not given, sin e this datashould not be measured be ause of its quantum nature.� (send;#): The ma hine sends some data. Again the data itself is not measured.� (world;#): In this time step, some transformation outside the IAQS happens.This sto hasti variable is formally de�ned as follows:De�nition 3.4: Exe ution trans riptLet M be an IAQS. Let further an quantum intera tion � be given. Then the exe ution trans ript of Mon � is a sto hasti variable (Xi)i2N0 , where ea h Xi has values from frun; stop; re ; send;worldg � ��. Thedistribution of this sto hasti variable is derived of that of the sto hasti variable (Yi) via the equationsXi = (k;#) () Yi = (k; 0; �) (k 2 fsend;worldg) (10)Xi = (re ; f) () Yi = (re ; 0; f) (f 2 ��) (11)Xi = (run;#) () Yi = (run; 0; �) and Yi+1 = (�; 1; �) orYi = (�; 1; �) and Yi+1 = (�; 1; �) (12)Xi = (stop; f) () Yi = (run; 0; �) and Yi+1 = (�; 0; f) orYi = (�; 1; �) and Yi+1 = (�; 0; f) (f 2 ��) (13)16

3 QUANTUM MACHINE MODELS 3.2 Exe ution trans riptswhere (Yi) be de�ned viaP (Yi = (ki; fi; ri); i = 1; : : : ; n) = nYi=1(OiPriPfiP (i)ki )(j0;Mi j#i j#i j0i j0i) 2for ki 2 frun; send; re ;worldg, ri 2 f0; 1g and fi 2 ��, and where Pri denotes the proje tion of C2 onto jrii,Pfi denotes the proje tion of HF onto jfii, and P (i)ki are the proje tions from the quantum intera tion �. Theequation lives in HQ;M HF HC CZ C2.We also all a sequen e (xi) with omponents in frun; stop; re ; send;worldg ��� an exe ution trans ript,therefore the on ept both stands for outputs of a single run and for the distribution of su h outputs.We say an exe ution trans ript (xi) is impossible on �, if there is some n 2 N, su h that P (Xi = xi;i = 1; : : : ; n) = 0. A set of exe ution trans ripts is said to be impossible if ea h trans ript is impossible. �In order to de�ne the exe ution trans ript (Xi), we have �rst de�ned some sto hasti variable (Yi), whi hdenotes the output of the following algorithm:1. Measure whi h will be the next a tion of the quantum intera tion (run, re , send, world). To a hievethis, the quantum intera tion itself provides the proje tions (P (i)k )i2N;k=run;send;re ;world.2. Measure what is written on the frame tape.3. Measure, whether the ma hine is running (i.e. will be running during the following time step). We have onstru ted the quantum intera tion thus, that this information an be found in C2.4. Output the results of these measurements.5. Go to step 1.From the data gathered by the pre eding algorithm, we an easily dedu e everything we wanted to putinto the exe ution trans ript:� If we measured send or world as the quantum intera tion's a tion, while the ma hine was not running,we write into the exe ution trans ript, a (send;#) resp. a (world;#) event.� If we measure a re a tion and a frame f , we know that the ma hine is going to re eive f , so we append(re ; f) to the trans ript.� When we have a run a tion (or the ma hine was already running), and the ma hine will still be runningafter this time step, we append (run;#).� When we have a run a tion (or the ma hine was already running), but after this step the ma hine is notrunning any more, the ma hine obviously stops in this step, so we take the frame f of the next time stepand append (stop; f) to the trans ript.This is formalised by equations (10�13). Note that Xi is in fa t well-de�ned, sin e exa tly one of the right-handsides of those equations will hold.The notion of impossibility is best lari�ed by an example. Consider the result of tossing a oin an in�nitenumber of times and writing down the result of ea h oin toss twi e. Then the sequen e (0; 0; 0; : : :) and thesequen e (1; 0; 0; : : :) both have probability 0, but the se ond is impossible, while the �rst is not. We haveformalised this idea for exe ution trans ripts, but in fa t this de�nition an be used for any sto hasti variablewhi h yields a sequen e of obje ts, ea h oming from a ountable set.7Note that sets of impossible trans ripts have probability 0, sin e for an impossible set E it isP (X 2 E) = P (X 2 E \ 1[n f(xi) : P (Xi = xi; i = 1; : : : ; n) = 0g)� limn!1P (X 2 f(xi) : P (Xi = xi; i = 1; : : : ; n) = 0g)� limn!1 Xx1;:::;xn withP (xi=Xi;i=1;:::;n)=0P (Xi = xi; i = 1; : : : ; n)| {z }=0 = 0;be ause there is only a ountable number of possible �nite sequen es x1; : : : ; xn. �7If we would allow non- ountable sets, too, we get a problem: Consider (Xi) to be a series of i.i.d. sto hasti variables uniformlydistributed in [0; 1℄, Than any value for (Xi) is impossible, be ause any value for Xi has probability 0. So the probability, that(Xi) has an impossible output, is 1. 17

3.3 Running time of an IAQS 3 QUANTUM MACHINE MODELS3.3 Running time of an IAQS3.3.1 Running timeWe will now �rst introdu e a sto hasti variable whi h represents the running time of an IAQS. This will allowus to formulate most of the ideas of the following se tions more easily.De�nition 3.5: Running timeConsider some exe ution trans ript � = (xi). It is � 2 Kk (k � 0), if one of the following two onditions ismet:� For the �rst element of � having the form (re ; f) and appearing before the �rst element having the form(run;#) or (stop; �), the word f has length k.� There is no su h element and k = 0.It is further � 2 Ek;n;t (k � 0, n � 1, t 2 N[f1g), if � 2 Kk and one of the following onditions is satis�ed:� Let (ri)mi=1 (where m may be1) be the n-th sequen e of onse utive elements of (xi) whi h has the formri = (run,#) for (i 6= m) and rm = (stop; f) (where (ri) may also onsist only of one element (stop; f)),or be an in�nite sequen e of (run;#), and is not pre eded by an element (run;#). Then m � t (and inparti ular m 6=1 if t 6=1).� There is no su h sequen e.For onvenien e, we set Ek;n;0 := ;.Let E be the set of all exe ution trans ripts.The running time TXk;n of an exe ution trans ript X in invo ation n with se urity parameter k is de�ned byP (TXk;n = t) = P (X 2 Ek;n;t nEk;n;t�1)P (X 2 St2N[f1gEk;n;t) (k � 0; n � 1; t > 0):If the denominator is 0, we set P (TXk;n = t) := 0 for t > 0 and P (TXk;n = ?) := 1, otherwise P (TXk;n = ?) := 0.Let P (TXk;n =1) := P (TXk;n =2 N [ f?g). �In this de�nition, we have two auxiliary on epts: Kk is the set of all trans ripts, in whi h the length of the�rst input frame is k (with k := 0 if there is no su h frame, or if it only appears after the �rst invo ation).Ek;n;t is the set of all trans ripts, in whi h the length of the �rst input frame is k (with k = 0 if there isno su h frame), and in whi h the n-th invo ation has running time at most t (or does not happen at all).In this de�nition, the probability of running time t in invo ation n with se urity parameter k is de�nedas the onditional probability of having an exe ution trans ript with se urity parameter k and whi h satis�es,that there is no n-th invo ation or that the n-th invo ation has running time t (Ek;n;t n Ek;n;t�1), under the ondition that in this trans ript the se urity parameter is k (St2N[f1gEk;n;t = Kk). Note that t may also be1. If the probability of the denominator is 0, this means that the se urity parameter is not k, and we simplyset TXk;n := ?.3.3.2 Polynomial IAQSWe will now examine the on ept of polynomially bounded running time. In the ontext of networks, thenotion of running time is a little more omplex than regarding stand-alone ma hines: There is the runningtime per invo ation and the number of invo ations, whi h both should be polynomial to ensure, that no omputationally infeasible problems are solved by the ma hines. In our de�nition of polynomially boundedIAQS we will however only onsider the running time of a single invo ation, sin e for reasons dis ussed inse tion 5.2 a limitation of the number of invo ations would ause some problems. Bounding the number ofinvo ations to a polynomial shall then be realised by the s heduling, see se tion 5.2 and the de�nition ofpolynomial se urity (de�nition 6.3).A further di�eren e to traditional notions of se urity is the fa t, that we annot let the running time of ea hinvo ation depend on the length of the input of that spe i� invo ation, sin e this would ause two problems:� Some invo ations might get no or little input, but nevertheless the ma hine might want to work on somedata from previous invo ations whi h would request a running time bounded depending of the size ofthat previous input. 18

3 QUANTUM MACHINE MODELS 3.3 Running time of an IAQS� Two ma hines might send ea h other messages, ea h twi e the size of the pre eding one. If ea h invo ationhas a running time linear in its input length, the running time is nevertheless growing exponentially.Therefore it is ne essary to let the running time depend only on the length of the �rst input.We ome to the following notion of polynomial running time: A ma hine has polynomial running time ifthere is a polynomial p, su h that the following holds: Let k0 be the length of the �rst frame ever re eived, 0if no su h exists. Then ea h invo ation terminates after at most p(k0) steps.This de�nition also makes it fairly simple to distribute some se urity parameter k to all ma hines. We justsend a frame with the unary en oded se urity parameter before sending anything else, then the running timein ea h invo ation will be bounded by p( 1k+ 2), where 1 � 1, 2 � 0 denote some overhead used in en odingthe frame ontaining the se urity parameter. Sin e this p( 1X + 2) is a polynomial again, the running timeof ea h invo ation will be bounded polynomially in k.There is a further �nesse in the notion of polynomial running time. We have the following hoi es:� Stri t polynomial running time: The running time annot ex eed p(k). Note that here it is the same tosay �the probability is 0� and �it is impossible� (see se tion A.3 for a proof).� Reliable polynomial running time: The probability that the running time ex eeds p(k) is for ea h invo- ation bounded by a fun tion negligible in k.� Expe ted polynomial running time: The expe tation value of the running time for ea h invo ation isbounded by p(k).The �rst of these hoi es is obviously the stri test one. And in ases where we onsider absolute se urity(i.e. where we want the probability distributions of the environment's output to be identi al, see de�nition 6.1)it is the only a eptable one.In the ase that we want only indistinguishable distributions, the de�nition of reliable polynomial runningtime seems an interesting hoi e, too, but it an be seen that by repla ing a ma hine whi h ex eeds its runningtime with a negligible probability by a ma hine whi h for ibly terminates after q(p(k)) steps (the polynomialq shall denote some overhead for ounting steps) but operates identi ally to the other ma hine, the overallbehaviour of the system is�with overwhelming probability�only hanged in its overall step ount (whi hwe will not onsider in our de�nition of se urity). So in this ase we may also use the �rst de�nition ofpolynomially bounded running time.The de�nition of expe ted polynomial time is of ourse weaker than the stri t one. But it is not omparablewith the reliable one, as the following examples demonstrate:� A ma hine having running time T with P (T = n) = 2�n has expe ted polynomial running time (sin eET = Pn2�n is �nite and independent of k), but for ea h polynomial p the bound p(k) is ex eededwith a non-vanishing probability independent of k, so it is not of reliable polynomial running time.� A ma hine running a onstant number of steps with overwhelming probability but non-terminatingwith a non-vanishing probability is of ourse of reliable polynomial running time, but not of expe tedpolynomial time, sin e the expe tation value of the running time does not even exist.There is a disadvantage to the de�nition of expe ted polynomial running time. If we have e.g. some ma hineM1 with a running time P (T (1)n;k = t) / t�3, and another ma hineM2 simulatingM1 with quadrati overhead,then M1 has expe ted polynomial running time, sin e ET (1)n;k /P1t t�2 is �nite and independent of k and n,whereas ET (2)n;k / P1t t�1 = 1, so M2 is not of expe ted polynomial running time. Therefore this lass ofma hines is not losed under simulation with polynomial overhead.We do not know, whether using this de�nition of polynomial running time would make a di�eren e to ournotion of se urity.There are many further possible variants of the de�nition of polynomial running time, e.g. in the de�nitionof reliable polynomial time we ould onsider the probability, that the bound is ex eeded for any invo ation(instead of al ulating that probability for ea h invo ation separately), or ombinations of the above de�nitions.We will hoose the notion of stri t polynomial running time as the default, sin e the exa t impli ations ofthe expe ted one are un lear in this ontext, we will nevertheless also formalise the other two for ompleteness.De�nition 3.6: (Stri t) polynomial running timeWe say an IAQS M has (stri t) polynomial running time or (stri tly) polynomially bounded running time ifthere is a polynomial p su h that for any quantum intera tion � it isP (TXk;n < p(k + n) or TXk;n = ?) = 119

3.3 Running time of an IAQS 3 QUANTUM MACHINE MODELSfor all n 2 N, k 2 N0 with X being the exe ution trans ript on �.An IAQS with polynomially bounded running time we all a polynomial IAQS (PIAQS), the set of allpolynomial IAQS is written PIAQS. �De�nition 3.7: Reliable polynomial running timeAn IAQS M has reliable polynomial running time or reliably polynomially bounded running time, if there is apolynomial p and a negligible bound ", su h that for any quantum intera tion � it isP (TXk;n < p(k + n) or TXk;n = ?) > 1� "(k)for all n 2 N, k 2 N0 with X being the exe ution trans ript on �. �De�nition 3.8: Expe ted polynomial running timeThen a IAQSM has expe ted polynomial running time or expe ted polynomially bounded running time, if thereis a polynomial p, su h that for any quantum intera tion �, it is ETXn;k � p(t) or P (TXn;k = ?) = 1 for alln 2 N, k 2 N0, where X is the exe ution trans ript on �. �3.3.3 Terminating IAQSAs with polynomial running time, we have several possibilities to de�ne termination:� Stri t termination: It is impossible, that the ma hine does not terminate.� Weak termination: It has probability 0, that the ma hine does not terminate.� Reliable termination: It has negligible probability that the ma hine does not terminate.In this ase�other than with polynomial running time�the on epts of impossibility and vanishing proba-bility di�er. Therefore both the stri t and the weak termination are analogues to the stri t polynomial runningtime. An example for an weakly terminating ma hine, whi h is not stri tly terminating would be one, whi hin every step stops with a probability of 12 . It is of ourse possible, that this ma hine will run forever, but theprobability of this is 0.Here the three de�nition form a stri t hierar hy: Stri t termination is stronger than weak one, whi h againis stronger than reliable one.Again we will take the stri t termination as the default.We will now formalise those three notions:De�nition 3.9: (Stri t) terminationLet H{ be the set of all exe ution trans ripts (xi), su h that there exists an n0 2 N, su h that for every i � n0it is xi = (run; �).We then all an IAQS (stri tly) terminating, if H{ is impossible on any quantum intera tion. �Here H{ an be thought of as the set of all non-terminating exe ution trans ripts.De�nition 3.10: Weak terminationLet H{ be as in the previous de�nition.We then say that an IAQS is weakly terminating, if for any quantum intera tion � it is P (X 2 H{) = 0,where X is the exe ution trans ript on �. �De�nition 3.11: Reliable terminationLet H{ be as in the foregoing two de�nitions and Kk as in the de�nition of running time (de�nition 3.5)We then say that an IAQS is reliably terminating, if for any quantum intera tion � and any k 2 N0, theprobabilities (P (X 2 H{ \Kk))k are negligible in k, where X is the exe ution trans ript on �. �It is H{k the set of all exe ution trans ripts where the �rst re eived frame has length k (or does not exist ifk = 0), and whi h additionally do not terminate. 20

3 QUANTUM MACHINE MODELS 3.3 Running time of an IAQS3.3.4 Relative polynomial running timeBesides lassi� ation of the running time of a single ma hine, we may also ompare running times. An espe iallyimportant notion is that of relative polynomial running times, i.e. we want to formalise statements like �M2has a running time polynomial in that of M1�.We will now pro eed by giving two possible de�nitions of relative polynomial running time. Informallythey go as follows:� (Hard) relative polynomial running time: For any invo ation and any se urity parameter, let T1 be theworst- ase running time of M1. The worst ase running time T2 of M2 shall then be polynomial in T1.� Sto hasti relative polynomial running time: For any invo ation and any se urity parameter, let T1 bethe distribution of the running time of M1, and T2 that of M2. Then the probability, that T2 ex eedssome value t2, should be bounded by the probability, that p(T1) ex eeds t2.The formalisations of these notions are:De�nition 3.12: (Hard) relative polynomial running timeLet M1 and M2 be IAQS. Let further �1 and �2 be quantum intera tions for M1 resp. M2 and X1 and X2exe ution trans ripts for M1 resp. M2 on �1 resp. �2.We then say, M2 has (hard) polynomial running time relative to M1, if the following holds for any hoi eof �1, �2:For i = 1; 2 let Ti;k;n 2 N be minimal with P (TXik;n > Ti;k;n) = 0, resp. Ti;k;n := ? if P (TXik;n = ?) = 1.Then there is a polynomial p independent of the hoi e of �1, �2, su h that T2;k;n � p(T1;k;n + k+ n) for everyk � 0, n � 1, where we onsider the inequality as true, if T1;k;n = ? or T2;k;n = ?. �Note that we have given T1;k;n + k + n as argument to the polynomial. This is due to the fa t, that if wehave e.g. M1 with onstant running time, then being polynomial just in T1;k;n would imply that M2 has onstant running time, too. With our de�nition however,M2 may then be of polynomial running time, sin eits running time an also grow polynomially in k and n.De�nition 3.13: Sto hasti relative polynomial running timeLet M1, M2, �1, �2, X1, X2 be as in the previous de�nition.We then say, M2 has sto hasti polynomial running time relative to M1, if the following holds for any hoi e of �1, �2:There is a polynomial p independent of �1 and �2, su h thatP (TX2k;n � t) � P (p(TX1k;n + k + n) � t) (14)for all n 2 N, k 2 N0, t 2 N0. We onsider the inequality to be true, if TX1k;n = ? or TX2k;n = ?. �The main advantage of the hard relative polynomial time is that is probably mu h simpler to handle and moreintuitive, further it is probably approximately this de�nition people have in mind, when they say that somema hine has a running time polynomially bounded in that of some other.The advantage of the sto hasti relative polynomially time is that it takes �ner details of the two run timedistributions into a ount. E.g. if M1 has a running time distribution P (T = t) / 2�t, this would not bedistinguished from a non-terminating ma hine by the �rst de�nition, the se ond however would requireM2 tohave�somewhat unpre isely spoken�a running time distribution in whi h the probabilities for higher runningtimes diminish in some way exponentially. And if M1 is of stri t polynomial time, the set of ma hines withsto hasti polynomial running time relative to M1 would be exa tly the set of ma hines of stri t polynomialrunning time. IfM1 is of reliable polynomial time, then any ma hine with sto hasti polynomial running timerelative to M1 is of reliable polynomial time, too.However, if M1 is of expe ted polynomial time, then M2 may have sto hasti polynomial running timerelative to M1 without being of expe ted polynomial time. The ounterexample given after the de�nition ofexpe ted polynomial time is valid here, too (see de�nition 3.8).Another advantage of these de�nitions is, that if some IAQS M2 simulates another IAQS M1 with poly-nomial overhead, M2 is of hard and of sto hasti polynomial running time relative to M1.If M2 is of sto hasti polynomial running time relative to M1, then it is also of hard polynomial runningtime relative to M1, so sto hasti relative polynomial time is the stri ter de�nition.21

3.4 Classi al Systems 3 QUANTUM MACHINE MODELS3.4 Classi al SystemsIf we do not only want to speak about quantum, but also about lassi al se urity, we need some notions whatthe word � lassi al� means in our ontext. This is a hieved by the following de�nition:De�nition 3.14: lassi alLet U opy;M be the operator on HQ;M HF HC , whi h is de�ned byU opy;M : jY(q; r1; r2; : : :)i j i jfi �! jY(q; q; ; f; r1; r2; : : :)i j i jfifor q; ri; 2 �Z�n, f 2 ��.We all an IAQS M lassi al, if� there are ~UM 2 U(HQ;M), ~UFS;M 2 U(HQ;MHF ), ~US;M 2 U(HQ;MHC), ~UR;M 2 U(HQ;MHF HC), ~U orr;M 2 (HQ;M HC), su h thatUM = ~UM � U opy;M;UFS;M = U opy;M � ~UFS;M � U opy;M;US;M = U opy;M � ~US;M � U opy;M;UR;M = ~UR;M � U opy;M;U orr;M = U opy;M � ~U orr;M � U opy;M:� for q; r1; ~r1; r2; ~r2; : : : 2 �Z�n with ri 6= ~ri for some i 2 N it is(hY(q; r1; r2; : : :)j 1 1)M(jY(~q; ~r1; ~r2; : : :)i 1 1) = 0 (15)for ea h M 2 f ~UM 1 1; ~UFS;M 1; ~US;M 1; ~UR;M; ~U orr;M 1; PF;M 1 1g. �The ideas behind this de�nition are the following: The on�guration spa e of M is split into an in�nitesequen e of spa es using the Y-fun tion, ea h again ontaining a omplete tape, i.e.HQ;M �= HQ;M;1 HQ;M;2 HQ;M;3 : : : :Now we de�ned all operators operating on HQ;M to be pre eded in every appli ation by a opy operation,whi h pushes a opy ofHQ;M;1, HF andHC (in the standard basis) onto the sta k of tapesHQ;M;2, HQ;M;3,. . .(we will all these the measurement tapes). Doing this is equivalent to measuring HQ;M;1 in the standardbasis. The operators whi h write onto the external tapes are also followed by this opy operation.To ensure, that the measurement tapes are not modi�ed any more, we for e all operators (ex epting thejust des ribed opying operation) to be read-only on the measurement tapes. This is done by (15).Note that this in fa t de�nes probabilisti ma hines, though there is no random tape, sin e the IAQS isallowed to do unitary transformations, whi h are not ne essarily permutations of basis ve tors, and sin e thisis followed by a �measurement� afterwards, we an get random results.8That these onstraints are in fa t su� ient to make a ma hine lassi al, is demonstrated by the followinglemma:Lemma 3.15Let M be a lassi al IAQS and � some quantum intera tion for M onsisting of operators (Oi).LetMi : HQ;MHFHCC2 ! HQ;MHFHCC2 (i = 1; : : : ; n+1) be observables with eigenspa esspanned by ve tors of the standard basis of HQ;MHF HC C2, where HQ;M HF HC j0i should be ompletely ontained in one of the eigenspa es.We de�ne the mixed states%1 := �Mr �Mf �M (i) nYi=1( �Oi �Mr �Mf �M (i)) %(j0;Mi j#i j#i j0i j0i);%2 := �Mr �Mf �M (i) �Mn+1 nYi=1( �Oi �Mr �Mf �M (i) �Mi) %(j0;Mi j#i j#i j0i j0i);8E.g. a random bit ould be obtained by applying the Hadamard transform on a single qubit, after measuring it will have thevalue 0 or 1 with equal probability. 22

3 QUANTUM MACHINE MODELS 3.4 Classi al Systemsin HQ;MHF HCCZC2, whereMf is the standard basis measurement of HF ,Mr that of C2, andM (i)is the measurement fP (i)k ; k 2 frun; send; re ;worldgg, with P (i)k as in the de�nition of quantum intera tions(de�nition 3.2). �X denotes the density matrix operator for X .Let M be any observable satisfying for ea h of its eigenspa es E, that(h~qj h ~f j h~ j 1 1)PE(jqi jfi j i 1 1) = 0for any basis states j~qi; jqi 2 HQ;M, j ~fi; jfi 2 HF , j~ i; j i 2 HC with j~qi j ~fi j~ i 6= jqi jfi j i, where PEis the proje tion onto E.Then the out omes of M -measuring %1 and %2 have the same probability distribution. �This lemma an be interpreted as follows: Ea h Mi is a lassi al observation of the ma hines on�gurationand its external tapes; however if the ma hine is not running (i.e. we have a state in HQ;MHF HC j0i),the measurement always yields the same value. The latter is ne essary for formal reasons, be ause in ourmodelling of the quantum intera tion the external tapes may temporarily be used by the external world in aquantum way while the ma hine is not running.Then we de�ned two mixed states. The �rst, %1, is the result of applying the quantum intera tion similarto the way already des ribed in the de�nition of the exe ution trans ript. But instead of proje ting ontomeasurement results hosen in advan e, we perform unobserved measurements. Furthermore we end in ameasurement, not with an appli ation of Oi.The se ond one, %2, we get by applying the same operations as when reating %1, but by measuring thema hine's lassi al data with the measurements Mi before and after every time step.Note that the order of the measurements does not matter, sin e they do all ommute.The result of this lemma is that we annot distinguish %1 and %2 by applying a measurement that behaves lassi ally on the ma hine's on�guration and the external tapes, i.e. whi h satis�es, that any basis ve tor inthose spa es stays unmodi�ed after the measurement.The whole formalises the intuitive notion that the ma hine is lassi al and thus justi�es the above de�nition.A proof for this lemma an be found in se tion A.1.It is not only important to speak about ompletely lassi al ma hines, we also have to formalise the notion ofma hines, whi h an do quantum al ulations, but whi h annot ommuni ate with ea h other in a quantummanner. These ma hines an be thought as a lassi al omputer having a ess to some internal quantum omputer. Su h a ma hine an obviously be simulated by a lassi al probabilisti omputer with an exponentialoverhead with arbitrary pre ision. We have named this kind of IAQS an IAQS with lassi al interfa es.De�nition 3.16: Classi al interfa esLet U opyif;M be the unitary operator on HQ;M HF HC , whi h is de�ned byU opyif;M : jY(q; r1; r2; : : :)i j i jfi �! jY(q; ; f; r1; r2; : : :)i j i jfifor q; ri; 2 �Z�n, f 2 ��.We say an IAQS M has lassi al interfa es, if� There are some ~US;M 2 U(HQ;M HC), ~UFS;M 2 HQ;M HF , and ~UR;M 2 HQ;M HF HC , su hthat US;M = U opyif;M � ~US;M;UFS;M = U opyif;M � ~UFS;M;UR;M = ~UR;M � U opyif;M;� and for q; r1; ~r1; r2; ~r2; : : : 2 �Z�n with ri 6= ~ri for some i 2 N it is(hY(q; r1; r2; : : :)j 1 1)M(jY(~q; ~r1; ~r2; : : :)i 1 1) = 0for ea h M 2 fUM 1 1; ~UFS;M 1; ~US;M 1; ~UR;M; U orr;M 1; PF;M 1 1g. �This de�nition an be understood quite analogous to that of lassi al IAQS. The only di�eren e is, that wedo only opy the ontent of the external tapes onto our measurement tapes, and that this opy operation23

3.4 Classi al Systems 3 QUANTUM MACHINE MODELSonly takes pla e immediately after send and frame send operations, and immediately before re eive operations,be ause only then the external tapes ontain something to be measured.We will now introdu e two mappings from the set of IAQS to the set of lassi al IAQS resp. the set of IAQSwith lassi al interfa es. These shall formalise the result of taking an IAQSM and measuring the the externaltapes and in the �rst ase also the on�guration after ea h time step. The se ond one we will need in hapter 8when dis ussing the equivalen e of lassi al and quantum se urity in some ases. The �rst one is given for ompleteness.De�nition 3.17: Making an IAQS lassi al (mapping C)The mapping C : IAQS �! IAQSmaps an IAQS M to a lassi al IAQS C := C(M) onstru ted as follows:MC : jY(q; r1; r2; : : :)ijij�i 7�! X~q2�Z�n(h~qjhjh�jMMjqijij�i)jY(~q; r1; r2; : : :)ijij�i (16)for q; r1; r2; : : : 2 �Z�n, ji 2 HF , j�i 2 HC , and for every (MC ;MM) inf( ~UC 1 1; UM 1 1); ( ~UFS;C 1; UFS;M 1);( ~US;C 1; US;M 1); ( ~UR;C ; UR;M)g:Let then~U orr;C : jY(q; r1; r2; : : :)i jY(q0; r01; r02; : : :)i7�! X~q;~q02�Z�n(h~qj h~q0jU orr;Mjqi jq0i)jY(~q; r1; r2; : : :)i jY(~q0; r01 � r1; r02 � r2; : : :)i (17)and PF;C be the proje tor ontospanfXi2I �ijY(qi; r1; r2; : : :)i : qi; ri 2 �Z�n; PF;MXi2I �ijqii =Xi2I �ijqii;#I <1g:The UC , UFS;C , US;C, UR;C and U orr;C operators are then onstru ted as in the de�nition of lassi al IAQS. �This mapping onstru ts the send, frame send, and re eive operator of C thus, that they operate on HQ;C;1,as the operators ofM would have done on HQ;M (equation (16)). These operators are then ompleted by theinvo ations of U opy;C required by the de�nition of lassi al IAQS.The orruption operator is de�ned su h, that HC is de omposed into HC;1 HC;2 � � �, and then theU orr;C operates on HQ;C;1 HC;1, as U orr;M would have done one HQ;M HC , and opies HQ;C;i to HC;i(i � 2). So this orruption operator delivers all information about past measurements, but does not allow toundo any measurement, therefore the information is opied onto the ommuni ation tape, but not removedfrom the measurement tapes. This behaviour is spe i�ed by (17). Finally the alls to U opy;C ne essitated bythe de�nition of lassi al IAQS are added to U orr;C .The end on�guration proje tion PF;C proje ts HQ;C;1, as PF;M would have done with HQ;M. The mea-surement tapes are ignored for the de ision, whether we have rea hed an end on�guration.To get the mapping onto the set of IAQS with lassi al interfa es, only few modi� ations of the previousde�nition are ne essary:De�nition 3.18: Making the interfa es of an IAQS lassi al (mapping CI)The mapping CI : IAQS �! IAQSmaps an IAQS M to an IAQS C := CI(M) onstru ted as follows:The operators ~UC, ~UFS;C , ~US;C , ~UR;C, ~U orr;C and PF;C are onstru ted as in the pre eding de�nition.Then UFS;C , US;C , and UR;C are de�ned as in the de�nition of lassi al interfa es, andUC := ~UC ; U orr;C := ~U orr;C : �24

3 QUANTUM MACHINE MODELS 3.5 Turing ma hinesThis de�nition is almost the same as that of C, with the ex eption, that we have added invo ations of U opyif;Cinstead of U opy;C , and only there, where it is required by the de�nition of lassi al interfa es, i.e. in UFS;C ,US;C , and UR;C .There are of ourse other on eivable models, whi h we will not formalise, but whi h should be mentionedhere:� We ould model ma hines whi h have no quantum storage, this ould be done by measuring the ma hines ontent after rea hing the end on�guration, but not after ea h step.� We ould also model ma hines, whi h do not have full quantum interfa es, but whi h an hoose in whatbasis they want to send their lassi al data, and in whi h basis to measure in oming data (here we ouldfurther distinguish, whether we have to spe ify a basis for ea h ell of the input or a basis for the wholein oming tape).This models e.g. a quantum hannel realised by photons whi h we may polarise and measure using �lterswhi h an be pla ed in any orientation, but without the possibility to let some photons intera t withea h other, and without any quantum storage.� The orruption operator does not opy the measurement tapes, but swaps them with the ommuni ationtape. This models the ase, that real lassi al omputation is impossible, and that existing lassi alma hines just hide their measurement tapes in the laboratories thermal a tivity or the like, and that asu� iently skillful adversary may isolate those �lost states� again and operate on them.This probably is not a very present threat, but should nevertheless be thought of.3.5 Turing ma hines3.5.1 Intera tive quantum Turing ma hinesIn this se tion we will introdu e intera tive quantum Turing ma hines and how to regard them as IAQS. Wewill strongly draw from [BV93℄, but introdu e important hanges due to the intera tive nature of those Turingma hines.To show whi h are the ru ial points when making a quantum Turing ma hine intera tive, we will �rstre olle t how a lassi al intera tive Turing ma hine is usually onstru ted. They are basi ally normal multi-tape Turing ma hines, where some tapes have spe ial meaning, the ommuni ation tapes. If there is somein oming message, it is written onto or appended to the in oming ommuni ation tape; if a message shall besend, it is opied from the outgoing ommuni ation tape.In our ase, we have to restri tions, whi h obviate su h a simple solution: We want to model the impossi-bility of data erasure, and we need unitary operations due to the quantum nature of our model.The handling of outgoing messages an easily be �xed with respe t to these restri tions, instead of opyingthe outgoing message, we move it o� the outgoing tape, leaving the latter in a ooled state.In the ase of in oming messages, the world gets ompli ated. We annot overwrite9 the in oming om-muni ation tape, sin e then we would erase data, but appending is not feasible, either. Though appending isa well-de�ned operation even in quantum me hani s, we run into the following problem: When we have twomessages on the in oming ommuni ation tape, we annot read the se ond one without knowing the lengthof the �rst one. It may however be on eivable, that some proto ol inhibits measuring the length of somemessages, and in the general ase there might not even be known bounds on the message length.So apparently there is only one way to solve this problem: We have to add the in oming message as a newtape into the Turing ma hine.10 So the intera tive quantum Turing ma hines presented here have a �nite butdynami ally growing number of tapes.Sin e the state transition fun tion annot operate on a variable number of tapes,11 we introdu e the on eptof a tape revolver, whi h is part of our Turing ma hine in addition to the normal tapes. This is a y li sequen eof tapes, of whi h exa tly one is in use at a time. We an turn this revolver in two dire tions, thus navigatingto any one of the tapes. The state transition fun tion then operates on the normal tapes and the sele tedrevolver tape. Thus the transition fun tion is �nite and an nevertheless a ess a growing number of tapes.9Here the word overwriting also overs the ase, where we move the ontent of the in oming ommuni ation tape to someina essible lo ation and then put the new date in its pla e.10In fa t, we ould also interleave the message with one of the existing tapes, but this is essentially the same, sin e we add new ells to the Turing ma hine.11Otherwise it would be possible to en ode an in�nite amount of information into the transition fun tion, allowing to solve evennon- omputable problems. 25

3.5 Turing ma hines 3 QUANTUM MACHINE MODELSIn this Turing ma hine, re eiving a message is implemented by inserting frame and message as two newtapes into the revolver, while when sending a message, we take the a tive revolver tape as frame, and thefollowing one as the message data.12 Note that we move the ontent o� the tape when sending as des ribedabove, but we do not remove that tape, sin e this would imply mapping the number of the a tive tape ontosome number of a smaller set, an intrinsi ally non-reversible operation.We will now pro eed and give the formal details of quantum Turing ma hines.De�nition 3.19: Computable real and omplex numbers ~R, ~CWe all ~R the set of all numbers � 2 R, su h that there is a deterministi algorithm A�, that omputes � towithin a pre ision of 2�n in time polynomial in n.Let then ~C := ~R+ i ~R and ~R�0 := ~R \R�0. �We will restri t the amplitudes in the de�nition of an IQTM to su h omputable numbers to ensure, that we annot hide some not e� iently omputable information in the amplitudes. See [BV93℄ for more informationon this.De�nition 3.20: Intera tive quantum Turing ma hine (IQTM)An intera tive quantum Turing ma hine (IQTM) M = (Q; q0; qf ; n; Æ) onsists of a �nite set of states Q � ��,an initial state q0 2 Q, a �nal state qf 2 Q, a tape number n � 2 and a transition fun tionÆ : Q��n �! ~C�n�Q�fL;Rgn�1�fL;R;U;Dg: �The interpretation of the transition fun tion Æ is as follows: It takes as input the urrent state q 2 Q and thesymbols at the urrent head positions in the n di�erent tapes. Here the n-th tape is the a tive revolver tape.Ea h revolver tape has its own head position.We onsider a state q 2 Q as a string (Q � ��) in order to be able to write the on�guration of a ma hineas a string (see de�nition 3.28).The output of Æ is a superposition of transitions, ea h onsisting of n new symbols to be written at the urrent head positions, a new state q0 2 Q and n dire tions for head movements. Here the n-th dire tion,whi h applies to the revolver an either move the head of the a tive revolver tape (L, R), or turn the revolverup or down (U , D).De�nition 3.21: Time evolution of an IQTMThe time evolution UM of an IQTM M = (Q; q0; qf ; n; Æ) is a linear operator on HQ;M, whi h is de�ned asfollows:Let Æ(q; �1; : : : ; �n; q0; �1; : : : ; �n; d1; : : : ; dn) := hq0; �1; : : : ; �n; d1; : : : ; dnjÆ(q; �1; : : : ; �n) and let u(n) be asin de�nition 2.17.For any basis state of HQ;M having the form jY(q; u(rm); u(r); �; u(h1); t1; u(h2); t2; : : :)i with q 2 Q,rm 2 N, rm � 3, r 2 f0; : : : ; rm � 1g, � 2 ��, hi 2 Z, ti 2 �Z�n, and hi = 0, ti = # for i > n+ rm � 1, it isUMjY(q; u(rm); u(r); �; (u(hi); ti)i)i=X Æ(q; (ti;hi)n�1i=1 ; tn+r;hn+r ; q0; (�i)ni=1; (di)ni=1)jY(q0; u(rm); u(r + �dn mod rm); �0; (u(hi + ~di); ~ti)i)i (18)where ~ti is the tape resulting from the tape ti by repla ing the symbol at index hi by �i (i < n) resp. �r+n(i = n). For i � n, i 6= r + n, it is ~ti = ti. Let �0 := �.Further let be ( ~di; �di) := 8>>>>>><>>>>>>:(0; 0); if i � n and i 6= r + n;(�1; 0); if di = L (i < n) or dn = L (i = r + n);(1; 0); if di = R (i < n) or dn = R (i = r + n);(0;�1); if dn = U (i = r + n);(0; 1); if dn = D (i = r + n):The sum in (18) runs over all q0 2 Q, �1; : : : ; �n 2 �, d1; : : : ; dn�1 2 fL;Rg, dn 2 fL;R;U;Dg.For any basis state ji 2 HQ;M whi h has not the form above, it is UMji = ji. �12It would be possible to spe ify, that for sending normal tapes are used, but when hoosing revolver tapes, we an resend are eived message without having to opy it onto another tape, the latter being impossible in the ase of a message of unknownlength. 26

3 QUANTUM MACHINE MODELS 3.5 Turing ma hinesIn this de�nition, we embed the spa e HIQTM := CQ CZ CZ C�� (CZ C�Z�n)N in HQ;M. Ourembedding is not surje tive, outside of this subspa e we de�ne UM arbitrary to be the identity. States outsideHIQTM will never be rea hed.A basis state in HIQTM onsists of the automaton's state q, the size of the revolver rm, the number r ofthe urrent revolver tape, some string � whi h will be ignored,13 and tapes ti (i 2 N) together with headpositions hi 2 Z.The tapes t1; : : : ; tn�1 are the n � 1 normal tapes, the tapes tn; : : : ; tn+rm�1 are the revolver tapes, ofwhi h tr+n is the urrently sele ted one.We assume that rm � 3 (otherwise moving the revolver in di�erent dire tions will give the same position,whi h might lead to problems with the unitarity) and, of ourse, r 2 f0; : : : ; rm � 1g. Otherwise we operateas the identity.For any given state, we an al ulate the value of Æ, whi h is Æ(q; (ti;hi )n�1i=1 ; tn+r;hn+r). This value is asuperposition of a tions (q0; (�i)ni=1; (di)ni=1). Here q0 is the automaton's new state, �i are the symbols to writeto the urrent head positions, and di are the head and revolver movements to apply afterwards.The new tape ontents ~ti are then onstru ted by repla ing the ell at position hi in ti by the new symbol�i, if it is a normal tape. For the urrent revolver tape ~tr+n, we repla e by �n, of ourse, sin e there is no �r+n.Ina tive revolver tapes are not modi�ed.The head positions are then shifted by ~di. Here ~di is dire tly derived from di for normal tapes. In aseof the urrent revolver tape dn may have four values R, L, U , D. In ase of R or L, we pro eed as withthe normal tapes to al ulate ~dr+n. But for U or D, the is no head movement, but �di, the movement of therevolver, is set to �1 resp. 1. For ina tive tapes, no movement o urs ( ~di = 0).If �di was set to a nonzero value, the revolver position r is moved by �di modulo the revolver size.This time evolution is in general not unitary. Therefore we will on entrate on those IQTM, where it isunitary, the well-formed ones:De�nition 3.22: Well-formedness of an IQTMAn IQTM is well-formed, if its time evolution is unitary.The set of all well-formed IQTM is denoted IQTM.Throughout this work, we will always impli itly assume well-formedness when talking about IQTM. �De�nition 3.23: Start on�guration of an IQTMThe start on�guration j0;Mi of an IQTM M = (Q; q0; qf ; n; Æ) is de�ned byj0;Mi := jY(q0; u(3);#;#;#; : : :)i: �In the start on�guration, the state is the initial state q0, the revolver size is set to its minimal size, all headpositions are zero (u(0) = #), and all tapes are empty.De�nition 3.24: End on�guration proje tion of an IQTMThe end on�guration proje tion PF;M of an IQTM M = (Q; q0; qf ; n; Æ) is the proje tion ontospanfjY(qf ; x1; x2; x3; : : :)i : x1; x2; : : : 2 �Z�n; xi = # for almost every ig: �The ondition for being an end on�guration is that the urrent state q is the �nal state qf .De�nition 3.25: Frame send operator of an IQTMThe frame send operator UFS;M of an IQTM M = (Q; q0; qf ; n; Æ) operates on HQ;M HF as follows:UFS;MjY(q; u(rm); u(r); �; (u(hi); ti)i)i jfi = jY(q; u(rm); u(r+1 mod rm); �; (u(hi); ti)i)i jf �K(tr+n)i:On basis ve tors not having that form, or where r =2 f0; : : : ; rm � 1g, UFS;M operates as the identity. �The frame send operator takes the urrent revolver tape, opies a string from its ontent (i.e. from headposition 0 to the �rst #-symbol) to the frame tape jframei. Copying is feasible here, sin e we assume jframeito ontain lassi al data.The revolver is then moved one position, sin e the send operator, whi h is often exe uted dire tly after theframe send operator, should not use the same tape, of ourse.De�nition 3.26: Send operator of an IQTMThe send operator US;M of an IQTM M = (Q; q0; qf ; n; Æ) operates on HQ;M HC as follows:US;MjY(q; u(rm); u(r); �; (u(hi); ti)i)i j i = jY(q; u(rm); u(r + 1 mod rm); �; (u(hi); ~ti)i)i jtr+ni;13It will be used when de�ning intera tive lassi al Turing ma hines in se tion 3.5.2. It is in luded in the de�nition of IQTMto have more uniform de�nitions. 27

3.5 Turing ma hines 3 QUANTUM MACHINE MODELSwhere ~ti := ti if i 6= r + n and ~ti := if i = r + n. On basis ve tors not having that form, or wherer =2 f0; : : : ; rm � 1g, US;M operates as the identity. �The send operator works similar to the frame send operator, ex ept that the ontent of the urrent revolvertape is swapped, not opied, with the ommuni ation tape.De�nition 3.27: Re eive operator of an IQTMThe re eive operator UFS;M of an IQTM M = (Q; q0; qf ; n; Æ) operates on HQ;M HF HC as follows:UR;MjY(q; u(rm); u(r); �; (u(hi); ti)i)i jfi j i = jY(q; u(rm + 2); u(r); �; (u(~hi); ~ti)ii j#i j#i;where (~hi; ~ti) := 8>>><>>>:(hi; ti); if i < r + n;(0; f); if i = r + n;(0; ); if i = r + n+ 1;(hi�2; ti�2); if i � r + n+ 2: �In the ase of the re eive operator, the number of revolver tapes rm is in reased by 2, and the new two tapesare inserted at the urrent revolver position. The new tapes have the ontent of the frame tape and the ommuni ation tape respe tively. The frame and the ommuni ation tape are left empty after this operation,as required by the de�nition of IAQS.De�nition 3.28: Corruption operator of an IQTMThe orruption operator U orr;M of an IQTMM = (Q; q0; qf ; n; Æ) operates onHQ;MHC as U orr;Mjqij i =j i jqi. �The orruption operator gives all information about the IQTM to the orrupting party.With those operators, an IQTM is an IAQS, so we have an embedding IQTM � IAQS.De�nition 3.29: Polynomial intera tive quantum Turing ma hineAn well-formed IQTM, whi h has polynomial running time, we all a polynomial intera tive quantum Turingma hine (PIQTM).The set of all PIQTM we all PIQTM. �Lemma 3.30: Lo al well-formedness ondition for IQTMAn IQTM M = (Q; q0; qf ; n; Æ) is well-formed, if and only if the following onditions are ful�lled for Æ:� Unit length: kÆ(q; �1; : : : ; �n)k = 1 for all q 2 Q, �1; : : : ; �n 2 �.� Orthogonality: Æ(q; �1; : : : ; �n) ? Æ(~q; ~�1; : : : ; ~�n) for any q; ~q 2 Q, �i; ~�i 2 � with (q; �1; : : : ; �n) 6=(~q; ~�1; : : : ; ~�n).� Separability: For any I � f1; : : : ; ng, I 6= ; it is: For �i; ~�i; �0i; ~�0i 2 �, q; ~q 2 Q, di; ~di 2 fL;Rg (i < n),dn; ~dn 2 fL;R;U;Dg, di 6= ~di, it isXq0 X Æ(q; (�i)i; (�0i)i; q0; (di)i)yÆ(~q; (~�i)i; (~�0i)i; q0; ( ~di)i) = 0where the se ond sum runs over all �0i; ~�0i 2 �, di; ~di 2 fL;Rg (i < n), dn; ~dn 2 fL;R;U;Dg, whi hsatisfy for i 2 I : �0i = �0i, ~�0i = ~�0i, di = di, ~di = ~di; and for i =2 I : �0i = ~�0i, di = ~di.Here Æ is used as in the de�nition of the time evolution (de�nition 3.21). �This lemma is the natural extension of the lo al well-formedness ondition for quantum Turing ma hinespresented in [BV93℄ to our model of IQTM. When removing the revolver and restri ting the number of tapesto 1, then our lemma spe ialises to the well-formedness ondition given there.A proof for this lemma is given in se tion A.6. 28

3 QUANTUM MACHINE MODELS 3.5 Turing ma hines3.5.2 Intera tive lassi al Turing ma hinesBeside IQTM, we also need intera tive lassi al Turing ma hines (ICTM) to model parti ipants, whi h are notable to do anything non- lassi al.The lassi al Turing ma hine has a state transition fun tion very similar to that of a quantum Turingma hine, ex ept that the image is not a superposition of a tions, but a probability distribution.De�nition 3.31: Intera tive lassi al Turing ma hine (ICTM)An intera tive lassi al Turing ma hine (ICTM) (Q; q0; qf ; n; Æ) onsists of a �nite set of states Q � ��, aninitial state q0 2 Q, a �nal state qf 2 Q, a tape number n � 2 and a transition fun tionÆ : Q��n �! ~R�n�Q�fL;Rgn�1�fL;R;U;Dg�0 :where for any x 2 im Æ the sum of all omponents of x is 1.The set of all ICTM is written ICTM. �We want to onsider an ICTM as an IAQS, and we have the additional requirement, that it mat hes thede�nition of a lassi al IAQS (de�nition 3.14). In order to a hieve this, we �rst de�ne an intermediate IAQSC0, whi h has the desired behaviour, and then make it lassi al using the mapping C (de�nition 3.18).De�nition 3.32: Pseudo time evolution of an ICTMThe pseudo time evolution UC0 of an ICTM C = (Q; q0; qf ; n; Æ) is de�ned almost exa tly as the time evolutionof an IQTM C0 := (Q; q0; qf ; n; Æ0) withÆ0(q; �1; : : : ; �n) :=XqÆ(q; �1; : : : ; �n)�1;:::;�n;q0;d1;:::;dn j�1; : : : ; �n; q0; d1; : : : ; dniHere the sum runs over all (�1; : : : ; �n; q0; d1; : : : ; dn) 2 �n �Q� fL;Rgn�1 � fL;R;U;Dg.The only di�eren e is, that�0 := N(�;Æ(q; q0; (ti;hi)n+rm�1i=1 ; d1; : : : ; dn; �1; : : : ; �n)): �This time evolution is analogous to that of an IQTM, with the ex eption, that the string � gets all informationappended, whi h is needed to� Undo the last time step.� Re-exe ute the last time step if only the ontents of � are known.These two properties make UC0 unitary, sin e due to the �rst ondition, two di�erent basis states go ontoorthogonal states and due to the se ond property a basis state goes into a superposition of orthogonal states,ea h with a squared amplitude equal to the orresponding value of Æ, whi h sum up to 1.De�nition 3.33: An ICTM as an IQTMAn ICTM C is onsidered as an IQTM M, whi h is onstru ted as follows:Let C0 be the IAQS onsisting of the pseudo time evolution of C, and the end on�guration proje tion, theframe send operator, the send operator, the re eive operator and the orruption operator as de�ned for the(not ne essarily well-formed) IQTM C.Then M := C(C0). �Be ause UC0 is unitary, C0 is well-formed, and so is M, its image under C. We thus have ICTM � IQTM.3.5.3 Classi al interfa esThe last variant of Turing ma hines we need is that of quantum Turing ma hine with lassi al interfa es(IQCTM).These are easy to onstru t using the mapping CI. We simply onstru t a normal IQTM and then makethe interfa es lassi al by measuring them. See the explanation of C in the previous se tion.De�nition 3.34: Intera tive quantum Turing ma hine with lassi al interfa es (IQCTM)An intera tive quantum Turing ma hine with lassi al interfa es (IQCTM) is de�ned exa tly as is an IQTM.�De�nition 3.35: An IQCTM as a IAQSAn IQCTM C is onsidered to be an IAQS M, whi h is onstru ted as follows:29

3.6 ITM and partial ITM 3 QUANTUM MACHINE MODELSLet C0 be the IAQS belonging to the IQTM C. Then M := CI(C0). �De�nition 3.36: Well-formednessWe all an IQCTM well-formed, if it is a well-formed IAQS.The set of all well-formed IQCTM we all IQCTM. �3.6 ITM and partial ITMMostly, if we want to allow a lass of Turing ma hines in some de�nition (e.g. when restri ting to polynomialTuring ma hines), we do not are whi h kind of intera tive Turing ma hines are used, i.e. whether IQTM,ICTM, or IQCTM. Therefore we de�ne the intera tive Turing ma hine as follows:De�nition 3.37: Intera tive Turing ma hine (ITM)An intera tive Turing ma hine (ITM) is an IQTM, an ICTM, or an IQCTM.The set of all well-formed ITM we denote as ITM � IAQS. The set of all polynomial well-formed ITM wewrite PITM � ITM. �At some point we will also need partial Turing ma hines, these are de�ned straightforwardly as:De�nition 3.38: Partial intera tive Turing ma hineA partial intera tive Turing ma hine (partial ITM) is de�ned as an IQTM, ICTM or IQCTM, ex ept that thestate transition fun tion is allowed to be a partial fun tion.The restri tion of an ITM M = (Q; q0; qf ; n; Æ) to a set of states Q0 is a partial ITMM = (Q; q0; qf ; n; Æ0),where Æ0 obtained by restri ting Æ to Q0 ��n. �There is no natural interpretation of a partial ITM as an IAQS.

30

4 QUANTUM NETWORK MODELS4 Quantum Network Models4.1 Quantum networksIn this hapter we will introdu e a model for quantum networks. It is based on the model of IAQS des ribed inthe previous hapter and shall be as general a model as possible, not only restri ted to purposes of ryptology.Therefore we do not in lude notions like the adversary or the environment in this model, nor do we give a spe i� s heduling me hanism. This will be done in the spe ialisation des ribed in se tion 5.1 where the adversarialquantum network is introdu ed. We will however already in lude primitive operations like orruption at thispoint.De�nition 4.1: Quantum Network (QN)A quantum network is a ountable set of well-formed IAQS (Ni)i2IN and a set of ma hine IDs IN � ��together with a s heduling fun tion S hedN : �� �! E� � IN ���:Here the elements of E� are �nite, possibly empty sequen es of events, ea h of whi h an be:� a transmission event ontaining a sour e s and a destination d from IN , and a new frame f 2 ��, su han event is written (transmit; s; d; f),� a ontrol event ontaining a destination d 2 IN and a new frame f 2 ��, su h an event is written( ontrol; d; f),� a orruption event ontaining a orrupting party and a orruption target t, both from IN , and a newframe f 2 ��, su h an event is written ( orrupt; ; t; f). �The s heduling fun tion gets as input a string ontaining information on the state and history of the quantumnetwork (the exa t ontent of whi h will be spe i�ed below when de�ning the time evolution of a QN). Theoutput is a list of a tions to be taken, i.e. delivering a message (transmission event) or orrupting a party( orruption event), the token, i.e. the ID of the ma hine to be a tivated next, and a string to be given as partof the input to the next invo ation of S hedN .The transmission event omes together with the sour e and the destination of the message and furtherwith a new frame whi h the re ipient of the message gets. So the re ipient may get wrong or no information on erning e.g. the sender of the message. Note that the message itself is not ontained in the event, afterissuing the event the a tual message will be read from the sender using the send operator US;M.The ontrol event only has a destination and a new frame. It is meant for lassi al noti� ations and ontrolmessages sent from the system to individual parties, e.g. the se urity parameter is given to the parties via a ontrol event.The orruption event has a orrupting party whi h will get the information of the orrupted party, andthe target whi h is to be orrupted. The orruption event will ause the transmission of information from thetarget to the orrupting party, but it will not in�uen e the transmission of messages to or from the target lateron or hinder the further a tivation of the target. So if it is wanted that the target is a tivated no more andall ommuni ation rerouted to the orrupting party, the s heduling fun tion has to implement this. This isdoable, sin e the s heduling fun tion de ides who gets the a tivation token. Further the s heduling fun tionmay reroute messages by just setting the sour e or destination to appropriate values and hanging the newframe thus, that the re ipient will not noti e this rerouting.Outstanding a formal de�nition, we will give here a partial list, whi h are the informations the s hedulingfun tion an extra t of its input:� What ma hines have been a tivated in whi h order so far?� In parti ular: Whi h one was a tivated last?� Whi h were the running times of those ma hines?� What frame was uttered by whi h ma hine after whi h a tivation?� Whi h de isions and outputs did the s heduling fun tion make during past invo ations?31

4.2 Time evolution 4 QUANTUM NETWORK MODELS4.2 Time evolutionThe above de�nition of a quantum network is still quite meaningless. We need to know how it evolves overthe time. Therefore we will now spe ify what happens in a single time step.First we need to know in what spa e our network operates and in whi h state it begins:De�nition 4.2: Con�guration spa e and start on�guration of a QNThe start on�guration of an QN N is given asj0;N i := j#i j#i j#i Oi2IN (j0;Nii j#i)whi h is an element of HN := HG;N HF HC Oi2IN (HQ;Ni HH;Ni):The symbols j0;Nii, HQ;Ni , HF , HC denote the start on�guration, the on�guration spa e, the frame tapespa e resp. the ommuni ation spa e of ma hine Ni as de�ned in se tion 3.1. Three new Hilbert spa esappear above: The networks on�guration spa e HN , the ma hine history tape spa e of Ni, whi h is de�nedas HH;Ni := C�� , and the global history tape spa e of N , given by HG;N := C�� . �We see that the on�guration of a QN onsists of one storage for a �global history�, the (shared) ommuni ationand frame tapes, and for ea h ma hine of its state and a storage for a �ma hine history�.The purpose of the global history is to store all information whi h gets �measured� during the exe ution ofthe quantum network. Sin e we do no assume an external measurement pro ess (but see se tion 5.5), we haveto simulate the measurement by opying all information whi h is taken as lassi al onto the global historytape. There is another purpose of this history: the s heduling fun tion gets its ontent as input and an thusbase on all past measured information to de ide whi h a tions to invoke.The lo al history serves another purpose. At di�erent times some measurements are done on the IAQS,e.g. it is measured whether the ma hine has terminated, what frame it has issued, et . Sin e we want to modelsystems without reliable erasure (resp. its weakened quantum variant as dis ussed in 1.7) a ma hine oulduse the following tri k to ir umvent this restri tion: Assume some number, oded unary, at a known positionon some tape. The ma hine goes to the end of that number, starts erasing 1's until a # is found. Then itterminates. Every step is reversible, so the time evolution of this ma hine is in fa t unitary. But the end on�guration is independent of the number. What has happened? The information is not lost, but it is nowen oded in the running time T of the ma hine. We have to apply the inverse time evolution T times to get theinitial state. Sin e we do not want to enable the ma hine to forget information using this method, we writeinformations like the running time onto the history tape and make this tape a essible to a orrupting party.We will now �rst des ribe the time evolution UN of a quantum network and give the formal but quite omplex de�nition in se tion A.4.Let jGi jframei j ommi Oi2IN (jNii jhistii)be the state of the QN, where we assume everything exept jNii to be a base state.14 Then one step of thetime evolution is given by appli ation of the following steps:1. Find the last datum of the formÆ(s hed; events; token; data) on jGi and set i := token. If there is nosu h datum, ontinue with step 9.2. Let UNi operate on jNii.3. Measure, whether jNii is an end on�guration (using PF;Ni). We will all the result of this measure-ment Fi.4. Append end onf:Fi to jGi and jhistii.5. If Fi = 0 (�not an end on�guration�), do not exe ute the following steps, but append nos hed to jGi.1514If the state is a tually a superposition of thus formed states, just apply the time evolution to ea h summand.15We append nos hed, so that step 10 by itself is unitary. It has no relevan e for the intuitive meaning of this algorithm.32

4 QUANTUM NETWORK MODELS 4.2 Time evolution6. Apply UFS;Ni to jNii jframei.7. Append frame:jframei to jGi and jhistii.8. Set jframei to an empty string.9. Evaluate (events,token,data) := S hedN (jGi).10. AppendÆ(s hed; events-txt; token; data) to jGi.Here events-txt is the texti� ation of events, de�ned via (e1; : : : ; en) := events, (ti; i1; : : : ; im) := ei, t0i :=transmit; orrupt or ontrol, depending on ti, e0i := (t0i; i1; : : : ; im) and events-txt :=Æ(e01; : : : ; e0n).11. For ea h event e in events evaluate it as des ribed below.A transmission event we evaluate as follows:1. Let sour e be the sour e of the event and dest its destination. newframe shall denote the new frame.2. Let US;Nsour e operate on jNsour ei j ommi.3. Write newframe onto jframei.4. Let UR;Ndest operate on jNdesti jframei j ommi.A ontrol event is handled by:1. Let dest be the destination of the event and newframe the the new frame.2. Write newframe onto jframei.3. Let UR;Ndest operate on jNdesti jframei j ommi.A orruption event is evaluated by the following steps:1. Let orrupter be the orrupting party and target the orruption target. As above, newframe is the newframe.2. Write newframe onto jframei and append jhisttargeti by opying.3. Let U orr;Ntarget operate on jtargeti j ommi.4. Let UR;N orrupter operate on j orrupteri jframei j ommi.We will now explain the individual steps of the time evolution.Step 1 �nds out, whi h is the a tive ma hine. We do this by sear hing the last output of S hedN , whi hwe have stored on jGi in step 10. From now on i ontains the ID of the a tive ma hine.Step 2 lets the a tive ma hine operate one time step.In step 3 we �nd out, whether the a tive ma hine Ni has halted. In step 4 the result of the �measurement�if stored on jGi for further use and to make this information lassi al. Note that the term �measurement� isnot formally orre t here, sin e all that is done is to let the exe ution of the following steps depend on whetherNi has halted. Sin e this is done in superposition, no a tual measurement takes pla e.Then, due to step 5, we only exe ute the rest of the steps, i.e. steps 6�11, if the ma hine has halted. Thee�e t of this is that iterated appli ation of the time evolution exe utes a loop, whi h is approximately des ribedby the following pseudo- ode:while true dorepeattime step of a tive ma hineuntil ma hine has terminateddo s heduling, messages transmission, et .end while 33

4.3 Classi al quantum networks 4 QUANTUM NETWORK MODELSIn steps 6�8 we extra t the frame out of the a tive ma hine, store it onto jGi and then erase the ontentsof jframei again to make it free for future use. The frame the ma hine has sent is now stored on jGi.Steps 9 and 10 all the s heduling fun tion and store its output onto jGi. In our model storing theinformation on jGi does not make any di�eren e, sin e the information is deterministi ally depend of theforegoing ontent of jGi. We nevertheless in lude this step here to make it learer, that S hedN has a ess tothe output of all its previous invo ations, to make formulation of step 1 simpler, and to make it possible toextend the notion of the s heduling fun tion to e.g. a probabilisti one.In step 11 all the a tions requested by S hedN are invoked. Note that we do not do anything here withthe token the s heduling fun tion has yielded, this is done at the beginning of the next iteration by step 1.When evaluating a transmission event, we extra t the data to be sent from Nsour e via US;Nsour e andtransfer it to Ndest using UR;Ndest , together with the newframe supplied by S hedN .A ontrol event di�ers from the transmission event in that we do not fet h data from a sour e, but insteadleave j ommi unmodi�ed (i.e. ooled), so that the only information gotten by the destination is that ontainedin the new frame.When a orruption event is to be evaluated, we extra t the state from Ntarget using U orr;Ntarget and sendit, together with newframe and the history of Ntarget to N orrupter. The history is given to Ntarget as part ofthe frame, sin e it is lassi al information and we use the frame for su h by onvention.A omplete formal de�nition, together with a proof that the time evolution is unitary, an be found inse tion A.4.4.3 Classi al quantum networksWe have de�ned lassi al IAQS and IAQS with lassi al interfa es in se tion 3.4. So its is straightforwardto de�ne lassi al quantum networks and quantum networks with lassi al interfa es, i.e. quantum networks,that ontain only ma hines with that property.De�nition 4.3: Classi al quantum networksWe say a quantum network N is is lassi al, when all its ma hines Ni (i 2 IN ) are lassi al. �De�nition 4.4: Quantum networks with lassi al interfa esWe say a quantum network N has lassi al interfa es, when all its ma hines Ni (i 2 IN ) have lassi alinterfa es. �Note that it is enough to require lassi al behaviour (or lassi al interfa es) of the ma hines, sin e all matri esappearing in the time evolution of the quantum network, ex ept those appertaining to the ma hines, arepermutations of basis ve tors.

34

5 ADVERSARIAL COMMUNICATION5 Adversarial Communi ation5.1 Adversarial quantum networkIn the previous se tion we have developed the notion of a quantum network and of quantum ommuni ation.But this model is still too abstra t for our needs, we need a model ontaining environment, adversary, par-ties, fun tionalities, some on rete s heduling, and a se urity parameter. Therefore we will now de�ne theadversarial quantum network.De�nition 5.1: (Adaptive) adversarial quantum network (AQN)An (adaptive) adversarial quantum network (AQN) N onsists of a sequen e of quantum networks (N (k))k2N,whi h are identi al ex ept for the s heduling fun tions, and whose set of IDs isIN (k) = Iadv = fE;Ag [ IP [ IF ;where IP = fPg�(�n#)+ and IF = fFg�(�n#)+, further of an a ess stru ture fN : IP�IF [IF�IP ! f0; 1g,and of a orruption stru ture AN � 2IP . The s heduling fun tion S hedN (k) is the adaptive adversarials heduling fun tion to the parameter k as de�ned below.We all fN a full a ess stru ture, if its image is f1g.The set of all adversarial quantum networks is alled AQN. �De�nition 5.2: Stati adversarial quantum network (SAQN)A stati adversarial quantum network (SAQN) is de�ned exa tly as the adaptive adversarial quantum network,ex ept that the s heduling fun tion is the stati adversarial s heduling fun tion. �5.2 S hedulingThe s heduling is the point, in whi h we deviate most from the se urity model presented in [Can00b℄�besidethe fa t that we allow quantum ommuni ation, of ourse. This is due to the fa t, that we have hosen notto use message driven s heduling16, but some kind of non-preemptive multitasking, i.e. the identity of there ipient of some message has no in�uen e on the party whi h is a tivated next, instead the adversary isa tivated after any a tivation of some other ma hine to de ide, whi h ma hine should get the token next. Wehave hosen this approa h, sin e �rst this seems to model the reality more exa tly, sin e in reality the deliveryof messages does not in�uen e the distribution of omputational time; se ond, the message driven model tendsto get unne essarily ompli ated, sin e it has to have a rule, whi h ma hine is a tivated next for ea h possiblea tion of any parti ipant of the ommuni ation.Another important point on erning the s heduling is ensuring that no polynomial party gets a tivatedmore than a polynomial number of times. The most apparent way to do this is to say, that a polynomialma hine an be a tivated at most a polynomial number of times. But then we have to de ide, what shouldhappen after rea hing that limit for some ma hine. If we say, that the proto ol should stop, if some ma hineis a tivated too often, then even a polynomial adversary ould halt the proto ol just by a tivating some partytoo often (a polynomial number of times is su� ient, sin e the adversary has w.l.o.g. a greater polynomial tobound its running time).The other alternative is to say that the ma hine behaves as a dummy ma hine after rea hing the limit, inthat way that it just gives ba k the token without sending a message or the like when a tivated again. Herethe problem is, that the adversary ould �kill� a ma hine by a tivating it too often. Image a proto ol withparties A, B, C, whi h should implement a fun tionality ommuni ating only with A and B. Assume further,that the proto ol needs C to work. Than the environment ould distinguish the real and the ideal proto ol ifthe adversary �kills� C. This is not a desired property.One ould propose, that just environment and adversary should be limited in that way, not the partiesand fun tionalities. But then it would be impossible to make statements like �there is no proto ol running inpolynomial time that implements. . . �, sin e this would imply quantifying about polynomial parties.Therefore we introdu e another model to ensure a polynomial total step ount: There is a variable in ourmodel, all the time blo k number. This time blo k number an be in reased by the adversary at will, providedthat the adversary in reases the time blo k after at most a polynomial number of invo ations. Then we will16A message driven s heduling is one, in whi h the question, whi h ma hine is to be a tivated next, is strongly in�uen ed by theidentity of the re ipient of the message. A purely message driven approa h would always a tivate the re ipient of the message, ina se urity model however this is not feasible, sin e the adversary should be a tivated between the parties' invo ations, resultingin some mixed model. 35

5.2 S heduling 5 ADVERSARIAL COMMUNICATIONde�ne se urity su h, that se urity should be provided, when the model runs a polynomial number of timeblo ks, i.e. it should be se ure for any su� iently large polynomial. This is motivated by the fa t, that inreality there is no hard limit on the running time of a proto ol, up to whi h we want to maintain se urity,instead we want to ensure se urity for any reasonable (i.e. polynomial) running time.But why do we not just restri t the proto ol exe ution to a polynomial number of invo ations instead ofintrodu ing the on ept of time blo ks? This is due to the fa t, that the environment an �nd out, afterhow many of its a tivations the exe ution terminates, using the following tri k: After the n-th invo ation,the environment terminates with output 0 with a probability of (n + 1)�2. Then when terminating after theN -th invo ation, the probability that the environment has not output 0, is PN := QNn=1(n + 1)�2. So if inthe real and the ideal model the environment is a tivated a di�erent number of times, we get some di�erentprobabilities PN for a non-zero output independent of the se urity parameter. Therefore real and ideal proto olare distinguishable only be ause the number of invo ations between two invo ations of the environment aredi�erent.Further solving this problem using time blo ks makes it easier to think of extensions of the model, wheresome ma hines are allowed to be invoked more than a polynomial number of times, while some others are not.The restri tion, that in any time blo k there are at most a polynomial number of a tivations, is ensuredby the well-formedness of the adversary (see de�nition 5.5).So the s heduling in our model goes as follows:� The adversary is a tivated �rst.� Whenever the adversary is a tivated, it may de ide, whi h ma hine is a tivated next.� If some ma hine other than the adversary was a tivated last, the adversary is a tivated next.� Any ma hine whi h is a tivated for the �rst time, gets a frame ontaining the se urity parameter inunary notation.� If the adversary requests this, the time blo k number is in reased.� The environment may transmit a message to some party or the adversary. If the re ipient is orrupted,the message is rerouted to the adversary.� The adversary may do one of the following:� Send a message to the environment or some fun tionality, indi ating the orre t sender.� Transmit a message, indi ating some orrupted party as the sender. This is allowed in thosesituations, in whi h the party would have been allowed to send that message (see below).� Corrupt a party. This is only possible if afterwards the set of orrupted parties is an element of A.The environment is informed about this.� A party may send a message to the environment or some fun tionality. If the re ipient is a fun tionality,the party must have a ess to that fun tionality.� A fun tionality may send a message to the adversary or to some party. If the re ipient is a party, thefun tionality must have a ess to that party. If the re ipient is orrupted, the message is rerouted to theadversary.These points are realised by the following s heduling fun tion:De�nition 5.3: Adversarial s heduling fun tionThe adversarial s heduling fun tion to the parameter kS hedN (k) : �� �! E� � Iadv ���is given the output of the following algorithm (the notation of the foregoing de�nition still applies):1. Let events := " (sequen e of length 0), token := ?.36

5 ADVERSARIAL COMMUNICATION 5.2 S heduling2. Extra t from input:lasttoken ID of the ma hine whi h last had the token (or ?). orr Set of orrupted parties.timeblo k Time blo k (from data part of last invo ation of S hedN ).running List of ma hines whi h ever have had the token.frame Frame sent by the last a tivated ma hine (or ?).token-req Next token as requested in frame (or ?, if frame is synta ti ally in orre t).timeblo k-req Equals 1 if an in rement of the time blo k is requested in frame, ? otherwise.event-req Event requested in frame, i.e. one of ftransmit; orrupt;?g.destination-req Destination of the requested event (in ase of transmit).sour e-req Sour e of the requested event (in ase of transmit).target-req Target of the requested event (in ase of orrupt).This means formally:� Let k 2 N0 and (ai)ki=1 (ai 2 ��) be su h, that Æ(a1; : : : ; ak) is the input to the algorithm, or, ifno su h k, (ai) exist, let k := 0.� Let (Æ(s hed; bi;ev; bi;tok; bi;dat))li=1 be the subsequen e of (ai), that onsists of all elements havingthe formÆ(s hed; �; �; �).� If l > 0 and bl;tok 2 Iadv, then let lasttoken := bl;tok. Otherwise set lasttoken := ?.� Let orr be the set of all p 2 IP , whi h satisfy, that there is an i, s.t. bi;ev has the formÆ(�; : : : ; �;Æ( orrupt; �; p; �); �; : : : ; �).� Let timeblo k be su h, that bl;dat =Æ(timeblo k; u(timeblo k)). Let timeblo k := 0, if there is novalue of timeblo k satisfying that ondition. Here u is de�ned as in de�nition 3.21.� Let running := fm 2 Iadv : 9i 2 f1; : : : ; lg : bi;tok = mg.� If there is an element of (ai) having the form Æ(frame; �), then let Æ(frame; frame) be the lastsu h element. Otherwise let frame := ?.� Let (fi)mi=1 be su h, thatÆ(f1; : : : ; fm) = frame. If this is not possible, set m := 0.� If there is an element of (fi) having the formÆ(token; �), than letÆ(token; token-req) be the �rstsu h element. Otherwise let token-req := ?.� If there is an element of (fi) having the form timeblo k, than let timeblo k-req := 1, otherwisetimeblo k-req := 0.� If there is an element of (fi) having the formÆ(event; �), than let Æ(event; e) be the �rst su helement. If e = transmit or e = orrupt, set event-req to transmit resp. orrupt. In all other aseslet event-req := ?.� If there is an element of (fi) having the form Æ(destination; �), than let Æ(destination;destination-req) be the �rst su h element. Otherwise let destination-req := ?.� If there is an element of (fi) having the formÆ(sour e; �), than letÆ(sour e; sour e-req) be the�rst su h element. Otherwise let sour e-req := ?.� If there is an element of (fi) having the formÆ(target; �), than letÆ(target; target-req) be the�rst su h element. Otherwise let target-req := ?.3. If timeblo k-req = 1, in rease timeblo k by 1.4. Handle the token as follows:(a) If last = A, token-req 6= ?, and token-req =2 orr, set token := token-req.(b) Otherwise set token := A.( ) If token =2 running, append ( ontrol; token;Æ(se param; 1k))to events, where 1k denotes the unary representation of the se urity parameter k.37

5.3 Adversary types 5 ADVERSARIAL COMMUNICATION5. In the following table, �nd that row, whi h mat hes last and whose onditions are satis�ed, and appendthe orresponding events to events. If no row mat hes, leave events un hanged.last onditions events= E event-req = transmitdestination-req 2 fAg [ IP n orr (transmit; E; destination-req;Æ(message; E; destination-req))event-req = transmitdestination-req 2 orr (transmit; E;A;Æ(message; E; destination-req))= A event-req = transmitdestination-req 2 fEg [ IFsour e-req = A (transmit; A; destination-req;Æ(message; A; destination-req))event-req = transmitsour e-req 2 orrdestination-req = E (transmit; A;E;Æ(message; sour e-req; E))event-req = transmitsour e-req 2 orrdestination-req 2 IFfN (last; destination-req) = 1 (transmit; A; destination-req;Æ(message; sour e-req; destination-req))event-req = orruptftarget-reqg [ orr 2 Atarget-req =2 orrtoken 6= target-req ( orrupt; A; target-req;Æ( orrupted; target-req));( ontrol; E;Æ( orrupted; target-req)) (�)2 IP event-req = transmitdestination-req = E (transmit; last; E;Æ(message; last; E))event-req = transmitdestination-req 2 IFfN (last; destination-req) = 1 (transmit; last; destination-req;Æ(message; last; destination-req))2 IF event-req = transmitdestination-req = A (transmit; last; A;Æ(message; last; A))event-req = transmitdestination-req 2 IP n orrfN (last; destination-req) = 1 (transmit; last; destination-req;Æ(message; last; destination-req))event-req = transmitdestination-req 2 IP \ orrfN (last; destination-req) = 1 (transmit; last; A;Æ(message; last; destination-req))6. Return (events; token;Æ(timeblo k; timeblo k)). �De�nition 5.4: Stati adversarial s heduling fun tionThe stati adversarial s heduling fun tion is de�ned exa tly like the adaptive one, ex ept that the row in thetable of step 5 marked with (�) has the additional ondition running � fA;Eg. �This additional onstraint has the e�e t, that the adversary may not orrupt any party after some party orfun tionality has been a tivated, i.e. only at the very beginning or the proto ol exe ution.Another, stri ter de�nition of stati ould have the ondition running � fAg, i.e. the adversary must de idewhom to orrupt even before ommuni ating with the environment.5.3 Adversary typesAs we have seen in the pre eding se tion, the adversary is responsible for the order of a tivation in theadversarial quantum network. Sin e it should further be impossible, that a polynomially bounded adversarygets de fa to more than polynomial time by a tivating itself very often without in reasing the number of thetime blo k, we should restri t the adversaries to su h ones, whi h are �fair� in this respe t, i.e. the adversaryshould be invoked at most a polynomial number of times between two in reases of the time blo k number.De�nition 5.5: Well-formedness of an adversaryFor any polynomial p let Fk;p be the set of exe ution trans ripts � = (xi) whi h satisfy both of the following onditions: 38

5 ADVERSARIAL COMMUNICATION 5.3 Adversary types� pre eding the n-th element of � having the form (stop;Æ(�; : : : ; �; timeblo k; �; : : : ; �)), there are at mostp(k + n) elements of the form (stop; f) with f 2 ��,� there is an in�nite number of elements formed (stop;Æ(�; : : : ; �; timeblo k; �; : : : ; �)) in �,and one of� for the �rst element of � having the form (re ; f) the word f has length k,� there is no su h element and k = 0.Let E be the set of all exe ution trans ripts.We then say an adversary A 2 IAQS is well-formed, if there is a polynomial p, su h that E nSk2N0 Fk;p isimpossible. �Here Fk;p is the set of exe ution trans ripts, in whi h the �rst frame has length k and there the number ofinvo ations of the adversary until the n-th time blo k is bounded by p(k + n). So E n Sk2N0 Fk;p denotestrans ripts whi h violate the informal well-formedness ondition stated at the beginning of this se tion.Note that it does not make a di�eren e, whether we require E n Sk2N0 Fk;p to be impossible or to haveprobability 0.17When we try to onsider robustness against denial of servi e atta ks, we see that the adversary may hindertermination of the proto ol by just not giving time sli es to some party, maybe even taking all time sli esfor itself. This is learly allowed by the notion of well-de�nedness, but in many ases we may need somenon-blo king adversary whi h will not stop any party inde�nitely. We again have several variants:� Non-blo king: Ea h ma hine is invoked an in�nite number of times.� Polynomially non-blo king: Ea h ma hine is invoked an in�nite number of times and between two of itsinvo ations there passes at most a number of time blo ks polynomial in the se urity parameter, in theID of the party, and in the number of the invo ation.In the �rst variant we again have to distinguish between the impossibility of violating our ondition and theprobability of 0.18In the se ond one this distin tion does not make a di�eren e.17Note that our de�nitions imply termination of the adversary, sin e otherwise the ma hines would not gettheir in�nite number of invo ations.De�nition 5.6: (Sto hasti ally) non-blo king adversaryLet R be the set of exe ution trans ripts � = (xi), whi h satisfy that for any ma hine P 2 Iadv there is anin�nite number of xi in � with xi = (stop; token:P ).Let E be the set of all exe ution trans ripts.We all an adversary A 2 IAQS non-blo king, if E nR is impossible on any quantum intera tion.An adversary A 2 IAQS is sto hasti ally non-blo king, if, for any quantum intera tion �, the probabilityP (X 2 E nR) vanishes, where X is the exe ution trans ript on �. �Here R is the set of the trans ripts, in whi h every party is a tivated an in�nite number of times, or equivalently,in whi h no party is ever a tivated for the last time. So this de�nition requires, that it is impossible or hasprobability 0, that a party is sometime a tivated for the last time.A separating example for those two de�nitional variants would be an adversary, whi h on every a tivationi sele ts some ma hine Mi with P (Mi = j) / e�j . It isP (some j appears only a �nite number of times in (Pi)) = 0;but learly any sequen e of a tivations is possible.De�nition 5.7: Polynomially non-blo king adversaryLet R be as in the previous de�nition, and let RP;n;m;k (P 2 Iadv, n 2 N, k;m 2 N0) be the set of all exe utiontrans ripts � = (xi), whi h satisfy, that there is an n-th element of � having the form (stop;Æ(�; : : : ; �;Æ(token; P ); �; : : : ; �)), and in front of it there are at most m elements having the form (stop;Æ(�; : : : ; �;timeblo k; �; : : : ; �)), and whi h additionally satisfy one of:17We omit the proof for this statement, but it uses ideas similar to the reasoning presented in se tion A.3.18Image an adversary randomly hoosing the next re ipient of the token out of a linearly growing set of ma hines. Then it isof probability 0, though not impossible, that some party gets the token only a �nite number of times.39

5.4 Proto ols and adversarial ommuni ation frameworks 5 ADVERSARIAL COMMUNICATION� for the �rst element of � having the form (re ; f) the word f has length k,� there is no su h element and k = 0.Let E be the set of all exe ution trans ripts and i : Iadv ! N0 any mapping.We all an adversary A 2 IAQS polynomially non-blo king with respe t to i if there is a polynomial p, su hthat on any quantum intera tion the following set is impossible:E n �R \ [k2N0 \P2Iadv \n2NRP;n;p(i(P )+n+k);k� (19)where we onsider sets RP;n;m;k with negative m as empty. �Here RP;n;m;k is the set of all trans ripts with se urity parameter k, in whi h the ma hine P was a tivatedfor the n-th time in the m-th time blo k or earlier. So (19) denotes the set of trans ripts, whi h are not in R(i.e. do not even satisfy the non-blo king property de�ne previously) or for whi h have a se urity parameter k,su h that there is a party P and an invo ation number n, su h that the n-th invo ation of P does not happenbefore time blo k p(i(P ) + n+ k), i.e. within polynomial time.We have still to larify the meaning of the fun tion i. As seen above, it is used to assign ea h party anumber, so that the expression �polynomial in the ID of the party� gets meaningful. But what a fun tion shallbe used here? This in fa t depends strongly of the situation. But the following points should be onsidered:� A bounded fun tion i should not be taken, sin e then an in�nite number of parties must be invokedwithin a �nite number of time blo ks (namely p(maxP i(P ) + 1 + k)), whi h is obviously impossible.� Also many unbounded fun tions i are infeasible for similar reasons, at least for a well-formed adversary.� If there is only a �nite number of non-dummy ma hines, the following onstru t an be used for i: Let~{ : Iadv ! N0 be an arbitrary inje tive fun tion. Then set i(P ) := 0 for non-dummy ma hines andi(P ) := ~{(P ) for dummy ma hines.This is feasible even for a well-formed adversary19 and fair with regard to the non-dummy ma hines.� Pay attention not to use simply any arbitrary enumeration of Iadv. If you have e.g. non-dummy ma hineswith IDs P:1n an would enumerate them by taking i to yield the number of the party interpreted as abinary string, and not as a unary one, then i would grow exponentially in n, though n would intuitivelybe onsidered the number of the party.Try to �nd out what intuitively is the enumeration of the parties, and hoose i a ordingly.� If the number of ma hines partaking the proto ol in always �nite, but grows with k, then try to hoose thei su h, that there is a polynomial q su h that i(P ) < q(k) for ea h k and all ma hines partaking on se urityparameter k, and additionally for all n the ardinality of i�1(fng) should be bounded polynomially inn. This gives a sensible and feasible de�nition of polynomially non-blo king adversaries for this ase.5.4 Proto ols and adversarial ommuni ation frameworksIn order to fa ilitate the de�nition of se urity in hapter 6, we now introdu e the notion of the adversarial ommuni ation framework. It is an AQN without adversary, environment, parties, or orruption stru ture. Soit basi ally is the underlying ommuni ation ar hite ture in whi h we want to exe ute our proto ol.De�nition 5.8: Adversarial ommuni ation framework (ACF)An adversarial ommuni ation framework (ACF) C is a sequen e of fun tionalities (Ci)i2IF (Ci 2 IAQS), andan a ess stru ture fC : IF � IP [ IP � IF ! f0; 1g. �The de�nition of a proto ol is fairly simple:De�nition 5.9: Proto olA proto ol � is a mapping � : IP ! IAQS; i 7! �i and an asso iated ACF C�. �We an now ombine those two de�nitions:De�nition 5.10: Instantiation of an ACFLet C be an ACF. Let further be E ;A 2 IAQS (the environment and the adversary), A � 2IP (the orruption19A tivate e.g. in time blo k n the parties P with i(P ) < n. 40

5 ADVERSARIAL COMMUNICATION 5.5 Output of an AQNstru ture) and � a proto ol. Then the adaptive resp. stati instantiation of C with environment E, adversaryA, orruption stru ture A and the proto ol � is denoted by C(adaptive; E ;A;A; �) resp. C(stati ; E ;A;A; �),and de�ned to be the adaptive resp. stati AQN N onstru ted as follows:The a ess stru ture of is taken from C (fN := fC), the spe i�ed environment, adversary and orruptionstru ture are used as spe i�ed (N (k)E := E , N (k)A := A, AN := A), the fun tionalities are taken from the ACF(N (k)i := Ci for i 2 IF ) and �nally the parties from the proto ol (N (k)i := �i for i 2 IP ). �5.5 Output of an AQNWe now have a notion of adversarial quantum networks, whi h ontain an environment. But for our de�nitionof se urity we need to de�ne, what the output of the environment is, i.e. the overall out ome of our experiment omparing the two proto ols. Therefore we will de�ne the output of an AQN as follows:Let N be an AQN. The output Outk(N ) of N with se urity parameter k is a probability distribution overf0; 1;?g, given by the following probabilisti algorithm:1. Set jN (k)i 2 HN to j0;N (k)i, i.e. to the start on�guration of N (k).2. Apply UN (k) to jN (k)i, i.e. let the network evolve one time step.3. Measure the ontent of the global history tape, i.e. measure HG;N (k) . Let the out ome of that measure-ment be G.4. Sear h on G for the �rst frame output by E whi h is of the form return0 or return1. Call it r.5. Go to step 2, if no su h frame was found.6. If r = return0, terminate and output 0.7. If r = return1, terminate and output 1.If the algorithm does not terminate, let its output be ?.Additionally we need the notion of the output Outk;n(N ) of N with se urity parameter k after n timeblo ks. It is de�ned by a similar algorithm, in fa t we only need to hange step 4 into4. Sear h on G for the �rst frame output by E whi h is of the form return0, return1 or for the �rst outputof the s heduling fun tion ontainingÆ(timeblo k; u(n)), whi hever omes �rst. Call it r.and append a last step8. If r =Æ(timeblo k; u(n)), terminate and output ?.Formally, these two on epts are de�ned as follows:De�nition 5.11: Output of an AQNLet N be an AQN. The output Outk(N ) of N with se urity parameter k is a probability distribution overf0; 1;?g, de�ned as follows:Let for some G 2 �� be Æ(g1; : : : ; gm) := G. If this is not possible, let m := 0. Let r0(G) be minimalwith gr0(G) =Æ(frame; E; return0) or, if no su h index exists, r0(G) :=1. Let also r1(G) be minimal withgr1(G) =Æ(frame; E; return1) or r1(G) :=1.Let P0 be the proje tion onto spanfG 2 �� : r0(G) <1; r0(G) < r1(G)gand P1 the proje tion onto spanfG 2 �� : r1(G) <1; r1(G) < r0(G)gThen P (Outk(N ) = i) := limT!1kPiUTN (k) j0;N (k)ik2 (i = 1; 2)and P (Outk(N ) = ?) := P (Outk(N ) =2 f0; 1g): �41

5.5 Output of an AQN 5 ADVERSARIAL COMMUNICATIONIn this de�nition, r0(G) denotes the index on the global history tape, where the environment has outputreturn0. Sin e to that tape data is only appended, r0(G) indi ates the time, when the environment outputthis frame. The same holds for r1(G) and return1.Therefore P0 proje ts onto all on�gurations, in whi h there was an output return0, and in whi h ito urred before a potential output return1. The analogue is valid for P1.So �nally tr �Pi( �MG �UN (k))T %(j0;N (k)i)is the probability, that the output of the algorithm is i after T steps, where MG is the measurement of theglobal history tape and �X is the density matrix operator for X .Sin e U := UN (k) operates inje tively on jGi, i.e. for U ji jGi =Pi �ijiijGii the value of G is known,when one of the Gi is known, it is �MG �U �MG = �MG �U .20So we an simplifytr �Pi( �MG �UN (k))T %(j0;N i) = tr �MG �Pi �UTN (k)%(j0;N i) = tr �Pi �UTN (k)%(j0;N i) = kPiUTN (k) j0;N ik2;where we use additionally, that the �Pi and �MG ommute, and that �MG is tra e-preserving.So P (Outk(N ) = i) is the probability, that the algorithm yields i at all. (Note that the argument of thelimes is monotone in n, so we an use the limes here.)De�nition 5.12: Output of an AQN after n time blo ksLet N be an AQN. The output Outk;n(N ) of N with se urity parameter k is a probability distribution overf0; 1;?g, de�ned as follows:For any G 2 ��, let g1; : : : ; gm, r0(G) and r1(G) be as in the pre eding de�nition. Let further tn(G) beminimal su h that gtn(G) has the form Æ(s hed; �; �;Æ(timeblo k; n). Let tn(G) := 1, if there is no su hindex.Let P0;n be the proje tion ontospanfG 2 �� : r0(G) <1; r0(G) < r1(G); r0(G) < tn(G)gand P1;n the proje tion ontospanfG 2 �� : r1(G) <1; r1(G) < r0(G); r1(G) < tn(G)gThen P (Outk;n(N ) = i) := limT!1kPi;nUTN (k) j0;N (k)ik2 (i = 1; 2)and P (Outk;n(N ) = ?) := P (Outk;n(N ) =2 f0; 1g): �Here tn(G) is the moment, in whi h the n-th time blo k is entered, so that Pi;n are proje tions similar toPi, with the additional onstraint, that the on erning frame must have been output before time blo k n,otherwise it is ignored.Therefore we get P (Outk;n(N ) = i) to be the probability of an output i in the above algorithm.Note that Outk(N ) = limn!1Outk;n(N ). We omit the formal proof for this.

20This is due to the fa t, that the result of the �rst MG-measurement is ompletely determined by the se ond one, so the �rstone an be omitted. A formal proof of this statement is given in se tion A.5.42

6 BASIC SECURITY MODEL6 Basi Se urity ModelIn this hapter we will introdu e the formal de�nition of se urity. Due to the work in previous hapters, thede�nitions are omparatively simple.We will distinguish several notions of se urity, di�erentiated by several parameters:First we distinguish between adaptive and stati se urity. In the adaptive ase, the adversary is free to orrupt parties at any time, while in the stati ase, it may only orrupt before any ma hine ex ept theadversary and the environment have been a tivated.Se ondly we may spe ify, when two output distribution ensembles are to be onsidered indistinguishable.Any relation an be spe i�ed, but two spe ial ases are of greater importan e and have proper names: Inthe ase of absolute se urity, we demand omplete equality between the two ensembles, while in the ase ofapproximative se urity, the sto hasti indistinguishability as de�ned in de�nition 2.8 is assumed.The third point we may spe ify is, whi h parties may be orrupted. This is spe i�ed by a set of sets A. Aparty may be orrupted, if and only if the resulting set of orrupted parties is an element of A.Further we may restri t the sets of environments and adversaries, over whi h is quanti�ed.And lastly may spe ify in whi h ACF the proto ols to be ompared are to be exe uted. If unspe i�ed,their asso iated ACF are assumed.De�nition 6.1: Se urityWe all a proto ol � adaptively resp. stati ally as se ure as a proto ol % with respe t to an indistinguishabilityrelation �, an environment set CE , an adversary set CA, a orruption set A � 2IP , and ommuni ationframeworks C�, C% (written � ��;x;CE ;CA;A;C�;C% %), where x is adaptive resp. stati , if for ea h well-formedadversary A 2 CA there is a well-formed adversary S 2 CA with polynomial running time relative to A, sothat for ea h environment E 2 CE the following equation holds:(Outk(C�(x; E ;A;A; �)))k � (Outk(C%(x; E ;S;A; %)))kIf x is not spe i�ed, we assume x = adaptive.If CE or CA are not spe i�ed or given by the ontext, we assume the set of all IAQS.If C� or C% are not given we assume the ommuni ation framework asso iated to � resp. %.If � is not given, we assume the sto hasti indistinguishability de�ned in de�nition 2.8 and talk aboutapproximative se urity (� is approximatively as se ure as %).If � is equality, we talk about absolute se urity (� is absolutely as se ure as %). �The foregoing de�nition is just what we have developed in se tion 1.6. Noti eable is only the order of quanti�ers.We require, that the ideal adversary S depends only of the real adversary A, but is independent of theenvironment E . This is the stri ter variant ( ompared with an ideal adversary depending on the environment),and this form is needed for our proof of the omposition theorem, though we do not know whether it wouldstill hold using the weaker variant.De�nition 6.2: Se urity under polynomial running timeWe say � is as se ure as % under polynomial running time21 if for ea h well-formed adversary A 2 CA there isa well-formed adversary S 2 CA, so that for su� iently large polynomials p the following equation holds forea h environment E 2 CE :(Outk;p(k)(C�(x; E ;A;A; �)))k � (Outk;p(k)(C%(x; E ;S;A; %)))kNotational onventions are as in the above de�nition of se urity. �Here we restri t the running time (more exa t: the number of time blo ks, whi h is the time as seen by theenvironment) to be bounded by a polynomial in the se urity parameter. Obviously we should not restri tthe de�nition to some parti ular polynomial, so we want the indistinguishability for any su� iently largepolynomial. The quanti�er for the polynomial has been inserted thus, that the de�nition is stri test possible.Note that this de�nition is more an auxiliary one, more useful is the following one:De�nition 6.3: Polynomial se urityWe say � is polynomially as se ure as %21 (� �P;�;x;CE;CA;A;C�;C% % or simply � �P %) if � is as se ure as %under polynomial running time with respe t to environment set CE \ PITM and adversary set CA \ PITM.Notational onventions are as in the above de�nitions of se urity. �21with respe t to the same things as in the de�nition of se urity above.43

6 BASIC SECURITY MODELIn the de�nition of se urity under polynomial running time we had no restri tion on the nature of environmentor adversary. In the de�nition of polynomial se urity, however, we restri t these to be PITM, sin e our intuitivenotion of polynomial running time is, that no party an evaluate more than a polynomial number of time steps.By restri ting the ma hines to polynomial ones, we omply with this intuitive point of view.Sometimes we annot only say, that for any adversary and environment the output distributions are indis-tinguishable, but we an even give a bound to the statisti al distan e independent of the given adversary orenvironment, giving us the possibility to state expli itly what is the maximum probability of a su essful atta kto the proto ol for a given se urity parameter. This stronger notion of se urity is aptured by the de�nitionof se urity with bounded risk:De�nition 6.4: Se urity with bounded riskWe all � as se ure as % with bounded risk (� ��;�;x;CE;CA;A;C�;C% % or simply � �� %) if there is a negligiblebound Æ : N! R�0 (as de�ned in de�nition 2.5), su h that � �� %, where � is the sto hasti indistinguisha-bility with respe t to f" : " = Æ almost everywhereg (as de�ned in de�nition 2.7).Notational onventions are as in the above de�nitions of se urity. �

44

7 EXTENSIONS7 ExtensionsIn this hapter we will present some extensions or variants to the se urity model presented previously. Theseextensions will mostly be given in a less formal way or sometimes even only be hinted.7.1 Multi-phase proto olsThe �rst extension we present is that of multi-phase proto ols. Here we extend our framework (stri tly speakingjust the adversarial s heduling fun tion) to have some additional variable, the urrent phase of the proto ol.This phase is then known to all ma hines, and an be used for the following purposes:� The proto ol spe i� ation may depend on the phases, you may e.g. design a proto ol, where on the �rstday there is some ommuni ation using some se rets, and on the se ond day all se rets are dis losed.� You may design further extensions to the se urity model, where some properties (like available primitives)depend on the urrent phase.The existen e of phases every ma hine knows is justi�ed by the fa t, that in real life we an usually assume,that all ma hine have a reliable onsensus, whi h e.g. is the urrent date, so that a proto ol, whi h runs everyday at noon within some se onds will be learly separated into phases by the day breaks.A new phase is initiated by the environment, sin e we assume those phases to be externally given and notmodi�able by the adversary (e.g. the urrent date).As the set of all phases we take PH := fpre; postg [Q. Here pre denotes the pre-exe ution phase, post thepost-exe ution phase, and q 2 Q is some phase during the proto ol exe ution. We hose Q for the proto olphases, so that before, after and between two phases there may be another phase, giving mu h �exibility. In ases where only a few phases are needed, we an simply partition Q into intervals and onsider all phasesinside one interval as the same phase.The phases are half-ordered, no phase '2 may be a tivated after some phase '1, if '2 < '1. We take herethe natural total-ordering on Q, extended by pre < Q < post.In the pre and the post phase, all ommuni ation to and from the parties is disabled. Only intera tionbetween environment, adversary and fun tionalities, and orruption of parties is possible in these phases.The following hanges are to be made to the s heduling fun tion:� Let ' be the urrent phase.� At the beginning, ' = pre.� If the environment outputs a frame of the formÆ(phase; ), where is some phase,22 and where ' � ,set ' := .� If a ma hine is to be a tivated, whi h was a tivated the last time with another value of ', then send tothat ma hine the urrent phase (using a ontrol event with new frameÆ(phase; ')).� If a message delivery from or to a party is requested, but ' 2 fpre; postg, do not deliver that message.The foregoing de�nition of multi-phase proto ols ontains one problem: The urrent phase might hangebefore the parties have done all al ulation intended for that phase. This is ontrary to the intuitive notion ofphases, sin e in real life it would not happen, that e.g. some day is suddenly and unexpe tedly rather short.This fa t ould possibly introdu e unwanted means of distinguishing real and ideal proto ol. Fortunately, thisdoes only make the de�nition of se urity stri ter. Of ourse, this problem is only of importan e, if we onsidernon-blo king adversaries, in the ase of blo king adversaries, the parties ould be blo ked until the end of thephase anyway, so premature phase hanging does not make any di�eren e.7.2 Temporary assumptionsOften the se urity of proto ols is proven with respe t to some assumptions, e.g. available primitives, om-putational power, or even known algorithms. In some ases however, it may be reasonable to assume thenon-availability of some adversarial resour es for the present, though would be is questionable, whether thesame resour es might not possibly be available in the future. To model this ase, we would like to be able to22There must of ourse be some en oding of phases, e.g. pre and post are pre resp. post, and rs with ggT(r; s) = 1 and s > 0 isÆ(u(r); u(s)) with u(x) = 1n for n � 0 and u(x) = 01�n for n < 0.45

7.2 Temporary assumptions 7 EXTENSIONSformalise statements like �the proto ol is se ure, assuming that some resour e X is not available at moment,but assuming further, that it might be available some day after the proto ol's termination.�An example would be a broad ast hannel implemented using RSA. We ould prove it to be se ure under omputational assumptions, if atta king RSA is not e� iently feasible. But we an further prove, that if someday after the proto ol exe ution there will be e.g. the possibility to fa tor large numbers, then the broad astwould still be se ure, sin e all inputs of the proto ol have been made publi anyway.All extensions des ribed below assume multi-phase proto ols as des ribed in se tion 7.1, of ourse.7.2.1 Available primitivesThe �rst kind of temporary assumption is that of available primitives. We do not implement this by lettingthe fun tionalities be present or absent a ording to the phase, but instead by allowing or restri ting a essto them.To do so, we use fN : (I 0P � IF [ IF � I 0P )�PH �! f0; 1gas the a ess fun tion of the QN N . Here I 0P := IP [ fAg.Then in the s heduling fun tion, the urrent phase is given as the se ond argument to fN , so that a essi-bility of fun tionalities is dependent of the urrent phase.Further the messages from or to the adversary are subje t to the a ess fun tion, in order that we an hidethe fun tionality even from the adversary.237.2.2 CorruptionA resour e of the adversary, whi h might be subje t to temporal hanges, is the possibility to orrupt parties.Here manifold variants are on eivable. Examples in lude:� There ould be a set of sets of orruptible parties for ea h phase, and the orruptions in ea h phase beindependent of those in previous phases.� Ea h phase ould have a set of sets whi h is a superset of that in the previous phase, and a party ouldthen be orrupted if after orruption the set of orrupted parties lies in that set of sets.� Or a party ould only be orruptible in some later phase, if some other �twin party� had been orruptedin some foregoing phase.To be able to ope with that variety of possibilities, we hoose a rather general approa h: Instead of a setof sets A, we have a fun tion A : (PH[f?g)IP �PH �! f0; 1g:It is then determined as follows, whether a party P an be orrupted in phase ': Let t(P 0) := '0 if the partyP 0 has been orrupted in phase '0, or t(P 0) := ? if P 0 is still un orrupted. Then P an be orrupted, if andonly if A(t; ') = 1 holds.247.2.3 Computational powerComputational power, too, may be subje t to temporary assumptions. Most important is the ase, that werestri t ma hines (espe ially adversary and environment) to polynomial time within some phases, but let themrun unrestri ted (or at least not polynomially restri ted) in others.A �rst approa h would be to introdu e some omputationally unbounded fun tionality, whi h an be usedto outsour e omputation. This fun tionality might then be subje t to the temporary a ess restri tionsdes ribed in se tion 7.2.1. Two problems arise with this approa h:� To give the environment superior omputational power, we would have to give it a ess to the fun tion-alities, whi h would ne essitate a major hange of our model.� We have restri ted the ideal adversary to be of relative polynomial time in the running time of the realadversary. It is hard to formalise this, if the omputation may be outsour ed.23When the adversary fakes ommuni ation of a orrupted party, the a ess to fun tionalities is determined as for the simulatedparty, of ourse, i.e. the argument to fN is the ID of that party, not A.24And, of ourse, the token is not requested to be transferred to P .46

7 EXTENSIONS 7.2 Temporary assumptionsTherefore we favour another approa h: We extend the di�erent de�nitions of running time introdu ed inse tion 3.3:The de�nition of running time TXk;n we hange to a phase dependent running time TXk;n;', whi h denotesthe average running time on se urity parameter k in invo ation n and phase '. This is done by repla ingEk;n;t by Ek;n;t;', whi h ontains Ek;n;t and all trans ripts, in whi h the n-th invo ation does not lie in phase'. Then P (TXk;n;' = t) is de�ned by using Ek;n;t;' instead of Ek;n;t.The de�nitions (reliable) polynomial time we repla e by (reliable) polynomial time in phase '. This is doneby simply repla ing TXk;n by TXk;n;'.We do not dis uss the extensions of the de�nitions of termination, sin e it does not seem ne essary torestri t termination to ertain phases. Those extensions would, however, run in the same lines as those of thepolynomial running time.The hard and sto hasti relative polynomial running time is extended to a hard resp. sto hasti phasedependent relative polynomial running time. Here we do now require, that the running time of the M2 ispolynomial in M1 for ea h phase separately. This is done by repla ing TX1=2k;n by TX1=2k;n;', and by quantifyingnot only over all n, k, and t, but also over all phases ' 2 PH.Having those new de�nitions, we hange the de�nition of se urity to require phase dependent relative poly-nomial running time between the adversaries, and we do not restri t the sets of adversaries and environmentssimply to polynomial or terminating ma hines, but to ma hines, whi h are e.g. terminating, but only in somephases polynomial.7.2.4 Known algorithmsOften we assume, that for some problem there is no known (e� ient) algorithm. For example we might say,that no one knows how to e� iently fa tor large numbers. While this is a realisti assumption, it may well bethat in the future some algorithm is dis overed.Sin e we annot easily model knowledge, an obvious way to model ignoran e of an algorithm would be toassume non-existen e of that algorithm. So we say: �If there is no algorithm for fa toring, then the proto olis se ure.� This may be su� ient for some ases, but there are two major problems:� If there is an unknown algorithm for fa toring, the proof of se urity is wrong, and it may theoreti ally be,that there is an atta k against the proto ol, whi h does not need knowledge of the fa toring algorithm.In praxis it is reasonable to suppose, that if there is an atta k, the algorithm for fa toring an be foundin the proof of se urity or in the des ription of the atta k. For formally orre t reasoning, however, thisargument is not vindi able.� When we want to use temporary assumptions, we would have to say something like �if there is noalgorithm for fa toring now and if there will be an algorithms for fa toring after the proto ols exe ution,then the proto ol is se ure�. Sin e the premise of this impli ation is formally wrong, we would triviallybe able to prove se urity and, indeed, anything else, too.The se ond problem ould be �xed by assuming the non-existen e of the algorithm, and then adding aprimitive for fa toring, whi h is only available in ertain phases, but this solution would be somewhat dirty,and it would not help against the �rst problem.Therefore we will pursue an approa h, whi h tries to get hold of the idea of knowledge and ignoran e ofalgorithms. The underlying de�nition runs approximately in the following terms:De�nition 7.1: Non-usage of an algorithm (informal version)We say, an algorithm (i.e. an IQTM) A does not use an algorithm for a problem P with respe t to , where is an e� iently omputable fun tion mapping algorithms to algorithms, if and only if (A) is not an algorithmfor P . �This de�nition is used as follows: When we prove, that a proto ol � is se ure when restri ting the lass ofadversaries and environments to ma hines, whi h do not use an algorithm for P with respe t to , where must be expli itly given, then we an reason as follows:We assume, that there is no known algorithm for P . However is known and�if � is su essfully at-ta ked�an adversary or an environment A exists, whi h does use an algorithm for P , so (A) is an algorithmfor P , but (A) is also known,25 so we have a ontradi tion. Therefore � annot be su essfully atta ked.25Sin e A and are known. We have, of ourse, to assume that the person designing the adversary knows , so this reasoningis only valid for publi ly published . 47

7.2 Temporary assumptions 7 EXTENSIONSWe now ome to the formal version of the above de�nition:De�nition 7.2: ProblemA problem P is a set of ITM, and we say an ITM M solves P, if M2 P . �Here we simply de�ne a problem as the set of all ITM whi h solve it. So a reasonable de�nition of the problemof fa toring would be the set of all ITM, whi h on input of a number emit its fa torisation with bounded errorprobability in a time polynomial in the length of the number. Other de�nitions of a problem, whi h use ades ription of the problem rather than enumerating its solutions, might be used, too, sin e problems de�nedby spe i� ation an be onsidered as problems in our sense in a natural way. (It is not ne essary to expli itlyname the elements of a problem.)De�nition 7.3: Non-usage of an algorithmWe say, a partial ITM A does not use an algorithm for a problem P with respe t to , where : �� ! �� isan e� iently omputable fun tion, if and only if s�1((s(A))) is not de�ned, or is not an ITM, or does notsolve P . Here s(M) denotes the des ription of M2 ITM. �The des ription s : ITM ! �� is an inje tive fun tion onverting a partial ITM M into a des ription of M,whi h an be e� iently used. We will not give an expli it de�nition here, this an however be done in astraightforward way, it should only be remembered, that elements of ~R an be spe i�ed by giving an algorithm al ulating its digits.Note that we have spe i�ed to be an e� iently omputable fun tion, not only a fun tion e� iently omputable on quantum omputers. In the ase, that we allow ITM to solve our problem, and if we have asu� iently natural de�nition of the problem, this does not make any di�eren e, sin e ould simply simulatea quantum ~ by just onstru ting an universal quantum Turing ma hine whi h evaluates ~ and then runs itsoutput.On the other hand, if we have only allowed lassi al ma hines to be solutions to our problem, then weprobably wanted to model a world without quantum adversaries, so restri ting to be lassi al, too, makessense.Until now, we have only de�ned what it means when we say, �a ma hine does not use an algorithm A�. Inorder to formulate temporary assumptions, however, we need to say, �a ma hine does not use an algorithm Ain phases ��. In order to do this, we have to extra t that part of an ITM, whi h gets used in some phases �.De�nition 7.4: Phase tra e in an ITMLet M = (Q; q0; qf ; n; Æ) be an ITM, and � 2 PH be a set of phases. Then we onstru t the tra e M� of thephases � in M as follows:Let Oi, Pri , Pfi , P (i)ki be the various parts of an quantum intera tion �, and Pq be the proje tion of HQ;Monto all on�gurations, where the urrent state is q.26Then let QT � Q be the set of all states q 2 Q satisfying, that there is a quantum intera tion �, and ann 2 N0, su h that Pq nYi=1(OiPriPfiP (i)ki )(j0;Mi j#i j#i j0i j0i) 6= 0;and su h that in f1; : : : ; fn there is an fi having the formÆ(phase; �), and the last su h fi equalsÆ(phase; ')for some ' 2 �.Then let M� be the partial ITM resulting from M by restri ting it to the states in QT . �In the forgoing de�nition, we onsider all quantum intera tions �, whi h let M after the n-th time step be inphase ' for some ' 2 �. Then we measure the state of M after the n-th time step, and let QT ontain allstates, whi h an o ur in this measurement with non-vanishing probability. Then we an restri t M to onlythose states and thus get the tra e.To larify this de�nition, we ompare the ITM with a normal program. Then we an run the program andmark any ode, whi h gets exe uted while in phase ' 2 �. When we do this for any possible exe utions, weget all ode whi h has in�uen e on the behaviour in phases �.We an now �nish our de�nition of non-usage of an algorithm in ertain phases:De�nition 7.5: Phase dependent non-usage of an algorithmWe say, an ITM A does not use an algorithms for a problem P with respe t to up to phase ' 2 PH, if andonly if A� with � := f ~' 2 PH : ~' � 'g does not use an algorithms for P with respe t to . �26The exa t form of Pq depends, of ourse, of whether M is an IQTM, an ICTM, or an IQCTM.48

7 EXTENSIONS 7.3 ConstraintsIn the pre eding de�nition, it might seem useful also to allow some � whi h is not of the stru ture f ~' 2 PH :~' � 'g. This de�nition, however, would not onform to our intuitive requirement any more, as the followingexample shall demonstrate: Assume some ma hine whi h does not use an algorithm for P in phases � := f'2g.Then an algorithm for P might be written onto some tape in phase '1 < '2, and in phase '2 simply exe uted.Then in phase '2, the tra e ontains nothing but some universal Turing ma hine's program, but neverthelessit may solve the problem P .7.3 ConstraintsSometimes, we do not want to get se urity in all ases, but are ontented with se urity under spe i� onditions.Some examples of su h onditional se urity spe i� ations would be, informally stated:� �The proto ol is se ure, as long as the inputs to the parties are all di�erent.�� �The proto ol behaves as a oin toss, or all parties output ?.�� �The proto ol is se ure, as long as the adversary does not send more than a million messages.�The �rst two of those problems we will handle using onstraints. Roughly sket hed, onstraints are mea-surements, whi h test ontinuously, whether a ertain ondition is satis�ed while exe uting the AQN, and, ifthat test fails, the given run is aborted and not onsidered when generating the statisti s of the output ofthe environment. This e�e ts, that the output distribution goes only over those runs, where the onstraint issatis�ed.The third problem annot, unfortunately, be handled using this me hanism. If we use the onstraint �theadversary has not send more than a million messages�, and try e.g. to implement oin tossing, then the idealadversary ould try to use the following tri k to adjust the ideal oin toss to yield any desired value: Assumethe adversary gets to know the result of the oin toss before the environment does. Then if the result is not asdesired, the adversary sends a million dummy messages, thus aborting the run and preventing it from being ounted in the environment's output statisti s. So the statisti s run only over the ases, where the oin tossoutputs the desired result. This makes many proto ols se ure, whi h we would onsider as inse ure. So we annot use onstraints for formulating onditions like the above one.We do not know any formal spe i� ation, whi h onstraints are �harmless�, so onstraints should only bedesigned with great are.Formally, a onstraint is de�ned as follows:De�nition 7.6: ConstraintLet N be a quantum network. Then a onstraint C on N is a sequen e (C(k))k2N of unitary transformationson HN CZ C2, whi h operates read-only on HN . �We have hosen to de�ne the onstraint not dire tly as a measurement, but as a transformation whi h operateson the network's on�guration spa e HN , on an auxiliary spa e CZ, and on an output spa e C2. This outputspa e will be measured and should ontain j1i for a satis�ed onstraint and j0i for an unsatis�ed one. Due tothe auxiliary spa e CZ, the onstraint an hold arbitrarily omplex information about previous time steps.The parameter k whi h sele ts a spe i� unitary transformation is the se urity parameter.When some onstraints C := fC1; : : : ; Cng are given, the output of an AQN is rede�ned as follows: Thestate of the quantum network is a ve tor in HN CZ1 C21CZ2 C22 � � �CZn C2n instead of simply HN ,as it was in se tion 5.5. All operations given in se tion 5.5 still operate only on HN . After the time evolution,but before measuring jGi, apply C(k)i on HN CZi C2i for ea h i. Then measure all C2i in the standardbasis. If one of them ontains j0i, terminate with output �. Otherwise ontinue as in se tion 5.5.By this modi�ed algorithm we get an output distribution Outk;n(N ) over f0; 1;?;�g. We an now de�nethe onstrained output OutCk;n(N ) as the onditional sto hasti variable over f0; 1;?g de�ned byP (Outk;n(N ) = t) = P (Outk;n(N ) = tjOutk;n(N ) 6= �) (t 2 f0; 1;?g)If P (Outk;n(N ) = �) = 1, we write OutCk;n(N ) = ?.Then, in the de�nitions of se urity, we he k for indistinguishability of the onstrained output distributions,where we assume two output distributions to be indistinguishable, if one of them is ?.Using the foregoing rede�nition, the onstrained output distributions are statisti s only over the runs wherethe onstraints are satis�ed. If a onstraint is never satis�ed, we assume indistinguishability, sin e if e.g. someenvironment would never satisfy some onstraint, then this environment's output should not be ounted at all.Sin e all Ci are read-only on HQ;M, and operate on separated spa es otherwise, they ommute, so it isjusti�ed to spe ify a set C of onstraints and not a sequen e.49

7.4 Passive orruption 7 EXTENSIONS7.4 Passive orruptionIn this se tion, we introdu e the on ept of passive orruption. This models the ase, where after orruptionthe adversary knows the state of the orrupted party, but does not get ontrol over it or its messages. Apassive orruption may even take pla e several times on the same party.When introdu ing passive orruption, we have to make the following hanges to our de�nitions:� The de�nition of the IAQS is to be extended by a passive orruption operator, whi h is analogous to the orruption operator, but is applied in ase of passive orruptions.� The s heduling fun tion is to be modi�ed thus, that the adversary may request an a tive or a passive orruption. In ase of the passive orruption, the orrupted party is not added to the set of orruptedparties, so that it will still get the token and be able to send and re eive messages.� Instead of A, the set of sets of allowed orruptions, a more sophisti ated me hanism is needed to spe ify,whether a requested orruption may still take pla e. There ould e.g. be restri tions on how often aparty may be passively orrupted, et .Probably only passive orruption operators whi h are read-only on the on�guration spa e make sense, sin eotherwise the orruption would not satisfy an intuitive notion of �passiveness�. Further passive orruptionshould only be allowed on lassi al ma hines, sin e otherwise interferen e ould be destroyed and thus thema hine be in�uen ed. However, if the passive orruption operator is restri ted to those parts of a ma hinewhi h an be onsidered as lassi al, also a partly quantum ma hine ould be passively orrupted. E.g. thepassive orruption operator of an IAQS with lassi al interfa es ould just export the measured data from theinterfa es.7.5 Cheat Dete tionIn some ases, we do not ne essarily need a proto ol se urely implementing e.g. some primitive, we only need aproto ol whi h does run se urely or informs all honest parties that it ran inse urely. Lets for example onsideren rypted ommuni ation. If we know after exe ution of the proto ol whether it ran se urely or not, we anuse it to implement a se ure en rypted ommuni ation as follows: First transfer a key.27 Then en rypt themessage to be transfered using that key, if there was no heating during the transmission of the key. Now allthe adversary an a hieve, is hindering the ommuni ation, eavesdropping however is impossible.28Informally we de�ne � to be se ure with heat-dete tion, if � is se ure under the onstraint, that there isat least one un orrupted party not outputting ? , where ? stands for some previously de�ned message.To de�ne this more formally, we �rst need the on ept of a se urity notion.De�nition 7.7: Se urity notionA se urity notion � is one of the se urity on epts de�ned in hapters 6 and 7, together with all its parametersex ept for the real proto ol (i.e. e.g. the set of adversaries, the onstraints, the ideal proto ol, et .)We say a proto ol � is �-se ure under onstraints C, if when adding � to � as the real proto ol (whi h wasthe last missing parameter), and adding C to the set of onstraints given in �, the se urity de�nition given bythat onstru t is ful�lled.If no onstraints are given, we assume the empty set. �To larify this formalism, we give an example: Let � be the polynomial se urity with A := X , indistinguisha-bility relation �0, and onstraints Y , and with the ideal proto ol %. Then � is �-se ure under onstraints Cmeans that � is as se ure as % with A := X , indistinguishability relation �0, and onstraints Y [ C.Having this, we an write down the de�nition of heat-dete tion:De�nition 7.8: Se urity with heat-dete tionLet � be a se urity notion and � a proto ol. Then � is �-se ure with heat-dete tion ? , where ? 2 ��, if �is �-se ure under the onstraint, that for some un orrupted party P it holds, that is has never sent a message? to the environment. �27Possible as long as the message.28In fa t, we have onstru ted en rypted ommuni ation with partial abort (see se tion 7.6) from en rypted ommuni ationwith heat-dete tion. 50

7 EXTENSIONS 7.6 Se urity with Partial Abort7.6 Se urity with Partial AbortAnother variant of standard se urity models is se urity with partial abort. Here we want to model proto olparti ipants, whi h implement a given fun tionality or, if this is not possible, retreat from the proto ol. Foran example, assume the following situation: We have some proto ol for some multi-party omputation, whereindividual parties may ome to suspe t the omputation of being ompromised. Then they will notify the userof this (by outputting ?a) and stop inputting our outputting anything.To a hieve this on ept of se urity, we add a new fun tionality F to the ideal ommuni ation framework,and we modify the ideal proto ol thus, that on getting any message from F , a party P will send ?a to theenvironment, and afterwards P will ignore all messages from the environment (and forward them to F), andwherever P 's program tells it to send a message to the environment, it will send it to F instead.The fun tionality F will, when re eiving a message from the adversary ontaining a party's ID P , send toP an empty message. When re eiving a message from a party, it is ignored, i.e. simply stored on some tapeand never read again.For a se urity notion �, we will then say a proto ol � is �-se ure with partial abort, if � is �0-se ure, where�0 is obtained from � by following the above instru tions.We will omit a more formal de�nition of this notion.7.7 Pliable Se urityA generalisation of se urity with heat-dete tion is the pliable se urity. Imagine some proto ol, whi h duringits run dete ts, what level of se urity may be a hieved and then uses and outputs this level of se urity.An example would be a proto ol for en rypted and authenti ated ommuni ation. This proto ol may thene.g. output, that the hannel is en rypted and authenti ated, or that it is only authenti ated, but not en ryptedany more.29To spe ify su h a pliable se urity, we need to spe ify a set of se urity notions S, together with a halfordering �, a phase �, an inje tive mapping f : S ! ��, a se urity model �0, and a set of parties P . Thenintuitively (S;�; �; f; �0;P)-pliable se urity of a proto ol � means, that the proto ol � will run with somese urity � 2 S, and at the latest in phase � un orrupted parties in P may output, whi h se urity has been hosen. Furthermore the proto ol is in any ase �0-se ure. Instead of outputting a se urity whi h is in fa tful�lled, it may also output some se urity ~� � �, be ause � � � shall mean that � is a se urity �at least asgood as� � . Sin e the se urity notions have no anoni al string representation, f(�) denotes whi h message isto be sent to the environment for se urity notion �.More formally pliable se urity is de�ned as follows:De�nition 7.9: Pliable se urityLet (S;�) be a half-ordered set of se urity notions having a supremum for any subset, � 2 PH a phase,f : S! �� an inje tive mapping, P � IP a �nite set, and �0 a se urity notion or �0 = ?.Then a proto ol � has (S;�; �; f; �0;P)-pliable se urity, if the following onditions hold:� The proto ol � is �0-se ure or �0 = ?� For ea h � 2 S the proto ol � is �-se ure under the onstraint' � � _ � = supP2 ~P�P 6=?�P :Here ' denotes the urrent phase, ~P the set of all un orrupted parties in P , and �P is su h, that f(�P )is the �rst message send from P to E during a phase smaller-or-equal � formed f(�0) with �0 2 S; itis �P = ?, if no su h �P exists. If the supremum goes over an empty set, we assume its value to be ?(note � 6= ? for � 2 S, so in this ase the ondition is trivially ful�lled).If � is not given, we assume � � �, if and only if being �-se ure implies being � -se ure. If �0 is not given,we assume �0 = ?.If P is not given, but there is some natural notion of a �nite set of parties parti ipating in the proto ol,then let P be that set. �This de�nition is in fa t stri ter than the intuitive formulation, sin e we say here, that the se urity rea hedis exa tly the supremum of the se urity notions signalled to the environment, instead of, as required in the29This example ould, of ourse, be realised mu h simpler by reating an ideal fun tionality implementing both behaviours, butin some ases the di�eren es between the se urity models might be more subtle, e.g. polynomial and non-polynomial se urity.51

7.8 Adjustable Se urity 7 EXTENSIONSintuitive formulation, some se urity notion greater-or-equal that supremum. This may make realisation ofproto ols with pliable se urity mu h harder, unless � is the equivalen e or the natural half-ordering of S givenby the impli ations between se urity notions. We have, however, not found a way to formalise the desiredde�nition.7.8 Adjustable Se uritySometimes, we do not know exa tly, what se urity is needed when designing a proto ol. The se urity oulddepend on some inputs of the proto ol, and the proto ol would have to behave a ordingly. Usually, the lessstri t se urity notions will be more e� ient, so using the stri ter ones will only be done in ase of need.An example for su h proto ols omes from human intera tion. In some ases, an ele tion may be open(i.e. the individual votes are known to the adversary), but as soon as one of the voters requests a se ret ele tion,a se ret ele tion is arried out.30So we again have a set of se urity notions S, a half ordering �, a phase �, an inje tive mapping f , and ase urity notion �0. The meanings of S, �, f , and �0 are as with pliable se urity, � however is the phase upto whi h the parties need to have the input, whi h se urity notion is required. The set P � IP (this time notne essarily �nite) denotes the parties, whi h may have in�uen e on the hoi e of the se urity notion.Then (S;�; �; f; �0)-adjustable se urity means intuitively, that up to phase � (in lusive) only se urity �0is guaranteed, and after � a se urity � greater or equal to all se urity notions the parties P have got as inputup to phase �. Formally:De�nition 7.10: Adjustable se urityLet (S;�) be a half-ordered set of se urity notions, � 2 PH a phase, f : S ! �� an inje tive mapping,P � IP a �nite set, �0 a se urity notion or �0 = ?, and P � IP .Then a proto ol � has (S;�; �; f; �0;P)-adjustable se urity, if the following onditions hold:� The proto ol � is �0-se ure or �0 = ?.� For ea h � 2 S the proto ol � is �-se ure under the onstraint' � � _ � = supP2Pf(�P )6=?�P :Here ' denotes the urrent phase, ~P the set of all un orrupted parties in P , and �P is su h, that f(�P )is the �rst message send from E to P during a phase smaller-or-equal � formed f(�0) with �0 2 S; itis �P = ?, if no su h �P exists. If the supremum goes over an empty set, we assume its value to be ?(note � 6= ? for � 2 S, so in this ase the ondition is trivially ful�lled).If � is not given, we assume � � �, if and only if being �-se ure implies being � -se ure, and if �0 is notgiven, we assume �0 = ?.If P is not given, but there is some natural notion of a set of parties parti ipating in the proto ol, then letP be that set. �7.9 Corruption noti� ationIn our model we have assumed so far, that if the adversary orrupts a party, a noti� ation of this orruptionis gotten by the environment upon its next a tivation. There are, however, several variants.� Immediate orruption noti� ation. This is the orruption model used so far, where the environment getsa orruption noti� ation upon its next invo ation.� Delayed orruption noti� ation. Here the environment is not immediately noti�ed. Instead, upon en-tran e of the post-phase, the environment gets (when a tivated the next time) a list of all parties orruptedso far.� Covert orruption. In this ase, the environment is not noti�ed at all about orruptions.30See footnote 29 on page 51. 52

7 EXTENSIONS 7.9 Corruption noti� ationIn the �rst two models we have, that A-se urity implies A0-se urity with A0 � A. With overt orruptionshowever, this is not given. Consider the following example: Some two-party-proto ol � is not 1-se ure31. Itthen is, with overt orruption, 2-se ure, be ause the ideal adversary an simulate any behaviour by orruptingall two parties.32 So � is then 2- but not 1-se ure.Therefore the se urity de�nition should be hanged thus, that A-se urity is given, if and only if the oldse urity de�nition holds for any subset of A.7.9.1 Adaptive vs. stati se urityIn this se tion, we will sket h an example, that adaptive and stati se urity are di�erent for all orruptionnoti� ation models given in the previous se tion, even for the three party ase.We assume three parties named A1; A2; B, and an authenti ated broad ast hannel. Whenever we say� hoi e�, we mean an uniformly distributed random hoi e. Further let always be A := ffA1g; fA2g; ;g.Consider an ideal fun tionality F having the following program:� Choose � from f0; 1g.� Send � to the adversary.� Wait for a message a from the adversary.� If � = 0, hoose r from f0; 1g and send r to B.� If � = 1, send a to B.As real proto ol, we take parties A1; A2; B, whi h behave as follows: The parties Ai wait for some messageon the broad ast hannel, and then broad ast some ai hosen from f0; 1g.The party B does the following:� Choose 2 f1; 2g.� Broad ast .� Wait for broad asted messages a1=2 from A1=2.� Send a to the environment.We �rst laim, that � is stati ally as se ure as F . Proof sket h:Let some real A be given. Then onstru t the ideal adversary S as follows:� Simulate A and the real proto ol's parties.� Whenever A orrupts a party, orrupt the same party.� Pass ommuni ation between environment and orrupted parties to A.� If F sends � to A, simulate, that B broad asts a message , given as = 8>>>>>><>>>>>>:2; if � = 0, A1 orrupted;1; if � = 0, A2 orrupted;1; if � = 1, A1 orrupted;2; if � = 1, A2 orrupted;1; if no party is orrupted:� When both simulated parties have send their ai, send a to F , where a is what the orrupted Ai has sentif there is some, 0 otherwise.Obviously this behaves as the real proto ol, so � is stati ally se ure. �We further laim, that � is adaptively inse ure. Proof sket h:Let the real adversary run as follows:31I.e. A onsists of all one-element-subsets of IP .32Cases may be onstru ted, where this is not given, if non-simulatable fun tionalities or parties are present, but for usualproto ols this argumentation holds. 53

7.9 Corruption noti� ation 7 EXTENSIONS� Wait for from B.� Corrupt A .� Let A broad ast 1.Let the environment simply output, what it gets from B. Then the output of the environment is always 1.However, for ideal adversary the probability of B sending 0 is at least 14 , so the same holds for the environment'soutput. Therefore the proto ol is not adaptively se ure. �

54

8 RELATION OF CLASSICAL AND QUANTUM SECURITY8 Relation of lassi al and quantum se urityAn important question, whi h arises when introdu ing quantum se urity, is, whether the proofs of se urityalready made for lassi al proto ols in a lassi al world are all obsolete.In this hapter, we will address this question. We will, however, not examine lassi al se urity with lassi alma hines, but se urity, where all ommuni ation is lassi al, the ma hines will however be internally quantum(i.e. they are IAQS with lassi al interfa es). This is due to the fa t, that�assuming that a quantum omputermay not be simulated by a lassi al one with polynomial overhead�a lassi al adversary or environment isinferior to a quantum one in omputational power, thus some proto ols may get inse ure just be ause of thatadditional power.In the omputationally unbounded ase the di�eren e between IAQS with lassi al interfa es and lassi alIAQS is unimportant, sin e e.g. an ICTM an simulate an IQCTM with exponential overhead, and a lassi alIAQS an simulate an IAQS with lassi al interfa es even without overhead.The proposition we want to prove goes as follows:Proposition 8.1: Relation of lassi al and quantum se urityLet � and % be proto ols onsisting only of lassi al IAQS. Let their asso iated ACF C�, C% onsist only ofIAQS with lassi al interfa es.Then � is as se ure as %, assuming any ombination of the following parameters:� adaptive or stati se urity,� polynomial or unbounded se urity,� approximative or absolute se urity,� any orruption set A � 2IP ,� se urity with bounded risk,� any indistinguishability relation �,if � is also as se ure as % with respe t to the same parameters, when restri ting the set of adversaries and theset of environments to IQCTM. �The set of se urity models for this su h an impli ation holds, is probably greater than the set given here,but not every se urity model stays se ure in the quantum ase. E.g. if restri ting the set of adversaries toIQTM n IQCTM, we would of ourse get lassi al se urity, sin e here the set of adversaries would be empty, butquantumly the proto ol might nevertheless be inse ure. Further resear h might e.g. give some hara terisationsof sets of adversaries and environments, for whi h the proposition still holds.Now we pro eed to the proof sket h of this proposition:For larity, we will always write IAQS with lassi al interfa es with a supers ript prime (e.g. M0)Let us �rst assume, that the se urity model omparing � and % is not polynomial and not of bounded risk.Let then A be any real life adversary and E be any environment. Let N0r be the instantiation of C� withE , A, � and A.Then we an repla e E by some EA and A by some A0, without hanging the output behaviour of thenetwork, when de�ning EA and A0 as follows:Let EA be a ma hine in CE simulating the ma hines A and E , where all ommuni ation between those twoma hines is handled internally,33 the ommuni ation between E and the parties is forwarded by EA and all ommuni ation of A is rerouted via A0, together with all ne essary information on destination and possiblysender. In oming ommuni ation, orruptions and time blo k in reases are also rerouted via A0. When Awants to transfer the token to some ma hine X 2 Iadv, then the token is given to that ma hine by A0. If EA isa tivated, A is a tivated internally, ex ept when A had just requested an a tivation of the environment, thenE is a tivated. If A0 is a tivated without having instru tions whom to a tivate next, EA is a tivated.Let A0 be a polynomial IQCTM, whi h simply does the rerouting as spe i�ed in the previous paragraph.We an hoose A0 to be an IQCTM, sin e every forwarded message is measured anyway by some party. Themessage ontaining the state of a orrupted ma hine may also be measured before forwarding, sin e all partiesare lassi al, so their state may be measured.The instantiation of C� with EA and A0 we all N1r. It is nowOutk(N0r) = Outk(N1r); Outk;n(N0r) = Outk;n(N1r):33In luding the faked ommuni ation between two orrupted parties, whi h generates messages from A to A.55

8 RELATION OF CLASSICAL AND QUANTUM SECURITYSin e in the resulting QN all ma hines ex ept EA are IQCTM, all in oming and outgoing ommuni ationof A may be measured. So by repla ing EA by E 0A := CI(EA), we get the QN N2r, withOutk(N1r) = Outk(N2r); Outk;n(N1r) = Outk;n(N2r):Sin e in N2r all ma hines have lassi al interfa es, the pre ondition holds and there is an ideal adversaryS 0 independent of E , su h that for the instantiation N2i of C% with E 0A, S 0, % and A, we haveOutk(N2r) � Outk(N2i): (20)When repla ing E 0A by EA again, we get a QN N1i. Following a similar reasoning as above, it holds:Outk(N1i) = Outk(N2i); Outk;n(N1i) = Outk;n(N2i):We an now onstru t an ideal adversary S, whi h simulates S 0 and A, passing all of the ommuni ation ofA through S 0, ex ept for the ommuni ation with the environment. The details of this rerouting are analogousto those where we onstru ted EA. Be ause S 0 was independent of EA, the adversary S is independent of E .The resulting QN we all N0i. It isOutk(N0i) = Outk(N1i); Outk;n(N0i) = Outk;n(N1i):So we get overall: Outk(N0r) � Outk(N0i): (21)Sin e S has polynomial running time relative to A,34 we have proven � to be as se ure as %.We still have to onsider the polynomial se urity and the se urity with bounded risk. We will �rst examinethe polynomial se urity.The restri tion of the sets of adversaries and of environments to PITM does not hange our proof at all,sin e all onstru ted ma hines will be polynomial in the running time of A; E 2 PITM, therefore the newma hines will be in PITM themselves.Then (20), (21) hange to Outk;p(n)(N�r) � Outk;p(n)(N�i)for a su� iently large polynomial p. The rest of the argumentation stays same.We will now prove the remaining ase, se urity with bounded risk. Sin e we have proven, that se urity holdsfor any indistinguishability relation, it holds espe ially for �0, where �0 is the statisti al indistinguishabilitywith respe t to f" : " = Æ almost everywhereg for a negligible bound Æ. Here Æ is hosen su h, that �0-se urityis given in the lassi al ase (the existen e of su h a Æ is guaranteed by the de�nition of se urity with boundedrisk). Then �0-se urity is also given in the quantum ase, so in parti ular we have se urity with bounded riskin the quantum ase. �

34S simulates S0 and A. A0 was of polynomial running time, S0 was of polynomial running time relative to A0, therefore it ispolynomial, too. 56

9 COMPOSABILITY9 ComposabilityIn order to be useful, a se urity notion needs to ful�l the requirement of omposability, i.e. the proto ol beingdeemed se ure in a stand-alone ontext must also be se ure as part of a larger s heme. If we would forexample spe ify some proto ol and laim it to be se ure, adding the restri tion that it may only be exe utedon e during the lifetime of the universe and that it may not be used in a world where some other proto olis running, our notion of se urity might be onsidered risible. Therefore a good se urity model should alsoprovide omposability.In this work, we distinguish three types of omposability. The �rst kind is the simple omposability. Itmeans, that any meta-proto ol � using some proto ol % instead of some ideal fun tionality F will not su�erany loss of se urity, provided % se urely realises F .The se ond kind of omposability is the on urrent omposability. Here we laim, that if � se urely realisesF , than several opies of � se urely realise several opies of F .And the third kind is the universal omposability, whi h is a ombination of the two pre eding notions,and in fa t an easy orollary of those. It states, that any meta-proto ol � using some proto ols %i instead ofsome ideal fun tionalities Fi will not su�er any loss of se urity, provided ea h %i se urely realises ea h Fi.We have separated the notion of omposability into these three parts, be ause the pre onditions for theirappliability are di�erent.9.1 Simple ComposabilityFirst we will de�ne the formal operation of simple omposition, whi h means inserting one proto ol intoanother. The de�nition will not be fully formalised, for brevity.De�nition 9.1: Simple omposition of proto olsLet � and %(i) (i = 1; : : : ; n) be proto ols, and F1; : : : ; Fn 2 IF . For shorter formulation let %(0) := �.Let F (i; k) :=Æ(u(i); k) with i = 0; : : : ; n and k 2 IF , where u is as de�ned in de�nition 2.17.Then we de�ne ~�j (j 2 IP ) to be an IAQS onstru ted as follows:The IAQS ~�j simulates all IAQS %(i)j with i = 0; : : : ; n. The se urity parameter is passed to all those uponre eption. Communi ation with the environment is routed to �j . Messages from and to fun tionalities F (i; k)are routed to %(i)j for i = 0; : : : ; n as oming from resp. going to fun tionalities Fk. Messages from and to otherfun tionalities are stored and not used any more.Messages from ~�j to Fi are given to %(i)j (i 6= 0) as oming from the environment. Messages from %(i)j(i 6= 0) to the environment are given to �j as oming from Fi.On ea h invo ations of ~�j , a di�erent %(i)j (i = 0; : : : ; n) is a tivated. The invo ations take pla e in theorder of growing indi es i, after %(n)j , %(0)j 's turn omes next.The orruption operator of �j onsidersHC as HC;�HC;0� � �HC;n, and for i = 0; : : : ; n the orruptionoperators for %(i)j is exe uted on the on�guration spa e of %(i)j and HC;i. The whole state of the simulator isswapped onto HC;�.Then the simple omposition �fF1=%(1) ;:::;Fn=%(n)g is de�ned to be the proto ol ~�. The asso iated ACF C~�is ~C� �C%1 � � � � � C%n (see below), where ~C� is as C�, ex ept that ( ~C�)i := ? for i 2 fF1; : : : ; Fng. Here ? is adummy ma hine whi h never sends any message. �In this de�nition, we take some proto ol �, whi h a esses some fun tionalities addressed F1; : : : ; Fn. We then onstru t some new proto ol ~� = �fF1=%(1);:::;Fn=%(n)g by repla ing every all to one of these fun tionalities by alls to some orresponding simulated subproto ol %i. To the environment, ~� behaves in an un hanged way,but the fun tionalities get a new addressing, sin e now our ACF does not only ontain the fun tionalities for�, but also those for ea h %i. The following de�nition takes are of reating this new ACF and reordering thefun tionalities to mat h to pre eding de�nition.De�nition 9.2: Simple omposition of ACFLet C(0); : : : ; C(n) be ACF. Then let the omposition C(0) � � � � � C(n) be the ACF ~C whi h is de�ned by~CF (i;k) := C(i)k , ~Cm := ? (m =2 imF ), where F is de�ned as in the pre eding de�nition, and ? is a dummyma hine whi h never sends any message.The a ess stru ture f of ~C is de�ned as:f(F (i; k); p) := fC(i)(k; p) (i = 1; : : : ; n; k 2 IF ; p 2 IP )f(p; F (i; k)) := fC(i)(p; k) (i = 1; : : : ; n; k 2 IF ; p 2 IP )57

9.1 Simple Composability 9 COMPOSABILITYand f := 0 everywhere else. �These de�nitions allow us to modularly onstru t proto ols, we may spe ify some proto ol, whi h uses someabstra t primitive F and later on spe ify some real proto ol to use instead. To help showing, that the proto olthus designed is se ure, we provide the following omposition theorem:Proposition 9.3: Simple omposition theoremLet �(i), %(i), � be proto ols. Let further CE be one of IAQS, IQTM, PIAQS, ICTM, IQCTM, or anynon-empty interse tion of these, and CA one of IAQS, IQTM, PIAQS, ICTM, IQCTM, the set of (sto hasti- ally/polynomially) non-blo king adversaries, or any non-empty interse tion of these. The ACF C� asso iatedto � shall be su h, that all its fun tionalities an be simulated by a ma hine in CE .35 Let B be any set ofbounds. Let Fi 2 IF (i = 1; : : : ; n, n 2 N0) be pairwise di�erent.Then it is 8i 2 f1; : : : ; ng : �(i) � %(i) =) �fF1=�(1) ;:::;Fn=�(n)g � �fF1=%(1);:::;Fn=%(n)gwhere � means approximative or absolute se urity, se urity with respe t to B, polynomial se urity, se uritywith bounded risk or any ombination of these. �Note that the two sides of the impli ation have di�erent ACF, i.e. the respe tive asso iated ACF for thedi�erent proto ols.Proof sket h: We will restri t the proposition to the ase n = 1. The ase n > 1 is proven indu tively. Wethen write F := F1, � := �(1), % := %(1). Let further F be the fun tionality with ID F in C�. When writingOutk(E ;A; �) we mean Outk(C�(x; E ;A;A; �)), where x is adaptive or stati , depending on the hosen se uritymodel �.Assume that � � % and �F=� � �F=%. Then there is an adversary A, s.t.8S 2 CA 9E 2 CE : (Outk(E ;A; �F=�)) 6� (Outk(E ;S; �F=%)): (22)We then onstru t an environment ~E , whi h simulates E , all fun tionalities in C� and all parties in �. Com-muni ation between these ma hines is routed internally, the outside ommuni ation o urring is:� Communi ation between the parties in � and F . These a esses to F are rewritten to a esses to theproto ol outside ~E , i.e. when �i sends a message to F , it is sent to the party i outside ~E , and vi e versa.� Communi ation between E and A. This ommuni ation (and that of the following two points) is routedto ~A (the adversary, see below), together with additional messages informing ~A of the ommuni ationpartner.� Communi ation between the fun tionalities in C� and A. See the previous point.� Corruptions of parties in � by A. The orruption of parties is�from the point of view of ommuni a-tion�simply a message transmission, so see the previous two points.We will not over details of this message transmission and of the s heduling in this proof sket h.The adversary ~A shall be onstru ted thus, that it simulates A and reroutes ommuni ation with E andfun tionalities in C� to the orresponding parts of ~E . When orrupting a party, that party shall be orruptedand additionally the simulated party in ~E shall be orrupted. From the states of these two orrupted ma hineswe onstru t the state, the orresponding omposed ma hine �F=%i in �F=% would have, assuming that thestates of the two simulated ma hines in �F=%i are the two states we just got as the result of our orruption.That onstru ted state is given to A as the results of the orruption. Communi ation with fun tionalities inC� is simply passed through.Then it is 8E 2 CE : (Outk(E ;A; �F=�)) = (Outk( ~E ; ~A; �)): (23)Sin e � � %, there is an ~S 2 CA, s.t.8E 2 CE : (Outk( ~E ; ~A; �)) � (Outk( ~E ; ~S; %)): (24)35This is e.g. satis�ed, if C� ontains only a �nite number of non-dummy ma hines and they are all in CE .58

9 COMPOSABILITY 9.2 Con urrent ComposabilitySin e otherwise ~S would be easily distinguishable from ~A, it does obey with overwhelming probability (orwith probability 1, in ase of absolute se urity) the ommuni ation proto ol between ~E and ~A. Thereforewe an repla e it by an adversary, whi h fully onforms to that proto ol. So we will w.l.o.g. assume su h onformity. Then we an onstru t an adversary S, whi h simulates ~S and reroutes the ommuni ation from~S as follows:� Communi ation with the fun tionalities in C% is simply passed through.� Communi ation with any simulated ma hines in ~E (i.e. E , parties in �, fun tionalities in C�) is routed tothe orresponding real ma hines.� Corruptions requested by ~S are exe uted and then�assuming that a ma hine in �F=% is orrupted�splitinto two parts, the part a orruption of the orresponding ma hine in % would have yielded, and the part~E would have simulated with respe t to �.Then we have 8E 2 CE : (Outk( ~E ; ~S ; %)) = (Outk(E ;S; �F=%));whi h gives, together with (23) and (24)8E 2 CE : (Outk(E ;A; �F=�)) � (Outk(E ;S; �F=%));in ontradi tion to (22).The ase of se urity under polynomial running time, and the ase of polynomial se urity are analogous,simply repla e Outk by Outk;n and quantify over all n.In the ase of se urity with bounded risk, the bound valid for � � % is valid for �F=� � �F=%, too, due tothe previously shown, so the proposition also holds for se urity with bounded risk. �The most frequent appli ation of this theorem is the following: We have some proto ol �, whi h, whenusing some fun tionality F with ID F , is in some way se ure, we than want to get se urity also for �F=%,provided that % is as se ure as F . For this purpose we state the following orollary, of whi h we omit theproof:36Corollary 9.4Let the pre onditions and variables be as in proposition 9.3 and F (i) := (C�)Fi .Then it is � � � and 8i 2 f1; : : : ; ng : �(i) � F (i) =) �fF1=�(1) ;:::;Fn=�(n)g � �;with the same meaning of the symbol � as in proposition 9.3, with the additional onstraint, that B is losedunder addition.37 �9.2 Con urrent ComposabilityWe will now de�ne the formal operation of parallelisation, i.e. running a proto ol several times in parallel.Again we will not fully formalise the de�nition.De�nition 9.5: Parallelisation of IAQSLet M be an IAQS.We then de�ne the parallelisation Mm of M, with m : N0 ! N0 [ f1g, to be an IAQS onstru ted asfollows:Let k be the se urity parameter. Then the ma hine Mm simulates m(k) opies of M (possibly an in�nitenumber), indexed by i 2 f1; : : : ;m(k)g (i.e. N in the ase m(k) =1), here denoted as Mi, i 2 N. We all ithe session ID (SID). of the indexed ma hine.On ea h se ond invo ation of Mm one simulated ma hine Mi is invoked, the value of i �rst in reasesfrom 1 to 1, then from 1 to 2, then from 1 to 3, et ., until it rea hes the y le 1 to m(k), where it keeps y ling.36The proof an be onstru ted by taking into a ount, that �fF1=�(1);:::;Fn=�(n)g is essentially the same as �, if �(i) is adummy proto ol simply rerouting messages to F(i), and that � is transitive, if B is losed under addition.37I.e. for a; b 2 B there is a 2 B, s.t. ab � . 59

9.2 Con urrent Composability 9 COMPOSABILITYCommuni ation is routed to the outside, with the following en apsulation: When a message is to betransmitted to the outside of Mm from Mi, a message ontaining only the index i is send to the re ipient,and only after the next invo ation the a tual message is sent.38Similarly, when a message omes in, it is taken to be an index i, and the next message from the samesender is taken to ontain a message for Mi (and is not taken to be an index, of ourse).A orruption gives the full state of the simulator, and evaluates the orruption operators of allMi invokedso far (analogous to de�nition 9.1).When ma hines with invalid indi es are a essed (i.e. indi es greater m(k), or synta ti ally in orre t ones),dummy ma hines are simulated. �This de�nition takes a single ma hineM, and onstru ts a ma hineMm ontaining a whole bun h of identi al opies ofM. Ea h in oming and outgoing ommuni ation an then be addressed to or oming from a parti ular opy of M. We write a fun tion into the supers ript of the newly onstru ted ma hine Mm, whi h indi ateswhether and to what value the number of opies is then restri ted (in dependen e of the se urity parameter).If m =1, we have an unbounded number of opies available.This onstru t is useful as well for parties (when used in the ontext of the following de�nition), as wellas when used with fun tionalities, e.g. a fun tionality for a single ommon oin toss be omes a fun tionalitywhi h provides a (bounded or unbounded) number of oin tosses.When we apply this onstru t to parties, it is of ourse only sensible, if all parties undergo the same hange,and if all fun tionalities they use are also parallelised. This is a hieved by the following two de�nitions:De�nition 9.6: Parallelisation of proto olsLet � be a proto ol. The parallelisation �m of �, m : N0 ! N0 [ f1g is de�ned by (�m)i := (�i)m, i 2 IP .The asso iated ACF C�m is the parallelisation (C�)m (see below). �De�nition 9.7: Parallelisation of ACFLet C be an ACF. Then the parallelisation Cm of C, m : N0 ! N0 [ f1g is de�ned by (Cm)i := (Ci)m, i 2 IF .The a ess stru ture of Cm is the same as that of C. �Proposition 9.8: Con urrent omposition theoremLet �, % be proto ols. Let further CE be one of IAQS, IQTM, PIAQS, ICTM, IQCTM, or any non-empty inter-se tion of these, and CA one of IAQS, IQTM, PIAQS, ICTM, IQCTM, the set of (sto hasti ally/polynomially)non-blo king adversaries, or any non-empty interse tion of these. Let m : N0 ! N0 be any fun tion and Ba set of bounds, whi h is losed under multipli ation with m.39 All of the following should be doable by ama hine in CE :� Simulate the parties in the proto ols �, %.� Simulate the fun tionalities in the ACF C� and C% asso iated to � resp. %.� Simulate any ma hine from CA.� Evaluate m.Then it is � � % =) �m � %m;where � means se urity with respe t to B, polynomial se urity with respe t to B, se urity with bounded riskand with respe t to B or any ombination of these.If we restri t � to polynomial se urity with respe t to B, and require B to be losed under multipli ationwith polynomials, then we an omit the restri tion, that B must be losed under multipli ation with m. �Note that the two sides of the impli ation have di�erent ACF, namely the respe tive asso iated ACF for thedi�erent proto ols.Proof sket h: When writing Outk(E ;A; �) we mean Outk(C�(x; E ;A;A; �)), where x is adaptive or stati ,depending on the hosen se urity model �.Assume that � � %, and let A be an arbitrary well-formed adversary from CA. Our goal is to onstru t awell-formed adversary S, su h that8E 2 CE : (Outk(E ;A; �m)) � (Outk(E ;S; �m)):38This is due to the fa t, that we annot add that ID to the message itself without measuring parts of its ontent.39I.e. for any b 2 B, there is a ~b 2 B, s.t. mb � ~b. 60

9 COMPOSABILITY 9.2 Con urrent ComposabilityIf we have allowed an unrestri ted m, then let m0 be the maximum number of invo ations of A. Sin e inthis ase we have polynomial se urity, and be ause of the de�nition of the well-formedness of the adversary, we an hoose m0 as a polynomial only depending on the adversary and on the polynomial limiting the numberof time blo ks of the QN (see the de�nition of se urity under polynomial running time, de�nition 6.2).If we have instead restri ted m, then let instead m0 := m.Note that B is losed under multipli ation with m0 in both ases.We will now onstru t some auxiliary obje ts:Let A0 be a dummy adversary that simply reroutes any messages or orruption requests. For details, seethe de�nition of A0 in the proof for proposition 8.1, whi h ful�ls the same tasks.Let then S0 the orresponding ideal adversary, ful�lling8E 2 CE : (Outk(E ;A0; �)) � (Outk(E ;S0; %)): (25)Su h an S0 exists, sin e � � %.Let �%m be the proto ol that, similar to the omposition �m, simulates several on urrent proto ols, withthe di�eren e, that for some SIDs i the ma hines �i are simulated, for some SIDs i the ma hines %i instead.Whi h kind of ma hine is to be simulated is queried from a spe ial fun tionality F� (see below) upon the �rsta tivation of that opy. When a essing invalid SIDs (greater m or synta ti ally invalid), dummy ma hinesare simulated as with �m.Let ASm be an adversary onstru ted as follows: It simulates A, with the slight variation, that it does notdire tly a ess fun tionalities or parties any more, but instead does this through opies of A0, whi h are then onne ted with the orresponding non-simulated opies of the proto ols and their respe tive fun tionalities.Instead of simply simulating opies of A0, ASm queries the fun tionality F� upon the �rst a tivation of a opyof A0, and then, if F� says, that for that parti ular SID a opy of % is exe uted, S0 is exe uted instead of A0,so that the hoi e of the adversary (A0 or S0) mat hes the orresponding opy of the proto ol.The fun tionality Fi simulates opies of fun tionalities (C�)i or (C%)i, for ea h SID querying F� in orderto know, whether to simulate fun tionalities for � or for %. The asso iated ACF for �%m is then the ACF onsisting of the Fi thus onstru ted. In order to do this, we have to make a small hange to our s hedulingfun tion by allowing, that fun tionalities may ommuni ate with F�.To the asso iated ACF for �%m a new fun tionality F� is added (remapping the IDs of the other fun tion-alities to reate spa e and rewriting all on erned ma hines to use the new IDs). The fun tionality F� = F�(l)depends on a parameter l, and operates as follows: Whenever it is queried on erning an SID i, it does thefollowing:� If i is invalid (greater m or synta ti ally invalid), return ?.� If i has already been queried by some ma hine, return the previously given answer.� In rease num (a global ounter, initialised with 0 upon the �rst a tivation of F�).� If num � l, return �.� If num > l, return %.To denote, given whi h value of l we onstru t F�, we add F�(l) to the argument list of Outk.Using this new onstru tions, we get8E 2 CE : Outk(E ;A; �m) = Outk(E ;ASm; �%m;F�(m0(k))); (26)sin e m0 is onstru ted thus, that F� annot be invoked with more that m0 di�erent valid SIDs.We now onstru t a new environment E� = E�(l), depending on a parameter l 2 N0. This environmentsimulates the environment E , opies of of � resp. % together with their ACFs, the adversary A (as modi�edbefore, i.e. using intermediate adversaries A0 resp. S0), and the opies of the adversaries A0, S0. Instead ofquerying a fun tionality F�, however, E� de ides itself, whether to use the proto ol � or the proto ol % for agiven SID (and the fun tionalities in C� resp. C%, and the adversaries A0 resp. S0). It does this a ording tothe following rules:� If a proto ol/fun tionality/adversary with invalid SID (greater m(k) or synta ti ally in orre t) is a ti-vated, simulate a dummy ma hine.� If a proto ol/fun tionality/adversary with SID i is a tivated, and i is the n-th SID used, and n < l,de ide in favour of �, C� and A0 for this SID. 61

9.3 Universal Composability 9 COMPOSABILITY� If a proto ol/fun tionality/adversary with SID i is a tivated, and i is the n-th SID used, and n > l,de ide in favour of %, C% and S0 for this SID.� If a proto ol/fun tionality/adversary with SID i is a tivated, and i is the l-th SID used, then do notsimulate the obje ts belonging to that SID, but route messages to them to the outside of E�.Using a thus onstru ted environment E�(l), we get for l � 0:8E 2 CE : Outk(E�(l);A0; �) = Outk(E ;ASm; �%m;F�(l)) (27)8E 2 CE : Outk(E�(l);S0; %) = Outk(E ;ASm; �%m;F�(l + 1)) (28)We now simply de�ne S by modifying AS0 thus, that instead of querying F�, it simply assumes the answerto be %, whi h gives the equality:8E 2 CE : (Outk(E ;S; %m)) = (Outk(E ;ASm; �%m;F�(0))) (29)Then we get for all E 2 CE :12 Xa2f0;1gjOutk(E ;A; �m)�Outk(E ;S; %m)j(26;29)= 12 Xa2f0;1gjOutk(E ;ASm; �%m;F�(m0(k))) �Outk(E ;ASm; �%m;F�(0))j= 12 Xa2f0;1g���m0(k)Xl=1 Outk(E ;ASm; �%m;F�(l))� m0(k)Xl=1 Outk(E ;ASm; �%m;F�(l � 1))���(27;28)= 12 Xa2f0;1g���m0(k)Xl=1 Outk(E�(l);A0; �)� m0(k)Xl=1 Outk(E�(l);S0; %)���� m0(k)Xl=1 12 Xa2f0;1g���Outk(E�(l);A0; �)�Outk(E�(l);S0; %)���(25)� m0(k)"(k)for some " 2 B (possibly depending on E and A). Sin e B is losed under multipli ation with m0, it is8E 2 CE : (Outk(E ;A; �m)) � (Outk(E ;S; %m));so �m � %m.We still have two ases to he k: First the polynomial se urity, then the se urity with bounded risk.In the ase of se urity under polynomial running time, the argument given above holds for any polynomialp bounding the number of time blo ks (see de�nition 6.2), and S is onstru ted independently of that p. Sothe proposition does also hold for polynomial se urity.In the ase of se urity with bounded risk, the fun tion m0 = m is �xed, and also " an be hosen indepen-dently of E and A, thus m0" is �xed, too, therefore se urity with bounded risk is also given when omparing�m and %m. �9.3 Universal ComposabilityFor the se urity model in [Can00b℄ there is a proof in that work for universal omposability. This on eptis simply the ombination of the two previous omposability on epts. It states, that when some proto ol� using multiple opies of some fun tionality F is se ure, then the same proto ol � using multiple opies ofsome proto ol % implementing the fun tionality F se urely is also se ure. In our framework, this an easily beproven in two steps, whi h are here informally given: First the on urrent omposability ensures (under the onditions given in proposition 9.8), that multiple opies of the proto ol % are a valid repla ement for multiple opies of the fun tionality, and then be ause of the simple omposability (see proposition 9.3 for details) we an see, that � with the opies of % is as se ure as � with the opies of F .62

A FORMAL DETAILSA Formal detailsA.1 Lemma 3.15In se tion 3.4 we have stated the following lemma, of whi h we will now give the proof:Lemma 3.15Let M be a lassi al IAQS and � some quantum intera tion for M onsisting of operators (Oi).LetMi : HQ;MHFHCC2 ! HQ;MHFHCC2 (i = 1; : : : ; n+1) be observables with eigenspa esspanned by ve tors of the standard basis of HQ;MHF HC C2, where HQ;M HF HC j0i should be ompletely ontained in one of the eigenspa es.We de�ne the mixed states%1 := �Mr �Mf �M (i) nYi=1( �Oi �Mr �Mf �M (i)) %(j0;Mi j#i j#i j0i j0i);%2 := �Mr �Mf �M (i) �Mn+1 nYi=1( �Oi �Mr �Mf �M (i) �Mi) %(j0;Mi j#i j#i j0i j0i);in HQ;MHF HCCZC2, whereMf is the standard basis measurement of HF ,Mr that of C2, andM (i)is the measurement fP (i)k ; k 2 frun; send; re ;worldgg, with P (i)k as in the de�nition of quantum intera tions(de�nition 3.2). �X denotes the density matrix operator for X .Let M be any observable satisfying for ea h of its eigenspa es E, that(h~qj h ~f j h~ j 1 1)PE(jqi jfi j i 1 1) = 0for any basis states j~qi; jqi 2 HQ;M, j ~fi; jfi 2 HF , j~ i; j i 2 HC with j~qi j ~fi j~ i 6= jqi jfi j i, where PEis the proje tion onto E.Then the out omes of M -measuring %1 and %2 have the same probability distribution. �We will now pro eed with the proof of this lemma:Let ri 2 f0; 1g, fi 2 ��, and ki 2 frun; send; re ;worldg (i = 1; : : : ; n) have arbitrary values. Then wede�ne %(k)1 := kYi=1( �Pri+1 �Oi �Pri �Pfi �P (i)ki )%(j0;Mi j#i j#i j0i j0i| {z }=:jSi )%(k)2 := kYi=1( �Mi+1 �Pri+1 �Oi �Pri �Pfi �P (i)ki ) �M1%(jSi)where Pri denotes the proje tion of C2 onto jrii, Pfi denotes the proje tion of HF onto jfii, and P (i)ki are theproje tions from the quantum intera tion � (see de�nition 3.2).Let � := fjqi jfi j i CZ j1i � HQ;M HF HC CZ C2 : q; 2 �Z�n; f 2 ��g[ fjqi HF HQ;M CZ j0i � HQ;M HF HC CZ C2 : q 2 �Z�ng:If for two density matri es %, � there is a de omposition% = j%ih%j; � =X� j�� ih�� jsu h that Pij�i i = j%i, and su h that the sets ��i are disjun t, when de�ned as the minimal subsets of �satisfying j�i i 2LH2��i H, we will say that � is ompatible to % in the ontext of this proof.We will now show by indu tion, that %(k)2 is ompatible to %(k)1 for k = 1; : : : ; n.For k = 0 this is easy: %(0)1 = jSi and %(0)2 =M1jSi. Sin e M1 is de�ned su h, that all its eigenspa es aredire t sums of elements of �, so an appli ation of M1 splits jSi into a sum of ve tors jii, ea h lying in anownLH2�i H with disjun t �i � �. Therefore %(0)2 is ompatible to %(0)1 .63

A.1 Lemma 3.15 A FORMAL DETAILSWe an now assume that %(k)2 is ompatible to %(k)1 for some k 2 f1; : : : ; n � 1g, and will therewith provethat %(k+1)2 is ompatible to %(k+1)1 , thus ompleting the indu tion proof.As an be seen from the de�nition of � and Prk+1 , Pfk+1 , Pkk+1 , it is PH � H for P 2 fPrk+1 ; Pfk+1 ; Pkk+1gand any H 2 �. Therefore if % is ompatible to �, so is �P% to �P�. We get by thri e applying this result that%02 := �Prk+1 �Pfk+1 �P (i)kk+1%(k)2 is ompatible to %01 := �Prk+1 �Pfk+1 �P (i)kk+1%(k)1 .We will now examine how %01 and %02 behave under appli ation of Ok+1. In order to do so, we have todistinguish �ve ases:1. rk+1 = 1,2. rk+1 = 0, kk+1 = run,3. rk+1 = 0, kk+1 = send,4. rk+1 = 0, kk+1 = re ,5. rk+1 = 0, kk+1 = world.Case 1 (rk+1 = 1): In this ase %01 and %02 have been proje ted to have j1i in C2. Therefore Prk+2Ok+1 operateson %01 and %02 by de�nition as�Prk+2 �Ok+1%01;2 = �Prk+2 �UFS;M; ond �UF;M �UM%01;2= �Prk+2 �UFS;M; ond �Prk+2 �UF;M �UM%01;2 (30)where UM = ~UM � U opy;MUFS;M; ond := (U opy;M � ~UFS;M � U opy;M) P0 + 1 P1UF;M := P {F;M 1+ PF;M Xand X = ( 0 11 0 ) 2 U(C2) is the bit �ip. The se ond equality in (30) is due to the fa t, that P0 and P1 ommute,and therefore also Prk+2 and UFS;M; ond.Sin e Y(q;m1; : : :) 7! Y(q; q;m1; : : :) is inje tive, ea h element of � is mapped by U opy;M into someunique element of �. Therefore U opy;M%02 is ompatible to U opy;M%01.Let for brevity be �i := �U opy;M%02i . Then no two di�erent elements of Si �i lie in the same �m1;::: with�m1;::: := spanfjY(q;m1; : : :)i; q 2 �Z�ng HF HC CZ C2 (m1;m2; : : : 2 �Z�n);i.e. ea h element of Si �i is uniquely de�ned by the ontent of the measurement tapes.Sin e ~UM�m1;::: � �m1;::: (by de�nition of ~UM, equation 15), ea h LH2�i H is mapped by ~UM into aLm1;:::2Ti �m1;:::, with disjun t Ti, and sin e ea h �m1;::: is a dire t sum of elements of �, the ompatibility ondition is again satis�ed for �UM%01 = �~UM �U opy;M%01 and �UM%02 = �~UM �U opy;M%02, and, with �i := � �UM%02i ,again no two elements of Si �i lie in the same �m1;:::.Sin e �m1;::: is also losed under appli ation of UF;M, the same argumentation as just given for ~UM holdsfor UF;M, too.After applying Prk+2 , the ompatibility is preserved as already explained above for Prk+1 .If rk+2 = 1, UFS;M; ond operates as the identity, so the ompatibility is trivially preserved. If rk+2 =0, UFS;M; ond operates as U opy;M � ~UFS;M � U opy;M. This also preserves the ompatibility, with the sameargumentation as given for ~UM �U opy;M (with the only di�eren e, that U opy;M is applied a se ond time after~UFS;M).We on lude, that in ase 1 we have ompatibility of �Ok%01 = �UFS;M; ond �Prk+2 �UF;M �UM%01 and �Ok%02 =�UFS;M; ond �Prk+2 �UF;M �UM%02.Case 2 (rk+1 = 0, kk+1 = run): Here %01 and %02 have been proje ted with P0 and P (k+1)run . Therefore Ok+1operates on %01 and %02 by de�nition as�Prk+2 �Ok+1%01;2 = �Prk+2 �UFS;M; ond �UF;M �UM �X%01;2:Sin e � is well-formed, %01 lies in HQ;M j#i j#i CZ C2. To prove this, onsider that all Pri , Pfi , P iki ,and the proje tor used in the well-formedness ondition for quantum intera tions ommute.64

A FORMAL DETAILS A.1 Lemma 3.15Sin e %02 is ompatible to %01, is does also lie in HQ;M j#i j#i CZ C2.Be ause of rk+1 = 0, we further have that %01 and %02 both lie in HQ;M j#i j#i CZ j0i.The bit �ip X maps jqi j#i j#iCZ j0i into jqi j#i j#iCZ j1i, so the ompatibility of X%01and X%02 follows.The rest of this ase is proven as in ase 1, sin e the X%01;2 populate the same spa e as is done in ase 1 by%01;2, and the remaining parts of Oi are the same (i.e. �UFS;M; ond �UF;M �UM).Case 3 (rk+1 = 0, kk+1 = send): Here Oi operates as U opy;M ~US;MU opy;M. The ompatibility is preserved,the proof is analogous to that for the preservation under appli ation of ~UMU opy;M above.Case 4 (rk+1 = 0, kk+1 = re ): Here Oi operates as U opy;M ~UR;MU opy;M. By pro eeding analogously to~UMU opy;M, we prove ompatibility.Case 5 (rk+1 = 0, kk+1 = world): Here %01;2 lie in HQ;M HF HC CZ j0i, and Oi operates onlyon HF HC CZ. Thus ea h �%02i is of the form jqi HF HC CZ j0i and mapped onto itself. Thispreserves the ompatibility and �nishes this ase.We have now proven, that in all �ve ases we have ompatible �Ok+1 �Prk+1 �Pfk+1 �P (k+1)kk+1 %(k)1;2. A furtherappli ation of Prk+2 does not destroy this ompatibility as already des ribed above. So%002 := �Prk+2Ok+1 �Prk+1 �Pfk+1 �P (k+1)kk+1 %(k)1;2is ompatible to %(k+1)1 .To �nish the indu tion step, we still need to prove that �Mk+2%002 is ompatible to %(k+1)1 .Ea h eigenspa e Ej of M := Mk+2 an be written as a dire t sum SH2�0j��H of elements of �. M -measuring %002 =Pi %(j%002i i) thus yields%(k+1)2 =Xi;j %(Pj j%002i i) =:Xi;j %(ji;ji)where Pj is the proje tion on Ej . Be ause of i;j 2 SH2�i\�0j H and Pi;j ji;ji = Pij%002i i = j%(k+1)1 i, wehave shown that %(k+1)2 is ompatible to %(k+1)1 , sin e the �i \ �j are pairwise disjun t.So the indu tion step is ompleted, and we have proven, that %(k)2 is ompatible to %(k)1 for k = 1; : : : ; n.Using te hniques analogue to those above, we see, that %�1;2 := �Prn+1 �Pfn+1 �P (n+1)kn+1 %(n)1;2 are ompatible. Sin eall Pri , Pfi , P (i)ki ommute, it is%�1 := �Prn+1 �Pfn+1 �P (n+1)kn+1 nYi=1( �Oi �Pri �Pfi �P (i)ki ) %(jSi);%�2 := �Prn+1 �Pfn+1 �P (n+1)kn+1 �Mn+1 nYi=1( �Oi �Pri �Pfi �P (i)ki �Mi) %(jSi);Note that this is almost the de�nition of %1 resp. %2, we have only repla ed the Mr-, Mf - and M (i)-measurements by proje tions on a sequen e of their eigenspa es. Therefore summing %�1;2 over all possiblesequen es of ri 2 f0; 1g, fi 2 ��, ki 2 frun; send; re ;worldg, we get %1;2. So if we an prove, that M -measuring of %�1;2 gives the same generalised probability distributions, we know that this also holds for %1;2,sin e the generalised probability distribution of a measurement of a sum of generalised density matri es is thesum of the generalised probability distributions of the measurements of the generalised density matri es.So we will now prove that M -measuring %�1 and %�2 gives the same generalised probability distribution andtherewith �nish this proof.Let E be some eigenspa e of M and PE the proje tor onto E. It follows from the de�nition of M , thatE =LH2�E H for some �E � �. Therefore jPi i := PE j%�2i i 2LH2�E\�i H. So all jPi i are orthogonal andPijPi i = jP i := PE j%�1 i. If P1;E and P2;E are the generalised probabilities of measuring E on %�1 resp. %�2,we get P1;E = hP jP i =Xi;j hPi jPj i =Xi hPi jPi i = P2;E :We have shown the last pending statement, i.e. that M -measuring %�1 and %�2 yields the same generalisedprobability distribution, so our proof is omplete. �65

A.2 Sto hasti vs. hard relative polynomial running time (se tion 3.3.4) A FORMAL DETAILSA.2 Sto hasti vs. hard relative polynomial running time (se tion 3.3.4)In se tion 3.3.4 we have laimed, that if M2 is of sto hasti polynomial running time relative to M1, then itis also of hard polynomial running time relative to M1. Of this we will now give the proof:Assume, that M2 is of sto hasti polynomial running time relative to M1, therefore there is a polynomialp, su h that P (T2 � t) � P (p(T1 + k + n) � t):for all k � 0, n � 1, t � 0, �1, �2, where Xi is the exe ution trans ripts of Mi on �i, and Ti := TXik;n.W.l.o.g. we an assume, that p has oe� ients in N0 and is stri tly monotonously in reasing. Thereforewe get P (T2 > t) = P (T2 � t+ 1) � P (p(T1 + k + n) � t+ 1) = P (p(T1 + k + n) > t):Let ti := Ti;n;k (as in the de�nition of hard relative polynomial running time), and t02 := p(t1 +n+ k). Wethen haveP (T2 > t02) = P (T2 > p(t1 + n+ k)) � P (p(T1 + n+ k) > p(t1 + n+ k)) = P (T1 > t1) def= 0:Sin e t2 is minimal with P (T2 > t2) = 0, we have t2 � t02 = p(t1 + n + k), so M2 is of hard polynomialrunning time relative to M1. �A.3 Stri t polynomial running timeThe following de�nition is equivalent to the original de�nition of stri t polynomial running time given inde�nition 3.6:De�nition A.2: Stri t polynomial running time (variant 1)Let Ek;n;t be as in the de�nition of running time (de�nition 3.5).We say an IAQS M has (stri t) polynomial running time if there is a polynomial p su h that for anyquantum intera tion � it is P (X 2 Kk nEk;n;p(k+n)�1) = 0for all n 2 N, k 2 N0 with X being the exe ution trans ript on �. �Proof: Sin e TXk;n = ? has probability 1 or 0 (by de�nition of TXk;n), it isP (TXk;n < p(k + n) or TXk;n = ?) = 1() P (TXk;n � p(k + n); TXk;n 6= ?) = 0 or P (TXk;n = ?) = 1def TXk;n() P (X 2 [t2N[f1gEk;n;t nEk;n;p(k+n)�1) = 0 orP (X 2 [t2N[f1gEk;n;t) = 0() P (X 2 [t2N[f1gEk;n;t nEk;n;p(k+n)�1) = 0:Further it is [t2N[f1gEk;n;t = Ek;n;1 = Kkas follows from the de�nition of Ek;n;t and Kk (the latter being as in de�nition 3.5). �If we repla e vanishing probability by impossibility, we get the equivalentDe�nition A.3: Stri t polynomial running time (variant 2)Let Ek;n;t be as in the de�nition of running time (de�nition 3.5).We say an IAQS M has (stri t) polynomial running time if there is a polynomial p su h that for anyquantum intera tion � the set Kk nEk;n;p(k+n)�1is impossible for all n 2 N, k 2 N0 with X being the exe ution trans ript on �. �Proof: It is su� ient to show, that Mk;n := Kk nEk;n;p(k+n)�1 is impossible if and only if is has probability 0.66

A FORMAL DETAILS A.4 Time evolution of a quantum networkIf Mk;n is impossible, it also has probability 0, as shown in se tion 3.2.Let Mk;n be of probability 0, and (ei) 2 Mk;n. Then there is a sequen e of onse utive elements (ri)mi=1having the properties as des ribed in the de�nition of Ek;n;t (de�nition 3.5) and m � p(k + n). Let ~m besu h, that r1; : : : ; rp(k+n) is ontained in e1; : : : ; e ~m. Then any sequen e beginning with e1; : : : ; e ~m is not inEk;n;p(k+n)�1. Further any sequen e beginning with e1; : : : ; e ~m is in Kk, be ause the value of k is determinedby the elements of the trans ript pre eding the �rst element formed (run;#) or (stop; �), and r1 has that form.So P (Xi = ei; i = 1; : : : ; ~m) � P (X 2Mk;n) = 0, therefore (ei) is impossible.Sin e (ei) was an arbitrary hosen element of Mk;n, that set is impossible, too. �A.4 Time evolution of a quantum networkDe�nition A.4: Time evolution of a quantum networkLet N be a quantum network, then the time evolution UN is onstru ted as follows:Let for G 2 �� be Æ(a1; : : : ; an) = G, Æ(s hed; �; token; �) be the last element of (ai) having the formÆ(s hed; �; �; �). De�ne then token(G) := token, if token 2 IN , and set token(G) := ? if token =2 IN or if thereis no element of the required form.Let P (1)t (t 2 IN [ f?g) be the proje tion of HG;N ontospanfjGi : token(G) = tg:Let then U (2) := Xi2IN (UNiP (1)i ) + P (1)?P (3)1 := Xi2IN (PF;NiP (1)i )P (3)0 := Xi2IN (P {F;NiP (1)i ):Let the linear operators UFi=f (f 2 f0; 1g) operate on HG;N HH;Ni asUFi=f jGi jhi := jN(G;Æ(end onf; f))i jN(h;Æ(end onf; f))i (G; h 2 ��)and P (30)f (f = 0; 1) the proje tion of HG;N ontospanfjGi : G 2 ��; f(G) = fgwhere f(G) := 1 ifÆ�1(G) exists and the last element ofÆ�1(G) having the formÆ(end onf; �) exists andisÆ(end onf; 1), otherwise let f(G) = 0.Let further Uframe;i (i 2 IN ) operate on HG;N HF HH;Ni asUframe;ijGi jfi jhii := jN(G;Æ(frame; f))i jfi jN(hi;Æ(frame; f))i (G; f; hi 2 ��);and Uframe=f (f 2 ��) operate on HG;N HF asUframe=f jGi j ~fi := jGi j ~f frame(G)� fi (G; f; ~f 2 ��);where frame(G) is de�ned su h, that Æ(frame; frame(G)) is the last element of Æ�1(G) having the formÆ(frame; �), ifÆ�1(G) exists, and there is an element thus formed. Let frame(G) := # otherwise.Let S := E��IN ��� (the image range of S hedN ) and the operators Us hed;s (s 2 S) and Unos hed operateon HG;N as follows: Us hed;(E;t;d)jGi := jN(G;Æ(s hed; E0; t; d))iUnos hedjGi := jN(G; nos hed)iHere E0 is the texti� ation of E, de�ned via (e1; : : : ; en) := E, (ti; i1; : : : ; im) := ei, t0i := transmit, orruptor ontrol, depending on ti, e0i := (t0i; i1; : : : ; im) and E0 :=Æ(e01; : : : ; e0n).67

A.4 Time evolution of a quantum network A FORMAL DETAILSThen let U (4) := Xi2IN (UFi=1P (3)1 P (1)i + UFi=0P (3)0 P (1)i ) + P (1)? ;U (6) := Xi2IN (UFS;NiP (30)1 P (1)i + P (30)0 P (1)i ) + P (1)? ;U (7) := Xi2IN (Uframe;iP (30)1 P (1)i + P (30)0 P (1)i ) + P (1)? ;U (8) := Xi2IN (Uframe=#P (30)1 P (1)i + P (30)0 P (1)i ) + P (1)? :Let ~P (9)s (s 2 S) be the proje tion of HG;N ontospanfjGi : S hedN (G) = sgand P (9)s := Xi2IN ( ~P (9)s P (30)1 P (1)i + P (30)0 P (1)i ) + ~P (9)s P (1)? (s 2 S);U (10) := Xi2IN (Xs2S(Us hed;sP (9)s P (30)1 P (1)i ) + Unos hedP (30)0 P (1)i ) +Xs2SUs hed;sP (9)s P (1)? :Let s hed(G) be the last element of Æ�1 having the form Æ(s hed; �) or nos hed. Let s hed(G) := ?, ifthere is no su h element. Then P (11)E (E 2 E�) proje ts HG;N ontospanfjGi : G; t; d 2 ��; s hed(G) =Æ(s hed; E0; t; d)g;where E0 is the texti� ation of E, as des ribed above.The operator P (11)? proje ts ontospanfjGi : s hed(G) = nos hed or s hed(G) = ?g:Then it is U (11)E :=Qn�=1 Ueve� with (e1; : : : ; en) := E for an event list E 2 E� andU (11) := XE2E�(U (11)E P (11)E ) + P (11)? ;Uev(transmit;s;d;f) := UR;NdU 0frame=fUS;Ns ;Uev( ontrol;d;f) := UR;NdU 0frame=f ;Uev( orrupt; ;t;f) := UR;N U orr;NtU 0frame=f;histiHere U 0frame=f;histi operates on HF HH;Ni asU 0frame=f;histi j ~fi jhi := j ~f �Æ(f; h)i (f; ~f; h 2 ��)and U 0frame=i operates on HF asU 0frame=ij ~fi := j ~f � fi (f; ~f 2 ��):We �nally get the time evolution UN asUN := U (11)U (10)U (8)U (7)U (6)U (4)U (2): �We will now ompare this formal de�nition with the algorithm given in se tion 4.2 and show, that both do thesame.Step 1 does not modify the state of the network, therefore there is no orresponding unitary operator U (1).It is formulated as setting i to some value, this an also be interpreted as a bran h, where the program takesanother path for ea h possible value of i, ea h of those paths exe uting its program as if the variable i would68

A FORMAL DETAILS A.4 Time evolution of a quantum networkhold that given value. To implement su h bran hes, we need to have a proje tion onto those states, whi hlead into a given path. Therefore we have onstru ted P (1)i , whi h goes into the bran h onditioned by �thelast datum formed . . . had token = i�, and for the bran h �there is no su h datum�, we have P (1)? . Now ea hstep whose behaviour depends on this bran h, has to be of the form Pi2IN (UiP (1)i ) + U?P (1)? , where Ui, U?are the a tions to be taken in dependen e of the respe tive out omes of the bran h.Step 2 is to evaluate US;Ni . Sin e US;Ni may be di�erent for ea h i, we have to split the exe ution usingP (1)i . If P (1)? applies, we do nothing (i.e. we apply the identity), sin e the instru tion in 1 was to skip steps2�9.In step 3 we again have no real a tion, but only a bran h depending on the result of applying the end on�guration measurement PF;Ni on Ni. Again this is formulated in the algorithm as an assignment to avariable, and again we reformulate it as a bran h between paths �Fi = 0� and �Fi = 1�. And this measurementwe also have to split depending on the bran h done in step 1.In step 4 we exe ute UFi=f for ea h path in whi h we have Fi = f (f = 0; 1), and do nothing if P (1)? applies,i.e. if we are in the path skipping steps 2�9. The operator UFi=f just appends the informationÆ(end onf; f)to jGi and jhistii.For step 5 we have not onstru ted any operators, sin e it is only a bran h depending on the value of Fi,and that bran h is already realised by P (3)k . We only have to pay attention, that all further steps do nothingif Fi = 0. In step 5 there does also appear an instru tion �append nos hed to jGi�, but this instru tion wewill only exe ute in step 10, we may hoose to do su h, sin e in the intermediate steps there is no a tion onthat exe ution path. And we hoose to do so, sin e this makes the proof, that the time evolution is unitary,mu h easier, sin e it ensures that every step by itself is already unitary.For step 6 we have onstru ted U (6) quite analogous to U (2), ex ept that it does nothing, if the ma hinehas not terminated (Fi = 0).There is an important point: Sin e we now hange the ma hines on�guration by appli ation of UFS;Ni ,and in parti ular whether the ma hine is in an end on�guration, we may no longer use P (3) to get the valueof the variable Fi, sin e P (3) uses PF;Ni to de ide depending on the ma hine's state and may thus yield otherresults now. Therefore we de�ne the operator P (30) to be used in pla e of P (3) from now on.40 This proje tion�nds out, whi h is the value of Fi by looking at jGi, where we have storedÆ(end onf; Fi) in step 4.In step 7 we have U (7), whi h alls Uframe;i depending on the value of i, and only if we are not in a pathwhi h skips this step. Uframe;i just appends the ontent of jframei to jGi and jhistii.In step 8 we set jframei to j#i, provided that we do not skip this step. To a hieve this, we de�ne anoperator Uframe=f , whi h sets jframei to f by using the �- and the -operations: Sin e frame(G) holds, dueto step 7, the same value as jframei, for jframei = j ~fi it is ~f frame(G) � f = f , so we an in fa t write fonto jframei. With the spe ial ase of f = # we an thus onstru t U (8).We now ome to step 9. Note that here the bran h begun in step 1 merges again, therefore we will exe utethis step for the ase that Fi = 1 and for the ase that �nding the token in step 1 failed (proje tor P (1)? ). Asin step 1, this variable assignment is realised by a bran h over all possible values for that variable ( alled sresp. (events,token,data)), so we only de�ne a proje tor P (9)s to be used in the following steps.Then step 10 writes the value of s, i.e. of the output of S hedN al ulated in the pre eding step, onto jGiusing the a ording syntax, ex ept when we are in the path with Fi = 0, where we write nos hed (this wasdelayed from step 5). This is done using the operators Us hed;s and Unos hed respe tively.For step 11 we have to split in a path for ea h possible event list returned by S hedN , and in a path for the ase, that we have not exe uted S hedN at all, due to previous bran hes. We annot, however, use P (1)t anymore to de ide in whi h bran h we are, sin e we have modi�ed the ontent of jGi in a way whi h hanges theoutput of token(G). Therefore we de�ne the operator P (11)? , whi h he ks whether we have written nos hedin step 10. In this ase we abstain from any a tions.Otherwise we split depending of the data stored on jGi into a path for ea h event list output by S hedN .We annot use P (9) for this, sin e �rst this operator uses P (1) and se ond we have modi�ed the ontent ofjGi, i.e. the input to S hedN . Therefore we de�ne P (11)E , whi h proje ts onto those paths, where we have gotthe event list E, depending on what was stored on jGi.In ea h path we exe ute U (11)E , whi h again exe utes Ueve� for ea h event e� in E. Depending of the type ofe� , we have three de�nitions for Ueve� , whi h should be straightforward, ex ept for the operators U 0frame=f andU 0frame=f;histi still to be explained: They write f resp. the on atenation of f and jhistii onto jframei. This an be done, be ause jframei has the ontent j#i.40We already use this new proje tion in this step to ensure that U(6) is unitary.69

A.4 Time evolution of a quantum network A FORMAL DETAILSWe get the �nal time evolution operator UN by applying all the unitary evolutions for the single steps.We will now pro eed and prove, that UN is unitary. In order to do this, we will prove it for ea h of the fa torsU (2), U (4), U (6), U (7), U (8), U (10), and U (11).Any operator of the form U =Pi UiPi is unitary, if the Ui are unitary, and if the Pi are pairwise ommutingproje tions with Pi Pi = 1 and PiPj = 0 (i 6= j), whi h do also ommute with the Ui, sin eUyU =Xi;j P yi Uyi UjPj =Xi;j Uyi P yi PjUj =Xi Uyi PiUi =Xi Pi = 1:This ondition is satis�ed by U (2):41 The P (1)t (t 2 IN [ f?g) satisfy the pairwise ommutation, sin e theyproje t onto pairwise orthogonal subspa es by onstru tion, and the UNi ommute with the P (1)t , sin e theUNi operate only on HQ;M, while the P (1)t operate on HQ;Ni . So U (2) is unitary.We will now examine U (4). It isXi2IN (P (3)1 P (1)i + P (3)0 P (1)i ) + P (1)? = (P (3)1 + P (3)0 )| {z }=Pi2IN P (1)i Xi2IN P (1)i + P (1)? = 1:It ommutes PF;Ni with P (1)t , sin e they operate on HQ;Ni resp. HG;N . The ommutator of PF;Ni and PF;Njvanishes, too, be ause they operate on the di�erent tensor fa tors HQ;Ni and HQ;Nj if they are di�erent. TheP (1)t ommute, as already mentioned above.Sin e the P (3)k are in the ring generated by the P (1)i and the PF;Ni , they do also ommute with the P (1)t .So the pairwise ommutation is given in the ase of U (4).It ommutes UFi=f with PF;Ni , sin e they operate on di�erent tensor fa tors HG;N HH;Ni and HQ;Ni .Further does UFi=f also ommute with P (1)t , due to the following: It is token(G) = t if and only iftoken(N(G;Æ(end onf; f))) = t, so for any basis state jGi jhi 2 HG;N HH;Ni it isUFi=fP (1)t jGi jhi = UFi=fÆjGi jhi= ÆjN(G;Æ(end onf; f))i jN(h;Æ(end onf; f))i = P (1)t UFi=f jGi jhi;where we set Æ := 1 if token(G) = t, Æ := 0 otherwise.So the UFi=f ommute with all P (1)t and all P (3)k , therefore U (4) is unitary.The P (30)k and the P (1)t all ommute pairwise, sin e they are all proje tions onto spa es spanned by basisve tors. They do also ommute with UFS;Ni , sin e the latter operates on HQ;Ni HF , while the proje tionsoperate on HG;N .Further it is Pi2IN (P (30)1 P (1)i + P (30)0 P (1)i ) + P (1)? = 1, so U (6) is unitary.For U (7), the proje tions ommute and sum up to 1 as already shown above. And that Uframe;i ommuteswith those proje tions is shown analogous to the ommutation of UFi=f and P (1)t . So U (7) is unitary.Sin e the P (30)k and the P (1)t are all proje tions onto basis ve tors and operate only onHG;N , while Uframe=#is read-only on HG;N , they do all ommute, so U (8) is unitary.To prove, that U (10) is unitary, we annot use the above re ipe, sin e Us hed;s and Unos hed do not ommutewith P (1)k nor with P (9)s .42 So we will �rst introdu e some proje tions P (10)t (t 2 IN [ f?g) and P (90)s (s 2 S),that satisfy UP (1)t = P (10)t U and UP (9)s = P (90)s U:for U 2 fUs hed;s; Unos hedg.Proje tions with these properties are given byimP (10)t = spanfjN(G; h)i : G; h 2 ��; token(G) = tg (t 2 IN [ f?g);imP (90)s = spanfjN(G; h)i : G; h 2 ��; S hedN (G) = sg (s 2 S):41Note, that the Ui orresponding to P (1)? is the identity.42In fa t, Unos hed ommutes with P (1)k , but this is of no matter for our proof.70

A FORMAL DETAILS A.5 �MG �U �MG = �MG �U (se tion 5.5)Sin e P (1)i , P (10)i , P (30), P (9) and P (90) are all proje tions onto spans of basis ve tors, they do all ommute.Be ause of this, ea h two di�erent proje tions out of P (10)i P (30)1 P (90)s , P (10)i P (30)0 , P (10)? P (90)s have vanishingprodu t.It is Xs2S P (9)s P (30)1 P (1)i =Xs2S ~P (9)s| {z }=1 P (30)1 P (1)i = P (30)1 P (1)iand similarly Ps2S P (9)s P (1)? = P (1)? , soXi2IN (Xs2S(P (9)s P (30)1 P (1)i ) + P (30)0 P (1)i ) +Xs2S P (9)s P (1)? = Xi2IN (P (30)1 P (1)i + P (30)0 P (1)i ) + P (1)? = 1:We an now write U := U (10) asP� U�P� with unitary U� and with U�P� = P 0�U� , where P 0�P 0� = 0 for � 6= �,and where P� P� = 1. Therefore it isUyU =X�;� P y�Uy�U�P� =X�;� Uy�P 0y� P 0�U� =X� Uy�P 0y� P 0�U� =X� P y�Uy�U�P� =X� P� = 1;so U (10) is unitary.For U (11) we an again use our re ipe, sin e the P (11)E , P (11)? sum up to 1, multiply mutually to 0, ommutewith ea h other and with U (11), sin e the latter does not operate on HG;N , while the proje tions operate onlyon HG;N . So U (11) is unitary.Sin e all fa tors of UN are unitary, UN itself is unitary, too. �A.5 �MG �U �MG = �MG �U (se tion 5.5)In se tion 5.5 we have stated the following:Let U 2 U(HHG;N ) operate inje tively on HG;N , i.e. for any basis state jGi 2 HG;N the value of G isknown, when one of the Gi in U ji jGi =Pi �ijiijGii is known. Let further MG be the measurement ofHG;N in the standard basis. Then �MG �U �MG = �MG �U .This an be proven as follows: Any state in H HG;N an be written as Pi �ij�iijGii with �i 2 C,di�erent basis ve tors jGii 2 HG;N , and ve tors j�ii 2 H. Then we get%�Xi �ij�iijGii� �MG�!Xi j�ij2%(j�iijGii)�U�!Xi j�ij2%�Xj �ij j�ijijGiji��MG�!Xi j�ij2Xj j�ij j2%(j�ijijGij i):Sin e all the jGii were di�erent, the jGiji were di�erent, too (inje tivity of U). Therefore the appli ation of�MG has ex hanged the summation and the appli ation of %. The same applies for%�Xi �ij�iijGii� �U�! %�Xi �iXj �ij j�ijijGiji��MG�!Xi j�ij2Xj j�ij j2%(j�ijijGij i):So �MG �U �MG = �MG �U for all pure states, thus also for all mixed states. �A.6 Lemma 3.30In se tion 3.5.1 we have stated the followingLemma 3.30: Lo al well-formedness ondition for IQTMAn IQTM M = (Q; q0; qf ; n; Æ) is well-formed, if and only if the following onditions are ful�lled for Æ:71

A.6 Lemma 3.30 A FORMAL DETAILS� Unit length: kÆ(q; �1; : : : ; �n)k = 1 for all q 2 Q, �1; : : : ; �n 2 �.� Orthogonality: Æ(q; �1; : : : ; �n) ? Æ(~q; ~�1; : : : ; ~�n) for any q; ~q 2 Q, �i; ~�i 2 � with (q; �1; : : : ; �n) 6=(~q; ~�1; : : : ; ~�n).� Separability: For any I � f1; : : : ; ng, I 6= ; it is: For �i; ~�i; �0i; ~�0i 2 �, q; ~q 2 Q, di; ~di 2 fL;Rg (i < n),dn; ~dn 2 fL;R;U;Dg, di 6= ~di, it isXq0 X Æ(q; (�i)i; (�0i)i; q0; (di)i)yÆ(~q; (~�i)i; (~�0i)i; q0; ( ~di)i) = 0where the se ond sum runs over all �0i; ~�0i 2 �, di; ~di 2 fL;Rg (i < n), dn; ~dn 2 fL;R;U;Dg, whi hsatisfy for i 2 I : �0i = �0i, ~�0i = ~�0i, di = di, ~di = ~di; and for i =2 I : �0i = ~�0i, di = ~di.Here Æ is used as in the de�nition of the time evolution (de�nition 3.21). �To prove, that from the lo al well-formedness follows well-formedness, we have to show for any two di�erentbasis states ji; j�i 2 HQ;M of length 1, that UMji ? UMj�i and kUMjik = 1. If any of those states doesnot have the form required in the de�nition of UM, this is easily veri�able, so we an assume w.l.o.g. twostates ji = jY(q; u(rm); u(r); �; u(h1); t1; u(h2); t2; : : :)iand j�i = jY(q�; u(r�m); u(r�); ��; u(h�1); t�1; u(h�2); t�2; : : :)i:For onvenien e, we onsider ve tors jY(a1; a2; : : :)i 2 HQ;M as ja1i ja2i � � � 2 HQ;M;1 HQ;M;2 � � �.That kUMjik = 1, follows from the de�nition of UM and the unit-length- ondition.If rm 6= r�m, then UMji and UMj�i are orthogonal, sin e they are omposed from basis ve tors whi hhave u(rm) resp. u(r�m) in HQ;M;2. So we an assume w.l.o.g. rm = r�m. With the same argumentation wealso get w.l.o.g. � = ��, and hi = h�i for i � n, i 6= n+ r, and of ourse ti = t�i for i � n+ rm.Now if ji and j�i di�er at most in q, ti;hi (i = 1; : : : ; n � 1; n+ r), orthogonality of UMji and UMj�ifollows from the orthogonality of Æ (note rm � 3). So we will now assume, that ji and j�i di�er somewhereelse.If for some i 2 f1; : : : ; n� 1g it is h�i =2 fhi + 2; hi; hi � 2g, the images of ji and j�i will be orthogonal,sin e they are omposed of basis ve tors, whi h have in the subspa e ontaining hi, h�i the ontents u(hi +L)or u(hi + R), resp. u(h�i + L) or u(h�i + R), whi h are di�erent. So we assume h�i 2 fhi + 2; hi; hi � 2g fori 2 f1; : : : ; n� 1; n+ rg.Similarly we assume (h�n+r� ; r�) 2 f(hn+r � 2; r); (hn+r� ; r � 2); (hn+r; r)g (mod (0; rm)).Let now I := fi 2 f1; : : : ; n� 1g; hi 6= h�i g [(fng; if hn+r 6= h�n+r or r 6= r�;;; otherwise:If I = ;, there must be some tape symbols other than ti;hi , t�i;h�i that di�er between ji and j�i, these symbolswill also di�er after applying UM, resulting in UMji ? UMj�i. So we will assume I 6= ;.It ishjU yMUMj�i=X Æ(q; (ti;hi)n�1i=1 ; tn+r;hn+r ; q0; (�i)ni=1; (di)ni=1)yÆ(q�; (t�i;h�i )n�1i=1 ; t�n+r�;h�n+r� ; q0�; (��i )ni=1; (d�i )ni=1) �hY(q0; u(rm); u(r + �dn mod rm); �; (u(hi + ~di); ~ti)i)jjY(q0�; u(rm); u(r� + �d�n mod rm); �; (u(h�i + ~d�i ); ~t�i )i)i;where the meanings of the~and the�are analogous to the use in the de�nition of UM. The sum runs over allq0; q0� 2 Q, �1; : : : ; �n; ��1 ; : : : ; ��n 2 �, d1; : : : ; dn�1; d�1; : : : ; d�n�1 2 fL;Rg, dn; d�n 2 fL;R;U;Dg.The s alar produ t inside the sum is non-zero (thus equal 1), if and only if the following onditions aresatis�ed:� At least one of the s alar produ ts is non-zero.� It is q0 = q0�. 72

A FORMAL DETAILS A.6 Lemma 3.30� For i 2 I , i 6= n, we have or di = R, d�i = L or di = L, d�i = R, depending only on how hi and h�i relate,i.e. independent of the summation variables.� For i =2 I , i 6= n, we have di = d�i .� For n 2 I , we have dn; d�n 2 f(L;R;U;D)g, dn 6= d�n. Again the values of dn, d�n are independent of thesummation variables.� For n =2 I , we have and di = d�i .� For i 2 I , i 6= n, it is ti;h�i = ��i and t�i;hi = �i.� For n 2 I , it is tn+r�;h�n+r� = ��i and t�n+r;hn+r = �i.� If i =2 I , then �i = ��i .When we remove all summands, in whi h these onditions are not ful�lled, we get a sum of the same value,whi h is empty or has the form of the sum in the separability ondition. In both ases the sum vanishes, soUMji ? UMj�i.The reverse dire tion of this proof is left to the reader. �

73

B KEYWORD INDEXB Keyword Indexabortpartial, se urity with, 51absolute se urity, 43abstra t, 5a ess stru ture, 35full, 35ACF, 40(adaptive/stati ) instantiation of an, 40asso iated, 40parallelisation, 60simple omposition of, 57adaptive adversarial quantum network, 35adaptive instantiationof an ACF, 40adaptive se urity, 53adjustable se urity, 52adversarial ommuni ation framework, 40(adaptive/stati ) instantiation of an, 40asso iated, 40adversarial quantum network, 35adaptive, 35stati , 35adversarypolynomially non-blo king, 39(sto hasti ally) non-blo king, 39well-formed, 38algorithmknown, temporary assumption on, 47non-usage of, 48phase dependent, 48appendstru tured, 12approximative se urity, 43AQN, 35asso iated ACF, 40asso iated adversarial ommuni ation framework, 40assumptiontemporary, 45on available primitives, 46on omputational power, 46on orruption, 46on known algorithms, 47base, 9blank, 11blank symbol, 11bounded riskse urity with, 44 heat-dete tionse urity with, 50 lassi al IAQS, 22 lassi al interfa esIAQS with, 23 ommuni ation frameworkadversarial, 40

ommuni ation tape spa e, 14 ompositionsimple, of ACF, 57simple, of proto ols, 57universal, 62 omposition theorem on urrent, 60simple, 58 omputational powertemporary assumption, 46 on atenationstru tured, 12 on urrent omposition theorem, 60 on�guration spa eof an IAQS, 14of a QN, 32 on�guration spa e� 14 onstraint, 49 ontrol event, 31 orruption overt, 52passive, 50temporary assumption, 46 orruption event, 31 orruption noti� ation, 52delayed, 52immediate, 52 orruption operator, 14of an IQTM, 28passive, 50 overt orruption, 52delayed orruption noti� ation, 52density matrix, 9generalised, 9normalised, 10density matrix operator, 10empty string, 12empty tape ontent, 11end on�guration proje tion, 14event ontrol, 31 orruption, 31transmission, 31expe ted polynomial running time, 20exponentially negligible, 11exponential negligibility, 11exponential sto hasti indistinguishability, 11frame send operator, 14of an IQTM, 27frame tape spa e, 14frameworkadversarial ommuni ation, 40full a ess stru ture, 3574

B KEYWORD INDEXgeneralised density matrix, 9intensity of a, 10generalised probability distribution, 10global history tape spa e, 32hard relative polynomial running time, 21IAQS, 14 lassi al, 22parallelisation, 59polynomial, 20with lassi al interfa es, 23IAQS with lassi al interfa es, 29ICTM, 29ID ma hine, 31identity, 9immediate orruption noti� ation, 52indistinguishabilityexponential sto hasti , 11sto hasti , 11with respe t to a set of bounds, 11instantiationof an ACF, 40intensityof a generalised density matrix, 10intera tionquantum, 15intera tive lassi al Turing ma hine, 29intera tive quantum system, 14intera tive quantum Turing ma hine, 26intera tive quantum Turing ma hineswith lassi al interfa es, 29intera tive Turing ma hine, 30partial, 30interleavingtape ontents, 12introdu tion, 5IQCTM, 29well-formed, 30IQTM, 26 orruption operator, 28frame send operator, 27lo al well-formedness ondition, 28, 71polynomial, 28re eive operator, 28send operator, 27time evolution operator, 26well-formed, 27ITM, 30partial, 30known algorithmstemporary assumption, 47lengthof a string, 11literals

string, 12lo al well-formedness onditionfor IQTM, 28, 71ma hine history tape spa e, 32ma hine ID, 31message driven s heduling, 35mixed state, 9multi-phase proto ols, 45negligibility, 11exponential, 11negligible, 11exponentially, 11network(adaptive) adversarial quantum, 35quantum, 31stati adversarial quantum, 35non-blo king adversary, 39polynomially, 39sto hasti ally, 39non-usageof an algorithm, 48phase dependent, 48normalised density matrix, 10noti� ation orruption, 52delayed orruption, 52immediate orruption, 52notionse urity, 50numbering of �, 11operator, 9passive orruption, 50outputof an AQN, 41overview, 5parallelisationof ACF, 60of IAQS, 59of proto ols, 60partial abortse urity with, 51partial intera tive Turing ma hine, 30partial ITM, 30passive orruption, 50passive orruption operator, 50phase dependent non-usageof an algorithm, 48phases, 45phase tra e, 48PIAQS, 20PIQTM, 28pliable se urity, 51polynomial IQTM, 28polynomially non-blo king adversary, 3975

B KEYWORD INDEXpolynomial running time, 19expe ted, 20(hard) relative, 21reliable, 20se urity under, 43polynomial se urity, 43primitive, 7temporary assumption on, 46probability distributiongeneralised, 10of a density matrix, 9problem, 48proje tion, 9proto ol, 40multi-phase, 45parallelisation, 60simple omposition of, 57pure state, 9QN, 31quantum intera tion, 15quantum network, 31(adaptive) adversarial, 35stati adversarial, 35time evolution, 32quantum systemintera tive, 14read-only, 9re eive operator, 14of an IQTM, 28relative polynomial running time, 21hard, 21reliable polynomial running time, 20reliable termination, 20restri tionof an ITM, 30running time, 18expe ted polynomial, 20(hard) relative polynomial, 21reliable polynomial, 20(stri t) polynomial, 19SAQN, 35s heduling, 35message driven, 35se urity, 43absolute, 43adaptive, 53adjustable, 52approximative, 43pliable, 51polynomial, 43stati , 53under polynomial running time, 43with bounded risk, 44with heat-dete tion, 50with partial abort, 51

se urity notion, 50send operator, 14of an IQTM, 27simple ompositionof ACF, 57of proto ols, 57simple omposition theorem, 58start on�gurationof an IAQS, 14of a QN, 32stati adversarial quantum network, 35stati instantiationof an ACF, 40stati se urity, 53statisti al distan e, 11sto hasti ally non-blo king adversary, 39sto hasti indistinguishability, 11exponential, 11with respe t to a set of bounds, 11stri t polynomial running time, 19stri t termination, 20string, 11empty, 12length of, 11string extra tion, 13string literals, 12stru tured append, 12stru tured on atenation, 12symbol, 11tape, 11tape ontent, 11empty, 11temporary assumption, 45on available primitives, 46on omputational power, 46on orruption, 46on known algorithms, 47termination, 20reliable, 20stri t, 20weak, 20time evolutionof a quantum network, 32time evolution operator, 14of an IQTM, 26tra ephase, 48transmission event, 31trusted party, 6Turing ma hineintera tive, 30partial intera tive, 30universal omposition, 62weak termination, 20well-formed76

B KEYWORD INDEXIQTM, 27well-formednesslo al ondition for IQTM, 28, 71of adversaries, 38of IQCTM, 30

77

C SYMBOL INDEXC Symbol Index� addition of symbols/strings/tapes 13�::: as se ure as 43��::: as se ure as with bounded risk 44# blank symbol 11�X density matrix operator for X 10# empty string 12# empty tape ontent 11Cm parallelisation of ACF C 60Mm parallelisation of IAQS M 59�m parallelisation of proto ol � 60Qbi=a produ t 9C(0) � C(1) simple omposition of ACF C(0) and C(1) 57 subtra tion of symbols/strings/tapes 13Y(t(1); t(2); : : :) interleaved tape ontents t(1); t(2); : : : 12N(a; b) stru tured append 121 identity 9AN orruption stru ture of AQN N 35AQN set of adversarial quantum networks 35C omplex numbers 9~C omputable omplex numbers ( ~C = ~R+ i ~R) 26Ci fun tionality i in ACF C 40C(M) making the IAQS M lassi al 24C(adaptive=stati ; E ;A;A; �) adaptive resp. stati instantiation of ACF C with environment E ,adversary A, orruption stru ture A and the proto ol � 41CI(M) making the interfa es of the IAQS M lassi al 24E� sequen es of events 31Ek;n;t auxiliary de�nition 18fC a ess stru ture of ACF C 40fN a ess stru ture of AQN N 35F (i; k) auxiliary de�nition 57H{ auxiliary de�nition 20HC ommuni ation tape spa e of M 14HF frame tape spa e of M 14HG;N global history tape spa e of N 32HH;M ma hine history tape spa e of M 32HQ;M on�guration spa e of M 14IAQS set of all IAQS 14ICTM set of all ICTM 29IF set of IDs of fun tionalities 35IP set of IDs of parties 35IQCTM set of all well-formed IQCTM 30ITM set of all well-formed intera tive Turing ma hines 30Kk auxiliary de�nition 18N natural numbers (N = f1; 2; 3; : : :g) 9N0 natural numbers in luding zero (N0 = f0; 1; 2; : : :g) 978

C SYMBOL INDEXOi transformations in a quantum intera tion (i 2 N) 15�P::: polynomially as se ure as 43P (i)k proje tions in a quantum intera tion (i 2 N,k 2 frun; send; re ;worldg) 15PF;M end on�guration proje tion of M 14PIAQS set of all PIAQS 20PIQTM set of all PIQTM 28PITM set of all polynomial well-formed intera tive Turing ma hines 30~R omputable real numbers 26R+ positive real numbers 9R real numbers 9~R�0 non-negative omputable real numbers ( ~R�0 = ~R \R�0) 26R�0 non-negative real numbers 9TXk;n running time of exe ution trans ript X in invo ation n withse urity parameter k 18u(n) string representation of n 2 Z 13UN time evolution of the quantum network N 32UM time evolution operator of M 14U opyif;M auxiliary de�nition 23U orr;M orruption operator of M 14UFS;M frame send operator of M 14UR;M re eive operator of M 14US;M send operator of M 14�fF1=%(1);:::;Fn=%(n)g simple omposition of proto ols 57%(ji) density matrix for ji (%(ji) = jihj) 9�� set of all strings 12� set of symbols 11�Z�n set of all tape ontents 11Æ(s1; s2; : : : ; sn) stru tured on atenation of strings s1; : : : ; sn 12K(t) string extra tion 13

79

D REFERENCESD Referen es[BV93℄ Ethan Bernstein and Umesh Vazirani. Quantum omplexity theory. In Pro eedings of the twenty-�fthannual ACM symposium on Theory of omputing, pages 11�20. ACM Press, 1993.[Can00a℄ Ran Canetti. Se urity and omposition of multiparty ryptographi proto ols. Journal of Cryptology:the journal of the International Asso iation for Cryptologi Resear h, 13(1):143�202, 2000.[Can00b℄ Ran Canetti. Universally omposable se urity: A new paradigm for ryptographi proto ols.http://eprint.ia r.org/2000/067 and ECCC TR 01-24. Extended abstra t appears in 42ndFOCS, 2000.[CGS02℄ Claude Crépeau, Daniel Gottesman, and Adam Smith. Se ure multi-party quantum omputation.In Pro eedings of the 34th ACM Symposium on Theory of Computing, pages 643�652. ACM Press,2002.[PW94℄ Birgit P�tzmann and Mi hael Waidner. A General Framework for Formal Notions of "Se ure"Systems, Hildesheimer Informatik-Beri hte 11/94. Te hni al report, Universität Hildesheim, 1994.Available at http://www.semper.org/sirene/publ/PfWa_94FormalItse IB.ps.gz.[Smi01℄ Adam Smith. Multi-party quantum omputation. Master's thesis, Department of Ele tri al Engi-neering and Computer S ien e, MIT, August 2001. Available as quant-ph/0111030.

80