%!PS-Adobe-2.0 %%Creator: dvips 5.519 Copyright 1986, 1993 Radical Eye Software %%Title: jour.dvi %%CreationDate: Mon Mar 13 18:43:19 1995 %%Pages: 15 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSCommandLine: dvips jour %DVIPSSource: TeX output 1995.03.13:1843 %%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 4 get round 4 exch put dup dup 5 get round 5 exch put 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 add]{ 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 showpage userdict /eop-hook known{eop-hook}if}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 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/hosts/wisdom/users/naor/PAPERS/CRYPTO/UOWHF/jour.dvi) @start /Fa 1 51 df50 D E /Fb 2 84 df80 D83 D E /Fc 4 50 df<020408103020604040C0C0C0C0C0 C0C0C0404060203010080402071A7F920C>40 D<8040201018080C040406060606060606 0604040C081810204080071A7E920C>I<1F00318060C04040C060C060C060C060C060C0 60C060C060404060C031801F000B107F8F0F>48 D<0C003C00CC000C000C000C000C000C 000C000C000C000C000C000C000C00FF8009107E8F0F>I E /Fd 13 113 df<01E0021804080C00080018000C000E00070007800CC0106020606020C020C0 20C06080408040C080C08063003C000D177E9610>14 D<60F0F070101020204040040A7D 830A>59 D<0018001800380030003000700060006000E000C001C0018001800380030003 000700060006000E000C000C001C001800380030003000700060006000E000C000C0000D 217E9812>61 D<071018F0307060706060C060C060C06080C080C480C4C1C446C838700E 0E7E8D13>97 D<7C0018001800180018003000300030003000678068C070406060C060C0 60C060C06080C080C08180C10046003C000B177E960F>I<003E000C000C000C000C0018 001800180018073018F0307060706060C060C060C06080C080C480C4C1C446C838700F17 7E9612>100 D<0300038003000000000000000000000000001C002400460046008C000C 0018001800180031003100320032001C0009177F960C>105 D<00180038001000000000 000000000000000001C0022004300430086000600060006000C000C000C000C001800180 018001806300E300C60078000D1D80960E>I<1F0006000600060006000C000C000C000C 00181C1866188E190C32003C003F00318060C060C460C460C8C0C8C0700F177E9612>I< 3E0C0C0C0C181818183030303060606060C0C8C8C8D07007177E960B>I<383C1E0044C6 630047028100460301008E0703000C0603000C0603000C060600180C0600180C0620180C 0C20180C0C4030180440301807801B0E7F8D1F>I<383C0044C6004702004602008E0600 0C06000C06000C0C00180C00180C40181840181880300880300F00120E7F8D15>I<1C3C 22462382230346030603060306030C060C060C0C0C081A3019E018001800300030003000 FC001014808D12>112 D E /Fe 2 108 df<040C00000000007058989830306064646830 06127E910B>105 D<3C000C000C00180018001800187031903230340038007F00618061 906190C1A0C0C00C117E9010>107 D E /Ff 7 62 df<0102040C1818303070606060E0 E0E0E0E0E0E0E0E0E060606070303018180C04020108227D980E>40 D<8040203018180C0C0E060606070707070707070707070606060E0C0C18183020408008 227E980E>I<003000003000003000003000003000003000003000003000003000003000 003000FFFFFCFFFFFC003000003000003000003000003000003000003000003000003000 00300000300016187E931B>43 D<07C018303018701C600C600CE00EE00EE00EE00EE00E E00EE00EE00EE00E600C600C701C30181C7007C00F157F9412>48 D<03000700FF000700070007000700070007000700070007000700070007000700070007 00070007007FF00C157E9412>I<0F8030E040708030C038E03840380038007000700060 00C00180030006000C08080810183FF07FF0FFF00D157E9412>I61 D E /Fg 47 122 df<000FF000007FFC0001F80E0003E01F0007C03F000F803F000F803F 000F801E000F800C000F8000000F8000000F8000000F800000FFFFFF00FFFFFF000F801F 000F801F000F801F000F801F000F801F000F801F000F801F000F801F000F801F000F801F 000F801F000F801F000F801F000F801F000F801F000F801F000F801F000F801F007FF0FF E07FF0FFE01B237FA21F>12 D<0007F80FF000007FFE7FFC0001F80FF80E0003E00FE01F 0007C01FC03F000F801F803F000F801F803F000F800F801E000F800F800C000F800F8000 000F800F8000000F800F8000000F800F800000FFFFFFFFFF00FFFFFFFFFF000F800F801F 000F800F801F000F800F801F000F800F801F000F800F801F000F800F801F000F800F801F 000F800F801F000F800F801F000F800F801F000F800F801F000F800F801F000F800F801F 000F800F801F000F800F801F000F800F801F000F800F801F000F800F801F007FF07FF0FF E07FF07FF0FFE02B237FA22F>14 D<3803807C07C0FE0FE0FF0FF0FF0FF07F07F03B03B0 0300300300300700700600600600600C00C01C01C018018070070020020014117EA21D> 34 D<387CFEFFFF7F3B03030706060C1C18702008117CA210>39 D45 D<387CFEFEFE7C3807077C8610>I<0018000078 0001F800FFF800FFF80001F80001F80001F80001F80001F80001F80001F80001F80001F8 0001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F8 0001F80001F80001F80001F8007FFFE07FFFE013207C9F1C>49 D<03FC000FFF003C1FC0 7007E07C07F0FE03F0FE03F8FE03F8FE01F87C01F83803F80003F80003F00003F00007E0 0007C0000F80001F00003E0000380000700000E01801C0180380180700180E00380FFFF0 1FFFF03FFFF07FFFF0FFFFF0FFFFF015207D9F1C>I<00FE0007FFC00F07E01E03F03F03 F03F81F83F81F83F81F81F03F81F03F00003F00003E00007C0001F8001FE0001FF000007 C00001F00001F80000FC0000FC3C00FE7E00FEFF00FEFF00FEFF00FEFF00FC7E01FC7801 F81E07F00FFFC001FE0017207E9F1C>I<0000E00001E00003E00003E00007E0000FE000 1FE0001FE00037E00077E000E7E001C7E00187E00307E00707E00E07E00C07E01807E038 07E07007E0E007E0FFFFFEFFFFFE0007E00007E00007E00007E00007E00007E00007E000 FFFE00FFFE17207E9F1C>I<1000201E01E01FFFC01FFF801FFF001FFE001FF8001BC000 18000018000018000018000019FC001FFF001E0FC01807E01803E00003F00003F00003F8 0003F83803F87C03F8FE03F8FE03F8FC03F0FC03F07007E03007C01C1F800FFF0003F800 15207D9F1C>I<387CFEFEFE7C380000000000000000387CFEFEFE7C3807167C9510>58 D<000070000000007000000000F800000000F800000000F800000001FC00000001FC0000 0003FE00000003FE00000003FE00000006FF000000067F0000000E7F8000000C3F800000 0C3F800000183FC00000181FC00000381FE00000300FE00000300FE00000600FF0000060 07F00000E007F80000FFFFF80000FFFFF800018001FC00018001FC00038001FE00030000 FE00030000FE000600007F000600007F00FFE00FFFF8FFE00FFFF825227EA12A>65 DI<0003 FE0080001FFF818000FF01E38001F8003F8003E0001F8007C0000F800F800007801F8000 07803F000003803F000003807F000001807E000001807E00000180FE00000000FE000000 00FE00000000FE00000000FE00000000FE00000000FE00000000FE000000007E00000000 7E000001807F000001803F000001803F000003801F800003000F8000030007C000060003 F0000C0001F800380000FF00F000001FFFC0000003FE000021227DA128>IIII72 D<0007FC0000003FFF800000FC 07E00003F001F80007E000FC000FC0007E001F80003F001F80003F003F00001F803F0000 1F807F00001FC07E00000FC07E00000FC0FE00000FE0FE00000FE0FE00000FE0FE00000F E0FE00000FE0FE00000FE0FE00000FE0FE00000FE0FE00000FE07E00000FC07F00001FC0 7F00001FC03F00001F803F80003F801F80003F000FC0007E0007E000FC0003F001F80000 FC07E000003FFF80000007FC000023227DA12A>79 DI<01FC0407FF8C1F03FC3C007C7C003C 78001C78001CF8000CF8000CFC000CFC0000FF0000FFE0007FFF007FFFC03FFFF01FFFF8 0FFFFC03FFFE003FFE0003FF00007F00003F00003FC0001FC0001FC0001FE0001EE0001E F0003CFC003CFF00F8C7FFE080FF8018227DA11F>83 D<7FFFFFFF807FFFFFFF807E03F8 0F807803F807807003F803806003F80180E003F801C0E003F801C0C003F800C0C003F800 C0C003F800C0C003F800C00003F800000003F800000003F800000003F800000003F80000 0003F800000003F800000003F800000003F800000003F800000003F800000003F8000000 03F800000003F800000003F800000003F800000003F800000003F800000003F800000003 F8000003FFFFF80003FFFFF80022227EA127>II87 D<0400400E00E0180180380380300300600600600600E00E00C0 0C00C00C00DC0DC0FE0FE0FF0FF0FF0FF07F07F03E03E01C01C014117AA21D>92 D<07FC001FFF803F07C03F03E03F01E03F01F01E01F00001F00001F0003FF003FDF01FC1 F03F01F07E01F0FC01F0FC01F0FC01F0FC01F07E02F07E0CF81FF87F07E03F18167E951B >97 D<00FF8007FFE00F83F01F03F03E03F07E03F07C01E07C0000FC0000FC0000FC0000 FC0000FC0000FC00007C00007E00007E00003E00301F00600FC0E007FF8000FE0014167E 9519>99 D<0001FE000001FE0000003E0000003E0000003E0000003E0000003E0000003E 0000003E0000003E0000003E0000003E0000003E0001FC3E0007FFBE000F81FE001F007E 003E003E007E003E007C003E00FC003E00FC003E00FC003E00FC003E00FC003E00FC003E 00FC003E00FC003E007C003E007C003E003E007E001E00FE000F83BE0007FF3FC001FC3F C01A237EA21F>I<00FE0007FF800F87C01E01E03E01F07C00F07C00F8FC00F8FC00F8FF FFF8FFFFF8FC0000FC0000FC00007C00007C00007E00003E00181F00300FC07003FFC000 FF0015167E951A>I<003F8000FFC001E3E003C7E007C7E00F87E00F83C00F80000F8000 0F80000F80000F80000F8000FFFC00FFFC000F80000F80000F80000F80000F80000F8000 0F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F8000 7FF8007FF80013237FA211>I<03FC1E0FFF7F1F0F8F3E07CF3C03C07C03E07C03E07C03 E07C03E07C03E03C03C03E07C01F0F801FFF0013FC003000003000003800003FFF801FFF F00FFFF81FFFFC3800FC70003EF0001EF0001EF0001EF0001E78003C7C007C3F01F80FFF E001FF0018217E951C>II<1C003F007F007F007F003F001C000000000000000000 000000000000FF00FF001F001F001F001F001F001F001F001F001F001F001F001F001F00 1F001F001F001F001F00FFE0FFE00B247EA310>I107 DIII<00FE0007FFC00F83E01E00F03E00F87C007C7C007C7C00 7CFC007EFC007EFC007EFC007EFC007EFC007EFC007E7C007C7C007C3E00F81F01F00F83 E007FFC000FE0017167E951C>II114 D<0FF3003FFF00781F00600700E00300E00300F00300FC00007FE0007F F8003FFE000FFF0001FF00000F80C00780C00380E00380E00380F00700FC0E00EFFC00C7 F00011167E9516>I<0180000180000180000180000380000380000780000780000F8000 3F8000FFFF00FFFF000F80000F80000F80000F80000F80000F80000F80000F80000F8000 0F80000F80000F81800F81800F81800F81800F81800F830007C30003FE0000F80011207F 9F16>IIII121 D E /Fh 15 107 df0 D<07E01FF8381C700E6006E007C003C003C003C003C003C003E0076006700E381C 1FF807E010127D9317>14 D<07E01FF83FFC7FFE7FFEFFFFFFFFFFFFFFFFFFFFFFFFFFFF FFFF7FFE7FFE3FFC1FF807E010127D9317>I<000000C0000003C000000F0000003C0000 00F0000003C000000F0000001C00000078000001E00000078000001E00000078000000E0 000000780000001E0000000780000001E0000000780000001C0000000F00000003C00000 00F00000003C0000000F00000003C0000000C00000000000000000000000000000000000 0000000000000000000000FFFFFFC0FFFFFFC01A247C9C23>20 DI<0000 000400000000020000000002000000000100000000008000000000400000000020FFFFFF FFFCFFFFFFFFFC0000000020000000004000000000800000000100000000020000000002 00000000040026107D922D>33 D<007FF801FFF80780000E00001C000038000030000070 0000600000600000E00000C00000C00000FFFFF8FFFFF8C00000C00000E0000060000060 00007000003000003800001C00000E000007800001FFF8007FF8151C7C981E>50 D<00000C00000C00001C0000180000380000300000700000600000E00000C00001C00001 80000380000300000700000600000E00000C00001C000018000038000030000030000070 0000600000E00000C00001C0000180000380000300000700000600000E00000C00001C00 00180000380000300000700000600000E00000C00000C00000162C7AA000>54 DIII<003800003800003800007C00006C0000EE0000 C60000C60001C7000183000383800301800301800701C00600C00E00E00C00600C00601C 007018003038003830001830001870001C60000CE0000EC00006C00006171C7D9A1E>94 D<000F0038006000E001C001C001C001C001C001C001C001C001C001C001C001C001C001 C001C0038007001E00F8001E000700038001C001C001C001C001C001C001C001C001C001 C001C001C001C001C001C000E000600038000F102D7DA117>102 DI106 D E /Fi 47 123 df<001E0000610000C0800180800180000380000300 0003800003800003C00001F00000F800007C0001FC00070E000E0E001E06001C06003C06 00780600780600780600F00400F00400F00C00F00800F008007018007010003020001840 000F800011207E9F14>14 D<007E01C007000E001C003C003800780078007FF0F000F000 F000700070007000300018000C1807E00F147E9312>I<70F8F8F87005057C840D>58 D<70F8FCFC74040404080810102040060E7C840D>I<000001C00000078000001E000000 78000001E00000078000000E0000003C000000F0000003C000000F0000003C000000F000 0000F00000003C0000000F00000003C0000000F00000003C0000000E0000000780000001 E0000000780000001E0000000780000001C01A1A7C9723>I<0003000300070006000600 0E000C000C001C0018001800380030003000700060006000E000C000C001C00180018001 800380030003000700060006000E000C000C001C00180018003800300030007000600060 00E000C000C000102D7DA117>II<000002000000060000000E0000000E0000001E 0000001F0000002F0000002F0000004F0000008F0000008F0000010F0000010F0000020F 0000040F0000040F0000080F8000080780001007800020078000200780007FFF80004007 8000800780018007800100078002000780020007C0040003C00C0003C01E0007C0FF807F FC1E207E9F22>65 D<00FFFFE0000F0078000F003C000F001C000F001E001E001E001E00 1E001E001E001E001E003C003C003C003C003C0078003C00F0007803C0007FFF80007803 C0007801E000F000F000F000F000F000F000F0007001E000F001E000F001E000F001E000 E003C001E003C003C003C0038003C00F0007801E00FFFFF0001F1F7E9E22>I<0000FE02 00078186001C004C0038003C0060003C00C0001C01C0001803800018070000180F000018 1E0000101E0000103C0000003C00000078000000780000007800000078000000F0000000 F0000000F0000000F0000000F00000807000008070000080700001003800010038000200 180004000C001800060020000381C00000FE00001F217E9F21>I<00FFFFE000000F0078 00000F001C00000F000E00000F000700001E000700001E000380001E000380001E000380 003C000380003C000380003C000380003C00038000780007800078000780007800078000 7800078000F0000F0000F0000F0000F0000E0000F0001E0001E0001C0001E0003C0001E0 00380001E000700003C000E00003C001C00003C003800003C007000007803C0000FFFFF0 0000211F7E9E26>I<00FFFFFF000F000E000F0006000F0002000F0002001E0002001E00 02001E0002001E0002003C0404003C0400003C0400003C0C0000781800007FF800007818 000078180000F0100000F0100000F0100000F0000401E0000801E0000801E0001001E000 1003C0002003C0006003C0004003C001C0078007C0FFFFFF80201F7E9E22>I<00FFFFFF 000F000E000F0006000F0002000F0002001E0002001E0002001E0002001E0002003C0004 003C0400003C0400003C04000078080000781800007FF8000078180000F0100000F01000 00F0100000F0100001E0000001E0000001E0000001E0000003C0000003C0000003C00000 03C0000007C00000FFFE0000201F7E9E1D>I<00007E0100038183000E00460038002E00 70001E00E0000E01C0000C0380000C0700000C0F00000C1E0000081E0000083C0000003C 00000078000000780000007800000078000000F0000000F0007FFCF00001E0F00001E0F0 0003C0700003C0700003C0700003C038000780380007801C000F800C000B800600330003 80C100007F000020217E9F24>I<00FFF9FFF0000F801F00000F001E00000F001E00000F 001E00001E003C00001E003C00001E003C00001E003C00003C007800003C007800003C00 7800003C007800007800F000007FFFF000007800F000007800F00000F001E00000F001E0 0000F001E00000F001E00001E003C00001E003C00001E003C00001E003C00003C0078000 03C007800003C007800003C007800007C00F8000FFF8FFF800241F7E9E26>I<00FFF80F F8000F8003E0000F000380000F000200000F000400001E000800001E002000001E004000 001E008000003C010000003C040000003C080000003C180000007838000000787C000000 793C0000007A3C000000F41E000000F81E000000F01E000000F00F000001E00F000001E0 0F000001E007800001E007800003C007800003C003C00003C003C00003C003C00007C003 E000FFFC3FFC00251F7E9E27>75 D<00FFFC00000F8000000F0000000F0000000F000000 1E0000001E0000001E0000001E0000003C0000003C0000003C0000003C00000078000000 780000007800000078000000F0000000F0000000F0000000F0004001E0008001E0008001 E0018001E0010003C0030003C0030003C0060003C00E0007803C00FFFFFC001A1F7E9E1F >I<00FF00001FF0000F00003F00000B80003E00000B80005E00000B80005E0000138000 BC00001380013C00001380013C00001380023C0000238002780000238004780000238008 78000021C00878000041C010F0000041C020F0000041C020F0000041C040F0000081C041 E0000081C081E0000081C101E0000081C101E0000100E203C0000100E203C0000100E403 C0000100E803C0000200E80780000200F00780000200F00780000600E00780000F00C00F 8000FFE0C1FFF8002C1F7E9E2C>I<00FF803FF0000F800780000F800200000BC0020000 0BC002000013C004000011E004000011E004000011E004000020F008000020F008000020 F808000020780800004078100000403C100000403C100000403C100000801E200000801E 200000801E200000800F200001000F400001000F4000010007C000010007C00002000780 000200038000020003800006000380000F00010000FFE0010000241F7E9E25>I<0001FC 0000070700001C01C0003000E000E0006001C000700380007007800038070000380E0000 381E0000381C0000383C0000383C00003878000078780000787800007878000078F00000 F0F00000F0F00000E0F00001E0F00001C0F00003C0700003807000070078000F0038001E 0038003C001C0070000E00E0000783800001FC00001D217E9F23>I<00FFFFC0000F0070 000F0038000F001C000F001E001E001E001E001E001E001E001E001E003C003C003C003C 003C0078003C0070007800E000780380007FFE000078000000F0000000F0000000F00000 00F0000001E0000001E0000001E0000001E0000003C0000003C0000003C0000003C00000 07C00000FFFC00001F1F7E9E1D>I<0007E0800018118000300B000060070000C0070001 C0030001800200038002000380020003800200038000000380000003C0000003F8000003 FF800001FFC00000FFE000003FF0000003F0000000F00000007000000070000000700020 00700020007000200060006000E0006000C0006001C00070018000E8030000C60E000081 F8000019217D9F1C>83 D<7FFC1FF807C003C00780010007800100078001000F0002000F 0002000F0002000F0002001E0004001E0004001E0004001E0004003C0008003C0008003C 0008003C00080078001000780010007800100078001000F0002000F0002000F0002000F0 004000F0004000700080007001000030020000380400000C18000007E000001D207C9E1F >85 DI<00F1800389C0 0707800E03801C03803C0380380700780700780700780700F00E00F00E00F00E00F00E10 F01C20F01C20703C20705C40308C400F078014147E9318>97 D<07803F80070007000700 07000E000E000E000E001C001C001CF01D0C3A0E3C0E380F380F700F700F700F700FE01E E01EE01EE01CE03CE038607060E031C01F0010207E9F14>I<007C01C207010E0F1E0F1C 0E3C04780078007800F000F000F000F000F00070017002300418380FC010147E9314>I< 0000780003F80000700000700000700000700000E00000E00000E00000E00001C00001C0 00F1C00389C00707800E03801C03803C0380380700780700780700780700F00E00F00E00 F00E00F00E10F01C20F01C20703C20705C40308C400F078015207E9F18>I<00007C0000 CE00019E00039E00030C000700000700000700000700000E00000E00000E0000FFF0000E 00000E00001C00001C00001C00001C00001C000038000038000038000038000038000070 0000700000700000700000700000E00000E00000E00000E00000C00001C0003180007980 00F300006200003C000017297E9F16>102 D<001E3000713800E0F001C0700380700780 700700E00F00E00F00E00F00E01E01C01E01C01E01C01E01C01E03801E03800E07800E0B 8006170001E700000700000700000E00000E00300E00781C00F038006070003FC000151D 809316>I<01E0000FE00001C00001C00001C00001C00003800003800003800003800007 0000070000071F000761800E80C00F00C00E00E00E00E01C01C01C01C01C01C01C01C038 0380380380380380380704700708700E08700E10700610E006206003C016207E9F1A>I< 00E001E001E000C000000000000000000000000000000E00130023804380438043808700 070007000E000E001C001C001C20384038403840388019000E000B1F7E9E10>I<0000C0 0001E00001E00001C0000000000000000000000000000000000000000000001E00006300 004380008380010380010380020700000700000700000700000E00000E00000E00000E00 001C00001C00001C00001C0000380000380000380000380000700000700030700078E000 F1C0006380003E00001328819E13>I<01E0000FE00001C00001C00001C00001C0000380 000380000380000380000700000700000701E00706100E08700E10F00E20F00E40601C80 001D00001E00001FC000387000383800383800381C20703840703840703840701880E018 80600F0014207E9F18>I<03C01FC0038003800380038007000700070007000E000E000E 000E001C001C001C001C0038003800380038007000700070007100E200E200E200E20064 0038000A207E9F0E>I<1E07C07C00231861860023A032030043C0340300438038038043 8038038087007007000700700700070070070007007007000E00E00E000E00E00E000E00 E00E000E00E01C101C01C01C201C01C038201C01C038401C01C018403803801880180180 0F0024147E9328>I<1E07802318C023A06043C0704380704380708700E00700E00700E0 0700E00E01C00E01C00E01C00E03821C03841C07041C07081C03083803101801E017147E 931B>I<007C0001C3000301800E01C01E01C01C01E03C01E07801E07801E07801E0F003 C0F003C0F003C0F00780F00700700F00700E0030180018700007C00013147E9316>I<03 C1E004621804741C08781C08701E08701E10E01E00E01E00E01E00E01E01C03C01C03C01 C03C01C0380380780380700380E003C1C0072380071E000700000700000E00000E00000E 00000E00001C00001C0000FFC000171D819317>I<00F0400388C00705800E03801C0380 3C0380380700780700780700780700F00E00F00E00F00E00F00E00F01C00F01C00703C00 705C0030B8000F380000380000380000700000700000700000700000E00000E0000FFE00 121D7E9314>I<1E1E0023210023C38043C7804387804383008700000700000700000700 000E00000E00000E00000E00001C00001C00001C00001C000038000018000011147E9315 >I<007C018203010603060706060E00078007F803FC01FE001F00077007F006F006E004 400820301FC010147E9315>I<00C000E001C001C001C001C003800380FFF80380070007 00070007000E000E000E000E001C001C001C001C10382038203820384018800F000D1C7F 9B10>I<0F006060118070F02180E0F821C0E07841C0E0384380E0188381C0100701C010 0701C0100701C0100E0380200E0380200E0380200E0380400E0380400E0380800E078080 060781000709860001F078001D147E9321>119 D<03C1C00C62201034701038F02038F0 20386040700000700000700000700000E00000E00000E00000E02061C040F1C040F1C080 E2C080446300383C0014147E931A>I<0F00601180702180E021C0E041C0E04380E08381 C00701C00701C00701C00E03800E03800E03800E03800E07000C07000C07000E0F00061E 0003EE00000E00000E00001C0078180078380070700060600021C0001F0000141D7E9316 >I<01E02003F04007F8C00C1F8008010000020000040000080000100000600000C00001 00000200000400800801001003003F060061FC0040F80080700013147E9315>I E /Fj 38 122 df45 D<000E00001E00007E0007FE00FFFE00FFFE00F8FE0000FE0000FE0000FE0000FE0000FE 0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE 0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE 007FFFFE7FFFFE7FFFFE17277BA622>49 D<00FF800003FFF0000FFFFC003F03FF007C00 FF807C007FC0FE007FC0FF003FE0FF003FE0FF003FE0FF001FE07E001FE03C003FE00000 3FE000003FC000003FC000007F8000007F800000FF000001FE000001FC000003F0000007 E000000FC000001F0000003E0000007C00E0007800E000F000E001E001C0038001C00700 01C00FFFFFC01FFFFFC03FFFFFC07FFFFFC0FFFFFF80FFFFFF80FFFFFF801B277DA622> I<007F800003FFF00007FFFC001F81FE001F00FF003F80FF003F807F803FC07F803F807F 803F807F801F007F800000FF800000FF000000FF000001FE000003F8000007F00000FFC0 0000FFF0000001FC000000FF0000007F8000007FC000003FC000003FE000003FE000003F E03C003FE07E003FE0FF003FE0FF003FE0FF003FC0FF007FC0FE007F807C00FF803F01FF 001FFFFC0007FFF00000FF80001B277DA622>I<00000E0000001E0000003E0000007E00 0000FE000000FE000001FE000003FE0000077E00000E7E00000E7E00001C7E0000387E00 00707E0000E07E0000E07E0001C07E0003807E0007007E000E007E000E007E001C007E00 38007E0070007E00E0007E00FFFFFFF8FFFFFFF8FFFFFFF80000FE000000FE000000FE00 0000FE000000FE000000FE000000FE000000FE00007FFFF8007FFFF8007FFFF81D277EA6 22>I<0C0003000F803F000FFFFE000FFFFE000FFFFC000FFFF8000FFFE0000FFFC0000F FE00000E0000000E0000000E0000000E0000000E0000000E0000000E7FC0000FFFF8000F 80FE000E007F000C003F8000003F8000001FC000001FC000001FE000001FE018001FE07E 001FE0FE001FE0FE001FE0FE001FE0FE001FE0FE001FC078003FC078003F803C007F001F 01FE000FFFFC0003FFF00000FF80001B277DA622>I<0007F000003FFC0000FFFF0001FC 0F0007F01F800FE03F800FC03F801FC03F803F803F803F801F007F8000007F0000007F00 00007F000000FF000000FF0FC000FF3FF800FF70FE00FFE03F00FFC03F80FF801FC0FF80 1FC0FF801FC0FF001FE0FF001FE0FF001FE0FF001FE07F001FE07F001FE07F001FE07F00 1FE03F801FC03F801FC01F803F800FC03F8007E0FF0003FFFC0000FFF000003FC0001B27 7DA622>I<000003800000000007C00000000007C0000000000FE0000000000FE0000000 000FE0000000001FF0000000001FF0000000003FF8000000003FF8000000003FF8000000 0073FC0000000073FC00000000F3FE00000000E1FE00000000E1FE00000001C0FF000000 01C0FF00000003C0FF80000003807F80000007807FC0000007003FC0000007003FC00000 0E003FE000000E001FE000001E001FF000001C000FF000001FFFFFF000003FFFFFF80000 3FFFFFF80000780007FC0000700003FC0000700003FC0000E00001FE0000E00001FE0001 E00001FF0001C00000FF0001C00000FF00FFFE001FFFFEFFFE001FFFFEFFFE001FFFFE2F 297EA834>65 D<00003FF001800003FFFE0780000FFFFF8F80003FF007FF8000FF8001FF 8001FE00007F8007FC00003F8007F800001F800FF000000F801FE000000F803FE0000007 803FC0000007807FC0000003807FC0000003807FC000000380FF8000000000FF80000000 00FF8000000000FF8000000000FF8000000000FF8000000000FF8000000000FF80000000 00FF8000000000FF8000000000FF80000000007FC0000000007FC0000003807FC0000003 803FC0000003803FE0000003801FE0000007800FF00000070007F800000F0007FC00001E 0001FE00003C0000FF8000F800003FF007F000000FFFFFC0000003FFFF000000003FF800 0029297CA832>67 D70 D72 DI<0000FFE00000 0007FFFC0000003FC07F8000007F001FC00001FC0007F00003F80003F80007F00001FC00 0FF00001FE001FE00000FF001FE00000FF003FC000007F803FC000007F807FC000007FC0 7F8000003FC07F8000003FC07F8000003FC0FF8000003FE0FF8000003FE0FF8000003FE0 FF8000003FE0FF8000003FE0FF8000003FE0FF8000003FE0FF8000003FE0FF8000003FE0 FF8000003FE07F8000003FC07FC000007FC07FC000007FC03FC000007F803FC000007F80 1FE00000FF001FE00000FF000FF00001FE0007F00001FC0003F80003F80001FC0007F000 00FF001FE000003FC07F8000000FFFFE00000000FFE000002B297CA834>79 D82 D<007F806003FFF0E00FFFFFE01F807FE03F001FE07E0007E07E0003E07C0003E0FC 0001E0FC0001E0FC0000E0FE0000E0FE0000E0FF000000FFC000007FFE00007FFFE0003F FFFC003FFFFF001FFFFF8007FFFFC003FFFFE000FFFFF00007FFF000007FF000000FF800 0007F8000003F8E00003F8E00001F8E00001F8E00001F8F00001F8F00001F0F80003F0FC 0003E0FF0007E0FFE01FC0FFFFFF00E0FFFE00C01FF0001D297CA826>I<7FFFFFFFFFC0 7FFFFFFFFFC07FFFFFFFFFC07F803FC03FC07E003FC007C078003FC003C078003FC003C0 70003FC001C0F0003FC001E0F0003FC001E0E0003FC000E0E0003FC000E0E0003FC000E0 E0003FC000E0E0003FC000E000003FC0000000003FC0000000003FC0000000003FC00000 00003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC00000 00003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC00000 00003FC0000000003FC0000000003FC0000000003FC0000000003FC0000000003FC00000 007FFFFFE000007FFFFFE000007FFFFFE0002B287EA730>II<01FF800007FFF0000F81 FC001FC0FE001FC07F001FC07F001FC03F800F803F8000003F8000003F8000003F80000F FF8000FFFF8007FC3F801FE03F803F803F807F803F807F003F80FE003F80FE003F80FE00 3F80FE007F80FF007F807F00FFC03F83DFFC0FFF0FFC01FC03FC1E1B7E9A21>97 DI<001FF80000FFFE0003F01F000FE03F801FC03F803F803F803F803F807F801F007F00 0000FF000000FF000000FF000000FF000000FF000000FF000000FF000000FF000000FF00 00007F0000007F8000003F8001C03FC001C01FC003C00FE0078003F01F0000FFFC00001F E0001A1B7E9A1F>I<00003FF80000003FF80000003FF800000003F800000003F8000000 03F800000003F800000003F800000003F800000003F800000003F800000003F800000003 F800000003F800000003F800001FE3F80000FFFBF80003F03FF8000FE00FF8001FC007F8 003F8003F8003F8003F8007F8003F8007F0003F800FF0003F800FF0003F800FF0003F800 FF0003F800FF0003F800FF0003F800FF0003F800FF0003F800FF0003F8007F0003F8007F 0003F8003F8003F8003F8007F8001FC00FF8000FE01FF80003F03FFF8000FFF3FF80003F C3FF80212A7EA926>I<003FE00001FFF80003F07E000FE03F001FC01F803F800FC03F80 0FC07F000FC07F0007E0FF0007E0FF0007E0FF0007E0FFFFFFE0FFFFFFE0FF000000FF00 0000FF000000FF0000007F0000007F8000003F8000E03F8001E01FC001C00FE003C003F8 1F8000FFFE00001FF0001B1B7E9A20>I<0007F0003FFC00FE3E01FC7F03F87F03F87F07 F07F07F03E07F00007F00007F00007F00007F00007F00007F000FFFFC0FFFFC0FFFFC007 F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007 F00007F00007F00007F00007F00007F00007F00007F00007F0007FFF807FFF807FFF8018 2A7EA915>I<00FF81F003FFE7FC0FC1FE7C1F80FC7C3F80FE7C3F007E107F007F007F00 7F007F007F007F007F007F007F007F007F003F007E003F80FE001F80FC000FC1F8001FFF E00018FF8000380000003C0000003C0000003E0000003FFFF8003FFFFF001FFFFFC00FFF FFE007FFFFF01FFFFFF07E0007F87C0001F8F80001F8F80000F8F80000F8F80000F8FC00 01F87E0003F03F0007E00FC01F8003FFFE00007FF0001E287E9A22>II<07001FC01FE0 3FE03FE03FE01FE01FC007000000000000000000000000000000FFE0FFE0FFE00FE00FE0 0FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE0 0FE0FFFEFFFEFFFE0F2B7DAA14>I107 DIII<003FE00001FFFC0003F07E000FC01F801F800FC03F800FE03F0007 E07F0007F07F0007F07F0007F0FF0007F8FF0007F8FF0007F8FF0007F8FF0007F8FF0007 F8FF0007F8FF0007F87F0007F07F0007F03F800FE03F800FE01F800FC00FC01F8007F07F 0001FFFC00003FE0001D1B7E9A22>I114 D<03FE300FFFF03E03F07800F07000F0F00070F00070F80070FC0000FFE000FFFE007FFF C03FFFE01FFFF007FFF800FFFC0003FC0000FCE0007CE0003CF0003CF0003CF80078FC00 78FF01F0F7FFC0C1FF00161B7E9A1B>I<00700000700000700000700000F00000F00000 F00001F00003F00003F00007F0001FFFF0FFFFF0FFFFF007F00007F00007F00007F00007 F00007F00007F00007F00007F00007F00007F00007F00007F00007F03807F03807F03807 F03807F03807F03807F03803F87001F8F000FFE0001F8015267FA51B>IIII 121 D E /Fk 57 123 df<00FC000182000703000607000E02000E00000E00000E00000E 00000E0000FFFF000E07000E07000E07000E07000E07000E07000E07000E07000E07000E 07000E07000E07000E07000E07007F0FE0131A809915>12 D<60F0F07010101020204080 040B7D830B>44 DI<60F0F06004047D830B>I<07801860303030 3060186018E01CE01CE01CE01CE01CE01CE01CE01CE01CE01CE01CE01C60186018703830 30186007800E187E9713>48 D<03000700FF000700070007000700070007000700070007 0007000700070007000700070007000700070007000700FFF00C187D9713>I<0F801060 20304038803CC01CE01C401C003C003800380070006000C0018001000200040408041004 30083FF87FF8FFF80E187E9713>I<0F8010E02070607870382038007800700070006000 C00F8000E000700038003C003CE03CE03CC03C4038407030E00F800E187E9713>I<3018 3FF03FE03FC02000200020002000200027C03860203000380018001C001C401CE01CE01C 80184038403030E00F800E187E9713>53 D<01E006100C1818383038300070006000E000 E7C0E860F030F018E018E01CE01CE01C601C601C701830183030186007C00E187E9713> I<40007FFE7FFC7FFC400880108010802000400040008001800180010003000300030003 0007000700070007000700070002000F197E9813>I<0780186030302018601860186018 70103C303E600F8007C019F030F86038401CC00CC00CC00CC00C6008201018600FC00E18 7E9713>I<07801860303070306018E018E018E01CE01CE01C601C603C303C185C0F9C00 1C00180018003870307060604021801F000E187E9713>I<60F0F0600000000000000000 60F0F06004107D8F0B>I<007F00000180C000060030000800080010000400203E020020 E1020041C081004380710083807080870070808700708087007080870070808700708087 007080838070804380708041C0F10020E13100203E1E0010000000080000000600038001 803E00007FE000191A7E991E>64 D<000C0000000C0000000C0000001E0000001E000000 3F000000270000002700000043800000438000004380000081C0000081C0000081C00001 00E0000100E00001FFE000020070000200700006007800040038000400380008001C0008 001C001C001E00FF00FFC01A1A7F991D>II<003F0201C0 C603002E0E001E1C000E1C0006380006780002700002700002F00000F00000F00000F000 00F00000F000007000027000027800023800041C00041C00080E000803003001C0C0003F 00171A7E991C>IIII<003F020001C0C60003002E000E001E001C000E001C00060038 000600780002007000020070000200F0000000F0000000F0000000F0000000F0000000F0 01FFC070000E0070000E0078000E0038000E001C000E001C000E000E000E000300160001 C06600003F82001A1A7E991E>III<1FFC00E000E000E000E000E000E000E000E000E000E0 00E000E000E000E000E000E000E000E000E040E0E0E0E0E041C061801E000E1A7D9914> I77 DI80 D82 D<0FC21836200E6006C006C002C002C002E00070007E003FE01FF807FC003E00 0E00070003800380038003C002C006E004D81887E0101A7E9915>I<7FFFFF00701C0700 401C0100401C0100C01C0180801C0080801C0080801C0080001C0000001C0000001C0000 001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000 001C0000001C0000001C0000001C0000001C000003FFE000191A7F991C>II 87 D89 D<3F8070C070E020700070007007F01C7030707070E070E071E071E0F171 FB1E3C10107E8F13>97 DI<07F80C1C381C30087000E000 E000E000E000E000E0007000300438080C1807E00E107F8F11>I<007E00000E00000E00 000E00000E00000E00000E00000E00000E00000E0003CE000C3E00380E00300E00700E00 E00E00E00E00E00E00E00E00E00E00E00E00600E00700E00381E001C2E0007CFC0121A7F 9915>I<07C01C3030187018600CE00CFFFCE000E000E000E0006000300438080C1807E0 0E107F8F11>I<01F0031807380E100E000E000E000E000E000E00FFC00E000E000E000E 000E000E000E000E000E000E000E000E000E000E007FE00D1A80990C>I<0FCE18733030 7038703870387038303018602FC02000600070003FF03FFC1FFE600FC003C003C003C003 6006381C07E010187F8F13>II<18003C003C0018000000 00000000000000000000FC001C001C001C001C001C001C001C001C001C001C001C001C00 1C001C00FF80091A80990A>I107 DIII<07E01C38300C700E6006E007E007E007E007E007E0076006700E381C1C38 07E010107F8F13>II114 D<1F2060E04020C020C020F0007F003FC01FE0 00F080708030C030C020F0408F800C107F8F0F>I<0400040004000C000C001C003C00FF C01C001C001C001C001C001C001C001C001C201C201C201C201C200E4003800B177F960F >IIII121 D<7FF86070407040E041C041C00380070007000E081C081C08381070 107030FFF00D107F8F11>I E /Fl 4 123 df0 D<0C000C008C40EDC07F800C007F80EDC08C400C000C000A0B7D8B10>3 D<1818181818FFFF18181818181818181818181818181808167D900D>121 D<1818181818FF18181818180018181818FFFF1818181808167D900D>I E /Fm 61 123 df<00003F03E00000C386700001878CF00003879CF00003031860000700 380000070038000007003800000E003800000E007000000E007000000E00700000FFFFFF 80001C007000001C00E000001C00E000001C00E000001C00E000003800E000003801C000 003801C000003801C000003801C000007001C00000700380000070038000007003800000 70038000006003800000E007000000E007000000E007000000E007000000C006000001C0 0E000001C00E000031860C0000798F180000F31E100000620C6000003C07C00000242982 9F1C>11 D<00003FE00000E0100001803800038078000300780007003000070000000700 0000070000000E0000000E0000000E000000FFFFE0000E00E0001C01C0001C01C0001C01 C0001C01C0001C0380003803800038038000380380003807000038070000700700007007 1000700E2000700E2000700E2000E00E2000E0064000E0038000E0000000C0000001C000 0001C000003180000079800000F3000000620000003C0000001D29829F1A>I<00003FC0 FF800000E0E38040000181E600E0000381EC01E0000300DC01E00007001C00C000070018 0000000700380000000E00380000000E00380000000E00380000000E0070000000FFFFFF FF80001C00700380001C00700700001C00700700001C00700700001C00E00700001C00E0 0E00003800E00E00003800E00E00003800E00E00003801C01C00003801C01C00007001C0 1C00007001C01C40007001C0388000700380388000700380388000E00380388000E00380 190000E003000E0000E00700000000C00700000001C00600000001C00600000031860E00 0000798F0C000000F31E18000000620C300000003C07C00000002B29829F28>14 D<0E1F3F3F1D0102020404081020C0080E779F0E>39 D<00010002000400080010002000 6000C0018001800300070006000E000C001C0018003800380030007000700060006000E0 00E000C000C000C000C000C000C000C000C000C000C000C000C000C00040006000600020 00100010000800102E79A113>I<00100000080000040000060000020000030000030000 030000010000018000018000018000018000018000018000018000038000038000038000 0300000300000300000700000700000600000600000E00000C00000C00001C0000180000 380000300000700000600000E00000C0000180000100000300000600000C000018000030 0000600000800000112E80A113>I<1C3C3C3C3C040408081020204080060E7D840E>44 D<7FF0FFE07FE00C037D8A10>I<70F8F8F0E005057B840E>I<0000006000000060000000 E0000000C0000001C00000038000000300000007000000060000000E0000001C00000018 00000038000000300000007000000060000000E0000001C0000001800000038000000300 000007000000060000000E0000001C000000180000003800000030000000700000006000 0000E0000001C0000001800000038000000300000007000000060000000E0000001C0000 0018000000380000003000000070000000E0000000C00000001B2D80A117>I<00020002 0006000E003C00DC031C001C0038003800380038007000700070007000E000E000E000E0 01C001C001C001C003800380038003800780FFF80F1E7B9D17>49 D<001F000061800080E00100E00200700220700420700410700820F00820F00820F00840 E00881E00703C0000380000700000C000018000060000080000300000400000800401000 401000802001807E030047FF0041FE0080FC00807800141F7C9D17>I<070F1F1F0E0000 000000000000000070F8F8F0E008147B930E>58 D<00000200000006000000060000000E 0000001E0000001E0000003F0000002F0000004F0000004F0000008F0000010F0000010F 0000020F0000020F0000040F00000C0F0000080F0000100F0000100F0000200F80003FFF 800040078000C007800080078001000780010007800200078002000780060007801E000F 80FF807FF81D207E9F22>65 D<01FFFFC0001E00F0001E0078001E0038001E003C003C00 3C003C003C003C003C003C003C0078007800780078007800F0007801E000F0078000FFFE 0000F00F8000F003C001E001C001E001E001E001E001E001E003C001E003C001E003C001 E003C001C0078003C00780078007800F0007801E000F007800FFFFE0001E1F7D9E20>I< 0000FE0200078186001C004C0038003C0060003C00C0001C01C000180380001807000018 0F0000181E0000101E0000103C0000003C00000078000000780000007800000078000000 F0000000F0000000F0000000F0000000F000008070000080700000807000010038000100 38000200180004000C001800060020000381C00000FE00001F217A9F21>I<01FFFF8000 1E00E0001E0070001E0038001E001C003C001C003C000E003C000E003C000E0078000E00 78000E0078000E0078000E00F0001E00F0001E00F0001E00F0001E01E0003C01E0003C01 E0003C01E0007803C0007003C0007003C000E003C001C0078001C00780038007800E0007 801C000F007000FFFFC0001F1F7D9E22>I<01FFFFFE001E001C001E000C001E0004001E 0004003C0004003C0004003C0004003C00040078080800780800007808000078180000F0 300000FFF00000F0300000F0300001E0200001E0200001E0200001E0001003C0002003C0 002003C0004003C00040078000800780018007800100078007000F001F00FFFFFE001F1F 7D9E1F>I<01FFFFFC001E0038001E0018001E0008001E0008003C0008003C0008003C00 08003C00080078001000780800007808000078080000F0100000F0300000FFF00000F030 0001E0200001E0200001E0200001E0200003C0000003C0000003C0000003C00000078000 000780000007800000078000000F800000FFF800001E1F7D9E1E>I<0000FC040007030C 001C00980030007800E0007801C000380380003003800030070000300E0000301E000020 1E0000203C0000003C00000078000000780000007800000078000000F0000000F000FFF0 F0000780F0000780F0000F0070000F0070000F0070000F0070001E0038001E0018003E00 1C002E000E00CC000383040000FC00001E217A9F23>I<01FFF3FFE0001F003E00001E00 3C00001E003C00001E003C00003C007800003C007800003C007800003C007800007800F0 00007800F000007800F000007800F00000F001E00000FFFFE00000F001E00000F001E000 01E003C00001E003C00001E003C00001E003C00003C007800003C007800003C007800003 C007800007800F000007800F000007800F000007800F00000F801F0000FFF1FFE000231F 7D9E22>I<01FFF0001F00001E00001E00001E00003C00003C00003C00003C0000780000 780000780000780000F00000F00000F00000F00001E00001E00001E00001E00003C00003 C00003C00003C0000780000780000780000780000F8000FFF800141F7D9E12>I<01FFF0 3FE0001F000F80001E000E00001E000800001E001000003C002000003C004000003C0100 00003C020000007804000000780800000078100000007830000000F0F0000000F1F80000 00F278000000F478000001E83C000001F03C000001E03C000001E01E000003C01E000003 C01E000003C00F000003C00F000007800F00000780078000078007800007800780000F80 07C000FFF03FF800231F7D9E23>75 D<01FFF800001F0000001E0000001E0000001E0000 003C0000003C0000003C0000003C00000078000000780000007800000078000000F00000 00F0000000F0000000F0000001E0000001E0000001E0000001E0008003C0010003C00100 03C0030003C00200078006000780060007800C0007801C000F007800FFFFF800191F7D9E 1D>I<01FE00007FC0001E0000FC00001E0000F800001700017800001700017800002700 02F00000270004F00000270004F00000270008F00000470009E00000470011E000004700 21E00000470021E00000870043C00000838043C00000838083C00000838083C000010381 0780000103820780000103820780000103840780000203840F00000203880F0000020390 0F00000203900F00000401E01E00000401E01E00000401C01E00000C01801E00001C0180 3E0000FF8103FFC0002A1F7D9E29>I<01FF007FE0001F000F00001F0004000017800400 001780040000278008000023C008000023C008000023C008000041E010000041E0100000 41F010000040F010000080F0200000807820000080782000008078200001003C40000100 3C400001003C400001001E400002001E800002001E800002000F800002000F800004000F 0000040007000004000700000C000700001C00020000FF80020000231F7D9E22>I<0001 FC0000070700001C01C0003000E000E0006001C000700380007007800038070000380E00 00381E0000381C0000383C0000383C00003878000078780000787800007878000078F000 00F0F00000F0F00000E0F00001E0F00001C0F00003C0700003807000070078000F003800 1E0038003C001C0070000E00E0000783800001FC00001D217A9F23>I<01FFFF80001E00 E0001E0070001E0038001E003C003C003C003C003C003C003C003C003C00780078007800 78007800F0007800E000F003C000F00F0000FFFC0000F0000001E0000001E0000001E000 0001E0000003C0000003C0000003C0000003C00000078000000780000007800000078000 000F800000FFF000001E1F7D9E1F>I<01FFFF00001E03C0001E00E0001E0070001E0078 003C0078003C0078003C0078003C0078007800F0007800F0007801E0007801C000F00700 00F01E0000FFF00000F0380001E01C0001E01E0001E00E0001E00F0003C01E0003C01E00 03C01E0003C01E0007803C0007803C0807803C0807803C100F801C10FFF00C20000007C0 1D207D9E21>82 D<0007E040001C18C0003005800060038000C0038001C0018001800100 0380010003800100038001000380000003C0000003C0000003F8000001FF800001FFE000 007FF000001FF0000001F800000078000000780000003800000038002000380020003800 2000300060007000600060006000E0007000C000E8038000C606000081F800001A217D9F 1A>I<0FFFFFF01E0780E0180780201007802020078020200F0020600F0020400F002040 0F0020801E0040001E0000001E0000001E0000003C0000003C0000003C0000003C000000 78000000780000007800000078000000F0000000F0000000F0000000F0000001E0000001 E0000001E0000001E0000003E00000FFFF00001C1F789E21>I<7FFC1FF807C003C00780 010007800100078001000F0002000F0002000F0002000F0002001E0004001E0004001E00 04001E0004003C0008003C0008003C0008003C0008007800100078001000780010007800 1000F0002000F0002000F0002000F0004000F00040007000800070010000300200003804 00000C18000007E000001D20779E22>III89 D<007FFFF800FC00F000E001E000C003C00080078001 80078001000F0001001E0001003C00020078000000F8000000F0000001E0000003C00000 078000000F0000000F0000001E0000003C00000078010000F0010001F0020001E0020003 C00600078004000F000C001E0008003E0018003C0038007801F000FFFFF0001D1F7D9E1C >I<00F1800389C00707800E03801C03803C0380380700780700780700780700F00E00F0 0E00F00E00F00E20F01C40F01C40703C40705C40308C800F070013147C9317>97 D<07803F8007000700070007000E000E000E000E001C001C001CF01D0C3A0E3C0E380F38 0F700F700F700F700FE01EE01EE01EE01CE03CE038607060E031C01F0010207B9F15>I< 007E0001C1000300800E07801E07801C07003C0200780000780000780000F00000F00000 F00000F00000F0000070010070020030040018380007C00011147C9315>I<0000780003 F80000700000700000700000700000E00000E00000E00000E00001C00001C000F1C00389 C00707800E03801C03803C0380380700780700780700780700F00E00F00E00F00E00F00E 20F01C40F01C40703C40705C40308C800F070015207C9F17>I<007C01C207010E011C01 3C013802780C7BF07C00F000F000F000F0007000700170023804183807C010147C9315> I<00007800019C00033C00033C000718000700000700000E00000E00000E00000E00000E 0001FFE0001C00001C00001C00001C000038000038000038000038000038000070000070 0000700000700000700000700000E00000E00000E00000E00000C00001C00001C0000180 003180007B0000F300006600003C00001629829F0E>I<003C6000E27001C1E00380E007 00E00F00E00E01C01E01C01E01C01E01C03C03803C03803C03803C03803C07003C07001C 0F001C17000C2E0003CE00000E00000E00001C00001C00301C00783800F0700060E0003F 8000141D7E9315>I<01E0000FE00001C00001C00001C00001C000038000038000038000 038000070000070000071E000763000E81800F01C00E01C00E01C01C03801C03801C0380 1C0380380700380700380700380E10700E20700C20701C20700C40E00CC060070014207D 9F17>I<00C001E001E001C000000000000000000000000000000E003300230043804300 470087000E000E000E001C001C001C003840388030807080310033001C000B1F7C9E0E> I<01E0000FE00001C00001C00001C00001C0000380000380000380000380000700000700 000703C00704200E08E00E11E00E21E00E40C01C80001D00001E00001FC00038E0003870 00387000383840707080707080707080703100E03100601E0013207D9F15>107 D<03C01FC0038003800380038007000700070007000E000E000E000E001C001C001C001C 0038003800380038007000700070007100E200E200E200E200640038000A207C9F0C>I< 1C0F80F0002630C318004740640C004780680E004700700E004700700E008E00E01C000E 00E01C000E00E01C000E00E01C001C01C038001C01C038001C01C038001C01C070803803 8071003803806100380380E10038038062007007006600300300380021147C9325>I<1C 0F802630C04740604780604700704700708E00E00E00E00E00E00E00E01C01C01C01C01C 01C01C03843803883803083807083803107003303001C016147C931A>I<007C0001C300 0301800E01C01E01C01C01E03C01E07801E07801E07801E0F003C0F003C0F003C0F00780 F00700700F00700E0030180018700007C00013147C9317>I<01C1E002621804741C0478 1C04701E04701E08E01E00E01E00E01E00E01E01C03C01C03C01C03C01C0380380780380 700380E003C1C0072380071E000700000700000E00000E00000E00000E00001C00001C00 00FFC000171D809317>I<00F0400388C00705800E03801C03803C038038070078070078 0700780700F00E00F00E00F00E00F00E00F01C00F01C00703C00705C0030B8000F380000 380000380000700000700000700000700000E00000E0000FFE00121D7C9315>I<1C1E00 2661004783804787804707804703008E00000E00000E00000E00001C00001C00001C0000 1C000038000038000038000038000070000030000011147C9313>I<00FC030206010C03 0C070C060C000F800FF007F803FC003E000E700EF00CF00CE008401020601F8010147D93 13>I<018001C0038003800380038007000700FFF007000E000E000E000E001C001C001C 001C003800380038003820704070407080708031001E000C1C7C9B0F>I<0E00C03300E0 2301C04381C04301C04701C08703800E03800E03800E03801C07001C07001C07001C0710 1C0E20180E20180E201C1E200C264007C38014147C9318>I<0E03803307802307C04383 C04301C04700C08700800E00800E00800E00801C01001C01001C01001C02001C02001C04 001C04001C08000E300003C00012147C9315>I<0E00C1C03300E3C02301C3E04381C1E0 4301C0E04701C060870380400E0380400E0380400E0380401C0700801C0700801C070080 1C0701001C0701001C0602001C0F02000C0F04000E13080003E1F0001B147C931E>I<03 83800CC4401068E01071E02071E02070C040E00000E00000E00000E00001C00001C00001 C00001C040638080F38080F38100E5810084C60078780013147D9315>I<0E00C03300E0 2301C04381C04301C04701C08703800E03800E03800E03801C07001C07001C07001C0700 1C0E00180E00180E001C1E000C3C0007DC00001C00001C00003800F03800F07000E06000 C0C0004380003E0000131D7C9316>I<01C04003E08007F1800C1F000802000004000008 000010000020000040000080000100000200000401000802001002003E0C0063FC0041F8 0080E00012147D9313>I E /Fn 83 124 df<001F83E000F06E3001C078780380F87803 00F03007007000070070000700700007007000070070000700700007007000FFFFFF8007 007000070070000700700007007000070070000700700007007000070070000700700007 00700007007000070070000700700007007000070070000700700007007000070070007F E3FF001D20809F1B>11 D<003F0000E0C001C0C00381E00701E00701E007000007000007 0000070000070000070000FFFFE00700E00700E00700E00700E00700E00700E00700E007 00E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E07FC3FE17 20809F19>I<003FE000E0E001C1E00381E00700E00700E00700E00700E00700E00700E0 0700E00700E0FFFFE00700E00700E00700E00700E00700E00700E00700E00700E00700E0 0700E00700E00700E00700E00700E00700E00700E00700E00700E07FE7FE1720809F19> I<001F81F80000F04F040001C07C06000380F80F000300F00F000700F00F000700700000 07007000000700700000070070000007007000000700700000FFFFFFFF00070070070007 007007000700700700070070070007007007000700700700070070070007007007000700 700700070070070007007007000700700700070070070007007007000700700700070070 0700070070070007007007007FE3FE3FF02420809F26>I<70F8F8F8F8F8F8F870707070 7070707070702020202020000000000070F8F8F87005217CA00D>33 D<7038F87CFC7EFC7E743A0402040204020804080410081008201040200F0E7E9F17>I< 70F8FCFC74040404080810102040060E7C9F0D>39 D<0020004000800100020006000C00 0C00180018003000300030007000600060006000E000E000E000E000E000E000E000E000 E000E000E000E0006000600060007000300030003000180018000C000C00060002000100 0080004000200B2E7DA112>I<800040002000100008000C000600060003000300018001 80018001C000C000C000C000E000E000E000E000E000E000E000E000E000E000E000E000 C000C000C001C001800180018003000300060006000C00080010002000400080000B2E7D A112>I<0006000000060000000600000006000000060000000600000006000000060000 00060000000600000006000000060000000600000006000000060000FFFFFFF0FFFFFFF0 000600000006000000060000000600000006000000060000000600000006000000060000 0006000000060000000600000006000000060000000600001C207D9A23>43 D<70F8FCFC74040404080810102040060E7C840D>II<70F8F8F8 7005057C840D>I<00030003000700060006000E000C000C001C00180018003800300030 00700060006000E000C000C001C00180018001800380030003000700060006000E000C00 0C001C0018001800380030003000700060006000E000C000C000102D7DA117>I<03F000 0E1C001C0E00180600380700700380700380700380700380F003C0F003C0F003C0F003C0 F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0700380700380700380 7807803807001806001C0E000E1C0003F000121F7E9D17>I<018003800F80F380038003 800380038003800380038003800380038003800380038003800380038003800380038003 80038003800380038007C0FFFE0F1E7C9D17>I<03F0000C1C00100E0020070040078080 0780F007C0F803C0F803C0F803C02007C00007C0000780000780000F00000E00001C0000 380000700000600000C0000180000300000600400C00401800401000803FFF807FFF80FF FF80121E7E9D17>I<03F0000C1C00100E00200F00780F80780780780780380F80000F80 000F00000F00000E00001C0000380003F000003C00000E00000F000007800007800007C0 2007C0F807C0F807C0F807C0F00780400780400F00200E001C3C0003F000121F7E9D17> I<000600000600000E00000E00001E00002E00002E00004E00008E00008E00010E00020E 00020E00040E00080E00080E00100E00200E00200E00400E00C00E00FFFFF0000E00000E 00000E00000E00000E00000E00000E0000FFE0141E7F9D17>I<1803001FFE001FFC001F F8001FE00010000010000010000010000010000010000011F000161C00180E0010070010 07800003800003800003C00003C00003C07003C0F003C0F003C0E0038040038040070020 0600100E000C380003E000121F7E9D17>I<007C000182000701000E03800C07801C0780 380300380000780000700000700000F1F000F21C00F40600F80700F80380F80380F003C0 F003C0F003C0F003C0F003C07003C07003C07003803803803807001807000C0E00061C00 01F000121F7E9D17>I<4000007FFFC07FFF807FFF804001008002008002008004000008 0000080000100000200000200000400000400000C00000C00001C0000180000380000380 00038000038000078000078000078000078000078000078000078000030000121F7D9D17 >I<03F0000C0C001006003003002001806001806001806001807001807803003E03003F 06001FC8000FF00003F80007FC000C7E00103F00300F806003804001C0C001C0C000C0C0 00C0C000C0C000806001802001001002000C0C0003F000121F7E9D17>I<03F0000E1800 1C0C00380600380700700700700380F00380F00380F003C0F003C0F003C0F003C0F003C0 7007C07007C03807C0180BC00E13C003E3C0000380000380000380000700300700780600 780E00700C002018001070000FC000121F7E9D17>I<70F8F8F870000000000000000000 0070F8F8F87005147C930D>I<70F8F8F8700000000000000000000070F0F8F878080808 101010202040051D7C930D>I<7FFFFFE0FFFFFFF0000000000000000000000000000000 0000000000000000000000000000000000FFFFFFF07FFFFFE01C0C7D9023>61 D<000100000003800000038000000380000007C0000007C0000007C0000009E0000009E0 000009E0000010F0000010F0000010F00000207800002078000020780000403C0000403C 0000403C0000801E0000801E0000FFFE0001000F0001000F0001000F0002000780020007 8002000780040003C00E0003C01F0007E0FFC03FFE1F207F9F22>65 DI<000FC040007030C001C009C0 038005C0070003C00E0001C01E0000C01C0000C03C0000C07C0000407C00004078000040 F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000 780000007C0000407C0000403C0000401C0000401E0000800E0000800700010003800200 01C0040000703800000FC0001A217D9F21>IIII<000FE0200078186000E004E0038002E0070001E0 0F0000E01E0000601E0000603C0000603C0000207C00002078000020F8000000F8000000 F8000000F8000000F8000000F8000000F8000000F8007FFCF80003E0780001E07C0001E0 3C0001E03C0001E01E0001E01E0001E00F0001E0070001E0038002E000E0046000781820 000FE0001E217D9F24>III<0FFFC0007C 00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C 00003C00003C00003C00003C00003C00003C00003C00003C00003C00203C00F83C00F83C 00F83C00F0380040780040700030E0000F800012207E9E17>IIIII<001F800000F0F00001C0380007801E000F000F000E0007001E00 07803C0003C03C0003C07C0003E0780001E0780001E0F80001F0F80001F0F80001F0F800 01F0F80001F0F80001F0F80001F0F80001F0F80001F0780001E07C0003E07C0003E03C00 03C03C0003C01E0007800E0007000F000F0007801E0001C0380000F0F000001F80001C21 7D9F23>II<001F800000F0F000 01C0380007801E000F000F000E0007001E0007803C0003C03C0003C07C0003E07C0003E0 780001E0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0 F80001F0780001E0780001E07C0003E03C0003C03C0F03C01E1087800E2047000F204F00 07A03E0001E0380000F0F010001FB01000003010000038300000387000003FF000001FE0 00001FE000000FC0000007801C297D9F23>II<07E0800C1980100780300380600180600180E00180E00080E000 80E00080F00000F000007800007F00003FF0001FFC000FFE0003FF00001F800007800003 C00003C00001C08001C08001C08001C08001C0C00180C00380E00300F00600CE0C0081F8 0012217D9F19>I<7FFFFFE0780F01E0600F0060400F0020400F0020C00F0030800F0010 800F0010800F0010800F0010000F0000000F0000000F0000000F0000000F0000000F0000 000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000 000F0000000F0000000F0000000F0000001F800007FFFE001C1F7E9E21>IIII89 D91 D<080410082010201040204020804080408040B85CFC7EFC7E7C3E381C0F0E7B9F17>I< FEFE06060606060606060606060606060606060606060606060606060606060606060606 06060606060606FEFE072D7FA10D>I<3078FC783006057D9E0D>95 D<081020204040808080B8FCFC7C38060E7D9F0D>I<1FE000303000781800781C00300E 00000E00000E00000E0000FE00078E001E0E00380E00780E00F00E10F00E10F00E10F01E 10781E103867200F83C014147E9317>I<0E0000FE00000E00000E00000E00000E00000E 00000E00000E00000E00000E00000E00000E3E000EC3800F01C00F00E00E00E00E00700E 00700E00780E00780E00780E00780E00780E00780E00700E00700E00E00F00E00D01C00C C300083E0015207F9F19>I<03F80E0C1C1E381E380C70007000F000F000F000F000F000 F00070007000380138011C020E0C03F010147E9314>I<000380003F8000038000038000 038000038000038000038000038000038000038000038003E380061B801C078038038038 0380700380700380F00380F00380F00380F00380F00380F0038070038070038038038038 07801C07800E1B8003E3F815207E9F19>I<03F0000E1C001C0E00380700380700700700 700380F00380F00380FFFF80F00000F00000F000007000007000003800801800800C0100 07060001F80011147F9314>I<007C00C6018F038F070607000700070007000700070007 00FFF0070007000700070007000700070007000700070007000700070007000700070007 0007007FF01020809F0E>I<0000E003E3300E3C301C1C30380E00780F00780F00780F00 780F00780F00380E001C1C001E380033E0002000002000003000003000003FFE001FFF80 0FFFC03001E0600070C00030C00030C00030C000306000603000C01C038003FC00141F7F 9417>I<0E0000FE00000E00000E00000E00000E00000E00000E00000E00000E00000E00 000E00000E3E000E43000E81800F01C00F01C00E01C00E01C00E01C00E01C00E01C00E01 C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0FFE7FC16207F9F19>I<1C 001E003E001E001C000000000000000000000000000E007E000E000E000E000E000E000E 000E000E000E000E000E000E000E000E000E000E000E00FFC00A1F809E0C>I<00E001F0 01F001F000E0000000000000000000000000007007F000F0007000700070007000700070 0070007000700070007000700070007000700070007000700070007000706070F060F0C0 61803F000C28829E0E>I<0E0000FE00000E00000E00000E00000E00000E00000E00000E 00000E00000E00000E00000E0FF00E03C00E03000E02000E04000E08000E10000E30000E 70000EF8000F38000E1C000E1E000E0E000E07000E07800E03800E03C00E03E0FFCFF815 207F9F18>I<0E00FE000E000E000E000E000E000E000E000E000E000E000E000E000E00 0E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00FFE00B20 809F0C>I<0E1F01F000FE618618000E81C81C000F00F00E000F00F00E000E00E00E000E 00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00 E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E00FFE7FE7FE023147F 9326>I<0E3E00FE43000E81800F01C00F01C00E01C00E01C00E01C00E01C00E01C00E01 C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0FFE7FC16147F9319>I<01 F800070E001C03803801C03801C07000E07000E0F000F0F000F0F000F0F000F0F000F0F0 00F07000E07000E03801C03801C01C0380070E0001F80014147F9317>I<0E3E00FEC380 0F01C00F00E00E00E00E00F00E00700E00780E00780E00780E00780E00780E00780E0070 0E00F00E00E00F01E00F01C00EC3000E3E000E00000E00000E00000E00000E00000E0000 0E00000E0000FFE000151D7F9319>I<03E0800619801C05803C07803803807803807003 80F00380F00380F00380F00380F00380F003807003807803803803803807801C0B800E13 8003E380000380000380000380000380000380000380000380000380003FF8151D7E9318 >I<0E78FE8C0F1E0F1E0F0C0E000E000E000E000E000E000E000E000E000E000E000E00 0E000E00FFE00F147F9312>I<1F9030704030C010C010C010E00078007F803FE00FF000 70803880188018C018C018E030D0608F800D147E9312>I<020002000200060006000E00 0E003E00FFF80E000E000E000E000E000E000E000E000E000E000E000E080E080E080E08 0E080610031001E00D1C7F9B12>I<0E01C0FE1FC00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E03C00603C0030DC0 01F1FC16147F9319>III<7FC3FC0F01E00701C007018003810001 C20000E40000EC00007800003800003C00007C00004E000087000107000303800201C006 01E01E01E0FF07FE1714809318>I I<3FFF380E200E201C40384078407000E001E001C00380078007010E011E011C03380270 06700EFFFE10147F9314>II E /Fo 41 123 df<000FE000007FF80000F81C0001E07C0003E07C0007C07C0007C07C0007C0380007C0 000007C0000007C0000007C1FE00FFFFFE00FFFFFE0007C03E0007C03E0007C03E0007C0 3E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C0 3E0007C03E0007C03E0007C03E003FF9FFC03FF9FFC01A20809F1D>12 D<387CFEFEFE7C3807077C860F>46 D<00E00001E0000FE000FFE000F3E00003E00003E0 0003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E0 0003E00003E00003E00003E00003E00003E00003E00003E000FFFF80FFFF80111D7C9C1A >49 D<07F0001FFE00383F007C1F80FE0FC0FE0FC0FE0FE0FE07E07C07E03807E0000FE0 000FC0000FC0001F80001F00003E0000780000F00000E00001C0000380600700600E0060 1C00E01FFFC03FFFC07FFFC0FFFFC0FFFFC0131D7D9C1A>I<01FC0007FF000E0F801E0F C03F07E03F07E03F07E03F07E01E0FC0000FC0000F80001F0001FC0001FC00000F800007 C00003E00003F00003F83803F87C03F8FE03F8FE03F8FE03F0FC03F07807E03C0FC01FFF 8003FC00151D7E9C1A>I<0001C00003C00007C00007C0000FC0001FC0003BC00073C000 63C000C3C00183C00383C00703C00E03C00C03C01803C03803C07003C0E003C0FFFFFEFF FFFE0007C00007C00007C00007C00007C00007C000FFFE00FFFE171D7F9C1A>I<387CFE FEFE7C38000000000000387CFEFEFE7C3807147C930F>58 D<0000E000000000E0000000 01F000000001F000000001F000000003F800000003F800000006FC00000006FC0000000E FE0000000C7E0000000C7E000000183F000000183F000000303F800000301F800000701F C00000600FC00000600FC00000C007E00000FFFFE00001FFFFF000018003F000018003F0 00030001F800030001F800060001FC00060000FC000E0000FE00FFE00FFFE0FFE00FFFE0 231F7E9E28>65 D68 D75 DII<001FF80000FFFF0001F81F8007E007E00FC003F01F8001F81F00 00F83F0000FC7F0000FE7E00007E7E00007EFE00007FFE00007FFE00007FFE00007FFE00 007FFE00007FFE00007FFE00007FFE00007F7E00007E7F0000FE7F0000FE3F0000FC3F80 01FC1F8001F80FC003F007E007E001F81F8000FFFF00001FF800201F7D9E27>79 DI82 D<03FC080FFF381E03F83800F8700078700038F00038F00018F00018F800 00FC00007FC0007FFE003FFF801FFFE00FFFF007FFF000FFF80007F80000FC00007C0000 3CC0003CC0003CC0003CE00038E00078F80070FE01E0E7FFC081FF00161F7D9E1D>I<7F FFFFFC7FFFFFFC7C07E07C7007E01C6007E00C6007E00CE007E00EC007E006C007E006C0 07E006C007E0060007E0000007E0000007E0000007E0000007E0000007E0000007E00000 07E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E00000 07E00003FFFFC003FFFFC01F1E7E9D24>I86 D<07FC001FFF003F0F803F07C03F03E03F03E00C03E00003E0007FE007FBE01F03E03C03 E07C03E0F803E0F803E0F803E0FC05E07E0DE03FF9FE0FE07E17147F9319>97 DI<01FE0007 FF801F0FC03E0FC03E0FC07C0FC07C0300FC0000FC0000FC0000FC0000FC0000FC00007C 00007E00003E00603F00C01F81C007FF0001FC0013147E9317>I<0007F80007F80000F8 0000F80000F80000F80000F80000F80000F80000F80000F80000F801F8F80FFEF81F83F8 3E01F87E00F87C00F87C00F8FC00F8FC00F8FC00F8FC00F8FC00F8FC00F87C00F87C00F8 7E00F83E01F81F07F80FFEFF03F8FF18207E9F1D>I<01FE0007FF801F83E03F01F07E00 F07E00F8FC00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC00007C00007E00003E00183F00 380F807007FFE000FF8015147F9318>I<001F8000FFC001F3E003E7E003C7E007C7E007 C3C007C00007C00007C00007C00007C000FFFC00FFFC0007C00007C00007C00007C00007 C00007C00007C00007C00007C00007C00007C00007C00007C00007C00007C00007C0003F FC003FFC0013207F9F10>I<01FC3C07FFFE0F079E1E03DE3E03E03E03E03E03E03E03E0 3E03E01E03C00F07800FFF0009FC001800001800001C00001FFF800FFFF007FFF81FFFFC 3C007C70003EF0001EF0001EF0001E78003C78003C3F01F80FFFE001FF00171E7F931A> II<1C003F00 7F007F007F003F001C00000000000000000000000000FF00FF001F001F001F001F001F00 1F001F001F001F001F001F001F001F001F001F001F00FFE0FFE00B217EA00E>I<003800 FE00FE00FE00FE00FE003800000000000000000000000001FE01FE003E003E003E003E00 3E003E003E003E003E003E003E003E003E003E003E003E003E003E003E003E783EFC3EFC 7EFC7CFCF87FF01FC00F2A83A010>IIIII<01FF0007FFC01F83F03E00F83E00F87C007C7C007CFC007EFC007EFC007EFC00 7EFC007EFC007E7C007C7C007C3E00F83E00F81F83F007FFC001FF0017147F931A>II114 D<0FE63FFE701E600EE006E006F800FFC07FF8 3FFC1FFE03FE001FC007C007E007F006F81EFFFCC7F010147E9315>I<01800180018003 800380038007800F803F80FFFCFFFC0F800F800F800F800F800F800F800F800F800F800F 860F860F860F860F8607CC03F801F00F1D7F9C14>II119 D121 D<3FFFE03FFFE03C0FC0381FC0701F80603F00607E0060FE0000FC0001F80003F00007E0 600FE0600FC0601F80E03F00C07F01C07E03C0FFFFC0FFFFC013147F9317>I E /Fp 16 119 df<183E7E7F3F1F070E0E1CFCF8E0080D77851A>44 D<00C001C001C003C007C00FC07FC0FDC071C001C001C001C001C001C001C001C001C001 C001C001C001C001C001C001C001C001C001C07FFF7FFF7FFF101E7B9D1A>49 D<01FC0007FF001FFF801E03C03C01C03C00E03C00E00000E00000E00001C00003C00007 8001FF0001FF0001FFC00003E00000F0000070000078000038000038600038F00038F000 78E000707000F07E03E03FFFC00FFF0001FC00151E7E9D1A>51 D<3FFFC07FFFC07FFFC0 70000070000070000070000070000070000070000070000071F8007FFE007FFF007E0780 7803C03001C00001C00000E00000E00000E06000E0F000E0F001C0E001C07003807C0F80 3FFF000FFC0003F000131E7D9D1A>53 D<01F00007FC001FFE003E0F0038078070038070 01C0E001C0E001C0E001E0E000E0E000E0E001E07001E07803E03C0FE01FFFE00FFCE003 F0E00001C00001C00001C0000380600380F00700F00F00F03E007FFC003FF0000FC00013 1E7D9D1A>57 D<7E003F00FF007F807F007F001D80DC001D80DC001D80DC001DC1DC001D C1DC001CC19C001CC19C001CE39C001CE39C001C631C001C771C001C771C001C361C001C 361C001C3E1C001C1C1C001C1C1C001C001C001C001C001C001C001C001C001C001C001C 001C001C001C007F007F00FF80FF807F007F00191E809D1A>77 D82 D<1FF0003FFC007FFE00780F0030070000038000 0380007F8007FF801FFF803F8380780380700380E00380E00380E00380700780780F803F FFFC1FFDFC07F0FC16157D941A>97 D<00FF8003FFC00FFFE01F01E03C00C07800007000 00700000E00000E00000E00000E00000E000007000007000007800703C00701F01F00FFF E003FFC000FE0014157D941A>99 D<001FC0001FC0001FC00001C00001C00001C00001C0 0001C00001C001F1C007FDC00FFFC01E0FC03C07C07803C07001C0E001C0E001C0E001C0 E001C0E001C0E001C0E001C07003C07003C03807C03E0FC01FFFFC07FDFC01F1FC161E7E 9D1A>I<01F80007FF000FFF801E07C03C01C07800E07000E0E00070E00070FFFFF0FFFF F0FFFFF0E000007000007000007800703C00701F01F00FFFE003FFC000FE0014157D941A >I104 D<00C00001E00001E00000C0000000000000000000000000000000000000007FE0007FE0 007FE00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E0 0000E00000E00000E00000E0007FFF80FFFFC07FFF80121F7C9E1A>I<7F83F0FF8FF87F BFFC03FC3C03F01803E00003C00003C00003800003800003800003800003800003800003 80000380000380000380007FFF00FFFF007FFF0016157E941A>114 D<07FB801FFF807FFF80780780E00380E00380E003807800007FC0003FFC0007FE00003F 800007806001C0E001C0E001C0F003C0FC0780FFFF00EFFE00E3F80012157C941A>I<7F 83FCFFC7FE7F83FC0E00E00E00E00E00E00701C00701C00701C003838003838003838001 C70001C70001C70000EE0000EE0000EE00007C00007C0000380017157F941A>118 D E /Fq 4 123 df0 D<060F0F0E1E1E1C3C383830707060 E0C04008117F910A>48 D<06000600060006000600060006000600FFF0FFF00600060006 0006000600060006000600060006000600060006000600060006000600060006000C1D7E 9611>121 D<060006000600060006000600FFF0FFF00600060006000600060006000000 060006000600060006000600FFF0FFF00600060006000600060006000C1D7E9611>I E /Fr 11 118 df77 DI89 D<0FE0001838003C0C003C0E0018070000070000070000070000FF0007C7001E0700 3C0700780700700700F00708F00708F00708F00F087817083C23900FC1E015157E9418> 97 D<00007001F198071E180E0E181C07001C07003C07803C07803C07803C07801C0700 1C07000E0E000F1C0019F0001000001000001800001800001FFE000FFFC00FFFE03800F0 600030400018C00018C00018C000186000306000303800E00E038003FE0015217F9518> 103 D<1C001E003E001E001C00000000000000000000000000000000000E00FE001E000E 000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00FFC00A 227FA10E>105 D<0E1F80FE60C01E80E00F00700F00700E00700E00700E00700E00700E 00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E0070FFE7FF18 157F941B>110 D<01FC000707000C01801800C03800E0700070700070F00078F00078F0 0078F00078F00078F00078F000787000707800F03800E01C01C00E038007070001FC0015 157F9418>I<0E3CFE461E8F0F0F0F060F000E000E000E000E000E000E000E000E000E00 0E000E000E000E000F00FFF010157F9413>114 D<02000200020002000600060006000E 001E003E00FFF80E000E000E000E000E000E000E000E000E000E000E000E040E040E040E 040E040E040708030801F00E1F7F9E13>116 D<0E0070FE07F01E00F00E00700E00700E 00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00F00E 00F006017003827800FC7F18157F941B>I E /Fs 1 4 df<00C00000C00000C00000C000 00C000C0C0C0F0C3C038C7000EDC0003F00000C00003F0000EDC0038C700F0C3C0C0C0C0 00C00000C00000C00000C00000C00012157D9619>3 D E /Ft 25 122 df45 D<000003000000000003000000000003 00000000000780000000000780000000000FC0000000000FC0000000000FC00000000017 E00000000013E00000000013E00000000023F00000000021F00000000021F00000000040 F80000000040F80000000040F800000000807C00000000807C00000001807E0000000100 3E00000001003E00000002003F00000002001F00000002001F00000004000F8000000400 0F80000004000F800000080007C00000080007C00000180007E000001FFFFFE000001FFF FFE00000200003F00000200001F00000200001F00000400001F80000400000F800004000 00F800008000007C00008000007C00008000007C00010000003E00010000003E00030000 003F00030000001F00070000001F001F8000003F80FFE00003FFFCFFE00003FFFC2E327E B132>65 D<00001FE0010001FFF8030007F00E03000F800307003E0000C7007C00004F00 F800003F01F000001F03E000000F07C000000F07800000070F800000071F000000031F00 0000033F000000033E000000013E000000017E000000017E000000017C00000000FC0000 0000FC00000000FC00000000FC00000000FC00000000FC00000000FC00000000FC000000 00FC00000000FC00000000FC000000007C000000007E000000007E000000013E00000001 3E000000013F000000011F000000011F000000020F80000002078000000607C000000403 E000000C01F000000800F8000010007C000020003E0000C0000F8001800007F00F000001 FFFC0000001FE00028337CB130>67 D70 D72 D<00003FC000000001E07800000007000E0000001E0007800000380001C00000F00000F0 0001E00000780003E000007C0003C000003C00078000001E000F8000001F000F0000000F 001F0000000F801F0000000F803E00000007C03E00000007C07E00000007E07E00000007 E07C00000003E07C00000003E0FC00000003F0FC00000003F0FC00000003F0FC00000003 F0FC00000003F0FC00000003F0FC00000003F0FC00000003F0FC00000003F0FC00000003 F0FC00000003F07C00000003E07E00000007E07E00000007E07E00000007E03E00000007 C03F0000000FC01F0000000F801F0000000F800F8000001F000F8000001F0007C000003E 0003C000003C0003E000007C0001F00000F80000F80001F000003C0003C000001E000780 000007000E00000001E078000000003FC000002C337CB134>79 D85 D87 D<00FE00000303C0000C00E00010007000100038003C003C003E001C003E001E003E001E 0008001E0000001E0000001E0000001E00000FFE0000FC1E0003E01E000F801E001F001E 003E001E003C001E007C001E00F8001E04F8001E04F8001E04F8003E04F8003E0478003E 047C005E043E008F080F0307F003FC03E01E1F7D9E21>97 D<003F8000E0600380180700 040F00041E001E1C003E3C003E7C003E7C0008780000F80000F80000F80000F80000F800 00F80000F80000F80000F800007800007C00007C00003C00011E00011E00020F00020700 0403801800E060003F80181F7D9E1D>99 D<0000006000000FE000003FE000003FE00000 03E0000001E0000001E0000001E0000001E0000001E0000001E0000001E0000001E00000 01E0000001E0000001E0000001E0000001E0000001E0001F81E000F061E001C019E00780 05E00F0003E00E0003E01E0001E03C0001E03C0001E07C0001E0780001E0F80001E0F800 01E0F80001E0F80001E0F80001E0F80001E0F80001E0F80001E0F80001E0780001E07800 01E03C0001E03C0001E01C0001E01E0003E00E0005E0070009E0038011F000E061FF003F 81FF20327DB125>I<003F800000E0E0000380380007003C000E001E001E001E001C000F 003C000F007C000F0078000F8078000780F8000780F8000780FFFFFF80F8000000F80000 00F8000000F8000000F8000000F8000000780000007C0000003C0000003C0000801E0000 800E0001000F0002000780020001C00C0000F03000001FC000191F7E9E1D>I<000000F0 007F030801C1C41C0380E81C070070080F0078001E003C001E003C003E003E003E003E00 3E003E003E003E003E003E003E003E001E003C001E003C000F007800070070000780E000 09C1C000087F000018000000180000001800000018000000180000001C0000000E000000 0FFFF80007FFFF0003FFFF800E000FC0180001E0300000F070000070E0000038E0000038 E0000038E0000038E00000387000007070000070380000E01C0001C00700070001C01C00 003FE0001E2F7E9F21>103 D<01800000003F80000000FF80000000FF800000000F8000 000007800000000780000000078000000007800000000780000000078000000007800000 000780000000078000000007800000000780000000078000000007800000000780000000 0780FE00000783078000078C03C000079001E00007A001E00007A000F00007C000F00007 C000F000078000F000078000F000078000F000078000F000078000F000078000F0000780 00F000078000F000078000F000078000F000078000F000078000F000078000F000078000 F000078000F000078000F000078000F000078000F000078000F000078000F0000FC001F8 00FFFC1FFF80FFFC1FFF8021327EB125>I<07000F801F801F800F800700000000000000 0000000000000000000000000000000001801F80FF80FF800F8007800780078007800780 078007800780078007800780078007800780078007800780078007800780078007800780 0FC0FFF8FFF80D307EAF12>I<01803F80FF80FF800F8007800780078007800780078007 800780078007800780078007800780078007800780078007800780078007800780078007 80078007800780078007800780078007800780078007800780078007800780078007800F C0FFFCFFFC0E327EB112>108 D<0180FE00003F83078000FF8C03C000FF9001E0000FA0 01E00007A000F00007C000F00007C000F000078000F000078000F000078000F000078000 F000078000F000078000F000078000F000078000F000078000F000078000F000078000F0 00078000F000078000F000078000F000078000F000078000F000078000F000078000F000 078000F000078000F0000FC001F800FFFC1FFF80FFFC1FFF80211F7E9E25>110 D<001FC00000F0780001C01C00070007000F0007801E0003C01C0001C03C0001E03C0001 E0780000F0780000F0780000F0F80000F8F80000F8F80000F8F80000F8F80000F8F80000 F8F80000F8F80000F8780000F07C0001F03C0001E03C0001E01E0003C01E0003C00F0007 8007800F0001C01C0000F07800001FC0001D1F7E9E21>I<0181FC003F860700FF8803C0 FF9001E00FA000F007C00078078000780780003C0780003C0780003E0780001E0780001F 0780001F0780001F0780001F0780001F0780001F0780001F0780001F0780001F0780003E 0780003E0780003C0780007C0780007807C000F007A000F007A001E00798038007860F00 0781F8000780000007800000078000000780000007800000078000000780000007800000 0780000007800000078000000FC00000FFFC0000FFFC0000202D7E9E25>I<0183E03F8C 18FF907CFF907C0FA07C07C03807C00007C00007C0000780000780000780000780000780 000780000780000780000780000780000780000780000780000780000780000780000780 000780000780000FC000FFFE00FFFE00161F7E9E19>114 D<01FC100E03301800F03000 70600030E00030E00010E00010E00010F00010F800007E00003FF0001FFF000FFFC003FF E0003FF00001F80000F880003C80003C80001CC0001CC0001CE0001CE00018F00038F000 30EC0060C301C080FE00161F7E9E1A>I<00400000400000400000400000400000C00000 C00000C00001C00001C00003C00007C0000FC0001FFFE0FFFFE003C00003C00003C00003 C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003 C00003C01003C01003C01003C01003C01003C01003C01003C01001C02001E02000E04000 78C0001F00142C7FAB19>I<01800030003F8007F000FF801FF000FF801FF0000F8001F0 00078000F000078000F000078000F000078000F000078000F000078000F000078000F000 078000F000078000F000078000F000078000F000078000F000078000F000078000F00007 8000F000078000F000078000F000078000F000078001F000078001F000078001F0000380 02F00003C004F00001C008F800007030FF80001FC0FF80211F7E9E25>II121 D E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%EndSetup %%Page: 0 1 0 0 bop 103 303 a Ft(Univ)n(ersal)21 b(One-W)-6 b(a)n(y)21 b(Hash)g(F)-6 b(unctions)21 b(and)g(their)h(Cryptographic)784 394 y(Applications)1166 368 y Fs(\003)649 521 y Fr(Moni)16 b(Naor)879 502 y Fq(y)1072 521 y Fr(Moti)g(Y)l(ung)1301 502 y Fq(z)693 622 y Fp(Revised)23 b(March)h(13,)g(1995)875 967 y Fo(Abstract)75 1073 y Fn(W)l(e)16 b(de\014ne)i(a)d Fm(Universal)h(One-Way)i(Hash)f(F)m(unction)e Fn(family)l(,)i(a)f(new)g (primitiv)o(e)i(whic)o(h)f(enables)g(the)75 1129 y(compression)23 b(of)f(elemen)o(ts)i(in)f(the)g(function)h(domain.)43 b(The)23 b(main)g(prop)q(ert)o(y)f(of)g(this)i(primitiv)o(e)75 1186 y(is)d(that)e(giv)o(en)i(an)f(elemen)o(t)h Fm(x)f Fn(in)h(the)f(domain,)i(it)e(is)h(computationally)g(hard)f(to)g(\014nd) h(a)f(di\013eren)o(t)75 1242 y(domain)13 b(elemen)o(t)h(whic)o(h)g (collides)g(with)g Fm(x)p Fn(.)19 b(W)l(e)13 b(pro)o(v)o(e)f (constructiv)o(ely)i(that)e(univ)o(ersal)i(one-w)o(a)o(y)e(hash)75 1299 y(functions)k(exist)g(if)f(an)o(y)g(1-1)g(one-w)o(a)o(y)f (functions)i(exist.)146 1355 y(Among)21 b(the)h(v)m(arious)g (applications)h(of)f(the)g(primitiv)o(e)h(is)f(a)f Fm(One-Way)i(b)n (ase)n(d)e(Se)n(cur)n(e)h(Digital)75 1412 y(Signatur)n(e)f Fn(Sc)o(heme)g(whic)o(h)h(is)g(existen)o(tially)h(secure)f(against)f (adoptiv)o(e)g(attac)o(ks.)36 b(Previously)l(,)24 b(all)75 1468 y(pro)o(v)m(ably)c(secure)h(signature)f(sc)o(hemes)g(w)o(ere)f (based)h(on)g(the)g(stronger)f(mathematical)h(assumption)75 1525 y(that)14 b Fm(tr)n(ap)n(do)n(or)i Fn(one-w)o(a)o(y)f(functions)h (exist.)75 1606 y Fo(Key)h(w)o(ords.)h Fn(cryptograph)o(y)l(,)c (randomized)i(algorithms)75 1687 y Fo(AMS)h(sub)s(ject)g (classi\014cations.)22 b Fn(68M10,)13 b(68Q20,)h(68Q22,)h(68R05,)f (68R10)p 75 2169 720 2 v 126 2196 a Fl(\003)144 2212 y Fk(P)o(art)i(of)g(this)h(w)o(ork)f(w)o(as)g(done)h(while)g(the)g (authors)g(w)o(ere)e(at)i(the)f(IBM)g(Almaden)h(Researc)o(h)g(Cen)o (ter.)27 b(The)16 b(\014rst)75 2257 y(author)d(w)o(as)g(supp)q(orted)h (in)f(part)g(b)o(y)f(NSF)h(gran)o(t)g(CCR-88)f(13632.)18 b(A)12 b(preliminary)j(v)o(ersion)f(of)e(this)i(w)o(ork)e(app)q(eared)i (in)75 2303 y(Pro)q(c.)j(of)c(the)g(21st)g(A)o(CM)g(Symp)q(osium)i(on)e (Theory)h(of)e(Computing)128 2334 y Fl(y)144 2350 y Fk(Incum)o(b)q(en)o (t)21 b(of)e(the)g(Morris)i(and)f(Rose)g(Goldman)h(Career)e(Dev)o (elopmen)o(t)j(Chair,)f(Dept.)f(of)f(Applied)i(Mathe-)75 2395 y(matics)c(and)g(Computer)g(Science,)i(W)m(eizmann)f(Institute)f (of)f(Science,)j(Reho)o(v)o(ot)e(76100,)h(Israel.)28 b(Most)16 b(of)h(this)g(w)o(ork)75 2441 y(p)q(erformed)g(while)h(at)f (the)f(IBM)h(Almaden)h(Researc)o(h)f(Cen)o(ter.)28 b(Researc)o(h)18 b(supp)q(orted)g(b)o(y)f(an)g(Alon)g(F)m(ello)o(wship)i(and)75 2487 y(a)h(gran)o(t)g(from)f(the)h(Israel)h(Science)g(F)m(oundation)h (administered)g(b)o(y)e(the)g(Israeli)h(Academ)o(y)g(of)e(Sciences.)39 b(E-mail:)75 2532 y(naor@wisdom.w)o(eizmann.ac.il)q(.)128 2563 y Fl(z)144 2579 y Fk(IBM)19 b(Researc)o(h)g(Division)q(,)j(T.J)c (W)m(atson)h(Researc)o(h)h(Cen)o(ter,)f(Y)m(orkto)o(wn)g(Heigh)o(ts,)h (NY)e(10598,)j(USA.)d(E-mail:)75 2625 y(moti@w)o(atson.ibm.com.)p eop %%Page: 1 2 1 1 bop 75 121 a Fj(1)69 b(In)n(tro)r(duction)75 222 y Fn(Consider)17 b(an)f(en)o(vironmen)o(t)g(in)h(whic)o(h)g(users)f (share)g(computer)g(programs)f(that)h(reside)h(in)g(the)f(com-)75 279 y(mon)g(\(read/write\))f(space.)24 b(W)l(e)16 b(assume)g(that)f(a)h (small)h(read-only)g(area)f(is)h(a)o(v)m(ailable)g(in)h(the)e(shared)75 335 y(memory)l(.)j(T)l(o)12 b(prev)o(en)o(t)g(computer)h(viruses)g (from)e(mo)q(difying)j(the)f(programs,)e(the)i(users)f(w)o(ould)h(lik)o (e)h(to)75 391 y(authen)o(ticate)h(the)g(programs)f(b)q(efore)i(their)f (use.)21 b(A)15 b(p)q(ossible)i(w)o(a)o(y)d(to)g(do)h(it)h(is)f(to)g (use)g(the)g(read-only)75 448 y(area)i(as)h(a)g(common)f(securit)o(y)i (serv)o(er)e(whic)o(h)i(stores)f(the)g(hash)g(v)m(alue)h(of)f(the)g (\014les)h(of)e(the)h(common)75 504 y(space,)c(where)f(the)h(hash)f (function)h Fi(h)g Fn(itself)g(is)g(publicly)i(kno)o(wn)d(and)g(can)h (b)q(e)g(stored)f(in)h(the)f(read-only)75 561 y(space)i(as)f(w)o(ell.) 20 b(The)15 b(prop)q(ert)o(y)f(required)h(from)f(the)g(hash)g(function) i Fi(h)e Fn(is)h(that)e(for)h(a)g(giv)o(en)h(v)m(alue)g Fi(x)g Fn(it)75 617 y(is)h(computationally)g(hard)f(to)g(\014nd)g(a)g Fi(y)i Fn(suc)o(h)f(that)e Fi(h)p Fn(\()p Fi(y)r Fn(\))f(=)g Fi(h)p Fn(\()p Fi(x)p Fn(\))h(and)i Fi(y)e Fh(6)p Fn(=)f Fi(x)p Fn(.)146 674 y(W)l(e)19 b(call)h(the)f(hashing)h(of)e(a)h(large) g(\014le)h(a)f Fm(public)h(\014ngerprint)p Fn(.)30 b(Notice)19 b(that)g(this)g(sc)o(heme)h(do)q(es)75 730 y(not)c(require)g(the)h (user)f(to)f(o)o(wn)h(a)f(priv)m(ate)i(secure)f(space,)h(the)f (compression)g(metho)q(d)g(is)h(public,)h(and)75 787 y(\(in)f(the)g(spirit)g(of)g(mo)q(dern)g(cryptograph)o(y\))e(priv)m (ate)i(k)o(eys)g(are)f(not)g(required.)26 b(F)l(urthermore,)16 b(it)h(can)75 843 y(pro)o(vide)c(authen)o(tication)g(ev)o(en)g(to)e(a)h (new)h(or)f(a)g(casual)h(user;)g(this)g(cannot)f(b)q(e)h(ac)o(hiev)o (ed)g(b)o(y)g(previously)75 900 y(suggested)i(\(priv)m(ate\))g (\014ngerprin)o(ting)i(tec)o(hniques)f([34,)e(29].)20 b(This)15 b(scenario)h(exempli\014es)i(the)d(setting)75 956 y(of)f(this)g(pap)q(er)h(whic)o(h)g(com)o(bines)g(cryptographic)f (securit)o(y)h(and)f(data)g(compression;)g(as)g(w)o(e)g(shall)h(see,)75 1012 y(this)h(setting)f(includes)i(a)e(v)m(ariet)o(y)h(of)e (applications.)146 1069 y(W)l(e)i(consider)h(cryptographic)g(primitiv)o (es)h(that)d(implemen)o(t)j(suc)o(h)e(hash)h(functions:)23 b(In)17 b(the)f(\014rst)75 1125 y(part)11 b(of)f(the)h(pap)q(er)h(w)o (e)f(giv)o(e)g(a)g(computational)g(complexit)o(y)h(de\014nition)h(of)e (a)g(new)g(primitiv)o(e,)i(whic)o(h)f(w)o(e)75 1182 y(call)k Fm(universal)f(one-way)h(hash)g(functions)p Fn(,)d(and)i(then)g(sho)o (w)f(ho)o(w)g(to)g(construct)g(the)h(primitiv)o(e)h(based)75 1238 y(on)f(an)o(y)h(1-1)f(one-w)o(a)o(y)g(function.)21 b(In)c(the)e(second)h(part)f(w)o(e)g(presen)o(t)h(applications;)h(in)f (particular,)g(w)o(e)75 1295 y(sho)o(w)d(ho)o(w)h(to)f(use)i(the)f (primitiv)o(e)h(to)f(construct)f(a)h(digital)h(signature)f(whic)o(h)h (is)g(pro)o(v)m(ably)f(secure)h(and)75 1351 y(is)h(based)f(on)g(the)h (existence)g(of)f(an)o(y)g(1-1)f(one-w)o(a)o(y)h(functions.)146 1408 y(In)g(the)g(rest)g(of)f(the)h(in)o(tro)q(duction,)h(w)o(e)f (discuss)h(cryptographic)f(assumptions)g(and)g(primitiv)o(es)h(in)75 1464 y(section)g(1.1,)e(and)h(de\014ne)h(and)g(pro)o(vide)f(the)h (history)f(of)g(digital)h(signatures)f(in)h(section)g(1.2.)75 1586 y Fg(1.1)56 b(Cryptographic)18 b(Assumptions)g(and)h(Primitiv)n (es)75 1672 y Fn(A)c(curren)o(t)g(researc)o(h)g(program)f(in)i (cryptograph)o(y)e(is)h(to)g(pro)o(vide)g(constructions)g(of)g(basic)h (primitiv)o(es)75 1728 y(under)g(assumptions)f(that)g(are)f(as)h (general)h(as)f(p)q(ossible.)21 b(Usually)l(,)c(these)e(primitiv)o(es)h (are)f(\014rst)g(in)o(tro-)75 1785 y(duced)k(and)f(implemen)o(ted)i (based)e(on)f(sp)q(eci\014c)j(assumptions)e(\(e.g.)27 b(factoring)18 b(of)f(a)h(sp)q(eci\014c)h(family)75 1841 y(of)d(comp)q(osite)h(n)o(um)o(b)q(ers)g(is)g(hard\);)f(these)h (implemen)o(tations)h(rely)f(on)f(certain)h(algebraic)g(prop)q(erties) 75 1897 y(of)g(the)h(assumption)f(in)o(v)o(olv)o(ed.)28 b(On)18 b(the)f(other)g(hand,)h(basing)g(cryptograph)o(y)f(on)g (general)h(assump-)75 1954 y(tions)e(pro)o(vides)g(a)g(uni\014ed)i (cohesiv)o(e)e(complexit)o(y-theoretic)i(formalism)e(and)g(it)g(enric)o (hes)h(the)f(c)o(hoice)75 2010 y(of)j(candidates)g(for)g(underlying)h (mathematical)g(to)q(ols)e(for)h(implemen)o(tations.)32 b(Therefore,)19 b(general)75 2067 y(assumptions)c(are)g(app)q(ealing)i (to)e(b)q(oth)g(theorists)g(and)g(practitioners.)146 2123 y(Di\016e)k(and)h(Hellman)h([6)o(],)f(who)f(initiated)i(public-k)o (ey)h(cryptograph)o(y)c(in)j(1976,)e(suggested)g(the)75 2180 y(general)g(to)q(ols)f(of)g(one-w)o(a)o(y)f(functions)i(and)g (one-w)o(a)o(y)e(trap)q(do)q(or)h(functions.)30 b(Basically)l(,)20 b(a)e(function)75 2236 y Fi(F)23 b Fn(is)17 b(one-w)o(a)o(y)e(if)i(for) f(a)g(random)f Fi(x)p Fn(,)h(giv)o(en)h Fi(F)6 b Fn(\()p Fi(x)p Fn(\))16 b(it)h(is)g(hard)f(to)g(compute)g Fi(x)p Fn(.)23 b(A)16 b(function)h Fi(E)i Fn(is)e(one-)75 2293 y(w)o(a)o(y)d(trap)q(do)q(or)g(if)i(it)f(is)g(one-w)o(a)o(y)l(,)f(and)h (in)h(addition,)g(there)f(exists)g(a)g(secret)g(piece)h(of)e (information)h Fi(D)q Fn(,)75 2349 y(called)f(a)f(trap)q(do)q(or,)f (whic)o(h)h(represen)o(ts)g(the)g(in)o(v)o(erse)g(function,)g(suc)o(h)g (that)f Fi(D)q Fn(\()p Fi(E)s Fn(\()p Fi(x)p Fn(\)\))f(=)i Fi(E)s Fn(\()p Fi(D)q Fn(\()p Fi(x)p Fn(\)\))d(=)j Fi(x)75 2406 y Fn(and)k(the)g(kno)o(wledge)h(of)f Fi(D)h Fn(enables)g(easy)f (in)o(v)o(ersion.)26 b(The)17 b(idea)h(of)f(Di\016e)g(and)g(Hellman)i (has)e(since)75 2462 y(b)q(een)e(formalized,)f(and)g(pro)q(of)g(tec)o (hniques)h(based)f(on)f(complexit)o(y)i(theory)e(ha)o(v)o(e)g(b)q(een)i (dev)o(elop)q(ed.)21 b(In)75 2518 y(particular,)d(Y)l(ao)f([35)o(])f (has)h(initiated)i(the)e(researc)o(h)g(program)f(of)h(basing)g (cryptographic)h(primitiv)o(es)75 2575 y(on)d(general)h(assumptions.) 964 2750 y(1)p eop %%Page: 2 3 2 2 bop 146 121 a Fn(Examples)20 b(of)g(cryptographic)h(primitiv)o(es)g (\(in)g(addition)h(to)d(the)i(new)f(one)h(men)o(tioned)g(ab)q(o)o(v)o (e\))75 177 y(are:)e(\(a\))13 b(secure)h(message)g(sending)h([6)o(,)e (31,)g(30,)g(13],)g(\(b\))g(cryptographically)i(secure)g(pseudo-random) 75 234 y(generation)d([33)o(,)g(2],)g(and)g(\(c\))g(general)h(zero-kno) o(wledge)f(in)o(teractiv)o(e)h(pro)q(ofs)f([14)o(].)18 b(In)13 b(recen)o(t)f(y)o(ears,)g(all)75 290 y(these)i(primitiv)o(es)h (ha)o(v)o(e)e(b)q(een)i(constructed)f(under)g(formal)f(general)h (assumptions:)20 b(message)13 b(sending)75 346 y(on)k(trap)q(do)q(or)f (one-w)o(a)o(y)g(functions)h([35)o(,)f(17],)g(pseudo)h(random)g(bit)g (generator)e([35)o(,)i(22)o(,)f(11,)g(17],)g(and)75 403 y(general)g(zero-kno)o(wledge)f(in)o(teractiv)o(e)h(pro)q(ofs)f([12)o (,)g(20)o(,)g(27)o(])g(on)g(one-w)o(a)o(y)g(functions.)75 525 y Fg(1.2)56 b(One-w)n(a)n(y)19 b(hash)75 610 y Fn(The)c(need)g(for) f(a)g(primitiv)o(e)h(that)f(allo)o(ws)h(hashing)g(so)f(that)f(it)i(w)o (ould)g(b)q(e)g(hard)f(to)g(\014nd)h(collisions)i(w)o(as)75 667 y(recognized)h(since)f(the)g(earlier)h(da)o(ys)e(of)g(mo)q(dern)h (cryptograph)o(y:)22 b(Di\016e)16 b(and)h(Hellman)h([6)o(])f(men)o (tion)75 723 y(suc)o(h)g(functions)h(and)g(Rabin)g([28)o(])f(lists)g (required)i(prop)q(erties)e(of)g(suc)o(h)h(functions.)26 b(Other)17 b(examples)75 780 y(of)f(w)o(ork)g(in)o(v)o(olving)j(suc)o (h)e(functions)g(are)g(Merkle's)g([24)o(,)f(25,)g(23])g(and)h(Damgard)f ([5)o(].)25 b(One)18 b(usage)e(of)75 836 y(suc)o(h)d(functions)g(w)o (as)f(in)h(conjunction)g(with)g(digital)h(signatures:)k(instead)13 b(of)f(signing)i(a)e(long)h(message,)75 893 y(apply)j(the)f(hash)h (function)g(and)f(sign)h(the)f(result.)146 949 y(The)i(prop)q(ert)o(y)g (that)g(all)h(previous)h(researc)o(her)e(lo)q(ok)o(ed)h(for)f(w)o(as)f (that)h(giv)o(en)h(the)f(description)i(of)75 1006 y(the)g(hash)f (function)h Fi(h)g Fn(it)g(should)g(b)q(e)h(hard)e(to)g(\014nd)h Fi(x)f Fh(6)p Fn(=)h Fi(y)h Fn(suc)o(h)f(that)f Fi(h)p Fn(\()p Fi(x)p Fn(\))f Fh(6)p Fn(=)i Fi(h)p Fn(\()p Fi(y)r Fn(\).)29 b(W)l(e)18 b(deviate)75 1062 y(from)d(this)i(scenario)f(and)g (relax)g(the)g(rules)h(somewhat.)k(In)c(our)e(game,)g(\014rst)h Fi(x)g Fn(is)g(c)o(hosen)g(arbitrarily)75 1119 y(b)o(y)g(an)g(adv)o (ersary)l(,)g(then)g(and)g Fi(h)h Fn(is)f(c)o(hosen)h(at)e(random)h (and)g(the)h(adv)o(ersary)e(is)i(c)o(hallenged)g(to)f(come)75 1175 y(up)22 b(with)g(a)f Fi(y)j Fh(6)p Fn(=)g Fi(x)d Fn(suc)o(h)h(that)e Fi(h)p Fn(\()p Fi(x)p Fn(\))j(=)g Fi(h)p Fn(\()p Fi(y)r Fn(\).)38 b(This)22 b(relaxation)g(pro)o(v)o(es)e (to)h(b)q(e)h(v)o(ery)f(useful:)34 b(it)75 1231 y(allo)o(ws)17 b(construction)f(giv)o(en)h(an)o(y)f(1-1)g(one-w)o(a)o(y)g(function,)h (y)o(et)f(it)g(is)h(su\016cien)o(tly)h(strong)d(to)h(supp)q(ort)75 1288 y(applications)i(suc)o(h)e(as)g(public)i(\014ngerprin)o(ts)f(and)f (digital)h(signatures.)23 b(No)16 b(pro)o(v)m(ably)h(secure)f(general) 75 1344 y(construction)f(for)g(one-w)o(a)o(y)g(hash)g(functions)h(that) e(previous)i(researc)o(hers)f(considered)i(is)f(kno)o(wn.)75 1466 y Fg(1.3)56 b(Digital)17 b(Signatures)75 1552 y Fn(The)d(history)h(of)e(digital)j(signature)e(started)f(b)o(y)h (Di\016e)h(and)f(Hellman)i([6)o(])e(where)g(a)g(signature)h(sc)o(heme) 75 1608 y(based)j(on)f(trap)q(do)q(or)g(one-w)o(a)o(y)g(function)i(w)o (as)d(pro)o(vided.)28 b(Eac)o(h)18 b(user)f(has)h(a)f(public)j(k)o(ey)d Fi(E)j Fn(and)e(its)75 1665 y(secret)11 b(in)o(v)o(erse)h Fi(D)g Fn(as)f(a)g(priv)m(ate)h(k)o(ey)l(.)19 b(The)12 b(signer)g(sends)g(the)f(message)g Fi(M)16 b Fn(and)c(signs)g(b)o(y)f (applying)i(and)75 1721 y(sending)j Fi(D)q Fn(\()p Fi(M)5 b Fn(\),)13 b(an)o(y)h(receiv)o(er)i(can)e(v)o(erify)h(the)g(signature) f(b)o(y)h(computing)g Fi(E)s Fn(\()p Fi(D)q Fn(\()p Fi(M)5 b Fn(\)\))12 b(and)j(c)o(hec)o(king)75 1778 y(that)d(this)h(v)m(alue)h (matc)o(hes)f(the)f(message)h Fi(M)5 b Fn(.)19 b(The)13 b(ab)q(o)o(v)o(e)f(sc)o(heme)h(w)o(as)f(dev)o(elop)q(ed)j(without)d(a)h (precise)75 1834 y(notion)k(of)g(securit)o(y;)g(the)h(argumen)o(t)e(w)o (as)g(that)g(since)i(in)o(v)o(ersion)g(is)f(hard)g(to)g(compute,)g(a)f (forgery)g(is)75 1891 y(in)o(tractable)f(and)f(the)g(system)g(is)h (secure.)20 b(The)14 b(\014rst)g(implemen)o(tations)i(of)d(public-k)o (ey)k(cryptograph)o(y)75 1947 y(\(the)c(Merkle-Hellman,)i(RSA)f(and)g (Rabin`s)g(sc)o(hemes)g([26)o(,)f(31)o(,)g(30]\))f(ga)o(v)o(e)h (signature)g(sc)o(hemes)h(of)f(this)75 2004 y(kind.)146 2060 y(F)l(ollo)o(wing)19 b([6)o(],)f(signature)h(systems)f(design)h (has)g(b)q(ecome)g(an)f(extensiv)o(e)h(\014eld)h(of)e(researc)o(h)g (\(see)75 2116 y([15)o(]\);)11 b(w)o(e)g(concen)o(trate)f(here)i(only)f (on)g(pro)o(v)m(ably)g(secure)h(systems.)18 b(The)11 b(\014rst)g(sc)o(heme)g(to)f(deal)i(formally)75 2173 y(with)f(the)g(notion)g(of)g(securit)o(y)g(of)g(signature)g(sc)o(heme)g (w)o(as)f(suggested)h(b)o(y)g(Goldw)o(asser,)g(Micali)h(and)f(Y)l(ao)75 2229 y([16)o(])h(who)g(also)h(p)q(oin)o(ted)g(out)f(\015a)o(ws)g(in)h (the)g(Di\016e-Hellman)h(sc)o(heme.)19 b(They)13 b(based)g(their)g (probabilistic)75 2286 y(sc)o(heme)k(on)g(the)f(problem)i(of)e (factoring.)23 b(Then,)18 b(the)e(strongest)g(kno)o(wn)g(de\014nition)j (of)d(securit)o(y)h(w)o(as)75 2342 y(formalized)e(b)o(y)f(Goldw)o (asser,)g(Micali,)h(and)f(Riv)o(est)h([15)o(];)f(they)g(de\014ned)i (what)d(it)i(means)f(for)g(a)f(system)75 2399 y(to)j(b)q(e)i Fm(existential)r(ly)e(unfor)n(ge)n(able)h(under)h(an)g(adaptive)g (chosen)g(plaintext)f(attack)p Fn(;)h(\(this)f(is)g(what)f(w)o(e)75 2455 y(call)21 b(\\secure")g(in)g(the)f(rest)g(of)g(the)g(pap)q(er\).) 35 b(This)21 b(is)g(an)f(attac)o(k)f(b)o(y)h(an)g(adv)o(ersary)f (\(forger\))g(who)75 2512 y(initially)j(computes)c(a)h(plain)o(text)g (and)g(receiv)o(es)h(from)e(the)h(signature)g(algorithm)g(a)f(corresp)q (onding)75 2568 y(v)m(alid)h(signature;)f(this)g(is)g(rep)q(eated)f(in) i(an)e(adaptiv)o(e)g(fashion,)h(for)f(p)q(olynomially)i(man)o(y)e (iterations.)75 2625 y(Then)11 b(the)h(forger)e(has)g(to)h(pro)q(duce,) h(without)f(the)g(co)q(op)q(eration)h(of)e(the)h(signature)g (algorithm,)h(an)f(extra)964 2750 y(2)p eop %%Page: 3 4 3 3 bop 75 121 a Fn(signature)12 b(for)f(a)h(message)g(that)f(w)o(as)g (not)h(previously)h(signed.)20 b(A)12 b(secure)g(system)g(w)o(as)f (designed)i(under)75 177 y(the)f(assumption)h(that)e(factoring)h(is)g (hard,)h(or)e(a)h(more)g(general)g(assumption)h(that)e(cla)o(w-free)i (trap)q(do)q(or)75 234 y(p)q(erm)o(utations)19 b(exist)g([15)o(].)31 b(Recen)o(tly)l(,)21 b(Bellare)f(and)f(Micali)h([1])e(ha)o(v)o(e)h(sho) o(wn)f(ho)o(w)g(to)h(construct)f(a)75 290 y(secure)12 b(signature)g(system)f(based)h(on)f(the)h(assumption)g(that)f(trap)q (do)q(or)g(one-w)o(a)o(y)f(p)q(erm)o(utations)i(exist;)75 346 y(this)k(matc)o(hes)g(the)g(original)h(suggestion)f(of)f(Di\016e)h (and)g(Hellman,)h(but)g(this)f(time)g(the)g(system)g(has)f(a)75 403 y(pro)q(of)g(of)g(securit)o(y)l(.)146 459 y(As)j(one)g(can)g(see)h (in)g(the)f(ab)q(o)o(v)o(e)g(history)l(,)h(the)f(en)o(tire)g(researc)o (h)g(in)h(pro)o(v)m(ably)g(secure)g(signatures)75 516 y(w)o(as)e(directed)h(to)o(w)o(ards)e(designing)j(secure)f(signature)f (sc)o(hemes)h(based)g(on)f(the)h(trap)q(do)q(or)e(prop)q(ert)o(y)l(.)75 572 y(In)21 b([15)o(])e(the)h(trap)q(do)q(or)g(prop)q(ert)o(y)g(w)o(as) f(ev)o(en)h(included)j(as)c(part)h(of)g(the)g(de\014nition)h(of)f(a)g (signature)75 629 y(sc)o(heme.)h(F)l(urthermore,)15 b(there)g(is)h(no)f (system)g(whic)o(h)i(w)o(as)d(pro)o(v)o(ed)h(secure)h(ev)o(en)g(under)g (a)f(v)o(ery)h(w)o(eak)75 685 y(attac)o(k)e(and)h(is)h(based)f(on)h(a)f (one-w)o(a)o(y)f(function)i(\(ev)o(en)f(a)g(sp)q(ecial)i(one\))e(whic)o (h)h(is)g(not)f(trap)q(do)q(or.)146 742 y(In)j(this)g(w)o(ork,)f(w)o(e) h(presen)o(t)f(a)h Fm(one-way)h(b)n(ase)n(d)f(se)n(cur)n(e)f(signatur)n (e)i(scheme)p Fn(,)e(a)h(system)f(based)h(on)75 798 y(the)f(existence)g (of)f(1-1)g(one-w)o(a)o(y)g(functions;)i(the)e(system)g(mak)o(es)g(use) h(of)f(the)h(primitiv)o(e)h(of)e(univ)o(ersal)75 855 y(one-w)o(a)o(y)c(hash)h(functions.)20 b(Unlik)o(e)14 b(the)e(philosoph)o(y)i(of)f(previous)g(systems,)f(the)h(signature)g (algorithm)75 911 y(is)j(not)f(based)h(on)g(a)f(user's)g(adv)m(an)o (tage)g(of)g(\\kno)o(wing)g(some)h(trap)q(do)q(or)f(information")g(and) h(can)f(use)h(a)75 967 y(one-w)o(a)o(y)f(k)o(ey)g(without)g(a)g(trap)q (do)q(or.)k(Nev)o(ertheless,)d(the)f(system)g(is)g(pro)o(v)m(ably)h (secure.)146 1024 y(Tw)o(o)11 b(signature)h(sc)o(hemes)h(not)f(based)h (on)f(trap)q(do)q(or)g(functions)h(w)o(ere)f(suggested)g(previously)l (,)i(ho)o(w-)75 1080 y(ev)o(er)h(neither)h(of)e(them)h(w)o(as)f(pro)o (v)o(ed)g(secure,)h(ev)o(en)g(in)h(the)f(w)o(eak)o(est)f(sense)h(of)g ([15)o(]:)k(Fiat)14 b(and)h(Shamir)75 1137 y([8)o(])g(suggested)h(a)f (metho)q(d)h(on)f(con)o(v)o(erting)g(zero)h(kno)o(wledge)g(pro)q(ofs)f (for)g(iden)o(ti\014cation)i(in)o(to)e(e\016cien)o(t)75 1193 y(signatures)h(sc)o(hemes.)21 b(Merkle)16 b([23)o(])f(pro)o(vided) h(a)f(pragmatic)h(signature)f(sc)o(heme)h(based)g(on)f(an)o(y)h(\\en-) 75 1250 y(cryption)c(function".)19 b(Our)12 b(construction)g(follo)o (ws)g(Merkle's)g(paradigm)f(and)h(turns)g(it)f(in)o(to)h(a)f(pro)o(v)m (ably)75 1306 y(secure)16 b(sc)o(heme.)146 1363 y(Besides)24 b(the)e(fact)h(that)f(w)o(e)g(ha)o(v)o(e)h(reduced)g(the)g(su\016cien)o (t)h(conditions)g(for)e(ha)o(ving)h(a)f(secure)75 1419 y(signature,)d(the)f(sc)o(heme)h(has)f(other)g(practical)h(adv)m(an)o (tages.)28 b(F)l(or)18 b(example,)h(ev)o(en)g(if)g(the)f(source)g(of)75 1476 y(cryptographic)c(securit)o(y)h(is)f(a)g(single)i(instance)f(of)e (a)h(one-w)o(a)o(y)f(function)i(\(assumed)f(to)g(b)q(e)g(hard)h(to)e (all)75 1532 y(participan)o(ts\))k(whic)o(h)g(is)g(published)i(b)o(y)e (a)f(cen)o(tral)h(serv)o(er)f(\(sa)o(y)l(,)f(the)i(NSA\),)f(still)i(an) o(y)e(individual)k(in)75 1588 y(the)d(comm)o(unit)o(y)f(of)g(users)h (can)f(base)h(a)f(signature-k)o(ey)h(of)f(his)i(o)o(wn)e(on)g(this)h (function)g(instance)h(and)75 1645 y(sign)h(safely)g(\(a)e(scenario)i (similar)h(to)e(the)g(iden)o(ti\014cation)i(sc)o(heme)f(of)f([8]\).)28 b(F)l(urthermore,)19 b(concrete)75 1701 y(functions)14 b(whic)o(h)g(are)g(b)q(eliev)o(ed)h(to)e(b)q(e)h(one-w)o(a)o(y)f (require)h(less)g(time)g(to)f(compute)g(than)g(ones)h(assumed)75 1758 y(to)h(b)q(e)i(trap)q(do)q(or)f(functions.)23 b(Th)o(us,)15 b(basing)i(a)f(construction)g(on)g(one-w)o(a)o(y)f(functions)i(yields)h (a)d(more)75 1814 y(e\016cien)o(t)h(one)f(\(unless)h(the)g (construction)f(is)h(v)o(ery)f(ine\016cien)o(t,)h(whic)o(h)g(is)g(not)f (the)g(case)g(here\).)146 1871 y(Recen)o(tly)l(,)f(Impagliazzo)g(and)e (Rudic)o(h)j([19)o(])d(ha)o(v)o(e)g(sho)o(wn)g(a)h(separation)f(b)q(et) o(w)o(een)h(the)g(assumption)75 1927 y(that)i(one-w)o(a)o(y)h (functions)h(exist)f(and)g(the)g(assumption)h(that)e(trap)q(do)q(or)g (functions)i(exist,)g(at)e(least)h(in)75 1984 y(a)f(certain)i (restricted)f(mo)q(del.)23 b(This)16 b(pro)o(vides)g(ev)o(en)g(more)g (incen)o(tiv)o(e)h(to)e(try)g(to)h(w)o(eak)o(en)f(underlying)75 2040 y(assumptions,)g(and)g(to)g(ascertain)g(when)h(the)f(trap)q(do)q (or)g(prop)q(ert)o(y)g(is)g(needed.)75 2097 y Fo(Organization)25 b(of)e(the)g(pap)q(er:)29 b Fn(In)20 b(section)g(2)g(w)o(e)f(presen)o (t)h(and)g(construct)f(univ)o(ersal)i(one-w)o(a)o(y)75 2153 y(hash)c(functions.)25 b(In)18 b(Section)f(3)g(w)o(e)f(formally)h (de\014ne)h(secure)f(signature)g(sc)o(hemes)g(and)g(in)h(section)f(4)75 2209 y(w)o(e)g(construct)g(our)f(sc)o(heme)i(and)f(sk)o(etc)o(h)g(the)g (pro)q(of)g(of)f(its)i(securit)o(y)l(.)26 b(In)18 b(section)f(5)g(w)o (e)g(conclude)i(at)75 2266 y(least)c(some)g(op)q(en)h(problems.)75 2409 y Fj(2)69 b(Univ)n(ersal)22 b(One-w)n(a)n(y)h(Hash)g(F)-6 b(unctions)75 2511 y Fn(In)21 b(this)g(section)g(w)o(e)f(de\014ne)i (univ)o(ersal)g(one-w)o(a)o(y)e(hash)g(functions)h(\(UO)o(WHF\))f(and)h (sho)o(w)f(ho)o(w)g(to)75 2567 y(construct)e(them)g(giv)o(en)h(an)o(y)f (1-1)g(one-w)o(a)o(y)f(function.)30 b(After)18 b(w)o(e)g(de\014ne)h(UO) o(WHF,)f(in)h(section)g(2.1)75 2624 y(w)o(e)g(sho)o(w)g(that)f(comp)q (osing)i(families)h(of)e(UO)o(WHF)g(yields)i(a)e(family)h(of)f(UO)o (WHF.)f(In)i(section)g(2.2)964 2750 y(3)p eop %%Page: 4 5 4 4 bop 75 121 a Fn(w)o(e)19 b(sho)o(w)g(ho)o(w)g(to)g(construct)g(a)g (family)h(of)f(univ)o(ersal)i(one-w)o(a)o(y)d(hash)i(functions)g(that)f (compresses)75 177 y(one)e(bit.)24 b(Com)o(bining)18 b(this)f(and)f(the)h(comp)q(osition)g(prop)q(ert)o(y)g(allo)o(ws)f(us)h (to)f(construct)g(a)g(family)i(for)75 234 y(an)o(y)f(input)i(and)f (output)f(size)h(that)f(are)g(p)q(olynomially)j(related.)28 b(Section)18 b(2.3)f(sho)o(ws)g(ho)o(w)g(to)f(mak)o(e)75 290 y(UO)o(WHF)f(that)f(ha)o(v)o(e)h(a)g(more)g(succinct)h(represen)o (tation)f(and)h(are)f(more)f(e\016cien)o(t)i(to)f(compute.)146 346 y(Let)g Fh(f)p Fi(n)277 353 y Ff(1)295 358 y Fe(i)310 346 y Fh(g)f Fn(and)i Fh(f)p Fi(n)486 353 y Ff(0)504 358 y Fe(i)519 346 y Fh(g)e Fn(b)q(e)i(t)o(w)o(o)e(increasing)i (sequences)g(suc)o(h)f(that)g(for)f(all)i Fi(i)f(n)1513 353 y Ff(0)1531 358 y Fe(i)1559 346 y Fh(\024)d Fi(n)1633 353 y Ff(1)1651 358 y Fe(i)1667 346 y Fn(,)i(but)h Fh(9)p Fi(q)r Fn(,)g(a)75 403 y(p)q(olynomial,)h(suc)o(h)g(that)e Fi(q)r Fn(\()p Fi(n)590 410 y Ff(0)608 415 y Fe(i)623 403 y Fn(\))e Fh(\025)h Fi(n)728 410 y Ff(1)746 415 y Fe(i)777 403 y Fn(\(w)o(e)h(sa)o(y)h(that)f(these)i(sequences)g(are)f (p)q(olynomially)i(related\).)75 459 y(Let)i Fi(H)198 466 y Fd(k)238 459 y Fn(b)q(e)g(a)g(collection)h(of)e(functions)i(suc)o (h)f(that)f(for)g(all)i Fi(h)e Fh(2)h Fi(H)1284 466 y Fd(k)1305 459 y Fn(,)g Fi(h)g Fn(:)37 b Fh(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)1545 441 y Fd(n)1566 446 y Fc(1)1581 454 y Fe(k)1621 459 y Fh(7!)38 b(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)1817 441 y Fd(n)1838 446 y Fc(0)1853 454 y Fe(k)75 516 y Fn(and)18 b(let)g Fi(U)j Fn(=)338 484 y Fb(S)372 527 y Fd(k)401 516 y Fi(H)439 523 y Fd(k)460 516 y Fn(.)27 b(Let)18 b Fi(A)f Fn(b)q(e)i(a)e(probabilistic)j(p)q (olynomial)f(time)f(algorithm)f(\()p Fi(A)g Fn(is)h(a)f Fm(c)n(ol)r(lision)75 572 y(adversary)p Fn(\))e(that)f(on)g(input)i Fi(k)f Fn(outputs)g Fi(x)d Fh(2)28 b(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)994 554 y Fd(n)1015 559 y Fc(1)1030 567 y Fe(k)1066 572 y Fn(whic)o(h)16 b(w)o(e)e(call)i(an)e Fm(initial)h(value)p Fn(,)g(then)f(giv)o(en)75 629 y(a)g(random)f Fi(h)g Fh(2)g Fi(H)397 636 y Fd(k)432 629 y Fn(attempts)g(to)g(\014nd)i Fi(y)f Fh(2)27 b(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)973 611 y Fd(n)994 616 y Fc(1)1009 624 y Fe(k)1045 629 y Fn(suc)o(h)14 b(that)f Fi(h)p Fn(\()p Fi(x)p Fn(\))g(=)f Fi(h)p Fn(\()p Fi(y)r Fn(\))i(but)g Fi(x)e Fh(6)p Fn(=)h Fi(y)r Fn(.)20 b(In)14 b(other)75 685 y(w)o(ords,)g(after)h(getting)g (a)f(hash)i(function)g(it)f(tries)h(to)e(\014nd)i(a)f(collision)i(with) f(the)f(initial)j(v)m(alue.)75 742 y Fo(De\014nition:)32 b Fn(Suc)o(h)21 b(a)f Fi(U)26 b Fn(is)21 b(called)h(a)e Fm(family)h(of)g(universal)g(one-way)g(hash)h(functions)40 b Fn(if)21 b(for)f(all)75 798 y(p)q(olynomials)15 b Fi(p)d Fn(and)i(for)e(all)i(p)q(olynomial)g(time)g(probabilistic)h(algorithms) e Fi(A)g Fn(the)g(follo)o(wing)h(holds)g(for)75 855 y(su\016cien)o(tly) j(large)e Fi(k)q Fn(.)131 948 y(1.)22 b(If)d Fi(x)f Fh(2)38 b(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)463 930 y Fd(n)484 935 y Fc(1)499 943 y Fe(k)540 948 y Fn(is)19 b Fi(A)p Fn('s)g(initial)i(v)m(alue,)f(then)g Fi(P)6 b(r)q(ob)p Fn([)p Fi(A)p Fn(\()p Fi(h;)i(x)p Fn(\))17 b(=)i Fi(y)r(;)8 b(h)p Fn(\()p Fi(x)p Fn(\))17 b(=)i Fi(h)p Fn(\()p Fi(y)r Fn(\))p Fi(;)8 b(y)19 b Fh(6)p Fn(=)g Fi(x)p Fn(])g Fi(<)189 1005 y Fn(1)p Fi(=p)p Fn(\()p Fi(n)303 1012 y Ff(1)321 1018 y Fe(k)341 1005 y Fn(\))14 b(where)g(the)h(probabilit)o(y)g(is)g (tak)o(en)f(o)o(v)o(er)g(all)h Fi(h)e Fh(2)g Fi(H)1259 1012 y Fd(k)1294 1005 y Fn(and)i(the)f(random)g(c)o(hoices)h(of)f Fi(A)p Fn(.)131 1099 y(2.)22 b Fh(8)p Fi(h)15 b Fh(2)h Fi(H)339 1106 y Fd(k)377 1099 y Fn(there)h(is)g(a)g(description)h(of)f Fi(h)g Fn(of)f(length)i(p)q(olynomial)g(in)g Fi(n)1425 1106 y Ff(1)1443 1112 y Fe(k)1464 1099 y Fn(,)f(suc)o(h)g(that)f(giv)o (en)h Fi(h)p Fn('s)189 1155 y(description)f(and)g Fi(x)p Fn(,)e Fi(h)p Fn(\()p Fi(x)p Fn(\))h(is)h(computable)g(in)g(p)q (olynomial)h(time.)131 1249 y(3.)22 b Fi(H)227 1256 y Fd(k)269 1249 y Fn(is)h(accessible)g(:)33 b(there)22 b(exists)g(an)g(algorithm)f Fi(G)h Fn(suc)o(h)g(that)f Fi(G)g Fn(on)h(input)h Fi(k)f Fn(generates)189 1305 y(uniformly)16 b(at)e(random)h(a)g(description)i(of)e Fi(h)d Fh(2)h Fi(H)1060 1312 y Fd(k)1081 1305 y Fn(.)75 1399 y(W)l(e)i(note)f(that)g (w)o(e)g(treat)g Fi(H)566 1406 y Fd(k)602 1399 y Fn(as)g(a)g (collection)j(of)d(descriptions)i(of)e(functions;)h(t)o(w)o(o)f (di\013eren)o(t)h(descrip-)75 1456 y(tions)g(migh)o(t)g(corresp)q(ond)h (to)f(the)g(same)g(function.)146 1512 y(In)c(this)h(de\014nition)h(the) e(collision)i(adv)o(ersary)d Fi(A)h Fn(is)h(a)f(\(uniform\))f (algorithm.)19 b(W)l(e)11 b(can)g(alternativ)o(ely)75 1569 y(de\014ne)16 b(UO)o(WHF)f(where)g Fi(A)g Fn(is)g(a)g(p)q (olynomial)i(sized)f(circuit)g(\(the)f(non-uniform)h(case\).)j(In)d (this)f(case,)75 1625 y(all)g(our)f(results)g(still)i(hold,)f(but)f(w)o (e)g(require)h(the)f(one-w)o(a)o(y)f(functions)i(that)e(w)o(e)h(use)h (to)e(b)q(e)i(one-w)o(a)o(y)e(in)75 1681 y(the)i(non-uniform)h(setting) f(as)g(w)o(ell.)75 1803 y Fg(2.1)56 b(Comp)r(osition)16 b(of)j(UO)n(WHF)75 1889 y Fn(An)d(imp)q(ortan)o(t)f(prop)q(ert)o(y)g (of)g(UO)o(WHF)g(families)i(that)e(w)o(e)h(will)h(mak)o(e)e(use)h(of)f (\(and)g(is)h(probably)g(im-)75 1945 y(p)q(ortan)o(t)c(in)i (applications\))g(is)f(that)f(a)h(comp)q(osition)g(of)g(suc)o(h)g (families)h(remains)f(a)g(family)g(of)g(UO)o(WHF.)146 2002 y(Let)18 b Fi(H)268 2009 y Ff(1)287 2002 y Fi(;)8 b(H)346 2009 y Ff(2)365 2002 y Fi(;)g(:)g(:)g(:)d(H)484 2009 y Fd(l)515 2002 y Fn(b)q(e)18 b(families)i(of)e(functions)g(suc)o (h)h(that)e Fh(8)p Fi(i)h Fn(and)g Fh(8)p Fi(h)1409 2009 y Fd(i)1441 2002 y Fh(2)g Fi(H)1527 2009 y Fd(i)1559 2002 y Fi(h)1585 2009 y Fd(i)1616 2002 y Fn(:)35 b Fh(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)1777 1985 y Fd(n)1798 1990 y Fe(i)1830 2002 y Fh(7!)75 2058 y(f)p Fn(0)p Fi(;)g Fn(1)p Fh(g)188 2042 y Fd(n)209 2047 y Fe(i)p Fl(\000)p Fc(1)283 2058 y Fn(and)22 b Fi(n)405 2065 y Fd(i)442 2058 y Fi(<)h(n)527 2065 y Fd(i)p Ff(+1)586 2058 y Fn(.)39 b(W)l(e)21 b(call)h Fi(H)27 b Fn(=)c Fh(f)p Fi(h)p Fh(j)p Fi(h)f Fn(=)i Fi(h)1129 2065 y Ff(1)1163 2058 y Fh(\016)13 b Fi(h)1225 2065 y Ff(2)1260 2058 y Fh(\016)g Fi(:)8 b(:)g(:)13 b Fh(\016)h Fi(h)1427 2065 y Fd(l)1440 2058 y Fh(g)21 b Fn(an)g Fi(l)q Fm(-c)n(omp)n(osition)f Fn(of)75 2115 y Fi(H)113 2122 y Ff(1)133 2115 y Fi(;)8 b(H)192 2122 y Ff(2)210 2115 y Fi(;)g(:)g(:)g(:)d(;)j(H)350 2122 y Fd(l)362 2115 y Fn(.)18 b Fi(H)d Fn(is)d(a)f(m)o(ultiset;)h(if)g Fi(h)771 2122 y Ff(1)793 2115 y Fh(\016)r Fi(h)844 2122 y Ff(2)866 2115 y Fh(\016)r Fi(:)c(:)g(:)p Fh(\016)r Fi(h)997 2122 y Fd(l)1023 2115 y Fn(=)k Fi(h)1096 2098 y Fq(0)1096 2126 y Ff(1)1118 2115 y Fh(\016)r Fi(h)1169 2098 y Fq(0)1169 2126 y Ff(2)1191 2115 y Fh(\016)r Fi(:)c(:)g(:)p Fh(\016)r Fi(h)1322 2098 y Fq(0)1322 2128 y Fd(l)1346 2115 y Fn(for)j(di\013eren)o(t)g(\()p Fi(h)1631 2122 y Ff(1)1651 2115 y Fi(;)d(h)1698 2122 y Ff(2)1717 2115 y Fi(;)g(:)g(:)g(:)d(;)j(h)1845 2122 y Fd(l)1857 2115 y Fn(\))75 2171 y(and)15 b(\()p Fi(h)207 2155 y Fq(0)207 2183 y Ff(1)227 2171 y Fi(;)8 b(h)274 2155 y Fq(0)274 2183 y Ff(2)293 2171 y Fi(;)g(:)g(:)g(:)d(;)j(h)421 2155 y Fq(0)421 2184 y Fd(l)433 2171 y Fn(\),)15 b(b)q(oth)g(instances)h (are)f(mem)o(b)q(ers)g(of)g Fi(H)t Fn(.)75 2278 y Fo(Lemm)o(a)f(2.1)23 b Fm(L)n(et)16 b Fi(H)k Fm(b)n(e)d(an)g Fi(l)q Fm(-c)n(omp)n(osition)f (as)g(ab)n(ove.)23 b(If)17 b(ther)n(e)f(exists)h(an)f(algorithm)i Fi(A)f Fm(that)g(pr)n(o-)75 2334 y(duc)n(es)12 b(an)g(initial)f(value)i Fi(x)f Fm(and)g(when)g(given)g(a)g(uniformly)h(r)n(andom)f Fi(h)h Fh(2)g Fi(H)j(P)6 b(r)q(ob)p Fn([)p Fi(A)p Fn(\()p Fi(h;)i(x)p Fn(\))i(=)j Fi(y)r(;)8 b(h)p Fn(\()p Fi(x)p Fn(\))k(=)75 2390 y Fi(h)p Fn(\()p Fi(y)r Fn(\))p Fi(;)c(y)13 b Fh(6)p Fn(=)g Fi(x)p Fn(])f Fi(>)h(\017)p Fm(,)k(then)f(ther)n(e)g (exists)g(an)g Fn(1)c Fh(\024)h Fi(i)f Fh(\024)h Fi(l)k Fm(and)f(an)h(algorithm)f Fi(A)1398 2374 y Fq(0)1426 2390 y Fm(such)h(that)143 2484 y Fh(\017)23 b Fi(A)223 2468 y Fq(0)251 2484 y Fm(pr)n(o)n(duc)n(es)16 b(an)g(initial)f(value)i Fi(x)776 2491 y Fd(i)802 2484 y Fh(2)29 b(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)974 2468 y Fd(n)995 2473 y Fe(i)143 2578 y Fh(\017)23 b Fm(then)16 b(on)g(input)g Fi(h)499 2585 y Fd(i)526 2578 y Fh(2)d Fi(H)607 2585 y Fd(i)637 2578 y Fm(tries)j(to)h(\014nd)e(a)i Fi(y)948 2585 y Fd(i)978 2578 y Fm(that)g(c)n(ol)r(lides)f(with)g Fi(x)1356 2585 y Fd(i)1371 2578 y Fm(.)964 2750 y Fn(4)p eop %%Page: 5 6 5 5 bop 143 121 a Fh(\017)23 b Fi(P)6 b(r)q(ob)p Fn([)p Fi(A)335 104 y Fq(0)346 121 y Fn(\()p Fi(h)390 128 y Fd(i)404 121 y Fi(;)i(x)451 128 y Fd(i)464 121 y Fn(\))19 b(=)i Fi(y)579 128 y Fd(i)593 121 y Fi(;)8 b(h)p Fn(\()p Fi(x)684 128 y Fd(i)697 121 y Fn(\))19 b(=)i Fi(h)p Fn(\()p Fi(y)856 128 y Fd(i)870 121 y Fn(\))p Fi(;)8 b(y)931 128 y Fd(i)964 121 y Fh(6)p Fn(=)20 b Fi(x)1045 128 y Fd(i)1059 121 y Fn(])f Fi(>)h(\017=l)h Fm(wher)n(e)f(the)h(pr)n(ob)n (abilities)e(ar)n(e)h(taken)189 177 y(over)c Fi(h)315 184 y Fd(i)342 177 y Fh(2)d Fi(H)423 184 y Fd(i)453 177 y Fm(and)j Fi(A)575 161 y Fq(0)587 177 y Fm('s)g(r)n(andom)g(choic)n (es.)143 270 y Fh(\017)23 b Fm(The)16 b(running)f(time)h(of)h Fi(A)644 254 y Fq(0)672 270 y Fm(is)f(p)n(olynomial)r(ly)f(r)n(elate)n (d)h(to)h(that)g(of)f Fi(A)p Fm(.)75 373 y Fo(Pro)q(of:)22 b Fn(Supp)q(ose)c(that)d(suc)o(h)i(an)f Fi(A)h Fn(exists)g(and)f(supp)q (ose)h(that)f Fi(A)p Fn('s)g(initial)j(v)m(alue)e(is)g Fi(x)g Fn(and)f(then)h Fi(A)75 430 y Fn(is)g(giv)o(en)h Fi(h)d Fn(=)h Fi(h)361 437 y Ff(1)392 430 y Fh(\016)11 b Fi(h)452 437 y Ff(2)484 430 y Fh(\016)f Fi(:)e(:)g(:)i Fh(\016)h Fi(h)642 437 y Fd(l)655 430 y Fn(.)25 b(Whenev)o(er)17 b Fi(A)g Fn(succeeds)h(in)g(\014nding)g(a)f Fi(y)h Fn(suc)o(h)g(that)e Fi(h)p Fn(\()p Fi(y)r Fn(\))f(=)g Fi(h)p Fn(\()p Fi(x)p Fn(\))75 486 y(but)g Fi(y)f Fh(6)p Fn(=)f Fi(x)h Fn(there)h(is)g(the)f (\014rst)g(1)f Fh(\024)g Fi(i)f Fh(\024)h Fi(l)i Fn(where)f(the)h(comp) q(osition)g(of)f(the)g Fi(h)1417 493 y Fd(j)1436 486 y Fn('s)g(on)g Fi(x)g Fn(and)h Fi(y)h Fn(b)q(ecomes)75 543 y(equal,)g(i.e.)k Fi(h)312 550 y Fd(i)p Ff(+1)381 543 y Fh(\016)10 b Fi(:)e(:)g(:)g Fh(\016)i Fi(h)536 550 y Fd(l)549 543 y Fn(\()p Fi(y)r Fn(\))i Fh(6)p Fn(=)h Fi(h)695 550 y Fd(i)p Ff(+1)764 543 y Fh(\016)d Fi(:)e(:)g(:)g Fh(\016)i Fi(h)919 550 y Fd(l)932 543 y Fn(\()p Fi(x)p Fn(\))15 b(but)g Fi(h)1118 550 y Fd(i)1142 543 y Fh(\016)10 b Fi(:)e(:)g(:)g Fh(\016)i Fi(h)1297 550 y Fd(l)1310 543 y Fn(\()p Fi(y)r Fn(\))i(=)h Fi(h)1456 550 y Fd(i)1480 543 y Fh(\016)d Fi(:)e(:)g(:)g Fh(\016)i Fi(h)1635 550 y Fd(l)1648 543 y Fn(\()p Fi(x)p Fn(\).)19 b(Hence,)75 599 y(b)o(y)c(the)g(pigeon)g(hole)h(principle,)h(there)e(m)o(ust)g (exist)g(an)g(1)d Fh(\024)h Fi(i)f Fh(\024)h Fi(l)j Fn(where)f(this)g (o)q(ccurs)g(in)h(at)e(least)h(1)p Fi(=l)75 656 y Fn(of)g(the)g(cases.) 20 b(F)l(or)14 b(that)h Fi(i)p Fn(,)f(if)i Fi(A)p Fn(\()p Fi(h;)8 b(x)p Fn(\))j(=)i Fi(y)r Fn(,)i(then)131 812 y Fi(P)6 b(r)q(ob)p Fn([\()p Fi(h)287 819 y Fd(i)p Ff(+1)356 812 y Fh(\016)k Fi(:)e(:)g(:)g Fh(\016)i Fi(h)511 819 y Fd(l)524 812 y Fn(\()p Fi(y)r Fn(\))i Fh(6)p Fn(=)h Fi(h)670 819 y Fd(i)p Ff(+1)739 812 y Fh(\016)d Fi(:)e(:)g(:)g Fh(\016)i Fi(h)894 819 y Fd(l)907 812 y Fn(\()p Fi(x)p Fn(\)\))f Fh(^)i Fn(\()p Fi(h)1081 819 y Fd(i)1105 812 y Fh(\016)f Fi(:)e(:)g(:)g Fh(\016)h Fi(h)1259 819 y Fd(l)1273 812 y Fn(\()p Fi(y)r Fn(\))j(=)h Fi(h)1419 819 y Fd(i)1443 812 y Fh(\016)d Fi(:)e(:)g(:)g Fh(\016)i Fi(h)1598 819 y Fd(l)1611 812 y Fn(\()p Fi(x)p Fn(\)\)])h Fi(>)i(\017=l)90 911 y Fn(where)i(the)g(probabilit)o(y)h(is)g(o)o(v)o (er)e(uniformly)i(random)e Fi(h)f Fn(=)g Fi(h)1160 918 y Ff(1)1190 911 y Fh(\016)c Fi(h)1248 918 y Ff(2)1277 911 y Fh(\016)h Fi(:)e(:)g(:)f Fh(\016)j Fi(h)1431 918 y Fd(l)1456 911 y Fh(2)j Fi(H)19 b Fn(and)c Fi(A)p Fn('s)f(random)75 968 y(c)o(hoices.)21 b(This)15 b Fi(i)g Fn(w)o(ould)h(b)q(e)g(the)f (one)g(for)g(whic)o(h)h(w)o(e)f(can)g(\\break")g Fi(H)1295 975 y Fd(i)1324 968 y Fn(\(i.e.)20 b(\014nd)c(collisions\).)146 1024 y(W)l(e)g(can)h(no)o(w)f(de\014ne)i(an)f(algorithm)f Fi(A)846 1008 y Fq(0)875 1024 y Fn(that)g(\014rst)g(pro)q(duces)h(an)g (initial)i Fi(x)1486 1031 y Fd(i)1500 1024 y Fn(,)e(then)g(giv)o(en)g (a)f(ran-)75 1080 y(domly)g(c)o(hosen)f Fi(h)384 1087 y Fd(i)411 1080 y Fh(2)e Fi(H)492 1087 y Fd(i)521 1080 y Fn(tries)i(to)g(\014nd)h Fi(y)791 1087 y Fd(i)820 1080 y Fn(that)f(collides)i(with)f Fi(x)1208 1087 y Fd(i)1237 1080 y Fn(:)131 1172 y(1.)22 b(Giv)o(en)15 b Fi(A)p Fn('s)g(initial)i (v)m(alue)g Fi(x)p Fn(.)131 1265 y(2.)22 b(Cho)q(ose)15 b(at)h(random)f Fi(h)597 1272 y Fd(i)p Ff(+1)671 1265 y Fh(2)f Fi(H)753 1272 y Fd(i)p Ff(+1)812 1265 y Fi(;)8 b(h)859 1272 y Fd(i)p Ff(+2)931 1265 y Fh(2)14 b Fi(H)1013 1272 y Fd(i)p Ff(+2)1072 1265 y Fi(;)8 b(:)g(:)g(:)d(h)1179 1272 y Fd(l)1206 1265 y Fh(2)15 b Fi(H)1289 1272 y Fd(l)1317 1265 y Fn(and)h(output)g Fi(x)1582 1272 y Fd(i)1610 1265 y Fn(=)e Fi(h)1685 1272 y Fd(i)p Ff(+1)1755 1265 y Fh(\016)d Fi(:)d(:)g(:)g Fh(\016)189 1322 y Fi(h)215 1329 y Fd(l)228 1322 y Fn(\()p Fi(x)p Fn(\).)131 1414 y(3.)22 b(on)15 b(input)h Fi(h)399 1421 y Fd(i)413 1414 y Fn(,)f(c)o(ho)q(ose)g(at)g (random)g Fi(h)834 1421 y Ff(1)866 1414 y Fh(2)e Fi(H)947 1421 y Ff(1)967 1414 y Fi(;)8 b(:)g(:)g(:)t(;)g(h)1094 1421 y Fd(i)p Fq(\000)p Ff(1)1166 1414 y Fh(2)k Fi(H)1246 1421 y Fd(i)p Fq(\000)p Ff(1)131 1507 y Fn(4.)22 b(run)15 b(algorithm)g Fi(A)h Fn(on)f(input)h Fi(h)d Fn(=)g Fi(h)826 1514 y Ff(1)856 1507 y Fh(\016)d Fi(:)e(:)g(:)g Fh(\016)h Fi(h)1010 1514 y Fd(i)p Fq(\000)p Ff(1)1080 1507 y Fh(\016)h Fi(h)1139 1514 y Fd(i)1163 1507 y Fh(\016)g Fi(h)1222 1514 y Fd(i)p Ff(+1)1289 1507 y Fi(:)e(:)g(:)e(h)1376 1514 y Fd(l)1389 1507 y Fn(.)131 1600 y(5.)22 b(if)15 b(the)h(output)f(of)f Fi(A)i Fn(is)f Fi(y)i Fn(output)e Fi(y)814 1607 y Fd(i)841 1600 y Fn(=)e Fi(h)915 1607 y Fd(i)p Ff(+1)985 1600 y Fh(\016)d Fi(:)e(:)g(:)g Fh(\016)i Fi(h)1140 1607 y Fd(l)1153 1600 y Fn(\()p Fi(y)r Fn(\).)146 1692 y(All)21 b(the)e(functions)i Fi(h)534 1699 y Ff(1)554 1692 y Fi(;)8 b(h)601 1699 y Ff(2)620 1692 y Fi(;)g(:)g(:)g(:)d(;)j(h) 748 1699 y Fd(l)780 1692 y Fn(are)19 b(c)o(hosen)h(uniformly)h(at)e (random)h(from)f(their)h(resp)q(ectiv)o(e)75 1748 y(families)15 b Fi(H)277 1755 y Ff(1)296 1748 y Fi(;)8 b(H)355 1755 y Ff(2)374 1748 y Fi(;)g(:)g(:)g(:)d(H)493 1755 y Fd(l)506 1748 y Fn(,)13 b(and)h(th)o(us)f Fi(h)g Fn(is)h(uniformly)h (distributed)g(in)f Fi(H)t Fn(.)19 b(Therefore)13 b(the)g(distribution) 75 1805 y(on)i(inputs)h(that)f(the)g(sim)o(ulated)h Fi(A)f Fn(sees)h(is)f(iden)o(tical)j(to)c(the)h(usual)h(one)g(and)125 1904 y Fi(P)6 b(r)q(ob)p Fn([\()p Fi(h)281 1911 y Fd(i)p Ff(+1)349 1904 y Fh(\016)k Fi(:)e(:)g(:)g Fh(\016)i Fi(h)504 1911 y Fd(l)517 1904 y Fn(\()p Fi(y)r Fn(\))i Fh(6)p Fn(=)h Fi(h)663 1911 y Fd(i)p Ff(+1)733 1904 y Fh(\016)d Fi(:)e(:)g(:)g Fh(\016)i Fi(h)888 1911 y Fd(l)901 1904 y Fn(\()p Fi(x)p Fn(\)\))f Fh(^)h Fn(\()p Fi(h)1074 1911 y Fd(i)1098 1904 y Fh(\016)g Fi(:)e(:)g(:)g Fh(\016)i Fi(h)1253 1911 y Fd(l)1266 1904 y Fn(\()p Fi(y)r Fn(\))i(=)h Fi(h)1412 1911 y Fd(i)1437 1904 y Fh(\016)c Fi(:)f(:)g(:)h Fh(\016)g Fi(h)1591 1911 y Fd(l)1605 1904 y Fn(\()p Fi(x)p Fn(\)\)])i Fi(>)i(\017=l)q(:)146 2004 y Fn(Therefore)h Fi(P)6 b(r)q(ob)p Fn([)p Fh(^)p Fi(h)p Fn(\()p Fi(x)563 2011 y Fd(i)577 2004 y Fn(\))12 b(=)h Fi(h)p Fn(\()p Fi(y)721 2011 y Fd(i)735 2004 y Fn(\))c Fh(^)g Fi(y)823 2011 y Fd(i)850 2004 y Fh(6)p Fn(=)k Fi(x)924 2011 y Fd(i)938 2004 y Fn(])f Fi(>)h(\017=l)q Fn(.)19 b(Note)14 b(that)g(the)h(running)h(time)e(of)h Fi(A)1741 1988 y Fq(0)1767 2004 y Fn(is)g(the)75 2060 y(running)h(time)g(of)f Fi(A)g Fn(plus)h(some)f(p)q(olynomial)i(amoun)o(t)d(of)h(w)o(ork.)k Fa(2)75 2117 y Fo(Remark:)d Fn(The)d(comp)q(osition)h(lemma)f(motiv)m (ates)g(the)h(separation)e(of)h(c)o(ho)q(osing)h Fi(x)f Fn(from)f(that)g(of)h Fi(h)g Fn(in)75 2173 y(our)h(de\014nition)h(of)f (UO)o(WHF)f(families.)21 b(If)14 b(w)o(e)g(had)g(de\014ned)h(it)f (di\013eren)o(tly)l(,)h(with)f Fi(x)g Fn(b)q(eing)h(part)e(of)h(the)75 2230 y(input)i(c)o(hosen)g(at)e(random)h(uniformly)l(,)h(the)f(lemma)h (w)o(ouldn't)f(ha)o(v)o(e)g(b)q(een)h(true.)k(Coun)o(ter-examples)75 2286 y(can)d(b)q(e)g(constructed)g(similarly)i(to)d(ones)h(in)g([11)o (].)24 b(Note)17 b(that)f(in)h(step)g(1)f(of)h(algorithm)f Fi(A)1679 2270 y Fq(0)1708 2286 y Fn(the)h Fi(x)1814 2293 y Fd(i)1844 2286 y Fn(is)75 2343 y(not)e(necessarily)h(c)o(hosen)g (uniformly)g(at)f(random)f(o)o(v)o(er)h(all)31 b Fh(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)1246 2326 y Fd(n)1267 2331 y Fe(i)1281 2343 y Fn(.)146 2399 y(Lemma)i(2.1)f(is)i(a)e(k)o(ey)h (comp)q(onen)o(t)h(in)g(the)f(pro)q(of)g(of)f(the)i(next)f(theorem:)17 b(Let)10 b Fh(f)p Fi(n)1519 2406 y Ff(0)1537 2411 y Fe(i)1552 2399 y Fh(g)p Fi(;)e Fh(f)p Fi(n)1646 2406 y Ff(1)1664 2411 y Fe(i)1678 2399 y Fh(g)p Fi(;)g Fh(f)p Fi(n)1772 2406 y Ff(2)1790 2411 y Fe(i)1804 2399 y Fh(g)p Fi(;)g(:)g(:)g(:)75 2456 y Fn(b)q(e)17 b(a)f(sequence)i(of)e(increasing)h(sequences,)h(let) f Fi(U)952 2463 y Ff(1)971 2456 y Fi(;)8 b(U)1023 2463 y Ff(2)1042 2456 y Fi(;)g(:)g(:)g(:)14 b Fn(b)q(e)j(a)f(sequence)i(of)e (families)h(of)f(UO)o(WHF)75 2512 y(suc)o(h)f(that)g Fi(U)307 2519 y Fd(i)333 2512 y Fn(=)381 2480 y Fb(S)416 2524 y Fd(k)445 2512 y Fi(H)483 2519 y Fd(i;k)541 2512 y Fn(where)g Fh(8)p Fi(h)e Fh(2)g Fi(H)817 2519 y Fd(i;k)875 2512 y Fi(h)g Fn(:)27 b Fh(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)1067 2493 y Fd(n)1088 2498 y Fe(i)1099 2507 y(k)1134 2512 y Fh(7!)28 b(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)1320 2491 y Fd(n)1341 2498 y Fc(\()p Fe(i)p Fl(\000)p Fc(1\))1415 2507 y Fe(k)1437 2512 y Fn(.)20 b(W)l(e)15 b(also)g(require)h(that)75 2569 y(the)d Fi(U)182 2576 y Fd(i)197 2569 y Fn('s)f(b)q(e)i Fm(simultane)n(ously)g(har)n(d)p Fn(:)20 b(for)12 b(ev)o(ery)i(p)q (olynomial)h Fi(p)e Fn(and)g(ev)o(ery)h(probabilistic)h(p)q(olynomial-) 75 2625 y(time)j(algorithm)f Fi(A)p Fn(,)h(there)f(is)h(a)f Fi(K)j Fn(suc)o(h)e(that)f Fh(8)p Fi(k)g(>)g(K)j Fn(and)e(for)f(all)h Fi(i)e Fh(\025)h Fn(1,)g Fi(A)g Fn(cannot)h(succeed)g(in)964 2750 y(5)p eop %%Page: 6 7 6 6 bop 75 121 a Fn(\014nding)17 b(collisions)i(in)d Fi(H)512 128 y Fd(i;k)571 121 y Fn(with)h(probabilit)o(y)g(greater)e (than)1216 103 y Ff(1)p 1176 110 99 2 v 1176 137 a Fd(p)p Ff(\()p Fd(n)1229 142 y Fe(i)1240 150 y(k)1261 137 y Ff(\))1280 121 y Fn(.)22 b(Let)16 b Fi(l)f Fn(:)e Fi(N)19 b Fh(7!)14 b Fi(N)21 b Fn(b)q(e)16 b(a)g(p)q(olyno-)75 189 y(mial)h(computable)g(function)g(suc)o(h)f(that)f Fi(q)r Fn(\()p Fi(n)871 196 y Ff(0)889 202 y Fe(k)910 189 y Fn(\))f Fi(>)g(n)1018 198 y Fd(l)p Ff(\()p Fd(k)q Ff(\))1076 204 y Fe(k)1113 189 y Fn(for)i(some)g(p)q(olynomial)h Fi(q)r Fn(.)23 b(Let)16 b Fi(H)1712 196 y Fd(k)1749 189 y Fn(b)q(e)h(the)75 245 y Fi(l)q Fn(\()p Fi(k)q Fn(\)-comp)q(osition)e (of)g Fi(H)509 252 y Ff(1)p Fd(;k)557 245 y Fi(;)8 b(H)616 252 y Ff(2)p Fd(;k)664 245 y Fi(;)g(:)g(:)g(:)d(H)783 254 y Fd(l)p Ff(\()p Fd(k)q Ff(\))p Fd(;k)887 245 y Fn(and)15 b(let)h Fi(U)h Fn(=)1137 213 y Fb(S)1172 257 y Fd(k)1201 245 y Fi(H)1239 252 y Fd(k)1260 245 y Fn(.)75 339 y Fo(Theorem)e(1)23 b Fi(U)e Fm(is)16 b(a)g(family)h(of)f(UO)o(WHF.)75 433 y Fo(Pro)q(of:)i Fn(It)13 b(is)g(easy)g(to)f(see)h(that)f Fi(H)681 440 y Fd(k)715 433 y Fn(is)h(accessible,)i(and)d(that)g(giv)o (en)i Fi(h)e Fh(2)h Fi(H)1391 440 y Fd(k)1425 433 y Fn(computing)g Fi(h)p Fn(\()p Fi(x)p Fn(\))f(can)h(b)q(e)75 489 y(done)i(in)g(p)q (olynomial)g(time.)20 b(As)15 b(for)e(the)h(hardness)h(of)f(\014nding)h (collisions,)h(assume)f(the)f(con)o(trary)l(,)f(i.e.)75 546 y(there)f(exists)g(an)g(algorithm)g Fi(A)g Fn(suc)o(h)h(that)e(for) g(ev)o(ery)h(p)q(olynomial)i Fi(p)p Fn(.)19 b(for)11 b(in\014nite)j Fi(k)q Fn('s,)e(the)g(probabilit)o(y)75 602 y(that)i Fi(A)i Fn(succeeds)g(in)g(\014nding)h(collisions)g(for)e Fi(H)910 609 y Fd(k)946 602 y Fn(is)h(larger)f(than)g(1)p Fi(=p)p Fn(\()p Fi(k)q Fn(\).)146 659 y(Lemma)i(2.1)f(and)i(the)f(fact) g(the)g Fi(U)759 666 y Fd(i)773 659 y Fn('s)g(are)g(sim)o(ultaneously)i (hard)e(imply)i(that)d(otherwise)i(one)f(of)75 715 y(the)e Fi(U)184 722 y Fd(i)198 715 y Fn('s)g(w)o(ould)h(not)e(b)q(e)i(a)f (family)h(of)f(UO)o(WHF.)f Fa(2)75 837 y Fg(2.2)56 b(Compressing)17 b(One)i(Bit)75 923 y Fn(Theorem)i(1)g(\(the)g(comp)q(osition)h (theorem\))e(tells)j(us)e(that)f(in)i(order)f(to)g(construct)g(an)o(y)g (family)g(of)75 979 y(UO)o(WHF)13 b(it)h(su\016ces)f(to)g(ha)o(v)o(e)g (a)g(construction)h(for)e(a)h(family)h(of)f(UO)o(WHF)g(that)g (compresses)g(one)h(bit,)75 1036 y(i.e)19 b(that)e Fi(h)h Fn(:)36 b Fh(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)446 1019 y Fd(k)483 1036 y Fh(7!)36 b(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)677 1019 y Fd(k)q Fq(\000)p Ff(1)760 1036 y Fh(8)p Fi(h)18 b Fh(2)g Fi(H)915 1043 y Fd(k)936 1036 y Fn(.)29 b(In)19 b(this)g(subsection)g(w)o(e)f(sho)o(w)g(ho)o(w)f(to)h(compress) 75 1092 y(one)h(bit,)g(assuming)g(that)f(a)h(1-1)f(one-w)o(a)o(y)g (function)h(is)g(a)o(v)m(ailable.)32 b(The)19 b(construction)g(is)g(ac) o(hiev)o(ed)75 1148 y(b)o(y)d(comp)q(osing)h(a)e(univ)o(ersal)i(hash)g (function)g(with)f(the)g(one-w)o(a)o(y)f(function.)24 b(W)l(e)16 b(start)f(b)o(y)h(assuming)75 1205 y(that)k(the)h(one-w)o(a) o(y)f(function)i(is)f(a)f(p)q(erm)o(utation,)i(then)f(relax)g(this)h (condition)g(to)e(a)g(1-1)h(one-w)o(a)o(y)75 1261 y(function.)h(A)16 b Fm(one-way)h(p)n(ermutation)f Fn(is)g(a)g(1-1)f(length)h(preserving)h (function)f Fi(f)21 b Fn(that)15 b(is)h(p)q(olynomial-)75 1318 y(time)c(computable,)h(but)f(for)g(an)o(y)f(p)q(olynomial)j Fi(p)e Fn(and)g(an)o(y)g(probabilistic)i(p)q(olynomial)g(time)e (algorithm)75 1374 y Fi(A)i Fn(\()p Fm(an)h(inversion)f(adversary)p Fn(\))h(and)f(su\016cien)o(tly)i(large)e Fi(k)q Fn(,)h Fi(P)6 b(r)q(ob)i Fn([)o Fi(A)p Fn(\()p Fi(f)d Fn(\()p Fi(x)p Fn(\)\))11 b(=)i Fi(x)p Fn(])f Fh(\024)h Fn(1)p Fi(=p)p Fn(\()p Fi(k)q Fn(\))g(where)i(the)75 1431 y(probabilit)o(y)h (is)g(tak)o(en)f(uniformly)h(o)o(v)o(er)e(all)j Fi(x)12 b Fh(2)28 b(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)1054 1414 y Fd(k)1089 1431 y Fn(and)15 b Fi(A)p Fn('s)g(in)o(ternal)h(random)f(c) o(hoices.)146 1487 y(W)l(e)g(will)i(\014rst)e(assume)g(that)f(w)o(e)h (ha)o(v)o(e)g(a)g(one-w)o(a)o(y)f(p)q(erm)o(utation)h Fi(f)5 b Fn(.)146 1544 y(The)20 b(source)h(of)e(the)i(compression)g (will)h(b)q(e)f(a)f(family)h(of)f(strongly)g(univ)o(ersal)h(hash)g (functions.)75 1600 y(Carter)13 b(and)g(W)l(egman)h([34)o(,)f(4])g (de\014ned)i Fm(str)n(ongly)e(universal)1125 1607 y Ff(2)1173 1600 y Fn(functions)h(as)f(a)g(family)i(of)e(functions)h Fi(G)75 1657 y Fn(where)f Fi(g)h Fn(:)e Fi(C)k Fh(7!)d Fi(B)j Fn(for)c(all)i Fi(g)g Fh(2)f Fi(G)g Fn(if)g(for)g(ev)o(ery)f (pair)i(of)e(inputs)i(\()p Fi(a)1222 1664 y Ff(1)1242 1657 y Fi(;)8 b(a)1287 1664 y Ff(2)1306 1657 y Fn(\))k(and)i(pair)f(of) g(outputs)f(\()p Fi(b)1766 1664 y Ff(1)1785 1657 y Fi(;)c(b)1826 1664 y Ff(2)1845 1657 y Fn(\),)75 1713 y(the)19 b(n)o(um)o(b)q(er)g(of) g(functions)h(that)e(map)h Fi(a)813 1720 y Ff(1)851 1713 y Fn(to)g Fi(b)931 1720 y Ff(1)969 1713 y Fn(and)g Fi(a)1085 1720 y Ff(2)1123 1713 y Fn(to)g Fi(b)1203 1720 y Ff(2)1241 1713 y Fn(is)g Fh(j)p Fi(G)p Fh(j)p Fi(=)p Fh(j)p Fi(B)r Fh(j)1437 1696 y Ff(2)1456 1713 y Fn(.)31 b(If)19 b Fi(g)h Fh(2)g Fi(G)e Fn(is)i(c)o(hosen)75 1769 y(uniformly)d(then)g(the)f(the) g(v)m(alues)i(of)d Fi(g)r Fn(\()p Fi(x)p Fn(\))g(and)i Fi(g)r Fn(\()p Fi(y)r Fn(\))d(are)i(indep)q(enden)o(t)j(and)d (uniformly)h(distributed)75 1826 y(in)f Fi(B)i Fn(for)d(an)o(y)f Fi(x;)8 b(y)14 b Fh(2)f Fi(C)s Fn(,)146 1882 y Fm(Col)r(lision)d(A)n(c) n(c)n(essibility)d Fn(prop)q(ert)o(y:)17 b(W)l(e)10 b(require)h (another)f(prop)q(ert)o(y)g(from)f(the)h(strongly)g(univ)o(ersal)1869 1889 y Ff(2)75 1939 y Fn(family)17 b Fi(G)p Fn(.)24 b(Giv)o(en)17 b(that)f Fi(g)r Fn(\()p Fi(x)p Fn(\))e(=)h Fi(g)r Fn(\()p Fi(y)r Fn(\))g(it)i(is)g(p)q(ossible)i(to)d(generate)g(in)i(p)q (olynomial)g(time)f(a)f(function)75 1995 y Fi(g)f Fh(2)e Fi(G)i Fn(suc)o(h)h(that)f Fi(g)r Fn(\()p Fi(x)p Fn(\))d(=)i Fi(g)r Fn(\()p Fi(y)r Fn(\))g(with)i(equal)g(probabilit)o(y)h(o)o(v)o (er)e(all)h(functions)h(in)f Fi(G)f Fn(whic)o(h)i(ob)q(ey)f(the)75 2052 y(restriction)g Fi(g)r Fn(\()p Fi(x)p Fn(\))11 b(=)i Fi(g)r Fn(\()p Fi(y)r Fn(\).)146 2108 y(F)l(or)f(an)i(example)g(of)f (suc)o(h)h(a)f(family)l(,)h(consider)g(the)g(lines)h(in)f(the)f (\014nite)i(\014eld)f Fi(GF)6 b Fn([2)1595 2092 y Fd(k)1616 2108 y Fn(],)13 b Fi(ax)6 b Fn(+)g Fi(b)15 b Fn(with)75 2165 y(the)g(last)g(bit)h(c)o(hopp)q(ed)h(for)d(the)h(compression.)21 b Fi(G)947 2172 y Fd(k)981 2165 y Fn(=)13 b Fh(f)p Fi(g)1074 2172 y Fd(a;b)1119 2165 y Fh(j)p Fi(g)1154 2172 y Fd(a;b)1199 2165 y Fn(\()p Fi(x)p Fn(\))f(=)h Fi(chop)p Fn(\()p Fi(ax)c Fn(+)i Fi(b)p Fn(\))p Fi(;)d(a;)g(b)i Fh(2)j Fi(GF)6 b Fn([2)1819 2148 y Fd(k)1840 2165 y Fn(])p Fh(g)75 2221 y Fn(where)15 b(all)i(the)e(computation)g(are)g(in)h Fi(GF)6 b Fn([2)849 2205 y Fd(k)870 2221 y Fn(])15 b(and)g Fi(chop)e Fn(:)27 b Fh(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)1243 2205 y Fd(k)1275 2221 y Fh(7!)28 b(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)1461 2205 y Fd(k)q Fq(\000)p Ff(1)1541 2221 y Fn(simply)17 b(c)o(hops)e(the)75 2278 y(last)g(bit.)146 2334 y(De\014ne)f Fi(H)323 2341 y Fd(k)357 2334 y Fn(=)f Fh(f)p Fi(h)f Fn(=)h Fi(g)c Fh(\016)e Fi(f)e Fh(j)p Fi(g)13 b Fh(2)g Fi(G)729 2341 y Fd(k)750 2334 y Fh(g)p Fn(,)h(where)g Fi(G)966 2341 y Fd(k)1000 2334 y Fn(is)h(a)e(strongly)h(univ)o(ersal) 1432 2341 y Ff(2)1466 2334 y Fn(family)h(whic)o(h)f(has)g(the)75 2390 y(collision)19 b(accessibilit)o(y)g(prop)q(ert)o(y)l(.)24 b(The)17 b(n)o(um)o(b)q(er)g(of)f(bits)h(required)h(to)e(sp)q(ecify)h (a)g(mem)o(b)q(er)g(of)f Fi(H)1807 2397 y Fd(k)1844 2390 y Fn(is)75 2447 y(the)f(n)o(um)o(b)q(er)h(needed)g(to)f(sp)q(ecify)h(a) f(mem)o(b)q(er)h(of)e Fi(G)976 2454 y Fd(k)997 2447 y Fn(.)20 b(In)c(our)f(example)h(this)g(is)f(2)p Fi(k)q Fn(.)75 2553 y Fo(Lemm)o(a)f(2.2)23 b Fi(U)17 b Fn(=)446 2521 y Fb(S)481 2565 y Fd(k)510 2553 y Fi(H)548 2560 y Fd(k)585 2553 y Fm(is)f(a)h(UO)o(WHF)e(family.)964 2750 y Fn(6)p eop %%Page: 7 8 7 7 bop 75 121 a Fo(pro)q(of)p Fn(:)31 b(W)l(e)20 b(will)j(sho)o(w)c (that)h(if)h Fi(U)26 b Fn(is)21 b(not)f(a)g(UO)o(WHF)g(family)h(then)g (w)o(e)g(ha)o(v)o(e)f(an)g(algorithm)h(to)75 177 y(in)o(v)o(ert)g(a)f (randomly)h(c)o(hosen)f Fi(f)26 b Fn(on)20 b(a)h(random)f(input,)i (i.e.)37 b(giv)o(en)21 b(a)f(randomly)h(c)o(hosen)f Fi(f)5 b Fn(\()p Fi(w)q Fn(\))20 b(w)o(e)75 234 y(apply)f(a)e(randomized)i (reduction)g(from)e(a)h(collision)i(adv)o(ersary)d(to)g(an)h(in)o(v)o (ersion)h(adv)o(ersary)e(whic)o(h)75 290 y(will)g(succeed)f(in)g (\014nding)h Fi(w)f Fn(with)f(non-negligible)k(probabilit)o(y)l(.)146 346 y(Supp)q(ose)d(that)f Fi(A)g Fn(is)h(an)g(algorithm)f(that)g(on)h (a)f(length)h Fi(k)h Fn(pro)q(duces)f(an)f(initial)j Fi(x)13 b Fh(2)29 b(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)1767 330 y Fd(k)1802 346 y Fn(and)75 403 y(when)19 b(giv)o(en)h Fi(h)e Fh(2)h Fi(H)451 410 y Fd(k)491 403 y Fi(P)6 b(r)q(ob)i Fn([)o Fi(A)p Fn(\()p Fi(x;)g(h)p Fn(\))k(=)h Fi(y)f Fh(^)e Fi(h)p Fn(\()p Fi(x)p Fn(\))i(=)h Fi(h)p Fn(\()p Fi(y)r Fn(\))d Fh(^)g Fi(y)15 b Fh(6)p Fn(=)e Fi(x)p Fn(])18 b Fh(\025)h Fi(\017)g Fn(when)g(the)g(probabilit)o(y)h(is)75 459 y(o)o(v)o(er)d(all)i Fi(h)e Fh(2)h Fi(H)370 466 y Fd(k)409 459 y Fn(and)g Fi(A)p Fn('s)f(random)h(c)o(hoices.)29 b(W)l(e)18 b(can)g(de\014ne)h(an)f(algorithm)g Fi(A)1542 443 y Fq(0)1571 459 y Fn(so)g(that)f(giv)o(en)h(a)75 516 y(random)d Fi(z)g Fn(=)e Fi(f)5 b Fn(\()p Fi(w)q Fn(\))14 b(tries)h(to)g(\014nd)h Fi(w)q Fn(:)131 605 y(1.)22 b(run)15 b Fi(A)g Fn(to)g(pro)q(duce)h Fi(x)131 697 y Fn(2.)22 b(c)o(ho)q(ose)15 b(a)g(random)g Fi(g)e Fh(2)g Fi(G)i Fn(suc)o(h)h(that)e Fi(z)k Fn(and)d Fi(f)5 b Fn(\()p Fi(x)p Fn(\))15 b(collide,)i(i.e.,)d Fi(g)r Fn(\()p Fi(f)5 b Fn(\()p Fi(x)p Fn(\)\))11 b(=)i Fi(g)r Fn(\()p Fi(z)r Fn(\).)131 789 y(3.)22 b(run)15 b(A)g(on)g(input)i Fi(h)12 b Fn(=)h Fi(g)f Fh(\016)e Fi(f)20 b Fn(and)15 b Fi(x)p Fn(,)g(let)h(the)f(output)g(b)q(e)h Fi(y)r Fn(.)146 877 y(Step)h(2)g(is)h(easy)g(to)e(p)q(erform)i(\(b)o(y)f(c)o(ho)q (osing)g(a)h(random)f(elemen)o(t)h(to)e(whic)o(h)j Fi(g)f Fn(maps)g Fi(f)5 b Fn(\()p Fi(x)p Fn(\)\);)17 b(the)75 934 y(construction)d(giv)o(es)h(a)e(2-1)h(function)h(and)f(exactly)h (one)f(elemen)o(t)h(collides)h(with)f Fi(f)5 b Fn(\()p Fi(x)p Fn(\).)19 b(Hence,)14 b(if)h(step)75 990 y(3)g(is)h(successful,) g(i.e.)k Fi(h)p Fn(\()p Fi(x)p Fn(\))12 b(=)h Fi(h)p Fn(\()p Fi(y)r Fn(\))i(but)g Fi(y)g Fh(6)p Fn(=)e Fi(x)p Fn(,)h(then)i Fi(f)5 b Fn(\()p Fi(y)r Fn(\))12 b(=)h Fi(z)k Fn(and)f Fi(y)e Fn(=)f Fi(w)q Fn(.)75 1047 y(Claim:)27 b(if)18 b Fi(w)h Fn(w)o(as)f(c)o(hosen)g(at)g(random,)g(then)h(the)f (ab)q(o)o(v)o(e)g(pro)q(cedure)i(c)o(ho)q(oses)e Fi(h)g Fn(at)g(random)g(from)75 1103 y Fi(H)113 1110 y Fd(k)134 1103 y Fn(.)75 1160 y(Pro)q(of:)k(W)l(e)17 b(can)g(de\014ne)h(a)e (partition)h(of)f Fi(H)21 b Fn(according)c(to)f(whic)o(h)h(elemen)o(t)h (collides)h(with)e Fi(f)5 b Fn(\()p Fi(x)p Fn(\).)24 b(All)75 1216 y(parts)14 b(are)g(of)g(equal)h(size)g(\(b)o(y)f(the)g (prop)q(ert)o(y)g(of)g(strongly)g(univ)o(ersal)1265 1223 y Ff(2)1300 1216 y Fn(hash)h(functions\).)20 b(Since)c Fi(w)f Fn(w)o(as)75 1273 y(c)o(hosen)k(at)f(random)h(and)f Fi(f)24 b Fn(is)c(a)e(p)q(erm)o(utation,)h(a)g(random)f(part)g(w)o(as)g (c)o(hosen)h(uniformly)l(.)32 b(Step)19 b(2)75 1329 y(c)o(ho)q(oses)d (with)h(equal)g(probabilit)o(y)g(an)g Fi(h)f Fn(from)f(that)h(part.)23 b(Hence,)17 b(the)f(whole)h(pro)q(cedure)g(de\014nes)g(a)75 1386 y(random)e(c)o(hoice)h(of)f Fi(h)p Fn(.)146 1442 y(Since)e Fi(h)g Fn(is)g(c)o(hosen)g(uniformly)g(at)f(random,)g(step)g (3)h(of)f(the)g(algorithm)g(succeeds)i(with)f(probabilit)o(y)75 1499 y(at)i(least)g Fi(\017)p Fn(,)g(b)o(y)g(assumption.)20 b(Hence,)c(the)f(in)o(v)o(ersion)h(succeeds)h(with)e(probabilit)o(y)i (at)d(least)i Fi(\017)p Fn(.)p Fa(2)146 1555 y Fn(This)j(lemma)h(in)g (conjunction)g(with)g(theorem)f(1)g(and)g(the)h(fact)f(that)f(one-w)o (a)o(y)h(functions)h(o)o(v)o(er)75 1611 y(strings)15 b(of)g(p)q(olynomially)i(related)f(sizes)g(are)f(sim)o(ultaneously)h (hard)g(yield)h(the)e(follo)o(wing:)75 1700 y Fo(Theorem)g(2)23 b Fm(If)d(one-way)g(p)n(ermutations)h(exist,)g(then)f(for)h(any)f(two)h (incr)n(e)n(asing)d(se)n(quenc)n(es)g Fh(f)p Fi(n)1819 1707 y Ff(1)1837 1712 y Fe(i)1852 1700 y Fh(g)75 1757 y Fm(and)g Fh(f)p Fi(n)215 1764 y Ff(0)233 1769 y Fe(i)248 1757 y Fh(g)f Fm(that)i(ar)n(e)e(p)n(olynomial)r(ly)h(r)n(elate)n(d)f (ther)n(e)h(exists)f(a)h(family)f(of)h(UO)o(WHF)f Fi(U)k Fn(=)1647 1725 y Fb(S)1682 1768 y Fd(k)1711 1757 y Fi(H)1749 1764 y Fd(k)1788 1757 y Fm(such)75 1813 y(that)c Fi(h)c Fn(:)28 b Fh(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)361 1795 y Fd(n)382 1800 y Fc(1)397 1808 y Fe(k)432 1813 y Fh(7!)29 b(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)619 1795 y Fd(n)640 1800 y Fc(0)655 1808 y Fe(k)693 1813 y Fm(for)17 b Fi(h)c Fh(2)g Fi(H)886 1820 y Fd(k)907 1813 y Fm(.)146 1902 y Fn(The)20 b(n)o(um)o(b)q(er)g(of)g(bits)h(required)g(to)e(sp)q(ecify) j Fi(h)f Fh(2)g Fi(H)1100 1909 y Fd(k)1141 1902 y Fn(using)g(our)f (example)h(is)1585 1870 y Fb(P)1628 1873 y Fd(n)1649 1878 y Fc(1)1664 1887 y Fe(k)1628 1915 y Fd(i)p Ff(=)p Fd(n)1688 1920 y Fc(0)1703 1929 y Fe(k)1726 1915 y Ff(+1)1780 1902 y Fn(2)p Fi(i)g Fn(=)75 1967 y Fi(n)102 1974 y Ff(1)120 1980 y Fe(k)141 1967 y Fn(\()p Fi(n)186 1974 y Ff(1)204 1980 y Fe(k)235 1967 y Fh(\000)10 b Fn(1\))g Fh(\000)g Fi(n)403 1974 y Ff(0)421 1980 y Fe(k)442 1967 y Fn(\()p Fi(n)487 1974 y Ff(0)505 1980 y Fe(k)536 1967 y Fh(\000)h Fn(1\).)146 2023 y(Supp)q(ose)i(w)o(e)f(only)g(ha)o(v)o(e)g(a)g(1-1)g (one-w)o(a)o(y)f(function,)j(i.e.)19 b(unlik)o(e)14 b(a)e(one-w)o(a)o (y)f(p)q(erm)o(utation)h(it)h(is)f(not)75 2080 y(necessarily)19 b(length)e(preserving.)27 b(It)17 b(can)g(b)q(e)h(sho)o(wn)f(that)f (the)i(construction)f(w)o(e)g(ga)o(v)o(e)f(for)h(one-w)o(a)o(y)75 2136 y(p)q(erm)o(utation)h(still)h(w)o(orks.)27 b(W)l(e)18 b(only)g(ha)o(v)o(e)f(to)g(use)i(strongly)e(univ)o(ersal)i(functions)f (o)o(v)o(er)f(the)h(range)75 2193 y(and)d(de\014ne)i(the)e(c)o(hopping) h(to)f(b)q(e)h(all)g(but)f(the)g(last)g Fi(k)d Fh(\000)e Fn(1)15 b(bits.)75 2313 y Fg(2.3)74 b(E\016cien)n(t)18 b(and)h(Succinct)f(UO)n(WHF)75 2399 y Fn(Supp)q(ose)g(w)o(e)f(w)o(an)o (t)f(to)g(ha)o(v)o(e)h(public)i(\014ngerprin)o(t,)f(i.e.)26 b(w)o(e)17 b(ha)o(v)o(e)g(large)g(\014les,)h(stored)f(in)h(an)f (insecure)75 2456 y(area,)g(that)g(w)o(e)g(wish)h(to)f(hash)g(do)o(wn)h (to)e(a)i(compact)f(size)h(whic)o(h)g(\014ts)f(in)i(the)e(secure)h (area.)26 b(A)18 b(hash)75 2512 y(function)j(whose)g(description)h(is)f (as)f(long)h(as)f(the)h(\014le)g(w)o(ould)g(not)g(help)g(m)o(uc)o(h;)i (storing)e(it)f(in)i(the)75 2569 y(secure)f(area)f(w)o(ould)h(require)g (as)f(m)o(uc)o(h)h(space)f(as)g(storing)h(the)f(\014le)i(itself.)36 b(Hence)22 b(w)o(e)e(dev)o(elop)h(in)75 2625 y(this)15 b(section)h(constructions)f(for)f(UO)o(WHF)h(families)h(whic)o(h)g(ha)o (v)o(e)e(a)h(more)f(succinct)i(represen)o(tation.)964 2750 y(7)p eop %%Page: 8 9 8 8 bop 75 121 a Fn(F)l(urthermore,)12 b(these)g(functions)h(can)f(b)q (e)h(computed)f(more)g(e\016cien)o(tly)h(then)f(the)g(ones)h(of)e(the)h (previous)75 177 y(section.)146 234 y(The)f(\014rst)h(observ)m(ation)g (is)g(that)f(at)g(eac)o(h)g(stage)g(w)o(e)g(can)h(compress)g(more)f (than)g(one)h(bit.)19 b(If,)12 b(instead)75 290 y(of)18 b(using)h(a)e(2-1)h(strongly)g(univ)o(ersal)h(hash)f(function)h(w)o(e)f (used)h(in)g(the)f(previous)h(section,)g(w)o(e)f(use)g(a)75 346 y Fi(t)p Fn(-1)e(strongly)g(univ)o(ersal)h(hashing,)f(then)g(the)g (probabilit)o(y)h(that)e(step)h(3)g(of)f(the)h(algorithm)g(suggested)75 403 y(in)i(the)g(pro)q(of)f(of)g(lemma)g(2)g(pro)q(duces)i(the)e (pre-image)h(w)o(e)f(w)o(an)o(t)f(will)j(b)q(e)f Fi(\017=t)p Fn(.)27 b(Hence,)19 b(as)e(long)h(as)f Fi(t)75 459 y Fn(is)i(p)q(olynomial)h(in)f(the)f(length,)h(w)o(e)f(ha)o(v)o(e)g(a)g (p)q(olynomial)i(algorithm)e(to)g(break)g Fi(f)5 b Fn(.)29 b(If)18 b(w)o(e)g(compress)75 516 y(a)h(logarithmic)h(n)o(um)o(b)q(er)g (of)f(bits,)h(then)g Fi(t)g Fn(is)f(p)q(olynomial.)34 b(The)20 b(total)f(n)o(um)o(b)q(er)g(of)g(bits)h(to)f(sp)q(ecify)75 572 y(a)f(compression)h(from)f Fi(n)513 579 y Ff(1)551 572 y Fn(to)g Fi(n)637 579 y Ff(2)676 572 y Fn(is)h(therefore)f Fi(n)946 579 y Ff(1)966 556 y(2)986 572 y Fi(=)8 b Fn(log)f Fi(n)1109 579 y Ff(1)1129 572 y Fn(.)30 b(There)19 b(is)g(a)f(similar)i (reduction)g(in)f(the)75 629 y(n)o(um)o(b)q(er)c(of)f(stages.)19 b(\(F)l(urthermore,)14 b(if)h(w)o(e)g(ha)o(v)o(e)f(a)g(1-1)h(one-w)o(a) o(y)f(function)h(whose)g(in)o(v)o(ersion)h(is)f(hard)75 685 y(for)h(algorithms)h(that)f(run)h(in)h(time)f Fi(O)q Fn(\(2)795 669 y Fd(\016)q(k)833 685 y Fn(\),)f(then)i(w)o(e)e(can)h (compress)g(as)g(man)o(y)f(as)g Fi(\016)r(k)i Fn(bits)g(at)e(eac)o(h)75 742 y(stage.\))146 798 y(A)e(m)o(uc)o(h)h(greater)f(sa)o(ving)g(can)h (b)q(e)h(ac)o(hiev)o(ed)f(b)o(y)g(emplo)o(ying)h(a)e(blo)q(c)o(k)h (hashing)h(tec)o(hnique)g(similar)75 855 y(to)21 b(the)g(one)h(in)g ([34)o(].)38 b(Let)22 b Fi(m)f Fn(b)q(e)h(large)g(enough)f(so)g(that)g (in)o(v)o(erting)h Fi(f)27 b Fn(on)21 b Fi(m)g Fn(bits)h(is)g (infeasible.)75 911 y(Divide)d(the)e(input)h(in)o(to)f(blo)q(c)o(ks)h (of)f(size)h(2)p Fi(m)p Fn(.)25 b(Let)17 b Fi(H)k Fn(b)q(e)d(a)e(UO)o (WHF)h(family)h(whose)f(mem)o(b)q(ers)g(are)75 967 y Fh(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)188 951 y Ff(2)p Fd(m)256 967 y Fh(7!)39 b(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)453 951 y Fd(m)484 967 y Fn(.)31 b(Let)20 b Fi(H)656 951 y Fq(0)686 967 y Fn(b)q(e)f(the)h(family)f(y)o(ou)g(get)g(b)o(y)g (applying)h(the)f(same)g(hash)g(function)75 1024 y(that)e(compresses)g (from)g(2)p Fi(m)g Fn(to)g Fi(m)h Fn(bits)g(on)f(ev)o(ery)h(blo)q(c)o (k)g(of)f(the)h(input.)28 b(The)18 b(mem)o(b)q(ers)f(of)h Fi(H)1786 1007 y Fq(0)1814 1024 y Fn(are)75 1080 y(functions)35 b Fh(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)403 1064 y Fd(n)424 1069 y Fc(1)457 1080 y Fh(7!)33 b(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)648 1064 y Fd(n)669 1069 y Fc(1)685 1064 y Fd(=)p Ff(2)739 1080 y Fn(.)25 b(Breaking)17 b(it)g(requires)h (breaking)f(the)34 b Fh(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)1588 1064 y Ff(2)p Fd(m)1653 1080 y Fh(7!)33 b(f)p Fn(0)p Fi(;)8 b Fn(1)p Fh(g)1844 1064 y Fd(m)75 1137 y Fn(function)18 b(on)g(one)g(of)f(the)g(blo)q(c)o(ks.)28 b(Hence,)19 b(when)f(the)f(n)o(um)o(b)q(er)h(of)f(blo)q(c)o(ks)i(is)f(p)q (olynomial)h(in)f Fi(m)g Fn(\(as)75 1193 y(w)o(e)e(assume)f(here\),)h (breaking)g Fi(H)658 1177 y Fq(0)685 1193 y Fn(means)g(that)f(at)g (least)h(one)g(of)g(the)f(blo)q(c)o(ks)i(has)f(1)p Fi(=pol)q(y)r Fn(\()p Fi(m)p Fn(\))d(c)o(hance)75 1250 y(of)h(b)q(eing)h(in)o(v)o (erted)g(and)f(this)h(can)f(b)q(e)h(used)g(as)f(an)g(algorithm)g(for)g (breaking)h Fi(H)t Fn(.)k(The)14 b(n)o(um)o(b)q(er)h(of)f(bits)75 1306 y(needed)i(to)d(sp)q(ecify)j(a)e(mem)o(b)q(er)g(in)h Fi(H)734 1290 y Fq(0)760 1306 y Fn(is)g(the)f(same)g(n)o(um)o(b)q(er)h (needed)g(to)f(sp)q(ecify)i(one)e(in)h Fi(H)t Fn(,)f(i.e.,)g Fi(m)1843 1290 y Ff(2)1862 1306 y Fn(.)75 1363 y(T)l(o)g(further)f (hash)h(the)g(\014le,)h(w)o(e)f(will)h(use)f(a)g(new)g(UO)o(WHF)f (family)i(that)e(again)h(halv)o(es)g(the)g(n)o(um)o(b)q(er)g(of)75 1419 y(bits.)20 b(T)l(o)14 b(hash)g(from)g Fi(n)486 1426 y Ff(1)520 1419 y Fn(bits)g(to)g Fi(n)689 1426 y Ff(0)723 1419 y Fn(bits)h(w)o(e)f(will)i(con)o(tin)o(ue)e(inductiv)o(ely)j(and)d (will)i(need)f(to)f(comp)q(ose)75 1476 y Fi(l)q(og)r Fn(\()p Fi(n)181 1483 y Ff(1)212 1476 y Fh(\000)f Fi(n)287 1483 y Ff(0)307 1476 y Fn(\))18 b(suc)o(h)i(functions.)31 b(By)19 b(the)g(comp)q(osition)h(theorem)e(this)i(is)f(still)h(a)f(UO)o (WHF)f(family)l(.)75 1532 y(Th)o(us)g(to)g(sp)q(ecify)i(a)e(function)h (that)e(compresses)i(from)e Fi(n)1103 1539 y Ff(1)1142 1532 y Fn(bits)h(to)g Fi(n)1319 1539 y Ff(0)1357 1532 y Fn(bits)h(requires)g Fi(O)q Fn(\()p Fi(m)1717 1516 y Ff(2)1744 1532 y Fn(log)8 b Fi(n)1837 1539 y Ff(1)1857 1532 y Fn(\))75 1588 y(bits.)29 b(An)18 b(additional)h(adv)m(an)o(tage) f(is)g(that)f(the)h(one-w)o(a)o(y)g(p)q(erm)o(utation)g(\(1-1)f (functions\))h(has)g(to)f(b)q(e)75 1645 y(computed)f(only)f(on)g (inputs)i(of)d(size)i Fi(m)g Fn(and)f(the)g(time)h(complexit)o(y)g(is)g (essen)o(tially)g(linear)h(in)f Fi(n)1751 1652 y Ff(1)1771 1645 y Fn(.)75 1787 y Fj(3)92 b(One-w)n(a)n(y)23 b(based)g(Signature)g (Sc)n(heme)75 1888 y Fn(In)12 b(this)g(section)h(w)o(e)e(giv)o(e)h(our) g(de\014nition)h(of)e(a)h(signature)g(sc)o(heme)g(\(based)f(on)h([15)o (,)f(1]\))g(and)h(its)g(securit)o(y)l(.)75 2009 y Fg(3.1)56 b(De\014nition)17 b(of)i(a)g(Signature)f(Sc)n(heme)75 2095 y Fn(A)d(signature)h(sc)o(heme)f(includes)j(the)d(follo)o(wing)h (comp)q(onen)o(ts:)131 2182 y(1.)22 b(A)e Fm(se)n(curity)i(p)n(ar)n (ameter)f Fi(k)h Fn(whic)o(h)f(determines)h(the)f(size)g(of)g(k)o(eys,) g(messages)g(and)f(other)h(re-)189 2238 y(sources;)14 b(all)j(sizes)f(and)f(algorithms)g(are)g(p)q(olynomial)i(in)f Fi(k)q Fn(.)131 2330 y(2.)22 b(A)15 b Fm(message)g(sp)n(ac)n(e)g Fi(M)5 b(S)s Fn(;)14 b(w)o(e)h(allo)o(w)g(all)i(messages)d(of)h(a)g (giv)o(en)h(size)g(p)q(olynomial)h(in)f Fi(k)131 2421 y Fn(3.)22 b(A)d Fm(key)h(c)n(omp)n(onent)e Fn(whic)o(h)i(includes)i(a) c Fm(key)i(sp)n(ac)n(e)f Fi(K)s(S)s Fn(\()p Fi(k)q Fn(\),)f(a)h(family) h(from)e(whic)o(h)i(k)o(eys)f(are)189 2477 y(b)q(eing)d(dra)o(wn)f(and) g(a)g Fm(gener)n(ation)h(algorithm)f Fi(K)s(AL)g Fn(whic)o(h)h(c)o(ho)q (oses)g(random)e(k)o(eys.)131 2569 y(4.)22 b(A)13 b Fm(signatur)n(e)g (b)n(ound)g Fi(S)s(B)r Fn(,)h(a)e(p)q(olynomial)j(represen)o(ting)f(a)e (b)q(ound)i(on)f(the)h(n)o(um)o(b)q(er)f(of)f(messages)189 2625 y(signed;)j(an)o(y)g(p)q(olynomial)i(should)f(w)o(ork.)964 2750 y(8)p eop %%Page: 9 10 9 9 bop 131 121 a Fn(5.)22 b(A)17 b Fm(system)h(state)f Fi(s)h Fn(whic)o(h)g(represen)o(ts)f(the)h(state)e(of)h(the)h(system;)f (there)h(are)f(an)g(initial)j(state)189 177 y(and)15 b(execution)h(states.)131 271 y(6.)22 b(A)10 b Fm(signing)h(algorithm)g Fi(S)s(AL)f Fn(whic)o(h)h(is)g(giv)o(en)g(a)g(message,)f(a)h(system)f (state,)g(and)h(a)f(k)o(ey)l(,)h(generates)189 327 y(a)k(signature)g (and)g(up)q(dates)h(the)f(system's)g(state.)131 421 y(7.)22 b(A)17 b Fm(veri\014c)n(ation)h(algorithm)h Fi(V)9 b(AL)18 b Fn(whic)o(h)h(is)f(giv)o(en)g(a)f(message,)h(a)g(signature)f(and)h(a) g(system's)189 478 y(state,)c(c)o(hec)o(ks)h(the)g(v)m(alidit)o(y)i(of) e(the)g(signature.)146 571 y(A)21 b(signature)g(system)g(is)g(a)g (distributed)i(system)d(in)i(whic)o(h)g(eac)o(h)f(user)g(is)h(a)f(p)q (olynomial-time)75 628 y(mac)o(hine)16 b(whic)o(h)g(initiates)h(its)e (instance)h(of)f(the)g(signature)g(sc)o(heme.)75 750 y Fg(3.2)56 b(Securit)n(y)17 b(of)i(a)g(Signature)f(Sc)n(heme)75 835 y Fn(The)k(most)f(general)h(attac)o(k)f(on)g(a)h(signature)g(sc)o (heme)g(\([15)n(]\))f(has)h(t)o(w)o(o)e(phases.)40 b(First,)23 b(it)f(allo)o(ws)75 892 y(a)e(p)q(olynomial-time)i(adv)o(ersary)d Fi(F)26 b Fn(\(a)19 b Fm(for)n(ger)p Fn(\))h(to)f(use)h(the)g (signature)g(algorithm)g(in)h(an)f(adaptiv)o(e)75 948 y(fashion,)c(getting)f(signatures)h(to)f(p)q(olynomially)j(man)o(y)e (plain)o(texts)g(of)g(its)f(c)o(hoice.)23 b(Next,)15 b(the)h(attac)o(k)75 1005 y(has)c(an)g(existen)o(tial)h(nature,)f (i.e.,)g(the)g(forger)f(itself)i(has)f(to)f(come)h(up)g(with)g(a)g(v)m (alid)i(signature)e(of)f(a)h(new)75 1061 y(message)i(of)f(its)h(c)o (hoice,)h(in)g(whic)o(h)g(case)f(w)o(e)f(sa)o(y)h(that)f(it)h(w)o(as)f (successful.)21 b(A)14 b(sc)o(heme)g(is)h Fm(p-for)n(ge)n(able)e Fn(if)75 1118 y(for)i(a)g(p)q(olynomial)i Fi(p)e Fn(there)h(is)g(a)f (forger)f Fi(F)22 b Fn(whic)o(h)17 b(for)d(in\014nitely)k(man)o(y)d Fi(k)q Fn('s,)g(succeeds)h(in)h(the)e(attac)o(k)75 1174 y(with)f(probabilit)o(y)h(larger)e(than)h(1)p Fi(=p)p Fn(\()p Fi(k)q Fn(\),)e(where)i(the)g(probabilit)o(y)h(is)f(tak)o(en)f (o)o(v)o(er)g(the)h(random)f(c)o(hoices)75 1231 y(of)j(k)o(eys)h(b)o(y) g Fi(K)s(AL)p Fn(,)g(the)g(c)o(hoices)h(of)e(the)h(signatures)g(b)o(y)g Fi(S)s(AL)p Fn(,)f(and)h(the)g(coin)h(\015ips)g(of)f Fi(F)23 b Fn(itself.)j(W)l(e)75 1287 y(sa)o(y)15 b(that)f(a)h(system)g (is)g Fm(se)n(cur)n(e)g Fn(if)g(it)h(is)g(not)e Fi(p)p Fn(-forgeable)i(for)e(an)o(y)h(p)q(olynomial)i Fi(p)p Fn(.)75 1430 y Fj(4)69 b(The)23 b(Signature)f(Sc)n(heme)75 1532 y Fn(Here)13 b(w)o(e)f(presen)o(t)h(our)g(one-w)o(a)o(y)f(based)h (sc)o(heme:)19 b(its)13 b(comp)q(onen)o(ts,)g(algorithms,)g(and)g (securit)o(y)g(pro)q(of.)75 1654 y Fg(4.1)56 b(Bac)n(kground:)24 b(T)-5 b(agging)19 b(System-)e(\\One-Time)f(Signature")75 1739 y Fn(The)e(starting)f(p)q(oin)o(t)h(of)f(our)g(system)g(is)h(the)g (Di\016e-Lamp)q(ort)g Fm(tagging)g(system)f Fn([21)o(];)g(b)q(oth)h (the)f(system)75 1796 y(of)j(Bellare)i(and)f(Micali)h([2)o(])e(and)h (the)g(practical)g(system)f(of)g(Merkle)h([23)o(])f(whic)o(h)i(motiv)m (ated)f(us)f(w)o(ere)75 1852 y(based)h(on)f(it.)23 b(The)16 b(suggestion)g(of)g([21)o(])g(is)h(to)e(mak)o(e)h(public)i(a)e(one-w)o (a)o(y)g(function)h Fi(f)k Fn(and)c Fm(a)g(window)p Fn(,)75 1909 y(whic)o(h)k(is)f(an)g(ordered)h(pair)f(of)g(v)m(alues)h Fi(<)g(f)5 b Fn(\()p Fi(x)920 1916 y Ff(0)940 1909 y Fn(\))p Fi(;)j(f)d Fn(\()p Fi(x)1050 1916 y Ff(1)1068 1909 y Fn(\))20 b Fi(>)p Fn(,)i(for)d(randomly)h(c)o(hosen)h Fi(x)1635 1916 y Ff(0)1654 1909 y Fn(,)g Fi(x)1714 1916 y Ff(1)1754 1909 y Fn(in)g(the)75 1965 y(function)c(domain.)25 b(The)16 b(user,)h(then,)g(is)g(committed)g(to)f(the)g(windo)o(w)h(and) g(later)f(on)h(when)g(it)f(sends)75 2022 y(a)g(bit)g Fi(b)p Fn(,)g(it)g(is)h(done)g(b)o(y)f(publishing)i(a)e(tag)g Fi(x)866 2029 y Fd(b)883 2022 y Fn(,)g(an)g(op)q(eration)g(w)o(e)g (call)h Fm(op)n(ening)f(half)h(a)h(window)p Fn(.)23 b(W)l(e)75 2078 y(sa)o(y)15 b(that)f(the)h(other)g(half)h(of)f(the)g(windo)o(w)g (remains)h Fm(unuse)n(d)p Fn(.)146 2134 y(The)g(construction)h(can)g(b) q(e)g(extended)h(to)e(tag)g(a)g(message)g(of)g(length)i Fi(m)e Fn(bits,)h(b)o(y)g(initially)i(pub-)75 2191 y(lishing)d (\(committing\))d(to)g(a)g Fm(r)n(ow)i(of)g(windows)f Fn([)p Fi(<)e(f)5 b Fn(\()p Fi(x)1031 2174 y Fd(i)1031 2203 y Ff(0)1051 2191 y Fn(\))p Fi(;)j(f)d Fn(\()p Fi(x)1161 2174 y Fd(i)1161 2203 y Ff(1)1179 2191 y Fn(\))12 b Fi(>;)c(i)k Fn(=)h(1)p Fi(;)8 b(:)g(:)g(:)d(;)j(m)p Fn(])k(and)i(then)g(op)q(ening) 75 2247 y(the)f(halv)o(es)g(corresp)q(onding)h(to)e(the)h(bits)g(of)g (the)g(message.)18 b(Since)d Fi(f)j Fn(is)13 b(one-w)o(a)o(y)l(,)g (only)g(the)g(committed)75 2304 y(user)20 b(can)h(op)q(en)f(a)g(tag,)g (and)h(no)f(one)g(else)h(can)g(tag)e(a)h(di\013eren)o(t)g(message)g (unless)h(it)g(can)f(in)o(v)o(ert)g(a)75 2360 y(random)15 b(v)m(alue)h(of)e Fi(f)5 b Fn(,)15 b(furthermore,)f(an)o(y)o(one)h(can) g(v)o(erify)g(tags;)f(in)i(this)f(sense)h(the)f(system)f(resem)o(bles) 75 2417 y(a)f(signature)f(sc)o(heme.)20 b(Ho)o(w)o(ev)o(er,)12 b(the)h(dra)o(wbac)o(k)f(is)h(that)f(the)h(size)h(of)e(the)h(initial)i (commitmen)o(t)e(limits)75 2473 y(the)k(n)o(um)o(b)q(er)h(of)e(bits)i (whic)o(h)g(can)f(b)q(e)g(tagged;)g(in)h(this)g(sense)f(it)g(is)h(not)f (a)f(signature)i(sc)o(heme,)f(whic)o(h)75 2530 y(requires)e(that)e (once)i(the)f(initial)j(k)o(ey)d(is)g(placed)i(in)f(the)f(public-k)o (ey)j(directory)d(the)g(system)g(should)h(b)q(e)75 2586 y(activ)o(e)g(\\p)q(olynomially)j(forev)o(er".)964 2750 y(9)p eop %%Page: 10 11 10 10 bop 146 121 a Fn(A)14 b(tagging)f(system)g(pro)o(vides)i(what)e (w)o(e)h(ma)o(y)f(call)i(a)e Fm(one-time)j(signatur)n(e)d Fn(\(analogous)g(to)g(a)h(\014nite)75 177 y(one-time)22 b(pad\),)h(whic)o(h)g(cannot)e(b)q(e)i(extended)f(b)q(ey)o(ond)h(a)e (giv)o(en)h(length.)40 b(Merkle)22 b(ga)o(v)o(e)f(a)g(more)75 234 y(space-e\016cien)o(t)16 b(tagging)f(system)g(based)g(on)g(a)g (tree)g(structure)g([25)o(].)75 355 y Fg(4.2)56 b(An)19 b(Ov)n(erview)75 441 y Fn(Here)13 b(w)o(e)g(presen)o(t)g(the)g (simplest)h(v)o(ersion)g(of)e(our)h(system;)g(in)h(section)f(4.5)f(w)o (e)h(suggest)g(other)f(v)o(ersions.)146 498 y(The)17 b(general)g(strategy)e(of)h(the)h(system)g(is)g(to)f(extend)h(the)g (tagging)f(system,)g(enhancing)j(it)e(with)75 554 y(the)i(capabilit)o (y)h(of)e(\\regenerating)h(ro)o(ws)e(of)i(windo)o(ws".)30 b(The)19 b(system)f(is)h(represen)o(ted)h(as)e(a)g(link)o(ed)75 610 y(list;)f(a)f(system's)f(state)g(is)h(a)g(list)h(consisting)g(of)f (no)q(des.)22 b(Eac)o(h)16 b(no)q(de)h(is)f(asso)q(ciated)h(with)f(a)g (message,)75 667 y(i.e.,)e(it)g(tags)g(that)f(message.)19 b(The)c(no)q(de)f(is)h(also)f(connected)h(to)f(its)g(successor)g(in)h (the)g(list;)g(i.e.,)f(it)g(tags)75 723 y(the)h(successor)h(no)q(de)f (as)g(w)o(ell.)146 780 y(The)h(no)q(de)g Fi(N)387 787 y Fd(i)417 780 y Fn(con)o(tains)g(three)g(data)f(\014elds:)23 b Fi(h)979 787 y Fd(i)1009 780 y Fn(a)15 b(univ)o(ersal)i(one-w)o(a)o (y)f(hash)g(function,)g(and)g(t)o(w)o(o)75 836 y(ro)o(ws)i(of)g(windo)o (ws)h Fi(r)q(m)488 843 y Fd(i)520 836 y Fn(and)g Fi(r)q(s)655 843 y Fd(i)669 836 y Fn(;)h(the)f(\014rst)f(will)i(tag)e(the)h(next)f (message)h Fi(M)1462 843 y Fd(i)p Ff(+1)1540 836 y Fn(while)h(the)e (second)75 893 y(one)i(will)h(tag)d(the)i(successor)f(no)q(de)h(in)g (the)g(list,)h Fi(N)1002 900 y Fd(i)p Ff(+1)1060 893 y Fn(.)33 b(The)20 b(set)f(of)g(one-w)o(a)o(y)f(p)q(erm)o(utations)i (\(1-1)75 949 y(functions\))13 b(used)h(in)g(the)f(tag)f(encryption)i (and)f(in)h(the)f(hashing)h(will)g(b)q(e)g(called)h(the)e(one-w)o(a)o (y)f(function)75 1006 y Fi(f)5 b Fn(.)20 b(It)15 b(is)h(publicly)i(kno) o(wn,)c(or)h(is)h(otherwise)f(pro)q(duced)i(b)o(y)e(eac)o(h)g(user.)75 1127 y Fg(4.3)56 b(The)18 b(System's)e(Algorithms)75 1213 y Fn(Next)h(w)o(e)h(sk)o(etc)o(h)f(the)g(algorithms)h(and)f(the)h (dynamic)g(b)q(eha)o(vior)g(of)f(the)h(system.)26 b(The)18 b(system)f(has)75 1270 y(an)h(initial)j(state)d(\(state)f(0\))h(in)h (whic)o(h)g(a)f(user)h(dep)q(osits)g(an)g(initial)h(\(ro)q(ot\))d(no)q (de)i Fi(N)1578 1277 y Ff(0)1616 1270 y Fn(in)g(the)g(public)75 1326 y(directory)l(.)146 1383 y(In)h(a)f(t)o(ypical)h(situation)g(the)g (system)f(is)h(in)h(state)e Fi(s)1079 1390 y Fd(i)p Fq(\000)p Ff(1)1158 1383 y Fn(where)g(there)h(is)g(a)f(list)i(of)e Fi(i)13 b Fh(\000)g Fn(1)19 b(no)q(des)75 1439 y(and)e(the)g Fm(last-no)n(de)f Fi(N)474 1446 y Fd(i)p Fq(\000)p Ff(1)549 1439 y Fn(is)h(un)o(used.)26 b(The)17 b(connection)g(b)q(et)o(w)o(een)g (no)q(des)h(will)g(b)q(e)g(explained)g(in)g(the)75 1495 y(follo)o(wing)e(sk)o(etc)o(h)f(of)g(the)g(signature)g(and)h(the)f(v)o (eri\014cation)h(algorithms.)146 1552 y Fo(SAL:)g Fn(Eac)o(h)h(message) g(signing)h(c)o(hanges)f(the)g(state)f(of)h(the)g(system,)g(the)g(list) h(gro)o(ws)e(b)o(y)h(a)f(no)q(de)75 1608 y(whic)o(h)21 b(b)q(ecomes)f(the)g(new)g(last-no)q(de.)35 b(A)o(t)19 b(state)g Fi(s)1011 1615 y Fd(i)p Fq(\000)p Ff(1)1091 1608 y Fn(the)h(user)g(sends)g(a)f(message)h Fi(M)1667 1615 y Fd(i)1701 1608 y Fn(and)g(tags)75 1665 y(it)h(using)h(the)e(ro)o (w)g Fi(r)q(m)489 1672 y Fd(i)p Fq(\000)p Ff(1)548 1665 y Fn(.)37 b(F)l(urthermore,)21 b(a)f(new)h(no)q(de)h Fi(N)1176 1672 y Fd(i)1210 1665 y Fn(is)f(generated)g(b)o(y)g (algorithm)f Fi(K)s(AL)p Fn(:)75 1721 y Fi(N)112 1728 y Fd(i)139 1721 y Fn(=)p Fi(<)15 b(h)250 1728 y Fd(i)264 1721 y Fi(;)8 b(r)q(m)347 1728 y Fd(i)360 1721 y Fi(;)g(r)q(s)424 1728 y Fd(i)451 1721 y Fi(>)16 b Fn(where)g(its)g(comp)q(onen)o(ts)g (are)g(c)o(hosen)g(at)f(random:)21 b Fi(h)1440 1728 y Fd(i)1470 1721 y Fn(is)16 b(a)g(random)f(elemen)o(t)75 1778 y(of)f(the)g(UO)o(WHF)g(family)h(based)f(on)h Fi(f)5 b Fn(,)14 b(and)g(the)g(ro)o(ws)g(are)g(encryption)h(b)o(y)f Fi(f)19 b Fn(of)14 b(random)g(tag)f(v)m(alues.)146 1834 y(In)20 b(order)f(to)g(link)i(the)f(new)g(no)q(de)g(in)o(to)g(the)f (list,)j(the)d(user)h(has)g(to)f(tag)f(the)i(new)g(no)q(de)g(b)o(y)g (its)75 1891 y(predecessor.)g(Notice)15 b(that)e(the)h(new)h(no)q(de)f (as)g(a)g(string)g(of)g(random)f(bits)i(is)f(larger)g(than)g(the)h (tagging)75 1947 y(capabilities)j(of)d(the)g(ro)o(w)g Fi(r)q(s)574 1954 y Fd(i)p Fq(\000)p Ff(1)648 1947 y Fn(whic)o(h)h(w)o(as)f(giv)o(en)h(this)g(tagging)e(task!)20 b(Here)c(is)g(where)f(the)h(one-w)o(a)o(y)75 2004 y(hash)j(is)g(needed) i(in)e(a)g(non-trivial)h(w)o(a)o(y)l(.)30 b(The)19 b(algorithm)g (\014rst)f(computes)h(the)g(hash)g(v)m(alue)h(of)f(the)75 2060 y(new)c(no)q(de)h(b)o(y)g(ev)m(aluating)g Fi(n)587 2067 y Fd(i)614 2060 y Fn(=)d Fi(h)688 2067 y Fd(i)p Fq(\000)p Ff(1)747 2060 y Fn(\()p Fi(N)802 2067 y Fd(i)816 2060 y Fn(\),)h(then)i(the)f(smaller)h(string)f Fi(n)1356 2067 y Fd(i)1386 2060 y Fn(is)h(tagged)e(b)o(y)h(op)q(ening)i(the)75 2116 y(corresp)q(onding)f(half-windo)o(ws)g(in)f Fi(r)q(s)735 2123 y Fd(i)p Fq(\000)p Ff(1)795 2116 y Fn(.)k(This)d(de\014nes)g(a)e (signature)h(on)g Fi(M)1421 2123 y Fd(i)1450 2116 y Fn(and)g(a)g(new)g (v)m(alid)i(state)75 2173 y(of)e(the)g(system)g Fi(s)377 2180 y Fd(i)391 2173 y Fn(.)146 2229 y Fo(V)-6 b(AL:)15 b Fn(V)l(eri\014cation)j(of)e(the)g(v)m(alidit)o(y)j(of)d(a)g(message)g (can)g(b)q(e)h(done)g(b)o(y)g(c)o(hec)o(king)g(the)g(tagging)e(of)75 2286 y(the)e(message)g Fi(M)368 2293 y Fd(i)395 2286 y Fn(b)o(y)g Fi(r)q(m)518 2293 y Fd(i)p Fq(\000)p Ff(1)590 2286 y Fn(and)g(testing)g(the)g(v)m(alidit)o(y)i(of)d(the)h(system's)g (state)f(b)o(y)h(c)o(hec)o(king)h(that)e(the)75 2342 y(tagging)j(of)h Fi(n)317 2349 y Fd(j)349 2342 y Fn(=)e Fi(h)424 2349 y Fd(j)r Fq(\000)p Ff(1)488 2342 y Fn(\()p Fi(N)543 2349 y Fd(j)560 2342 y Fn(\))i(is)g(a)f(v)m(alid)j(one,)e (namely)l(,)g(it)g(w)o(as)f(done)i(b)o(y)e(a)h(prop)q(er)g(op)q(ening)h (of)f Fi(r)q(s)1812 2349 y Fd(j)r Fq(\000)p Ff(1)75 2399 y Fn(for)g(all)h Fi(j)g Fn(=)e(1)p Fi(;)8 b(:)g(:)g(:)d(;)j(i)h Fh(\000)j Fn(1.)23 b(This)17 b(is)g(done)f(all)i(the)e(w)o(a)o(y)g(to)f (the)i(ro)q(ot)e(and)i(if)g(all)g(c)o(hec)o(ks)g(are)f(v)m(alid)i(the) 75 2455 y(user)d(accepts)h(the)f(signature.)146 2512 y Fo(Remark:)g Fn(In)f(practice,)g(once)f(old)h(messages)e(and)h (signatures)g(are)g(out)f(of)h(date,)g(a)f(user)i(can)f(k)o(eep)75 2568 y(on-line)j(only)e(the)g(relev)m(an)o(t)h(and)f(previously)i(v)o (eri\014ed)f(su\016x)f(of)f(the)h(list;)h(this)f(sa)o(v)o(es)g(time)g (and)g(space.)75 2625 y(With)j(resp)q(ect)h(to)e(a)h(forger,)f(though,) h(the)g(w)o(orst)f(assumption)h(is)h(that)e(it)i(has)f(access)g(to)f (the)h(en)o(tire)952 2750 y(10)p eop %%Page: 11 12 11 11 bop 75 121 a Fn(history)13 b(at)g(an)o(y)g(time.)19 b(In)14 b(case)g(not)e(all)j(users)e(are)g(follo)o(wing)h(all)g (message)f(transmissions,)g(a)g(user)h(can)75 177 y(ha)o(v)o(e)h(a)g (separate)g(system)f(dedicated)j(to)e(eac)o(h)g(other)g(user,)g(or)g(a) g(practical)h(tree-lik)o(e)g(system)f(can)g(b)q(e)75 234 y(used)h(\(to)e(b)q(e)i(describ)q(ed)h(later\).)75 340 y Fo(Lemm)o(a)d(4.1)23 b Fm(The)15 b(key-gener)n(ation,)f(signing,) g(and)h(veri\014c)n(ation)f(algorithms)h(ar)n(e)g(p)n(olynomial-time.) 75 462 y Fg(4.4)56 b(Securit)n(y)17 b(of)i(the)f(Signature)g(Sc)n(heme) 75 547 y Fn(The)11 b(securit)o(y)h(of)e(our)h(sc)o(heme)h(is)f(based)h (on)f(a)f(randomized)i(reduction)g(from)f(a)f(forgery)h(to)f(an)h(in)o (v)o(ersion)75 604 y(adv)o(ersary)k(of)g(the)h(one-w)o(a)o(y)g (function)g Fi(f)5 b Fn(;)16 b(it)h(translates)e(an)h(existen)o(tial)h (attac)o(k)d(to)i(an)g(attac)o(k)e(whic)o(h)75 660 y(tries)e(to)f(in)o (v)o(ert)g(a)h(random)f(elemen)o(t)h(in)h(the)e(range)h(of)f(the)h (function.)19 b(The)12 b(follo)o(wing)g(lemma)g(describ)q(es)75 717 y(ho)o(w)j(a)g(forger)f(ma)o(y)g(b)q(e)i(successful.)75 811 y Fo(Lemm)o(a)e(4.2)23 b Fm(Assume)17 b(a)i(for)n(ger)f(is)f(suc)n (c)n(essful)f(in)i(its)g(attack)g(after)h Fi(i)c Fn(=)h Fi(pol)q(y)r Fn(\()p Fi(k)q Fn(\))h Fm(signatur)n(e)h(steps,)75 867 y(then)h(either)g(\(1\))f(a)h(half-window)h(unuse)n(d)e(by)h(the)g (signatur)n(e)g(algorithm)g(is)g(op)n(ene)n(d,)g(or)g(\(2\))f(a)h(no)n (de)75 923 y(not)f(gener)n(ate)n(d)g(by)h(the)f(signatur)n(e)g (algorithm)h(\(SAL\))e(is)h(tagge)n(d)g(by)h(a)g(pr)n(e)n(de)n(c)n (essor)e(no)n(de)h(gener)n(ate)n(d)75 980 y(by)e(SAL.)146 1074 y Fn(Giv)o(en)d(a)f(successful)j(forger)d Fi(F)6 b Fn(,)13 b(w)o(e)g(will)h(use)f(the)g(lemma)g(to)g(generate)f(an)h(in) o(v)o(ersion)h(adv)o(ersary)e(to)75 1130 y(the)i(underlying)h(one-w)o (a)o(y)e(function)i Fi(f)5 b Fn(.)20 b(Assume)13 b(w)o(e)h(are)f(giv)o (en)i(a)e(signature)h(sc)o(heme,)g(and)g(assume)f(a)75 1187 y(forger)i(can)g(successfully)i(attac)o(k)e(with)g(a)g (non-negligible)k(success)d(probabilit)o(y)h Fi(\017)c Fn(=)g Fi(\017)p Fn(\()p Fi(k)q Fn(\).)21 b(Using)16 b(the)75 1243 y(lemma)g(ab)q(o)o(v)o(e)g(w)o(e)g(kno)o(w)f(that)h (either)g(case)g(\(1\))f(or)h(\(2\))f(o)q(ccurs)h(with)h(probabilit)o (y)g Fi(\017=)p Fn(2)f(for)f(in\014nitely)75 1300 y(man)o(y)c Fi(k)q Fn('s,)g(\(w)o(e)g(sa)o(y)f(that)h(the)g(more)g(frequen)o(t)h (case)f(dominates\).)18 b(If)12 b(case)f(\(1\))g(dominates)g(then)h(w)o (e)f(can)75 1356 y(in)o(v)o(ert)g(a)g(random)g(tag)f(v)m(alue;)k(the)d (reduction)h(algorithm)g(pla)o(ys)f(the)g(role)h(of)f(SAL)h(but)f (plugs)h(this)g(v)m(alue)75 1412 y(at)h(a)h(random)g(lo)q(cation)h(as)e (half)i(a)f(windo)o(w)g(\(this)g(do)q(es)g(not)g(c)o(hange)g(the)g (probabilit)o(y)i(distribution)f(of)75 1469 y(system)g(states\).)21 b(With)16 b(probabilit)o(y)h(1/2)e(the)h(forger)f(ma)o(y)g(ask)g(to)g (sign)h(a)g(message)f(whic)o(h)i(con)o(tains)75 1525 y(a)e(bit)h(corresp)q(onding)h(to)d(this)i(half)g(a)g(windo)o(w,)f(in)h (whic)o(h)h(case)e(w)o(e)g(fail)i(and)e(stop.)21 b(Otherwise,)16 b(with)75 1582 y(probabilit)o(y)j(in)o(v)o(erse)f(p)q(olynomial)i(in)f (the)f(size)h(of)e(the)h(history)l(,)g(the)g(successful)i(forger)d(in)o (v)o(erts)h(this)75 1638 y(sp)q(eci\014c)d(windo)o(w.)k(If)13 b(case)g(\(2\))f(dominates,)h(the)g(reduction)h(algorithm)f(pla)o(ys)g (the)g(role)g(of)g(SAL)g(again,)75 1695 y(generating)j(random)f(no)q (des,)i(but)f(at)f(a)g(random)h(step)f(it)i(c)o(ho)q(oses)e(a)h (successor)g(no)q(de)g(\014rst)g(and)g(then)75 1751 y(a)h(hash)h (function)g(whic)o(h)h(will)g(collide)h(and,)e(b)o(y)f(theorem)h(2,)f (will)i(in)o(v)o(ert)f(a)f(random)g(giv)o(en)h(elemen)o(t)75 1808 y(in)g(the)g(range)f(of)g(one)h(of)f(the)h(one-w)o(a)o(y)e (functions)j(used)f(in)g(the)g(hashing)g(with)g(probabilit)o(y)h(in)o (v)o(erse)75 1864 y(p)q(olynomial)g(in)g(the)f(size)h(of)e(the)h (history)l(.)28 b(\(This)18 b(construction)g(do)q(es)g(not)g(c)o(hange) g(the)g(probabilit)o(y)75 1921 y(distribution)c(of)e(system)g (states.\))18 b(Th)o(us)12 b(a)h(successful)g(forgery)f(implies)j(a)d (successful)i(in)o(v)o(ersion)f(of)f(the)75 1977 y(underlying)18 b(one-w)o(a)o(y)d(function)h Fi(f)21 b Fn(with)16 b(probabilit)o(y)h(p) q(olynomially)h(related)e(to)f Fi(\017)p Fn(,)h(a)f(con)o(tradiction.) 75 2033 y(W)l(e)g(summarize)h(the)f(ab)q(o)o(v)o(e:)75 2140 y Fo(Theorem)g(3)23 b Fm(If)17 b(1-1)i(one-way)g(functions)e (exist,)h(then)g(the)g(one-way)h(b)n(ase)n(d)e(signatur)n(e)h(scheme)g (de-)75 2196 y(scrib)n(e)n(d)d(ab)n(ove)h(is)g(se)n(cur)n(e.)75 2318 y Fg(4.5)56 b(E\016ciency)75 2404 y Fn(Suggestions)16 b(for)f(impro)o(ving)h(the)g(e\016ciency)h(from)d([15)o(,)i(9)o(,)f (24,)g(1])g(are)g(applicable)j(to)d(our)g(sc)o(heme)h(as)75 2460 y(w)o(ell.)21 b(Instead)15 b(of)f(a)h(link)o(ed)h(list)g(w)o(e)e (can)h(arrange)f(the)h(one-time)g(signatures)g(in)g(a)g Fi(d)p Fn(-w)o(a)o(y)e(tree,)i(where)75 2517 y(the)f(paren)o(t)g(tags)g (all)h(its)f Fi(d)g Fn(c)o(hildren.)22 b(If)14 b Fi(k)i Fn(is)f(the)f(v)m(alue)i(of)e(the)g(securit)o(y)h(parameter)e(and)i Fi(t)f Fn(messages)75 2573 y(ha)o(v)o(e)h(b)q(een)h(signed)g(so)f(far,) f(then)i(the)f(length)h(of)f(a)g(signature)g(in)h(suc)o(h)g(a)e(system) h(is)h Fi(O)q Fn(\()p Fi(k)1641 2557 y Ff(2)1668 2573 y Fn(log)1727 2584 y Fd(d)1754 2573 y Fi(t)p Fn(\).)952 2750 y(11)p eop %%Page: 12 13 12 12 bop 146 121 a Fn(Using)17 b(pseudo-random)h(functions)g(of)f([10) o(])g(w)o(e)g(can)g(mak)o(e)g(our)g(sc)o(heme)h(\\memoryless",)f(in)h (the)75 177 y(sense)j(that)e(the)h(signer)g(need)h(not)f(remem)o(b)q (er)g(the)g(messages)g(that)f(he)i(has)f(signed)h(or)e(ev)o(en)h(their) 75 234 y(n)o(um)o(b)q(er.)g(In)13 b(particular)h(man)o(y)f (\(authorized\))g(signers)g(can)h(exist)f(sim)o(ultaneously)i(without)e (the)g(need)75 290 y(to)g(co)q(ordinate)h(their)h(signatures.)k(This)c (is)f(done)g(b)o(y)g(using)g(the)g(tec)o(hniques)h(of)f(Levin)h(and)f (Goldreic)o(h)75 346 y([9)o(])h(whic)o(h)h(w)o(ere)f(also)g(used)h(b)o (y)f([15)o(,)g(1].)75 490 y Fj(5)92 b(Conclusions)75 591 y Fn(The)21 b(signi\014cance)i(of)d(the)h(this)h(w)o(ork)d(is)j(in) f(iden)o(tifying)i(a)e(\\go)q(o)q(d")f(de\014nition)i(for)f(one-w)o(a)o (y)f(hash)75 648 y(functions.)33 b(W)l(e)20 b(ha)o(v)o(e)f(seen)h(that) f(the)g(de\014nition)j(is)e(strong)e(enough)i(to)f(implemen)o(t)i (construction)75 704 y(suc)o(h)16 b(a)g(public)i(\014ngerprin)o(ts)f (and)f(digital)h(signature.)23 b(On)16 b(the)h(other)e(hand)i(w)o(e)f (ha)o(v)o(e)f(seen)i(ho)o(w)e(an)o(y)75 761 y(1-1)g(one-w)o(a)o(y)h (function)g(can)g(supp)q(ort)g(the)g(construction)h(of)e(suc)o(h)h (families.)24 b(V)l(ery)16 b(recen)o(tly)h(Romp)q(el)75 817 y([32)o(])j(has)f(extended)i(our)f(w)o(ork)f(and)h(sho)o(w)o(ed)g (ho)o(w)f(to)h(construct)f(a)h(UO)o(WHF)g(from)f(an)o(y)h(one-w)o(a)o (y)75 873 y(function.)146 930 y(It)d(w)o(ould)h(b)q(e)h(in)o(teresting) f(to)f(see)h(more)f(e\016cien)o(t)i(constructions,)f(p)q(erhaps)g (based)g(on)g(more)f(re-)75 986 y(strictiv)o(e)h(assumptions.)27 b(One)18 b(suc)o(h)g(construction)g(w)o(as)f(giv)o(en)h(b)o(y)f (Impagliazzo)i(and)e(Naor)g(in)i([18)o(].)75 1043 y(based)d(of)e(on)h (the)h(hardness)f(of)g(random)g(subset)g(sum)g(problems)h(of)f(certain) h(dimensions.)75 1186 y Fj(6)69 b(Ac)n(kno)n(wledgme)o(n)n(ts)75 1287 y Fn(W)l(e)14 b(w)o(ould)f(lik)o(e)i(to)e(thank)g(Man)o(uel)h (Blum,)g(Benn)o(y)g(Chor,)f(Cyn)o(thia)h(Dw)o(ork,)e(Amos)h(Fiat,)g (Oded)i(Gol-)75 1344 y(dreic)o(h,)e(Stuart)e(Hab)q(er,)i(Ralph)g (Merkle,)f(and)g(Silvio)i(Micali)f(for)f(discussions)h(and)f(helpful)i (commen)o(ts.)75 1487 y Fj(References)98 1589 y Fn([1])21 b(Bellare)13 b(M.)e(and)g(S.)g(Micali)i Fm(How)g(to)g(Sign)e(Given)i (any)f(T)m(r)n(ap)n(do)n(or)g(F)m(unction)g Fn(,)g(Pro)q(c.)e(20th)h (Ann)o(ual)168 1645 y(Symp)q(osium)17 b(on)e(the)g(Theory)g(of)g (Computing,)g(Chicago,)g(Il,)g(1988,)f(pp.)h(32-42.)98 1739 y([2])21 b(Blum)13 b(M.)e(and)g(S.)g(Micali)i Fm(How)g(to)h(Gener) n(ate)e(Crypto)n(gr)n(aphic)n(al)r(ly)h(Str)n(ong)f(Se)n(quenc)n(es)f (of)i(Pseudo-)168 1795 y(R)n(andom)k(Bits)p Fn(,)d(SIAM)i(Journal)g(on) f(Computing,)g(V.)g(13,)f(No.)h(4,)f(No)o(v.)g(84,)h(pp.)g(850-864.)98 1889 y([3])21 b(G.)j(Brassard,)h(C.)e(Crep)q(eau)i(and)f(M.)f(Y)l(ung,) j Fm(A)o(l)r(l)e(NP)g(Can)f(Be)h(Pr)n(ove)n(d)g(in)g(Perfe)n(ct)g(Zer)n (o-)168 1946 y(Know)r(le)n(dge)16 b(in)g(Constant)f(R)n(ounds)p Fn(,)g(ICALP)h(1989,)d(to)i(app)q(ear.)98 2039 y([4])21 b(J.)h(L.)f(Carter)f(and)i(M.)e(N.)h(W)l(egman,)h Fm(Universal)f (Classes)f(of)i(Hash)g(F)m(unctions)p Fn(,)e(Journal)i(of)168 2096 y(Computer)15 b(and)h(System)f(Sciences)i(18)d(\(1979\),)f(pp.)j (143-154.)98 2190 y([5])21 b(I.)f(B.)g(Damgard,)f Fm(Col)r(lision)h(F)m (r)n(e)n(e)f(Hash)h(F)m(unctions)f(and)i(Public)f(Key)g(Signatur)n(e)h (Schemes)e Fn(,)168 2246 y(Euro)q(crypt,)c(1987.)98 2340 y([6])21 b(W.)13 b(Di\016e)h(and)g(M.)f(Hellman,)i Fm(New)f(Dir)n(e)n (ctions)g(in)g(Crypto)n(gr)n(aphy)i Fn(,)d(IEEE)h(T)l(rans.)f(on)g (Informa-)168 2396 y(tion)j(Theory)l(,)f(v)o(ol.)g(IT-22,)f(6)h (\(1976\),)e(pp.)i(644-654.)98 2490 y([7])21 b(S.)e(Ev)o(en,)f(O.)g (Goldreic)o(h,)i(and)f(S.)f(Micali,)i Fm(On-line/O\013-line)d(Digital)i (Signatur)n(es)p Fn(,)f(Pro)q(c.)g(Ad-)168 2547 y(v)m(ances)e(in)g (Cryptology)f({)g(Crypto)f('89,)g(Springer)i(V)l(erlag,)f(pp.)h (263{275,)c(1990.)952 2750 y(12)p eop %%Page: 13 14 13 13 bop 98 121 a Fn([8])21 b(A.)d(Fiat)g(and)h(A.)f(Shamir,)h Fm(How)g(to)h(Pr)n(ove)f(Y)m(ourself:)25 b(Pr)n(actic)n(al)19 b(Solutions)f(to)i(Identi\014c)n(ation)168 177 y(Pr)n(oblems)c(and)g (Signatur)n(e)g(Pr)n(oblems)p Fn(,)e(Pro)q(c)5 b(_)-18 b(of)14 b(Crypto)h(86,)f(pp.)h(186-194.)98 269 y([9])21 b(O.)d(Goldreic)o(h,)i Fm(Two)f(R)n(emarks)f(Conc)n(erning)f(the)i(GMR) g(Signatur)n(e)f(Scheme)p Fn(,)g(Pro)q(c)5 b(_)-18 b(of)18 b(Crypto)168 325 y(86,)d(pp.)g(104-110.)75 417 y([10])21 b(O.)14 b(Goldreic)o(h,)g(S.)f(Goldw)o(asser)g(and)g(S.)h(Micali,)g Fm(How)h(to)g(Construct)f(R)n(andom)h(F)m(unctions)d Fn(Jour-)168 473 y(nal)k(of)f(the)g(A)o(CM)g(\(1986\).)75 565 y([11])21 b(O.)d(Goldreic)o(h,)h(H.)e(Kra)o(w)o(czyk)g(and)g(M.)g (Lub)o(y)l(,)h Fm(On)g(the)h(existenc)n(e)e(of)h(Pseudor)n(andom)h (Gener-)168 622 y(ators)p Fn(,)f(Pro)q(ceedings)h(of)e(the)h(29th)e (Symp)q(osium)j(on)e(the)h(F)l(oundation)g(of)f(Computer)g(Science)i(,) 168 678 y(1988,)14 b(pp.)h(12-24.)75 770 y([12])21 b(S.)e(Goldreic)o (h,)h(S.)f(Micali)h(and)e(A.)h(Wigderson,)g Fm(Pr)n(o)n(ofs)g(that)h (Yields)e(Nothing)i(But)f(their)h(V)m(a-)168 826 y(lidity,)g(and)f(a)h (Metho)n(dolo)n(gy)f(of)g(Crypto)n(gr)n(aphic)h(Pr)n(oto)n(c)n(ol)f (Design)p Fn(,)f(Pro)q(ceedings)h(of)f(the)h(27th)168 883 y(Symp)q(osium)e(on)e(the)g(F)l(oundation)h(of)e(Computer)h (Science,)i(1986,)d(pp.)h(174-187.)75 974 y([13])21 b(S.)14 b(Goldw)o(asser)g(and)g(S.)g(Micali,)h Fm(Pr)n(ob)n(abilistic)f (Encryption)p Fn(,)g(J.)g(Com.)f(Sys.)h(Sci.)g(28)g(\(1984\),)e(pp.)168 1031 y(270-299.)75 1122 y([14])21 b(S.)g(Goldw)o(asser,)h(S.)e(Micali)j (and)e(C.)f(Rac)o(k)o(o\013,)i Fm(The)f(Know)r(le)n(dge)g(Complexity)g (of)h(Inter)n(active)168 1179 y(Pr)n(o)n(of-Systems)p Fn(,)e(Pro)q(c.)f(17th)g(Ann)o(ual)i(Symp)q(osium)f(on)g(the)g(Theory)f (of)g(Computing,)i(Pro)o(vi-)168 1235 y(dence)c(RI,,)e(1985,)f(pp.)h (291-304.)75 1327 y([15])21 b(S.)11 b(Goldw)o(asser,)f(S.)h(Micali)h (and)e(R.)h(Riv)o(est,)g Fm(A)h(se)n(cur)n(e)f(digital)h(signatur)n(e)g (scheme)f Fn(,)g(Siam)g(Journal)168 1383 y(on)16 b(Computing,)f(V)l (ol.)g(17,)f(2)h(\(1988\),)e(pp.)i(281-308.)75 1475 y([16])21 b(S.)14 b(Goldw)o(asser,)g(S.)f(Micali)j(and)e(A.)g(C.)f(Y)l(ao,)h Fm(Str)n(ong)g(signatur)n(e)h(schemes)f Fn(,)g(Pro)q(c.)g(15th)f(Ann)o (ual)168 1532 y(Symp)q(osium)k(on)e(the)g(Theory)g(of)g(Computing,)g (Boston,)f(Ma,)g(1983,)g(pp.)h(431-439.)75 1623 y([17])21 b(R.)15 b(Impagliazzo,)h(L.)e(Levin)i(and)f(M.)f(Lub)o(y)l(,)h Fm(Pseudo-r)n(andom)h(Gener)n(ation)g(given)f(fr)n(om)g(a)h(One-)168 1680 y(way)h(F)m(unction)p Fn(,)d(STOC)h(89.)75 1771 y([18])21 b(R.)d(Impagliazzo)g(and)g(M.)e(Naor,)h Fm(E\016cient)h (Crypto)n(gr)n(aphic)g(Schemes)g(Pr)n(ovably)g(as)g(Se)n(cur)n(e)f(as) 168 1828 y(Subset)g(Sum)p Fn(,)f(Pro)q(c.)g(of)g(the)g(30th)g(Symp.)g (on)g(F)l(oundations)g(of)g(Computer)g(Science,)i(1989,)d(pp.)168 1884 y(236{241.)e(F)l(ull)k(v)o(ersion:)j(T)l(ec)o(hnical)d(Rep)q(ort)e (CS93-12,)f(W)l(eizmann)j(Institute.)75 1976 y([19])k(R.)16 b(Impagliazzo)g(and)g(S.)f(Rudic)o(h,)h Fm(Limits)g(on)g(the)g(Pr)n (ovable)g(Conse)n(quenc)n(es)e(of)i(One-way)h(Per-)168 2032 y(mutations)p Fn(,)f(These)f(Pro)q(c.)75 2124 y([20])21 b(R.)g(Impagliazzo)h(and)e(M.)g(Y)l(ung,)i Fm(Dir)n(e)n(ct)f (Minimum-Know)r(le)n(dge)g(Computations)h Fn(,)f(Pro)q(c.)f(of)168 2181 y(Crypto)15 b(87,)f(Springer)i(V)l(erlag.)75 2272 y([21])21 b(L.)14 b(Lamp)q(ort,)f Fm(Constructing)h(digital)h(signatur) n(es)f(fr)n(om)h(one-way)h(functions)p Fn(,)c(SRI)j(in)o(tl.)f(CSL-98,) 168 2329 y(Octob)q(er)i(1979.)75 2420 y([22])21 b(L.)14 b(Levin,)h Fm(One-way)g(F)m(unctions)e(and)i(Pseudor)n(andom)h(Gener)n (ators)p Fn(,)d(Pro)q(c.)g(17th)g(Ann)o(ual)i(Sym-)168 2477 y(p)q(osium)i(on)e(the)g(Theory)g(of)g(Computing,)g(1985,)e(pp.)j (363-365.)75 2569 y([23])21 b(R.)f(Merkle,)g Fm(A)f(Digital)h(Signatur) n(e)g(b)n(ase)n(d)f(on)g(Conventional)g(Encryption)g(F)m(unction)p Fn(,)g(Crypto)168 2625 y(1987,)14 b(Springer)i(V)l(erlag.)952 2750 y(13)p eop %%Page: 14 15 14 14 bop 75 121 a Fn([24])21 b(R.)13 b(Merkle,)g Fm(Se)n(cr)n(e)n(cy,) g(A)o(uthentic)n(ation)g(and)h(Public)g(Key)f(Systems)p Fn(,)f(Ph.D.)g(Thesis)h(\(1982\),)e(UMI)168 177 y(Researc)o(h)16 b(Press,)f(Ann)g(Arb)q(or,)g(Mic)o(higan.)75 271 y([25])21 b(R.)16 b(Merkle,)f Fm(A)h(Certi\014e)n(d)f(Digital)i(Signatur)n(e)p Fn(,)d(Man)o(uscript)h(1979.)75 365 y([26])21 b(R.)16 b(Merkle)f(and)g(M.)f(Hellman,)j Fm(Hiding)e(Information)h(and)g (Signatur)n(e)f(in)h(T)m(r)n(ap)n(do)n(or)g(Knapsack)p Fn(,)168 421 y(IEEE)g(T)l(rans.)e(on)h(Information)h(Theory)l(,)e(v)o (ol.)h(IT-24,)g(5)g(\(1978\),)e(pp.)i(525-530.)75 515 y([27])21 b(M.)15 b(Naor,)f Fm(Bit)i(c)n(ommitment)h(using)e(pseudo-r)n (andomness)g Fn(Pro)q(c.)g(of)g(Crypto)f(89.)75 609 y([28])21 b(M.)16 b(O.)g(Rabin)i Fm(digitalize)n(d)e(signatur)n(es)g Fn(,)h(in)g(F)l(oundation)f(of)g(Secure)h(Computation,)f(Academic)168 665 y(Press,)f(R.A.)g(DeMillo,)h(D.)e(Dobkin,)i(A.)f(Jones)g(and)h(R.)f (Lipton,)h(eds.,)e(Academic)j(Press,)d(1977.)75 759 y([29])21 b(M.)16 b(O.)f(Rabin)j Fm(Fingerprinting)d(by)i(R)n(andom)g (Polynomials)f Fn(,)g(Harv)m(ard)f(Univ)o(ersit)o(y)l(,)i(TR-15-81,)168 816 y(1981.)75 909 y([30])k(M.)14 b(O.)h(Rabin)h Fm(Digital)g(Signatur) n(es)e(and)i(Public)f(Key)h(F)m(unctions)e(as)i(Intr)n(actable)f(as)g (F)m(actoring)p Fn(,)168 966 y(T)l(ec)o(hnical)i(Memo)e(TM-212,)f(Lab.) h(for)f(Computer)h(Science,)i(MIT,)e(1979.)75 1060 y([31])21 b(R.)16 b(Riv)o(est,)g(A.)g(Shamir)g(and)g(L.)f(Adleman,)i Fm(A)f(Metho)n(d)h(for)g(Obtaining)f(Digital)h(Signatur)n(e)f(and)168 1116 y(Public)g(Key)g(Cryptosystems)p Fn(,)f(Comm.)f(of)g(A)o(CM,)h(21) f(\(1978\),)f(pp.)i(120-126.)75 1210 y([32])21 b(J.)16 b(Romp)q(el,)g Fm(One-way)g(functions)g(ar)n(e)g(ne)n(c)n(essary)f(and) h(su\016c)n(ent)f(for)i(se)n(cur)n(e)f(signatur)n(es)p Fn(,)d(Pro)q(c.)168 1266 y(22nd)j(A)o(CM)e(Ann)o(ual)i(Symp)q(osium)g (on)f(the)h(Theory)f(of)f(Computing,)h(1990,)f(pp.)h(387{394.)75 1360 y([33])21 b(A.)f(Shamir,)h Fm(On)e(the)i(Gener)n(ation)f(of)g (Crypto)n(gr)n(aphic)n(al)r(ly)g(Str)n(ong)g(Pseudo-R)n(andom)h(Numb)n (er)168 1417 y(Se)n(quenc)n(es)p Fn(,)13 b(A)o(CM)i(T)l(rans.)f (Comput.)h(Sys.,)f(1)h(\(1983\),)e(pp.)i(38-44.)75 1510 y([34])21 b(M.)12 b(N.)g(W)l(egman)f(and)i(J.)f(L.)g(Carter,)f Fm(New)j(Hash)f(F)m(unctions)f(and)i(Their)f(Use)g(in)f(A)o(uthentic)n (ation)168 1567 y(and)17 b(Set)f(Equality)p Fn(,)e(Journal)i(of)f (Computer)g(and)g(System)g(Sciences)i(22,)e(pp.)g(265-279)f(\(1981\).) 75 1661 y([35])21 b(A.)f(C.)e(Y)l(ao,)i Fm(The)n(ory)g(and)g(Applic)n (ations)f(of)i(T)m(r)n(ap)n(do)n(or)e(functions)p Fn(,)h(Pro)q (ceedings)g(of)f(the)h(23th)168 1717 y(Symp)q(osium)d(on)e(the)g(F)l (oundation)h(of)e(Computer)h(Science,)i(1982,)d(pp.)h(80-91.)952 2750 y(14)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF