%!PS-Adobe-2.0 %%Creator: dvips 5.58 Copyright 1986, 1994 Radical Eye Software %%Title: concur.dvi %%CreationDate: Mon Mar 24 09:55:58 1997 %%Pages: 15 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSCommandLine: dvips concur %DVIPSParameters: dpi=300, comments removed %DVIPSSource: TeX output 1997.03.24:0955 %%BeginProcSet: tex.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72 mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1} ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if} forall round exch round exch]setmatrix}N /@landscape{/isls true N}B /@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{ /nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{ /sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0] N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{ 128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 sub]{ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]} if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{ cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore userdict /eop-hook known{eop-hook}if showpage}N /@start{userdict /start-hook known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false} ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail {dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M} B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{ 4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{ p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet TeXDict begin 40258431 52099146 1000 300 300 (/tmp_mnt/jumbo/r/dlusers4/adg/Pub/spi/concur.dvi) @start /Fa 1 26 df<1FFFE03FFFE07FFFC04108008218000210000610000610000410000C3800 0C38001C3800183800383C00381C0030180013107E8F16>25 D E /Fb 40 122 df<1838783808101020204080050B7D830C>44 DI<003E0000C1800100800200C00600C00600C00E018007030007860003CC0001F000 01F800067C000C3E00181E00300700600700600700C00600C00600400C00601800307000 0FC00012187D9714>56 D<060F1E0C00000000000000003078F06008107C8F0C>58 D<0000200000600000E00000E00001E00001F00002700002700004700008700008700010 7000107000207000407000407000803800FFF80100380200380200380400380400380800 38180038FE01FF181A7E991D>65 D<000F8200706200C01603801E07000C0E000C1C000C 18000C380008300008700000700000E00000E00000E00000E00000E00020E00020E00020 E000406000406000803001001006000C180003E000171A7A991B>67 D<03FFFF00700700700300700100E00100E00100E00100E00101C08001C08001C08001C1 8003FF000381000381000381000702000700040700040700080E00080E00180E00100E00 301C00E0FFFFE0181A7D991A>69 D<03FFFF00700700700300700100E00100E00100E001 00E00101C08001C08001C08001C18003FF00038100038100038100070200070000070000 0700000E00000E00000E00000E00001E0000FFC000181A7D9919>I<03FF007000700070 00E000E000E000E001C001C001C001C0038003800380038007000700070007000E000E00 0E000E001C00FF80101A7D990F>73 D<00FFC0000E00000E00000E00001C00001C00001C 00001C0000380000380000380000380000700000700000700000700000E00000E00000E0 0000E00061C000E1C000E180008380004700003C0000121A7C9914>I<03FF0000700000 700000700000E00000E00000E00000E00001C00001C00001C00001C00003800003800003 80000380000700000700100700100700200E00200E00600E00400E00C01C0380FFFF8014 1A7D9918>76 D<03F8001FC00078003C000078003C000078005C0000B800B80000B800B8 00009C013800009C013800011C027000011C027000011C047000011C087000021C08E000 021C10E000021C10E000021C20E000041C41C000041C41C000041C81C000041C81C00008 0F038000080F038000080E038000180C038000180C070000FE083FE000221A7D9922>I< 03F007F8007800C00078008000780080009C0100009C0100009C0100008E0100010E0200 0106020001070200010702000203840002038400020384000201C4000401C8000401C800 0400E8000400E8000800F00008007000080070001800700018002000FE0020001D1A7D99 1D>I<001F8000706001C03003001806001C0E000C1C000C18000E38000E30000E70000E 70000EE0001CE0001CE0001CE00038E00038E00030E00070E000E0E000C0600180700300 3806001C1C0007E000171A7A991D>I<03FFF800701C00700600700700E00700E00700E0 0700E00701C00E01C00E01C01C01C03803806003FF800380000380000700000700000700 000700000E00000E00000E00000E00001C0000FF8000181A7D991A>I<03FFF000701C00 700E00700700E00700E00700E00700E00701C00E01C01C01C03801C0E003FF800380C003 80600380700700700700700700700700700E00E00E00E00E00E10E00E21C0062FF803C18 1A7D991C>82 D<003F100060900180700100700300200600200600200600200600000700 0007C00003F80001FE00007F00000F800003800001800001802001802001806003006003 00600600700C00C8180087E000141A7D9916>I<3FFFFC381C0C201C04401C0440380480 380480380480380400700000700000700000700000E00000E00000E00000E00001C00001 C00001C00001C000038000038000038000038000078000FFF800161A79991B>I87 D<03CC0E2E181C381C30 1C701CE038E038E038E038C072C072C07260F261341E180F107C8F14>97 D<01E006180C181838301070006000E000E000E000E000E008E010602030C01F000D107C 8F12>99 D<001F80000380000380000380000700000700000700000700000E00000E0003 CE000E2E00181C00381C00301C00701C00E03800E03800E03800E03800C07200C07200C0 720060F2006134001E1800111A7C9914>I<01E00E181C08380870087010FFE0E000E000 E000E000E0086010602030C01F000D107C8F12>I<000700000980001B80003B00003800 00300000700000700000700000700007FF0000E00000E00000E00000E00000E00001C000 01C00001C00001C00001C000038000038000038000038000030000070000070000060000 660000E40000CC0000700000112181990C>I<00F300038B800607000E07000C07001C07 00380E00380E00380E00380E00301C00301C00301C00183C0018780007B8000038000038 00007000607000E0E000C1C0007F000011177E8F12>I<1F800003800003800003800007 00000700000700000700000E00000E00000E7C000F86001E07001E07001C07001C070038 0E00380E00380E00381C00701C80701C80703880703900E01900600E00111A7E9914>I< 030706000000000000384C4E8E9C9C1C3838707272E2E4643808197C980C>I<1F800380 0380038007000700070007000E000E000E0E0E131C271C431C801F003C003F8039C038E0 70E270E270E270E4E0646038101A7E9912>107 D<1F0707070E0E0E0E1C1C1C1C383838 3870707070E4E4E4E4E830081A7D990A>I<307C1E00598663009E0783809E0703809C07 03809C070380380E0700380E0700380E0700380E0E00701C0E40701C0E40701C1C40701C 1C80E0380C80601807001A107C8F1F>I<307C005986009E07009E07009C07009C070038 0E00380E00380E00381C00701C80701C80703880703900E01900600E0011107C8F16>I< 01F006180C0C180E300E700E600EE00EE00EE00CE01CE018E030606030C01F000F107C8F 14>I<030F000590C009E0C009C06009C06009C0600380E00380E00380E00380E00701C0 0701800703800703000E8E000E78000E00000E00001C00001C00001C00001C0000FF0000 1317808F14>I<30F05D189E389C189C009C0038003800380038007000700070007000E0 0060000D107C8F10>114 D<03E004300830187018601C001F801FC00FE000E00060E060 E06080C041803E000C107D8F10>I<06000E000E000E000E001C001C00FFC01C00380038 00380038007000700070007000E100E100E100E200E40038000A177C960D>I<38064C07 4E0E8E0E9C0E9C0E1C1C381C381C381C7039703970393079389A0F0C10107C8F15>I<38 184C1C4E1C8E0C9C0C9C0C1C08380838083810701070107020304018C00F000E107C8F12 >I<380C104C0E384E1C388E1C189C1C189C1C181C381038381038381038381070702070 702070704030704018B8800F0F0015107C8F19>I<38064C074E0E8E0E9C0E9C0E1C1C38 1C381C381C703870387038307838F00F700070006060E0E1C0C18047003C0010177C8F13 >121 D E /Fc 1 51 df<7FFFFCFFFFFEC00006C00006C00006C00006C00006C00006C0 0006C00006C00006C00006C00006C00006C00006C00006C00006C00006C00006C00006C0 0006FFFFFEFFFFFE17177D991F>50 D E /Fd 1 49 df<181818303030606060C0C0050B 7E8B09>48 D E /Fe 3 111 df<001800003800003800005800009800008C00010C0002 0C00060C0007FC00080600100600300600F81F80110E7E8D16>65 D<1FFE000601800600C00600C00C01800C03000FFE000C07001801801801801801801803 00300E00FFF800120E7E8D16>I<73809C40986030C030C030C03188619060E00D097D88 12>110 D E /Ff 2 50 df<00400000E00001F000013000021800061C00040C00080E00 0806001003002003802001807FFFC0FFFFE0130E7E8D17>1 D<18F81818181818181818 1818FF080D7D8C0E>49 D E /Fg 2 82 df<0000700001F00003C0000780000E00001C00 00380000700000700000F00000E00000E00000E00000E00000E00000E00000E00000E000 00E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E000 00E00000E00000E00000E00000E00000E00000E00000E00000E00000E00001C00001C000 01C0000380000700000600000E0000380000700000C000007000003800000E0000060000 07000003800001C00001C00001C00000E00000E00000E00000E00000E00000E00000E000 00E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E000 00E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000F000 007000007000003800001C00000E000007800003C00001F000007014637B811F>26 D81 D E /Fh 16 116 df<03C0000C2080183080301900601900601A00601A00C01C00C0 180040180060280020CD001F0700110D7E8C16>11 D<003C00C201030203040304020806 08FC08FC08041006100610061006200C200C30183010486047C040004000800080008000 8000101A7F9313>I<3FF87FF8C200820006000600040004000C000C000C00180018000D 0D7E8C0F>28 D<40E04003037D820A>58 D<000100000300000700000780000B80001B80 0013800023800023800043800083800083C00101C003FFC00201C00401C00C01C00801C0 1801E0FE07F815147F9319>65 D<07FFE000E03801C01801C01C01C01C01C01C03803803 80700380E003FFC00700E00700700700300700380E00700E00700E00E00E00E01C0380FF FE0016147F9319>I<07FC1FC000E0060001C0080001C0100001C0600001C08000038100 0003860000038E0000039E0000076700000787000007038000070380000E01C0000E01C0 000E00E0000E00E0001C00F000FF83FC001A147F931C>75 D<07E01FC000E00600017004 00017004000138040001380400021C0800021C0800020E0800020E080004071000040710 0004039000040390000801E0000801E0000800E0000800E00018004000FE0040001A147F 931A>78 D<06070600000000384C4C8C98181830323264643808147F930C>105 D<1E0006000C000C000C000C0018001838185C189C3118360038003F8061C060C860C860 C8C0D0C0600E147F9312>107 D<3C0C181818183030303060606060C0C8C8C8D0600614 7F930A>I<30F87C00590C86004E0D06009C0E0600980C0600180C0600180C060030180C 0030180C8030181880301818806030190060300E00190D7F8C1D>I<30F8590C4E0C9C0C 980C180C180C30183019303130316032601C100D7F8C15>I<0C78168C13042606260606 0606060C0C0C0C0C080C101A2019C018001800300030003000FC000F13818C11>112 D<31E05A704C709C609800180018003000300030003000600060000C0D7F8C0F>114 D<0700188019C0318038001E000F0003804180E180C10082007C000A0D7E8C10>I E /Fi 25 119 df0 D<60F0F06004047C8B0C>I17 D<007FFF8001FFFF80078000000E000000180000003000 0000300000006000000060000000C0000000C0000000C0000000C0000000C0000000C000 0000C000000060000000600000003000000030000000180000000E0000000780000001FF FF80007FFF80000000000000000000000000000000000000000000000000000000007FFF FF807FFFFF8019227D9920>I21 D<0F8000201FE000203FF80020707C0060E01F00E0C007C1 C08003FF808000FF0080003E001B097E8E20>24 D<000000300000000018000000001800 00000018000000000C000000000C0000000006000000000300000000038000000000C0FF FFFFFFF8FFFFFFFFF800000000C00000000380000000030000000006000000000C000000 000C00000000180000000018000000001800000000300025167E942A>33 D<00C00000C00000C00000C00000C00000C00000C00000C00000C00000C00000C00000C0 0000C00000C00000C00000C00000C00000C00000C00000C00000C00000C00000C00000C0 0000C000C0C0C0F0C3C038C7000CCC0006D80003F00001E00001E00000C00000C00000C0 0000400012257F9C15>35 D<0F8000201FE000203FF80020707C0060E01F00E0C007C1C0 8003FF808000FF0080003E00000000000000000000000000000000000000000000000000 00000000000000007FFFFFE0FFFFFFE01B137E9220>39 D<030180030180030180030180 030180030180030180030180030180030180030180030180030180030180030180030180 030180030180030180030180030180030180C30186F3019E3B01B80F01E00701C0030180 01830000C60000C600006C0000280000380000380000100000100017257F9C19>43 D<007FF801FFF80780000E0000180000300000300000600000600000C00000C00000C000 00FFFFF8FFFFF8C00000C00000C000006000006000003000003000001800000E00000780 0001FFF8007FF8151A7D961C>50 D<0000600000600000C00000C0000180000180000180 000300000300000600000600000C00000C00001800001800001800003000003000006000 00600000C00000C0000180000180000300000300000300000600000600000C00000C0000 180000180000300000300000300000600000600000C0000040000013287A9D00>54 D<400004C0000C6000186000186000183000303000303000301800601800601FFFE00FFF C00C00C00C00C006018006018003030003030003030001860001860001860000CC0000CC 0000CC00007800007800007800003000003000161E809C17>56 D<0004000C03CC0C3818 18301C303C703E603660666066E067E067E0C7E0C7E0C7E187E187E187E307E307E307E6 07E607E60766066C067C0E3C0C380C18181C3033C03000300010237E9F15>59 D<0003F0000FF80030F80040780180780300700700700E00E00E00E01C01801C00003800 00380000780000780000700000700000F00000F00000F00000F00000F00000F00020F800 60F801C07C01807E03003F04001FF8000FE000151E7F9C16>67 D<003FFF000001FFFFE0 00071E0FF000081C01F800381C00F800703C007800603C007800C03C007800003C007000 0038007000003800E000007800C0000078018000007802000000700C00000071F0000000 F3F0000000E1F0000000E0F8000001E0F8000001C07C000001C07C000003C03C00000380 3E018003803E070007801F060007001F880006000FF0000C0007C000211D809B23>82 D<0001FC000007FF0000083F8000300F800070078000E0078000E0060001E0040001E000 0001F0000001F8000000FC0000007E0000003F8000001FE0000007F0000001F8000000FC 0008007C0038003C0070003C0070003C00F0003800F0003800F8007000F80060007C0080 007F0300003FFC00000FF00000191E7F9C19>I<00FE0003FF800F01E01C007030001860 000C60000CC00006C00006C00006C00006C00006C00006C00006C00006C00006C00006C0 0006C00006C00006C00006C00006C00006C00006C00006400002171A7E981C>92 D<400000C00000C00000C00000C00000C00000C00000C00000C00000C00000C00000C000 00C00000FFFFE0FFFFF0C00000C00000C00000C00000C00000C00000C00000C00000C000 00C00000C00000C00000C00000400000141D7E9C19>96 D<003C00E001C0018003800380 03800380038003800380038003800380038003800380030007001C00F0001C0007000300 0380038003800380038003800380038003800380038003800380018001C000E0003C0E29 7D9E15>102 DI<004000C00180018001800300 03000600060006000C000C0018001800180030003000600060006000C000C00060006000 6000300030001800180018000C000C000600060006000300030001800180018000C00040 0A2A7D9E10>III<7FFFFFC0FFFFFFC0C0000000C0000000C0000000C0000000C0000000C0000000C000 0000C0000000C0000000C0000000C0000000C0000000C0000000C0000000C0000000C000 0000C0000000C0000000C0000000C0000000C0000000FFFFFFC0FFFFFFC0000000000000 000000000000000000000000000000000000000000007FFFFF80FFFFFFC01A227D9920> 118 D E /Fj 36 122 df<183878380808101020404080050C7D830D>44 DI<3078F06005047C830D>I<060F0F060000000000000000 00003078F06008127C910D>58 D<01FFFF00003C0380003801C0003800E0003800E00038 00E0007000E0007001E0007001E0007003C000E0038000E00F0000E01E0000FFFC0001C0 0E0001C0070001C0078001C007800380078003800780038007800380078007000F000700 0E0007001E0007003C000E00F000FFFFC0001B1C7E9B1D>66 D<01FFFFF0003C00F00038 00300038002000380020003800200070002000700020007008200070080000E0100000E0 100000E0300000FFF00001C0200001C0200001C0200001C0200003804000038000000380 000003800000070000000700000007000000070000000F000000FFF000001C1C7E9B1B> 70 D<03FF0078007000700070007000E000E000E000E001C001C001C001C00380038003 80038007000700070007000E000E000E000E001E00FFC0101C7D9B10>73 D<01FE0001FE003E0001E0002E0003C0002E0005C0002E0005C0002E0009C0004E000B80 004E001380004E0023800047002380008700470000870047000087008700008701070001 07010E000107020E000107040E000107040E000207081C000203881C000203901C000203 A01C000403A038000403C038000403C038000C038038001C03007800FF8307FF00271C7E 9B25>77 D<01FFFE00003C0380003801C0003800E0003800E0003800E0007001E0007001 E0007001E0007001C000E003C000E0038000E0070000E01C0001FFF00001C0000001C000 0001C0000003800000038000000380000003800000070000000700000007000000070000 000F000000FFE000001B1C7E9B1C>80 D<000F8400304C00403C00801801001803001803 001806001006001006000007000007000003E00003FC0001FF00007F800007C00001C000 01C00000C00000C02000C02000C0600180600180600300600200F00400CC180083E00016 1E7D9C17>83 D<1FFFFFC01C0701C0300E00C0200E0080600E0080400E0080401C008080 1C0080801C0080001C000000380000003800000038000000380000007000000070000000 7000000070000000E0000000E0000000E0000000E0000001C0000001C0000001C0000001 C0000003C000007FFE00001A1C799B1E>I<01E307170C0F180F380E300E700E700EE01C E01CE01CE01CE039E039E0396079319A1E0C10127C9115>97 D<3F00070007000E000E00 0E000E001C001C001C001C0039E03A183C0C380C700C700E700E700EE01CE01CE01CE018 E038E030E06060C031801E000F1D7C9C13>I<00F803040E041C0E181C300070007000E0 00E000E000E000E000E0046008601030600F800F127C9113>I<0007E00000E00000E000 01C00001C00001C00001C000038000038000038000038001E7000717000C0F00180F0038 0E00300E00700E00700E00E01C00E01C00E01C00E01C00E03900E03900E0390060790031 9A001E0C00131D7C9C15>I<00F807040C0418023804300470087FF0E000E000E000E000 E00060046008301030600F800F127C9113>I<0003C0000670000C70001C60001C00001C 0000380000380000380000380000380003FF8000700000700000700000700000700000E0 0000E00000E00000E00000E00001C00001C00001C00001C00001C0000380000380000380 00030000030000070000C60000E60000CC00007800001425819C0D>I<0078C001C5C003 03C00603C00E03800C03801C03801C0380380700380700380700380700380E00380E0038 0E00181E000C7C00079C00001C00001C00003800003800C03000E07000C1C0007F000012 1A7E9113>I<0FC00001C00001C000038000038000038000038000070000070000070000 0700000E3E000EC3000F03800E03801E03801C03801C03801C0380380700380700380700 380E00700E40700E40701C40701C80E00C80600700121D7E9C15>I<0180038001000000 0000000000000000000000001C002600470047008E008E000E001C001C001C0038003800 710071007100720072003C00091C7C9B0D>I<0003000700030000000000000000000000 0000000078008C010C020C021C041C001C001C0038003800380038007000700070007000 E000E000E000E001C001C0C180E300C60078001024819B0D>I<0FC00001C00001C00003 80000380000380000380000700000700000700000700000E07800E08800E11C00E21C01C 41801C80001D00001E00003FC00038E000387000387000707100707100707100707200E0 3200601C00121D7E9C13>I<1F800380038007000700070007000E000E000E000E001C00 1C001C001C0038003800380038007000700070007000E200E200E200E40064003800091D 7D9C0B>I<1C1E0780266318C04683A0E04703C0E08E0380E08E0380E00E0380E00E0380 E01C0701C01C0701C01C0701C01C070380380E0388380E0388380E0708380E0710701C03 20300C01C01D127C9122>I<383E004CC3004D03804E03809E03809C03801C03801C0380 380700380700380700380E00700E40700E40701C40701C80E00C8060070012127C9117> I<00F800030C000E06001C0300180300300300700380700380E00700E00700E00700E00E 00E00E00E01C0060180060300030E0000F800011127C9115>I<03878004C86004D03004 E03009C03009C03801C03801C0380380700380700380700380600700E00700C007018007 83000E86000E78000E00000E00001C00001C00001C00001C0000380000FF0000151A8091 15>I<01E107130C0F180F380E300E700E700EE01CE01CE01CE01CE038E038E038607831 F01E700070007000E000E000E000E001C00FF8101A7C9113>I<1C3C2642468747078E06 8E000E000E001C001C001C001C0038003800380038007000300010127C9112>I<01F006 080C080C1C18181C001F001FC00FF007F0007800386030E030C030806060C01F000E127D 9111>I<03000700070007000E000E000E000E00FFE01C001C001C003800380038003800 7000700070007000E080E080E100E100660038000B1A7C990E>I<1C01802E03804E0380 4E03808E07008E07001C07001C0700380E00380E00380E00380E00301C80301C80301C80 383C80184D000F860011127C9116>I<1C062E0E4E064E068E028E021C021C0238043804 38043808300830083010382018400F800F127C9113>I<1E018327038747038747038387 07018707010E07010E07011C0E021C0E021C0E021C0E04180C04181C04181C081C1E080C 263007C3C018127C911C>I<0387800CC8400870E01070E020E0C020E00000E00000E000 01C00001C00001C00001C000038100638100E38200C5820085840078780013127E9113> I<1C01802E03804E03804E03808E07008E07001C07001C0700380E00380E00380E00380E 00301C00301C00301C00383C001878000FB800003800003000007000E06000E0C0008180 004300003C0000111A7C9114>I E /Fk 45 124 df<0020004001800380030006000E00 1C001C003C0038003800780078007800F800F000F000F000F000F000F000F000F000F000 F800780078007800380038003C001C001C000E000600030003800180004000200B297C9E 13>40 D<800040003000380018000C000E000700070007800380038003C003C003C003E0 01E001E001E001E001E001E001E001E001E003E003C003C003C003800380078007000700 0E000C00180038003000400080000B297D9E13>I<78FCFCFCFC7806067D850D>46 D<03F8000F1E001C07003C07803803807803C07803C07803C0F803E0F803E0F803E0F803 E0F803E0F803E0F803E0F803E0F803E0F803E0F803E0F803E07803C07803C03803803C07 801C07000F1E0003F800131B7E9A18>48 D<00600001E0000FE000FFE000F3E00003E000 03E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E000 03E00003E00003E00003E00003E00003E00003E0007FFF807FFF80111B7D9A18>I<07F8 001FFE00383F80780FC0FC07C0FC07E0FC03E0FC03E07803E00007E00007C00007C0000F 80001F00001E0000380000700000E0000180600300600600600800E01FFFC03FFFC07FFF C0FFFFC0FFFFC0131B7E9A18>I<07F8001FFE003C1F003C0F807C07C07E07C07C07C038 07C0000F80000F80001E00003C0003F800001E00000F800007C00007C00007E03007E078 07E0FC07E0FC07E0FC07C0780F80781F001FFE0007F800131B7E9A18>I<000180000380 000780000F80001F80003F80006F8000CF80008F80018F80030F80060F800C0F80180F80 300F80600F80C00F80FFFFF8FFFFF8000F80000F80000F80000F80000F80000F8000FFF8 00FFF8151B7F9A18>I<3801803FFF003FFE003FFC003FF8003FC0003000003000003000 0030000031F800361E00380F803007800007C00007E00007E00007E07807E0F807E0F807 E0F807C0F007C0600F80381F001FFE0007F000131B7E9A18>I<007E0003FF000781800F 03C01E07C03C07C07C0380780000780000F80000F8F800FB0E00FA0780FC0380FC03C0F8 03E0F803E0F803E0F803E07803E07803E07803C03C03C03C07801E0F0007FE0003F80013 1B7E9A18>I<6000007FFFE07FFFE07FFFC07FFF807FFF80E00300C00600C00C00C01800 00300000300000600000E00000E00001E00001C00003C00003C00003C00003C00007C000 07C00007C00007C00007C00007C000038000131C7D9B18>I<03F8000FFE001E0F803807 803803C07803C07C03C07E03C07F83803FC7003FFE001FFC000FFE0007FF001DFF80387F C0781FE0700FE0F003E0F001E0F001E0F001E07801C07803803E07801FFE0003F800131B 7E9A18>I<03F8000FFE001E0F003C07807807807803C0F803C0F803C0F803E0F803E0F8 03E0F803E07807E03807E03C0BE00E1BE003E3E00003E00003C00003C03807C07C07807C 0700780F00383C001FF8000FE000131B7E9A18>I<00038000000380000007C0000007C0 000007C000000FE000000FE000001FF000001BF000003BF8000031F8000031F8000060FC 000060FC0000E0FE0000C07E0000C07E0001803F0001FFFF0003FFFF8003001F8007001F C006000FC006000FC00C0007E00C0007E0FF803FFEFF803FFE1F1C7E9B24>65 DI<001FE02000FFF8E003F80FE007C003E00F8001E01F0000E0 3E0000E03E0000607E0000607C000060FC000000FC000000FC000000FC000000FC000000 FC000000FC000000FC0000007C0000607E0000603E0000603E0000C01F0000C00F800180 07C0030003F80E0000FFFC00001FE0001B1C7D9B22>I69 D76 D80 D82 D<07F8201FFEE03C07E07801E07000E0F000E0F00060F00060F80000FE0000FF E0007FFE003FFF003FFF800FFFC007FFE0007FE00003F00001F00000F0C000F0C000F0C0 00E0E000E0F001C0FC03C0EFFF0083FC00141C7D9B1B>I<7FFFFFE07FFFFFE0781F81E0 701F80E0601F8060E01F8070C01F8030C01F8030C01F8030C01F8030001F8000001F8000 001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000 001F8000001F8000001F8000001F8000001F800007FFFE0007FFFE001C1C7E9B21>I<0F F8001C1E003E0F803E07803E07C01C07C00007C0007FC007E7C01F07C03C07C07C07C0F8 07C0F807C0F807C0780BC03E13F80FE1F815127F9117>97 DI<03FC000E0E001C1F003C1F00781F00780E00F80000F80000F8 0000F80000F80000F800007800007801803C01801C03000E0E0003F80011127E9115>I< 000FF0000FF00001F00001F00001F00001F00001F00001F00001F00001F00001F001F9F0 0F07F01C03F03C01F07801F07801F0F801F0F801F0F801F0F801F0F801F0F801F07801F0 7801F03C01F01C03F00F0FFE03F9FE171D7E9C1B>I<03FC000F07001C03803C01C07801 C07801E0F801E0F801E0FFFFE0F80000F80000F800007800007800603C00601E00C00F03 8001FC0013127F9116>I<03F0F00E1F383C0F3838073078078078078078078078078038 07003C0F001E1C0033F0003000003000003000003FFF003FFFC01FFFE01FFFF07801F8F0 0078F00078F000787000707800F01E03C007FF00151B7F9118>103 DI<1E003F003F003F003F001E0000 00000000000000000000007F007F001F001F001F001F001F001F001F001F001F001F001F 001F001F001F00FFC0FFC00A1E7F9D0E>I107 DIII<01FC000F07801C01C03C01E07800F07800F0F800F8F800 F8F800F8F800F8F800F8F800F87800F07800F03C01E01E03C00F078001FC0015127F9118 >II<03F0600F0CE01E07E03C03E07C03E07803E0F803E0 F803E0F803E0F803E0F803E0F803E07803E07C03E03C03E01C07E00E0FE003F3E00003E0 0003E00003E00003E00003E00003E0001FFC001FFC161A7E9119>II<1FD830786018E018E018F000FF807FE07FF01F F807FC007CC01CC01CE01CE018F830CFC00E127E9113>I<030003000300030007000700 0F000F003FFCFFFC1F001F001F001F001F001F001F001F001F001F0C1F0C1F0C1F0C0F08 079803F00E1A7F9913>II< FFC1FCFFC1FC1F00601F80600F80C00F80C007C18007C18003E30003E30003F70001F600 01FE0000FC0000FC0000780000780000300016127F9119>II121 D123 D E /Fl 5 51 df0 D<40E04003037D880A>I<040004000400C460F5E03F 800E003F80F5E0C4600400040004000B0D7E8D11>3 D<040E0E1C1C1C38383070706060 C0C0070F7F8F0A>48 D<03FC0FFC1C003000600060006000C000C000FFFCFFFCC000C000 60006000600030001C000FFC03FC0E147D9016>50 D E /Fm 35 127 df<00F800030C000E06041C0704380308300388700390700390E003A0E003A0E003 C0E00380E00380E00380600780600B883071900F80E016127E911B>11 D<0001F000061800080C00100C00200E00400E00800E00801C01001C010018010038020F F00210C0020FE00200300400300400300400380400380800700800700800700800E01800 E01801C0140180140300230E0020F8002000002000004000004000004000004000008000 0080000017257F9C17>I<7E00600E00E00E00E00E00E01C01C01C01C01C03801C030038 0700380E00380C0038180070300070600071C000730000FC0000F0000013127E9115>23 D<01FFF803FFF80FFFF81E1E00180E00380600700600700600E00E00E00E00E00E00E00C 00E01C00E01800E0300060600030C0001F000015127E9118>27 D<0FFFE01FFFE03FFFE0 60C00040C000808000008000018000018000018000030000030000030000070000070000 0700000E000006000013127E9112>I<60F0F06004047C830C>58 D<60F0F0701010101020204080040C7C830C>I<00010003000600060006000C000C000C 0018001800180030003000300060006000C000C000C00180018001800300030003000600 06000C000C000C00180018001800300030003000600060006000C000C00010297E9E15> 61 DI<0000 0C0000000C0000001C0000001C0000003C0000005C0000005C0000009E0000008E000001 0E0000020E0000020E0000040E0000040E0000080E0000100E0000100E0000200700003F FF0000400700008007000080070001000700010007000200070004000700040007001C00 0780FF803FF01C1D7F9C1F>65 D<01FFFF00003C01C0003800E0003800F0003800700038 007000700070007000F0007000F0007001E000E003C000E0078000E01F0000FFFC0001C0 0F0001C0078001C003C001C003C0038003C0038003C0038003C0038003C0070007800700 070007000E0007001C000E007800FFFFC0001C1C7E9B1F>I<0001F808000E0618003801 38006000F001C0007003800070070000300F0000200E0000201C0000203C0000203C0000 00780000007800000078000000F0000000F0000000F0000000F0000000F0000100F00001 00F0000100700002007000020030000400380008001C0010000E0060000701800000FE00 001D1E7E9C1E>I<01FFFFF8003C00780038001800380010003800100038001000700010 00700010007008100070080000E0100000E0100000E0300000FFF00001C0200001C02000 01C0200001C0200003804040038000400380008003800080070001000700010007000300 070006000E003E00FFFFFC001D1C7E9B1F>69 D<01FFFFF0003C00F00038003000380020 00380020003800200070002000700020007008200070080000E0100000E0100000E03000 00FFF00001C0200001C0200001C0200001C0200003804000038000000380000003800000 070000000700000007000000070000000F000000FFF000001C1C7E9B1B>I<0001F80800 0E061800380138006000F001C0007003800070070000300F0000200E0000201C0000203C 0000203C000000780000007800000078000000F0000000F0000000F0007FF0F0000780F0 000700F0000700F00007007000070070000E0030000E0038000E001C001E000E00640007 01840000FE00001D1E7E9C21>I<01FFC07F80003C001E00003800180000380020000038 0040000038008000007002000000700400000070080000007010000000E040000000E0C0 000000E1E0000000E2E0000001C470000001D070000001E038000001C038000003803800 0003801C000003801C000003800E000007000E000007000E000007000700000700070000 0F00078000FFE03FF000211C7E9B23>75 D<01FFE0003C00003800003800003800003800 00700000700000700000700000E00000E00000E00000E00001C00001C00001C00001C000 03800203800203800203800407000407000C0700180700380E00F0FFFFF0171C7E9B1C> I<01FE0000FF003E0000F0002E0001E0002E0002E0002E0002E0002E0004E0004E0009C0 004E0009C000470011C000470011C0008700238000870043800087004380008700838001 070107000107010700010382070001038207000203840E000203880E000203880E000203 900E000403A01C000403A01C000401C01C000C01C01C001C01803C00FF8103FF80281C7E 9B28>I<01FC00FF80001C001C00002E001800002E001000002E00100000270010000047 0020000043002000004380200000438020000081C040000081C040000081C040000080E0 40000100E080000100708000010070800001007080000200390000020039000002003900 0002001D000004001E000004000E000004000E00000C000E00001C00040000FF80040000 211C7E9B21>I<01FFFF00003C03C0003800E0003800F00038007000380070007000F000 7000F0007000F0007000E000E001E000E003C000E0070000E01E0001FFF00001C0000001 C0000001C000000380000003800000038000000380000007000000070000000700000007 0000000F000000FFE000001C1C7E9B1B>80 D<0003F800000E0E000038038000E001C001 C001C0038000E0070000E00F0000F01E0000F01C0000F03C0000F03C0000F0780000F078 0000F0780000F0F00001E0F00001E0F00001E0F00003C0F00003C0F0000380F0000780F0 000F00703C0E0070421C0038823800388270001C83C0000787810001FF01000003030000 03020000038E000003FC000003F8000001F8000001E0001C257E9C21>I<01FFFE00003C 03C0003800E0003800F00038007000380070007000F0007000F0007000F0007001E000E0 01C000E0078000E01E0000FFF00001C0380001C00C0001C00E0001C00E0003800E000380 0E0003800E0003800E0007001E0007001E0807001E0807001E100F000F10FFE00F200000 03C01D1D7E9B20>I<01F0030C0C0C1C1E383C301870007000E000E000E000E000E000E0 046008601030601F800F127E9112>99 D<01C003C003C001800000000000000000000000 001C00270047004700870087000E000E001C001C001C003800388038807080710032001C 000A1C7E9B0E>105 D<0FC00001C00001C0000380000380000380000380000700000700 000700000700000E07000E08800E11C00E23C01C47801C83001D00001E00003FC00038E0 00387000387000707100707100707100707200E03200601C00121D7E9C16>107 D<381F81F04E20C6184640E81C4680F01C8F00F01C8E00E01C0E00E01C0E00E01C1C01C0 381C01C0381C01C0381C01C0703803807138038071380380E1380380E270070064300300 3820127E9124>109 D<3C1F004E61804681C04701C08F01C08E01C00E01C00E01C01C03 801C03801C03801C0700380710380710380E10380E2070064030038014127E9119>I<07 878009C86008D03008E03011C03011C03801C03801C03803807003807003807003806007 00E00700C00701800783000E86000E78000E00000E00001C00001C00001C00001C00003C 0000FF0000151A819115>112 D<01C206260C1E181E381C301C701C701CE038E038E038 E038E070E070E07060F023E01CE000E000E001C001C001C001C003801FF00F1A7E9113> I<3C3C4E424687470F8E1E8E0C0E000E001C001C001C001C003800380038003800700030 0010127E9113>I<1C00C0802701C1C04701C1C04701C0C087038040870380400E038040 0E0380401C0700801C0700801C0700801C07010018060100180601001C0E02001C0F0400 0E13080003E1F0001A127E911E>119 D<07878008C84010F0C020F1E020E3C040E18000 E00000E00001C00001C00001C00001C000638080F38080F38100E5810084C60078780013 127E9118>I<1C00C02701C04701C04701C08703808703800E03800E03801C07001C0700 1C07001C0700180E00180E00180E001C1E000C3C0007DC00001C00001800603800F03000 F06000E0C0004180003E0000121A7E9114>I<038107C10FF6081C100800100020004000 80010002000400080410043C1867F843F081E010127E9113>I<000200000300000300FF FF80FFFF80000700000C000008001108789D15>126 D E /Fn 43 122 df<00180030006000C001C00380070007000E001E001C003C003C003C0078007800 78007800F800F000F000F000F000F000F000F000F000F000F000F000F800780078007800 78003C003C003C001C001E000E0007000700038001C000C00060003000180D317BA416> 40 DI< 00180000780001F800FFF800FFF80001F80001F80001F80001F80001F80001F80001F800 01F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F800 01F80001F80001F80001F80001F80001F8007FFFE07FFFE013207C9F1C>49 D<03FC000FFF003C1FC07007E07C07F0FE03F0FE03F8FE03F8FE01F87C01F83803F80003 F80003F00003F00007E00007C0000F80001F00003E0000380000700000E01801C0180380 180700180E00380FFFF01FFFF03FFFF07FFFF0FFFFF0FFFFF015207D9F1C>I<00FE0007 FFC00F07E01E03F03F03F03F81F83F81F83F81F81F03F81F03F00003F00003E00007C000 1F8001FE0001FF000007C00001F00001F80000FC0000FC3C00FE7E00FEFF00FEFF00FEFF 00FEFF00FC7E01FC7801F81E07F00FFFC001FE0017207E9F1C>I<0000E00001E00003E0 0003E00007E0000FE0001FE0001FE00037E00077E000E7E001C7E00187E00307E00707E0 0E07E00C07E01807E03807E07007E0E007E0FFFFFFFFFFFF0007E00007E00007E00007E0 0007E00007E00007E000FFFF00FFFF18207E9F1C>I<3000203E01E03FFFC03FFF803FFF 003FFE003FF80033C00030000030000030000030000031FC0037FF003E0FC03807E03003 E00003F00003F00003F80003F83803F87C03F8FE03F8FE03F8FC03F0FC03F07007E03007 C03C1F800FFF0003F80015207D9F1C>I<001F8000FFE003E07007C0F00F01F81F01F83E 01F83E01F87E00F07C00007C0000FC0800FC7FC0FCFFE0FD80F0FF00F8FE007CFE007CFC 007EFC007EFC007EFC007E7C007E7C007E7C007E3C007C3E007C1E00F80F00F00783E003 FFC000FF0017207E9F1C>I<6000007800007FFFFE7FFFFE7FFFFC7FFFF87FFFF87FFFF0 E00060E000C0C00180C00300C00300000600000C00001C00001800003800007800007800 00F00000F00000F00001F00001F00001F00003F00003F00003F00003F00003F00003F000 03F00001E00017227DA11C>I<00FE0003FFC00703E00E00F01C00F01C00783C00783E00 783F00783F80783FE0F01FF9E01FFFC00FFF8007FFC003FFE007FFF01E7FF83C1FFC7807 FC7801FEF000FEF0003EF0001EF0001EF0001EF8001C7800383C00381F00F00FFFC001FF 0017207E9F1C>I<000070000000007000000000F800000000F800000000F800000001FC 00000001FC00000003FE00000003FE00000003FE000000067F000000067F0000000C7F80 00000C3F8000000C3F800000181FC00000181FC00000301FE00000300FE00000700FF000 006007F000006007F00000C007F80000FFFFF80001FFFFFC00018001FC00018001FC0003 0001FE00030000FE00070000FF000600007F000600007F00FFE007FFF8FFE007FFF82522 7EA12A>65 D<0003FE0080001FFF818000FF01E38001F8003F8003E0001F8007C0000F80 0F800007801F800007803F000003803F000003807F000001807E000001807E00000180FE 00000000FE00000000FE00000000FE00000000FE00000000FE00000000FE00000000FE00 0000007E000000007E000001807F000001803F000001803F000003801F800003000F8000 030007C000060003F0000C0001F800380000FF00F000001FFFC0000003FE000021227DA1 28>67 D69 DI73 D<0007FC0000003FFF800000FC07E00003F001F80007E000FC000FC0007E001F 80003F001F80003F003F00001F803F00001F807F00001FC07E00000FC07E00000FC0FE00 000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE0000 0FE0FE00000FE07E00000FC07F00001FC07F00001FC03F00001F803F80003F801F80003F 000FC0007E0007E000FC0003F001F80000FC07E000003FFF80000007FC000023227DA12A >79 DI82 D<01FE0207FF861F01FE3C007E7C001E78000E78000EF80006F80006FC0006FC0000FF00 00FFE0007FFF007FFFC03FFFF01FFFF80FFFFC03FFFE003FFE0003FE00007F00003F0000 3FC0001FC0001FC0001FE0001EE0001EF0003CFC003CFF00F8C7FFE080FF8018227DA11F >I<7FFFFFFF807FFFFFFF807E03F80F807803F807807003F803806003F80180E003F801 C0E003F801C0C003F800C0C003F800C0C003F800C0C003F800C00003F800000003F80000 0003F800000003F800000003F800000003F800000003F800000003F800000003F8000000 03F800000003F800000003F800000003F800000003F800000003F800000003F800000003 F800000003F800000003F800000003F8000001FFFFF00001FFFFF00022227EA127>II<0FFC003F FF807E07C07E03E07E01E07E01F03C01F00001F00001F0003FF003FDF01FC1F03F01F07E 01F0FC01F0FC01F0FC01F0FC01F07E02F07E0CF81FF87F07E03F18167E951B>97 D<00FF8007FFE00F83F01F03F03E03F07E03F07C01E07C0000FC0000FC0000FC0000FC00 00FC0000FC00007C00007E00007E00003E00181F00300FC06007FFC000FF0015167E9519 >99 D<0001FE000001FE0000003E0000003E0000003E0000003E0000003E0000003E0000 003E0000003E0000003E0000003E0000003E0001FC3E0007FFBE000F81FE001F007E003E 003E007E003E007C003E00FC003E00FC003E00FC003E00FC003E00FC003E00FC003E00FC 003E00FC003E007C003E007C003E003E007E001F00FE000F83BE0007FF3FC001FC3FC01A 237EA21F>I<00FE0007FF800F87C01E01E03E01F07C00F07C00F8FC00F8FC00F8FFFFF8 FFFFF8FC0000FC0000FC00007C00007C00007E00003E00181F00300FC07003FFC000FF00 15167E951A>I<001FC0007FE000F1F001E3F003E3F007C3F007C1E007C00007C00007C0 0007C00007C00007C000FFFE00FFFE0007C00007C00007C00007C00007C00007C00007C0 0007C00007C00007C00007C00007C00007C00007C00007C00007C00007C00007C0003FFC 003FFC00142380A211>I<01FE0F0007FFBF800F87C7801F03E7801E01E0003E01F0003E 01F0003E01F0003E01F0003E01F0001E01E0001F03E0000F87C0000FFF800009FE000018 000000180000001C0000001FFFE0000FFFF80007FFFE001FFFFF003C003F0078000F80F0 000780F0000780F0000780F000078078000F003C001E001F007C000FFFF80001FFC00019 217F951C>II<1C003E007F007F007F003E001C0000000000000000000000000000 00FF00FF001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F001F 001F001F00FFE0FFE00B247EA310>I108 DII<00FE0007FFC00F83E01E00F03E00F87C007C7C007C7C007CFC007EFC007EFC 007EFC007EFC007EFC007EFC007E7C007C7C007C3E00F81F01F00F83E007FFC000FE0017 167E951C>II<00FE03 0007FF87000FC1C7001F006F003F003F007E003F007E001F007C001F00FC001F00FC001F 00FC001F00FC001F00FC001F00FC001F00FC001F007E001F007E001F003E003F001F007F 000FC1DF0007FF9F0001FC1F0000001F0000001F0000001F0000001F0000001F0000001F 0000001F0000001F000000FFE00000FFE01B207E951E>II<0FF3003FFF00781F006007 00E00300E00300F00300FC00007FE0007FF8003FFE000FFF0001FF00000F80C00780C003 80E00380E00380F00700FC0E00EFFC00C7F00011167E9516>I<01800001800001800001 80000380000380000780000780000F80003F8000FFFF00FFFF000F80000F80000F80000F 80000F80000F80000F80000F80000F80000F80000F80000F81800F81800F81800F81800F 81800F830007C30003FE0000F80011207F9F16>IIIIII E /Fo 8 117 df<78FCFCFCFC7806067D850C >46 D<000300000007800000078000000FC000000FC000000FC000001BE000001BE00000 3BF0000031F0000031F0000060F8000060F80000E0FC0000C07C0000C07C0001803E0001 FFFE0003FFFF0003001F0007001F8006000F8006000F800C0007C0FF803FFCFF803FFC1E 1A7F9921>65 D<1FF000383C007C1E007C0F007C0F00380F00000F0000FF000FCF003E0F 007C0F00F80F00F80F00F80F00F817007C27E01FC3E013117F9015>97 DI<03FC000F0E001C1F003C1F00781F00780E00F80000F8 0000F80000F80000F800007800007800003C01801C03000F060003FC0011117F9014>I< F8F0F9383A7C3A7C3C7C3C383C003C003C003C003C003C003C003C003C00FF80FF800E11 7E9012>114 D<1FD820784018C018C018F000FF807FE03FF007F8003CC00CC00CE00CE0 08F830CFE00E117F9011>I<06000600060006000E000E001E003FF0FFF01E001E001E00 1E001E001E001E001E001E181E181E181E181E180F3003E00D187F9711>I E /Fp 68 124 df<00FE000381000601800E03801C01001C00001C00001C00001C00001C 0000FFFF801C03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C 03801C03801C03801C0380FF8FF0141A809915>12 D<01C0000003200000061000000E10 00000E1000000E1000000E1000000E2000000E4000000E40000007807F8007001E000700 0800078010000B80100011C0200031E0200060E0400060708000E0788000E03D0000E01E 0080E00E0080701F01003861C3000F807C00191A7E991E>38 D<00800100020004000C00 080018003000300030006000600060006000E000E000E000E000E000E000E000E000E000 E0006000600060006000300030003000180008000C00040002000100008009267D9B0F> 40 D<8000400020001000180008000C0006000600060003000300030003000380038003 80038003800380038003800380038003000300030003000600060006000C000800180010 0020004000800009267E9B0F>I<60F0F07010101020204040040B7D830B>44 DI<60F0F06004047D830B>I<07E01C38381C300C700E60066006 E007E007E007E007E007E007E007E007E007E00760066006700E300C381C1C3807E01018 7F9713>48 D<03000700FF00070007000700070007000700070007000700070007000700 070007000700070007000700070007007FF80D187D9713>I<0F80106020304038803CC0 1CE01C401C003C003800380070006000C001800100020004040804100430083FF87FF8FF F80E187E9713>I<07E01838201C601E700E201E001E001C001C0038007007E00038001C 000E000F000FE00FE00FC00F400E601C183807E010187F9713>I<001800180038007800 F800B8013802380238043808381838103820384038C038FFFF0038003800380038003800 3803FF10187F9713>I<30183FF03FE03F80200020002000200020002FC0306020300038 0018001C001C401CE01CE01C80184038403030E00F800E187E9713>I<01F807040C0618 0E300E300070006000E000E3E0E418E80CF00EE006E007E007E007600760077006300E18 0C0C3807E010187F9713>I<40007FFF7FFE7FFE40048008801080100020004000400080 01800100030003000700060006000E000E000E000E000E00040010197E9813>I<07E018 18300C2006600660067006780C3E181F3007C003E00CF8307C601E600FC007C003C003C0 0360022004181807E010187F9713>I<07E01C303018700C600EE006E006E007E007E007 6007700F3017182707C700070006000E000C700C7018603030600F8010187F9713>I<60 F0F060000000000000000060F0F06004107D8F0B>I<000C0000000C0000000C0000001E 0000001E0000002F000000270000002700000043800000438000004380000081C0000081 C0000181E0000100E0000100E00003FFF000020070000200700004003800040038000400 380008001C0008001C003C001E00FF00FFC01A1A7F991D>65 DI<003F0201C0C603002E0E001E1C000E1C0006380006780002700002700002F00000 F00000F00000F00000F00000F000007000027000027800023800041C00041C00080E0008 03003001C0C0003F00171A7E991C>IIII<003F020001C0C60003002E000E001E001C000E001C000600380006 00780002007000020070000200F0000000F0000000F0000000F0000000F0000000F001FF C070000E0070000E0078000E0038000E001C000E001C000E000E000E000300160001C066 00003F82001A1A7E991E>III<0FFE0070007000700070007000700070007000700070007000700070007000700070 0070007000704070E070E07040E061C01F000F1A7E9914>IIIII80 D82 D<0FC21836200E6006C006C002C002C002E00070007E003FE01FF803FC007E000E000700 03800380038003C002C006E004D81887E0101A7E9915>I<7FFFFF00701C0700401C0100 401C0100C01C0180801C0080801C0080801C0080001C0000001C0000001C0000001C0000 001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000 001C0000001C0000001C0000001C000003FFE000191A7F991C>IIIII 91 D93 D<1FC000387000383800101C00001C00001C0003FC001E1C00 381C00701C00E01C00E01C80E01C80E03C80705F801F8F0011107F8F13>97 DI<07F81C1C381C70087000E000E000E000E000E000E000 7000700438081C1807E00E107F8F11>I<003F0000070000070000070000070000070000 070000070000070000070003E7000C1700180F00300700700700E00700E00700E00700E0 0700E00700E00700600700700700380F001C370007C7E0131A7F9915>I<07C01C303018 7018600CE00CFFFCE000E000E000E0006000700438081C1807E00E107F8F11>I<01F007 180E381C101C001C001C001C001C001C00FFC01C001C001C001C001C001C001C001C001C 001C001C001C001C001C00FF800D1A80990C>I<0FCF0018718030300070380070380070 38007038003030001860002FC0006000006000007000003FF0003FFC001FFE00600F00C0 0300C00300C00300C00300600600381C0007E00011187F8F13>II<183C3C18000000000000FC1C1C1C1C1C1C1C1C1C1C1C1C1C1CFF081A80990A>I< FC00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C1FC01C0F00 1C0C001C18001C20001C40001CE0001DE0001E70001C78001C38001C1C001C1E001C0F00 1C0F80FF9FE0131A809914>107 DI II<07E01C38300C700E6006E007E007E007 E007E007E0076006700E381C1C3807E010107F8F13>II<03E1000C1300180B00 300F00700700E00700E00700E00700E00700E00700E00700700700700700380F001C3700 07C700000700000700000700000700000700000700003FE013177F8F14>II<1F20 60E04020C020C020F0007F003FC01FE000F080708030C030C020F0408F800C107F8F0F> I<0800080008000800180018003800FFC038003800380038003800380038003800382038 203820382018201C4007800B177F960F>I IIIIIII E /Fq 3 66 df<1878981818181818181818 18181818FF08107D8F0F>49 D<1F00618040C08060C0600060006000C00180030006000C 00102020207FC0FFC00B107F8F0F>I<00C00000C00001E0000160000160000230000230 00023000041800041800080C000FFC00080C00100600100600300700FC1FC012117F9016 >65 D E /Fr 3 52 df<0C001C00EC000C000C000C000C000C000C000C000C000C000C00 0C000C000C000C000C00FFC00A137D9211>49 D<1F0060C06060F070F030603000700070 006000C001C00180020004000810101020207FE0FFE00C137E9211>I<0FC03070703870 3870380038003000E00FC0007000380018001C601CF01CF018E03860701FC00E137F9211 >I E /Fs 78 123 df<007E1F0001C1B1800303E3C00703C3C00E03C1800E01C0000E01 C0000E01C0000E01C0000E01C0000E01C000FFFFFC000E01C0000E01C0000E01C0000E01 C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01 C0000E01C0000E01C0000E01C0007F87FC001A1D809C18>11 D<007E0001C18003018007 03C00E03C00E01800E00000E00000E00000E00000E0000FFFFC00E01C00E01C00E01C00E 01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E 01C07F87F8151D809C17>I<007FC001C1C00303C00703C00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C0FFFFC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C07FCFF8151D809C17>I<003F 07E00001C09C18000380F018000701F03C000E01E03C000E00E018000E00E000000E00E0 00000E00E000000E00E000000E00E00000FFFFFFFC000E00E01C000E00E01C000E00E01C 000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C00 0E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C007FC7FCFF8021 1D809C23>I16 D<0E0E1E3870E0800707779C15>19 D<60F0F0F0F0F0F0F060606060606060606060606060000000000060F0F060041E7C9D0C >33 D<6060F0F0F8F86868080808080808101010102020404080800D0C7F9C15>I<60F0 F8680808081010204080050C7C9C0C>39 D<00800100020006000C000C00180018003000 300030006000600060006000E000E000E000E000E000E000E000E000E000E000E000E000 6000600060006000300030003000180018000C000C000600020001000080092A7C9E10> I<8000400020003000180018000C000C0006000600060003000300030003000380038003 8003800380038003800380038003800380038003000300030003000600060006000C000C 00180018003000200040008000092A7E9E10>I<60F0F0701010101020204080040C7C83 0C>44 DI<60F0F06004047C830C>I<03C00C301818300C300C70 0E60066006E007E007E007E007E007E007E007E007E007E007E007E007E0076006600670 0E300C300C18180C3007E0101D7E9B15>48 D<010007003F00C700070007000700070007 000700070007000700070007000700070007000700070007000700070007000700070007 00FFF80D1C7C9B15>I<07C01830201C400C400EF00FF80FF807F8077007000F000E000E 001C001C00380070006000C00180030006010C01180110023FFE7FFEFFFE101C7E9B15> I<07E01830201C201C781E780E781E381E001C001C00180030006007C00030001C001C00 0E000F000F700FF80FF80FF80FF00E401C201C183007C0101D7E9B15>I<000C00000C00 001C00003C00003C00005C0000DC00009C00011C00031C00021C00041C000C1C00081C00 101C00301C00201C00401C00C01C00FFFFC0001C00001C00001C00001C00001C00001C00 001C0001FFC0121C7F9B15>I<300C3FF83FF03FC020002000200020002000200023E02C 303018301C200E000E000F000F000F600FF00FF00FF00F800E401E401C2038187007C010 1D7E9B15>I<00F0030C04040C0E181E301E300C700070006000E3E0E430E818F00CF00E E006E007E007E007E007E007600760077006300E300C18180C3003E0101D7E9B15>I<40 00007FFF807FFF007FFF0040020080040080040080080000100000100000200000600000 400000C00000C00001C00001800001800003800003800003800003800007800007800007 8000078000078000078000030000111D7E9B15>I<03E00C301008200C20066006600670 0670067C0C3E183FB01FE007F007F818FC307E601E600FC007C003C003C003C003600260 04300C1C1007E0101D7E9B15>I<03C00C301818300C700C600EE006E006E007E007E007 E007E0076007700F300F18170C2707C700060006000E300C780C78187018203010C00F80 101D7E9B15>I<60F0F0600000000000000000000060F0F06004127C910C>I<60F0F06000 00000000000000000060F0F0701010101020204080041A7C910C>I<7FFFFFC0FFFFFFE0 0000000000000000000000000000000000000000000000000000000000000000FFFFFFE0 7FFFFFC01B0C7E8F20>61 D<003F800000C0600003001800040004000800020010000100 201F00802070808040E0404040C0384041C0384081803820838038208380382083803820 83803820838038208180382041C0382040C0384040E0784020709880201F0F0010000000 0800000004000000030001E000C01F80003FF0001B1D7E9C20>64 D<000600000006000000060000000F0000000F0000000F000000178000001780000037C0 000023C0000023C0000043E0000041E0000041E0000080F0000080F0000080F000010078 000100780001FFF80002003C0002003C0002003C0004001E0004001E000C001F000C000F 001E001F00FF00FFF01C1D7F9C1F>II<001F808000E0618001 801980070007800E0003801C0003801C00018038000180780000807800008070000080F0 000000F0000000F0000000F0000000F0000000F0000000F0000000F00000007000008078 00008078000080380000801C0001001C0001000E000200070004000180080000E0300000 1FC000191E7E9C1E>IIII<001F808000E061800180198007 0007800E0003801C0003801C00018038000180780000807800008070000080F0000000F0 000000F0000000F0000000F0000000F0000000F000FFF0F0000F80700007807800078078 000780380007801C0007801C0007800E00078007000B800180118000E06080001F80001C 1E7E9C21>III75 DIII<003F800000E0E0000380380007001C000E000E 001C0007003C00078038000380780003C0780003C0700001C0F00001E0F00001E0F00001 E0F00001E0F00001E0F00001E0F00001E0F00001E0700001C0780003C0780003C0380003 803C0007801C0007000E000E0007001C000380380000E0E000003F80001B1E7E9C20>I< FFFF800F00E00F00780F003C0F001C0F001E0F001E0F001E0F001E0F001E0F001C0F003C 0F00780F00E00FFF800F00000F00000F00000F00000F00000F00000F00000F00000F0000 0F00000F00000F0000FFF000171C7E9B1C>I<003F800000E0E0000380380007001C000E 000E001C0007003C00078038000380780003C0780003C0700001C0F00001E0F00001E0F0 0001E0F00001E0F00001E0F00001E0F00001E0F00001E0700001C0780003C0780003C038 0003803C0E07801C1107000E208E0007205C0003A0780000F0E020003FE0200000602000 003060000038E000003FC000003FC000001F8000000F001B257E9C20>II<07E0801C1980300580300380600180E00180E00080E00080E00080 F00000F800007C00007FC0003FF8001FFE0007FF0000FF80000F800007C00003C00001C0 8001C08001C08001C0C00180C00180E00300D00200CC0C0083F800121E7E9C17>I<7FFF FFC0700F01C0600F00C0400F0040400F0040C00F0020800F0020800F0020800F0020000F 0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000001F800003FF FC001B1C7F9B1E>II87 D91 D<08081010202040404040808080808080B0B0F8F87878 30300D0C7A9C15>II<1FC000307000783800781C00301C00 001C00001C0001FC000F1C00381C00701C00601C00E01C40E01C40E01C40603C40304E80 1F870012127E9115>97 DI<03F80C 0C181E301E700C6000E000E000E000E000E000E00060007002300218040C1803E00F127F 9112>I<001F800003800003800003800003800003800003800003800003800003800003 8003F3800E0B80180780300380700380600380E00380E00380E00380E00380E00380E003 806003807003803003801807800E1B8003E3F0141D7F9C17>I<07E00C301818300C700E 6006E006FFFEE000E000E000E00060007002300218040C1803E00F127F9112>I<00F801 8C071E061E0E0C0E000E000E000E000E000E00FFE00E000E000E000E000E000E000E000E 000E000E000E000E000E000E000E000E007FE00F1D809C0D>I<00038007C4C01C78C038 3880301800701C00701C00701C00701C003018003838001C700027C00020000020000030 00003FF8001FFF001FFF802003806001C0C000C0C000C0C000C06001803003001C0E0007 F800121C7F9215>II<18003C003C 0018000000000000000000000000000000FC001C001C001C001C001C001C001C001C001C 001C001C001C001C001C001C001C00FF80091D7F9C0C>I<00C001E001E000C000000000 0000000000000000000007E000E000E000E000E000E000E000E000E000E000E000E000E0 00E000E000E000E000E000E000E000E060E0F0C0F1C061803E000B25839C0D>III II<03F0000E1C0018060030 0300700380600180E001C0E001C0E001C0E001C0E001C0E001C060018070038030030018 06000E1C0003F00012127F9115>II<03E0800E19801805 80380780700380700380E00380E00380E00380E00380E00380E003807003807003803807 801807800E1B8003E380000380000380000380000380000380000380000380001FF0141A 7F9116>II<1F9020704030C010C010E010F8007F803FE00FF000F88038 8018C018C018E010D0608FC00D127F9110>I<04000400040004000C000C001C003C00FF E01C001C001C001C001C001C001C001C001C001C101C101C101C101C100C100E2003C00C 1A7F9910>IIIIII<7FFC7038603840 7040F040E041C003C0038007000F040E041C043C0C380870087038FFF80E127F9112>I E /Ft 20 122 df<00007FE0030007FFFC07001FFFFF0F007FF00F9F00FF0001FF01FC00 00FF03F800007F07F000003F0FE000001F1FC000001F1FC000000F3F8000000F3F800000 077F800000077F800000077F00000000FF00000000FF00000000FF00000000FF00000000 FF00000000FF00000000FF00000000FF00000000FF000000007F000000007F800000007F 800000073F800000073F800000071FC00000071FC000000E0FE000000E07F000001C03F8 00003C01FC00007800FF0001F0007FF007C0001FFFFF800007FFFE0000007FF00028297C A831>67 D 80 D82 D<00FF00C003FFE1C00FFFF9C01F80FFC03F003FC03E000FC07C0007C07C0007 C0FC0003C0FC0003C0FC0001C0FE0001C0FE0001C0FF000000FFC000007FFC00007FFFE0 003FFFF8001FFFFE001FFFFF0007FFFF8003FFFFC000FFFFC0000FFFE000007FE000001F F000000FF0000007F0E00003F0E00003F0E00003F0E00003F0F00003E0F00003E0F80007 E0FC0007C0FF000F80FFE01F80E3FFFF00E1FFFC00C01FF0001C297CA825>I<03FF8000 0FFFF0001F01FC003F80FE003F807F003F803F003F803F801F003F8000003F8000003F80 00003F8000003F80003FFF8001FC3F800FE03F801F803F803F003F807E003F80FC003F80 FC003F80FC003F80FC003F80FC005F807E00DF803F839FFC1FFE0FFC03F803FC1E1B7E9A 21>97 DI<00 3FF00001FFFC0003F03E000FC07F001F807F003F007F003F007F007F003E007E0000007E 000000FE000000FE000000FE000000FE000000FE000000FE000000FE0000007E0000007E 0000007F0000003F0003803F8003801F8007000FE00E0003F83C0001FFF800003FC00019 1B7E9A1E>I<003FC00001FFF00003E07C000F803E001F801F001F001F003F000F807E00 0F807E000FC07E000FC0FE0007C0FE0007C0FFFFFFC0FFFFFFC0FE000000FE000000FE00 00007E0000007E0000007F0000003F0001C01F0001C00F80038007C0070003F01E0000FF FC00003FE0001A1B7E9A1F>101 D<007F80F001FFE3F807C0FE1C0F807C7C1F003E7C1F 003E103F003F003F003F003F003F003F003F003F003F003F003F001F003E001F003E000F 807C0007C0F80005FFE0000C7F8000180000001C0000001C0000001E0000001FFFF8001F FFFF000FFFFFC007FFFFE003FFFFF00FFFFFF03E0007F07C0001F8F80000F8F80000F8F8 0000F8F80000F87C0001F07C0001F03F0007E00FC01F8007FFFF00007FF0001E287E9A22 >103 DI<07 000F801FC03FE03FE03FE01FC00F8007000000000000000000000000000000FFE0FFE0FF E00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00F E00FE00FE00FE0FFFEFFFEFFFE0F2B7EAA12>I108 D110 D<003FE00001FFFC0003F07E000FC01F801F800FC03F00 07E03F0007E07E0003F07E0003F07E0003F0FE0003F8FE0003F8FE0003F8FE0003F8FE00 03F8FE0003F8FE0003F8FE0003F87E0003F07E0003F03F0007E03F0007E01F800FC00FC0 1F8007F07F0001FFFC00003FE0001D1B7E9A22>II114 D<03FE300FFFF03E03F07800F07000 F0F00070F00070F80070FE0000FFE0007FFF007FFFC03FFFE01FFFF007FFF800FFF80007 FC0000FCE0007CE0003CF0003CF00038F80038FC0070FF01E0E7FFC0C1FF00161B7E9A1B >I<00700000700000700000700000F00000F00000F00001F00003F00003F00007F0001F FFE0FFFFE0FFFFE007F00007F00007F00007F00007F00007F00007F00007F00007F00007 F00007F00007F00007F00007F07007F07007F07007F07007F07007F07007F07003F0E001 F8C000FFC0003F0014267FA51A>II121 D E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%EndSetup %%Page: 1 1 1 0 bop 283 194 a Ft(Reasoning)22 b(ab)r(out)h(Cryptographic)h(Proto)r (cols)623 277 y(in)f(the)g(Spi)h(Calculus)539 421 y Fs(Mart)-5 b(\023)-16 b(\020n)13 b(Abadi)788 406 y Fr(1)820 421 y Fs(and)h(Andrew)h(D.)c(Gordon)1249 406 y Fr(2)398 492 y Fq(1)434 508 y Fp(Digital)16 b(Equipmen)o(t)e(Corp)q(oration,)h (Systems)f(Researc)o(h)f(Cen)o(ter)483 538 y Fq(2)519 554 y Fp(Univ)o(ersit)o(y)i(of)e(Cam)o(bridge,)h(Computer)f(Lab)q (oratory)301 675 y Fo(Abstract.)22 b Fp(The)13 b(spi)h(calculus)h(is)e (an)g(extension)i(of)e(the)g(pi)h(calculus)h(with)e(con-)301 721 y(structs)j(for)g(encryption)j(and)d(decryption.)i(This)f(pap)q(er) g(dev)o(elops)h(the)f(theory)301 766 y(of)12 b(the)g(spi)h(calculus,)h (fo)q(cusing)g(on)e(tec)o(hniques)i(for)e(establishin)q(g)j(testing)e (equiv-)301 812 y(alence,)j(and)h(applying)h(these)f(tec)o(hniques)g (to)f(the)g(pro)q(of)g(of)f(authen)o(ticit)o(y)k(and)301 858 y(secrecy)13 b(prop)q(erties)i(of)e(cryptographic)i(proto)q(cols.) 183 993 y Fn(1)56 b(F)-5 b(rom)18 b(Cryptograph)n(y)h(to)f(T)-5 b(esting)18 b(Equiv)m(alence)183 1087 y Fs(The)13 b(idea)g(of)g(con)o (trolling)e(comm)o(unication)f(b)o(y)j(capabilities)f(underlies)i(b)q (oth)g(the)f(pi)g(cal-)183 1137 y(culus)21 b(and)f(m)o(uc)o(h)g(of)g (the)h(curren)o(t)h(w)o(ork)f(on)f(securit)o(y)i(in)e(distributed)h (systems)g(\(see)183 1186 y(e.g.)11 b([MPW92)o(,)17 b(Lie93)o(,)g(Sc)o (h96b]\).)f(In)i(the)f(pi)g(calculus,)g(c)o(hannel)g(names)g(are)g (capabili-)183 1236 y(ties;)11 b(a)g(pro)q(cess)i(can)f(use)g(a)f(c)o (hannel)g(only)g(if)g(it)f(has)i(in)o(v)o(en)o(ted)f(or)h(b)q(een)g (giv)o(en)f(the)h(name)e(of)183 1286 y(the)i(c)o(hannel,)f(but)h (cannot)g(guess)h(this)f(name.)e(In)h(w)o(ork)h(on)f(securit)o(y)m(,)h (on)f(the)i(other)f(hand,)183 1336 y(the)h(capabilities)e(for)h(comm)o (unication)d(are)k(often)f(k)o(eys,)h(whic)o(h)f(are)h(used)g(for)f (encrypting)183 1386 y(and)h(decrypting)i(messages)f(that)g(tra)o(v)o (el)f(on)h(otherwise)h(unprotected)h(c)o(hannels.)245 1435 y(These)g(observ)n(ations)g(motiv)n(ate)d(the)j(de\014nition)f(of) g(the)h(spi)f(calculus,)g(an)g(extension)183 1485 y(of)j(the)h(pi)f (calculus)h(with)g(constructs)h(for)f(encryption)g(and)g(decryption.)g (In)f(a)h(recen)o(t)183 1535 y(pap)q(er)13 b([A)o(G97a)n(],)18 b(w)o(e)h(in)o(tro)q(duced)h(the)f(spi)g(calculus)g(and)f(w)o(e)h(sho)o (w)o(ed)g(ho)o(w)g(it)f(can)h(b)q(e)183 1585 y(used)c(for)g(describing) g(proto)q(cols,)f(particularly)g(authen)o(tication)h(proto)q(cols.)f (This)h(pap)q(er)183 1635 y(dev)o(elops)f(the)h(theory)f(of)g(the)g (spi)g(calculus,)g(concen)o(trating)g(on)g(results)h(and)f(tec)o (hniques)183 1685 y(for)f(v)o(erifying)g(securit)o(y)i(prop)q(erties)g (of)e(proto)q(cols.)245 1734 y(As)e(a)g(\014rst,)g(informal)d(example,) h(let)i(us)g(consider)h(a)f(proto)q(col)f(where)i(a)f(user)h Fm(A)f Fs(sends)h(a)183 1784 y(message)g Fm(M)k Fs(under)d(a)f(shared)h (k)o(ey)g Fm(K)i Fs(to)d(a)g(user)h Fm(B)i Fs(on)d(a)g(public)g(c)o (hannel.)g(It)g(is)g(straigh)o(t-)183 1834 y(forw)o(ard)17 b(to)g(write)h(this)f(proto)q(col)h(in)f(the)h(spi)f(calculus.)g(W)m(e) g(ma)o(y)f(w)o(an)o(t)h(to)g(formalise,)183 1884 y(and)g(then)i(v)o (erify)m(,)d(t)o(w)o(o)h(imp)q(ortan)o(t)f(prop)q(erties)j(of)e(this)h (proto)q(col:)f(\(1\))12 b(if)17 b Fm(B)j Fs(receiv)o(es)g(a)183 1934 y(message,)f(then)i(it)f(is)g(the)g(one)h(that)f Fm(A)g Fs(sen)o(t,)h(and)f(\(2\))12 b(no)20 b(ea)o(v)o(esdropp)q(er)i (learns)e Fm(M)5 b Fs(.)183 1983 y(These)17 b(prop)q(erties)h(hold)d (ev)o(en)i(in)f(the)g(presence)j(of)d(an)g(activ)o(e)g(attac)o(k)o(er,) g(pro)o(vided)g(the)183 2033 y(attac)o(k)o(er)j(do)q(es)g(not)f(ha)o(v) o(e)h(access)h(to)f Fm(K)s Fs(.)f(T)m(aking)f(the)i(p)q(oin)o(t)f(of)g (view)g(of)g(suc)o(h)i(an)e(at-)183 2083 y(tac)o(k)o(er,)13 b(w)o(e)h(can)g(rephrase)h(prop)q(erties)g(\(1\))f(and)f(\(2\))h(in)f (terms)g(of)g(an)h(informal)c(notion)j(of)183 2133 y (indistinguishabilit)o(y:)e(\(1\))h(the)j(proto)q(col)f(is)g (indistinguishable)f(from)f(one)j(where)g Fm(B)i Fs(dis-)183 2183 y(cards)e(the)g(message)g(that)g(it)f(receiv)o(es)i(and)f(acts)g (as)g(though)f(the)i(message)e(w)o(as)h Fm(M)5 b Fs(,)14 b(and)183 2232 y(\(2\))e(assuming)g(that)i Fm(A)g Fs(and)f Fm(B)j Fs(do)d(not)h(rev)o(eal)g Fm(M)k Fs(b)q(eforehand)c(or)g(afterw) o(ards,)f(the)i(pro-)183 2282 y(to)q(col)d(is)g(indistinguishable)g (from)e(one)j(where)h(some)d(other)i(message)g Fm(M)1345 2267 y Fl(0)1369 2282 y Fs(is)f(sen)o(t)h(instead)183 2332 y(of)f Fm(M)5 b Fs(.)245 2382 y(In)15 b(ligh)o(t)e(of)i(this)g (example,)e(it)h(seems)h(imp)q(ortan)o(t)e(to)i(\014nd)g(a)f(formal)f (coun)o(terpart)j(to)183 2432 y(the)g(informal)c(notion)j(of)f (indistinguishabilit)o(y)m(.)e(The)k(concurrency)h(literature)f (suggests)p eop %%Page: 2 2 2 1 bop 340 194 a Fs(sev)o(eral)12 b(candidates.)g(Unfortunately)m(,)e (a)i(straigh)o(tforw)o(ard)e(notion)h(of)g(bisimilarit)o(y)d(w)o(ould) 340 244 y(b)q(e)16 b(to)q(o)g(\014ne-grained)f(\(b)q(ecause)i(it)e(w)o (ould)g(b)q(e)h(sensitiv)o(e)g(to)f(the)h(con)o(ten)o(ts)h(of)d (encrypted)340 293 y(messages)g(ev)o(en)g(if)f(the)h(corresp)q(onding)g (k)o(eys)g(are)g(nev)o(er)g(disclosed\).)g(A)f(more)f(promising)340 343 y(approac)o(h)k(is)f(based)h(on)g(testing)g(equiv)n(alence.)f (Roughly)m(,)e(t)o(w)o(o)i(pro)q(cesses)j Fm(P)j Fs(and)16 b Fm(Q)f Fs(are)340 393 y(testing)d(equiv)n(alen)o(t)f(if,)f(although)h (they)h(ma)o(y)e(ha)o(v)o(e)h(di\013eren)o(t)i(in)o(ternal)e (structure,)i(a)e(third)340 443 y(pro)q(cess)i Fm(R)d Fs(cannot)g(di\013eren)o(tiate)h(running)f(in)g(parallel)f(with)h Fm(P)16 b Fs(from)9 b(running)h(in)f(parallel)340 493 y(with)17 b Fm(Q)p Fs(.)f(W)m(e)g(lik)o(e)g(testing)h(equiv)n(alence)f (for)h(the)g(sp)q(eci\014cation)g(of)f(securit)o(y)i(prop)q(erties)340 542 y(b)q(ecause)j(it)d(is)g(su\016cien)o(tly)g(coarse-grained,)h(and)f (b)q(ecause)j(a)d(test)h(captures)h(the)g(idea)340 592 y(of)14 b(an)h(observ)n(ation)f(that)g(another)h(pro)q(cess)i(\(suc)o (h)e(as)g(an)f(attac)o(k)o(er\))h(ma)o(y)e(p)q(erform)g(on)i(a)340 642 y(pro)q(cess.)403 695 y(Our)21 b(testing)g(equiv)n(alence)f(is)g(a) h(v)o(ersion)f(of)g(De)h(Nicola's)e(and)h(Hennessy's)i(ma)o(y-)340 745 y(testing)14 b(equiv)n(alence)f([DH84)o(],)f(whic)o(h)i(essen)o (tially)f(relies)h(on)f(tests)i(of)e(safet)o(y)g(prop)q(erties.)340 794 y(Our)f(emphasis)e(on)h(safet)o(y)h(agrees)g(with)f(that)g(of)f (the)i(securit)o(y)g(literature,)f(where)i(liv)o(eness)340 844 y(is)h(often)g(secondary)h(\(in)f(part)g(b)q(ecause)h(it)f(is)f(t)o (ypically)g(hard)h(to)g(guaran)o(tee\).)403 897 y(While)g(the)i(use)g (of)e(testing)i(equiv)n(alence)f(ma)o(y)f(lead)h(to)g(neat)g(sp)q (eci\014cations,)h(it)f(also)340 947 y(implies)h(serious)j (di\016culties)e(in)g(v)o(eri\014cations.)g(Naiv)o(ely)m(,)f(in)h (order)i(to)e(pro)o(v)o(e)h(that)g(t)o(w)o(o)340 997 y(pro)q(cesses)j Fm(P)j Fs(and)18 b Fm(Q)h Fs(are)f(testing)h(equiv)n (alen)o(t,)e(one)i(w)o(ould)e(need)j(to)e(consider)h(an)f(ar-)340 1046 y(bitrary)f(attac)o(k)o(er)g Fm(R)f Fs(and)g(arbitrary)g (sequences)j(of)d(in)o(teractions)h(with)f Fm(R)p Fs(.)f(This)i(pap)q (er)340 1096 y(in)o(v)o(estigates)g(more)e(sophisticated)i(metho)q(ds)f (for)g(pro)o(ving)g(testing)g(equiv)n(alence)h(in)f(the)340 1146 y(spi)c(calculus.)g(Some)f(of)g(these)i(metho)q(ds)f(are)g(based)h (on)e(earlier)h(w)o(ork)g(on)g(the)g(pi)g(calculus,)340 1196 y(with)18 b(new)g(ingredien)o(ts)h(motiv)n(ated)d(b)o(y)i(our)g (in)o(terest)h(in)e(securit)o(y)i(and)f(cryptograph)o(y)m(.)340 1246 y(While)12 b(our)h(tec)o(hniques)h(ma)o(y)d(not)h(b)q(e)i (complete,)d(they)i(constitute)h(a)f(useful)f(set)i(of)e(to)q(ols.)340 1295 y(With)g(these)i(tec)o(hniques,)f(w)o(e)g(can)f(establish)h (securit)o(y)g(prop)q(erties)h(of)e(particular)g(crypto-)340 1345 y(graphic)f(proto)q(cols,)f(for)f(example)g(formal)f(v)o(ersions)j (of)f(prop)q(erties)k(\(1\))c(and)i(\(2\))f(discussed)340 1395 y(ab)q(o)o(v)o(e.)340 1534 y Fk(Con)o(ten)o(ts)340 1632 y Fs(Section)i(2)d(is)g(an)f(informal)f(review)i(of)f(the)i(spi)f (calculus.)f(Section)k(3)d(giv)o(es)g(t)o(w)o(o)f(op)q(erational)340 1682 y(seman)o(tics)k(of)g(the)h(spi)f(calculus.)g(Section)g(4)g (de\014nes)h(testing)g(equiv)n(alence)f(precisely)h(and)340 1731 y(commences)k(its)h(study)m(.)g(Section)13 b(5)18 b(and)13 b(6)18 b(study)i(some)e(other)h(equiv)n(alences)h(and)f(the) 340 1781 y(new)14 b(underpinning)g(relation;)e(these)j(are)f(useful)g (in)f(our)g(pro)q(ofs)h(of)f(testing)h(equiv)n(alence.)340 1831 y(Section)f(7)g(discusses)j(ho)o(w)d(our)g(tec)o(hniques)i(can)e (b)q(e)h(applied,)f(through)g(an)g(example.)f(Fi-)340 1881 y(nally)m(,)f(Section)i(8)f(men)o(tions)g(some)f(related)j(w)o (ork)e(and)h(some)e(conclusions.)i(Throughout,)340 1931 y(w)o(e)18 b(restrict)g(atten)o(tion)f(to)g(shared-k)o(ey)h (cryptograph)o(y)g(\(where)g(the)g(same)e(k)o(ey)h(is)g(used)340 1980 y(for)d(encrypting)h(and)f(decrypting)g(a)g(message\);)g(there)h (are)g(v)n(arian)o(ts)e(of)g(the)i(spi)f(calculus)340 2030 y(for)g(other)g(\015a)o(v)o(ours)g(of)f(cryptograph)o(y)m(,)h(but) g(w)o(e)g(ha)o(v)o(e)f(not)h(y)o(et)g(studied)h(their)f(theory)m(.)403 2083 y(This)j(pap)q(er)i(is)f(a)g(companion)d(to)j(the)h(pap)q(er)f (where)h(w)o(e)g(in)o(tro)q(duced)f(the)h(spi)f(cal-)340 2133 y(culus)13 b([A)o(G97a)o(].)h(That)i(pap)q(er)g(co)o(v)o(ers)h (the)f(material)d(of)j(Section)c(2)k(at)f(a)h(more)e(leisurely)340 2183 y(pace,)20 b(with)e(a)h(gen)o(tle)g(in)o(tro)q(duction)g(to)g(the) h(pi)e(calculus)h(and)g(the)h(spi)f(calculus,)f(and)340 2232 y(man)o(y)d(examples.)h(It)h(also)f(explains)g(the)i(simpler)d(of) i(the)g(op)q(erational)f(seman)o(tics)h(\(the)340 2282 y(reaction)h(relation\),)e(then)i(giv)o(es)f(the)h(de\014nition)f(of)g (testing)g(equiv)n(alence.)g(It)g(do)q(es)h(not)340 2332 y(con)o(tain)d(theorems,)g(pro)q(of)g(tec)o(hniques,)h(or)g(pro)q(ofs)f (for)g(examples,)f(whic)o(h)h(are)h(the)g(sub-)340 2382 y(ject)e(of)e(this)h(pap)q(er.)g(Most)h(of)e(the)h(material)e(in)i(the) g(t)o(w)o(o)g(pap)q(ers)h(is)e(included)h(in)g(a)g(longer)340 2432 y(rep)q(ort)h([A)o(G97b)o(].)p eop %%Page: 3 3 3 2 bop 183 194 a Fn(2)56 b(The)18 b(Spi)h(Calculus)f(\(Informal)f (Summary\))183 289 y Fs(W)m(e)12 b(assume)g(an)g(in\014nite)h(set)g(of) g Fj(names)j Fs(and)d(an)f(in\014nite)g(set)i(of)e Fj(variables)p Fs(.)g(W)m(e)g(let)h Fm(m)p Fs(,)f Fm(n)p Fs(,)183 339 y Fm(p)p Fs(,)h Fm(q)q Fs(,)g(and)h Fm(r)h Fs(range)f(o)o(v)o(er)g (names,)e(and)i(let)g Fm(w)q Fs(,)f Fm(x)p Fs(,)g Fm(y)q Fs(,)i(and)e Fm(z)j Fs(range)e(o)o(v)o(er)g(v)n(ariables.)245 388 y(The)g(set)h(of)e Fj(terms)k Fs(is)d(de\014ned)h(b)o(y)e(the)i (gramma)o(r:)183 467 y Fm(L;)7 b(M)r(;)g(N)16 b Fs(::=)515 b(terms)259 517 y Fm(n)703 b Fs(name)259 566 y(\()p Fm(M)r(;)7 b(N)e Fs(\))597 b(pair)259 616 y(0)707 b(zero)259 666 y Fj(suc)r Fs(\()p Fm(M)5 b Fs(\))591 b(successor)259 716 y Fi(f)p Fm(M)5 b Fi(g)346 722 y Fh(N)987 716 y Fs(shared-k)o(ey)15 b(encryption)259 766 y Fm(x)704 b Fs(v)n(ariable)183 844 y(In)11 b(the)h(standard)g(pi)e(calculus,)i(names)e(are)i(the)g (only)e(terms.)h(W)m(e)g(ha)o(v)o(e)g(added)h(constructs)183 894 y(for)g(pairing)g(and)h(n)o(um)o(b)q(ers,)g(\()p Fm(M)r(;)7 b(N)e Fs(\),)12 b(0,)h(and)f Fj(suc)s Fs(\()p Fm(M)5 b Fs(\),)13 b(so)g(as)g(to)g(p)q(ermit)f(a)h(direct)h(treat-)183 944 y(men)o(t)f(of)h(proto)q(cols)h(that)g(use)g(these)h(constructs.)h (Moreo)o(v)o(er,)d(w)o(e)h(distinguish)f(v)n(ariables)183 993 y(from)g(names;)g(this)i(distinction)f(simpli\014es)f(the)i (treatmen)o(t)f(of)g(some)g(equiv)n(alences.)h(W)m(e)183 1043 y(ha)o(v)o(e)d(also)h(added)g(a)f(construct)j(for)d(encryption)i (\(a)o(v)o(oiding)d(the)i(complexit)o(y)e(of)h(p)q(ossible)183 1093 y(enco)q(dings)k(within)f(the)h(pi)f(calculus\).)h(In)o(tuitiv)o (ely)m(,)d Fi(f)p Fm(M)5 b Fi(g)1120 1099 y Fh(N)1168 1093 y Fs(represen)o(ts)19 b(the)e(ciphertext)183 1143 y(obtained)e(b)o(y)g(encrypting)g(the)h(term)f Fm(M)20 b Fs(under)c(the)g(k)o(ey)f Fm(N)20 b Fs(using)15 b(a)g(shared-k)o(ey)h (cryp-)183 1193 y(tosystem)d(suc)o(h)i(as)f(DES)e([DES77)o(].)245 1243 y(The)i(set)h(of)e Fj(pr)n(o)n(c)n(esses)k Fs(is)d(de\014ned)h(b)o (y)f(the)g(grammar:)183 1321 y Fm(P)q(;)7 b(Q;)g(R)j Fs(::=)531 b(pro)q(cesses)p 259 1339 45 2 v 259 1373 a Fm(M)5 b Fi(h)p Fm(N)g Fi(i)p Fm(:P)574 b Fs(output)259 1422 y Fm(M)5 b Fs(\()p Fm(x)p Fs(\))p Fm(:P)588 b Fs(input)259 1472 y Fm(P)17 b Fi(j)11 b Fm(Q)628 b Fs(comp)q(osition)259 1522 y(\()p Fm(\027)s(n)p Fs(\))p Fm(P)620 b Fs(restriction)259 1572 y(!)p Fm(P)689 b Fs(replication)259 1622 y([)p Fm(M)13 b Fj(is)g Fm(N)5 b Fs(])j Fm(P)535 b Fs(matc)o(h)259 1671 y Fk(0)704 b Fs(nil)259 1721 y Fj(let)17 b Fs(\()p Fm(x;)7 b(y)q Fs(\))12 b(=)g Fm(M)18 b Fj(in)f Fm(P)377 b Fs(pair)13 b(splitting)259 1771 y Fj(c)n(ase)18 b Fm(M)i Fj(of)j Fs(0)12 b(:)f Fm(P)19 b Fj(suc)s Fs(\()p Fm(x)p Fs(\))11 b(:)g Fm(Q)233 b Fs(in)o(teger)14 b(case)259 1821 y Fj(c)n(ase)j Fm(L)d Fj(of)23 b Fi(f)p Fm(x)p Fi(g)515 1827 y Fh(N)559 1821 y Fj(in)17 b Fm(P)348 b Fs(shared-k)o(ey)15 b(decryption)183 1899 y(In)f Fm(M)5 b Fs(\()p Fm(x)p Fs(\))p Fm(:P)h Fs(,)12 b(the)j(v)n(ariable)e Fm(x)h Fs(is)g(b)q(ound)g(in)g Fm(P)6 b Fs(.)13 b(In)h(\()p Fm(\027)s(n)p Fs(\))p Fm(P)6 b Fs(,)13 b(the)i(name)e Fm(n)h Fs(is)g(b)q(ound)g(in)g Fm(P)6 b Fs(.)183 1949 y(In)14 b Fj(let)j Fs(\()p Fm(x;)7 b(y)q Fs(\))12 b(=)g Fm(M)18 b Fj(in)f Fm(P)6 b Fs(,)13 b(the)i(v)n(ariables)e Fm(x)g Fs(and)h Fm(y)i Fs(are)e(b)q(ound)g(in)g Fm(P)6 b Fs(.)12 b(In)i Fj(c)n(ase)19 b Fm(M)g Fj(of)24 b Fs(0)11 b(:)183 1999 y Fm(P)k Fj(suc)s Fs(\()p Fm(x)p Fs(\))c(:)g Fm(Q)p Fs(,)f(the)g(v)n(ariable)f Fm(x)h Fs(is)g(b)q(ound)g(in)f Fm(Q)p Fs(.)g(In)h Fj(c)n(ase)k Fm(L)c Fj(of)19 b Fi(f)p Fm(x)p Fi(g)1237 2005 y Fh(N)1277 1999 y Fj(in)14 b Fm(P)6 b Fs(,)i(the)j(v)n(ariable)e Fm(x)183 2049 y Fs(is)g(b)q(ound)h(in)f Fm(P)d Fs(.)i(W)m(e)h(write)h Fm(P)c Fs([)p Fm(M)r(=x)p Fs(])i(for)h(the)h(outcome)f(of)g(replacing)g(eac)o(h)h(free)h(o)q (ccurrence)183 2099 y(of)16 b Fm(x)g Fs(in)h(pro)q(cess)h Fm(P)k Fs(with)17 b(the)g(term)f Fm(M)5 b Fs(,)16 b(and)h(iden)o(tify)f (pro)q(cesses)j(up)e(to)g(renaming)e(of)183 2148 y(b)q(ound)c(v)n (ariables)f(and)h(names.)f(W)m(e)h(adopt)g(the)h(abbreviations)1198 2117 y Fg(Q)1238 2161 y Fh(i)p Fl(2)p Fr(1)p Fh(::k)1335 2148 y Fm(P)1362 2154 y Fh(i)1387 2148 y Fs(for)f(the)h Fm(k)q Fs(-w)o(a)o(y)183 2204 y(parallel)f(comp)q(osition)f Fm(P)586 2210 y Fr(1)616 2204 y Fi(j)h(\001)c(\001)g(\001)j(j)h Fm(P)749 2210 y Fh(k)769 2204 y Fs(,)g(and)p 871 2171 V 12 w Fm(M)5 b Fi(h)p Fm(N)g Fi(i)12 b Fs(for)p 1060 2171 V 12 w Fm(M)5 b Fi(h)p Fm(N)g Fi(i)p Fm(:)p Fk(0)11 b Fs(and)h Fm(M)5 b Fs(\()p Fm(x)p Fs(\))12 b(for)g Fm(M)5 b Fs(\()p Fm(x)p Fs(\))p Fm(:)p Fk(0)p Fs(.)183 2254 y(W)m(e)13 b(also)h(express)h(the)g Fm(k)q Fs(-fold)e(restriction)i(\() p Fm(\027)s(p)933 2260 y Fr(1)951 2254 y Fs(\))7 b Fi(\001)g(\001)g (\001)e Fs(\()p Fm(\027)s(p)1090 2260 y Fh(k)1110 2254 y Fs(\))p Fm(P)19 b Fs(b)o(y)14 b(\()p Fm(\027)s(p)1291 2260 y Fh(i)1313 2239 y(i)p Fl(2)p Fr(1)p Fh(::k)1404 2254 y Fs(\))p Fm(P)20 b Fs(or,)13 b(when)183 2303 y Fm(~)-21 b(p)11 b Fs(=)h Fm(p)280 2309 y Fr(1)298 2303 y Fm(;)7 b(:)g(:)g(:)e(;)i(p)412 2309 y Fh(k)432 2303 y Fs(,)13 b(b)o(y)h(\()p Fm(\027)s(~)-21 b(p)o Fs(\))p Fm(P)6 b Fs(.)13 b(In)o(tuitiv)o(ely)m(,)f(pro)q(cesses)k(ha)o(v)o(e)e (the)h(follo)o(wing)c(meanings:)209 2382 y Fk({)20 b Fs(An)14 b Fj(output)i(pr)n(o)n(c)n(ess)p 594 2359 37 2 v 17 w Fm(m)p Fi(h)p Fm(N)5 b Fi(i)p Fm(:P)19 b Fs(is)14 b(ready)g(to)g(output)g Fm(N)19 b Fs(on)14 b Fm(m)p Fs(,)g(and)g(then)g (to)g(b)q(eha)o(v)o(e)253 2432 y(as)g Fm(P)6 b Fs(.)12 b(The)h(output)h(happ)q(ens)g(only)e(when)i(there)h(is)e(a)g(pro)q (cess)i(ready)e(to)g(input)g(from)p eop %%Page: 4 4 4 3 bop 411 194 a Fm(m)p Fs(.)15 b(An)f Fj(input)i(pr)n(o)n(c)n(ess)i Fm(m)p Fs(\()p Fm(x)p Fs(\))p Fm(:Q)c Fs(is)h(ready)g(to)g(input)f (from)f Fm(m)p Fs(,)h(and)h(then)g(to)g(b)q(eha)o(v)o(e)411 244 y(as)f Fm(Q)p Fs([)p Fm(N)q(=x)p Fs(],)e(where)j Fm(N)k Fs(is)14 b(the)g(input)g(receiv)o(ed.)411 295 y(The)h(general)g(forms)p 757 262 45 2 v 14 w Fm(M)5 b Fi(h)p Fm(N)g Fi(i)p Fm(:P)20 b Fs(and)14 b Fm(M)5 b Fs(\()p Fm(x)p Fs(\))p Fm(:Q)14 b Fs(of)h(output)g(and)f(input)h (allo)o(w)e(for)i(the)411 345 y(c)o(hannel)f(to)g(b)q(e)h(an)f (arbitrary)g(term)f Fm(M)5 b Fs(;)13 b(the)i(only)e(useful)i(cases)g (are)f(for)g Fm(M)19 b Fs(to)14 b(b)q(e)h(a)411 395 y(name,)d(or)i(a)g (v)n(ariable)e(that)i(gets)h(instan)o(tiated)f(to)f(a)h(name.)366 446 y Fk({)21 b Fs(A)14 b Fj(c)n(omp)n(osition)j Fm(P)g Fi(j)11 b Fm(Q)j Fs(b)q(eha)o(v)o(es)h(as)f Fm(P)19 b Fs(and)14 b Fm(Q)f Fs(running)h(in)f(parallel.)366 497 y Fk({)21 b Fs(A)16 b Fj(r)n(estriction)h Fs(\()p Fm(\027)s(n)p Fs(\))p Fm(P)k Fs(is)15 b(a)h(pro)q(cess)h(that)f(mak)o(es)e(a)i(new,)f (priv)n(ate)h(name)e Fm(n)p Fs(,)h(whic)o(h)411 547 y(ma)o(y)d(o)q (ccur)j(in)e Fm(P)6 b Fs(,)13 b(and)h(then)g(b)q(eha)o(v)o(es)h(as)f Fm(P)6 b Fs(.)366 598 y Fk({)21 b Fs(A)14 b Fj(r)n(eplic)n(ation)i Fs(!)p Fm(P)j Fs(b)q(eha)o(v)o(es)c(as)f(in\014nitely)f(man)o(y)f (copies)i(of)g Fm(P)19 b Fs(running)13 b(in)h(parallel.)366 650 y Fk({)21 b Fs(A)c Fj(match)k Fs([)p Fm(M)16 b Fj(is)f Fm(N)5 b Fs(])11 b Fm(P)22 b Fs(b)q(eha)o(v)o(es)c(as)g Fm(P)k Fs(pro)o(vided)c(that)f Fm(M)22 b Fs(and)17 b Fm(N)22 b Fs(are)c(the)g(same)411 700 y(term;)13 b(otherwise)i(it)e(is) h(stuc)o(k,)g(that)g(is,)f(it)h(do)q(es)g(nothing.)366 751 y Fk({)21 b Fs(The)14 b Fj(nil)k Fs(pro)q(cess)e Fk(0)e Fs(do)q(es)g(nothing.)366 802 y Fk({)21 b Fs(A)13 b Fj(p)n(air)h(splitting)i Fs(pro)q(cess)f Fj(let)h Fs(\()p Fm(x;)7 b(y)q Fs(\))12 b(=)g Fm(M)18 b Fj(in)e Fm(P)j Fs(b)q(eha)o(v)o(es)14 b(as)f Fm(P)6 b Fs([)p Fm(N)q(=x)p Fs(][)p Fm(L=y)q Fs(])11 b(if)i Fm(M)k Fs(is)411 852 y(a)d(pair)f(\()p Fm(N)r(;)7 b(L)p Fs(\),)14 b(and)g(it)f(is)h(stuc)o (k)h(if)e Fm(M)18 b Fs(is)c(not)g(a)f(pair.)366 904 y Fk({)21 b Fs(An)14 b Fj(inte)n(ger)g(c)n(ase)j Fs(pro)q(cess)e Fj(c)n(ase)k Fm(M)g Fj(of)24 b Fs(0)11 b(:)g Fm(P)19 b Fj(suc)s Fs(\()p Fm(x)p Fs(\))12 b(:)f Fm(Q)i Fs(b)q(eha)o(v)o(es)i (as)e Fm(P)19 b Fs(if)13 b Fm(M)19 b Fs(is)13 b(0,)411 953 y(as)h Fm(Q)p Fs([)p Fm(N)q(=x)p Fs(])f(if)g Fm(M)18 b Fs(is)c Fj(suc)s Fs(\()p Fm(N)5 b Fs(\))14 b(for)f(some)g Fm(N)5 b Fs(,)13 b(and)h(otherwise)h(is)f(stuc)o(k.)366 1005 y Fk({)21 b Fs(A)f Fj(de)n(cryption)j Fs(pro)q(cess)f Fj(c)n(ase)h Fm(L)d Fj(of)28 b Fi(f)p Fm(x)p Fi(g)1096 1011 y Fh(N)1146 1005 y Fj(in)23 b Fm(P)j Fs(attempts)19 b(to)h(decrypt)h Fm(L)f Fs(with)411 1055 y(the)c(k)o(ey)f Fm(N)5 b Fs(.)15 b(If)g Fm(L)g Fs(has)h(the)g(form)d Fi(f)p Fm(M)5 b Fi(g)1046 1061 y Fh(N)1077 1055 y Fs(,)15 b(then)h(the)g(pro)q(cess)h(b)q(eha)o(v)o(es)f(as)f Fm(P)6 b Fs([)p Fm(M)r(=x)p Fs(].)411 1105 y(Otherwise)15 b(the)g(pro)q(cess)h (is)d(stuc)o(k.)340 1192 y(F)m(or)h(example,)e(\()p Fm(\027)s(K)s Fs(\))p 683 1169 37 2 v Fm(m)p Fi(hf)p Fs(0)p Fi(g)798 1198 y Fh(K)830 1192 y Fi(i)i Fs(is)g(a)g(pro)q(cess)i(that)e(creates)i (a)d(name)g Fm(K)k Fs(and)d(then)h(sends)340 1242 y(the)f(result)h(of)e (encrypting)h(the)g(n)o(umeral)e(0)h(with)g Fm(K)k Fs(on)c(a)g(c)o (hannel)h Fm(m)p Fs(.)f(Here)i(w)o(e)e(use)i(the)340 1292 y(letter)j Fm(K)i Fs(for)d(a)f(name)g(b)q(ecause)i(the)g(name)d (pla)o(ys)h(the)i(role)f(of)f(a)g(k)o(ey)m(.)g(Since)i Fm(m)f Fs(is)f(not)340 1342 y(b)q(ound,)f(an)o(y)o(one)f(ma)o(y)e (receiv)o(e)k Fi(f)p Fs(0)p Fi(g)911 1348 y Fh(K)942 1342 y Fs(;)e(ho)o(w)o(ev)o(er,)h(since)g Fm(K)j Fs(is)c(b)q(ound,)h (this)f(term)g(cannot)340 1392 y(b)q(e)h(successfully)g(decrypted.)g (In)f(order)h(to)f(illustrate)f(the)i(use)f(of)g(decryption,)g(w)o(e)g (add)g(a)340 1441 y(pro)q(cess)i(that)e(has)g(the)h(necessary)g(k)o (ey:)628 1536 y(\()p Fm(\027)s(K)s Fs(\)\()p 738 1513 V Fm(m)p Fi(hf)p Fs(0)p Fi(g)853 1542 y Fh(K)885 1536 y Fi(i)c(j)g Fm(m)p Fs(\()p Fm(y)q Fs(\))p Fm(:)p Fj(c)n(ase)19 b Fm(y)c Fj(of)23 b Fi(f)p Fm(x)p Fi(g)1287 1542 y Fh(K)1332 1536 y Fj(in)p 1385 1513 V 17 w Fm(m)q Fi(h)p Fm(x)p Fi(i)p Fs(\))340 1631 y(The)13 b(new)f(pro)q(cess)h(\(to)f(the)h(righ)o (t)e(of)g Fi(j)p Fs(\))h(tries)g(to)g(decrypt)h(the)f(message)g Fm(y)h Fs(that)f(it)g(receiv)o(es)340 1681 y(on)i Fm(m)g Fs(using)g Fm(K)s Fs(,)g(and)f(sends)i(the)g(result)g Fm(x)e Fs(on)h Fm(m)p Fs(.)403 1732 y(W)m(e)e(write)h Fj(fn)s Fs(\()p Fm(M)5 b Fs(\))13 b(and)g Fj(fn)s Fs(\()p Fm(P)6 b Fs(\))13 b(for)f(the)i(sets)g(of)e(names)g(free)i(in)e(term)g Fm(M)18 b Fs(and)12 b(pro)q(cess)340 1782 y Fm(P)23 b Fs(resp)q(ectiv)o(ely)m(,)17 b(and)g(write)g Fj(fv)t Fs(\()p Fm(M)5 b Fs(\))17 b(and)g Fj(fv)t Fs(\()p Fm(P)6 b Fs(\))17 b(for)f(the)i(sets)g(of)e(v)n(ariables)g(free)i(in)f Fm(M)340 1832 y Fs(and)e Fm(P)20 b Fs(resp)q(ectiv)o(ely)m(.)c(A)f (term)f(or)h(pro)q(cess)i(is)d Fj(close)n(d)20 b Fs(if)14 b(it)g(has)h(no)g(free)h(v)n(ariables;)d Fj(Pr)n(o)n(c)340 1881 y Fs(is)h(the)h(set)f(of)g(closed)g(pro)q(cesses.)403 1933 y(A)f(con)o(text)h Fi(C)h Fs(is)f(a)f(pro)q(cess)i(with)e(a)g (single)f(hole;)h Fi(C)r Fs([)p Fm(P)6 b Fs(])12 b(is)h(the)h(outcome)e (of)h(\014lling)f(the)340 1983 y(hole)h(with)g Fm(P)6 b Fs(.)12 b(A)i(congruence)h(is)e(an)g(equiv)n(alence)g(relation)g Fi(R)g Fs(suc)o(h)h(that)g(if)e Fm(P)g Fi(R)7 b Fm(Q)14 b Fs(then)340 2032 y Fi(C)r Fs([)p Fm(P)6 b Fs(])h Fi(R)g(C)r Fs([)p Fm(Q)p Fs(])j(for)h(an)o(y)g(con)o(text)i Fi(C)r Fs(.)e(One)i(can)f(restrict)h(atten)o(tion)e(to)h(closed)g(pro)q (cesses)i(and)340 2082 y(con)o(texts,)h(but)f(the)g(claims)f(of)g(this) h(pap)q(er)g(hold)g(indep)q(enden)o(tly)g(of)g(this)f(restriction.)340 2225 y Fn(3)56 b(Tw)n(o)20 b(Op)r(erational)e(Seman)n(tics)340 2332 y Fs(The)j(reaction)f(relation)f(is)h(a)g(concise)h(accoun)o(t)f (of)f(computation)g(in)g(the)i(pi)e(calculus)340 2382 y(in)o(tro)q(duced)14 b(b)o(y)f(Milner)f([Mil92)n(],)g(with)h(ideas)g (from)e(Berry)k(and)d(Boudol)g([BB92].)g(In)h(this)340 2432 y(section)i(w)o(e)f(adapt)g(the)g(reaction)g(relation)g(to)g(the)g (spi)g(calculus.)p eop %%Page: 5 5 5 4 bop 245 194 a Fs(The)19 b(de\014nition)f(of)g(reaction)h(is)g (rather)h(elegan)o(t,)e(but)h(not)f(con)o(v)o(enien)o(t)h(for)g(pro)q (ofs)183 244 y(\(b)q(ecause)g(it)e(relies)h(on)f(an)g(auxiliary)e (notion)i(of)f(structural)j(equiv)n(alence\).)e(Therefore,)183 293 y(w)o(e)12 b(pro)o(vide)f(an)h(alternativ)o(e,)f(direct)i(c)o (haracterisation)f(of)g(reaction.)f(W)m(e)h(ac)o(hiev)o(e)g(this)g(b)o (y)183 343 y(de\014ning)h(a)h(commitm)o(en)o(t)d(relation,)i(in)g(the)i (st)o(yle)f(of)f(Milner)g([Mil95b)n(].)183 470 y Fk(The)i(Reaction)f (Relation)183 555 y Fs(The)e(de\014nition)f(of)h(reaction)g(has)g(sev)o (eral)g(phases.)h(First)f(w)o(e)g(de\014ne)h(a)e Fj(r)n(e)n(duction)i (r)n(elation)183 605 y Fm(>)18 b Fs(on)g Fj(Pr)n(o)n(c)r Fs(.)g(W)m(e)f(require)i(that)f(!)p Fm(P)24 b(>)19 b Fs(\()p Fm(P)24 b Fi(j)18 b Fs(!)p Fm(P)5 b Fs(\),)18 b(that)g([)p Fm(M)e Fj(is)f Fm(M)5 b Fs(])12 b Fm(P)24 b(>)19 b(P)6 b Fs(,)17 b(and)g(that)183 655 y Fj(c)n(ase)f Fi(f)p Fm(M)5 b Fi(g)360 661 y Fh(N)405 655 y Fj(of)22 b Fi(f)p Fm(x)p Fi(g)527 661 y Fh(N)571 655 y Fj(in)16 b Fm(P)h(>)12 b(P)6 b Fs([)p Fm(M)r(=x)p Fs(];)12 b(w)o(e)h(omit)f (similar)f(conditions)i(for)g Fj(let)k Fs(and)c(for)183 705 y(the)f Fj(c)n(ase)k Fs(construct)d(for)f(n)o(umerals.)e(Then)j(w)o (e)f(de\014ne)h(a)f Fj(structur)n(al)g(e)n(quivalenc)n(e)h(r)n(elation) 183 754 y Fi(\021)k Fs(on)h Fj(Pr)n(o)n(c)r Fs(.)f(It)g(is)h(the)g (least)g(equiv)n(alence)f(relation)g(including)g Fm(>)h Fs(suc)o(h)g(that)g Fm(P)23 b Fi(\021)18 b Fm(P)1613 739 y Fl(0)183 804 y Fs(implies)12 b Fm(P)17 b Fi(j)11 b Fm(Q)g Fi(\021)h Fm(P)512 789 y Fl(0)534 804 y Fi(j)f Fm(Q)j Fs(and)g(\()p Fm(\027)s(m)p Fs(\))p Fm(P)j Fi(\021)11 b Fs(\()p Fm(\027)s(m)p Fs(\))p Fm(P)989 789 y Fl(0)1000 804 y Fs(,)j(and)f(suc)o(h)i(that)405 889 y Fm(P)i Fi(j)11 b Fk(0)g Fi(\021)h Fm(P)190 b(P)17 b Fi(j)11 b Fm(Q)g Fi(\021)h Fm(Q)f Fi(j)g Fm(P)61 b(P)17 b Fi(j)11 b Fs(\()p Fm(Q)h Fi(j)f Fm(R)p Fs(\))g Fi(\021)h Fs(\()p Fm(P)17 b Fi(j)11 b Fm(Q)p Fs(\))h Fi(j)f Fm(R)262 938 y Fs(\()p Fm(\027)s(m)p Fs(\)\()p Fm(\027)s(n)p Fs(\))p Fm(P)16 b Fi(\021)c Fs(\()p Fm(\027)s(n)p Fs(\)\()p Fm(\027)s(m)p Fs(\))p Fm(P)82 b Fs(\()p Fm(\027)s(n)p Fs(\))p Fk(0)10 b Fi(\021)i Fk(0)77 b Fs(\(\()p Fm(\027)s(n)p Fs(\))p Fm(P)6 b Fs(\))11 b Fi(j)g Fm(Q)g Fi(\021)h Fs(\()p Fm(\027)s(n)p Fs(\)\()p Fm(P)17 b Fi(j)11 b Fm(Q)p Fs(\))183 1023 y(where,)20 b(in)g(the)h(last)e(equation,)h Fm(n)26 b(=)-26 b Fi(2)22 b Fj(fn)s Fs(\()p Fm(Q)p Fs(\).)e(In)o(tuitiv)o(ely)m(,)e(this)i(equiv) n(alence)g(relation)183 1073 y(allo)o(ws)8 b(pro)q(cesses)k(to)e(b)q(e) g(rearranged)g(so)g(that)g(reaction)g(is)f(p)q(ossible.)h(Finally)m(,)d (the)j Fj(r)n(e)n(action)183 1123 y(r)n(elation)j Fi(!)c Fs(is)i(the)g(least)f(relation)g(on)g Fj(Pr)n(o)n(c)i Fs(suc)o(h)g(that)e Fm(P)17 b Fi(!)11 b Fm(P)1189 1108 y Fl(0)1210 1123 y Fs(implies)e Fm(P)17 b Fi(j)11 b Fm(Q)g Fi(!)g Fm(P)1545 1108 y Fl(0)1568 1123 y Fi(j)g Fm(Q)183 1173 y Fs(and)j(\()p Fm(\027)s(m)p Fs(\))p Fm(P)19 b Fi(!)13 b Fs(\()p Fm(\027)s(m)p Fs(\))p Fm(P)582 1158 y Fl(0)593 1173 y Fs(,)h(suc)o(h)i(that)f Fm(P)k Fi(\021)14 b Fm(P)930 1158 y Fl(0)954 1173 y Fi(!)f Fm(Q)1042 1158 y Fl(0)1067 1173 y Fi(\021)g Fm(Q)i Fs(implies)e Fm(P)19 b Fi(!)13 b Fm(Q)p Fs(,)h(and)h(suc)o(h)183 1222 y(that)p 273 1200 37 2 v 14 w Fm(m)p Fi(h)p Fm(N)5 b Fi(i)p Fm(:P)17 b Fi(j)11 b Fm(m)p Fs(\()p Fm(x)p Fs(\))p Fm(:Q)g Fi(!)g Fm(P)17 b Fi(j)11 b Fm(Q)p Fs([)p Fm(N)q(=x)p Fs(].)245 1273 y(\(The)16 b(reduction)h(relation,)d Fm(>)p Fs(,)i(is)f(not)h (found)f(in)h(previous)g(accoun)o(ts)g(of)f(the)i(pi)e(cal-)183 1323 y(culus.)g(W)m(e)g(in)o(tro)q(duced)h(it)f(in)g(the)g (de\014nition)g(of)g(structural)h(equiv)n(alence)g(b)q(ecause)h(it)e (is)183 1372 y(useful)f(also)f(in)g(the)i(de\014nition)e(of)h(commitm)n (en)o(t,)d(giv)o(en)j(next.\))183 1499 y Fk(The)h(Commitmen)o(t)e (Relation)183 1584 y Fs(In)g(order)i(to)f(de\014ne)g(commitm)o(en)o(t,) d(w)o(e)j(need)h(some)d(new)j(syn)o(tactic)f(forms.)e(An)i Fj(abstr)n(ac-)183 1634 y(tion)k Fs(is)c(an)h(expression)h(of)e(the)h (form)e(\()p Fm(x)p Fs(\))p Fm(P)6 b Fs(,)14 b(where)i Fm(x)f Fs(is)f(a)h(b)q(ound)g(v)n(ariable)e(and)i Fm(P)20 b Fs(is)15 b(a)183 1684 y(pro)q(cess.)g(In)o(tuitiv)o(ely)m(,)d(\()p Fm(x)p Fs(\))p Fm(P)19 b Fs(is)14 b(lik)o(e)f(the)i(pro)q(cess)g Fm(p)p Fs(\()p Fm(x)p Fs(\))p Fm(:P)k Fs(min)o(us)12 b(the)j(name)e Fm(p)p Fs(.)g(When)h Fm(F)183 1734 y Fs(is)i(the)h (abstraction)g(\()p Fm(x)p Fs(\))p Fm(P)22 b Fs(and)16 b Fm(M)21 b Fs(is)16 b(a)g(term,)g(w)o(e)h(write)f Fm(F)6 b Fs(\()p Fm(M)f Fs(\))16 b(for)g Fm(P)6 b Fs([)p Fm(M)r(=x)p Fs(].)15 b(A)h Fj(c)n(on-)183 1784 y(cr)n(etion)j Fs(is)e(an)g (expression)h(of)e(the)i(form)d(\()p Fm(\027)s(m)938 1790 y Fr(1)956 1784 y Fm(;)7 b(:)g(:)g(:)e(;)i(m)1085 1790 y Fh(k)1105 1784 y Fs(\))p Fi(h)p Fm(M)e Fi(i)p Fm(P)h Fs(,)16 b(where)j Fm(M)i Fs(is)c(a)g(term,)183 1833 y Fm(P)j Fs(is)c(a)f(pro)q(cess,)i Fm(k)e Fi(\025)f Fs(0,)h(and)g(the)h(names)f Fm(m)919 1839 y Fr(1)938 1833 y Fs(,)g(.)6 b(.)h(.)f(,)15 b Fm(m)1083 1839 y Fh(k)1119 1833 y Fs(are)h(b)q(ound)g(in)f Fm(M)20 b Fs(and)15 b Fm(P)6 b Fs(.)15 b(In-)183 1883 y(tuitiv)o(ely)m(,)f(\()p Fm(\027)s(m)434 1889 y Fr(1)452 1883 y Fm(;)7 b(:)g(:)g(:)e(;)i(m)581 1889 y Fh(k)601 1883 y Fs(\))p Fi(h)p Fm(M)e Fi(i)p Fm(P)22 b Fs(is)15 b(lik)o(e)h(the)g(pro)q(cess)i(\()p Fm(\027)s(m)1161 1889 y Fr(1)1179 1883 y Fs(\))7 b Fm(:)g(:)g(:)f Fs(\()p Fm(\027)s(m)1334 1889 y Fh(k)1354 1883 y Fs(\))p 1370 1860 21 2 v Fm(p)p Fi(h)p Fm(M)f Fi(i)p Fm(P)21 b Fs(min)o(us)183 1933 y(the)c(name)e Fm(p)p Fs(,)h(pro)o(vided)g Fm(p)h Fs(is)f(not)g(one)h(of)f Fm(m)915 1939 y Fr(1)934 1933 y Fs(,)g(.)6 b(.)h(.)f(,)16 b Fm(m)1081 1939 y Fh(k)1102 1933 y Fs(.)g(W)m(e)g(often)h(write)f(concretions)183 1983 y(as)e(\()p Fm(\027)7 b(~)-25 b(m)p Fs(\))p Fi(h)p Fm(M)5 b Fi(i)p Fm(P)h Fs(,)13 b(where)20 b Fm(~)-26 b(m)12 b Fs(=)h Fm(m)710 1989 y Fr(1)729 1983 y Fm(;)7 b(:)g(:)g(:)e(;)i(m)858 1989 y Fh(k)878 1983 y Fs(,)13 b(or)i(simply)d(\()p Fm(\027)s Fs(\))p Fi(h)p Fm(M)5 b Fi(i)p Fm(P)19 b Fs(if)13 b Fm(k)g Fs(=)f(0.)h(Finally)m(,)f(an)183 2033 y Fj(agent)18 b Fs(is)c(an)g(abstraction,)g(a)g(pro)q(cess,)h(or)f (a)g(concretion.)h(W)m(e)f(use)h(the)f(meta)o(v)n(ariables)e Fm(A)183 2083 y Fs(and)h Fm(B)j Fs(to)e(stand)g(for)f(arbitrary)g(agen) o(ts,)h(and)f(let)h Fj(fv)t Fs(\()p Fm(A)p Fs(\))g(and)f Fj(fn)t Fs(\()p Fm(A)p Fs(\))h(b)q(e)g(the)g(sets)h(of)e(free)183 2132 y(v)n(ariables)g(and)h(free)g(names)f(of)h(an)f(agen)o(t)h Fm(A)p Fs(,)g(resp)q(ectiv)o(ely)m(.)245 2183 y(W)m(e)g(extend)h(the)f (restriction)h(and)f(comp)q(osition)e(op)q(erators)j(to)f(arbitrary)g (agen)o(ts,)f(as)183 2232 y(follo)o(ws.)k(F)m(or)i(an)g(abstraction)h (\()p Fm(x)p Fs(\))p Fm(P)6 b Fs(,)18 b(w)o(e)i(let)g(\()p Fm(\027)s(m)p Fs(\)\()p Fm(x)p Fs(\))p Fm(P)26 b Fs(=)21 b(\()p Fm(x)p Fs(\)\()p Fm(\027)s(m)p Fs(\))p Fm(P)k Fs(and)19 b(let)g Fm(R)i Fi(j)183 2282 y Fs(\()p Fm(x)p Fs(\))p Fm(P)c Fs(=)11 b(\()p Fm(x)p Fs(\)\()p Fm(R)h Fi(j)f Fm(P)6 b Fs(\),)11 b(assuming)f(that)i Fm(x)f Fi(62)g Fj(fv)5 b Fs(\()p Fm(R)p Fs(\).)11 b(F)m(or)h(a)f(concretion)i (\()p Fm(\027)r(~)-20 b(n)o Fs(\))p Fi(h)p Fm(M)5 b Fi(i)p Fm(Q)p Fs(,)11 b(w)o(e)h(let)183 2332 y(\()p Fm(\027)s(m)p Fs(\)\()p Fm(\027)r(~)-20 b(n)o Fs(\))p Fi(h)p Fm(M)5 b Fi(i)p Fm(Q)11 b Fs(=)h(\()p Fm(\027)s(m;)6 b(~)-20 b(n)o Fs(\))p Fi(h)p Fm(M)5 b Fi(i)p Fm(Q)11 b Fs(if)g Fm(m)h Fi(2)f Fj(fn)s Fs(\()p Fm(M)5 b Fs(\))11 b(and)g(=)h(\()p Fm(\027)r(~)-20 b(n)o Fs(\))p Fi(h)p Fm(M)5 b Fi(i)p Fs(\()p Fm(\027)s(m)p Fs(\))p Fm(Q)11 b Fs(otherwise,)183 2382 y(and)e(let)g Fm(R)j Fi(j)f Fs(\()p Fm(\027)r(~)-20 b(n)o Fs(\))p Fi(h)p Fm(M)5 b Fi(i)p Fm(Q)11 b Fs(=)h(\()p Fm(\027)r(~)-20 b(n)o Fs(\))p Fi(h)p Fm(M)5 b Fi(i)p Fs(\()p Fm(R)12 b Fi(j)f Fm(Q)p Fs(\),)e(in)g(all)f(cases)j(assuming)c (that)j Fm(m)i Fi(62)f(f)o Fm(~)-20 b(n)p Fi(g)9 b Fs(and)183 2432 y(that)k Fi(f)o Fm(~)-20 b(n)o Fi(g)7 b(\\)g Fj(fn)s Fs(\()p Fm(R)p Fs(\))12 b(=)g Fi(;)p Fs(.)g(W)m(e)g(de\014ne)i(the)f (dual)g(comp)q(osition)d Fm(A)i Fi(j)f Fm(R)i Fs(symmetrically)l(.)d (If)i Fm(F)p eop %%Page: 6 6 6 5 bop 340 194 a Fs(is)12 b(the)g(abstraction)g(\()p Fm(x)p Fs(\))p Fm(P)17 b Fs(and)12 b Fm(C)i Fs(is)d(the)i(concretion)f (\()p Fm(\027)r(~)-20 b(n)o Fs(\))p Fi(h)p Fm(M)5 b Fi(i)p Fm(Q)p Fs(,)12 b(and)f Fi(f)o Fm(~)-20 b(n)p Fi(g)5 b(\\)g Fj(fn)r Fs(\()p Fm(P)h Fs(\))11 b(=)h Fi(;)p Fs(,)340 244 y(w)o(e)j(de\014ne)f(the)h Fj(inter)n(actions)i Fm(F)6 b Fs(@)p Fm(C)16 b Fs(and)e Fm(C)s Fs(@)p Fm(F)19 b Fs(to)14 b(b)q(e)g(the)h(pro)q(cesses)h(giv)o(en)e(b)o(y:)516 323 y Fm(F)6 b Fs(@)p Fm(C)644 300 y Ff(\001)639 323 y Fs(=)26 b(\()p Fm(\027)r(~)-20 b(n)o Fs(\)\()p Fm(P)6 b Fs([)p Fm(M)r(=x)p Fs(])k Fi(j)h Fm(Q)p Fs(\))83 b Fm(C)s Fs(@)p Fm(F)1230 300 y Ff(\001)1225 323 y Fs(=)26 b(\()p Fm(\027)r(~)-20 b(n)o Fs(\)\()p Fm(Q)12 b Fi(j)f Fm(P)6 b Fs([)p Fm(M)r(=x)p Fs(]\))340 399 y(In)o(tuitiv)o(ely)m(,)14 b(these)j(pro)q(cesses)i(are)d(the)g(p)q(ossible)g(immedia)o(te)e (results)i(of)g(the)g(encoun)o(ter)340 449 y(of)f Fm(F)21 b Fs(and)16 b Fm(C)s Fs(.)e(Giv)o(en)h(a)h(common)c(name)j Fm(p)p Fs(,)g(w)o(e)g(ha)o(v)o(e)h(that)f Fm(F)21 b Fs(is)16 b(lik)o(e)f Fm(p)p Fs(\()p Fm(x)p Fs(\))p Fm(:P)20 b Fs(and)15 b Fm(C)j Fs(is)340 499 y(lik)o(e)11 b(\()p Fm(\027)r(~)-20 b(n)p Fs(\))p 495 476 21 2 v Fm(p)p Fi(h)p Fm(M)5 b Fi(i)p Fm(P)h Fs(,)k(so)i(an)g(in)o(teraction)f(of)g Fm(F)17 b Fs(and)12 b Fm(C)i Fs(is)e(a)f(pro)q(cess)j(obtained)d(when)h Fm(p)p Fs(\()p Fm(x)p Fs(\))p Fm(:P)340 548 y Fs(and)i(\()p Fm(\027)r(~)-20 b(n)o Fs(\))p 501 526 V Fm(p)p Fi(h)p Fm(M)5 b Fi(i)p Fm(P)h Fs(,)13 b(put)h(in)g(parallel,)e(comm)o(unicate) g(on)h Fm(p)p Fs(.)403 598 y(An)20 b Fj(action)k Fs(is)c(a)g(name)f Fm(m)i Fs(\(represen)o(ting)h(input\),)e(a)g(co-name)p 1488 575 37 2 v 19 w Fm(m)g Fs(\(represen)o(ting)340 648 y(output\),)11 b(or)f(the)i(distinguished)e Fj(silent)i(action)i Fm(\034)5 b Fs(.)10 b(The)h Fj(c)n(ommitment)g(r)n(elation)i Fs(is)e(written)340 703 y Fm(P)407 679 y Fh(\013)384 703 y Fi(\000)-6 b(!)11 b Fm(A)p Fs(,)f(where)i Fm(P)17 b Fs(is)11 b(a)f(closed)i(pro)q(cess,)g Fm(\013)f Fs(is)g(an)f(action,) g(and)h Fm(A)g Fs(is)g(a)g(closed)g(agen)o(t;)g(it)f(is)340 763 y(de\014ned)j(inductiv)o(ely)e(b)o(y)g(the)h(axioms)d Fm(m)p Fs(\()p Fm(x)p Fs(\))p Fm(:P)1120 740 y Fh(m)1101 763 y Fi(\000)-7 b(!)11 b Fs(\()p Fm(x)p Fs(\))p Fm(P)17 b Fs(and)p 1357 741 V 11 w Fm(m)q Fi(h)p Fm(M)5 b Fi(i)p Fm(:P)p 1545 722 30 2 v 1545 740 a Fh(m)1526 763 y Fi(\000)-6 b(!)11 b Fs(\()p Fm(\027)s Fs(\))p Fi(h)p Fm(M)5 b Fi(i)p Fm(P)g Fs(,)340 813 y(and)14 b(the)h(rules:)457 892 y Fm(P)519 868 y Fh(m)500 892 y Fi(\000)-6 b(!)11 b Fm(F)47 b(Q)p 716 851 V 716 868 a Fh(m)697 892 y Fi(\000)-6 b(!)11 b Fm(C)p 451 908 364 2 v 489 953 a(P)17 b Fi(j)11 b Fm(Q)624 929 y Fh(\034)600 953 y Fi(\000)-6 b(!)11 b Fm(F)6 b Fs(@)p Fm(C)903 892 y(P)p 966 851 30 2 v 966 868 a Fh(m)947 892 y Fi(\000)-7 b(!)11 b Fm(C)44 b(Q)1162 868 y Fh(m)1144 892 y Fi(\000)-7 b(!)11 b Fm(F)p 897 908 364 2 v 935 953 a(P)17 b Fi(j)11 b Fm(Q)1071 929 y Fh(\034)1047 953 y Fi(\000)-7 b(!)11 b Fm(C)s Fs(@)p Fm(F)1349 888 y(P)17 b(>)12 b(Q)41 b(Q)1578 864 y Fh(\013)1556 888 y Fi(\000)-7 b(!)11 b Fm(A)p 1343 904 328 2 v 1430 949 a(P)1497 925 y Fh(\013)1474 949 y Fi(\000)-6 b(!)11 b Fm(A)543 1060 y(P)609 1037 y Fh(\013)587 1060 y Fi(\000)-7 b(!)11 b Fm(A)p 470 1077 300 2 v 476 1122 a(P)16 b Fi(j)11 b Fm(Q)609 1098 y Fh(\013)587 1122 y Fi(\000)-7 b(!)11 b Fm(A)h Fi(j)f Fm(Q)925 1060 y(Q)992 1037 y Fh(\013)970 1060 y Fi(\000)-7 b(!)11 b Fm(A)p 853 1077 V 859 1122 a(P)16 b Fi(j)11 b Fm(Q)992 1098 y Fh(\013)970 1122 y Fi(\000)-7 b(!)11 b Fm(P)17 b Fi(j)11 b Fm(A)1241 1060 y(P)1308 1037 y Fh(\013)1285 1060 y Fi(\000)-7 b(!)11 b Fm(A)42 b(\013)16 b(=)-26 b Fi(2)11 b(f)p Fm(m;)p 1589 1038 37 2 v 7 w(m)q Fi(g)p 1235 1077 417 2 v 1275 1122 a Fs(\()p Fm(\027)s(m)p Fs(\))p Fm(P)1433 1098 y Fh(\013)1411 1122 y Fi(\000)-7 b(!)11 b Fs(\()p Fm(\027)s(m)p Fs(\))p Fm(A)403 1207 y Fs(The)17 b(commitm)o(en)o(t)d(relation)i(indexed)i(b)o(y)e Fm(\034)5 b Fs(,)1183 1183 y Fh(\034)1159 1207 y Fi(\000)-7 b(!)p Fs(,)16 b(is)h(a)f(binary)h(relation)f(on)h Fj(Pr)n(o)n(c)r Fs(.)340 1263 y(W)m(e)f(write)546 1239 y Fh(\034)522 1263 y Fi(\000)-7 b(!)589 1233 y Fl(\003)623 1263 y Fs(for)16 b(its)f(re\015exiv)o(e)i(and)f(transitiv)o(e)f(closure;)h(and)g(w)o(e)g (write)g Fm(P)1659 1239 y Fh(\034)1635 1263 y Fi(\000)-7 b(!\021)15 b Fm(Q)340 1312 y Fs(when)g(there)g(exists)g(a)e(pro)q(cess) j Fm(R)e Fs(suc)o(h)g(that)g Fm(P)1146 1289 y Fh(\034)1122 1312 y Fi(\000)-7 b(!)12 b Fm(R)h Fs(and)h Fm(R)d Fi(\021)h Fm(Q)p Fs(.)340 1386 y Fk(Prop)q(osition)5 b(1.)20 b Fm(P)d Fi(!)11 b Fm(Q)k Fj(if)f(and)i(only)f(if)f Fm(P)1113 1362 y Fh(\034)1088 1386 y Fi(\000)-6 b(!)o(\021)12 b Fm(Q)p Fj(.)340 1511 y Fn(4)56 b(T)-5 b(esting)19 b(Equiv)m(alence)340 1601 y Fs(As)c(explained)g(in)f(the)h(in)o(tro)q(duction,)f(w)o(e)g (rely)h(on)f(testing)h(equiv)n(alence)g(for)f(the)h(sp)q(eci\014-)340 1650 y(cation)c(of)g(securit)o(y)h(prop)q(erties.)g(This)g(section)g (giv)o(es)f(the)h(de\014nition)e(of)h(tests)i(and)e(testing)340 1700 y(equiv)n(alence,)j(and)g(some)f(basic)h(results)h(ab)q(out)f (them.)403 1750 y(A)g Fj(b)n(arb)j Fs(is)e(either)h(a)e(name)g Fm(m)h Fs(or)f(a)h(co-name)p 1151 1727 37 2 v 13 w Fm(m)q Fs(.)f(If)g Fm(P)20 b Fs(is)15 b(a)f(closed)h(pro)q(cess,)i(w)o(e)d(sa) o(y)340 1800 y(that)g Fm(P)k Fj(exhibits)c(b)n(arb)i Fm(\014)r Fs(,)d(and)g(write)h Fm(P)j Fi(#)11 b Fm(\014)r Fs(,)j(if)e Fm(P)19 b Fs(ma)o(y)11 b(comm)o(unicate)g(immedia)o(tely)g (on)340 1850 y Fm(\014)r Fs(.)k(Similarly)m(,)c(the)k Fj(c)n(onver)n(genc)n(e)k Fs(predicate)d Fm(P)i Fi(+)13 b Fm(\014)18 b Fs(means)c(that)h Fm(P)20 b Fs(ma)o(y)13 b(comm)o(unicate)340 1899 y(on)19 b Fm(\014)j Fs(after)d(some)g (reactions.)g(F)m(ormally)m(,)c(these)21 b(t)o(w)o(o)d(predicates)j (are)f(de\014ned)g(b)o(y)f(the)340 1949 y(axioms)12 b Fm(m)p Fs(\()p Fm(x)p Fs(\))p Fm(:P)17 b Fi(#)11 b Fm(m)k Fs(and)p 791 1926 V 13 w Fm(m)q Fi(h)p Fm(M)5 b Fi(i)p Fm(:P)16 b Fi(#)p 993 1926 V 12 w Fm(m)p Fs(,)d(and)h(b)o(y)g(the)g (rules:)607 2025 y Fm(P)j Fi(#)11 b Fm(\014)p 567 2041 181 2 v 573 2086 a(P)17 b Fi(j)11 b Fm(Q)g Fi(#)h Fm(\014)837 2025 y(P)17 b Fi(#)11 b Fm(\014)44 b(\014)19 b(=)-25 b Fi(2)11 b(f)p Fm(m;)p 1133 2002 37 2 v 7 w(m)p Fi(g)p 831 2041 365 2 v 916 2086 a Fs(\()p Fm(\027)s(m)p Fs(\))p Fm(P)17 b Fi(#)12 b Fm(\014)1284 2025 y(P)17 b Fi(\021)12 b Fm(Q)41 b(Q)12 b Fi(#)f Fm(\014)p 1278 2041 277 2 v 1366 2086 a(P)16 b Fi(#)c Fm(\014)803 2195 y(P)17 b Fi(#)11 b Fm(\014)p 795 2211 119 2 v 801 2256 a(P)16 b Fi(+)c Fm(\014)1002 2195 y(P)17 b Fi(!)11 b Fm(Q)82 b(Q)12 b Fi(+)g Fm(\014)p 996 2211 332 2 v 1108 2256 a(P)17 b Fi(+)12 b Fm(\014)340 2332 y Fs(A)j Fj(test)p Fs(,)g(\()p Fm(R;)7 b(\014)r Fs(\),)14 b(consists)i(of)f(a)f(closed)i(pro)q(cess)h Fm(R)e Fs(and)f(a)h(barb)g Fm(\014)r Fs(.)g(A)h(closed)f(pro)q(cess)i Fm(P)340 2382 y Fj(p)n(asses)i Fs(the)c(test)h(if)e(and)h(only)f(if)g (\()p Fm(P)19 b Fi(j)13 b Fm(R)p Fs(\))g Fi(+)g Fm(\014)r Fs(.)j(The)f(follo)o(wing)d(prop)q(osition)i(enables)i(us)340 2432 y(to)e(use)h(the)f(commitm)o(en)o(t)d(relation)j(in)f(pro)q(ofs)h (ab)q(out)g(tests:)p eop %%Page: 7 7 7 6 bop 183 202 a Fk(Prop)q(ositi)o(on)5 b(2.)21 b Fm(P)e Fi(#)14 b Fm(\014)19 b Fj(if)d(and)h(only)f(if)g Fm(P)941 177 y Fh(\014)918 202 y Fi(\000)-7 b(!)14 b Fm(A)i Fj(for)g(some)g (agent)h Fm(A)p Fj(.)f(Mor)n(e)n(over,)g Fm(P)183 252 y Fj(p)n(asses)f(a)g(test)f Fs(\()p Fm(R;)7 b(\014)r Fs(\))15 b Fj(if)g(and)g(only)h(if)663 349 y Fm(P)h Fi(j)11 b Fm(R)795 326 y Fh(\034)771 349 y Fi(\000)-7 b(!)838 319 y Fl(\003)866 349 y Fm(Q)15 b Fj(and)g Fm(Q)1060 324 y Fh(\014)1036 349 y Fi(\000)-6 b(!)8 b Fm(A)183 432 y Fj(for)14 b(some)h(agent)g Fm(A)g Fj(and)h(pr)n(o)n(c)n(ess)f Fm(Q)p Fj(.)245 513 y Fs(The)g(de\014nition)g(of)f(testing)i(induces)g (a)e(testing)i(preorder)g Fi(v)g Fs(and)e(a)h(testing)g(equiv)n(a-)183 563 y(lence)f Fi(')h Fs(on)e Fj(Pr)n(o)n(c)r Fs(:)344 646 y Fm(P)k Fi(v)12 b Fm(Q)495 622 y Ff(\001)490 646 y Fs(=)26 b(for)14 b(an)o(y)f(test)i(\()p Fm(R;)7 b(\014)r Fs(\),)14 b(if)f(\()p Fm(P)k Fi(j)11 b Fm(R)p Fs(\))g Fi(+)h Fm(\014)17 b Fs(then)d(\()p Fm(Q)e Fi(j)f Fm(R)p Fs(\))g Fi(+)h Fm(\014)344 715 y(P)17 b Fi(')12 b Fm(Q)495 691 y Ff(\001)490 715 y Fs(=)26 b Fm(P)17 b Fi(v)12 b Fm(Q)i Fs(and)f Fm(Q)f Fi(v)f Fm(P)245 797 y Fs(The)j(follo)o(wing)e (prop)q(osition)h(is)h(crucial)f(for)h(pro)q(ofs)g(of)f(testing)h (equiv)n(alence:)183 878 y Fk(Prop)q(ositi)o(on)5 b(3.)21 b Fj(T)m(esting)g(e)n(quivalenc)n(e)g(is)g(a)h(c)n(ongruenc)n(e.)g(F)m (urthermor)n(e,)e(structur)n(al)183 928 y(e)n(quivalenc)n(e)15 b(implies)f(testing)h(e)n(quivalenc)n(e.)245 1009 y Fs(W)m(e)d(ha)o(v)o (e)h(dev)o(elop)q(ed)h(a)f(n)o(um)o(b)q(er)f(of)g(auxiliary)f(lemmas)g (ab)q(out)h(testing)i(equiv)n(alence,)183 1059 y(for)f(use)i(in)f(our)g (v)o(eri\014cations.)g(As)g(a)g(sample,)f(w)o(e)h(sho)o(w)g(a)g(prop)q (osition)f(that)h(enables)h(us)183 1108 y(to)d(reduce)i(in\014nite)e (problems)f(\(with)i(replication\))f(to)g(\014nite)g(but)h(un)o(b)q (ounded)g(problems:)183 1189 y Fk(Prop)q(ositi)o(on)5 b(4.)21 b Fj(If)15 b Fs(\()p Fm(\027)s(~)-21 b(p)p Fs(\)\()p Fm(P)655 1195 y Fr(1)687 1189 y Fi(j)712 1158 y Fg(Q)751 1202 y Fh(i)p Fl(2)p Fr(1)p Fh(::n)851 1189 y Fm(P)878 1195 y Fr(2)896 1189 y Fs(\))14 b Fi(')g Fs(\()p Fm(\027)s(~)-21 b(p)o Fs(\)\()p Fm(Q)1097 1195 y Fr(1)1130 1189 y Fi(j)1155 1158 y Fg(Q)1194 1202 y Fh(i)p Fl(2)p Fr(1)p Fh(::n)1294 1189 y Fm(Q)1327 1195 y Fr(2)1345 1189 y Fs(\))17 b Fj(for)e(al)r(l)h Fm(n)d Fi(\025)h Fs(0)p Fj(,)183 1239 y(then)h Fs(\()p Fm(\027)s(~)-21 b(p)o Fs(\)\()p Fm(P)394 1245 y Fr(1)424 1239 y Fi(j)11 b Fs(!)p Fm(P)486 1245 y Fr(2)504 1239 y Fs(\))h Fi(')g Fs(\()p Fm(\027)s(~)-21 b(p)o Fs(\)\()p Fm(Q)701 1245 y Fr(1)731 1239 y Fi(j)11 b Fs(!)p Fm(Q)799 1245 y Fr(2)817 1239 y Fs(\))p Fj(.)245 1320 y Fs(T)m(esting)22 b(equiv)n(alence)g(b)q(ecomes)h(\014ner-grained)f(\(and)h(p)q(erhaps)g (ev)o(en)g(more)e(com-)183 1369 y(p)q(elling\))d(in)i(the)g(presence)i (of)d(a)g(construct)j([)p Fm(M)17 b Fj(is)g(not)g Fm(N)5 b Fs(])13 b Fm(P)25 b Fs(for)19 b(mismatc)o(h)10 b([BN95].)183 1419 y(Our)k(calculus)g(do)q(es)g(not)g(include)g(that)f(construct)j(b) q(ecause)f(w)o(e)f(ha)o(v)o(e)f(not)h(found)f(a)h(need)183 1469 y(for)9 b(it)h(in)g(writing)f(proto)q(cols.)h(The)g(same)f(is)h (true)h(for)f(other)g(sensible)h(negativ)o(e)f(constructs,)183 1519 y(for)15 b(example)f(one)h(that)h(c)o(hec)o(ks)g(whether)h(a)e (term)g(is)g(not)g(a)g(pair.)g(W)m(e)f(b)q(eliev)o(e)i(that)g(our)183 1569 y(results)f(remain)d(v)n(alid)g(in)i(the)g(presence)j(of)c(suc)o (h)i(constructs.)183 1701 y Fn(5)56 b(Other)18 b(Equiv)m(alences)e (Useful)i(in)h(Pro)r(ofs)183 1798 y Fs(In)14 b(addition)f(to)i(testing) g(equiv)n(alence,)f(sev)o(eral)h(other)g(equiv)n(alences)g(are)g (useful)f(for)g(rea-)183 1848 y(soning)k(ab)q(out)g(cryptographic)h (proto)q(cols.)g(In)f(particular,)g(barb)q(ed)i(congruence)g(is)f(an) 183 1898 y(equiv)n(alence)12 b(with)g(a)h(tractable)f(co-inductiv)o(e)h (presen)o(tation)g(and)f(is)h(stronger)g(than)g(test-)183 1948 y(ing)18 b(equiv)n(alence.)h(The)h(de\014nitions)f(of)g(these)i (equiv)n(alences)e(are)h(adaptations)f(of)f(cor-)183 1998 y(resp)q(onding)g(de\014nitions)f(in)g(the)h(pi)f(calculus.)g(Ho)o (w)o(ev)o(er,)g(the)h(presence)i(of)d(encryption)183 2047 y(a\013ects)e(the)f(use)h(of)e(these)j(equiv)n(alences)e(in)g (examples.)183 2170 y Fk(Strong)g(Bisimil)o(ari)o(t)o(y)183 2250 y Fs(If)f Fi(R)g Fs(is)g(a)g(relation)g(on)g(closed)h(pro)q (cesses,)h(w)o(e)f(de\014ne)g(the)g(relation)p 1270 2217 36 2 v 12 w Fi(R)g Fs(on)f(closed)h(agen)o(ts:)472 2330 y Fm(P)p 516 2297 V 17 w Fi(R)e Fm(Q)180 b Fs(i\013)25 b Fm(P)17 b Fi(R)12 b Fm(Q)416 2382 y Fs(\()p Fm(x)p Fs(\))p Fm(P)p 516 2348 V 17 w Fi(R)g Fs(\()p Fm(x)p Fs(\))p Fm(Q)131 b Fs(i\013)18 b Fm(P)6 b Fs([)p Fm(M)r(=x)p Fs(])k Fi(R)i Fm(Q)p Fs([)p Fm(M)r(=x)p Fs(])h(for)g(all)g(closed)h Fm(M)314 2433 y Fs(\()p Fm(\027)r(~)-20 b(n)p Fs(\))p Fi(h)p Fm(M)5 b Fi(i)p Fm(P)p 516 2400 V 17 w Fi(R)12 b Fs(\()p Fm(\027)7 b(~)-25 b(m)o Fs(\))p Fi(h)p Fm(M)5 b Fi(i)p Fm(Q)19 b Fs(i\013)k Fm(~)-26 b(m)15 b Fs(is)e(a)h(p)q(erm)o (utation)f(of)f Fm(~)-20 b(n)14 b Fs(and)f Fm(P)k Fi(R)12 b Fm(Q)p eop %%Page: 8 8 8 7 bop 340 194 a Fs(A)20 b Fj(str)n(ong)f(simulation)j Fs(is)d(a)g(binary)f(relation)h Fi(S)j Fs(on)d Fj(Pr)n(o)n(c)i Fs(suc)o(h)f(that)f(if)g Fm(P)25 b Fi(S)f Fm(Q)18 b Fs(and)340 244 y Fm(P)416 220 y Fh(\013)393 244 y Fi(\000)-6 b(!)19 b Fm(A)h Fs(then)g(there)g(exists)g Fm(B)i Fs(with)d Fm(Q)1090 220 y Fh(\013)1068 244 y Fi(\000)-7 b(!)20 b Fm(B)i Fs(and)d Fm(A)p 1345 210 29 2 v 20 w Fi(S)24 b Fm(B)r Fs(.)19 b(A)g(relation)g Fi(S)k Fs(is)c(a)340 293 y Fj(str)n(ong)c(bisimulation)i Fs(if)d(and)g(only)f(if)h(b)q(oth)g Fi(S)k Fs(and)c(its)g(con)o(v)o(erse)i Fi(S)1427 278 y Fl(\000)p Fr(1)1486 293 y Fs(are)f(strong)f(sim)o(u-)340 343 y(lations)e([Mil95b)n(].)g Fj(Str)n(ong)i(bisimilarity)p Fs(,)c(written)k Fi(\030)1181 349 y Fh(s)1199 343 y Fs(,)e(is)h(the)g (greatest)h(strong)f(bisim)o(ula-)340 393 y(tion,)g(namely)f(the)j (union)e(of)g(all)g(strong)h(bisim)o(ulations.)403 443 y(Strong)21 b(bisimilarit)o(y)d(is)j(a)g(rather)h(\014ne-grained)f (equiv)n(alence)g(for)g(the)h(spi)f(calcu-)340 493 y(lus.)g(F)m(or)h (instance,)f(it)h(discriminates)e(b)q(et)o(w)o(een)j(the)f(pro)q (cesses)j(\()p Fm(\027)s(K)s Fs(\))p 1525 470 18 2 v Fm(c)o Fi(hf)p Fm(M)5 b Fi(g)1645 499 y Fh(K)1677 493 y Fi(i)21 b Fs(and)340 542 y(\()p Fm(\027)s(K)s Fs(\))p 434 520 V Fm(c)p Fi(hf)p Fm(M)534 527 y Fl(0)545 542 y Fi(g)566 548 y Fh(K)598 542 y Fi(i)p Fs(,)16 b(whic)o(h)g(w)o(e)g(w)o (ould)g(wish)g(to)g(equate)h(since)g(these)g(pro)q(cesses)i(send)e(en-) 340 592 y(crypted)e(messages)f(under)g(k)o(eys)g(that)g(are)g(nev)o(er) g(disclosed,)g(so)f(their)h(di\013erence)h(should)340 642 y(not)f(matter.)e(Still,)f(strong)j(bisimilarit)o(y)c(is)j(often)g (useful)h(in)f(justifying)f(particular)h(steps)340 692 y(of)h(our)g(pro)q(ofs.)340 806 y Fk(Barb)q(ed)h(Equiv)m(alence)340 878 y Fs(In)o(tuitiv)o(ely)m(,)d(one)h(w)o(a)o(y)g(of)g(w)o(eak)o (ening)g(strong)g(bisimilarit)o(y)d(is)k(to)f(ignore)g(what)g(messages) 340 928 y(are)20 b(sen)o(t)g(on)f(what)f(c)o(hannels,)i(and)f(to)f (record)j(only)d(what)h(c)o(hannels)g(are)h(used.)f(This)340 978 y(informal)13 b(idea)j(leads)f(to)h(the)g(follo)o(wing)d (de\014nition.)i(A)h Fj(b)n(arb)n(e)n(d)g(simulation)j Fs(is)c(a)h(binary)340 1027 y(relation)e Fi(S)j Fs(on)c Fj(Pr)n(o)n(c)j Fs(suc)o(h)f(that)f Fm(P)j Fi(S)e Fm(Q)e Fs(implies:)337 1100 y(\(1\))21 b(for)13 b(eac)o(h)i(barb)f Fm(\014)r Fs(,)g(if)f Fm(P)k Fi(#)11 b Fm(\014)17 b Fs(then)d Fm(Q)e Fi(#)f Fm(\014)r Fs(,)j(and)337 1149 y(\(2\))21 b(if)13 b Fm(P)k Fi(!)11 b Fm(P)579 1134 y Fl(0)604 1149 y Fs(then)j(there)i(exists)e Fm(Q)952 1134 y Fl(0)978 1149 y Fs(suc)o(h)g(that)g Fm(Q)d Fi(!)h Fm(Q)1292 1134 y Fl(0)1317 1149 y Fs(and)i Fm(P)1431 1134 y Fl(0)1453 1149 y Fi(\021S)s(\021)e Fm(Q)1590 1134 y Fl(0)340 1222 y Fs(where)22 b Fm(P)500 1207 y Fl(0)534 1222 y Fi(\021S)s(\021)h Fm(Q)682 1207 y Fl(0)714 1222 y Fs(means)d(that)g(there)i(exist)f Fm(P)1195 1207 y Fl(00)1236 1222 y Fs(and)f Fm(Q)1356 1207 y Fl(00)1398 1222 y Fs(suc)o(h)h(that)g Fm(P)1628 1207 y Fl(0)1661 1222 y Fi(\021)i Fm(P)1749 1207 y Fl(00)1770 1222 y Fs(,)340 1272 y Fm(P)373 1257 y Fl(00)406 1272 y Fi(S)16 b Fm(Q)480 1257 y Fl(00)501 1272 y Fs(,)d(and)i Fm(Q)641 1257 y Fl(00)674 1272 y Fi(\021)d Fm(Q)751 1257 y Fl(0)763 1272 y Fs(.)h(A)i Fj(b)n(arb)n(e)n(d)g(bisimulation)i Fs(is)d(a)g(relation)g Fi(S)j Fs(suc)o(h)e(that)g(b)q(oth)f Fi(S)340 1321 y Fs(and)h Fi(S)450 1306 y Fl(\000)p Fr(1)510 1321 y Fs(are)g(barb)q(ed)h(sim)o(ulations.)c Fj(Barb)n(e)n(d)k(e)n (quivalenc)n(e)p Fs(,)f(written)1475 1298 y Fl(\001)1464 1321 y Fi(\030)p Fs(,)g(is)f(the)i(greatest)340 1371 y(barb)q(ed)f(bisim)o(ulation.)340 1443 y Fk(Prop)q(osition)5 b(5.)20 b Fj(Barb)n(e)n(d)c(e)n(quivalenc)n(e)g(is)f(an)g(e)n (quivalenc)n(e)h(r)n(elation,)f(and)h(is)f(pr)n(eserve)n(d)340 1493 y(by)j(r)n(estriction.)e(F)m(urthermor)n(e,)g(b)n(oth)i(structur)n (al)e(e)n(quivalenc)n(e)i(and)g(str)n(ong)f(bisimilarity)340 1543 y(imply)e(b)n(arb)n(e)n(d)g(e)n(quivalenc)n(e.)403 1615 y Fs(In)f(order)g(to)g(establish)g(a)g(barb)q(ed)h(equiv)n (alence,)e(it)h(is)g(often)g(con)o(v)o(enien)o(t)g(to)g(use)g(Mil-)340 1665 y(ner's)e(tec)o(hnique)h(of)d(\\bisim)o(ulation)e(up)k(to")g ([Mil89)n(,)f(MPW92)o(].)g(A)g Fj(b)n(arb)n(e)n(d)h(simulation)h(up)340 1721 y(to)401 1697 y Fl(\001)390 1721 y Fi(\030)i Fj(and)h(r)n (estriction)g Fs(is)d(a)h(binary)f(relation)h Fi(S)j Fs(on)c Fj(Pr)n(o)n(c)j Fs(suc)o(h)f(that)f Fm(P)j Fi(S)e Fm(Q)e Fs(implies:)337 1793 y(\(1\))21 b(for)13 b(eac)o(h)i(barb)f Fm(\014)r Fs(,)g(if)f Fm(P)k Fi(#)11 b Fm(\014)17 b Fs(then)d Fm(Q)e Fi(#)f Fm(\014)r Fs(,)j(and)337 1843 y(\(2\))21 b(if)14 b Fm(P)19 b Fi(!)13 b Fm(P)584 1828 y Fl(0)610 1843 y Fs(then)j(there)g(exists)g Fm(Q)962 1828 y Fl(0)989 1843 y Fs(suc)o(h)f(that)h Fm(Q)d Fi(!)g Fm(Q)1309 1828 y Fl(0)1320 1843 y Fs(,)i(and)g(there)h(exist)g Fm(P)1669 1828 y Fl(00)1689 1843 y Fs(,)f Fm(Q)1749 1828 y Fl(00)1770 1843 y Fs(,)411 1899 y(and)f(names)e Fm(~)-20 b(n)13 b Fs(suc)o(h)i(that)f Fm(P)874 1884 y Fl(0)908 1875 y(\001)897 1899 y Fi(\030)d Fs(\()p Fm(\027)r(~)-20 b(n)p Fs(\))p Fm(P)1054 1884 y Fl(00)1074 1899 y Fs(,)14 b Fm(Q)1133 1884 y Fl(0)1167 1875 y(\001)1156 1899 y Fi(\030)e Fs(\()p Fm(\027)r(~)-20 b(n)o Fs(\))p Fm(Q)1313 1884 y Fl(00)1334 1899 y Fs(,)13 b(and)h Fm(P)1473 1884 y Fl(00)1505 1899 y Fi(S)h Fm(Q)1578 1884 y Fl(00)1599 1899 y Fs(.)340 1977 y(A)g Fj(b)n(arb)n(e)n(d)h(bisimulation)g(up)g(to)871 1953 y Fl(\001)860 1977 y Fi(\030)g Fj(and)h(r)n(estriction)f Fs(is)f(a)g(relation)f Fi(S)k Fs(suc)o(h)e(that)f(b)q(oth)g Fi(S)340 2027 y Fs(and)f Fi(S)449 2012 y Fl(\000)p Fr(1)508 2027 y Fs(are)g(barb)q(ed)h(sim)o(ulations)c(up)j(to)1057 2003 y Fl(\001)1046 2027 y Fi(\030)g Fs(and)g(restriction.)340 2105 y Fk(Prop)q(osition)5 b(6.)20 b Fj(If)i Fi(S)j Fj(is)d(a)g(b)n (arb)n(e)n(d)g(bisimulation)f(up)i(to)1353 2081 y Fl(\001)1342 2105 y Fi(\030)f Fj(and)h(r)n(estriction,)d(then)340 2155 y Fi(S)15 b(\022)435 2131 y Fl(\001)424 2155 y Fi(\030)p Fj(.)403 2232 y Fs(Barb)q(ed)g(equiv)n(alence)f(is)f(still)g(only)g(a)h (stepping)g(stone.)g(One)h(reason)f(for)g(this)g(is)f(that)340 2282 y(there)22 b(are)f(pro)q(cesses)i(that)d(are)h(barb)q(ed)g(equiv)n (alen)o(t)f(but)g(not)h(strongly)f(bisimilar)d(or)340 2332 y(testing)e(equiv)n(alen)o(t,)d(suc)o(h)j(as)p 830 2309 37 2 v 14 w Fm(m)p Fi(h)p Fm(n)p Fi(i)p Fm(:)p 935 2309 V(m)q Fi(h)p Fm(n)p Fi(i)f Fs(and)p 1123 2309 V 13 w Fm(m)q Fi(h)p Fm(n)p Fi(i)p Fs(.)f(Moreo)o(v)o(er,)h(barb)q(ed)h (equiv)n(alence)340 2382 y(is)g(far)g(from)e(b)q(eing)i(a)g (congruence:)h(it)f(is)g(not)g(ev)o(en)h(closed)f(under)h(comp)q (osition,)d(as)i(can)340 2432 y(b)q(e)g(seen)g(b)o(y)f(comparing)p 748 2409 V 12 w Fm(m)p Fi(h)p Fm(n)p Fi(i)p Fm(:)p 853 2409 V(m)p Fi(h)p Fm(n)p Fi(i)e(j)f Fm(m)p Fs(\()p Fm(x)p Fs(\))j(and)p 1168 2409 V 14 w Fm(m)q Fi(h)p Fm(n)p Fi(i)d(j)g Fm(m)p Fs(\()p Fm(x)p Fs(\).)p eop %%Page: 9 9 9 8 bop 183 194 a Fk(Barb)q(ed)15 b(Congruence)183 275 y Fj(Barb)n(e)n(d)e(c)n(ongruenc)n(e)p Fs(,)f(written)h Fi(\030)p Fs(,)e(is)h(the)h(relation)e(on)h Fj(Pr)n(o)n(c)i Fs(obtained)e(b)o(y)f(strengthening)183 325 y(barb)q(ed)j(equiv)n (alence)g(as)g(follo)o(ws:)552 413 y Fm(P)j Fi(\030)12 b Fm(Q)703 389 y Ff(\001)698 413 y Fs(=)26 b Fi(8)p Fm(R)11 b Fi(2)g Fj(Pr)n(o)n(c)r Fs(\()p Fm(P)18 b Fi(j)11 b Fm(R)1083 389 y Fl(\001)1072 413 y Fi(\030)h Fm(P)17 b Fi(j)11 b Fm(R)p Fs(\))245 496 y(F)m(or)f(example,)f(it)h(is)h(easy)g (to)f(pro)o(v)o(e)h(that)g(a)f(pro)q(cess)j(that)d(attempts)h(to)f (decrypt)i(\\with)183 546 y(the)i(wrong)g(k)o(ey")f(is)h(barb)q(ed)h (congruen)o(t)g(to)e Fk(0)p Fs(:)329 653 y Fj(c)n(ase)k Fm(M)i Fj(of)j Fi(f)p Fm(x)p Fi(g)601 659 y Fh(K)646 653 y Fj(in)17 b Fm(P)31 b Fi(\030)815 594 y Fg(\032)852 627 y Fm(P)6 b Fs([)p Fm(N)q(=x)p Fs(])k(if)j Fm(M)j Fs(=)c Fi(f)p Fm(N)5 b Fi(g)1216 633 y Fh(K)1261 627 y Fs(for)14 b(some)f Fm(N)852 677 y Fk(0)122 b Fs(otherwise)183 759 y(This)16 b(is)f(an)h(example)f(of)g(the)i(fairly)d(ob)o(vious)i (fact)f(that)i(barb)q(ed)f(congruence)i(do)q(es)f(not)183 809 y(imply)11 b(structural)k(equiv)n(alence.)245 858 y(As)c(another)h(example,)d(w)o(e)i(pro)o(v)o(e)g(in)f(Section)j(6)e (that)g(\()p Fm(\027)s(K)s Fs(\))p 1193 836 18 2 v Fm(c)p Fi(hf)p Fm(M)5 b Fi(g)1314 864 y Fh(K)1345 858 y Fi(i)11 b Fs(is)g(barb)q(ed)g(con-)183 908 y(gruen)o(t)i(to)f(\()p Fm(\027)s(K)s Fs(\))p 455 885 V Fm(c)p Fi(hf)p Fm(M)555 893 y Fl(0)566 908 y Fi(g)587 914 y Fh(K)619 908 y Fi(i)p Fs(.)g(This)g(example)g(sho)o(ws)g(that)h(barb)q(ed)g(congruence)h(do)q (es)g(not)183 958 y(imply)e(strong)j(bisimilarit)o(y)l(.)d(It)i(also)h (sho)o(ws)g(that)g(barb)q(ed)g(congruence)i(is)d(not)h(sensitiv)o(e)183 1008 y(to)f(the)i(con)o(ten)o(ts)f(of)g(encrypted)h(messages)f(whose)g (k)o(eys)h(are)f(not)f(disclosed,)h(suggesting)183 1058 y(that)h(barb)q(ed)h(congruence)i(is)d(coarse-grained)h(enough)g(for)f (in)o(teresting)h(cryptographic)183 1108 y(applications.)183 1197 y Fk(Prop)q(ositi)o(on)5 b(7.)21 b Fj(Barb)n(e)n(d)e(c)n(ongruenc) n(e)h(is)e(a)i(c)n(ongruenc)n(e.)f(F)m(urthermor)n(e,)f(b)n(oth)h (struc-)183 1247 y(tur)n(al)d(e)n(quivalenc)n(e)i(and)g(str)n(ong)f (bisimilarity)e(imply)i(b)n(arb)n(e)n(d)g(c)n(ongruenc)n(e,)g(while)g (b)n(arb)n(e)n(d)183 1296 y(c)n(ongruenc)n(e)e(implies)g(testing)f(e)n (quivalenc)n(e.)245 1386 y Fs(Th)o(us,)f(whenev)o(er)i(w)o(e)e(wish)g (to)g(pro)o(v)o(e)h(a)f(testing)g(equiv)n(alence,)g(w)o(e)h(ma)o(y)d (try)i(to)g(pro)o(v)o(e)183 1436 y(a)e(barb)q(ed)g(congruence,)i(as)e (a)g(su\016cien)o(t)h(condition.)e(Ho)o(w)o(ev)o(er,)h(testing)g(equiv) n(alence)h(do)q(es)183 1485 y(not)h(imply)d(barb)q(ed)k(congruence,)h (b)q(ecause)f(barb)q(ed)g(congruence)h(is)e(more)f(sensitiv)o(e)i(to)f Fm(\034)183 1535 y Fs(steps)i(and)f(to)f(branc)o(hing)h(structure.)183 1668 y Fn(6)56 b(The)18 b(Underpinning)g(Relation)183 1766 y Fs(This)12 b(section)h(in)o(tro)q(duces)h(the)f Fj(underpinning)i(r)n(elation)p Fs(,)c(whic)o(h)h(is)h(also)e(useful)i (in)f(pro)q(ofs.)183 1816 y(W)m(e)j(sa)o(y)h(that)g Fm(x)446 1822 y Fr(1)464 1816 y Fs(:)p Fi(f\000g)550 1822 y Fh(p)567 1826 y Ff(1)585 1816 y Fm(;)7 b(:)g(:)g(:)e(;)i(x)702 1822 y Fh(n)724 1816 y Fs(:)o Fi(f\000g)809 1822 y Fh(p)826 1826 y Fe(n)864 1816 y Fj(underpins)20 b Fs(the)d(agen)o(t)f Fm(A)g Fs(roughly)f(if)g Fm(A)h Fs(is)g(an)183 1866 y(agen)o(t)f(that)h (ma)o(y)d(con)o(tain)i(o)q(ccurrences)k(of)c(an)o(y)g(of)g(the)h(v)n (ariables)f Fm(x)1301 1872 y Fr(1)1319 1866 y Fs(,)g(.)7 b(.)f(.)h(,)15 b Fm(x)1453 1872 y Fh(n)1475 1866 y Fs(,)g(but)h(no)183 1916 y(o)q(ccurrences)h(of)c(an)o(y)g(of)h(the)g(names)f Fm(p)798 1922 y Fr(1)817 1916 y Fs(,)g(.)7 b(.)f(.)g(,)14 b Fm(p)944 1922 y Fh(n)966 1916 y Fs(.)g(W)m(e)f(write)h(this:)650 1999 y Fm(x)674 2005 y Fr(1)692 1999 y Fs(:)p Fi(f\000g)778 2005 y Fh(p)795 2009 y Ff(1)813 1999 y Fm(;)7 b(:)g(:)g(:)e(;)i(x)930 2005 y Fh(n)952 1999 y Fs(:)o Fi(f\000g)1037 2005 y Fh(p)1054 2009 y Fe(n)1088 1999 y Fi(`)12 b Fm(A)183 2083 y Fs(Our)h(in)o(ten)o (tion)f(is)g(that)h Fm(A)f Fs(represen)o(ts)j(an)e(attac)o(k)o(er)g (and)f(that)h(the)g(v)n(ariables)f Fm(x)1456 2089 y Fr(1)1474 2083 y Fs(,)g(.)6 b(.)h(.)f(,)12 b Fm(x)1601 2089 y Fh(n)183 2133 y Fs(represen)o(t)19 b(ciphertexts)g(that)e(the)h(attac)o(k)o(er)f (ma)o(y)e(ha)o(v)o(e)i(in)o(tercepted)i(encrypted)g(under)183 2183 y(the)13 b(k)o(eys)h Fm(p)365 2189 y Fr(1)383 2183 y Fs(,)f(.)6 b(.)h(.)f(,)13 b Fm(p)509 2189 y Fh(n)531 2183 y Fs(,)g(whic)o(h)g(the)h(attac)o(k)o(er)f(do)q(es)h(not)f(ha)o(v) o(e.)f(\(Here)j(w)o(e)e(tak)o(e)g(all)f(k)o(eys)i(to)183 2232 y(b)q(e)f(names)f(as)i(this)f(su\016ces)h(for)e(our)i(presen)o(t)g (purp)q(oses;)g(but)f(the)h(general)f(case,)h(where)g(a)183 2282 y(k)o(ey)g(is)f(an)h(arbitrary)g(term,)f(could)g(also)h(b)q(e)g (in)o(teresting.\))245 2332 y(Next)i(w)o(e)g(giv)o(e)g(a)f(precise)j (de\014nition)d(of)g(the)i(underpinning)f(relation.)f(An)h Fj(envir)n(on-)183 2382 y(ment)j Fs(is)d(a)g(\014nite)f(list)h(of)f(en) o(tries)i(of)e(the)h(form)e Fm(x)p Fs(:)o Fi(f\000g)1067 2388 y Fh(n)1090 2382 y Fs(,)h(where)i Fm(x)e Fs(is)h(a)f(v)n(ariable)g (and)h Fm(n)183 2432 y Fs(is)f(a)h(name;)e(all)g(the)j(v)n(ariables)e (m)o(ust)g(b)q(e)h(distinct)g(\(but)g(the)g(names)f(need)i(not)f(b)q (e\).)g(W)m(e)p eop %%Page: 10 10 10 9 bop 340 194 a Fs(let)16 b Fj(dom)t Fs(\()p Fm(E)r Fs(\))f(b)q(e)i(the)f(set)g(of)f(v)n(ariables)g(men)o(tioned)g(in)g (the)h(en)o(tries)h(in)e Fm(E)r Fs(,)g(and)g Fj(keys)t Fs(\()p Fm(E)r Fs(\))340 244 y(the)g(set)h(of)d(names)h(men)o(tioned)f (in)h(the)h(en)o(tries)g(in)f Fm(E)r Fs(.)g(When)g Fm(E)j Fs(is)d(an)g(en)o(vironmen)o(t,)f Fm(M)340 293 y Fs(a)h(term,)f(and)h Fm(A)f Fs(an)h(agen)o(t,)g(w)o(e)g(de\014ne:)561 375 y Fm(E)f Fi(`)f Fm(M)717 352 y Ff(\001)712 375 y Fs(=)26 b Fj(fv)5 b Fs(\()p Fm(M)g Fs(\))11 b Fi(\022)h Fj(dom)s Fs(\()p Fm(E)r Fs(\))j(and)e Fj(fn)t Fs(\()p Fm(M)5 b Fs(\))k Fi(\\)g Fj(keys)t Fs(\()p Fm(E)r Fs(\))i(=)h Fi(;)561 432 y Fm(E)h Fi(`)f Fm(A)717 409 y Ff(\001)712 432 y Fs(=)26 b Fj(fv)5 b Fs(\()p Fm(A)p Fs(\))11 b Fi(\022)h Fj(dom)t Fs(\()p Fm(E)r Fs(\))i(and)g Fj(fn)s Fs(\()p Fm(A)p Fs(\))c Fi(\\)f Fj(keys)s Fs(\()p Fm(E)r Fs(\))j(=)g Fi(;)340 508 y Fs(The)j(relation)e Fi(`)h Fs(is)g(the)g(underpinning)g (relation.)403 558 y(When)d Fm(x)p Fs(:)o Fi(f\000g)630 564 y Fh(n)663 558 y Fs(o)q(ccurs)h(in)e(an)h(en)o(vironmen)o(t,)e(w)o (e)i(in)o(tend)f(that)h Fm(x)g Fs(stands)g(for)f(a)h(cipher-)340 608 y(text)i(of)d(the)j(form)c Fi(f)p Fm(M)c Fi(g)721 614 y Fh(n)743 608 y Fs(.)11 b(An)h Fm(E)r Fj(-closur)n(e)i Fs(is)e(a)f(substitution)h(that)f(\014xes)i(all)d(the)i(v)n(ariables) 340 657 y(in)h Fm(E)i Fs(to)d(appropriate)h(ciphertexts;)i(more)c (precisely)m(,)i(an)g Fm(E)r Fs(-closure)h(is)e(a)h(substitution)g Fm(\033)340 707 y Fs(of)e(closed)h(ciphertexts)h(for)e(v)n(ariables)f (suc)o(h)i(that)g Fm(E)h Fi(`)f Fm(\033)h Fs(is)e(deriv)n(able)g(from)e (the)j(follo)o(wing)340 757 y(rules:)p 663 810 102 2 v 669 855 a Fi(;)g(`)f(;)854 793 y Fm(E)i Fi(`)f Fm(\033)43 b(x)16 b(=)-26 b Fi(2)12 b Fj(dom)s Fs(\()p Fm(E)r Fs(\))42 b Fj(fv)t Fs(\()p Fm(M)5 b Fs(\))12 b(=)g Fi(;)p 848 810 611 2 v 940 855 a Fm(E)r(;)7 b(x)p Fs(:)o Fi(f\000g)1101 861 y Fh(n)1135 855 y Fi(`)12 b Fm(\033)o(;)7 b Fi(f)p Fm(M)e Fi(g)1301 861 y Fh(n)1322 855 y Fm(=x)340 923 y Fs(where)22 b Fi(;)e Fs(represen)o(ts)i(the)f(empt)o(y)e(en)o (vironmen)o(t,)g(the)i(empt)o(y)e(substitution,)h(and)g(the)340 973 y(empt)o(y)13 b(set,)i(and)e Fm(\033)o(;)7 b Fi(f)p Fm(M)e Fi(g)753 979 y Fh(n)775 973 y Fm(=x)13 b Fs(is)h(the)g (extension)h(of)e Fm(\033)i Fs(that)f(maps)f Fm(x)g Fs(to)h Fi(f)p Fm(M)5 b Fi(g)1590 979 y Fh(n)1612 973 y Fs(.)403 1023 y(T)m(o)k(pro)o(v)o(e)g(secrecy)j(prop)q(erties,)f(w)o(e)f(w)o (ould)f(lik)o(e)f(to)i(sho)o(w)g(that)f(a)h(pro)q(cess)h(underpinned) 340 1073 y(b)o(y)k(an)g(en)o(vironmen)o(t)f(acts)i(uniformly)d(no)i (matter)f(whic)o(h)h(ciphertexts)i(are)f(substituted)340 1123 y(for)11 b(the)h(v)n(ariables)e(in)g(the)i(en)o(vironmen)o(t.)d(A) o(t)j(\014rst)f(sigh)o(t)g(one)g(migh)o(t)e(think)i(that)g(if)f Fm(E)j Fi(`)f Fm(P)6 b Fs(,)340 1172 y Fm(E)23 b Fi(`)d Fm(\033)q Fs(,)f(and)g Fm(E)j Fi(`)e Fm(\033)704 1157 y Fl(0)716 1172 y Fs(,)f(then)g Fm(P)6 b(\033)21 b Fi(\030)g Fm(P)6 b(\033)1035 1157 y Fl(0)1065 1172 y Fs(on)19 b(the)g(reasoning)g (that,)g(since)h Fm(P)k Fs(cannot)340 1222 y(un)o(wrap)18 b(the)f(ciphertexts)i(in)e Fm(\033)i Fs(or)e Fm(\033)958 1207 y Fl(0)970 1222 y Fs(,)f(it)h(will)f(b)q(eha)o(v)o(e)i(the)g(same) e(whether)j(closed)f(b)o(y)340 1272 y(one)i(or)g(the)h(other)f Fm(E)r Fs(-closure.)g(This)g(w)o(ould)f(hold)g(w)o(ere)i(it)e(not)h (for)f(the)i(presence)h(of)340 1322 y(matc)o(hing)12 b(in)h(the)h(language.)e(F)m(or)h(example,)e Fm(E)j Fs(=)d Fm(x)p Fs(:)p Fi(f\000g)1269 1328 y Fh(m)1300 1322 y Fm(;)c(y)q Fs(:)p Fi(f\000g)1426 1328 y Fh(m)1457 1322 y Fs(,)13 b Fm(P)k Fs(=)12 b([)p Fm(x)7 b Fj(is)k Fm(y)q Fs(])p 1696 1299 21 2 v 9 w Fm(p)p Fi(h)p Fs(0)p Fi(i)p Fs(,)340 1372 y Fm(\033)20 b Fs(=)g([)p Fi(f)p Fs(0)p Fi(g)511 1378 y Fh(m)541 1372 y Fm(=x;)13 b Fi(f)p Fs(0)p Fi(g)674 1378 y Fh(m)705 1372 y Fm(=y)q Fs(],)18 b(and)g Fm(\033)899 1357 y Fl(0)929 1372 y Fs(=)i([)p Fi(f)p Fs(0)p Fi(g)1056 1378 y Fh(m)1086 1372 y Fm(=x;)13 b Fi(f)p Fj(suc)r Fs(\(0\))p Fi(g)1311 1378 y Fh(m)1342 1372 y Fm(=y)q Fs(])19 b(meet)f(the)h(conditions)340 1422 y(ab)q(o)o(v)o(e,)11 b(but)h Fm(P)6 b(\033)13 b Fs(ma)o(y)d(output)i(0)f(whereas)i Fm(P)6 b(\033)1078 1406 y Fl(0)1101 1422 y Fs(is)12 b(stuc)o(k.)g(Th)o(us,)g Fm(P)17 b Fs(can)12 b(act)g(con)o(tingen)o(tly)340 1471 y(on)18 b(the)g(ciphertexts)h(ev)o(en)f(though)g(it)f(cannot)g(decrypt) i(them.)d(Ho)o(w)o(ev)o(er,)i(if)f(w)o(e)g(insist)340 1521 y(that)f Fm(\033)g Fs(and)f Fm(\033)579 1506 y Fl(0)606 1521 y Fs(b)q(e)h(injectiv)o(e)f(\(that)g(is,)g Fm(x)e Fs(=)h Fm(y)j Fs(whenev)o(er)g Fm(x\033)e Fs(=)f Fm(y)q(\033)q Fs(,)h(and)g(similarly)e(for)340 1571 y Fm(\033)365 1556 y Fl(0)377 1571 y Fs(\))h(then)h(w)o(e)f(obtain)f Fm(P)6 b(\033)12 b Fi(\030)g Fm(P)6 b(\033)863 1556 y Fl(0)874 1571 y Fs(.)403 1621 y(These)15 b(informal)c(argumen)o(ts)i(lead)h(to)f (the)i(follo)o(wing)c(results.)340 1699 y Fk(Lemma)d(8.)21 b Fj(Supp)n(ose)16 b(that)f Fm(E)f Fi(`)f Fm(P)20 b Fj(and)c Fm(E)e Fi(`)f Fm(\033)q Fj(,)i(and)h(that)f Fm(\033)i Fj(is)d(inje)n(ctive.)h(If)g Fm(P)6 b(\033)12 b(>)h(Q)1770 1684 y Fl(0)340 1748 y Fj(then)21 b(ther)n(e)e(is)g(a)h(pr)n(o)n(c)n (ess)g Fm(Q)f Fj(with)g Fm(E)k Fi(`)e Fm(Q)p Fj(,)e(fv)t Fs(\()p Fm(Q)p Fs(\))i Fi(\022)f Fj(fv)5 b Fs(\()p Fm(P)h Fs(\))p Fj(,)19 b(fn)s Fs(\()p Fm(Q)p Fs(\))h Fi(\022)h Fj(fn)s Fs(\()p Fm(P)6 b Fs(\))p Fj(,)20 b(and)340 1798 y Fm(Q)373 1783 y Fl(0)396 1798 y Fs(=)12 b Fm(Q\033)h Fj(such)g(that,)f(whenever)g Fm(E)i Fi(`)e Fm(\033)982 1783 y Fl(0)1006 1798 y Fj(and)h Fm(\033)1109 1783 y Fl(0)1133 1798 y Fj(is)e(inje)n(ctive,)h Fm(P)6 b(\033)1407 1783 y Fl(0)1430 1798 y Fm(>)12 b(Q\033)1532 1783 y Fl(0)1543 1798 y Fj(.)g(Similarly,)f(if)340 1848 y Fm(P)6 b(\033)432 1825 y Fh(\013)410 1848 y Fi(\000)-7 b(!)11 b Fm(A)519 1833 y Fl(0)545 1848 y Fj(then)j(ther)n(e)f(is)h(an)g(agent)h Fm(A)f Fj(with)f Fm(E)g Fi(`)f Fm(A)p Fj(,)i(fv)t Fs(\()p Fm(A)p Fs(\))e Fi(\022)g Fj(fv)t Fs(\()p Fm(P)6 b Fs(\))p Fj(,)14 b(fn)s Fs(\()p Fm(A)p Fs(\))e Fi(\022)g Fj(fn)s Fs(\()p Fm(P)6 b Fs(\))p Fj(,)340 1903 y(and)16 b Fm(A)452 1888 y Fl(0)475 1903 y Fs(=)c Fm(A\033)k Fj(such)g(that,)e(whenever)h Fm(E)f Fi(`)e Fm(\033)1070 1888 y Fl(0)1096 1903 y Fj(and)k Fm(\033)1202 1888 y Fl(0)1229 1903 y Fj(is)e(inje)n(ctive,)g Fm(P)6 b(\033)1508 1888 y Fl(0)1554 1879 y Fh(\013)1531 1903 y Fi(\000)-6 b(!)11 b Fm(A\033)1666 1888 y Fl(0)1678 1903 y Fj(.)340 1988 y Fk(Prop)q(osition)5 b(9.)20 b Fj(Supp)n(ose)g(that)e Fm(E)i Fi(`)d Fm(\033)j Fj(and)f Fm(E)g Fi(`)f Fm(\033)1237 1973 y Fl(0)1249 1988 y Fj(,)g(and)h(that)f (b)n(oth)g Fm(\033)i Fj(and)f Fm(\033)1696 1973 y Fl(0)1726 1988 y Fj(ar)n(e)340 2037 y(inje)n(ctive.)c(Then)g Fi(S)g Fs(=)c Fi(f)p Fs(\()p Fm(P)6 b(\033)o(;)h(P)f(\033)879 2022 y Fl(0)889 2037 y Fs(\))12 b Fi(j)f Fm(E)j Fi(`)d Fm(P)6 b Fi(g)15 b Fj(is)f(a)h(b)n(arb)n(e)n(d)g(bisimulation.)403 2122 y Fs(This)d(last)f(prop)q(osition)h(pro)o(vides)g(an)g(easy)g(w)o (a)o(y)g(to)g(pro)o(v)o(e)g(some)f(equiv)n(alences,)h(as)g(w)o(e)340 2172 y(no)o(w)k(demonstrate)h(with)f(a)g(small)f(pro)q(of)h(of)g(a)g (secrecy)i(prop)q(ert)o(y)m(.)f(W)m(e)f(pro)o(v)o(e)h(that,)f(for)340 2222 y(an)o(y)e(closed)g(terms)g Fm(M)19 b Fs(and)13 b Fm(M)841 2207 y Fl(0)853 2222 y Fs(:)751 2302 y(\()p Fm(\027)s(K)s Fs(\))p 845 2279 18 2 v Fm(c)p Fi(hf)p Fm(M)5 b Fi(g)966 2308 y Fh(K)997 2302 y Fi(i)26 b(')g Fs(\()p Fm(\027)s(K)s Fs(\))p 1191 2279 V Fm(c)o Fi(hf)p Fm(M)1290 2285 y Fl(0)1302 2302 y Fi(g)1323 2308 y Fh(K)1354 2302 y Fi(i)340 2382 y Fs(By)20 b(Prop)q(osition)12 b(7,)19 b(w)o(e)h(can)g(reduce)i(this)e(testing)g(equiv)n(alence)g(to)f(the)i (barb)q(ed)f(con-)340 2432 y(gruence)15 b(\()p Fm(\027)s(K)s Fs(\))p 586 2409 V Fm(c)p Fi(hf)p Fm(M)5 b Fi(g)707 2438 y Fh(K)738 2432 y Fi(i)12 b(\030)g Fs(\()p Fm(\027)s(K)s Fs(\))p 904 2409 V Fm(c)o Fi(hf)p Fm(M)1003 2417 y Fl(0)1014 2432 y Fi(g)1035 2438 y Fh(K)1067 2432 y Fi(i)p Fs(.)h(According)h(to)f (the)g(de\014nition)g(of)g(barb)q(ed)p eop %%Page: 11 11 11 10 bop 183 194 a Fs(congruence,)12 b(it)e(su\016ces)i(to)f (establish)g(the)g(barb)q(ed)h(equiv)n(alence)f(\(\()p Fm(\027)s(K)s Fs(\))p 1329 171 18 2 v Fm(c)p Fi(hf)p Fm(M)5 b Fi(g)1450 200 y Fh(K)1481 194 y Fi(i)p Fs(\))12 b Fi(j)f Fm(R)1603 170 y Fl(\001)1591 194 y Fi(\030)183 244 y Fs(\(\()p Fm(\027)s(K)s Fs(\))p 293 221 V Fm(c)o Fi(hf)p Fm(M)392 228 y Fl(0)404 244 y Fi(g)425 250 y Fh(K)457 244 y Fi(i)p Fs(\))i Fi(j)f Fm(R)j Fs(for)f(ev)o(ery)i(closed) f(pro)q(cess)i Fm(R)p Fs(.)d(Since)h Fm(K)j Fs(is)c(b)q(ound,)h(w)o(e)g (ma)o(y)e(as-)183 293 y(sume)g(that)g Fm(K)19 b(=)-25 b Fi(2)11 b Fj(fn)s Fs(\()p Fm(R)p Fs(\).)i(So)h(w)o(e)f(ha)o(v)o(e)g (the)i(structural)f(equiv)n(alences)g(\(\()p Fm(\027)s(K)s Fs(\))p 1416 270 V Fm(c)p Fi(hf)p Fm(M)5 b Fi(g)1537 299 y Fh(K)1568 293 y Fi(i)p Fs(\))12 b Fi(j)183 343 y Fm(R)19 b Fi(\021)g Fs(\()p Fm(\027)s(K)s Fs(\)\()p 395 320 V Fm(c)p Fi(hf)p Fm(M)5 b Fi(g)516 349 y Fh(K)547 343 y Fi(i)20 b(j)f Fm(R)p Fs(\))f(and)g(\(\()p Fm(\027)s(K)s Fs(\))p 875 320 V Fm(c)p Fi(hf)p Fm(M)975 328 y Fl(0)986 343 y Fi(g)1007 349 y Fh(K)1039 343 y Fi(i)p Fs(\))i Fi(j)e Fm(R)i Fi(\021)f Fs(\()p Fm(\027)s(K)s Fs(\)\()p 1334 320 V Fm(c)p Fi(hf)p Fm(M)1434 328 y Fl(0)1445 343 y Fi(g)1466 349 y Fh(K)1498 343 y Fi(i)g(j)g Fm(R)p Fs(\).)183 393 y(Since)c(barb)q(ed)i(equiv)n(alence)e(is)g(an)g(equiv)n(alence)h (relation)f(and)g(since)h(it)f(includes)g(struc-)183 443 y(tural)h(equiv)n(alence)i(\(b)o(y)f(Prop)q(osition)12 b(5\),)k(it)h(su\016ces)i(to)e(sho)o(w)g(that)g(\()p Fm(\027)s(K)s Fs(\)\()p 1427 420 V Fm(c)p Fi(hf)p Fm(M)5 b Fi(g)1548 449 y Fh(K)1579 443 y Fi(i)17 b(j)183 498 y Fm(R)p Fs(\))255 475 y Fl(\001)243 498 y Fi(\030)d Fs(\()p Fm(\027)s(K)s Fs(\)\()p 399 476 V Fm(c)o Fi(hf)p Fm(M)498 483 y Fl(0)510 498 y Fi(g)531 504 y Fh(K)562 498 y Fi(i)f(j)g Fm(R)p Fs(\).)h(Since)h(restriction)h(preserv)o(es)h (barb)q(ed)e(equiv)n(alence)g(\(also)183 548 y(b)o(y)e(Prop)q(osition)f (5\),)i(it)f(su\016ces)i(to)f(pro)o(v)o(e)g(that:)p 621 617 V 621 640 a Fm(c)p Fi(hf)p Fm(M)5 b Fi(g)742 646 y Fh(K)773 640 y Fi(i)12 b(j)f Fm(R)892 617 y Fl(\001)881 640 y Fi(\030)p 939 617 V 26 w Fm(c)p Fi(hf)p Fm(M)1039 623 y Fl(0)1050 640 y Fi(g)1071 646 y Fh(K)1103 640 y Fi(i)h(j)f Fm(R)183 726 y Fs(But)20 b(this)g(follo)o(ws)e(from)g(Prop)q (osition)12 b(9)19 b(with)h Fm(E)j Fs(=)e Fm(x)p Fs(:)p Fi(f\000g)1184 732 y Fh(K)1215 726 y Fs(,)f Fm(P)26 b Fs(=)p 1354 703 V 22 w Fm(c)p Fi(h)p Fm(x)p Fi(i)21 b(j)g Fm(R)p Fs(,)e Fm(\033)j Fs(=)183 776 y([)p Fi(f)p Fm(M)5 b Fi(g)282 782 y Fh(K)312 776 y Fm(=x)p Fs(],)13 b(and)h Fm(\033)500 761 y Fl(0)523 776 y Fs(=)e([)p Fi(f)p Fm(M)645 761 y Fl(0)656 776 y Fi(g)677 782 y Fh(K)708 776 y Fm(=x)p Fs(].)183 911 y Fn(7)56 b(A)19 b(Simple)d(Example)183 1011 y Fs(In)h(this)h(section)g(w)o(e)g(describ)q(e)h(and)e(v)o(erify)g (a)g(t)o(w)o(o-message)g(proto)q(col.)g(Proto)q(cols)h(used)183 1061 y(in)h(practice)i(generally)f(ha)o(v)o(e)f(more)g(messages,)h(but) g(not)g(man)o(y)e(more.)g(W)m(e)h(fo)q(cus)i(on)183 1111 y(this)d(short)h(proto)q(col)g(in)f(order)h(to)f(allo)o(w)f(a)h (concise)i(exp)q(osition)e(of)g(our)h(metho)q(d.)e(W)m(e)183 1160 y(ha)o(v)o(e)g(applied)f(the)i(same)e(metho)q(d)g(to)h(more)f (complex)g(proto)q(cols)h(\(in)g(particular,)f(to)h(a)183 1210 y(sev)o(en-message)d(proto)q(col)g(de\014ned)h(in)d([A)o(G97a)n (]\).)245 1260 y(The)f(purp)q(ose)h(of)f(the)g(proto)q(col)g(is)g(to)g (enable)g(comm)o(unicatio)o(n)d(b)q(et)o(w)o(een)13 b(t)o(w)o(o)d (users)j(or)183 1310 y(mac)o(hines)f Fm(A)h Fs(and)g Fm(B)r Fs(.)h(F)m(or)e(simplicit)o(y)m(,)e(b)q(oth)k Fm(A)f Fs(and)g Fm(B)j Fs(are)d(\014xed,)h(and)f Fm(A)g Fs(sends)h(a)f(\014nite)183 1360 y(but)e(un)o(b)q(ounded)h(set)g(of)f (messages)g(to)g Fm(B)r Fs(.)h(All)e(the)i(messages)f(are)h (transmitted)f(under)h(the)183 1410 y(same)j(shared)i(k)o(ey)g Fm(K)536 1416 y Fh(AB)590 1410 y Fs(.)f(The)g(messages)h(are)g (accompanied)e(b)o(y)h(nonces,)h(whic)o(h)g(m)o(ust)183 1459 y(b)q(e)e(fresh)g(and)g(unpredictable)g(quan)o(tities)e([AN96)o (];)h(for)g(eac)o(h)h(message)g Fm(M)5 b Fs(,)14 b Fm(A)g Fs(creates)j(a)183 1509 y(nonce)d Fm(N)333 1515 y Fh(A)374 1509 y Fs(and)g Fm(B)j Fs(creates)e(a)f(nonce)h Fm(N)827 1515 y Fh(B)855 1509 y Fs(.)f(Informally)l(,)d(the)j(proto)q(col)g(is:) 540 1592 y(Message)h(1)41 b Fm(B)14 b Fi(!)d Fm(A)h Fs(:)27 b Fm(N)978 1598 y Fh(B)540 1642 y Fs(Message)15 b(2)41 b Fm(A)12 b Fi(!)f Fm(B)j Fs(:)27 b Fi(f)p Fm(N)999 1648 y Fh(A)1026 1642 y Fm(;)7 b(N)1078 1648 y Fh(B)1107 1642 y Fm(;)g(M)e Fi(g)1192 1648 y Fh(K)1220 1652 y Fe(AB)183 1726 y Fs(In)10 b(Message)h(1,)e Fm(B)j Fs(c)o(hallenges)e Fm(A)g Fs(with)g(the)g(nonce)h Fm(N)1012 1732 y Fh(B)1041 1726 y Fs(.)e(Message)i(1)f(ma)o(y)e(b)q(e)i(sp)q(on)o(taneous,)183 1776 y(or)i(it)f(ma)o(y)g(b)q(e)h(triggered)h(b)o(y)f(an)g(arbitrary)g (message)f(from)g Fm(A)p Fs(;)h(the)g(details)g(of)g(this)g(do)g(not) 183 1826 y(matter.)k(Message)i(2)f(is)g(the)h(transmission)e(of)g Fm(M)22 b Fs(under)c Fm(K)1170 1832 y Fh(AB)1224 1826 y Fs(.)f(The)g(presence)j(of)d Fm(N)1595 1832 y Fh(B)183 1876 y Fs(pro)o(v)o(es)10 b(the)g(freshness)h(of)e(Message)i(2.)e(The)h (presence)i(of)d Fm(N)1107 1882 y Fh(A)1144 1876 y Fs(guaran)o(tees)h (the)g(distinctness)183 1926 y(of)j(all)g(ciphertexts.)245 1975 y(F)m(or)j(this)h(example,)e(w)o(e)i(enco)q(de)h(a)e(triple)h(\()p Fm(L;)7 b(M)r(;)g(N)e Fs(\))16 b(b)o(y)h(a)f(pair)g(\()p Fm(L;)7 b Fs(\()p Fm(M)r(;)g(N)e Fs(\)\),)17 b(and)183 2025 y(extend)f(pair)e(splitting)g(to)h(triples)g(in)g(the)h(usual)e(w) o(a)o(y)m(.)g(W)m(e)g(also)h(omit)e(the)i(inner)g(brac)o(k-)183 2075 y(ets)k(from)e(an)i(encrypted)h(triple)f(of)f(the)h(form)e Fi(f)p Fs(\()p Fm(N)r(;)7 b(N)1091 2060 y Fl(0)1102 2075 y Fm(;)g(N)1159 2060 y Fl(00)1180 2075 y Fs(\))p Fi(g)1217 2081 y Fh(N)1246 2073 y Fd(000)1278 2075 y Fs(,)18 b(and)h(simply)d (write)183 2125 y Fi(f)p Fm(N)r(;)7 b(N)296 2110 y Fl(0)307 2125 y Fm(;)g(N)364 2110 y Fl(00)384 2125 y Fi(g)405 2131 y Fh(N)434 2123 y Fd(000)466 2125 y Fs(.)245 2175 y(W)m(e)13 b(express)j(the)f(proto)q(col)e(with)h(the)g(follo)o(wing)e (parameterised)i(de\014nitions:)518 2265 y Fm(A)p Fs(\()p Fm(N)598 2271 y Fh(A)626 2265 y Fm(;)7 b(M)e Fs(\))736 2241 y Ff(\001)731 2265 y Fs(=)26 b Fm(c)807 2271 y Fh(A)834 2265 y Fs(\()p Fm(x)p Fs(\))p Fm(:)p 902 2242 47 2 v(c)920 2271 y Fh(B)948 2265 y Fi(hf)p Fm(N)1018 2271 y Fh(A)1045 2265 y Fm(;)7 b(x;)g(M)e Fi(g)1173 2271 y Fh(K)1201 2275 y Fe(AB)1247 2265 y Fi(i)527 2334 y Fm(B)r Fs(\()p Fm(N)609 2340 y Fh(B)638 2334 y Fm(;)i(F)f Fs(\))736 2310 y Ff(\001)731 2334 y Fs(=)p 789 2311 46 2 v 26 w Fm(c)807 2340 y Fh(A)834 2334 y Fi(h)p Fm(N)883 2340 y Fh(B)912 2334 y Fi(i)11 b(j)g Fm(c)980 2340 y Fh(B)1009 2334 y Fs(\()p Fm(x)p Fs(\))p Fm(:)p Fj(c)n(ase)17 b Fm(x)c Fj(of)23 b Fi(f)p Fm(y)q Fi(g)1325 2340 y Fh(K)1353 2344 y Fe(AB)1415 2334 y Fj(in)1004 2384 y(let)17 b Fs(\()p Fm(y)1101 2390 y Fr(1)1120 2384 y Fm(;)7 b(y)1159 2390 y Fr(2)1178 2384 y Fm(;)g(y)1217 2390 y Fr(3)1235 2384 y Fs(\))12 b(=)g Fm(y)j Fj(in)1004 2433 y Fs([)p Fm(y)1036 2439 y Fr(2)1064 2433 y Fj(is)d Fm(N)1139 2439 y Fh(B)1168 2433 y Fs(])d Fm(F)d Fs(\()p Fm(y)1258 2439 y Fr(3)1276 2433 y Fs(\))p eop %%Page: 12 12 12 11 bop 493 194 a Fj(Sys)t Fs(\()p Fm(M)613 200 y Fr(1)632 194 y Fm(;)7 b(:)g(:)g(:)e(;)i(M)765 200 y Fh(m)796 194 y Fm(;)g(F)f Fs(\))893 170 y Ff(\001)889 194 y Fs(=)25 b(\()p Fm(\027)s(K)1021 200 y Fh(AB)1074 194 y Fs(\)\(\()1122 163 y Fg(Q)1162 206 y Fh(k)q Fl(2)p Fr(1)p Fh(::m)1271 194 y Fs(\()p Fm(\027)s(N)1344 200 y Fh(A)1370 194 y Fs(\))p Fm(A)p Fs(\()p Fm(N)1466 200 y Fh(A)1494 194 y Fm(;)7 b(M)1553 200 y Fh(k)1573 194 y Fs(\)\))12 b Fi(j)1106 244 y Fs(!\()p Fm(\027)s(N)1191 250 y Fh(B)1219 244 y Fs(\))p Fm(B)r Fs(\()p Fm(N)1317 250 y Fh(B)1347 244 y Fm(;)7 b(F)f Fs(\))o(\))340 324 y(The)20 b(c)o(hannels)g Fm(c)622 330 y Fh(A)668 324 y Fs(and)e Fm(c)771 330 y Fh(B)819 324 y Fs(represen)o(t)j(input)e(c)o(hannels)h(for)f Fm(A)g Fs(and)g Fm(B)r Fs(,)g(resp)q(ectiv)o(ely)m(.)340 374 y(P)o(arameter)d Fm(F)22 b Fs(is)16 b(an)g(abstraction)g(suc)o(h)h (that)f Fm(F)6 b Fs(\()p Fm(M)f Fs(\))16 b(is)g(the)h(b)q(eha)o(viour)f (of)f Fm(B)k Fs(when)e(it)340 424 y(successfully)k(receiv)o(es)g(a)e (message)g Fm(M)5 b Fs(;)18 b(w)o(e)i(assume)f(that)g(the)h(b)q(ound)g (parameters)f(of)340 474 y(the)c(proto)q(col)g(\(including)e(in)h (particular)g Fm(K)1048 480 y Fh(AB)1102 474 y Fs(\))g(do)h(not)f(o)q (ccur)h(free)g(in)f Fm(F)6 b Fs(.)14 b(The)g(pro)q(cess)340 523 y Fj(Sys)t Fs(\()p Fm(M)460 529 y Fr(1)479 523 y Fm(;)7 b(:)g(:)g(:)e(;)i(M)612 529 y Fh(m)643 523 y Fm(;)g(F)f Fs(\))17 b(is)g(a)g(description)h(of)f(a)h(complete)e(system)i(where)g Fm(A)g Fs(sends)h(the)340 573 y(messages)c Fm(M)557 579 y Fr(1)576 573 y Fs(,)f(.)7 b(.)f(.)h(,)14 b Fm(M)724 579 y Fh(m)770 573 y Fs(to)h Fm(B)r Fs(,)f(and)h Fm(B)i Fs(applies)d Fm(F)21 b Fs(to)14 b(the)h(messages)g(that)g(it)f(receiv)o (es.)340 623 y(The)f(restrictions)g(mo)q(del)d(the)j(in)o(tended)g (scop)q(e)g(for)e(the)i(shared)g(k)o(ey)f(and)g(for)f(the)i(nonces.)340 673 y(The)i(replication)g(indicates)g(that)f Fm(B)j Fs(is)e(willing)d (to)j(engage)g(in)f(an)g(arbitrary)h(n)o(um)o(b)q(er)f(of)340 723 y(transmissions.)403 772 y(In)o(tuitiv)o(ely)m(,)9 b(the)i(proto)q(col)g(has)g(an)f(authen)o(ticit)o(y)h(prop)q(ert)o(y:)g (if)g Fm(B)i Fs(accepts)f(a)f(message,)340 822 y(then)j(it)g(is)f(one)g (sen)o(t)i(b)o(y)e Fm(A)p Fs(;)g(moreo)o(v)o(er,)f Fm(B)k Fs(do)q(es)e(not)f(accept)i(message)e(repla)o(ys.)g(In)h(other)340 872 y(w)o(ords,)c(the)h(prop)q(ert)o(y)h(is)e(that)g(if)g Fj(Sys)s Fs(\()p Fm(M)980 878 y Fr(1)999 872 y Fm(;)d(:)g(:)g(:)e(;)i (M)1132 878 y Fh(m)1163 872 y Fm(;)g(F)f Fs(\))k(causes)i(the)e (execution)h(of)f Fm(F)c Fs(\()p Fm(L)1735 878 y Fr(1)1754 872 y Fs(\),)340 922 y(.)h(.)f(.)h(,)13 b Fm(F)6 b Fs(\()p Fm(L)498 928 y Fh(l)511 922 y Fs(\))14 b(then)g Fi(f)p Fm(L)684 928 y Fr(1)703 922 y Fm(;)7 b(:)g(:)g(:)e(;)i(L)824 928 y Fh(l)836 922 y Fi(g)14 b Fs(is)f(a)h(sub-m)o(ultiset)f(of)g Fi(f)p Fm(M)1292 928 y Fr(1)1311 922 y Fm(;)7 b(:)g(:)g(:)e(;)i(M)1444 928 y Fh(m)1475 922 y Fi(g)p Fs(.)403 972 y(This)18 b(authen)o(ticit)o (y)h(prop)q(ert)o(y)g(w)o(ould)f(b)q(e)h(fairly)f(ob)o(vious)g(if)f Fj(Sys)t Fs(\()p Fm(M)1531 978 y Fr(1)1550 972 y Fm(;)7 b(:)g(:)g(:)e(;)i(M)1683 978 y Fh(m)1714 972 y Fm(;)g(F)f Fs(\))340 1021 y(had)16 b(the)h(form)d(\()p Fm(\027)s(p)658 1027 y Fh(k)688 1006 y(k)q Fl(2)p Fr(1)p Fh(::m)796 1021 y Fs(\)\()p Fm(Q)h Fi(j)903 990 y Fg(Q)942 1034 y Fh(k)q Fl(2)p Fr(1)p Fh(::m)1057 1021 y Fm(p)1078 1027 y Fh(k)1099 1021 y Fs(\()p Fm(x)p Fs(\))p Fm(:F)6 b Fs(\()p Fm(M)1256 1027 y Fh(k)1276 1021 y Fs(\)\),)15 b(where)i Fm(Q)f Fs(is)g(a)f(pro)q(cess)j(in-)340 1071 y(dep)q(enden)o(t)d(of)d Fm(F)6 b Fs(.)12 b(The)h(follo)o(wing)d(prop)q(osition)i(establishes)i (that)e Fj(Sys)t Fs(\()p Fm(M)1531 1077 y Fr(1)1550 1071 y Fm(;)7 b(:)g(:)g(:)e(;)i(M)1683 1077 y Fh(m)1714 1071 y Fm(;)g(F)f Fs(\))340 1121 y(is)14 b(in)g(fact)f(equiv)n(alen)o(t)h (to)f(a)h(pro)q(cess)i(of)d(this)h(form:)340 1201 y Fk(Prop)q(osition)5 b(10)15 b(\(Authen)o(ti)o(cit)n(y\).)j Fj(F)m(or)g(any)h(numb)n(er)g Fm(m)g Fj(and)g(distinct)f(names)h Fm(p)1750 1207 y Fr(1)1769 1201 y Fj(,)340 1251 y(.)6 b(.)g(.)g(,)15 b Fm(p)446 1257 y Fh(m)492 1251 y Fj(ther)n(e)g(is)f(a)h(close)n(d)g(pr)n(o)n(c)n (ess)g Fm(Q)f Fj(with)h(fn)s Fs(\()p Fm(Q)p Fs(\))c Fi(\022)h(f)p Fm(p)1277 1257 y Fr(1)1296 1251 y Fm(;)7 b(:)g(:)g(:)t(;)g(p)1409 1257 y Fh(m)1440 1251 y Fm(;)g(c)1477 1257 y Fh(A)1504 1251 y Fm(;)g(c)1541 1257 y Fh(B)1569 1251 y Fi(g)14 b Fj(such)i(that,)340 1301 y(for)f(al)r(l)g(close)n(d)g(terms)g Fm(M)745 1307 y Fr(1)764 1301 y Fj(,)g(.)6 b(.)g(.)g(,)15 b Fm(M)917 1307 y Fh(m)964 1301 y Fj(and)h(al)r(l)f(close)n(d)g(abstr)n (actions)g Fm(F)6 b Fj(,)15 b(if)f Fm(p)1578 1307 y Fr(1)1597 1301 y Fm(;)7 b(:)g(:)g(:)e(;)i(p)1711 1307 y Fh(m)1758 1301 y Fm(=)-25 b Fi(2)340 1351 y Fj(fn)t Fs(\()p Fj(Sys)t Fs(\()p Fm(M)516 1357 y Fr(1)535 1351 y Fm(;)7 b(:)g(:)g(:)t(;)g(M)667 1357 y Fh(m)699 1351 y Fm(;)g(F)f Fs(\)\))14 b Fj(then:)482 1433 y(Sys)t Fs(\()p Fm(M)602 1439 y Fr(1)621 1433 y Fm(;)7 b(:)g(:)g(:)t(;)g(M)753 1439 y Fh(m)785 1433 y Fm(;)g(F)f Fs(\))25 b Fi(')i Fs(\()p Fm(\027)s(p)998 1439 y Fh(k)1027 1416 y(k)q Fl(2)p Fr(1)p Fh(::m)1135 1433 y Fs(\)\()p Fm(Q)12 b Fi(j)1235 1402 y Fg(Q)1274 1445 y Fh(k)q Fl(2)p Fr(1)p Fh(::m)1390 1433 y Fm(p)1411 1439 y Fh(k)1431 1433 y Fs(\()p Fm(x)p Fs(\))p Fm(:F)6 b Fs(\()p Fm(M)1588 1439 y Fh(k)1608 1433 y Fs(\)\))340 1520 y Fj(Pr)n(o)n(of.)20 b Fs(W)m(e)d(only)e(sk)o(etc)o(h)j(the)f(pro) q(of,)f(for)g(brevit)o(y)m(.)g(It)h(dep)q(ends)h(on)e(an)h(analysis)f (of)g(the)340 1570 y(state)g(space)g(of)e(the)i(proto)q(col,)e(and)h (on)f(most)g(of)g(the)i(other)f(prop)q(ositions)g(presen)o(ted)i(in)340 1620 y(this)d(pap)q(er.)g(F)m(or)g(an)g(arbitrary)f(n)o(um)o(b)q(er)h Fm(m)g Fs(and)g(distinct)g(names)f Fm(p)1439 1626 y Fr(1)1457 1620 y Fs(,)h(.)6 b(.)h(.)f(,)13 b Fm(p)1584 1626 y Fh(m)1616 1620 y Fs(,)g(w)o(e)h(set:)520 1706 y Fm(Q)583 1683 y Ff(\001)578 1706 y Fs(=)26 b(\()p Fm(\027)s(K)711 1712 y Fh(AB)764 1706 y Fs(\)\()796 1675 y Fg(Q)835 1719 y Fh(k)q Fl(2)p Fr(1)p Fh(::m)944 1706 y Fs(\()p Fm(\027)s(N)1017 1712 y Fh(A)1044 1706 y Fs(\))p Fm(A)p Fs(\()p Fm(N)1140 1712 y Fh(A)1167 1706 y Fm(;)7 b(p)1207 1712 y Fh(k)1227 1706 y Fs(\))12 b Fi(j)f Fs(!\()p Fm(\027)s(N)1363 1712 y Fh(B)1391 1706 y Fs(\))p Fm(B)r Fs(\()p Fm(N)1489 1712 y Fh(B)1518 1706 y Fm(;)c(G)p Fs(\)\))340 1788 y(where)20 b(the)e(names)g Fm(K)707 1794 y Fh(AB)760 1788 y Fs(,)g Fm(N)823 1794 y Fh(A)850 1788 y Fs(,)g(and)g Fm(N)998 1794 y Fh(B)1045 1788 y Fs(are)h(distinct)f(from)e(one)j(another)f(and) g(from)340 1838 y Fm(p)361 1844 y Fr(1)380 1838 y Fs(,)c(.)6 b(.)g(.)h(,)14 b Fm(p)508 1844 y Fh(m)539 1838 y Fs(,)g Fm(c)583 1844 y Fh(A)610 1838 y Fs(,)f Fm(c)653 1844 y Fh(B)682 1838 y Fs(,)h(and)g(where)h Fm(G)f Fs(is)g(the)h (abstraction)f(\()p Fm(x)p Fs(\))p 1343 1815 24 2 v Fm(x)p Fi(h)p Fs(0)p Fi(i)p Fs(.)f(\(The)i(c)o(hoice)g(of)f(0)f(is)340 1888 y(somewhat)d(arbitrary;)h(an)o(y)f(term)g(with)h(no)f(free)i (names)e(or)h(v)n(ariables)f(w)o(ould)g(do)g(instead.\))340 1938 y(It)j(follo)o(ws)e(that)i Fj(fn)s Fs(\()p Fm(Q)p Fs(\))f(=)g Fi(f)p Fm(p)810 1944 y Fr(1)828 1938 y Fm(;)7 b(:)g(:)g(:)e(;)i(p)942 1944 y Fh(m)973 1938 y Fm(;)g(c)1010 1944 y Fh(A)1036 1938 y Fm(;)g(c)1073 1944 y Fh(B)1101 1938 y Fi(g)p Fs(.)12 b(Consider)h(an)o(y)g(closed)g(terms)f Fm(M)1671 1944 y Fr(1)1690 1938 y Fs(,)g(.)7 b(.)f(.)h(,)340 1988 y Fm(M)380 1994 y Fh(m)412 1988 y Fs(,)19 b(and)g(an)o(y)f(closed) i(abstraction)f Fm(F)25 b Fs(suc)o(h)19 b(that)g(none)h(of)e(the)i (names)e Fm(p)1594 1994 y Fr(1)1613 1988 y Fs(,)g(.)6 b(.)h(.)f(,)19 b Fm(p)1750 1994 y Fh(m)340 2038 y Fs(o)q(ccurs)c(free)g (in)e Fj(Sys)s Fs(\()p Fm(M)715 2044 y Fr(1)734 2038 y Fm(;)7 b(:)g(:)g(:)e(;)i(M)867 2044 y Fh(m)899 2038 y Fm(;)g(F)f Fs(\).)12 b(W)m(e)h(ma)o(y)e(assume)i(that)h(the)g(b)q (ound)f(name)g Fm(K)1728 2044 y Fh(AB)340 2087 y Fs(do)q(es)g(not)e(o)q (ccur)i(free)g(in)e Fm(M)777 2093 y Fr(1)796 2087 y Fs(,)g(.)6 b(.)h(.)f(,)11 b Fm(M)937 2093 y Fh(m)969 2087 y Fs(,)g(or)h Fm(F)6 b Fs(.)k(The)j(righ)o(t-hand)e(side)h(of)f(the)h(prop)q(osition) 340 2137 y(is)i(structurally)g(equiv)n(alen)o(t)g(to:)547 2219 y(\()p Fm(\027)s(K)622 2225 y Fh(AB)675 2219 y Fs(\)\()707 2188 y Fg(Q)746 2232 y Fh(k)q Fl(2)p Fr(1)p Fh(::m)855 2219 y Fs(\()p Fm(\027)s(p)916 2225 y Fh(k)935 2219 y Fs(\)\(\()p Fm(\027)s(N)1040 2225 y Fh(A)1067 2219 y Fs(\))p Fm(A)p Fs(\()p Fm(N)1163 2225 y Fh(A)1191 2219 y Fm(;)7 b(p)1231 2225 y Fh(k)1251 2219 y Fs(\))12 b Fi(j)f Fm(p)1323 2225 y Fh(k)1343 2219 y Fs(\()p Fm(x)p Fs(\))p Fm(:F)6 b Fs(\()p Fm(M)1500 2225 y Fh(k)1520 2219 y Fs(\)\))12 b Fi(j)707 2269 y Fs(!\()p Fm(\027)s(N)792 2275 y Fh(B)820 2269 y Fs(\))p Fm(B)r Fs(\()p Fm(N)918 2275 y Fh(B)948 2269 y Fm(;)7 b(G)p Fs(\))o(\))1728 2219 y(\(1\))340 2350 y(Therefore,)15 b(b)o(y)f(Prop)q(osition)e(4,)h(it)g (su\016ces)j(to)d(sho)o(w)h(that)508 2432 y(\()p Fm(\027)s(K)583 2438 y Fh(AB)636 2432 y Fs(\)\()668 2401 y Fg(Q)708 2444 y Fh(k)q Fl(2)p Fr(1)p Fh(::m)816 2432 y Fs(\()p Fm(\027)s(N)889 2438 y Fh(A)916 2432 y Fs(\))p Fm(A)p Fs(\()p Fm(N)1012 2438 y Fh(A)1040 2432 y Fm(;)7 b(M)1099 2438 y Fh(k)1119 2432 y Fs(\))k Fi(j)1170 2401 y Fg(Q)1209 2444 y Fh(s)p Fl(2)p Fr(1)p Fh(::r)1301 2432 y Fs(\()p Fm(\027)s(N)1374 2438 y Fh(B)1403 2432 y Fs(\))p Fm(B)r Fs(\()p Fm(N)1501 2438 y Fh(B)1530 2432 y Fm(;)c(F)f Fs(\)\))114 b(\(2\))p eop %%Page: 13 13 13 12 bop 183 194 a Fs(and)389 255 y(\()p Fm(\027)s(K)464 261 y Fh(AB)517 255 y Fs(\)\()549 224 y Fg(Q)588 268 y Fh(k)q Fl(2)p Fr(1)p Fh(::m)697 255 y Fs(\()p Fm(\027)s(p)758 261 y Fh(k)778 255 y Fs(\)\(\()p Fm(\027)s(N)883 261 y Fh(A)910 255 y Fs(\))p Fm(A)p Fs(\()p Fm(N)1006 261 y Fh(A)1033 255 y Fm(;)7 b(p)1073 261 y Fh(k)1093 255 y Fs(\))12 b Fi(j)f Fm(p)1165 261 y Fh(k)1185 255 y Fs(\()p Fm(x)p Fs(\))p Fm(:F)6 b Fs(\()p Fm(M)1342 261 y Fh(k)1362 255 y Fs(\)\))12 b Fi(j)549 274 y Fg(Q)588 318 y Fh(s)p Fl(2)p Fr(1)p Fh(::r)681 305 y Fs(\()p Fm(\027)s(N)754 311 y Fh(B)782 305 y Fs(\))p Fm(B)r Fs(\()p Fm(N)880 311 y Fh(B)910 305 y Fm(;)7 b(G)p Fs(\)\))1571 255 y(\(3\))183 387 y(are)18 b(testing)g(equiv)n(alen)o(t)f(for)h(all)e Fm(r)j Fi(\025)f Fs(0.)f(By)i(Prop)q(ositions)12 b(5)17 b(and)c(7)k(\(and)h(via)f(sev)o(eral)183 437 y(small)9 b(formal)h(manipulatio)o(ns\),)f(it)j(su\016ces)h(to)f(pro)o(v)o(e)g (that)g(the)g(follo)o(wing)d(t)o(w)o(o)j(pro)q(cesses)183 487 y(are)i(barb)q(ed)h(equiv)n(alen)o(t:)482 553 y Fg(Q)521 596 y Fh(k)q Fl(2)p Fr(1)p Fh(::m)637 584 y Fm(A)p Fs(\()p Fm(N)717 590 y Fh(Ak)763 584 y Fm(;)7 b(M)822 590 y Fh(k)842 584 y Fs(\))k Fi(j)893 553 y Fg(Q)932 596 y Fh(s)p Fl(2)p Fr(1)p Fh(::r)1031 584 y Fm(B)r Fs(\()p Fm(N)1113 590 y Fh(B)q(s)1159 584 y Fm(;)c(\034)r(:F)f Fs(\))k Fi(j)h Fm(R)247 b Fs(\(4\))230 650 y(\()p Fm(\027)s(p)291 656 y Fh(k)320 635 y(k)q Fl(2)p Fr(1)p Fh(::m)429 650 y Fs(\)\()461 619 y Fg(Q)500 663 y Fh(k)q Fl(2)p Fr(1)p Fh(::m)609 650 y Fs(\()p Fm(A)p Fs(\()p Fm(N)705 656 y Fh(Ak)751 650 y Fm(;)7 b(p)791 656 y Fh(k)810 650 y Fs(\))12 b Fi(j)f Fm(p)882 656 y Fh(k)903 650 y Fs(\()p Fm(x)p Fs(\))p Fm(:F)6 b Fs(\()p Fm(M)1060 656 y Fh(k)1079 650 y Fs(\)\))12 b Fi(j)1146 619 y Fg(Q)1185 663 y Fh(s)p Fl(2)p Fr(1)p Fh(::r)1285 650 y Fm(B)r Fs(\()p Fm(N)1367 656 y Fh(B)q(s)1412 650 y Fm(;)7 b(G)p Fs(\))k Fi(j)g Fm(R)p Fs(\))e(\(5\))183 747 y(where)19 b Fm(N)340 753 y Fh(A)p Fr(1)384 747 y Fs(,)f(.)7 b(.)f(.)g(,)18 b Fm(N)532 753 y Fh(Am)589 747 y Fs(,)g Fm(N)652 753 y Fh(B)q Fr(1)698 747 y Fs(,)g(.)6 b(.)g(.)h(,)18 b Fm(N)846 753 y Fh(B)q(r)909 747 y Fs(are)h(distinct,)g (fresh)g(names,)e(and)h Fm(R)g Fs(is)h(an)183 797 y(arbitrary)11 b(closed)h(pro)q(cess)h(suc)o(h)f(that)f(none)h(of)e(the)i(names)f Fm(K)1167 803 y Fh(AB)1220 797 y Fs(,)g Fm(N)1276 803 y Fh(A)p Fr(1)1320 797 y Fs(,)g(.)6 b(.)h(.)f(,)11 b Fm(N)1454 803 y Fh(Am)1511 797 y Fs(,)g Fm(N)1567 803 y Fh(B)q Fr(1)1612 797 y Fs(,)183 847 y(.)6 b(.)h(.)f(,)13 b Fm(N)296 853 y Fh(B)q(r)341 847 y Fs(,)g Fm(p)387 853 y Fr(1)405 847 y Fs(,)g(.)7 b(.)f(.)h(,)12 b Fm(p)531 853 y Fh(m)576 847 y Fs(o)q(ccurs)j(free)f(in)f Fm(R)p Fs(;)g(and)g(where)h Fm(\034)r(:F)19 b Fs(is)13 b(de\014ned)i(b)o(y)e (\()p Fm(\034)r(:F)6 b Fs(\)\()p Fm(M)f Fs(\))11 b(=)183 897 y(\()p Fm(\027)s(m)p Fs(\)\()p 291 874 37 2 v Fm(m)p Fi(h)p Fs(0)p Fi(i)h(j)f Fm(m)p Fs(\()p Fm(x)p Fs(\))p Fm(:F)6 b Fs(\()p Fm(M)f Fs(\)\))13 b(with)h Fm(m)g Fs(a)g(fresh)g (name)f(and)h Fm(x)f Fs(a)h(fresh)h(v)n(ariable.)245 948 y(The)i(remainder)f(of)g(the)h(pro)q(of)f(consists)i(in)e (constructing)h(a)f(relation)g Fi(S)k Fs(suc)o(h)d(that)183 998 y Fi(\021S)s(\021)g Fs(relates)h(pro)q(cesses)d(\(4\))i(and)c (\(5\),)j(and)h(establishing)f(that)h Fi(S)k Fs(is)16 b(a)h(barb)q(ed)h(bisim-)183 1054 y(ulation)e(up)h(to)455 1031 y Fl(\001)444 1054 y Fi(\030)g Fs(and)h(restriction.)f(It)g(then)h (follo)o(ws)e(that)h(pro)q(cesses)e(\(4\))j(and)12 b(\(5\))17 b(are)183 1104 y(barb)q(ed)f(equiv)n(alen)o(t)e(b)o(y)h(Prop)q(osition) e(6.)h(W)m(e)h(omit)e(the)j(de\014nition)f(of)g Fi(S)j Fs(and)e(its)f(study)m(,)183 1154 y(whic)o(h)e(relies)i(on)f(Prop)q (osition)e(1.)872 b Fc(2)245 1253 y Fs(In)o(tuitiv)o(ely)m(,)12 b(the)j(proto)q(col)f(has)h(a)f(secrecy)i(prop)q(ert)o(y)f(to)q(o:)f (if)f(no)h(information)e(ab)q(out)183 1303 y(the)i(messages)h(is)f(giv) o(en)g(a)o(w)o(a)o(y)f(as)h(they)h(are)g(accepted,)g(then)g(no)f (external)h(observ)o(er)g(can)183 1353 y(iden)o(tify)k(the)i(messages.) e(Ho)o(w)o(ev)o(er,)h(the)h(observ)o(er)g(ma)o(y)e(b)q(e)h(able)g(to)g (tell)g(ho)o(w)f(man)o(y)183 1402 y(messages)g(are)h(transmitted.)e (This)i(secrecy)h(prop)q(ert)o(y)f(is)g(captured)g(in)f(the)h(follo)o (wing)183 1452 y(prop)q(osition:)183 1543 y Fk(Prop)q(ositi)o(on)5 b(11)15 b(\(Secrecy\).)20 b Fj(F)m(or)11 b(any)h(p)n(airs)f(of)h(close) n(d)f(terms)g Fs(\()p Fm(M)1306 1549 y Fr(1)1325 1543 y Fm(;)c(M)1389 1528 y Fl(0)1384 1553 y Fr(1)1402 1543 y Fs(\))p Fj(,)12 b(.)6 b(.)g(.)g(,)11 b Fs(\()p Fm(M)1580 1549 y Fh(m)1612 1543 y Fm(;)183 1593 y(M)228 1578 y Fl(0)223 1603 y Fh(m)254 1593 y Fs(\))k Fj(and)h(any)g(close)n(d)f (abstr)n(action)f Fm(F)6 b Fj(,)14 b(if)h Fm(F)6 b Fs(\()p Fm(M)969 1599 y Fh(i)982 1593 y Fs(\))12 b Fi(')g Fm(F)6 b Fs(\()p Fm(M)1148 1578 y Fl(0)1143 1604 y Fh(i)1159 1593 y Fs(\))15 b Fj(for)f(e)n(ach)h Fm(i)d Fi(2)g Fs(1)p Fm(::m)i Fj(then:)491 1690 y(Sys)s Fs(\()p Fm(M)610 1696 y Fr(1)629 1690 y Fm(;)7 b(:)g(:)g(:)e(;)i(M)762 1696 y Fh(m)794 1690 y Fm(;)g(F)f Fs(\))25 b Fi(')i Fj(Sys)t Fs(\()p Fm(M)1071 1673 y Fl(0)1066 1700 y Fr(1)1085 1690 y Fm(;)7 b(:)g(:)g(:)t(;)g(M)1222 1673 y Fl(0)1217 1700 y Fh(m)1249 1690 y Fm(;)g(F)f Fs(\))183 1791 y Fj(Pr)n(o)n(of.)20 b Fs(Prop)q(osition)12 b(10)h(implies)f(that)325 1888 y Fj(Sys)t Fs(\()p Fm(M)445 1894 y Fr(1)464 1888 y Fm(;)7 b(:)g(:)g(:)e(;)i(M)597 1894 y Fh(m)628 1888 y Fm(;)g(F)f Fs(\))24 b Fi(')i Fs(\()p Fm(\027)s(p)839 1894 y Fh(k)868 1871 y(k)q Fl(2)p Fr(1)p Fh(::m)976 1888 y Fs(\)\()p Fm(Q)12 b Fi(j)1076 1857 y Fg(Q)1115 1901 y Fh(k)q Fl(2)p Fr(1)p Fh(::m)1231 1888 y Fm(p)1252 1894 y Fh(k)1272 1888 y Fs(\()p Fm(x)p Fs(\))p Fm(:F)6 b Fs(\()p Fm(M)1429 1894 y Fh(k)1449 1888 y Fs(\)\))183 1985 y(and)325 2083 y Fj(Sys)t Fs(\()p Fm(M)450 2065 y Fl(0)445 2093 y Fr(1)464 2083 y Fm(;)h(:)g(:)g(:)e(;)i(M)602 2065 y Fl(0)597 2093 y Fh(m)628 2083 y Fm(;)g(F)f Fs(\))24 b Fi(')i Fs(\()p Fm(\027)s(p)839 2089 y Fh(k)868 2065 y(k)q Fl(2)p Fr(1)p Fh(::m)976 2083 y Fs(\)\()p Fm(Q)12 b Fi(j)1076 2051 y Fg(Q)1115 2095 y Fh(k)q Fl(2)p Fr(1)p Fh(::m)1231 2083 y Fm(p)1252 2089 y Fh(k)1272 2083 y Fs(\()p Fm(x)p Fs(\))p Fm(:F)6 b Fs(\()p Fm(M)1434 2067 y Fl(0)1429 2094 y Fh(k)1449 2083 y Fs(\)\))183 2180 y(for)15 b(some)f(pro)q(cess)j Fm(Q)e Fs(and)h(some)e(names)h Fm(p)885 2186 y Fr(1)903 2180 y Fs(,)g(.)6 b(.)h(.)f(,)15 b Fm(p)1033 2186 y Fh(m)1065 2180 y Fs(.)f(Since)i(testing)g(equiv)n(alence)g(is)f(a)183 2229 y(congruence)g(\(b)o(y)f(Prop)q(osition)e(3\),)h(if)g Fm(F)6 b Fs(\()p Fm(M)882 2235 y Fh(i)896 2229 y Fs(\))12 b Fi(')g Fm(F)6 b Fs(\()p Fm(M)1062 2214 y Fl(0)1057 2240 y Fh(i)1073 2229 y Fs(\))14 b(for)f(eac)o(h)i Fm(i)c Fi(2)h Fs(1)p Fm(::m)h Fs(then:)183 2327 y(\()p Fm(\027)s(p)244 2333 y Fh(k)263 2309 y(k)q Fl(2)p Fr(1)p Fh(::m)372 2327 y Fs(\)\()p Fm(Q)e Fi(j)471 2295 y Fg(Q)511 2339 y Fh(k)q Fl(2)p Fr(1)p Fh(::m)626 2327 y Fm(p)647 2333 y Fh(k)667 2327 y Fs(\()p Fm(x)p Fs(\))p Fm(:F)6 b Fs(\()p Fm(M)824 2333 y Fh(k)844 2327 y Fs(\)\))12 b Fi(')g Fs(\()p Fm(\027)s(p)993 2333 y Fh(k)1012 2311 y(k)q Fl(2)p Fr(1)p Fh(::m)1121 2327 y Fs(\)\()p Fm(Q)g Fi(j)1221 2295 y Fg(Q)1260 2339 y Fh(k)q Fl(2)p Fr(1)p Fh(::m)1375 2327 y Fm(p)1396 2333 y Fh(k)1417 2327 y Fs(\()p Fm(x)p Fs(\))p Fm(:F)6 b Fs(\()p Fm(M)1579 2311 y Fl(0)1574 2338 y Fh(k)1593 2327 y Fs(\)\))183 2424 y(The)14 b(claim)e(follo)o(ws)g(b)o(y)i(transitivit)o(y)m(.)808 b Fc(2)p eop %%Page: 14 14 14 13 bop 340 194 a Fn(8)56 b(Conclusions)340 301 y Fs(In)12 b(the)g(last)g(few)g(y)o(ears,)f(the)i(imp)q(ortance)e(of)g(reasoning)g (ab)q(out)h(cryptographic)g(proto)q(cols)340 351 y(has)k(b)q(een)h (widely)e(recognised,)i(and)e(sev)o(eral)h(metho)q(ds)g(ha)o(v)o(e)f(b) q(een)i(used)g(for)e(this)h(task.)340 401 y(Those)21 b(metho)q(ds)e(are)h(based)g(on)f(a)g(large)h(v)n(ariet)o(y)f(of)g (formal)e(framew)o(orks:)h(temp)q(oral)340 451 y(logics,)i(mo)q(dal)e (logics,)h(state-transition)i(mo)q(dels,)e(CSP)h(\(see)i(e.g.)12 b([MCF87)o(,)20 b(BAN89,)340 500 y(Kem89)o(,)e(Mil95a)o(,)g(Mea92)o(,)g (GM95,)g(Lo)o(w96)o(,)g(Sc)o(h96a)o(]\).)g(The)h(main)e(emphasis)g(of)h (that)340 550 y(w)o(ork)c(has)g(b)q(een)h(on)f(authen)o(ticit)o(y)f (prop)q(erties.)403 602 y(Pro)q(ofs)i(in)g(the)g(spi)h(calculus)f(are)g (sometimes)f(more)g(di\016cult)h(than)g(pro)q(ofs)g(in)g(those)340 651 y(earlier)i(framew)o(orks.)f(The)h(sources)h(of)f(this)g (di\016cult)o(y)f(are)h(in)f(part)h(the)h(no)o(v)o(elties)e(and)340 701 y(adv)n(an)o(tages)g(of)f(the)i(spi-calculus)f(approac)o(h:)g(the)g (expressiv)o(e)i(scoping)e(mec)o(hanisms)e(of)340 751 y(the)g(pi)f(calculus;)f(the)i(treatmen)o(t)f(of)f(secrecy)j(prop)q (erties;)f(the)g(view)f(of)f(attac)o(ks)h(as)g(tests,)340 801 y(and)h(the)g(fo)q(cus)f(on)g(testing)h(equiv)n(alence.)f(W)m(e)g (hop)q(e)h(that,)f(through)g(tec)o(hniques)i(suc)o(h)f(as)340 851 y(ours,)g(pro)q(ofs)g(in)g(the)g(spi)g(calculus)g(will)e(b)q(ecome) i(easier,)g(ev)o(en)h(routine.)340 983 y Fk(Ac)o(kno)o(wledgemen)o(ts) 340 1074 y Fs(P)o(aola)f(Quaglia,)f(Stev)o(e)j(Sc)o(hneider,)f(and)g(P) o(eter)h(Sew)o(ell)e(suggested)j(impro)o(v)o(em)o(en)o(ts)c(to)i(a)340 1124 y(draft)f(of)f(this)h(pap)q(er.)340 1266 y Fn(References)340 1369 y Fp([A)o(G97a])34 b(M.)12 b(Abadi)17 b(and)g(A.)12 b(D.)k(Gordon.)26 b(A)16 b(calculus)i(for)e(cryptographic)i(proto)q (cols:)f(The)511 1415 y(spi)e(calculus.)24 b(T)m(o)14 b(app)q(ear)h(in)g(the)g(Pro)q(ceedings)h(of)e(the)h(F)m(ourth)g(A)o (CM)f(Conference)511 1460 y(on)f(Computer)h(and)f(Comm)o(unications)j (Securit)o(y)m(,)e(1997.)340 1508 y([A)o(G97b])32 b(M.)12 b(Abadi)17 b(and)g(A.)12 b(D.)k(Gordon.)26 b(A)16 b(calculus)i(for)e (cryptographic)i(proto)q(cols:)f(The)511 1553 y(spi)12 b(calculus.)19 b(T)m(ec)o(hnical)13 b(Rep)q(ort)f(414,)f(Univ)o(ersit)o (y)j(of)d(Cam)o(bridge)h(Computer)g(Lab-)511 1599 y(oratory)m(,)h(Jan)o (uary)h(1997.)340 1646 y([AN96])53 b(M.)12 b(Abadi)i(and)g(R.)e (Needham.)18 b(Pruden)o(t)c(engineering)i(practice)e(for)f (cryptographic)511 1692 y(proto)q(cols.)18 b Fb(IEEE)12 b(T)m(r)n(ansactions)d(on)i(Softwar)n(e)f(Engine)n(ering)p Fp(,)e(22\(1\):6{15,)j(Jan)o(uary)511 1737 y(1996.)340 1785 y([BAN89])26 b(M.)12 b(Burro)o(ws,)f(M.)h(Abadi,)f(and)g(R.)h(M.)e (Needham.)16 b(A)10 b(logic)i(of)e(authen)o(tication.)19 b Fb(Pr)n(o-)511 1830 y(c)n(e)n(e)n(dings)9 b(of)i(the)f(R)n(oyal)g(So) n(ciety)f(of)i(L)n(ondon)e(A)p Fp(,)h(426:233{271,)h(1989.)17 b(A)10 b(preliminary)511 1876 y(v)o(ersion)k(app)q(eared)g(as)f (Digital)i(Equipmen)o(t)f(Corp)q(oration)h(Systems)e(Researc)o(h)g (Cen-)511 1922 y(ter)g(rep)q(ort)g(No.)g(39,)g(F)m(ebruary)g(1989.)340 1969 y([BB92])57 b(G.)12 b(Berry)h(and)g(G.)f(Boudol.)18 b(The)13 b(c)o(hemical)h(abstract)e(mac)o(hine.)18 b Fb(The)n(or)n(etic)n(al)11 b(Com-)511 2015 y(puter)h(Scienc)n(e)p Fp(,)e(96\(1\):217{248,)k(April)h(1992.)340 2062 y([BN95])55 b(M.)12 b(Boreale)j(and)f(R.)e(De)i(Nicola.)19 b(T)m(esting)14 b(equiv)n(alence)i(for)d(mobile)i(pro)q(cesses.)j Fb(In-)511 2107 y(formation)12 b(and)g(Computation)p Fp(,)e(120\(2\):279{303,)15 b(August)e(1995.)340 2155 y([DES77])35 b(Data)14 b(encryption)h (standard.)k(F)m(ed.)13 b(Inform.)g(Pro)q(cessing)i(Standards)g(Pub.)d (46,)i(Na-)511 2200 y(tional)h(Bureau)f(of)e(Standards,)j(W)m (ashington)g(DC,)e(Jan)o(uary)g(1977.)340 2248 y([DH84])53 b(R.)12 b(De)19 b(Nicola)g(and)g(M.)12 b(C.)g(B.)17 b(Hennessy)m(.)33 b(T)m(esting)19 b(equiv)n(alences)i(for)c(pro)q(cesses.)511 2293 y Fb(The)n(or)n(etic)n(al)11 b(Computer)i(Scienc)n(e)p Fp(,)d(34:83{133,)k(1984.)340 2340 y([GM95])46 b(J.)12 b(Gra)o(y)i(and)h(J.)d(McLean.)22 b(Using)15 b(temp)q(oral)g(logic)h (to)e(sp)q(ecify)i(and)f(v)o(erify)g(crypto-)511 2386 y(graphic)i(proto)q(cols)h(\(progress)e(rep)q(ort\).)25 b(In)16 b Fb(Pr)n(o)n(c)n(e)n(e)n(dings)d(of)j(the)f(8th)g(IEEE)h(Com-) 511 2432 y(puter)c(Se)n(curity)g(F)m(oundations)e(Workshop)p Fp(,)h(pages)i(108{116,)h(1995.)p eop %%Page: 15 15 15 14 bop 183 194 a Fp([Kem89])31 b(R.)13 b(A.)h(Kemmerer.)23 b(Analyzing)18 b(encryption)f(proto)q(cols)g(using)f(formal)g(v)o (eri\014cation)353 239 y(tec)o(hniques.)j Fb(IEEE)14 b(Journal)e(on)h(Sele)n(cte)n(d)e(A)o(r)n(e)n(as)h(in)h(Communic)n (ations)p Fp(,)d(7,)j(1989.)183 285 y([Lie93])59 b(A.)12 b(Liebl.)20 b(Authen)o(tication)c(in)f(distributed)h(systems:)e(A)f (bibliography)m(.)21 b Fb(A)o(CM)15 b(Op-)353 331 y(er)n(ating)d (Systems)g(R)n(eview)p Fp(,)g(27\(4\):31{41,)h(1993.)183 376 y([Lo)o(w96])40 b(G.)12 b(Lo)o(w)o(e.)25 b(Breaking)18 b(and)f(\014xing)g(the)f(Needham-Sc)o(hro)q(eder)i(public-k)o(ey)g (proto)q(col)353 422 y(using)f(FDR.)23 b(In)15 b Fb(T)m(o)n(ols)g(and)f (A)o(lgorithms)g(for)h(the)f(Construction)f(and)h(A)o(nalysis)f(of)353 468 y(Systems)p Fp(,)c(v)o(olume)k(1055)f(of)f Fb(L)n(e)n(ctur)n(e)f (Notes)h(in)g(Computer)g(Scienc)n(e)p Fp(,)e(pages)j(147{166.)353 513 y(Springer)j(V)m(erlag,)e(1996.)183 559 y([MCF87])22 b(J.)12 b(K.)d(Millen,)i(S.)h(C.)d(Clark,)h(and)g(S.)i(B.)d(F)m (reedman.)16 b(The)9 b(In)o(terrogator:)h(Proto)q(col)h(se-)353 605 y(curit)o(y)j(analysis.)19 b Fb(IEEE)13 b(T)m(r)n(ansactions)d(on)j (Softwar)n(e)e(Engine)n(ering)p Fp(,)e(SE-13\(2\):274{)353 650 y(288,)k(F)m(ebruary)h(1987.)183 696 y([Mea92])39 b(C.)12 b(Meado)o(ws.)17 b(Applying)c(formal)f(metho)q(ds)g(to)f(the)g (analysis)i(of)e(a)g(k)o(ey)g(managemen)o(t)353 742 y(proto)q(col.)19 b Fb(Journal)12 b(of)h(Computer)g(Se)n(curity)p Fp(,)d(1\(1\):5{36,)j (1992.)183 787 y([Mil89])55 b(R.)13 b(Milner.)27 b Fb(Communic)n(ation) 14 b(and)i(Concurr)n(ency)p Fp(.)23 b(Pren)o(tice-Hall)18 b(In)o(ternational,)353 833 y(1989.)183 879 y([Mil92])55 b(R.)13 b(Milner.)30 b(F)m(unctions)19 b(as)e(pro)q(cesses.)31 b Fb(Mathematic)n(al)15 b(Structur)n(es)g(in)h(Computer)353 924 y(Scienc)n(e)p Fp(,)10 b(2:119{141,)k(1992.)183 970 y([Mil95a])36 b(J.)12 b(K.)g(Millen.)19 b(The)13 b(In)o(terrogator)g (mo)q(del.)18 b(In)12 b Fb(IEEE)i(Symp)n(osium)d(on)i(Se)n(curity)e (and)353 1016 y(Privacy)p Fp(,)g(pages)j(251{260,)g(1995.)183 1061 y([Mil95b])34 b(R.)13 b(Milner.)28 b(The)16 b Fa(\031)q Fp(-calculus.)30 b(Undergraduate)18 b(lecture)f(notes,)f(Cam)o(bridge)i (Uni-)353 1107 y(v)o(ersit)o(y)m(,)c(1995.)183 1153 y([MPW92])21 b(R.)12 b(Milner,)j(J.)c(P)o(arro)o(w,)i(and)h(D.)e(W)m(alk)o(er.)18 b(A)13 b(calculus)i(of)e(mobile)h(pro)q(cesses,)g(parts)353 1198 y(I)g(and)i(I)q(I.)21 b Fb(Information)12 b(and)i(Computation)p Fp(,)e(pages)j(1{40)g(and)g(41{77,)g(Septem)o(b)q(er)353 1244 y(1992.)183 1290 y([Sc)o(h96a])33 b(S.)13 b(Sc)o(hneider.)18 b(Securit)o(y)12 b(prop)q(erties)g(and)g(CSP.)k(In)11 b Fb(IEEE)g(Symp)n(osium)f(on)h(Se)n(curity)353 1335 y(and)i(Privacy)p Fp(,)e(pages)i(174{187,)h(1996.)183 1381 y([Sc)o(h96b])31 b(B.)13 b(Sc)o(hneier.)19 b Fb(Applie)n(d)12 b(Crypto)n(gr)n(aphy:)f(Pr)n(oto)n(c)n(ols,)h(A)o(lgorithms,)g(and)h (Sour)n(c)n(e)f(Co)n(de)353 1427 y(in)h(C)p Fp(.)k(John)d(Wiley)h(&)d (Sons,)i(Inc.,)e(second)i(edition,)h(1996.)183 2424 y(This)e(article)i (w)o(as)e(pro)q(cessed)h(using)g(the)f(L)810 2415 y Fq(A)827 2424 y Fp(T)849 2432 y(E)870 2424 y(X)f(macro)i(pac)o(k)n(age)g(with)f (LLNCS)g(st)o(yle)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF