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

На правах рукописи

ШУТЫЙ Родион Сергеевич

РАНДОМИЗИРОВАННЫЕ ПРОТОКОЛЫ, ПРИМЕНЯЕМЫЕ ДЛЯ ВЫПОЛНЕНИЯ КОНФИДЕНЦИАЛЬНЫХ МНОГОСТОРОННИХ ВЫЧИСЛЕНИЙ В КОМПЬЮТЕРНЫХ СЕТЯХ

05.13.13 — Телекоммуникационные системы и компьютерные сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2009

003488368

Работа выполнена в Санкт-Петербургском государственном университете телекоммуникаций им. проф. М. А. Бонч-Бруевича на кафедре «Информационной безопасности телекоммуникационных систем»

Научный руководитель:

доктор технических наук, профессор ЯКОВЛЕВ Виктор Алексеевич

Официальные оппоненты:

доктор технических наук, профессор, заслуженный деятель науки РФ КРУ К Евгений Абрамович

кандидат технических наук ТРИФОНОВ Петр Владимирович

Ведущая организация:

ЗАО «Эврика»

Защита диссертации состоится « X// 2009 г. в часов на

заседании диссертационного совета Д 219.004702 при Санкт-Петербургском государственном университете телекоммуникаций им. проф. М. А. Бонч-Бруевича по адресу: 191186, Санкт-Петербург, наб. р. Мойки, 61.

С диссертацией можно ознакомиться в библиотеке университета.

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

Автореферат разослан « Х^_2009 г.

Ученый секретарь диссертационного совета,, канд. техн. наук, доц.

В. X. Харитонов

Общая характеристика работы

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

1) у пользователей компьютерной сети есть базы данных с конфиденци-ьной информацией; им необходимо провести совместный анализ этих данных

например, проверить совпадение столбцов таблиц) без их раскрытия;

2) несколько компаний планируют расширять свои рынки сбыта, разделив ежду собой определенные регионы, но не хотят при этом конкурировать друг другом в одном регионе; им нужно определить, перекрываются ли их регионы ежду собой, не раскрывая данные о своем присутствии в этих регионах.

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

Для решения задач КМВ применяются криптографические протоколы Передача данных на хранение» (Bit commitment, ВС) и «Забывчивая передача» Oblivious transfer, ОТ). По типу стойкости эти протоколы делятся на вычисли-ельно стойкие и безусловно стойкие. Вычислительно стойкие протоколы — ротоколы, стойкие против злоумышленника, ограниченного в плане вычисли-ельных возможностей; их стойкость основывается на вычислительной сложно-ти решения некоторых математических задач и оценивается исключительно на акой-то определенный момент времени. Безусловно стойкие протоколы осно-ываются на использовании рандомизированных преобразований, например на аналах с шумом, и их стойкость не зависит от вычислительных возможностей лоумышленника. Безусловно стойкие протоколы исследовались К. Крепо С. Сгёреаи), В. И. Коржиком, К. Г. Морозовым, И. Дамгордом (I. Damgard),

Г. Саввидесом (в. Sawides) и др. Анализ публикаций и проведенные автором расчеты показали, что эти протоколы обладают низкой эффективностью.

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

В работе исследуются задачи КМВ, относящихся к группе безусловно стойких протоколов.

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

1) исследование и разработка модифицированного протокола «Забывчивая передача» для цепочек бит на основе канала с ошибками;

2) исследование и разработка модифицированного протокола «Передача данных на хранение» для цепочек бит на основе канала с ошибками;

3) разработка методик расчета параметров протоколов конфиденциальных многосторонних вычислений над базами данных в компьютерных сетях на основе модифицированного протокола «Забывчивая передача».

Методы исследований. При выполнении исследований применялись методы теории вероятности, теории информации, теории помехоустойчивого кодирования, математической статистики. Исследования проводились с использованием программного обеспечения, реализованного на языках программирования С++ и С#.

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

Научная новизна. Основными результатами диссертации, обладающими научной новизной, являются:

1) модифицированный протокол «Забывчивая передача» на основе канала с ошибками, где для увеличения эффективности и безопасности протокола используется интерактивное хэширование;

2) методика оптимизации параметров модифицированного протокола «Забывчивая передача»;

3) модифицированный протокол «Передача данных на хранение» на основе канала с изменяемой вероятностью ошибки;

4) методика оптимизации параметров модифицированного протокола «Передача данных на хранение»;

5) методики расчета параметров протоколов КМВ над базами данных в компьютерных сетях.

Практическая значимость работы. Разработаны методики расчета параметров и научно-технические предложения по применению модифицированного протокола «Забывчивая передача», предназначенного для использования в задачах КМВ при сравнении столбцов таблиц, нахождении доминирующего столбца и поиске часто встречающихся наборов в базах данных, содержащих конфиденциальную информацию.

Внедрение результатов исследований. Результаты исследований использовались в СПИИРАН и в Санкт-Петербургском филиале ОАО «НИИАС», что подтверждено соответствующими актами.

Апробация работы. Результаты диссертации докладывались, обсуждались и были одобрены на 59 и 61-й НТК профессорско-преподавательского состава и сотрудников СПбГУТ им. проф. М. А. Бонч-Бруевича (2007, 2009), XII Международной НПК «Информационные технологии на железнодорожном транспорте» (2007), ХУ-ХУП общероссийских НТК «Методы и технические средства обеспечения безопасности» (2006-2008) и Международной НТК «Кибернетика и высокие технологии XXI века» (С&Т-2009).

Публикации. По теме диссертации опубликовано 12 печатных работ, в том числе две статьи в журналах из перечня, рекомендованного ВАК.

Основные положения, выносимые на защиту:

1. Модифицированный протокол «Забывчивая передача» для цепочек бит на основе канала с ошибками с использованием интерактивного хэширования и методика оптимизации его параметров.

2. Модифицированный протокол «Передача данных на хранение» для цепочек бит на основе канала с изменяемой вероятностью ошибки и методика оптимизации его параметров.

3. Методики расчета параметров протоколов конфиденциальных многосторонних вычислений над базами данных в компьютерных сетях на основе модифицированного протокола «Забывчивая передача».

Объем и структура работы. Работа состоит из введения, четырех разделов, заключения, списка литературы, включающего 97 наименований, и приложения. Работа содержит 154 страницы машинописного текста, 45 рисунков, 1 таблицу.

Содержание работы

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

В разделе 1 рассматривается модель КМВ. На основе анализа литературы приведена классификация задач КМВ. Все они могут быть разделены на задачи на сравнение и задачи на совместное получение результата. Приводится подробное описание таких задач и примеры их практической значимости. К зада-

3

чам на сравнение относятся задачи конфиденциального сравнения чисел, векторов, пересечения геометрических фигур, принадлежности точки многоугольнику; к задачам на совместное получение результата относятся операции с числами и векторами, решение систем линейных уравнений и неравенств, статистический анализ и др. В разделе обосновывается необходимость использования криптографических примитивов «Забывчивая передача» и «Передача данных на хранение» для выполнения КМВ, приведена классификация этих протоколов и их описание. Подраздел 1.4 посвящен общему решению задач КМВ на основе криптографических примитивов.

Раздел 2 посвящен разработке модифицированного протокола «Забывчивая передача» (ОТ).

Модифицированный протокол основывается на протоколе ОТ, предложенном К. Крепо для однобитовых цепочек и обобщенном В. И. Коржиком и К. Г. Морозовым для цепочек бит произвольной длины. Приведем основные этапы исходного протокола.

Пользователь А имеет две последовательности Ь0 и — цепочки двоичных символов длиной I (два секрета), из которых пользователь В может выбрать только одну цепочку, оставаясь в неосведомленности относительно второй цепочки. Причем А не должен узнать, какую цепочку выбрал В.

Пусть А и В связаны между собой двоичным симметричным каналом (ДСК) с вероятностью ошибки 5 в направлении от А к В и каналами без ошибок в направлениях от А к В и от В к А.

Пусть V— помехоустойчивый линейный (п, к)-код, имеющий минимальное хэмминговое расстояние с/т!п ; Н— проверочная матрица этого кода; g(v) — хэш-функция, отображающая «-битную последовательность v в I-битную последовательность. Эти параметры известны обоим пользователям до начала выполнения протокола.

Протокол состоит из следующих шести шагов.

1. Пользователь А формирует строку РГиз 2п случайных равновероятных, взаимонезависимых двоичных символов и',. (/=1,...,2и), кодирует каждый бит кодом с двукратным повторением и посылает кодированную последовательность пользователю В по ДСК.

2. Пользователь В декодирует каждую принятую пару символов по правилу: последовательность из двух нулей декодируется в ноль, последовательность из двух единиц — в единицу, последовательность из нуля и единицы или единицы и нуля — в стирание. В итоге он получает строку IV' длиной 2п бит. Далее В разделяет строку IV на две непересекающиеся строки \¥'а и

