И. Д. Иогансон

Протокол пересечения множеств с сохранением конфиденциальности

Введение. Протокол пересечения закрытых множеств (Private Set Intersection, PSI) является одним из фундаментальных примитивов конфиденциальных вычислений. Данный примитив позволяет нескольким сторонам, которые не доверяют друг другу, совместными усилиями вычислить пересечение их секретных множеств без разглашения при этом дополнительной информации об этих множествах. Это позволяет пользователям совместно проводить анализ данных без раскрытия конфиденциальной информации друг другу. Метод. В работе представлен новый протокол пересечения закрытых множеств для трех и более участников. Протокол работает в сети с топологией типа «кольцо». Это минимизирует количество необходимых каналов связи между пользователями. Протокол основан на идее условного разделения нуля, позволяющей использовать схему разделения секрета для определения принадлежности элемента множества всем пользователям. Для оценки быстродействия нового решения предложена программная реализация протокола на языке С++. Основные результаты. Показана безопасность разработанного протокола для трех и более пользователей при условии, что пользователи не будут сговариваться друг с другом для «Honest-But-Curious» модели злоумышленника. Предложенная модель подразумевает, что злоумышленником является один из участников протокола, который корректно выполняет протокол, но может анализировать полученную в ходе этого информацию для извлечения выгоды. Безопасность протокола основывается только на предположении о недостатке у злоумышленника информации для получения каких-либо полезных данных из полученных во время выполнения протокола сообщений. Таким образом, этот протокол обладает информационно-теоретической стойкостью. Обсуждение. Представленный протокол может быть использован для конфиденциального анализа данных, например, при обмене несколькими компаниями информацией об общих клиентах. Протокол позволяет трем пользователям найти пересечение множеств размера 106 примерно за 42 с. В настоящей реализации существует возможность добавления многопоточности или перенос вычислений больших матриц с процессора на графический ускоритель.