О задаче конфиденциального многостороннего вычисления в кластерном анализе k-means

Секция «Методы и средства зашиты информации»

1.9) Формирование списка сертифицированного ПО в соответствии с государственным реестром сертифицированных средств защиты информации. Результатом выполнения данного мероприятия является создание списка сертифицированного ПО.

Приведем описание мероприятий, которые необходимо выполнить на второй стадии при создании АСЗИ:

2) Разработка концепции АС:

2.1) Поиск путей реализации требований по ЗИ в АС. Для этого этапа необходимы следующие информационные ресурсы: состав, структура, условия размещения АС; модель угроз; модель нарушителя; перечень сведений, подлежащих защите, в том числе о самой АСЗИ; номенклатура требований к АСЗИ; список сертифицированных средств ЗИ; список сертифицированного ПО.

2.2) Оценка возможности реализации требований по ЗИ в АСЗИ. В соответствие с результатами данного мероприятия может быть повторно проведён этап 2. 1.

2.3) Разработка альтернативных вариантов концепции ЗИ в АС и облика СЗИ и процессов её создания. В соответствие с результатами данного мероприятия может быть повторно проведён этап 2. 2.

2.4) Выбор оптимального варианта концепции ЗИ в АС и СЗИ АС.

По окончании второй стадии формируется модель безопасности АСЗИ.

Таким образом, данный алгоритм представляет основные требования и рекомендации международных и национальных стандартов в области защиты информации, регламентирует последовательность действий при создании модели безопасности АСЗИ. Не имеет противоречий с рассмотренными в ходе анализа стандартами.

Библиографическая ссылка

1. ГОСТ Р 51583-201Х Порядок создания автоматизированных систем в защищенном исполнении. Общие положения.

© Березовский Ю. А., 2013

УДК 004.056

А. В. Вашкевич Научный руководитель - В. Г. Жуков Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Красноярск

О ЗАДАЧЕ КОНФИДЕНЦИАЛЬНОГО МНОГОСТОРОННЕГО ВЫЧИСЛЕНИЯ В КЛАСТЕРНОМ АНАЛИЗЕ К-МЕА^

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

С развитием информационных технологий в коммерческой сфере возникла необходимость проводить совместный анализ данных, при этом сохраняя конфиденциальность своих данных, но получая некоторые общие выводы, необходимые для всех участников анализа. С этими целями разрабатывались различные протоколы конфиденциальных вычислений для простых функций, использующие так называемые криптографические примитивы - относительно простые криптографические преобразования [1]. Конфиденциальные вычисления были применены и к наиболее распространённому методу кластеризации - алгоритму к-теаш. Большинство работ по сохранению конфиденциальности данных для кластеризации с помощью к-теапБ основаны на конфиденциальном вычислении данных с несколькими участниками.

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

неса - задача обеспечения конфиденциальности вычислений является актуальной.

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

Тривиальным решением задачи КМВ является использование третьей доверительной стороны (Trusted

Актуальные проблемы авиации и космонавтики. Информационные технологии

Third Party), которой пользователи передают свои данные, - она выполняет вычисления и отсылает результат обратно пользователям. Однако наличие такой доверительной стороны не всегда возможно и допустимо. Поэтому очевидна необходимость разработки криптографических протоколов, специально предназначенных для выполнения соответствующих вычислений в компьютерных сетях без помощи третьей доверительной стороны. Вопросам КМВ уделяется много внимания в современной научно-технической литературе, ежегодно проводятся конференции по данной тематике.

Задачу конфиденциальных вычислений можно описать в следующей постановке. Имеется n участников протокола (процессоров), соединенных сетью связи. Изначально каждому процессору известна своя «часть» некоторого входного значения x. Требуется вычислить f(x), где f - некоторая известная всем участникам вычислимая функция, таким образом, чтобы выполнились требования:

- корректности, когда значение f(x) должно быть вычислено правильно, даже если некоторая ограниченная часть участников произвольным образом отклоняются от предписанных протоколом действий;

- конфиденциальности, когда в результате выполнения протокола ни один из участников не получает никакой дополнительной информации о начальных значениях других участников (кроме той, которая содержится в вычисленном значении функции).

Алгоритм k-means строит k кластеров, расположенных на возможно больших расстояниях друг от друга. Полное описание алгоритма можно найти в работе Хартигана и Вонга [3]. Основной тип задач, которые решает алгоритм k-means, - наличие предположений (гипотез) относительно числа кластеров, при этом они должны быть различны настолько, насколько это возможно. Выбор числа k может базироваться на результатах предшествующих исследований, теоретических соображениях или интуиции.

Формальное описание алгоритма: дан набор данных D из n элементов (объектов, точек и т. п.) в пространстве с m измерениями, а также целое число кластеров k. Алгоритм кластеризации k-means распределяет набор данных в k непересекающихся кластеров. Каждый кластер представлен центроидом (центром кластера).

Данные для кластеризации могут быть по-разному распределены между участниками. Существуют вер-

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

Важными требованиями к конфиденциальному кластерному анализу также являются количество участников, требуемая скорость работы алгоритма и необходимость в сохранении конфиденциальности таких этапов алгоритма, как, например, центры кластеров и количество итераций. Все эти условия оказывают влияние на выбор алгоритма сохранения конфиденциальности в k-means.

Сформированы требования к протоколу обеспечения конфиденциальности данных при их кластеризации и определены этапы алгоритма, которые необходимо защищать при заданных условиях (секционирование данных и количество участников). Также определены возможные пути модернизации существующих протоколов обеспечения конфиденциальности данных при их кластеризации методом k-means. Проделанная работа позволяет в дальнейшем модернизировать существующие протоколы, а также распространить полученные сведения в Российской Федерации.

Библиографические ссылки

1. Meskine F., Bahloul S. N. Privacy Preserving K-means Clustering: A Survey Research. The International Arab Journal of Information Technology. Vol. 9. No. 2. March 2012.

2. Шутый Р. С. Рандомизированные протоколы, применяемые для выполнения конфиденциальных многосторонних вычислений в компьютерных сетях // С.-Петерб. гос. ун-т телекоммуникаций им. проф. М. А. Бонч-Бруевича, 2009.

3. Hartigan J. A.; Wong M. A. Algorithm AS 136: A K-Means Clustering Algorithm // Journal of the Royal Statistical Society, Series C (Applied Statistics) 28, 1979.

4. Samet S., Miri A., Orozco-Barbosa L. Privacy-Preserving K-Means Clustering in Multi-Party Environment. Proceedings of International Conference on Security and Cryptography, Barcelona, Spain, 2007.

© Вашкевич А. В., 2013