《新的承诺方案设计及应用》由会员分享，可在线阅读，更多相关《新的承诺方案设计及应用（57页珍藏版）》请在金锄头文库上搜索。
1、上海交通大学 硕士学位论文 新的承诺方案设计及应用 姓名：张宗洋 申请学位级别：硕士 专业：计算机软件与理论 指导教师：董晓蕾 20080101 #YO9A ? Y5 ka5 q-+=C?pY S5yY=Y5#61J#N ?3uyG eD4=A =D4L RmO3m$1r)Lxre . U?uniform =Vm( m5LSnon-uniform 5L Vm ?kadvice 3n eadvicel(n)l : N Nm?E 2.1 (?): : N R ?XJ? p()3g,N?n N (n) 1 p(n) 6 1 Vg ?Vg?prNe ?Cu3=?q ?Xf : N R?nf(n) =
2、1 2n?n f(n) = 1w,f =v?v? XJ3g?,u)V(n)KE d? 1 (n) gwTu) ?$1g =?XJu)V?KmA?wu) y (witness):R0,1 0,1 ? X LR def = x|ys.t.(x,y) RXJx LR y iGv(x,y) R Ky ux LRywitnessRx= y|(x,y) RbT : N N L Ntime(T(n)XJ3XR L = LR (M3(x,y)eM $1T(|x|)1X J(x,y) RK0 2.2 (Vq): I 8dIqdIC 8X = XiiIdIqXiC e5O5,?Vg 2.3 (O): VqX de
3、f = XnnNY def = YnnNO XJu?VmD?p()9 kn | Pr D(Xn,1n) = 1 Pr D(Yn,1n)| 1 p(n) PX = XnnNCY = YnnN D UD 1k Xnn UmX: |Xn| poly(n),n poly(|Xn|) U3mSO,? 3?K1n X0 OVg?k?OlV qX def = XnnNY def = YnnNOl (n) def = 1 2 X | Pr Xn= Pr Yn= | 7 ?a X def = XnnNY def = YnnNOXJOlun ?w,eVqOKUO w41 2.2 ?b ,?CVg3E,nuP a
4、km(8NP akm?y(8b P 6= NP e?Ee 2.4 (): f : 0,1 0,1XJve 1. N O : 3 ( 5 m A x e A(x)=A(x) = f(x) 2. _(J: ?VmA 0?p()v n Pr A 0(f(U n) f 1(f(Un) n mOG : 0,1 0,1*l )XJ kiGs 0,1|G(s)| = l(|s|) kn NCG(Un)Ul(n) O sf)kn n 2.1: )k*3? =?313 2.6 (k?Oq): qxf0,18f 0,1|iGN0,1|iGqk?O XJ3mF,x 0,1neF(,x) = f(x) e5|-EMF
5、y3p?yMFSHA-1 u (J5bX)(J5?E|-EMFq 2.7 ( |-EMFqCRHF): k?Oqf0,1 f: 0,1 0,1|-EXJkVmD3 ?() PrR0,1nD(,1n) = |x 6= y,h(x) = h(y) (n) 8 1 Vg 3|-EMFqbr uTbX, yS?S%S|-Ekr|-E ?5J fbf|-EVg1?e0 universal MF qUOWFH11 2.8 ( universal MFqUOWFH): l : N Nk?O qfss0,1fs: 0,1 0,1l|s|universalMFqXJ 3VmIe 1. k? u p()kg,nu
6、?s Dom(I(1n)vn p(|s|) nl3usmSO5 2. k?O 3Vm3sxOhs(x) 3. 1?u?q()?VmD? VmA?pg,n PrhI(1n)(A(I(1n),Uq(n) = hI(1n)(D(Uq(n) A(I(1n),Uq(n) 6= D(Uq(n) 1 p(n) mA 1mr mKdu pr=| Pr A(G(Un) = 1 Pr A(G(Un) r) = 1| | Pr A(G(Un) = 1 Pr A(U3n) = 1| + | Pr A(U3n) = 1 Pr A(G(Un) r) = 1| | Pr A(G(Un) = 1 Pr A(U3n) = 1|
7、 1 2 p(n) | Pr A(U3n) = 1 Pr A(G(Un) r) = 1| 1 2 p(n) Nwcf)5gu?f| uzr 0,13nU3nU3nC | Pr A(U3n r) = 1 Pr A(G(Un) r) = 1| 1 2 p(n) 14 1 Vg = | Pr A(U3n) = 1 Pr A(G(Un) = 1| 1 2 p(n) )5g 5TYOr 0,13nXJ8G(s)|s 0,1n 8G(s) r|s 0,1n ?r 0,13ns1 0,1n s2 0,1n)-EXJG(s1) = G(s2) rw,r XJ? f)-E,u?rK?kf r = G(s1)G(
8、s2) kfk?2 n 2 ? 22nk22nr r r ?23n 22nJrV ? 23n 22n 23n = 1 2n d(r,)Umr e 3s1G(s1) = K3s2G(s2)r = e3s2G(s2)r = K3s1G(s1) = nTYO 2.3.3 A5?! ?!OSBPP k?KXJBPP )KTKk?O BPP O k dec 0 TDec(auxcom0,0) Ver(crs,com 0,dec0,) = 1 52: k,V (crs,com,dec,)|(crs,aux) Gen(1n),(com,dec) Com(crs) ( (crs,com 0,dec0,) ? ? ? ? ? (crs,aux) Gen(1n),(com 0,aux com0) TCom(crs,aux); dec 0 TDec(auxcom0,) ) O 2.3: 2.2YC?pY=d) r R0,13nUddec 0 TDec(auxcom0,) yb3mD U A0A1K?E VmE|D )G E Xe3iGy?Js 0,1n = G(s),r = G(s) y X R(y,)(r,s)$1DDcLn?|(r,s) lA0A1 ?XJc = 1E/0XJc = 0/0 2.4 /y 2.4.1 ?p 391?p=kN
