Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://iisi.msu.ru/UserFiles/File/publications/mabit04.pdf Äàòà èçìåíåíèÿ: Mon Apr 2 16:24:06 2012 Äàòà èíäåêñèðîâàíèÿ: Fri Feb 28 20:16:26 2014 Êîäèðîâêà: Ïîèñêîâûå ñëîâà: m 87 jet

. .


28­29 2004 .

2005


32.816 34


. 34 28­29 2004 . -- .: , 2005. -- 384 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

: «-» «» « ""» « ""» «-» «» «» «- »


. . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . , . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . , . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . , . . , . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Scott D. Stoller, Yanhong A. Liu. Security policy languages and enforcement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 32 65 91

28­29 2004 .
. 119002, , ., 11. 01335 24.03.2000 . 15.09.2005 . 60 â 90/16. . 24 . . 500 . . «». 248640, . , . , 5.

99 118

« »
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

ISBN 5-94057-212-X

9 785940 572121 >

© , 2005. © , 2005.


4





5

. . , . . . . . . . . . . . . . . . . . . . . . . . . 141 . . , . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 . . . MV2 . . . . . . . . . . . 156 . . . - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 . . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 . . , . . , . . . . . 177 . . . . . . . . 185 . . . YAQS -- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 . . . (n, m, k) - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 . . . VR . . . . . 209 . . , . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 . . . (superimposed) . . . . . . . . . . . . . . . . . . . . . . . 217 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 . . , . . . « » . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 . . . p - 1 243

« »
. . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 . . . . . . . . . . . . . . 257 . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 . . . . . . . . . . . . . . . . . . . . . . . . . 273 . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 . . , . . , . . , . . , . . , . . . - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 . . , . . . : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 . . , . . . «Linux over » . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 . . , . . , . . . . . . . 326 . . , . . , . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332


6



. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 . . , . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360


, 28 2004 .
, . . . - (SUNY) , - . (Dr. Elizabeth D. Capaldi) . , - .-. , . . . : . . , . . , . . . . . . , . . . . . . . , . . . . . . , . . , . . . . . . . , . . , . . , . . . . . . , . . , . . . . Scott D. Stoller, Yanhong A. Liu. Security policy languages and enforcement. Tzi-cker Chiueh. Program semantic-aware intrusion detection.


8





9

, 29 2004 .
« » -- . . , . . . . , . . , . . . . . . . . . . . VR. . . . . . . . . . . . , . . . . . . , . . . « » . . . . . . . , . . , . . . . . . . MV2. . . . (n, m, k) - . . . . - . . . . , . . , . . . .

. . . . . . . YAQS -- . . . . p - 1. . . . . . . . side channel attack . . . . 3- . : . . . . . . . . . . , . . . Z2k . . . , . . . . . . . , . . . . . . . . . . . . (superimposed) . « » -- . . , . . . . , . . . . . . . . . . , . . . .


10



. . , . . . . E. Rich. An emerging perspective on the dynamics of insider cyber threats. . . . , . . , . . , . . , . . , . . , . . . - . . . , . . . : . . . . . H. G. Berg. A teaching Hospital Approach to identifying risks, research problems and teaching materials in information security. . . . , . . . «Linux over ». . . , . . , . . . . . . , . . , . . , . . . . . . . . . . . , . . . . . . . . . . . . . . , . . , . . . Linux: , , .

. .
!
« ». , . , . , . , , - -, - . , , . , , , . , , . , , , , . -


12

. .

...

13

- . . , , , , , , . , . , , , , . , . , . , - . , , , . , , , . , . , , . .

. . , , . « », , . -, , , . , , . 1. , . , - , . , , . 2. , , - ; , ; , , , , . .


14

. .

...

15

- . , , . . 3. -- , , . , , . 4. - , . - . . - , « ». 5. , , , , , . 6. , , . · ,

· -- , , , · , , -- , . , - . , , : « -- , , ». , . , , ( - , , , , ) , . . . - . - , , . (, - , ) - , - . , -


16

. .

...

17

