kiev-security.org.ua-Криптография.О специальном классе каналов перехвата

S.K.Leung-Yan Cheong. On a Special Class of Wiretap Channels// IEEE Tr. on IT, v.23, Э5, 1977, pp.625-627. Аннотация. Исследуется специальный класс каналов перехвата, для которого некоторая величина Г(R) является константой, и даются некоторые характеристики ег членов. Для "симметричных" каналов перехвата показано, что Г(R) равна разности между пропускными способностями основного канала и канала от отправителя к подслушивателю. I. Введение Концепция канала перехвата впервые была введена Вайнером [1]. Предложенная им модель показана на рис.1. здддддддддјS здддддддддјX здддддддддјY здддддддддјS °источник цдддѓ кодер цддддѓосновной цдбддѓ декодер цдддддддддд ° ° ° ° ° канал ° ° ° ° законный юддддддддды юддддддддды юддддддддды ° юдддддддддыполучатель ° ° здддадддддј ° канал ° Рис.1. Общий вид канала °перехвата° перехвата. юдддбддддды °Z ° подслушиватель Канал перехвата - это разновидность ухудшенного широковещательного канала с той новой идеей, что одна информационная скорость должна максимизироваться, а другая - минимизироваться. Цель заключается в максимизации скорости надгжной передачи от источника законному получателю. При этом налагается ограничение, что неопределгнность подслушивателя после пригма данных Z будет не меньше некоторой заданной величины. Подслушиватель знает методы кодирования, используемые отправителем, и метод декодирования, используемый законным получателем, и попадает в затруднительное положение только из-за более значительного шума в принимаемом сигнале. Таким образом, хотя цель такая же, как и в криптографии, но для достижения секретности используется совершенно другой метод. В этой статье мы используем основные результаты Вайнера для дискретных каналов перехвата без памяти, чтобы проанализировать класс каналов, для которых некоторая величина Г(R) постоянна. Мы покажем, что если основной канал, а также каскад основного канала и канала перехвата являются симметричными, то Г(R) - константа. II. Предварительные замечания Ссылаясь на рис.1, предположим, что источник является эргодическим и имеет конечный алфавит. Первые k выходных значений источника, s , кодируются в N-вектор x , который является входом для основного канала. Законный получатель делает оценку s для s , основанную на y с выхода основного канала, подверженного воздействию ошибок с частотой появления на блок Pe=Pr{s = s}. (1) y является также входом для канала перехвата, и подслушиватель имеет усреднгнную остаточную неопределгнность H(S |Z ) после наблюдения выхода Z канала перехвата. Определим относительную неопределгнность подслушивателя как =H(S |Z )/H(S ), (2) а скорость передачи законному получателю - R=H(S )/N. (3) Отметим, что при =1 апостериорная неопределгнность подслушивателя относительно выхода источника равна его априорной неопределгнности. Таким образом, при =1 подслушиватель после пригма данных не становится более информированным. Говорят, что пара (R*,d*) достижима, если для всех >0 существует пара кодер-декодер такая, что R>=R* - (4а) R>=d* - (4а) Pe<= . (4с) Основной результат Вайнера для области достижимых (R,d) следующий. Теорема 1. (Вайнер) Пусть p ( ) будет распределением вероятности на входе основного канала. Определим, что (R), R>=0, является множеством p таких, что I(X;Y)>=R. Для 0<=R<=Cм, где Смпропускная способность основного канала, пусть Г(R)= max I(X;Y|Z). (5) Тогда множество всех достижимых пар (R,d) задагтся так: *=Х{(R,d)| 0<=R<=Cм, 0<=d<=1, Rd<=Г(R)}. (6) В главе III мы охарактеризуем класс каналов, для которых Г(R) являтся константой. III. Каналы с постоянной величиной Г(R) Полезная характеристика каналов с постоянной величиной Г(R) дагтся в следующей теореме. Теорема 2. Г(R) является константой тогда и только тогда, если p* максимизирует I(X;Y)-I(X;Z), где p* - достигающее пропускной способности распределение на основном канале. Доказательство: отметим сперва, что I(X;Y|Z) можно переписать следующим образом - I(X;Y|Z)=H(X|Z)-H(X|Y,Z) (7) =H(X|Z)-H(X|Y) (8) =I(X;Y)-I(X;Z), (9) при этом в (8) мы использовали тот факт, что X, Y и Z образуют марковскую цепочку. Если p* максимизирует I(X;Y)-I(X;Z), то Г(R)=I (X;Y)-I (X;Z), (10) поскольку p* (R) для 0<=R<=Cм. Следовательно, Г(R) - константа. Обратно предположим, что p* не максимизирует I(X;Y)-I(X;Z). Обозначим максимизирующее распределение как p' , и пусть Ip' (X;Y)=R1. Тогда очевидно, что Г(R1)>Г(См). Это показывает, что Г(R) не может быть константой. ЧИТД Теперь дадим необходимое условие, чтобы Г(R) являлось константой, для специального класса дискретных каналов перехвата без памяти. Теорема 3. Пусть основной канал будет дискретным каналом без памяти (ДКБП) с К входами, а канал перехвата будет некоторым другим ДКБП. Предположим, что I(X;Y) максимизируется при единственном входном распределении p* =(p*(1),p*(2),...,p*(К)), причгм все составляющие p* строго положительны. Тогда необходимое условие, чтобы Г(R) было константой, заключается в следующем: p* должно быть максимизирующим распределением для I(X;Z). Доказательство: сперва отметим, что I(X;Y) и I(X;Z) являются вогнутыми функциями распределения вероятностей p на входе основного канала [3, теорема 4.4.2]. Будем использовать ограничительное равенство p(i)=1, подставляя 1- p(i) вместо p(К) в выражениях для I(X;Y) и I(X;Z). Таким образом, можно рассмотреть максимизацию I(X;Y) и I(X;Z), которые теперь являются функциями от К-1 переменных с ограничительным неравенством p(i)>=0. По гипотезе I(X;Y) имеет максимум при p* , и p* >0. Следовательно I(X;Y) p(i) 1<=i<=К-1. (11) Теперь предположим, что p* не максимизирует I(X;Z). Тогда существует по крайней мере одно j [1,К-1] такое, что I(X;Z) p(j) (12) Следовательно, передвигаясь от p* в направлении p(j) (это всегда возможно, так как мы предположили, что все составляющие p* строго положительны), можно увеличить разность между I(X;Y) и I(X;Z) (по крайней мере первоначально). Следовательно, p* не максимизирует I(X;Y)-I(X;Z), и из теоремы 2 следует, что Г(R) не является константой. ЧИТД Примечание. Теорему 3 можно непосредственно применить для случая, когда I(X;Y) максимизируется неединственными, но строго положительными входными распределениями. На рис. 2(а) и 2(б) показаны примеры основного канала и канала перехвата, для которых Г(R) не является константой. Каскад этих двух каналов эквивалентен двоичному симметричному каналу (ДСК) с переходной вероятностью 1/11, как показано на рис.2(в). 1 10/11 0 ддддддддддддддддд 0 0 ддддддддддддддддд 0 X 0,1 Y Y 1/11 Z 1 ддддддддддддддддд 1 1 ддддддддддддддддд 1 0,9 1 (а) (б) 10/11 0 ддддддддддддддддд 0 X Z 1 ддддддддддддддддд 1 10/11 (в) Рис.2. (а) основной канал; (б) канал перехвата; (в) каскад основного канала и канала перехвата. Максимум I(X;Y) достигается при Pr{X=0}=0,54. С другой стороны, ввиду симметрии канала относительно X и Z I(X;Z) максимизируется при Pr{X=0}=0,5. Следовательно, по теореме 3 Г(R) не является константой. Теперь докажем результат, дающий достаточное условие, чтобы Г(R) была константой. Теорема 4. Предположим, что I(X;Y) и I(X;Z) одновременно максимизируются при входном распределении p* . Тогда Г(R) является константой и равна См-Смw, где Смw - пропускная способность каскадного канала. Доказательство: p* позволяет достичь максимумов I(X;Y) и I(X;Z) и, следовательно, соответствует стационарной точке I(X;Y)I(X;Z)=I(X;Y|Z). Ниже в лемме 1 показано, что I(X;Y|Z) - это вогнутая функция входного распределения вероятностей. Следовательно, стационарная точка p* также максимизирует I(X;Y)-I(X;Z). И наконец, из теоремы 2 следует, что Г(R) - константа. Кроме того, Г(R)=I (X;Y)-I (X;Z) (13) =Cм-Смw. ЧИТД (14) Следствие. Предположим, что основной канал - это симметричный ДКБП [3, с.90] и что каскад основного канала и канала перехвата - это также симметричный ДКБП. Тогда Г(R) является константой и равна Cм-Cмw. Доказательство: хорошо известно [3, теорема 4.5.2], что для симметричного ДКБП пропускная способность достигается при использовании равновероятных входных величин. Этот факт в совокупности с теоремой 4 доказывает, что Г(R) - константа. Поскольку См и Смw в этом случае легко оценить, то можно найти и Г(R). Эту главу завершим доказательством следующей леммы. Лемма 1. Пусть X, Y и Z обозначают входы и выходы двух каскадированных ДКБП, как показано на рис.3. Тогда I(X;Y|Z) - это вогнутая функция входного распределения вероятностей. здддддддддј здддддддддј дддѓ ДКБП цддддѓ ДКБП цддд X ° ° Y ° ° Z юддддддддды юддддддддды Рис.3. Каскад двух ДКБП. Доказательство: предположим, что Q0 и Q1 - это два произвольных распределения вероятностей на X. Пусть I (X;Y|Z)=I (15) и I (X;Y|Z)=I . (16) Пусть (0,1) будет произвольной, и Q= Q +(1- )Q, а соответствующую взаимную информацию обозначим I. Тогда мы хотим показать, что I +(1- )I <=I. (17) Рассмотрим дополнительную случайную переменную U, принимающую значения {0,1} с вероятностями Pr{U=0}= , Pr{U=1}=1- . (18) Теперь примем Q и Q в качестве условных вероятностей относительно U: если U=0, то входное распределение вероятностей равно Q , а если U=1, то входное распределение - Q . Тогда U, X, Y и Z образуют марковскую цепочку, и выполняются следующие равенства: p(z|y,x,u)=p(z|y) (19а) p(y|x,u)=p(y|x) (19б) p(z|x,u)=p(z|x) (19в) p(z|x,y)=p(z|y). (19г) Теперь p(y|z,u,x)=(p(z|y,x,u)p(y|x,u))/p(z|x,u) (20) =(p(z|y)p(y|x))/p(z|x), (21) что следует из (19а)-(19в). Кроме того, p(y|z,x)=(p(z|y,x)p(y|x))/p(z|x) (22) =(p(z|y)p(y|x))/p(z|x), (23) что следует из (19г). Из (21) и (23) заключаем, что p(y|z,u,x)=p(y|z,x). (24) Следовательно, H(Y|Z,U,X)=H(Y|Z,X). (25) Левая часть (17) равна I(X;Y|Z,U), а правая часть (17) равна I(X;Y|Z). Остагтся показать, что I(X;Y|Z,U)<=I(X;Y|Z). (26) Однако I(X;Y|Z,U)=H(Y|Z,U)-H(Y|Z,U,X) (27) и H(Y|Z,U)<=H(Y|Z), (28) поскольку условность может только уменьшить энтропию. Подставляя (25) и (28) в (27), получаем I(X;Y|Z,U)<=H(Y|Z)-H(Y|Z,X) (29) =I(X;Y|Z) ЧИТД (30) IV. Заключение Мы показали, что можно точно оценить полную достижимую (R,d)область для "симметричных" каналов перехвата. Получены необходимое и достаточное условия, чтобы функция Г(R) была константой, которые оказались полезными в оценке множества достижимых (R,d)-пар для многих каналов. Автор хотел бы поблагодарить профессора М.Е.Хеллмана за многие интересные обсуждения. Литература: 1. Wyner A.D. The wire-tap channel//BSTJ, v.54, pp.1355-1387, Oct 1975. 2. S.K.Leung-Yan-Cheong. Multi-user and wire-tap channels including feedback//Technical Report Э6603-2, Center for Systems Research, Stanford University, Stanford, CA 94305. 3. Р.Галлагер. Теория информации и надгжная связь.