( |ГУ0'| = = п ) таким образом, чтобы в строке И^. не было стертых символов, а в строке Щ'^ были как стертые, так и нестертые символы, при этом с = (0,1) — индекс выбранного В секрета Ьс. Обозначим через Ыитй и Ыитх непересекающиеся подмножества номеров позиций символов первоначальной строки

IV', вошедших в и соответственно. Далее В посылает А Ли/и0 и А/м/и, по каналу без шума.

3. А, получив подмножество номеров Агг/м0 и Штх, формирует строки Ид и (Г, из имеющейся у него исходной строки Ж и вычисляет синдромы

л>'н0 = • НТ и ц'«, = 1¥{ ■ Нт, которые он передает В по каналу без ошибок.

4. В, используя $упс, исправляет ошибки в IV' и получает последовательность 1УС. Далее он выполняет проверку: с1и (IVс, IV') < [_(с/т:„ -l)/2J, где [а] — целое число, меньшее или равное а; — расстояние по Хэммингу между 1УС и И". Если неравенство не выполняется, В прерывает протокол.

5. А хэширует \У0а.\¥х, находит Ь0=Ь0 © и ¿, = Ьх Ф g(iV^) и передает их В.

6. В вычисляет требуемый секрет по правилу: bc=bc@g{Wc) =

Для оценки безопасности и эффективности протокола введем следующие параметры." Рс — вероятность незавершения протокола из-за его прерывания любым из пользователей в силу невыполнения условий; /0 — количество информации по Шеннону, которое может получить В о второй последовательности, т. е. о последовательности ¿>,_с; РА — вероятность того, что А узнает, какую последовательность выбрал В; Рг — вероятность риска невыполнения какого-либо из неравенств. Эффективность данного протокола будем оценивать отношением длины I последовательности Ьс к общему числу бит, переданных по ДСК,— 2п. Назовем это отношение скоростью протокола = 1/2п.

Оптимизация параметров протокола с точки зрения разработчика заключается в максимизации его скорости при выполнении условий:

Кг тах; Рс < РГ \ /„ < /<Г; Рг < РГ, (1)

где РСЛ0Л, /Одоп и Р'Ч0П — заданные требования, которым должен удовлетворять протокол.

Анализ протокола с использованием введенных параметров показал его низкую эффективность. Так, при / = 105, Р;10" = 1(Г6, /¿оп=1(Г10, Ргдоп=10"14 и 6 = 0,096 скорость протокола составила 0,041.

Приведем описание нового модифицированного протокола.

Шаги 1-4 в точности повторяют предыдущий протокол. Дальнейшие шаги состоят в следующем.

5. Пусть 1пс1й и /«(/[ — вспомогательные подмножества, состоящие из порядковых номеров позиций в подмножествах Ыитй и Мит{ соответственно. Пользователь В формирует подмножество 5 мощностью еп (е>0), помещая в него случайным образом выбранные номера нестертых символов из подмножества 1пс1х_с. Если количество нестертых бит в оказывается меньше, чем еп, он прерывает протокол.

6. Используя протокол интерактивного хэширования и протокол кодирования (декодирования) подмножеств в строку бит, А и В формируют на основе S два подмножества S0 и такой же мощности, что и S, причем или S0, или

в точности совпадает с S.

7. А проверяет, выполняется ли неравенство ]50 п < А,, где А, — максимальное количество позиций, в которых могут пересекаться подмножества. Если неравенство не выполняется, он прерывает протокол.

8. В выбирает бит / е {0,1} такой, чтобы St = S, и передает А бит а = с © t.

9. В передает А последовательность ^[Sj.,]©^.,,^,], где W^Sj] обозначает подмножество символов из последовательности Wi, выбранных в соответствии с номерами из Sj.

10. А проверяет, выполняется ли условие, что принятая последовательность lVc[S^t](B lVi-c[St] и последовательность W0[S^a]® Щ[За], сформированная им, отличаются не более чем в Д2 позициях. Если условие не выполняется, А прерывает протокол.

11.А вычисляет ¿о = b^ © gG^o) > b\ = b\ ® g(ff\) и передает их В.

12.В вычисляет требуемый секрет Ьс = Ьс Ф g(Wc) = bc © g(Wc) © g(Wc) ■

Приведем пояснения к отдельным шагам протокола.

Шаги 5-10 нужны для проверки честности В. Если В нечестный, он будет помещать стертые биты в обе строки WQ и W{, для того чтобы, получив синдромы от А, исправить ошибки в обеих строках и получить в итоге оба секрета.

Проверка заключается в передаче от В к А небольшого числа случайно выбранных нестертых бит из обеих строк. Если В честный и строго следует протоколу, то биты, содержащиеся на одних и тех же позициях в строках W0 и W{ у Айв строках W0 и Щ у В, будут отличаться не более чем в Д2 позициях. Биты, участвующие в проверке, формируются следующим образом. Пользователь В на шаге 5 формирует подмножество S, помещая в него выбранные случайным образом индексы нестертых бит из Ind^_c. На основе S А и В выбирают второе случайное подмножество такой же мощности, что и S. Для этого подмножество S преобразуется в двоичную последовательность v, к которой применяется протокол интерактивного хэширования.

Сущность интерактивного хэширования заключается в том, что на основе строки v пользователи А и В получают две строки v0 и v,, одна из которых совпадает с исходной, причем А не может узнать, какая именно, а В не может повлиять на выбор второй строки. Далее А и В преобразуют двоичные строки v0 и v, в подмножества S0 и соответственно.

На рис. 1 показано распределение бит, выбранных для проверки f^c[Si4] и HUS,], в строках Wc и для случаев честного и нечестного В.

Подмножество , полученное после интерактивного хэширования

В честный

Подмножество X выбранное В из/ис/ь,

Г

В нечестный

К

I I — нестертые биты КХХЮ — стертые биты

У//Л — стертые биты, которые нечестный В перенес из в №с

Рис. 1. Распределение бит, выбранных из строк Цгс и , для проверки честности пользователя В

На шаге 9 В вычисляет суммарную последовательность и передает ее А. Если В честный, то все биты в ] и [5", ] будут не-

стертыми. В строке [£[_,] все биты будут без ошибок, так как В исправил их, используя синдром на шаге 4; в строке будет не более Д2 ошибочных

бит, и следовательно, в суммарной последовательности ^[З^,]© бу-

дет не более Д2 бит с ошибками. Если же В нечестный и поместил в 1¥с стертые биты, то эти биты также окажутся в и для того, чтобы пройти тест, ему придется заменить стертые биты их значениями, случайно выбранными из множества {0,1}. В передает А именно сумму двух последовательностей с той целью, чтобы А не мог определить, к какому подмножеству (1пс1с или 1пс1{_с) принадлежит 5.

На шаге 10 А сравнивает последовательности и

^Д^.,]® Если число несовпадающих позиций не превышает Д2, то, с

точки зрения А, в строке 1УС нет стертых бит и, следовательно, В не пытался его обмануть, поэтому количество информации о втором секрете, которое получит В после выполнения процедуры усиления секретности, будет мало. Если условие не выполняется, А прерывает протокол.

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

¡-1

1=1 у=0

(2)

РС1 — вероятность прерывания протокола пользователем В на шаге 4 из-за того, что число ошибок в канале превысило исправляющую способность кода:

рс1< хсуо-ф)-',

где минимальное расстояние dmin кода V оценивается по границе Варшамова — Гильберта:

к/п > \-h(djn), (4)

где h(a) = -a log а - (1 - а) log(l - а) — энтропийная функция; ф — вероятность

ошибки в нестертом бите: ф = 82/[б2 + (1 - б)2 ].

Рс1 — вероятность прерывания протокола пользователем В на шаге 5 из-за того, что количество нестертых бит в Щ_с меньше, чем необходимо для проверки:

f^ZOifl-i'J (5)

¡=0

где pg — вероятность приема бита в цепочке W: pg - 52 + (1 - 8)2.

Рс3 — вероятность прерывания протокола пользователем А на шаге 7 из-за того, что подмножества SQ и оказались пересекающимися более чем в Д, позициях:

Ь ^■ (6)

i=&l +1 Fl

Рс4 — вероятность прерывания протокола пользователем А на шаге 10 из-за того, что последовательности W0[Si_a]®Wl[Sa]H ^[i1,.,]® Wt_c[S,] отличаются более чем в Д2 позициях:

ЕЯ

Рс4< ХСф'О-ФГ"'. (7)

<=д2 +1

Количество информации, которое пользователь В может получить о втором секрете, рассчитывается по формуле:

/0=гшх{Рв(ад^(^)}; 0<^<«-у/2, (8)

где Рв (<;и) — вероятность того, что В пройдет проверку на шаге 10 при условии, что он поместил в строку Wc fyi стертых бит:

Л^-^С/^г X (!-ф) ; (9)

,'=0 i'n J=О 2 fc=o

Г0 (fyi) — остаточная информация о втором секрете:

Г [„_/_(„_*)_., 1

/¿(^)<min -—-,/ , (10)

где (п-к) — количество проверочных символов кода V; s — параметр безопасности, определяемый из вероятности риска Рг1 невыполнения неравенства (10): Pri < 2~s/2~' ; IR (tji) — информация Реньи о втором секрете:

h ФО = (Y - « + + log2 (ф2 + (1 - Ф)2)], (11)

где у — общее количество принятых нестертых бит, определяемое из формулы:

Pri* ZcLp^I-PJ"-'. (12)

i=y+l

Вероятность того, что А узнает, какую последовательность выбрал В, равна вероятности угадывания, т. е. РА = 1/2.

На основе (2)—(12) разработана методика оптимизации параметров протокола.

Входные данные: 1,8, Рсаоп, /Одоп, Ргяоп.

1. Задать длину кода и равной пнт, выбрать начальный шаг изменения п — Ди и рассчитать минимальное расстояние кода dmm по (3).

2. Найти число проверочных символов кода n-к по (4).

3. Рассчитать количество нестертых бит у по (11).

4. Рассчитать относительную мощность е множества S, необходимого для проверки, по (5)-(7).

5. Задать <;нач — количество стертых бит, которое В может перенести из второго подмножества; вычислить вероятность прохождения проверки пользователем В на шаге 10 и остаточную информацию, получаемую им о второй последовательности, по (9) и (10); многократно повторяя расчет для других найти максимальное количество информации /0, которое может получить В о второй последовательности.

6. Если An = 0, то перейти к шагу 8.

7. Если An ^ 0 и /0 < , уменьшить и; если на предыдущей итерации /0 > 1Г, уменьшить шаг Ди и повторить шаги 1-5.

8. Если АпфО и /0 > /д0", увеличить и; если на предыдущей итерации /0 </ о°п, уменьшить шаг An и повторить шаги 1-5.

9. Рассчитать скорость протокола R0T -1/2п.

Выходные данные: параметры помехоустойчивого кода (и, k,d) и относительная мощность множества, выбираемого для проверки б.

На основе разработанной методики, с введением заданных требований Р™", Igon, Р*'т, в работе получены оценки для параметров модифицированного протокола.

На рис. 2 показана зависимость скорости исходного и модифицированного протоколов от вероятности ошибки в канале 5 и длины цепочек I.

б)

/=105.рдап=10-6./доп=10-10.рдоп=10-14

--исходный протокол

модифицированный протокол

/ДО1,=10-Ю.рдап=10-14

0,10 5=5„„т

- — 5=0,10

0,08 -----8=0,20

0,06

----------

0,04

0,02

0,05 0,10 0,15 0,20 0,25 0,30

I, бит

Рис. 2. Зависимость скорости исходного и модифицированного протоколов от вероятности ошибки в канале (а) и длины цепочек (б)

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

В подразделе 2.3 исследуется обобщенный протокол «Забывчивая передача», в котором вместо кода с двукратным повторением используется код с многократным повторением. Для этого протокола выведены расчетные соотношения и произведен анализ эффективности по вышеизложенной методике, который показал, что скорость обобщенного протокола на основе модифицированного в 2,5—4 раза выше скорости протокола, основанного на исходном протоколе. Максимальная скорость протокола достигается при использовании кода с трехкратным повторением. Также было выявлено, что для каждого конкретного кода повторения существует своя оптимальная вероятность ошибки в канале, при которой скорость протокола максимальна. Это следует учитывать при практической реализации протокола, так как при заданной вероятности ошибки в ДСК нужно использовать оптимальный код повторения.

Подраздел 2.4 посвящен исследованию усиленного протокола, в котором обеспечивается защита от действий нечестного отправителя. Для реализации этой защиты модифицированный протокол необходимо многократно повторять. Тогда пользователю А для определения секрета, выбираемого В, необходимо обманывать на каждой итерации протокола, что создает условия для выявления В обмана по анализу статистики со стороны А. Исследования усиленного протокола показали, что существует оптимальная длина цепочек, при которой скорость протокола максимальна. Это важно при практической реализации, так как общая скорость протокола достаточно низкая. Применение модифицированного протокола для построения усиленного протокола позволило повысить его скорость почти на порядок по сравнению с усиленным протоколом на основе исходного.

В разделе 3 исследуется модифицированный протокол «Передача данных на хранение» (ВС), представляющий собой двусторонний криптографический примитив, суть которого заключается в следующем. У пользователя А есть

блок данных (обязательство) длиной I бит, который он передает на хранение пользователю В в закодированном виде. При этом В не может узнать обязательство, пока А не откроет его (свойство скрытия), а А не может подменить обязательство при его открытии (свойство обязательства).

В работе рассматривается протокол ВС, основанный на расширенной модели ДСК — канале с изменяемой вероятностью ошибки (unfair noisy channel, (у, 8)-UNC), в котором вероятность ошибки изменяется в диапазоне (у, 5). Это означает, что нечестный пользователь может понизить вероятность ошибки до у. При этом честный участник не знает истинной вероятности ошибки и для него канал представляет собой ДСК с вероятностью ошибки 8.

Для анализа исходного протокола введены следующие параметры: Pfr —

вероятность ложного отказа, когда В прерывает выполнение протокола, ошибочно считая, что А нечестный, т. е. он изменил i на s ; Рс — вероятность успешной подмены обязательства s на другое обязательство — 7; Рв — вероятность правильного восстановления обязательства на основе v' и х до его открытия. Эффективность протокола оценивалась по его скорости, равной отношением длины обязательства к общему числу бит, переданных по каналу с ошибками: RBC =1/п.

Оптимизация параметров протокола с точки зрения разработчика заключается в максимизации RBC при выполнении условий:

RBC -> max; Pfi < Р™; Рс < , (13)

где Р™п, Рсяоп — заданные требования, которым должен удовлетворять протокол.

Протокол ВС был предложен К. Крепо для однобитового обязательства, что и определяет его специфику. При этом вероятность Рв должна быть близка к вероятности угадывания: Рв =l/2 + s, где 8— заданная малая величина. Для обеспечения высокой степени защищенности необходимо, чтобы е « 0,5. Это достигается применением процедуры усиления секретности и помехоустойчивого кодирования.

Для случая, когда / > 1, требование близости Рв к вероятности угадывания можно записать следующим образом: Рв= 1/2' + е, где 8 < l/2;. При больших I, например / > 100, величина l/l1 настолько мала, что требование s<l/2' является чрезмерно жестким. В этой ситуации разумно отказаться от требования близости Рв к вероятности случайного угадывания и задать Рв < Рвоп, где РГ — допустимая величина вероятности нахождения обязательства до его открытия. Приведенные соображения позволяют модифицировать и сам протокол путем обеспечения требуемой вероятности ошибочного декодирования кодового слова без дополнительного использования процедуры усиления секретности. В этом случае количество информационных символов к кода V равно длине обязательства.

В работе предложен следующий модифицированный протокол ВС.

Передача обязательства на хранение

Пусть— обязательство (двоичная цепочка длиной к бит).

1. А генерирует случайную последовательность и длиной к бит, находит х = з®и и вычисляет кодовое слово V (и,к)-кода К; V = м•С, где С— порождающая матрица этого кода. Скорость кода Яс = к/п выбирается из условия Ле>1-А(у).

2. А посылает у по (у, 8)-ЦМС, ах — по каналу без ошибок.

3. В принимает V ,хп хранит их.

Открытие обязательства

1. А открывает кодовое слово V и обязательство х, передавая их В по каналу без ошибок.

2. В проверяет, что V € V, с!н(у,у') < с!,, находит и и вычисляет .у' = и(В х. При выполнении всех проверок и совпадении 5иУВ убеждается в верности обязательства.

Особенность расчета параметров протокола заключается в оценке величины Рв. Поскольку скорость кода V больше пропускной способности, для нахождения Рв используется граница Аримото:

Рв <2 р , (14)

где -1<р<0 ; £0(р)=р-(1+р)1о§2[у1/(1+рЧ(1-у)1/(1+р)] — функция Галлагера дляу-ДСК.

Вероятности ложного отказа и успешной подмены обязательства рассчитываются по формулам:

^ = (15)

,=4

Рс =К(1-у)У-' -у)"-^'. (16)

/=0 ;=о

Методика оптимизации параметров протокола.

Входные данные: /, у, 5, Р/гоп, Рсдоп, Р£ои.

1. Задать длину кода п равной птч.

2. Рассчитать вероятность правильного восстановления обязательства до его открытия по (14).

3. Найти порог <И, по (15).

4. Рассчитать минимальную длину кода из (4).

5. Рассчитать вероятность успешной подмены обязательства по (16).

6. Если Ап = 0, то перейти к шагу 8.

7. Если Ап Ф 0 и Рс< Рстп, уменьшить п; если на предыдущей итерации Рс > /,слоп, уменьшить шаг Ап и повторить шаги 1-6.

8. Если АпфО и если Рс > Рслоп, увеличить и; если на предыдущей итерации Рс < Р™", уменьшить шаг An и повторить шаги 1-6.

9. Рассчитать скорость протокола: RBC - kin. Выходные данные: параметры помехоустойчивого кода п и d.

На основе разработанной методики, с введением заданных требований

рлоп

пдоп

Г/г '

РГ, в работе получены оценки для параметров модифицирован-

ного протокола.

На рис. 3 приведены графики зависимости скорости исходного и модифицированного протоколов от длины обязательства для разных у и 8 при

а)

рдоп=10-5 и А?оп =1(Г15.

Я*г 0,8 0,60,40,2-

У = 0,1

_____8=0,10

-----8=0.11

-----8=0,13

-----8=0,15

•10'

/, бит

I, бит

Рис. 3. Зависимость скорости исходного (пунктирная линия) и модифицированного (сплошная линия) протоколов от длины обязательства для разных у и 5

Проведенный анализ показал, что скорость модифицированного протокола выше скорости исходного протокола. Причем выигрыш в скорости тем больше, чем меньше вероятность у, что видно из сравнения рисунков За и 36. Однако необходимо отметить, что протокол может применяться, только когда длина обязательства превышает минимальную длину /т;п, определяемую заданными требованиями к параметрам протокола. При 1 < 1тт, необходимо использовать исходный протокол.

В разделе 4 разработан комплекс методик для выполнения КМВ над базами данных (БД) в компьютерных сетях. Это методики расчета параметров протоколов:

1) конфиденциального сравнения столбцов таблиц БД;

2) нахождения доминирующего вектора в таблицах БД;

3) поиска часто встречающихся наборов в таблицах БД.

Данным практическим задачам соответствуют математические задачи:

1) конфиденциальное сравнение векторов (КСВ);

2) конфиденциальное нахождение доминирующего вектора;

3) конфиденциальное вычисление скалярного произведения.

Эти задачи решаются с помощью базовых протоколов конфиденциального сравнения чисел (КСЧ) и умножения чисел, которые основываются на модифицированном протоколе «Забывчивая передача». Все предложенные методики построены по общей схеме: сначала разрабатываются методики расчета пара-

метров базовых протоколов, затем на их основе предлагаются методики расчета параметров протоколов КМВ над базами данных.

В качестве примера приведем одну из разработанных методик — методику расчета параметров протокола конфиденциального сравнения столбцов таблиц БД. Этой задаче соответствует математическая задача КСВ, которая может быть декомпозирована, как показано на рис. 4.

Задача КСВ заключается в следующем. КСВ Пусть у пользователя А есть вектор

\ = (х],х1,...,хы) , соответствующий столбцу таблицы БД, а у пользователя В— вектор У = (Уг > У г > ■ • • > Уы) > также соответствующий

Протокол «Забывчивая передача»

столбцу таблицы БД. Им необходимо поэлементно сравнить векторы х и у, т. е. определить, для каких i ( / = 1,2,...,N) x¡ > y¡ и для каких i Рис. 4. Декомпозиция задачи КСВ x¡ < y¡ . Протокол КСВ состоит в последовательном выполнении протокола КСЧ для чисел x¡ и y¡. Поэтому рассмотрим сначала методику расчета параметров протокола КСЧ.

Задача КСЧ состоит в следующем. Пусть у пользователя А есть секретное число х, а у пользователя В — секретное число у. Им необходимо выяснить, выполняется ли неравенство х > у, не раскрывая чисел х и у. Решение этой задачи основывается на протоколе КСЧ, предложенном А. Грама (A. Grama) и И. Иоаннидисом (I. Ioannidis). Суть их протокола заключается в том, что пользователь А для каждого бита числа х формирует две строки, одна из которых является случайной, а вторая содержит i-й бит числа х в закодированном виде. Пользователь В, используя протокол ОТ, выбирает из этих двух строк строку с индексом, равным г'-му биту числа у. Далее, складывая все выбранные строки, В находит результат сравнения.

Для анализа безопасности протокола КСЧ в работе введены параметры: Рс ксч — вероятность незавершения протокола из-за его прерывания любым из пользователей в силу невыполнения условий; Рт ксч — вероятность того, что В узнает /-й бит числа х; РВ2 ксч — вероятность того, что В узнает разряд, в котором различаются числа х и у.

Эти параметры должны удовлетворять условиям:

р рДОП . р < рдоп . р ^ рДОП /1 п\

гс_КСЧ - гс_КСЧ ' rffl_KC4 - rBi КСЧ > Г£2_КСЧ -rfi2_KC4> U ')

