Confidentiality preserving scheme for the algorithm raid-pir.pdf Под анонимностью в сетях передачи данных, как правило, понимается либо невозможность идентификации сервером пользователей, отправивших запрос (анонимность пользователя), либо невозможность идентификации сервером запрашиваемой пользователями информации (анонимность запроса) [1]. В настоящей работе рассматривается обеспечение второго варианта анонимности. Предполагается, что для хранения информационной базы данных используется несколько серверов. Пользователь заинтересован в получении некоторой части базы данных таким образом, чтобы серверы, участвующие в хранении, по отдельности не смогли идентифицировать, какая именно часть базы была запрошена пользователем. В подобных схемах серверы могут рассматриваться как недобросовестные наблюдатели, цель которых заключается в выяснении, в получении какой информации из базы данных заинтересован пользователь. Простейшим случаем обеспечения анонимности является схема с одним сервером, когда пользователь с сервера запрашивает всю базу полностью [2]. Обычно в системах обеспечения анонимности запроса предполагается, что серверу может быть известно (частично или полностью) информационное содержимое базы. В работе рассматривается ситуация, когда знание сервером базы нежелательно, при этом необходимо также защититься от получения сервером информации о расположении или доле запрашиваемой информации в базе. Таким образом, ставится задача построения схемы защиты конфиденциальности информационной базы данных, позволяющей анонимно считывать данные из базы и перезаписывать их. Пусть DB Е Fn - информационная база данных, представленная в виде конкатенации b блоков длины k бит каждый: DB = (d1,...,db), Е F^, а для хранения базы DB используются r серверов хранения S1,... , Sr, где r - нечётное число. Целью пользователей этой системы хранения является получение j-го (j Е {1,..., b}) блока базы DB таким образом, чтобы каждый из серверов не узнал j. Для этого пользователь отправляет специальные вектор-запросы всем серверам, а серверы вычисляют побитовые суммы блоков, соответствующих вектор-запросу пользователя, и отправляют пользователю результаты суммирования. Вектор-запрос к серверу - это бинарный вектор, в котором единицы находятся на позициях с номерами блоков базы, которые сервер должен просуммировать в ответ. Отметим, что способ построения запросов и соответствующих ответов, при котором отдельный сервер может знать информационное содержимое базы, но не может по запросу понять, какой именно блок запрошен пользователем, предложен в [3]. Далее схему из [3] назовём RAID-PIR. В настоящей работе на базе варианта RAID-PIR, когда каждый сервер отвечает несколькими блоками, строится решение задачи обеспечения конфиденциальности информации в базе относительно серверов. Для этого используется шифрование методом модульного гаммирования с r - 1 случайными (псевдослучайными) ключами длины n. Предполагается, что для генерации ключевой последовательности (гаммы) используется генератор непредсказуемой последовательности чисел, который обозначим rnd_gen. Построены четыре протокола: распределения базы по серверам (DistribDB), чтения i-го блока из базы (GetBlock), перешифрования данных на серверах (NewKey) и перезаписи i-го блока в базе (SetBlock). Параметром протоколов является число p (1 < p < r) -число зашифрованных на разных ключах копий базы DB, хранимых на каждом сервере. Алгоритм 1. DistribDB - распределение базы DB Е Fn по серверам S1,..., Sr 1: Владелец базы строит набор Г = {Г1,..., Гг}, где для j = 1,..., r - 1 вектор Г = r- 1 = (Yj,... , Yj), Yj Е , генерируется с помощью генератора rnd_gen; Гг := ф Г\ i=1 2: По DB и Г вычисляются векторы: DB^ = DB ф Г-7 = (dj,..., dj), j = 1,... , r. 3: Серверу S-7 передаются DBfmod (r+1)+7/(r+1)J,..., db[7'+p-1) mod (r+1)+L(j+p-1)/(r+1)J, j = 1,...,r. Алгоритм 2. GetBlock - получение i-го блока (блока d^) из базы DB 1: Пользователь с помощью алгоритма RAID-PIR получает i-й блок dj с каждого вектора DB^, j = 1,..., r. r r r r 2: Пользователь вычисляет: ф dj = ®(y7 © dj) =1 ф y7 I ©I Ф dj ). Так как 7=1 7=1 \7=1 J \7=1 rr ф y7 = 0(е F^) и r - нечётное число, то ф dj = d». 7=1 7=1 Алгоритм 3. NewKey - перешифрование данных на серверах с помощью набора Г = {Г1,..., Гг } 1: Пользователь передаёт на сервер Sj, j = 1,..., r, соответствующие этому серверу p векторов: Г j m°d (r+1) + UV(r+1)j , . . . , p(j+p-1) mod (r+1) + |_(j+p- 1)/(r+1)j. 2: Сервер Sj обновляет хранящиеся у него части: ББгг := ББгг ф Г1, где / Е {j mod (r + 1) + Lj/(r + 1)J ,..., (j + p - 1) mod (r + 1) + [(j + p - 1)/(r + 1)j}, j = 1,...,r. Алгоритм 4. SetBlock - перезапись i-го блока в базе DB новым значением dj 1: Пользователь получает i-й блок базы (dj = GetBlock(i)), генерирует новый набор Г = {Г1,... , Гг} (Г ^ rnd_gen) и для каждого rj = (Г1,... ,rj) из Г переопределяет Г: Г? := 7j ф (dj ф dj). 2: Пользователь выполняет протокол перешифрования NewKey (Г). Показано, что 1) протоколы GetBlock и SetBlock обеспечивают анонимность соответственно запрашиваемых и записываемых данных; 2) протоколы DistribDB, NewKey и SetBlock обеспечивают конфиденциальность хранимых на серверах данных; 3) любая коалиция мощности t < |~r/p] не может нарушить конфиденциальность базы данных, а любая коалиция мощности t ^ r - p +1 однозначно дешифрует базу данных.

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