() , . . , , , , , . , , . - , , - . , , . , . 9 2003 . . -- , : · ; · ; · . - , - , , .

- . . « », -. , , . -- , . . XXI . , , , . , , XXI , . , . . . , , , IT-- . , , .


. . , . .
. -- , . , , , () , , . , . m (. [1, . 126] ) . , () Z/mZ. , . , (. [1, . 125] ) . (, RSA -, . [1, . 310] ) , , . , , . . , , , , . - , - .
-2358.2003.9.




20

. . , . .



21

, , , . . , , , , , . . , , . , [43] , [27] [28] . S () , A () , Sn , An = {1, . . . , n}. , = {0, . . . , 2m - 1}. +, · 2m , , GF (2m) an-1 2n-1 + . . . + a1 2 + a0 , ai {0, 1}, (an-1 , . . . , a1 , a0) GF (2m) .

1.
. . . , , DES AES. . [40] [12] . , [40] , g Sn ( , n = 4 g ) Sn h, g Sn . , Sn , . [39] , Sn Sn An

1 n . 1 m [33] . , Sn . An Sn . n = 2m . . 1. 1975­76 . . . n, 2m - 2m < n - 1. [30] ( ) , 2m = n - 1, n. , , 2m = n An , PGL (2, p) p = 2m - 1 > 3. 2. n = 2m , 2m-2 -, An . (. . , ) . 3. .. 1­2 [7] , P = GF (2m) , g = (0, 1, . . . , 2m - 1) - h (P , ) GF (2) , S (P) . h : k â (n - k) k = 1, . . . , n. 4. , , DES AES, () , . [41] , [42] . , [38] , , DES , . Sn , An M , M. . n 64 ( ) [31] . [27] . , . . . . , . . n < 1000 (. . [28] ) .


22

. . , . .

. [29] ,
n2 n - -1 3 3

23

, , 2m , .

L (Sn , { g , h})

2. ,
, : L (G , M) -- G M, . . t , G = M1 . . . Mt ; d (G , M) -- G M, . . d , G d Ms . k- , , dk (M) -- k- M, . . r , Mr k- ( r ) . , L (G , M) dk (M) M G G . Sn An . . [12] , [17] . . 1. G = M -- , M, M2 , M3 , . . . G H , H -- G , M ; d (G , M) = [G : H ] [6] . 2. G M M [6] . 3. Sn An [37] , : An < G < Sn , G = M M-1 = M, max L (G , M) exp (n log n)
1/2

L (Sn , { g , h}) , 3n2 /4, [21] . : L (Sn , M) n2 , |M| = 2 ( n < 8, . [32] ) . 5. [21] , [29] , n log2 n, . M G , L (G , M) |M| . ( ) k- Sn ( k > 1) , . . [16] . [6] , [7] , [35] Sn , . Sn M 2- M. : L (Sn , M) d2 (M) · n.

4n 2 n 5 --. 3 2 6

3.
( , ) H S () , H |H | = ||. . , . , , , DES AES, . . . ,

(1 + O (1)) .

4. Sn g = (1, 2, . . . , n) , h = (1, 2) . . . [15] 2n2 .


24

. . , . .



25

2- , , H . , 2- H . , 2- Sn , n ( . ., ) . , 2- . [8] , 2- m fh, m -- (P , +) , f -- P = GF (2m) , f (x) = x - 1, x = 0, f (0) = 0, h Aut (P , +) . , AES. [6] , [7] D GF (2m) , m > 1, 2- 4- 5- m D , m -- , g = (0, 1, . . . , 2m - 1) . [9] 2- AES. 84n , n = 4, 6, 8, 5, 6, 7. : , , G1 , G2 , 2-. (. [7] ) . , 2-, : · n 23 pq , p , q -- ; · ; · 2- . , . : GH 2- ( ) G , H Sn .

4.
. , , , . , , , , . . , . [18­20] . [18] . 1 , 2 , . . . -- G , (k) = 1 2 . . . k , M = { g G : 1 (g) > 0}, G = M , H -- G , M , d = [G : H ] . (ks) , ks N, , , s , ks j (mod d) j . G H . [19] , [20] , (k) , .