где Р™ксч > РвГксч > ?и° ксч — допустимые ограничения.

Методика расчета параметров протокола КСЧ.

Входные данные: р — количество разрядов сравниваемых чисел; Р^ксч '>

рдоп . рдоп •'fil_KC4 > ГВ2_КСЧ ■

1. Рассчитать длину цепочек I, используемых в протоколе ОТ, из формулы:

(/-3p-3)/2 2

¿I Ti т , 14 =РВ2 ксч- (18)

Í=1 (/-3p-3)(i + l)

2. Рассчитать вероятность прерывания протокола ОТ:

Pgj? <\-ф-РГксч • (19)

3. Задать Iq" = нач. Рассчитать Рт ксч из неравенства Фано:

/ + (1 - ^_ксч )log ' ~ Р2?-*СЧ + Рт_ кеч l°g Рв1ксч <Сг- (20)

4. Если Рт < сч > уменьшить Iqt и повторить шаг 3.

5. Если Рт > /3д10Пксч, увеличить Iq" и повторить шагЗ.

6. Если Рт = />ЙДГКСЧ перейти на шаг 7.

7. Рассчитать скорость протокола ОТ по методике, приведенной в разделе 2.

8. Повторяя шаг 7, найти оптимальную вероятность ошибки в канале ôom., при которой скорость протокола максимальна.

