没有合适的资源?快使用搜索试试~ 我知道了~
280理论计算机科学电子笔记45(2001)网址:http://www.elsevier.nl/locate/entcs/volume45.html31页用于密码协议分析的概率多项式时间演算(初步报告)J. Mitchell米切尔1,3,4计算机科学系,斯坦福大学,斯坦福,CA 94305美国A. Ramanathan1计算机科学系,斯坦福大学,斯坦福,CA 94305美国A. Scedrov1,2,5宾夕法尼亚大学数学系,费城PA 19104-6395 USAV. Teague提格1,6计算机科学系,斯坦福大学,斯坦福,CA 94305美国摘要我们描述了一个进程演算,已开发的目的是分析安全协议的性质。进程演算是π演算的一种限制形式,允许有界复制和概率多项式时间表达式在消息和布尔测试中使用。为了避免在不确定性的情况下表达安全性的问题,消息被概率地而不是不确定地调度。我们证明了评估可以在概率多项式时间内完成,并开发了一种形式的渐近协议等价的属性,该协议等价允许使用观察等价来指定安全性,这是一种来自编程语言理论的标准关系,涉及量化可能与协议交互的可能环境。我们还涉及过程等价的加密概念,如伪随机数生成器和多项式时间的统计测试。2001年由ElsevierScienceB. 诉 在CCBY-NC-ND许可下开放访问。米塔尔,RAMANATHAN,SCEDROV和 TEAGUE2811介绍采用多种方法对安全防护进行分析和推理。主要的系统或形式化方法包括专门的逻辑,如BAN逻辑[8,13],为加密协议分析设计的专用工具[20],定理证明[32,31]和使用[24,26,29,34,35]中描述的几种通用工具的模型检查方法。虽然这些方法在很大程度上不同,但它们都反映了关于对手可能与协议交互或尝试解密加密消息的方式的相同基本假设。在共同模式中,主要来自[12] 和[30]中的建议(参见,例如,[10]),允许协议对手在可能的行动中进行非确定性选择。这是一种方便的理想化,目的是给对手一个机会来找到攻击,如果有一个。然而,在存在非确定性的情况下,对手可能用来干扰协议的消息集必须受到严格限制。虽然Dolev-Yao式的假设使得协议分析变得容易处理,但是它们也使得“验证”实际上易受影响的协议成为可能到简单的攻击,这些攻击不属于对手模型。另一个限制是,确定性或非确定性设置不允许我们分析概率协议。在本文中,我们描述了安全协议分析中的一些一般概念,提到了一些竞争性的方法,并描述了在[23,22]中提出的过程演算的一些技术特性,该过程演算是一种形式化的协议分析形式的基础,但在基础上更接近现代密码学的数学设置。 该框架依赖于 一种用于定义通信多项式时间过程的语言[28]。我们将进程限制为概率多项式时间的原因是,我们可以通过量化语言中可定义的所有“对抗”进程来推断协议的安全性。因此,建立一个对手的运行时间的界限允许我们放松简化的假设。具体来说,可以考虑可能发送随机选择的消息或执行复杂(但概率多项式时间)计算的对手,以从其在网络上无意中听到的消息中获得攻击。我们的框架的一个重要方面是,我们可以分析概率以及确定性的加密功能和协议。如果没有概率框架,就不可能分析ElGamal[14]等加密函数,对于ElGamal[14],单个明文可能有多个1由DoD MURI“信息交换中的语义一致性”部分支持通过ONR Grant N 00014 -97-1-0505。2OSD/ONR CIP/SW URI通过ONR Grant N 00014 -01-1-0795提供的“分布式计算的软件质量和基础设施保护”的额外支持3来自DARPA合同N66001-00-C-8015的额外支持。4 来自NSF CCR-9629754的额外支持。5 来自NSF Grants CCR-9800785和CCR-0098096的额外支持。6由斯坦福大学研究生奖学金提供部分支助米塔尔,RAMANATHAN,SCEDROV和 TEAGUE282F × → F ×→密文这项工作的一些基本思想在[23]中概述,术语语言在[28]中提出,进一步的示例协议在[22]中考虑。最接近的技术先驱是Abadi和Gordon spi演算[3,2],它使用观测等价和信道抽象,但不涉及概率或计算复杂性界限;随后的相关工作在[1]中引用。CSP和安全协议的先前工作,例如,[34,35],也使用进程演算和安全规格的形式等价或相关的近似顺序的进程。虽然我们的主要长期目标是基于标准的密码学假设的协议分析,这个框架也可能揭示密码学的基本问题。特别是,用于协议的“安全”加密函数的特征似乎还没有完全解决。虽然[18]中语义安全的定义似乎已经被接受,但还有更强的概念,如不可延展性[11],更适合于协议分析。从某种意义上说,不同之处在于语义安全对于加密消息的单次传输是自然的,而不可延展性解释了可能在更复杂的协议中出现的漏洞。我们的框架提供了一个设置,用于从协议的安全属性向后导出必要的属性底层加密原语的信息虽然我们坦率地承认,需要做更多的工作,以产生一个系统的分析方法,我们认为,结合概率和复杂性限制的用于协议分析的基础设置在未来有很多改进2预赛2.1概率函数定义2.1我们定义集合X,Y上的概率函数F为满足以下条件的函数F:X×Y→[0,Σx∈X:y∈YF(x,y)≤1(1)对于某个x∈X,y∈Y,如果F(x,y)=p,我们说F在x具有概率p或F(x)=y具有概率p。2.2概率函数定义2.2我们定义了两个概率函数1:XY[0,1]和2:Y的合成F:X × Z →[0,1] Z [0,1]作为满足以下条件的概率函数:Σx∈X。F(x,z)=y∈YF1(x,y)·F2(y,z)(2)米塔尔,RAMANATHAN,SCEDROV和 TEAGUE283Σ F·≡我们把F1和F2的合成记为F2<$F1.引理2.3给定两个概率函数F1:X×Y→[0, 1]和F2:Y×Z→[0,1],则组合F2<$F1=F:X×<$Z→[0,1]是一个p-o-b功能,即,它满足条件<$x∈ X:z∈ZF(x,z)≤1。证据 对于任何固定的x∈X:ΣΣF(x,z)= ΣF1(x,y)·F2(y,z)由defn. 二、2z∈Zz∈Z y∈Y=1(x,y)y∈ YΣz∈ZF2(y,z)因子分解定义为1。 二、1因此,组合是一个概率函数。✷2.3术语在下文中,P表示过程,T表示项,p(x)表示有限个带宽多项式中的一个,使得na∈N:p(a)≥0。cp(x)表示与多项式p(x)相关联的信道名称的可数无穷大C q(x)中的一个,使得没有信道名称与多于一个多项式相关联有一个特殊的安全参数,n,可以出现在条款(第2.3.1节),作为复制操作符的参数(defn。2.13),作为带宽多项式的参数,并且在上下文(defn. 2.21)。对于每个n值,带宽多项式给出了可以在该信道上传输的最大比特数3.3)。双位关系代表句法同一性。 我们表示变量 最后,函数γ(x)是一个多项式,使得γa∈N:γ(a)≥0。定义2.4[6]一台Oracle图灵机是一台带有额外的Oracle磁带和三个额外状态qquery,qyes和qno的图灵机。当机器进入状态q时,如果oracle磁带上的内容在oracle集中,则查询控制传递到状态qyes;否则,控制传递到状态qno。给定一个Oracle图灵机M,我们将写M(x,x)来指定M在输入x上的行为。我们只考虑二进制神谕。另一种说法是,二进制oracle确定了一个集合X,因为我们可以将X写成{x|{x(x)}。因此,对x的查询是一个二元结果,表示如果x∈Xx。定义2.5如果存在多项式q使得对于所有预言机M,M(x,x)在时间q停止,则预言机图灵机M在预言机多项式时间内运行(|X|)其中x =x1,.,x m和|X|为|X1|,...,|.|.米塔尔,RAMANATHAN,SCEDROV和 TEAGUE284Fe1K为了查询oracle,M必须在oracle磁带上写入它想要查询oracle的数字。如果M在oracle多项式时间内运行,则M(x)查询最多具有q的oracle集合(|X|)位。定义2.6设M是多时间预言图灵机。 我们可以把M看作是一个概率多时间图灵机,如果我们从M的时间范围内可以查询的神谕空间中随机选择一个神谕。更准确地说,设M是一台运行在多项式q所限定的时间内的预言机。由于M(x)只能查询最多为q(x)位的oracle,我们有一个有限的神谕空间,它们在以q为界的时间内运行。称此空间为Q. 然后,我们可以把M看作是一个概率多时间图灵机,其中我们说M(x)=y的概率为p,如果从q中均匀随机地选择一个预言机,M(x,n)=y的概率为p。给定一个多时间概率图灵机M,我们将写M(x)来使用随机选择的oracle指定M在输入x上的行为定义2.7一个概率多时间图灵机M计算一个概率函数F,如果对于所有输入x和所有输出y,我们有,F(x,y)= ProbM(x)=y.定义2.8概率函数是多时间的,如果它是由概率多时间图灵机计算的。2.3.1方面在[28]中研究了基于[19,7]的函数项演算和该演算的语义。虽然我们在这里省略了细节,但我们确实注意到,terms可以包含安全参数n以及返回一个随机位的函数rand对于每一个变量为x1,.的项T, x k,存在k + 1个输入的概率多时间图灵机M T和多项式q T(v1,...,vk+1),使得以下两个定理成立:定理2.9[28]设T是k个变量的项,M T是与T相关联的机器。 则M T(a1,...,100-10|的1|,..., |一个k|、|n|)的。定理2.10 [28]对于每个概率多时间函数f,存在一个项T使得M T计算f。虽然可能有许多图灵机分配给满足上述两个定理的项,但就我们的目的而言,分配的确切性质事实上,我们将简单地考虑概率多时间图灵机MT来定义术语T的含义。定义2.11我们在输入x,.上写T−→r a, xi如果有可能M T(x1,...,x k,n)= a是r。 我们说T以概率r求值为a。定义2.12我们在这里定义了两个概率:(1)两个项求值为相同数的概率,(2)两个项求值为不同数的概率。米塔尔,RAMANATHAN,SCEDROV和 TEAGUE285S1S2S1S2| |122112e2Σ Σ(i) 概率=T1、T2Σ=as1s2,其中a∈N, T−→a,T−→1ea和中国大陆2e(ii) Prob/=T1,T2=一个一个二个一个二,其中a,a∈N,af=a,T−→a, T−→a。2.3.2过程定义2.13进程的语法由以下文法给出P::=0(终止)v cp(|n|)的。(P)(私人频道)c p(|n|)(x)。(P)(输入)c p(|n|(输出)[T = T]。(P)(match)(P|P)(平行组合)!(|n|)的。(2)(3)(|n|)-折叠复制)私有通道上的每个输入或输出都必须出现在一个v-操作符绑定该通道。否则,表达式被认为是不可计算的。再说说频道名称。与通道c相关联的多项式p(n)是c上的带宽参数-更多详细信息,请参见3.3.此外,如第2.3节所述,没有通道名称与一个以上的多项式相关联。为了简单起见,在固定n之后,当我们评估一个进程P时,我们将P的所有子表达式s替换为m!(|n|).R与γ(|n|)并行的R副本。快点,我们确定!(|n|).Rtobeeleftass ociati ve. 最后,我们声明所有的通道名和变量名都被α-重命名分开。最后,在下面的内容中,如果表达式的解析树是明确的,我们将倾向于省略括号。定义2.14定义一个输入表达式 作为一种形式c p(|n|)(x).P,输出表达式的形式为c p(|n|)定义2.15我们称一个没有自由变量的过程表达式为封闭的过程表达式定义2.16设P是过程表达式,T是项。 如果T不在任何输入运算符的作用域中,我们说T是一个暴露项。类似地,设[T1=T2].R是P的子表达式。如果[T1=T2]. R不出现在任何输入运算符的作用域中,我们就说它是一个暴露的匹配1e米塔尔,RAMANATHAN,SCEDROV和 TEAGUE286||·定义2.17我们定义指标函数Eq?0(P)作为进程上的一元函数,当其输入为0进程时,其值为1,否则:情商?0(Q) 为 如果Q/N =0,则为0,如果Q≥ 0,则为1。定义2.18outerEval是封闭过程表达式和封闭过程表达式上的概率函数,其中所有暴露项被简化为原子并且没有暴露匹配:OuterEval(0,0)= 1外部评估(νcP(|n|).(P),νcP(|n|). (PJ))=s110、C ++(|n|)(x)。C = 0,C = 0(|n|)(x)。(Q))= 110、C ++(|n|)T,c p(|n|)a)=s2out erEva l([T1=ΔT2]. (Q1),Q2)=s3·Prob=T1,T2+ Eq?0(Q2)·Pro b=/T1,T2否则,out erEval((P1 P2),(P1J P2J))=s4s5outerEval(P,Q)= 0。其中,outerEval(P,PJ)=s1,a∈N, T−s→2a,eouterEval( Q1, Q2)=s3,outerEval ( P1 ,P1J ) =s4 , outerEval(P2,P2 J)=s5如果outerEval(P,PJ)=s,则我们说P外求值为PJ,概率为能力ys,或P−→sPJ。O在定义outerEval时的匹配情况需要进行一些讨论。考虑匹配[T1=T2].我们希望计算P外求值到PJ的概率.这里有两种不同的情况(i) PJ/m0,并且,(ii) PJ0.00。在第一种情况下,如果匹配成功,我们将只对P进行外求值,即,T1=T2。然而,在第二种情况下,我们可以通过传递匹配并将P外求值为0,或者简单地通过匹配失败来达到0。因此,外评估到PJ的概率由通过匹配的概率和外评估P到PJ的概率的乘积的和给出,并且在我们希望外评估到0的情况下,匹配失败-因此在和的第二项中使用指示符函数然而,我们必须确定,我们在这个表达式中没有过度计数。从情形i和ii的定义中,我们可以看到PJ永远不可能同时满足这两种情形,因此情形i和ii是不相交的。我们在情况ii中不过度计数,因为s超过了我们在情况ii中定义的两个和的估计(one从概率=T1,T2项和一个从概率T1,T2项)是米塔尔,RAMANATHAN,SCEDROV和 TEAGUE287t1OOO不相交引理a2.19LetP,Q和R是满足P-s-1->→0的概率表达式Q和Q−s−2−>→0R。那么,Q有一个与原子相关的指数项,暴露匹配,Q=R,且s2= 1。证据 通过对 P.我们给出一个证明的草图。10 - 1|n|)T,很容易看到。如果P = p,则P = p(|n|)的。(1)Q = 0,|n|)的。(J)其中PJ−s→1QJ。通过归纳定理,我们得到了QJ-→1QJ,O如下 如果P&PP(|n|)(x).PJ我们注意到P−→Q和The结果如下。 在P∈[T1=T2].PJ的情况下,我们有两种情况。如果两T1和T2等于相同的数,则Q<$QJ,其中PJ−→oQJ。通过归纳定理QJ−→1QJ,结果如下。在To1和T2分别取不同的数,我们可以看出Q≥0,很容易跟随。 如果P = 1,|归纳假设告诉我们是PSJ11−→oQ1−→o 年q1 和Psj22−→oQ2−→o Q2 结果如下。✷因此,在两个outerEval的合成中,只有第一个outerEval做任何工作。具体来说,它将所有暴露的术语转换为原子,并消除所有暴露的匹配项。花冠y2.20LetP和Q是随机的,并让−→o,m代表m-重−→的位置。IfP−s−>→0Q,则Q−→1o,mQ。证据 直接从引理2.19开始。✷定义2.21设Γ是由下列文法生成的表达式的集合:其中i∈N。C[ ]::= []iv cp(|n|)的。(C[])cp(|n|)(x)。(C[])P[T = T]。(C[])(C) ]的一种|C [])!(|n|)的。(C[])上下文是一个过程表达式,它是Γ的一个成员,其给定上下文C [ ]和进程P1,...,Pm,记法C [P1,...,P m]意味着我们用过程P i代替C [ ]中的洞[ ] i。111OO米塔尔,RAMANATHAN,SCEDROV和 TEAGUE288中文(简体)⟨ ⟩最后,我们将通过为上下文中的每个孔放置一个空方括号(通常没有编号)来指示孔的数量。例如,C[]将是一个单孔上下文,而D[]有三个孔。定义2.22我们说B是A的子过程,如果存在上下文C [ ]使得C [B] A。如果C[ ][ ],我们就说B是A的严格子过程。2.2.3设P和Q为过程表达式,c p(|n|)是一个渠道。我们认为,P是由Cp约束的(|n|)inQifcp(|n|)(x)。D[P]是Q对于某个变量x和某个上下文表达式D [ ]的子过程。定义2.24设C[ ]是一个上下文,P是一个过程。 然后,C[ ]对于P是最小的,如果P的每个自由变量在C[P]中有界,并且每个通道 在C[P]中,P与之结合的是P的自由变量。定义2.25外求值过程P的可分解过程集S(P)归纳定义为:S(0)=0S(v cp)(|n|)的。(1 )A(1)A(2)B(3)C(|n|)(x)。(1)A =(|n|)(x)。(2)C(|n|)T)={c p(|n|)T}S((Q1|Q2))= S(Q1)<$S(Q2)注意,S(P)中的每个进程要么等待输入,要么准备输出。定义2.26通信三元组的集合C(P)被定义为:{P1,P2,Q P1,P2 [ ] |01-02 |n|)a,P2c p(|n|)(x).R,Pi∈S(P),PQP1,P2[P1,P2]}给定一个过程P和一个上下文Q,P1,P2[ ],P1和P2是唯一确定的.例2.27考虑进程表达式:C=C(|n|)100元|cp(|n|)100元|cp(|n|)(x).dq(|n|)2011年1月函数表达式c p(|n|)(x).d q(|n|)1可以从两个输出表达式中的任何一个接收其输入。虽然这两种通信看起来相同,但它们的输出来自P中的不同位置。 我们通过关联上下文来区分这两种通信[ ] 1|c p(|n|)100元|[2]与米塔尔,RAMANATHAN,SCEDROV和 TEAGUE289⟨⟩||第一次通信(输出"来自“并行组合中的第一个进程)并将上下文c p(|n|)0 [ ] 1[]2与第二个通信(输出“来自”并行组合中的第二个进程的对所以,C(P)是集合:、0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 |n|)0,c p(|n|)(x).d q(|n|)1,[] 1|c p(|n|)100元|[] 2分,,0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 |n|)0,c p(|n|)(x).d q(|n|)2011年10月21日,|n|)100元|的 ]一个|[] 2个定义2.28合格过程集合E(P)定义为:C(P)i表示E(P)=C(P)是公共的,C(P)|私人频道,否则。注意,在C(P)包含私有信道的任何时候将E(P)限制为仅私有信道确保了所有私有通信在公共通信之前发生。这使我们能够通过使私人通信具有特权来3评价3.1减少定义3.1我们写[a/x]P表示我们将替换操作定义如下:[a/x]0=02019 - 05 - 22 00:00:00 00:00 |n|)的。(1)A= A(|n|)的。([a/x]Q)[a/x]cp(|n|)(y)。(2)C=C(|n|)(y)。([a/x]Q)[a/x] c p(|n|)(x)。(2)C = C(|n|)(x)。(2)[1] x = 0(|n|)T=c p(|n|)(λx.T)a[a/x][T1= T2]。(Q)=[(λx.T1)a =(λx.T2)a]. ([a/x]Q)米塔尔,RAMANATHAN,SCEDROV和 TEAGUE290[a/x](P1|P2)=([a/x] P1|[a/x]P2)[a/x]!(|n|)的。(Q)=!(|n|)的。([a/x]Q)我们可以将替换操作推广到上下文,即, 以替代a对于C[]中x的所有自由出现定义3.2我们将调度器S定义为从通信三元组集合到通信三元组的概率函数,使得对于每个通信三元组集合E,如果S(E,e)>0则e∈E。如果S(E,e)=r,则米塔尔,RAMANATHAN,SCEDROV和 TEAGUE291S| || |假设调度器S以概率r从集合E中挑选通信三元组e。定义3.3设a为自然数,n为安全参数的值,S为调度器。我们将说P在一个通信步骤中关于S以概率r减少到Pj,当且仅当:P1,P2,QP1,P2[ ]n ∈E(P):S(E(P),e)=r,01 - 02|n|)a,2019 - 02- 0100:00:00|n|)(x).P2J,10- 12 -1|n|)-1。我们把它写成sP−→rPJ。2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.2.n)-1,以确保最多只有||P(|n|)发送a的最小有效位。通过规定最多可以传输p(n)比特的消息,我们确保了我们不能从多项式时间过程表达式中创建指数时间过程-如果我们允许传输任意长度的消息,我们就可以做到这一点。考虑流程表达式:P!(|n|).cp(|n|)(x).cp(|n|)10x2|cp(|n|)2002年设多项式γ(x)总是返回x虽然更复杂的多项式会使结果更引人注目,但γ的选择简化了问题。很明显,P将平方其输入(这里初始化为2)n次。我们将这个过程的输出称为Pn。下表显示了n的几个不同值的输出:nP n| P n|14= 222= 21216= 244= 223256= 288= 23465,536 =21616=245 4, 294, 967, 296= 232 32=25...显然,P输出n中长度指数的值。现在,如果P的输出被用作某个多时间过程表达式Q的输入,那么我们将得到一个指数时间过程,因为Q必须在指数长的值上运行米塔尔,RAMANATHAN,SCEDROV和 TEAGUE292p1pm11−→1,S·· ·−−→1,Sm−1然而,如果我们截断传输的消息,那么任何消息都不会太长,即,指数级增长3.2评价3.2.1宏步长缩减直观地,我们基于以下三阶段过程定义P到PJ的宏步缩减(i) 我们外求值P,得到R。(ii) 调度程序从E(R)中挑选一个进程三元组E,并执行所选择的通信。这导致过程表达式RJ。(iii) 最后,我们外求值RJ,得到PJ。因此,宏步减少仅仅是一个过程的简写,通过该过程,我们选择要执行的通信并评估结果,直到有必要选择下一个通信。第一个外求值只是确保我们执行通信步骤的过程表达式满足defn中指定的S(P)条件。2.25.除了第一次外求值,过程表达式的求值就变成了一系列交替的过程求值(外求值)和通信步骤。我们将定义宏观步骤缩减,使其只是一个沟通步骤,然后是一个过程评估--由于上述原因,在此之前是一个过程评估。定义3.4更准确地说,相对于调度器的S是概率函数,由组合定义:−→o(−→S−→o)(3a)从P到PJ的宏步简化的概率r直接从定义2.2获得:Σr=abc(3b)a B CQ,QJ|P−→oQ−→SQJ−→oPJ我们将相对于调度程序将P的宏步长减少到PJS的概率yr为P−→r1,SPJ。3.2.2m-步减少定义3.5设P和PJ是两个过程表达式。将集合路径P,PJ定义为:{{Q,...,Q}|P−→Qp2pm−1Q−→PJ}我们称路径P,Pj为从P到Pj的路径的集合。m−11,S1,S米塔尔,RAMANATHAN,SCEDROV和 TEAGUE293m,S| |定义3.6P相对于调度器S在m步中减少到PJ的概率由下式给出:Σ{Q1,··· ,Qm−1}∈PathsP,PJp1p2···pmp1p2pm−1pJMP−→1,SQ1−→1,S···−−→1,SQm−1−→1,S P我们把P到PJ的m步约化记为P−→r,PJ。3.2.3评价定义3.7如果使用调度器S,P通过一定数量的宏步骤减少到Q,则我们说P相对于调度器S评估。我们将P到PJ的求值相对于调度器S写为P。→SPJ.4多项式时间求值界我们对最坏情况下的评估时间感兴趣由于特定降低的概率与最差情况下的评价时间无关,因此我们无需在分析中考虑各种降低的概率我们的求值边界将被推导为三个边界的某种组合:任何求值序列长度的边界,任何外求值步骤的边界,以及任何通信步骤的边界4.1任意求值序列长度的一个界定义4.1设P是一个过程表达式。我们定义输入(P),P中的输入数,归纳如下:输入(0)= 010、C++(|n|)的。(1)输入(Q)=输入(Q)|n|)(x)。(1)A = A + B + C + C + D+ C + D + D + C + D +D|n|)T)=0输入([T1= T2]. (Q))=输入(Q)输入((Q1|Q2)) =输入(Q1)+输入(Q2)inputs(!(|n|)的。(1)A(|n|输入(Q)从定义中可以清楚地看出,输入(P)是n中的多项式,对于所有输入值都是正的。定义4.2设P是一个过程表达式。 我们定义输出(P),米塔尔,RAMANATHAN,SCEDROV和 TEAGUE294| |LL·LP中的输出数量,归纳如下:0 =|n|)的。(Q))=输出(Q)输出(c p)(|n|)(x)。(Q))=输出(Q)输出(c p)(|n|)T)= 1个输出([T1= T2]。(Q))=输出(Q)输出((第一季度|Q2)) =输出(Q1)+输出(Q2)outputs(!(|n|)的。(1)A(|n|·输出(Q)从定义中可以清楚地看出,输出(P)是n中的多项式,对于所有输入值都是正的。下面的引理很简单。引理4.3设P是一个闭过程。然后,对于所有的n和S,在P的任何评估期间,至多发生输入(P)通信步骤。推论4.4设P是一个闭过程。然后,对于所有的n和S,在P的任何评估期间,至多输入(P)宏步骤发生。4.2外求值时间定义4.5我们有一个自然数T,T的长度,与每一项T相关联。如果T是一个项,则LT是一个常数与T,即,T= c length(T)其中c是常数。 的更多细节T可以 在引理4.10的证明中可以找到定义4.6设P为进程表达式,n为安全参数的值。我们定义一个多项式normlength(P),P的长度,归纳如下:10)numerical()numerical(|n|)的。(2)C++ C++C + C ++ C +C++ C + C++ C+|n|)(x)。(Q))=c+normlength(Q)100- 100 - 100(|n|)T)=c + LTnormlength([T1= T2]. (Q))= c + LT1 + LT2 + normlength(Q)normlength((Q1|Q2))= c + normlength(Q1)+normlength(Q2)normlength(!(|n|)的。(1)A(|n|)·c·normlength(Q)米塔尔,RAMANATHAN,SCEDROV和 TEAGUE295| |···| | −| |· ·||| |其中c是常数,LT是项T的长度。由于项的长度不取决于n(即,对于我们的目的,它是一个常数),从定义中可以清楚地看出,范数长度(P)是多项式,|n|.此外,normlength(P)对所有n都是正的。定义4.7设P是某个过程。设p是出现在P中的带宽多项式的集合。注意,p是有限的(多项式,|n|大)设置。对于每个i∈N,设a是p中每个多项式的xi项的系数的集合.注意a是有限的,因为p是有限的。对于每个i∈N,我们定义项ai为a中的最大项。因为a是有限的,所以最大的”“善有善报,恶有恶报。然后,我们定义多项式χ(x)为注意,n(x)∈p:x(b)≥p(b).∞i=0aixi.设P是一个过程,x(x)定义为defn。4.7.我们现在指定一台图灵机,它将填充P。图灵机首先重写P中的每个变量x,使其在输入磁带上占用χ(n它通过在变量前插入χ(n)1个空白符号来实现,这样x就变成了字符串o ox。 由于P的长度是一个大小为n的多项式,所以最多有一个大小为n的多项式变量,每个变量都有一个大小为n的多项式,在它之前插入n个空白符号。因此,很容易看出,填充P的变量可以通过图灵机在最多n个步骤的大小的多项式中这种填充的作用是确保可以在不增加填充进程P的长度的情况下替换x的值(因为x(n)超过任何带宽多项式的大小,并且因为我们在替换变量的值时最多只需要在P的求值期间,最多可以有输入(P)通信步骤(引理4.3)。设T是P中的任意项。 在P的评估期间的每个通信步骤可以将T隐藏在一个λ-抽象级别之后;在评估结束时,在最坏的情况下,T将隐藏在输入(P)λ-抽象之后。由单个λ-抽象引起的项T的长度的增加是一个常数-T变成(λx.T)a。加到T上的符号是“λ”、“x”、“。’, ‘(’, ‘)’ and ‘因此,如果我们在P中的每个项之前添加inputs(P)c x(n)空格,则我们将在每个项周围具有足够的空间,以确保我们可以考虑由于在通信步骤期间创建λ同样,该填充可以在时间量为n的多项式中完成,因为存在至多n个项和输入(P)大小的多项式是n大小的多项式。因此,填充P可以通过图灵机以n定义4.8设P是一个过程表达式,n是米塔尔,RAMANATHAN,SCEDROV和 TEAGUE296| |≤安全参数 我们定义一个多项式长度(P),P,归纳如下:长度(0)=10、C++(|n|)的。(1)A= A + B(|n|)(x)。(2)C ++(|n|)+length(Q)length(c p)(|n|)T)=c1+ LT+输入(P)·c2·χ(|n|)长度([T1= T2]. (1)(1)(2)(3)(4)(3)(4)(4)(5)(|n|))2)2)3)4)5)6)7)7)8)9)10)10)11)11)12)11)12)12)13)14)15)16)19)110)111)112)112)113)1114)1115)1116)11116)11117)11119)11119)111119)111119)111119)111111119)111111119)1111111119)111111119)1111111119)11111111119)11111111191111111119 111111119 11111119 1111111111n))+长度(Q)||长度((Q1|Q2))= c+长度(Q1)+长度(Q2)length(!(|n|)的。(1)A(|n|)·c·长度(Q)其中c、c1、c2、d1、d2、e1、e2是常数,LT是项T的长度。由于项的长度不取决于n(即,对于我们的目的,它是一个常数),从定义中可以清楚地看出,长度(P)是多项式,|.|. 此外,长度(P)对所有n都是正的。考虑到第15页关于填充的讨论,长度(P)的构造背后的原理应该是清楚的。本质上,出于技术原因,我们假设变量的长度为χ(n)(参见引理4.10,其中χ(x)是一个多项式,在任何地方都大于P中出现的任何带宽多项式。这允许我们用值替换变量,而不需要到处推此外,每个项为通信步骤创建的λ-抽象留下足够的空白空间(回想一下,在大多数输入(P)中,这样的通信步骤可以在评估期间发生)。在下文中,我们将通过短语“P的长度“来表示让我们观察到,长度不会由于宏步骤而增加。引理4.9设P是一个闭过程,R是一个过程,使得R是在P上执行一些宏步骤的结果。我们现在表明,任何外部评估步骤可以在概率多项式时间图灵机上进行。我们依赖于2.3.1节中讨论的概率多项式时间图灵机MT到项T引理4.10设T1,.,Tm是项,设MT1,.,MTm是它们关联的概率多项式时米塔尔,RAMANATHAN,SCEDROV和 TEAGUE297间图灵机。设P是一个封闭的亲-米塔尔,RAMANATHAN,SCEDROV和 TEAGUE298| || |IJ≡···iJiiJ1r含有项(λx1···λ xr. Tj)a1···ar的cess,其中1 ≤j≤m. 从 M T1,...,我们可以构造一个概率图灵机,它在时间多项式中对P进行外求值,|n|.证据让我们做以下两个假设。首先,我们假设变量的长度为χ(n)。这确保了当我们用一个值(回想一下,由于通信步骤中的截断,值的长度受到适当带宽多项式的限制)替换变量时,很容易用该值替换变量,即,我们不需要将其次,我们假设当我们计算一个项时,我们只写下结果值的χ(n)最小有效位。原则上,我们允许写下任意大的值,只有在通信过程中,这些值才会被截断。然而,这意味着当项评估我们正在处理的过程表达式时,其大小可能会任意增加。由于只有在我们传递值时才会使用由术语求值创建的值,因此在创建时截断值不会改变任何内容。在匹配中确实使用了由项求值生成的值,但是我们并不写下这些值;我们只是写下0或对绑定到匹配的流程表达式进行外求值的结果。这两个假设的结果是,每个外部评估要么不改变过程的长度,要么减少过程的长度(通过将输入和输出替换为0并评估匹配)。如果我们在对P进行外求值之前填充它,我们就可以保证这些约束。此外,正如我们所看到的,填充可以在大小为n的时间量的多项式中完成。现在我们将构造所需的概率图灵机pTM。本质上,pTM必须评估P中的每个暴露项和每个暴露匹配(很容易确定项或匹配是否暴露-每次输入运算符,比如c p(|n|)(x).P,我们考虑每个子表达式P不暴露)。 因为我们知道P只包含是来自集合{T1,...,T m},我们可以将来自P的每个项U i与算法M T相关联,其中T J是U i是其替换实例的项。通过定理2.9,我们有MT在多项式时间内计算TiJ在某个输入上的值由于Ui是TiJ的替换实例,我们有Ui<$(λx1···λxr.TiJ)a1···ar。因此,我们可以通过在a,...,a和n。因此,我们定义pTM,以便当它遇到这m个项中的一个项的替换实例时,它调用适当的算法(在它遇到U i(λx1λx i.T iJ)a1.的情况下)。a i,它调用M TiJ 在1,...,a1和n)。 回想一下,每个通信步骤创建项的λ-替换实例,即, 将值替换为项延迟到项-米塔尔,RAMANATHAN,SCEDROV和 TEAGUE299||| |||·评估时间。因此,我们的pTM通过在替换实例指定的值处评估相关算法来评估它遇到的每个暴露项。计算一
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功