5.
-- , n -- n, -- , f (P , Q) -- f P Q . : , , -- 7 . I ( , f ) : , f , . . : P , Q f ( (P) , (Q)) f (P , Q) , (1)



26

. . , . .



27

S ( , f ) -- I ( , f ) , ( , f ) ( f ) . 1956 . . . , , [24] . f , : S ( , ) (a1 . . . an) = g1 (ah (1) ) . . . gn (ah (n) ) , gi S () , h Sn . , S (n , f ) = S () n Sn . , || > 4 S (n , ) S (n) . [4, 10, 11] I ( , f ) , S ( , f ) , : (1) 7 f 1 , 1 . : , f , k , , k = 2. , . . f = , . . . . . , - n , «» . n , , 2 .

6.
Fk (n) -- k- n , . . f : n n , || = k, G -- S (n) . G Fk (n) : Fk (n) : f Fk (n) , g S (n) f g (x1 , . . . , xn) = f (g (x1 , . . . , xn)) ; f1 G f2 g G f2 = f IG (f ) = { g G : f g = f }.
g 1

f G :

. , G -- n , Sn , S () n, GL (n, ) , AGL (n, ) , n -- (n , +) ; Sn -- . [ f ] G , f IG (f ) . ( 1988 .) [13] . [14] , H k N n f Fk (n) , IG (f ) H G = Sn . = f Fk (n) n · Sn n . AGL (n, ) , -- (. [22] ) = Z/m (. [14] ) . [2] AGL (n, R) · H , R -- , H -- . . , n, k G , . . . , 1997 . [34] . 6, 7, 8 , 6 , 4- . . , 7 8 [44] . . .

7.
, () .

. [ f ] G , f , G IG (f ) : | [ f ] G | = |G | · |IG (f ) |.


28

. . , . .



29


A1 X1 . . . An Xn An+1 = B , (2)
[1] . ., . ., . ., . . . ., , 2001. [2] . ., . . . , . 36, 1979. [3] . . , . , . 21, 6 , 1 9 8 2 , 6 2 7 ­6 4 6 . [4] . ., . ., . . , . . ., . 9, . 3, 1997, 3­19. [5] . . - . ., , 2003. [6] . . , . . ., . 1, 1997, 43­66. [7] . . 2- . . ., . 3, 2000, 37­52. [8] . . . , . 10, . 3, 2003, 634. [9] . . «Rijndael». , . 11, . 2, 2003, 634. [10] . . , . . ., . 11, . 2, 1999, 20­39. [11] . . , . .., . 4, 2001, 17­32. [12] . ., . . () . . . , . 8, 1999, 5­32. [13] . ., . ., . . k- . I. ., 1988. [14] . . (. ) , , 1981. [15] . . . , 2, 1968, 1­5. [16] . . . , 1, 1 9 7 1 , 4 3 ­4 4 . [17] . . . , 3, 1977, 1­15. [18] . ., . ., . . . . ., . 1, 1997, 85­112. [19] . . . . .,

A1 , . . . , An+1 -- , X1 , . . . , Xn -- G . , , . -- . . , . , . . , (2) G , , (X1 , . . . , Xn) G . . (2) , . , [36] , [3] -- ( ) . X d = 1, X -1 gX = h . ax = b . . . [5] . , . . GF (p) exp (c + o (1)) (ln p) 1/3 (ln ln p) 2/3 . c . [25] , [26] , GF (p) . c 1,902 ( [26] ) . , - , -- .


30

. . , . .



31

. 3, 2000, 73­94. [20] . . . .., . 3, 2000, 53­72. [21] . . Sn , . . ., . 2, 1998, 1 1 2 ­1 5 0 . [22] . ., . . . , . 9, 1963, 63­98. [23] . ., . ., . . . ., , 2004. [24] . . , . , . 2, 70­93. [25] . ., . . GF (p) . , . 7, . 2, 2000, 387­389. [26] . . GF (p) . . ., . 15, . 1, 2003, 28­49. [27] . . . 1. . ., 1986. [28] . . . 1. ( 1981­95 .) . . ., . 2, 1998. [29] . . . . . , 5, 1 9 7 3 , 1 4 1 ­1 4 4 . [30] . . , 2m . , . 19, 2, 1973, 236­247. [31] . . . , . 19, 3, 1973, 423­457. [32] . . , . , 5, 1975, 51­55. [33] . . . . ., . 3, 2000, 215­234. [34] . . . . ., . 4, 2001, 273­314. [35] . . , . . ., . 16, . 1, 114­120. [36] . . . , . 6, 2, 1967, 111­113. [37] Babai L., Seress A. On the diameter of Cayley graphs of the symmetric group. J. comb. Theory, v. A49, 1988, 175­179. [38] Cambell K ., Wiener M. DES is not a group. Crypto'92, 512­520. [39] Dixon J. D. The probability of generating the symmetric groups. Mat. Z.,

v. 110, 1969, 199­205. [40] Piccard S. Sur les bases des groupes d'ordre fini. Neuchatel, 1957. [41] Wernsdorf R. The one-round function of the DES generate alternating group. Eurocrypt'92, 99­112. [42] Wernsdorf R. The round function of RIJNDAEL generate the alternating groups. Fast software 2002, Leuven, Berlin, Preproceed., 272. [43] Wielandt H. Finite permutation groups. N.Y., 1964. [44] Xiang-Dong Hou. GL (m, 2) acting on Rm /R (m) . J. Discr. Math., v. 149, 1 9 9 6 , 9 9 ­1 2 2 .




33

. . , . . , . .
1.
, . , . , , . -- , , , , . (, , ) , . . , . , , , , , . , , . . : « . , ».

2.
, Crypto'83 [14] . - -

. , , , . . , , () . , Information Hiding: First International Workshop [13] , , , (embedded) . , , , : , (image) . . , , (hidden) . . , , , . . , , (cover, carriage) . -- . , , , . . , . , . [2] , [5] () [5] . . , , . , , . , , , , . , , -- .


34

. . , . . , . .



35

, , . . . , Emb Ext, . , = Emb (, , ) , -- = Ext (, ) . , , . Emb , , . , (, , ) , , Emb . . : · . , . , ; · . , , - , ; · Emb. , , . , , , . , , .

. , . : · . , ; · . . , , ; · . . . , . , . , , -- , . , : , . . (. 3) . « » : (covert) (subliminal) . , , . , . -- , . , . , . C -- , K -- , M -- S = {s = Emb (c , m, k) , s = | c C , m M, k K } -- . S C . , , , -


36

. . , . . , . .



37

. , , . (, ) . -, . «» , «» . , . , , () , . -- . , . . «» (subliminal) , , « ». , « » , « » . , . . , , , . , , . , , . - -

. , - , , . : . , . , , «», 0, «», 1. ? . , () (, ) . 3. . . 1. , , , , . , . -, . -, , . , . 2. , , . , , . , , , . . , , , , , -- . , , , -- .


38

. . , . . , . .



39

3.
. . -- . . «» , . . , , , . : · , , ( ) . , ; · , ( ) . . , . . . , . , (. ) . , , . . , . : - . . . . ,

( ) . . -- ; . , , , . . , . , -- . , , . , , , . , , ( , ) . , (. 5.3) , . (. [11] ) . . , . , , . (, , , ) . : 1. , . , , . , ( ) . , , , . 2. C = {c1 , . . . , cn } , . , , -


40

. . , . . , . .



41

C1 C , C2 C . , C , cn+1 , (. ) , . , , , C3 C2 . cn+1 . 1 , , , cn+1 . . , , . . . . , . -- , -- . , . . . , , , . , - , , (, , - ) . . , . , . , , . «» , , .

. , , , . 5. , , . . . . , , . , , . ? . , , () G , . , , , , , . . -- . G , , , . . , G . , , G . . 4.1. C , K M -- . ( , ) , C , K M . C , K M , , . R R. .