Выходные данные: I— длина цепочек, используемых в протоколе ОТ; 5опт —оптимальная вероятность ошибки в канале; (и, k,d) — параметры помехоустойчивого кода; s — относительная мощность тестового подмножества.

На основе изложенной методики разработана методика расчета параметров протокола КСВ. Для оценки безопасности протокола КСВ вводятся те же параметры, что и для протокола КСЧ, причем параметр Рсд0£св находится из соотношения РЛсв^Ч-^счГ' а параметры /^10пксв, Р,™" ксв не зависят от длины векторов.

Методика расчета параметров протокола КСВ выглядит так.

Входные данные: N,p, PcaoJCB, РВТ_КСв, ПТксв-

1. Рассчитать допустимые условия для протокола КСЧ.

2. Используя методику расчета параметров протокола КСЧ, найти параметры протокола ОТ.

Выходные данные: /; 5OITT; (п, k, d)\ е.

По разработанным методикам был проведен расчет и построены зависимости объема передаваемой по ДСК информации от длины векторов и количества разрядов в элементах сравниваемых векторов. Проведенный анализ показал возможность применения модифицированного протокола «Забывчивая передача» для КМВ над базами данных.

В заключении изложены основные научные и практические результаты.

Основные результаты работы

1. Разработан модифицированный протокол «Забывчивая передача» для цепочек бит на основе канала с ошибками, в котором для увеличения эффективности введена проверка честности пользователя В, выбирающего секрет. Проверка проводится на основе процедуры интерактивного хэширования. Разработана методика оптимизации параметров протокола. Анализ, проведенный

15

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

2. Разработан модифицированный протокол «Передача данных на хранение» для цепочек бит на основе канала с ошибками. Его суть заключается в том, что для обязательств большой длины требование вероятности правильного восстановления обязательства до его открытия обеспечивается только за счет большой вероятности ошибочного декодирования кодового слова, без использования процедуры усиления секретности. Разработана методика оптимизации параметров модифицированного протокола. Скорость модифицированного протокола при большой длине обязательства и при малой вероятности ошибки в канале выше скорости исходного протокола в 1,5-2 раза.

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

Таким образом, решены все задачи, поставленные для достижения сформулированной в работе цели.

Список работ по теме диссертации

1. Шутый, Р.С. Исследование эффективности протокола Bit Commitment / В. А. Яковлев, Р. С. Шутый // Методы и техн. средства обеспечения безопасности информации: Материалы XV Общерос. НТК. - СПб.: Изд-во СПбГПУ, 2006.-С. 95.

2. Шутый, Р.С. Исследование эффективности протокола Oblivious Transfer / В. А. Яковлев, Р. С. Шутый // 59-я НТК: Материалы / ГОУВПО СПбГУТ. -СПб., 2007.-С. 190-191.

3. Шутый, Р.С. Исследование протокола «Забывчивая передача для случая активного нарушителя» / В. А. Яковлев, Р. С. Шутый // Методы и техн. средства обеспечения безопасности информации: Материалы XVI Общерос. НТК. - СПб.: Изд-во СПбГПУ, 2007. - С. 85-86.

4. Шутый, Р.С. Исследование протокола «Забывчивая передача с модификацией процедуры кодирования» / В. А. Яковлев, Р. С. Шутый // Методы и техн. средства обеспечения безопасности информации: Материалы XVI Общерос. НТК. - СПб.: Изд-во СПбГПУ, 2007. - С. 87.

5. Шутый, Р.С. Исследование протокола передачи бита на хранение для случая канала с изменяемой вероятностью ошибки / В. А. Яковлев, Р. С. Шутый

// Информационные технологии на железнодорожном транспорте: Материалы XII Международ. НПК. - СПб.: СПбГПУ, 2007. - С. 75-81.

6. Шутый, P.C. Модифицированный протокол «Передача бита на хранение» для канала с изменяемой вероятностью ошибки / В. А. Яковлев, Р. С. Шутый // Проблемы информационной безопасности. Компьютерные системы. - 2008. - № 1. - С. 88-95. (из Перечня ведущих рецензируемых научных журналов и изданий ВАК Минобрнауки РФ)

7. Шутый, P.C. Протокол «Забывчивая передача» с использованием интерактивного хэширования / В. А. Яковлев, Р. С. Шутый // Методы и техн. средства обеспечения безопасности информации: Материалы XVII Общерос. НТК. -СПб.: Изд-во СПбГПУ, 2008. - С. 74-75.

8. Шутый, P.C. Методика расчета параметров протокола «Забывчивая передача» для цепочек бит с использованием интерактивного хэширования /Р. С. Шутый //61-я НТК: Материалы /ГОУВПО СПбГУТ. - СПб., 2009. -С. 258-259.

9. Шутый, P.C. Применение интерактивного хэширования для построения криптографических протоколов /P.C. Шутый //61-я НТК: Материалы / ГОУВПО СПбГУТ. - СПб., 2009. - С. 259-260.

10.Шутый, P.C. Применение модифицированного протокола «Забывчивая передача» для конфиденциального сравнения двух чисел / В. А. Яковлев, Р. С. Шутый // X Международ. НТК «Кибернетика и высокие технологии XXI века» (С&Т-2009): Сб. докл. - Воронеж: Изд-во ВГТУ, 2009. - Т. 1. -С. 385-392.

11 .Шутый, P.C. Протокол «Забывчивая передача» для цепочек бит на основе канала с ошибками с использованием интерактивного хэширования / В. А. Яковлев, Р. С. Шутый // Проблемы информационной безопасности. Компьютерные системы. - 2009. - № 1. - С. 78-91. (из Перечня ведущих рецензируемых научных журналов и изданий ВАК Минобрнауки РФ)

12.Шутый, P.C. Использование протокола «Забывчивая передача» для конфиденциальных многосторонних вычислений с базами данных в компьютерных сетях / В. А. Яковлев, Р. С. Шутый // Информационная безопасность регионов России (ИБРР-2009): Материалы конф. - СПб.: СПОИСУ, 2009. -С. 147.

Подписано в печать 29.10.2009г. Формат 60x84/16 П.л. 1 Уч.-изд.лД. Тир.80 экз. Отпечатано в типографии ООО «Турусел» 191186, Санкт-Петербург, ул. Миллионная д. 1. Тел. 571-5474 Зак. № 13146 от 02.11.2009г.

ВВЕДЕНИЕ.

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

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

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

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

1.2.1. Способы преобразования обычных вычислений к конфиденциальным многосторонним вычислениям.

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

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) у пользователей компьютерной сети есть базы данных с конфиденциальной информацией; им необходимо провести совместный анализ этих данных (например, проверить совпадение столбцов таблиц) без их раскрытия;

2) несколько компаний планируют расширять свои рынки сбыта, разделив между собой определенные регионы, но не хотят при этом конкурировать друг с другом в одном регионе; им нужно определить, перекрываются ли их регионы между собой, не раскрывая данные о своем присутствии в этих регионах.

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

Для решения задач КМВ применяются криптографические протоколы «Передача данных на хранение» (Bit commitment, ВС) и «Забывчивая передача» (Oblivious transfer, ОТ). По типу стойкости эти протоколы делятся на вычислительно стойкие и безусловно стойкие. Вычислительно стойкие протоколы— протоколы, стойкие против злоумышленника, ограниченного в плане вычислительных возможностей; их стойкость основывается на вычислительной сложности решения некоторых математических задач и оценивается исключительно на какой-то определенный момент времени. Безусловно стойкие протоколы основываются на использовании рандомизированных преобразований, например на каналах с шумом, и их стойкость не зависит от вычислительных возможностей злоумышленника. Безусловно стойкие протоколы исследовались К. Крепо (С. Сгёреаи), В. И. Коржиком, К. Г. Морозовым, И. Дамгором (I. Damgard), Г. Саввидесом (G. Savvides) и др. Анализ публикаций и проведенные автором расчеты показали, что эти протоколы обладают низкой эффективностью.

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

В работе исследуются задачи КМВ, относящихся к группе безусловно стойких протоколов.

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

1) исследование и разработка модифицированного протокола «Забывчивая передача» для цепочек бит на основе канала с ошибками;

2) исследование и разработка модифицированного протокола «Передача данных на хранение» для цепочек бит на основе канала с ошибками;

3) разработка методик расчета параметров протоколов конфиденциальных многосторонних вычислений над базами данных в компьютерных сетях на основе модифицированного протокола «Забывчивая передача».

Методы исследований. При выполнении исследований были использованы методы теории вероятности, теории информации, теории помехоустойчивого кодирования, методы математической статистики. Экспериментальные исследования проводились с использованием программного обеспечения, реализованного на языках программирования С++ и С#.

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

Научная новизна. Основными результатами диссертации, обладающими научной новизной, являются:

1) модифицированный протокол «Забывчивая передача» на основе канала с ошибками, где для увеличения эффективности и безопасности протокола используется интерактивное хэширование;

2) методика оптимизации параметров модифицированного протокола «Забывчивая передача»;

3) модифицированный протокол «Передача данных на хранение» на основе канала с изменяемой вероятностью ошибки;

4) методика оптимизации параметров модифицированного протокола «Передача данных на хранение»;

5) методики расчета параметров протоколов КМВ над базами данных в компьютерных сетях.

Личный вклад автора. Результаты исследований, теоретические и практические выводы, основные научные положения, содержащиеся в диссертационной работе, получены и сформулированы автором самостоятельно.

Практическая ценность работы. Разработаны методики расчета параметров и научно-технические предложения по применению модифицированного протокола «Забывчивая передача», предназначенного для использования в задачах КМВ при сравнении столбцов таблиц, нахождении доминирующего столбца и нахождении часто встречающихся наборов в базах данных, содержащих конфиденциальную информацию.

Внедрение результатов исследований. Результаты исследований использовались в СПИИРАН и в Санкт-Петербургском филиале ОАО «НИИ-АС», что подтверждено соответствующими актами.

Апробация работы и публикации. Результаты диссертации докладывались, обсуждались и были одобрены на 59 и 61-й НТК профессорско-преподавательского состава и сотрудников СПбГУТ им. проф. М. А. Бонч-Бруевича (2007, 2009), XII Международной НПК «Информационные технологии на железнодорожном транспорте» (2007), ХУ-ХУП общероссийских НТК «Методы и технические средства обеспечения безопасности» (2006-2008) и Международной НТК «Кибернетика и высокие технологии XXI века» (С&Т-2009).

Публикации. По теме диссертации опубликовано 12 печатных работ, в том числе две статьи в журналах из перечня, рекомендованного ВАК.

Основные положения, выносимые на защиту:

1. Модифицированный протокол «Забывчивая передача» для цепочек бит на основе канала с ошибками с использованием интерактивного хэширования и методика оптимизации его,параметров.

2. Модифицированный протокол «Передача данных на хранение» для цепочек бит на основе канала с изменяемой вероятностью ошибки и методика оптимизации его параметров.

3. Методики расчета параметров протоколов конфиденциальных многосторонних вычислений над базами данных в компьютерных сетях на основе модифицированного протокола «Забывчивая передача».

Структура диссертации. Диссертационная работа состоит из введения, четырех разделов, заключения, списка литературы и приложения.

Основные результаты работы можно сформулировать следующим образом:

1. Разработан модифицированный протокол «Забывчивая передача» на основе канала с ошибками с использованием интерактивного хэширования.

2. Разработана методика оптимизации параметров модифицированного протокола «Забывчивая передача».

3. Разработан модифицированный протокол «Передача данных на хранение» на основе канала с ошибками.

4. Разработана методика оптимизации параметров модифицированного протокола «Передача данных на хранение».

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

Таким образом, решены все задачи, поставленные для достижения сформулированной в работе цели.

Разработанные модифицированные протоколы «Забывчивая передача» и «Передача данных на хранение» позволяют повысить эффективность и безопасность конфиденциальных многосторонних вычислений.

На основе решенных в диссертационной работе задач можно определить следующие направления дальнейших исследований:

1. Разработка протоколов «Забывчивая передача» и «Передача данных на хранение» для более общих каналов с шумом.

2. Расширение области применения модифицированного протокола «Забывчивая передача» для решения других задач, связанных с конфиденциальными многосторонними вычислениями.

ЗАКЛЮЧЕНИЕ

В работе предложены модифицированные протоколы «Забывчивая передача» и «Передача данных на хранение» на основе канала с ошибками и разработаны методики по оптимизации параметров этих протоколов и их применение для конфиденциальных многосторонних вычислений с базами данных в компьютерных сетях.

В разделе 1 проведен обзор КМВ и криптографических примитивов. Приведено определение КМВ и примеры, показывающие необходимость их использования, рассмотрена модель КМВ и методы сведения обычных вычислений к КМВ. На основе анализа литературы проведена классификация КМВ. В разделе показана необходимость использования криптографических примитивов «Передача данных на хранение» и «Забывчивая передача» для выполнения КМВ, проведена их классификация.

В разделе 2 проведено исследование протокола «Забывчивая передача» для цепочек бит на основе канала с ошибками. Проведенные исследования показали, что скорость протокола возрастает при увеличении длины цепочек и достигает максимума при оптимальной вероятности ошибки в канале. Анализ протокола показал, что его скорость мала и не превышает 0,04.

На основе рассмотренного исходного протокола предложен модифицированный протокол, в котором для увеличения эффективности протокола введена проверка честности пользователя, выбирающего секрет. Эта проверка проводится на основе интерактивного хэширования и состоит в сравнении небольшого количества бит в тестовых подмножествах у обоих пользователей, что позволяет определить честность участника В. Для предложенного протокола была разработана методика оптимизации его параметров и выведены соотношения для их расчета. По разработанной методике был проведен анализ протокола, который показал, что скорость протокола при одинаковых требованиях к другим параметрам в три раза выше скорости известного протокола. Исследование скорости протокола при различных требованиях к параметрам протокола, показало, что ужесточение ограничений приводит к незначительному снижению скорости протокола. Также было проведено исследование зависимости скорости протокола от мощности подмножеств, выбираемых для проверки. Исследование показало, что для проверки достаточно выбирать множество мощностью равной 1% от длины цепочек.

В подразделе 2.3 проведено исследование обобщенного протокола, в котором пользователь А кодирует исходную строку кодом с а-кратным повторением, вместо двукратного. Проведенный анализ показал, что скорость обобщенного модифицированного протокола в 2,5-4 раза выше скорости обобщенного исходного протокола. Из анализа протокола можно сделать вывод, "что для каждого конкретного кода повторения существует своя оптимальная вероятность ошибки в канале, при которой скорость протокола максимальна. Поэтому при заданной вероятности ошибки в канале необходимо найти такой код повторения, при котором скорость протокола будет максимальной. Для диапазона вероятностей 8 е (0,0,5) максимальная скорость достигается при использовании кода повторения а ~3\Ъ-3.

В подразделе 2.4 проведено исследование усиленного протокола, в котором исходный протокол повторяется многократно для предотвращения обмана со стороны участника А. Установлено, что скорость усиленного протокола, основанного на модифицированном протоколе, почти иа порядок выше скорости протокола, построенного на основе исходного. Исследование усиленного протокола показало, что существует оптимальная длина цепочек, при которой скорость протокола максимальна. Оптимальная вероятность ошибки увеличивается с увеличением длины цепочек.

В разделе 3 исследуется протокол «Передача данных на хранение». В подразделе 3.1 проведен подробный анализ исходного протокола, определены зависимости его скорости от требований на заданные параметры и от диапазона вероятностей ошибки в ДСК, в котором работает протокол. Проведенные исследования показали, что скорость исходного протокола увеличивается с увеличением нижней границы диапазона вероятностей ошибки (у, 8), в котором работает протокол. Увеличение длины обязательства приводит к увеличению эффективности протокола.

В подразделе 3.2 предложен модифицированный протокол, заключающийся в том, что для обязательств большой длины использование процедуры усиления секретности становится излишним. Проведенные исследования показали, что обобщение задачи передачи бита на хранение для случая / » 1 требует четкого задания требований (ограничений) при решении задачи. Это позволяет модифицировать протокол и обеспечить требуемую вероятность правильного восстановления обязательства до его открытия пользователем Л только за счет большой вероятности ошибочного декодирования кодового слова без использования процедуры усиления секретности.

Для предложенного протокола была разработана методика оптимизации параметров протокола и выведены соотношения для их расчета. По разработанной методике был проведен анализ модифицированного протокола, который показал, что его использование позволяет для обязательств большой длины и при малой вероятности ошибки в канале увеличить скорость по сравнению с исходным протоколом в 1,5-2 раза. Однако необходимо отметить, что такой подход применяется, когда длина обязательства больше минимальной длины, определяемой заданными требованиями к параметрам протокола. При "меньших длинах обязательства необходимо использовать исходный протокол.

В разделе 4 разработаны методики расчета параметров протоколов конфиденциальных многосторонних вычислений над базами данных в компьютерных сетях, позволяющие рассчитать параметры протоколов для выполнения поэлементного сравнения столбцов таблиц, нахождения доминирующего вектора, поиска часто встречающихся наборов в таблицах баз данных, принадлежащих пользователям и содержащих конфиденциальную информацию, которая не может быть раскрыта. По разработанным методикам был проведен расчет и построены зависимости объема передаваемой по ДСК информации от длины векторов и количества разрядов в элементах сравниваемых векторов. Проведенный анализ показал возможность применения модифицированного протокола «Забывчивая передача» для совместных вычислений над базами данных, содержащих конфиденциальную информацию.

1. Аттетков A.B., Галкин C.B., Зарубин B.C. Методы оптимизации.— М.: Изд-во МГТУ им. Н. Э. Баумана, 2001. 440 с.

2. Галлагер Р. Теория информации и надежная связь.— М.: Сов. радио, 1987. 720 с.

3. Коржик В.И., Финк Л.М., Щелкунов К.Н. Расчет помехоустойчивости систем передачи дискретных сообщений.— М.: Радио и связь, 1981. 231 с.

4. Мак-Вильямс Ф., Слоэн Н. Теория кодов, исправляющих ошибки.— М.: Связь, 1979. 744 с.

5. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976. 596 с.

6. Шутый P.C. Применение интерактивного хэширования для построения криптографических протоколов // 61-я НТК профессорско-преподават. состава, науч. сотрудников и аспирантов: Материалы / ГОУВПО СПбГУТ.— СПб., 2009. С. 259-260.

7. Яковлев В.А., Шутый P.C. Исследование эффективности протокола Bit Commitment // Методы и техн. средства обеспечения безопасности информации: Материалы XV Общерос. НТК.— СПб.: Изд-во СПбГПУ, 2006. С. 95.

8. Яковлев В.А., Шутый P.C. Исследование эффективности протокола Oblivious Transfer // 59-я НТК профессорско-преподаваг. состава, науч. сотрудников и аспирантов: Материалы / ГОУВПО СПбГУТ.— СПб., 2007. С. 190-191.

9. Яковлев В.А., Шутый P.C. Исследование протокола «Забывчивая передача для случая активного нарушителя» // Методы и техн. средства обеспечения безопасности информации: Материалы XVI Общерос. НТК.— СПб.: Изд-во СПбГПУ, 2007. С. 85-86.

10. Яковлев В.А., Шутый P.C. Исследование протокола «Забывчивая передача с модификацией процедуры кодирования» // Методы и техн. средства обеспечения безопасности информации: Материалы XVI Общерос. НТК.— СПб.: Изд-во СПбГПУ, 2007. С. 87.

