%!PS-Adobe-2.0 %%Creator: dvips 5.519 Copyright 1986, 1993 Radical Eye Software %%Title: gln.dvi %%CreationDate: Sat Dec 9 15:07:14 1995 %%Pages: 11 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSCommandLine: dvips -o xx gln %DVIPSSource: TeX output 1995.12.09:1505 %%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 (/a/oded/PAPERS/LEVIN/OWP/gln.dvi) @start /Fa 2 111 df<0018000038000038 00005800009800008C00010C00020C00060C0007FE00080600100600300600F81F80110E 7E8D16>65 D<73809C40986030C030C030C03188619060E00D097D8812>110 D E /Fb 1 51 df<7FFFFF80FFFFFF80C0000180C0000180C0000180C0000180C0000180 C0000180C0000180C0000180C0000180C0000180C0000180C0000180C0000180C0000180 C0000180C0000180C0000180C0000180C0000180C0000180C0000180FFFFFF807FFFFF80 19197C9B22>50 D E /Fc 1 41 df<00001C00003C0000F80001E00003C0000780000F00 000E00001E00003C00003C00003C00007800007800007800007800007800007800007800 007800007800007800007800007800007800007800007800007800007800007800007800 007800007800007800007800007800007800007800007800007800007800007800007800 00780000780000780000780000780000780000780000F00000F00000F00001E00001E000 03C0000380000700000E00001C0000780000E00000E000007800001C00000E0000070000 03800003C00001E00001E00000F00000F00000F000007800007800007800007800007800 007800007800007800007800007800007800007800007800007800007800007800007800 007800007800007800007800007800007800007800007800007800007800007800007800 007800007800007800007800007800007800007800007800007800003C00003C00003C00 001E00000E00000F000007800003C00001E00000F800003C00001C167C7B8121>40 D E /Fd 32 122 df<387CFEFEFE7C3807077C8610>46 D<00180000780001F800FFF800 FFF80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F800 01F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F800 01F80001F8007FFFE07FFFE013207C9F1C>49 D<03FC000FFF003C1FC07007E07C07F0FE 03F0FE03F8FE03F8FE01F87C01F83803F80003F80003F00003F00007E00007C0000F8000 1F00003E0000380000700000E01801C0180380180700180E00380FFFF01FFFF03FFFF07F FFF0FFFFF0FFFFF015207D9F1C>I<00FE0007FFC00F07E01E03F03F03F03F81F83F81F8 3F81F81F03F81F03F00003F00003E00007C0001F8001FE0001FF000007C00001F00001F8 0000FC0000FC3C00FE7E00FEFF00FEFF00FEFF00FEFF00FC7E01FC7801F81E07F00FFFC0 01FE0017207E9F1C>I<0000E00001E00003E00003E00007E0000FE0001FE0001FE00037 E00077E000E7E001C7E00187E00307E00707E00E07E00C07E01807E03807E07007E0E007 E0FFFFFEFFFFFE0007E00007E00007E00007E00007E00007E00007E000FFFE00FFFE1720 7E9F1C>I<387CFEFEFE7C380000000000000000387CFEFEFE7C3807167C9510>58 D<000070000000007000000000F800000000F800000000F800000001FC00000001FC0000 0003FE00000003FE00000003FE00000006FF000000067F0000000E7F8000000C3F800000 0C3F800000183FC00000181FC00000381FE00000300FE00000300FE00000600FF0000060 07F00000E007F80000FFFFF80000FFFFF800018001FC00018001FC00038001FE00030000 FE00030000FE000600007F000600007F00FFE00FFFF8FFE00FFFF825227EA12A>65 D<0003FE0080001FFF818000FF01E38001F8003F8003E0001F8007C0000F800F80000780 1F800007803F000003803F000003807F000001807E000001807E00000180FE00000000FE 00000000FE00000000FE00000000FE00000000FE00000000FE00000000FE000000007E00 0000007E000001807F000001803F000001803F000003801F800003000F8000030007C000 060003F0000C0001F800380000FF00F000001FFFC0000003FE000021227DA128>67 DI76 D80 D82 D<01FC0407FF8C1F03FC3C007C7C003C78001C78001CF8000CF8000CFC000CFC0000FF00 00FFE0007FFF007FFFC03FFFF01FFFF80FFFFC03FFFE003FFE0003FF00007F00003F0000 3FC0001FC0001FC0001FE0001EE0001EF0003CFC003CFF00F8C7FFE080FF8018227DA11F >I<7FFFFFFF807FFFFFFF807E03F80F807803F807807003F803806003F80180E003F801 C0E003F801C0C003F800C0C003F800C0C003F800C0C003F800C00003F800000003F80000 0003F800000003F800000003F800000003F800000003F800000003F800000003F8000000 03F800000003F800000003F800000003F800000003F800000003F800000003F800000003 F800000003F800000003F800000003F8000003FFFFF80003FFFFF80022227EA127>I<07 FC001FFF803F07C03F03E03F01E03F01F01E01F00001F00001F0003FF003FDF01FC1F03F 01F07E01F0FC01F0FC01F0FC01F0FC01F07E02F07E0CF81FF87F07E03F18167E951B>97 DI<00FF8007FFE00F83F01F03F03E03F07E03F07C01E07C0000FC0000FC0000FC00 00FC0000FC0000FC00007C00007E00007E00003E00301F00600FC0E007FF8000FE001416 7E9519>I<0001FE000001FE0000003E0000003E0000003E0000003E0000003E0000003E 0000003E0000003E0000003E0000003E0000003E0001FC3E0007FFBE000F81FE001F007E 003E003E007E003E007C003E00FC003E00FC003E00FC003E00FC003E00FC003E00FC003E 00FC003E00FC003E007C003E007C003E003E007E001E00FE000F83BE0007FF3FC001FC3F C01A237EA21F>I<00FE0007FF800F87C01E01E03E01F07C00F07C00F8FC00F8FC00F8FF FFF8FFFFF8FC0000FC0000FC00007C00007C00007E00003E00181F00300FC07003FFC000 FF0015167E951A>I<03FC1E0FFF7F1F0F8F3E07CF3C03C07C03E07C03E07C03E07C03E0 7C03E03C03C03E07C01F0F801FFF0013FC003000003000003800003FFF801FFFF00FFFF8 1FFFFC3800FC70003EF0001EF0001EF0001EF0001E78003C7C007C3F01F80FFFE001FF00 18217E951C>103 DI<1C003F007F007F007F003F001C0000000000000000000000 00000000FF00FF001F001F001F001F001F001F001F001F001F001F001F001F001F001F00 1F001F001F001F00FFE0FFE00B247EA310>I108 DII<00FE0007FFC00F83E01E00F03E00F87C007C7C007C7C007CFC007EFC 007EFC007EFC007EFC007EFC007EFC007E7C007C7C007C3E00F81F01F00F83E007FFC000 FE0017167E951C>II< FE1F00FE3FC01E67E01EC7E01E87E01E87E01F83C01F00001F00001F00001F00001F0000 1F00001F00001F00001F00001F00001F00001F00001F0000FFF000FFF00013167E9517> 114 D<0FF3003FFF00781F00600700E00300E00300F00300FC00007FE0007FF8003FFE00 0FFF0001FF00000F80C00780C00380E00380E00380F00700FC0E00EFFC00C7F00011167E 9516>I<0180000180000180000180000380000380000780000780000F80003F8000FFFF 00FFFF000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80 000F81800F81800F81800F81800F81800F830007C30003FE0000F80011207F9F16>II121 D E /Fe 17 121 df<40E06020202040408003097D82 0A>59 D<00200060006000C000C000C0018001800180030003000300060006000C000C00 0C00180018001800300030003000600060006000C000C000C0000B1D7E9511>61 D<000100000300000700000780000B80001B800013800023800023800043800083800083 C00101C003FFC00201C00401C00401C00801C01801E0FE07F815147F9319>65 D<07FC00E001C001C001C001C0038003800380038007000700070007000E000E000E000E 001C00FF800E147F930F>73 D<07E01FC000E00600017004000170040001380400013804 00021C0800021C0800020E0800020E0800040710000407100004039000040390000801E0 000801E0000800E0000800E00018004000FE0040001A147F931A>78 D<07FFE000E07001C01801C01C01C01C01C01C0380380380380380700381C007FF000700 000700000700000E00000E00000E00000E00001C0000FF800016147F9315>80 D<003F0001C1C00300E00600700C0030180038380038700038700038700038E00070E000 70E00070E000E0E000C06001C071C3803A26001C3C0007F0400030400030C0003180003F 80001F00000E00151A7E931A>I<00F8800305800603000401000C01000C01000C00000E 00000FE00007F80001FC00001C00000E00000E00400C00400C00400800601800D020008F C00011147E9314>83 D<07800C401020304060407F8060004000C0004020604021801E00 0B0D7E8C10>101 D<01D8023804380C3018301830183030603060306010E019C00EC000 C000C06180E180C3007C000D137F8C10>103 D<06070600000000384C4C8C9818183032 6262643808147F930C>105 D<7C0C181818183030303060606060C0D0D0D0D06006147E 930A>108 D<30F8590C4E0C9C0C980C180C180C30183019303130316032601C100D7F8C 15>110 D<0C78168C130426062606060606060C0C0C0C0C080C101A2019C01800180030 0030003000FC000F13818C11>112 D<072008E010E030C060C060C060C0C180C180C180 438067003B00030003000600060006003F800B137E8C0F>I<31E05A704C709C60980018 0018003000300030003000600060000C0D7F8C0F>I<0E3C13CE238E430C430003000300 06000608C608E610CA2071C00F0D7F8C13>120 D E /Ff 46 122 df<0000F000F8F001F8F003F8F00780000700000F00000F00000F00000F00000F00000F 00000F0000FFF8F0FFF8F0FFF8F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F 00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F00F0142180A018>12 D45 DI<00C001C00FC0FFC0FFC0 F3C003C003C003C003C003C003C003C003C003C003C003C003C003C003C003C003C003C0 03C003C003C003C003C0FFFEFFFEFFFE0F1F7C9E17>49 D<07F0000FFC001FFE00383F00 700F00600780E00780E003C04003C04003C00003C00003C00003C0000780000780000F00 000E00001C00003C0000780000E00001C0000380000700000E00001C0000380000700000 FFFFC0FFFFC0FFFFC0121F7E9E17>I<03F0000FFC001FFE003C1F00780F003007802007 80000780000780000780000F00000F00003E0003FC0003F80003FC00001E00000F000007 800003800003C00003C00003C00003C08003C0C003C0C00780700F807C1F003FFE000FFC 0003F00012207E9E17>I<7FFF007FFF007FFF0078000078000078000078000078000078 000078000079F0007FFC007FFE007F1F007C07007C07807807800003C00003C00003C000 03C00003C00003C00003C0400780600780F00F007C1E003FFC001FF80007E000121F7E9D 17>53 D<03F0000FFC001FFE003E1F003C0F007807807807807807807807807807807807 803C0F001E1E000FFC0007F8000FFC001F3E003C0F00780780780780F003C0F003C0F003 C0F003C0F003C0F003C07807807C0F803E1F001FFE000FFC0003F00012207E9E17>56 D<03F00007F8000FFC001E1E003C0F00780700780780F00780F00380F003C0F003C0F003 C0F003C0F003C0F003C07807C07807C07C0FC03E1FC01FFBC00FF3C007C7800007800007 80000700000F00001E00201E00307C007FF8003FF0000FC00012207E9E17>II<001F0000001F0000003F800000 3B8000003B8000007BC0000073C0000071C00000F1E00000E1E00000E0E00001E0F00001 E0F00001C0F00003C0780003C078000380780007803C0007803C0007003C000FFFFE000F FFFE000FFFFE001E000F001E000F003C000F803C0007803C000780780007C0780003C078 0003C0F00003E01B207F9F1E>65 D<001FC000FFF801FFFC03E03C07800C0F00001E0000 3E00003C00007C0000780000780000780000F00000F00000F00000F00000F00000F00000 F00000F000007800007800007800007C00003C00003E00001E00000F000207800E03E03E 01FFFC00FFF0001FC017227DA01D>67 DI70 D73 D<003C003C003C003C003C003C003C003C003C003C003C003C 003C003C003C003C003C003C003C003C003C003C003C003C003C003C003C003CC078E078 FFF07FE00FC00E217E9F15>I76 DI< FC0078FE0078FE0078F60078F70078F70078F38078F38078F38078F3C078F1C078F1E078 F1E078F0E078F0F078F07078F07078F07878F03878F03C78F03C78F01C78F01E78F00E78 F00E78F00E78F00778F00778F00378F003F8F003F8F001F815207B9F20>I<003F000000 FFC00003FFF00007E1F8000F807C001F003E001E001E003C000F003C000F007800078078 00078078000780F00003C0F00003C0F00003C0F00003C0F00003C0F00003C0F00003C0F0 0003C0F00003C0F80007C07800078078000780780007803C000F003C000F001E001E001F 003E000F807C0007E1F80003FFF00000FFC000003F00001A227DA021>II82 D<01FC0007FF800FFFC01F03C03C00C0 3C00007800007800007800007800007800007C00003C00003F00001FE0000FFC0007FE00 01FF00003F800007C00003C00003E00001E00001E00001E00001E00001E00001C0C003C0 F007C0FC0F807FFF001FFE0003F80013227EA019>II<07E03FF87FFC701E401F000F000F000F003F07FF1FFF7E 0FF80FF00FF00FF00FF83F7FFF3FEF1F8F10147E9316>97 DI<03F00FFC1FFE3E0E3C0278007800F000 F000F000F000F000F000780078003C013E0F1FFF0FFE03F010147E9314>I<0007800007 8000078000078000078000078000078000078000078000078000078000078007C7800FF7 801FFF803E1F807C0780780780F80780F00780F00780F00780F00780F00780F00780F007 80780780780F803E1F801FFF800FF78007C78011207E9F17>I<03F0000FFC001FFE003E 1F003C0700780700700380FFFF80FFFF80FFFF80F00000F00000F000007000007800003C 01003E07001FFF0007FE0001F80011147F9314>I<007E01FE03FE078007000F000F000F 000F000F000F000F00FFF0FFF0FFF00F000F000F000F000F000F000F000F000F000F000F 000F000F000F000F000F000F000F20809F0E>I<03E0F00FFFF01FFFF03E3E003C1E0078 0F00780F00780F00780F00780F003C1E003E3E001FFC003FF80033E0003000003800003F FE003FFF801FFFC03FFFE07803F0F000F0F000F0F000F0F801F07E07E03FFFC00FFF0003 FC00141E7F9317>III107 DII I<01F80007FE001FFF803F0FC03C03C07801E07801E0F000F0F000F0F000F0F000F0F000 F0F000F07801E07801E03C03C03F0FC01FFF8007FE0001F80014147F9317>II114 D<07F01FFC3FFC780C7800780078007C003FC01FF00FF803F8007C003C003CC03CF07CFF F87FF00FC00E147F9311>I<1E001E001E001E001E001E00FFF0FFF0FFF01E001E001E00 1E001E001E001E001E001E001E001E001E001E001E201FF00FF007C00C1A7F9910>IIII121 D E /Fg 38 124 df<000FE000007FF80000F81C0001E07C0003E07C00 07C07C0007C07C0007C0380007C0000007C0000007C0000007C1FE00FFFFFE00FFFFFE00 07C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E00 07C03E0007C03E0007C03E0007C03E0007C03E0007C03E0007C03E003FF9FFC03FF9FFC0 1A20809F1D>12 D<0018007000E001C00380038007000E000E001E001C003C003C007800 780078007800F800F000F000F000F000F000F000F000F000F000F8007800780078007800 3C003C001C001E000E000E0007000380038001C000E0007000180D2D7DA114>40 DI<00E00001E0000FE000FF E000F3E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003 E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E000FF FF80FFFF80111D7C9C1A>49 D<07F0001FFE00383F007C1F80FE0FC0FE0FC0FE0FE0FE07 E07C07E03807E0000FE0000FC0000FC0001F80001F00003E0000780000F00000E00001C0 000380600700600E00601C00E01FFFC03FFFC07FFFC0FFFFC0FFFFC0131D7D9C1A>I<01 FC0007FF000E0F801E0FC03F07E03F07E03F07E03F07E01E0FC0000FC0000F80001F0001 FC0001FC00000F800007C00003E00003F00003F83803F87C03F8FE03F8FE03F8FE03F0FC 03F07807E03C0FC01FFF8003FC00151D7E9C1A>I<0001C00003C00007C00007C0000FC0 001FC0003BC00073C00063C000C3C00183C00383C00703C00E03C00C03C01803C03803C0 7003C0E003C0FFFFFEFFFFFE0007C00007C00007C00007C00007C00007C000FFFE00FFFE 171D7F9C1A>I<3803803FFF803FFF003FFE003FFC003FF0003F80003000003000003000 0030000033F80037FE003C1F00380F801007C00007C00007E00007E07807E0FC07E0FC07 E0FC07E0FC07C0780FC0600F80381F001FFC0007F000131D7D9C1A>I<003F0001FFC007 E0E00F81E01F03F01E03F03E03F07C03F07C01E07C0000FC1000FCFF00FDFFC0FD03E0FE 01F0FE01F0FC01F8FC01F8FC01F8FC01F87C01F87C01F87C01F83C01F03E01F01E03E00F 07C007FF8001FE00151D7E9C1A>I<387CFEFEFE7C38000000000000387CFEFEFE7C3807 147C930F>58 D<0007FC02003FFF0E00FE03DE03F000FE07E0003E0FC0001E1F80001E3F 00000E3F00000E7F0000067E0000067E000006FE000000FE000000FE000000FE000000FE 000000FE000000FE0000007E0000007E0000067F0000063F0000063F00000C1F80000C0F C0001807E0003803F0007000FE01C0003FFF800007FC001F1F7D9E26>67 DI70 D73 D78 D80 D82 D<03FC080FFF381E03F83800F8700078700038F00038F00018F00018F80000FC00007FC0 007FFE003FFF801FFFE00FFFF007FFF000FFF80007F80000FC00007C00003CC0003CC000 3CC0003CE00038E00078F80070FE01E0E7FFC081FF00161F7D9E1D>I<7FFFFFFC7FFFFF FC7C07E07C7007E01C6007E00C6007E00CE007E00EC007E006C007E006C007E006C007E0 060007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0 000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E00003FFFF C003FFFFC01F1E7E9D24>I<3FFFFF803FFFFF803F803F003E007F0038007E003800FC00 7001FC007001F8006003F0006007F0006007E000000FC000001FC000001F8000003F0000 007F0000007E000000FC000001FC018001F8018003F0018007F0018007E003800FC00380 1FC003001F8007003F000F007F001F007E007F00FFFFFF00FFFFFF00191F7D9E20>90 D<07FC001FFF003F0F803F07C03F03E03F03E00C03E00003E0007FE007FBE01F03E03C03 E07C03E0F803E0F803E0F803E0FC05E07E0DE03FF8FE0FE07E17147F9319>97 D<01FE0007FF801F0FC03E0FC03E0FC07C0FC07C0300FC0000FC0000FC0000FC0000FC00 00FC00007C00007E00003E00603F00C01F81C007FF0001FC0013147E9317>99 D<01FE0007FF800F83C01E01E03E00F07C00F07C00F8FC00F8FFFFF8FFFFF8FC0000FC00 00FC00007C00007C00003E00181E00180F807007FFE000FF8015147F9318>101 D<001F8000FFC001F3E003E7E003C7E007C7E007C3C007C00007C00007C00007C00007C0 00FFFC00FFFC0007C00007C00007C00007C00007C00007C00007C00007C00007C00007C0 0007C00007C00007C00007C00007C00007C0003FFC003FFC0013207F9F10>I104 D<1C003E003F007F003F003E001C00000000000000000000000000FF00FF001F001F001F 001F001F001F001F001F001F001F001F001F001F001F001F001F00FFE0FFE00B217EA00E >I107 DI< FE0FE03F80FE1FF07FC01E70F9C3E01E407D01F01E807E01F01F807E01F01F007C01F01F 007C01F01F007C01F01F007C01F01F007C01F01F007C01F01F007C01F01F007C01F01F00 7C01F01F007C01F01F007C01F01F007C01F0FFE3FF8FFEFFE3FF8FFE27147D932C>II<01FF0007FFC0 1F83F03E00F83E00F87C007C7C007CFC007EFC007EFC007EFC007EFC007EFC007E7C007C 7C007C3E00F83E00F81F83F007FFC001FF0017147F931A>II114 D<0FE63FFE701E600EE006E006F800FFC07FF83FFC1FFE03FE001FC007 C007E007F006F81EFFFCC7F010147E9315>I<01800180018003800380038007800F803F 80FFFCFFFC0F800F800F800F800F800F800F800F800F800F800F860F860F860F860F8607 CC03F801F00F1D7F9C14>II121 D123 D E /Fh 46 123 df<00003FE00000E010000180380003807800030078000700 30000700000007000000070000000E0000000E0000000E000000FFFFE0000E00E0001C01 C0001C01C0001C01C0001C01C0001C038000380380003803800038038000380700003807 00007007000070071000700E2000700E2000700E2000E00E2000E0064000E0038000E000 0000C0000001C0000001C000003180000079800000F3000000620000003C0000001D2982 9F1A>12 D<00003FC0FF800000E0E38040000181E600E0000381EC01E0000300DC01E000 07001C00C0000700180000000700380000000E00380000000E00380000000E0038000000 0E0070000000FFFFFFFF80001C00700380001C00700700001C00700700001C0070070000 1C00E00700001C00E00E00003800E00E00003800E00E00003800E00E00003801C01C0000 3801C01C00007001C01C00007001C01C40007001C0388000700380388000700380388000 E00380388000E00380190000E003000E0000E00700000000C00700000001C00600000001 C00600000031860E000000798F0C000000F31E18000000620C300000003C07C00000002B 29829F28>14 D<0E1F3F3F1D0102020404081020C0080E779F0E>39 D<1C3C3C3C3C040408081020204080060E7D840E>44 D<7FF0FFE07FE00C037D8A10>I< 70F8F8F0E005057B840E>I<000200020006000E003C00DC031C001C0038003800380038 007000700070007000E000E000E000E001C001C001C001C003800380038003800780FFF8 0F1E7B9D17>49 D<001F800060E000807001003002003804203804203804103804207004 60700380600000E00001C000030000FE00001C0000060000070000078000078000078030 0780780780780780F00F00800F00401E00401C0040380020E0001F8000151F7C9D17>51 D<00000200000006000000060000000E0000001E0000001E0000003F0000002F0000004F 0000004F0000008F0000010F0000010F0000020F0000020F0000040F00000C0F0000080F 0000100F0000100F0000200F80003FFF800040078000C007800080078001000780010007 800200078002000780060007801E000F80FF807FF81D207E9F22>65 D<0000FE0200078186001C004C0038003C0060003C00C0001C01C0001803800018070000 180F0000181E0000101E0000103C0000003C000000780000007800000078000000780000 00F0000000F0000000F0000000F0000000F0000080700000807000008070000100380001 0038000200180004000C001800060020000381C00000FE00001F217A9F21>67 D<01FFFF80001E00E0001E0070001E0038001E001C003C001C003C000E003C000E003C00 0E0078000E0078000E0078000E0078000E00F0001E00F0001E00F0001E00F0001E01E000 3C01E0003C01E0003C01E0007803C0007003C0007003C000E003C001C0078001C0078003 8007800E0007801C000F007000FFFFC0001F1F7D9E22>I<01FFFFFC001E0038001E0018 001E0008001E0008003C0008003C0008003C0008003C0008007800100078080000780800 0078080000F0100000F0300000FFF00000F0300001E0200001E0200001E0200001E02000 03C0000003C0000003C0000003C00000078000000780000007800000078000000F800000 FFF800001E1F7D9E1E>70 D<01FFF0001F00001E00001E00001E00003C00003C00003C00 003C0000780000780000780000780000F00000F00000F00000F00001E00001E00001E000 01E00003C00003C00003C00003C0000780000780000780000780000F8000FFF800141F7D 9E12>73 D<01FFF800001F0000001E0000001E0000001E0000003C0000003C0000003C00 00003C00000078000000780000007800000078000000F0000000F0000000F0000000F000 0001E0000001E0000001E0000001E0008003C0010003C0010003C0030003C00200078006 000780060007800C0007801C000F007800FFFFF800191F7D9E1D>76 D<01FE00007FC0001E0000FC00001E0000F80000170001780000170001780000270002F0 0000270004F00000270004F00000270008F00000470009E00000470011E00000470021E0 0000470021E00000870043C00000838043C00000838083C00000838083C0000103810780 000103820780000103820780000103840780000203840F00000203880F00000203900F00 000203900F00000401E01E00000401E01E00000401C01E00000C01801E00001C01803E00 00FF8103FFC0002A1F7D9E29>I<0001FC0000070700001C01C0003000E000E0006001C0 00700380007007800038070000380E0000381E0000381C0000383C0000383C0000387800 0078780000787800007878000078F00000F0F00000F0F00000E0F00001E0F00001C0F000 03C0700003807000070078000F0038001E0038003C001C0070000E00E0000783800001FC 00001D217A9F23>79 D<01FFFF80001E00E0001E0070001E0038001E003C003C003C003C 003C003C003C003C003C0078007800780078007800F0007800E000F003C000F00F0000FF FC0000F0000001E0000001E0000001E0000001E0000003C0000003C0000003C0000003C0 0000078000000780000007800000078000000F800000FFF000001E1F7D9E1F>I<01FFFF 00001E03C0001E00E0001E0070001E0078003C0078003C0078003C0078003C0078007800 F0007800F0007801E0007801C000F0070000F01E0000FFF00000F0380001E01C0001E01E 0001E00E0001E00F0003C01E0003C01E0003C01E0003C01E0007803C0007803C0807803C 0807803C100F801C10FFF00C20000007C01D207D9E21>82 D<0007E040001C18C0003005 800060038000C0038001C00180018001000380010003800100038001000380000003C000 0003C0000003F8000001FF800001FFE000007FF000001FF0000001F80000007800000078 00000038000000380020003800200038002000300060007000600060006000E0007000C0 00E8038000C606000081F800001A217D9F1A>I<0FFFFFF01E0780E01807802010078020 20078020200F0020600F0020400F0020400F0020801E0040001E0000001E0000001E0000 003C0000003C0000003C0000003C00000078000000780000007800000078000000F00000 00F0000000F0000000F0000001E0000001E0000001E0000001E0000003E00000FFFF0000 1C1F789E21>I87 D<00F1800389C0070780 0E03801C03803C0380380700780700780700780700F00E00F00E00F00E00F00E20F01C40 F01C40703C40705C40308C800F070013147C9317>97 D<07803F8007000700070007000E 000E000E000E001C001C001CF01D0C3A0E3C0E380F380F700F700F700F700FE01EE01EE0 1EE01CE03CE038607060E031C01F0010207B9F15>I<007E0001C1000300800E07801E07 801C07003C0200780000780000780000F00000F00000F00000F00000F000007001007002 0030040018380007C00011147C9315>I<0000780003F800007000007000007000007000 00E00000E00000E00000E00001C00001C000F1C00389C00707800E03801C03803C038038 0700780700780700780700F00E00F00E00F00E00F00E20F01C40F01C40703C40705C4030 8C800F070015207C9F17>I<007C01C207010E011C013C013802780C7BF07C00F000F000 F000F0007000700170023804183807C010147C9315>I<00007800019C00033C00033C00 0718000700000700000E00000E00000E00000E00000E0001FFE0001C00001C00001C0000 1C0000380000380000380000380000380000700000700000700000700000700000700000 E00000E00000E00000E00000C00001C00001C0000180003180007B0000F300006600003C 00001629829F0E>I<003C6000E27001C1E00380E00700E00F00E00E01C01E01C01E01C0 1E01C03C03803C03803C03803C03803C07003C07001C0F001C17000C2E0003CE00000E00 000E00001C00001C00301C00783800F0700060E0003F8000141D7E9315>I<01E0000FE0 0001C00001C00001C00001C000038000038000038000038000070000070000071E000763 000E81800F01C00E01C00E01C01C03801C03801C03801C0380380700380700380700380E 10700E20700C20701C20700C40E00CC060070014207D9F17>I<00C001E001E001C00000 0000000000000000000000000E003300230043804300470087000E000E000E001C001C00 1C003840388030807080310033001C000B1F7C9E0E>I<01E0000FE00001C00001C00001 C00001C0000380000380000380000380000700000700000703C00704200E08E00E11E00E 21E00E40C01C80001D00001E00001FC00038E00038700038700038384070708070708070 7080703100E03100601E0013207D9F15>107 D<03C01FC0038003800380038007000700 070007000E000E000E000E001C001C001C001C0038003800380038007000700070007100 E200E200E200E200640038000A207C9F0C>I<1C0F80F0002630C318004740640C004780 680E004700700E004700700E008E00E01C000E00E01C000E00E01C000E00E01C001C01C0 38001C01C038001C01C038001C01C0708038038071003803806100380380E10038038062 007007006600300300380021147C9325>I<1C0F802630C0474060478060470070470070 8E00E00E00E00E00E00E00E01C01C01C01C01C01C01C0384380388380308380708380310 7003303001C016147C931A>I<007C0001C3000301800E01C01E01C01C01E03C01E07801 E07801E07801E0F003C0F003C0F003C0F00780F00700700F00700E0030180018700007C0 0013147C9317>I<01C1E002621804741C04781C04701E04701E08E01E00E01E00E01E00 E01E01C03C01C03C01C03C01C0380380780380700380E003C1C0072380071E0007000007 00000E00000E00000E00000E00001C00001C0000FFC000171D809317>I<00F0400388C0 0705800E03801C03803C0380380700780700780700780700F00E00F00E00F00E00F00E00 F01C00F01C00703C00705C0030B8000F3800003800003800007000007000007000007000 00E00000E0000FFE00121D7C9315>I<1C1E002661004783804787804707804703008E00 000E00000E00000E00001C00001C00001C00001C00003800003800003800003800007000 0030000011147C9313>I<00FC030206010C030C070C060C000F800FF007F803FC003E00 0E700EF00CF00CE008401020601F8010147D9313>I<018001C003800380038003800700 0700FFF007000E000E000E000E001C001C001C001C003800380038003820704070407080 708031001E000C1C7C9B0F>I<0E00C03300E02301C04381C04301C04701C08703800E03 800E03800E03801C07001C07001C07001C07101C0E20180E20180E201C1E200C264007C3 8014147C9318>I<0E03803307802307C04383C04301C04700C08700800E00800E00800E 00801C01001C01001C01001C02001C02001C04001C04001C08000E300003C00012147C93 15>I<0E00C1C03300E3C02301C3E04381C1E04301C0E04701C060870380400E0380400E 0380400E0380401C0700801C0700801C0700801C0701001C0701001C0602001C0F02000C 0F04000E13080003E1F0001B147C931E>I<0383800CC4401068E01071E02071E02070C0 40E00000E00000E00000E00001C00001C00001C00001C040638080F38080F38100E58100 84C60078780013147D9315>I<0E00C03300E02301C04381C04301C04701C08703800E03 800E03800E03801C07001C07001C07001C07001C0E00180E00180E001C1E000C3C0007DC 00001C00001C00003800F03800F07000E06000C0C0004380003E0000131D7C9316>I<01 C04003E08007F1800C1F0008020000040000080000100000200000400000800001000002 00000401000802001002003E0C0063FC0041F80080E00012147D9313>I E /Fi 15 107 df0 D<70F8F8F87005057C8D0D>I<40 0004C0000C6000183000301800600C00C006018003030001860000CC0000780000300000 300000780000CC000186000303000601800C00C0180060300030600018C0000C40000416 187A9623>I<03C00FF01FF83FFC7FFE7FFEFFFFFFFFFFFFFFFFFFFFFFFF7FFE7FFE3FFC 1FF80FF003C010127D9317>15 D<003FFFC000FFFFC003C00000070000000C0000001800 000030000000300000006000000060000000C0000000C0000000C0000000C0000000C000 0000C0000000C000000060000000600000003000000030000000180000000C0000000700 000003C0000000FFFFC0003FFFC000000000000000000000000000000000000000000000 0000000000007FFFFFC07FFFFFC01A247C9C23>18 D<0000000400000000020000000002 000000000100000000008000000000400000000020FFFFFFFFFCFFFFFFFFFC0000000020 00000000400000000080000000010000000002000000000200000000040026107D922D> 33 D<003FF800FFF803C0000700000C0000180000300000300000600000600000C00000 C00000C00000FFFFF8FFFFF8C00000C00000C00000600000600000300000300000180000 0C000007000003C00000FFF8003FF8151C7C981E>50 D<00000C00000C00001800001800 00300000300000600000600000C00000C000018000018000018000030000030000060000 0600000C00000C0000180000180000300000300000600000600000C00000C00001800001 80000300000300000600000600000600000C00000C000018000018000030000030000060 0000600000C00000400000162C7AA000>54 DI<00040000000C0000000C0000000C0000000C0000000C0000000C0000000C 0000000C0000000C0000000C0000000C0000000C0000000C0000000C0000000C0000000C 0000000C0000000C0000000C0000000C0000000C0000000C0000000C0000000C0000000C 0000FFFFFFE0FFFFFFE01B1C7C9B23>63 D<400002C00006C00006C00006C00006C00006 C00006C00006C00006C00006C00006C00006C00006C00006C00006C00006C00006C00006 C00006C00006C0000660000C60000C3000181C00700F01E003FF8000FE00171C7D9A1E> 91 D<00FE0003FF800F01E01C007030001860000C60000CC00006C00006C00006C00006 C00006C00006C00006C00006C00006C00006C00006C00006C00006C00006C00006C00006 C00006C00006C00006C00006400002171C7D9A1E>I<000F0038006000E001C001C001C0 01C001C001C001C001C001C001C001C001C001C001C001C0038007001E00F8001E000700 038001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C000E00060 0038000F102D7DA117>102 DI106 D E /Fj 10 103 df<0102040810302060 6040C0C0C0C0C0C0C0C0C0C040606020301008040201081E7E950D>40 D<80402010080C0406060203030303030303030303020606040C0810204080081E7E950D >I<0F0030C0606060604020C030C030C030C030C030C030C030C030C030402060606060 30C00F000C137E9211>48 D<0C001C00EC000C000C000C000C000C000C000C000C000C00 0C000C000C000C000C000C00FFC00A137D9211>I<1F0060C06060F070F0306030007000 70006000C001C00180020004000810101020207FE0FFE00C137E9211>I<0FC030707038 703870380038003000E00FC0007000380018001C601CF01CF018E03860701FC00E137F92 11>I<60607FC07F8044004000400040004F0070C040E0006000700070E070E070E06040 E021C01F000C137E9211>53 D<00780018001800180018001800180F98187820386018C0 18C018C018C018C0186018203810580F9E0F147F9312>100 D<0F80104020206030C010 FFF0C000C000C0006000201018200FC00C0D7F8C0F>I<03C00CE018E018401800180018 00FF00180018001800180018001800180018001800180018007F000B1480930A>I E /Fk 8 113 df0 D<040004000400C460E4E03F800E003F 80E4E0C4600400040004000B0D7E8D11>3 D<040E0E1C1C1C38383070706060C0C0070F 7F8F0A>48 D<03FC0FFC1C003000600060006000C000C000FFFCFFFCC000C00060006000 600030001C000FFC03FC0E147D9016>50 D<00E003000600060006000600060006000600 06000600060006001C00F0001C0006000600060006000600060006000600060006000600 030000E00B1D7E9511>102 DI106 D<00000040000000C00000018000000180000003000000030000000600 0000060000000C000000180000001800000030000000300000006000000060003000C000 D800C000180180000C0180000C0300000603000006060000030C0000030C000001980000 0198000000F0000000F0000000600000006000001A1E7F811B>112 D E /Fl 31 122 df<000040000040000080000080000080000080000100000100000100 000100000200000200001FC000E27003841806040C0C040E1C0406380807300807700807 700807E0100EE0100EE0100CE0101C6020387020303020601821C00E470003F800004000 00400000800000800000800000800001000001000001000018297E9F1B>30 D<70F8F8F87005057C840D>58 D<70F8FCFC74040404080810102040060E7C840D>I<00 0001C00000078000001E00000078000001E00000078000000E00000038000000F0000003 C000000F0000003C000000F0000000F00000003C0000000F00000003C0000000F0000000 380000000E0000000780000001E0000000780000001E0000000780000001C01A1A7C9723 >I<000100030003000600060006000C000C000C00180018001800300030003000600060 006000C000C000C00180018001800300030003000600060006000C000C000C0018001800 1800300030003000600060006000C000C000C000102D7DA117>II<000002000000 060000000E0000000E0000001E0000001F0000002F0000002F0000004F0000008F000000 8F0000010F0000010F0000020F0000040F0000040F0000080F8000080780001007800020 078000200780007FFF800040078000800780018007800100078002000780020007C00400 03C00C0003C01E0007C0FF807FFC1E207E9F22>65 D<00FFFFE0000F0078000F003C000F 001C000F001E001E001E001E001E001E001E001E001E003C003C003C003C003C0078003C 00F0007803C0007FFF80007803C0007801E000F000F000F000F000F000F000F0007001E0 00F001E000F001E000F001E000E003C001E003C003C003C0038003C00F0007801E00FFFF F0001F1F7E9E22>I<00FFFFE000000F007800000F001C00000F000E00000F000700001E 000700001E000380001E000380001E000380003C000380003C000380003C000380003C00 0380007800078000780007800078000780007800078000F0000F0000F0000F0000F0000E 0000F0001E0001E0001C0001E0003C0001E000380001E000700003C000E00003C001C000 03C003800003C007000007803C0000FFFFF00000211F7E9E26>68 D<00007E0100038183000E00460038002E0070001E00E0000E01C0000C0380000C070000 0C0F00000C1E0000081E0000083C0000003C000000780000007800000078000000780000 00F0000000F0007FFCF00001E0F00001E0F00003C0700003C0700003C0700003C0380007 80380007801C000F800C000B80060033000380C100007F000020217E9F24>71 D<00FFFC000F80000F00000F00000F00001E00001E00001E00001E00003C00003C00003C 00003C0000780000780000780000780000F00000F00000F00000F00001E00001E00001E0 0001E00003C00003C00003C00003C00007C000FFFC00161F7F9E14>73 D<00FF803FF0000F800780000F800200000BC00200000BC002000013C004000011E00400 0011E004000011E004000020F008000020F008000020F808000020780800004078100000 403C100000403C100000403C100000801E200000801E200000801E200000800F20000100 0F400001000F4000010007C000010007C000020007800002000380000200038000060003 80000F00010000FFE0010000241F7E9E25>78 D<0001FC0000070700001C01C0003000E0 00E0006001C000700380007007800038070000380E0000381E0000381C0000383C000038 3C00003878000078780000787800007878000078F00000F0F00000F0F00000E0F00001E0 F00001C0F00003C0700003807000070078000F0038001E0038003C001C0070000E00E000 0783800001FC00001D217E9F23>I<00FFFFC0000F0070000F0038000F001C000F001E00 1E001E001E001E001E001E001E001E003C003C003C003C003C0078003C0070007800E000 780380007FFE000078000000F0000000F0000000F0000000F0000001E0000001E0000001 E0000001E0000003C0000003C0000003C0000003C0000007C00000FFFC00001F1F7E9E1D >I<0001FC0000070700001C01C0003000E000E000E001C0007003800070078000780700 00380F0000381E0000381E0000383C0000383C0000787800007878000078780000787800 0078F00000F0F00000F0F00000E0F00001E0F00001C0F00003C070000380701C07007060 0F0038811E0038813C001C8170000E81E0000783808001FD008000010180000101000003 8300000386000003FE000003FC000001F8000000F0001D297E9F24>I<0007E080001811 8000300B000060070000C0070001C0030001800200038002000380020003800200038000 000380000003C0000003F8000003FF800001FFC00000FFE000003FF0000003F0000000F0 000000700000007000000070002000700020007000200060006000E0006000C0006001C0 0070018000E8030000C60E000081F8000019217D9F1C>83 D<07803F8007000700070007 000E000E000E000E001C001C001CF01D0C3A0E3C0E380F380F700F700F700F700FE01EE0 1EE01EE01CE03CE038607060E031C01F0010207E9F14>98 D<007C01C207010E011C013C 013802780C7BF07C00F000F000F000F0007000700170023004183807C010147E9315> 101 D<00007C0000CE00019E00039E00030C000700000700000700000700000E00000E00 000E0000FFF0000E00000E00001C00001C00001C00001C00001C00003800003800003800 00380000380000700000700000700000700000700000E00000E00000E00000E00000C000 01C000318000798000F300006200003C000017297E9F16>I<001E3000713800E0F001C0 700380700780700700E00F00E00F00E00F00E01E01C01E01C01E01C01E01C01E03801E03 800E07800E0B8006170001E700000700000700000E00000E00300E00781C00F038006070 003FC000151D809316>I<00E001E001E000C000000000000000000000000000000E0013 0023804380438043808700070007000E000E001C001C001C20384038403840388019000E 000B1F7E9E10>105 D<03C01FC0038003800380038007000700070007000E000E000E00 0E001C001C001C001C0038003800380038007000700070007100E200E200E200E2006400 38000A207E9F0E>108 D<1E07802318C023A06043C0704380704380708700E00700E007 00E00700E00E01C00E01C00E01C00E03821C03841C07041C07081C03083803101801E017 147E931B>110 D<03C1E004621804741C08781C08701E08701E10E01E00E01E00E01E00 E01E01C03C01C03C01C03C01C0380380780380700380E003C1C0072380071E0007000007 00000E00000E00000E00000E00001C00001C0000FFC000171D819317>112 D<00F0400388C00705800E03801C03803C0380380700780700780700780700F00E00F00E 00F00E00F00E00F01C00F01C00703C00705C0030B8000F38000038000038000070000070 0000700000700000E00000E0000FFE00121D7E9314>I<1E1E0023210023C38043C78043 87804383008700000700000700000700000E00000E00000E00000E00001C00001C00001C 00001C000038000018000011147E9315>I<007C018203010603060706060E00078007F8 03FC01FE001F00077007F006F006E004400820301FC010147E9315>I<00C000E001C001 C001C001C003800380FFF8038007000700070007000E000E000E000E001C001C001C001C 10382038203820384018800F000D1C7F9B10>I<0F006060118070F02180E0F821C0E078 41C0E0384380E0188381C0100701C0100701C0100701C0100E0380200E0380200E038020 0E0380400E0380400E0380800E078080060781000709860001F078001D147E9321>119 D<03C1C00C62201034701038F02038F020386040700000700000700000700000E00000E0 0000E00000E02061C040F1C040F1C080E2C080446300383C0014147E931A>I<0F006011 80702180E021C0E041C0E04380E08381C00701C00701C00701C00E03800E03800E03800E 03800E07000C07000C07000E0F00061E0003EE00000E00000E00001C0078180078380070 700060600021C0001F0000141D7E9316>I E /Fm 36 122 df45 D<000E00001E00007E0007FE00FFFE00FFFE00F8FE0000FE0000FE 0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE 0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE 0000FE0000FE0000FE007FFFFE7FFFFE7FFFFE17277BA622>49 D<00FF800007FFF0000F FFFC001E03FE003800FF807C003F80FE003FC0FF001FC0FF001FE0FF000FE0FF000FE07E 000FE03C001FE000001FE000001FC000001FC000003F8000003F0000007E000000FC0000 00F8000001F0000003E00000078000000F0000001E0000003C00E0007000E000E000E001 C001C0038001C0060001C00FFFFFC01FFFFFC03FFFFFC07FFFFFC0FFFFFF80FFFFFF80FF FFFF801B277DA622>I<007F800003FFF00007FFFC000F80FE001F007F003F807F003F80 3F803F803F803F803F801F803F801F003F8000007F0000007F0000007E000000FC000001 F8000007F00000FFC00000FFC0000001F80000007E0000003F0000003F8000001FC00000 1FC000001FE000001FE03C001FE07E001FE0FF001FE0FF001FE0FF001FC0FF003FC0FE00 3F807C007F003F00FE001FFFFC0007FFF00000FF80001B277DA622>I<00000E0000001E 0000003E0000007E000000FE000000FE000001FE000003FE0000077E00000E7E00000E7E 00001C7E0000387E0000707E0000E07E0000E07E0001C07E0003807E0007007E000E007E 000E007E001C007E0038007E0070007E00E0007E00FFFFFFF8FFFFFFF8FFFFFFF80000FE 000000FE000000FE000000FE000000FE000000FE000000FE000000FE00007FFFF8007FFF F8007FFFF81D277EA622>I<180003001F801F001FFFFE001FFFFC001FFFF8001FFFF000 1FFFC0001FFF00001C0000001C0000001C0000001C0000001C0000001C0000001C000000 1C7FC0001DFFF8001F80FC001E003F0008003F0000001F8000001FC000001FC000001FE0 00001FE018001FE07C001FE0FE001FE0FE001FE0FE001FE0FE001FC0FC001FC078003F80 78003F803C007F001F01FE000FFFFC0003FFF00000FF80001B277DA622>I<0000078000 0000000780000000000FC0000000000FC0000000000FC0000000001FE0000000001FE000 0000003FF0000000003FF0000000003FF00000000077F80000000077F800000000F7FC00 000000E3FC00000000E3FC00000001C1FE00000001C1FE00000003C1FF0000000380FF00 00000380FF00000007007F80000007007F8000000F007FC000000E003FC000000E003FC0 00001C001FE000001C001FE000003FFFFFF000003FFFFFF000003FFFFFF00000700007F8 0000700007F80000F00007FC0000E00003FC0000E00003FC0001C00001FE0001C00001FE 0003C00001FF00FFFE003FFFFCFFFE003FFFFCFFFE003FFFFC2E297EA833>65 D<00007FE0030007FFFC07001FFFFF0F007FF00F9F00FF0001FF01FC0000FF03F800007F 07F000003F0FE000001F1FC000001F1FC000000F3F8000000F3F800000077F800000077F 800000077F00000000FF00000000FF00000000FF00000000FF00000000FF00000000FF00 000000FF00000000FF00000000FF000000007F000000007F800000007F800000073F8000 00073F800000071FC00000071FC000000E0FE000000E07F000001C03F800003C01FC0000 7800FF0001F0007FF007C0001FFFFF800007FFFE0000007FF00028297CA831>67 D70 D73 D<0000FFC00000000FFFFC0000 003F807F000000FE001FC00001F80007E00003F00003F00007E00001F8000FE00001FC00 1FC00000FE001FC00000FE003F8000007F003F8000007F007F8000007F807F0000003F80 7F0000003F807F0000003F80FF0000003FC0FF0000003FC0FF0000003FC0FF0000003FC0 FF0000003FC0FF0000003FC0FF0000003FC0FF0000003FC0FF0000003FC0FF0000003FC0 7F0000003F807F8000007F807F8000007F803F8000007F003F8000007F001FC00000FE00 1FC00000FE000FE00001FC0007F00003F80003F80007F00001FC000FE00000FE001FC000 003FC0FF0000000FFFFC00000000FFC000002A297CA833>79 DI82 D<7FFFFFFFFF807FFFFFFFFF80 7FFFFFFFFF807F807F807F807C007F800F8078007F80078078007F80078070007F800380 F0007F8003C0F0007F8003C0E0007F8001C0E0007F8001C0E0007F8001C0E0007F8001C0 E0007F8001C000007F80000000007F80000000007F80000000007F80000000007F800000 00007F80000000007F80000000007F80000000007F80000000007F80000000007F800000 00007F80000000007F80000000007F80000000007F80000000007F80000000007F800000 00007F80000000007F80000000007F80000000007F80000000007F80000000FFFFFFC000 00FFFFFFC00000FFFFFFC0002A287EA72F>84 D87 D<03FF80000FFFF0001F01FC003F80FE003F807F003F803F003F803F801F003F8000003F 8000003F8000003F8000003F80003FFF8001FC3F800FE03F801F803F803F003F807E003F 80FC003F80FC003F80FC003F80FC003F80FC005F807E00DF803F839FFC1FFE0FFC03F803 FC1E1B7E9A21>97 DI<003FF00001FFFC0003F03E000FC07F001F807F003F007F003F007F007F003E00 7E0000007E000000FE000000FE000000FE000000FE000000FE000000FE000000FE000000 7E0000007E0000007F0000003F0003803F8003801F8007000FE00E0003F83C0001FFF800 003FC000191B7E9A1E>I<00007FF000007FF000007FF0000007F0000007F0000007F000 0007F0000007F0000007F0000007F0000007F0000007F0000007F0000007F0000007F000 3F87F001FFF7F007F03FF00FC00FF01F8007F03F0007F03F0007F07E0007F07E0007F07E 0007F0FE0007F0FE0007F0FE0007F0FE0007F0FE0007F0FE0007F0FE0007F0FE0007F07E 0007F07E0007F03F0007F03F0007F01F800FF00FC01FF007E07FFF01FFE7FF007F87FF20 2A7EA925>I<003FC00001FFF00003E07C000F803E001F801F001F001F003F000F807E00 0F807E000FC07E000FC0FE0007C0FE0007C0FFFFFFC0FFFFFFC0FE000000FE000000FE00 00007E0000007E0000007F0000003F0001C01F0001C00F80038007C0070003F01E0000FF FC00003FE0001A1B7E9A1F>I<0007F8003FFC007E3E01FC7F03F87F03F07F07F07F07F0 3E07F00007F00007F00007F00007F00007F00007F000FFFFC0FFFFC0FFFFC007F00007F0 0007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F0 0007F00007F00007F00007F00007F00007F00007F0007FFF807FFF807FFF80182A7EA915 >I<007F80F001FFE3F807C0FE1C0F807C7C1F003E7C1F003E103F003F003F003F003F00 3F003F003F003F003F003F003F001F003E001F003E000F807C0007C0F80005FFE0000C7F 8000180000001C0000001C0000001E0000001FFFF8001FFFFF000FFFFFC007FFFFE003FF FFF00FFFFFF03E0007F07C0001F8F80000F8F80000F8F80000F8F80000F87C0001F07C00 01F03F0007E00FC01F8007FFFF00007FF0001E287E9A22>II<07000FC01FE03FE03FE03FE01FE00FC0 07000000000000000000000000000000FFE0FFE0FFE00FE00FE00FE00FE00FE00FE00FE0 0FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE0FFFEFFFEFFFE0F2B 7EAA12>I 107 DIII<003FE00001FFFC0003F07E000FC01F801F800FC03F0007E03F0007 E07E0003F07E0003F07E0003F0FE0003F8FE0003F8FE0003F8FE0003F8FE0003F8FE0003 F8FE0003F8FE0003F87E0003F07E0003F03F0007E03F0007E01F800FC00FC01F8007F07F 0001FFFC00003FE0001D1B7E9A22>II114 D<03FE300FFFF03E03F07800F07000F0F00070F0 0070F80070FE0000FFE0007FFF007FFFC03FFFE01FFFF007FFF800FFF80007FC0000FCE0 007CE0003CF0003CF00038F80038FC0070FF01E0E7FFC0C1FF00161B7E9A1B>I<007000 00700000700000700000F00000F00000F00001F00003F00003F00007F0001FFFE0FFFFE0 FFFFE007F00007F00007F00007F00007F00007F00007F00007F00007F00007F00007F000 07F00007F00007F07007F07007F07007F07007F07007F07007F07003F0E001F8C000FFC0 003F0014267FA51A>II119 D121 D E /Fn 82 124 df<001F83E000F06E3001C078780380F8780300F03007007000070070 000700700007007000070070000700700007007000FFFFFF800700700007007000070070 000700700007007000070070000700700007007000070070000700700007007000070070 000700700007007000070070000700700007007000070070007FE3FF001D20809F1B>11 D<003F0000E0C001C0C00381E00701E00701E00700000700000700000700000700000700 00FFFFE00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700 E00700E00700E00700E00700E00700E00700E00700E07FC3FE1720809F19>I<003FE000 E0E001C1E00381E00700E00700E00700E00700E00700E00700E00700E00700E0FFFFE007 00E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E007 00E00700E00700E00700E00700E00700E07FE7FE1720809F19>I<001F81F80000F04F04 0001C07C06000380F80F000300F00F000700F00F00070070000007007000000700700000 070070000007007000000700700000FFFFFFFF0007007007000700700700070070070007 007007000700700700070070070007007007000700700700070070070007007007000700 700700070070070007007007000700700700070070070007007007000700700700070070 07007FE3FE3FF02420809F26>I<3E004100808080808080808041003E00090874A022> 23 D<7038F87CFC7EFC7E743A0402040204020804080410081008201040200F0E7E9F17> 34 D<70F8FCFC74040404080810102040060E7C9F0D>39 D<0020004000800100020006 000C000C00180018003000300030007000600060006000E000E000E000E000E000E000E0 00E000E000E000E000E0006000600060007000300030003000180018000C000C00060002 0001000080004000200B2E7DA112>I<800040002000100008000C000600060003000300 01800180018001C000C000C000C000E000E000E000E000E000E000E000E000E000E000E0 00E000C000C000C001C001800180018003000300060006000C0008001000200040008000 0B2E7DA112>I<0006000000060000000600000006000000060000000600000006000000 06000000060000000600000006000000060000000600000006000000060000FFFFFFF0FF FFFFF0000600000006000000060000000600000006000000060000000600000006000000 0600000006000000060000000600000006000000060000000600001C207D9A23>43 D<70F8FCFC74040404080810102040060E7C840D>II<70F8F8F8 7005057C840D>I<000100030003000600060006000C000C000C00180018001800300030 003000600060006000C000C000C00180018001800300030003000600060006000C000C00 0C00180018001800300030003000600060006000C000C000C000102D7DA117>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>II82 D<07E0800C198010078030038060018060 0180E00180E00080E00080E00080F00000F000007800007F00003FF0001FFC000FFE0003 FF00001F800007800003C00003C00001C08001C08001C08001C08001C0C00180C00380E0 0300F00600CE0C0081F80012217D9F19>I<7FFFFFE0780F01E0600F0060400F0020400F 0020C00F0030800F0010800F0010800F0010800F0010000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000001F800007FFFE001C1F 7E9E21>IIII89 D<7FFFF87C00F87000F06001E04001E0C003C0C003C0800780800F80800F00001E00001E 00003C00003C0000780000F80000F00001E00001E00003C00403C0040780040F80040F00 0C1E000C1E00083C00183C0018780038F801F8FFFFF8161F7D9E1C>II<080410082010201040204020804080408040B85CFC7EFC7E7C3E38 1C0F0E7B9F17>II<081020204040808080B8FCFC 7C38060E7D9F0D>96 D<1FE000303000781800781C00300E00000E00000E00000E0000FE 00078E001E0E00380E00780E00F00E10F00E10F00E10F01E10781E103867200F83C01414 7E9317>I<0E0000FE00000E00000E00000E00000E00000E00000E00000E00000E00000E 00000E00000E3E000EC3800F01C00F00E00E00E00E00700E00700E00780E00780E00780E 00780E00780E00780E00700E00700E00E00F00E00D01C00CC300083E0015207F9F19>I< 03F80E0C1C1E381E380C70007000F000F000F000F000F000F00070007000380138011C02 0E0C03F010147E9314>I<000380003F8000038000038000038000038000038000038000 038000038000038000038003E380061B801C0780380380380380700380700380F00380F0 0380F00380F00380F00380F003807003807003803803803807801C07800E1B8003E3F815 207E9F19>I<03F0000E1C001C0E00380700380700700700700380F00380F00380FFFF80 F00000F00000F000007000007000003800801800800C010007060001F80011147F9314> I<007C00C6018F038F07060700070007000700070007000700FFF0070007000700070007 0007000700070007000700070007000700070007000700070007007FF01020809F0E>I< 0000E003E3300E3C301C1C30380E00780F00780F00780F00780F00780F00380E001C1C00 1E380033E0002000002000003000003000003FFE001FFF800FFFC03001E0600070C00030 C00030C00030C000306000603000C01C038003FC00141F7F9417>I<0E0000FE00000E00 000E00000E00000E00000E00000E00000E00000E00000E00000E00000E3E000E43000E81 800F01C00F01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01 C00E01C00E01C00E01C00E01C0FFE7FC16207F9F19>I<1C001E003E001E001C00000000 0000000000000000000E007E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E000E000E000E00FFC00A1F809E0C>I<00E001F001F001F000E0000000000000 000000000000007007F000F0007000700070007000700070007000700070007000700070 0070007000700070007000700070007000706070F060F0C061803F000C28829E0E>I<0E 0000FE00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E 0FF00E03C00E03000E02000E04000E08000E10000E30000E70000EF8000F38000E1C000E 1E000E0E000E07000E07800E03800E03C00E03E0FFCFF815207F9F18>I<0E00FE000E00 0E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00 0E000E000E000E000E000E000E000E000E000E00FFE00B20809F0C>I<0E1F01F000FE61 8618000E81C81C000F00F00E000F00F00E000E00E00E000E00E00E000E00E00E000E00E0 0E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E 000E00E00E000E00E00E000E00E00E00FFE7FE7FE023147F9326>I<0E3E00FE43000E81 800F01C00F01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01 C00E01C00E01C00E01C00E01C0FFE7FC16147F9319>I<01F800070E001C03803801C038 01C07000E07000E0F000F0F000F0F000F0F000F0F000F0F000F07000E07000E03801C038 01C01C0380070E0001F80014147F9317>I<0E3E00FEC3800F01C00F00E00E00E00E00F0 0E00700E00780E00780E00780E00780E00780E00780E00700E00F00E00E00F01E00F01C0 0EC3000E3E000E00000E00000E00000E00000E00000E00000E00000E0000FFE000151D7F 9319>I<03E0800619801C05803C0780380380780380700380F00380F00380F00380F003 80F00380F003807003807803803803803807801C0B800E138003E3800003800003800003 80000380000380000380000380000380003FF8151D7E9318>I<0E78FE8C0F1E0F1E0F0C 0E000E000E000E000E000E000E000E000E000E000E000E000E000E00FFE00F147F9312> I<1F9030704030C010C010C010E00078007F803FE00FF00070803880188018C018C018E0 30D0608F800D147E9312>I<020002000200060006000E000E003E00FFF80E000E000E00 0E000E000E000E000E000E000E000E000E080E080E080E080E080610031001E00D1C7F9B 12>I<0E01C0FE1FC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C00E01C00E01C00E03C00603C0030DC001F1FC16147F9319>III<7FC3FC0F01E00701C007018003810001C20000E40000EC0000780000 3800003C00007C00004E000087000107000303800201C00601E01E01E0FF07FE17148093 18>II<3FFF380E200E201C403840 78407000E001E001C00380078007010E011E011C0338027006700EFFFE10147F9314>I< FFFFFC1601808C17>I E /Fo 19 123 df45 D<70F8F8F8700505798414>I<01E007F00E38181C38FC71FC739E739EE70EE70EE70EE7 0EE70EE70EE70E739C739C71F838F018060E1E07F801F00F177E9614>64 D<1FC0007FF000707800201800001C00001C0007FC001FFC003C1C00701C00E01C00E01C 00E01C00707C003FFF800F8F8011107E8F14>97 DI<03F80FFC1C1C3808700060 00E000E000E000E00060007000380E1C1E0FFC03F00F107E8F14>I<007E00007E00000E 00000E00000E00000E00000E0007CE000FFE001C3E00301E00700E00E00E00E00E00E00E 00E00E00E00E00E00E00700E00301E00383E001FEFC007CFC012177F9614>I<07E00FF0 1C38301C700CE00EE00EFFFEFFFEE00060007000380E1C1E0FFC03F00F107E8F14>I104 D<030007800780030000000000000000007F807F800380038003800380038003 80038003800380038003800380FFFCFFFC0E187D9714>I<006000F000F0006000000000 000000001FF01FF000700070007000700070007000700070007000700070007000700070 007000700070007040E0E0C07F803F000C207E9714>I108 DII<07C01FF03C78701C701CE00EE00EE00EE00EE00EE00E701C783C3C78 1FF007C00F107E8F14>I<0FD83FF86038C038C038F0007F803FF007F8001C6006E006F0 06F81CFFF8CFE00F107E8F14>115 D117 D119 D<3FFF7FFF700E701C7038007000E0 01C0038007000E001C0738077007FFFFFFFF10107F8F14>122 D E /Fp 48 124 df<00800100020004000C00080018003000300030006000600060006000 E000E000E000E000E000E000E000E000E000E00060006000600060003000300030001800 08000C00040002000100008009267D9B0F>40 D<8000400020001000180008000C000600 060006000300030003000300038003800380038003800380038003800380038003000300 030003000600060006000C0008001800100020004000800009267E9B0F>I<60F0F07010 101020204080040B7D830B>44 DI<60F0F06004047D830B>I<07 8018603030303060186018E01CE01CE01CE01CE01CE01CE01CE01CE01CE01CE01CE01C60 18601870383030186007800E187E9713>48 D<0F80106020304038803CC01CE01C401C00 3C003800380070006000C001800100020004040804100430083FF87FF8FFF80E187E9713 >50 D<01E006100C1818383038300070006000E000E7C0E860F030F018E018E01CE01CE0 1C601C601C701830183030186007C00E187E9713>54 D<07801860303070306018E018E0 18E01CE01CE01C601C603C303C185C0F9C001C00180018003870307060604021801F000E 187E9713>57 D<60F0F060000000000000000060F0F06004107D8F0B>I<000C0000000C 0000000C0000001E0000001E0000003F0000002700000027000000438000004380000043 80000081C0000081C0000081C0000100E0000100E00001FFE00002007000020070000600 7800040038000400380008001C0008001C001C001E00FF00FFC01A1A7F991D>65 DI<003F0201C0C603002E0E001E1C000E1C000638000678 0002700002700002F00000F00000F00000F00000F00000F0000070000270000278000238 00041C00041C00080E000803003001C0C0003F00171A7E991C>IIII72 DI<1FFC00E000 E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E040 E0E0E0E0E041C061801E000E1A7D9914>I77 DI82 D<0FC21836200E6006C006C002C002C002E00070007E003FE01FF807FC003E000E00 070003800380038003C002C006E004D81887E0101A7E9915>I85 D87 D<3F8070C070E020700070007007F01C7030707070E070E071E071E0F171FB1E3C10107E 8F13>97 DI<07F80C1C381C30087000E000E000E000E000 E000E0007000300438080C1807E00E107F8F11>I<007E00000E00000E00000E00000E00 000E00000E00000E00000E00000E0003CE000C3E00380E00300E00700E00E00E00E00E00 E00E00E00E00E00E00E00E00600E00700E00381E001C2E0007CFC0121A7F9915>I<07C0 1C3030187018600CE00CFFFCE000E000E000E0006000300438080C1807E00E107F8F11> I<01F0031807380E100E000E000E000E000E000E00FFC00E000E000E000E000E000E000E 000E000E000E000E000E000E000E007FE00D1A80990C>I<0FCE18733030703870387038 7038303018602FC02000600070003FF03FFC1FFE600FC003C003C003C0036006381C07E0 10187F8F13>II<18003C003C0018000000000000000000 00000000FC001C001C001C001C001C001C001C001C001C001C001C001C001C001C00FF80 091A80990A>I108 DI< FCF8001D0C001E0E001E0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E00 1C0E001C0E001C0E00FF9FC012107F8F15>I<07E01C38300C700E6006E007E007E007E0 07E007E0076006700E381C1C3807E010107F8F13>II114 D<1F2060E04020C020C020F0007F003FC01FE000F080708030C030C020F0408F800C107F 8F0F>I<0400040004000C000C001C003C00FFC01C001C001C001C001C001C001C001C00 1C201C201C201C201C200E4003800B177F960F>IIII121 D<7FF86070407040E041C041C00380070007000E081C081C08381070107030FFF00D107F 8F11>II E /Fq 3 123 df<0C000C008C40EDC07F800C007F80ED C08C400C000C000A0B7D8B10>3 D<1818181818FFFF1818181818181818181818181818 1808167D900E>121 D<1818181818FF18181818180018181818FFFF1818181808167D90 0E>I E /Fr 35 122 df<007E0001C1800301800703C00E03C00E01800E00000E00000E 00000E00000E0000FFFFC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E 01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C07F87F8151D809C17>12 D<004000800100020006000C000C0018001800300030007000600060006000E000E000E0 00E000E000E000E000E000E000E000E000E000600060006000700030003000180018000C 000C00060002000100008000400A2A7D9E10>40 D<800040002000100018000C000C0006 00060003000300038001800180018001C001C001C001C001C001C001C001C001C001C001 C001C0018001800180038003000300060006000C000C00180010002000400080000A2A7E 9E10>I<60F0F0701010101020204080040C7C830C>44 DI<60F0 F06004047C830C>I<030007003F00C70007000700070007000700070007000700070007 000700070007000700070007000700070007000700070007000F80FFF80D1C7C9B15>49 D<000600000006000000060000000F0000000F0000000F00000017800000178000001780 000023C0000023C0000023C0000041E0000041E0000041E0000080F0000080F0000180F8 000100780001FFF80003007C0002003C0002003C0006003E0004001E0004001E000C001F 001E001F00FF80FFF01C1D7F9C1F>65 D68 D76 D80 D82 D<07E0801C1980300580700380600180 E00180E00080E00080E00080F00000F800007C00007FC0003FF8001FFE0007FF0000FF80 000F800007C00003C00001C08001C08001C08001C0C00180C00180E00300D00200CC0C00 83F800121E7E9C17>I87 D<1FC000307000783800781C00301C00001C 00001C0001FC000F1C00381C00701C00601C00E01C40E01C40E01C40603C40304E801F87 0012127E9115>97 DI<07E00C3018 78307870306000E000E000E000E000E000E00060007004300418080C3007C00E127E9112 >I<003F0000070000070000070000070000070000070000070000070000070000070003 E7000C1700180F00300700700700600700E00700E00700E00700E00700E00700E0070060 0700700700300700180F000C370007C7E0131D7E9C17>I<03E00C301818300C700E6006 E006FFFEE000E000E000E00060007002300218040C1803E00F127F9112>I<00F8018C07 1E061E0E0C0E000E000E000E000E000E00FFE00E000E000E000E000E000E000E000E000E 000E000E000E000E000E000E000E007FE00F1D809C0D>I<00038003C4C00C38C01C3880 181800381C00381C00381C00381C001818001C38000C300013C000100000300000180000 1FF8001FFF001FFF803003806001C0C000C0C000C0C000C06001803003001C0E0007F800 121C7F9215>II<18003C003C0018 000000000000000000000000000000FC001C001C001C001C001C001C001C001C001C001C 001C001C001C001C001C001C00FF80091D7F9C0C>I108 DII<03F0000E1C 00180600300300700380600180E001C0E001C0E001C0E001C0E001C0E001C06001807003 803003001806000E1C0003F00012127F9115>II114 D<1F9030704030C010C010E010F8007F803FE00FF000F880388018C018C018 E010D0608FC00D127F9110>I<04000400040004000C000C001C003C00FFE01C001C001C 001C001C001C001C001C001C001C101C101C101C101C100C100E2003C00C1A7F9910>I< FC1F801C03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C0380 1C03801C03801C07800C07800E1B8003E3F014127F9117>III121 D E /Fs 7 117 df<00038000000380000007C0000007C0000007C000000FE000000FE0 00001FF000001BF000001BF0000031F8000031F8000061FC000060FC0000E0FE0000C07E 0000C07E0001803F0001FFFF0003FFFF8003001F8003001F8006000FC006000FC00E000F E00C0007E0FFC07FFEFFC07FFE1F1C7E9B24>65 D<0FF8001C1E003E0F803E07803E07C0 1C07C00007C0007FC007E7C01F07C03C07C07C07C0F807C0F807C0F807C0780BC03E13F8 0FE1F815127F9117>97 DI<03FC00 0E0E001C1F003C1F00781F00780E00F80000F80000F80000F80000F80000F80000780000 7801803C01801C03000E0E0003F80011127E9115>I114 D<1FD830786018E018E018F000FF807FE07FF01FF807FC00 7CC01CC01CE01CE018F830CFC00E127E9113>I<0300030003000300070007000F000F00 3FFCFFFC1F001F001F001F001F001F001F001F001F001F0C1F0C1F0C1F0C0F08079803F0 0E1A7F9913>I E /Ft 3 123 df<020002000200C218F2783AE00F800F803AE0F278C218 0200020002000D0E7E8E12>3 D<06000600060006000600060006000600FFF0FFF00600 060006000600060006000600060006000600060006000600060006000600060006000600 0C1D7E9611>121 D<060006000600060006000600FFF0FFF00600060006000600060006 000000060006000600060006000600FFF0FFF00600060006000600060006000C1D7E9611 >I E /Fu 25 119 df<70F8FCFC7404040404080810102040060F7C840E>44 D<008003800F80F380038003800380038003800380038003800380038003800380038003 80038003800380038003800380038003800380038003800380038007C0FFFE0F217CA018 >49 D<03F0000C1C001007002007804003C04003C08003E0F003E0F801E0F801E0F801E0 2003E00003E00003C00003C0000780000700000E00001C0000180000300000600000C000 0180000100000200200400200800201800603000403FFFC07FFFC0FFFFC013217EA018> I<1000801E07001FFF001FFE001FF80013E0001000001000001000001000001000001000 0010F800130E001407001803801003800001C00001C00001E00001E00001E00001E07001 E0F001E0F001E0E001C08001C04003C04003802007001006000C1C0003F00013227EA018 >53 D<01F000060C000C0600180700380380700380700380F001C0F001C0F001C0F001E0 F001E0F001E0F001E0F001E07001E07003E03803E01805E00C05E00619E003E1E00001C0 0001C00001C0000380000380300300780700780600700C002018001030000FC00013227E A018>57 D<0001800000018000000180000003C0000003C0000003C0000005E0000005E0 00000DF0000008F0000008F0000010F800001078000010780000203C0000203C0000203C 0000401E0000401E0000401E0000800F0000800F0000FFFF000100078001000780030007 C0020003C0020003C0040003E0040001E0040001E00C0000F00C0000F03E0001F8FF800F FF20237EA225>65 D<0007F008003C0C1800E0021801C001B8038000F8070000780F0000 381E0000381E0000183C0000183C0000187C0000087800000878000008F8000000F80000 00F8000000F8000000F8000000F8000000F8000000F8001FFF780000F8780000787C0000 783C0000783C0000781E0000781E0000780F00007807000078038000B801C000B800E003 18003C0C080007F00020247DA226>71 D<03FFF0001F00000F00000F00000F00000F0000 0F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F0000 0F00000F00000F00000F00000F00000F00000F00000F00700F00F80F00F80F00F80E00F0 1E00401C0020380018700007C00014237EA119>74 D76 D78 D<000FE00000783C0000E00E0003C0 0780078003C00F0001E00E0000E01E0000F03C0000783C0000787C00007C7C00007C7800 003C7800003CF800003EF800003EF800003EF800003EF800003EF800003EF800003EF800 003EF800003E7800003C7C00007C7C00007C3C0000783E0000F81E0000F00F0001E00F00 01E0078003C003C0078000E00E0000783C00000FE0001F247DA226>I<0FE0001838003C 0C003C0E0018070000070000070000070000FF0007C7001E07003C0700780700700700F0 0708F00708F00708F00F087817083C23900FC1E015157E9418>97 D<01FE000703000C07801C0780380300780000700000F00000F00000F00000F00000F000 00F00000F000007000007800403800401C00800C010007060001F80012157E9416>99 D<0000E0000FE00001E00000E00000E00000E00000E00000E00000E00000E00000E00000 E00000E00000E001F8E00704E00C02E01C01E03800E07800E07000E0F000E0F000E0F000 E0F000E0F000E0F000E0F000E07000E07800E03800E01801E00C02E0070CF001F0FE1723 7EA21B>I<01FC000707000C03801C01C03801C07801E07000E0F000E0FFFFE0F00000F0 0000F00000F00000F000007000007800203800201C00400E008007030000FC0013157F94 16>I<0E0000FE00001E00000E00000E00000E00000E00000E00000E00000E00000E0000 0E00000E00000E00000E1F800E60C00E80E00F00700F00700E00700E00700E00700E0070 0E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E0070FFE7FF 18237FA21B>104 D<1C001E003E001E001C00000000000000000000000000000000000E 00FE001E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E00FFC00A227FA10E>I<0E00FE001E000E000E000E000E000E000E000E000E000E00 0E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00 0E000E000E000E00FFE00B237FA20E>108 D<0E1FC07F00FE60E183801E807201C00F00 3C00E00F003C00E00E003800E00E003800E00E003800E00E003800E00E003800E00E0038 00E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800E00E003800 E00E003800E00E003800E0FFE3FF8FFE27157F942A>I<0E1F80FE60C01E80E00F00700F 00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E 00700E00700E00700E0070FFE7FF18157F941B>I<01FC000707000C01801800C03800E0 700070700070F00078F00078F00078F00078F00078F00078F000787000707800F03800E0 1C01C00E038007070001FC0015157F9418>I<0E3CFE461E8F0F0F0F060F000E000E000E 000E000E000E000E000E000E000E000E000E000E000F00FFF010157F9413>114 D<0F8830786018C018C008C008E008F0007F803FE00FF001F8003C801C800C800CC00CC0 08E018D0308FC00E157E9413>I<0E0070FE07F01E00F00E00700E00700E00700E00700E 00700E00700E00700E00700E00700E00700E00700E00700E00700E00F00E00F006017003 827800FC7F18157F941B>117 DI E /Fv 18 122 df45 D<00080000380000780001F8003FF800FE7800C078000078000078000078000078000078 000078000078000078000078000078000078000078000078000078000078000078000078 000078000078000078000078000078000078000078000078000078000078000078000078 0000780000780000780000780000780000780000780000780000FC007FFFF87FFFF8152F 7AAE21>49 D<00003FE0010001FFF8030007F01E03001F800307003E000087007800004F 00F000002F01E000001F03C000000F078000000F0F800000070F000000071F000000031E 000000033E000000033C000000017C000000017C000000017C000000017800000000F800 000000F800000000F800000000F800000000F800000000F800000000F800000000F80000 0000F800000000F800000000F80000000078000000007C000000007C000000017C000000 013C000000013E000000011E000000011F000000020F000000020F800000060780000004 03C000000801E000000800F00000100078000020003E0000C0001F8003800007F00F0000 01FFFC0000003FE00028337CB130>67 D70 D<00003FC000000001C03800000007000E0000 001C0003800000380001C00000F00000F00001E00000780003C000003C00038000001C00 078000001E000F0000000F000F0000000F001E00000007801E00000007803C00000003C0 3C00000003C07C00000003E07C00000003E07800000001E07800000001E0F800000001F0 F800000001F0F800000001F0F800000001F0F800000001F0F800000001F0F800000001F0 F800000001F0F800000001F0F800000001F0F800000001F07C00000003E07C00000003E0 7C00000003E07C00000003E03C00000003C03E00000007C01E00000007801E0000000780 0F0000000F000F0000000F00078000001E0003C000003C0003C000003C0001E000007800 00F00000F00000380001C000001C000380000007000E00000001E078000000003FC00000 2C337CB134>79 D87 D<00FE00000303C0000C00E00010007000100038003C003C003E001C003E001E003E001E 0008001E0000001E0000001E0000001E00000FFE0000FC1E0003E01E000F801E001F001E 003E001E003C001E007C001E00F8001E04F8001E04F8001E04F8003E04F8003E0478003E 047C005E043E008F080F0307F003FC03E01E1F7D9E21>97 D<003F8000E0600380180700 040F00041E001E1C003E3C003E7C003E7C0008780000F80000F80000F80000F80000F800 00F80000F80000F80000F800007800007C00007C00003C00011E00011E00020F00020700 0403801800E060003F80181F7D9E1D>99 D<003F800000E0E0000380380007003C000E00 1E001E001E001C000F003C000F007C000F0078000F8078000780F8000780F8000780FFFF FF80F8000000F8000000F8000000F8000000F8000000F8000000780000007C0000003C00 00003C0000801E0000800E0001000F0002000780020001C00C0000F03000001FC000191F 7E9E1D>101 D<000000F0007F030801C1C41C0380E81C070070080F0078001E003C001E 003C003E003E003E003E003E003E003E003E003E003E003E003E001E003C001E003C000F 007800070070000780E00009C1C000087F00001800000018000000180000001800000018 0000001C0000000E0000000FFFF80007FFFF0003FFFF800E000FC0180001E0300000F070 000070E0000038E0000038E0000038E0000038E00000387000007070000070380000E01C 0001C00700070001C01C00003FE0001E2F7E9F21>103 D<07000F801F801F800F800700 000000000000000000000000000000000000000000000780FF80FF800F80078007800780 078007800780078007800780078007800780078007800780078007800780078007800780 0780078007800FC0FFF8FFF80D307EAF12>105 D<0780FE0000FF83078000FF8C03C000 0F9001E00007A001E00007A000F00007C000F00007C000F000078000F000078000F00007 8000F000078000F000078000F000078000F000078000F000078000F000078000F0000780 00F000078000F000078000F000078000F000078000F000078000F000078000F000078000 F000078000F000078000F000078000F0000FC001F800FFFC1FFF80FFFC1FFF80211F7E9E 25>110 D<001FC00000F0780001C01C00070007000F0007801E0003C01C0001C03C0001 E03C0001E0780000F0780000F0780000F0F80000F8F80000F8F80000F8F80000F8F80000 F8F80000F8F80000F8F80000F8780000F07C0001F03C0001E03C0001E01E0003C01E0003 C00F00078007800F0001C01C0000F07800001FC0001D1F7E9E21>I<0783E0FF8C18FF90 7C0F907C07A07C07C03807C00007C00007C0000780000780000780000780000780000780 000780000780000780000780000780000780000780000780000780000780000780000780 000780000FC000FFFE00FFFE00161F7E9E19>114 D<01FC100E03301800F03000706000 30E00030E00010E00010E00010F00010F800007E00003FF0001FFF000FFFC003FFE0003F F00001F80000F880003C80003C80001CC0001CC0001CE0001CE00018F00038F00030CC00 60C301C080FE00161F7E9E1A>I<00400000400000400000400000400000C00000C00000 C00001C00001C00003C00007C0000FC0001FFFE0FFFFE003C00003C00003C00003C00003 C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003 C01003C01003C01003C01003C01003C01003C01003C01001C02001E02000E0400078C000 1F00142C7FAB19>I<078000F000FF801FF000FF801FF0000F8001F000078000F0000780 00F000078000F000078000F000078000F000078000F000078000F000078000F000078000 F000078000F000078000F000078000F000078000F000078000F000078000F000078000F0 00078000F000078000F000078000F000078001F000078001F000078001F000038002F000 03C004F00001C008F800007030FF80001FC0FF80211F7E9E25>I121 D E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%EndSetup %%Page: 0 1 0 0 bop 364 377 a Fv(On)21 b(Constructing)g(1-1)g(One-W)-6 b(a)n(y)22 b(F)-6 b(unctions)324 504 y Fu(Oded)16 b(Goldreic)o(h)660 486 y Ft(\003)808 504 y Fu(Leonid)h(A)f(Levin)1157 486 y Ft(y)1306 504 y Fu(Noam)f(Nisan)1585 486 y Ft(z)808 606 y Fu(June)h(12,)h(1995)863 823 y Fs(Abstract)176 899 y Fr(W)m(e)e(sho)o(w)g(ho)o(w)g(to)g(construct)h(length-preserving) h(1-1)d(one-w)o(a)o(y)h(functions)g(based)h(on)f(p)q(opular)f(in-)114 949 y(tractabilit)o(y)h(assumptions)g(\(e.g.,)g(RSA,)h(DLP\).)f(Suc)o (h)i(1-1)e(functions)i(should)e(not)h(b)q(e)h(confused)g(with)114 999 y(\(in\014nite\))i(famili)o(es)e(of)h(\(\014nite\))i(one-w)o(a)o(y) e(p)q(erm)o(utations.)32 b(What)18 b(w)o(e)i(w)o(an)o(t)e(and)h(obtain) f(is)h(a)f(single)114 1048 y(\(in\014nite\))c(1-1)f(one-w)o(a)o(y)g (function.)p 0 2416 764 2 v 51 2443 a Fq(\003)69 2459 y Fp(Departmen)o(t)i(of)f(Applied)h(Mathematics)h(and)e(Computer)h (Science,)g(W)m(eizmann)g(Institute)g(of)f(Science,)h(Reho)o(v)o(ot,)g (Israel.)0 2505 y(Email:)24 b Fo(oded@wisd)o(om.)o(we)o(izm)o(ann)o(.a) o(c.i)o(l)p Fp(.)e(Researc)o(h)16 b(w)o(as)g(supp)q(orted)h(in)g(part)f (b)o(y)g(gran)o(t)g(No.)f(92-00226)i(from)e(the)h(United)0 2550 y(States)d({)g(Israel)h(Binational)i(Science)f(F)m(oundation)g (\(BSF\),)e(Jerusalem,)h(Israel.)53 2581 y Fq(y)69 2597 y Fp(Computer)g(Science)g(Departmen)o(t,)g(Boston)f(Univ)o(ersit)o(y)m (,)i(Boston,)e(USA.)g(Email:)18 b Fo(lnd@bu-cs)o(.bu)o(.ac)o(.i)o(l)p Fp(.)53 2628 y Fq(z)69 2644 y Fp(Institute)c(for)f(Computer)g(Science,) h(Hebrew)f(Univ)o(ersit)o(y)m(,)i(Jerusalem,)e(Israel.)18 b(Email:)g Fo(noam@cs.hu)o(ji.)o(ac.)o(il)o Fp(.)943 2769 y Fn(0)p eop %%Page: 1 2 1 1 bop 0 195 a Fm(1)67 b(In)n(tro)r(duction)0 297 y Fn(Giv)o(en)17 b(an)o(y)g(one-w)o(a)o(y)f(p)q(erm)o(utation)g(\(i.e.,)h (a)f(length)i(preserving)f(1-1)f(one-w)o(a)o(y)g(function\),)i(one)f (can)f(easily)0 353 y(construct)j(an)g(e\016cien)o(t)h(pseudorandom)f (generator.)31 b(The)19 b(construction)h(follo)o(ws)f(the)g(sc)o(heme)h (giv)o(en)g(b)o(y)0 409 y(Blum)d(and)g(Micali)g([3],)e(using)i(the)g (fact)e(that)h(ev)o(ery)g(one-w)o(a)o(y)g(function)h(has)f(a)g (hard-core)g(bit)h([5)o(].)23 b(Sp)q(ecif-)0 466 y(ically)l(,)c(assume) f(that)e Fl(f)23 b Fn(is)17 b(suc)o(h)h(a)f(function)h(and)g(let)f Fl(b)g Fn(b)q(e)h(a)f(hard)g(core-bit)h(for)f(it)g(\(i.e.,)g(starting)g (with)h(a)0 531 y(function)e Fl(f)205 514 y Fk(0)231 531 y Fn(w)o(e)f(de\014ne)h Fl(f)5 b Fn(\()p Fl(x;)j(r)q Fn(\))572 506 y Fj(def)577 531 y Fn(=)18 b(\()p Fl(f)675 514 y Fk(0)687 531 y Fn(\()p Fl(x)p Fn(\))p Fl(;)8 b(r)q Fn(\))k(and)j Fl(b)p Fn(\()p Fl(x;)8 b(r)q Fn(\))13 b(as)i(the)f (inner-pro)q(duct)j(mo)q(d)e(2)f(of)h(the)g(strings)g Fl(x)0 587 y Fn(and)g Fl(r)h Fn(when)g(view)o(ed)g(as)f(binary)h(v)o (ectors)e(of)h(length)h Fi(j)p Fl(x)p Fi(j)11 b Fn(=)i Fi(j)p Fl(r)q Fi(j)p Fn(\).)19 b(Then,)c(the)g(pseudorandom)h (generator)e Fl(G)p Fn(,)0 644 y(on)h(input)h(a)f(seed)h Fl(s)f Fn(outputs)g(the)h(sequence)g Fl(b)p Fn(\()p Fl(s)p Fn(\))p Fl(;)8 b(b)p Fn(\()p Fl(f)d Fn(\()p Fl(s)p Fn(\)\))p Fl(;)i(b)p Fn(\()o Fl(f)e Fn(\()p Fl(f)g Fn(\()p Fl(s)p Fn(\)\)\))o Fl(;)j(b)o Fn(\()p Fl(f)1335 627 y Fj(3)1351 644 y Fn(\()p Fl(s)p Fn(\)\))p Fl(;)g(:::)71 700 y Fn(Pseudorandom)16 b(generators)f(can)i(b)q(e)g(constructed)f(also)g(based)h(on)f (arbitrary)g(one-w)o(a)o(y)g(functions)h([8)o(];)0 757 y(y)o(et,)g(the)g(kno)o(wn)g(construction)g(is)h(v)o(ery)f(complex)h (and)f(ine\016cien)o(t.)27 b(In)18 b(fact,)f(it)g(is)h(of)f(no)g (practical)h(v)m(alue.)0 813 y(The)k(construction)f(in)h([6],)g(whic)o (h)g(uses)f(arbitrary)g Fh(r)n(e)n(gular)g Fn(one-w)o(a)o(y)g (functions)h(is)f(more)g(attractiv)o(e)g(in)0 869 y(these)14 b(resp)q(ects,)h(y)o(et)f(it)g(is)h(far)e(less)i(attractiv)o(e)f(than)g (the)g(simple)i(construction)e(outlined)i(ab)q(o)o(v)o(e.)j(A)14 b(similar)0 926 y(situation)f(o)q(ccurs)g(with)g(resp)q(ect)g(to)f(the) h(construction)g(of)f(digital)i(signature)f(sc)o(hemes)g(\(cf.,)f([10)o (])g(vs)g([15]\).)18 b(In)0 982 y(general,)d(1-1)g(one-w)o(a)o(y)g (functions)h(curren)o(tly)g(o\013er)e(simpler)j(and)e(more)g(practical) h(constructions)f(\(of)g(more)0 1039 y(complex)h(primitiv)o(es\))g (than)f(o\013ered)g(b)o(y)g(general)h(one-w)o(a)o(y)e(functions.)71 1095 y(These)h(facts)g(w)o(ere)g(our)g(initial)i(motiv)m(ation)e(for)g (trying)g(to)g(construct)g(length-preserving)h(1-1)f(one-w)o(a)o(y)0 1152 y(functions.)22 b(Suc)o(h)16 b(functions)g(should)h(not)e(b)q(e)h (confused)g(with)g(what)f(is)h(commonly)g(referred)f(to)g(\(esp)q (ecially)0 1208 y(in)i(the)f(\\Crypto)f(Comm)o(unit)o(y"\))f(as)i (\\one-w)o(a)o(y)f(p)q(erm)o(utations")g(and)i(whic)o(h)f(are)g (actually)h(in\014nite)g(sets)f(of)0 1265 y(\014nite)g(functions)f({)f (see)h(de\014nitions)i(b)q(elo)o(w.)j(What)14 b(w)o(e)g(w)o(an)o(t)g (is)h(a)f(single)i(in\014nite)h(function,)e(whic)o(h)g(is)g(b)q(oth)0 1321 y(length-preserving)20 b(and)f(1-1)g(\(and)f(needless)j(to)d(sa)o (y)g(one-w)o(a)o(y\).)30 b(W)l(e)19 b(sho)o(w)f(ho)o(w)g(to)g (construct)h(suc)o(h)g(1-1)0 1378 y(one-w)o(a)o(y)14 b(functions)h(based)g(on)f(p)q(opular)i(in)o(tractabilit)o(y)f (assumptions)g(suc)o(h)f(as)g(the)h(in)o(tractabilit)o(y)g(of)f(DLP)0 1434 y(and)h(in)o(v)o(erting)h(RSA.)71 1490 y(Indeed,)25 b(some)e(\(but)f(not)g(all\))h(of)g(the)f(constructions)h(whic)o(h)h (use)f(length-preserving)h(1-1)e(one-w)o(a)o(y)0 1547 y(functions)14 b(can)g(b)q(e)g(mo)q(di\014ed)h(so)e(that)g(families)h (of)f(one-w)o(a)o(y)g(p)q(erm)o(utations)h(can)f(b)q(e)h(used)g (instead.)20 b(Still)15 b(the)0 1603 y(question)h(of)f(whether)g(the)g (former)g(exists)g(is)h(of)f(b)q(oth)g(theoretical)h(and)f(practical)h (imp)q(ortance.)0 1744 y Fm(2)67 b(One-W)-6 b(a)n(y)23 b(F)-6 b(unctions)24 b(and)f(F)-6 b(amilies)0 1845 y Fg(De\014nition)19 b(1)k Fn(\(one-w)o(a)o(y)12 b(functions\):)21 b Fh(L)n(et)14 b Fl(f)c Fn(:)5 b Fi(f)p Fn(0)p Fl(;)j Fn(1)p Fi(g)956 1828 y Fk(\003)978 1845 y Fi(7!)d(f)p Fn(0)p Fl(;)j Fn(1)p Fi(g)1141 1828 y Fk(\003)1173 1845 y Fh(b)n(e)14 b(a)h Fn(length)f(preserving)i Fh(function)e(which)0 1901 y(is)i(p)n(olynomial-time)g(c)n(omputable.)68 1979 y Fi(\017)23 b Fn(\(strongly)16 b(one-w)o(a)o(y\):)23 b Fl(f)g Fh(is)18 b(c)n(al)r(le)n(d)f Fn(\(strongly\))g Ff(one-w)o(a)o(y)h Fh(if)g(for)h(any)e(pr)n(ob)n(abilistic)h(p)n (olynomial-time)114 2035 y(algorithm)e Fl(A)p Fh(,)h(any)f(p)n(ositive) g(p)n(olynomial)g Fl(p)g Fh(and)g(al)r(l)g(su\016ciently)f(lar)n(ge)h Fl(n)p Fh('s)681 2134 y Fn(Prob)o(\()p Fl(A)p Fn(\()p Fl(f)5 b Fn(\()p Fl(x)p Fn(\)\))12 b Fi(2)h Fl(f)1036 2115 y Fk(\000)p Fj(1)1080 2134 y Fl(f)5 b Fn(\()p Fl(x)p Fn(\)\))12 b Fl(<)1283 2103 y Fn(1)p 1252 2124 86 2 v 1252 2165 a Fl(p)p Fn(\()p Fl(n)p Fn(\))114 2241 y Fh(wher)n(e)19 b(the)g(pr)n(ob)n(ability)g(is)g(taken)f(uniformly)i(over)f Fl(x)f Fi(2)g(f)p Fn(0)p Fl(;)8 b Fn(1)p Fi(g)1240 2224 y Fe(n)1260 2241 y Fh(,)20 b(and)f(the)h(internal)e(c)n(oin)g(tosses)g (of)114 2297 y(algorithm)e Fl(A)p Fh(.)68 2385 y Fi(\017)23 b Fn(\(w)o(eakly)15 b(one-w)o(a)o(y\):)k Fl(f)j Fh(is)16 b(c)n(al)r(le)n(d)f Ff(w)o(eakly)g(one-w)o(a)o(y)h Fh(if)g(ther)n(e)h (exists)e(a)i(p)n(ositive)f(p)n(olynomial)g Fl(p)g Fh(so)g(that)114 2441 y(for)g(any)g(pr)n(ob)n(abilistic)g(p)n(olynomial-time)g (algorithm)h Fl(A)f Fh(and)g(al)r(l)g(su\016ciently)g(lar)n(ge)g Fl(n)p Fh('s)681 2540 y Fn(Prob)o(\()p Fl(A)p Fn(\()p Fl(f)5 b Fn(\()p Fl(x)p Fn(\)\))17 b Fl(=)-28 b Fi(2)13 b Fl(f)1036 2521 y Fk(\000)p Fj(1)1080 2540 y Fl(f)5 b Fn(\()p Fl(x)p Fn(\)\))12 b Fl(>)1283 2509 y Fn(1)p 1252 2530 V 1252 2571 a Fl(p)p Fn(\()p Fl(n)p Fn(\))114 2644 y Fh(wher)n(e)k(the)g(pr)n(ob)n(ability)g(is)g(as)g(ab)n(ove.)943 2769 y Fn(1)p eop %%Page: 2 3 2 2 bop 0 195 a Fn(\(Note)17 b(that)g Fl(f)c Fn(:)c Fi(f)p Fn(0)p Fl(;)f Fn(1)p Fi(g)401 179 y Fk(\003)427 195 y Fi(7!)h(f)p Fn(0)p Fl(;)f Fn(1)p Fi(g)594 179 y Fk(\003)629 195 y Fn(is)18 b(1-1)f(if)h Fl(f)5 b Fn(\()p Fl(x)p Fn(\))16 b Fi(6)p Fn(=)g Fl(f)5 b Fn(\()p Fl(y)r Fn(\))17 b(for)g(all)h Fl(x)f Fi(6)p Fn(=)g Fl(y)r Fn(\).)26 b(In)18 b(case)f Fl(f)5 b Fn(\()p Fl(x)p Fn(\))16 b Fi(6)p Fn(=)h Fl(f)5 b Fn(\()p Fl(y)r Fn(\))17 b(for)g(all)0 252 y(but)h(a)f(negligible)j (fraction)d(of)g(the)g(pairs)h(\()p Fl(x;)8 b(y)r Fn(\))16 b(w)o(e)h(sa)o(y)g(that)f Fl(f)23 b Fn(is)18 b Ff(almo)o(st)d(1-1)p Fn(.)26 b(Namely)l(,)19 b(an)e(almost)g(1-1)0 308 y(function)f Fl(f)k Fn(satis\014es,)15 b(for)g(ev)o(ery)g(p)q(ositiv)o(e)h(p)q (olynomial)h Fl(p)e Fn(and)g(all)i(su\016cien)o(tly)f(large)f Fl(n)p Fn('s,)701 424 y(Prob)o(\()p Fl(f)5 b Fn(\()p Fl(x)p Fn(\))g(=)g Fl(f)g Fn(\()p Fl(y)r Fn(\)\))12 b Fl(<)1150 393 y Fn(1)p 1119 413 86 2 v 1119 455 a Fl(p)p Fn(\()p Fl(n)p Fn(\))0 548 y(where)j(the)h(probabilit)o(y)g(is)g(tak)o (en)f(uniformly)h(and)f(indep)q(eden)o(tly)j(o)o(v)o(er)c(all)j Fl(x;)8 b(y)13 b Fi(2)g(f)p Fn(0)p Fl(;)8 b Fn(1)p Fi(g)1575 531 y Fe(n)1596 548 y Fn(.)0 650 y Fg(De\014nition)19 b(2)k Fn(\(family)11 b(of)g(one-w)o(a)o(y)g(p)q(erm)o(utations)g({)f (simpli\014ed)k(v)o(ersion\):)19 b Fh(A)12 b(set)g(of)h(\014nite)e(p)n (ermutations,)0 722 y Fg(F)i Fn(=)f Fi(f)p Fl(f)138 729 y Fe(i)157 722 y Fn(:)5 b Fl(D)213 729 y Fe(i)232 697 y Fr(1-1)236 722 y Fi(7!)11 b Fl(D)330 729 y Fe(i)343 722 y Fi(g)366 729 y Fe(i)p Fk(2)p Fe(I)419 722 y Fh(,)16 b(is)g(c)n(al)r(le)n(d)g(a)g Ff(family)c(of)j(one-w)o(a)o(y)g(p)q (ermutations)g Fh(if)h(the)h(fol)r(lowing)f(c)n(onditions)f(hold)68 813 y Fi(\017)23 b Fn(\(e\016cien)o(t)14 b(ev)m(aluation\):)21 b Fh(ther)n(e)16 b(exists)e(a)i(p)n(olynomial-time)f(algorithm)h(that)g (on)f(input)g(an)g(index)g Fn(\(of)f(a)114 870 y(p)q(erm)o(utation\))i Fl(i)c Fi(2)h Fl(I)20 b Fh(and)c(a)g(domain)h(element)f Fl(x)c Fi(2)h Fl(D)1082 877 y Fe(i)1112 870 y Fh(r)n(eturns)j Fl(f)1291 877 y Fe(i)1305 870 y Fn(\()p Fl(x)p Fn(\))p Fh(.)68 963 y Fi(\017)23 b Fn(\(e\016cien)o(t)d(index)i(selection\):)31 b Fh(ther)n(e)21 b(exists)f(a)h(pr)n(ob)n(abilistic)f(algorithm)i Fl(S)h Fh(that)f(on)e(input)h Fl(n)p Fh(,)i(runs)114 1019 y(for)16 b Fn(p)q(oly)r(\()p Fl(n)p Fn(\))f Fh(time)i(and)f(r)n (eturns)g(a)g(uniformly)h(distribute)n(d)f(index)g(of)g(length)g Fl(n)g Fn(\(i.e.,)f(an)g Fl(i)f Fn(uniformly)114 1076 y(distributed)i(in)g Fl(I)e Fi(\\)c(f)p Fn(0)p Fl(;)e Fn(1)p Fi(g)586 1059 y Fe(n)607 1076 y Fn(\))p Fh(.)68 1168 y Fi(\017)23 b Fn(\(e\016cien)o(t)18 b(domain)g(sampling\):)25 b Fh(ther)n(e)19 b(exists)f(a)g(pr)n(ob)n(abilistic)g(p)n (olynomial-time)g(algorithm)h Fl(D)h Fh(that)114 1225 y(on)c(input)g(an)g(index)g Fl(i)c Fi(2)h Fl(I)t Fh(,)j(r)n(eturns)g(a) g(uniformly)h(distribute)n(d)f(element)g(of)g Fl(D)1494 1232 y Fe(i)1508 1225 y Fh(.)68 1318 y Fi(\017)23 b Fn(\(one-w)o(a)o (yness\):)c Fh(F)m(or)d(any)g(pr)n(ob)n(abilistic)f(p)n(olynomial-time) h(algorithm)h Fl(A)p Fh(,)f(any)g(p)n(ositive)g(p)n(olynomial)114 1374 y Fl(p)g Fh(and)g(al)r(l)g(su\016ciently)g(lar)n(ge)f Fl(n)p Fh('s)723 1490 y Fn(Prob\()p Fl(A)p Fn(\()p Fl(i;)8 b(f)949 1497 y Fe(i)961 1490 y Fn(\()p Fl(x)p Fn(\)\))k(=)h Fl(x)p Fn(\))f Fl(<)1241 1459 y Fn(1)p 1210 1480 V 1210 1521 a Fl(p)p Fn(\()p Fl(n)p Fn(\))114 1614 y Fh(wher)n(e)k(the)h(pr)n (ob)n(ability)f(is)g(taken)h(uniformly)f(over)h Fl(i)c Fi(2)g Fl(I)h Fi(\\)d(f)p Fn(0)p Fl(;)d Fn(1)p Fi(g)1277 1597 y Fe(n)1297 1614 y Fh(,)17 b Fl(x)c Fi(2)g Fl(D)1448 1621 y Fe(i)1462 1614 y Fh(,)j(and)h(the)g(internal)e(c)n(oin)114 1670 y(tosses)g(of)h(algorithm)h Fl(A)p Fh(.)0 1773 y Fn(In)c(the)f Ff(non-simpli\014ed)g(version)p Fn(,)g(b)q(oth)h (probabilistic)h(algorithms)e(men)o(tioned)h(ab)q(o)o(v)o(e)f(\(i.e.,)g Fl(S)j Fn(and)d Fl(D)q Fn(\))g(are)g(al-)0 1830 y(lo)o(w)o(ed)g(to)e (pro)q(duce)j(output)e(with)h(only)g(non-negligible)j(probabilit)o(y)e (\(i.e.,)e(probabilit)o(y)i(at)e(least)h(1)p Fl(=)p Fn(p)q(oly)q(\()p Fl(n)p Fn(\)\).)0 1886 y(F)l(urthermore,)h(giv)o(en)g(these)h (algorithms)f(ha)o(v)o(e)f(pro)q(duced)j(an)e(output,)g(the)g(output)g (is)g(allo)o(w)o(ed)h(to)e(b)q(e)i(wrong)0 1943 y(\(i.e.,)19 b(out)f(of)h(the)g(target)e(set)i(or)f(non-uniformly)i(distributed\))g (with)f(negligible)j(probabilit)o(y)e(\(e.g.,)e(with)0 1999 y(probabilit)o(y)e(at)f(most)f(2)422 1982 y Fk(\000)p Fe(n)471 1999 y Fn(\).)71 2055 y(Analogously)k(to)g(De\014nition)h(1,)f (families)i(of)d(p)q(erm)o(utations)h(can)g(b)q(e)h(de\014ned)h(to)d(b) q(e)i Fh(we)n(akly)e Fn(one-w)o(a)o(y)l(,)0 2112 y(rather)e(than)g (\(strongly\))f(one-w)o(a)o(y)l(.)0 2255 y Fm(3)67 b(T)-6 b(ransforming)23 b(One-W)-6 b(a)n(y)23 b(F)-6 b(amilies)24 b(in)n(to)g(F)-6 b(unctions)0 2356 y Fn(Clearly)l(,)21 b(an)o(y)e(family)h(of)f(one-w)o(a)o(y)f(p)q(erm)o(utations)h(can)h(b)q (e)g(con)o(v)o(erted)f(in)o(to)g(a)g(single)h(one-w)o(a)o(y)f (function;)0 2418 y(namely)l(,)j Fl(f)5 b Fn(\()p Fl(r)o(;)j(s)p Fn(\))317 2393 y Fj(def)323 2418 y Fn(=)26 b Fl(f)406 2425 y Fe(i)420 2418 y Fn(\()p Fl(x)p Fn(\),)21 b(where)f Fl(i)h Fn(=)g Fl(S)s Fn(\()p Fl(n;)8 b(r)q Fn(\))19 b(is)i(the)f(index) h(selected)h(using)f(coin-tosses)g Fl(r)g Fn(and)f Fl(x)h Fn(=)0 2475 y Fl(D)q Fn(\()p Fl(i;)8 b(s)p Fn(\))17 b Fi(2)i Fl(D)237 2482 y Fe(i)269 2475 y Fn(is)g(the)g(elemen)o(t)g (selected)h(on)f(input)g Fl(i)g Fn(and)f(coin-tosses)h Fl(s)p Fn(.)31 b(\(P)o(adding)19 b(can)g(b)q(e)g(applied,)i(if)0 2531 y(necessary)l(,)14 b(to)e(mak)o(e)h Fl(f)19 b Fn(length)14 b(preserving.\))19 b(Ho)o(w)o(ev)o(er,)13 b(this)g(pro)q(cedure)i(do)q (es)e(not)g(necessarily)i(yield)g(a)e(1-1)0 2588 y(function;)i (furthermore,)f(for)g(most)g(natural)h(examples)h(suc)o(h)f(as)f(RSA,)h (DLP)l(,)g(etc.,)f(the)h(resulting)h(function)0 2644 y(will)h(b)q(e)f(man)o(y-to-one.)943 2769 y(2)p eop %%Page: 3 4 3 3 bop 71 195 a Fn(An)15 b(alternativ)o(e)g(construction,)g(whic)o(h)h (do)q(es)f(yield)i(a)d(1-1)h(one-w)o(a)o(y)f(function,)i(is)f(p)q (ossible)i(under)f(some)0 252 y(additional)j(conditions,)h(as)d (demonstrated)h(b)q(elo)o(w.)28 b(In)19 b(fact,)e(the)h(conditions)i (are)d(de\014ned)i(to)f(mak)o(e)f(this)0 308 y(natural)e(construction)f (w)o(ork)g(and)h(the)f(thrust)g(of)g(this)h(pap)q(er)g(is)g(in)h (demonstrating)e(that)g(these)g(conditions)0 364 y(can)h(b)q(e)h(met)f (under)h(reasonable)g(and)f(p)q(opular)h(assumptions)f(\(see)h(next)f (section\).)0 486 y Fd(3.1)56 b(The)18 b(Conditions)0 572 y Fn(Let)d Fg(F)g Fn(b)q(e)g(a)g(family)g(of)f(one-w)o(a)o(y)g(p)q (erm)o(utations)h(and)g(that)f(let)h Fl(q)r Fn(\()p Fl(n)p Fn(\))g(denote)g(the)g(n)o(um)o(b)q(er)g(of)f(coins)h(\015ipp)q(ed)0 628 y(b)o(y)g(the)f(index)i(selection)g(algorithm)f Fl(S)i Fn(on)d(input)i Fl(n)p Fn(.)k(W)l(e)14 b(consider)i(the)f(follo)o(wing) g(conditions)h(that)e Fg(F)g Fn(ma)o(y)0 685 y(satisfy)0 791 y Fg(De\014nition)19 b(3)k Fn(\(additional)16 b(conditions\))68 885 y Fi(\017)23 b Ff(augmented)c(one-w)o(a)o(yness:)32 b Fh(F)m(or)21 b(any)g(pr)n(ob)n(abilistic)f(p)n(olynomial-time)h (algorithm)h Fl(A)p Fh(,)g(any)f(p)n(ositive)114 941 y(p)n(olynomial)15 b Fl(p)i Fh(and)f(al)r(l)g(su\016ciently)f(lar)n(ge) h Fl(n)p Fh('s)680 1060 y Fn(Prob)o(\()p Fl(A)p Fn(\()p Fl(r)o(;)8 b(f)909 1067 y Fe(S)r Fj(\()p Fe(n;r)q Fj(\))1004 1060 y Fn(\()p Fl(x)p Fn(\)\))k(=)h Fl(x)p Fn(\))f Fl(<)1284 1029 y Fn(1)p 1253 1050 86 2 v 1253 1091 a Fl(p)p Fn(\()p Fl(n)p Fn(\))114 1191 y Fh(wher)n(e)18 b(the)h(pr)n(ob)n(ability)g(is)f (taken)h(uniformly)f(over)h Fl(r)f Fi(2)g(f)p Fn(0)p Fl(;)8 b Fn(1)p Fi(g)1232 1174 y Fe(q)q Fj(\()p Fe(n)p Fj(\))1294 1191 y Fh(,)20 b Fl(x)d Fi(2)g Fl(D)1456 1198 y Fe(S)r Fj(\()p Fe(n;r)q Fj(\))1552 1191 y Fh(,)j(and)e(the)h (internal)114 1247 y(c)n(oin)c(tosses)g(of)i(algorithm)g Fl(A)p Fh(.)114 1304 y Fn(\(Namely)l(,)h(the)f(p)q(erm)o(utations)h (are)f(hard)g(to)g(in)o(v)o(ert)h(ev)o(en)g(when)g(the)f(in)o(v)o (erting)h(algorithm)g(is)g(giv)o(en)114 1360 y(the)d(random)g(coins)h (used)f(to)g(generate)g(the)g(index)i(of)d(the)i(p)q(erm)o(utation.\)) 68 1454 y Fi(\017)23 b Ff(canonical)c(domain)d(sampling:)25 b Fh(The)19 b(domain-sampling)g(algorithm)h(may)g(c)n(onsist)e(of)i (uniformly)g(se-)114 1510 y(le)n(cting)14 b(a)i(string)g(of)g(sp)n(e)n (ci\014c)e Fn(\(easy)g(to)g(determine\))j Fh(length)e(and)h(testing)f (whether)i(the)f(string)g(r)n(esides)114 1567 y(in)f(the)i(domain.)k (In)15 b(other)i(wor)n(ds,)g(we)f(r)n(e)n(quir)n(e)165 1661 y Fg({)23 b Fn(\(recognizable)g(domain\):)32 b Fh(Ther)n(e)22 b(exists)g(a)g(p)n(olynomial-time)g(algorithm)h(that)g(on)f(input)h(an) 214 1717 y(index)16 b Fl(i)c Fi(2)h Fl(I)20 b Fh(and)c(a)g(string)g Fl(x)g Fh(de)n(cides)g(if)g Fl(x)d Fi(2)g Fl(D)1065 1724 y Fe(i)1078 1717 y Fh(.)165 1790 y Fg({)23 b Fn(\(non-negligible)13 b(domain\):)19 b Fh(Ther)n(e)11 b(exists)g(a)h(p)n(olynomial-time)g(c)n (omputable)h(function)e Fl(l)6 b Fn(:)j Fg(I)-24 b(N)12 b Fi(7!)e Fg(I)-25 b(N)214 1847 y Fh(and)16 b(a)g(p)n(ositive)g(p)n (olynomial)g Fl(p)p Fn(\()p Fi(\001)p Fn(\))f Fh(so)h(that)h Fl(D)1010 1854 y Fe(i)1036 1847 y Fi(\022)c(f)p Fn(0)p Fl(;)8 b Fn(1)p Fi(g)1197 1830 y Fe(l)p Fj(\()p Fe(n)p Fj(\))1271 1847 y Fh(and)16 b Fi(j)p Fl(D)1410 1854 y Fe(i)1423 1847 y Fi(j)c Fl(>)1525 1829 y Fj(1)p 1501 1836 64 2 v 1501 1862 a Fe(p)p Fj(\()p Fe(n)p Fj(\))1580 1847 y Fi(\001)e Fn(2)1626 1830 y Fe(l)p Fj(\()p Fe(n)p Fj(\))0 1968 y Fd(3.2)56 b(The)18 b(Construction)0 2054 y Fn(Giv)o(en)i(a)g(family)h(of)e(one-w)o(a)o(y)g(p)q(erm)o(utations)h (that)f(satis\014es)i(the)f(additional)h(conditions,)h(w)o(e)e (explicitly)0 2111 y(construct)15 b(a)g(1-1)g(one-w)o(a)o(y)f(function) i(as)f(follo)o(ws.)0 2217 y Fg(Construction)j(1)23 b Fn(\(simple)e(v)o(ersion\):)29 b Fh(L)n(et)19 b Fg(F)i Fh(b)n(e)e(a)i(family)g(of)f(p)n(ermutations)h(with)g(an)f(index)g (sele)n(ction)0 2273 y(algorithm)i Fl(S)h Fh(that)f(uses)e Fl(q)r Fn(\()p Fi(\001)p Fn(\))g Fh(c)n(oins)g(and)h(having)f(domains)h Fl(D)1138 2280 y Fe(i)1152 2273 y Fh('s)f(which)i(ar)n(e)f(subsets)f (of)h Fi(f)p Fn(0)p Fl(;)8 b Fn(1)p Fi(g)1749 2257 y Fe(l)p Fj(\()p Fk(j)p Fe(i)p Fk(j)p Fj(\))1817 2273 y Fh(,)22 b(for)0 2330 y(some)16 b(function)g Fl(l)q Fn(\()p Fi(\001)p Fn(\))p Fh(.)j(We)e(c)n(onstruct)f(the)g(function)g Fl(f)22 b Fh(as)16 b(fol)r(lows)437 2465 y Fl(f)5 b Fn(\()p Fl(r)o(;)j(s)p Fn(\))573 2440 y Fj(def)578 2465 y Fn(=)631 2393 y Fc(\()685 2441 y Fn(\()p Fl(r)o(;)g(f)766 2448 y Fe(i)778 2441 y Fn(\()p Fl(s)p Fn(\)\))41 b Fh(if)16 b Fl(s)d Fi(2)g Fl(D)1053 2448 y Fe(i)1067 2441 y Fh(,)j(wher)n(e)g Fl(i)1254 2416 y Fj(def)1259 2441 y Fn(=)i Fl(S)s Fn(\()p Fl(n;)8 b(r)q Fn(\))685 2498 y(\()p Fl(r)o(;)g(s)p Fn(\))111 b Fh(otherwise)0 2604 y(wher)n(e)16 b Fl(r)e Fi(2)f(f)p Fn(0)p Fl(;)8 b Fn(1)p Fi(g)319 2587 y Fe(q)q Fj(\()p Fe(n)p Fj(\))398 2604 y Fh(and)16 b Fl(s)d Fi(2)g(f)p Fn(0)p Fl(;)8 b Fn(1)p Fi(g)676 2587 y Fe(l)p Fj(\()p Fe(n)p Fj(\))733 2604 y Fh(,)943 2769 y Fn(3)p eop %%Page: 4 5 4 4 bop 0 195 a Fg(Prop)q(osition)19 b(1)j Fn(:)33 b Fh(The)22 b(function)f Fl(f)28 b Fh(is)21 b(1-1)i(and)f(length)g(pr)n (eserving.)37 b(If)22 b Fg(F)g Fh(is)f(a)i(family)f(of)g(one-way)0 252 y(p)n(ermutations)17 b(satisfying)f(the)i(additional)f(c)n (onditions)f(of)h(De\014nition)f(3)i(then)f Fl(f)22 b Fh(is)16 b(we)n(akly)h(one-way.)24 b(The)0 308 y(latter)16 b(holds)h(even)e(if)h Fg(F)g Fh(is)g(only)g(we)n(akly)g(one-way)h Fn(\(and)e(satis\014es)g(the)g(additional)i(conditions\))p Fh(.)0 390 y Fg(pro)q(of:)h Fn(By)11 b(de\014nition)i Fl(f)j Fn(is)c(length-preserving.)20 b(Let)11 b Fl(G)985 397 y Fe(n)1019 390 y Fn(b)q(e)g(the)h(set)e(of)h(pairs)h(\()p Fl(r)o(;)c(s)p Fn(\))i Fi(2)j(f)p Fn(0)p Fl(;)8 b Fn(1)p Fi(g)1637 373 y Fe(q)q Fj(\()p Fe(n)p Fj(\))1702 390 y Fi(\002)r(f)p Fn(0)p Fl(;)g Fn(1)p Fi(g)1852 373 y Fe(l)p Fj(\()p Fe(n)p Fj(\))0 446 y Fn(so)i(that)g Fl(s)j Fi(2)g Fl(D)260 453 y Fe(S)r Fj(\()p Fe(n;r)q Fj(\))367 446 y Fn(holds)f(and)f(let)g Fl(B)661 453 y Fe(n)695 446 y Fn(b)q(e)g(the)g(set)g(of)f(the)h(other)g(pairs)g(\(i.e.,)g Fl(B)1370 453 y Fe(n)1405 446 y Fn(=)i(\()p Fi(f)p Fn(0)p Fl(;)8 b Fn(1)p Fi(g)1584 430 y Fe(q)q Fj(\()p Fe(n)p Fj(\))1648 446 y Fi(\002)q(f)p Fn(0)p Fl(;)g Fn(1)p Fi(g)1797 430 y Fe(l)p Fj(\()p Fe(n)p Fj(\))1855 446 y Fn(\))q Fi(\000)0 503 y Fl(G)36 510 y Fe(n)58 503 y Fn(\).)36 b(The)21 b(k)o(ey)f(observ)m(ation)h(is)g(that)f(if)h(\()p Fl(r)o(;)8 b(s)p Fn(\))20 b Fi(2)i Fl(G)966 510 y Fe(n)1009 503 y Fn(then,)g(letting)f Fl(i)g Fn(=)h Fl(S)s Fn(\()p Fl(n;)8 b(r)q Fn(\),)20 b Fl(s)i Fi(2)g Fl(D)1678 510 y Fe(i)1712 503 y Fn(holds)f(and)0 559 y Fl(f)22 566 y Fe(i)36 559 y Fn(\()p Fl(s)p Fn(\))12 b Fi(2)h Fl(D)186 566 y Fe(i)213 559 y Fn(\(and)g Fl(f)5 b Fn(\()p Fl(r)o(;)j(s)p Fn(\))j Fi(2)h Fl(G)531 566 y Fe(n)554 559 y Fn(\))g(follo)o(ws.)20 b(On)13 b(the)g(other)g(hand,)h(if)f(\()p Fl(r)o(;)8 b(s)p Fn(\))j Fi(2)i Fl(B)1367 566 y Fe(n)1403 559 y Fn(then)g Fl(f)5 b Fn(\()p Fl(r)o(;)j(s)p Fn(\))j(=)i(\()p Fl(r)o(;)8 b(s)p Fn(\))j Fi(2)i Fl(B)1874 566 y Fe(n)1897 559 y Fn(.)0 616 y(Th)o(us,)i Fl(f)20 b Fn(maps)15 b Fl(G)325 623 y Fe(n)362 616 y Fn(\(resp.,)g Fl(B)536 623 y Fe(n)559 616 y Fn(\))f(to)h(itself)h(and)f(furthermore)g(the)g (mapping)h(induced)h(on)e Fl(G)1630 623 y Fe(n)1668 616 y Fn(\(rep.,)f Fl(B)1823 623 y Fe(n)1846 616 y Fn(\))h(is)0 672 y(1-1.)k(It)d(follo)o(ws)f(that)f Fl(f)21 b Fn(is)15 b(1-1.)71 729 y(The)d(function)i Fl(f)k Fn(is)13 b(p)q(olynimal-time)i (computable)e(b)o(y)g(virtue)g(of)f(the)g(\014rst)h(t)o(w)o(o)e (e\016ciency)j(conditions)g(of)0 785 y Fg(F)g Fn(and)h(the)f (additional)i(`recognizable)g(domain')e(condition.)21 b(By)15 b(the)f(additional)i(`non-negligible)h(domain')0 841 y(condition)i(w)o(e)f(kno)o(w)f(that)g Fl(G)530 848 y Fe(n)570 841 y Fn(forms)g(a)g(non-negligible)k(fraction)d(of)f Fl(G)1292 848 y Fe(n)1327 841 y Fi([)12 b Fl(B)1403 848 y Fe(n)1443 841 y Fn(and)18 b(b)o(y)g(the)g(`augmen)o(ted)0 898 y(one-w)o(a)o(yness')h(condition)i(w)o(e)e(infer)h(that)f Fl(f)24 b Fn(is)c(hard)g(to)f(in)o(v)o(ert)g(on)h Fl(G)1266 905 y Fe(n)1288 898 y Fn(.)33 b(Th)o(us,)20 b(w)o(e)f(conclude)j(that)c Fl(f)25 b Fn(is)0 954 y(w)o(eakly)15 b(one-w)o(a)o(y)l(.)20 b(In)c(fact,)e(the)i(latter)f(conclusion)i(remain)f(v)m(alid)h(ev)o(en) e(if)h(the)f(family)h(of)f(p)q(erm)o(utations)h Fg(F)0 1011 y Fn(is)g(only)f(w)o(eakly)h(one-w)o(a)o(y)l(.)j Fb(2)0 1103 y Fg(Remark:)k Fn(The)17 b(function)h Fl(f)k Fn(\(constructed)16 b(ab)q(o)o(v)o(e\))h(ma)o(y)f(b)q(e)i(only)f(w)o (eakly)g(one-w)o(a)o(y)f(since)i(it)g(equals)f(the)0 1160 y(iden)o(tit)o(y)f(transformation)e(for)h(a)h(part)f(of)g(its)g (domain)h(and)g(this)g(part)f(ma)o(y)g(ha)o(v)o(e)g(non-negligible)k (measure.)0 1216 y(T)l(o)14 b(get)g(a)g(\(strongly\))g(one-w)o(a)o(y)g (function,)h(one)f(ma)o(y)g(apply)i(the)e(transformation)f(in)j([4)o(]) e(to)g(the)g(function)i Fl(f)5 b Fn(.)0 1273 y(\(In)15 b(fact,)g(degenerate)g(v)o(ersions)h(of)e(the)i(transformation)d(in)j ([4])f(su\016ce)g(for)g(this)g(purp)q(ose.\))0 1365 y(The)h(ab)q(o)o(v) o(e)f(construction)g(is)h(stated)f(with)h(resp)q(ect)g(to)f(the)g (simpli\014ed)k(de\014nition)e(of)e(a)g(family)h(of)f(one-w)o(a)o(y)0 1421 y(p)q(erm)o(utations.)20 b(Recall)c(that)e(in)h(the)g (non-simpli\014ed)i(v)o(ersion,)e(the)f(index-selectin)q(g)j (algorithm,)d Fl(S)s Fn(,)g(is)h(only)0 1478 y(required)f(to)f(ha)o(v)o (e)f(an)h(output)g(with)h(non-negligible)i(probabilit)o(y)e(\(i.e.,)f (the)g(probabilit)o(y)i(is)e(b)q(ounded)i(b)q(elo)o(w)0 1534 y(b)o(y)e(1)p Fl(=p)p Fn(\()p Fl(n)p Fn(\))g(where)g Fl(p)h Fn(is)g(some)f(\014xed)h(p)q(ositiv)o(e)g(p)q(olynomial\).)21 b(F)l(urthermore,)13 b Fl(S)j Fn(is)e(allo)o(w)o(ed)g(to)e(err)i (\(i.e.,)f(ha)o(v)o(e)0 1591 y(output)h(not)f(in)i Fl(I)t Fn(\))e(with)h(a)g(negligible)j(probabilit)o(y)l(.)k(F)l(or)13 b(the)h(general)g(case,)g(w)o(e)g(rede\014ne)h(the)f(function)h Fl(f)k Fn(as)0 1647 y(follo)o(ws)0 1729 y Fg(Construction)f(2)23 b Fn(\(complex)16 b(v)o(ersion\):)21 b Fh(L)n(et)15 b Fg(F)e Fn(=)g Fi(f)p Fl(f)968 1736 y Fe(i)987 1729 y Fn(:)5 b Fl(D)1043 1736 y Fe(i)1062 1704 y Fr(1-1)1067 1729 y Fi(7!)10 b Fl(D)1160 1736 y Fe(i)1174 1729 y Fi(g)1197 1736 y Fe(i)p Fk(2)p Fe(I)1266 1729 y Fh(b)n(e)16 b(a)g(family)h(of)f (p)n(ermutations)h(with)0 1785 y(an)j(index-sele)n(cting)d(algorithm,) 22 b Fl(S)s Fh(,)e(which)g(pr)n(o)n(duc)n(es)g(output)h(with)f(non-ne)n (gligible)d(pr)n(ob)n(ability)j(and)g(errs)0 1842 y(with)d(ne)n (gligible)d(pr)n(ob)n(ability.)20 b(We)d(c)n(onstruct)f(the)g(function) g Fl(f)22 b Fh(as)16 b(fol)r(lows)416 1953 y Fl(f)5 b Fn(\()p Fl(r)o(;)j(s)p Fn(\))552 1928 y Fj(def)557 1953 y Fn(=)610 1881 y Fc(\()664 1930 y Fn(\()p Fl(r)o(;)g(f)745 1937 y Fe(i)757 1930 y Fn(\()p Fl(s)p Fn(\)\))41 b Fh(if)16 b Fl(i)946 1905 y Fj(def)951 1930 y Fn(=)i Fl(S)s Fn(\()p Fl(n;)8 b(r)q Fn(\))j Fi(6)p Fn(=)i Fi(?)j Fh(and)h Fl(s)c Fi(2)f Fl(D)1454 1937 y Fe(i)664 1986 y Fn(\()p Fl(r)o(;)c(s)p Fn(\))111 b Fh(otherwise)0 2071 y(wher)n(e)18 b(the)g(c)n(onvention)e (is)i(that)g(in)f(c)n(ase,)h(on)f(input)h Fl(n)g Fh(and)g(c)n(oin)f (tosses)g Fl(r)f Fi(2)g(f)p Fn(0)p Fl(;)8 b Fn(1)p Fi(g)1502 2055 y Fe(q)q Fj(\()p Fe(n)p Fj(\))1565 2071 y Fh(,)18 b(the)g(algorithm)g Fl(S)0 2136 y Fh(halts)e(with)h(no)f(output)i(then) e Fl(S)s Fn(\()p Fl(n;)8 b(r)q Fn(\))662 2111 y Fj(def)667 2136 y Fn(=)19 b Fi(?)f Fl(=)-28 b Fi(2)13 b(f)p Fn(0)p Fl(;)8 b Fn(1)p Fi(g)925 2120 y Fk(\003)942 2136 y Fh(.)0 2218 y Fg(Prop)q(osition)19 b(2)j Fn(:)e Fh(The)14 b(function)g Fl(f)19 b Fh(is)14 b(length)g(pr)n(eserving)f(and)h(almost)h(1-1,)g (and)f(in)g(c)n(ase)g Fl(S)i Fh(never)e(errs)g Fl(f)0 2274 y Fh(is)e(1-1.)20 b(If)11 b Fg(F)h Fh(is)g(a)g(family)h(of)f (one-way)g(p)n(ermutations)h(satisfying)e(the)h(additional)h(c)n (onditions)e(of)h(De\014nition)f(3)0 2331 y(then)18 b Fl(f)24 b Fh(is)18 b(we)n(akly)g(one-way.)29 b(The)18 b(latter)g(holds)h(even)f(if)g Fg(F)h Fh(is)f(only)g(we)n(akly)g (one-way)h Fn(\(and)e(satis\014es)h(the)0 2387 y(additional)f (conditions\))p Fh(.)0 2469 y Fg(pro)q(of:)h Fn(In)13 b(case)f(algorithm)g Fl(S)i Fn(nev)o(er)e(errs,)g(the)g(pro)q(of)f(is)i (similar)g(to)e(the)h(pro)q(of)g(of)f(the)h(previous)h(prop)q(osition)0 2531 y(\(i.e.,)i Fl(G)140 2538 y Fe(n)179 2531 y Fn(is)h(de\014ned)h (as)f(the)g(set)g(of)f(all)i(pairs)f(\()p Fl(r)o(;)8 b(s)p Fn(\))14 b(so)i(that)f Fl(i)1115 2506 y Fj(def)1121 2531 y Fn(=)k Fl(S)s Fn(\()p Fl(n;)8 b(r)q Fn(\))k Fi(6)p Fn(=)i Fi(?)i Fn(and)h Fl(s)d Fi(2)g Fl(D)1631 2538 y Fe(i)1644 2531 y Fn(\).)22 b(Otherwise,)0 2588 y(w)o(e)13 b(observ)o(e)g(that)g(the)h(collision)h(probabilit)o(y)g(of)e Fl(f)19 b Fn(is)14 b(b)q(ouded)g(ab)q(o)o(v)o(e)f(b)o(y)h(the)f (probabilit)o(y)i(that)e Fl(S)i Fn(errs)f(\(and)0 2644 y(outputs)h(a)g(string)g(not)g(in)h Fl(I)t Fn(\).)j(Since)e(this)e (happ)q(ens)h(with)g(negligible)i(probabilit)o(y)l(,)e(w)o(e)f(are)g (done.)20 b Fb(2)943 2769 y Fn(4)p eop %%Page: 5 6 5 5 bop 0 195 a Fm(4)67 b(Applying)25 b(the)d(T)-6 b(ransformation)0 297 y Fn(Using)16 b(the)g(transformation)e(sp)q(eci\014ed)k(in)f(the)e (previous)i(section,)f(w)o(e)f(sho)o(w)g(ho)o(w)g(to)g(construct)h(a)f (1-1)g(one-)0 353 y(w)o(a)o(y)j(function)i(based)f(on)g(one)g(of)g(sev) o(eral)g(p)q(opular)h(in)o(tractabilit)o(y)g(assumptions.)32 b(T)l(o)19 b(this)g(end,)h(w)o(e)f(use)0 409 y(these)13 b(in)o(tractabilit)o(y)h(assumptions)f(in)h(order)e(to)h(construct)f (families)j(of)d(one-w)o(a)o(y)g(p)q(erm)o(utations)h(satisfying)0 466 y(the)g(additional)i(conditions)f(of)f(De\014nition)i(3.)k(Before) 13 b(presen)o(ting)h(these)f(constructions,)h(w)o(e)f(wish)g(to)g (stress)0 522 y(an)i(imp)q(ortan)o(t)g(asp)q(ect)g(regarding)h(them;)e (namely)l(,)i(their)g(\\securit)o(y".)0 644 y Fd(Securit)n(y)0 730 y Fn(The)h Ff(securit)o(y)h Fn(of)f(a)f(one-w)o(a)o(y)h(function)g Fl(f)23 b Fn(is)17 b(a)g(function,)h Fl(s)8 b Fn(:)k Fg(I)-24 b(N)8 b Fi(7!)k Fg(I)-24 b(N)p Fn(,)17 b(sp)q(ecifying)i(the)e (amoun)o(t)f(of)h(\\w)o(ork")0 786 y(required)23 b(to)f(in)o(v)o(ert)g Fl(f)27 b Fn(on)22 b(inputs)i(of)d(giv)o(en)i(length.)42 b(The)22 b Ff(w)o(o)o(rk)f Fn(of)h(an)g(algorithm)g(is)h(de\014ned)h (as)d(the)0 843 y(pro)q(duct)12 b(of)g(the)g(running-time)i(\(of)d(the) h(in)o(v)o(erting)h(algorithm\))e(and)i(the)f(in)o(v)o(erse)g(of)g(its) g(success)h(probabilit)o(y;)0 908 y(namely)l(,)i Fl(w)199 915 y Fe(A)225 908 y Fn(\()p Fl(n)p Fn(\))300 883 y Fj(def)306 908 y Fn(=)j Fl(t)375 915 y Fe(A)402 908 y Fn(\()p Fl(n)p Fn(\))7 b Fi(\001)532 890 y Fj(1)p 497 897 88 2 v 497 923 a Fe(p)514 927 y Fa(A)538 923 y Fj(\()p Fe(n)p Fj(\))589 908 y Fn(,)14 b(where)g Fl(t)762 915 y Fe(A)789 908 y Fn(\()p Fl(n)p Fn(\))g(is)g(the)g(running)h(time)f(of)g Fl(A)f Fn(on)h Fl(f)5 b Fn(-images)14 b(of)g(length)g Fl(n)g Fn(and)0 984 y Fl(p)23 991 y Fe(A)50 984 y Fn(\()p Fl(n)p Fn(\))125 959 y Fj(def)130 984 y Fn(=)19 b(Prob)280 991 y Fe(x)p Fk(2f)p Fj(0)p Fe(;)p Fj(1)p Fk(g)399 983 y Fa(n)421 984 y Fn(\()p Fl(A)p Fn(\()p Fl(f)5 b Fn(\()p Fl(x)p Fn(\)\))11 b Fi(2)i Fl(f)679 968 y Fk(\000)p Fj(1)724 984 y Fl(f)5 b Fn(\()p Fl(x)p Fn(\)\))14 b(is)i(its)f(success)h (probabilit)o(y)l(.)71 1041 y(T)o(ypical)11 b(cryptographic)g (constructions,)g(and)g(in)h(particular)f(our)g(constructions,)g (transform)e(one)i(ob)s(ject)0 1097 y(\(in)17 b(our)g(case)g(a)f (family)i(of)e(one-w)o(a)o(y)h(p)q(erm)o(utations\))f(of)h(securit)o(y) g Fl(s)p Fn(\()p Fi(\001)p Fn(\))f(in)o(to)h(another)f(ob)s(ject)g (\(in)i(our)e(case)0 1153 y(a)h(single)h(1-1)f(one-w)o(a)o(y)g (function\))g(of)g(related)h(securit)o(y)f Fl(s)1021 1137 y Fk(0)1033 1153 y Fn(\()p Fi(\001)p Fn(\).)25 b(The)18 b(relation)g(b)q(et)o(w)o(een)f Fl(s)h Fn(and)f Fl(s)1712 1137 y Fk(0)1741 1153 y Fn(is)h(of)f(k)o(ey)0 1210 y(imp)q(ortance.)i (A)11 b(w)o(eak)f(relation,)i(whic)o(h)g(is)f(usually)h(easier)g(to)e (obtain,)i(is)f(that)f Fl(s)1384 1193 y Fk(0)1396 1210 y Fn(\(p)q(oly)q(\()p Fl(n)p Fn(\)\))i Fl(>)h(s)p Fn(\()p Fl(n)p Fn(\))p Fl(=)p Fn(p)q(oly)q(\()p Fl(n)p Fn(\).)0 1266 y(Although)g(this)g(relation)g(translates)f(an)o(y)g(sup)q(er-p)q (olynomial)j(securit)o(y)d Fl(s)h Fn(in)o(to)f(a)g(sup)q(erp)q (olynomial)j(securit)o(y)0 1323 y Fl(s)21 1306 y Fk(0)33 1323 y Fn(,)e(it)g(is)g(of)g(limited)h(practical)g(v)m(alue.)20 b(In)14 b(order)e(to)g(use)h(the)g(resulting)h(ob)s(ject)e(of)h (securit)o(y)g Fl(s)1599 1306 y Fk(0)1624 1323 y Fn(one)g(ma)o(y)f (needs)0 1379 y(to)19 b(use)h(v)o(ery)f(big)h(instances.)33 b(F)l(or)19 b(example,)i(if)f Fl(s)901 1363 y Fk(0)913 1379 y Fn(\()p Fl(n)958 1363 y Fj(5)976 1379 y Fn(\))g(=)g Fl(s)p Fn(\()p Fl(n)p Fn(\))f(and)h(the)g(original)g(ob)s(ject)f(is)h (\\secure)g(in)0 1436 y(realit)o(y")e(for)g(instance)h(size)g(100)f (\(bits\))g(then)g(the)g(resulting)i(ob)s(ject)d(\(of)h(securit)o(y)g Fl(s)1507 1419 y Fk(0)1519 1436 y Fn(\))g(will)i(b)q(e)f(\\secure)g(in) 0 1492 y(realit)o(y")12 b(only)h(for)e(instances)i(of)e(size)i(10)693 1476 y Fj(10)728 1492 y Fn(,)f(and)g(is)h(th)o(us)f(unlik)o(ely)i(to)d (b)q(e)i(of)e(practical)i(v)m(alue.)20 b(Th)o(us,)12 b(stronger)0 1549 y(relation)17 b(b)q(et)o(w)o(een)h(the)f(securit)o(y) g Fl(s)g Fn(of)f(the)h(original)h(ob)s(ject)f(and)g(the)g(securit)o(y)g Fl(s)1436 1532 y Fk(0)1465 1549 y Fn(of)f(the)h(resulting)h(ob)s(ject)0 1605 y(are)f(of)f(more)h(v)m(alue.)27 b(In)17 b(particular,)h(it)g(is)f (desirable)i(to)d(ha)o(v)o(e)h Fl(s)1143 1589 y Fk(0)1155 1605 y Fn(\()p Fl(O)q Fn(\()p Fl(n)p Fn(\)\))e Fl(>)h(s)p Fn(\()p Fl(n)p Fn(\))p Fl(=)p Fn(p)q(oly)q(\()p Fl(n)p Fn(\),)h(in)h(whic)o(h)f(case)0 1662 y(w)o(e)e(sa)o(y)f(that)h(the)g (transformation)f Ff(p)o(reserves)i(the)g(securit)o(y)p Fn(.)71 1718 y(Getting)i(bac)o(k)g(to)g(the)g(constructions)h(of)f(the) g(previous)i(section,)f(w)o(e)f(note)g(that)g(the)h(securit)o(y)f(of)g (the)0 1774 y(resulting)12 b(one-w)o(a)o(y)e(1-1)g(function)h Fl(f)5 b Fn(,)11 b(on)g Fl(f)5 b Fn(-images)11 b(of)f(length)h Fl(q)r Fn(\()p Fl(n)p Fn(\))q(+)q Fl(l)q Fn(\()p Fl(n)p Fn(\),)f(is)h(at)f(least)h(a)f(p)q(olynomial)j(fraction)0 1831 y(of)19 b(the)h(securit)o(y)g(of)f(the)h(family)g(of)f(one-w)o(a)o (y)g(p)q(erm)o(utations)h(on)g Fl(f)1204 1838 y Fe(i)1218 1831 y Fn(-images)g(of)f(length)h Fl(l)q Fn(\()p Fl(n)p Fn(\).)32 b(\(Recall,)22 b Fl(n)0 1887 y Fn(denotes)14 b(the)g(length)g(of)g(the)g(index)h(of)e(the)h(p)q(erm)o(utation,)g Fl(l)q Fn(\()p Fl(n)p Fn(\))f(the)g(length)i(of)e(the)h(description)h (of)f(elemen)o(ts)0 1944 y(in)21 b(the)e(domain)h(of)g(the)g(p)q(erm)o (utation)f(and)h Fl(q)r Fn(\()p Fl(n)p Fn(\))f(the)h(randomness)g (complexit)o(y)g(of)g(the)g(index-selecting)0 2000 y(algorithm.\))41 b(Namely)l(,)25 b Fl(s)470 1984 y Fk(0)482 2000 y Fn(\()p Fl(q)r Fn(\()p Fl(n)p Fn(\))14 b(+)h Fl(l)q Fn(\()p Fl(n)p Fn(\)\))24 b Fl(>)h(s)p Fn(\()p Fl(l)q Fn(\()p Fl(n)p Fn(\)\))p Fl(=)p Fn(p)q(oly\()p Fl(n)p Fn(\),)e(where)g Fl(s)f Fn(denotes)h(the)g(securit)o(y)f(of)g(the)0 2057 y(family)16 b Fg(F)f Fn(and)g Fl(s)296 2040 y Fk(0)323 2057 y Fn(the)g(securit)o(y)g(of)g(the)g(function)g Fl(f)5 b Fn(.)20 b(Therefore,)15 b(the)g(smaller)h(the)f(p)q(olynomial)h Fl(q)r Fn(\()p Fi(\001)p Fn(\))e(is,)h(the)0 2113 y(b)q(etter)f (securit)o(y)g(one)f(gets.)19 b Ff(It)14 b(is)g(pa)o(rticula)o(rly)f (desirable)h(to)g(k)o(eep)g Fl(q)r Fn(\()p Fl(n)p Fn(\))f Ff(linea)o(r)g(in)h Fl(l)q Fn(\()p Fl(n)p Fn(\))p Ff(.)19 b Fh(A)o(l)r(l)14 b(the)h(c)n(onstructions)0 2170 y(pr)n(esente)n(d)d (b)n(elow)h(achieve)g(this)g(go)n(al.)20 b(Conse)n(quently,)12 b(the)h(one-way)h(functions)f(c)n(onstructe)n(d)f(b)n(elow)h(pr)n (eserve)0 2226 y(the)j(se)n(curity)g(of)h(the)f(intr)n(actability)g (assumption)g(on)g(which)g(they)h(ar)n(e)f(b)n(ase)n(d.)j Fn(W)l(e)c(remark)g(that)f(the)h(\(w)o(eak)0 2283 y(to)d(strong)g (one-w)o(a)o(y\))f(transformation)h(of)g([4)o(])h(\(men)o(tioned)g(in)g (the)g(Remark)g(ab)q(o)o(v)o(e\))f(preserv)o(es)g(securit)o(y)h(to)q (o.)0 2404 y Fd(Preliminaries:)21 b(selecting)c(prime)g(n)n(um)n(b)r (ers)0 2490 y Fn(Prime)h(n)o(um)o(b)q(ers)f(pla)o(y)h(a)f(k)o(ey)g (role)h(in)g(all)h(our)e(constructions)g(and)h(so)f(e\016cien)o(t)h (algorithms)f(for)g(selecting)0 2547 y(suc)o(h)g(n)o(um)o(b)q(ers)f (are)g(of)g(k)o(ey)g(imp)q(ortance)h(to)f(us.)23 b(W)l(e)17 b(will)h(use)e(t)o(w)o(o)f(algorithms)h(due)h(to)f(Bac)o(h)g([1,)g(2)o (].)23 b(The)0 2603 y(\014rst)12 b(algorithm)h([2)o(])g(is)g(merely)g (a)f(v)o(ery)h(e\016cien)o(t)g(\(problem-sp)q(eci\014c\))i (\\deterministic)f(ampli\014cation")g(of)e(the)943 2769 y(5)p eop %%Page: 6 7 6 6 bop 0 195 a Fn(Miller-Rabin)21 b(primalit)o(y)e(tester)f([9)o(,)g (13)o(].)29 b(The)18 b(second)h(algorithm)f([1)o(])g(pro)q(duces)h (uniformly)g(distributed)0 252 y(in)o(tegers)c(together)g(with)g(their) h(prime)g(factorization.)0 345 y Fg(Theorem)h(1)23 b Fn(\(randonmess)17 b(e\016cien)o(t)i(primalit)o(y)f(tester)g([2)o(]\):) 24 b Fh(Ther)n(e)19 b(exists)e(a)i(pr)n(ob)n(abilistic)f(p)n(olynomial) 0 401 y(time)i(algorithm)g(that)g(on)f(input)h Fl(P)26 b Fh(uses)19 b Fi(j)p Fl(P)6 b Fi(j)19 b Fh(r)n(andom)g(bits)g(so)h (that)g(if)f Fl(P)26 b Fh(is)19 b(prime)h(then)f(the)h(algorithm)0 457 y(always)14 b(ac)n(c)n(epts,)g(and)h(otherwise)f Fn(\(i.e.,)f Fl(P)20 b Fn(is)13 b(comp)q(osite\))i Fh(the)f(algorithm)h (ac)n(c)n(epts)f(with)h(pr)n(ob)n(ability)f(at)g(most)23 496 y Fj(1)p 5 503 53 2 v 5 508 a Fk(p)p 32 508 26 2 v 25 x Fe(P)75 514 y Fn(=)f(2)146 497 y Fk(\000j)p Fe(P)t Fk(j)p Fe(=)p Fj(2)253 514 y Fh(.)0 607 y Fg(Theorem)k(2)23 b Fn(\(space)18 b(e\016cien)o(t)h(generation)g(of)f(in)o(tegers)h(with) f(kno)o(wn)h(prime)g(factorization)f([1)o(]\):)26 b Fh(Ther)n(e)0 663 y(exists)15 b(a)h(pr)n(ob)n(abilistic)f(p)n(olynomial)h(time)g (algorithm)h(that)f(uses)g(line)n(ar)f(sp)n(ac)n(e)g(and)h(on)g(input)g Fn(1)1680 647 y Fe(n)1718 663 y Fh(uniformly)0 720 y(gener)n(ates)f(a)i (numb)n(er)f Fl(N)k Fh(in)c(the)h(interval)e Fn([2)792 703 y Fe(n)p Fk(\000)p Fj(1)857 720 y Fl(;)8 b Fn(2)901 703 y Fe(n)933 720 y Fi(\000)i Fn(1])16 b Fh(and)g(outputs)h(the)g (prime)f(factorization)h(of)f Fl(N)5 b Fh(.)0 813 y Fn(The)13 b(ab)q(o)o(v)o(e)f(t)o(w)o(o)g(algorithms)g(are)h(reasonablly)g (e\016cien)o(t.)20 b(W)l(e)13 b(are)f(reluctan)o(t)h(to)f(use)h(the)g (primalit)o(y)h(certi\014er)0 869 y(of)e(Goldw)o(asser)g(and)g(Kilian)j (whic)o(h)e(for)f(all)h(but)g(a)f(negligible)j(fraction)d(of)g(the)h (primes)g(\014nds)g(in)g(probabilistic)0 926 y(p)q(olynomial-time)19 b(a)e(certi\014cate)h(of)f(primalit)o(y)h([7)o(].)25 b(In)o(terestingly)l(,)19 b(this)e(algorithm)h(can)f(b)q(e)h(implemen)o (ted)0 982 y(within)g(linear)g(space)f(and)g(so)g(applying)h(the)f (transforam)o(tion)e(of)i(Nisan)g(and)h(Zuc)o(k)o(erman)e([11)o(])g(w)o (e)h(get)g(an)0 1039 y(implemen)o(tation)f(whic)o(h)h(uses)e(linear)h (randomness.)0 1132 y Fg(Theorem)h(3)23 b Fn(\(randonmess)13 b(e\016cien)o(t)g(primalit)o(y)h(certi\014er)g([7)o(,)f(11]\):)18 b Fh(Ther)n(e)c(exists)g(a)g(pr)n(ob)n(abilistic)g(p)n(olyno-)0 1188 y(mial)e(time)h(algorithm)g(that)g(on)f(input)h Fl(P)19 b Fh(uses)12 b Fl(O)q Fn(\()p Fi(j)p Fl(P)6 b Fi(j)p Fn(\))11 b Fh(r)n(andom)i(bits)f(and)g(for)h(al)r(l)f(but)h(a)g (ne)n(gligible)d(fr)n(action)i(of)0 1245 y(the)i(primes)f(\014nds)g(a)g (c)n(erti\014c)n(ate)g(of)h(primality)g Fn(\(i.e.,)e(a)g(witness/pro)q (of)f(with)i(resp)q(ect)g(to)e(some)h(NP-relation\))p Fh(.)0 1365 y Fd(4.1)56 b(A)19 b(construction)f(based)h(on)f(RSA)0 1450 y Fn(The)g(standard)f(presen)o(tation)g(of)g(RSA)h([14)o(])f (yields)i(a)f(family)g(of)f(p)q(erm)o(utations)g(whic)o(h)h(is)g(b)q (eliev)o(ed)i(to)d(b)q(e)0 1507 y(one-w)o(a)o(y)l(,)i(but)g(is)g (certainly)h Fg(not)f Fn(one-w)o(a)o(y)f(in)i(the)f(augmen)o(ted)f (sense)i(of)e(De\014nition)i(3.)30 b(\(Here)19 b(w)o(e)g(refer)0 1563 y(to)c(a)h(family)g(in)h(whic)o(h)g(the)e(indices)j(are)e(pairs)g (\()p Fl(N)r(;)8 b(e)p Fn(\),)14 b(where)i Fl(N)21 b Fn(is)16 b(the)g(pro)q(duct)g(of)f(t)o(w)o(o)g(primes)h(of)g(equal)0 1620 y(length)e(and)g Fl(e)f Fn(is)h(relativ)o(ely)h(prime)f(to)f Fl(\036)p Fn(\()p Fl(N)5 b Fn(\).)18 b(The)c(index)h(is)f(generated)f (b)o(y)h(randomly)f(selecting)i(these)f(t)o(w)o(o)0 1676 y(primes,)g(m)o(ultiplying)i(them)e(and)g(next)g(selecting)h(a)e(prop)q (er)h Fl(e)p Fn(.)20 b(Th)o(us,)13 b(giving)i(these)f(random)f(c)o (hoices)i(a)o(w)o(a)o(y)0 1733 y(compromises)g(the)f(securit)o(y)h(of)f (RSA,)h(since)g(giv)o(en)g(the)f(prime)i(factors)d(it)i(is)f(easy)h(to) e(in)o(v)o(ert)i(the)f(function.\))71 1789 y(W)l(e)g(consider,)h (instead,)f(the)g(follo)o(wing)h(family)g(of)e(w)o(eak)h(one-w)o(a)o(y) f(p)q(erm)o(utations.)20 b(The)14 b(indices)i(in)f(this)0 1846 y(family)d(are)f(pairs)h(of)e(in)o(tegers)i(\()p Fl(N)r(;)c(P)e Fn(\))k(so)h(that)f Fl(P)18 b Fn(is)12 b(a)f(prime)h(and)f Fi(j)p Fl(P)6 b Fi(j)13 b Fn(=)g Fi(j)p Fl(N)5 b Fi(j)p Fn(.)17 b(F)l(or)11 b(eac)o(h)g(suc)o(h)h(pair)f (w)o(e)g(de\014ne)0 1910 y(a)16 b(p)q(erm)o(utation)h(o)o(v)o(er)e Fg(Z)431 1889 y Fk(\003)431 1922 y Fe(N)463 1910 y Fn(,)h(the)h(m)o (ultiplicativ)o(e)h(group)f(mo)q(dulo)g Fl(N)5 b Fn(;)16 b(sp)q(eci\014cally)l(,)j Fl(f)1487 1917 y Fe(N)q(;P)1553 1910 y Fn(\()p Fl(x)p Fn(\))1629 1885 y Fj(def)1634 1910 y Fn(=)h Fl(x)1715 1894 y Fe(P)1756 1910 y Fn(mo)q(d)12 b Fl(N)5 b Fn(.)0 1967 y(Note)17 b(that)g(w)o(e)h(do)f(not)g(insist)i (that)e Fl(N)22 b Fn(is)c(a)g(pro)q(duct)g(of)f(t)o(w)o(o)f(primes)j (of)e(the)g(same)h(length.)28 b(Y)l(et,)18 b(a)f(non-)0 2023 y(negligible)j(fraction)d(of)f(the)h(p)q(ossible)i Fl(N)5 b Fn('s)16 b(will)i(ha)o(v)o(e)f(this)g(form.)25 b(Th)o(us,)17 b(if)g(the)g(standard)g(RSA)g(family)h(is)0 2080 y(strongly)d(one-w)o(a)o(y)g(\(for)f(random)h(exp)q(onen)o(t\))g (then)h(it)f(is)h(also)f(\(strongly\))g(one-w)o(a)o(y)f(for)h(a)g (prime)h(exp)q(onen)o(t)0 2136 y(and)c(consequen)o(tly)g(the)g(ab)q(o)o (v)o(e)f(\(non-standard\))g(family)h(of)f(functions)i(will)g(b)q(e)f(w) o(eakly)g(one-w)o(a)o(y)f(\(due)g(to)g(the)0 2193 y(non-negligible)18 b(fraction)c(of)g(comp)q(osites)h(of)f(the)g(standard)g(form\).)19 b(Since)d Fl(P)21 b Fn(is)15 b(relativ)o(ely-prime)h(to)e Fl(\036)p Fn(\()p Fl(N)5 b Fn(\),)0 2249 y(the)20 b(functions)g(in)g (this)g(family)g(are)f(in)i(fact)d(p)q(erm)o(utations)i(o)o(v)o(er)e Fg(Z)1223 2228 y Fk(\003)1223 2260 y Fe(N)1255 2249 y Fn(.)33 b(\(Note)18 b(that)h(the)h(index-selecting)0 2306 y(algorithm)15 b(do)q(es)h(not)f(kno)o(w)g Fl(\036)p Fn(\()p Fl(N)5 b Fn(\))14 b(and)i(so)f(relativ)o(e-primalit)o(y)i(of)e Fl(P)22 b Fn(and)15 b Fl(\036)p Fn(\()p Fl(N)5 b Fn(\))15 b(is)g(imp)q(osed)i(b)o(y)e(requiring)0 2362 y(that)f Fl(P)22 b Fn(is)16 b(prime.\))71 2418 y(W)l(e)g(no)o(w)f(sho)o(w)h (that)g(the)g(ab)q(o)o(v)o(e)g(family)g(satis\014es)h(the)f (non-simpli\014ed)j(requiremen)o(ts)e(\(from)e(a)h(family)0 2475 y(of)h(one-w)o(a)o(y)f(p)q(erm)o(utations\))h(as)f(w)o(ell)i(as)f (the)g(additional)h(conditions)h(in)e(De\014nition)i(3.)25 b(Of)17 b(the)g(e\016ciency)0 2531 y(conditions)e(only)f(the)g(index)h (selection)g(is)f(problematic,)g(y)o(et)g(it)g(do)q(es)g(hold)g(when)g (allo)o(wing)h(negligible)h(error)0 2588 y(and)d(requiring)h(that)e (output)g(is)h(pro)q(duced)h(only)f(with)g(non-negligible)j(probabilit) o(y)e(\(i.e.,)e(just)g(select)i(t)o(w)o(o)d Fl(n)p Fn(-)0 2644 y(bit)h(in)o(tegers)g(at)f(random)g(and)h(c)o(hec)o(k)g(if)g(the)f (second)h(is)h(prime)f({)f(pro)q(ducing)i(an)f(output)f(only)h(if)g (the)g(answ)o(er)f(is)943 2769 y(6)p eop %%Page: 7 8 7 7 bop 0 195 a Fn(in)14 b(the)g(a\016rmativ)o(e\).)k(Also,)c Fg(Z)536 174 y Fk(\003)536 206 y Fe(N)581 195 y Fn(is)g(easily)h (recognizable)g(and)f(is)g(non-negligible)j(with)d(resp)q(ect)g(to)f Fi(f)p Fn(0)p Fl(;)8 b Fn(1)p Fi(g)1848 179 y Fk(j)p Fe(N)s Fk(j)1897 195 y Fn(.)0 252 y(F)l(urthermore,)13 b(this)g(family)h(is)f(one-w)o(a)o(y)g(in)h(the)f(augmen)o(ted)g(sense) g(\(under)h(the)f(\\RSA)h(assumption"\))e(since)0 308 y(the)20 b(mo)q(dulus)h(is)f(generated)f(via)h(an)g(iden)o(tit)o(y)g (transformation)f(from)g(the)g(coins)i(of)e(the)h(index-selecting)0 364 y(algorithm)15 b(\(and)g(th)o(us)g(these)h(coins)g(add)f(no)g(kno)o (wledge)h(to)e(the)i(in)o(v)o(erter\).)j(It)d(follo)o(ws)f(that)f(w)o (e)h(can)h(apply)0 421 y(Prop)q(osition)g(2)f(and)g(deriv)o(e)h(an)f (almost)g(1-1)g(one-w)o(a)o(y)f(function.)0 524 y Fg(De\014nition)19 b(4)k Fn(\(standard)12 b(RSA)i(Assumption\):)20 b Fh(We)14 b(say)g(that)h Ff(inverting)f(RSA)g(is)f(intractable)h(with)g(securit)o (y)0 580 y Fl(s)p Fn(\()p Fi(\001)p Fn(\))g Fh(if)g(any)g(algorithm)g (for)h(the)f Ff(inverting)g(task)h Fh(uses)f(work)g(gr)n(e)n(ater)g (than)h Fl(s)p Fn(\()p Fi(\001)p Fn(\))p Fh(.)k(The)14 b(inverting)f(task)h(c)n(onsists)0 636 y(of)20 b(\014nding)f Fl(x)h Fh(such)g(that)h Fl(y)h Fn(=)e Fl(x)587 620 y Fe(e)617 636 y Fn(mo)q(d)13 b Fl(N)5 b Fh(,)20 b(when)g(given)g Fl(N)5 b Fh(,)20 b Fl(e)g Fh(and)g Fl(y)r Fh(,)h(wher)n(e)g Fl(N)j Fh(is)c(uniformly)g(sele)n(cte)n(d)0 693 y(among)c(al)r(l)g(c)n (omp)n(osites)g(which)h(ar)n(e)f(the)g(pr)n(o)n(duct)h(of)g(two)f Fn(\()p Fl(n=)p Fn(2\))p Fh(-bit)g(long)f(primes,)i Fl(e)f Fh(is)g(uniformly)g(sele)n(cte)n(d)0 749 y(among)g(the)g(elements)f(of) i(the)f(multiplic)n(ative)g(gr)n(oup)g(mo)n(dulo)h Fl(\036)p Fn(\()p Fl(N)5 b Fn(\))p Fh(,)15 b(and)h Fl(y)i Fh(is)e(uniformly)g (sele)n(cte)n(d)e(among)0 806 y(the)j(elements)e(of)h(the)g(multiplic)n (ative)g(gr)n(oup)h(mo)n(dulo)g Fl(N)5 b Fh(.)0 908 y Fn(T)l(o)18 b(justify)g(our)g(claim)h(that)f(securit)o(y)g(\(of)g(the)g (RSA)h(Assumption\))f(is)h(preserv)o(ed)f(w)o(e)g(ha)o(v)o(e)g(to)f (note)h(that)0 965 y(pairs)e(\()p Fl(N)r(;)8 b(P)e Fn(\))14 b(as)i(required)g(can)g(b)q(e)g(selected)h(using)g Fl(O)q Fn(\()p Fi(j)p Fn(\()p Fl(N)r(;)8 b(P)e Fn(\))p Fi(j)p Fn(\))13 b(random)i(bits.)22 b(T)l(o)15 b(this)h(end,)g(w)o(e)f(use)h (the)0 1021 y(algorithm)f(guaran)o(teed)g(in)h(Theorem)f(1.)20 b(Th)o(us,)14 b(w)o(e)h(get)0 1124 y Fg(Corollary)j(1)k Fn(:)h Fh(Supp)n(ose)17 b(that)h(inverting)e(RSA)h(is)g(intr)n(actable) f(with)i(se)n(curity)f Fl(s)p Fn(\()p Fl(n)p Fn(\))p Fh(.)23 b(Then,)17 b(ther)n(e)g(exists)0 1189 y(an)f(almost)g(1-1)h (one-way)g(function)f(with)h(se)n(curity)f Fl(s)935 1172 y Fk(0)947 1189 y Fn(\()p Fl(O)q Fn(\()p Fl(n)p Fn(\)\))1093 1164 y Fj(def)1098 1189 y Fn(=)i Fl(s)p Fn(\()p Fl(n)p Fn(\))p Fl(=)p Fn(p)q(oly)r(\()p Fl(n)p Fn(\))p Fh(.)0 1291 y Fn(The)k(p)q(ossible)i(colisions)g(in)f(the)f(one-w)o(a)o(y)f (function)i(are)f(due)h(to)e(the)i(error)e(probabilit)o(y)i(of)f(the)g (index)0 1348 y(selection)16 b(algorithm)e(whic)o(h)i(in)f(turn)f(is)h (due)g(to)f(the)g(probabilit)o(y)i(that)e(a)g(comp)q(osite)h(passes)f (the)h(primalit)o(y)0 1404 y(test.)k(Using)14 b(Theorem)f(3)g(w)o(e)h (can)f(get)g(rid)h(of)f(this)h(error)f(\(i.e.,)g(if)h(w)o(e)f(fail)i (to)e(generate)g(a)g(certi\014cate)h(then)g(w)o(e)0 1461 y(treat)f(the)g(in)o(teger,)h(whic)o(h)h(is)f(p)q(ossibly)h(a)e(prime,) h(as)g(if)g(it)g(w)o(ere)f(found)h(to)f(b)q(e)h(comp)q(osite\).)20 b(Th)o(us,)13 b(assuming)0 1517 y(that)i(in)o(v)o(erting)h(RSA)g(is)g (in)o(tractable)g(\(with)f(securit)o(y)h Fl(s)p Fn(\()p Fl(n)p Fn(\)\),)e(there)i(exists)g(a)f(1-1)g(one-w)o(a)o(y)f(function)i (\(with)0 1582 y(securit)o(y)g Fl(s)191 1566 y Fk(0)203 1582 y Fn(\()p Fl(O)q Fn(\()p Fl(n)p Fn(\)\))349 1557 y Fj(def)354 1582 y Fn(=)i Fl(s)p Fn(\()p Fl(n)p Fn(\))p Fl(=)p Fn(p)q(oly)r(\()p Fl(n)p Fn(\)\).)0 1703 y Fd(4.2)56 b(A)19 b(construction)f(based)h(on)f(a)h(restricted)e(DLP)0 1789 y Fn(Here)12 b(w)o(e)g(rely)h(on)f(the)g(assumption)h(that)e(the)h (Discrete)h(Logarithm)f(Problem)g(\(DLP\))g(in)h(the)f(m)o (ultiplicativ)o(e)0 1846 y(group)18 b(mo)q(dulo)h Fl(P)25 b Fn(is)18 b(hard)h(also)f(for)g(the)g(sp)q(ecial)i(case)e(of)g(primes) h(of)f(the)g(form)g Fl(P)24 b Fn(=)18 b(2)p Fl(Q)12 b Fn(+)h(1,)18 b(where)h Fl(Q)0 1902 y Fn(is)f(a)g(prime.)28 b(W)l(e)18 b(also)g(use)g(the)f(assumption)h(that)g(suc)o(h)g(primes)g (form)f(a)g(non-negligibl)q(e)j(fraction)e(of)f(the)0 1958 y(in)o(tegers)g(of)g(the)h(same)f(length.)27 b(Based)18 b(on)f(these)g(assumptions,)h(the)f(follo)o(wing)i(family)f(of)f(p)q (erm)o(utations)0 2015 y(is)f(one-w)o(a)o(y)l(.)k(The)15 b(indices)j(in)e(the)f(family)h(are)f(pairs)h(\()p Fl(P)q(;)8 b(g)r Fn(\),)13 b(where)j Fl(P)22 b Fn(is)15 b(a)g(prime)h(of)f(the)h (ab)q(o)o(v)o(e)f(form)f(and)0 2071 y Fl(g)j Fn(is)f(a)g(primitiv)o(e)h (elemen)o(t)f(mo)q(dulo)h Fl(P)6 b Fn(.)22 b(The)16 b(index)h(is)f (selected)h(b)o(y)e(\014rst)h(selecting)h(a)e(prime)i(of)e(the)h(ab)q (o)o(v)o(e)0 2128 y(form)d(and)h(next)g(using)g(the)g(kno)o(wn)f (factorization)h(of)f Fl(\036)p Fn(\()p Fl(P)6 b Fn(\))12 b(=)h(2)p Fl(Q)h Fn(to)f(test)g(candidates)h(for)f(primitivit)o(y)i (\(see)0 2184 y(details)g(b)q(elo)o(w\).)20 b(F)l(or)13 b(eac)o(h)h(index,)i(\()p Fl(P)q(;)8 b(g)r Fn(\),)k(w)o(e)h(de\014ne)j (a)d(p)q(erm)o(utation)h(o)o(v)o(er)g Fg(Z)1379 2163 y Fk(\003)1379 2195 y Fe(P)1406 2184 y Fn(,)g(the)g(m)o(ultiplicativ)o (e)j(group)0 2249 y(mo)q(dulo)e Fl(P)6 b Fn(;)15 b(sp)q(eci\014cally)l (,)i Fl(f)485 2256 y Fe(P)q(;g)537 2249 y Fn(\()p Fl(x)p Fn(\))611 2224 y Fj(def)616 2249 y Fn(=)h Fl(g)693 2233 y Fe(x)726 2249 y Fn(mo)q(d)13 b Fl(P)6 b Fn(.)20 b(Noting)14 b(that)g Fg(Z)1173 2228 y Fk(\003)1173 2260 y Fe(P)1215 2249 y Fn(is)h(b)q(oth)g(`non-negligible')i(and)e(easy)f(to)0 2306 y(recognize,)i(w)o(e)f(can)g(apply)h(Prop)q(osition)g(2.)71 2362 y(T)l(o)k(justify)h(our)g(claim)g(that)f(the)h(resulting)h(1-1)e (one-w)o(a)o(y)h(function)g(preserv)o(es)g(the)g(securit)o(y)g(of)f (the)0 2418 y(family)l(,)k(w)o(e)d(note)g(that)g(pairs)h(\()p Fl(P)q(;)8 b(g)r Fn(\))19 b(can)j(b)q(e)g(selected)h(using)f Fl(O)q Fn(\()p Fi(j)p Fl(P)6 b Fi(j)p Fn(\))20 b(random)h(bits.)40 b(On)22 b(input)g Fl(n)g Fn(w)o(e)0 2475 y(uniformly)e(select)f(an)g (\()p Fl(n)12 b Fi(\000)h Fn(1\)-bit)19 b(in)o(teger,)g Fl(Q)p Fn(,)g(and)g(test)f Fl(Q)h Fn(and)g Fl(P)25 b Fn(=)18 b(2)p Fl(Q)12 b Fn(+)h(1)19 b(for)f(primalit)o(y)l(.)31 b(In)19 b(case)0 2531 y(w)o(e)d(are)h(successful,)h(w)o(e)e(uniformly)i (select)g Fl(g)e Fi(2)g Fg(Z)886 2510 y Fk(\003)886 2543 y Fe(P)930 2531 y Fn(and)h(test)f(if)h(it)g(is)h(primitiv)o(e)g(\(mo)q (d)e Fl(P)6 b Fn(\))17 b(b)o(y)g(computing)0 2588 y Fl(g)24 2571 y Fe(P)t Fk(\000)p Fj(1)106 2588 y Fn(mo)q(d)c Fl(P)6 b Fn(,)17 b Fl(g)295 2571 y Fe(Q)335 2588 y Fn(mo)q(d)12 b Fl(P)23 b Fn(and)17 b Fl(g)600 2571 y Fj(2)630 2588 y Fn(mo)q(d)c Fl(P)6 b Fn(.)24 b(\(If)16 b(the)g(\014rst)g(expression)h (ev)m(aluates)h(to)d(1)h(whereas)g(the)h(other)0 2644 y(t)o(w)o(o)d(don't,)g(then)i Fl(g)g Fn(is)g(a)f(primitiv)o(e)h(elemen) o(t)g(mo)q(dulo)g Fl(P)6 b Fn(.\))20 b(W)l(e)15 b(get)943 2769 y(7)p eop %%Page: 8 9 8 8 bop 0 195 a Fg(Corollary)18 b(2)k Fn(:)j Fh(Supp)n(ose)18 b(that)h(the)f(r)n(estricte)n(d)g(DLP)g(is)g(intr)n(actable)f(with)i (se)n(curity)f Fl(s)p Fn(\()p Fl(n)p Fn(\))g(\(see)g(de\014nition)0 252 y(b)q(elo)o(w\))p Fh(,)h(and)f(that)h(the)g(set)f(of)g Fl(n)p Fh(-bit)h(primes,)g Fl(P)6 b Fh(,)19 b(for)f(which)h Fl(\036)p Fn(\()p Fl(P)6 b Fn(\))p Fl(=)p Fn(2)18 b Fh(is)g(prime,)h(c) n(onstitute)e(a)i Fn(1)p Fl(=)p Fn(p)q(oly)q(\()p Fl(n)p Fn(\))0 308 y Fh(fr)n(action)12 b(of)h(the)g Fl(n)p Fh(-bit)g(long)f (inte)n(gers.)19 b(Then,)12 b(ther)n(e)h(exists)f(an)g(almost)h(1-1)g (one-way)g(function)g(with)g(se)n(curity)0 370 y Fl(s)21 354 y Fk(0)33 370 y Fn(\()p Fl(O)q Fn(\()p Fl(n)p Fn(\)\))180 345 y Fj(def)185 370 y Fn(=)18 b Fl(s)p Fn(\()p Fl(n)p Fn(\))p Fl(=)p Fn(p)q(oly)q(\()p Fl(n)p Fn(\))p Fh(.)0 477 y Fn(Again,)d(the)g(one-w)o(a)o(y)g(function)h(can)f(b)q(e)h(made)f (1-1)g(b)o(y)g(using)h(Theorem)f(3)g(\(as)g(ab)q(o)o(v)o(e\).)0 583 y Fg(De\014nition)k(5)k Fn(\(restricted)18 b(DLP)g(Assumption\):)26 b Fh(We)20 b(say)e(that)i Ff(the)f(restricted)h(DLP)d(is)h(intractable) i(with)0 639 y(securit)o(y)g Fl(s)p Fn(\()p Fi(\001)p Fn(\))g Fh(if)g(any)h(algorithm)g(for)g(the)f(fol)r(lowing)g Ff(inverting)g(task)i Fh(uses)e(work)h(gr)n(e)n(ater)f(than)g Fl(s)p Fn(\()p Fi(\001)p Fn(\))p Fh(.)33 b(The)0 696 y(inverting)18 b(task)h(c)n(onsists)e(of)j(\014nding)e Fl(x)h Fh(such)g(that)h Fl(y)g Fn(=)e Fl(g)1040 679 y Fe(x)1073 696 y Fn(mo)q(d)12 b Fl(P)6 b Fh(,)21 b(when)e(given)f Fl(P)6 b Fh(,)20 b Fl(g)h Fh(and)e Fl(y)r Fh(,)h(wher)n(e)f Fl(P)0 752 y Fh(is)e(uniformly)h(sele)n(cte)n(d)e(among)i(al)r(l)g Fl(n)p Fh(-bit)g(primes)g(for)g(which)g Fl(\036)p Fn(\()p Fl(P)6 b Fn(\))p Fl(=)p Fn(2)17 b Fh(is)g(prime,)i Fl(g)g Fh(is)e(uniformly)h(sele)n(cte)n(d)0 809 y(among)f(the)h(primitive)f (elements)f(mo)n(dulo)i Fl(P)6 b Fh(,)18 b(and)f Fl(y)i Fh(is)d(uniformly)i(sele)n(cte)n(d)d(among)j(the)f(elements)f(of)h(the) 0 865 y(multiplic)n(ative)f(gr)n(oup)h(mo)n(dulo)g Fl(P)6 b Fh(.)0 987 y Fd(4.3)56 b(A)19 b(construction)f(based)h(on)f(the)h (general)e(DLP)0 1073 y Fn(Here)c(w)o(e)g(rely)g(on)g(a)f(seemingly)j (w)o(eak)o(er)d(assumption)h(concerning)h(the)f(DLP)l(.)g(Sp)q (eci\014cally)l(,)j(w)o(e)c(assume)h(that)0 1129 y(the)18 b(Discrete)h(Logarithm)e(Problem)i(\(DLP\))e(in)i(the)g(m)o (ultiplicativ)o(e)h(group)e(mo)q(dulo)h(a)e(prime)i Fl(P)25 b Fn(is)18 b(hard)0 1186 y(also)13 b(when)h(giv)o(en)f(the)g (factorization)g(of)g Fl(\036)p Fn(\()p Fl(P)6 b Fn(\).)19 b(Making)13 b(this)g(assumption,)g(w)o(e)g(can)g(w)o(aiv)o(e)g(the)g (assumption)0 1242 y(made)18 b(in)g(the)g(previous)g(subsection)h (concerning)f(the)g(densit)o(y)g(of)f(primes)h(of)g(sp)q(ecial)h(form)e Fl(P)23 b Fn(=)17 b(2)p Fl(Q)11 b Fn(+)h(1,)0 1298 y(where)17 b Fl(Q)g Fn(is)h(a)e(prime.)27 b(\(Note)16 b(that)g(for)h(primes)g(of)g (the)g(sp)q(ecial)i(form)d Fl(P)22 b Fn(=)17 b(2)p Fl(Q)10 b Fn(+)i(1)17 b(the)g(factorization)g(of)0 1355 y Fl(\036)p Fn(\()p Fl(P)6 b Fn(\))13 b(=)g(2)c Fi(\001)h Fl(Q)15 b Fn(is)h(alw)o(a)o(ys)e(kno)o(wn.\))71 1411 y(Based)k(on)h(the)f(ab)q (o)o(v)o(e)g(in)o(tractabilit)o(y)i(assumption,)f(the)f(follo)o(wing)i (family)f(of)f(p)q(erm)o(utations)g(is)h(one-)0 1468 y(w)o(a)o(y)l(.)i(The)16 b(indices)i(in)f(the)f(family)g(are)g(pairs)g (\()p Fl(P)q(;)8 b(g)r Fn(\),)14 b(where)i Fl(P)22 b Fn(is)16 b(a)g(prime)g(and)h Fl(g)g Fn(is)f(a)g(primitiv)o(e)h(elemen)o (t)0 1524 y(mo)q(dulo)g Fl(P)6 b Fn(.)22 b(The)16 b(index)h(is)f(c)o (hosen)h(b)o(y)e(\014rst)h(generating)g(a)f(random)h(prime)h Fl(P)22 b Fn(with)16 b(kno)o(wn)g(factorization)0 1581 y(of)h Fl(\036)p Fn(\()p Fl(P)6 b Fn(\))17 b(\(see)g(details)h(b)q(elo) o(w\),)f(and)g(next)h(using)f(this)h(factorization)f(to)f(test)h (candidates)h(for)e(primitivit)o(y)l(.)0 1646 y(F)l(or)i(eac)o(h)h (index,)i(\()p Fl(P)q(;)8 b(g)r Fn(\),)17 b(w)o(e)i(de\014ne)g(a)g(p)q (erm)o(utation)g(o)o(v)o(er)f Fg(Z)1116 1625 y Fk(\003)1116 1657 y Fe(P)1162 1646 y Fn(as)g(b)q(efore)h(\(i.e.,)g Fl(f)1491 1653 y Fe(P)q(;g)1543 1646 y Fn(\()p Fl(x)p Fn(\))1623 1621 y Fj(def)1628 1646 y Fn(=)24 b Fl(g)1711 1629 y Fe(x)1744 1646 y Fn(mo)q(d)13 b Fl(P)6 b Fn(\).)0 1702 y(Again,)15 b(w)o(e)g(can)g(apply)h(Prop)q(osition)g(2.)71 1758 y(W)l(e)i(ha)o(v)o(e)f(p)q(ostp)q(oned)i(the)f(discussion)i(of)e (ho)o(w)f(to)h(randomly)g(generate)g(primes)h Fl(P)24 b Fn(with)19 b(kno)o(wn)f(fac-)0 1815 y(torization)h(of)h Fl(\036)p Fn(\()p Fl(P)6 b Fn(\).)32 b(Here,)21 b(a)e(di\013eren)o(t)h (algorithm)f(of)g(Bac)o(h)h(comes)f(to)g(the)g(rescue.)34 b(This)20 b(algorithm,)0 1871 y(uniformly)15 b(generates)e(comp)q (osites)h(with)g(their)g(factorization)f([1].)19 b(Ha)o(ving)13 b(pro)q(duced)i(a)e(factored)g(comp)q(os-)0 1928 y(ite)i Fl(N)5 b Fn(,)15 b(w)o(e)f(test)h Fl(N)f Fn(+)c(1)15 b(for)f(primalit)o(y)i(and)f(are)g(done)g(if)g(the)h(answ)o(er)e(is)h (in)h(the)f(a\016rmativ)o(e.)k(Actually)l(,)d(the)0 1984 y(algorithm)f(pro)q(duces)h(a)f(certi\014cate)h(for)e(the)h(primalit)o (y)h(of)f Fl(P)k Fn(=)13 b Fl(N)i Fn(+)10 b(1)15 b(in)h(probabilistic)h (p)q(olynomail-time)0 2041 y(using)i(the)e(\(certi\014ed\))i (factorization)e(of)h Fl(P)g Fi(\000)12 b Fn(1)18 b(\(pro)q(duced)g(b)o (y)g(Bac)o(h's)f(algorithm\).)28 b(A)18 b(straigh)o(tforw)o(ard)0 2097 y(implemen)o(tation)k(of)f(Bac)o(h's)g(algorithm)g(requires)h(a)f (sup)q(er-linear)i(n)o(um)o(b)q(er)e(of)g(coin)h(tosses.)37 b(Y)l(et,)23 b(it)e(is)0 2154 y(p)q(ossible)h(to)e(implemen)o(t)i(an)f (appro)o(ximation)f(of)g(the)h(algorithm)f(using)i(only)f(a)f(linear)i (n)o(um)o(b)q(er)f(of)f(coin)0 2210 y(tosses)14 b(\(i.e.,)g(linear)h (in)g(the)g(length)g(of)f(the)g(comp)q(osite)h(b)q(eing)h(generated\).) j(The)c(details)g(are)f(quite)h(tedious.)0 2267 y(Instead,)i(w)o(e)g (prefer)g(to)f(in)o(v)o(ok)o(e)h(a)f(general)i(result)f(of)f(Nisan)i (and)f(Zuc)o(k)o(erman)f([11)o(])h(b)o(y)f(whic)o(h)i(an)o(y)f(proba-)0 2323 y(bilistic)i(p)q(olynomial-time)g(algorithm,)d(whic)o(h)i(uses)e (linear)i(space,)f(can)f(b)q(e)i(appro)o(ximated)e(using)h(a)f(linear)0 2379 y(n)o(um)o(b)q(er)h(of)f(coin)h(tosses.)23 b(It)17 b(is)g(v)o(ery)f(easy)g(to)g(see)h(that)f(Bac)o(h's)g(algorithm)g (falls)i(in)o(to)e(this)h(category)f(\(and)0 2436 y(this)g(is)h(stated) e(in)i(Theorem)f(2)g(ab)q(o)o(v)o(e\).)22 b(This)16 b(yields)i(an)e (index)h(selecting)g(algorithm)g(whic)o(h)f(selects)h(pairs)0 2492 y(\()p Fl(P)q(;)8 b(g)r Fn(\))13 b(using)j Fl(O)q Fn(\()p Fi(j)p Fn(\()p Fl(P)q(;)8 b(g)r Fn(\))p Fi(j)p Fn(\))j(random)k(bits,)g(justifying)h(our)e(claim)i(that)e(the)h (resulting)h(1-1)e(one-w)o(a)o(y)h(function)0 2549 y(preserv)o(es)f (the)h(securit)o(y)g(of)f(the)g(family)l(.)21 b(W)l(e)14 b(stress)g(that)g(the)g(index)i(selecting)g(algorithm)e(nev)o(er)h (errs)f(\(and)0 2605 y(furthermore)h(it)g(pro)q(duces)h(a)f (certi\014can)o(te)h(for)e(mem)o(b)q(ership)j(in)f(the)f(index)i (set\).)i(Th)o(us,)c(w)o(e)g(get)943 2769 y(8)p eop %%Page: 9 10 9 9 bop 0 195 a Fg(Corollary)18 b(3)k Fn(:)e Fh(Supp)n(ose)13 b(that)h(DLP)f(is)g(intr)n(actable)g(with)h(se)n(curity)f Fl(s)p Fn(\()p Fl(n)p Fn(\))p Fh(,)h(even)f(when)g(the)h(factorization) f(of)0 252 y(the)k(or)n(der)g(of)f(the)h(gr)n(oup)g(is)f(given)g Fn(\(see)g(de\014nition)h(b)q(elo)o(w\))p Fh(.)22 b(Then,)16 b(ther)n(e)g(exists)g(a)h(1-1)g(one-way)g(function)0 316 y(with)g(se)n(curity)f Fl(s)289 300 y Fk(0)301 316 y Fn(\()p Fl(O)q Fn(\()p Fl(n)p Fn(\)\))447 291 y Fj(def)452 316 y Fn(=)j Fl(s)p Fn(\()p Fl(n)p Fn(\))p Fl(=)p Fn(p)q(oly)q(\()p Fl(n)p Fn(\))p Fh(.)0 423 y Fg(De\014nition)g(6)k Fn(\(DLP)c (Assumption\):)28 b Fh(We)20 b(say)g(that)g Ff(the)h(DLP)d(is)i (intractable)g(with)g(securit)o(y)g Fl(s)p Fn(\()p Fi(\001)p Fn(\))f Fh(if)h(any)0 479 y(algorithm)c(for)g(the)g(fol)r(lowing)g Ff(inverting)f(task)h Fh(uses)f(work)i(gr)n(e)n(ater)e(than)h Fl(s)p Fn(\()p Fi(\001)p Fn(\))p Fh(.)k(The)15 b(inverting)g(task)g(c)n (onsists)0 536 y(of)h(\014nding)e Fl(x)i Fh(such)g(that)g Fl(y)f Fn(=)e Fl(g)549 519 y Fe(x)582 536 y Fn(mo)q(d)f Fl(P)6 b Fh(,)17 b(when)e(given)g Fl(P)6 b Fh(,)16 b(the)g (factorization)g(of)g Fl(\036)p Fn(\()p Fl(P)6 b Fn(\))p Fh(,)16 b Fl(g)h Fh(and)f Fl(y)r Fh(,)f(wher)n(e)h Fl(P)0 592 y Fh(is)d(uniformly)g(sele)n(cte)n(d)f(among)h(al)r(l)g Fl(n)p Fh(-bit)h(primes,)g Fl(g)g Fh(is)f(uniformly)h(sele)n(cte)n(d)d (among)j(the)f(primitive)h(elements)0 648 y(mo)n(dulo)i Fl(P)6 b Fh(,)16 b(and)g Fl(y)h Fh(is)e(uniformly)h(sele)n(cte)n(d)e (among)i(the)g(elements)e(of)i(the)g(multiplic)n(ative)f(gr)n(oup)h(mo) n(dulo)g Fl(P)6 b Fh(.)0 792 y Fm(5)67 b(Conclusions)22 b(and)h(Op)r(en)f(Problems)0 893 y Fn(W)l(e)e(ha)o(v)o(e)g(presen)o (ted)g(a)g(metho)q(d)g(for)g(constructing)g(\(strongly\))f(one-w)o(a)o (y)h(p)q(erm)o(utations.)34 b(The)20 b(metho)q(d)0 950 y(consists)15 b(of)g(three)g(steps.)0 1043 y Fg(Step)j(\(1\))23 b Fn(using)c(w)o(ell-kno)o(wn)f(in)o(tractabilit)o(y)h(assumptions)f (to)f(construct)g(families)j(of)d(one-w)o(a)o(y)g(p)q(erm)o(u-)114 1100 y(tations)d(satisfying)i(the)f(additional)i(prop)q(erties)f(sp)q (eci\014ed)h(in)f(De\014nition)h(3;)0 1194 y Fg(Step)h(\(2\))23 b Fn(using)16 b(suc)o(h)g(a)f(family)h(to)e(construct)h(a)g(w)o(eak)f (one-w)o(a)o(y)h(function;)0 1288 y Fg(Step)j(\(3\))23 b Fn(transforming)15 b(the)g(resulting)h(function)g(in)o(to)f(a)g (strongly)g(one-w)o(a)o(y)g(function.)0 1381 y(W)l(e)e(consider)i(the)e (iden)o(ti\014cation)i(of)e(the)g(conditions)i(in)f(De\014nition)g(3)f (and)h(the)f(construction)g(of)g(families)i(of)0 1438 y(one-w)o(a)o(y)g(p)q(erm)o(utations)h(satisfying)g(these)g(conditions) g(to)g(b)q(e)g(the)g(most)e(imp)q(ortan)o(t)i(con)o(tributions)g(of)f (the)0 1494 y(curren)o(t)g(pap)q(er.)21 b(Th)o(us,)15 b(most)f(of)h(the)h(pap)q(er)g(is)f(dedicated)i(to)e(the)g(implemen)o (tation)i(of)e(Step)h(\(1\),)e(whereas)0 1551 y(Step)i(\(2\))e(is)h (obtained)h(b)o(y)f(Construction)h(1)e(and)i(Step)f(\(3\))g(is)g (obtained)h(b)o(y)f(referring)h(to)e([4].)71 1607 y(Regarding)i(Step)g (\(3\),)f(w)o(e)g(remark)g(that)g(applying)i(the)f(general)g(\(\\w)o (eak)f(to)g(strong"\))f(transformation)0 1664 y(of)i([4)o(])g(seems)g (an)g(o)o(v)o(er-kill)h(since)g(in)g(our)f(case)g(the)g(w)o(eakly)h (one-w)o(a)o(y)e(function)i Fl(f)k Fn(has)16 b(a)g(sp)q(ecial)i (structure)0 1720 y(\(e.g.,)g(it)i(is)f(hard)g(to)g(in)o(v)o(ert)g (almost)g(on)g(all)h(p)q(oin)o(ts)f(on)g(whic)o(h)h(it)f(is)h(not)f (the)g(iden)o(tit)o(y)h(transformation\).)0 1777 y(F)l(urthermore,)13 b(it)i(seems)f(that)f(ad-ho)q(c)i(metho)q(ds)f(ma)o(y)f(b)q(e)i (applicable)h(to)d(the)i(function)f Fl(f)19 b Fn(resulting)d(from)d(a)0 1833 y(sp)q(eci\014c)18 b(transformation.)23 b(Ho)o(w)o(ev)o(er,)15 b(in)j(our)e(attempts)f(to)h(a)o(v)o(oid)g(using)i([4)o(],)e(w)o(e)g(w) o(ere)g(not)h(able)g(to)f(a)o(v)o(oid)0 1889 y(using)e(random)f(w)o (alks)g(on)g(expander)h(graphs)f(\(and)g(since)h(expander)g(graphs)f (are)g(the)g(only)h(non-elemen)o(tary)0 1946 y(comp)q(onen)o(t)20 b(of)g([4)o(])g(w)o(e)g(see)g(no)g(p)q(oin)o(t)h(in)g(presen)o(ting)g (these)f(alternativ)o(es)g(here\).)35 b(Certainly)l(,)22 b(it)e(will)i(b)q(e)0 2002 y(b)q(etter)15 b(to)g(the)g(use)h(of)e (expander)i(graphs)f(and)g(p)q(erform)g(Step)h(\(3\))e(in)i(a)f(more)g (e\016cien)o(t)h(manner.)71 2059 y(Another)10 b(ob)o(vious)g(op)q(en)h (problem)g(is)f(to)g(construct)g(one-w)o(a)o(y)f(1-1)h(functions)h (based)f(on)g(the)h(in)o(tractabilit)o(y)0 2115 y(of)16 b(factoring.)25 b(T)l(o)17 b(ac)o(hiev)o(e)g(this)g(goal)g(using)h(our) e(metho)q(d)h(one)g(will)i(need)f(to)e(construct)h(a)f(family)i(of)e (one-)0 2172 y(w)o(a)o(y)h(p)q(erm)o(utations)i(satisfying)f(the)h (additional)g(prop)q(erties)g(sp)q(eci\014ed)i(in)e(De\014nition)h(3.) 29 b(\(The)18 b(standard)0 2228 y(construction)i(of)f(a)g(family)h(of)f (one-w)o(a)o(y)g(p)q(erm)o(utations)h(based)f(on)h(factoring)f([12)o(]) g(do)q(es)h(not)f(satisfy)g(the)0 2285 y(augmen)o(ted)c(one-w)o(a)o (yness)g(condition.\))0 2428 y Fm(Ac)n(kno)n(wledgmen)n(ts)0 2529 y Fn(W)l(e)g(w)o(ould)h(lik)o(e)g(to)f(thank)g(Eric)h(Bac)o(h)f (and)g(Hugo)g(Kra)o(w)o(czyk)g(for)f(helpful)k(discussions)e(and)g (commen)o(ts.)943 2769 y(9)p eop %%Page: 10 11 10 10 bop 0 195 a Fm(References)23 297 y Fn([1])21 b(E.)15 b(Bac)o(h,)g Ff(Analytic)i(Metho)q(ds)g(in)e(the)i(Analysis)f(and)g (Design)g(of)f(Numb)q(er-Theo)o(retic)f(Algo)o(rithms)f Fn(\(A)o(CM)93 353 y(Distinguished)18 b(Dissertation)d(1984\),)e(MIT)i (Press,)g(Cam)o(bridge)g(MA,)f(1985.)23 440 y([2])21 b(E.)16 b(Bac)o(h,)f(\\Realistic)j(Analysis)f(of)e(some)g(Randomized)j (Algorithms",)d Ff(19th)h(STOC)p Fn(,)g(1987,)f(pp.)h(453{)93 496 y(461.)23 583 y([3])21 b(M.)16 b(Blum)h(and)f(S.)g(Micali,)i(\\Ho)o (w)d(to)g(Generate)h(Cryptographically)h(Strong)f(Sequences)h(of)f (Pseudo-)93 639 y(Random)g(Bits",)f Ff(SIAM)g(J.)g(on)h(Com)o(puting)p Fn(,)e(V)l(ol.)h(13,)f(1984,)g(pp.)h(850{864.)23 726 y([4])21 b(O.)d(Goldreic)o(h,)h(R.)f(Impagliazzo,)h(L.)f(Levin,)h(R.)f (V)l(enk)m(atesan)h(and)f(D.)f(Zuc)o(k)o(erman,)g(\\Securit)o(y)h(Pre-) 93 782 y(serving)e(Ampli\014cation)h(of)e(Hardness",)g Ff(31st)g(F)o(OCS)p Fn(,)g(1990,)f(pp.)h(318{326.)23 869 y([5])21 b(O.)13 b(Goldreic)o(h)h(and)f(L.)g(Levin,)h(\\A)f (Hard-Core)g(Predicate)g(for)f(an)o(y)h(One-w)o(a)o(y)g(F)l(unction",)g Ff(21st)g(STOC)p Fn(,)93 925 y(1989,)h(pp.)h(25{32.)23 1012 y([6])21 b(O.)14 b(Goldreic)o(h,)h(H.)e(Kra)o(w)o(czyk)h(and)g(M.) f(Lub)o(y)l(,)h(\\On)g(the)g(Existence)h(of)e(Pseudorandom)h (Generators",)93 1068 y Ff(SIAM)i(J.)f(on)g(Computing)p Fn(,)e(V)l(ol.)j(22,)e(1993,)g(pp.)h(1163{1175.)23 1155 y([7])21 b(S.)14 b(Goldw)o(asser)f(and)h(J.)g(Kilian,)i(\\Almost)e(all) h(primes)f(can)g(b)q(e)h(quic)o(kly)g(certi\014ed",)g Ff(18th)f(STOC)p Fn(,)g(1986,)93 1211 y(pp.)i(316{329.)23 1298 y([8])21 b(J.)12 b(H)-6 b(\027)-28 b(astad,)12 b(R.)g (Impagliazzo,)h(L.)f(Levin)h(and)f(M.)f(Lub)o(y)l(,)i(\\Construction)e (of)h(a)f(pseudo-random)h(genera-)93 1354 y(tor)i(from)f(an)o(y)g (one-w)o(a)o(y)h(function",)g Fh(ICSI)f(T)m(e)n(chnic)n(al)g(R)n(ep)n (ort)p Fn(,)h(No.)f(91-068,)g(submitted)i(to)e Fh(SICOMP)p Fn(.)93 1411 y(Com)o(bines)23 b(pap)q(ers)f(of)f(Impagliazzo,)j(Levin)g (and)e(Lub)o(y)g(\()p Ff(21st)g(STOC)p Fn(,)g(1989,)g(pp.)f(12{24\))g (and)h(J.)93 1467 y(H)-6 b(\027)-28 b(astad,)15 b(\()p Ff(22nd)g(STOC)p Fn(,)g(1990,)f(pp.)h(395{404\).)23 1554 y([9])21 b(G.L.)d(Miller,)j(\\Riemann's)e(Hyp)q(othesis)h(and)f(tests)f (for)g(primalit)o(y",)h Ff(JCSS)p Fn(,)h(V)l(ol.)f(13,)f(pp.)h (300{317,)93 1610 y(1976.)0 1697 y([10])i(M.)16 b(Naor)g(and)h(M.)e(Y)l (ung,)i(\\Univ)o(ersal)g(Hash)g(F)l(unctions)g(and)g(their)g (Cryptographic)f(Applications",)93 1753 y Ff(21st)g(STOC)p Fn(,)f(1989,)f(pp.)h(33{43.)0 1840 y([11])21 b(N.)15 b(Nisan)g(and)g(D.)f(Zuc)o(k)o(erman,)g(\\More)f(Deterministic)j(Sim)o (ulation)g(in)g(LOGSP)l(A)o(CE",)e Ff(25th)h(STOC)p Fn(,)93 1896 y(1993,)f(pp.)h(235{244.)0 1983 y([12])21 b(M.O.)13 b(Rabin,)h(\\Digitalized)h(Signatures)e(and)h(Public)g(Key)g(F)l (unctions)g(as)f(In)o(tractable)g(as)g(F)l(actoring",)93 2039 y(MIT/LCS/TR-212,)i(1979.)0 2126 y([13])21 b(M.O.)11 b(Rabin,)h(\\Probabilistic)h(algorithm)e(for)f(testing)h(primalit)o (y",)h Ff(Jour.)22 b(of)10 b(Numb)q(er)f(Theo)o(ry)p Fn(,)i(V)l(ol.)g(12,)93 2182 y(pp.)16 b(128{138,)d(1980.)0 2269 y([14])21 b(R.)e(Riv)o(est,)h(A.)e(Shamir,)i(and)f(L.)g(Adleman,)h (\\A)f(Metho)q(d)f(for)g(Obtaining)j(Digital)e(Signatures)g(and)93 2325 y(Public)e(Key)f(Cryptosystems",)d Ff(CA)o(CM)p Fn(,)i(V)l(ol.)h(21,)e(F)l(eb.)h(1978,)f(pp.)h(120{126.)0 2412 y([15])21 b(J.)d(Romp)q(el,)h(\\One-w)o(a)o(y)f(F)l(unctions)g (are)f(Necessary)h(and)g(Su\016cien)o(t)h(for)e(Secure)h(Signatures",)g Ff(22nd)93 2468 y(STOC)p Fn(,)e(1990,)e(pp.)h(387{394.)0 2555 y([16])21 b(R.)c(Solo)o(v)m(a)o(y)f(and)h(V.)f(Strassen,)g(\\A)g (fast)g(Mon)o(te-Carlo)f(test)h(for)g(primalit)o(y",)h Ff(SIAM)f(Jour.)33 b(on)16 b(Com-)93 2611 y(puting)p Fn(,)h(V)l(ol.)e(6,)g(pp.)g(84{85,)e(1977.)932 2769 y(10)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF