Construction of (4,8)-schemes of visual cryptography on the base of a class of linear hash functions.pdf В [1] М. Наором и А. Шамиром предложена (к,п)-схема разделения секрета, представляющего собой чёрно-белое изображение. В основе этой схемы лежит построение на основе исходного изображения n таких чёрно-белых («теневых») изображений, что при совмещении любых k из них (и более) можно восстановить исходное секретное изображение. При этом «совмещение» теневых изображений следует представлять как наложение этих изображений, нанесённых на прозрачную пленку, а «восстановление» - просмотр совмещённых теневых изображений на свет. Свою схему М. Наор и А. Шамир назвали схемой визуальной криптографии. В [1] сначала строятся (k, k)-схемы, а затем на их основе - (к,п)-схема (n > k), в частности, с использованием к-универсальных хэш-функций. В настоящей работе ставится задача построения (4, 8)-схемы на основе класса линейных хэш-функций [2]. Для построения схемы возьмём (4, 4)-схему визуальной криптографии из [1]. Рассмотрим матрицы 1 1 1 0 0 0 0 1 1 0 0 0 1 1 1 0 1 0 0 1 1 0 0 1 , S1 = 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 и соответствующие им коллекции матриц С0 и C1, С = {7(Sl) : 7 Е Ss}, i = 0,1, где Ss - симметрическая группа подстановок; 7(Sl) -перестановка столбцов матрицы S1 в соответствии с перестановкой 7. Для построения четырёх теневых изображений секретное чёрно-белое изображение представляется в виде последовательности нулей (белый пиксель изображения) и единиц (чёрный пиксель). Теневые изображения формируются следующим образом: для очередного пикселя (бита) b Е {0,1} секретного изображения случайным образом выбирается матрица из коллекции Сь ив j-е теневое изображение записывается j -я строка матрицы j Е {1, 2, 3, 4}. Таким образом, один бит секретного изображения кодируется восемью битами теневого изображения (размер каждого теневого изображения в 8 раз больше секретного изображения). Как следует из [1], четыре теневых изображения позволяют восстановить секретное изображение, так как в коллекции С0 все матрицы имеют один нулевой столбец, в то время как в коллекции С1 таких матриц нет. Относительная контрастность секретного изображения, получаемого при совмещении теневых изображений, пропорциональна доле а нулевых столбцов в матрице S0: а = 1/8. Стойкость этой (4, 4)-схемы характеризуется тем, что совмещение трёх и менее теневых изображений не даёт какой-либо информации о секретном изображении (кроме его размера), так как удаление из матриц S0 и S1 любых I (/ Е {1, 2, 3}) строк даёт матрицы S0 и S1, одинаковые с точностью до перестановки столбцов: {Y(S0) : 7 Е Ss} = {7(S1) : 7 Е Ss}. Для построения (4, 8)-схемы воспользуемся правилом построения из [1] на основе хэш-функций. Однако вместо класса k-универсальных хэш-функций применим класс линейных хэш-функций. Рассмотрим множество H всех (0,1)-матриц размера 3 х 2, |H| = 26 = 64. Для H Е H определим функцию H • xT -'г , где x fH : {0,1}3 ^{0,1}2 действующую на элемент x Е {0,1}3 по правилу fn(x) рование x. Класс функций Fh = {fH : H Е H} является 2-универсальным классом линейных хэш-функций [2]. Пусть b : {0,1}1 ^ ^ {1,... , 21} - функция, ставящая однозначно в соответствие вектору из {0,1}1 число из множества {1,... , 21}, b-1 : {1,... , 21} ^ {0,1}1 -обратная к b функция; рассмотрим также функцию h : {1,..., 64} ^ H, однозначно сопоставляющую десятичным числам из множества {1,..., 64} матрицы из H. S0 Для построения (4, 8)-схемы необходимо построить коллекции матриц С0 и С1, с помощью строк которых будут кодироваться белые пиксели (нулевые биты) и черные пиксели (единичные биты) соответственно. Представляется удобным описать формирование матрицы Е Сь для кодирования бита b, а не вводить громоздкое определение коллекции Сь. Для построения матрицы случайным образом выбираются (возможно, с повторениями) 64 матрицы T-f, ... ,T64 из коллекции Сь, построенной для (4, 4)транспони-схемы. Тогда элемент i-й строки (1 ^ i ^ 8) и (j • /)-го столбца (1 ^ j ^ 8, 1 ^ I ^ 64) матрицы формируется следующим образом: 5b[i,j • 1] = Tib[b2(/h(0(b3-1(i))),j], (2) где Д(г) -функция вида (1). Отметим, что построенная таким образом матрица имеет 8 строк и 512 столбцов. Правило (2) предложено в [1], за исключением того, что в [1] используемый класс F хэш-функций должен быть применительно к (4, 8)-схеме 4-универсальным, а именно: для всех подмножеств B С {1,... , 8}, |B| = 4, и всех q, 1 ^ ^ q ^ 4, вероятность того, что случайно выбранная функция / G F имеет q различных значений на множестве B, одна и та же. В настоящей работе доказано утверждение, из которого следует, что класс функций вида (1) не является 4-универсальным классом. Утверждение 1. Пусть B - множество двоичных (4 х 3)-матриц, состоящих из попарно различных строк; C(B,H) -число различных значений, которые функция /я G FH принимает на множестве строк матрицы B G B, СБ (l) = |{H GH : C (B, H) = 1}|, l = 1,..., 4. Тогда B = B1 U B2 U B3, |B11 = 56, |B2| = |B31 = 7, причём B^ П Bj = 0 для всех i = j и 1) CB(1) = 1, CB(2) = 21, CB(3) = 36, CB(4) = 6 для всех B G B1; 2) CB(1) = 4, CB(2) = 36, CB(3) = 0, CB(4) = 24 для всех B G B2; 3) Cb(1) = 4, Cb(2) = 36, Cb(3) = 0, Cb(4) = 24 для всех B G B3. Утверждение 2. Пусть (4, 8)-схема визуальной криптографии построена с применением класса линейных хэш-функций по правилу (2) на основе (4, 4)-схемы. Тогда построенная (4, 8)-схема характеризуется относительной контрастностью, пропорциональной числу а = 0,01875. Отметим, что стойкость (4, 8)-схемы следует из стойкости (4,4)-схемы [1]. Полученные результаты показывают, что возможно построение схем визуальной криптографии на основе 2-универсальных классов хэш-функций, при этом обеспечивается приемлемая для схем визуальной криптографии относительная контрастность восстанавливаемых изображений [3]. Недостатком предложенной схемы является большое увеличение размеров теневых изображений. В частности, размер каждого теневого изображения увеличивается в 512 раз. Представляется, что сокращения размера теневых изображений можно добиться путем использования не всего класса FH, а случайно выбранного подмножества из этого класса.

Скачать электронную версию публикации