11. Яковлев В.А., Шутый P.C. Исследование протокола передачи бита на хранение для случая канала с изменяемой вероятностью ошибкиг

12. Информационные технологии на железнодорожном транспорте: Материалы XII Международ. НПК.—СПб.: СПбГПУ, 2007. С. 75-81.

13. Яковлев В.А., Шутый P.C. Модифицированный протокол «Передача бита на хранение» для канала с изменяемой вероятностью ошибки // Проблемы информационной безопасности. Компьютерные системы. 2008. № 1. С. 88-95.

14. Яковлев В.А., Шутый P.C. Протокол «Забывчивая передача» с использованием интерактивного хэширования // Методы и техн. средства обеспечения безопасности информации: Материалы XVII Общерос. НТК.— СПб.: Изд-во СПбГПУ, 2008. С. 74-75.

15. Яковлев В.А., Шутый P.C. Протокол «Забывчивая передача» для цепочек бит на основе канала с ошибками с использованием интерактивногохэширования // Проблемы информационной безопасности. Компьютерные системы. 2009. № 1. С. 78-91.

16. Aiello W., Ishai Y., Reingold О. Priced Oblivious Transfer: How to Sell Digital Goods //Advances in Cryptology — EUROCRYPT'01. LNCS, Vol. 2045. Springer, 2001. P. 119-135.

17. Arimoto S. On the Converse to the Coding Theorem for Discrete Mem-uryless Channels // IEEE Transactions on Inform. Theory. 1973. № 5. P. 357-359.

18. AtallahM.J., Du W. Secure Multi-Party Computational Geometry //Algorithms and Data Structures. LNCS, Vol.2125. Springer-Verlag, 2001. P. 165-179.

19. Barros J., Imai H., Nascimento A., Skludarek S. Bit Commitment over Gaussian Channels // Proc. ISIT'06. IEEE, 2006. P. 1437-1441.

20. Bellare M., Micali S. Non-Interactive Oblivious Transfer and Applications //Advances in Cryptology— CRYPTO'89. LNCS, Vol.435. SpringerVerlag, 1989. P. 547-557.

21. Bennett C.H., Brassard G., Crepeau C., Skubiszewska H. Practical Quantum Oblivious Transfer //Advances in Cryptology — CRYPTO'91. LNCS, Vol. 576. Springer-Verlag, 1992. P. 351-366.

22. Bennett C.H., Brassard G., Maurer U. Generalized Privacy Amplification // IEEE Transactions on Inform. Theory. 1995. Vol. 41. No. 4. P. 1915-1923.

23. Bennett C.H., Brassard G., Robert J.-M. Privacy Amplification by Public Discussion// SIAM J. on Computing. 1988. Vol. 17. No. 2. P. 210-229.

24. Bloch M., Barros J., McLaughlin S.W. Practical Information-Theoretic Commitment //Proc. of the 45th Allerton Conf. on Communication, Control, and Computing.—USA, 2007. P. 1035-1039.

25. Blum M. Coin Flipping by Telephone: A Protocol for Solving Impossible Problems // Proc. IEEE Computer Conf. 1982. P. 133-137.

26. Brassard G., Crepeau C. Oblivious Transfers and Privacy Amplification //Advances in Cryptology— EUROCRYPT'97. LNCS, Vol.1233. SpringerVerlag, 1997. P. 334-347.

27. Brassard G., Crepeau C., Robert J.-M. All-or-Nothing Disclosure of Secrets //Advances in Cryptology— CRYPTO'86. LNCS, Vol.263. SpringerVerlag, 1986. P. 234-238.

28. Brassard G., Crepeau C., Robert J.-M. Information Theoretic Reductions among Disclosure Problems // Proc. of the 27th FOCS'86. 1986. P. 168-173.

29. Brassard G., Crepeau C., Santha M. Oblivious Transfers and Intersecting Codes // IEEE Transactions on Inform. Theory, special iss. on coding and complexity. 1996. Vol. 42. No. 6. P. 1769-1780.

30. Brassard G., Crepeau C., WolfS. Oblivious Transfers and Privacy Amplification // J. of Cryptology. 2003. Vol. 16. No. 4. P. 219-237.

31. Brickell J., Shmatikov V. Privacy-Preserving Graph Algorithms in the Semi-honest Model //Advances in Cryptology— ASIACRYPT'2005. LNCS, Vol. 3788. Springer-Verlag, 2005. P. 236-252.

32. Cachin C. On the Foundations of Oblivious Transfer // Advances in Cryptology— EUROCRYPT'98. LNCS, Vol. 1403. Springer-Verlag, 1998. P. 361-374.

33. Cachin C., Crepeau C., Marcil J. Oblivious Transfer with a Memory Bound Receiver//39th IEEE FOCS. 1998. P. 493-502.

34. Cachin C., Maurer U. Linking Information Reconciliation and Privacy Amplification //Advances in Cryptology — EUROCRYPT'94; LNCS, Vol.950. Springer, 1995. P. 267-274.

35. Cover T. Enumerative Source Encoding // IEEE Transactions on Inform. Theory. 1973. Vol. 19. No. l.P. 73-77.

36. Cramer R. Introduction to Secure Computation // Lectures on Data Security: Modern Cryptology in Theory and Practice. LNCS, Vol. 1561. SpringerVerlag, 1999. P. 16-62.

37. Crepeau C. Equivalence between Two Flavours of Oblivious Transfers //Advances in Cryptology — CRYPTO'87. LNCS, Vol.293. Springer-Verlag, 1988. P. 350-354.

38. Crepeau C. Efficient Cryptographic Protocols Based on Noisy Channels //Advances in Cryptology — CRYPTO'97. LNCS, Vol. 1233. Springer-Verlag, "1997. P. 306-317.

39. Crepeau C., Graaf J., Tapp A. Committed Oblivious Transfer and Private Multi-Party Computations //Advances in Cryptology— CRYPTO'95. LNCS, Vol. 963. Springer-Verlag, 1995. P. 110-123.

40. Crepeau C., Kilian J. Achieving Oblivious Transfer Using Weakened Security Assumptions // Proc. of the 29th FOCS'88. 1988. P. 42-52.

41. Crepeau C., MorozovK., WolfS. Efficient Unconditional Oblivious Transfer from Almost any Noisy Channel // Security in Communication Networks. LNCS, Vol. 3352. Springer-Verlag, 2004. P. 47-59.

42. Crepeau C., Savvides G. Optimal Reductions between Oblivious Transfers Using Interactive Hashing //Advances in Cryptology— EUROCRYPT'06. LNCS, Vol. 4004. Springer-Verlag, 2006. P. 201-221.

43. Damgärd I., Fehr S., Morozov K., Salvail L. Unfair Noisy Channels and Oblivious Transfer //Theory of Cryptography Conf.—TCC'04. LNCS, Vol. 2951. Springer-Verlag, 2004. P. 355-373.

44. Damgärd I., Fehr S., Salvail L., Schaffner C. Oblivious Transfer and Linear Functions //Advances in Cryptology — CRYPTO'06. LNCS, Vol.4117. Springer-Verlag, 2006. P. 427-444.

45. Damgärd I., Kilian J., Salvail L. On the (Im)possibility of Basing Oblivious Transfer and Bit Commitment on Weakened Security Assumptions //Advances in Cryptology— EUROCRYPT'99. LNCS, Vol., 1592: SpringerVerlag, 1999. P. 56-73.

46. Ding Y. Z. Oblivious Transfer in the Bounded Storage Model //Advances in Cryptology— CRYPTO'Ol. LNCS, Vol.2139. Springer-Verlag, 2001. P. 155-170.

47. Ding Y. Z., Harnik D., Rosen A., Shaltiel R. Constant-Round Oblivious Transfer in the Bounded Storage Model //Theory of Cryptography Conf.— TCC'04. LNCS, Vol. 2951. Springer-Verlag, 2004. P. 446-472.

48. Dodis Y., Micali S. Lower Bounds for Oblivious Transfer Reductions //Advances in Cryptology— EUROCRYPT'99. LNCS, Vol. 1592. SpringerVerlag, 1999. P. 42-55.

49. Dowsley R., Graaf J., Miiller-Quade J., Nascimento A. Oblivious Transfer Based on McEliece Assumptions // Inform. Theoretic Security. LNCS, Vol. 5155. Springer-Verlag, 2008. P. 107-117.

50. Du W., AtallahM.J. Privacy-Preserving Cooperative Scientific Computations // Proc. of the 14th IEEE workshop on Computer Security Found. IEEE Computer Security, 2001. P. 273-294.

51. Du W., Atallah M.J. Privacy-Preserving Cooperative Statistical Analysis //Proc. of the 17th Annu. Computer Security Applications Conf. IEEE Computer Soc., 2001. P. 102-110.

