1/p-безопасные вычисление без честного большинства и лучший из обоих миров

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:11, 13 декабря 2015.
Аннотация Протокол для вычисления функции является безопасным, если противник в этом протоколе не может причинить больше вреда, чем в идеальном вычислений, где стороны передают свои входные данные третьей доверенной стороне, которая возвращает выход функции всем сторонам. В частности, в идеальной модели, честность таких вычислений - получение всеми сторонами результатов выхода функции. Клив (STOC 1986) доказал, что, в общем, справедливость невозможна без честного большинства. Чтобы преодолеть эту невозможность, Гордон и Кац (Eurocrypt 2010) предложил широкое определение - 1 / р-безопасное вычисление - которое гарантирует частичную справедливость. Для двух сторон, они строят 1 / р-безопасные протоколы для функций, для которых размер или их домен или их диапазон полиномиальны(в параметре безопасности). Гордон и Кац спросили, могут ли их результаты быть обобщены на случай многосторонних протоколов.

Мы изучаем 1 / р-защищенные протоколы в многосторонней установке для общих функций. Основным результатом работы является построение 1/р-защищенных протоколов, устойчивых к любому числу недобросовестных сторон при условии, что число сторон является постоянным и размер диапазона функции не превышает многочлен(в параметре безопасности n). Если меньше чем 2/3 сторон недобросовестны, размер домена постоянен, а функция детерминированна, то наши протоколы являются эффективными даже тогда, когда количество сторон равно loglog(n). С отрицательной стороны, мы показали, что, когда число сторон супер-постоянно, 1 / р-защищенные протоколы невозможны, когда размер домена полиномиален. Таким образом, наши результаты возможности 1/р-безопасного вычисления, по существу, связаны. Наши результаты мотивируют нас построить в будущем протоколы с большими гарантиями: если после выполнения протокола есть большинство честных сторон, то наши протоколы обеспечивают полную безопасность. Однако, если только меньшинство из сторон честно, то наши протоколы 1 / р-безопасны. Таким образом, наши протоколы обеспечивают лучшее из обоих миров, где 1/р-безопасность является лишь резервным вариантом, если нет честного большинства.

Введение