Рандомизированные протоколы, применяемые для выполнения конфиденциальных многосторонних вычислений в компьютерных сетях

• Автор: Шутый, Родион Сергеевич
• Шифр специальности: 05.13.13
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Санкт-Петербург
• Количество страниц: 170 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

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

И КРИПТОГРАФИЧЕСКИЕ ПРИМИТИВЫ

1.1. Определение конфиденциальных многосторонних вычислений

1.2. Модель и классификация конфиденциальных многосторонних

вычислений

1.2.1 Способы преобразования обычных вычислений к

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

1.2.2. Классификация конфиденциальных многосторонних вычислений.1

1.2.3. Применение криптографических примитивов для решения конфиденциальных многосторонних вычислений
1.3. Анализ криптографических примитивов, используемых для построения конфиденциальных многосторонних вычислений
1.3.1. Протокол Забывчивая передача.
1.3.2. Протокол Передача данных на хранение.
1.4. Общее решение конфиденциальных многосторонних вычислений
1.5. Выводы по разделу.
2. МОДИФИЦИРОВАННЫЙ ПРОТОКОЛ ЗАБЫВЧИВАЯ ПЕРЕДАЧА
И МЕТОДИКА ОПТИМИЗАЦИИ ЕГО ПАРАМЕТРОВ
2.1. Анализ протокола Забывчивая передача для цепочек бит на основе канала с ошибками
2.2. Модифицированный протокол Забывчивая передача
с использованием интерактивного хэширования.
2.2.1. Разработка модифицированного протокола.
2.2.2. Методика оптимизации параметров протокола
2.3. Анализ обобщенного протокола Забывчивая передача
2.4. Анализ усиленного протокола Забывчивая передача.
2.5. Выводы по разделу.
3. МОДИФИЦИРОВАННЫЙ ПРОТОКОЛ ПЕРЕДАЧА ДАННЫХ НА ХРАНЕНИЕ И МЕТОДИКА ОПТИМИЗАЦИИ ЕГО ПАРАМЕТРОВ
3.1. Анализ протокола Передача бита на хранение для цепочек бит
на основе канала с изменяемой вероятностью ошибки
3.2. Модифицированный протокол Передача бита на хранение для цепочек бит на основе канала с изменяемой вероятностью ошибки
3.3. Выводы по разделу.
4. МЕТОДИКИ РАСЧЕТА ПАРАМЕТРОВ ПРОТОКОЛОВ КОНФИДЕНЦИАЛЬНЫХ МНОГОСТОРОННИХ ВЫЧИСЛЕНИЙ НАД БАЗАМИ ДАННЫХ НА ОСНОВЕ МОДИФИЦИРОВАН НОГО ПРОТОКОЛА ЗАБЫВЧИВАЯ ПЕРЕДАЧА.
4.1. Базовые протоколы конфиденциальных вычислений и методики их расчета.
4.1.1. Разработка методики расчета параметров протокола конфиденциального сравнения чисел
4.1.2. Разработка методики расчета параметров протокола конфиденциального умножения чисел
4.1.3. Разработка методики расчета параметров протокола конфиденциального вычисления скалярного произведения векторов.
4.2. Протоколы конфиденциальных вычислений с базами данных.
4.2.1. Разработка методики расчета параметров протокола
сравнения столбцов таблиц баз данных.
4.2.2. Разработка методики расчета параметров протокола нахождения доминирующего столбца таблиц
4.2.3. Разработка методики расчета параметров протокола поиска часто встречающихся наборов в таблицах.
4.2.4. Выводы по разделу
ЗАКЛЮЧЕНИЕ.
СПИСОК ЛИТЕРАТУРЫ


При этом ни медицинское учреждение, ни исследовательский институт не должны раскрывать информацию о пациентах, иначе если институт, проводящий исследование, узнает, что у пациента есть данное заболевание, то он может получить дополнительную информацию о пациенте, например о других проблемах со здоровьем, которые могут быть у пациента. Кроме того, если эта информация будет раскрыта, то у пациента могут возникнуть проблемы при устройстве на работу, получении кредита и т. Третий пример . Банк хочет проверить кредитную историю заемщика перед выдачей кредита, так как банк должен быть уверен в том, что заемщик сможет выплатить кредит. Для этого он обращается в кредитное агентство, у которого есть финансовый отчет о заемщике. Но отчет содержит достаточно большое количество конфиденциальной информации о заемщике информация о выданных кредитах, наличие долгов, количестве просроченных платежей и другие данные о финансовой истории заемщика. Банк должен узнать только необходимую ему информацию. Критерии, по которым банк предоставляет кредит, являются конфиденциальной информацией банка. При этом кредитное агентство не должно знать заемщика, по которому запрашивается отчет, и готов ли банк выдать ему кредит. Таким образом, возникает задача проверки кредитной истории заемщика без разглашения конфиденциальной информации о нем. Для решения подобных задач участники должны выполнить некоторый протокол. Участники могут быть как пассивными нарушителями, так и активными. Активный нарушитель не следует протоколу и может игнорировать некоторые шаги протокола или посылать не ту информацию, которая требуется. Для строгого и формального описания задач КМ В и протоколов, на основе которых эти задачи решаются, введем модель КМВ. Рассмотрим модель КМВ, показанную на рис. Пусть у каждого из п участников есть секретные данные входы х. Такими входами могут быть числа, вектора, матрицы, множества, графы и т. С помощью блока вычислений участники обмениваются данными и вычисляют функцию . Рис. Рассмотрим далее способы, с помощью которых можно преобразовать обычные вычисления к КМВ рис. Учк 1
Модель с одним входом 1 Учк
Учк п Ч . Рис. В зависимости от числа входов вычисления можно разделить на два типа вычисления с одним входом и с несколькими входами. Например, вычисления клиентсервер представляют собой вычисления с двумя входами. Преобразуем оба типа вычислений к КМВ, в ко торых входные данные каждого участники являются конфиденциальными. Модель с несколькими входами преобразуется путем распределения входов между участниками. Тогда новая задача заключается в том, как выполнить те же вычисления, при сохранении конфиденциальности значений всех участников. Для преобразования модели с одним входом мы должны сначала преобразовать ее к модели с несколькими входами. Предположим, что вход представляет собой набор элементов данных х. Для того чтобы получить модель с несколькими входами нам необходимо разделить х на п непересекающихся наборов данных ,х. Существуют различные способы разделения х на несколько наборов данных. При этом для каждого способа будет своя задача КМВ. Рассмотрим два возможных способа разделения гомогенный и гетерогенный. При гомогенном способе элементы данных из х разделяются на п наборов, но сам элемент данных не разделяется на несколько частей. Например, если х таблица с записями о студентах, то при гомогенном преобразовании в каждый из наборов будет включена какаято часть студентов. При этом информация о конкретном студенте не разделяется между наборами. При гетерогенном способе, каждый элемент данных разделяется на п частей, и каждая часть входит в разные наборы. Например, в рассмотренном примере с таблицей студентов, если каждая строка содержит личные данные и данные об успеваемости, то в один набор попадут личные данные студентов, а в другой данные об их успеваемости. Два созданных набора данных содержат разную информацию об одних и тех же студентах. После описанных выше преобразований, новая задача состоит в том, как выполнить вычисления над объединением наборов х9.