4. -
- , .


42

. . , . . , . .



43

k, K . m ( M) , s = Emb (c , m, k, r) , c r -- C R , . , s C . s , m Ext (s , k) . G (c , D) , D -- D, G -- C â D C . , D . () {Ac |c C }, Ac : C {0, 1}. , , C , ( S = Emb (C , M, K , R)) ( C = G (C , D)) . c -- , Ac (x) = 1 (Ac (x) = 0) , , , x C (, ) . , . , . , . , . ( C) . 4.2. - . [4] : ( ) . , (relative) ; . . , . . [15] . : . ,

(, ) . [3] [2] , (, ) . . X , Y Z -- X , Y Z . Ent (X) X . Ent (X |Y ) -- X Y . , Ent (X |Y ) Ent (X) , Ent (X |Y ) = Ent (X) , X Y . X Y X Y , REnt (X Y ) REnt (X Y ) =
x X

Pr{X = x } log2

Pr{X = x } . Pr{Y = x }

X Y X Y , X Y , -- X Y , . , REnt (X Y ) , X Y . , Pr{X = x } ( 0) Pr{Y = x } = 0 x X , REnt (X Y ) = +, . X Y Z : REnt ((X |Z) (Y |Z)) = Pr{Z = z } REnt ((X |Z = z) (Y |Z = z)) .

z Z

REnt ((X |Z = z) (Y |Z = z)) X Y Z = z , , REnt (X Y ) , Z = z . , REnt (X Y ) 0, REnt (X Y ) = 0 , X Y . REnt ((X |Z) (Y |Z)) 0, REnt ((X |Z) (Y |Z)) = 0 , (X |Z = z) (Y |Z = z) z Z . -- . 1 ( 4] . (Emb, Ext) [) · - , REnt (C S) ;


44

. . , . . , . .



45

· , 0- , . . C S . . . 2. (Emb, Ext) · - ( ) , REnt ((C |C) (S |C)) . 3 ( 15] . (Emb, Ext) [) · - ., Ent (M) - Ent (M|C , S) ; · ., 0- ., . . M (C , S) . 4.3. (Emb, Ext) - . [4] . , f X Y . REnt (f (X) f (Y )) REnt (X Y ) . (1) , 0 , log2 ( / (1 - )) + (1 - ) log2 ((1 - ) /) , ( , ) = log2 (1/) , log2 (1/ (1 - )) , 1, {0, 1}; / = 0; = 1.

, C , . . G . 2 ( 15] . (Emb, Ext) -- , [) . Ent (S |C) = Ent (C |S) = 0.

, , G .

5. -
, « ». , . , , , ( -- , -) . , , - . , , . - , 4, - , . , , , , , , , . . , () . . , . - . . , , ,

