О скрытом компактном способе хранения данных | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/17

О скрытом компактном способе хранения данных

Предлагается принципиально новый способ компактного хранения данных в скрытом виде. Каждое из этих данных может быть извлечено единообразным способом. Приводится сравнение с другими возможными способами такого хранения.

About the hidden compact way to store data.pdf Исследование поддержано Программой фундаментальных научных исследований СО РАН I. 1.1.4, проект №0314-2019-0004. Допустим, имеются данные a^, i = 1,... , n, каждое из которых представляет собой бинарную строку длины m, то есть ai G {0,1}m. Предположим, что эти данные необходимо хранить в компактном скрытом виде X, имея простой единообразный способ извлечения из X любого из них. Такая проблема может возникнуть при хранении в облаке, а также в других случаях защищённого хранения. Например, её решение может иметь значение для поисковых систем. Может также возникнуть потребность хранить данные, разбитые на подмножества по типу данных или их принадлежности. В работе представлен принципиально новый способ решения указанной проблемы. Но сначала рассмотрим некоторые напрашивающиеся идеи такого хранения. Хранение в зашифрованном виде. Можно использовать какую-нибудь систему шифрования и хранить данные в виде Ek(ai), i = 1,... ,m, где Ek - функция зашифрования с ключом k. Такой способ, конечно, обеспечивает свойство «скрытости», но непонятно, как обеспечить компактность. Нужно хранить ключи, зашифрованные данные могут быть существенно большего объёма и т. п. Эффективность такого способа хранения зависит от свойств выбранной системы шифрования. Если использовать один ключ для всех данных, то ключ расшифрования не может быть делегирован пользователю, которому необходимо извлечь только какие-то данные, к которым ему может быть предоставлен доступ. Возможно, что указанные недостатки могут быть устранены, но для этого требуется отдельное исследование. Использование Китайской теоремы об остатках. Напомним эту известную теорему (см., например, [1]). Предположим, что целые числа m1,... , mn ^ 2 попарно взаимно просты. Тогда система сравнений x = b (mod mi), i = 1,... , n, всегда имеет решение X, которое находится следующим образом. Полагаем Mj = M/mi, где M = n = П mj. В силу попарной взаимной простоты модулей m^ существуют числа Lj, для i=1 n которых LjMj = 1 (mod mi). Тогда число X = b^M^ является решением системы. i=1 Более того, решением является любое целое число Y, такое, что Y = X (mod M), и других решений нет. Покажем, как можно организовать скрытое компактное хранение данных, используя эту теорему. Сопоставим каждой последовательности ai G {0,1}m натуральное число bi, получающееся, если считать запись ai выражением числового значения в двоичной системе. Выберем попарно взаимно простые модули mi > bi, i = 1,..., n. Храним данные bi в виде решения X рассмотренной выше системы. Для извлечения bi вычисляем X по модулю mi. Скрытость и возможность единообразного извлечения данных обеспечены, чего нельзя сказать в общем случае о компактности этого способа хранения данных. Действительно, если числа bi достаточно большие, то и модули mi большие. Если данных достаточно много, то число M (а также числа Mi) становится нереально большим. Это не только замедлит вычисления, но может сделать само хранение практически нереализуемым. Хранение в «магическом» квадрате. Пусть d = d1, d2,..., di,... -последовательность целых чисел. Дискретная производная d' этой последовательности определяется формулой d = d2 - di, d3 - d2,..., di+i - di,... Очевидно, что производная аддитивна. Для любой последовательности определяется дискретный интеграл f = f 1, f2,... , fi,..., f' = d. Интеграл определяется с точностью до произвольной константы c формулой i-1 =c + Е . j=i При выборе fi = c все остальные компоненты интеграла f определяются однозначно. Обозначим f = I(d, c). Пусть дана постоянная последовательность c(0) = c,... , c,... Обозначим c(1) = = I(c(0),c), c(2) = I(c(1),c), ... Тогда значение k-й производной от c(k) равно c(0). Записываем это в виде [c(k),z; k] = c. При i < k имеем [c(i),x; k] = 0. Мы несколько упростили запись, поставив в правую часть значение постоянной последовательности, а не саму эту последовательность. Символ z введён для различия в дальнейшем переменных интегрирования. Пусть имеется n ненулевых целых чисел c1,... , cn. Для каждого i вычислим интеграл c(n г). Построим квадратную таблицу со стороной n +1. Запишем в нижней строке первые n +1 элементов интеграла cin г). Получим набор (ci,1,1,... , ci,1,n+1). Затем для каждого элемента нижней строки ci,1,j определим постоянную последовательность c^j и вычислим для неё интеграл c(i) j. Тогда [c(i) j , y; i] = ci,1,j. Поставим в соответствующий столбец таблицы первые n +1 элементов этого интеграла. Пусть X означает сумму всех таких таблиц. Теорема 1. Справедлива формула [X,y; i,z; n - i]M = c*. Формула означает, что i-кратное дифференцирование столбцов с последующим (n - i)-кратным дифференцированием нижней строки даёт в левом нижнем углу значение q. Замечание 1. - Если записывать все последовательности, а не только их начальные отрезки, то в результате проведённых операций получится бесконечная вправо и вверх таблица, в которой во всех клетках будет стоять соответствующая константа. - Так как натуральное отображение вида Z ^ Zr является гомоморфизмом, то можно выбрать r > max (6 : i = 1,...,n) и вести все построения над элементами кольца Zr. Мы не приводим доказательство теоремы; дадим только небольшой иллюстрирующий пример. Пример 1. Пусть b1 = 12, 62 = 7, 63 = 3. Вычисления ведём в кольце Z13. Запишем в общем виде начальные интервалы длины 4 от константы а: а^ = (а, 2а, 3а, 4а), а^2 = (а, 2а, 4а, 7а), а^3) = (а, 2а, 4а, 8а). Запишем квадраты для 61 = 12, 62 = 7, 63 = 3: 10 7 1 5 2 4 8 1 12 4 7 7 1 2 10 7 2 10 5 9 5 10 10 7 1 11 9 5 12 11 9 11 9 7 5 12 11 10 9 6 12 5 11 3 6 9 12 Тогда 4 8 5 4 11 9 6 12 X 5 10 1 2 9 5 7 1 Для проверки проводим вычисления, записывая только те строки и столбцы, значения в которых полностью определяются заданными квадратами: 6 12 12 5 6 12 5 10 9 5 7 1 0078 10 7 11 9 [X, y; 1] [X, y; 2] [X, y; 3] 3 6 9 12 [X, y; 1, z; 3] 1,1 = 12, [X,y;2,z;2]i,i = 7, [X, y; 3, z; 1]M = 3.

Ключевые слова

данные, хранение, скрытость, компактность, доступ, data, storage, hidden, compactness, access

Авторы

ФИООрганизацияДополнительноE-mail
Романьков Виталий АнатольевичОмский государственный университет им. Ф. М. Достоевского; Институт математики им. С. Л. Соболева СО РАН (Омский филиал)доктор физико-математических наук, профессор, заведующий кафедрой; главный научный сотрудникromankov48@mail.ru
Всего: 1

Ссылки

 О скрытом компактном способе хранения данных | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/17

О скрытом компактном способе хранения данных | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/17