2RmJS)0:HG/F7JI>MV;?nfZk3eDF\*Ep[p8"5c@P#ibYg.PSFlKST,sQ4ggJ>TTeD;HOW!8,7)H`E&JHCm4@$cT0-&5TNZ`o>!Z061P>I\1e
%:VAIlR>Y4R'abH!q2#c$8t>.0BYNpLui2kZPT7
%:g1!0)8@&1ARL\$0[[95Fi@;I/oeLHdXUVo^TP2A(qJ>SXG2pC`\;V9IciVSmYZ?(bfn"L?H%n4bdn/EXB9J!_=N)Tmc;d>MKZ2]O*78?[sqa84,<7_)qB8u4e04oY(2@3TfqdiMupTT%poL55UpaI&O`(Og^jaIXCo?kI8&On\K[dOHrqnRn'fok7A3)R[Wdd1FKdr';3L'6VY^tS9RKl(DMPB_10l[K_s!elrU:m&$hS=(HedRa\`2gm%F"@PU+bM]p:-TK4o$.c-cJ@m=)I%tk](r*/,J=Rh!:O&qPl[@ou7r&G2j6knsn;b\8BtNCQh>+;2_KrGj2>V`hhdf
%:?D"_(DL_]X_t;6Cs,P;B)WPs!.eT_K[?hs[:uj:f:)Z:r2cN`hp:;MHfhbM!7prOR#r`Q_IjaT`6?#:X'n]TSH#Q,:nbuq"!o-UK,M:u:8[tIe7NN[e*SaIf!Jef$'m7H6(s%Gh>/tn/JNo5*"]_-NdVqKec)%%qhi//g^jL@"9U\s5=;34n[mkIr%csNJCk>+,&S_L`Ott:cqhA!%KnG#Q%iPm/be5IEeIrG!raH.c6MaVbTN6Y'M0.E3RQTaOhWp]S&a]FakU;Z/f7/?iNO3&0UOs"'mAe!3q/=DH_j**oC5i9b1U!Z"F-QZf3%Uo`M9OS]?*hlqH5F-SFKmHa]Wp:ei@M@AZ08KoF;U*RtYckH=1>n4;n]L/7?pT
%:e)lMcgo'UVM;EAJD^s;Hjk7a/NW$m#&+=(1A)qcda!4CL_Y//A=R)jS_=?JcZ-E:W)(_HWCdud^@qMQUZ/d:@*94Q8IYDP93i@N0`f*-@KHhP[IKtVXI73cFU+fUHbgC
%:D4f6[Q+,`oC=iigHhNU=$iX6jaqtF\G:!1"Z3X)865'IAh-;aU>c\1W&8G(E:Pb\IWK6U%i_[b8KN]up5#TOSHh5f6RnHD(HX^XZ:$itLVmkCp+nO:1U8!rHhMoEQXXmnrX;u3buZ<@J&gN`dZE[B<#aO`F+XL/3[0gYL617:e[Gr='Kc(q"C?Es!OW3"a71G@]3SUQ1Hql6O;o3h:Oq=S38',U@u`'Uf.et.pk@;*sK
%:91)E*h3%KOO[Q.V]"0rP*/R2AVG_pVc&kC11hb[bP48.'CN@X\2)%b9@W:UKM\LZDJE%?PVK>DN.<&O?2[/Z=\D!'Q3F^iA@mF@PALp(lm56"]*"lQ^O2o9Nl(=XG9iIQ*ORAL4>]F*:6^C<4b&,+054enb^+2^+Ws0M>:c'R$KI1<^S?c[@eo\<4[JRBPqZA?;iiAg(sV-625cGjc&0N3+L\/):_Y74XYr\=4^JKE)L4<
%:SL*jV,YF:+pbojEqsZc8`:n79IXh[m6i73S`\'B04npK"ib/$Hp>I/WN(<@F1!o%0%_"W\"1o5]`1t2:`+W';CJJ6l##SoKPlm;qajMug:9,c+`[A&*='*\>ZOqM`R%K-oj*(&@R03.]-3"'HS7FMX0`gS?N(.MtART%aAH2bs6t(1K<,$2\!!0-$6tp.Q!!/ut;fm%oDJ&qM'2W7\F)Y]#FD5o07riA7]c]!&[)ZDe!P_!/j<\Ch6"GF(96)E--#=!!0E.AoD^,!!06'9lNm;C&e6X7;QOPASuSi!Td7*D.7F"9PIsV@<-Vn!JXQbG]Z8gDef=RJ5frd<+06PAH2a\<)[mZBl7P`!"2(_6q2*4F8u;46Z6dZE]*mu7Sn,DE(k=p!!,D_Ec5H!A9Dp(!!'u3Bl7KY@<;JL7@tji
%:a\6DdAQ3)ICh3SHcV/%oF8u=c:gnBQB6%F"BE/%m9ho,6AH2^56t(1G!!%jFBkMR/AH2]]6=FqL@n(0KC]FH76ZmHlDf&^;fHYs6Z6dZE]*mt7mh32Ch7*uDfPgX]1cXYAT@bO<)R:;b^VMa
%:FCB'"Ch3SI%8V.UC]FJp:gnHfATDZXBl%Sc!A72WFD(XSTgs-AF`7<\,scQlDg,#dFD(XTKiDW.F@'e^@qu&FLK%i0F@0t_F_u!r!!!#0!N,s=!N,s=!N,s=!7(Ya!6"rW!6"rW!6"rW!6"rW!6"ra!$qUk!$qUk!$qUk!$qWk!N,s=!N,s=!N,s=!N,s=!N,s=!7(Z*!(d04!8mmU!4r5Q!8mjh!-A3_!2fhT!N,q0!-A7>$2,.>
%:!94(>!%e32!HnJ'!8mk;!8mk;!N,sK!%\/K!"/h*!NlDS!-A7J!=]'[!NlG^!-A7J!=]'[!NlG^!-A7J!=]&g!-A6@!94'$!ODg0!JUWQ!"/h1!?qPo!NlF\!6G7s!It3R!-A6@!-A7J!It3R!JUWX!?qPo!NlF\!6G7s!It3R!-A7J!=]$N!A4@(!%\+l!A4B1!N,q0!7(Z*!NlHH!7(Z*!)rr?!7(ZZ!8mnD!Ta;=!94'$cca>8
%:!2fhW!-A5!!20Fr!8mk;!N,qX!N,qX!N,qX!N,qX!9jLD!N,qU!/gj;!N,qX!*K<^!N,qX!9jLD!9jMR!94(;!.RIS@'KARfXhAH;c1s8N'!_"cEP
%:~>
userdict begin /AltsysDict 300 dict def end
AltsysDict begin
/bdf{bind def}bind def
/xdf{exch def}bdf
/defed{where{pop true}{false}ifelse}bdf
/ndf{1 index where{pop pop pop}{dup xcheck{bind}if def}ifelse}bdf
/d{setdash}bdf
/h{closepath}bdf
/H{}bdf
/J{setlinecap}bdf
/j{setlinejoin}bdf
/M{setmiterlimit}bdf
/n{newpath}bdf
/N{newpath}bdf
/q{gsave}bdf
/Q{grestore}bdf
/w{setlinewidth}bdf
/Xic{matrix invertmatrix concat}bdf
/Xq{matrix currentmatrix mark}bdf
/XQ{cleartomark setmatrix}bdf
/sepdef{
dup where not
{
AltsysSepDict
}
if
3 1 roll exch put
}bdf
/st{settransfer}bdf
/colorimage defed /_rci xdf
/cntr 0 def
/readbinarystring{
/cntr 0 def
2 copy readstring
{
{
dup
(\034) search
{
length exch pop exch
dup length 0 ne
{
dup dup 0 get 32 sub 0 exch put
/cntr cntr 1 add def
}
{
pop 1 string dup
0 6 index read pop 32 sub put
}ifelse
3 copy
putinterval pop
1 add
1 index length 1 sub
1 index sub
dup 0 le {pop pop exit}if
getinterval
}
{
pop exit
} ifelse
} loop
}if
cntr 0 gt
{
pop 2 copy
dup length cntr sub cntr getinterval
readbinarystring
} if
pop exch pop
} bdf
/_NXLevel2 defed {
_NXLevel2 not {
/colorimage where {
userdict eq {
/_rci false def
} if
} if
} if
} if
/md defed{
md type /dicttype eq {
/colorimage where {
md eq {
/_rci false def
}if
}if
/settransfer where {
md eq {
/st systemdict /settransfer get def
}if
}if
}if
}if
/setstrokeadjust defed
{
true setstrokeadjust
/C{curveto}bdf
/L{lineto}bdf
/m{moveto}bdf
}
{
/dr{transform .25 sub round .25 add
exch .25 sub round .25 add exch itransform}bdf
/C{dr curveto}bdf
/L{dr lineto}bdf
/m{dr moveto}bdf
/setstrokeadjust{pop}bdf
}ifelse
/privrectpath {
4 -2 roll m
dtransform round exch round exch idtransform
2 copy 0 lt exch 0 lt xor
{dup 0 exch rlineto exch 0 rlineto neg 0 exch rlineto}
{exch dup 0 rlineto exch 0 exch rlineto neg 0 rlineto}
ifelse
closepath
}bdf
/rectclip{newpath privrectpath clip newpath}def
/rectfill{gsave newpath privrectpath fill grestore}def
/rectstroke{gsave newpath privrectpath stroke grestore}def
/_fonthacksave false def
/currentpacking defed
{
/_bfh {/_fonthacksave currentpacking def false setpacking} bdf
/_efh {_fonthacksave setpacking} bdf
}
{
/_bfh {} bdf
/_efh {} bdf
}ifelse
/packedarray{array astore readonly}ndf
/`
{
false setoverprint
/-save0- save def
5 index concat
pop
storerect left bottom width height rectclip
pop
/MMdict_count countdictstack def
/MMop_count count 1 sub def
userdict begin
/showpage {} def
0 setgray 0 setlinecap 1 setlinewidth
0 setlinejoin 10 setmiterlimit [] 0 setdash newpath
} bdf
/currentpacking defed{true setpacking}if
/min{2 copy gt{exch}if pop}bdf
/max{2 copy lt{exch}if pop}bdf
/xformfont { currentfont exch makefont setfont } bdf
/fhnumcolors 1
statusdict begin
/processcolors defed
{
pop processcolors
}
{
/deviceinfo defed {
deviceinfo /Colors known {
pop deviceinfo /Colors get
} if
} if
} ifelse
end
def
% pix = x^2 + y^2
/printerRes
gsave
matrix defaultmatrix setmatrix
72 72 dtransform
abs exch abs
max
grestore
def
/graycalcs
[
{Angle Frequency}
{GrayAngle GrayFrequency}
{0 Width Height matrix defaultmatrix idtransform
dup mul exch dup mul add sqrt 72 exch div}
{0 GrayWidth GrayHeight matrix defaultmatrix idtransform
dup mul exch dup mul add sqrt 72 exch div}
] def
/calcgraysteps {
forcemaxsteps
{
maxsteps
}
{
/currenthalftone defed
{currenthalftone /dicttype eq}{false}ifelse
{
currenthalftone begin
HalftoneType 4 le
{graycalcs HalftoneType 1 sub get exec}
{
HalftoneType 5 eq
{
Default begin
{graycalcs HalftoneType 1 sub get exec}
end
}
{0 60}
ifelse
}
ifelse
end
}
{
currentscreen pop exch
}
ifelse
printerRes 300 max exch div exch
2 copy
sin mul round dup mul
3 1 roll
cos mul round dup mul
add 1 add
dup maxsteps gt {pop maxsteps} if
dup minsteps lt {pop minsteps} if
}
ifelse
} bdf
/nextrelease defed {
/languagelevel defed not {
/framebuffer defed {
0 40 string framebuffer 9 1 roll 8 {pop} repeat
dup 516 eq exch 520 eq or
{
/fhnumcolors 3 def
/currentscreen {60 0 {pop pop 1}}bdf
/calcgraysteps {maxsteps} bdf
}if
}if
}if
}if
fhnumcolors 1 ne {
/calcgraysteps {maxsteps} bdf
} if
/currentpagedevice defed {
currentpagedevice /PreRenderingEnhance known
{
currentpagedevice /PreRenderingEnhance get
{
/calcgraysteps
{
forcemaxsteps
{maxsteps}
{256 maxsteps min}
ifelse
} def
} if
} if
} if
/gradfrequency 144 def
printerRes 1000 lt {
/gradfrequency 72 def
} if
/adjnumsteps {
dup dtransform abs exch abs max
printerRes div
gradfrequency mul
round
5 max
min
}bdf
/goodsep {
spots exch get 4 get dup sepname eq exch (_vc_Registration) eq or
}bdf
/BeginGradation defed
{/bb{BeginGradation}bdf}
{/bb{}bdf}
ifelse
/EndGradation defed
{/eb{EndGradation}bdf}
{/eb{}bdf}
ifelse
/bottom -0 def
/delta -0 def
/frac -0 def
/height -0 def
/left -0 def
/numsteps1 -0 def
/radius -0 def
/right -0 def
/top -0 def
/width -0 def
/xt -0 def
/yt -0 def
/df currentflat def
/tempstr 1 string def
/clipflatness currentflat def
/inverted?
0 currenttransfer exec .5 ge def
/tc1 [0 0 0 1] def
/tc2 [0 0 0 1] def
/storerect{/top xdf /right xdf /bottom xdf /left xdf
/width right left sub def /height top bottom sub def}bdf
/concatprocs{
systemdict /packedarray known
{dup type /packedarraytype eq 2 index type /packedarraytype eq or}{false}ifelse
{
/proc2 exch cvlit def /proc1 exch cvlit def
proc1 aload pop proc2 aload pop
proc1 length proc2 length add packedarray cvx
}
{
/proc2 exch cvlit def /proc1 exch cvlit def
/newproc proc1 length proc2 length add array def
newproc 0 proc1 putinterval newproc proc1 length proc2 putinterval
newproc cvx
}ifelse
}bdf
/i{dup 0 eq
{pop df dup}
{dup} ifelse
/clipflatness xdf setflat
}bdf
version cvr 38.0 le
{/setrgbcolor{
currenttransfer exec 3 1 roll
currenttransfer exec 3 1 roll
currenttransfer exec 3 1 roll
setrgbcolor}bdf}if
/vms {/vmsv save def} bdf
/vmr {vmsv restore} bdf
/vmrs{vmsv restore /vmsv save def}bdf
/eomode{
{/filler /eofill load def /clipper /eoclip load def}
{/filler /fill load def /clipper /clip load def}
ifelse
}bdf
/normtaper{}bdf
/logtaper{9 mul 1 add log}bdf
/CD{
/NF exch def
{
exch dup
/FID ne 1 index/UniqueID ne and
{exch NF 3 1 roll put}
{pop pop}
ifelse
}forall
NF
}bdf
/MN{
1 index length
/Len exch def
dup length Len add
string dup
Len
4 -1 roll
putinterval
dup
0
4 -1 roll
putinterval
}bdf
/RC{4 -1 roll /ourvec xdf 256 string cvs(|______)anchorsearch
{1 index MN cvn/NewN exch def cvn
findfont dup maxlength dict CD dup/FontName NewN put dup
/Encoding ourvec put NewN exch definefont pop}{pop}ifelse}bdf
/RF{
dup
FontDirectory exch
known
{pop 3 -1 roll pop}
{RC}
ifelse
}bdf
/FF{dup 256 string cvs(|______)exch MN cvn dup FontDirectory exch known
{exch pop findfont 3 -1 roll pop}
{pop dup findfont dup maxlength dict CD dup dup
/Encoding exch /Encoding get 256 array copy 7 -1 roll
{3 -1 roll dup 4 -2 roll put}forall put definefont}
ifelse}bdf
/RCJ{4 -1 roll
/ourvec xdf
256 string cvs
(|______) anchorsearch
{pop
cvn
dup FDFJ
exch
1 index
eq
{
_bfh findfont _efh
dup
maxlength dict
CD
dup
/FontName
3 index
put
dup
/Encoding ourvec put
1 index
exch
definefont
pop
}
{exch pop}
ifelse
}
{pop}
ifelse
}bdf
/RFJ{
dup
FontDirectory exch
known
{pop 3 -1 roll pop}
{RCJ}
ifelse
}bdf
/hasfont
{
/resourcestatus where
{
pop
/Font resourcestatus
{
pop pop true
}
{
false
}
ifelse
}
{
dup FontDirectory exch known
{pop true}
{
256 string
cvs
(fonts/) exch MN
status
{pop pop pop pop true}
{false}
ifelse
}
ifelse
}
ifelse
}bdf
/FDFJ
{
dup
hasfont
not
{
pop
/Ryumin-Light-83pv-RKSJ-H
hasfont
{
/Ryumin-Light-83pv-RKSJ-H
}
{
/Courier
}
ifelse
}
if
}bdf
/FFJ{
_bfh
dup
256 string cvs
(|______)exch MN
cvn
dup
FontDirectory
exch known
{
exch
pop
findfont
3 -1 roll
pop
}
{
pop
FDFJ
dup findfont
dup maxlength dict
CD
dup dup
/Encoding exch
/Encoding get
256 array copy
7 -1 roll
{
3 -1 roll
dup
4 -2 roll
put
}forall
put
definefont
}
ifelse
_efh
}bdf
/GS {
dup
hasfont
{
findfont
exch makesetfont
exch
pop
ts
}
{
pop pop pop
ts
} ifelse
} bdf
/RCK{4 -1 roll
/ourvec xdf
256 string cvs
(|______) anchorsearch
{pop
cvn
dup FDFK
exch
1 index
eq
{
_bfh findfont _efh
dup
maxlength dict
CD
dup
/FontName
3 index
put
dup
/Encoding ourvec put
1 index
exch
definefont
pop
}
{exch pop}
ifelse
}
{pop}
ifelse
}bdf
/RFK{
dup
FontDirectory exch
known
{pop 3 -1 roll pop}
{RCK}
ifelse
}bdf
/hasfont
{
/resourcestatus where
{
pop
/Font resourcestatus
{
pop pop true
}
{
false
}
ifelse
}
{
dup FontDirectory exch known
{pop true}
{
256 string
cvs
(fonts/) exch MN
status
{pop pop pop pop true}
{false}
ifelse
}
ifelse
}
ifelse
}bdf
/FDFK
{
dup
hasfont
not
{
pop
/JCsm
hasfont
{
/JCsm
}
{
/Courier
}
ifelse
}
if
}bdf
/FFK{
_bfh
dup
256 string cvs
(|______)exch MN
cvn
dup
FontDirectory
exch known
{
exch
pop
findfont
3 -1 roll
pop
}
{
pop
FDFK
dup findfont
dup maxlength dict
CD
dup dup
/Encoding exch
/Encoding get
256 array copy
7 -1 roll
{
3 -1 roll
dup
4 -2 roll
put
}forall
put
definefont
}
ifelse
_efh
}bdf
/RCTC{4 -1 roll
/ourvec xdf
256 string cvs
(|______) anchorsearch
{pop
cvn
dup FDFTC
exch
1 index
eq
{
_bfh findfont _efh
dup
maxlength dict
CD
dup
/FontName
3 index
put
dup
/Encoding ourvec put
1 index
exch
definefont
pop
}
{exch pop}
ifelse
}
{pop}
ifelse
}bdf
/RFTC{
dup
FontDirectory exch
known
{pop 3 -1 roll pop}
{RCTC}
ifelse
}bdf
/FDFTC
{
dup
hasfont
not
{
pop
/DFMing-Lt-HK-BF
hasfont
{
/DFMing-Lt-HK-BF
}
{
/Courier
}
ifelse
}
if
}bdf
/FFTC{
_bfh
dup
256 string cvs
(|______)exch MN
cvn
dup
FontDirectory
exch known
{
exch
pop
findfont
3 -1 roll
pop
}
{
pop
FDFTC
dup findfont
dup maxlength dict
CD
dup dup
/Encoding exch
/Encoding get
256 array copy
7 -1 roll
{
3 -1 roll
dup
4 -2 roll
put
}forall
put
definefont
}
ifelse
_efh
}bdf
/fps{
currentflat
exch
dup 0 le{pop 1}if
{
dup setflat 3 index stopped
{1.3 mul dup 3 index gt{pop setflat pop pop stop}if}
{exit}
ifelse
}loop
pop setflat pop pop
}bdf
/fp{100 currentflat fps}bdf
/clipper{clip}bdf
/W{/clipper load 100 clipflatness dup setflat fps}bdf
/AVec 256 array def
AVec 0 /Helvetica findfont
/Encoding get 0 256 getinterval putinterval
/ANSIPatch[
16#0/grave 16#1/acute 16#2/circumflex 16#3/tilde 16#4/macron 16#5/breve
16#6/dotaccent 16#7/dieresis 16#8/ring 16#9/cedilla 16#A/hungarumlaut
16#B/ogonek 16#C/caron 16#D/dotlessi 16#27/quotesingle 16#60/grave
16#7C/bar 16#82/quotesinglbase 16#83/florin 16#84/quotedblbase 16#85
/ellipsis 16#86/dagger 16#87/daggerdbl 16#89/perthousand 16#8A/Scaron
16#8B/guilsinglleft 16#8C/OE 16#91/quoteleft 16#92/quoteright 16#93
/quotedblleft 16#94/quotedblright 16#95/bullet 16#96/endash 16#97/emdash
16#99/trademark 16#9A/scaron 16#9B/guilsinglright 16#9C/oe
16#9F/Ydieresis 16#A0/space 16#A4/currency 16#A6/brokenbar
16#A7/section 16#A8/dieresis 16#A9/copyright 16#AA/ordfeminine 16#AB/guillemotleft
16#AC/logicalnot 16#AD/hyphen 16#AE/registered 16#AF/macron 16#B0/degree
16#B1/plusminus 16#B2/twosuperior 16#B3/threesuperior 16#B4/acute 16#B5/mu
16#B6/paragraph 16#B7/periodcentered 16#B8/cedilla 16#B9/onesuperior
16#BA/ordmasculine 16#BB/guillemotright 16#BC/onequarter 16#BD/onehalf
16#BE/threequarters 16#BF/questiondown 16#C0/Agrave 16#C1/Aacute 16#C2/Acircumflex
16#C3/Atilde 16#C4/Adieresis 16#C5/Aring 16#C6/AE 16#C7/Ccedilla 16#C8/Egrave
16#C9/Eacute 16#CA/Ecircumflex 16#CB/Edieresis 16#CC/Igrave 16#CD/Iacute
16#CE/Icircumflex 16#CF/Idieresis 16#D0/Eth 16#D1/Ntilde 16#D2/Ograve
16#D3/Oacute 16#D4/Ocircumflex 16#D5/Otilde 16#D6/Odieresis 16#D7/multiply
16#D8/Oslash 16#D9/Ugrave 16#DA/Uacute 16#DB/Ucircumflex 16#DC/Udieresis
16#DD/Yacute 16#DE/Thorn 16#DF/germandbls 16#E0/agrave 16#E1/aacute
16#E2/acircumflex 16#E3/atilde 16#E4/adieresis 16#E5/aring 16#E6/ae
16#E7/ccedilla 16#E8/egrave 16#E9/eacute 16#EA/ecircumflex 16#EB/edieresis
16#EC/igrave 16#ED/iacute 16#EE/icircumflex 16#EF/idieresis 16#F0/eth
16#F1/ntilde 16#F2/ograve 16#F3/oacute 16#F4/ocircumflex 16#F5/otilde
16#F6/odieresis 16#F7/divide 16#F8/oslash 16#F9/ugrave 16#FA/uacute
16#FB/ucircumflex 16#FC/udieresis 16#FD/yacute 16#FE/thorn 16#FF/ydieresis
] def
127 1 159 { AVec exch/bullet put } for
ANSIPatch aload pop ANSIPatch length 2 idiv{AVec 3 1 roll put}repeat
/DoPatch { dup /CharStrings known
{ setfont
0 1 255 { dup
currentfont
/Encoding get
exch get
currentfont /CharStrings get
exch known
{pop} {currentfont /Encoding get exch /bullet put} ifelse
} for
} {pop} ifelse
} def
/findheaderfont {
AVec 256 array copy
/FHT /|______Helvetica dup RF findfont def
FHT DoPatch
FHT
} def
end %. AltsysDict
AltsysDict begin
_bfh
/f0 /Gen_Arial findfont def
_efh
end %. AltsysDict
AltsysDict begin
/onlyk4{false}ndf
/ccmyk{dup 5 -1 roll sub 0 max exch}ndf
/cmyk2gray{
4 -1 roll 0.3 mul 4 -1 roll 0.59 mul 4 -1 roll 0.11 mul
add add add 1 min neg 1 add
}bdf
/setcmykcolor{1 exch sub ccmyk ccmyk ccmyk pop setrgbcolor}ndf
/maxcolor {
max max max
} ndf
/maxspot {
pop
} ndf
/setcmykcoloroverprint{4{dup -1 eq{pop 0}if 4 1 roll}repeat setcmykcolor}ndf
/findcmykcustomcolor{5 packedarray}ndf
/setcustomcolor{exch aload pop pop 4{4 index mul 4 1 roll}repeat setcmykcolor pop}ndf
/setseparationgray{setgray}ndf
/setoverprint{pop}ndf
/currentoverprint false ndf
/cmykbufs2gray{
0 1 2 index length 1 sub
{
4 index 1 index get 0.3 mul
4 index 2 index get 0.59 mul
4 index 3 index get 0.11 mul
4 index 4 index get
add add add cvi 255 min
255 exch sub
2 index 3 1 roll put
}for
4 1 roll pop pop pop
}bdf
/colorimage{
pop pop
[
5 -1 roll/exec cvx
6 -1 roll/exec cvx
7 -1 roll/exec cvx
8 -1 roll/exec cvx
/cmykbufs2gray cvx
]cvx
image
}
%. version 47.1 on Linotronic of Postscript defines colorimage incorrectly (rgb model only)
version cvr 47.1 le
statusdict /product get (Lino) anchorsearch{pop pop true}{pop false}ifelse
and{userdict begin bdf end}{ndf}ifelse
fhnumcolors 1 ne {/yt save def} if
/customcolorimage{
aload pop
(_vc_Registration) eq
{
pop pop pop pop separationimage
}
{
/ik xdf /iy xdf /im xdf /ic xdf
ic im iy ik cmyk2gray /xt xdf
currenttransfer
{dup 1.0 exch sub xt mul add}concatprocs
st
image
}
ifelse
}ndf
fhnumcolors 1 ne {yt restore} if
fhnumcolors 3 ne {/yt save def} if
/customcolorimage{
aload pop
(_vc_Registration) eq
{
pop pop pop pop separationimage
}
{
/ik xdf /iy xdf /im xdf /ic xdf
1.0 dup ic ik add min sub
1.0 dup im ik add min sub
1.0 dup iy ik add min sub
/ic xdf /iy xdf /im xdf
currentcolortransfer
4 1 roll
{dup 1.0 exch sub ic mul add}concatprocs 4 1 roll
{dup 1.0 exch sub iy mul add}concatprocs 4 1 roll
{dup 1.0 exch sub im mul add}concatprocs 4 1 roll
setcolortransfer
{/dummy xdf dummy}concatprocs{dummy}{dummy}true 3 colorimage
}
ifelse
}ndf
fhnumcolors 3 ne {yt restore} if
fhnumcolors 4 ne {/yt save def} if
/customcolorimage{
aload pop
(_vc_Registration) eq
{
pop pop pop pop separationimage
}
{
/ik xdf /iy xdf /im xdf /ic xdf
currentcolortransfer
{1.0 exch sub ik mul ik sub 1 add}concatprocs 4 1 roll
{1.0 exch sub iy mul iy sub 1 add}concatprocs 4 1 roll
{1.0 exch sub im mul im sub 1 add}concatprocs 4 1 roll
{1.0 exch sub ic mul ic sub 1 add}concatprocs 4 1 roll
setcolortransfer
{/dummy xdf dummy}concatprocs{dummy}{dummy}{dummy}
true 4 colorimage
}
ifelse
}ndf
fhnumcolors 4 ne {yt restore} if
/separationimage{image}ndf
/spotascmyk false ndf
/newcmykcustomcolor{6 packedarray}ndf
/inkoverprint false ndf
/setinkoverprint{pop}ndf
/setspotcolor {
spots exch get
dup 4 get (_vc_Registration) eq
{pop 1 exch sub setseparationgray}
{0 5 getinterval exch setcustomcolor}
ifelse
}ndf
/currentcolortransfer{currenttransfer dup dup dup}ndf
/setcolortransfer{st pop pop pop}ndf
/fas{}ndf
/sas{}ndf
/fhsetspreadsize{pop}ndf
/filler{fill}bdf
/F{gsave {filler}fp grestore}bdf
/f{closepath F}bdf
/S{gsave {stroke}fp grestore}bdf
/s{closepath S}bdf
userdict /islevel2
systemdict /languagelevel known dup
{
pop systemdict /languagelevel get 2 ge
} if
put
islevel2 not
{
/currentcmykcolor
{
0 0 0 1 currentgray sub
} ndf
} if
/tc
{
gsave
setcmykcolor currentcmykcolor
grestore
} bind def
/testCMYKColorThrough
{
tc add add add 0 ne
} bind def
/fhiscomposite where not {
userdict /fhiscomposite
islevel2
{
gsave 1 1 1 1 setcmykcolor currentcmykcolor grestore
add add add 4 eq
}
{
1 0 0 0 testCMYKColorThrough
0 1 0 0 testCMYKColorThrough
0 0 1 0 testCMYKColorThrough
0 0 0 1 testCMYKColorThrough
and and and
} ifelse
put
}
{ pop }
ifelse
/bc4 [0 0 0 0] def
/_lfp4 {
1 pop
/yt xdf
/xt xdf
/ang xdf
storerect
/taperfcn xdf
/k2 xdf /y2 xdf /m2 xdf /c2 xdf
/k1 xdf /y1 xdf /m1 xdf /c1 xdf
c1 c2 sub abs
m1 m2 sub abs
y1 y2 sub abs
k1 k2 sub abs
maxcolor
calcgraysteps mul abs round
height abs adjnumsteps
dup 1 lt {pop 1} if
1 sub /numsteps1 xdf
currentflat mark
currentflat clipflatness
/delta top bottom sub numsteps1 1 add div def
/right right left sub def
/botsv top delta sub def
{
{
W
xt yt translate
ang rotate
xt neg yt neg translate
dup setflat
/bottom botsv def
0 1 numsteps1
{
numsteps1 dup 0 eq {pop pop 0.5} {div} ifelse
taperfcn /frac xdf
bc4 0 c2 c1 sub frac mul c1 add put
bc4 1 m2 m1 sub frac mul m1 add put
bc4 2 y2 y1 sub frac mul y1 add put
bc4 3 k2 k1 sub frac mul k1 add put
bc4 vc
1 index setflat
{
mark {newpath left bottom right delta rectfill}stopped
{cleartomark exch 1.3 mul dup setflat exch 2 copy gt{stop}if}
{cleartomark exit}ifelse
}loop
/bottom bottom delta sub def
}for
}
gsave stopped grestore
{exch pop 2 index exch 1.3 mul dup 100 gt{cleartomark setflat stop}if}
{exit}ifelse
}loop
cleartomark setflat
}bdf
/bcs [0 0] def
/_lfs4 {
/yt xdf
/xt xdf
/ang xdf
storerect
/taperfcn xdf
/tint2 xdf
/tint1 xdf
bcs exch 1 exch put
tint1 tint2 sub abs
bcs 1 get maxspot
calcgraysteps mul abs round
height abs adjnumsteps
dup 2 lt {pop 2} if
1 sub /numsteps1 xdf
currentflat mark
currentflat clipflatness
/delta top bottom sub numsteps1 1 add div def
/right right left sub def
/botsv top delta sub def
{
{
W
xt yt translate
ang rotate
xt neg yt neg translate
dup setflat
/bottom botsv def
0 1 numsteps1
{
numsteps1 div taperfcn /frac xdf
bcs 0
1.0 tint2 tint1 sub frac mul tint1 add sub
put bcs vc
1 index setflat
{
mark {newpath left bottom right delta rectfill}stopped
{cleartomark exch 1.3 mul dup setflat exch 2 copy gt{stop}if}
{cleartomark exit}ifelse
}loop
/bottom bottom delta sub def
}for
}
gsave stopped grestore
{exch pop 2 index exch 1.3 mul dup 100 gt{cleartomark setflat stop}if}
{exit}ifelse
}loop
cleartomark setflat
}bdf
/_rfs6 {
/tint2 xdf
/tint1 xdf
bcs exch 1 exch put
/inrad xdf
/radius xdf
/yt xdf
/xt xdf
tint1 tint2 sub abs
bcs 1 get maxspot
calcgraysteps mul abs round
radius inrad sub abs
adjnumsteps
dup 1 lt {pop 1} if
1 sub /numsteps1 xdf
radius inrad sub numsteps1 dup 0 eq {pop} {div} ifelse
2 div /halfstep xdf
currentflat mark
currentflat clipflatness
{
{
dup setflat
W
0 1 numsteps1
{
dup /radindex xdf
numsteps1 dup 0 eq {pop pop 0.5} {div} ifelse
/frac xdf
bcs 0
tint2 tint1 sub frac mul tint1 add
put bcs vc
1 index setflat
{
newpath mark
xt yt radius inrad sub 1 frac sub mul halfstep add inrad add 0 360
{ arc
radindex numsteps1 ne
inrad 0 gt or
{
xt yt
numsteps1 0 eq
{ inrad }
{
radindex 1 add numsteps1 div 1 exch sub
radius inrad sub mul halfstep add inrad add
}ifelse
dup xt add yt moveto
360 0 arcn
} if
fill
}stopped
{cleartomark exch 1.3 mul dup setflat exch 2 copy gt{stop}if}
{cleartomark exit}ifelse
}loop
}for
}
gsave stopped grestore
{exch pop 2 index exch 1.3 mul dup 100 gt{cleartomark setflat stop}if}
{exit}ifelse
}loop
cleartomark setflat
}bdf
/_rfp6 {
1 pop
/k2 xdf /y2 xdf /m2 xdf /c2 xdf
/k1 xdf /y1 xdf /m1 xdf /c1 xdf
/inrad xdf
/radius xdf
/yt xdf
/xt xdf
c1 c2 sub abs
m1 m2 sub abs
y1 y2 sub abs
k1 k2 sub abs
maxcolor
calcgraysteps mul abs round
radius inrad sub abs
adjnumsteps
dup 1 lt {pop 1} if
1 sub /numsteps1 xdf
radius inrad sub numsteps1 dup 0 eq {pop} {div} ifelse
2 div /halfstep xdf
currentflat mark
currentflat clipflatness
{
{
dup setflat
W
0 1 numsteps1
{
dup /radindex xdf
numsteps1 dup 0 eq {pop pop 0.5} {div} ifelse
/frac xdf
bc4 0 c2 c1 sub frac mul c1 add put
bc4 1 m2 m1 sub frac mul m1 add put
bc4 2 y2 y1 sub frac mul y1 add put
bc4 3 k2 k1 sub frac mul k1 add put
bc4 vc
1 index setflat
{
newpath mark
xt yt radius inrad sub 1 frac sub mul halfstep add inrad add 0 360
{ arc
radindex numsteps1 ne
inrad 0 gt or
{
xt yt
numsteps1 0 eq
{ inrad }
{
radindex 1 add numsteps1 div 1 exch sub
radius inrad sub mul halfstep add inrad add
}ifelse
dup xt add yt moveto
360 0 arcn
} if
fill
}stopped
{cleartomark exch 1.3 mul dup setflat exch 2 copy gt{stop}if}
{cleartomark exit}ifelse
}loop
}for
}
gsave stopped grestore
{exch pop 2 index exch 1.3 mul dup 100 gt{cleartomark setflat stop}if}
{exit}ifelse
}loop
cleartomark setflat
}bdf
/lfp4{_lfp4}ndf
/lfs4{_lfs4}ndf
/rfs6{_rfs6}ndf
/rfp6{_rfp6}ndf
/cvc [0 0 0 1] def
/vc{
AltsysDict /cvc 2 index put
aload length dup 4 eq
{pop dup -1 eq{pop setrgbcolor}{setcmykcolor}ifelse}
{6 eq {sethexcolor} {setspotcolor} ifelse }
ifelse
}bdf
0 setseparationgray
/imgr {1692 1584 2304 2376 } def
/bleed 0 def
/clpr {1692 1584 2304 2376 } def
/xs 1 def
/ys 1 def
/botx 0 def
/overlap 0 def
/wdist 18 def
0 2 mul fhsetspreadsize
0 0 ne {/df 0 def /clipflatness 0 def} if
/maxsteps 256 def
/forcemaxsteps false def
/minsteps 0 def
userdict begin /AGDOrigMtx matrix currentmatrix def end
vms
-1754 -2094 translate
/currentpacking defed{false setpacking}if
/spots[
1 0 0 0 (Process Cyan) false newcmykcustomcolor
0 1 0 0 (Process Magenta) false newcmykcustomcolor
0 0 1 0 (Process Yellow) false newcmykcustomcolor
0 0 0 1 (Process Black) false newcmykcustomcolor
]def
/makepattern defed /xt xdf
xt not {/yt save def} if
/PATmp{
exch
dup length 3 add dict copy
begin
currentdict /Multi known not {/Multi 1 def} if
Multi 1 ne {
/UserProc /PaintProc load def
/PaintProc {
begin
0 1 Multi 1 sub {
PaintColors 1 index get PATsc
PaintData exch get
gsave currentdict UserProc grestore
}for
end
} bdf
} if
currentdict
end
exch makepattern
}bdf
/PATsp{
dup /PaintType get 2 eq
{
exch aload length 4 eq
{5 -1 roll}
{spots exch get 0 4 getinterval aload pop
4 {4 index mul 4 1 roll} repeat 6 -2 roll pop}ifelse
[/Pattern /DeviceCMYK] setcolorspace
}if
setpattern
}bdf
/PATfill{{{eofill}fp}{{fill}fp}ifelse}bdf
/PATprestroke{}bdf
/PATstroke{stroke}bdf
xt not {yt restore} if
xt {/yt save def} if
/PATtcalc{
gsave
exch concat
matrix currentmatrix exch
2 ne {
dup 4 get exch dup 5 get exch
XStep 0 dtransform round exch round exch
XStep div exch XStep div exch
0 YStep dtransform round exch round exch
YStep div exch YStep div exch
7 -3 roll astore
} if
grestore
}bdf
/PATmp{
exch
dup
length 8 add
dict copy
begin
TilingType PATtcalc
/PATcurrentMtx xdf
currentdict /Multi known not {/Multi 1 def} if
/FontType 3 def
/Encoding 256 array def
3 string 0 1 255
{Encoding exch dup 3 index cvs cvn put} for pop
/FontMatrix matrix def
/FontBBox BBox def
/BuildChar {
mark 3 1 roll
exch begin
Multi 1 ne {PaintData exch get}{pop}ifelse
PaintType 2 eq Multi 1 ne or
{XStep 0 FontBBox aload pop setcachedevice}
{XStep 0 setcharwidth}ifelse
currentdict
/PaintProc load
end
gsave exec grestore
cleartomark
}bdf
currentdict
end
/foo exch
definefont
}bdf
/PATsp{
/PATcurrent xdf
PATcurrent /PaintType get 2 eq
{/PATcolor xdf}if
}bdf
/PATpcalc{
PATcurrent begin
gsave
PATcurrentMtx setmatrix
BBox aload pop pop pop translate
pathbbox
grestore
YStep div ceiling 4 1 roll
XStep div ceiling 4 1 roll
YStep div floor 4 1 roll
XStep div floor 4 1 roll
2 index sub cvi abs
exch 3 index sub cvi abs exch
4 2 roll
YStep mul exch XStep mul exch
end
}bdf
/PATfill{
{{eoclip}fp}{{clip}fp}ifelse
PATpcalc
newpath
PATcurrent dup begin
setfont
PATcurrentMtx setmatrix
PaintType 2 eq {PATcolor vc} if
3 index string
0 1 Multi 1 sub {
3 index 3 index moveto
Multi 1 ne {dup PaintColors exch get vc} if
0 1 7 index 1 sub {
2 index
exch
2 index put
} for
pop
3 index
{
currentpoint
2 index show
YStep add moveto
}repeat
}for
5 {pop} repeat
end
}bdf
/PATprestroke{{strokepath}fp}bdf
/PATstroke{false PATfill}bdf
xt {yt restore} if
/makepattern defed /xt xdf
xt not {/yt save def} if
userdict begin /fhpatdict 12 dict def end
fhpatdict begin
/PatternType 1 def
/PaintType 1 def
/TilingType 1 def
/BBox [0 0 8 8] def
/XStep 8 def
/YStep 8 def
/PatMtx [1 0 0 -1 0 8] def
/PatIMtx [1 0 0 1 0 0] def
/PaintProc
{begin FHPatColor vc 8 8 true PatMtx PatData imagemask end} bdf
/FHPatColor [0 0 0 0] def
end
/macpatorient{1 0 dtransform 0 eq exch 0 ne and}ndf
/veccalc { dtransform round exch round exch idtransform dup mul exch dup mul exch add sqrt } bdf
gsave
0 0 transform
2 copy
round exch round exch
2 index sub exch 3 index sub exch
idtransform translate
pop pop
1 0 veccalc 0 1 veccalc
scale
matrix currentmatrix
/PATmtx xdf
grestore
/pF{
gsave 1 setgray filler grestore
fhpatdict begin
/PatData xdf
/FHPatColor xdf
end
save
PATmtx setmatrix
fhpatdict dup
/PatIMtx get
PATmp
PATsp
/clipper load /eoclip load eq PATfill
restore
}bdf
/pS{
fhpatdict begin
/PatData xdf
/FHPatColor xdf
end
save
PATprestroke
PATmtx setmatrix
gsave 1 setgray stroke grestore
fhpatdict dup
/PatIMtx get
PATmp
PATsp
PATstroke
restore
}bdf
xt not {yt restore} if
xt {/yt save def} if
/macpatstring 8 string def
/macpattint 0 def
/macpatcol [] def
/macpatangle{1 0 matrix defaultmatrix dtransform exch atan}bdf
/macpatorient{1 0 dtransform 0 eq exch 0 ne and}ndf
/macpatcountbits
{
0 exch
{
cvi
0 1 8
{
pop
dup 1 and
0 ne
{
exch
1 add
exch
} if
-1 bitshift
} for
pop
}
forall
}bdf
/macpatset
{
macpatstring copy pop
9.375
macpatangle
macpatorient not{-90 add}if
{
1 add 4 mul cvi macpatstring exch get exch
1 add 4 mul cvi 7 sub bitshift 1 and
inverted? {1 exch sub} if
}
setscreen
64 macpatstring macpatcountbits sub 64 div
inverted? {.9921875 exch sub} if
/macpattint xdf
{} st
fhnumcolors 1 ne
{
cvc dup length array copy /macpatcol xdf
/macpattint 1 macpattint sub def
macpatcol length 4 eq
{
0 1 3
{
macpatcol exch 2 copy
get .25 lt{0}{macpattint}ifelse put
}for
}
{
macpatcol dup 0 get .25 lt{0}{macpattint}ifelse 0 exch put
}ifelse
macpatcol vc
}
{
currentgray 1 ne {macpattint setseparationgray} if
}
ifelse
}bdf
/pF{
gsave
exch vc
macpatset
{filler}fp
grestore
}bdf
/pS{
gsave
exch vc
macpatset
{stroke}fp
grestore
}bdf
xt {yt restore} if
/pf{closepath pF}bdf
/ps{closepath pS}bdf
/textopf false def
/curtextmtx{}def
/otw .25 def
/msf{dup/curtextmtx xdf makefont setfont}bdf
/makesetfont/msf load def
/curtextheight{.707104 .707104 curtextmtx dtransform
dup mul exch dup mul add sqrt}bdf
/ta2{
tempstr 2 index gsave exec grestore
cwidth cheight rmoveto
4 index eq{5 index 5 index rmoveto}if
2 index 2 index rmoveto
}bdf
/ta{exch systemdict/cshow known
{{/cheight xdf/cwidth xdf tempstr 0 2 index put ta2}exch cshow}
{{tempstr 0 2 index put tempstr stringwidth/cheight xdf/cwidth xdf ta2}forall}
ifelse 6{pop}repeat}bdf
/sts{/textopf currentoverprint def vc setoverprint
/ts{awidthshow}def exec textopf setoverprint}bdf
/stol{/xt currentlinewidth def
setlinewidth vc newpath
/ts{{false charpath stroke}ta}def exec
xt setlinewidth}bdf
/strk{/textopf currentoverprint def vc setoverprint
/ts{{false charpath stroke}ta}def exec
textopf setoverprint
}bdf
n
[] 0 d
3.863708 M
1 w
0 j
0 J
false setoverprint
0 i
false eomode
[0 0 0 1]vc
vms
1779.3812 2179.4606 m
1803.8184 2202.2485 1836.3758 2207.0508 1852.1013 2190.1871 C
1867.8268 2173.3234 1860.7647 2141.1804 1836.3275 2118.3926 C
1811.8903 2095.6048 1779.3329 2090.8024 1763.6075 2107.6661 C
1747.882 2124.5298 1754.944 2156.6728 1779.3812 2179.4606 C
3.863693 M
s
n
1948.7304 2179.4606 m
1973.1676 2202.2485 2005.7249 2207.0508 2021.4504 2190.1871 C
2037.1759 2173.3234 2030.1139 2141.1804 2005.6767 2118.3926 C
1981.2395 2095.6048 1948.6821 2090.8024 1932.9566 2107.6661 C
1917.2311 2124.5298 1924.2932 2156.6728 1948.7304 2179.4606 C
[0 0 0 1] <8244281028448201> pf
3.863708 M
S
n
vmrs
1784.3237 2142.4744 m
1792.6323 2150.2221 1803.7016 2151.8545 1809.0482 2146.1206 C
1814.3947 2140.3867 1811.9936 2129.4579 1803.6851 2121.7102 C
1795.3765 2113.9625 1784.3072 2112.3301 1778.9606 2118.064 C
1773.6141 2123.7979 1776.0152 2134.7267 1784.3237 2142.4744 C
[0 0 0 1] <8040201008040201> pf
3.863693 M
S
n
vmrs
2057.5 2180.5 m
2078 2180.5 L
2078 2164 L
2057.5 2164 L
2057.5 2180.5 L
[0 0 0 1] <0102040810204080> pf
S
n
vmrs
2092.5 2160.5 m
2042.5 2160.5 L
2042.5 2147.5002 L
2092.5 2147.5002 L
2092.5 2160.5 L
n
q
{
f0 [12 0 0 12 0 0] makesetfont
2042.5 2150.9001 m
0 0 32 0.392212 0 (Ef) ts
-0.1919 0 rmoveto }
true
[0 0 0 1]sts
{
f0 [12 0 0 12 0 0] makesetfont
0 0 32 0.392212 0 (f-SFE) ts
}
true
[0 0 0 1]sts
Q
false eomode
2057.5 2127.9872 m
2078 2127.9872 L
2078 2111.4872 L
2057.5 2111.4872 L
2057.5 2127.9872 L
[0 0 0 1] <8040201008040201> pf
[0 0 0 1]vc
false setoverprint
S
n
vmrs
2096 2107.4872 m
2040.5 2107.4872 L
2040.5 2094 L
2096 2094 L
2096 2107.4872 L
n
q
{
f0 [12 0 0 12 0 0] makesetfont
2040.5 2097.8873 m
0 0 32 0.584839 0 (Complete) ts
}
true
[0 0 0 1]sts
Q
false eomode
1805.794 2168.8109 m
1815.7734 2178.1167 1829.0733 2180.0726 1835.5007 2173.1796 C
1841.928 2166.2866 1839.0485 2153.1552 1829.0691 2143.8494 C
1819.0897 2134.5436 1805.7897 2132.5877 1799.3624 2139.4807 C
1792.9351 2146.3738 1795.8145 2159.5051 1805.794 2168.8109 C
[0 0 0 1] <0102040810204080> pf
3.863693 M
[0 0 0 1]vc
false setoverprint
S
n
vmrs
1796 2148.75 m
1796.5 2144.5 L
1797.875 2141.625 L
1799.625 2139.125 L
1802 2137.25 L
1805 2136 L
1807.625 2135.5 L
1809.75 2135.375 L
1811.625 2135.5 L
1811.875 2139.125 L
1811.375 2141.875 L
1810.5 2144.5 L
1808.625 2146.625 L
1806 2148.5 L
1803.5 2149.125 L
1801 2149.5 L
1798.75 2149.625 L
1796 2148.75 L
[0 0 0 1] <8244281028448201> pf
S
n
vmrs
1862 2138 m
1900.7481 2137.8572 L
6 w
3.863693 M
S
n
true eomode
1900.7481 2137.8572 m
1894.0815 2147.8572 L
1920.7481 2137.8572 L
1894.0815 2127.8572 L
1900.7481 2137.8572 L
f
n
vmr
vmr
end
%%EndDocument
@endspecial 803 11661 a Fr(Figure)396 b(2:)534 b(The)396
b(t)-34 b(w)g(o)397 b(families)f Fp(S)91 b(F)120 b(E)108
b Fr(-C)396 b(and)h(E\256-)p Fp(S)91 b(F)120 b(E)504
b Fr(ma)-34 b(y)396 b(ha)-34 b(v)g(e)396 b(no)h(in)-34
b(tersection,)397 b(but)g(if)f(they)g(in)-34 b(tersect)803
13167 y(\(as)367 b(is)g(sho)-34 b(wn)368 b(in)f(the)g(\257gure\))g
(then)g(all)f(e\261cien)-34 b(tly)366 b(computable)i(functions)g(ha)-34
b(v)g(e)367 b(SFE)g(proto)34 b(cols)367 b(and)g(also)803
14672 y Fp(S)91 b(F)120 b(E)109 b Fr(-C)337 b(=)f(E\256-)p
Fp(S)91 b(F)120 b(E)109 b Fr(.)0 18104 y(The)396 b(sets)g
Fp(S)91 b(F)120 b(E)108 b Fr(-C)396 b(and)g(E\256-)p
Fp(S)91 b(F)120 b(E)504 b Fr(ha)-34 b(v)g(e)396 b(the)g(follo)-34
b(wing)396 b(t)-34 b(w)g(o)397 b(p)34 b(ossibilities:)534
b(Either)395 b(the)h(t)-34 b(w)g(o)397 b(sets)e(are)g(distinct)0
19609 y(\(ha)-34 b(v)g(e)516 b(no)f(in)-34 b(tersection\))516
b(or)f(the)g(t)-34 b(w)g(o)517 b(sets)e(ha)-34 b(v)g(e)516
b(an)f(in)-34 b(tersection.)872 b(But)515 b(the)g(latter)g(case)g
(implies)f(that)j(all)0 21115 y(e\261cien)-34 b(tly)572
b(computable)i(functions)g(ha)-34 b(v)g(e)574 b(an)f(SFE)g(proto)34
b(col,)614 b(and)574 b(th)-34 b(us)574 b Fp(S)91 b(F)120
b(E)109 b Fr(-C)618 b(=)g(E\256-)p Fp(S)91 b(F)120 b(E)681
b Fr(and)574 b(they)0 22620 y(con)-34 b(tain)416 b(all)e(e\261cien)-34
b(tly)414 b(computable)h(functions)i(\(see)d(Figure)h(2\).)570
b(This)416 b(is)e(indeed)h(the)g(case,)i(for)d(instance,)k(if)0
24126 y(e\261cien)-34 b(t)432 b(OT)g(proto)34 b(cols)432
b(\(de\257ned)i(in)e(the)g(next)g(section\))h(exist.)622
b(Altogether,)439 b(either)431 b Fp(S)91 b(F)120 b(E)109
b Fr(-C)432 b(and)h(E\256-)p Fp(S)91 b(F)120 b(E)0 25631
y Fr(do)405 b(not)f(in)-34 b(tersect)405 b(or)e Fp(S)91
b(F)120 b(E)109 b Fr(-C)337 b(=)g(E\256-)p Fp(S)91 b(F)120
b(E)512 b Fr(and)405 b(they)g(con)-34 b(tain)405 b(all)e(e\261cien)-34
b(tly)404 b(computable)h(functions.)1882 27137 y(Note)269
b(that)i(this)f(is)f(also)g(the)h(situation)h(for)e(other)h
(de\257nitions)h(of)f(completeness)f(suc)-34 b(h)270
b(as)g Fp(N)179 b(P)99 b Fr(-completeness,)0 28642 y(but)310
b(the)f(SFE)g(scenario)f(di\256ers)h(that)h(of)f Fp(N)179
b(P)407 b Fr(in)309 b(the)g(sense)g(that)h(for)f Fp(N)179
b(P)407 b Fr(it)309 b(is)f(widely)h(assumed)g(that)h
Fp(P)437 b(6)p Fr(=)336 b Fp(N)179 b(P)0 30148 y Fr(\(and)279
b(therefore)e(the)h(sets)g Fp(N)179 b(P)99 b Fr(-C)278
b(and)g Fp(P)378 b Fr(are)277 b(assumed)h(to)g(b)34 b(e)278
b(distinct\).)497 b(While)277 b(in)g(our)h(case)f(of)h(SFE)g(it)g(is)f
(seems)0 31653 y(reasonable)407 b(\(or)g(at)g(least)g(not)g
(surprising\))h(that)g(there)f(is)f(an)h(in)-34 b(tersection)408
b(and)f(that)h(all)e(functions)j(are)d(b)34 b(oth)0 33158
y(SFE-complete)396 b(and)h(in)f(E\256-)p Fp(S)91 b(F)120
b(E)109 b Fr(.)536 b(P)-34 b(erhaps)396 b(a)g(b)34 b(etter)396
b(analogue)h(to)f(the)g(situation)h(in)f(SFE-completeness)h(is)0
34664 y(in)380 b(the)g(w)-34 b(orld)381 b(of)f(logspace)g(computation,)
386 b(where)380 b(the)g(actual)g(situation)h(is)f(not)h(clear,)i
(either)d Fp(N)179 b(L)336 b Fr(=)g Fp(L)380 b Fr(or)g(all)0
36169 y(logspace)404 b(complete)g(functions)h(are)f(not)h(in)f(L)g(\()p
Fp(N)179 b(L)o Fr(-C)270 b Fp(\\)f(L)337 b Fr(=)g Fp(;)p
Fr(\).)1882 37675 y(This)380 b(pap)34 b(er)380 b(aims)g(at)g(\257nding)
h(a)f(simple)f(criterion)g(as)h(to)g(what)h(functions)h(are)d(in)h
Fp(S)91 b(F)120 b(E)108 b Fr(-C)q(.)530 b(The)381 b(common)0
39180 y(metho)34 b(d)355 b(of)g(pro)-34 b(ving)355 b(that)h(a)e
(function)i(is)e(SFE-complete)h(is)f(sho)-34 b(wing)356
b(a)f(secure)f(reduction)g(from)h(a)g(previously)0 40686
y(kno)-34 b(wn)405 b(complete)f(function,)h(namely)-101
b(,)404 b(from)g(Oblivious)g(T)-101 b(ransfer.)0 43932
y Fn(2.3)1495 b(Oblivious)500 b(T)-125 b(ransfer)0 46220
y Fr(A)358 b(cen)-34 b(tral)358 b(comp)34 b(onen)-34
b(t)359 b(in)f(the)g(construction)h(of)g(SFE)f(proto)34
b(cols)358 b(is)f(the)i(Oblivious)e(T)-101 b(ransfer)359
b(\(OT\))f(proto)34 b(col.)0 47725 y(OT)396 b(refers)f(to)h(sev)-34
b(eral)395 b(equiv)-67 b(alen)-34 b(t)395 b(v)-34 b(ersions)396
b(of)g(t)-34 b(w)g(o-part)g(y)398 b(proto)34 b(cols.)536
b(F)-101 b(or)395 b(example,)i(an)f(imp)34 b(ortan)-34
b(t)397 b(form)-34 b(u-)0 49231 y(lation)374 b(is)f(the)h(1-2-OT)g
(\(due)g(to)g([14]\),)379 b(where)373 b(Bob)h(has)g(t)-34
b(w)g(o)375 b(secret)e(bits)h Fq(b)34758 49413 y Fo(0)35284
49231 y Fq(;)202 b(b)36343 49413 y Fo(1)37242 49231 y
Fr(and)374 b(Alice)e(has)i(a)g(c)-34 b(hoice)373 b(bit)h
Fq(c)p Fr(.)0 50736 y(A)-34 b(t)396 b(the)h(end)f(of)g(the)g(proto)34
b(col)395 b(Alice)g(learns)g Fq(b)21375 50918 y Fm(c)22234
50736 y Fr(but)i(learns)e(nothing)i(ab)34 b(out)397 b
Fq(b)36367 50918 y Fo(1)p FC(\241)p Fm(c)38032 50736
y Fr(,)g(while)f(Bob)f(learns)h(nothing)0 52242 y(ab)34
b(out)418 b(Alice's)e(c)-34 b(hoice.)577 b(In)417 b(principal,)j(w)-34
b(e)418 b(can)f(view)g(a)g(1-2-OT)h(proto)34 b(col)417
b(through)h(the)g(framew)-34 b(ork)417 b(of)h(SFE.)0
53747 y(Namely)-101 b(,)403 b(an)i(SFE)f(proto)34 b(col)404
b(for)g(the)h(function)g Fq(f)130 b Fr(\()p Fq(c;)202
b Fr(\()p Fq(b)25747 53929 y Fo(0)26274 53747 y Fq(;)g(b)27333
53929 y Fo(1)27859 53747 y Fr(\)\))337 b(=)g Fq(b)30938
53929 y Fm(c)31401 53747 y Fr(.)1882 55253 y(Another)466
b(imp)34 b(ortan)-34 b(t)467 b(v)-34 b(ersion)466 b(is)f(kno)-34
b(wn)468 b(as)d(Noisy-OT)h(or)g(Rabin-OT)g(\(due)h(to)f(Rabin)h
([42]\),)480 b(and)467 b(w)-34 b(as)0 56758 y(sho)g(wn)525
b(to)g(b)34 b(e)523 b(equiv)-67 b(alen)-34 b(t)523 b(to)i(1-2-OT)f(in)g
([11)o(].)898 b(This)524 b(v)-34 b(ersion)523 b(go)34
b(es)524 b(as)g(follo)-34 b(ws:)778 b(Bob)524 b(holds)h(a)e(secret)h
(bit)0 58264 y Fq(b)p Fr(.)863 b(After)512 b(the)h(proto)34
b(col,)538 b(Alice)511 b(receiv)-34 b(es)511 b(the)i(bit)f
Fq(b)h Fr(with)g(probabilit)-34 b(y)34679 57786 y Fo(1)p
34679 57984 471 49 v 34679 58682 a(2)35795 58264 y Fr(\(with)513
b(probabilit)-34 b(y)45575 57786 y Fo(1)p 45575 57984
V 45575 58682 a(2)46690 58264 y Fr(she)512 b(learns)0
59769 y(nothing\),)406 b(and)e(Bob)h(do)34 b(esn't)404
b(kno)-34 b(w)405 b(if)f(Alice)f(receiv)-34 b(ed)403
b(the)h(bit)h(or)f(not.)1882 61275 y(In)349 b(this)i(pap)34
b(er)349 b(w)-34 b(e)350 b(use)g(a)g(sligh)-34 b(tly)349
b(di\256eren)-34 b(t)350 b(v)-34 b(ersion)350 b(that)g(w)-34
b(e)351 b(call)d(Naiv)-34 b(e-OT,)349 b(that)i(is)f(clearly)d(equiv)-67
b(alen)-34 b(t)0 62780 y(to)367 b(the)h(Rabin-OT)g(in)f(the)g
(semi-honest)h(mo)34 b(del.)526 b(In)367 b(this)g(v)-34
b(ersion)367 b(Alice)f(simply)g(c)-34 b(ho)34 b(oses)368
b(whether)f(to)h(receiv)-34 b(e)0 64286 y(Bob's)404 b(secret)f(bit)i
(or)f(not,)g(while)g(Bob)g(learns)g(nothing)i(of)e(this)h(c)-34
b(hoice.)0 66787 y Fj(De\257nition)466 b(2.4)606 b Fk(A)434
b Fj(Naiv)-39 b(e-OT)433 b Fk(pr)-62 b(oto)g(c)g(ol)431
b(is)i(an)g(SFE)i(pr)-62 b(oto)g(c)g(ol)431 b(for)i(the)g(function:)
19541 70212 y Fq(f)130 b Fr(\()p Fq(c;)202 b(b)p Fr(\))338
b(=)24407 68503 y Fd(\275)26081 69457 y Fq(b)2425 b(c)336
b Fr(=)h(1)25870 70963 y Fp(?)2213 b Fq(c)336 b Fr(=)h(0)25394
75721 y(13)p eop
%%Page: 14 15
14 14 bop 1882 818 a Fr(As)467 b(men)-34 b(tioned)468
b(b)34 b(efore,)482 b(the)467 b(imp)34 b(ortance)467
b(of)g(OT)g(stems)h(from)f(the)g(fact)g(that)h(it)f(is)g(complete)g
(for)g(SFE.)0 2323 y(This)424 b(w)-34 b(as)425 b(sho)-34
b(wn)425 b(in)f(an)g(arra)-34 b(y)423 b(of)h(w)-34 b(orks,)429
b(originally)422 b(attributed)j(to)f([43,)g(45])f(with)h(a)g(line)f(of)
h(further)h(w)-34 b(orks)0 3829 y(for)413 b(di\256eren)-34
b(t)413 b(mo)34 b(dels)412 b(of)h(secure)f(computation,)k(e.g.)564
b([21,)412 b(24,)g(30].)564 b(In)413 b(turn,)i(OT)e(can)g(b)34
b(e)412 b(constructed)i(from)0 5334 y(trap)34 b(do)g(or)370
b(p)34 b(erm)-34 b(utations)371 b(and)g(public)f(k)-34
b(ey)369 b(encryption)h(with)h(particular)f(\\niceness")g(prop)34
b(erties)369 b([14,)h(19,)f(17])0 6839 y(and)523 b(v)-67
b(arious)522 b(sp)34 b(eci\257c)521 b(in)-34 b(tractabilit)g(y)523
b(assumptions)h(\(e.g.)892 b(the)523 b(Di\261e)e(Helman)i(assumptions)h
([3)o(,)e(39]\).)893 b(In)0 8345 y(con)-34 b(trast,)639
b(OT)591 b(cannot)h(b)34 b(e)590 b(reduced)h(in)g(a)g(blac)-34
b(k-b)34 b(o)-34 b(x)591 b(manner)h(to)f(w)-34 b(eak)g(er)591
b(primitiv)-34 b(es)591 b(suc)-34 b(h)592 b(as)f(one-w)-34
b(a)g(y)0 9850 y(functions,)405 b(general)f(public)g(k)-34
b(ey)404 b(encryption)g(or)g(ev)-34 b(en)404 b(trap)34
b(do)g(or)404 b(one-to-one)h(functions)h([29)o(,)e(27,)g(17].)0
13654 y Fs(3)1793 b(Completeness)0 16359 y Fr(Our)492
b(main)f(result)h(presen)-34 b(ts)493 b(criteria)d(for)i(functions)h
(to)f(b)34 b(eing)492 b(complete)f(or)h(in)f(E\256-)q
Fp(S)91 b(F)120 b(E)108 b Fr(.)801 b(While)491 b(the)h(t)-34
b(w)g(o)0 17865 y(criteria)569 b(are)g(not)i(complemen)-34
b(tary)570 b(of)h(eac)-34 b(h)570 b(other,)612 b(they)570
b(are)f(in)h(a)g(sense)h(a)f(\\strong)g(negation")h(of)g(eac)-34
b(h)0 19370 y(other.)639 b(F)-101 b(or)437 b(simplicit)-34
b(y)438 b(of)f(exp)34 b(osition,)446 b(the)438 b(criteria)e(w)-34
b(e)438 b(presen)-34 b(t)438 b(in)g(Sections)g(3)f(and)i(4)e(are)g(not)
h(as)g(tigh)-34 b(t)439 b(as)0 20876 y(p)34 b(ossible,)362
b(and)352 b(giv)-34 b(e)351 b(results)h(for)g(the)g(most)g(natural)h
(de\257nition)f(of)h(SFE.)e(In)h(Section)g(6)g(w)-34
b(e)352 b(discuss)g(alternativ)-34 b(e)0 22381 y(de\257nitions)405
b(that)h(bring)e(us)h(closer)e(to)h(a)g(tigh)-34 b(t)405
b(c)-34 b(haracterization.)0 25113 y Fj(De\257nition)466
b(3.1)f(\(Computational)g(Ro)-39 b(w)465 b(Non-T)-116
b(ransitivit)-39 b(y:\))606 b Fk(We)324 b(say)g(that)f(a)h(function)f
Fq(f)468 b Fr(:)336 b Fp(f)p Fr(0)p Fq(;)202 b Fr(1)p
Fp(g)50499 24673 y FC(\244)51057 25113 y Fp(\243)0 26619
y(f)p Fr(0)p Fq(;)g Fr(1)p Fp(g)2963 26179 y FC(\244)3825
26619 y Fp(!)337 b(f)p Fr(0)p Fq(;)202 b Fr(1)p Fp(g)8337
26179 y FC(\244)9256 26619 y Fk(is)393 b Fj(\(Computational\))415
b(Ro)-39 b(w)414 b(Non-T)-116 b(ransitiv)-39 b(e)393
b Fk(if)g(ther)-62 b(e)392 b(exist)g(p)-62 b(olynomial-time)390
b(sam-)0 28124 y(plable)415 b(distributions)f Fq(D)11364
28306 y Fm(x)11948 28124 y Fr(\()p Fp(\242)p Fr(\))p
Fq(;)202 b(D)14770 28306 y Fm(y)15322 28124 y Fr(\()p
Fp(\242)p Fr(\))418 b Fk(and)f(ther)-62 b(e)415 b(exists)h(a)h(p)-62
b(olynomial)415 b Fq(p)p Fr(\()p Fp(\242)p Fr(\))i Fk(such)f(that)f
(for)i(every)e(PPTMA)j Fq(M)132 b Fk(,)0 29630 y(for)433
b(al)62 b(l)433 b(auxiliary)e(information)h Fq(w)369
b Fp(2)337 b(f)p Fr(0)p Fq(;)202 b Fr(1)p Fp(g)20729
29190 y FC(\244)21689 29630 y Fk(and)433 b(for)g(al)62
b(l)433 b(but)f(\257nitely)h(many)g Fq(n)p Fk(:)13417
32761 y Fr(Pr)o([)p Fq(M)132 b Fr(\()p Fq(x)17525 32943
y Fo(0)18051 32761 y Fq(;)202 b(x)19283 32943 y Fo(1)19808
32761 y Fq(;)g(f)130 b Fr(\()p Fq(x)22234 32943 y Fo(0)22761
32761 y Fq(;)202 b(y)43 b Fr(\))p Fq(;)202 b(w)33 b Fr(\))337
b(=)f Fq(f)130 b Fr(\()p Fq(x)29822 32943 y Fo(1)30349
32761 y Fq(;)202 b(y)43 b Fr(\)])338 b Fq(<)e Fr(1)269
b Fp(\241)37007 31941 y Fr(1)p 36170 32482 2281 49 v
36170 33592 a Fq(p)p Fr(\()p Fq(n)p Fr(\))0 36132 y Fk(Wher)-62
b(e)432 b(the)h(pr)-62 b(ob)g(ability)430 b(is)j(taken)f(over)h
Fq(x)19607 36314 y Fo(0)20132 36132 y Fq(;)202 b(x)21364
36314 y Fo(1)22226 36132 y Fp(2)337 b Fq(D)24375 36314
y Fm(x)24960 36132 y Fr(\(1)26037 35692 y Fm(n)26663
36132 y Fr(\))p Fq(;)202 b(y)381 b Fp(2)337 b Fq(D)30797
36314 y Fm(y)31348 36132 y Fr(\(1)32425 35692 y Fm(n)33052
36132 y Fr(\))434 b Fk(and)f(the)g(r)-62 b(andomness)432
b(of)h(M.)47853 35692 y Fo(21)1882 38864 y Fr(W)-101
b(e)364 b(note)i(that)g(the)f(notion)h(of)f(hardness)h(in)f(ro)-34
b(w)365 b(non-transitivit)-34 b(y)366 b(is)f(v)-34 b(ery)364
b(di\256eren)-34 b(t)365 b(than)i(that)f(of)f(a)g(one-)0
40370 y(w)-34 b(a)g(y)454 b(function.)688 b(T)-101 b(o)453
b(b)34 b(egin)454 b(with,)466 b(ro)-34 b(w)454 b(non-transitivit)-34
b(y)454 b(guaran)-34 b(tees)455 b(that)f(it)f(is)h(hard)f(to)h(compute)
g Fq(f)130 b Fr(\()p Fq(x)49825 40552 y Fo(1)50352 40370
y Fq(;)202 b(y)43 b Fr(\))0 41875 y(giv)-34 b(en)427
b Fq(f)130 b Fr(\()p Fq(x)5075 42057 y Fo(0)5602 41875
y Fq(;)202 b(y)43 b Fr(\),)433 b(but)427 b(giv)-34 b(es)427
b(no)g(guaran)-34 b(tee)428 b(that)g(it)f(is)f(easy)h(to)g(compute)g
Fq(f)130 b Fr(\()p Fq(x)36688 42057 y Fo(0)37215 41875
y Fq(;)202 b(y)43 b Fr(\))428 b(from)f Fq(f)130 b Fr(\()p
Fq(x)44065 42057 y Fo(1)44592 41875 y Fq(;)202 b(y)43
b Fr(\),)433 b(th)-34 b(us,)433 b(this)0 43381 y(is)417
b(a)g(computation)h(that)g(migh)-34 b(t)418 b(b)34 b(e)417
b(hard)g(in)g(b)34 b(oth)418 b(w)-34 b(a)g(ys)417 b(\(ev)-34
b(en)418 b(when)f Fq(x)34331 43563 y Fo(0)35274 43381
y Fr(and)g Fq(x)38336 43563 y Fo(1)39279 43381 y Fr(are)f(\257xed)h(v)
-67 b(alues)416 b(and)i(not)0 44886 y(random)489 b(v)-67
b(ariables\).)790 b(F)-101 b(urthermore,)509 b(unlik)-34
b(e)488 b(one-w)-34 b(a)g(y)489 b(functions)h(where)e(one)h(is)f(giv)
-34 b(en)488 b Fq(g)43 b Fr(\()p Fq(y)g Fr(\))490 b(and)f(ask)-34
b(ed)489 b(to)0 46392 y(\257nd)455 b(an)-34 b(y)453 b
Fq(z)507 b Fr(suc)-34 b(h)454 b(that)g Fq(g)43 b Fr(\()p
Fq(z)53 b Fr(\))421 b(=)d Fq(g)43 b Fr(\()p Fq(y)g Fr(\),)468
b(here)453 b(w)-34 b(e)453 b(ask)h(only)f(that)h(it)g(is)f(imp)34
b(ossible)453 b(to)h(\257nd)g(the)g(sp)34 b(eci\257c)453
b(v)-67 b(alue)0 47897 y Fq(f)130 b Fr(\()p Fq(x)1887
48079 y Fo(1)2414 47897 y Fq(;)202 b(y)43 b Fr(\))470
b(from)g Fq(f)130 b Fr(\()p Fq(x)9349 48079 y Fo(0)9876
47897 y Fq(;)202 b(y)43 b Fr(\),)486 b(while)469 b(putting)j(no)d
(restriction)h(on)f(the)h(abilit)-34 b(y)470 b(of)g(\257nding)h(a)e(v)
-67 b(alue)469 b Fq(f)130 b Fr(\()p Fq(x)47020 48079
y Fo(1)47547 47897 y Fq(;)202 b(z)53 b Fr(\))469 b(with)0
49403 y Fq(f)130 b Fr(\()p Fq(x)1887 49585 y Fo(0)2414
49403 y Fq(;)202 b(z)53 b Fr(\))337 b(=)f Fq(f)130 b
Fr(\()p Fq(x)7544 49585 y Fo(0)8071 49403 y Fq(;)202
b(y)43 b Fr(\).)538 b(As)400 b(a)g(result,)g(ro)-34 b(w)400
b(non-transitivit)-34 b(y)401 b(do)34 b(es)400 b(not)h(ev)-34
b(en)399 b(imply)h(the)g(existence)f(of)h(one-w)-34 b(a)g(y)0
50908 y(functions,)461 b(and)450 b(its)f(hardness)h(can)f(come)f(also)h
(from)g(a)g(non)h(computational)g(source)f(\(for)g(example)g(the)g(OR)0
52413 y(of)404 b(t)-34 b(w)g(o)406 b(bits)f(is)f(a)g(ro)-34
b(w)404 b(non-transitiv)-34 b(e)405 b(function\).)0 55146
y Fj(Theorem)464 b(3.1)606 b Fk(If)434 b(a)f(function)g
Fq(f)564 b Fk(is)433 b(c)-62 b(omputational)430 b(r)-62
b(ow)434 b(non-tr)-62 b(ansitive)431 b(then)i(it)g(is)g(c)-62
b(omplete)432 b(for)h(SFE.)1882 57878 y Fr(T)-101 b(o)448
b(pro)-34 b(v)g(e)448 b(the)h(theorem)f(w)-34 b(e)448
b(sho)-34 b(w)449 b(a)f(construction)h(of)f(an)g(OT)g(proto)34
b(col)448 b(using)h(access)e(to)h(an)g(ideal)g(b)34 b(o)-34
b(x)0 59383 y(for)381 b(ev)-67 b(aluating)380 b(a)g(non-transitiv)-34
b(e)382 b Fq(f)130 b Fr(.)532 b(Rather)381 b(than)g(directly)f(sho)-34
b(wing)382 b(this,)j(w)-34 b(e)381 b(\257rst)g(construct)h(a)e(w)-34
b(eak)g(ened)0 60889 y(implemen)g(tation)565 b(of)g(Naiv)-34
b(e-OT)564 b(that)h(is)f(later)g(sho)-34 b(wn)565 b(to)g(imply)f(OT.)g
(This)g(is)g(called)g(W)-101 b(eak-OT)563 b(and)i(is)0
62394 y(essen)-34 b(tially)404 b(a)g(relaxation)f(of)i(the)f(securit)
-34 b(y)404 b(restrictions)g(on)h(the)f(receiv)-34 b(er.)0
64811 y Fj(De\257nition)466 b(3.2)606 b Fk(A)398 b Fj(W)-116
b(eak)418 b(implemen)-39 b(tation)420 b(of)g(Naiv)-39
b(e-OT)418 b(\(W)-116 b(eak-OT)418 b(in)i(short\))397
b Fk(c)-62 b(onsists)396 b(of)g(two)0 66316 y(p)-62 b(arties,)419
b(the)f(sender)g(and)h(the)f(r)-62 b(e)g(c)g(eiver.)550
b(The)418 b(sender)g(holds)f(a)i(se)-62 b(cr)g(et)417
b(bit)h Fq(b)i Fk(and)e(the)g(r)-62 b(e)g(c)g(eiver)417
b(holds)g(a)h(choic)-62 b(e)0 67822 y(bit)433 b Fq(c)p
Fk(.)556 b(Both)433 b(p)-62 b(arties)432 b(have)f(a)j(se)-62
b(curity)431 b(p)-62 b(ar)g(ameter)431 b Fq(n)p Fk(.)557
b(A)-31 b(t)433 b(the)g(end)g(of)g(the)g(pr)-62 b(oto)g(c)g(ol,)430
b(the)j(fol)62 b(lowing)432 b(holds:)1433 70239 y(1.)605
b(Corr)-62 b(e)g(ctness:)556 b(If)434 b Fq(c)336 b Fr(=)g(1)434
b Fk(then)f(the)f(r)-62 b(e)g(c)g(eiver)432 b(outputs)f(bit)h(b.)p
0 71260 20800 45 v 976 71977 a Fl(21)1843 72400 y Fv(Recall)335
b(that)g(a)f(PPTMA)g(is)h(a)f(PPTM)g(with)g(auxiliary)i(information,)g
(that)f(is)g(p)28 b(olynomial)336 b(time)g(in)e(the)h(securit)-28
b(y)335 b(parameter)25394 75721 y Fr(14)p eop
%%Page: 15 16
15 15 bop 1433 818 a Fk(2.)605 b(Se)-62 b(curity:)4485
3303 y Fp(\262)606 b Fk(R)-62 b(e)g(c)g(eiver's)376 b(view:)529
b(If)379 b Fq(c)336 b Fr(=)h(0)378 b Fk(then)g(ther)-62
b(e)378 b(exists)f(a)h(p)-62 b(olynomial)376 b Fq(p)35374
2863 y FC(0)35685 3303 y Fr(\()p Fp(\242)p Fr(\))j Fk(such)e(that)g
(for)h(every)f(PPTMA)5697 4808 y(A,)433 b(for)g(al)62
b(l)433 b(auxiliary)e(information)i Fq(w)369 b Fp(2)337
b(f)p Fr(0)p Fq(;)202 b Fr(1)p Fp(g)28133 4368 y FC(\244)29092
4808 y Fk(and)433 b(for)g(al)62 b(l)433 b(but)f(\257nitely)h(many)h
Fq(n)p Fk(:)17029 7991 y Fr(Pr)o([)p Fq(A)p Fr(\()p Fe(view)22844
7481 y Fm(w)24 b(eak)g FC(\241)p Fm(O)i(T)22844 8353
y(r)g(eceiv)32 b(er)27199 7991 y Fr(\()p Fq(c;)202 b(b)p
Fr(\))p Fq(;)g(w)33 b Fr(\))336 b(=)g Fq(b)p Fr(])h Fq(<)g
Fr(1)269 b Fp(\241)38937 7171 y Fr(1)p 37945 7712 2591
49 v 37945 8823 a Fq(p)38555 8473 y FC(0)38865 8823 y
Fr(\()p Fq(n)p Fr(\))4485 11527 y Fp(\262)606 b Fk(Sender's)437
b(view:)565 b(for)438 b(every)e(PPTMA)j Fq(B)61 b Fk(,)439
b(for)e(al)62 b(l)438 b(p)-62 b(olynomials)435 b Fq(q)43
b Fr(\()p Fp(\242)p Fr(\))p Fk(,)440 b(for)d(al)62 b(l)437
b(auxiliary)f(informa-)5697 13032 y(tion)d Fq(w)369 b
Fp(2)337 b(f)p Fr(0)p Fq(;)202 b Fr(1)p Fp(g)13551 12592
y FC(\244)14510 13032 y Fk(and)434 b(for)f(al)62 b(l)432
b(but)h(\257nitely)g(many)g Fq(n)p Fk(:)17026 16215 y
Fr(Pr[)p Fq(B)61 b Fr(\()p Fe(view)22912 15705 y Fm(w)24
b(eak)g FC(\241)p Fm(O)i(T)22912 16606 y(sender)27267
16215 y Fr(\()p Fq(c;)202 b(b)p Fr(\))p Fq(;)g(w)33 b
Fr(\))336 b(=)h Fq(c)p Fr(])f Fq(<)35930 15395 y Fr(1)p
35930 15936 607 49 v 35930 17047 a(2)36938 16215 y(+)39108
15395 y(1)p 38283 15936 2255 49 v 38283 17047 a Fq(q)43
b Fr(\()p Fq(n)p Fr(\))0 19683 y(The)405 b(de\257nition)g(of)f(W)-101
b(eak-OT)404 b(is)g(justi\257ed)h(b)-34 b(y)405 b(the)f(follo)-34
b(wing)405 b(claim:)0 22467 y Fj(Lemma)464 b(3.2)606
b Fk(The)433 b(existenc)-62 b(e)432 b(of)h(We)-62 b(ak-OT)432
b(implies)g(the)g(existenc)-62 b(e)432 b(of)h(OT.)0 25252
y Fr(The)405 b(Lemma)e(is)h(pro)-34 b(v)g(ed)405 b(in)f(Section)g(7.)
539 b(W)-101 b(e)403 b(no)-34 b(w)406 b(turn)f(to)f(pro)-34
b(v)g(e)404 b(Theorem)h(3.1:)0 28036 y Fk(Pr)-62 b(o)g(of)p
Fr(.)1144 b(\(of)414 b(Theorem)g(3.1\))g(W)-101 b(e)413
b(sho)-34 b(w)416 b(a)d(construction)i(of)g(a)e(W)-101
b(eak-OT)414 b(proto)34 b(col)413 b(using)i(access)e(to)h(an)g(ideal)0
29541 y(b)34 b(o)-34 b(x)404 b(for)g(ev)-67 b(aluating)404
b(a)g(ro)-34 b(w)405 b(non-transitiv)-34 b(e)405 b Fq(f)130
b Fr(.)1882 31047 y(In)419 b(the)g(W)-101 b(eak-OT)419
b(the)g(sender)g(holds)h(a)f(secret)f(bit)h Fq(b)h Fr(and)f(the)h
(receiv)-34 b(er)417 b(holds)i(a)g(c)-34 b(hoice)419
b(bit)g Fq(c)p Fr(.)583 b(The)419 b(t)-34 b(w)g(o)0 32552
y(sides)400 b(call)e(a)i(b)34 b(o)-34 b(x)399 b(\246)9355
32749 y Fm(f)10360 32552 y Fr(for)h(the)g(non-transitiv)-34
b(e)400 b(function)h Fq(f)130 b Fr(.)538 b(Let)399 b(the)h(receiv)-34
b(er)398 b(pla)-34 b(y)400 b(Alice)e(\(holds)j Fq(x)p
Fr(\))e(and)i(the)0 34058 y(sender)j(pla)-34 b(y)404
b(Bob)h(\(holds)g Fq(y)43 b Fr(\).)p 1882 36518 51723
45 v 1860 65240 45 28723 v 2546 39417 a Fj(W)-116 b(eak-OT)8406
38977 y Fo(\246)9111 39133 y Fc(f)9695 39417 y Fr(\()p
Fq(c;)202 b(b)p Fr(\))p Fj(:)4027 41919 y Fr(1.)606 b(The)475
b(sender)f(c)-34 b(ho)34 b(oses)474 b(random)h Fq(x)21593
42101 y Fo(0)22118 41919 y Fq(;)202 b(x)23350 42101 y
Fo(1)24350 41919 y Fr(according)474 b(to)g(the)h(distribution)g
Fq(D)41270 42101 y Fm(x)41854 41919 y Fr(\(1)42931 41479
y Fm(n)43558 41919 y Fr(\))g(and)f(sends)h(them)5576
43424 y(to)405 b(the)f(receiv)-34 b(er.)4027 45926 y(2.)606
b(The)405 b(receiv)-34 b(er)402 b(and)j(sender)f(join)-34
b(tly)405 b(call)e(the)i(ideal)e(b)34 b(o)-34 b(x)404
b(\246)32899 46123 y Fm(f)33505 45926 y Fr(.)6182 48428
y(The)h(receiv)-34 b(er)402 b(uses)j Fq(x)336 b Fr(=)g
Fq(x)18699 48610 y Fm(c)6182 50376 y Fr(The)405 b(sender)f(c)-34
b(ho)34 b(oses)404 b(a)g(random)h Fq(y)448 b Fr(according)404
b(to)g Fq(D)31221 50558 y Fm(y)31773 50376 y Fr(\(1)32850
49936 y Fm(n)33477 50376 y Fr(\).)6182 52324 y(The)h(receiv)-34
b(er)402 b(learns)i Fq(f)130 b Fr(\()p Fq(x;)202 b(y)43
b Fr(\).)4027 54826 y(3.)606 b(The)405 b(sender:)6182
57328 y(Computes)h Fq(z)390 b Fr(=)336 b Fq(f)130 b Fr(\()p
Fq(x)16033 57510 y Fo(1)16560 57328 y Fq(;)202 b(y)43
b Fr(\))405 b(and)g(c)-34 b(ho)34 b(oses)404 b(a)g(string)h
Fq(r)437 b Fr(uniformly)404 b(at)h(random)g(in)f Fp(f)p
Fr(0)p Fq(;)202 b Fr(1)p Fp(g)46563 56888 y FC(j)p Fm(z)37
b FC(j)47616 57328 y Fr(.)6182 59276 y(Sends)344 b(to)e(the)h(receiv)
-34 b(er)340 b Fq(r)376 b Fr(and)343 b Fp(h)p Fq(z)53
b(;)202 b(r)34 b Fp(i)146 b(\251)g Fq(b)p Fr(,)354 b(where)342
b Fp(h)p Fq(z)53 b(;)202 b(r)34 b Fp(i)342 b Fr(denotes)h(the)g(inner)f
(pro)34 b(duct)343 b(of)f(the)h(strings)8243 60781 y
Fq(z)457 b Fr(and)405 b Fq(r)438 b Fr(mo)34 b(d)404 b(2)g(\(in)g(other)
h(w)-34 b(ords)405 b(this)g(is)e(the)i(Goldreic)-34 b(h-Levin)403
b(predicate\).)4027 63283 y(4.)606 b(If)404 b Fq(c)337
b Fr(=)f(1)404 b(then)h(the)g(receiv)-34 b(er)402 b(retriev)-34
b(es)403 b(the)h(bit)h Fq(b)f Fr(b)-34 b(y)405 b(computing)g
Fp(h)p Fq(f)130 b Fr(\()p Fq(x;)202 b(y)43 b Fr(\))p
Fq(;)202 b(r)34 b Fp(i)339 b Fr(=)d Fp(h)p Fq(z)53 b(;)202
b(r)34 b Fp(i)p Fr(.)p 53582 65240 V 1882 65285 51723
45 v 1882 67701 a(W)-101 b(e)403 b(sho)-34 b(w)406 b(that)f(the)g(ab)34
b(o)-34 b(v)g(e)404 b(proto)34 b(col)404 b(constitutes)h(of)g(a)f(W)
-101 b(eak-OT)403 b(proto)34 b(col:)0 70895 y Fj(Correctness:)1212
b Fr(If)464 b Fq(c)437 b Fr(=)g(1,)479 b(then)465 b(the)g(receiv)-34
b(er)463 b(learns)h Fq(f)130 b Fr(\()p Fq(x;)202 b(y)43
b Fr(\))439 b(=)e Fq(f)130 b Fr(\()p Fq(x)34094 71077
y Fo(1)34621 70895 y Fq(;)202 b(y)43 b Fr(\))438 b(=)f
Fq(z)53 b Fr(,)479 b(and)466 b(can)e(therefore)g(learn)0
72400 y Fp(h)p Fq(z)53 b(;)202 b(r)34 b Fp(i)404 b Fr(and)h(can)f
(retriev)-34 b(e)403 b(the)i(bit)f Fq(b)p Fr(.)25394
75721 y(15)p eop
%%Page: 16 17
16 16 bop 0 818 a Fj(Securit)-39 b(y:)1818 3319 y Fp(\262)606
b Fr(Sender's)397 b(view:)535 b(The)397 b(sender's)g(view)f(consists)h
(of)g(his)g(o)-34 b(wn)398 b(messages)f(as)g(he)g(only)f(sends)i
(messages.)536 b(In)3030 4825 y(the)425 b(access)e(to)h(the)h(ideal)e
(b)34 b(o)-34 b(x)424 b(he)g(only)g(sees)g(his)g(input)h(and)g(do)34
b(es)424 b(not)g(see)g(the)g(output.)600 b(He)424 b(therefore)3030
6330 y(has)405 b(no)f(information)h(at)g(all)e(regarding)h(the)h(bit)f
Fq(c)p Fr(.)1818 8832 y Fp(\262)606 b Fr(Receiv)-34 b(er's)541
b(view:)813 b(If)542 b Fq(c)566 b Fr(=)g(0,)576 b(then)543
b(the)f(receiv)-34 b(er)540 b(learns)h Fq(f)130 b Fr(\()p
Fq(x;)202 b(y)43 b Fr(\))569 b(=)d Fq(f)130 b Fr(\()p
Fq(x)38723 9014 y Fo(0)39249 8832 y Fq(;)202 b(y)43 b
Fr(\).)953 b(W)-101 b(e)541 b(sho)-34 b(w)543 b(that)g(the)3030
10337 y(receiv)-34 b(er)425 b(cannot)j(use)f(this)g(information)g(to)h
(predict)e(the)h(bit)h Fp(h)p Fq(f)130 b Fr(\()p Fq(x)34609
10519 y Fo(1)35136 10337 y Fq(;)202 b(y)43 b Fr(\))p
Fq(;)202 b(r)34 b Fp(i)427 b Fr(\(and)h(equiv)-67 b(alen)-34
b(tly)425 b(the)j(bit)3030 11843 y Fq(b)p Fr(\),)355
b(with)342 b(probabilit)-34 b(y)343 b(b)34 b(etter)341
b(than)i(1)145 b Fp(\241)22481 11366 y Fo(1)p 21829 11564
1777 49 v 21829 12277 a Fm(p)p Fo(\()p Fm(n)p Fo(\))24079
11843 y Fr(for)342 b(some)g(p)34 b(olynomial)341 b Fq(p)p
Fr(\()p Fp(\242)p Fr(\).)518 b(This)343 b(is)e(equiv)-67
b(alen)-34 b(t)342 b(the)g(w)-34 b(eak)3030 13348 y(v)g(ersion)516
b(of)h(Goldreic)-34 b(h-Levin's)515 b(hardcore)h(bit)h(where)f(it)g(is)
g(only)g(required)f(to)i(sho)-34 b(w)518 b(that)f(the)g(bit)f(is)3030
14854 y(somewhat)406 b(hard)e(to)h(predict.)538 b(The)405
b(statemen)-34 b(t)405 b(is)f(formalized)g(and)h(pro)-34
b(v)g(ed)405 b(in)f(the)g(follo)-34 b(wing)405 b(lemma.)0
17688 y Fj(Lemma)464 b(3.3)606 b Fk(Supp)-62 b(ose)400
b Fq(f)534 b Fk(is)401 b(r)-62 b(ow)403 b(non-tr)-62
b(ansitive.)545 b(Then)402 b(ther)-62 b(e)401 b(exists)g(a)h(p)-62
b(olynomial)400 b Fq(p)p Fr(\()p Fp(\242)p Fr(\))j Fk(such)d(that)h
(for)h(al)62 b(l)0 19193 y(PPTMA)434 b(A,)g(for)f(al)62
b(l)432 b(auxiliary)g(information)g Fq(w)369 b Fp(2)337
b(f)p Fr(0)p Fq(;)202 b Fr(1)p Fp(g)27369 18753 y FC(\244)28328
19193 y Fk(and)434 b(for)f(al)62 b(l)432 b(but)h(\257nitely)g(many)g
Fq(n)p Fk('s:)12059 22426 y Fr(Pr[)p Fq(A)p Fr(\()p Fq(x)15769
22608 y Fo(0)16295 22426 y Fq(;)202 b(x)17527 22608 y
Fo(1)18052 22426 y Fq(;)g(f)130 b Fr(\()p Fq(x)20478
22608 y Fo(0)21004 22426 y Fq(;)202 b(y)43 b Fr(\))p
Fq(;)202 b(r)-34 b(;)202 b(w)33 b Fr(\))337 b(=)g Fp(h)p
Fq(f)130 b Fr(\()p Fq(x)29589 22608 y Fo(1)30116 22426
y Fq(;)202 b(y)43 b Fr(\))p Fq(;)202 b(r)34 b Fp(i)p
Fr(])337 b Fq(<)f Fr(1)270 b Fp(\241)38365 21606 y Fr(1)p
37528 22147 2281 49 v 37528 23257 a Fq(p)p Fr(\()p Fq(n)p
Fr(\))0 25993 y Fk(Wher)-62 b(e)437 b(the)g(pr)-62 b(ob)g(ability)434
b(is)k(taken)f(over)f Fq(x)19633 26175 y Fo(0)20159 25993
y Fq(;)202 b(x)21391 26175 y Fo(1)22261 25993 y Fp(2)345
b Fq(D)24418 26175 y Fm(x)25003 25993 y Fr(\(1)26080
25553 y Fm(n)26706 25993 y Fr(\))p Fq(;)202 b(y)389 b
Fp(2)345 b Fq(D)30856 26175 y Fm(y)31408 25993 y Fr(\(1)32485
25553 y Fm(n)33111 25993 y Fr(\))p Fq(;)202 b(r)379 b
Fp(2)345 b(f)p Fr(0)p Fq(;)202 b Fr(1)p Fp(g)39163 25553
y FC(j)p Fm(f)98 b Fo(\()p Fm(x)40870 25676 y Fl(1)41330
25553 y Fm(;y)32 b Fo(\))p FC(j)43209 25993 y Fk(and)438
b(the)f(r)-62 b(andom-)0 27498 y(ness)433 b(of)g Fq(A)p
Fk(.)0 30332 y(Pr)-62 b(o)g(of)p Fr(.)1144 b(Supp)34
b(ose)593 b(for)g(the)g(sak)-34 b(e)592 b(of)h(con)-34
b(tradiction)594 b(that)f(there)g(exists)f(a)h(PPTMA)f
Fq(A)h Fr(that)h(manages)f(to)0 31837 y(predict)558 b
Fp(h)p Fq(f)130 b Fr(\()p Fq(x)6623 32019 y Fo(1)7150
31837 y Fq(;)202 b(y)43 b Fr(\))p Fq(;)202 b(r)34 b Fp(i)558
b Fr(giv)-34 b(en)558 b Fq(f)130 b Fr(\()p Fq(x)16152
32019 y Fo(0)16678 31837 y Fq(;)202 b(y)43 b Fr(\))559
b(and)f Fq(r)591 b Fr(with)559 b(o)-34 b(v)g(erwhelming)558
b(probabilit)-34 b(y)-101 b(.)1000 b(More)557 b(precisely:)844
b(there)0 33343 y(exists)462 b(a)h(PPTMA)f(A)h(with)g(auxiliary)e
(information)j Fq(w)i Fp(2)434 b(f)p Fr(0)p Fq(;)202
b Fr(1)p Fp(g)30951 32903 y FC(\244)31939 33343 y Fr(suc)-34
b(h)464 b(that)f(for)g(all)f(p)34 b(olynomials)462 b
Fq(q)43 b Fr(\()p Fp(\242)p Fr(\),)478 b(for)0 34848
y(in\257nitely)404 b(man)-34 b(y)405 b(n's:)12072 38013
y(Pr)o([)p Fq(A)p Fr(\()p Fq(x)15781 38195 y Fo(0)16307
38013 y Fq(;)202 b(x)17539 38195 y Fo(1)18064 38013 y
Fq(;)g(f)130 b Fr(\()p Fq(x)20490 38195 y Fo(0)21017
38013 y Fq(;)202 b(y)43 b Fr(\))p Fq(;)202 b(r)-34 b(;)202
b(w)33 b Fr(\))337 b(=)f Fp(h)p Fq(f)130 b Fr(\()p Fq(x)29601
38195 y Fo(1)30129 38013 y Fq(;)202 b(y)43 b Fr(\))p
Fq(;)202 b(r)34 b Fp(i)p Fr(])337 b Fq(>)f Fr(1)270 b
Fp(\241)38365 37193 y Fr(1)p 37540 37735 2255 49 v 37540
38845 a Fq(q)43 b Fr(\()p Fq(n)p Fr(\))50451 38013 y(\(1\))0
41385 y(W)-101 b(e)363 b(deriv)-34 b(e)363 b(a)h(con)-34
b(tradiction)364 b(to)g(the)h(non-transitivit)-34 b(y)364
b(of)g Fq(f)495 b Fr(b)-34 b(y)364 b(presen)-34 b(ting)365
b(a)e(pro)34 b(cedure)364 b Fq(B)424 b Fr(\(with)365
b(blac)-34 b(k)364 b(b)34 b(o)-34 b(x)0 42891 y(access)403
b(to)i Fq(A)p Fr(\))f(that)i(correctly)c(computes)j Fq(f)130
b Fr(\()p Fq(x)21779 43073 y Fo(1)22306 42891 y Fq(;)202
b(y)43 b Fr(\))405 b(giv)-34 b(en)404 b Fq(f)130 b Fr(\()p
Fq(x)29410 43073 y Fo(0)29937 42891 y Fq(;)202 b(y)43
b Fr(\))405 b(with)g(v)-34 b(ery)403 b(high)i(probabilit)-34
b(y)-101 b(.)1882 44396 y(W)g(e)529 b(concen)-34 b(trate)530
b(our)g(e\256orts)g(on)h(inputs)g Fq(y)573 b Fr(on)530
b(whic)-34 b(h)531 b(the)f(algorithm)g(A)g(succeeds)g(with)g
(probabilit)-34 b(y)0 45902 y(greater)403 b(than)7311
45425 y Fo(9)p 7076 45623 941 49 v 7076 46320 a(10)8149
45902 y Fr(.)539 b(De\257ne:)10975 49249 y Fq(E)11870
49431 y Fm(n)12833 49249 y Fr(=)336 b Fp(f)p Fq(y)43
b Fp(j)p Fr(Pr[)p Fq(A)p Fr(\()p Fq(x)19402 49431 y Fo(0)19928
49249 y Fq(;)202 b(x)21160 49431 y Fo(1)21685 49249 y
Fq(;)g(f)130 b Fr(\()p Fq(x)24111 49431 y Fo(0)24638
49249 y Fq(;)202 b(y)43 b Fr(\))p Fq(;)202 b(r)-34 b(;)202
b(w)33 b Fr(\))337 b(=)f Fp(h)p Fq(f)130 b Fr(\()p Fq(x)33222
49431 y Fo(1)33750 49249 y Fq(;)202 b(y)43 b Fr(\))p
Fq(;)202 b(r)34 b Fp(i)p Fr(])337 b Fq(>)39377 48429
y Fr(9)p 39074 48970 1213 49 v 39074 50081 a(10)40419
49249 y Fp(g)0 52251 y Fr(Since)383 b Fq(A)g Fr(has)g(a)g(v)-34
b(ery)382 b(high)i(success)e(probabilit)-34 b(y)-101
b(,)388 b(the)383 b(set)g Fq(E)28236 52433 y Fm(n)29245
52251 y Fr(m)-34 b(ust)384 b(con)-34 b(tain)384 b(almost)g(all)e(of)h
(the)h(inputs.)532 b(This)0 53756 y(is)404 b(formalized)f(b)-34
b(y)405 b(the)g(follo)-34 b(wing)404 b(easy)g(claim)f(\(brough)-34
b(t)407 b(here)c(without)j(a)e(pro)34 b(of)94 b(\):)0
56258 y Fj(Claim)464 b(3.4)606 b Fk(F)-93 b(or)434 b(al)62
b(l)432 b(p)-62 b(olynomials)431 b Fq(q)43 b Fr(\()p
Fp(\242)p Fr(\))p Fk(,)435 b(for)e(al)62 b(l)433 b(but)f(\257nitely)h
(many)g Fq(n)33521 55818 y FC(0)33831 56258 y Fq(s)p
Fk(:)19031 59491 y Fr(Pr)20331 59737 y Fm(y)32 b FC(2)p
Fm(D)22227 59848 y Fc(y)22726 59737 y Fo(\(1)23562 59485
y Fc(n)24129 59737 y Fo(\))24550 59491 y Fr([)p Fq(E)25782
59673 y Fm(n)26408 59491 y Fr(])337 b Fq(>)f Fr(1)269
b Fp(\241)31406 58671 y Fr(1)p 30581 59212 2255 49 v
30581 60322 a Fq(q)43 b Fr(\()p Fq(n)p Fr(\))0 62862
y(The)531 b(claim)e(is)i(sp)34 b(eci\257cally)529 b(true)h(for)h
Fq(q)43 b Fr(\()p Fq(n)p Fr(\))548 b(=)f(2)p Fq(p)p Fr(\()p
Fq(n)p Fr(\),)561 b(where)531 b Fq(p)p Fr(\()p Fp(\242)p
Fr(\))f(is)h(the)f(p)34 b(olynomial)530 b(giv)-34 b(en)531
b(b)-34 b(y)530 b(the)h(non-)0 64368 y(transitivit)-34
b(y)404 b(of)h Fq(f)130 b Fr(.)539 b(So)405 b(Pr)12269
64615 y Fm(y)32 b FC(2)p Fm(D)14165 64726 y Fc(y)14665
64615 y Fo(\(1)15501 64362 y Fc(n)16068 64615 y Fo(\))16489
64368 y Fr([)p Fq(E)17721 64550 y Fm(n)18347 64368 y
Fr(])336 b Fq(>)h Fr(1)269 b Fp(\241)23408 63891 y Fo(1)p
22520 64089 2247 49 v 22520 64802 a(2)p Fm(p)p Fo(\()p
Fm(n)p Fo(\))25304 64368 y Fr(for)404 b(all)g(but)h(\257nitely)f(man)
-34 b(y)405 b Fq(n)p Fr(.)1882 66043 y(Next)330 b(w)-34
b(e)330 b(in)-34 b(tro)34 b(duce)331 b(the)f(pro)34 b(cedure)330
b(B)g(that)h(uses)f Fq(A)g Fr(to)h(compute)g Fq(f)130
b Fr(\()p Fq(x)34982 66225 y Fo(1)35508 66043 y Fq(;)202
b(y)43 b Fr(\))331 b(giv)-34 b(en)330 b Fq(f)130 b Fr(\()p
Fq(x)42464 66225 y Fo(0)42991 66043 y Fq(;)202 b(y)43
b Fr(\))331 b(for)f(all)g Fq(y)380 b Fp(2)337 b Fq(E)51374
66225 y Fm(n)0 67548 y Fr(and)c(with)f(v)-34 b(ery)331
b(high)h(probabilit)-34 b(y)333 b(\(o)-34 b(v)g(er)332
b(the)g(pro)34 b(cedure's)331 b(random)h(bits\).)516
b(Consider)332 b(a)g(sp)34 b(eci\257c)331 b Fq(y)380
b Fp(2)337 b Fq(E)48435 67730 y Fm(n)49061 67548 y Fr(.)514
b(The)0 69054 y(computation)274 b(of)f Fq(f)130 b Fr(\()p
Fq(x)10075 69236 y Fo(1)10602 69054 y Fq(;)202 b(y)43
b Fr(\))273 b(is)g(done)g(bit)g(b)-34 b(y)273 b(bit.)495
b(In)272 b(order)h(to)f(compute)i(the)f Fq(i)p Fr(th)g(bit)g(\(denoted)
h Fq(f)130 b Fr(\()p Fq(x)44902 69236 y Fo(1)45428 69054
y Fq(;)202 b(y)43 b Fr(\))47075 69236 y Fm(i)47452 69054
y Fr(\),)299 b(c)-34 b(ho)34 b(ose)0 70559 y(a)502 b(random)h
Fq(r)534 b Fp(2)500 b(f)p Fr(0)p Fq(;)202 b Fr(1)p Fp(g)11006
70120 y FC(j)p Fm(f)98 b Fo(\()p Fm(x)12713 70243 y Fl(1)13173
70120 y Fm(;y)32 b Fo(\))p FC(j)15116 70559 y Fr(and)503
b(compute)g Fq(A)p Fr(\()p Fq(x)24658 70741 y Fo(0)25184
70559 y Fq(;)202 b(x)26416 70741 y Fo(1)26941 70559 y
Fq(;)g(f)130 b Fr(\()p Fq(x)29367 70741 y Fo(0)29894
70559 y Fq(;)202 b(y)43 b Fr(\))p Fq(;)202 b(r)-34 b(;)202
b(w)33 b Fr(\))502 b(and)h Fq(A)p Fr(\()p Fq(x)39534
70741 y Fo(0)40060 70559 y Fq(;)202 b(x)41292 70741 y
Fo(1)41818 70559 y Fq(;)g(f)130 b Fr(\()p Fq(x)44244
70741 y Fo(0)44770 70559 y Fq(;)202 b(y)43 b Fr(\))p
Fq(;)202 b(r)369 b Fp(\251)334 b Fq(e)49713 70120 y Fm(i)50090
70559 y Fq(;)202 b(w)33 b Fr(\))25394 75721 y(16)p eop
%%Page: 17 18
17 17 bop 0 818 a Fr(\(where)455 b Fq(e)4591 378 y Fm(i)5421
818 y Fr(is)f(the)h(binary)f(v)-34 b(ector)454 b(with)h(one)f(in)h(the)
f Fq(i)p Fr(th)h(place)f(and)h(zero)e(in)h(all)g(others\).)690
b(If)454 b Fq(A)g Fr(succeeds)h(on)0 2323 y(b)34 b(oth)405
b(inputs)g(then:)2442 4473 y Fq(A)p Fr(\()p Fq(x)4515
4655 y Fo(0)5041 4473 y Fq(;)202 b(x)6273 4655 y Fo(1)6798
4473 y Fq(;)g(f)130 b Fr(\()p Fq(x)9224 4655 y Fo(0)9751
4473 y Fq(;)202 b(y)43 b Fr(\))p Fq(;)202 b(r)-34 b(;)202
b(w)33 b Fr(\))270 b Fp(\251)f Fq(A)p Fr(\()p Fq(x)17916
4655 y Fo(0)18442 4473 y Fq(;)202 b(x)19674 4655 y Fo(1)20199
4473 y Fq(;)g(f)130 b Fr(\()p Fq(x)22625 4655 y Fo(0)23152
4473 y Fq(;)202 b(y)43 b Fr(\))p Fq(;)202 b(r)303 b Fp(\251)269
b Fq(e)27964 3972 y Fm(i)28340 4473 y Fq(;)202 b(w)33
b Fr(\))1107 b(=)f Fp(h)p Fq(f)130 b Fr(\()p Fq(x)35765
4655 y Fo(1)36293 4473 y Fq(;)202 b(y)43 b Fr(\))p Fq(;)202
b(r)34 b Fp(i)270 b(\251)f(h)p Fq(f)130 b Fr(\()p Fq(x)43371
4655 y Fo(1)43898 4473 y Fq(;)202 b(y)43 b Fr(\))p Fq(;)202
b(r)303 b Fp(\251)270 b Fq(e)48711 3972 y Fm(i)49087
4473 y Fp(i)31358 6310 y Fr(=)1106 b Fq(f)130 b Fr(\()p
Fq(x)35294 6492 y Fo(1)35821 6310 y Fq(;)202 b(y)43 b
Fr(\))37468 6492 y Fm(i)1882 8460 y Fr(The)450 b(probabilit)-34
b(y)450 b(that)g(A)g(succeeds)f(on)h(b)34 b(oth)450 b(of)g(the)g(ab)34
b(o)-34 b(v)g(e)450 b(inputs)h(is)e(at)h(least)f(1)300
b Fp(\241)f Fr(2)h Fp(\242)f Fr(\(1)h Fp(\241)47379 7982
y Fo(9)p 47144 8180 941 49 v 47144 8878 a(10)48218 8460
y Fr(\))413 b(=)50825 7982 y Fo(8)p 50590 8180 V 50590
8878 a(10)51663 8460 y Fr(.)0 9965 y(Rep)34 b(eating)593
b(this)h Fq(n)f Fr(times)g(and)h(taking)f(a)g(ma)67 b(jorit)-34
b(y)594 b(giv)-34 b(es)593 b(the)h(bit)f Fq(f)130 b Fr(\()p
Fq(x)35475 10147 y Fo(1)36002 9965 y Fq(;)202 b(y)43
b Fr(\))37649 10147 y Fm(i)38619 9965 y Fr(with)594 b(exp)34
b(onen)-34 b(tially)592 b(small)0 11471 y(error)551 b(probabilit)-34
b(y)552 b(2)10073 11031 y FC(\241)p Fo(\255\()p Fm(n)p
Fo(\))13395 11471 y Fr(\(b)-34 b(y)553 b(a)f(Cherno\256)g(b)34
b(ound\).)984 b(This)552 b(pro)34 b(cedure)552 b(is)g(carried)f(out)h
(for)g(ev)-34 b(ery)551 b(bit)i(of)0 12976 y Fq(f)130
b Fr(\()p Fq(x)1887 13158 y Fo(1)2414 12976 y Fq(;)202
b(y)43 b Fr(\))463 b(separately)-101 b(,)476 b(ultimately)462
b(outputting)j(the)e(full)f(string)h Fq(f)130 b Fr(\()p
Fq(x)32317 13158 y Fo(1)32844 12976 y Fq(;)202 b(y)43
b Fr(\))463 b(with)g(probabilit)-34 b(y)463 b(at)f(least)g(1)309
b Fp(\241)f Fq(n)f Fp(\242)0 14482 y Fr(2)606 14042 y
FC(\241)p Fo(\255\()p Fm(n)p Fo(\))3712 14482 y Fr(=)337
b(1)202 b Fp(\241)g Fr(2)7551 14042 y FC(\241)p Fo(\255\()p
Fm(n)p Fo(\))10692 14482 y Fr(for)370 b(in\257nitely)h(man)-34
b(y)371 b Fq(n)p Fr(.)527 b(Com)-34 b(bining)372 b(this)g(with)f(Claim)
g(3.4)f(and)i(lo)34 b(oking)369 b(at)j(all)e(inputs)0
15987 y Fq(y)380 b Fp(2)337 b Fq(D)3123 16169 y Fm(y)3675
15987 y Fr(\(1)4752 15547 y Fm(n)5379 15987 y Fr(\),)360
b(the)351 b(describ)34 b(ed)349 b(e\261cien)-34 b(t)350
b(pro)34 b(cedure)349 b(B)h(computes)g Fq(f)130 b Fr(\()p
Fq(x)32324 16169 y Fo(1)32851 15987 y Fq(;)202 b(y)43
b Fr(\))351 b(from)f Fq(f)130 b Fr(\()p Fq(x)39547 16169
y Fo(0)40074 15987 y Fq(;)202 b(y)43 b Fr(\))350 b(with)h(probabilit)
-34 b(y)351 b(at)0 17493 y(least:)554 b(Pr)o([)p Fq(E)5853
17675 y Fm(n)6479 17493 y Fr(])274 b Fp(\242)h Fr(\(1)f
Fp(\241)h Fr(2)10877 17053 y FC(\241)p Fo(\255\()p Fm(n)p
Fo(\))13646 17493 y Fr(\))350 b Fq(>)f Fr(\(1)275 b Fp(\241)19350
17015 y Fo(1)p 18461 17213 2247 49 v 18461 17926 a(2)p
Fm(p)p Fo(\()p Fm(n)p Fo(\))20841 17493 y Fr(\)\(1)g
Fp(\241)g Fr(2)24488 17053 y FC(\241)p Fo(\255\()p Fm(n)p
Fo(\))27257 17493 y Fr(\))350 b Fq(>)f Fr(1)275 b Fp(\241)32254
17015 y Fo(1)p 31601 17213 1777 49 v 31601 17926 a Fm(p)p
Fo(\()p Fm(n)p Fo(\))33510 17493 y Fr(,)414 b(con)-34
b(tradicting)412 b(the)h(non-transitivit)-34 b(y)0 18998
y(of)404 b Fq(f)130 b Fr(.)51057 20503 y Fb(\244)1882
22764 y Fr(T)-101 b(o)435 b(conclude)h(the)f(pro)34 b(of)435
b(supp)34 b(ose)436 b(that)h(there)e(exists)g(a)g(PPTMA)g
Fq(A)g Fr(that)i(predicts)e(the)g(bit)h Fq(b)f Fr(from)g(the)0
24269 y(receiv)-34 b(er's)343 b(view,)357 b(with)346
b(probabilit)-34 b(y)346 b(b)34 b(etter)346 b(than)h(1)152
b Fp(\241)26080 23792 y Fo(1)p 25438 23990 1755 49 v
25438 24703 a Fm(q)32 b Fo(\()p Fm(n)p Fo(\))27671 24269
y Fr(for)345 b(all)g(p)34 b(olynomials)345 b Fq(q)43
b Fr(\()p Fp(\242)p Fr(\))347 b(and)f(for)g(in\257nitely)f(man)-34
b(y)0 25944 y(n's.)513 b(The)326 b(receiv)-34 b(er's)324
b(view)i(only)f(consists)i(of)f Fq(x)21619 26126 y Fo(0)22145
25944 y Fq(;)202 b(x)23377 26126 y Fo(1)23902 25944 y
Fq(;)g(f)130 b Fr(\()p Fq(x)26328 26126 y Fo(0)26855
25944 y Fq(;)202 b(y)43 b Fr(\))327 b(and)g(the)f(bit)h
Fp(h)p Fq(f)130 b Fr(\()p Fq(x)37283 26126 y Fo(1)37810
25944 y Fq(;)202 b(y)43 b Fr(\))p Fq(;)202 b(r)34 b Fp(i)113
b(\251)g Fq(b)p Fr(.)513 b(Th)-34 b(us)328 b Fq(A)e Fr(predicts)0
27450 y Fp(h)p Fq(f)130 b Fr(\()p Fq(x)2358 27632 y Fo(1)2885
27450 y Fq(;)202 b(r)34 b Fr(\))p Fp(i)439 b Fr(giv)-34
b(en)438 b(only)g Fq(x)11972 27632 y Fo(0)12498 27450
y Fq(;)202 b(x)13730 27632 y Fo(1)14255 27450 y Fq(;)g(f)130
b Fr(\()p Fq(x)16681 27632 y Fo(0)17208 27450 y Fq(;)202
b(y)43 b Fr(\))439 b(with)g(probabilit)-34 b(y)439 b(b)34
b(etter)438 b(than)i(1)292 b Fp(\241)37733 26972 y Fo(1)p
37091 27170 V 37091 27884 a Fm(q)32 b Fo(\()p Fm(n)p
Fo(\))39417 27450 y Fr(for)438 b(all)g(p)34 b(olynomials)438
b Fq(q)43 b Fr(\()p Fp(\242)p Fr(\),)0 28955 y(and)405
b(this)g(con)-34 b(tradicts)405 b(Lemma)e(3.3.)p 18519
28955 788 788 v 0 31215 a(Note)333 b(that)h(the)f(approac)-34
b(h)334 b(w)-34 b(e)333 b(tak)-34 b(e)333 b(in)g(our)f(pro)34
b(of)333 b(of)h(Theorem)e(3.1)h(is)f(of)h(taking)g(a)g(hardcore)g(bit)g
(of)g(a)g(function)0 32721 y(that)503 b(has)g(only)f(\\w)-34
b(eak")502 b(hardness,)528 b(and)503 b(later)e(amplifying)i(the)f
(hardness)h(b)-34 b(y)503 b(rep)34 b(etition)502 b(and)h(X)-34
b(ORing)503 b(of)0 34226 y(the)508 b(resulting)f(w)-34
b(eak)508 b(hardcore)f(bits)h(\(as)f(sho)-34 b(wn)509
b(in)f(Section)f(7\).)849 b(An)507 b(alternativ)-34 b(e)508
b(approac)-34 b(h)508 b(w)-34 b(ould)509 b(b)34 b(e)507
b(to)0 35732 y(\257rst)470 b(amplify)g(the)g(hardness)h(guaran)-34
b(teed)470 b(b)-34 b(y)471 b(the)f(ro)-34 b(w)470 b(non-transitivit)-34
b(y)471 b(of)f(the)g(function,)487 b(b)-34 b(y)470 b(considering)0
37237 y(a)530 b(concatenation)h(of)f(man)-34 b(y)530
b(indep)34 b(enden)-34 b(t)532 b(copies)d(of)h(the)h(function)g
Fq(f)130 b Fr(,)562 b(and)530 b(only)g(then)h(applying)f(the)g(GL)0
38743 y(hardcore)404 b(bit.)539 b(W)-101 b(e)403 b(note)i(that)g(the)g
(t)-34 b(w)g(o)405 b(suggested)g(metho)34 b(ds)405 b(are)f(equiv)-67
b(alen)-34 b(t.)0 41854 y Fj(Wh)-39 b(y)403 b(use)h(the)f(Goldreic)-39
b(h-Levin)404 b(Hardcore)f(Bit?)1212 b Fr(Our)350 b(c)-34
b(hoice)350 b(of)h(the)g(GL)g(hardcore)f(bit)h(stems)g(from)0
43360 y(its)549 b(generalit)-34 b(y)-101 b(,)585 b(that)550
b(is)f(the)g(fact)h(that)g(it)f(applies)h(to)f(an)-34
b(y)550 b(computation)g(that)h(is)d(hard.)974 b(This)550
b(is)f(crucial)0 44865 y(since)373 b(w)-34 b(e)374 b(kno)-34
b(w)375 b(nothing)f(in)g(adv)-67 b(ance)373 b(ab)34 b(out)375
b(the)f(sp)34 b(eci\257c)373 b(computation)i(at)f(hand)h(\(i.e.)527
b(the)374 b(computation)i(of)0 46371 y Fq(f)130 b Fr(\()p
Fq(x)1887 46553 y Fo(1)2414 46371 y Fq(;)202 b(y)43 b
Fr(\))441 b(giv)-34 b(en)440 b Fq(x)8396 46553 y Fo(0)8922
46371 y Fq(;)202 b(x)10154 46553 y Fo(1)11120 46371 y
Fr(and)441 b Fq(f)130 b Fr(\()p Fq(x)15400 46553 y Fo(0)15927
46371 y Fq(;)202 b(y)43 b Fr(\)\).)649 b(In)440 b(fact,)450
b(it)440 b(is)h(su\261cien)-34 b(t)441 b(to)g(ha)-34
b(v)g(e)441 b(an)-34 b(y)441 b(c)-34 b(hoice)440 b(of)h(a)f(function)i
Fq(h)p Fr(\()p Fq(x;)202 b(r)34 b Fr(\))0 47876 y(with)398
b(the)f(follo)-34 b(wing)397 b(prop)34 b(ert)-34 b(y:)535
b(There)397 b(exists)f(a)h(p)34 b(olynomial)396 b Fq(p)p
Fr(\()p Fp(\242)p Fr(\))h(suc)-34 b(h)398 b(that)g(the)f(input)h
Fq(x)e Fr(can)h(b)34 b(e)397 b(retriev)-34 b(ed)0 49381
y(e\261cien)g(tly)369 b(with)h(o)-34 b(v)g(erwhelming)369
b(probabilit)-34 b(y)370 b(\(allo)-34 b(wing)370 b(only)f(a)g
(negligible)f(error\))g(when)i(giv)-34 b(en)369 b(access)g(to)h(an)0
50887 y(oracle)350 b(that)i(outputs)h Fq(h)p Fr(\()p
Fq(x;)202 b(r)34 b Fr(\))351 b(correctly)f(with)h(probabilit)-34
b(y)352 b(at)f(least)g(1)163 b Fp(\241)34922 50410 y
Fo(1)p 34269 50608 1777 49 v 34269 51321 a Fm(p)p Fo(\()p
Fm(n)p Fo(\))36529 50887 y Fr(for)351 b(a)g(random)h
Fq(r)34 b Fr(.)520 b(In)-34 b(terestingly)-101 b(,)0
52562 y(w)-34 b(e)435 b(can)g(ev)-34 b(en)434 b(use)h(the)g(function)i
Fq(h)p Fr(\()p Fq(x;)202 b(i)p Fr(\))387 b(=)h Fq(x)21582
52744 y Fm(i)22392 52562 y Fr(whic)-34 b(h)436 b(is)e(v)-34
b(ery)434 b(mildly)g(hard.)631 b(W)-101 b(e)434 b(prefer)g(to)h(use)g
(the)g(GL)g(bit)0 54067 y(as)404 b(it)g(implies)g(a)g(m)-34
b(uc)g(h)405 b(more)f(e\261cien)-34 b(t)404 b(construction)h(for)f(OT.)
0 57179 y Fj(The)381 b(BMM)f(Criterion)h(Implies)g(Non-T)-116
b(ransitivit)-39 b(y)1212 b Fr(An)331 b(imp)34 b(ortan)-34
b(t)332 b(test)g(case)f(for)g(our)g(completeness)0 58684
y(criterion)513 b(is)h(whether)h(it)f(encapsulates)h(previous)f
(results,)541 b(namely)-101 b(,)541 b(the)515 b(insecure)e(minor)h
(criterion)f(of)i([2].)0 60190 y(Recall)485 b(that)i(an)f(insecure)g
(minor)f(consists)i(of)f(inputs)h Fq(x)27027 60372 y
Fo(0)27553 60190 y Fq(;)202 b(x)28785 60372 y Fo(1)29796
60190 y Fr(and)487 b Fq(y)32829 60372 y Fo(0)33355 60190
y Fq(;)202 b(y)34488 60372 y Fo(1)35499 60190 y Fr(suc)-34
b(h)487 b(that)g Fq(f)130 b Fr(\()p Fq(x)42910 60372
y Fo(0)43437 60190 y Fq(;)202 b(y)44570 60372 y Fo(0)45096
60190 y Fr(\))473 b(=)g Fq(f)130 b Fr(\()p Fq(x)49343
60372 y Fo(0)49870 60190 y Fq(;)202 b(y)51003 60372 y
Fo(1)51529 60190 y Fr(\))0 61695 y(but)405 b Fq(f)130
b Fr(\()p Fq(x)4109 61877 y Fo(1)4636 61695 y Fq(;)202
b(y)5769 61877 y Fo(0)6295 61695 y Fr(\))337 b Fp(6)p
Fr(=)f Fq(f)130 b Fr(\()p Fq(x)10269 61877 y Fo(1)10796
61695 y Fq(;)202 b(y)11929 61877 y Fo(1)12455 61695 y
Fr(\).)13263 61255 y Fo(22)1882 63201 y Fr(Cho)34 b(osing)417
b(the)h(ro)-34 b(ws)417 b Fq(x)12798 63383 y Fo(0)13324
63201 y Fq(;)202 b(x)14556 63383 y Fo(1)15498 63201 y
Fr(and)417 b(the)g(distribution)h Fq(D)27593 63383 y
Fm(y)28562 63201 y Fr(to)f(b)34 b(e)416 b(uniform)i(on)f
Fp(f)p Fq(y)39176 63383 y Fo(0)39702 63201 y Fq(;)202
b(y)40835 63383 y Fo(1)41361 63201 y Fp(g)417 b Fr(w)-34
b(e)417 b(get)g(that)h(for)f(all)0 64706 y(PPTMA)404
b(M)h(\(or)f(an)-34 b(y)404 b(function)i(at)e(all)g(in)g(this)h
(case\):)15297 67365 y(Pr[)p Fq(M)132 b Fr(\()p Fq(x)19406
67547 y Fo(0)19932 67365 y Fq(;)202 b(x)21164 67547 y
Fo(1)21689 67365 y Fq(;)g(f)130 b Fr(\()p Fq(x)24115
67547 y Fo(0)24642 67365 y Fq(;)202 b(y)43 b Fr(\))p
Fq(;)202 b(w)33 b Fr(\))337 b(=)f Fq(f)130 b Fr(\()p
Fq(x)31703 67547 y Fo(1)32230 67365 y Fq(;)202 b(y)43
b Fr(\)])337 b Fp(\267)35964 66545 y Fr(1)p 35964 67086
607 49 v 35964 68197 a(2)p 0 68825 20800 45 v 976 69541
a Fl(22)1843 69965 y Fv(W)-85 b(e)424 b(note)h(that)f(this)g
(de\257nition)h(is)f(for)g(functions)f(of)h(constan)-28
b(t)424 b(input)g(length.)704 b(The)424 b(generalization)h(to)f
(functions)g(on)g(un-)0 71182 y(b)28 b(ounded)334 b(input)g(length)g
(requires)g(to)g(ha)-28 b(v)g(e)333 b(an)h(insecure)g(minor)f(for)g(ev)
-28 b(ery)335 b(input)e(length)i Fi(n)p Fv(,)g(and)e(also)h(requires)g
(that)g(\257nding)f(the)0 72400 y(v)-57 b(alues)342 b
Fi(x)3629 72511 y Fl(0)4091 72400 y Fi(;)171 b(x)5126
72511 y Fl(1)5929 72400 y Fv(and)341 b Fi(y)8424 72511
y Fl(0)8886 72400 y Fi(;)171 b(y)9845 72511 y Fl(1)10647
72400 y Fv(can)342 b(b)28 b(e)342 b(done)f(in)h(p)28
b(olynomial)343 b(time.)25394 75721 y Fr(17)p eop
%%Page: 18 19
18 18 bop 0 818 a Fr(Hence)404 b(the)g(function)i Fq(f)535
b Fr(is)404 b(also)g(computational)h(ro)-34 b(w)405 b(non-transitiv)-34
b(e.)0 4597 y Fs(4)1793 b(Criterion)599 b(for)f(E\256-)p
Fa(S)120 b(F)158 b(E)0 7303 y Fr(W)-101 b(e)497 b(no)-34
b(w)500 b(presen)-34 b(t)498 b(our)h(criterion)e(for)h(a)g(function)h
(to)g(b)34 b(e)498 b(unconditionally)g(in)h(E\256-)p
Fp(S)91 b(F)120 b(E)108 b Fr(.)820 b(This)499 b(criterion)e(is)0
8808 y(complemen)-34 b(tary)278 b(in)f(nature)h(to)g(the)g(criterion)f
(for)g(completeness,)303 b(in)277 b(the)h(sense)g(that)g(while)g(the)g
(computational)0 10314 y(ro)-34 b(w)352 b(non-transitiv)-34
b(e)353 b(condition)f(requests)g(the)g(\\w)-34 b(eak)352
b(hardness")h(of)f(computing)h Fq(f)130 b Fr(\()p Fq(x)40217
10496 y Fo(1)40744 10314 y Fq(;)202 b(y)43 b Fr(\))352
b(from)g Fq(f)130 b Fr(\()p Fq(x)47443 10496 y Fo(0)47970
10314 y Fq(;)202 b(y)43 b Fr(\),)362 b(the)0 11819 y(ro)-34
b(w)405 b(transitivit)-34 b(y)404 b(condition)h(requests)f(that)h(this)
g(computation)g(is)f(easy)-101 b(.)0 14401 y Fj(De\257nition)466
b(4.1)606 b(Computational)314 b(Ro)-39 b(w)313 b(T)-116
b(ransitivit)-39 b(y)312 b Fk(We)g(say)f(that)f(a)i(function)f
Fq(f)468 b Fr(:)336 b Fp(f)p Fr(0)p Fq(;)202 b Fr(1)p
Fp(g)45483 13961 y FC(\244)46014 14401 y Fp(\243)5 b(f)p
Fr(0)p Fq(;)202 b Fr(1)p Fp(g)49925 13961 y FC(\244)50788
14401 y Fp(!)0 15907 y(f)p Fr(0)p Fq(;)g Fr(1)p Fp(g)2963
15467 y FC(\244)3996 15907 y Fk(is)506 b Fj(\(computational\))557
b(ro)-39 b(w)556 b(transitiv)-39 b(e)508 b Fk(if)e(ther)-62
b(e)506 b(exists)f(a)i(PPTM)g Fq(M)639 b Fk(such)506
b(that)f(for)h(al)62 b(l)506 b(inputs)0 17412 y Fq(x)693
17594 y Fo(0)1219 17412 y Fq(;)202 b(x)2451 17594 y Fo(1)3313
17412 y Fp(2)336 b(f)p Fr(0)p Fq(;)202 b Fr(1)p Fp(g)7420
16972 y Fm(n)8047 17412 y Fq(;)g(y)380 b Fp(2)337 b(f)p
Fr(0)p Fq(;)202 b Fr(1)p Fp(g)13668 16972 y Fm(n)14239
16660 y Fw(0)15026 17412 y Fk(:)18247 18918 y Fq(M)132
b Fr(\()p Fq(x)20719 19100 y Fo(0)21246 18918 y Fq(;)202
b(x)22478 19100 y Fo(1)23003 18918 y Fq(;)g(f)130 b Fr(\()p
Fq(x)25429 19100 y Fo(0)25955 18918 y Fq(;)202 b(y)43
b Fr(\)\))338 b(=)f Fq(f)130 b Fr(\()p Fq(x)31578 19100
y Fo(1)32105 18918 y Fq(;)202 b(y)43 b Fr(\))0 21500
y(W)-101 b(e)304 b(emphasis)g(that)i(in)e(this)g(de\257nition)i
Fq(M)436 b Fr(is)304 b(required)f(to)h(b)34 b(e)304 b(a)g(uniform)h(T)
-101 b(uring)305 b(Mac)-34 b(hine,)324 b(as)305 b(it)f(will)f(actually)
0 23005 y(b)34 b(e)404 b(used)h(b)-34 b(y)404 b(the)h(parties)f(in)g
(the)g(SFE)h(proto)34 b(col)404 b(for)g Fq(f)130 b Fr(.)0
25587 y Fj(Theorem)464 b(4.1)606 b Fk(L)-62 b(et)572
b Fq(f)703 b Fk(b)-62 b(e)571 b(an)i(e\261ciently)c(c)-62
b(omputable)569 b(function)i(and)g(supp)-62 b(ose)569
b(it)j(is)f(c)-62 b(omputational)569 b(r)-62 b(ow)0 27092
y(tr)g(ansitive)431 b(then)i Fq(f)565 b Fk(is)433 b(unc)-62
b(onditional)62 b(ly)430 b(in)k(E\256-)q Fp(S)91 b(F)120
b(E)108 b Fk(.)25438 26652 y Fo(23)0 29674 y Fk(Pr)-62
b(o)g(of)p Fr(.)1144 b(Supp)34 b(ose)405 b(that)g Fq(f)535
b Fr(is)404 b(ro)-34 b(w)405 b(transitiv)-34 b(e,)404
b(then)h(the)f(follo)-34 b(wing)405 b(is)f(an)g(SFE)h(proto)34
b(col)404 b(for)g Fq(f)130 b Fr(:)p 1882 30865 48573
45 v 1860 39948 45 9084 v 2546 32988 a(\246)3455 33185
y Fm(f)4060 32988 y Fr(\()p Fq(x;)202 b(y)43 b Fr(\))4027
35490 y(1.)606 b(Bob)404 b(c)-34 b(ho)34 b(oses)405 b(an)f(arbitrary)
481 b(^)-683 b Fq(x)336 b Fp(2)h(f)p Fr(0)p Fq(;)202
b Fr(1)p Fp(g)24424 35050 y Fm(n)25454 35490 y Fr(and)405
b(sends)482 b(^)-683 b Fq(x)404 b Fr(and)h Fq(f)130 b
Fr(\()77 b(^)-683 b Fq(x)q(;)202 b(y)43 b Fr(\))405 b(to)f(Alice.)4027
37991 y(2.)606 b(Alice)403 b(computes)i(and)g(outputs)h
Fq(M)132 b Fr(\()77 b(^)-683 b Fq(x)q(;)202 b(x;)g(f)130
b Fr(\()77 b(^)-683 b Fq(x;)202 b(y)43 b Fr(\)\).)p 50432
39948 V 1882 39993 48573 45 v 1882 41745 a(The)328 b(ab)34
b(o)-34 b(v)g(e)327 b(preo)34 b(cedure)327 b(is)g(easily)f(sho)-34
b(wn)329 b(to)e(b)34 b(e)327 b(an)h(SFE)g(proto)34 b(col)327
b(for)g Fq(f)130 b Fr(.)514 b(The)328 b(correctness)e(follo)-34
b(ws)328 b(since)0 43251 y(Alice)466 b(learns)h Fq(M)132
b Fr(\()77 b(^)-683 b Fq(x;)202 b(x;)g(f)130 b Fr(\()77
b(^)-683 b Fq(x;)202 b(y)43 b Fr(\)\))443 b(=)e Fq(f)130
b Fr(\()p Fq(x;)202 b(y)43 b Fr(\))469 b(as)e(required.)727
b(As)467 b(for)g(securit)-34 b(y:)664 b(Bob)467 b(do)34
b(es)467 b(not)h(learn)f(an)-34 b(ything)0 44756 y(from)576
b(the)g(proto)34 b(col)575 b(simply)g(b)34 b(ecause)575
b(he)h(gets)f(no)h(message)g(from)f(Alice.)1052 b(On)575
b(the)h(other)g(hand,)619 b(Alice's)0 46262 y(view)492
b(can)h(b)34 b(e)492 b(sim)-34 b(ulated)494 b(giv)-34
b(en)492 b(the)h(output)i Fq(f)130 b Fr(\()p Fq(x;)202
b(y)43 b Fr(\),)516 b(simply)493 b(b)-34 b(y)493 b(c)-34
b(ho)34 b(osing)493 b(a)g(random)570 b(^)-683 b Fq(x)492
b Fr(and)i(computing)0 47767 y Fq(M)132 b Fr(\()p Fq(x;)279
b Fr(^)-683 b Fq(x;)202 b(f)130 b Fr(\()p Fq(x;)202 b(y)43
b Fr(\)\))338 b(=)f Fq(f)130 b Fr(\()77 b(^)-683 b Fq(x)q(;)202
b(y)43 b Fr(\).)p 15085 47767 788 788 v 0 51547 a Fs(5)1793
b(The)598 b(Semi-Honest)i(vs.)798 b(the)598 b(Malicious)h(Mo)50
b(del)0 54252 y Fr(Throughout)508 b(the)e(pap)34 b(er,)531
b(w)-34 b(e)507 b(allo)-34 b(w)506 b(ourselv)-34 b(es)505
b(to)h(assume)h(that)g(Alice)d(and)j(Bob)f(are)f(semi-honest.)844
b(This)0 55758 y(means)503 b(that)h(they)e(follo)-34
b(w)503 b(the)g(proto)34 b(col)502 b(exactly)g(as)h(sp)34
b(eci\257ed,)526 b(but)504 b(after)f(the)f(proto)34 b(col)503
b(is)f(executed,)526 b(the)0 57263 y(parties)380 b(ma)-34
b(y)381 b(try)f(to)h(extract)f(more)f(information)j(than)f(actually)f
(in)-34 b(tended)382 b(b)-34 b(y)380 b(insp)34 b(ecting)381
b(the)g(transcript)g(of)0 58769 y(the)410 b(proto)34
b(col.)555 b(W)-101 b(orking)409 b(in)h(this)g(mo)34
b(del)409 b(can)h(b)34 b(e)409 b(view)-34 b(ed)410 b(as)g(a)f(stepping)
i(stone)f(to)-34 b(w)g(ards)412 b(ac)-34 b(hieving)409
b(securit)-34 b(y)0 60274 y(in)495 b(the)h(more)f(realistic)g
(malicious)g(mo)34 b(del)495 b(where)g(the)h(parties)g(can)f(run)h(an)
-34 b(y)496 b(desirable)f(strategy)h(and)g(ma)-34 b(y)0
61780 y(c)g(ho)34 b(ose)364 b(to)g(violate)f(the)h(prescrib)34
b(ed)363 b(proto)34 b(col.)525 b(The)364 b(next)g(step)g(is)f
(transforming)i(semi-honest)g(proto)34 b(cols)363 b(in)-34
b(to)0 63285 y(malicious)422 b(ones.)594 b(This)423 b(can)f(b)34
b(e)422 b(ac)-34 b(hiev)g(ed)423 b(using)g(the)g(compiler)e(of)i
(Goldreic)-34 b(h,)427 b(Micali)421 b(and)i(Wigderson)g([22],)0
64791 y(that)500 b(tak)-34 b(es)498 b(a)h(proto)34 b(col)498
b(that)h(is)f(secure)g(in)h(the)f(semi-honest)h(mo)34
b(del,)522 b(and)499 b(transforms)g(it)g(in)-34 b(to)499
b(a)f(proto)34 b(col)0 66296 y(secure)396 b(in)h(the)h(malicious)e(mo)
34 b(del)397 b(\(assuming)h(\(non-uniform\))h(one-w)-34
b(a)g(y)398 b(functions)h(exist\).)536 b(This)397 b(means)h(that)0
67802 y(assuming)406 b(one-w)-34 b(a)g(y)406 b(functions)h(do)f(exist,)
e(the)i(main)f(theorem)h(of)f(this)h(pap)34 b(er)405
b(carries)f(o)-34 b(v)g(er)405 b(to)h(the)f(malicious)0
69307 y(mo)34 b(del:)p 0 70042 20800 45 v 976 70759 a
Fl(23)1843 71182 y Fv(Note)450 b(that)g(Theorem)g(4.1)g(holds)g
(unconditionally)-85 b(,)478 b(that)450 b(is,)478 b(the)450
b(v)-57 b(alidit)-28 b(y)452 b(of)d(the)h(SFE)g(proto)28
b(col)450 b(do)28 b(es)450 b(not)g(rely)h(on)e(an)-28
b(y)0 72400 y(assumption)341 b(\(suc)-28 b(h)341 b(as)g(the)h
(existence)i(of)d(OT\).)25394 75721 y Fr(18)p eop
%%Page: 19 20
19 19 bop 0 818 a Fj(Theorem)464 b(5.1)606 b Fk(If)434
b(\(non-uniform\))e(one-way)h(functions)f(exist)g(then:)1818
3026 y Fp(\262)606 b Fk(A)-31 b(l)62 b(l)433 b(r)-62
b(ow-tr)g(ansitive)432 b(functions)g(have)f(e\261cient)h(SFE)j(pr)-62
b(oto)g(c)g(ols)431 b(se)-62 b(cur)g(e)431 b(against)h(malicious)f(p)
-62 b(arties.)1818 5410 y Fp(\262)606 b Fk(If)340 b(a)g(r)-62
b(ow)340 b(non-tr)-62 b(ansitive)338 b(function)h(has)g(an)h
(e\261cient)e(SFE)j(pr)-62 b(oto)g(c)g(ol)338 b(\(even)h(in)h(the)f
(semi-honest)e(mo)-62 b(del\),)3030 6915 y(then)433 b(al)62
b(l)433 b(functions)f(have)g(SFE)i(pr)-62 b(oto)g(c)g(ols)431
b(se)-62 b(cur)g(e)432 b(against)f(malicious)g(adversaries.)0
9123 y Fr(Note)369 b(that)h(in)e(the)h(ab)34 b(o)-34
b(v)g(e)369 b(theorem,)376 b(\\SFE)369 b(proto)34 b(col")368
b(refers)g(only)h(to)g(sending)g(messages)g(and)g(tossing)g(coins,)0
10629 y(without)361 b(use)e(of)g(\\magic)f(b)34 b(o)-34
b(xes")359 b(suc)-34 b(h)360 b(as)f(third)h(parties,)367
b(noisy)359 b(c)-34 b(hannels)360 b(or)f(quan)-34 b(tum)360
b(c)-34 b(hannels,)369 b(where)359 b(the)0 12134 y(GMW)404
b(compiler)f(do)34 b(es)404 b(not)h(apply)-101 b(.)0
15280 y Fj(Ro)-39 b(w)536 b(Non-T)-116 b(ransitiv)-39
b(e)536 b(functions)h(in)g(the)f(Malicious)g(Mo)39 b(del)1213
b Fr(The)466 b(ab)34 b(o)-34 b(v)g(e)467 b(theorem)f(relies)f(on)h(the)
0 16786 y(existence)289 b(of)h(one-w)-34 b(a)g(y)291
b(functions.)502 b(W)-101 b(e)289 b(further)h(sho)-34
b(w)291 b(that)g(the)f(existence)f(of)h(SFE)g(for)g(an)-34
b(y)290 b(complete)g(function)0 18291 y(implies)445 b(the)h(existence)e
(of)i(one-w)-34 b(a)g(y)446 b(functions.)664 b(Th)-34
b(us)447 b(w)-34 b(e)446 b(get)g(the)f(follo)-34 b(wing)447
b(unconditional)f(Theorem)g(for)0 19797 y(ro)-34 b(w)405
b(non-transitiv)-34 b(e)405 b(functions:)0 22278 y Fj(Theorem)464
b(5.2)606 b Fk(If)521 b(a)f(r)-62 b(ow)520 b(non-tr)-62
b(ansitive)518 b(function)h(has)g(an)i(e\261cient)d(SFE)k(pr)-62
b(oto)g(c)g(ol)517 b(\(even)i(in)i(the)e(semi-)0 23783
y(honest)593 b(mo)-62 b(del\),)633 b(then)594 b(al)62
b(l)593 b(p)-62 b(olynomial)592 b(time)i(functions)f(have)g(SFE)i(pr)
-62 b(oto)g(c)g(ols)592 b(se)-62 b(cur)g(e)592 b(against)h(malicious)0
25289 y(adversaries.)0 27770 y(Pr)-62 b(o)g(of)p Fr(.)1144
b(Supp)34 b(ose)586 b(that)g(there)f(exists)g(an)g(SFE)h(proto)34
b(col)584 b(\(in)i(the)f(semi-honest)h(mo)34 b(del\))585
b(for)g(a)h(ro)-34 b(w)585 b(non-)0 29276 y(transitiv)-34
b(e)448 b(function)i Fq(f)130 b Fr(.)672 b(Then)449 b(b)-34
b(y)449 b(Theorem)f(3.1)g(there)g(exists)g(a)g(construction)i(of)e(an)h
(OT)f(proto)34 b(col)448 b(in)g(the)0 30781 y(semi-honest)h(mo)34
b(del.)669 b(By)447 b(the)h(result)g(of)g(Impagliazzo)f(and)i(Lub)-34
b(y)448 b([28],)458 b(the)448 b(existence)f(of)h(semi-honest)h(OT)0
32287 y(implies)404 b(the)i(existence)e(of)h(one-w)-34
b(a)g(y)406 b(functions.)22582 31847 y Fo(24)24121 32287
y Fr(No)-34 b(w,)406 b(in)f(order)f(to)i(construct)f(a)g(malicious)g
(SFE)g(proto)34 b(col)0 33792 y(for)489 b(an)-34 b(y)490
b(e\261cien)-34 b(tly)488 b(computable)i(function)h Fq(g)43
b Fr(,)510 b(\257rst)490 b(construct)g(a)f(semi-honest)h(SFE)g(proto)34
b(col)488 b(for)i Fq(g)532 b Fr(using)0 35298 y(the)442
b(reduction)g(to)h(OT)e([43],)451 b(and)442 b(giv)-34
b(en)442 b(that)h(one-w)-34 b(a)g(y)443 b(functions)g(exist,)450
b(run)443 b(the)f(GMW)f(compiler)g(on)h(the)0 36803 y(semi-honest)405
b(proto)34 b(col)404 b(for)g Fq(g)448 b Fr(to)404 b(receiv)-34
b(e)402 b(a)j(malicious)e(proto)34 b(col)404 b(for)g
Fq(g)43 b Fr(.)p 34950 36803 788 788 v 0 39949 a Fj(Ro)-39
b(w)431 b(T)-116 b(ransitiv)-39 b(e)431 b(functions)h(in)f(the)h
(Malicious)f(Mo)39 b(del)1212 b Fr(On)375 b(the)g(other)g(hand,)382
b(if)375 b(one-w)-34 b(a)g(y)375 b(functions)0 41455
y(are)548 b(not)h(guaran)-34 b(teed,)586 b(w)-34 b(e)549
b(do)g(not)g(kno)-34 b(w)550 b(if)e(there)h(exists)f(an)h(SFE)g(in)g
(the)g(malicious)f(mo)34 b(del)548 b(for)g(all)g(ro)-34
b(w)0 42960 y(transitiv)g(e)443 b(functions.)657 b(F)-101
b(or)443 b(example,)451 b(in)443 b(the)h(ab)34 b(o)-34
b(v)g(e)443 b(men)-34 b(tioned)444 b(trivial)e(SFE)h(proto)34
b(col)443 b(for)g(ro)-34 b(w)444 b(transitiv)-34 b(e)0
44466 y(functions,)545 b(Alice)515 b Fk(c)-62 b(annot)515
b Fr(act)g(maliciously)g(as)h(she)g(do)34 b(es)516 b(not)g(send)h(an)
-34 b(y)516 b(messages)f(to)i(Bob.)873 b(Ho)-34 b(w)g(ev)g(er,)544
b(it)0 45971 y(migh)-34 b(t)480 b(b)34 b(e)479 b(the)g(case)g(that)h(a)
g(malicious)e(Bob)h(c)-34 b(heats)480 b(b)-34 b(y)480
b(sending)g(Alice)e(an)h(illegal)f(v)-67 b(alue.)763
b(If)479 b(it)g(is)g(hard)h(to)0 47477 y(distinguish)498
b(a)g(legal)e(message)h(from)g(Bob)g(from)h(an)f(illegal)f(message,)520
b(then)498 b(suc)-34 b(h)498 b(a)f(proto)34 b(col)497
b(is)g(no)g(longer)0 48982 y(secure.)1882 50487 y(Moreo)-34
b(v)g(er,)389 b(w)-34 b(e)388 b(sho)-34 b(w)388 b(that)g(under)g
(certain)f(assumptions)i(\(that)f(are)f(plausible)g(within)h(our)f
(curren)-34 b(t)387 b(state)0 51993 y(of)339 b(kno)-34
b(wledge\),)353 b(there)339 b(are)f(functions)i(that)g(ha)-34
b(v)g(e)340 b(SFE)f(in)g(the)g(semi-honest)h(mo)34 b(del)338
b(but)i(not)g(in)f(the)g(malicious)0 53498 y(mo)34 b(del.)538
b(More)404 b(precisely)-101 b(,)402 b(de\257ne)j(the)f(follo)-34
b(wing)405 b(w)-34 b(eak)404 b(notion)h(of)g(one-w)-34
b(a)g(y)405 b(functions:)0 55706 y Fj(De\257nition)466
b(5.1)606 b Fk(A)434 b(c)-62 b(ol)62 b(le)-62 b(ction)431
b(of)i(functions)f Fp(f)p Fq(f)23480 55888 y Fm(i)24193
55706 y Fr(:)336 b Fq(D)25870 55888 y Fm(i)26582 55706
y Fp(!)h(f)p Fr(0)p Fq(;)202 b Fr(1)p Fp(g)31094 55267
y FC(\244)31620 55706 y Fp(g)32226 56021 y Fm(i)p FC(2)33281
55797 y Fo(\271)33173 56021 y Fm(I)34139 55706 y Fk(has)433
b Fj(one-w)-39 b(a)g(y)464 b(instances)433 b Fk(if:)1433
57914 y(1.)605 b(Easy)465 b(to)f(sample)g(and)h(c)-62
b(ompute:)618 b(Have)464 b(PPTMs)i(to)e(sample)g Fq(i)394
b Fp(2)34650 57608 y Fr(\271)34504 57914 y Fq(I)560 b
Fk(sample)464 b Fq(x)394 b Fp(2)g Fq(D)42949 58096 y
Fm(i)43790 57914 y Fk(and)465 b(to)f(c)-62 b(ompute)3030
59420 y Fq(f)3623 59602 y Fm(i)3999 59420 y Fr(\()p Fq(x)p
Fr(\))p Fk(.)1433 61804 y(2.)605 b(Some)492 b(functions)e(ar)-62
b(e)491 b(har)-62 b(d)490 b(to)h(invert:)672 b(F)-93
b(or)492 b(very)e(PPTM)j(A,)e(every)f(p)-62 b(olynomial)489
b Fq(p)p Fr(\()p Fp(\242)p Fr(\))j Fk(and)g(in\257nitely)3030
63309 y(many)434 b Fq(i)336 b Fp(2)8389 63003 y Fr(\271)8244
63309 y Fq(I)95 b Fk(,)18526 65257 y Fr(Pr)o([)p Fq(A)p
Fr(\()p Fq(i;)202 b(f)23092 65439 y Fm(i)23468 65257
y Fr(\()p Fq(x)p Fr(\)\))338 b Fp(2)e Fq(f)27779 64747
y FC(\241)p Fo(1)27649 65619 y Fm(i)29038 65257 y Fq(f)29631
65439 y Fm(i)30007 65257 y Fr(\()p Fq(x)p Fr(\)])h Fq(<)34747
64437 y Fr(1)p 33728 64978 2644 49 v 33728 66088 a Fq(p)p
Fr(\()p Fp(j)p Fq(i)p Fp(j)p Fr(\))3030 67887 y Fk(wher)-62
b(e)433 b(pr)-62 b(ob)g(ability)430 b(is)j(taken)g(over)f
Fq(x)337 b Fp(2)f Fq(D)22703 68069 y Fm(i)23512 67887
y Fk(and)433 b(the)g(r)-62 b(andomness)432 b(of)h Fq(A)p
Fk(.)p 0 68825 20800 45 v 976 69541 a Fl(24)1843 69965
y Fv(Actually)-85 b(,)330 b(in)d([28])f(it)h(w)-28 b(as)325
b(only)h(sho)-28 b(wn)325 b(that)h(sev)-28 b(eral)327
b(other)f(primitiv)-28 b(es)327 b(\(not)f(OT\))g(imply)h(one-w)-28
b(a)g(y)326 b(functions,)j(for)d(example,)0 71182 y(this)300
b(w)-28 b(as)298 b(sho)-28 b(wn)298 b(for)h(bit)h(commitmen)-28
b(t.)443 b(Ho)-28 b(w)g(ev)g(er,)307 b(it)300 b(is)g(standard)e(to)i
(sho)-28 b(w)298 b(that)i(OT)f(implies)j(bit)d(commitmen)-28
b(t)301 b(and)f(hence)g(also)0 72400 y(implies)343 b(one-w)-28
b(a)g(y)341 b(functions)25394 75721 y Fr(19)p eop
%%Page: 20 21
20 20 bop 0 818 a Fr(This)481 b(w)-34 b(eak)480 b(notion)i(of)e(one-w)
-34 b(a)g(yness)482 b(w)-34 b(as)481 b(de\257ned)g(in)g([18])f(as)g
(part)h(of)f(the)h(presen)-34 b(tation)482 b(of)f([41)o(].)767
b(W)-101 b(e)480 b(can)0 2323 y(no)-34 b(w)405 b(state)g(the)f(follo)
-34 b(wing)405 b(claim:)0 5157 y Fj(Claim)464 b(5.3)606
b Fk(Supp)-62 b(ose)540 b(that)h(ther)-62 b(e)541 b(exist)g(no)i(c)-62
b(ol)62 b(le)-62 b(ctions)539 b(of)j(functions)e(with)i(one-way)f
(instanc)-62 b(es)541 b(and)h(also)0 6662 y Fp(N)179
b(P)436 b Fg(*)336 b Fp(P)100 b Fq(=)p Fr(p)34 b(oly)450
b Fk(,)433 b(then)g(ther)-62 b(e)432 b(exist)h(functions)f
Fq(f)565 b Fk(that)432 b(have)f(semi-honest)g(SFE)k(but)d(no)i
(malicious)d(SFE.)0 9496 y(Pr)-62 b(o)g(of)p Fr(.)1144
b(A)531 b(Theorem)g(of)h(Ostro)-34 b(vsky)530 b(and)i(Wigderson)g([41)o
(])f(states)h(that)g(if)g(there)f(exist)g(no)g(collections)g(of)0
11002 y(functions)338 b(with)f(one-w)-34 b(a)g(y)338
b(instances)e(then)i Fp(Z)96 b(K)354 b Fr(=)337 b Fp(B)37
b(P)100 b(P)f Fr(,)350 b(that)337 b(is,)350 b(the)337
b(languages)f(that)i(ha)-34 b(v)g(e)337 b(zero)e(kno)-34
b(wledge)0 12507 y(pro)34 b(ofs)404 b(are)g(exactly)f(those)i
(languages)f(that)i(are)d(in)h Fp(B)37 b(P)100 b(P)g
Fr(.)1882 14013 y(Consider)536 b(for)f(example)g(the)h(problem)g(of)f
(\257nding)i(a)f(Hamiltonian)g(Cycle)e(\(HC\))j(in)e(a)h(graph.)933
b(De\257ne)0 15518 y Fq(G)p Fr(\()p Fq(C)19 b(;)202 b(E)70
b Fr(\))389 b(to)f(b)34 b(e)388 b(a)g(graph)g(with)h(Hamiltonian)f
(cycle)f Fq(C)475 b Fr(on)388 b(top)h(of)f(a)g(basic)g(edge)f(set)i
Fq(E)70 b Fr(.)532 b(De\257ne)388 b(the)h(function)0
17024 y Fq(f)130 b Fr(\()p Fq(x;)202 b(y)43 b Fr(\))564
b(=)d Fq(G)p Fr(\()p Fq(y)43 b Fr(\),)574 b(where)539
b Fq(y)605 b Fr(=)562 b(\()p Fq(C)19 b(;)202 b(E)70 b
Fr(\).)944 b(The)539 b(function)i Fq(f)670 b Fr(is)538
b(de\257nitely)h(a)h(ro)-34 b(w)539 b(transitiv)-34 b(e)539
b(function)i(as)e(it)0 18529 y(disregards)342 b(the)g(input)h
Fq(x)e Fr(is)h(iden)-34 b(tical)341 b(for)h(all)f(ro)-34
b(ws,)355 b(and)342 b(the)h(simple)e(semi-honest)h(SFE)h(proto)34
b(col)341 b(will)g(simply)0 20034 y(ha)-34 b(v)g(e)380
b(Bob)g(send)g(the)h(v)-67 b(alue)379 b Fq(G)p Fr(\()p
Fq(y)43 b Fr(\))381 b(to)f(Alice.)529 b(In)380 b(the)g(malicious)g(w)
-34 b(orld)380 b(it)g(is)g(requested,)k(among)c(other)g(things,)0
21540 y(that)322 b(Alice)d(outputs)j(a)f(v)-67 b(alue)319
b Fq(G)p Fr(\()p Fq(y)43 b Fr(\))322 b(for)f(some)f(legal)g(input)h
Fq(y)43 b Fr(.)512 b(Without)321 b(loss)f(of)h(generalit)-34
b(y)-101 b(,)337 b(Bob)320 b(can)g(start)h(the)0 23045
y(proto)34 b(col)335 b(b)-34 b(y)335 b(sending)g Fq(z)390
b Fr(=)337 b Fq(G)p Fr(\()p Fq(y)43 b Fr(\))336 b(to)f(Alice)f(\(since)
h(b)-34 b(y)335 b(the)g(securit)-34 b(y)335 b(of)g(the)h(SFE,)f(Bob)g
(is)f(required)g(to)h(c)-34 b(ho)34 b(ose)335 b Fq(y)0
24551 y Fr(in)357 b(adv)-67 b(ance)357 b(and)g(also)g(Alice)f(is)g(b)34
b(ound)359 b(to)e(learn)f(this)i(v)-67 b(alue)356 b(an)-34
b(yw)g(a)g(y)358 b(b)-34 b(y)357 b(the)h(end)f(of)g(the)h(proto)34
b(col\).)523 b(The)357 b(rest)0 26056 y(of)417 b(the)f(proto)34
b(col)416 b(can)h(b)34 b(e)416 b(view)-34 b(ed)416 b(as)g(a)g(zero)g
(kno)-34 b(wledge)416 b(pro)34 b(of)417 b(that)g(there)g(exists)e(a)i
Fq(y)460 b Fr(suc)-34 b(h)417 b(that)g Fq(z)410 b Fr(=)357
b Fq(G)p Fr(\()p Fq(y)43 b Fr(\).)0 27562 y(This)506
b(is)f(b)34 b(ecause)506 b(b)-34 b(y)506 b(the)g(prop)34
b(erties)505 b(of)h(SFE,)g(Alice)e(should)j(reject)e(a)g
Fq(z)559 b Fr(that)507 b(is)e(not)h(in)g(the)g(image)f(of)h
Fq(G)0 29067 y Fr(with)416 b(high)f(probabilit)-34 b(y)416
b(\(pro)-34 b(viding)416 b(the)f(soundness)i(requiremen)-34
b(t)415 b(in)g(ZK-pro)34 b(ofs\).)571 b(F)-101 b(urthermore,)418
b(the)d(SFE)0 30573 y(de\257nition)376 b(ensures)g(that)g(the)f(con)-34
b(v)g(ersation)376 b(can)g(b)34 b(e)374 b(sim)-34 b(ulated)376
b(seeing)f(only)g(Alice's)f(input)i Fq(x)f Fr(and)h(output)h
Fq(z)53 b Fr(,)0 32078 y(th)-34 b(us)431 b(capturing)e(the)h(sim)-34
b(ulation)430 b(requiremen)-34 b(t)428 b(of)i(zero)e(kno)-34
b(wledge.)614 b(So,)435 b(a)429 b(malicious)g(SFE)g(for)g
Fq(f)560 b Fr(is)429 b(a)g(zero)0 33584 y(kno)-34 b(wledge)441
b(pro)34 b(of)441 b(to)f(the)h(existence)f(of)g(a)h(hamiltonian)g
(cycle)e(in)h(a)h(graph.)648 b(Assume)441 b(to)f(the)h(con)-34
b(trary)441 b(that)0 35089 y(suc)-34 b(h)458 b(a)f(malicious)f(SFE)h
(proto)34 b(col)457 b(for)g Fq(f)587 b Fr(exists,)470
b(th)-34 b(us)458 b(there)f(is)f(a)h(zero)f(kno)-34 b(wledge)457
b(pro)34 b(of)457 b(to)h(the)f(existence)0 36595 y(of)435
b(a)f(hamiltonian)h(cycle.)627 b(But)434 b(since)g(hamiltonian)h(cycle)
e(is)h(an)g(NP-complete)g(problem,)442 b(and)435 b(w)-34
b(e)434 b(assumed)0 38100 y(that)379 b Fp(N)179 b(P)436
b Fg(*)336 b Fp(P)100 b Fq(=)p Fr(p)34 b(oly)17 b(,)383
b(then)c(hamiltonian)g(cycle)e(is)h(not)h(in)f Fp(B)37
b(P)100 b(P)478 b Fr(and)379 b(w)-34 b(e)379 b(get)f(a)g(con)-34
b(tradiction.)531 b(Altogether,)0 39606 y(under)434 b(the)g
(assumptions)i(ab)34 b(o)-34 b(v)g(e,)441 b(the)434 b(function)h
Fq(f)565 b Fr(has)434 b(a)g(semi-honest)g(SFE)g(but)h(cannot)g(ha)-34
b(v)g(e)434 b(a)f(malicious)0 41111 y(SFE.)p 2690 42616
788 788 v 0 45818 a Fj(Semi-Honest)591 b(vs.)997 b(Malicious)591
b(in)g(the)g(Information)g(Theoretic)f(mo)39 b(del)1212
b Fr(Finally)513 b(w)-34 b(e)515 b(note)f(that)0 47324
y(under)295 b(information)h(theoretic)f(securit)-34 b(y)294
b(de\257nitions)i(there)f(is)g(a)f(di\256erence)g(b)34
b(et)-34 b(w)g(een)296 b(the)f(malicious)g(and)g(semi-)0
48829 y(honest)424 b(w)-34 b(orlds)423 b(\(ev)-34 b(en)423
b(under)g(v)-67 b(arious)422 b(assumptions\).)597 b(Indeed,)427
b(Kilian)422 b([32])g(sho)-34 b(w)g(ed)424 b(that)g(the)f(criterion)f
(for)0 50334 y(completeness)309 b(in)g(the)h(malicious)e(mo)34
b(del)309 b(is)g(di\256eren)-34 b(t)310 b(than)g(the)f(insecure)g
(minor)g(criterion)f(of)i(the)f(semi-honest)0 51840 y(case)475
b(\(under)i(suc)-34 b(h)477 b(de\257nitions)g(the)f(GMW)f(compiler)g
(cannot)i(apply)f(as)g(it)f(promises)h(only)g(computational)0
53345 y(securit)-34 b(y\).)677 b(F)-101 b(or)451 b(example)e(the)i(OR)f
(of)h(t)-34 b(w)g(o)452 b(bits)f(is)f(complete)g(in)g(the)h
(semi-honest)g(case,)461 b(but)452 b(not)f(so)f(in)g(the)0
54851 y(malicious)404 b(mo)34 b(del.)0 58670 y Fs(6)1793
b(The)598 b(Gap)g(b)50 b(et)-50 b(w)g(een)599 b(the)g(Criteria)0
61376 y Fr(Our)486 b(ultimate)h(goal)f(is)h(to)f(categorize)g(all)g
(functions)i(as)e(either)g(in)h Fp(S)91 b(F)120 b(E)108
b Fr(-C)487 b(or)f(in)h(E\256-)p Fp(S)91 b(F)120 b(E)109
b Fr(,)506 b(ho)-34 b(w)g(ev)g(er,)508 b(our)0 62881
y(criteria)374 b(fall)i(short)g(of)g(this)g(task)g(and)h(lea)-34
b(v)g(e)375 b(a)g(gap)i(of)f(uncategorized)f(functions.)531
b(In)375 b(this)i(section)e(w)-34 b(e)376 b(discuss)0
64387 y(this)405 b(gap)f(and)h(what)g(functions)h(it)e(con)-34
b(tains,)405 b(starting)g(with)g(the)f(follo)-34 b(wing)405
b(imp)34 b(ortan)-34 b(t)406 b(observ)-67 b(ations:)1481
66888 y(1.)606 b(Some)402 b(of)g(the)g(functions)h(in)f(the)f(gap)h
(can)g(in)g(fact)g(b)34 b(e)401 b(categorized)g(b)-34
b(y)402 b(giving)f(more)g(accurate)g(or)g(more)3030 68394
y(relaxed)541 b(de\257nitions)j(of)e(the)h(ro)-34 b(w)543
b(transitivit)-34 b(y)542 b(criteria)f(and)i(the)f(de\257nitions)i(of)e
(SFE.)h(W)-101 b(e)541 b(a)-34 b(v)g(oided)3030 69899
y(doing)441 b(this)f(b)34 b(efore)439 b(in)h(order)g(to)g(presen)-34
b(t)440 b(simple)g(and)g(clean)g(de\257nitions)h(to)f(go)g(along)g
(with)g(standard)3030 71405 y(de\257nitions)406 b(of)e(SFE.)25394
75721 y(20)p eop
%%Page: 21 22
21 21 bop 1481 818 a Fr(2.)606 b(The)442 b(fact)g(that)g(a)g(gap)g
(exists)f(seem)g(to)g(re\260ect)g(the)h(actual)g(w)-34
b(orld)442 b(as)f(there)g(are)g(functions)i(that)f(seem)3030
2323 y(to)522 b(b)34 b(e)521 b(neither)g(complete)g(nor)g(in)g(E\256-)p
Fp(S)91 b(F)120 b(E)109 b Fr(.)890 b(This)521 b(state)h(is)f(v)-34
b(ery)520 b(common)i(in)f(computational)i(set-)3030 3829
y(tings,)387 b(and)382 b(in)g(fact,)k(this)c(c)-34 b(haracterization)
381 b(ma)-34 b(y)382 b(b)34 b(e)381 b(considered)h(v)-34
b(ery)381 b(tigh)-34 b(t)383 b(as)e(far)h(as)g(computational)3030
5334 y(c)-34 b(haracterizations)404 b(go.)1481 7836 y(3.)606
b(The)373 b(functions)g(in)f(the)g(gap)g(p)34 b(osses)372
b(some)g(\\unnatural")h(b)34 b(eha)-34 b(vior)372 b(\(see)f(b)34
b(elo)-34 b(w\))373 b(and)f(th)-34 b(us)374 b(w)-34 b(e)372
b(sa)-34 b(y)372 b(that)3030 9341 y(e\256ectiv)-34 b(ely)403
b(the)h(criteria)f(co)-34 b(v)g(er)404 b(all)f(\\nice")h(functions.)0
11843 y(That)360 b(b)34 b(eing)358 b(said,)368 b(w)-34
b(e)359 b(elab)34 b(orate)358 b(on)h(what)h(are)e(the)h(t)-34
b(yp)34 b(es)359 b(of)g(functions)h(that)g(migh)-34 b(t)359
b(b)34 b(e)359 b(in)f(the)h(gap)g(and)h(ho)-34 b(w)0
13348 y(these)404 b(functions)i(ma)-34 b(y)404 b(or)g(ma)-34
b(y)404 b(not)h(b)34 b(e)404 b(categorized)f(after)i(all:)1818
15850 y Fp(\262)606 b Fr(F)-101 b(unctions)573 b(for)e(whic)-34
b(h)572 b(it)f(is)f(p)34 b(ossible)571 b(to)h(compute)f(the)h
Fq(f)130 b Fr(\()p Fq(x)32763 16032 y Fo(1)33290 15850
y Fq(;)202 b(y)43 b Fr(\))571 b(giv)-34 b(en)571 b Fq(x)39533
16032 y Fo(0)40059 15850 y Fq(;)202 b(x)41291 16032 y
Fo(1)42387 15850 y Fr(and)572 b Fq(f)130 b Fr(\()p Fq(x)46798
16032 y Fo(0)47325 15850 y Fq(;)202 b(y)43 b Fr(\))572
b(b)-34 b(y)571 b(a)3030 17356 y(non-uniform)377 b(adv)-34
b(ersary)375 b(\(a)g(circuit)f(family\))h(but)h(hard)g(to)f(do)h(so)f
(for)g(a)g(uniform)h(adv)-34 b(ersary)374 b(\(PPTM\):)3030
19359 y(It)469 b(is)f(p)34 b(ossible)468 b(to)g(de\257ne)h(SFE)g(to)g
(b)34 b(e)468 b(secure)f(only)h(against)h(uniform)h(adv)-34
b(ersaries)467 b(if)h(w)-34 b(orking)469 b(in)f(the)3030
20865 y(semi-honest)380 b(mo)34 b(del.)13154 20425 y
Fo(25)14680 20865 y Fr(In)379 b(suc)-34 b(h)380 b(a)e(case,)384
b(ro)-34 b(w)379 b(non-transitivit)-34 b(y)380 b(ma)-34
b(y)379 b(b)34 b(e)379 b(de\257ned)h(as)f(ha)-34 b(ving)379
b(hardness)3030 22370 y(for)431 b(uniform)h(mac)-34 b(hines,)437
b(the)432 b(main)f(theorem)g(will)f(still)g(hold,)438
b(and)431 b(the)h(functions)g(men)-34 b(tioned)432 b(will)e(b)34
b(e)3030 23876 y(categorized)461 b(as)h(complete)g(\(in)g(the)g
(semi-honest)h(mo)34 b(del\).)712 b(Ho)-34 b(w)g(ev)g(er,)476
b(in)462 b(order)f(to)i(apply)f(the)g(GMW)3030 25381
y(transformation)505 b(one)f(m)-34 b(ust)504 b(use)f(one-w)-34
b(a)g(y)505 b(functions)g(that)f(are)f(hard)h(for)f(non-uniform)i(adv)
-34 b(ersaries,)3030 26887 y(and)405 b(th)-34 b(us)406
b(Theorem)e(1.2)g(do)34 b(es)404 b(not)h(hold)f(an)-34
b(ymore.)1818 29388 y Fp(\262)606 b Fr(F)-101 b(unctions)368
b(for)f(whic)-34 b(h)367 b(it)g(is)f(p)34 b(ossible)366
b(to)h(compute)g(the)g Fq(f)130 b Fr(\()p Fq(x)30922
29570 y Fo(1)31449 29388 y Fq(;)202 b(y)43 b Fr(\))368
b(giv)-34 b(en)366 b Fq(x)37284 29570 y Fo(0)37809 29388
y Fq(;)202 b(x)39041 29570 y Fo(1)39933 29388 y Fr(and)368
b Fq(f)130 b Fr(\()p Fq(x)44140 29570 y Fo(0)44666 29388
y Fq(;)202 b(y)43 b Fr(\))368 b(with)f(o)-34 b(v)g(er-)3030
30894 y(whelming)403 b(probabilit)-34 b(y)402 b(when)h
Fq(x)18535 31076 y Fo(0)19061 30894 y Fq(;)202 b(x)20293
31076 y Fo(1)21220 30894 y Fr(and)403 b Fq(y)445 b Fr(are)402
b(tak)-34 b(en)402 b(from)g(an)-34 b(y)403 b(samplable)f(distribution)h
(but)g(hard)3030 32399 y(to)336 b(do)h(so)e(for)h(inputs)h(tak)-34
b(en)337 b(from)f(some)f(distribution)j(that)e(is)g(not)h(e\261cien)-34
b(tly)335 b(samplable:)504 b(Considering)3030 33905 y(that)326
b(the)f(inputs)h(of)f(an)f(SFE)h(should)h(b)34 b(e)324
b(tak)-34 b(en)325 b(from)g(a)f(samplable)h(distribution,)341
b(then)326 b(these)e(functions)3030 35410 y(ha)-34 b(v)g(e)405
b(an)f(SFE)h(proto)34 b(col)404 b(with)h(the)f(exception)g(that)i(the)e
(proto)34 b(col)404 b(can)g(fail)g(with)h(negligible)e(error.)1818
37912 y Fp(\262)606 b Fr(F)-101 b(unctions)406 b(that)f(b)34
b(eha)-34 b(v)g(e)404 b(inconsisten)-34 b(tly)405 b(on)g(di\256eren)-34
b(t)404 b(input)i(lengths:)3030 39915 y(On)507 b(the)g(one)f(hand,)533
b(there)507 b(are)f(functions)i(with)f(suc)-34 b(h)507
b(b)34 b(eha)-34 b(vior)506 b(that)i(seem)e(to)h(b)34
b(e)506 b(in)h(neither)f(cate-)3030 41421 y(gory)-101
b(.)533 b(F)-101 b(or)389 b(instance)g(a)g(function)h(that)g
(alternates)f(b)34 b(et)-34 b(w)g(een)389 b(a)g(v)-34
b(ery)388 b(trivial)g(function)i(to)f(an)g(inheren)-34
b(tly)3030 42926 y(complete)437 b(one)f(\(lik)-34 b(e)436
b(OT\))h(dep)34 b(ending)438 b(on)f(the)g(input)h(length.)636
b(If)437 b(the)g(o)34 b(ccurrences)435 b(of)i(OT)g(are)f(sparse)3030
44432 y(enough)405 b(then)g(the)g(function)g(cannot)g(b)34
b(e)404 b(complete,)g(but)h(still)f(will)f(not)i(b)34
b(e)404 b(in)g(E\256-)p Fp(S)91 b(F)120 b(E)109 b Fr(.)3030
46435 y(On)529 b(the)f(other)h(hand,)560 b(there)528
b(are)g(functions)h(in)g(this)f(category)g(that)h(are)f(de\257nitely)g
(complete.)911 b(F)-101 b(or)3030 47941 y(instance,)332
b(the)314 b(requiremen)-34 b(t)313 b(for)h(\\all)f(but)i(\257nitely)e
(man)-34 b(y)314 b Fq(n)p Fr(")f(in)h(the)g(de\257nition)h(of)f(ro)-34
b(w)314 b(non-transitivit)-34 b(y)3030 49446 y(is)386
b(m)-34 b(uc)g(h)387 b(stronger)f(than)h(what)g(is)e(needed.)533
b(The)386 b(real)f(need)h(is)f(that)i(for)f(an)-34 b(y)386
b(securit)-34 b(y)386 b(parameter)f Fq(n)h Fr(w)-34 b(e)3030
50952 y(can)452 b(e\261cien)-34 b(tly)451 b(c)-34 b(ho)34
b(ose)452 b(an)g(input)g(length)h Fq(l)24 b Fr(\()p Fq(n)p
Fr(\))451 b(\(p)34 b(olynomially)451 b(related)g(to)h
Fq(n)p Fr(\))g(for)f(whic)-34 b(h)453 b(computing)3030
52457 y Fq(f)130 b Fr(\()p Fq(x)4917 52639 y Fo(1)5444
52457 y Fq(;)202 b(y)43 b Fr(\))393 b(from)f Fq(f)130
b Fr(\()p Fq(x)12224 52639 y Fo(0)12751 52457 y Fq(;)202
b(y)43 b Fr(\))392 b(is)g(\\w)-34 b(eakly)392 b(hard")g(\(probabilit)
-34 b(y)393 b(here)e(should)i(also)f(include)g(the)g(randomness)3030
53963 y(in)404 b(c)-34 b(ho)34 b(osing)405 b Fq(l)24
b Fr(\()p Fq(n)p Fr(\)\).)1818 56465 y Fp(\262)606 b
Fr(F)-101 b(unctions)321 b(suc)-34 b(h)320 b(that)g(for)f(ev)-34
b(ery)318 b(p)34 b(olynomial)318 b Fq(q)43 b Fr(\()p
Fp(\242)p Fr(\))320 b(there)f(exists)g(a)g(PPTM)g Fq(M)39262
56647 y Fm(q)40088 56465 y Fr(that)h(computes)g Fq(f)130
b Fr(\()p Fq(x)49825 56647 y Fo(1)50352 56465 y Fq(;)202
b(y)43 b Fr(\))3030 57970 y(giv)-34 b(en)365 b Fq(x)6849
58152 y Fo(0)7375 57970 y Fq(;)202 b(x)8607 58152 y Fo(1)9497
57970 y Fr(and)366 b Fq(f)130 b Fr(\()p Fq(x)13702 58152
y Fo(0)14229 57970 y Fq(;)202 b(y)43 b Fr(\))366 b(with)f(success)g
(probabilit)-34 b(y)366 b(at)f(least)g(1)191 b Fp(\241)36156
57493 y Fo(1)p 35514 57691 1755 49 v 35514 58404 a Fm(q)32
b Fo(\()p Fm(n)p Fo(\))37402 57970 y Fr(,)372 b(but)366
b(there)f(is)g(no)g(one)h(PPTM)3030 59475 y Fq(M)486
b Fr(that)354 b(ac)-34 b(hiev)g(es)354 b(this)g(for)f(all)g(p)34
b(ossible)353 b Fq(q)43 b Fr(:)514 b(Here)353 b(it)g(is)g(unclear)h
(what)g(can)g(b)34 b(e)353 b(done)h(unless)g(considering)3030
60981 y(strong)405 b(relaxations)f(of)g(the)h(de\257nitions)g(of)g
(SFE.)0 64800 y Fs(7)1793 b(W)-149 b(eak-OT)598 b(implies)h(OT)0
67506 y Fr(This)367 b(section)f(sho)-34 b(ws)368 b(that)f(the)f(w)-34
b(eak)367 b(implemen)-34 b(tation)367 b(of)g(OT)f(\(W)-101
b(eak-OT\))366 b(implies)g(a)g(strong)h(OT.)f(W)-101
b(e)365 b(note)0 69011 y(that)330 b(this)f(ampli\257cation)g(result)f
(defers)h(from)f(previous)h(suc)-34 b(h)329 b(results)g(lik)-34
b(e)327 b([12,)h(13])g(that)i(w)-34 b(ere)328 b(all)g(information)p
0 70133 20800 45 v 976 70850 a Fl(25)1843 71274 y Fv(This)341
b(is)h(since)g(comp)28 b(osition)342 b(theorems)g(hold)g(for)e(uniform)
h(mac)-28 b(hines)342 b(only)g(under)f(the)h(semi-honest)g(mo)28
b(del)25394 75721 y Fr(21)p eop
%%Page: 22 23
22 22 bop 0 818 a Fr(theoretic.)678 b(Our)450 b(ampli\257cation)i(w)-34
b(orks)451 b(against)g(computational)h(adv)-34 b(ersaries)450
b(and)i(requires)d(more)i(complex)0 2323 y(pro)34 b(ofs)404
b(using)h(to)34 b(ols)404 b(suc)-34 b(h)405 b(as)f(Y)-101
b(ao's)404 b(X)-34 b(OR-lemma.)1882 3829 y(Recall)355
b(that)j(the)e(de\257nition)i(of)f(a)f(\\strong")h(Naiv)-34
b(e-OT)356 b(proto)34 b(col)356 b(requires)f(that)j(the)f(views)e(of)i
(the)g(sender)0 5334 y(and)372 b(receiv)-34 b(er)369
b(ma)-34 b(y)371 b(b)34 b(e)371 b(sim)-34 b(ulated)372
b(\(up)g(to)g(a)f(negligible)f(deviance\),)377 b(when)372
b(seeing)f(just)h(their)f(lo)34 b(cal)370 b(input)i(and)0
6839 y(output.)893 b(This)522 b(is)f(equiv)-67 b(alen)-34
b(t)521 b(to)h(sa)-34 b(ying)522 b(that)h(the)f(sender)f(\(or)h(receiv)
-34 b(er\))520 b(cannot)j(guess)e(the)h(other)g(side's)0
8345 y(input)491 b(bit)e(with)i(non-negligible)e(adv)-67
b(an)-34 b(tage)490 b(o)-34 b(v)g(er)490 b(\260ipping)g(a)f(coin)h
(\(when)g(seeing)f(their)h(lo)34 b(cal)488 b(view)h(of)g(the)0
9850 y(proto)34 b(col\).)535 b(A)395 b(W)-101 b(eak-OT)394
b(is)g(a)g(relaxation)g(of)h(the)g(latter)g(de\257nition.)536
b(The)395 b(sender)f(is)h(restricted)f(in)g(the)h(same)0
11356 y(manner,)545 b(but)518 b(the)g(receiv)-34 b(er)515
b(is)i(allo)-34 b(w)g(ed)518 b(a)f(higher)g(success)f(probabilit)-34
b(y)-101 b(.)878 b(W)-101 b(e)517 b(require)e(that)k(the)e(receiv)-34
b(er's)0 12861 y(success)444 b(probabilit)-34 b(y)444
b(in)f(guessing)i(the)f(sender's)f(bit)h Fq(b)g Fr(is)g(b)34
b(ounded)445 b(b)-34 b(y)444 b(1)296 b Fp(\241)37242
12384 y Fo(1)p 36589 12582 1777 49 v 36589 13295 a Fm(p)p
Fo(\()p Fm(n)p Fo(\))38942 12861 y Fr(for)444 b(a)f(sp)34
b(eci\257c)443 b(p)34 b(olynomial)0 14536 y Fq(p)p Fr(\()p
Fp(\242)p Fr(\).)539 b(W)-101 b(e)403 b(sho)-34 b(w)406
b(the)e(follo)-34 b(wing:)0 17653 y Fj(Lemma)464 b(3.2)1239
b Fk(We)-62 b(ak-OT)432 b(exists)h(if)g(and)g(only)g(if)g(OT)h(exists.)
0 19949 y(Pr)-62 b(o)g(of)p Fr(.)1144 b(An)-34 b(y)435
b(OT)f(proto)34 b(col)435 b(is)f(also)g(a)h(W)-101 b(eak-OT)434
b(proto)34 b(col)434 b(since)g(it)h(withstands)h(harder)f(securit)-34
b(y)434 b(require-)0 21454 y(men)-34 b(ts.)527 b(T)-101
b(o)366 b(pro)-34 b(v)g(e)367 b(that)g(W)-101 b(eak-OT)365
b(implies)h(the)g(existence)f(of)i(a)f(strong)h(Naiv)-34
b(e-OT,)365 b(w)-34 b(e)367 b(presen)-34 b(t)366 b(a)g(construc-)0
22959 y(tion)418 b(of)h(an)f(OT)g(proto)34 b(col)418
b(based)g(on)h(a)f(proto)34 b(col)417 b(for)h(W)-101
b(eak-OT.)418 b(Let)f Fq(p)p Fr(\()p Fp(\242)p Fr(\))h(b)34
b(e)418 b(the)g(promised)g(p)34 b(olynomial)418 b(in)0
24465 y(the)405 b(W)-101 b(eak-OT's)403 b(de\257nition)i(of)g(securit)
-34 b(y)403 b(for)i(the)f(receiv)-34 b(er's)402 b(view.)538
b(De\257ne)404 b Fq(t)p Fr(\()p Fq(n)p Fr(\))337 b(=)g
Fq(p)p Fr(\()p Fq(n)p Fr(\))41981 24025 y Fo(2)42507
24465 y Fr(.)p 1882 25723 48573 45 v 1860 40519 45 14797
v 2546 28632 a Fj(OT)4563 28192 y Fm(W)131 b(eak)24 b
FC(\241)p Fm(O)i(T)9237 28632 y Fr(\()p Fq(c;)202 b(b)p
Fr(\))p Fj(:)4027 31466 y Fr(1.)606 b(The)361 b(Sender)f(randomly)g(c)
-34 b(ho)34 b(oses)360 b Fq(t)p Fr(\()p Fq(n)p Fr(\))g(random)g(bits)h
Fq(b)31326 31648 y Fo(1)31852 31466 y Fq(;)202 b(:::;)g(b)34461
31712 y Fm(t)p Fo(\()p Fm(n)p Fo(\))p FC(\241)p Fo(1)37696
31466 y Fp(2)38504 31654 y Fm(R)39611 31466 y Fp(f)p
Fr(0)p Fq(;)g Fr(1)p Fp(g)359 b Fr(and)i(sets)f Fq(b)48092
31712 y Fm(t)p Fo(\()p Fm(n)p Fo(\))5576 33347 y Fr(suc)-34
b(h)405 b(that)h Fq(b)336 b Fr(=)13073 32438 y Fd(L)14420
32708 y Fm(t)p Fo(\()p Fm(n)p Fo(\))14420 33709 y Fm(i)p
Fo(=1)16320 33347 y Fq(b)16840 33529 y Fm(i)17216 33347
y Fr(.)4027 35849 y(2.)606 b(The)405 b(sender)f(and)h(receiv)-34
b(er)402 b(run)j(the)f(proto)34 b(col)404 b(W)-101 b(eak-OT\()p
Fq(c;)202 b(b)34928 36031 y Fm(i)35303 35849 y Fr(\))405
b(for)f(ev)-34 b(ery)403 b Fq(i)p Fr(.)4027 38562 y(3.)606
b(If)404 b Fq(c)337 b Fr(=)f(0,)404 b(then)h(the)f(receiv)-34
b(er)403 b(computes)i Fq(b)336 b Fr(=)27106 37653 y Fd(L)28453
37923 y Fm(t)p Fo(\()p Fm(n)p Fo(\))28453 38924 y Fm(i)p
Fo(=1)30353 38562 y Fq(b)30873 38744 y Fm(i)31249 38562
y Fr(.)p 50432 40519 V 1882 40564 48573 45 v 1882 42316
a(Note:)539 b(Stage)404 b(2)g(can)g(b)34 b(e)404 b(run)h(in)f(parallel)
f(since)h(w)-34 b(e)404 b(are)g(in)g(the)h(semi-honest)f(mo)34
b(del.)606 44611 y(The)405 b(correctness)e(of)i(the)f(ab)34
b(o)-34 b(v)g(e)404 b(proto)34 b(col)404 b(follo)-34
b(ws)405 b(immediately)-101 b(.)606 46933 y Fj(The)496
b(Sender's)h(view:)594 b Fr(Supp)34 b(ose)432 b(the)g(sender)g(can)f
(guess)h(the)g(bit)g Fq(c)f Fr(with)h(adv)-67 b(an)-34
b(tage)433 b(of)44709 46456 y Fo(1)p 44067 46654 1755
49 v 44067 47367 a Fm(q)32 b Fo(\()p Fm(n)p Fo(\))46386
46933 y Fr(for)432 b(a)f(p)34 b(oly-)3030 48609 y(nomial)438
b Fq(q)43 b Fr(\()p Fp(\242)p Fr(\).)641 b(Then)438 b(b)-34
b(y)438 b(a)g(h)-34 b(ybrid)439 b(argumen)-34 b(t,)447
b(there)437 b(is)h(an)g(algorithm)g(that)h(can)f(guess)g
Fq(c)f Fr(on)i(a)e(single)3030 50114 y(w)-34 b(eak-OT)473
b(run)f(with)h(adv)-67 b(an)-34 b(tage)473 b(of)22309
49637 y Fo(1)p 20846 49835 3398 49 v 20846 50548 a Fm(t)p
Fo(\()p Fm(n)p Fo(\))p Fm(q)32 b Fo(\()p Fm(n)p Fo(\))24848
50114 y Fr(th)-34 b(us)473 b(con)-34 b(tradicting)473
b(the)g(w)-34 b(eak-OT)472 b(de\257nition.)743 b(So)472
b(the)3030 51619 y(sender)404 b(can)h(only)f(guess)g(the)h(bit)f
Fq(c)g Fr(with)h(negligible)e(adv)-67 b(an)-34 b(tage.)606
53942 y Fj(The)589 b(Receiv)-39 b(er's)588 b(view:)755
b Fr(T)-101 b(o)512 b(sho)-34 b(w)514 b(that)f(the)f(receiv)-34
b(er's)510 b(adv)-67 b(an)-34 b(tage)513 b(is)f(only)g(negligible)f(w)
-34 b(e)512 b(apply)g(the)3030 55447 y(so)476 b(called)e(Y)-101
b(ao's)476 b(X)-34 b(OR-Lemma.)752 b(Originally)474 b(due)i(to)g(Y)-101
b(ao)475 b(\(in)h(presen)-34 b(tations)477 b(of)f([44]\),)493
b(with)476 b(formal)3030 56953 y(pro)34 b(ofs)405 b(presen)-34
b(ted)405 b(in)f([36,)f(26)q(,)g(23].)539 b(The)404 b(X)-34
b(OR-Lemma)404 b(states)h(the)g(follo)-34 b(wing:)3030
58866 y(Supp)34 b(ose)527 b(that)g Fq(P)708 b Fr(:)539
b Fp(f)p Fr(0)p Fq(;)202 b Fr(1)p Fp(g)15979 58427 y
Fm(m)17406 58866 y Fp(!)539 b(f)p Fr(0)p Fq(;)202 b Fr(1)p
Fp(g)526 b Fr(is)f(a)h(predicate)f(that)i(is)f(\\w)-34
b(eakly)525 b(hard)h(to)g(compute".)904 b(Let)3030 60372
y Fq(x)3723 59932 y Fo(\()p Fm(t)p Fo(\))5267 60372 y
Fr(=)417 b(\()p Fq(x)7791 60554 y Fo(1)8317 60372 y Fq(;)202
b(:::;)g(x)11099 60554 y Fm(t)11492 60372 y Fr(\))453
b(b)34 b(e)452 b(a)g Fq(t)p Fr(-tuple)g(of)h(indep)34
b(enden)-34 b(t)454 b(inputs)g(to)e Fq(P)168 b Fr(.)684
b(Denote)452 b Fq(P)39912 59932 y Fo(\()p Fm(t)p Fo(\))41040
60372 y Fr(\()p Fq(x)42204 59932 y Fo(\()p Fm(t)p Fo(\))43331
60372 y Fr(\))417 b(=)45579 59463 y Fd(L)46926 59813
y Fm(t)46926 60730 y(i)p Fo(=1)48706 60372 y Fq(P)168
b Fr(\()p Fq(x)50816 60554 y Fm(i)51192 60372 y Fr(\).)3030
61877 y(Then)405 b(the)g(lemma)f(asserts)g(that)h Fq(P)19690
61437 y Fm(t)20490 61877 y Fr(is)f(\\strongly)g(hard)h(to)f(compute".)
539 b(F)-101 b(ormally:)3030 64339 y Fj(Theorem)464 b(7.1)h(\(The)g(X)
-39 b(OR-Lemma\))606 b Fk(Supp)-62 b(ose)409 b(that)h(any)h(PPTMA)h
(fails)e(to)h(c)-62 b(ompute)409 b Fq(P)168 b Fr(\()p
Fq(x)p Fr(\))413 b Fk(with)3030 65844 y(pr)-62 b(ob)g(ability)329
b(b)-62 b(etter)331 b(than)g Fr(1)49 b Fp(\241)17116
65367 y Fo(1)p 16463 65565 1777 49 v 16463 66278 a Fm(p)p
Fo(\()p Fm(n)p Fo(\))18704 65844 y Fk(for)332 b(al)62
b(l)331 b(but)g(\257nitely)h(many)g Fq(n)g Fk(for)g(al)62
b(l)331 b(auxiliary)f(information)h(and)h(for)f(a)3030
67714 y(given)412 b(p)-62 b(olynomial)411 b Fq(p)p Fr(\()p
Fp(\242)p Fr(\))p Fk(.)551 b(T)-93 b(ake)412 b Fq(t)p
Fr(\()p Fq(n)p Fr(\))337 b(=)f Fq(p)p Fr(\()p Fq(n)p
Fr(\))23989 67274 y Fo(2)24515 67714 y Fk(.)551 b(Then)413
b(any)f(PPTMA)i(fails)d(to)i(c)-62 b(ompute)411 b Fq(P)45505
67274 y Fo(\()p Fm(t)p Fo(\()p Fm(n)p Fo(\)\))47935 67714
y Fr(\()p Fq(x)49099 67274 y Fo(\()p Fm(t)p Fo(\()p Fm(n)p
Fo(\)\))51529 67714 y Fr(\))3030 69220 y Fk(with)396
b(pr)-62 b(ob)g(ability)393 b(b)-62 b(etter)394 b(than)17604
68742 y Fo(1)p 17604 68940 471 49 v 17604 69638 a(2)18395
69220 y Fr(+)20301 68742 y Fo(1)p 19659 68940 1755 49
v 19659 69653 a Fm(q)32 b Fo(\()p Fm(n)p Fo(\))21943
69220 y Fk(for)396 b(any)g(p)-62 b(olynomial)394 b Fq(q)43
b Fr(\()p Fq(n)p Fr(\))397 b Fk(for)f(al)62 b(l)395 b(auxiliary)f
(information)h(and)3030 70895 y(for)373 b(al)62 b(l)373
b(but)f(\257nitely)g(many)i Fq(n)p Fk('s)e(\(the)g(pr)-62
b(ob)g(abilities)369 b(ar)-62 b(e)373 b(taken)f(over)g(a)h(given)g
(distribution)d(on)j(the)f(inputs)3030 72400 y Fq(x)337
b Fp(2)g(f)p Fr(0)p Fq(;)202 b Fr(1)p Fp(g)8168 71960
y Fm(m)9489 72400 y Fk(and)433 b(the)f(r)-62 b(andomness)433
b(of)g(the)f(PPTMs\).)25394 75721 y Fr(22)p eop
%%Page: 23 24
23 23 bop 3030 818 a Fr(In)393 b(our)g(application)g(w)-34
b(e)393 b(tak)-34 b(e)393 b Fq(x)18013 1000 y Fm(i)18725
818 y Fr(=)337 b Fe(view)22803 308 y Fm(W)131 b(eak)24
b FC(\241)p Fm(O)i(T)22803 1179 y(r)g(eceiv)32 b(er)27477
818 y Fr(\()p Fq(c)337 b Fr(=)f(0)p Fq(;)202 b(b)31754
1000 y Fm(i)32130 818 y Fr(\))393 b(and)g Fq(P)168 b
Fr(\()p Fq(x)37449 1000 y Fm(i)37826 818 y Fr(\))337
b(=)f Fq(b)40433 1000 y Fm(i)40809 818 y Fr(.)535 b(By)392
b(the)h(de\257nition)h(of)3030 2323 y(W)-101 b(eak-OT,)421
b Fq(P)590 b Fr(is)422 b(indeed)f(w)-34 b(eakly)422 b(hard.)591
b(The)422 b(conclusion)g(is)g(that)g(if)g Fq(c)365 b
Fr(=)h(0,)426 b(then)c(the)g(sender)g(cannot)3030 4049
y(predict)431 b(the)h(bit)f Fq(b)382 b Fr(=)13421 3140
y Fd(L)14768 3410 y Fm(p)p Fo(\()p Fm(n)p Fo(\))16545
3098 y Fl(2)14768 4411 y Fm(i)p Fo(=1)17263 4049 y Fq(b)17783
4231 y Fm(i)18589 4049 y Fr(from)432 b(the)f(view)f(of)i(OT)29643
3609 y Fm(W)131 b(eak)24 b FC(\241)p Fm(O)i(T)34748 4049
y Fr(with)432 b(a)e(non-negligible)h(adv)-67 b(an)-34
b(tage,)3030 5554 y(as)405 b(required)e(in)h(a)g(strong)h(OT)f(proto)34
b(col.)p 2690 8158 788 788 v 0 11941 a Fs(8)1793 b(F)-149
b(urther)599 b(Issues)0 14647 y Fj(The)404 b(Symmetric)g(SFE)g(Mo)39
b(del:)1213 b Fr(In)352 b(this)g(mo)34 b(del,)362 b(b)34
b(oth)352 b(sides)g(receiv)-34 b(e)350 b(the)i(output)i
Fq(f)130 b Fr(\()p Fq(x;)202 b(y)43 b Fr(\))353 b(at)f(the)g(end)h(of)0
16153 y(the)424 b(proto)34 b(col.)595 b(Actually)-101
b(,)427 b(most)d(of)f(the)h(w)-34 b(orks)423 b(considering)g(the)h
(questions)f(of)h(completeness)f(and)h(trivialit)-34
b(y)0 17658 y(w)g(ere)320 b(conducted)i(in)e(this)h(setting)g(\(e.g.)
511 b([10,)320 b(34,)g(31,)g(35,)g(33])h(and)g(part)g(of)g([32)o(]\).)
511 b(While)320 b(the)h(study)g(of)g(Bo)34 b(olean)0
19164 y(functions)439 b(in)f(this)h(mo)34 b(del,)446
b(yielded)437 b(clean)h(and)g(tigh)-34 b(t)439 b(results)g([10)o(],)446
b(this)439 b(is)e(not)i(the)g(case)e(when)i(considering)0
20669 y(non-Bo)34 b(olean)466 b(functions.)725 b(In)466
b(fact)h(Kushilevitz)e([34])g(demonstrates)i(a)f(function)i(that)f(is)e
(neither)h(complete)0 22174 y(nor)404 b(trivial)f(in)h(the)h
(information)g(theoretic)f(mo)34 b(del,)403 b(so)i(no)f(tigh)-34
b(t)405 b(c)-34 b(haracterization)404 b(can)h(b)34 b(e)403
b(exp)34 b(ected.)1882 23680 y(On)306 b(the)g(other)f(hand,)327
b(Kilian)305 b([31)o(])h(did)g(sho)-34 b(w)307 b(that)f(the)g(complete)
g(functions)h(are)e(exactly)g(those)h(con)-34 b(taining)0
25185 y(an)368 b(im)-34 b(b)34 b(edded)369 b(OR.)e(Here)g(as)h(w)-34
b(ell,)375 b(the)368 b(pro)34 b(of)368 b(that)h(if)f(a)f(function)j(do)
34 b(es)367 b(not)i(con)-34 b(tain)369 b(an)f(im)-34
b(b)34 b(edded)368 b(OR)g(then)0 26691 y(it)400 b(is)g(not)g(complete)g
(w)-34 b(orks)400 b(only)g(for)g(\257nite)h(functions)g(\(it)f(uses)h
(a)f(reduction)g(that)h(is)f(not)h(p)34 b(olynomial)399
b(time\).)0 28196 y(Moreo)-34 b(v)g(er)311 b(when)i(discussing)g
(computational)g(securit)-34 b(y)-101 b(,)330 b(the)312
b(follo)-34 b(wing)313 b(example)e(sho)-34 b(ws)314 b(a)e(function)h
(that)g(do)34 b(es)0 29702 y(not)405 b(con)-34 b(tain)405
b(an)f(im)-34 b(b)34 b(edded)405 b(OR)f(but)i(is)e(still)f(complete:)0
32012 y Fj(Example)464 b(4)606 b Fk(L)-62 b(et)353 b
Fq(g)380 b Fr(:)336 b Fp(f)p Fr(0)p Fq(;)202 b Fr(1)p
Fp(g)13665 31572 y Fm(n)14628 32012 y Fp(\303)337 b(f)p
Fr(0)p Fq(;)202 b Fr(1)p Fp(g)19140 31572 y Fm(n)20119
32012 y Fk(b)-62 b(e)353 b(a)f(one-one)g(one-way)g(function,)368
b(and)353 b(let)f Fq(x)41329 32194 y Fo(0)41854 32012
y Fq(;)202 b(x)43086 32194 y Fo(1)43612 32012 y Fq(;)g(y)44745
32194 y Fo(0)45270 32012 y Fq(;)g(y)46403 32194 y Fo(1)47266
32012 y Fp(2)337 b(f)p Fr(0)p Fq(;)202 b Fr(1)p Fp(g)51374
31572 y Fm(n)0 33517 y Fk(and)433 b Fq(c)336 b Fp(2)h(f)p
Fr(0)p Fq(;)202 b Fr(1)p Fp(g)p Fk(.)557 b(De\257ne)434
b(the)f(function)f Fq(f)468 b Fr(:)336 b Fp(f)p Fr(0)p
Fq(;)202 b Fr(1)p Fp(g)23560 33078 y Fo(2)p Fm(n)p Fo(+1)26129
33517 y Fp(\243)269 b(f)p Fr(0)p Fq(;)202 b Fr(1)p Fp(g)30304
33078 y Fo(2)p Fm(n)31737 33517 y Fp(!)337 b(f)p Fr(0)p
Fq(;)202 b Fr(1)p Fp(g)36249 33078 y Fo(2)p Fm(n)37779
33517 y Fk(as)433 b(fol)62 b(lows:)13856 36011 y Fq(f)130
b Fr(\(\()p Fq(c;)202 b(x)17278 36193 y Fo(0)17805 36011
y Fq(;)g(x)19037 36193 y Fo(1)19562 36011 y Fr(\))p Fq(;)g
Fr(\()p Fq(y)21637 36193 y Fo(0)22164 36011 y Fq(;)g(y)23297
36193 y Fo(1)23822 36011 y Fr(\)\))338 b(=)e(\()p Fq(x)27545
36193 y Fo(0)28341 36011 y Fp(\251)269 b Fq(y)30147 36193
y Fm(c)30610 36011 y Fq(;)202 b(x)31842 36193 y Fo(1)32636
36011 y Fp(\251)270 b Fq(g)43 b Fr(\()p Fq(y)35535 36193
y Fo(1)p FC(\241)p Fm(c)37201 36011 y Fr(\)\))0 38504
y(The)493 b(function)h Fq(f)623 b Fr(do)34 b(es)492 b(not)h(con)-34
b(tain)493 b(an)g(im)-34 b(b)34 b(edded)493 b(Or)f(\(ev)-34
b(ery)492 b(ro)-34 b(w)492 b(is)g(a)h(one-one)f(function\),)516
b(but)494 b(can)e(b)34 b(e)0 40009 y(sho)-34 b(wn)425
b(to)f(b)34 b(e)423 b(complete)g(in)g(the)h(symmetric)f(mo)34
b(del.)596 b(This)424 b(lea)-34 b(v)g(es)423 b(ro)34
b(om)423 b(to)g(try)h(and)g(\257nd)g(a)g(computational)0
41515 y(c)-34 b(haracterization)404 b(in)g(this)h(mo)34
b(del)403 b(as)i(w)-34 b(ell.)0 44680 y Fj(Probabilistic)371
b(F)-116 b(unctionalities:)1213 b Fr(Kilian)321 b([32])h(giv)-34
b(es)321 b(com)-34 b(binatorial)322 b(criteria)f(also)h(for)g(secure)f
(ev)-67 b(aluation)0 46186 y(of)603 b(probabilistic)f(functionalities)i
(\(rather)f(than)g(deterministic)g(functions\).)1135
b(It)603 b(is)f(in)-34 b(teresting)603 b(to)g(see)f(if)0
47691 y(computational)359 b(results)g(can)f(b)34 b(e)358
b(found)h(in)f(this)h(mo)34 b(del)358 b(as)g(w)-34 b(ell.)523
b(While)357 b(it)h(is)g(kno)-34 b(wn)359 b(that)h(giv)-34
b(en)357 b(OT)i(one)f(can)0 49197 y(ac)-34 b(hiev)g(e)392
b(SFE)h(of)h(an)-34 b(y)393 b(functionalit)-34 b(y)-101
b(,)396 b(it)c(is)h(in)-34 b(teresting)393 b(what)h(can)f(b)34
b(e)392 b(ac)-34 b(hiev)g(ed)393 b(on)g(lesser)e(assumptions.)537
b(F)-101 b(or)0 50702 y(example,)368 b(consider)360 b(a)g(proto)34
b(col)360 b(in)g(whic)-34 b(h)361 b(neither)f(part)-34
b(y)361 b(has)f(an)h(input)g(at)g(all,)368 b(and)360
b(in)h(whic)-34 b(h)361 b(Alice)d(receiv)-34 b(es)0 52208
y(as)436 b(output)h Fq(g)43 b Fr(\()p Fq(z)53 b Fr(\))437
b(for)f(a)f(function)i Fq(g)479 b Fr(and)436 b(a)g(random)g(input)h
Fq(z)488 b Fr(unkno)-34 b(wn)438 b(to)e(b)34 b(oth)436
b(Alice)f(and)h(Bob.)633 b(This)436 b(is)f(a)0 53713
y(go)34 b(o)g(d)394 b(example)f(of)i(an)f(SFE)h(of)f(a)g(probabilistic)
h(functionalit)-34 b(y)395 b(that)g(w)-34 b(e)395 b(call)e
Fk(inter)-62 b(active)422 b(oblivious)f(sampling)0 55218
y Fr(\(IOS\))488 b(and)h(has)f(useful)h(applications.)790
b(F)-101 b(or)488 b(instance,)509 b(IOS)488 b(can)g(b)34
b(e)487 b(used)i(in)f(order)f(to)h(build)h(an)f(oblivious)0
56724 y(transfer)439 b(proto)34 b(col)439 b(giv)-34 b(en)438
b(a)h(secret)f(k)-34 b(ey)439 b(agreemen)-34 b(t)439
b(proto)34 b(col.)642 b(It)439 b(is)f(not)i(kno)-34 b(wn)440
b(what)g(functions)g Fq(g)482 b Fr(can)439 b(b)34 b(e)0
58229 y(obliviously)403 b(sampled)i(if)f(the)h(existence)e(of)h(OT)h
(is)e(not)i(guaran)-34 b(teed.)0 61395 y Fj(Ac)-39 b(kno)g(wledgmen)g
(ts:)1213 b Fr(W)-101 b(e)491 b(are)h(grateful)h(to)f(T)-101
b(al)493 b(Malkin)f(for)g(discussions)h(regarding)f(her)g(w)-34
b(ork)493 b(on)f(this)0 62900 y(sub)67 b(ject)397 b(and)g(to)f(Ran)g
(Canetti)h(for)f(his)g(helpful)g(commen)-34 b(ts)397
b(on)f(this)g(pap)34 b(er.)536 b(W)-101 b(e)395 b(also)h(thank)g(Ronen)
h(Shaltiel)0 64406 y(for)404 b(useful)h(advice)e(regarding)h(hardness)h
(ampli\257cation.)0 68189 y Fs(References)606 70895 y
Fr([1])606 b(W.)301 b(Aiello)h(and)h(J.)f(Hastad.)372
b(Statistical)303 b(zero-kno)-34 b(wledge)303 b(languages)g(can)f(b)34
b(e)302 b(recognized)g(in)g(t)-34 b(w)g(o)304 b(rounds.)2492
72400 y Fk(Journal)433 b(of)f(Computer)h(and)g(Systems)f(Scienc)-62
b(es)432 b(\(JCSS\))p Fr(,)405 b(42\(3\):327{345,)g(1991.)25394
75721 y(23)p eop
%%Page: 24 25
24 24 bop 606 818 a Fr([2])606 b(A.)406 b(Beimel,)g(T.)h(Malkin,)g(and)
h(S.)f(Micali.)545 b(The)408 b(all-or-nothing)f(nature)h(of)f(t)-34
b(w)g(o-part)g(y)409 b(secure)e(computa-)2492 2323 y(tion.)554
b(In)410 b Fk(A)-62 b(dvanc)g(es)437 b(in)i(Cryptolo)-62
b(gy)436 b(-)j(CR)-93 b(YPTO)440 b('99,)f(L)-62 b(e)g(ctur)g(e)437
b(Notes)h(in)h(Computer)e(Scienc)-62 b(e)p Fr(,)410 b(v)-34
b(olume)2492 3829 y(1666,)404 b(pages)g(80{97.)g(Springer,)g(1999.)606
6330 y([3])606 b(M.)408 b(Bellare)f(and)j(S.)f(Micali.)551
b(Non-in)-34 b(teractiv)g(e)409 b(oblivious)g(transfer)h(and)f
(applications.)553 b(In)409 b Fk(A)-62 b(dvanc)g(es)436
b(in)2492 7836 y(Cryptolo)-62 b(gy)468 b(-)k(CR)-93 b(YPTO)473
b('89,)479 b(L)-62 b(e)g(ctur)g(e)470 b(Notes)g(in)i(Computer)e(Scienc)
-62 b(e)p Fr(,)454 b(v)-34 b(olume)446 b(435,)455 b(pages)446
b(547{557.)2492 9341 y(Springer,)404 b(1989.)606 11843
y([4])606 b(M.)406 b(Ben-Or,)f(S.)h(Goldw)-34 b(asser,)408
b(and)f(A.)f(Wigderson.)543 b(Completeness)407 b(theorems)g(for)f
(non-cryptographic)2492 13348 y(fault-toleran)-34 b(t)324
b(distributed)f(computation.)406 b(In)323 b Fk(20th)356
b(A)-31 b(CM)359 b(Symp)-62 b(osium)357 b(on)h(the)g(The)-62
b(ory)357 b(of)h(Computing)p Fr(,)2492 14854 y(pages)404
b(1{10,)g(1988.)606 17356 y([5])606 b(C.H.)356 b(Bennett,)366
b(G.)356 b(Brassard,)365 b(C.)356 b(Crep)34 b(eau,)365
b(and)357 b(M.H.)f(Skubiszewsk)-67 b(a.)459 b(Practical)355
b(quan)-34 b(tum)358 b(oblivious)2492 18861 y(transfer)530
b(proto)34 b(cols.)914 b(In)530 b Fk(A)-62 b(dvanc)g(es)548
b(in)i(Cryptolo)-62 b(gy)547 b(-)i(CR)-93 b(YPTO)552
b('91,)577 b(L)-62 b(e)g(ctur)g(e)548 b(Notes)g(in)j(Computer)2492
20367 y(Scienc)-62 b(e)p Fr(,)402 b(v)-34 b(olume)404
b(576,)g(pages)h(351{366.)f(Springer,)g(1992.)606 22868
y([6])606 b(R.)355 b(Boppana,)366 b(J.)355 b(Hastad,)366
b(and)356 b(S.)g(Zac)-34 b(hos.)458 b(Do)34 b(es)355
b(co-np)h(ha)-34 b(v)g(e)356 b(short)g(in)-34 b(teractiv)g(e)356
b(pro)34 b(ofs?)626 b Fk(Information)2492 24374 y(Pr)-62
b(o)g(c)g(essing)431 b(L)-62 b(etters)p Fr(,)403 b(25\(2\):127{132,)i
(1987.)606 26875 y([7])606 b(C.)436 b(Cac)-34 b(hin,)446
b(C.)436 b(Crep)34 b(eau,)445 b(and)437 b(J.)g(Marcil.)633
b(Oblivious)436 b(transfer)h(with)h(a)e(memory-b)34 b(ound)438
b(receiv)-34 b(er.)632 b(In)2492 28381 y Fk(39th)432
b(IEEE)i(Symp)-62 b(osium)432 b(on)i(F)-93 b(oundations)432
b(of)g(Computer)h(Scienc)-62 b(e)p Fr(,)402 b(pages)j(493{502,)f(1995.)
606 30883 y([8])606 b(R.)358 b(Canetti.)463 b(Securit)-34
b(y)359 b(and)g(comp)34 b(osition)358 b(of)h(m)-34 b(ultipart)g(y)360
b(cryptographic)e(proto)34 b(cols.)462 b Fk(Journal)391
b(of)g(Cryp-)2492 32388 y(tolo)-62 b(gy)p Fr(,)401 b(13\(1\):143{202,)k
(2000.)606 34890 y([9])606 b(D.)349 b(Chaum,)362 b(C.)351
b(Crep)34 b(eau,)360 b(and)351 b(I.)f(Damgard.)450 b(Multipart)-34
b(y)351 b(unconditionally)g(secure)e(proto)34 b(cols.)449
b(In)351 b Fk(20th)2492 36395 y(A)-31 b(CM)433 b(Symp)-62
b(osium)433 b(on)g(the)g(The)-62 b(ory)432 b(of)h(Computing)p
Fr(,)402 b(pages)j(11{19,)f(1988.)0 38897 y([10])606
b(B.)536 b(Chor)j(and)f(E.)f(Kushilevitz.)935 b(A)537
b(zero-one)g(la)-34 b(w)538 b(for)g(b)34 b(o)g(olean)537
b(priv)-67 b(acy)-101 b(.)934 b Fk(SIAM)557 b(Journal)f(on)g(Disc.)2492
40403 y(Math.)p Fr(,)402 b(4\(1\):36{47,)i(1991.)538
b(preliminary)403 b(v)-34 b(ersion)404 b(in)g(STOC)h(89.)0
42904 y([11])606 b(C.)299 b(Crep)34 b(eau.)366 b(Equiv)-67
b(alence)298 b(b)34 b(et)-34 b(w)g(een)301 b(t)-34 b(w)g(o)300
b(\260a)-34 b(v)g(ours)301 b(of)f(oblivious)f(transfers.)367
b(In)299 b Fk(A)-62 b(dvanc)g(es)335 b(in)j(Cryptolo)-62
b(gy)2492 44410 y(-)531 b(CR)-93 b(YPTO)533 b('87,)554
b(L)-62 b(e)g(ctur)g(e)530 b(Notes)g(in)i(Computer)e(Scienc)-62
b(e)p Fr(,)536 b(v)-34 b(olume)510 b(293,)537 b(pages)511
b(350{354.)g(Springer-)2492 45915 y(V)-101 b(erlag,)403
b(1987.)0 48417 y([12])606 b(C.)412 b(Crep)34 b(eau)412
b(and)h(J.)f(Kilian.)561 b(Ac)-34 b(hieving)412 b(oblivious)g(transfer)
h(using)f(w)-34 b(eak)g(ened)413 b(securit)-34 b(y)412
b(assumptions.)2492 49922 y(In)404 b Fk(29th)432 b(IEEE)i(Symp)-62
b(osium)432 b(on)i(F)-93 b(oundations)432 b(of)h(Computer)f(Scienc)-62
b(e)p Fr(,)402 b(pages)j(42{52,)f(1988.)0 52424 y([13])606
b(I.)421 b(Damgard,)426 b(J.)421 b(Kilian,)k(and)e(L.)e(Salv)-67
b(ail.)588 b(On)422 b(the)h(\(im\)p)34 b(ossibilit)-34
b(y)422 b(of)g(basing)g(oblivious)g(transfer)g(and)2492
53930 y(bit)500 b(commitmen)-34 b(t)501 b(on)g(w)-34
b(eak)g(ened)501 b(securit)-34 b(y)500 b(assumptions.)825
b(In)501 b Fk(A)-62 b(dvanc)g(es)520 b(in)i(Cryptolo)-62
b(gy)519 b(-)j(Eur)-62 b(o)g(crypt)2492 55435 y('99,)432
b(L)-62 b(e)g(ctur)g(e)432 b(Notes)g(in)i(Computer)e(Scienc)-62
b(e)p Fr(,)403 b(v)-34 b(olume)404 b(1592,)g(pages)g(56{73,)g(1999.)0
57937 y([14])606 b(S.)375 b(Ev)-34 b(en,)380 b(O.)375
b(Goldreic)-34 b(h,)381 b(and)376 b(A.)e(Lemp)34 b(el.)489
b(A)375 b(randomized)h(proto)34 b(col)375 b(for)g(signing)h(con)-34
b(tracts.)490 b Fk(Commu-)2492 59442 y(nic)-62 b(ations)432
b(of)h(the)f(A)-31 b(CM)p Fr(,)404 b(28\(6\):637{647,)h(1985.)0
61944 y([15])606 b(M.)583 b(Fitzi,)628 b(J.A.)582 b(Gara)-34
b(y)-101 b(,)629 b(U.M.)583 b(Maurer,)627 b(and)585 b(R.)e(Ostro)-34
b(vsky:.)1071 b(Minimal)583 b(complete)h(primitiv)-34
b(es)583 b(for)2492 63449 y(secure)397 b(m)-34 b(ulti-part)g(y)399
b(computation.)528 b(In)398 b Fk(A)-62 b(dvanc)g(es)426
b(in)i(Cryptolo)-62 b(gy)425 b(-)i(CR)-93 b(YPTO)430
b('01,)d(L)-62 b(e)g(ctur)g(e)427 b(Notes)f(in)2492 64955
y(Computer)432 b(Scienc)-62 b(e)p Fr(,)402 b(v)-34 b(olume)405
b(2139,)f(pages)g(80{100.)g(Springer,)g(2001.)0 67457
y([16])606 b(L.)564 b(F)-101 b(ortno)-34 b(w.)1017 b(The)566
b(complexit)-34 b(y)564 b(of)h(p)34 b(erfect)565 b(zero-kno)-34
b(wledge.)1016 b Fk(A)-62 b(dvanc)g(es)579 b(in)j(Computing)e(R)-62
b(ese)g(ar)g(ch)2492 68962 y(\(e)g(ditor)431 b(S.)j(Mic)-62
b(ali\))p Fr(,)401 b(18,)j(1989.)25394 75721 y(24)p eop
%%Page: 25 26
25 25 bop 0 818 a Fr([17])606 b(Y.)594 b(Gertner,)643
b(S.)595 b(Kannan,)644 b(T.)595 b(Malkin,)642 b(O.)595
b(Reingold,)642 b(and)596 b(M.)f(Visw)-34 b(anathan.)1109
b(The)596 b(relationship)2492 2323 y(b)34 b(et)-34 b(w)g(een)286
b(public)f(k)-34 b(ey)284 b(encryption)i(and)f(oblivious)g(transfer.)
344 b(In)285 b Fk(41st)322 b(IEEE)j(Symp)-62 b(osium)323
b(on)h(F)-93 b(oundations)2492 3829 y(of)432 b(Computer)h(Scienc)-62
b(e)p Fr(,)402 b(pages)j(325{335,)f(2000.)0 6268 y([18])606
b(O.)403 b(Goldreic)-34 b(h.)537 b Fk(F)-93 b(oundations)432
b(of)h(Crypto)-62 b(gr)g(aphy)p Fr(.)533 b(Cam)-34 b(bridge)405
b(Univ)-34 b(ersit)g(y)404 b(Press,)g(2001.)0 8708 y([19])606
b(O.)741 b(Goldreic)-34 b(h.)1543 b(F)-101 b(oundations)744
b(of)e(cryptograph)-34 b(y)742 b(-)g(v)-34 b(olume)742
b(2.)1543 b(W)-101 b(orking)741 b(Draft,)827 b(a)-34
b(v)-67 b(ailable)741 b(at)2492 10213 y(www.wisdom.w)-34
b(eizmann.ac.il/o)34 b(ded/fo)g(c-v)-34 b(ol2.h)g(tml,)405
b(2002.)0 12653 y([20])606 b(O.)438 b(Goldreic)-34 b(h)438
b(and)h(L.A.)f(Levin.)639 b(A)438 b(hard-core)h(predicate)f(for)h(all)f
(one-w)-34 b(a)g(y)439 b(functions.)641 b(In)439 b Fk(21st)464
b(A)-31 b(CM)2492 14158 y(Symp)-62 b(osium)432 b(on)h(the)g(The)-62
b(ory)432 b(of)h(Computing)p Fr(,)402 b(pages)j(25{32,)f(1989.)0
16598 y([21])606 b(O.)563 b(Goldreic)-34 b(h,)603 b(S.)563
b(Micali,)602 b(and)565 b(A.)e(Wigderson.)1012 b(Ho)-34
b(w)565 b(to)f(pla)-34 b(y)563 b(an)-34 b(y)564 b(men)-34
b(tal)565 b(game)e(-)h(a)f(complete-)2492 18103 y(ness)435
b(theorem)g(for)h(proto)34 b(cols)435 b(with)h(honest)g(ma)67
b(jorit)-34 b(y)-101 b(.)631 b(In)435 b Fk(19th)461 b(A)-31
b(CM)463 b(Symp)-62 b(osium)460 b(on)j(the)e(The)-62
b(ory)461 b(of)2492 19609 y(Computing)p Fr(,)402 b(pages)i(218{229,)g
(1987.)0 22048 y([22])606 b(O.)389 b(Goldreic)-34 b(h,)393
b(S.)d(Micali,)i(and)f(A.)e(Wigderson.)515 b(Pro)34 b(ofs)390
b(that)h(yield)f(nothing)h(but)h(their)e(v)-67 b(alidit)-34
b(y)-101 b(,)392 b(or)e(all)2492 23554 y(languages)381
b(in)g(np)h(ha)-34 b(v)g(e)381 b(zero-kno)-34 b(wledge)381
b(pro)34 b(of)381 b(systems.)500 b Fk(Journal)411 b(of)h(the)f(A)-31
b(CM)p Fr(,)381 b(38:691{729,)k(1)c(1991.)0 25993 y([23])606
b(O.)407 b(Goldreic)-34 b(h,)409 b(N.)f(Nisan,)h(and)g(A.)f(Wigderson.)
549 b(On)408 b(Yao's)g(X)-34 b(OR-lemma.)550 b(In)408
b Fk(Ele)-62 b(ctr)g(onic)436 b(Col)62 b(lo)-62 b(quium)2492
27499 y(on)433 b(Computational)e(Complexity)h(\(ECCC\))i(\(50\))p
Fr(,)402 b(v)-34 b(olume)404 b(2,)g(1995.)0 29939 y([24])606
b(O.)380 b(Goldreic)-34 b(h)381 b(and)g(R.)g(V)-101 b(ainish.)500
b(Ho)-34 b(w)381 b(to)g(solv)-34 b(e)381 b(an)-34 b(y)381
b(proto)34 b(col)381 b(problem)g(-)f(an)i(e\261ciency)d(impro)-34
b(v)g(emen)g(t.)2492 31444 y(In)442 b Fk(A)-62 b(dvanc)g(es)467
b(in)i(Cryptolo)-62 b(gy)466 b(-)j(CR)-93 b(YPTO)470
b('87,)477 b(L)-62 b(e)g(ctur)g(e)467 b(Notes)g(in)i(Computer)f(Scienc)
-62 b(e)p Fr(,)451 b(v)-34 b(olume)442 b(293,)2492 32949
y(pages)404 b(73{86.)g(Springer-V)-101 b(erlag,)403 b(1987.)0
35389 y([25])606 b(M.)422 b(Hirt)g(and)h(U.)f(Maurer.)592
b(Pla)-34 b(y)g(er)422 b(sim)-34 b(ulation)423 b(and)g(general)f(adv)
-34 b(ersary)422 b(structures)h(in)f(p)34 b(erfect)422
b(m)-34 b(ulti-)2492 36894 y(part)g(y)404 b(computation.)539
b Fk(Journal)433 b(of)g(Cryptolo)-62 b(gy)p Fr(,)401
b(13\(1\):31{60,)j(2000.)0 39334 y([26])606 b(R.)275
b(Impagliazzo.)327 b(Hard-core)276 b(distributions)h(for)f(somewhat)h
(hard)f(problems.)328 b(In)276 b Fk(36th)314 b(IEEE)j(Symp)-62
b(osium)2492 40840 y(on)433 b(F)-93 b(oundations)432
b(of)h(Computer)f(Scienc)-62 b(e)p Fr(,)403 b(pages)h(538{545,)g(1995.)
0 43279 y([27])606 b(R.)540 b(Impagliazzo.)942 b(A)541
b(p)34 b(ersonal)540 b(view)g(of)g(a)-34 b(v)g(erage-case)540
b(complexit)-34 b(y)-101 b(.)943 b(In)540 b Fk(10th)558
b(A)-31 b(nnual)558 b(Structur)-62 b(e)558 b(in)2492
44785 y(Complexity)431 b(The)-62 b(ory)433 b(Confer)-62
b(enc)g(e)p Fr(,)403 b(pages)h(134{147.)g(IEEE)g(Computer)h(So)34
b(ciet)-34 b(y)404 b(Press,)f(1995.)0 47224 y([28])606
b(R.)445 b(Impagliazzo)g(and)i(M.)f(Lub)-34 b(y)-101
b(.)662 b(One-w)-34 b(a)g(y)446 b(functions)i(are)d(essen)-34
b(tial)446 b(for)g(complexit)-34 b(y)445 b(based)i(cryptog-)2492
48730 y(raph)-34 b(y)-101 b(.)537 b(In)404 b Fk(30th)432
b(IEEE)j(Symp)-62 b(osium)432 b(on)i(F)-93 b(oundations)431
b(of)i(Computer)f(Scienc)-62 b(e)p Fr(,)403 b(pages)i(230{235,)f(1989.)
0 51169 y([29])606 b(R.)374 b(Impagliazzo)g(and)h(S.)g(Rudic)-34
b(h.)490 b(Limits)374 b(on)h(the)g(pro)-34 b(v)-67 b(able)375
b(consequences)f(of)h(one-w)-34 b(a)g(y)376 b(p)34 b(erm)-34
b(utations.)2492 52675 y(In)404 b Fk(21st)432 b(A)-31
b(CM)434 b(Symp)-62 b(osium)432 b(on)h(the)g(The)-62
b(ory)432 b(of)h(Computing)p Fr(,)402 b(pages)j(44{61,)f(1989.)0
55114 y([30])606 b(J.)554 b(Kilian.)985 b(F)-101 b(ounding)556
b(cryptograph)-34 b(y)555 b(on)g(oblivious)g(transfer.)986
b(In)555 b Fk(20th)570 b(A)-31 b(CM)572 b(Symp)-62 b(osium)571
b(on)h(the)2492 56620 y(The)-62 b(ory)432 b(of)h(Computing)p
Fr(,)402 b(pages)j(20{31,)f(1988.)0 59059 y([31])606
b(J.)393 b(Kilian.)519 b(A)394 b(general)f(completeness)g(theorem)h
(for)g(t)-34 b(w)g(o-part)g(y)396 b(games.)520 b(In)393
b Fk(23r)-62 b(d)423 b(A)-31 b(CM)425 b(Symp)-62 b(osium)422
b(on)2492 60565 y(the)432 b(The)-62 b(ory)432 b(of)h(Computing)p
Fr(,)403 b(pages)h(553{560,)g(1991.)0 63004 y([32])606
b(J.)512 b(Kilian.)859 b(More)512 b(general)g(completeness)g(theorems)h
(for)f(secure)g(t)-34 b(w)g(o-part)g(y)515 b(computation.)861
b(In)513 b Fk(32nd)2492 64510 y(A)-31 b(CM)433 b(Symp)-62
b(osium)433 b(on)g(the)g(The)-62 b(ory)432 b(of)h(Computing)p
Fr(,)402 b(pages)j(316{324,)f(2000.)0 66949 y([33])606
b(J.)313 b(Kilian,)332 b(E.)313 b(Kushilevitz,)332 b(S.)314
b(Micali,)331 b(and)315 b(R.)f(Ostro)-34 b(vsky)-101
b(.)390 b(Reducibilit)-34 b(y)315 b(and)g(completeness)f(in)h(priv)-67
b(ate)2492 68455 y(computations.)538 b Fk(SIAM)435 b(Journal)e(of)g
(Computing)p Fr(,)402 b(28\(4\):1189{1208,)j(2000.)0
70895 y([34])606 b(E.)624 b(Kushilevitz.)1196 b(Priv)-67
b(acy)624 b(and)i(comm)-34 b(unication)626 b(complexit)-34
b(y)-101 b(.)1196 b Fk(SIAM)637 b(Journal)g(on)g(Disc.)f(Math.)p
Fr(,)2492 72400 y(5\(2\):273{284,)404 b(1992.)538 b(preliminary)403
b(v)-34 b(ersion)404 b(in)g(F)-34 b(OCS)405 b(89.)25394
75721 y(25)p eop
%%Page: 26 27
26 26 bop 0 818 a Fr([35])606 b(E.)537 b(Kushilevitz,)571
b(S.)539 b(Micali,)570 b(and)539 b(R.)g(Ostro)-34 b(vsky)-101
b(.)936 b(Reducibilit)-34 b(y)539 b(and)g(completeness)f(in)h(m)-34
b(ulti-part)g(y)2492 2323 y(priv)-67 b(ate)419 b(computations.)586
b(In)420 b Fk(35th)447 b(IEEE)i(Symp)-62 b(osium)446
b(on)j(F)-93 b(oundations)446 b(of)h(Computer)g(Scienc)-62
b(e)p Fr(,)423 b(pages)2492 3829 y(478{489,)404 b(1994.)0
6330 y([36])606 b(L.)518 b(A.)g(Levin.)879 b(One-w)-34
b(a)g(y)519 b(functions)i(and)e(pseudorandom)i(generators.)879
b Fk(Combinatoric)-62 b(a)p Fr(,)545 b(7:357{363,)2492
7836 y(1987.)0 10337 y([37])606 b(U.)401 b(Maurer.)533
b(Information-theoretic)403 b(cryptograph)-34 b(y)-101
b(.)534 b(In)402 b Fk(A)-62 b(dvanc)g(es)429 b(in)j(Cryptolo)-62
b(gy)429 b(|)j(CR)-93 b(YPTO)433 b('99)p Fr(,)2492 11843
y(v)-34 b(olume)404 b(1666)g(of)g Fk(L)-62 b(e)g(ctur)g(e)433
b(Notes)f(in)h(Computer)g(Scienc)-62 b(e)p Fr(,)402 b(pages)j(47{64.)f
(Springer-V)-101 b(erlag,)403 b(1999.)0 14345 y([38])606
b(S.)458 b(Micali)f(and)i(P)-101 b(.)458 b(Roga)-34 b(w)g(a)g(y)-101
b(.)700 b(Secure)458 b(computation.)700 b(In)459 b Fk(A)-62
b(dvanc)g(es)481 b(in)j(Cryptolo)-62 b(gy)480 b(-)k(CR)-93
b(YPTO)485 b('91,)2492 15850 y(L)-62 b(e)g(ctur)g(e)432
b(Notes)g(in)i(Computer)e(Scienc)-62 b(e)p Fr(,)403 b(v)-34
b(olume)404 b(576,)g(pages)g(392{404.)g(Springer,)g(1991.)0
18352 y([39])606 b(M.)316 b(Naor)h(and)h(B.)f(Pink)-67
b(as.)395 b(E\261cien)-34 b(t)317 b(oblivious)g(transfer)h(proto)34
b(cols.)395 b(In)317 b Fk(SIAM)354 b(Symp)-62 b(osium)352
b(on)i(Discr)-62 b(ete)2492 19857 y(A)-31 b(lgorithms)431
b(\(SOD)-31 b(A)434 b(2001\))p Fr(,)402 b(pages)i(448{457,)g(2001.)0
22359 y([40])606 b(T.)335 b(Ok)-67 b(amoto.)425 b(On)335
b(relationships)h(b)34 b(et)-34 b(w)g(een)336 b(statistical)g(zero-kno)
-34 b(wledge)335 b(pro)34 b(ofs.)425 b Fk(Journal)370
b(of)g(Computer)2492 23865 y(and)433 b(Systems)f(Scienc)-62
b(es)432 b(\(JCSS\))p Fr(,)405 b(60\(1\):47{108,)g(2000.)0
26366 y([41])606 b(R.)320 b(Ostro)-34 b(vsky)320 b(and)i(A.)e
(Wigderson.)401 b(One-w)-34 b(a)g(y)321 b(fuctions)h(are)e(essen)-34
b(tial)320 b(for)h(non-trivial)f(zero-kno)-34 b(wledge.)2492
27872 y(In)396 b Fk(Se)-62 b(c)g(ond)426 b(Isr)-62 b(ael)426
b(Symp)-62 b(osium)425 b(on)i(The)-62 b(ory)426 b(of)g(Computing)f
(Systems,)i(ISTCS)i(93,)e(Pr)-62 b(o)g(c)g(e)g(e)g(dings.)424
b(IEEE)2492 29377 y(Computer)432 b(So)-62 b(ciety)p Fr(,)402
b(pages)i(3{17,)g(1993.)0 31879 y([42])606 b(M.)403 b(O.)h(Rabin.)538
b(Ho)-34 b(w)405 b(to)f(exc)-34 b(hange)404 b(secrets)g(b)-34
b(y)405 b(oblivious)e(transfer.)538 b(TR-81,)405 b(Harv)-67
b(ard,)403 b(1981.)0 34381 y([43])606 b(A.)453 b(C.)h(Y)-101
b(ao.)685 b(Proto)34 b(cols)453 b(for)h(secure)f(computations.)687
b(In)454 b Fk(23r)-62 b(d)478 b(IEEE)i(Symp)-62 b(osium)478
b(on)i(F)-93 b(oundations)477 b(of)2492 35886 y(Computer)432
b(Scienc)-62 b(e)p Fr(,)402 b(pages)j(160{164,)f(1982.)0
38388 y([44])606 b(A.)587 b(C.)i(Y)-101 b(ao.)1085 b(Theory)588
b(and)h(application)g(of)g(trap)34 b(do)g(or)588 b(functions.)1087
b(In)588 b Fk(23r)-62 b(d)602 b(IEEE)i(Symp)-62 b(osium)601
b(on)2492 39893 y(F)-93 b(oundations)431 b(of)i(Computer)f(Scienc)-62
b(e)p Fr(,)403 b(pages)h(80{91,)g(1982.)0 42395 y([45])606
b(A.)413 b(C.)g(Y)-101 b(ao.)566 b(Ho)-34 b(w)414 b(to)g(generate)f
(and)h(exc)-34 b(hange)414 b(secrets.)565 b(In)413 b
Fk(27th)441 b(IEEE)i(Symp)-62 b(osium)441 b(on)h(F)-93
b(oundations)2492 43901 y(of)432 b(Computer)h(Scienc)-62
b(e)p Fr(,)402 b(pages)j(162{167,)f(1986.)0 47720 y Fs(A)1793
b(Separating)599 b(UA-E\256-)p Fa(S)120 b(F)158 b(E)741
b Fs(and)598 b(IT-E\256-)o Fa(S)120 b(F)158 b(E)0 50425
y Fr(In)336 b(Example)f(1)h(w)-34 b(e)336 b(sho)-34 b(w)337
b(a)f(function)h(that)g(is)e(in)h(IT-E\256-)p Fp(S)91
b(F)120 b(E)445 b Fr(but)337 b(on)f(the)g(other)g(hand)h(in)f(Co-)p
Fp(S)91 b(F)120 b(E)109 b Fr(-C)336 b(\(under)0 51931
y(a)409 b(computational)i(assumption\).)555 b(This)410
b(sho)-34 b(ws)411 b(a)e(separation)h(b)34 b(et)-34 b(w)g(een)410
b(the)f(computational)i(mo)34 b(del)409 b(and)g(the)0
53436 y(un)-34 b(b)34 b(ounded)407 b(adv)-34 b(ersaries)403
b(and)i(information)g(theoretic)f(mo)34 b(dels.)1882
54942 y(An)459 b(in)-34 b(teresting)459 b(question)h(is)e(whether)i(a)e
(similar)g(separation)i(can)f(b)34 b(e)458 b(found)i(b)34
b(et)-34 b(w)g(een)460 b(the)f(un)-34 b(b)34 b(ounded)0
56447 y(adv)-34 b(ersaries)370 b(and)h(the)f(fully)h(information)g
(theoretic)f(mo)34 b(del.)527 b(That)371 b(is,)377 b(is)370
b(there)g(a)g(function)i(with)f(no)f(insecure)0 57953
y(minor)491 b(that)i(is)e(not)h(in)f(UA-E\256-)p Fp(S)91
b(F)120 b(E)600 b Fr(under)492 b(reasonable)g(assumptions?)35173
57513 y Fo(26)36971 57953 y Fr(W)-101 b(e)491 b(giv)-34
b(e)491 b(a)g(partial)h(answ)-34 b(er)492 b(to)0 59458
y(this)390 b(question,)j(starting)e(b)-34 b(y)390 b(giving)f(an)h
(example)f(of)i(suc)-34 b(h)390 b(a)g(function)h(in)f(the)g(malicious)f
(adv)-34 b(ersaries)390 b(mo)34 b(del.)0 61960 y Fj(Example)464
b(5)606 b Fk(L)-62 b(et)424 b Fr(\251)h Fk(b)-62 b(e)424
b(a)g(3-CNF)g(formula)f(and)h Fq(A)g Fk(b)-62 b(e)424
b(an)g(assignment)f(to)h(its)g(variables.)551 b(L)-62
b(et)424 b Fr(\251\()p Fq(A)p Fr(\))i Fk(denote)0 63465
y(the)432 b(value)g(of)h(the)f(formula)g Fr(\251)j Fk(under)d(the)h
(assignment)f Fq(A)p Fk(.)557 b(Consider)433 b(the)f(function:)18180
66189 y Fq(f)18773 66377 y Fo(3)p FC(\241)p Fm(S)50 b(AT)22036
66189 y Fr(\()p Fp(\242)p Fq(;)202 b Fr(\(\251)p Fq(;)g(A)p
Fr(\)\))338 b(=)e(\(\251)p Fq(;)202 b Fr(\251\()p Fq(A)p
Fr(\)\))0 68912 y Fk(\(A)-31 b(lic)-62 b(e)432 b(gets)g(no)i(input)e
(while)h(Bob)g(gets)f(input)h Fq(y)380 b Fr(=)337 b(\(\251)p
Fq(;)202 b(A)p Fr(\))p Fk(.)27935 68472 y Fo(27)p 0 70034
20800 45 v 976 70751 a Fl(26)1843 71174 y Fv(Recall)342
b(that)g(functions)f(with)g(no)h(insecure)f(minor)h(are)f(in)h
(IT-E\256-)o Fh(S)74 b(F)99 b(E)88 b Fv(.)976 71968 y
Fl(27)1843 72392 y Fv(Note)342 b(that)f(the)h(c)-28 b(hoice)342
b(of)f(3-SA)-85 b(T)340 b(is)i(immaterial)h(and)e(an)-28
b(y)341 b Fh(N)148 b(P)82 b Fv(-complete)344 b(language)d(w)-28
b(ould)341 b(ha)-28 b(v)g(e)341 b(su\261ced)25394 75721
y Fr(26)p eop
%%Page: 27 28
27 27 bop 0 818 a Fr(In)462 b(the)h(semi-honest)g(mo)34
b(del)462 b Fq(f)14644 1006 y Fo(3)p FC(\241)p Fm(S)50
b(AT)18369 818 y Fr(has)462 b(a)h(trivial)e(SFE)h(proto)34
b(col)462 b(where)g(Bob)h(simply)e(sends)i(the)g(output)0
2323 y(\(\251)p Fq(;)202 b Fr(\251\()p Fq(A)p Fr(\)\))472
b(to)f(Alice.)735 b(In)470 b(the)g(malicious)g(mo)34
b(del)470 b(ho)-34 b(w)g(ev)g(er,)486 b(it)471 b(is)e(not)i(clear)e
(what)i(can)f(b)34 b(e)470 b(done)h(to)f(prev)-34 b(en)g(t)0
3829 y(Bob)404 b(from)g(c)-34 b(heating.)540 b(F)-101
b(urthermore)404 b(w)-34 b(e)404 b(claim)g(the)g(follo)-34
b(wing:)0 6294 y Fj(Claim)464 b(A.1)606 b Fk(If)341 b(ther)-62
b(e)339 b(exists)g(a)h(malicious)e(SFE)j(pr)-62 b(oto)g(c)g(ol)338
b(for)i Fq(f)29935 6482 y Fo(3)p FC(\241)p Fm(S)50 b(AT)33539
6294 y Fk(in)341 b(the)e(unb)-62 b(ounde)g(d)338 b(adversaries)f(mo)-62
b(del)0 7799 y(then)433 b(the)f(p)-62 b(olynomial)432
b(hier)-62 b(ar)g(chy)431 b(c)-62 b(ol)62 b(lapses)430
b(to)j(the)f(se)-62 b(c)g(ond)432 b(level.)0 10264 y
Fr(The)577 b(Claim)g(is)g(pro)-34 b(v)g(ed)577 b(b)-34
b(y)578 b(sho)-34 b(wing)578 b(that)g(a)f(malicious)f(SFE)i(proto)34
b(col)576 b(for)h Fq(f)38454 10452 y Fo(3)p FC(\241)p
Fm(S)50 b(AT)42294 10264 y Fr(in)577 b(the)g(un)-34 b(b)34
b(ounded)0 11770 y(adv)-34 b(ersaries)539 b(is)h(actually)f(a)h(p)34
b(erfect)539 b(zero)g(kno)-34 b(wledge)541 b(pro)34 b(of)540
b(for)g(the)g(follo)-34 b(wing)540 b Fp(N)179 b(P)99
b Fr(-complete)540 b(language:)0 13275 y(3-SA)-101 b(T)611
b(=)f Fp(f)p Fr(\251)p Fp(j)p Fr(\251)405 b(has)g(a)f(satisfying)g
(assignmen)-34 b(t)406 b Fp(g)p Fr(.)1031 b(The)568 b(correctness)g(of)
h(the)f(SFE)h(proto)34 b(col)568 b(assures)g(the)0 14781
y(v)-34 b(eri\257er)467 b(\(pla)-34 b(ying)468 b(Alice\))f(that)i(up)34
b(on)468 b(receiving)e(output)k(\(\251)p Fq(;)202 b Fr(1\),)484
b(there)467 b(is)h(indeed)g(a)f(satisfying)i(assignmen)-34
b(t)0 16286 y(for)436 b(\251.)634 b(On)437 b(the)f(other)g(hand,)445
b(the)436 b(securit)-34 b(y)436 b(of)g(the)h(SFE)f(proto)34
b(col)436 b(assures)g(that)h(the)g(view)e(of)h(Alice)f(can)h(b)34
b(e)0 17791 y(p)g(erfectly)392 b(sim)-34 b(ulated)394
b(b)-34 b(y)393 b(an)g(e\261cien)-34 b(t)393 b(sim)-34
b(ulator.)535 b(Since)393 b(3-SA)-101 b(T)394 b(is)f(also)f
Fp(N)179 b(P)99 b Fr(-complete)393 b(w)-34 b(e)393 b(deduce)g(that)i
(all)0 19297 y Fp(N)179 b(P)497 b Fr(languages)399 b(ha)-34
b(v)g(e)398 b(p)34 b(erfect)398 b(zero)f(kno)-34 b(wledge)399
b(pro)34 b(ofs.)537 b(It)398 b(is)g(kno)-34 b(wn)399
b(that)h(ev)-34 b(ery)397 b(language)h(with)h(a)f(p)34
b(erfect)0 20802 y(zero)381 b(kno)-34 b(wledge)382 b(pro)34
b(of)382 b(is)g(also)f(in)h(co-)p Fp(AM)f Fr([16,)g(1,)g(40)q(],)k(th)
-34 b(us)383 b Fp(N)179 b(P)436 b(\265)336 b Fr(co-)p
Fp(AM)p Fr(.)531 b(Com)-34 b(bining)383 b(this)f(claim)f(with)0
22308 y(a)418 b(result)g(of)g(Boppana)h(et)f(al.)579
b([6])417 b(w)-34 b(e)418 b(get)g(that)h Fq(f)22973 22496
y Fo(3)p FC(\241)p Fm(S)50 b(AT)26654 22308 y Fr(do)34
b(es)418 b(not)h(ha)-34 b(v)g(e)418 b(an)g(SFE)h(proto)34
b(col)417 b(in)h(the)g(malicious)0 23813 y(un)-34 b(b)34
b(ounded)470 b(adv)-34 b(ersaries)467 b(mo)34 b(del)467
b(unless)h(the)g(p)34 b(olynomial)467 b(time)g(hierarc)-34
b(h)g(y)468 b(collapses)f(to)h(the)g(second)f(lev)-34
b(el.)0 25319 y(Th)g(us)406 b(UA-E\256-)p Fp(S)91 b(F)120
b(E)445 b Fg(\()404 b Fr(IT-E\256-)p Fp(S)91 b(F)120
b(E)513 b Fr(in)404 b(the)h(malicious)e(case)h(under)h(reasonable)f
(assumptions.)1882 26824 y(W)-101 b(e)397 b(further)i(ask)e(whether)i
(suc)-34 b(h)398 b(a)g(separation)h(exists)e(in)h(the)g(semi-honest)h
(case)e(as)h(w)-34 b(ell.)536 b(The)398 b(follo)-34 b(wing)0
28330 y(example)565 b(can)h(b)34 b(e)566 b(view)-34 b(ed)566
b(as)g(some)f(indication)i(that)g(it)f(is)f(unlik)-34
b(ely)565 b(that)i(IT-E\256-)q Fp(S)91 b(F)120 b(E)715
b Fr(=)565 b(UA-E\256-)p Fp(S)91 b(F)120 b(E)0 29835
y Fr(unconditionally)-101 b(.)0 32300 y Fj(Example)464
b(6)606 b Fk(L)-62 b(et)433 b Fq(g)9729 32482 y Fo(0)10255
32300 y Fq(;)202 b(g)11372 32482 y Fo(1)12234 32300 y
Fr(:)337 b Fp(f)p Fr(0)p Fq(;)202 b Fr(1)p Fp(g)15871
31860 y Fm(n)16834 32300 y Fp(!)337 b(f)p Fr(0)p Fq(;)202
b Fr(1)p Fp(g)21346 31860 y Fm(n)22405 32300 y Fk(\(for)433
b(every)f Fq(n)p Fk(\))h(b)-62 b(e)433 b(two)g(one-to-one)e(functions.)
556 b(De\257ne:)7784 34979 y Fq(L)8609 35161 y Fm(g)9057
35284 y Fl(0)9518 35161 y Fm(;g)10227 35284 y Fl(1)11080
34979 y Fr(=)336 b Fp(f)p Fr(\()p Fq(z)14000 35161 y
Fo(0)14526 34979 y Fq(;)202 b(z)15629 35161 y Fo(1)16155
34979 y Fr(\))p Fp(j)433 b Fk(ther)-62 b(e)433 b(exists)f
Fq(y)477 b Fk(such)432 b(that)g Fq(z)30606 35161 y Fo(0)31468
34979 y Fr(=)337 b Fq(g)33326 35161 y Fo(0)33852 34979
y Fr(\()p Fq(y)43 b Fr(\))435 b Fk(and)e Fq(z)38784 35161
y Fo(1)39646 34979 y Fr(=)337 b Fq(g)41504 35161 y Fo(1)42030
34979 y Fr(\()p Fq(y)43 b Fr(\))p Fp(g)0 37658 y Fk(A)-31
b(lso)433 b(de\257ne:)17441 39813 y Fq(f)18034 39995
y Fm(g)18482 40118 y Fl(0)18943 39995 y Fm(;g)19652 40118
y Fl(1)20169 39813 y Fr(\()p Fq(x;)202 b(y)43 b Fr(\))338
b(=)24597 38104 y Fd(\275)26060 39059 y Fq(g)26638 39241
y Fo(0)27164 39059 y Fr(\()p Fq(y)43 b Fr(\))2215 b Fq(x)336
b Fr(=)h(0)26060 40564 y Fq(g)26638 40746 y Fo(1)27164
40564 y Fr(\()p Fq(y)43 b Fr(\))2215 b Fq(x)336 b Fr(=)h(1)0
42733 y Fk(Cle)-62 b(arly)346 b Fq(f)4642 42915 y Fm(g)5090
43038 y Fl(0)5551 42915 y Fm(;g)6260 43038 y Fl(1)6777
42733 y Fr(\()p Fq(x;)202 b(y)43 b Fr(\))337 b Fp(2)g
Fk(IT-)q(E\256-)p Fp(S)91 b(F)120 b(E)455 b Fk(sinc)-62
b(e)346 b(an)h(al)62 b(l)346 b(p)-62 b(owerful)345 b(A)-31
b(lic)-62 b(e)346 b(le)-62 b(arns)346 b Fq(y)391 b Fk(fr)-62
b(om)347 b(either)e Fq(g)42845 42915 y Fm(i)43221 42733
y Fr(\()p Fq(y)43 b Fr(\))348 b Fk(and)f(ther)-62 b(efor)g(e)0
44238 y(Bob)433 b(may)g(simply)f(send)h Fq(y)477 b Fk(to)433
b(A)-31 b(lic)-62 b(e.)556 b(On)435 b(the)d(other)g(hand)h(we)g(claim)g
(the)f(fol)62 b(lowing:)0 47028 y Fj(Claim)464 b(A.2)606
b Fk(If)392 b(ther)-62 b(e)390 b(exist)h Fq(g)14398 47210
y Fo(0)14924 47028 y Fq(;)202 b(g)16041 47210 y Fo(1)16959
47028 y Fk(such)390 b(that)g Fq(L)22935 47210 y Fm(g)23383
47333 y Fl(0)23844 47210 y Fm(;g)24553 47333 y Fl(1)25541
47028 y Fq(=)-741 b Fp(2)337 b(P)100 b(Z)c(K)410 b Fk(\()p
Fq(L)31123 47210 y Fm(g)31571 47333 y Fl(0)32031 47210
y Fm(;g)32740 47333 y Fl(1)33649 47028 y Fk(do)-62 b(es)390
b Fr(not)j Fk(have)d(a)h(p)-62 b(erfe)g(ct)390 b(zer)-62
b(o)391 b(know)62 b(l-)0 48534 y(e)-62 b(dge)432 b(pr)-62
b(o)g(of)126 b(\))432 b(then)h Fq(f)9625 48716 y Fm(g)10073
48839 y Fl(0)10535 48716 y Fm(;g)11244 48839 y Fl(1)11760
48534 y Fr(\()p Fq(x;)202 b(y)43 b Fr(\))473 b Fq(=)-741
b Fp(2)337 b Fk(UA-)o(E\256-)q Fp(S)91 b(F)120 b(E)108
b Fk(.)0 51323 y(Pr)-62 b(o)g(of)p Fr(.)1144 b(Supp)34
b(ose)339 b(that)g Fq(f)12143 51505 y Fm(g)12591 51628
y Fl(0)13052 51505 y Fm(;g)13761 51628 y Fl(1)14278 51323
y Fr(\()p Fq(x;)202 b(y)43 b Fr(\))337 b Fp(2)g Fr(UA-E\256-)p
Fp(S)91 b(F)120 b(E)109 b Fr(,)351 b(then)338 b(w)-34
b(e)339 b(will)e(sho)-34 b(w)339 b(a)f(p)34 b(erfect)337
b(zero)g(kno)-34 b(wledge)338 b(proto-)0 52829 y(col)293
b(for)g Fq(L)4344 53011 y Fm(g)4792 53134 y Fl(0)5253
53011 y Fm(;g)5962 53134 y Fl(1)6478 52829 y Fr(.)502
b(The)293 b(assumption)i(states)f(that)g(there)f(is)g(a)g(proto)34
b(col)293 b(\246\()p Fq(x;)202 b(y)43 b Fr(\))294 b(that)g(alw)-34
b(a)g(ys)294 b(outputs)h Fq(f)46716 53011 y Fm(g)47164
53134 y Fl(0)47626 53011 y Fm(;g)48335 53134 y Fl(1)48851
52829 y Fr(\()p Fq(x;)202 b(y)43 b Fr(\),)0 54334 y(and)371
b(there)e(are)g(sim)-34 b(ulators)371 b Fq(S)13929 54522
y Fm(A)15059 54334 y Fr(and)f Fq(S)18124 54522 y Fm(B)19303
54334 y Fr(that)h(p)34 b(erfectly)369 b(sim)-34 b(ulate)370
b(the)g(resp)34 b(ectiv)-34 b(e)369 b(views)g(of)h(\246.)527
b(P)-34 b(erfect)370 b(sim-)0 55840 y(ulation)419 b(means)f(that,)423
b(in)418 b(particular,)k(ev)-34 b(ery)417 b(p)34 b(ossible)418
b(real)f(view)h Fq(v)461 b Fr(of)419 b(\246\()p Fq(x;)202
b(y)43 b Fr(\))419 b(is)f(also)g(a)g(p)34 b(ossible)418
b(output)j(of)0 57345 y(the)347 b(sim)-34 b(ulator)347
b(\(of)g(b)34 b(oth)347 b(sim)-34 b(ulators\),)359 b(and)347
b(ev)-34 b(ery)345 b(p)34 b(ossible)346 b(output)j(of)d(the)h(sim)-34
b(ulator)347 b(is)f(also)g(a)h(p)34 b(ossible)346 b(real)0
58851 y(view.)604 b(Notice)425 b(that)j(the)e(sim)-34
b(ulator)427 b Fq(S)18045 59039 y Fm(B)18854 58851 y
Fr(\()p Fq(y)43 b Fr(\))427 b(outputs)h(a)e(view)g(of)g(the)g(con)-34
b(v)g(ersation)427 b(b)34 b(et)-34 b(w)g(een)427 b(Alice)e(and)i(Bob)0
60356 y(that)412 b(is)e(indep)34 b(enden)-34 b(t)413
b(of)e(the)g(v)-67 b(alue)410 b Fq(x)p Fr(.)558 b(Hence,)412
b(for)e(an)-34 b(y)412 b(suc)-34 b(h)411 b(sim)-34 b(ulated)412
b(view)e Fq(v)454 b Fr(there)410 b(is)h(an)g(iden)-34
b(tical)411 b(real)0 61862 y(con)-34 b(v)g(ersation)466
b(of)f(\246\()p Fq(x)438 b Fr(=)f(1)p Fq(;)202 b(y)43
b Fr(\))466 b(and)g(also)e(a)h(real)f(con)-34 b(v)g(ersation)466
b(of)f(\246\()p Fq(x)438 b Fr(=)g(0)p Fq(;)202 b(y)43
b Fr(\).)721 b(Therefore,)480 b(the)465 b(view)f Fq(v)508
b Fr(is)0 63367 y(also)404 b(a)g(p)34 b(ossible)404 b(output)i(of)f
Fq(S)14097 63555 y Fm(A)14857 63367 y Fr(\()p Fq(x;)202
b(g)17138 63549 y Fm(x)17723 63367 y Fr(\()p Fq(y)43
b Fr(\)\))406 b(for)e Fq(x)337 b Fr(=)f(0)404 b(and)h(for)f
Fq(x)337 b Fr(=)f(1.)1882 64873 y(The)505 b(p)34 b(erfect)505
b(zero)f(kno)-34 b(wledge)506 b(pro)34 b(of)505 b(for)h
Fq(L)23293 65055 y Fm(g)23741 65178 y Fl(0)24202 65055
y Fm(;g)24911 65178 y Fl(1)25932 64873 y Fr(go)34 b(es)505
b(as)g(follo)-34 b(ws:)741 b(Giv)-34 b(en)505 b(\()p
Fq(z)39588 65055 y Fo(0)40114 64873 y Fq(;)202 b(z)41217
65055 y Fo(1)41743 64873 y Fr(\))505 b Fp(2)g Fq(L)44857
65055 y Fm(g)45305 65178 y Fl(0)45766 65055 y Fm(;g)46475
65178 y Fl(1)46992 64873 y Fr(,)530 b(with)506 b(an)0
66378 y(input)399 b Fq(y)442 b Fr(corresp)34 b(onding)398
b(to)g Fq(z)14086 66560 y Fo(0)15009 66378 y Fr(and)h
Fq(z)17924 66560 y Fo(1)18449 66378 y Fr(,)g(the)f(pro)-34
b(v)g(er)398 b(generates)g(a)g(random)g(view)g Fq(v)441
b Fr(of)398 b(a)g(con)-34 b(v)g(ersation)398 b(of)h(the)0
67884 y(proto)34 b(col)377 b(\246\()p Fq(x;)202 b(y)43
b Fr(\))379 b(for)e(an)-34 b(y)378 b Fq(x)f Fr(\()p Fq(x)337
b Fr(=)f(0)378 b(will)f(do\).)530 b(The)378 b(pro)-34
b(v)g(er)377 b(sends)i(the)e(view)g Fq(v)421 b Fr(to)378
b(the)f(v)-34 b(eri\257er.)529 b(The)378 b(v)-34 b(eri\257er)0
69389 y(then)362 b(c)-34 b(ho)34 b(oses)361 b(a)g(random)h(bit)f
Fq(x)g Fr(and)g(c)-34 b(hallenges)361 b(the)h(pro)-34
b(v)g(er)361 b(to)g(rev)-34 b(eal)360 b(ho)-34 b(w)362
b(the)f(view)g(sen)-34 b(t)362 b(ma)-34 b(y)361 b(corresp)34
b(ond)0 70895 y(to)452 b(an)f(output)j(of)e Fq(S)9451
71083 y Fm(A)10211 70895 y Fr(\()p Fq(x;)202 b(z)12478
71077 y Fm(x)13062 70895 y Fr(\).)681 b(A)451 b(non)h(c)-34
b(heating)453 b(pro)-34 b(v)g(er)451 b(can)g(alw)-34
b(a)g(ys)452 b(pro)-34 b(vide)452 b(the)g(random)g(coins)f(that)h(giv)
-34 b(e)0 72400 y Fq(S)743 72588 y Fm(A)1503 72400 y
Fr(\()p Fq(x;)202 b(z)3770 72582 y Fm(x)4355 72400 y
Fr(\))337 b(=)f Fq(v)43 b Fr(,)367 b(but)359 b(if)e(\()p
Fq(z)12052 72582 y Fo(0)12578 72400 y Fq(;)202 b(z)13681
72582 y Fo(1)14206 72400 y Fr(\))472 b Fq(=)-741 b Fp(2)337
b Fq(L)16984 72582 y Fm(g)17432 72705 y Fl(0)17893 72582
y Fm(;g)18602 72705 y Fl(1)19476 72400 y Fr(then)359
b(b)-34 b(y)357 b(the)h(correctness)f(of)h(the)g(SFE)g(proto)34
b(col)357 b(\246,)367 b(the)358 b(pro)-34 b(v)g(er)357
b(will)25394 75721 y(27)p eop
%%Page: 28 29
28 28 bop 0 818 a Fr(fail)426 b(on)h(at)g(least)f(one)h(of)g(the)f(p)34
b(ossible)427 b(c)-34 b(hallenges,)431 b(and)d(will)e(b)34
b(e)426 b(caugh)-34 b(t)427 b(with)h(probabilit)-34 b(y)427
b(at)g(least)48367 340 y Fo(1)p 48367 538 471 49 v 48367
1236 a(2)48970 818 y Fr(.)605 b(The)0 2323 y(ab)34 b(o)-34
b(v)g(e)434 b(proto)34 b(col)434 b(is)g(also)g(zero)f(kno)-34
b(wledge)435 b(since)f(the)g(v)-34 b(eri\257er's)433
b(view)h(ma)-34 b(y)434 b(b)34 b(e)434 b(p)34 b(erfectly)433
b(sim)-34 b(ulated,)442 b(simply)0 3829 y(b)-34 b(y)405
b(c)-34 b(ho)34 b(osing)404 b(a)g(random)h Fq(x)f Fr(and)h(setting)f
(the)h(view)f(to)g(b)34 b(e)404 b Fq(v)380 b Fr(=)336
b Fq(S)30501 4017 y Fm(A)31262 3829 y Fr(\()p Fq(x;)202
b(g)33543 4011 y Fm(x)34128 3829 y Fr(\()p Fq(y)43 b
Fr(\)\).)p 37863 3829 788 788 v 1882 6662 a(The)362 b(ab)34
b(o)-34 b(v)g(e)363 b(claim)e(is)g(not)i(in)f(itself)g(a)g(separation)h
(of)f(UA-E\256-)p Fp(S)91 b(F)120 b(E)471 b Fr(from)362
b(IT-E\256-)p Fp(S)91 b(F)120 b(E)109 b Fr(.)524 b(It)362
b(merely)f(p)34 b(oin)-34 b(ts)0 8168 y(out)376 b(that)g(if)f(there)g
(is)g(no)g(separation,)381 b(then)376 b(all)f(languages)g(of)h(the)f(t)
-34 b(yp)34 b(e)375 b Fq(L)34722 8350 y Fm(g)35170 8473
y Fl(0)35631 8350 y Fm(;g)36340 8473 y Fl(1)37232 8168
y Fr(ha)-34 b(v)g(e)376 b(p)34 b(erfect)374 b(zero)g(kno)-34
b(wledge)0 9673 y(pro)34 b(ofs.)505 b(W)-101 b(e)303
b(view)g(this)h(as)g(an)g(in)-34 b(teresting)304 b(consequence)f(as)h
(w)-34 b(e)304 b(are)f(una)-34 b(w)g(are)305 b(of)f(suc)-34
b(h)304 b(a)g(generic)e(construction.)25394 75721 y(28)p
eop
%%Trailer
end
userdict /end-hook known{end-hook}if
%%EOF