(1) , - . 1 ( 4] . (Emb, Ext) -- , -[) . (, ) . , = 0, , , - 2) . 2- . ( -


46

. . , . . , . .



47

, ? 5.1. N , n N -- . N N, n , = const, > 0, . C = {Cn }, Cn {0, 1}q , -- . q = q (n) -- . Cn . , - {0, 1}q . , , n Cn . 4. {cn }, cn Cn , , () , 1n ( n) cn . , . . , G -- , c Cn c = G (c) , c {0, 1}q . c -- . G . . G , l : N N , n G l (n) . c Cn r {0, 1}l (n) . c = G (c , r) . , G , . G . . . . , A, s {0, 1}q 0, 1. A (s) = 1, s , . . . A (s) = 0, s .

: N (0,1] . . c Cn , r R {0, 1}l c = G (c , r) . Pr{A (c ) = 1} (n) . r , A. , (n) -- , «» . , , « » , 1. ( , ) . , , , s , . , . . -- , s -- . 5 ( 1] . (Emb, Ext) [) G ( , ) , {cn }, {mn }, mn {0, 1}t (n) , {G (cn) } {Emb (cn , mn , k) }, k R {0, 1}n , . , {Dn } {Dn } , B , p n
x D

Pr {B (x) = 1} - Pr {B (x) = 1} < 1/ p (n) .
n

x D

n

Dn Dn q (n) . 1. {cn } , , , . , . , 5 -


48

. . , . . , . .



49

. , - , : . , (., , [15] ) . t (n) n + 1. , ( ) n. 5.2. 3 ( 1] . [) Emb, 5, . 3 . 6. {Dn } -- , Dn {0, 1} (n) . {Dn } (polynomially samplable) , Samp , Samp (1n) = Dn . 7 ( 10] . g : {0, 1}n {0, 1} (n) -- , [) . g , p {Dn } , 1. {Dn } { g (x) }, x R {0, 1}n , . 2. Ent (Dn) Ent (g (x)) + 1/ p (n) . Ent (Y ) Y . 3. . , 5, , . , [10] (. [12] ) , , . [10] , . , 5, G -- . g . {cn } -- -

. - () , 1n mn {0, 1}t (n) . x {0, 1}n -- g . g (x) = Emb (cn , mn , x) . , g . , Ent (g (x)) n. , 5 { g (x) }, x R {0, 1}n , {G (cn) } . , {G (cn) } r {0, 1}l . , {G (cn) } {Emb (cn , mn , k) }, k R {0, 1}n , mn R {0, 1}t (n) , . { g (x) }, x R {0, 1}n , {Emb (cn , mn , k) }, k R {0, 1}n , mn R {0, 1}t (n) . , {Emb (cn , mn , k) }, k R {0, 1}n , mn R {0, 1}t (n) , t (n) ( mn Emb (cn , mn , k) Ext) . t (n) n + 1, . 2. , , Emb . , , . , 3 : , Emb, . (, ) , , , , . , 5 G , . , G , . , , . , G (cn) Emb (cn , mn , k) , k R {0, 1}n , n. , , 5, . ,


50

. . , . . , . .



51

, . 8. G -- r {0, 1}l , r = r1 r2 , r1 {0, 1}l1 (n) , l1 (n) -- N N , l1 (n) < l (n) . G , Der , c r {0, 1}l , Der (G (c , r)) = r1 . , , . , l1 (n) t (n) . ( , ) . A, ( , ) . . A 1n mn {0, 1}t (n) , cn {0, 1}q (n) . , mn cn -- . A s {0, 1}q 0, 1. P1 (n) = Pr{A (s) = 1} , s = = G (cn , r) . r A. P2 (n) = Pr{A (s) = 1} , s = Emb (cn , mn , k) . P2 k A. , , , , , G Der. 9. (Emb, Ext) G ( , ) , A , p n , . , |P1 (n) - P2 (n) | < 1/ p (n) .

. , , . 4 ( 1] . , [) , ( , ) . . g : {0, 1}n {0, 1}t (n) -- . [10] , [12] . (Emb, Ext) . Emb (cn , mn , k) = g (k) mn . G , cn r = r , r R {0, 1}l (n) -t (n) . s = G (cn , r) . s () Emb. Ext Der, s . -- t (n) Der (s) . mn = g (k) . c : g (k) , k R {0, 1}n , . 5.3. , , , . -- , , , . , ( ) , , . , : «» , , . , .


52

. . , . . , . .



53

(, ) , . . , , , , . , , . , . , . , , c Cn -- , . G c = G (c) . , m , (Emb, Ext) -- , k -- . c , s = Emb (c , m, k) . c~ Sub c = Sub (c~ ) , . , {G (c) } {Sub (c ) }, c = G (c) . , , . . m. s , c1 , . . . , cu , G c1 , . . . , cu , , . -- . - , ( ) . , , c1 , . . . , cu ( !) . u , , , , V = {1, . . . , v }. , v . : , -

, . , . 10. (Emb, Ext) G - ( ) , : 1) (. 5) ; 2) Sub . s -- , , s , . . s = s , s = Sub (s) . Pr{ s & Ext (s ) = m} . , . 10 , , , m. , , , 10, . u R V c1 , . . . , cu , .