52. Du W., Atallah M.J. Secure Multi-Party Computation Problems and Their Applications: A Review and Open Problems //New Security Paradigms Workshop. Cloudcroft, New Mexico, USA, 2001. P. 13-22.

53. Du W., Han Y., Chen S. Privacy-Preserving Multivariate Statistical Analysis: Linear Regression and Classification // Proc. of the Fourth SI AM Intern. Conf. on Data Mining. 2004. P. 222-233.

54. Even S., Goldreich O., Lempel A. A Randomized Protocol for Signing Contracts // Proc. CRYPTO'82 Plenum Press. 1983. P. 205-210.

55. FanoR.M. Transmission of Information.— MIT Press, Cambridge, Mass., 1961. 389 p.

56. Frikken K.B., Atallah M J. Privacy-Preserving Route Planning I I Proc. of the 2004 ACM workshop on Privacy in the Electronic soc. (WPES'04). ACM, N. Y., 2004. P. 8-15.

57. Frikken K.B., Atallah M.J., Zhang C. Privacy-Preserving Credit Checking //Proc. of the 6th ACM conf. on Electronic commerce (EC'05). ACM, N. Y., 2005. P. 147-154.

58. Goldreich O. Foundations of Cryptography. Vol.2. Basic Applications.— Cambridge Univ. Press, 2004. 448 p.

59. Goldreich S., Micali S., RiverstR. A Digital Signature Scheme Secure Against Adaptive Chosen Message Attacks // SIAM J. on Computing. 1988. Vol. 17. P. 281-308.

60. Haitnerl. Implementing Oblivious Transfer Using Collection of Dense Trapdoor Permutations //Theory of Cryptography Conf.—TCC'04. LNCS, Vol. 2951. Springer-Verlag, 2004. P. 394-409.

61. Halevi S., Micali S. Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing // Advances in Cryptology — CRYPTO'96. LNCS, Vol. 1109. Springer-Verlag, 1996. P. 201-215.

62. Hastad J., Impagliazzo R., Levin L., Luby M. A Pseudorandom Generator from any One-Way Function // SIAM J. on Computing. 1999. Vol. 28. No. 4. P. 1364-1396.

63. Ibrahim M. H. Two-Party Private Vector Dominance: The AU-Or-Nothing Deal // Proc. of the Third Intern. Conf. on Inform. Technology: New Generations. IEEE Computer Soc., 2006. P. 166-171.

64. Imai H., Morozov K., Nascimento A. On the Oblivious Transfer Capacity of the Erasure Channel // Proc. of 2006 IEEE Intern. Symp. on Inform. Theory (ISIT'06). 2006. P. 1428-1431.

65. Impagliazzo R., Rudich S. Limits on the Provable Consequences of OneWay Permutations // Proc. of the 21st Annu. ACM Symp. on Theory of Computing (STOC'89). ACM Press, 1989. P. 186-208.

66. Ioannidis I., Grama A. An Efficient Protocol for Yao's Millionaires Problem //Proc. of the 36th Hawaii Intern. Conf. on System Sciences 2003. 2003.

67. Jha S., Kruger L., McDaniel P. Privacy-Preserving Clustering //Computer Security— ESORICS'2005. LNCS, Vol.3679. Springer-Verlag, 2005. P. 397-417.

68. Kalai Y. T. Smooth Projective Hashing and Two-Message Oblivious Transfer //Advances in Cryptology— EUROCRYPT'05. LNCS, Vol.3494. Springer, 2005. P. 78-95.

69. Kilian J. Founding Cryptography on Oblivious Transfer II Proc. of the 20th Annual ACM Symp. on Theory of Computing (STOC'88). ACM Press, 1988. P. 20-31.

70. Kissner L„ Song D. Privacy-Preserving Set Operations // Advances in Cryptology — CRYPTO'05. LNCS, Vol. 3621. Springer, 2005. P. 241-257.

71. Kobara K., Morozov K., Overbeck R. Coding-Based Oblivious Transfer //Mathematical Methods in Computer Science. LNCS, Vol. 5393. Springer-Verlag, 2008. P. 142-156.

72. Korjik V., Morozov K. Non-asymptotic Bit Commitment Protocol Based on Noisy Channels // 20th Biennial Symp. on Communications. Kingston, 2000. P. 74-78.

73. Korjik V., Morozov K. Generalized Oblivious Transfer Protocols Based on Noisy Channels II Inform. Assurance in Computer Networks. LNCS, Vol. 2052. Springer-Verlag, 2001. P. 219-229.

74. Li J., Atallah M. Secure and Private Collaborative Linear Programming // Proc. of the 2nd Intern. Conf. on Collaborative Computing: Networking, Applications and Worksharing (CoIlaborateCom 2006). IEEE, USA, 2006. P. 1-8.

75. Mayers D. Unconditionally Secure Quantum Bit Commitment is Impossible // Physical Rev. Letters. 1997. Vol. 78. No. 17. P. 3414-3417.

76. Naor M. Bit commitment Using Pseudo-Randomness // J. of Cryptology. 1991. Vol. 4. No. 2. P. 151-158.

77. NaorM., Ostrovsky R., Venkatesan R., YungM. Perfect Zero-Knowledge Arguments for NP Using any One-Way Permutation // J. of Cryptography. 1998. Vol. 11. No. 2. P. 78-108.

78. Naor M., Pinkas B. Efficient Oblivious Transfer Protocols // Proc. of the 12th Annual ACM-SIAM Symp. on Discrete Algorithms, 2001. P. 448-457.

79. Nascimento A., Winter A. On the Oblivious Transfer Capacity of Noisy Correlations // Proc. of the IEEE Intern. Symp. on Inform. Theory (ISIT'06). 2006. P. 1871-1875.

80. Peikert C., Vaikuntanathan V., Waters B. A Framework for Efficient and Composable Oblivious Transfer //Advances in Cryptology— CRYPTO'08. LNCS, Vol. 5157. Springer-Verlag, 2008. P. 554-571.

81. Peikert C., Waters B. Lossy Trapdoor Functions and Their Applications // STOC'08. ACM, 2008. P. 187-196.

82. Rabin M. O. How to Exchange Secrets by Oblivious Transfer //Technical Rep., TR'81. Harvard Aiken Computation Lab., 1981.

83. Savvides G. Interactive Hashing and Reductions between Oblivious Transfer Variants.— McGill Univ., Montreal, Canada, 2007. 128 p.

84. Saygin Y., Verykios V. S., Elmagarmid A. K. Privacy-Preserving Association Rule Mining // Proc. of the 12th Intern. Workshop on Research Iss. on Data Engineering: Engineering E-Commerce/E-Business Systems (RIDE'02). IEEE, USA, 2002. P. 151-158.

85. Troncoso-Pastoriza J. R., Katzenbeisser S., Celik M. Privacy-Preserving Error Resilient DNA Searching through Oblivious Automata //Proc. of the 14th ACM Conf. on Computer and Communications Security (CCS'07). ACM, N. Y., 2007. P. 519-528.

86. VaidyaJ., Clifton C. Privacy-Preserving Association Rule Mining in Vertically Partitioned Data // Proc. of the Eighth ACM SIGKDD Intern. Conf. on Knowledge Discovery and Data Mining. ACM, N. Y., USA, 2002. P. 639-644.

87. Vaidya J., Clifton C. Privacy-Preserving Outlier Detection // Proc. of the 4th IEEE Intern. Conf. on Data Mining (ICDM'04). IEEE Computer Society, USA, 2006. P. 233-240.

88. Wang Q., Luo Y., Hung L. Privacy-Preserving Protocols for Finding the Convex Hulls // 3-rd International Conference on Availability, Reliability and Security. IEEE Computer Society. P. 727-732.

89. WiesnerS. Conjugate Coding //SIGACT News. 1983. Vol. 15. No. 1. P. 78-88.

90. Winter A., Nascimento A., Imai H. Commitment Capacity of Discrete Memoryless Channels //Cryptography and Coding. LNCS, Vol.2898. SpringerVerlag, 2003. P. 35-51.

91. WullschlegerJ. Oblivious Transfer Amplification //Advances in Cryp-tology■— EUROCRYPT'07. LNCS, Vol.4515. Springer-Verlag, 2007. P. 555572.

92. WolfS., Wullschleger J. Oblivious Transfer is Symmetric // Advances in Cryptology — EUROCRYPT'06. LNCS, Vol.4004. Springer-Verlag, 2006. P. 222-232.

93. Yao A. Protocols for Secure Computations // Proc. of the 23rd FOCS'82. 1982. P. 160-164.

94. Yao A. How to Generate and Exchange Sccrets // Proc. Of the 27th FOCS. 1986. P. 162-167.