Модифицированное безопасное скалярное произведение в конфиденциальном кластерном анализе k-means с вертикальным секционированием данных

При проведении совместного анализа данных, принадлежащих разным организациям (пользователям) и являющихся конфиденциальными, не всегда достаточно обеспечения той конфиденциальности, что достигается при помощи традиционных криптосистем; необходимо обеспечить получение совместного результата без раскрытия самих исходных данных [1]. Задачи такого вида называются конфиденциальными многосторонними вычислениями (КМВ) – используются специальные протоколы, позволяющие нескольким участникам произвести вычисления на основе конфиденциальных входных данных каждого из них. После выполне- ния протокола КМВ каждый из участников получает результат вычисления, но ни один из них не должен иметь возможность получения никакой дополнительной информации о данных других участников.

В алгоритмах конфиденциальной кластеризации используется модель с получестными (semi-honest) участниками. Получестный участник следует протоколу, но волен использовать ту информацию, к которой он имеет доступ во время выполнения протокола, для попытки раскрытия данных других участников. При этом рассматривается возможность сговора (т. е. объединения знаний) некоторых из участников [2].

Работа поддержана грантом Президента молодым кандидатам наук, договор № 14.124.13.473-МК от 04.02.2013.

Участник №1		Участник №2	Участник №3
Атрибут №1	Атрибут №2	Атрибут №1	Атрибут №1	Атрибут №2	Атрибут №3

Рис. 1. Пример вертикального секционирования

На первом этапе исследований по применению КМВ в кластерном анализе рассматривался алгоритм, позволяющий работать с большими объемами данных и имеющий простую структуру. Наиболее распространенным и изученным алгоритмом кластерного анализа, удовлетворяющим предъявляемым требованиям, является алгоритм k-means.

Данные для многостороннего кластерного анализа могут быть по-разному распределены между участниками. Существует вертикальное (участники содержат разные столбцы данных), горизонтальное (участники содержат разные строки данных) и арбитральное (произвольное) секционирования данных. В вертикальном секционировании данных (рис. 1) каждый участник имеет набор только некоторых атрибутов, но каждого из объектов. При таком секционирование начальный выбор центров кластеров не является конфиденциальным, а защищаются такие шаги k-means, как вычисление расстояний между каждой точкой и центрами, выбор минимального расстояния для каждой точки, а также проверка условия остановки кластерного анализа.Алгоритм конфиденциальной кластеризации методом k-means при вертикальном секционировании:

Требуется: r участников, k кластеров, n точек.

• 1:    для всех участников j = 1, ..., r

• 2:    для всех кластеров i = 1, ..., к

• 3:      произвольная инициализация центров

кластеров ц ' j

• 4:    повторять

• 5:    для всех участников j = 1, ..., r

• 6:        для всех кластеров i = 1, ..., к

• 7:            Ц у =Ц ' у

• 8:            кластер [ i ] = 0

• 9:    для всех точек g = 1, ..., n

• 10:      для всех участников j = 1, ..., r

• 11:         {Вычисление вектора X _j от точки g

до каждого центра кластера по измерению j }

• 12:           для всех кластеров i = 1, ..., к

• 13:                   x_ij = |данные точки g_j –

данные центра кластера Ц у |

• 14:     каждый участник помещает g в кластер

[ближайший] {алгоритм определения ближайшего кластера должен сохранять конфиденциальность}

• 15:    для всех участников j = 1, ..., r

• 16:       для всех кластеров i = 1, ..., к

• 17:           ц ' у - среднее всех точек кластера [ i ]

по атрибуту j

• 18:    пока не выполнится условие останова {алгоритм проверки условия останова должен сохранять конфиденциальность}

За основу для модернизации [3] взята схема конфиденциального кластерного анализа k-means при вертикальном секционировании, предложенная Саметом и соавторами [4], так как в отличие от других решений для данного секционирования в ней отсутствуют так называемые «особые» участники, выполняющие дополнительные операции с данными.

Обозначим набор атрибутов, содержащихся у P_i (участника     под номером i ), как

A i = { a i 1 , a i ₂ , ..., a im } . Также P i владеет наборами атрибутов каждого из центров кластеров ц _j7 = { ц _j7 1 , ц _{j7 2} , ..., ц j _im } . Затем каждый участник суммирует расстояния между соответствующими измерениями. Так, порция расстояния между точкой и центром кластера ц ji у участника P i будет выглядеть следующим образом (пример для квадрата евклидового расстояния):

dji = ( ai 1 — ц ji 1) + ( ai 2 — ц ji 2 ) + - + ( aim - ц jim )

Просуммировав по всем участникам эти расстояния, получим dj 1 + dj2 +... + djr, где r - число участников. Для центра другого кластера цq имеем похожую формулу dq 1 + dq2 +... + dqr. Чтобы определить, какой из кластеров ( j или q ) ближе к точке, нужно rr просуммировать значения Z (dji- dqi)= ^ di . Если i=1                         i=1

результат положительный, цq будет ближе к точке, иначе ближе ц j. Этот шаг повторяется k -1 раз, чтобы найти минимальное из расстояний от точки до центра кластера. При этом ни одно из расстояний не раскрывается.

Однако реализация данной схемы Саметом и соавторами имела два существенных недостатка, которые обязательно требовалось устранить:

– для двух участников применялся криптографический примитив «безопасное скалярное произведение» [5], предложенный Малеком и Мири;

– для участников количеством более двух применялся примитив «безопасная сумма» [6], в котором раскрываются данные любого из участников при сговоре его соседей по алгоритму.

Схема применения Саметом и соавторами криптографического примитива «Безопасное скалярное произведение»:

0) Участник P ₁ имеет конфиденциальное значение d j 1 — d q i = d 1 , а P 2 имеет конфиденциальное значение d j 2 — d q 2 = d 2 , требуется получить числа 1 1 и l ₂ такие, чтоб 1 1 хранился у P 1 , l ₂ у P₂ и 1 1 • l ₂ = d 1 + d ₂;

• 1)    P ₁ генерирует случайное ненулевое число l ₁ и

• | dl 1 |

создаёт вектор X = —,— , а р создаёт вектор I l i l i )

Y = ( 1; d 2 ) ;

• 2)    P ₁ и P ₂ выполняют безопасное скалярное произведение [5] и P ₂ получает число l ₂ такое, что 1 1 • l ₂ = d 1 + d ₂.

• 3)    P₂ посылает знак 1 ₂. Если 1 ₂ = 0, то до обоих кластеров одинаковое расстояние, если l ₂ * 0 , то знак показывает кластер, до которого расстояние меньше.

Формальное описание протокола безопасного скалярного произведения:

Предположим, что у двух участников (назовем их Алисой и Бобом) есть по n -мерному вектору: x = { x 1 , x 2 , -> x n } ^- у Алисы и y = { У 1 , y 2 , ..., У п } ^-у Боба. Каждое измерение вектора является конечным полем F_p , а пространство векторов – конечным n -мерным расширением F_p ⁿ конечного поля F_p .

Алиса и Боб хотят совместно и с сохранением конфиденциальности посчитать x • у . Результат протокола должен быть известен только Алисе. Входные данные каждого из участников не должны быть раскрыты друг другу. Для достижения этих целей Алиса и Боб выполняют следующий протокол:

• 1.    Алиса генерирует случайные вектор фе F_pⁿ и числа a , b , c , d е F_p такие, что ( ad - bc ) ¹ * 0 е F_p . Алиса вычисляет следующие векторы:

• 2.    Затем Алиса посылает векторы u и v Бобу.

3. Алиса вычисляет

u = ax + b ф,

v = cx + dф .

Зная свой вектор y , Боб вычисляет у • u и y • v. За- тем Боб отправляет результаты обратно Алисе.

(ad -bc) 1 (d(y • u)-b(y • v)), что эквивалентно x • y .

Следует отметить два момента, из-за которых применение данной схемы некорректно. Первым таким моментом является то, что примитив Малека и Мири предназначен для конечных полей. Таким образом, нельзя после выполнения примитива использовать знаки чисел l1 и l2 для достоверного определе- ния знака суммы d1 + d2.

Пример, доказывающий данное утверждение:

Есть конечное поле

• { - 5, - 4, - 3, - 2, - 1, 0, 1, 2, 3, 4, 5 } . d 1 = - 1, d ₂ = - 2 .

Допустим, l 1 = 2. Тогда после проведения безопасного скалярного произведения будет получено 1 ₂ = 4 , так как в данном конечном поле 2 • 4 = - 1 - 2 .

Знаки чисел l1 и l2 оба положительные, а знак суммы отрицателен. Следовательно, данный протокол не всегда работает в конечных полях.

Таким образом, использование знаков после операций в конечных полях не всегда будет давать корректный результат. Данный недостаток устраняется использованием множества вещественных чисел вместо конечных полей. При этом все операции безопас- ного скалярного произведения сохраняют корректность. Данное решение также имеет полезность в том, что использование конечных полей ухудшает точность проведения кластерного анализа, так как необходимо было бы «накладывать» область допустимых значений на конечное поле, что породило бы погрешность из-за необходимости квантования.

Вторым моментом, из-за которого некорректно применение предложенной Саметом и соавторами схемы, является использование двумерных векторов

( 1; ^d 2 ) ^и

' d , ;¹ ^ 1 1 1 l 1 J

. Анализ криптографического при- митива показал, что использование двумерных векторов раскрывает данные Боба Алисе. Причина в шаге 2 криптографического примитива, когда Боб посылает Алисе результаты скалярных произведений y • u и y • v. Алиса, таким образом, получает два уравнения с двумя неизвестными:

y 1 u 1 + y 2 u 2 = y • u ,

y1 v1 + у 2 v 2 = у • v , где векторы u и v уже известны Алисе, а результаты скалярных произведений y • u и y • v она получила от Боба. Решив эти уравнения, Алиса вычисляет значе- d1

ния и , откуда узнает d , т. е. косвенные сведе- l 1         l 1                                     ¹

ния о данных Боба ( d j 1 - d q 1 , разница между расстояниями от точки до одного кластера и до другого) становятся известны Алисе и, следовательно, нет обеспечения конфиденциальности данных одного из участников кластерного анализа.

Эту проблему можно решить, искусственно разбив два измерения векторов (1;d2) и —;—I на три. По-х I li 11)

сле разбиения векторы будут выглядеть следующим образом:

• - вектор Алисы ( 1;1; d ₂ ) ,

  – вектор Боба

  
  

d1 + z _ - z _ 1 | v l1 к к J где z – случайное число, сгенерированное Бобом. Скалярное произведение данных векторов останется прежним, но теперь в двух уравнениях станет три не-

_ d + Z - z 1 _ _ _ известных: 1 , и , из которых «любопыт-l1 l1 l1

ному» (согласно модели нарушителя) участнику Алисе в общем случае будет нельзя получить значение d ₁ Боба. Однако при определенных параметрах векторов u и v раскрытие информации все-таки останется возможным, поэтому Боб должен проверять присланные ему от Алисы векторы u и v на следующие условия (они могут выполняться по отдельности, но не одновременно):

u1 = u 2, v1 = v2

потому что при выполнении обоих этих условий из уравнений можно будет узнать отдельно di + z | - z |            1

--+ — I и —, а   значит,   получить

• ^l 1        V ^l 1 J                ^l 1

  

Также следует отметить, что безопасное скалярное произведение проводится для двух участников. При использовании этого примитива для нескольких участников следует применять схему, также описанную у Самета и соавторов. Пример для трёх участников:

• 1.    P ₃ дробит своё значение d ₃ на случайные кусочки d ₃₁ и d 32 такие, что d ₃₁ + d 32 = d 3 , и выбирает случайное число r₃ * 0.

• 2.    P ₃ и P ₁ выполняют SDP, и P ₁ получает s ₁ такое, что d ₃₁ + d 1 = r ₃ • s 1 .

• 3.    P ₃ и P ₂ выполняют SDP, и P ₂ получает s ₂ такое, что d ₃₂ + d 2 = r ₃ • s 2 .

• 4.    P 2 и P выполняют SDP для получения S 1 + s ₂ .

• 5.    На выходе получается:

• 6.    Если r 1 = 0, P 1 рассылает всем флаг, что расстояния до кластеров одинаковые, иначе он посылает знак r ₁ участнику P ₂ , тот умножает знак r ₁ на знак r ₂ и посылает участнику P ₃ . Участник P ₃ умножает полученный знак на знак r ₃ и узнает, какой из кластеров ближе к точке, а затем рассылает всем.

  
  
  

d 1 + d ₂ + d ₃ = r₃ • ( S j + s ₂ ) = r 1 • r₂ • r₃ (рис. 2).

Причем участник P_i знает только d_i и r_i .

Основной минус данного алгоритма в том, что количество данных, передаваемых по сети, растёт пропорционально квадрату количества участников. Именно по этой причине алгоритм не подходит для кластерного анализа с большим количеством участников и обрабатываемых данных, поскольку он применяется на каждой итерации для каждого объекта данных к — 1 раз.

В связи с проектированием программного обеспечения, реализующего данный протокол, стало возможно сравнить сетевой трафик (рис. 3), генерируемый алгоритмом с использованием того или иного криптографического примитива.

Тем не менее, если к конфиденциальности предъявляются жёсткие требования, следует применять примитив «безопасное скалярное произведение», поскольку в нём гарантируется сохранение конфиденциальности даже при сговоре против одного из участников всех остальных (рис. 4).

Таким образом, устранив недостатки схемы по применению безопасного скалярного произведения, можно использовать данный криптографический примитив для определения ближайшего кластера. Однако применение безопасного скалярного произведения требует передачи данных от каждого участника каждому, что при большом количестве участников и большом количестве объектов данных приведет к большому объему трафика. Поэтому использование безопасного скалярного произведения рекомендуется к применению для малого количества объектов данных или участников, когда велик риск сговора и на первый план выходит обеспечение конфиденциальности данных в ущерб скорости работы алгоритма.

Рис. 3. Зависимость количества переданных байт за одну операцию сравнения расстояний от количества участников

Рис. 4. Зависимость максимального допустимого количества сговорившихся участников от общего количества участников