量子安全协议中的进程代数和量子多项式时间机器

理论计算机科学电子笔记170（2007）3-21www.elsevier.com/locate/entcs量子安全P. 一天一天，3，4里斯本技术大学IST数学系逻辑与计算中心葡萄牙里斯本P. Mateus马特乌斯2，3，5里斯本技术大学IST数学系逻辑与计算中心葡萄牙里斯本摘要我们提出了一个进程代数的量子安全协议的指定和推理由于协议代理的计算能力必须限制在量子多项式时间，我们引入了类似于[4，6]的对数成本量子随机存取机（QRAM），并将其纳入代数的语法中。概率转移系统给出了进程代数的语义。术语减少是随机的，因为量子计算是概率性的，而且，我们考虑了一个统一的调度器来解决不确定性的选择。为了定义安全性质，我们引入了观测等价和量子计算不相容，并证明了后者是一个同余关系.这个结果的一个简单推论是，任何通过仿真定义的安全属性都是组合的。最后，我们通过建立量子零知识协议的概念来说明我们的方法关键词：量子过程代数，量子多项式时间机器，量子零知识证明。1 电子邮件地址：pad@math.ist.utl.pt2电子邮件：pmat@math.ist.utl.pt3部分得到联邦经济发展局/联邦贸易委员会QuantLog POCI/MAT/55796/2004项目的支助。4来自联邦现金信托基金赠款的额外支助SFRH/BD/8148/2002。5英国-葡萄牙联合研究方案的额外支助，《温莎条约》B22/05，2005-2006年。1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.12.0094P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）31引言安全协议通常由并行运行的多个代理组成，其中每个代理计算信息（由安全参数的多项式时间限制）并与其他代理交换信息。在量子过程的上下文中，计算由量子多项式时间限制，并且交换的信息由量子比特支持在本文中，定义量子安全特性的问题是使用量子多项式时间过程代数解决的。这种方法在[13，9]中受到了很大的启发我们用来定义量子多项式项的计算模型是基于对数成本随机存取机[4]。一个混合模型，使用经典和量子存储器，类似于[6]，但具有复杂性假设，被认为是（多项式时间）等价于一个统一的量子电路族（它们本身等价于量子图灵机）。这样的机器对每个代理的计算进行建模，接收量子位作为输入，并返回量子位作为输出。由于不可克隆定理，量子信息在没有其状态的先验知识的情况下无法复制。这一观察在进程代数中强加了一些设计选项，因为有必要知道哪个代理拥有量子位，以便知道谁可以检索每条信息。为了处理这个事实，一组代理被固定，量子比特在它们之间被划分。虽然其他几种量子过程代数的方法已经出现在文献中（例如，见[5]），但由于应用安全协议的广泛性，我们的方法是非常原始的。在我们的方法中，过程术语分为局部和全局。代理由局部进程建模，而协议由全局进程建模，因此，全局进程对应于并行运行的局部进程。提供了一种基于概率转移系统（可以很容易地转换为马尔可夫链）的语义，并且使用规则定义概率转移，并假设统一的调度器来解决不确定性选择。代理观察被定义为通过在计算基础上测量代理的量子位（其中一些）而获得的二进制字的概率分布该测量在方案运行结束时完成。这一概念是建立观测等价性的关键要素，在安全协议的背景下，观测等价性基于计算不变性[14]。直觉上，如果在对每个过程进行所有可能的约简之后，不可能区分（在量子多项式时间中）两个过程上的代理的量子位，则两个过程项对于代理是观测等价的由于我们在过程alge中内化了量子多项式时间机器P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）35Σ在语言中，观察等价很容易定义，它被证明是一个同余关系。定义安全并发密码任务的最成功的方法之一是通过进程仿真[1，2]。这个定义性的工作可以归结为：一个进程实现一个密码任务，当且仅当它模拟了一个理想的进程，该进程已知可以实现这样的任务。基于观测等价的概念，我们建立了量子过程演算的模拟概念最后，我们通过过程仿真提供了量子零知识的概念。在第2节中，进程代数与对数代价随机存取机一起介绍过程代数的语法和语义都被清楚地建立起来，并且通过提出观察等价的概念来结束这一部分第3节致力于仿真及其合成定理，最后，在第4节中，量子零知识是使用过程仿真定义的。2进程代数在安全协议的上下文中，通常考虑安全参数η∈N。在量子协议的情况下，我们也将考虑这样的参数，以约束当事人和对手的量子复杂性。从现在开始，符号η被保留以指定这样的安全参数。这个参数的作用是双重的：它将可以通过通道发送的量子比特数限制为η的多项式，并且它将所有计算限制为量子多项式时间（η）。我们现在详细介绍这些方面，并最终介绍进程代数语言。2.1量子多项式机我们采用的量子多项式机的计算模型是基于对数代价随机存取机[4]，它与[6]中的量子随机存取机非常相似我们考虑一个混合模型使用经典和量子存储器。为了处理量子比特qB的可数集，我们采用以下希尔伯特空间H（同构于l2（2qB）和L2（2qB， λ））来模拟量子态（参见[10，11]关于为什么H是用于模拟量子比特的可数集的正确希尔伯特空间的讨论）：• 每个元素都是一个映射|2 qB→C，使得：·s=0，p =0（|B={v∈2qB：|n= 0 {\displaystyle n=0};·||电子邮件（v）|2=||电子邮件（v）|2<∞;2019- 05 - 22 00：00：00（|（掌声）6P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）3• |2|ψ2⟩ = λv. |（v）;|ψ2⟩(v);z|λv= λv。 z|（v）;Σ• ⟨ψ1|2v∈V|2002年12月（五）。 |ψ2⟩(v).√内积诱导范数|||ψ⟩||=|因此，距离（飞机）|2001年，|2|||ψ1⟩ −|ψ2⟩||. 显然，|v∈ 2 qB}是标准正交基其中H |v = 1，且|v（vJ）= 0对于每个vJH的计算或逻辑基础。v. 这个基础被称为量子随机存取机（QRAM）的配置是三重n =（m，|其中m∈NN，|且s∈N。 三元组的第一个组成部分表示机器的经典存储器-自然数的无限序列，第二个组成部分表示机器的量子状态，最后第三个组成部分是一个计数器，指示允许多少（qu）位操作我们将正多项式q与每个QRAM相关联，用于将允许的（qu）位操作的数量限制到q（n）。通过这种方式，我们迫使每个QRAM在多项式时间内终止。 给定一组有限|m=（m 0，|ϕ⟩⊗ |ϕ⟩ ⊗|0是H中的单位向量，使得|0<$（n）= 1（注意，如果Q是一个2 n维希尔伯特空间，那么H和Q <$H之间存在一个典范同构，因此|ϕ⟩ ⊗ |0 <$∈ Q <$H可以看作是H中的单位向量）。|0⟩ ∈ Q⊗ H can be seen as a unit vector in H).QRAM接收量子位的有限序列作为输入，但由于总是可以将经典位编码为量子位，因此这不是限制。原子命令AC的集合及其相关联的成本在下面的表6中呈现。6.我们用下式表示自然数n所需的位数：|n|.·P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）37Number指令计算成本1Ri=n|n|2Ri=Rj|RJ|3Ri=Rj+Rk|+的|RK|Rk|4Ri=Rj−Rk|+的|RK|Rk|5Ri=RjRk|RJ| × |RK|6Ri=Rj/Rk|RJ| × |RK|7Ri=RRj|+的|R R j|RRj|8RRi=Rj|+的|RJ|Rj|9泡利十世[b]110PauliY[b]111PauliZ[b]112阿达玛[b]113阶段[b]114π[b]8115c-not[b1，b2]116测度[b] →Ri1上面的大多数命令都是不言自明的，但值得注意的是，除了measure之外，所有命令都是确定性的。事实上，根据量子力学的测量假设（例如，见[3]），当量子系统被测量时，结果是随机的，而且状态相应地演变为这个结果。注意，我们仅考虑在计算基上的测量，然而这不是限制，因为在测量在计算基上的量子位之前，可以通过应用幺正变换来执行任何其他量子位测量QRAM命令C的集合归纳地获得如下：(i) a∈ C，如果a∈ AC;(ii) 如果c1，c2∈ C，则c1，c2∈ C;(iii) （如果（Rn>0）则c）∈ C，如果c∈ C;(iv) （虽然 （Rn>0）c）∈ C，如果c∈ C.QRAM命令c的执行是配置之间的随机函数设n = NN× H ×N是所有配置的集合，而Prob finn（n）是（n，2 n）上所有概率测度的集合，使得只有有限个配置的集合具有不同于0的概率。 QRAM命令c的执行是映射运行c：n→ Prob fin（n），并且我们写[c] n →pnJ来表示P runc （ n ） （nJ） =p。QRAMcomm和s的执行可以使用以下规则来定义，这些规则非常直观：8P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）3我KJK我KJK我JKJK我JKJKJ[Ris≥ |n|=n] （m，|（g）（s）→ 1（mJ，|ψ⟩,s−|n|）（Ri= n），其中，对于所有k i，mJ（k）=m（k），且mJ（i）=n;s≥ |RJ|（R） =R），[Ri =Rj]（m，|（g）（s）→1（mJ，|ψ⟩,s − |RJ|）其中，对于所有k i，mJ（k）=m（k），并且mJ（i）=m（j）;s≥|RJ|+的|RK|（R=R + R），[R=R+ R]（m，|ψ⟩, s)→（mJ，|2016年08月05日@上午10时30分（|R|+的|R|））ijk其中，对于所有ki=i，mJ（k）=m（k），并且mJ（i）=m（j）+m（k）;s≥|RJ|+的|RK|（R=R - R），[R=R-R]（m，|ψ⟩, s) →（mJ，|2016年08月05日@上午10时30分（|R|+的|R|））ijk其中，对于所有ki=i，mJ（k）=m（k），并且mJ（i）= max（m（j）-m（k），0）;s≥|RJ| × |RK|（R） =R R），[R = R R R]（m，|ψ⟩, s)→（mJ，|2016年08月05日@上午10时30分（|R |× |R|））ijk其中，对于所有ki=i，mJ（k）=m（k），并且mJ（i）=m（j）m（k）;s≥|RJ| × |RK|（R） =R /R），[R = R/R]（m，|ψ⟩, s) →（mJ，|2016年08月05日@上午10时30分（|R |× |R|））ijk其中对于所有k=i和mJ（i）=[m（j）/m（k）]，remJ（k）=m（k）;s≥|RJ|+的|RRj|（R=R），[R = R] （m，|ψ⟩, s) → （mJ，|2016年08月05日@上午10时30分（|R|+的|R|))iRji Rj1j RjJ1J111我P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）39其中，对于所有k i，mJ（k）=mJ（k），并且mJ（i）=m（m（j））;s≥|Ri|+的|RJ|（R）=R），[R=R]（m，|m，s）→（mJ，|2016年08月05日@上 午 1 0 时30分（|R|+的|R|））RijRij1i j其中，对于所有的ki=m（i），mJ（k）=m（k），并且mJ（m（i））=m（j）;10P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）312其中量子位b取|0 π），m（i）= 0且m（j）= m（j）;28[保罗iXs≥1[b]]（m，|（g）（s）→ 1（m，|J⎡ ⎤0 1哪里|从以下公式中获得：|通过应用Pauli X运算符来实现10库比特湾类似的规则适用于以下单量子位运算符：阿利翁⎡ ⎤ ⎡ ⎤保利·Y0−i我 0100 万;0−1⎡ ⎤ ⎡ ⎤ ⎡ ⎤1 1 10Hadamard101Phaseπ;π 100万;1−10i0eiπ/4s≥1[c-not[b，b]] （m，|ψ⟩, s)→（m，|J哪里|从以下公式中获得：|通过应用control-not运算符进行编译⎡ ⎤⎢10 0 0⎥⎢ ⎥⎢010 0⎥⎢ ⎥⎢ ⎥⎢0 0 01⎥⎣ ⎦0 0 1 0量子比特b1和b2上;s≥1[measure [b] → Ri]（m，|（g）（m，s）→p（mJ，|JWhere|J|2.1.1.|均p0|ψ⟩|（P0是子块速度的预测器|ψ⟩ |JJ|JJs≥1[measure [b] → Ri]（m，|（g）（m，s）→p（mJ，|[b] →Ri= 1），Z1P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）311其中量子位b取|1 π），m（i）= 1且m（j）= m（j），对于所有jWhere|J|2.1.1.|P1|ψ⟩|（P1是子块速度的推动器|ψ⟩ |JJ|JJ一、12P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）3[c1]（m，|m，s）→p1（mJ，|[c2]（mJ，|p2（mjj，SJ）→p2（MJJ，|jj（c;c）;[c1;c2]（m，|（s）→p1×p2（mJJ，|（jjj）12m（n）> 0 s ≥ |Rn|[c]（m，|ψ⟩,s − |Rn|）→p（mJ，|[（if（Rn> 0）thenc）]（m，|m，s）→p[c]（mJ，|J（ifT）;m（n）= 0[（if（Rn> 0）then c）]（m，|S，s）→1（m，|ψ⟩, s)（如有的话）;m（n）> 0s≥ |Rn|[c;（while（Rn> 0）c）] （m，|ψ⟩,s−|Rn|）→p（mJ，|J[（while（Rn>0）c）] （m，|m，s）→p（mJ，|J（whileT）;m（n）= 0[（while（Rn> 0）c）]（m，|S，s）→1（m，|ψ⟩,s− |Rn|）（while）。观察到，QRAM命令的减少总是终止，因为每个计算由q（n）（qu）位步长限制。QRAM命令的执行可以被看作是量子自动机的一个字运行[8]，但是关于这个主题的详细讨论不在本摘要的范围内。QRAM的输出是一组量子位的量子态。该输出集由与机器相关联的另一个正多项式o确定。给定一个安全参数η，输出量子位的集合由前o（η）个量子位构成。定义2.1量子多项式机器是一个三元组M=（c，q，o），其中c是一个QRAM命令，q是一个正阶边界多项式，o是一个正输出多项式。我们用QPM表示所有这些三元组的集合。给定一个量子多项式机M和一个安全参数η，|是前o（η）个量子比特状态的概率分布，|其中，该分布由执行规则[c]（m0，|q，q（η））→p（mJ，|J因此，QRAM的计算是前o（η）个量子比特的状态空间上的概率分布。 它 是量子算法中的传统方法，P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）313计算结束时，为了获得经典的结果（见肖尔和格罗弗的算法）。然而，由于我们使用QRAM来计算可以通过量子信道发送的量子信息，因此我们不强加这种最终测量，因为通过量子信道发送叠加可能是可取的下面的结果断言QRAM模型等价于通常的量子电路计算模型（对这个结果的详细介绍不在本摘要的范围命题2.2对于任何一致的多项式量子电路族Q={Qη}η∈N，存在量子多项式机MQ，使得MQ计算与Q相同的随机函数。此外，对于任意的量子多项式机M，存在等价的一致多项式量子电路族QM={Qη}η∈N.证明（草图）：请注意，统一电路精确地使用被定义为QRAM的量子原子命令的门。电路的结构可以通过RAM命令c来模仿。由于这种构造必须是η的多项式，程序必须在多项式时间内终止，因此，有一个多项式q来限制步骤的数量，最终输出必须总是量子位的多项式集，因此我们能够构造一个等效的QRAM机器。另一方面，QRAM程序是统一族构造的实现，因为对于每个η，可以通过查看由执行命令生成的量子原子门的有限（不要忘记QRAM程序总是终止）执行的随机性不会带来问题，因为在测量之后放置的门可以由该测量的结果控制如果测量值为1给一个量子位，在这种情况下，门U被放置在某个量子位b处，那么电路应该通过放置一个由测量的量子位控制并以b为目标的控制-U门来构建。Q2.2进程代数如前所述，我们需要知道谁拥有一个量子比特，以便知道谁可以检索一些信息。为了处理这个事实，量子位被认为属于某个代理，因此，量子位qB的集合在所有代理之间被划分 为了使这更精确，可数集A ={a1，.，ak，. }的分划qB={qBai}ai∈A，且qBissuchtateachsetqBai 是一个可递归的表。注意，每个chqBai具有由y诱导的总序（带有底序），14P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）3递归枚举。这种总排序的目的是当代理a执行M时重新索引由QPMM访问的量子位。该系统的一个明显的必要条件是，代理a被限制在它自己的量子位qBa上进行计算，因此，当代理a执行量子多项式机器M时，这台机器必须只能访问qBa中的量子位（注意，如果a的量子位与其他量子位纠缠，那么当前者被修改时，后者也可以因此，例如，如果一个代理a执行一个由命令PauliX[b]组成的机器，并且如果qBa被γ递归枚举，那么有效执行的命令是PauliX[γ（b）]。同样的过程也适用于输入和输出量子位，所以当由a执行的机器输出第一个o（n）量子位时，机器实际上输出的是量子位{γ（o（1）），..，γ（o（η））}<$qBa<$qB.代理之间的通信是通过公共渠道实现的，允许交换量子比特。显然，这个过程是通过修改qB的划分来模拟的。允许代理内部的并行性也是方便的（即，代理可以由并行的几个进程构成），为此目的，引入允许代理本地进程之间通信的私有信道（不能被拦截） 为了使这个假设清楚，考虑量子信道的两个可数不相交集合，全局或公共信道的集合G ={g1，g2，.，gk，. }，并且本地或专用信道的集合L ={11，12，.，lk，. }。我们用C表示集合GL。 所有的全局通道都可以被对手读写，而局部通道对应于从一个代理到它自己的私有通信。安全参数的一个作用是限制信道的带宽因此，我们引入带宽映射bw：C→q，其中q是所有取正值的多项式的集合。给定安全参数的值η，信道c可以发送至多bw（c）（η）个量子比特。我们还考虑变量Var ={x1，x2，.，xk，. }，这是定义量子比特术语所必需的。量子比特项t要么是qB的有限子集，要么是变量x∈Var。最后，我们给出了过程语言，它是π-演算的一个片段. 记住，整个计算必须是关于η的量子多项式，因此我们不处理递归和迁移。首先，我们建立一个代理的语言，我们称之为本地过程语言。定义2.3局部过程L的语言归纳如下：(i) 0∈ L（终止）;(ii) c<$M（t）<$∈ L，其中M∈QPM，t是量子比特项，c∈C（输出）;(iii) c（x），Q∈ L，其中c∈C，x∈Var，Q∈ L（输入）;P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）315(iv) [M（t）= 0].Q，其中M∈QPM，t是量子比特项，并且Q∈ L（匹配）;(v) （第一季）|Q2）其中Q1，Q2∈ L（平行合成）;(vi) ！其中Q∈ L且q∈q（有界复制）。大多数（本地）过程术语都是直观的。输出项cM（qBJ）表示机器M的输出通过通道c发送，机器M接收有限组量子位qBJ作为输入。 输入项c（x）.Q表示将在c上接收一组量子位，并且在接收时，x取接收到的量子位的值。在固定安全参数η之后，我们可以通过评估每个进程来消除复制！qR作为R的q（η）个平行拷贝。因此，我们总是假设过程项没有重复。现在，如前所述，协议由一组并行运行的代理组成，因此全局语言（或协议语言）非常简单：定义2.4一组主体A上的全局过程G的语言归纳定义如下：(i) 0∈ G（全局终止）;(ii) 其中P∈G，a∈A不出现在P中，且Q∈ L（全球平行组合）。下面的示例使用进程语言来描述使用Shor算法的RSA密码分析例2.5[基于肖尔Alice是一个简单的进程A，它知道一些消息w，并输出wemodpq，其中e是Bob的公钥。这个虚拟过程可以表示为（a：A（w））：=（a：gwe mod pq）。Bob接收x并计算xdmodpq。这个过程可以通过以下过程来模拟：（b：B）：=（b：g（x）. （lxdmod pq）|l（y）. 0））。因此，RSA协议由过程（a：A（w））<$（b：B）给出。最后，我们可以写“攻击”的过程，伊芙。她分解pq，求emodφ（pq）的倒数（这样，她就可以找到d），并拦截爱丽丝（在信道g上）发送的消息。我们将此过程编写如下：（c：l1Shor（pq）|l1（y）.l2Inv（y，e）|g（x）.l2（z）. （l3xzmod pq）|l3（w）. 0））。16P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）3qB22.3语义为了定义局部进程的语义，我们需要引入局部配置的概念。 本地配置或代理配置是一个三倍（|其中，|其中，qB是可数递归可积集，Q∈ L。局部配置的第一个元素是协议的全局状态，第二个元素是代理拥有的量子位集，最后一个元素是局部过程项。局部进程的语义是一个概率转换系统，其中转换由规则定义。 我们使用（|01- 02 - 2008刘晓波（|Qb，Qb，QJ）来声明，在全局状态下，|然而，当代理a拥有量子位qBa时，局部过程Q被简化为QJ，全局状态被修改为|概率为p的同样值得注意的是，我们使用符号M（|01-02-03-02|QRM M的执行，对qB a进行操作（即，使用qB a的递归枚举来重新索引量子位的位置），并接收qB1作为输入，输出qB2并修改全局状态|埃克塞特|概率为p的对于本地进程的情况，集合qB1和qB2是不相关的，因为当应用本地通信（LCom规则）时，代理所拥有的量子位当我们提出全球规则时，它们的功能将很清楚。M（|01-02-03-02|J.J.，qB2） qB1，qB2，qBa|≤ bw（l）（η）（LCom）| ≤ bw(l)(η) (LCom)（|Q，qBa，l（x）.Q|（1）A（1）A（|J我们还引入术语M; Meas来表示在执行M之后在M的输出量子比特的计算基础上执行测量的机器。因此，匹配对应于对M的输出量子位执行测量并检查结果是否为0字。（M;Meas）（|01-02|B.2）|吉吉|qB2=|0⟩（|[1][2][3][4][5][6][7][8][9][10 |J（M;Meas）（|01-02|B.2）|吉吉|qB2/=|0⟩（|[1][2][3][4][5][6][7][8][9][10 |J（匹配T）（匹配）（|01- 02 - 2008刘晓波（|10、A、B、C、D、E |B.A.，qBa，P|Q）→p（|J|Q）（|01- 02 - 2008刘晓波（|10、Q1，Q2（|B.A.，qBa，P|Q）→p（|J.J.，qBa，P |QJ）（LLPar）（LRPar）P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）317qB2Ri我们继续介绍全球规则。一个全局配置是一个三元组（|qB，P），其中|qB ={qBa}a∈A是qB的一个划分，它由主体A的集合索引（其中每个qBa是可数的，且r. e.）且P∈ G.全局进程的语义由以下规则定义（|01- 02 - 2008刘晓波（|10、Q1，Q2（|（1）A（1）B（2）C（|J（LtoG）M（|01-02|J.J.，qB2）qB1，qB2，qBb|qB2| ≤体重（g）（η）（|ψ⟩, qB,(a: g (x).Q)ǁ(b: g⟨M (qB1)⟩))→p （|J（GCom）））当reqBJ={qBaJ}a∈A，qBaJ对于所有的c/=a，b.=qBa<$qB2，qBbJ =qBb\qB2，andndqBcJ=qBc（|10- 12 - 2013张国荣（|10-12 - 13 - 2000（|2019-01-22 00：00：00 00：00（|J（|2019 -05 -22 00：00：0000：00|2019-02-2200：02：02（|2019-01-22 00：00：00 00：00（|J（GLPar）（GRPar）。所有的规则都很容易掌握。唯一不平凡的规则是全局通信（GCom），它使量子比特从一个代理交换到另一个代理，因此需要调整量子比特分区。过程项约简是非确定性的，在某种意义上说，可以在某个步骤中选择几个不同的约简。为了能够进行定量分析，这种减少应该是概率性的。为了简单起见，我们假设一个统一的调度程序，即任何可能的约简的选择是在所有可能的非确定性约简上以统一的概率进行的我们不详细介绍调度器模型，但原则上，任何概率分布建模的QPM可以用来模拟调度器策略。最后，请注意，通过应用局部和全局规则，并假设一个统一的调度程序，可以定义多步减少→psuchthat（|10-11-1|n• （|01-02|2019- 02-22 01：02：02 01：02- 2201：02：02（|n= n，qBn，Pn）;• p=p1×p2×· ··×pn−1，其中Ri是p可能n非确定性的整数倍R1R2Rn−1选择（|i∈ {1，...，n− 1};• （|n，qBn，Pn）不能再减少。多步减少通过用另一概率1加权每个随机减少pi来考虑调度器选择，其中Ri是调度器选择。步骤i中可能的非确定性选择的数量。18P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）3r（η）r（η）2.4观察和观察等效性在协议结束时，允许每个代理a∈A测量qBa中的多项式（以η为单位）数量的量子比特以提取信息。我们总是可以假设这些量子比特是qBa的第一个，比如说，r（η）个量子比特，其中r是正多项式。因此，过程项P的多步约简导致了2r（η）上的概率分布，其中2r（η）是在计算基上测量时r（η）个量子比特的所有可能结果的集合（即，2r（η）是所有r（η）长的二进制字的集合2.6给定一个正多项式r和一个全局配置（|，qB，P），令（|（qB，P）={（|J|2019 -05 -2501：0 1 ：02（|n（p>0）}。我们将主体a的观测定义为概率测度族Oa={（2r（η），22r（η），Pra ）}R其中：一个r（η）η∈N• （1）A =A（|，qB，P）pγ×|埃夫|ψγ⟩|;• pγ是suc h，则（|（qB， P）→pγγ;• |ψγ⟩ is the first component of γ;• |ψ γ⟩ |是通过测量qB a的r（η）个第一量子位（代理a拥有的量子位）来观察r（η）长的二进制字w的概率，|is theprobability of observing the r (η)-long binary word w by measuring the r(η) first qubits of qBa(qubits in possession of agent a) of|ψγ⟩ in the computational basis.注意，用于计算Pr的求和为（{w}）定义得很好，因为（|qB，P）是有限的。在这一点上，很明显，对代理人的观察是一个随机的r（η）长的二进制字，其分布由Pra给出。我们采用的观测等价性概念是基于安全社区中常见的计算不确定性[13]。首先，我们介绍了语境的概念。全局上下文集C被归纳地定义如下：[ ]∈C;C[ ]<$P和P<$C[ ]∈ C，条件是C[ ]∈ C和P∈ G。给定一个上下文C[ ]和一个全局进程P，符号C[P]意味着我们用进程P替换C[]中的[]定义2.7设P和PJ为过程项。我们说，P是计算上不可区分的代理a从PJ，当且仅当对于每个上下文C [ ]，多项式q和r，|n∈ H，qB的划分qB，η极大P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）319r（η）r（η）r（η）2和二进制字w∈2r（η），a r（η）（w）−PrJa1（w）|≤q（η）其中Pra一个人的观察，是一个人的观察，是一个人的观察。|A，qB，C[P]）和PrJa一个人的观察，是一个人的观察，是一个人的观察。|[J]）。在这种情况下，我们写PPJ。如果两个过程无法通过上下文区分，即对于任何输入（此处由|在这种情况下，没有上下文可以区分所产生的输出，直到一个可以忽略的函数。上面的定义将计算不可分辨性的经典定义扩展到量子情况，因为过程可以用量子多项式机建模，因此C[]诱导出所需的区分机。这个结果的详细证明超出了这个扩展摘要的范围。为了建立组合性，以下结果至关重要：命题2.8计算不可约性是关于G的平行本原的同余关系。证据对称性和反射性都很容易检验。传递性遵循三角不等式，并考虑到1q（n）是多项式。全局并行运算符上的同余式如下：注意对于任何上下文C[ ]和CJ[ ]，CJ[C[ ]]也是上下文。Q3仿真与合成定理定义安全并发加密任务的最成功的方法之一是通过进程仿真[1，2]。这个定义性的工作可以归结为：一个进程实现一个密码任务，当且仅当它模仿一个已知的实现这个任务的理想进程在本节中，在定义安全功能的目标的指导下，我们详细介绍了上一节中定义的量子过程演算的仿真概念。设I是一个实现某个安全协议（的诚实部分）的理想协议，P是一个实现I指定的功能的进程。总体目标是表明P实现了I指定的（部分）安全功能。如果对于任何真正的对手，比如（a：A），过程P||（a：A）在计算上无法被对手a与过程I区分开||（a：B）对于某个理想对手（a：B），|Pr20P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）3P其中理想对手是不能破坏I的对手，而真实对手是代理A的任何局部过程。这个性质断言，给定一个真正的对手（a：A），代理a不能区分P泄露的信息||（a：A）从行为良好的进程泄漏的信息中，||（a：B），因此，我们推断P||（A：A）也很好。这个讨论引出了关于一组真实对手A和理想对手B的仿真概念。定义3.1设P和I是过程项，A和B是全局过程的集合，其中唯一的主体是对手a，则P关于A和B模仿I当且仅当对于所有过程（a：A）∈ A，存在过程（a：B）∈ B，使得P||（a：A）I||（a：B）。在这种情况下，我们写帕夏甲乙丙和B.I和说P是I关于A的安全实现仿真关系的理想性质是所谓的合成定理。这个结果在[12]中首先针对经典安全计算环境进行了非正式讨论，并陈述如下：如果P是理想协议的第I部分的安全实现，则R和J是使用理想协议I作为组件的两个协议，并且最终，R是安全实现J，然后是RI应该是J.此结果被捕获如下所示定理3.2设P，I是过程，R[]和J[]是上下文，A，B是主体a上的过程集，C，D是主体b上的过程集。如果R[I||（答：B）]C和 D J[I||（答： （A）任何（A） ： B）、 ∈ BPa甲乙丙我当时对于任何Badvertisement（a：A）∈ A存在（a：B）∈ B使得R [Q||（a：A）]C和 DJ [I||（a：B）]。证据 设（a：A）∈ A且（a ： B）、 ∈ B 这样，P||（一个 ： A）一||（a：B）。 现在选择一些（B：C）∈C，显然，R [Q||（答：A）]||（c：C）R [I||（a：B）]||（c：C）因为是一个同余关系。此外，由于R[I||（a：B）]||（a：B）]，存在a（b：D）∈ D使得R [I|（答：B）] |C J[I||（答： B）]||（b） D）的情况。最后，根据 、 我们有R [Q||（a：A）]||（b：C）J [I||（a：B）]||（b：D），因此R [Q||（a：A）]||（a：B）]。Q观察到理想协议由诚实的部分I和理想的对手（a：B）构成，因此具有形式I||（a：B）。 这就是为什么R [I]||（a：B）]而不是R [I]。此外，由R和J实现的功能的对手可能不同于I和Q的对手，因此，需要两对进程集合C、D和A、B来建模两种对手。P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）3214量子零知识证明交互式证明是一个两方协议，其中一个代理被称为证明者，另一个被称为验证者。协议的主要目标是让证明者说服验证者一个断言的有效性，然而，这必须以这样一种方式完成，即证明者不能说服验证者一些错误断言的有效性。任何交互式证明系统都满足两个性质：完备性和可靠性。完备性是指，如果证明者想要说服验证者的断言是真的，那么验证者应该以概率1被说服另一方面，如果检验者在极小的概率下不能确信一个错误的断言，那么可靠性就被满足了。因此，完整性和可靠性允许验证者检查证明者的断言是真还是假。零知识是证明者（策略）的属性。考虑下面的非正式概念（量子）计算零知识策略，它对应于直接提升到经典版本的量子设置定义4.1证明者策略S被称为集合L上的量子计算零知识，当且仅当对于每个量子多项式时间验证者策略V，存在量子多项式时间算法M，使得对于所有l∈L，（S，V）（l）在计算上与M（l）不可区分，其中（S，V）表示S和V之间相互作用的输出。密码设置中的零知识证明协议的主要应用是在具有秘密并且应该根据秘密执行一些步骤的用户U的上下文中问题是其他用户如何确保你已经执行了正确的步骤，而你没有透露它的秘密。零知识证明协议（ZKP）可以用来满足这些冲突的要求。零知识本质上体现了验证者在与证明者交互时不能获得比单独运行量子多项式时间程序（在两种情况下使用相同的输入）更多的知识。也就是说，与证明器并行运行验证器应该与某些量子多项式时间程序无法区分。实际上，（量子计算）零知识证明的概念可以很容易地通过仿真来捕获假设证明策略S（x）和验证者V（x）被建模为进程代数的项，实际上可以通过进程（p：S）来建模p和v之间的交互。||（v：V）。用Lv（l）表示验证器的所有过程项的集合22P. 阿当山口Mateus/Electronic Notes in Theoretical Computer Science 170（2007）3LLL（v：V）x，即任何过程项（v：V），其中自由变量x被二进制字l替换。我们有以下特征：命题4.2表示证明策略的过程项（p：S）L的推定零知识当且仅当（p：S）xvvv0，对于所有l ∈ L.LL（L），L（L）证明（草图）：注意，ZKP重新开始强制所有（v：V）x存在一个过程（v：VJ）x，使得（p：S）x|