(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software %%Title: polemic.dvi %%Pages: 11 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips polemic -t letter -o %DVIPSParameters: dpi=300, compressed %DVIPSSource: TeX output 2004.07.19:1524 %%BeginProcSet: texc.pro %! /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S N}B/A{dup}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{A A 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/IEn 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 IEn N end A{/foo setfont}2 array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/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 A definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get }B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub} B/Cdx{Cd A length 1 sub get}B/Ci{Cd A 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/CharBuilder{save 3 1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx 0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{ rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B /chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{ /cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{ A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse} ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17 {2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{ 1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop} forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{A A length 1 sub A 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 A 1 get A mul exch 0 get A 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/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4 index cvrs cvn put}for pop 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/Rx 0 N/Ry 0 N/V{}B/RV/v{ /Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT) (LaserWriter 16/600)]{A length product length le{A length product exch 0 exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot} imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto fill grestore}B/a{moveto}B/delta 0 N/tail{A/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 (polemic.dvi) @start %DVIPSBitmapFont: Fa cmbx10 10.95 6 /Fa 6 55 df<13381378EA07F812FF12F91201B3A4387FFFE0A2131D7D9C1A>49 DII<14E0130113031307130F A2131B133B137313E3EA01C3EA038313031206120E121C1238127012E0B512FEA2380007 E0A6EBFFFEA2171D7F9C1A>I<001C13E0EA1FFF14C01480140013FC13C00018C7FCA4EA 19FC381FFF80381E07C0381C03E0001813F0120014F8A2127812FC12FEA200FC13F01278 387007E0383C0FC0380FFF00EA03F8151D7E9C1A>I<133F3801FFC03807C0E0EA0F8138 1F03F0121E123E127CEB01E090C7FCEAFC1013FF00FD13C0EB03E038FE01F0A200FC13F8 A4127CA3003C13F0123E381E03E0380F07C03807FF803801FE00151D7E9C1A>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fb cmr9 9 50 /Fb 50 123 df<13FCEA038338060380EA0E07121CEB030090C7FCA4B51280EA1C03AE38 FF8FF0141A809915>12 D34 D<126012F0A212701210A31220A21240A2040B7D830B>44 DI<126012F0A2126004047D830B>I48 D<12035AB4FC1207B3A3EA7FF80D197D9813>I51 D<1318A213381378A213B8EA0138A21202 1204A21208121012301220124012C0B5FCEA0038A6EA03FF10197F9813>I<1240EA7FFF 13FEA2EA4004EA80081310A2EA00201340A213801201A2120313005AA45AA51206101A7E 9813>55 D57 D<126012F0A212601200A8126012F0A2126004107D8F0B>I<130CA3131EA3132FA2EB6F 801347A2EB83C0A3380101E0A3380200F0EA03FFEA0200481378A2000C137C0008133CA2 003C133E39FF01FFC01A1B7F9A1D>65 DI70 D73 D<3807FF8038003C00B2127012 F8A3485AEA4070EA30E0EA0F80111B809914>I<39FF8001FF000F14F0A2380BC002A238 09E004A33808F008A3EB7810A3EB3C20A2EB1E40A3EB0F80A3EB0700A2121C39FF820FFF 201A7F9923>77 DI<137F3801C1C038070070000E7F487FA2487F0078130FA200707F00F01480A8 0070140000785BA20038130E6C5B001E133C000E13386C5B3801C1C0D8007FC7FC191C7E 9A1E>I<007FB5FC38701E0700601301124000C0148000801300A300001400B13803FFF0 191A7F991C>84 D<3AFFC3FF07F03A3E00F801C0001E9038780080A36C90387C0100A339 07809E02A33903C10F04A33901E20788A3D800F613D0EBF403A201FC13F090387801E0A3 90383000C0A3241B7F9927>87 D<12FEA212C0B3AF12FEA207257D9B0B>91 DI<12FEA21206B3 AF12FEA20725809B0B>I97 D<12FC121CA913FCEA1D07381E038038 1C01C0130014E0A6EB01C01480381E0300EA1906EA10F8131A809915>II<133F1307A9 EA03E7EA0C17EA180F487E127012E0A6126012706C5AEA1C373807C7E0131A7F9915>I< EA07C0EA1C30EA30181270EA600C12E0EAFFFCEAE000A41260EA7004EA3808EA1C18EA07 E00E107F8F11>II<1307380FC980EA187138303100EA7038A4EA30306C5AEA2FC00060C7FCA2 1270EA3FF013FC6C7EEA600FEAC003A4EA6006EA381CEA07E011197F9013>I<12FC121C A9137CEA1D87381E0380A2121CAB38FF9FF0141A809915>I<1218123CA212181200A612 FC121CAE12FF081A80990A>I<12FC121CA9EB1FC0EB0F00130C5B13205B13E0121DEA1E 70EA1C7813387F131E7F148038FF9FE0131A809914>107 D<12FC121CB3A6EAFF80091A 80990A>I<38FC7C1F391D8E6380391E0781C0A2001C1301AB39FF9FE7F81D107F8F20>I< EAFC7CEA1D87381E0380A2121CAB38FF9FF01410808F15>IIIII< EA1F20EA60E0EA402012C0A2EAF000127FEA3FC0EA1FE0EA00F0EA8070133012C01320EA F040EA8F800C107F8F0F>I<1208A41218A21238EAFFC0EA3800A81320A41218EA1C40EA 07800B177F960F>I<38FC1F80EA1C03AB1307120CEA0E0B3803F3F01410808F15>I<38FF 0F80383C0700EA1C061304A26C5AA26C5AA3EA03A0A2EA01C0A36C5A11107F8F14>I<39 FE7F1F8039381C0700003C1306381C0C04130E380E16081317A238072310149013A33803 C1A014E0380180C0A319107F8F1C>I<38FE3F80383C1E00EA1C086C5AEA0F306C5A6C5A 12017F1203EA0270487E1208EA181CEA381E38FC3FC012107F8F14>I<38FF0F80383C07 00EA1C061304A26C5AA26C5AA3EA03A0A2EA01C0A36C5AA248C7FC126112F112F25A1278 11177F8F14>II E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fc cmr6 6 3 /Fc 3 52 df<1218127812981218AC12FF08107E8F0F>49 D<123FEA6180EAF0C013E0EA 6060120013E013C0EA0180EA030012065AEA10201220EA7FC012FF0B107F8F0F>I<121F EA2180EA71C0A21231EA0180EA0300121FEA0180EA00C0EA60E012F0A213C0EA6180EA1F 000B107F8F0F>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fd cmr8 8 3 /Fd 3 52 df<1206120E12FE120EB1EAFFE00B157D9412>49 DII E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fe cmtt10 10.95 30 /Fe 30 127 df<387FFFC0B512E0A26C13C013047E8F18>45 D<127812FCA41278060677 8518>I<1303EB0780130FA214005BA2133EA2133C137CA25BA25B1201A2485AA2485AA2 5B120FA248C7FCA2121E123EA25AA2127812F8A25A126011247D9F18>I<127812FCA412 781200A8127812FCA412780614779318>58 D<387F07F038FF87F8387F07F0381C03C0EB 078014005B131E5B133813785B121D7F121F13BC131CEA1E1E130EEA1C0F7F1480130314 C01301387F03F038FF87F8387F03F0151C7F9B18>75 DI82 D97 D<127E12FE127E120EA5133EEB FF80000F13C0EBE3E0EB80F0EB00701478000E1338A5120F14781470EB80F0EBC3E0EBFF C0000E138038067E00151C809B18>II< EB1F80133F131F1303A5EA03F3EA0FFBEA1FFFEA3E1FEA780FEA700712F0EAE003A51307 12F01270EA780FEA3E3F381FFFF0380FFBF83803E3F0151C7E9B18>II<3803F1F03807FFF85A381E1F30383C0F00 EA3807A5EA3C0FEA1E1EEA1FFC485AEA3BF00038C7FC123CEA1FFF14C04813E0387801F0 38F00078481338A36C1378007813F0EA7E03383FFFE0000F13803803FE00151F7F9318> 103 D<127E12FE127E120EA5133FEBFF80000F13C0EBE1E013801300A2120EAA387FC7FC 38FFE7FE387FC7FC171C809B18>II<127E12FE127E120EA5EB3FF0A3EB0780EB0F00131E5B5B5B EA0FF87F139C131EEA0E0FEB0780130314C0387FC7F812FF127F151C7F9B18>107 DI<38FBE3E038FFF7F0EBFFF8383E3E38EA 3C3CA2EA3838AB38FE3E3EEB7E7EEB3E3E1714809318>IIII<3803F380EA0FFBEA1FFFEA3E1FEA780FEA700712F0EAE003 A6EAF0071270EA780FEA3E1FEA1FFFEA0FFBEA03F3EA0003A7EB1FF0EB3FF8EB1FF0151E 7E9318>I<38FF0FC0EB3FF0137FEA07F8EBE060EBC0005BA390C7FCA8EAFFFC7F5B1414 7E9318>II<487E1203A4387F FFC0B5FCA238038000A9144014E0A21381EBC3C0EA01FF6C1380EB7E0013197F9818>I< 387E07E0EAFE0FEA7E07EA0E00AC1301EA0F073807FFFC6C13FE3801FCFC1714809318> I<38FF07F8138F1307383800E0A4381C01C0137113F9A213D9EA1DDD000D1380A3138DEA 0F8FA23807070015147F9318>119 D<387F8FF000FF13F8007F13F0380E01C0EB0380A2 1207EB0700A2EA0387A2138EEA01CEA213CC120013DC1378A31370A313F05B1279EA7BC0 EA7F806CC7FC121E151E7F9318>121 D<383FFFF05AA2387001E0EB03C0EB078038000F 00131E137C5B485A485AEA0780380F0070121E5A5AB512F0A314147F9318>I126 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ff cmsy10 10.95 2 /Ff 2 121 df15 D120 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fg cmmi10 10.95 2 /Fg 2 111 df<48B4EB1FF8A23A001F8003800117EB0100A2903823C002A2EB21E0A290 3841F0041340A2147801805B147C143CA248486C5AA2140FA2000214A01407A2EC03E048 5CA21401120C39FFC00080A2251F7E9E25>78 D<381E0780382318C0EBA0603843C07013 80A2388700E01207A3380E01C0A3EB0382001C1384EB07041408130300381310381801E0 17147E931B>110 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fh cmti10 10.95 39 /Fh 39 122 df<121C123CA41204A21208A212101220A212401280060E7D840E>44 DI<127012F8A212F012E005057B840E>I<13021306A213 0E133C13FCEA03DC131CEA0038A41370A413E0A4EA01C0A4EA0380A4EAFFF8A20F1E7B9D 17>49 D<131FEB7F80EBE1C03801C0E0EA0380EA0700A3380F01C0A2EB83803807C70013 ECEA03F81201487EEA067EEA1C3F487E487E7F12E0A3130EA25B5BEA70F0EA3FE0EA1F80 131F7B9D17>56 D<131FEB7F80EBE1C0EA01C1380380E0EA07005A1301121EA314C0EA1C 03A31307EB0F80120CEA06373803C700EA000F130E131E131C1260EAF0385B485AEAC1C0 EA7F80003EC7FC131F7B9D17>I<1207120F121FA2120E1200AA127012F8A212F012E008 147B930E>I<1407A25C5CA25CA2146FA214CFA2EB018F1303140F13061580EB0C07A213 181338EB3FFF5BEB600713C0A2EA0180A2EA03005A5A397FC03FF800FF137F1D207E9F22 >65 D67 D<48B512FE15FC39001E003C151CA249130CA3 1518EB780CA21500141C495AEBFFF8A2EBF0383801E030A2153015603803C000A215C014 01D8078013801403EC0700141FB6FC5C1F1F7D9E1F>69 D<48B512FC15F839001E007815 38A2491318A31530EB780CA21500141C495AEBFFF8A2EBF0383801E030A44848C7FCA448 5AA4EAFFFC5B1E1F7D9E1E>I<3801FFF8A2D8001EC7FCA35BA45BA45BA4485AA2EC0180 A23903C00300A21406A23807800E5C143C14FCB55AA2191F7D9E1D>76 D<48B4ECFFC0A2D8001F903801F800A2ED037801375C1506150CA20167EB19E0EB638015 31A201C3495A15C3A2EC8183D80183EB8780EC8307A214862703038C0FC7FCA21498EB01 D80006EBF01EA214E0000E13C03AFFE1C3FFE0D9C1835B2A1F7D9E29>I<01FFEB7FE048 ECFFC0D8001FEB1E00EC800CA201375BEB33C0A301635BEB61E0A39038C0F060A31478D8 01805BA2143CA23903003D80141FA300066DC7FCA3120E38FFC006A2231F7D9E22>II<48B5128015E039001E00F015781538 49133CA4491378A215F015E09038F001C0EC07809038FFFE0001F0C7FC485AA4485AA448 5AA4EAFFF85B1E1F7D9E1F>I<903807E04090381FF8C090383C1D80EB700FEBE007EA01 C090388003001203A391C7FCA27F13F86CB47E14E06C6C7E131FEB01F8EB00781438A312 30A21430007013701460007813E0495A38EE0780D8C7FEC7FCEA81F81A217D9F1A>83 D<000FB512FC4814F8391E03C078001814380038141838300780A21260153038C00F00A2 00001400A2131EA45BA45BA45BA31201387FFF80A21E1F799E21>I97 DI< 137EEA01C338030180EA0E07121E001C1300003CC7FC5AA35AA45BEA70031306EA300CEA 1838EA07C011147C9315>I<1478EB03F814F0EB0070A314E0A4EB01C0A213F1EA038D38 070780120E121CEA3C03383807001278A3EAF00EA31430EB1C60A2EA703CEB7CC0EA30CC 380F070015207C9F17>I<137CEA01C338070180120E121C123C38380300EA780EEA7FF8 0078C7FC5AA4EA70015B13066C5AEA1838EA07C011147C9315>I<14F8EB019CEB03BC14 3CEB07181400A2130EA5EBFFE05A38001C00A35BA55BA55BA5485AA4EA3380127B00F3C7 FC1266123C1629829F0E>III<136013F0A213E01300A7120FEA19801231EA21C0EA6380A212 C3EA0700A3120EA3EA1C301360A2EA3840EA18C0EA1980EA0F000C1F7D9E0E>I107 DI<391E07C0F8393318618C9038A032063963E03407EBC03CEB80 3800C7EB780E38070070A3000E495AA3ED3860261C01C013C0A2ED708015313A38038033 00D81801131E23147D9325>I<381E07C038331860EBA030EA63E0EBC038138000C71370 EA0700A3000E13E0A3EB01C3001C13C6A2EB0384EB018C00381398381800F018147D931A >I<137CEA01C338030180000E13C0121E001C13E0123C1278A338F003C0A3EB07801400 EA700F130EEA3018EA1870EA07C013147C9317>I<3801C1E038066618EB7C1CEA0C78EB 701EA2EA18E01200A33801C03CA3143838038078EBC07014E0EBC1C038076380EB1E0090 C7FCA2120EA45AEAFFC05B171D809317>I114 D<13FCEA0306EA0603EA0C0FA213 0E1300EA0F8013F0EA07F8EA03FCEA003E130E1270EAF00CA2EAE008EA6010EA3060EA1F 8010147D9313>II<000F136038198070003113E0EA21C0EA63 80A238C381C0EA0701A3380E0380A3148CEB0718120CA2380E0F30EA06133803E1C01614 7D9318>I<380F01C0EA1983003113E0EA21C1EA6380A200C313C0EA0700A3380E0180A3 EB0300A2130213065B6C5AEA01E013147D9315>I<000F136038198070003113E0EA21C0 EA6380A238C381C0EA0701A3380E0380A4EB0700120CA2EA0E0FEA061EEA03EEEA000EA2 5B12785BEA7030EA6060EA31C0001FC7FC141D7D9316>121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fi cmbxti10 10.95 20 /Fi 20 122 df97 DI<133F 3801FFC03803E3E0EA0F87EA1F0714C0123E387E030090C7FCA25AA5007C1380EB03C038 3E0F80381FFF00EA07F813147C9318>II<137F3801FF8038 07E1C0380F80E0EA1F005A383E01C0387E0780387FFF0013FC00FCC7FCA4127C1480EB03 C0383E0F80381FFF00EA07F813147C9318>I<147CEB01FEEB03DFEB07FF14BFEB0FBE14 9C1480A2EB1F00A33807FFFCA238001F00133EA55BA55BA5485AA4EA39E0127F485AA2EA FB80007FC7FC123C1829819F12>III<137013F81201A213 F0EA00E01300A7EA0780EA1FC0EA39E012331273A2EAE7C01207A2EA0F80A2EA1F00A213 38EA3E70A21360EA3CE0EA1FC0EA0F000D217DA010>I108 D<3A0F03F01F803A1FCFFC7FE03A3BDC3EE1F03973F8 1FC001F0EB80F801E013003AE7C03E01F01207A33A0F807C03E0A3ED07C7261F00F813CE ED0F8E168CED079C001E01F013F8001C9038E001E028147D932B>I<380F03F0381FCFFC 383BDC3E3873F81EEBF01F13E038E7C03E1207A348485AA3ECF8E0391F00F9C0EB01F115 80EB00F3001EEBFF00001C133C1B147D931E>II<3803C1F83807F7FC380EFE1E381CFC1F9038F80F80001D131F1239EA01F0A212 03EC3F0013E0A20007133E147EEBC07C6D5A380FE1F0EBFFC001BFC7FC1380121FA290C8 FCA25AA2EAFFC0A2191D7F931B>I<380F0F80381FDFE0383BF8F0EA73F0EBE1F8A238E7 C3F0EA07C114E0EBC000485AA448C7FCA4121E121C15147D9317>114 D<13FE3803FF80380783C0EA0607120E1480381F030013F0EA0FFC6C7E6C7EC61380EA38 0FEA7C0700FC1300A2EAF80EEA701CEA3FF8EA1FE012147D9316>I<13E0EA01F0A2EA03 E0A4EA07C0A2EAFFFCA2EA0F80A4EA1F00A4123EA3131CEA7C38A21370EA3CE0EA3FC0EA 0F800E1D7C9C12>I<3807801C381FE03C0039137CEA31F01271EA73E000E35BEA07C0A3 380F81F0A3ECF380903883E700A3EB8FEE3807FDFC3801F07819147D931C>I<380780E0 381FE1F0EA39E33831F3F812713873E1F0EAE3E03807C070A3380F80E0A3EB81C0A2EB83 801400EA0786EA03FC6C5A15147D9318>I<3807800E381FE01E0039133EEA31F01271EA 73E000E3137CEA07C0A3380F80F8A4EB81F0A21383EA07873803FFE0EA01FBEA00030008 13C0EA3C07007E1380EB0F00EA7C1E137CEA3FF8EA0FC0171D7D931A>121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fj cmr10 10.95 83 /Fj 83 125 df<90381F83E09038F06E303901C07878380380F8903800F03048EB7000A7 B61280A23907007000B0383FE3FFA21D20809F1B>11 D<133FEBE0C0EA01C0380381E0EA 0701A290C7FCA6B512E0A2EA0700B0383FC3FCA21620809F19>II<90381F81F89038F04F0439 01C07C06390380F80FEB00F05A0270C7FCA6B7FCA23907007007B03A3FE3FE3FE0A22320 809F26>I<127012F8A71270AA1220A51200A5127012F8A3127005217CA00D>33 DI<127012F812FCA212741204A31208A21210A212201240060E7C9F0D>39 D<13401380EA01005A12061204120C5AA212381230A212701260A412E0AC1260A4127012 30A212381218A27E120412067E7EEA008013400A2E7BA112>I<7E12407E12307E120812 0C7EA212077EA213801201A413C0AC1380A412031300A25A1206A25A120812185A12205A 5A0A2E7EA112>I<127012F012F8A212781208A31210A31220A21240050E7C840D>44 DI<127012F8A3127005057C840D>I<14C0A213011480A2130314 005B1306A2130E130CA2131C131813381330A213701360A213E05B12015BA2120390C7FC A25A1206120E120CA2121C1218A21238123012701260A212E05AA2122D7EA117>II<13801203120F12FF12F31203B3A5EA7FFEA20F1E 7C9D17>III<1306A2130E131EA2132E134E13CE138EEA010E1202 1206120412081210A21220124012C0B512F0A238000E00A7EBFFE0A2141E7F9D17>II<137CEA01FE EA0783380E0380EA0C07121C3838030090C7FC12781270A2EAF1F0EAF21CEAF406EAF807 EB0380A200F013C0A51270A214801238EB0700121CEA0E1EEA07FCEA01F0121F7E9D17> I<1240387FFFE0A214C038400040481380EB0100130212005B5BA25B133013201360A213 E05BA21201A41203A66C5A131F7E9D17>III<12 7012F8A312701200AA127012F8A3127005147C930D>I<127012F8A312701200AA127012 F012F8A212781208A31210A31220A21240051D7C930D>I63 D<5B497EA3497EA3EB09E0A3EB10F0A3EB2078A3497EA2EB C03EEB801EEBFFFE487FEB000FA20002EB0780A348EB03C0A2001E14E039FF801FFEA21F 207F9F22>65 DI<90 380FE01090383FFC309038FC0E703803E0033907C000F048C712705A001E14305A151012 7C127800F81400A9127C1510123C123E001E1420121F6C1460D807C013C03903E0018039 00FC0700EB3FFCEB0FF01C217E9F21>III< B61280A2380780071401A2140015C01540A21420A21500146014E013FFA2138014601420 A391C7FCA8EAFFFEA21A1F7F9E1E>I<90380FE02090387FF8609038F80CE03803E00238 07800148C7FC5A001E14605A1520127C127800F81400A7EC7FFCA20078EB01E0127C123C A27E121F7E380780033803E0023900F80C6090387FF82090380FE0001E217D9F24>I<39 FFF07FF8A2390F000780AC90B5FCA2EB0007AD39FFF07FF8A21D1F7E9E22>II<3807FFC0A238001E00B3A3122012F8A3EAF01CEA 403CEA6038EA1070EA0FC012207F9E17>I<39FFF007FCA2390F0003C0EC010014025C5C 5C5C5C5C49C7FC5B497E130FEB13C0EB21E01341EB80F0EB0078A28080A280EC0780A2EC 03C015E039FFF01FFEA21F1F7E9E23>IIIIIIII<3803F040380F FCC0EA1C0FEA3803EA7001EA600012E01440A36C13007E127CEA7F80EA3FF86CB4FC0007 1380C613C0EB1FE01303130014F014707EA37E14E07E38F001C038FE038038C7FF00EA81 FC14217E9F19>I<007FB512E0A238780F010060EB006000401420A200C0143000801410 A400001400B23803FFFCA21C1F7E9E21>I<39FFF00FF8A2390F0001C0EC0080B3A36CEB 0100138000035BEBC0023801E00C3800F838EB3FF0EB0FC01D207E9E22>I<39FFF003FE A2000FC7127015606C6C1340A36C6C1380A2EBE00100011400A23800F002A213F8EB7804 A26D5AA36D5AA2131F6D5AA2EB07C0A36D5AA36DC7FC1F207F9E22>I<3BFFF07FF81FF0 A23B1F00078003806CED010015C001805C00071502EC09E013C000035DEC19F01410D801 E05CA2EC2078D800F05CA2EC403C01785CA2EC801E017C1460013C144090383D000F133F 6D5CA2011E1307010E91C7FCA2010C7F010413022C207F9E2F>I<397FF81FF8A23907C0 07800003EB0200EBE0063801F00400005BEBF818EB78106D5AEB3E60EB1E406D5AA21307 6D7E497E1305EB08F0EB18F8EB1078EB207CEB603EEB401EEB801F3901000F8014070002 14C0000F14E039FFC01FFEA21F1F7F9E22>I<39FFF001FFA2390F800070000714606D13 40000314807F3901F001001200EBF802EB7C06EB3C04EB3E08131EEB1F10EB0FB0EB07A0 14E06D5AABEB3FFCA2201F7F9E22>I<12FFA212C0B3B3A512FFA2082D7CA10D>91 DI<12FFA21203B3B3A512FFA2082D80A10D>I<120812101220A21240A21280A312B812 FCA2127C1238060E7D9F0D>96 DI<121C12FCA2 121CA9137CEA1D87381E0180EB00C0001C13E01470A21478A6147014F014E0001E13C038 1A018038198700EA107C15207E9F19>IIII<137CEA01C6EA030F1207EA0E 061300A7EAFFF0A2EA0E00B0EA7FE0A21020809F0E>I<14E03803E330EA0E3CEA1C1C38 380E00EA780FA5EA380E6C5AEA1E38EA33E00020C7FCA21230A2EA3FFE381FFF8014C038 3001E038600070481330A4006013606C13C0381C03803803FC00141F7F9417>I<121C12 FCA2121CA9137C1386EA1D03001E1380A2121CAD38FF8FF0A214207E9F19>I<1238127C A31238C7FCA6121C12FCA2121CAFEAFF80A2091F7F9E0C>I<13E0EA01F0A3EA00E01300 A61370EA07F0A212001370B3A21260EAF06013C0EA6180EA3F000C28829E0E>I<121C12 FCA2121CA9EB1FE0A2EB0F0013045B5B5B136013E0EA1DF0EA1E70EA1C38133C131C7F13 0F7F148038FF9FF0A214207E9F18>I<121C12FCA2121CB3A9EAFF80A209207F9F0C>I<39 1C3E03E039FCC30C3039FD019018001EEBE01CA2001C13C0AD3AFF8FF8FF80A221147E93 26>IIII<38 01F04038070CC0EA0E02EA1C03EA38011278127012F0A6127012781238EA1C03EA0C05EA 0709EA01F1EA0001A7EB0FF8A2151D7F9318>III<1202A412 06A2120EA2EA3FF812FFEA0E00AA1304A5EA07081203EA01F00E1C7F9B12>I<381C0380 EAFC1FA2EA1C03AD1307120C38061BF0EA03E314147E9319>I<38FF83F8A2381C00E06C 13C01480A238070100A21383EA0382A2EA01C4A213E4EA00E8A21370A3132015147F9318 >I<39FF9FE1FCA2391C0380701560000E1440A214C0D80704138014E0A2390388610014 71A23801D032143A143E3800E01CA2EB6018EB40081E147F9321>I<38FF87F8A2380E03 801400EA0702EA0384EA01C813D8EA00F01370137813F8139CEA010E1202EA0607380403 80001C13C038FE07FCA216147F9318>I<38FF83F8A2381C00E06C13C01480A238070100 A21383EA0382A2EA01C4A213E4EA00E8A21370A31320A25BA3EAF080A200F1C7FC126212 3C151D7F9318>IIII E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fk cmbx12 14.4 39 /Fk 39 122 df<49B4FC011F13C090387F81E0EBFC013901F807F01203EA07F0A4EC01C0 91C8FCA3EC3FF8B6FCA33807F003B3A33A7FFF3FFF80A3212A7FA925>12 D<903A01FF807FE0010F9038C3FFF8903A7F81FFE07CD9FE01EB803C3B01F803FE00FE12 034848485AA21403A20201143894C7FCA3EE07FFB9FCA33B07F001FC007FB3A33C7FFF1F FFC7FFF0A3342A7FA938>14 D<130E131E137EEA07FE12FFA212F81200B3ABB512FEA317 277BA622>49 DII<140FA25C5C5C5C5BA2EB 03BFEB073F130E131C133C1338137013E0EA01C0EA038012071300120E5A5A5A12F0B612 F8A3C7EA7F00A890381FFFF8A31D277EA622>I<00181303381F801FEBFFFE5C5C5C5C14 8049C7FC001CC8FCA6EB7FC0381DFFF8381F80FC381E003F121CC7EA1F8015C0A215E0A2 1218127C12FEA315C05A0078EB3F80A26CEB7F00381F01FE6CB45A000313F0C613801B27 7DA622>II< 1238123E003FB512F0A34814E015C0A215803970000F00141E5C48133814785CC6485A49 5A5C130749C7FCA25B131E133EA2137EA2137C13FCA41201A8EA00701C297CA822>I<48 B4FC000F13E0381E03F0383801F8387800FC00FC13FE7EA3127C003813FCEA0001EB03F8 EB07E0EB0FC01480EB1E00A25B1338A25BA790C7FCA51370EA01FC487EA56C5AEA007017 2A7CA920>63 D<91387FE003903903FFFC07011FEBFF0F90397FF00FDF9039FF8001FF48 48C7FC4848147FD807F0143F000F151F485A160F485A1607127F5B160012FFA9127FA26D 1407123FA26C7E160E6C7E0007151CD803FC143C6C6C14783A00FF8001F090397FF007C0 011FB512800103EBFE009038007FF028297CA831>67 DI73 D77 D79 DI82 D<9038FF80600003EBF0E0000F13F9381F80FF383F001F003E1307481303 A200FC1301A214007EA26C140013C0EA7FFCEBFFE06C13F86C13FE80000714806C14C0C6 FC010F13E0EB007FEC1FF0140F140700E01303A46C14E0A26C13076C14C0B4EB0F80EBE0 3F39F3FFFE0000E15B38C01FF01C297CA825>I<007FB71280A39039807F807FD87C0014 0F00781507A20070150300F016C0A2481501A5C791C7FCB3A490B612C0A32A287EA72F> I86 DI<3803FF80000F13F0381F01FC383F80FE147F801580EA1F00C7FCA314FF13 7F3803FFBF380FF03FEA1F80EA3F00127E5AA46C137F007EEBDFC0393F839FFC381FFF0F 3803FC031E1B7E9A21>97 DIIIII< EAFFE0A3120FAC14FE9038E3FF809038E70FC001EC13E0EBF80715F013F0A213E0B039FF FE3FFFA3202A7DA925>104 D<1207EA1FC0EA3FE0A5EA1FC0EA0700C7FCA7EAFFE0A312 0FB3A3EAFFFEA30F2B7EAA12>I108 D<26FFC07FEB1FC0903AC1FFC07FF0903AC707E1C1F8D80FCC9038F301FC9039D803F600 03FE7F01F05BA201E05BB03CFFFE3FFF8FFFE0A3331B7D9A38>I<38FFC0FE9038C3FF80 9038C70FC0D80FCC13E0EBD80715F013F0A213E0B039FFFE3FFFA3201B7D9A25>II<38FFC1F0EBC7FCEBCE3E380FDC7F13D813F0A2143EEBE000B0B5FCA3181B7F9A 1B>114 D<3803FE30380FFFF0EA3E03EA7800127000F01370A27E00FE1300EAFFE06CB4 FC14C06C13E06C13F0000713F8C6FCEB07FC130000E0137C143C7E14387E6C137038FF01 E038F7FFC000C11300161B7E9A1B>I<13E0A41201A31203A21207120F381FFFE0B5FCA2 380FE000AD1470A73807F0E0000313C03801FF8038007F0014267FA51A>I<39FFE07FF0 A3000F1307B2140FA20007131F3903F077FF3801FFE738007F87201B7D9A25>I<39FFFC 03FFA3390FF000F0000714E07F0003EB01C0A2EBFC0300011480EBFE070000140013FFEB 7F0EA2149EEB3F9C14FC6D5AA26D5AA36D5AA26D5AA2201B7F9A23>I<39FFFC03FFA339 0FF000F0000714E07F0003EB01C0A2EBFC0300011480EBFE070000140013FFEB7F0EA214 9EEB3F9C14FC6D5AA26D5AA36D5AA26D5AA25CA21307003890C7FCEA7C0FEAFE0E131E13 1C5BEA74F0EA3FE0EA0F8020277F9A23>121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fl cmtt12 12 15 /Fl 15 120 df<127812FCA41278060676851A>46 D<137E3801FF804813C03807C3E0EA 0F00381E0FF0EA3C3FEA387F387879F8EA70F038F0E07812E1EBC038A6EBE07800F01370 3870F0F0387879E0EA387F383C3FC0381E0F00380F00383807C1F8EA03FF6C13E038007F 80151E7E9D1A>64 D97 D<3801FF80000713C04813E0EA1F01383C00C0481300127012F05AA57E1270007813707E 381F01F0380FFFE06C13C00001130014157D941A>99 DII105 D108 D110 DI<387F83F838FF8FFEEA7FBF3803FE1EEBF80CEBE000A25BA25BA9EA7FFF B5FC7E17157F941A>114 D<380FFB80EA3FFF5AEAF80FEAE003A300F8C7FCEA7FC0EA3F FCEA0FFF38007F80EB07C0EA600112E012F0130338FC0F80B512005BEAE7F812157C941A >I<487E1203A6387FFFE0B5FCA238038000AA1470A314F0EBE1E0EA01FF6C13C0EB3F00 141C7F9B1A>I<387E07E0EAFE0FEA7E07EA0E00AC1301A2EA0F073807FFFC6C13FE3801 FCFC17157F941A>I<38FF83FEA338380038A26C1370A31338137CA2380C6C60380EEEE0 A413C6000613C0EA07C71383A217157F941A>119 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fm cmr12 12 38 /Fm 38 122 df<127012F812FCA212741204A41208A21210A212201240060F7C840E>44 D<127012F8A3127005057C840E>46 D48 D<13801203120F12FF12F31203B3A8EAFFFEA20F217CA018>III<1303A25B5BA213171337132713 4713C71387EA0107120312021204120C1208121012301220124012C0B512F8A238000700 A7EB7FF0A215217FA018>I57 D<903807E01090383FF830EBFC0E39 01E003703903C001F03807800048C71270121E15305AA2007C14101278A200F81400A812 781510127C123CA26C1420A26C14406C7E6C6C13803901E003003800FC0EEB3FFCEB07E0 1C247DA223>67 DI<903807F00890383FFC18EBFC063901F001383903C000F84848137848C71238121E15 185AA2007C1408A2127800F81400A7EC1FFF1278007CEB0078A2123CA27E121F7E6C7E6C 6C13B83801F0013900FC071890383FFC08903807F00020247DA226>71 D<3803FFE0A238000F00B3A6127012F8A2130EEAF01EEA401C6C5AEA1870EA07C013237E A119>74 D76 D<39FF8007FF13C00007EB0070D805E01320EA04F0A21378137C133C7F131F7F EB0780A2EB03C0EB01E0A2EB00F014F81478143C143E141E140FA2EC07A0EC03E0A21401 A21400000E1460EAFFE0152020227EA125>78 DI82 D<3803F020380FFC60EA1C0E383803E0EA7000A2481360 A21420A36C1300A21278127FEA3FF0EA1FFE6C7E0003138038003FC0EB07E01301EB00F0 A214707EA46C136014E06C13C0EAF80138CE038038C7FF00EA81FC14247DA21B>I<39FF FC07FFA239078000701520B3A5000314407FA2000114803800E0019038700300EB3C0EEB 1FF8EB03F020237EA125>85 D<3BFFF03FFC03FEA23B1F0003E000F86C4A13206E7ED807 801540A24A7E2603C0021480A39039E004780100011600A2EC083CD800F01402A2EC101E 01785CA2EC200F013C5CA20260138890391E400790A216D090391F8003F0010F5CA2EC00 016D5CA20106130001025C2F237FA132>87 D97 D99 D<14E0130FA213011300AAEA01F8EA 0704EA0C02EA1C01EA38001278127012F0A7127012781238EA1801380C02F038070CFEEA 01F017237EA21B>II<133E13 E33801C780EA0387130748C7FCA9EAFFF8A20007C7FCB1EA7FF0A2112380A20F>I<1470 3803F198380E1E18EA1C0E38380700A200781380A400381300A2EA1C0EEA1E1CEA33F000 20C7FCA212301238EA3FFE381FFFC06C13E0383000F0481330481318A400601330A20038 13E0380E03803803FE0015217F9518>I<120E12FEA2121E120EAAEB1F80EB60C0EB80E0 380F0070A2120EAE38FFE7FFA218237FA21B>I<121C123EA3121CC7FCA8120E127EA212 1E120EAFEAFFC0A20A227FA10E>I<120E12FEA2121E120EB3ABEAFFE0A20B237FA20E> 108 D<390E1FC07F3AFE60E183809039807201C03A1F003C00E07E000E1338AE3AFFE3FF 8FFEA227157F942A>I<380E1F8038FE60C0EB80E0381F00707E120EAE38FFE7FFA21815 7F941B>III114 DI<12 02A51206A3120E121EEA3FFC12FFEA0E00AA1304A6EA07081203EA01F00E1F7F9E13>I< 000E137038FE07F0A2EA1E00000E1370AC14F0A2380601783803827FEA00FC18157F941B >I<38FF80FEA2381E0078000E1320A26C1340A2EB80C000031380A23801C100A2EA00E2 A31374A21338A3131017157F941A>I<38FF80FEA2381E0078000E1320A26C1340A2EB80 C000031380A23801C100A2EA00E2A31374A21338A31310A25BA35B12F05B12F10043C7FC 123C171F7F941A>121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fn cmr17 17.28 22 /Fn 22 122 df<1403A34A7EA24A7EA3EC17E01413A2EC23F01421A2EC40F8A3EC807CA2 903801007E153EA20102133F81A2496D7EA3496D7EA2011880011FB5FCA29039200003F0 1501A2496D7EA349147CA20001157E90C8123EA248153F825AD81F80EC3F80D8FFE09038 01FFFCA22E327EB132>65 D<91381FE001903901FFF803903807F00E90390F800307013E C712C749144F49143F4848141F4848140F485A491407120F48C81203A25A003E1501A212 7EA2007C150012FCAB127C127E1601123EA2123F7E16026C7E000715066D14046C6C140C 6C6C14086C6C1410017C14206D14C090390F800180903907F00F00903801FFFC9038001F E028337CB130>67 D78 D80 D<90387F80203901FFE0603807C078390F001C E0001E130648130300381301007813001270156012F0A21520A37E1500127C127E7E13C0 EA1FF86CB47E6C13F06C13FCC613FF010F1380010013C0EC1FE01407EC03F01401140015 F8A26C1478A57E15706C14F015E07E6CEB01C000ECEB038000E7EB070038C1F01E38C07F FC38800FF01D337CB125>83 D<13FE380303C0380C00E00010137080003C133C003E131C 141EA21208C7FCA3EB0FFEEBFC1EEA03E0EA0F80EA1F00123E123C127C481404A3143EA2 1278007C135E6CEB8F08390F0307F03903FC03E01E1F7D9E21>97 D99 D101 DI<15F090387F03083901C1 C41C380380E8390700700848EB7800001E7FA2003E133EA6001E133CA26C5B6C13706D5A 3809C1C0D8087FC7FC0018C8FCA5121C7E380FFFF86C13FF6C1480390E000FC00018EB01 E048EB00F000701470481438A500701470A26C14E06CEB01C00007EB07003801C01C3800 3FE01E2F7E9F21>II<120FEA1F80A4EA 0F00C7FCABEA0780127FA2120F1207B3A6EA0FC0EAFFF8A20D307EAF12>I108 D<260780FEEB1FC03BFF830780 60F0903A8C03C180783B0F9001E2003CD807A013E4DA00F47F01C013F8A2495BB3A2486C 486C133F3CFFFC1FFF83FFF0A2341F7E9E38>I<380780FE39FF83078090388C03C0390F 9001E0EA07A06E7E13C0A25BB3A2486C487E3AFFFC1FFF80A2211F7E9E25>II<380781FC39FF86078090388801C0390F9000E0D807A0137001C0 1378497F153E151E151FA2811680A716005DA2151E153E153C6D5B01A013705D90389803 C0D9860FC7FCEB81F80180C8FCAB487EEAFFFCA2212D7E9E25>I<380783E038FF8418EB 887CEA0F90EA07A01438EBC000A35BB3487EEAFFFEA2161F7E9E19>114 D<3801FC10380E0330381800F048137048133012E01410A37E6C1300127EEA3FF06CB4FC 6C13C0000313E038003FF0EB01F813006C133CA2141C7EA27E14186C1338143000EC1360 38C301C03880FE00161F7E9E1A>I<1340A513C0A31201A212031207120F381FFFE0B5FC 3803C000B01410A80001132013E000001340EB78C0EB1F00142C7FAB19>II121 D E %EndDVIPSBitmapFont end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%BeginPaperSize: Letter letter %%EndPaperSize %%EndSetup %%Page: 1 1 1 0 bop 273 469 a Fn(A)22 b(P)n(olemic)f(on)g(Notions)g(of)g (Cryptographic)g(Securit)n(y)767 595 y Fm(Douglas)c(R.)f(Stinson)674 653 y(Sc)o(ho)q(ol)g(of)h(Computer)e(Science)729 711 y(Univ)o(ersit)o(y)f(of)j(W)l(aterlo)q(o)576 769 y(W)l(aterlo)q(o)g(On) o(tario,)f(N2L)g(3G1,)h(Canada)702 827 y Fl(dstinson@uw)o(at)o(erl)o (oo.)o(ca)829 929 y Fm(July)f(19,)h(2004)224 1122 y Fk(1)67 b(In)n(tro)r(duction)224 1224 y Fj(Koblitz)19 b(and)f(Menezes)g([8])f (ha)o(v)o(e)g(recen)o(tly)i(written)e(a)h(v)o(ery)f(in)o(teresting)h (pap)q(er)h(on)224 1280 y(the)c(topic)h(of)e(pro)o(v)m(able)i(securit)o (y)f(in)h(cryptograph)o(y)l(.)j(Their)d(pap)q(er)f(presen)o(ts)g(cogen) o(t)224 1336 y(summaries)j(of)f(sev)o(eral)h(imp)q(ortan)o(t)f(pro)o(v) m(able)i(securit)o(y)f(results.)27 b(In)18 b(addition,)h(the)224 1393 y(pap)q(er)g(pro)o(vides)g(some)g(in)o(teresting)g(and)g(insigh)o (tful)h(commen)o(tary)e(on)g(the)h(role)g(of)224 1449 y(pro)o(v)m(able)d(securit)o(y)g(in)g(cryptograph)o(y)l(.)295 1506 y(In)k(this)h(essa)o(y)l(,)f(I)g(will)i(address)e(some)g(of)f(the) h(p)q(oin)o(ts)h(raised)f(b)o(y)g(Koblitz)h(and)224 1562 y(Menezes)d(\(and)f(some)g(related)g(issues\).)27 b(I)17 b(ha)o(v)o(e)g(en)o(titled)h(this)g(pap)q(er)f(a)g(\\p)q(olemic")224 1619 y(b)q(ecause)f(man)o(y)e(of)g(the)g(topics)h(to)f(b)q(e)h (considered)h(are)e(of)g(a)h(con)o(tro)o(v)o(ersial)f(nature.)19 b(I)224 1675 y(hop)q(e)14 b(that)f(further)h(discussion)h(and)e (consideration)i(of)e(these)h(issues)g(will)h(b)q(e)g(under-)224 1732 y(tak)o(en)g(b)o(y)g(the)g(cryptographic)h(researc)o(h)f(comm)o (unit)o(y)l(.)295 1788 y(The)f(rest)g(of)g(this)g(pap)q(er)h(is)g (organized)g(as)f(follo)o(ws.)19 b(In)c(Section)g(2,)f(I)g(giv)o(e)h(a) f(v)o(ery)224 1845 y(informal)19 b(and)g(non-tec)o(hnical)i(discussion) f(of)e(cryptographic)h(securit)o(y)g(in)h(general)224 1901 y(and)c(pro)o(v)m(able)g(securit)o(y)g(in)h(particular.)k(Section) c(3)e(discusses)i(p)q(ossible)g(in)o(terpreta-)224 1957 y(tions)g(of)g(pro)o(v)m(able)h(securit)o(y)g(pro)q(ofs.)25 b(Then,)17 b(Section)i(4)d(addresses)i(the)f(particular)224 2014 y(issue)i(of)f(the)g(random)f(oracle)i(mo)q(del)g(in)g(pro)o(v)m (able)f(securit)o(y)l(.)29 b(Section)19 b(5)f(concerns)224 2070 y(one)f(asp)q(ect)g(of)f(the)g(dissemination)j(of)d(cryptographic) h(researc)o(h)f(that)g(I)h(feel)g(is)g(the)224 2127 y(source)f(of)g (some)g(of)g(the)g(credibili)q(t)o(y)i(problems)f(that)f(ha)o(v)o(e)f (arisen)i(in)g(recen)o(t)g(y)o(ears,)224 2183 y(namely)g(the)g(o)o(v)o (er-reliance)h(of)e(conference)i(pro)q(ceedings)g(for)e(publication)j (of)d(cryp-)224 2240 y(tographic)d(researc)o(h.)19 b(Section)13 b(6)g(p)q(oin)o(ts)g(out)g(the)f(problems)i(and)f(c)o(hallenges)h (caused)224 2296 y(b)o(y)g(de\014nitional)i(di\016culties)g(in)e (cryptograph)o(y)l(.)19 b(Finally)l(,)c(Section)g(7)e(is)h(a)g(brief)g (sum-)224 2353 y(mary)l(.)960 2613 y(1)p eop %%Page: 2 2 2 1 bop 224 286 a Fk(2)67 b(What)23 b(is)g(Pro)n(v)l(able)g(Securit)n (y?)224 388 y Fj(V)l(arious)14 b(lev)o(els)h(of)e(securit)o(y)h(are)f (considered)i(in)f(cryptograph)o(y)l(.)19 b(W)l(e)13 b(de\014ne)i(some)e(of)224 444 y(the)i(most)g(useful)h(criteria)g(no)o (w;)e(these)i(de\014nitions)h(are)d(adapted)i(from)e([9].)224 520 y Fi(c)m(omputational)j(se)m(curity)338 591 y Fj(This)i(measure)g (concerns)h(the)f(computational)g(e\013ort)f(required)i(to)f(break)g(a) 338 648 y(cryptosystem.)g(W)l(e)c(migh)o(t)f(de\014ne)i(a)f (cryptosystem)f(to)g(b)q(e)i Fh(c)n(omputational)r(ly)338 704 y(se)n(cur)n(e)k Fj(if)d(the)h(b)q(est)f(algorithm)h(for)e (breaking)i(it)f(requires)h(at)f(least)g Fg(N)22 b Fj(op)q(er-)338 761 y(ations,)d(where)f Fg(N)23 b Fj(is)c(some)f(sp)q(eci\014ed,)j(v)o (ery)e(large)f(n)o(um)o(b)q(er.)30 b(The)19 b(problem)338 817 y(is)f(that)g(no)g(kno)o(wn)g(practical)h(cryptosystem)e(can)h(b)q (e)h(pro)o(v)o(ed)f(to)f(b)q(e)i(secure)338 874 y(under)i(this)f (de\014nition.)36 b(In)21 b(practice,)g(p)q(eople)h(often)e(study)g (the)g(computa-)338 930 y(tional)14 b(securit)o(y)g(of)f(a)h (cryptosystem)f(with)h(resp)q(ect)g(to)f(certain)h(sp)q(eci\014c)i(t)o (yp)q(es)338 987 y(of)j(attac)o(ks.)30 b(F)l(or)18 b(example,)j(it)e (is)h(meaningful)g(to)f(sa)o(y)f(that)h(the)g(Adv)m(anced)338 1043 y(Encryption)14 b(Standard)f(is)h(secure)g(against)f(an)g (exhaustiv)o(e)h(k)o(ey)f(searc)o(h)h(at)e(the)338 1100 y(presen)o(t)g(time)h(and)f(for)g(the)g(foreseeable)h(future.)19 b(Of)13 b(course,)f(securit)o(y)h(against)338 1156 y(one)18 b(sp)q(eci\014c)i(t)o(yp)q(e)e(of)g(attac)o(k)f(do)q(es)h(not)g(guaran) o(tee)g(securit)o(y)g(against)g(some)338 1212 y(other)d(t)o(yp)q(e)g (of)g(attac)o(k.)224 1299 y Fi(pr)m(ovable)k(se)m(curity)338 1370 y Fj(Another)e(w)o(a)o(y)e(to)i(pro)o(vide)g(evidence)i(of)d (securit)o(y)i(is)f(b)o(y)g(reducing)h(the)f(secu-)338 1427 y(rit)o(y)11 b(of)g(the)g(cryptosystem)g(to)f(some)h(w)o (ell-studied)j(underlying)f(mathematical)338 1483 y(problem)g(that)f (is)h(b)q(eliev)o(ed)i(to)c(b)q(e)j(di\016cult)g(to)d(solv)o(e.)20 b(F)l(or)11 b(example,)j(it)f(is)g(easy)338 1540 y(to)18 b(pro)o(v)o(e)g(a)h(statemen)o(t)f(of)g(the)h(t)o(yp)q(e)g(\\the)f (Rabin)i(cryptosystem)e(is)h(secure)338 1596 y(\(with)h(resep)q(ct)g (to)f(ciphertext)i(decryption\))g(if)f(the)g(mo)q(dulus)h Fg(n)f Fj(cannot)g(b)q(e)338 1653 y(factored.")f(Cryptosystems)14 b(of)h(this)h(t)o(yp)q(e)f(are)g(sometimes)g(termed)h Fh(pr)n(ovably)338 1709 y(se)n(cur)n(e)p Fj(,)f(but)g(it)h(m)o(ust)g(b) q(e)g(understo)q(o)q(d)h(that)e(this)h(approac)o(h)f(only)i(pro)o (vides)f(a)338 1766 y(pro)q(of)g(of)g(securit)o(y)h(relativ)o(e)h(to)e (some)g(other)g(problem,)i(whic)o(h)f(is)h(not)e(an)g(ab-)338 1822 y(solute)g(pro)q(of)g(of)f(securit)o(y)l(.)23 b(In)16 b(the)g(example)h(men)o(tioned)g(ab)q(o)o(v)o(e,)e(there)h(is)h(no)338 1879 y(curren)o(tly)12 b(kno)o(wn)f(pro)q(of)h(that)f(factoring)g(is)h (di\016cult,)i(so)d(w)o(e)g(cannot)h(conclude)338 1935 y(that)i(the)h(Rabin)g(cryptosystem)f(is)h(secure.)21 b(Virtually)16 b(all)g(pro)o(v)m(able)f(securit)o(y)338 1991 y(results)j(in)o(v)o(olv)o(e)h(a)f(reduction)h(\(in)f(the)h(sense) f(of)g(algorithms)g(or)g(complexit)o(y)338 2048 y(theory\),)11 b(so)g(the)g(alternatv)o(e)g(term)f Fh(r)n(e)n(ductionist)i(se)n (curity)j Fj(is)d(sometimes)f(used.)224 2134 y Fi(unc)m(onditional)17 b(se)m(curity)338 2206 y Fj(This)22 b(measure)f(concerns)g(the)h (securit)o(y)f(of)g(cryptosystems)f(when)i(there)f(is)338 2262 y(no)16 b(b)q(ound)i(placed)f(on)g(the)f(amoun)o(t)g(of)g (computation)g(that)g(an)g(adv)o(ersary)g(is)338 2319 y(allo)o(w)o(ed)k(to)f(carry)g(out.)32 b(A)19 b(cryptosystem)g(is)h (de\014ned)h(to)e(b)q(e)h Fh(unc)n(ondition-)338 2375 y(al)r(ly)g(se)n(cur)n(e)j Fj(if)d(it)h(cannot)e(b)q(e)i(brok)o(en,)g (ev)o(en)f(with)g(in\014nite)i(computational)338 2432 y(resources.)f(F)l(or)15 b(example,)h(it)g(is)g(w)o(ell-kno)o(wn)g (that)f(the)h(one-time)g(pad)g(is)g(un-)338 2488 y(conditionally)e (secure)f(\(thatis,)e(observ)m(ation)i(of)e(a)h(single)h(ciphertext)g (pro)o(vides)960 2613 y(2)p eop %%Page: 3 3 3 2 bop 338 286 a Fj(no)12 b(information)g(ab)q(out)g(the)g(corresp)q (onding)h(plain)o(text\).)20 b(Pro)q(ofs)11 b(of)h(uncondi-)338 343 y(tionally)17 b(securit)o(y)f(do)f(not)h(in)o(v)o(olv)o(e)g (computational)g(complexit)o(y)l(,)g(but)g(rather)338 399 y(dep)q(end)j(on)f(com)o(binatorial)h(and)f(information-theoretic)h (analyses.)28 b(A)18 b(pre-)338 456 y(cise)e(stamen)o(t)e(of)h (unconditional)j(securit)o(y)d(usually)i(in)o(v)o(olv)o(es)f(computing) f(the)338 512 y(probabilit)o(y)h(that)f(an)g(adv)o(ersary)f(can)i(ac)o (hiev)o(e)f(some)g(sp)q(eci\014ed)j(goal.)295 603 y(Most)i(of)i(the)g (discussion)h(in)g(this)f(pap)q(er)g(concerns)g(pro)o(v)m(able)h (securit)o(y)l(.)40 b(Be-)224 659 y(fore)14 b(pro)q(ceeding)h(further,) f(w)o(e)f(wish)i(to)e(emphasize)i(that)f(pro)o(v)m(able)g(securit)o(y)h (can)f(b)q(e)224 715 y(relev)m(an)o(t)j(at)e(v)m(arious)i(stages)e(in)i (the)f(design)h(and)g(analysis)g(of)e(cryptographic)i(algo-)224 772 y(rithms)h(and)g(proto)q(cols.)27 b(Here)18 b(are)g(some)f(of)g (the)h(more)f(commonly)h(used)h(settings)224 828 y(for)c(pro)o(v)m (able)h(securit)o(y)f(in)h(cryptograph)o(y:)224 930 y Fi(r)m(e)m(ducing)k(crypto)m(gr)m(aphic)e(algorithms)g(to)g(mathematic) m(al)f(primitives)338 1002 y Fj(This)c(means)g(that)f(a)h (cryptographic)g(algorithm)g(is)g(pro)o(v)o(ed)g(secure,)g(assuming)338 1058 y(that)e(an)h(underlying)i(computational)e(problem)h(is)g(in)o (tractible.)20 b(F)l(or)11 b(example,)338 1115 y(Rabin)k(encryption)h (is)g(secure)g(if)g(factoring)e(is)i(in)o(tractible.)224 1207 y Fi(enhancing)i(se)m(curity)h(of)g(crypto)m(gr)m(aphic)f (algorithms)338 1279 y Fj(This)e(refers)f(to)f(the)i(situation)f(where) h(w)o(e)f(pro)o(v)o(e)f(that)h(an)g(\\enhanced")h(cryp-)338 1335 y(tographic)j(algorithm)g(pro)o(vides)h(a)f(certain)h(\(higher\))g (lev)o(el)g(of)f(securit)o(y)l(,)i(as-)338 1392 y(suming)c(that)g(the)g (\\basic")g(algorithm)f(pro)o(vides)i(a)e(certain)i(\(lo)o(w)o(er\))e (lev)o(el)i(of)338 1448 y(secuirt)o(y)l(.)i(F)l(or)13 b(example,)h(O)o(AEP)g(is)g(c)o(hosen-ciphertext)h(secure)f(if)g(basic) h(RSA)338 1504 y(encryption)h(is)g(a)f(one-w)o(a)o(y)f(function.)224 1597 y Fi(r)m(e)m(ducing)20 b(crypto)m(gr)m(aphic)e(pr)m(oto)m(c)m(ols) g(to)h(underlying)e(algorithms)338 1668 y Fj(This)11 b(means)f(that)f(a)h(cryptographic)g(proto)q(col)g(\(e.g.,)g(a)g(k)o (ey)g(agreemen)o(t)f(sc)o(heme\))338 1725 y(is)16 b(pro)o(v)o(ed)g (secure,)g(assuming)h(that)e(the)h(cryptographic)g(algorithms)g(used)h (in)338 1781 y(the)f(proto)q(col)g(are)f(secure.)23 b(F)l(or)15 b(example,)i(certain)f(v)o(ersions)g(of)f(the)h(Station-)338 1838 y(to-Station)j(k)o(ey)g(agreemen)o(t)g(sc)o(heme)h(are)g(secure)g (if)g(the)f(signature)h(sc)o(heme)338 1894 y(and/or)12 b(message)f(authen)o(tication)i(sc)o(heme)g(used)g(in)g(the)f(proto)q (col)g(are)g(secure.)224 2037 y Fk(3)67 b(V)-6 b(alidit)n(y)25 b(of)d(Pro)n(v)l(able)i(Securit)n(y)g(Pro)r(ofs)224 2138 y Fj(Pro)o(v)m(able)15 b(securit)o(y)g(in)h(cryptograph)o(y)d(has)i (had)g(a)f(rather)g(c)o(hequered)i(history)l(.)k(Lars)224 2195 y(Kn)o(udsen)d(said)554 2285 y(\\If)e(it's)g(pro)o(v)m(ably)h (secure,)f(it's)g(probably)h(not")224 2375 y(\(see)f([7)o(]\).)k(Ho)o (w)o(ev)o(er,)14 b(I)h(b)q(eliev)o(e)i(that)d(this)i(p)q(erception)g (of)f(pro)o(v)m(able)g(securit)o(y)g(is)h(due)224 2432 y(in)g(large)f(part)g(to)f(the)h(debate)g(o)o(v)o(er)f(the)i (signi\014cance)h(of)d(pro)o(v)m(able)i(securit)o(y)f(pro)q(ofs,)224 2488 y(rather)g(than)g(the)g(v)m(alidit)o(y)i(of)e(the)g(pro)q(ofs)g (themselv)o(es.)960 2613 y(3)p eop %%Page: 4 4 4 3 bop 295 286 a Fj(Let)14 b(us)f(examine)i(the)f(structure)f(of)g(a)h (t)o(ypical)g(pro)o(v)m(able)h(securit)o(y)f(pro)q(of,)f(whic)o(h,)224 343 y(as)21 b(men)o(tioned)h(previously)l(,)i(usually)f(tak)o(es)d(the) i(form)e(of)h(a)g(reduction.)39 b(Usually)224 399 y(there)21 b(are)f(some)g(underlying)j(assumptions,)e(whic)o(h)h(ma)o(y)d(or)h(ma) o(y)g(not)g(b)q(e)h(made)224 456 y(explicit.)28 b(These)18 b(comprise)f(the)h(rules)f(or)g(en)o(vironmen)o(t)h(in)g(whic)o(h)g(a)e (h)o(yp)q(othetical)224 512 y(attac)o(k)f(tak)o(es)g(place.)23 b(The)16 b Fh(attack)h(mo)n(del)f Fj(en)o(umerates)f(the)h(precise)h (cryptographic)224 569 y(information)12 b(a)o(v)m(ailable)h(to)d(the)i (adv)o(ersary)e(carrying)i(out)f(the)g(attac)o(k.)17 b(This)12 b(includes)224 625 y(sp)q(ecifying)17 b(the)f(follo)o(wing:) 292 719 y Ff(\017)23 b Fj(the)16 b(cryptographic)g(data)f(the)h(adv)o (ersary)f(is)h(pro)o(vided)h(with)f(\(e.g.,)f(a)g(c)o(hosen)338 775 y(ciphertext)h(attac)o(k\);)292 869 y Ff(\017)23 b Fj(whic)o(h)e(asp)q(ects)g(of)g(the)g(cryptographic)g(algorithms)g (are)f(sp)q(eci\014ed)j(\(e.g.,)e(a)338 926 y(description)d(of)e(a)g (hash)g(function)h(used)g(in)g(the)g(algorithm)f(ma)o(y)f(or)h(ma)o(y)g (not)338 982 y(b)q(e)h(pro)o(vided)f(to)g(the)g(adv)o(ersary)f(|)h (this)g(is)h(relev)m(an)o(t)g(in)f(the)h(random)e(oracle)338 1039 y(mo)q(del\);)292 1132 y Ff(\017)23 b Fj(whic)o(h)18 b(asp)q(ects)f(of)g(the)g(implemen)o(tation)i(are)e(sp)q(eci\014ed)i (\(e.g.,)d(a)h(white-b)q(o)o(x,)338 1189 y(grey-b)q(o)o(x)e(or)f(blac)o (k-b)q(o)o(x)i(mo)q(del\);)g(and)292 1283 y Ff(\017)23 b Fj(the)15 b(computational)h(resources)f(a)o(v)m(ailable)i(to)d(the)h (adv)o(ersary)l(.)295 1377 y(The)h(adv)o(ersary)f(tries)h(to)f(ac)o (hiev)o(e)h(a)g(certain)g(pre-sp)q(eci\014ed)i(cryptographic)e(ob-)224 1433 y(jectiv)o(e)e(\(whic)o(h)f(will)h(constitute)g(a)e Fe(break)g Fj(of)h(the)g(sc)o(heme\).)19 b(A)13 b(break)f(migh)o(t)h (consist)224 1489 y(of)j(computing)h(an)f(unkno)o(wn)g(k)o(ey)l(,)g(or) g(of)g(distinguishing)j(encryptions)e(of)e(t)o(w)o(o)g(pre-)224 1546 y(sp)q(eci\014ed)i(plain)o(texts.)295 1602 y(The)k(reduction)g (whic)o(h)h(constitutes)e(the)h(securit)o(y)g(pro)q(of)f(is)i(a)e(pro)q (of)g(that,)h(if)224 1659 y(the)d(adv)o(ersary)e(can)i(ac)o(hiev)o(e)g (his)g(ob)s(jectiv)o(e)g Fe(break)p Fj(,)e(then)i(the)g(adv)o(ersary)e (\(with)i(a)224 1715 y(bit)e(more)e(w)o(ork\))g(could)h(ac)o(hiev)o(e)h (some)e(other)h(ob)s(jectiv)o(e,)g Fe(supplementary-break)p Fj(,)224 1772 y(p)q(erhaps)g(relating)h(to)d(an)i(underlying)h (\\primitiv)o(e")g(on)e(whic)o(h)i(the)e(sc)o(heme)h(is)g(built.)224 1828 y(So)g(what)g(is)h(actually)g(pro)o(v)o(en)e(is)i(a)f(statemen)o (t)f(of)h(the)g(form)422 1922 y(\\If)h(the)f(adv)o(ersary)f(can)h(do)h (`X',)e(then)h(he)h(can)f(also)g(do)g(`Y')g(".)295 2016 y(What)c(do)q(es)h(this)g(ha)o(v)o(e)f(to)g(do)g(with)h(securit)o(y?)20 b(Usually)l(,)14 b(w)o(e)d(construct)g(the)h(pro)q(of)224 2072 y(so)i(that)f(`Y')g(is)i(some)e(computation)h(whic)o(h)h(w)o(e)e (b)q(eliev)o(e)j(is)f(infeasible.)22 b(If)14 b(w)o(e)f(b)q(eliev)o(e) 224 2129 y(that)18 b(that)g(adv)o(ersary)g(cannot)h(do)f(`Y',)g(then)h (it)g(is)h(a)e(logical)i(consequence)g(of)e(the)224 2185 y(pro)q(of)e(that)f(w)o(e)h(m)o(ust)f(also)h(b)q(eliev)o(e)i(that)d (the)h(adv)o(ersary)f(cannot)h(do)g(`X')f(\(at)g(least,)224 2242 y(when)h(he)f(is)h(op)q(erating)g(within)g(the)f(constrain)o(ts)g (of)g(the)g(giv)o(en)h(attac)o(k)e(mo)q(del\).)295 2298 y(The)h(situation)h(gets)e(m)o(urky)l(,)h(ho)o(w)o(ev)o(er,)f(when)i(w) o(e)e(try)h(to)g(in)o(trepret)g(a)g(pro)o(v)m(able)224 2355 y(securit)o(y)j(pro)q(of)g(in)h(the)f(\\real)g(w)o(orld".)28 b(Then)18 b(w)o(e)g(m)o(ust)f(ask)h(if)g(the)g(attac)o(k)f(mo)q(del)224 2411 y(is)f(reasonable.)22 b(W)l(e)15 b(ha)o(v)o(e)h(to)e(consider)j (the)f(p)q(ossiblilit)o(y)i(the)e(adv)o(ersary)e(migh)o(t)i(not)224 2467 y(\\follo)o(w)h(the)h(rules")g(as)f(sp)q(eci\014ed)i(in)f(the)g (attac)o(k)e(mo)q(del)i(\(for)e(example,)j(w)o(e)e(migh)o(t)960 2613 y(4)p eop %%Page: 5 5 5 4 bop 224 286 a Fj(pro)o(v)o(e)19 b(securit)o(y)g(in)h(a)f(blac)o (k-b)q(o)o(x)g(mo)q(del,)i(but)e(the)g(adv)o(ersary)g(could)h(carry)e (out)h(a)224 343 y(side-c)o(hannel)g(attac)o(k)c(if)j(he)f(is)g(giv)o (en)g(a)f(sp)q(eci\014c)j(implemen)o(tation)f(of)e(the)h(system\).)224 399 y(As)j(w)o(ell,)i(w)o(e)d(ha)o(v)o(e)h(to)f(ask)g(if)i(our)e(b)q (elief)j(that)d(the)h(adv)o(ersary)f(cannot)h(do)g(`Y')f(is)224 456 y(really)d(reasonable.)295 512 y(Historically)l(,)g(the)g(fundamen) o(tal)f(assumption)g(kno)o(wn)g(as)g(\\Kerc)o(kho\013)t('s)f(princi-) 224 569 y(ple")19 b(has)f(pla)o(y)o(ed)g(an)g(imp)q(ortan)o(t)g(in)h (role)f(in)h(dev)o(eloping)g(a)f(realistic)i(approac)o(h)d(to)224 625 y(concepts)f(of)g(cryptographic)f(securit)o(y)l(.)23 b(In)16 b(mo)q(dern)g(cryptographic)g(parlance,)g(this)224 682 y(principle)h(states)d(that)g(w)o(e)g(should)h(not)g(consider)g(an) f(attac)o(k)g(mo)q(del)h(to)f(b)q(e)h(\\reason-)224 738 y(able")g(unless)h(a)e(description)i(of)e(the)g(cryptographic)h (algorithm)f(\(whose)g(securit)o(y)h(is)224 795 y(b)q(eing)g(studied\)) g(is)f(pro)o(vided)g(to)f(the)h(adv)o(ersary)l(.)19 b(Ho)o(w)o(ev)o (er,)12 b(in)j(recen)o(t)f(y)o(ears,)f(it)h(has)224 851 y(b)q(een)19 b(recognized)f(that)f(the)g(adv)o(ersary)f(ma)o(y)h(ha)o (v)o(e)g(information)g(ab)q(out)h(a)f(sp)q(eci\014c)224 907 y(implemen)o(tation)f(of)e(a)h(cryptographic)f(algorithm,)h(whic)o (h)g(p)q(ermits)h(the)e(p)q(ossibilit)o(y)224 964 y(of)j(side)i(c)o (hannel)f(attac)o(ks,)f(suc)o(h)h(as)f(timing)h(attac)o(ks.)25 b(So)18 b(there)f(are)h(sev)o(eral)f(mo)q(d-)224 1020 y(els)g(whic)o(h)f(can)g(b)q(e)h(considered,)g(dep)q(ending)h(on)d(the) h(lev)o(el)h(of)f(detail)h(the)e(adv)o(ersary)224 1077 y(p)q(ossesses)f(ab)q(out)g(a)f(cryptosystem)g(and)h(ho)o(w)f(it)h(is)h (implemen)o(ted)g(in)g(a)e(real)h(system.)295 1133 y(Finally)l(,)h(it)f (is)h(imp)q(ortan)o(t)e(to)g(remem)o(b)q(er)h(that)f(w)o(e)h(should)h (not)e(hop)q(e)i(to)e(pro)o(vide)224 1190 y(mathematical)k(pro)q(ofs)g (that)f(apply)i(to)e(the)h(\\real)g(w)o(orld".)25 b(W)l(e)17 b(do)f(not)h(exp)q(ect)h(an)224 1246 y(engineer)k(to)e(pro)o(v)o(e)g (mathematically)h(that)f(a)h(b)q(oat)f(will)i(not)e(sink)i(\(the)e (Titanic,)224 1303 y(p)q(erhaps?\),)h(or)d(that)h(a)g(bridge)h(will)h (not)e(fall)h(do)o(wn)f(\(e.g.,)f(the)h(T)l(acoma)g(Narro)o(ws)224 1359 y(Bridge)354 1343 y Fd(1)375 1359 y Fj(\).)26 b(Similarly)l(,)21 b(w)o(e)c(should)h(not)g(exp)q(ect)g(to)f(b)q(e)h(able)h(to)d(pro)o(v)o (e)h(that)g(an)h(im-)224 1416 y(plemen)o(ted)i(cryptographic)f (algorithm)g(cannot)g(b)q(e)g(brok)o(en.)31 b(There)19 b(are)g(just)f(to)q(o)224 1472 y(man)o(y)c(unkno)o(wns:)20 b(a)14 b(cryptographic)g(algorithm)h(is)f(a)g(comp)q(onen)o(t)h(of)f(a) g(more)g(com-)224 1528 y(plicated)20 b(proto)q(col.)29 b(The)19 b(proto)q(col)f(is)h(implemen)o(ted)h(\(in)f(hardw)o(are)f(or) g(soft)o(w)o(are\))224 1585 y(on)13 b(some)g(platform,)g(running)i (some)e(op)q(erating)g(system,)g(whic)o(h)h(ma)o(y)f(b)q(e)h(connected) 224 1641 y(to)g(the)h(in)o(ternet.)21 b(Ho)o(w)14 b(could)i(w)o(e)f(ev) o(er)f(hop)q(e)i(to)e(pro)o(v)o(e)h(that)f(the)h(resulting)h(system)224 1698 y(is)g(secure?)295 1754 y(In)f(summary)l(,)f(it)h(is)g(imp)q (ortan)o(t)f(to)g(remem)o(b)q(er)h(that)f(the)h(v)m(alidit)o(y)h(and)f (the)g(rele-)224 1811 y(v)m(ance)h(of)f(a)g(pro)q(of)g(in)h (cryptograph)o(y)e(are)h(often)g(t)o(w)o(o)f(completely)i(di\013eren)o (t)g(things:)280 1905 y(1.)22 b(The)11 b Fh(validity)h Fj(of)f(a)g(pro)q(of)g(just)g(refers)h(to)e(the)i(correctness)f(of)g (the)h(pro)q(of,)f(within)338 1961 y(a)16 b(fully)j(sp)q(eci\014ed)g (and)e(consisten)o(t)g(mathematical)g(mo)q(del.)26 b(If)17 b(ev)o(erything)g(is)338 2017 y(de\014ned)c(precisely)l(,)h(then)d(it)h (is)g(p)q(ossible)i(\(in)e(principle,)i(at)d(least\))h(to)e(determine) 338 2074 y(whether)15 b(an)o(y)g(giv)o(en)h(pro)q(of)f(is)g(v)m(alid.) 280 2168 y(2.)22 b(The)g Fh(r)n(elevanc)n(e)f Fj(of)g(a)h(pro)q(of)g (is)g(m)o(uc)o(h)g(more)g(sub)s(jectiv)o(e.)41 b(In)23 b(judging)f(the)338 2224 y(relev)m(ance)c(of)d(a)h(pro)q(of,)g(w)o(e)g (are)g(implicitly)j(ev)m(aluating)f(the)e(appropriateness)338 2281 y(of)g(the)g(de\014nitions)j(and)d(mathematical)h(mo)q(del)g(used) g(in)h(the)e(pro)q(of)g(to)g(what)338 2337 y(exists)j(in)g(the)g(real)f (w)o(orld.)30 b(A)o(t)18 b(b)q(est,)i(a)e(pro)o(v)m(able)h(securit)o(y) g(pro)q(of)f(pro)o(vides)p 224 2368 598 2 v 276 2395 a Fc(1)293 2411 y Fb(On)12 b(No)o(v)o(em)o(b)q(er)g(7,)f(1940,)h(at)g (appro)o(ximately)i(11:00)e(AM,)f(the)h(\014rst)f(T)m(acoma)h(Narro)o (ws)f(susp)q(en-)224 2456 y(sion)j(bridge)h(collapsed)g(due)f(to)f (wind-induced)i(vibrations.)960 2613 y Fj(5)p eop %%Page: 6 6 6 5 bop 338 286 a Fj(some)15 b(plausible)i(evidence)g(\(sub)s(ject)e (to)g(some)g(plausible)i(assumptions\))e(that)338 343 y(a)g(cryptographic)g(sc)o(heme)h(will)g(b)q(e)g(secure)g(when)g(used)g (in)g(the)f(real)g(w)o(orld.)224 486 y Fk(4)67 b(The)22 b(Random)h(Oracle)f(Mo)r(del)224 587 y Fj(The)16 b(random)f(oracle)g (mo)q(del)i(has)e(ac)o(hiev)o(ed)h(a)g(considerable)h(amoun)o(t)d(of)h (notoriet)o(y)l(.)224 644 y(Cramer)h(and)h(Shoup)h(ha)o(v)o(e)e (written)h(that)f(an)o(y)g(pro)q(of)h(in)o(v)o(olving)h(the)f(random)f (ora-)224 700 y(cle)h(mo)q(del)g(should)g(b)q(e)g(considered)g(a)f (\\heuristic)h(pro)q(of)t(")e(\(see)g([5]\).)21 b(P)o(erhaps)16 b(more)224 757 y(imp)q(ortan)o(tly)l(,)e(there)f(ha)o(v)o(e)g(b)q(een)i (sev)o(eral)e(published)j(results)e(\([4)o(])e(w)o(as)h(the)g(\014rst)g (suc)o(h)224 813 y(result\))21 b(sho)o(wing)h(that)e(v)m(arious)i(t)o (yp)q(es)f(of)f(cryptographic)i(sc)o(hemes)f(that)g(can)g(b)q(e)224 869 y(pro)o(v)o(en)16 b(to)f(b)q(e)i(secure)f(in)h(the)f(random)f (oracle)h(mo)q(del)h(b)q(ecome)g(insecure)g(when)f(the)224 926 y(random)c(oracle)h(is)g(instan)o(tiated)g(with)f(an)o(y)h(real)f (hash)h(function)g(\(SHA-1,)g(for)f(exam-)224 982 y(ple\).)20 b(In)15 b(an)o(y)e(ev)o(en)o(t,)h(there)g(seems)g(to)f(b)q(e)i(a)e (fairly)i(widely-held)i(b)q(elief)f(that)d(there)h(is)224 1039 y(a)i(h)o(uge)g(\\gap")e(b)q(et)o(w)o(een)j(pro)q(ofs)e(that)g (use)h(the)g(random)f(oracle)h(mo)q(del)h(and)f(pro)q(ofs)224 1095 y(that)f(do)g(not)g(so.)295 1152 y(The)e(debate)g(really)h (concerns)g(the)f(suitabilit)o(y)i(of)e(the)g(random)g(oracle)g(mo)q (del)h(as)224 1208 y(a)d(to)q(ol)g(in)h(cryptograph)o(y)l(.)18 b(In)12 b(other)f(w)o(ords,)g(is)g(a)g(pro)q(of)g(in)h(the)f(random)g (oracle)h(mo)q(del)224 1265 y(relev)m(an)o(t)i(in)g(the)f(\\real)h(w)o (orld"?)20 b(More)12 b(precisely)l(,)j(is)f(a)f(pro)q(of)g(in)h(the)f (random)g(oracle)224 1321 y(mo)q(del)18 b(fundamen)o(tally)g(or)e (substan)o(tially)h(di\013eren)o(t,)g(in)h(terms)e(of)g(its)h(relev)m (ance)i(in)224 1378 y(the)c(real)h(w)o(orld,)f(to)f(a)h(pro)q(of)g (that)f(do)q(esn't)i(use)f(the)g(random)g(oracle)h(mo)q(del?)295 1434 y(The)i(source)g(of)f(this)i(discussion)g(dates)f(bac)o(k)g(to)f (the)h(seminal)h(1993)e(pap)q(er)i(b)o(y)224 1490 y(Bellare)13 b(and)e(Roga)o(w)o(a)o(y)d(\([2)o(]\))j(in)g(whic)o(h)h(the)g(random)e (oracle)h(mo)q(del)h(w)o(as)f(in)o(tro)q(duced.)224 1547 y(Bellare)17 b(and)e(Roga)o(w)o(a)o(y)e(stated)h(the)i(follo)o(wing)f (in)h(the)g(abstract)e(of)h(their)g(pap)q(er:)338 1651 y(W)l(e)22 b(argue)f(that)g(the)h(random)f(oracle)h(mo)q(del)h(|)e (where)h(all)h(parties)338 1707 y(ha)o(v)o(e)16 b(access)i(to)e(a)h (public)i(random)e(oracle)g(|)g(pro)o(vides)g(a)g(bridge)h(b)q(e-)338 1763 y(t)o(w)o(een)f(cryptographic)g(theory)g(and)h(cryptographic)f (practice.)27 b(In)18 b(the)338 1820 y(paradigm)h(w)o(e)g(suggest,)g(a) g(practical)h(proto)q(col)f(is)h(pro)q(duced)g(b)o(y)f(\014rst)338 1876 y(devising)i(and)f(pro)o(ving)g(correct)f(a)g(proto)q(col)h(for)f (the)g(random)h(oracle)338 1933 y(mo)q(del,)14 b(and)g(then)g (replacing)h(oracle)f(accesses)g(b)o(y)f(the)h(computation)f(of)338 1989 y(an)i(\\appropriately)g(c)o(hosen")h(function.)295 2093 y(This)22 b(is)g(really)g(taking)f(the)h(\\bull)h(b)o(y)e(the)h (horns"!)38 b(Basically)l(,)25 b(Bellare)d(and)224 2149 y(Roga)o(w)o(a)o(y)15 b(are)h(putting)i(forw)o(ard)e(the)h(thesis)h (that)e(a)h(pro)q(of)f(in)i(the)g(random)e(oracle)224 2206 y(mo)q(del)j(is)f(a)f(go)q(o)q(d)h(predicator)g(of)f(securit)o(y)h (in)h(the)e(real)h(w)o(orld.)27 b(Not)o(withstanding)224 2262 y(results)16 b(suc)o(h)f(as)g(those)g(in)h([4)o(],)f(I)g(w)o(ould) h(completely)g(agree)f(with)h(this)f(assessmen)o(t.)295 2319 y(W)l(e)h(ha)o(v)o(e)g(argued)g(ab)q(o)o(v)o(e)g(that)f(no)h(pro)o (v)m(able)h(securit)o(y)f(pro)q(of)g(is)h(a)f(pro)q(of)f(in)i(the)224 2375 y(real)h(w)o(orld.)25 b(There)17 b(are)g(v)m(arious)g(attac)o(k)f (mo)q(dels)i(that)e(can)h(b)q(e)h(considered)h(in)e(the)224 2432 y(con)o(text)e(of)g(an)o(y)g(pro)q(of)g(of)g(securit)o(y)l(.)22 b(Ideally)l(,)17 b(w)o(e)e(w)o(ould)h(seek)g(the)f(least)h(restrictiv)o (e)224 2488 y(attac)o(k)i(mo)q(del)i(when)g(carrying)g(out)f(a)g(pro)q (of)g(\(this)g(w)o(ould)h(lead)g(to)f(a)g(\\stronger")960 2613 y(6)p eop %%Page: 7 7 7 6 bop 224 286 a Fj(securit)o(y)22 b(result\).)38 b(There)21 b(are)g(man)o(y)g(v)m(ariations)g(in)h(attac)o(k)e(mo)q(dels,)j(from)e (v)o(ery)224 343 y(strong)c(to)h(v)o(ery)g(w)o(eak,)g(and)g(in)h(m)o(y) f(opinion,)i(the)e(random)g(oracle)g(mo)q(del)i(can)e(b)q(e)224 399 y(considered)f(as)e(just)f(one)i(of)f(man)o(y)f(p)q(ossible)j(v)m (ariations.)295 456 y(Adopting)11 b(the)g(random)f(oracle)h(mo)q(del)h (means)f(that)f(the)h(adv)o(ersary)f(is)h(restricted)224 512 y(to)19 b(attac)o(ks)f(that)h(treat)g(the)h(hash)f(function)i(as)e (a)g(random)h(oracle)f(\(regardless)h(of)224 569 y(whether)g(it)g(is)g (or)g(is)g(not)f(a)h(random)f(oracle\).)34 b(Suc)o(h)20 b(an)g(attac)o(k)e(can)i(reasonably)224 625 y(b)q(e)e(termed)f(a)g (\\hash-generic")h(attac)o(k.)25 b(A)17 b(securit)o(y)g(pro)q(of)g(in)h (the)f(random)g(oracle)224 682 y(mo)q(del)12 b(means)f(that)g(the)g(sc) o(heme)h(under)g(consideration)g(cannot)f(b)q(e)h(brok)o(en)f(\(sub)s (ject)224 738 y(to)18 b(the)h(v)m(arious)g(assumptions\))f(b)o(y)g(an)o (y)g(hash-generic)i(attac)o(k)1347 722 y Fd(2)1366 738 y Fj(.)29 b(In)20 b(other)e(w)o(ords,)224 795 y(w)o(e)e(end)i(up)f(sho) o(wing)f(that)g(the)h(sc)o(heme)g(cannot)f(b)q(e)h(brok)o(en)g(b)o(y)f (a)g(certain)h(t)o(yp)q(e)g(of)224 851 y(attac)o(k)d(|)h(but)g(that)f (is)i(all)g(an)o(y)f(pro)o(v)m(able)h(securit)o(y)g(pro)q(of)e(do)q (es,)i(an)o(yw)o(a)o(y)l(.)295 907 y(Of)k(course,)i(a)e(pro)q(of)f(in)j (the)e(random)g(oracle)h(mo)q(del)g(do)q(es)f(not)g(rule)h(out)f(the) 224 964 y(p)q(ossibilit)o(y)g(of)e(successful)h(attac)o(ks)d(that)h (mak)o(e)g(use)i(of)e(sp)q(eci\014c)j(prop)q(erties)e(of)f(the)224 1020 y(hash)12 b(function)g(emplo)o(y)o(ed)h(in)f(the)g(sc)o(heme.)19 b(Ho)o(w)o(ev)o(er,)11 b(this)h(do)q(es)g(not)f(really)i(giv)o(e)e(me) 224 1077 y(m)o(uc)o(h)16 b(cause)f(for)g(concern,)h(in)g(part)f(b)q (ecause)i(it)e(is)h(so)f(v)o(ery)h(hard)f(to)g(come)g(up)h(with)224 1133 y(a)i(\\real")g(sc)o(heme)h(that)e(can)h(b)q(e)h(attac)o(k)o(ed)e (via)i(a)f(hash)g(function)h(that)e(is)i(b)q(eliev)o(ed)224 1190 y(secure)g(\(this)g(issue)g(is)g(discussed)h(more)e(thoroughly)l (,)h(and)f(quite)h(con)o(vincingly)l(,)j(in)224 1246 y([8,)14 b Ff(x)p Fj(6]\).)295 1303 y(T)l(o)k(giv)o(e)g(a)g(bit)h(of)f (additional)i(rationale)e(for)g(m)o(y)g(argumen)o(ts)g(ab)q(o)o(v)o(e,) g(p)q(erhaps)224 1359 y(it)f(is)h(useful)g(to)e(consider)i(another)f (comp)q(onen)o(t)g(of)g(man)o(y)f(cryptographic)h(sc)o(hemes)224 1416 y(that)k(is)g(usually)i(not)e(ev)o(en)g(considered)i(when)e(doing) h(pro)o(v)m(able)g(securit)o(y)f(pro)q(ofs.)224 1472 y(Namely)l(,)j(man)o(y)e(encryption)g(sc)o(hemes,)i(signature)e(sc)o (hemes,)h(etc.,)g(mak)o(e)f(use)g(of)224 1528 y(random)14 b(n)o(um)o(b)q(er)h(generators.)k(It)14 b(is)h(w)o(ell-kno)o(wn)g(that) f(using)h(w)o(eak)f(random)g(n)o(um-)224 1585 y(b)q(er)h(generators)f (can)g(cause)h(otherwise)g(secure)g(sc)o(hemes)f(to)g(break)h (completely)l(.)21 b(On)224 1641 y(the)12 b(other)g(hand,)g(it)g(is)h (an)e(often)h(unstated,)g(implicit)i(assumption)f(in)f(pro)o(v)m(able)h (secu-)224 1698 y(rit)o(y)j(pro)q(ofs)g(that)f(p)q(erfectly)i(random)f (n)o(um)o(b)q(ers)g(are)g(a)o(v)m(ailable)i(whenev)o(er)f(they)f(are) 224 1754 y(needed)g(\(consider)f(the)g(Sc)o(hnorr)g(signature)g(sc)o (heme)g(as)f(one)h(example\).)20 b(Of)15 b(course,)224 1811 y(this)h(is)g(not)g(the)f(case,)h(and)f(random)h(n)o(um)o(b)q(ers) g(in)g(practice)g(are)g(usually)h(generated)224 1867 y(b)o(y)k(a)g Fh(pseudor)n(andom)i(numb)n(er)e(gener)n(ator)g Fj(whic)o(h)h(expands)g(a)f(small)h(secret)f(ran-)224 1924 y(dom)14 b(seed)h(in)o(to)f(a)g(long)h(string)f(of)g(seemingly)h (unpredictable)i(bits.)j(Pseudorandom)224 1980 y(n)o(um)o(b)q(er)13 b(generators)e(are)h(no)h(more)f(p)q(erfect)h(random)f(n)o(um)o(b)q(er) g(generators)g(than)g(real)224 2037 y(hash)i(functions)h(are)f(random)g (oracles.)19 b(Ho)o(w)o(ev)o(er,)13 b(there)h(do)q(es)h(not)e(seem)i (to)e(b)q(e)i(an)o(y)224 2093 y(ongoing)g(con)o(tro)o(v)o(ersy)f(ab)q (out)h(the)g(legitimacy)i(of)d(the)i(unsp)q(ok)o(en)g(\\p)q(erfect)f (random)224 2149 y(n)o(um)o(b)q(er)h(generator)e(mo)q(del")i(that)e (underlies)k(man)o(y)c(pro)o(v)m(able)i(securit)o(y)g(pro)q(ofs)1638 2133 y Fd(3)1657 2149 y Fj(.)p 224 2180 598 2 v 276 2207 a Fc(2)293 2223 y Fb(As)d(far)g(as)h(I)f(kno)o(w,)g(this)i(in)o (terpretation)g(w)o(as)e(\014rst)h(put)g(forw)o(ard)f(b)o(y)h(Blak)o (e-Wilson,)i(Johnson)224 2269 y(and)e(Menezes)g(in)f([3].)276 2298 y Fc(3)293 2314 y Fb(I)j(am)h(not)g(claiming)i(an)o(y)e(kind)h(of) e(\\equiv)n(alence")j(b)q(et)o(w)o(een)e(hash)g(functions)h(implemen)o (ting)224 2360 y(random)g(oracles,)h(as)e(opp)q(osed)h(to)f (pseudorandom)j(n)o(um)o(b)q(er)d(generators)h(implemen)o(ting)i(p)q (erfect)224 2406 y(random)d(n)o(um)o(b)q(er)g(generators.)27 b(F)m(or)16 b(one)g(thing,)i(pseudorandom)g(n)o(um)o(b)q(er)f (generators)g(ha)o(v)o(e)f(un-)224 2451 y(kno)o(wn)e(secret)f(seeds,)g (whereas)h(hash)f(functions)i(are)e(completely)i(public.)960 2613 y Fj(7)p eop %%Page: 8 8 8 7 bop 224 286 a Fk(5)67 b(The)22 b(Culture)i(of)e(Conference)f (Publications)224 388 y Fj(Complain)o(ts)16 b(ha)o(v)o(e)g(sometimes)f (b)q(een)i(made)f(that)f(some)g(pro)o(v)m(able)i(securit)o(y)f(pap)q (ers)224 444 y(are)h(jargon-\014lled,)h(hard)e(to)g(read,)h(imprecise,) h(and)f(sometimes)g(incorrect)g(\(see)g([8)o(],)224 501 y(for)j(example\).)36 b(Ho)o(w)o(ev)o(er,)21 b(this)g(complain)o(t)g (can)g(b)q(e)g(made)g(ab)q(out)f(man)o(y)g(pap)q(ers)224 557 y(in)d(cryptograph)o(y)f(and)g(theoretical)h(computer)f(science)i (in)f(general.)24 b(Mathematics)224 614 y(pap)q(ers)e(migh)o(t)f(b)q(e) h(no)g(easier)g(to)e(read,)j(but)e(there)h(seems)f(to)g(b)q(e)h(a)f (fairly)h(wide-)224 670 y(spread)f(b)q(elief)h(that)d(published)k(pro)q (ofs)d(in)h(mathematics)f(are)g(more)g(lik)o(ely)i(to)e(b)q(e)224 727 y(correct)f(than)g(published)j(pro)q(ofs)d(in)h(cryptograph)o(y)l (.)31 b(If)20 b(this)g(is)f(indeed)j(the)d(case,)224 783 y(wh)o(y)c(is)h(it)f(true?)295 840 y(I)f(w)o(ould)g(suggest)g(that) f(one)h(ma)s(jor)e(di\013erence)j(b)q(et)o(w)o(een)g(the)f(mathematics) f(and)224 896 y(computer)f(science)i(publication)g(culture)f(is)f(that) f(the)i(forums)e(for)g(mathematical)h(re-)224 952 y(searc)o(h)i(are)f (primarily)i(journal-based,)g(while)g(computer)e(science)j(researc)o(h) d(is)h(m)o(uc)o(h)224 1009 y(more)h(often)g(published)j(in)e (conference)g(pro)q(ceedings.)295 1065 y(Conference)k(publications)h (ha)o(v)o(e)e(the)h(adv)m(an)o(tage)f(of)g(fast)f(publication,)k(so)d (re-)224 1122 y(searc)o(h)g(is)h(disseminated)g(quic)o(kly)l(.)34 b(Unfortunately)l(,)20 b(review)g(b)o(y)f(a)g(program)f(com-)224 1178 y(mittee)e(of)f(a)g(conference)h(is)g(usually)h(a)e(p)q(o)q(or)g (substitute)h(for)f(review)h(b)o(y)g(a)f(quali\014ed)224 1235 y(referee)f(who)f(is)g(an)h(exp)q(ert)f(in)h(the)g(topic)f(of)g (the)h(pap)q(er)f(\(for)g(a)f(more)h(comprehensiv)o(e)224 1291 y(discussion,)k(see)e(Goldreic)o(h's)h(w)o(eb)f(page)g(on)g (program)f(committees)i([6)o(]\).)295 1348 y(Other)f(dra)o(wbac)o(ks)g (of)f(conference)i(publications)i(include)f(the)f(follo)o(wing:)292 1422 y Ff(\017)23 b Fj(Conference)f(pap)q(ers)g(are)f(often)g(prepared) h(in)h(haste)e(\(in)h(order)f(to)g(meet)h(a)338 1478 y(submission)16 b(deadline\).)292 1564 y Ff(\017)23 b Fj(Conference)14 b(pap)q(ers)h(migh)o(t)f(not)g(b)q(e)g(revised)i(or)d (up)q(dated)i(after)e(presen)o(tation)338 1621 y(at)k(the)i(conference) g(\(conference)f(pro)q(ceedings)i(are)e(often)f(published)k(b)q(efore) 338 1677 y(the)15 b(conference)h(tak)o(es)f(place\).)292 1763 y Ff(\017)23 b Fj(Pro)q(ofs)13 b(and)i(or)f(detailed)h (explanations)h(are)d(often)h(missing)i(\(p)q(erhaps)e(due)h(to)338 1820 y(page)g(limitations\).)292 1906 y Ff(\017)23 b Fj(There)18 b(is)h(often)f(little)i(incen)o(tiv)o(e)f(for)f(authors)g (to)f(go)h(to)g(the)g(extra)g(w)o(ork)f(of)338 1962 y(preparing)c(a)g (\\journal)g(v)o(ersion")g(of)g(their)g(pap)q(er.)20 b(F)l(or)12 b(example,)i(publication)338 2019 y(in)h(a)g(leading)h (conference)g(ma)o(y)e(carry)h(more)f(w)o(eigh)o(t)h(in)g(the)g(minds)h (of)e(ten)o(ure)338 2075 y(committees)h(than)g(journal)g(publications)j (do.)295 2149 y(I)j(b)q(eliev)o(e)i(it)d(is)i(reasonable)f(to)f (conclude)i(that)e(a)h(conference)g(publication)i(is)224 2206 y(not)15 b(equiv)m(alen)o(t)j(to)d(publication)j(in)e(an)g(arc)o (hiv)m(al)h(journal.)22 b(Conference)16 b(pap)q(ers)g(are)224 2262 y(v)o(ery)c(useful)i(in)f(rapidly)h(disseminating)g(researc)o(h)f (to)f(a)g(wide)h(audience,)i(but)d(journal)224 2319 y(pap)q(ers)i(pla)o (y)g(an)g(imp)q(ortan)o(t)f(and)h(complimen)o(tary)h(role)f(in)g (presen)o(ting)h(a)e(complete,)224 2375 y(detailed)22 b(and)f(correct)g(treatmen)o(t)e(of)i(researc)o(h)f(results)i(\(whic)o (h)f(ma)o(y)f(ha)o(v)o(e)g(b)q(een)224 2432 y(presen)o(ted)g(in)h (preliminary)g(form)e(at)g(a)g(conference\).)34 b(The)20 b(w)o(orld)g(needs)g(journal)224 2488 y(pap)q(ers)c(as)f(w)o(ell)h(as)f (conference)h(pap)q(ers!)960 2613 y(8)p eop %%Page: 9 9 9 8 bop 224 286 a Fk(6)67 b(De\014nitional)24 b(Di\016culties)224 388 y Fj(The)15 b(problems)h(of)e(giving)i(precise)g(de\014nitions)h (in)e(cryptograph)o(y)f(is)i(v)o(ery)e(c)o(halleng-)224 444 y(ing.)24 b(Ev)o(en)17 b(a)f(seemingly)h(simple)h(notion)f(suc)o(h) g(as)f(a)g(\\one-w)o(a)o(y)f(function")i(is)g(quite)224 501 y(di\016cult)h(to)d(de\014ne)i(formally)l(.)23 b(More)15 b(complicated)j(concepts,)e(suc)o(h)g(as)g(the)g(idea)h(of)224 557 y(\\existen)o(tial)d(forgery)d(in)j(an)e(adaptiv)o(e)h(c)o (hosen-message)g(attac)o(k")e(to)g(de\014ne)j(securit)o(y)224 614 y(of)h(a)h(signature)g(sc)o(heme,)g(to)q(ok)f(man)o(y)g(y)o(ears)g (to)g(dev)o(elop.)22 b(Securit)o(y)17 b(de\014nitions)g(for)224 670 y(cryptographic)c(proto)q(cols)g(\(e.g.,)f(electronic)j(v)o (oting\))d(are)h(still)h(more)f(complex.)20 b(Is)13 b(is)224 727 y(not)i(surprising)h(that)f(formal,)f(rigourous)h(pro)q(ofs)g(in)g (cryptograph)o(y)g(are)g(sometimes)224 783 y(hard)h(to)f(pro)o(vide?)22 b(After)15 b(all,)h(ho)o(w)f(can)h(w)o(e)f(pro)o(v)o(e)g(something)h (if)g(w)o(e)g(are)f(not)g(clear)224 840 y(ab)q(out)g(what)g(it)g(is)h (w)o(e)f(are)g(trying)g(to)g(pro)o(v)o(e?)295 896 y(These)f(kinds)g(of) f(de\014nitional)j(di\016culties)g(are,)d(for)g(the)h(most)e(part,)h (not)g(presen)o(t)224 952 y(in)20 b(traditional)g(pure)g(mathematics.) 32 b(W)l(e)19 b(don't)g(see)g(groups)g(of)g(mathematicians)224 1009 y(debating)g(whether)e(the)h(de\014nition)i(of)d(a)h(\014nite)g (\014eld)h(is)f(the)g(\\correct")f(de\014nition.)224 1065 y(The)12 b(concepts)g(and)g(terminology)g(in)h(mathematics)e(are)h (prett)o(y)f(m)o(uc)o(h)h(standardized)224 1122 y(and)j(w)o(ell)i (understo)q(o)q(d)e(b)o(y)g(practitioners.)21 b(It)15 b(ma)o(y)f(not)h(b)q(e)h(easy)f(to)f(pro)o(v)o(e)h(that)f(the)224 1178 y(classi\014cation)24 b(theorem)d(for)h(\014nite)h(simple)g (groups)f(is)g(true,)i(but)e(at)f(least)h(there)224 1235 y(is)e(no)f(am)o(biguit)o(y)g(in)g(in)o(trerpreting)h(what)e(the)i (theorem)e(sa)o(ys.)31 b(\(Inciden)o(tally)l(,)22 b(an)224 1291 y(in)o(teresting)16 b(discussion)g(of)e(the)h(status)f(of)g(the)h (pro)q(of)f(of)h(this)g(imp)q(ortan)o(t)f(result)h(can)224 1348 y(b)q(e)h(found)g(in)g([1)o(].\))295 1404 y(The)h(reason)f(for)g (this)h(con)o(trast)e(b)q(et)o(w)o(een)i(mathematics)f(and)h (cryptograph)o(y)f(is)224 1461 y(p)q(erhaps)23 b(based)f(on)f(the)h (orien)o(tation)g(of)g(cryptograph)o(y)e(as)i(an)g(applied)h(science.) 224 1517 y(Cryptographers)15 b(are)h(trying)g(to)f(analyze)i(and)f(pro) o(v)o(e)f(things)i(whic)o(h)g(are)e(plausibly)224 1573 y(relev)m(an)o(t)f(in)h(the)e(real)h(w)o(orld.)19 b(The)14 b(plethora)g(of)f(di\013eren)o(t)g(de\014nitional)j(mo)q(dels)e(that) 224 1630 y(arise)20 b(in)h(cryptographic)f(researc)o(h)g(is)g(a)g (re\015ection)g(of)g(the)g(fact)f(that)g(there)h(is)h(no)224 1686 y(single)16 b(\\righ)o(t")e(w)o(a)o(y)f(to)h(study)h(cryptograph)o (y)l(.)k(On)c(the)g(other)f(hand,)h(mathematics)224 1743 y(and)h(mathematical)g(pro)q(ofs)g(are)g(done)g(within)h(a)f(formal)g (mo)q(del,)g(and)g(it)h(is)f(usually)224 1799 y(irrelev)m(an)o(t)f(if)g (the)f(mo)q(del)i(\\conforms")d(in)i(an)o(y)f(meaningful)h(w)o(a)o(y)e (to)h(the)g(real)h(w)o(orld.)224 1856 y(Con)o(tro)o(v)o(ersies)10 b(o)o(v)o(er)g(the)i(v)m(alidit)o(y)g(of)f(pro)q(ofs)g(in)h (cryptograph)o(y)e(often)h(b)q(oil)h(do)o(wn)f(to)g(a)224 1912 y(di\013erence)16 b(in)f(in)o(terpretation)f(or)g(a)g (misunderstanding)i(related)f(to)e(the)i(underlying)224 1969 y(de\014nitions.)295 2025 y(F)l(or)22 b(me,)i(trying)e(to)g(sort)g (out)g(de\014nitions)i(is)f(one)g(of)f(the)g(most)g(fascinating)224 2082 y(asp)q(ects)13 b(of)g(cryptograph)o(y)l(,)f(precisely)j(b)q (ecause)f(it)g(is)f(so)g(di\016cult)i(to)d(do.)19 b(This)14 b(is)f(one)224 2138 y(feature)g(of)g(researc)o(h)h(in)g(cryptograph)o (y)e(that)h(seems)h(fundamen)o(tally)g(di\013eren)o(t)g(than)224 2194 y(researc)o(h)j(in)g(mathematics.)23 b(In)18 b(the)e(end,)h (cryptographic)g(researc)o(h)f(is)i(ric)o(her)f(\(and)224 2251 y(more)e(c)o(hallenging\))i(b)q(ecause)f(of)f(it.)960 2613 y(9)p eop %%Page: 10 10 10 9 bop 224 286 a Fk(7)67 b(Summary)224 388 y Fj(In)21 b(summary)l(,)f(the)f(main)i(p)q(oin)o(ts)f(I)g(ha)o(v)o(e)f(b)q(een)i (addressing)g(in)f(this)g(essa)o(y)f(are)h(as)224 444 y(follo)o(ws:)292 551 y Ff(\017)j Fj(A)17 b(pro)o(v)m(able)g(securit)o (y)g(pro)q(of)f(is)h(just)g(a)f(pro)q(of)g(of)h(a)f(certain)h(t)o(yp)q (e)g(of)f(securit)o(y)338 607 y(within)i(a)f(certain)h(attac)o(k)e(mo)q (del.)27 b(No)17 b(pro)o(v)m(able)h(securit)o(y)g(pro)q(of)f(should)h (b)q(e)338 664 y(in)o(terpreted)e(as)e(a)h(pro)q(of)g(of)g(securit)o(y) g(in)i(the)e(real)g(w)o(orld.)292 757 y Ff(\017)23 b Fj(The)16 b(random)g(oracle)h(mo)q(del)g(is)g(just)f(one)g(of)g(man)o (y)g(p)q(ossible)i(attac)o(k)d(mo)q(dels)338 814 y(that)i(can)i(b)q(e)g (considered)h(in)f(the)f(con)o(text)g(of)g(pro)o(v)m(able)h(securit)o (y)l(.)30 b(It)18 b(is)h(not)338 870 y(fundamen)o(tally)d(\\di\013eren) o(t")f(from)f(man)o(y)h(other)g(attac)o(k)f(mo)q(dels.)292 964 y Ff(\017)23 b Fj(There)15 b(needs)i(to)d(b)q(e)i(greater)f (emphasis)h(placed)h(on)e(publication)j(of)d(\\journal)338 1021 y(v)o(ersions")g(of)g(conference)h(publications,)h(in)f(order)g (to)e(ha)o(v)o(e)h(arc)o(hiv)m(al)i(records)338 1077 y(of)e(complete)g(and)h(correct)f(v)o(ersions)g(of)g(imp)q(ortan)o(t)g (researc)o(h)g(results.)292 1171 y Ff(\017)23 b Fj(De\014ning)c (concepts)f(in)h(cryptograph)o(y)f(precisely)i(is)e(one)g(of)g(the)g (main)h(c)o(hal-)338 1227 y(lenges)d(in)g(doing)g(go)q(o)q(d)f (cryptographic)g(researc)o(h.)224 1370 y Fk(References)270 1472 y Fj([1])21 b(M.)13 b(Asc)o(h)o(bac)o(her.)f(The)i(status)e(of)g (the)i(classi\014cation)g(of)f(\014nite)h(simple)g(groups.)340 1528 y Fh(Notic)n(es)i(of)g(the)h(AMS)d Fa(51)h Fj(\(2004\),)e (736{740.)270 1622 y([2])21 b(M.)11 b(Bellare)h(and)g(P)l(.)f(Roga)o(w) o(a)o(y)l(.)d(Random)i(oracles)i(are)f(practical:)18 b(A)12 b(paradigm)340 1679 y(for)i(designing)i(e\016cien)o(t)e(proto)q (cols.)g Fh(Pr)n(o)n(c)n(e)n(e)n(dings)f(of)i(the)h(First)f(A)o(nnual)f (Con-)340 1735 y(fer)n(enc)n(e)h(on)h(Computer)h(and)f(Communic)n (ations)g(Se)n(curity)p Fj(,)e(1993,)g(pp.)h(62{73.)270 1829 y([3])21 b(S.)d(Blak)o(e-Wilson,)g(D.)f(Johnson)h(and)f(A.J.)g (Menezes.)h(Key)g(agreemen)o(t)f(pro-)340 1885 y(to)q(cols)e(and)g (their)h(securit)o(y)f(analysis.)g Fh(L)n(e)n(ctur)n(e)g(Notes)g(in)h (Computer)g(Scienc)n(e)340 1942 y Fa(1355)e Fj(\(1997\),)d(30{45)h (\(Sixth)h(IMA)g(In)o(ternational)h(Conference)f(on)g(Cryptog-)340 1998 y(raph)o(y)i(and)h(Co)q(ding\).)270 2092 y([4])21 b(R.)g(Canetti,)h(O.)g(Goldreic)o(h)g(and)g(S.)f(Halevi.)h(The)g (random)f(oracle)h(mo)q(del)340 2149 y(revisited.)16 b Fh(STOC)f(1998)i(Pr)n(o)n(c)n(e)n(e)n(dings)p Fj(,)c(pp.)i(209{218.) 270 2242 y([5])21 b(R.)16 b(Cramer)g(and)h(V.)f(Shoup.)h(A)f(practical) i(public)h(k)o(ey)d(cryptosystem)g(pro)o(v-)340 2299 y(ably)i(secure)g(against)f(adaptiv)o(e)g(c)o(hosen)h(ciphertext)g (attac)o(k.)e Fh(L)n(e)n(ctur)n(e)h(Notes)340 2355 y(in)g(Computer)i (Scienc)n(e)c Fa(1462)i Fj(\(1998\),)e(13{25)g(\(Adv)m(ances)i(in)h (Cryptology)e({)340 2412 y(CR)l(YPTO)f('98\).)949 2613 y(10)p eop %%Page: 11 11 11 10 bop 270 286 a Fj([6])21 b(O.)32 b(Goldreic)o(h.)h(The)g(role)f (of)g(program)f(committees.)h(Av)m(ailable)i(from)340 343 y Fe(http://www.wisdom.weizmann.a)o(c.il/\~od)o(ed/on-p)o(c.html)p Fj(.)270 437 y([7])21 b(L.)181 b(Kn)o(udsen.)h(Quotes.)e(Av)m(ailable)j (from)340 493 y Fe(http://www.mat.dtu.dk/people)o(/Lars.R.)o(Knudsen)o (/quotes)o(.html)p Fj(.)270 587 y([8])21 b(N.)31 b(Koblitz)h(and)f (A.J.)f(Menezes.)h(Another)g(lo)q(ok)g(at)f(\\pro)o(v)m(able)h(secu-) 340 643 y(rit)o(y".)21 b(Cryptology)g(ePrin)o(t)h(Arc)o(hiv)o(e:)34 b(Rep)q(ort)21 b(2004/152,)g(a)o(v)m(ailable)i(from)340 700 y Fe(http://eprint.iacr.org/)p Fj(.)270 794 y([9])e(D.)e(R.)g (Stinson.)h Fh(Crypto)n(gr)n(aphy:)29 b(The)n(ory)20 b(and)g(Pr)n(actic)n(e,)h(Se)n(c)n(ond)e(Edition.)340 850 y Fj(CR)o(C)14 b(Press,)h(2002.)949 2613 y(11)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF