Эффективная строковая привязка, получаемая из слабой битовой

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:47, 30 октября 2015.
Efficient String-Commitment from Weak Bit-Commitment
NTRU.PNG
Авторы Kai-Min Chung,[@: 1],
Feng-Hao Liu[@: 2],
Chi-Jen Lu[@: 3],
Bo-Yin Yang[@: 4]
Опубликован 2011 г
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Краткое содержание. Мы изучаем усиление безопасности для схем привязок, а также улучшаем эффективность усиления черного ящика в вычисляемых параметрах, где безопасность противостоит ВПВ активному неприятелю. Мы показываем, что запросов черного ящика к слабой схеме битовой привязки с фиксированной безопасностью является достаточным для создания схемы привязки со стандартной пренебрегаемой безопасностью, где является параметром безопасности, а является супер-логарифмической функцией . Кроме того, результирующая схема привязки является схемой строковой привязки, которая может фиксировать -битовые строки. Это улучшает предыдущую работу Damgard, [DKS99], Halevi и Rabin [HR08], чьи преобразования требуют запросов черного ящика для фиксирования единичного бита.

Как субпродукт нашего анализа мы также улучшили эффективность усиления безопасности для имитовставок, цифровых подписей и псевдослучайных функций, которые были изучены в [DIJK09]. Это следует из улучшения динамической слабодоказываемой головоломки «класса Теорем Чернова» из [DIJK09].

ВВЕДЕНИЕ

Усиление безопасности для схем привязок.

Усиление безопасности для слабых криптографических примитивов является базовым вопросом, который изучался еще со времен основополагающей работы Yao [Yao82]. В последние годы этот вопрос активно изучается для множества примитивов в различных вариациях. Назовем несколько конкретных примеров, для которых изучалось усиление: протоколы шифрования [DNR04], схемы привязок [DKS99,Wul07, HR08], неочевидный обмен [DKS99,Wul07], имитовставки, цифровые подписи, псевдослучайные последовательности [DIJK09]. Некоторые из этих работ рассматривают теоретическую информационную безопасность (например, [DKS99]), некоторые - практическую. Многообразные свойства безопасности примитивов представляют различные параметры согласования, например схемы привязки, более согласованны, чем протоколы шифрования, а атаки-с-выбором-сообщений для имитовставок, представляют различные виды согласования. Доказательства улучшения результатов приводят к более глубокому изучению интерактивных и вычислительных параметров.


В этой статье мы продолжаем изучение усиления безопасности для схем привязок, которые были ранее изучены в [DKS99, Wul07, HR08]. Нашей целью является усиление черного ящика в вычисляемых параметрах, в котором безопасность сдерживает атаки вероятностного полиномиального времени (ВПВ). То есть, стартовой позицией является (слабая) схема привязки к биту , которая является p-скрытой в том смысле, что ни один враждебный ВПВ получатель, который мог произвольно изменить подписанный протокол, не может угадать связанный бит верно с вероятностью более , и q-связывание в том смысле, что ни один враждебный ВПВ отправитель не может открыть двумя способами с вероятностью большей, чем , и целью является преобразование в защищенную схему привязки , которая делает запросы черного ящика к и получает незначительную безопасность для обоих параметров.


Предыдущие работы основывались на реализуемых результатах. То есть, для каких значений и возможно усиление безопасности. В теоретико-информационных параметрах (т.е., безопасность защищает от неограниченного нарушителя), Damgard, Kilian and Salvail [DKS99] показали, что преобразование черного ящика возможно, тогда и только тогда, когда , где является параметром безопасности. Halevi and Rabin [HR08] проанализировали преобразование [DKS99] для вычисляемых параметров и доказали, что преобразование черного ящика возможно, когда . Не так давно, независимо от нашей работы, Holenstein and Schoenebeck [HS10], улучшили результат до оптимального. Они показали, что для вычисляемых параметров усиление безопасности черного ящика достижимо тогда и только тогда, когда .


Однако, существующие преобразования не очень эффективны. Для того, чтобы измерить эффективность, давайте рассмотрим запросы черных ящиков к , которые делает, когда и являются константами и . Заметим, что количество вызовов воздействует не только на коммуникационную сложность, но и на раундовую сложность результирующего протокола, так как в вычисляемых параметрах каждый запрос черного ящика нужно делать последовательно (*). Все существующие решения требуют запросов черного ящика для безопасной фиксации одного бита. На более высоких уровнях причина состоит в том, что они усиливают связывающие и скрывающие свойства раздельно. Кажется, что усиление каждого свойства от фиксированного до пренебрегаемого должно запрашивать запросов черного ящика, которые, в случае существующих конструкций и результатов, в общих запросов. С другой стороны, существующие конструкции реализуют схемы привязки к битам, но существуют варианты, когда нужны схемы привязки к строкам. Так как требуется запросов черного ящика для усиления безопасности, возможно мы сможем получить схему привязки к строкам, вместо одной лишь привязки к биту, которая также улучшает эффективность в исчислении показателей, т.е. количества запросов черного ящика на каждый связанный бит. Это заставляет нас задуматься над следующим вопросом.

(*) В целом, этап привязки может состоять из множества раундов. Если запросы черного ящика выполняются параллельно, можно показать на контр-примерах Bellare, Impagliazzo,and Naor [BIN97] для интерактивных аргументов, что безопасность не обязательно может усилиться.

Главный вопрос: Сколько запросов черного ящика требуется для усиления (слабой) схемы привязки к биту с фиксированной безопасностью до пренебрегаемой безопаснсоти? Какова длина строки, к которой результирующий может быть привязан, и каким будет достигнутый показатель?


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


Приложение 1.


Эффективность (p и q константы) Выполнимость
Работа Количество запросов Длина строки Показатель Соответственный диапазон параметров
[HR08] 1
[HS10] 1
Ours
Ours + [HS10]

Суммарные результаты на усиление безопасности для схем привязок в вычисляемых параметрах. «Эффективность» измеряет значения усиления схем привязок от фиксированной безопасности до пренебрегаемой. «Выполнимость» показывает диапазон параметров, в котором возможно усиление.

Для обхода барьера предыдущих преобразований мы использовали коды исправления ошибок и случайные экстракторы для усиления обоих свойств – скрытности и связности одновременно. Для того, чтобы проанализировать нашу конструкцию, была смоделирована безопасность схемы привязки в виде (трудности) решения «2ух фазной» (интерактивной) системы головоломок и изучена сложность решения хотя бы из головоломок. Наш результат по системам головоломок также применим для динамических слабодоказываемых систем головоломок из [DIJK09], и, следовательно, улучшает эффективность усиления безопасности для имитовставок, цифровых подписей и псевдослучайных последовательностей.

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

Системы Головоломок и Усиление Безопасности для Других Примитивов.

Проще говоря, в системах головоломок есть генератор, который создает их, и программа решения, который пытается решить головоломку. На более высоких уровнях системы головоломок обеспечивают хорошую возможность для абстрагирования свойств безопасности криптографических протоколов – сложность решения головоломки моделирует сложность взлома системы неприятелем. Ранее Canetti, Halevi и Steiner [CHS05] определили слабодоказываемые системы головоломок для захвата CAPTCHA сценария, а Dodis, Impagliazzo, Jaiswal, и kabanets [DIJK09] обобщили модель до динамически слабо-доказываемой системы головоломок для сбора данных безопасности имитовставок, цифровых подписей и псевдослучайных функций. В этой статье мы представили 2ух фазные системы головоломок, которые также обобщают модель [CHS05] для захвата обоих свойств – и привязки и сокрытия - схем привязок.

Один из естественных путей для достижения усиления стойкости/безопасности информации заключается в повторении. Предположим, что решение головоломки обладает -сложностью, т.е. ни одна эффективная программа решения не сможет успешно решить головоломку с вероятностью большей, чем . Если успешные решения различных головоломок были независимыми событиями, то успешное решение головоломок должно обладать -сложностью. Однако, с тех пор, как программа решения может сопоставлять свои ответы к различным головоломкам, события перестают быть независимыми и границы стойкости могут не выдержать. В литературе встречаются различные (параллельные) теоремы повторения для вышеупомянутых систем головоломок, говорящие, что границы стойкости соответствуют независимости событий и/или что стойкость увеличивается по экспоненте, что полезно для установления результатов усиления [CHS05, IJK07, DIJK09, Jut10]. В целом, результаты усиления стойкости для одной системы головоломок отличаются от другой. Более того, для обобщенных интерактивных протоколов, которые могут быть рассмотрены, как «интерактивные системы головоломок», существуют контр-примеры (при разумных допущениях), показывающие, что стойкость может и не усилиться вовсе при параллельном повторении [BIN97, PW07].


Предыдущие результаты. Для слабодоказываемых систем головоломок Canetti, Halevi и Steiner [CHS05] доказали непростую Теорему Прямого Произведения, говорящую что решение головоломок обладает - сложностью, если решение одной головоломки обладает – сложностью, а Impagliazzo, Jaiswal и Kabanets [IJK07] доказали более общую Теорему класса Чернова, говорящую, что решение хотя бы из головоломок обладает -сложностью, если решение одной головоломки обладает -сложностью. Границы [IJK07] были недавно улучшены Jutla [Jut10] до почти-оптимальных. Dodis, Impagliazzo, Jaiswal и Kabanets [DIJK09] расширили Теорему класса Чернова до динамической слабопроверяемой системы головоломок и используют это для достижения усиления безопасности имитовставок, цифровых подписей и псевдослучайных функций. Однако, способы доказательства [IJK07, DIJK09, Jut10] скорее всего не применимы для 2ух фазных систем головоломок.

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


Наши результаты. Мы показали, что три типа результатов стойкости (Прямое произведение, Тип Чернова, Понижение стойкости) в данный момент справедливы для трех вышеупомянутых систем головоломок (слабопроверяемые системы головоломок, динамические слабопроверяемые системы головоломок и 2ух фазные головоломки). Мы доказали Торему Полного Спектра, которая фактически говорит о том, что решение хотя бы из головоломок соответствует границам независимых событий, если решение одной головоломки имеет -сложность, для некоторой константы . Отметим, что такие границы являются оптимальными с тех пор, как программа решения всегда может решать каждую головоломку независимо. Данные по результатам представлены в Приложении 2.

Приложение 2.


Слабопроверяемая Динамическая слабопроверяемая 2ух фазная
Прямое Произведение [CHS05] [DIJK09], Наши [HR08]
Класс Чернова [IJK07, Jut10], Наши [DIJK09], Наши Ours, [HS10]
Понижение Стойкости [HR08] Наши* [HR08]
Полного Спектра Наши, [HS10] Наши* Ours, [HS10]

Общие результаты для различных систем головоломок. «Наши» означают, что либо мы получили новые результаты, либо улучшили границы старых. Работа [HS10] и наша являются независимыми. (*): Наши результаты по понижению стойкости и полному спектру подходят только для разновидностей динамических слабопроверяемых систем головоломок (см. полную версию статьи для подробностей).

Мы доказали Теорему Усиления Полного Спектра используя алгоритм единичного приведения, который применим для всех 3х систем головоломок. Алгоритм приведения можно рассматривать как обобщение алгоритмов приведения Canetti, Halevi и Steiner [PCHS05].

Вследствие этого, наши улучшения Теоремы класса Чернова для динамических слабопроверяемых систем головоломок Dodis’a и других [DIJK09] предполагают улучшения эффективности усиления безопасности для имитовставок, цифровых подписей и псевдослучайных последовательностей.

Исторические заметки. Работа Holenstein и Schoenebeck [HS10] выполнялась независимо от нашей, однако у них есть значительные совпадения. Мы кратко сравнили результаты и сделали несколько заметок, которые показаны далее. Обе работы улучшили результаты работы Halevi и Rabin[HR08], для усиления безопасности схем привязок, но сопряженными путями. Holenstein и Schoenebeck предложили осуществимый результат, показывая, что усиление безопасности возможно тогда и только тогда, когда . Мы улучшали эффективность преобразования, показывая, что достаточно только запросов черного ящика для усиления безопасности от фиксированного значения до пренебрегаемого и результирующая схема привязки сможет «привязаться» к -битной строке. Контструкции в обоих работах очень разные. Как показано в Таблице 1, несколько результатов можно скомбинировать для получения улучшений одновременно.

Для систем головоломок, Holenstein и Schoenebeck [HS10] показали практически ту же самую идею и алгоритм приведения, которые были в нашей работе. Однако, у них был более искусный путь, чтобы разобраться с параметрами, и, как следствие, их результаты подходят для каждой в противоположность постоянной у нас. Также, они рассмотрели более общие «монотонные объединяющиеся функции» вдобавок к пороговым функциям, рассмотренным в нашей работе. С другой стороны, применение повышения эффективности усиления безопасности для имитовставок, цифровых подписей и псевдослучайных последовательностей было акцентировано нами.

ПРЕДВАРИТЕЛЬНАЯ ИНФОРМАЦИЯ

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

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

TemplateDifinitionIcon.svg Определение «Определение 1»
Расстояние Хэмминга двух строк и является количеством позиций , таких что .Пусть будет кодом. Минимальное расстояние является минимальным расстоянием Хэмминга над всеми парами кодовых слов и , таких что
TemplateLemmaIcon.svg Лемма «Лемма 1»
Существуют универсальные константы для которых утверждение верно. Пусть будет положительным целым и будут удовлетворять условию . Пусть будет целым, таким что . Пусть будет произвольным линейным кодом определенным , где является произвольной 0-1 матрицей. Тогда минимальным расстояние C будет хотя бы с вероятностью хотя бы


ОПРЕДЕЛЕНИЯ И ГЛАВНЫЕ ТЕОРЕМЫ.

Схемы привязки.

В этом разделе мы формально определим схемы привязок и представим нашу главную теорему. Мы рассмотрим стандартную модель, где передача осуществляется посредством классического канала без шумов и «отвязка» не интерактивна [Gol01, HR08].

TemplateDifinitionIcon.svg Определение «Определение 2 (Схемы привязок). »
Схема привязки – интерактивный протокол , который обладает следующими свойствами:
  1. Схема состоит из 2ух стадий: стадия привязки и стадия открытия. В обоих стадиях отсылатель и получатель получают секретный параметр как общий параметр.
  2. В начале стадии привязки отправитель получает закрытый параметр , который указывает на строку, к которой должен «привязаться».Результаты стадии привязки находятся в открытом выходе, который мы называем привязка выход . Без потери общности, может быть полностью расшифрован из взаимодействия между и , а – закрытым «подбрасыванием монеты» .
  3. В стадии открытия, отправитель посылает пару , где – «строка отвязки» для строки . Получатель принимает или отвергает ее, в зависимости от .
  4. И отправитель, и получатель являются рациональными, т.е. оба обрабатываются за вероятностное полиномиальное время в параметре безопасности .
  5. всегда будет принимать с вероятностью , если и отправитель и получатель будут следовать предписанной стратегии. Если принимает с вероятностью равной 1, то можно сказать, что обладает идеальной точностью.
  6. Если строка привязки состоит только из 1ого бита в , то называется схемой привязки к биту. В других случаях называется схемой привязки к -битной строке.

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

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

TemplateDifinitionIcon.svg Определение «Определение 3 (p-скрытие в пределах времени T).  »
Схема привязки является p-скрытной в пределах одного времени , если для каждого незаконного получателя вероятностного времени , распределения (отображение и (отображение не различимы по времени , где – независимая и одинаково распределенная копия . То есть, для каждого вероятностного времени и отличительного признака ,

Можно сказать, что является p-скрытной, если p-скрытна в пределах времени для каждой фиксированной и достаточно большого параметра безопасности .

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

Замечание 2. Для схем привязки к биту, p-сокрытие равносильно утверждению, что получатель может угадать связанный бит с вероятностью, большей чем . Формально, для каждого времени независимой переменной ,

отображение
TemplateDifinitionIcon.svg Определение «Определение 4 (Связывающая игра).»
Связывающая игра для схемы привязки разыгрывается между законным получателем , и незаконным отправителем с поисковиком «отвязки» . Игра состоит из 2ух стадий:
  1. В стадии привязки, взаимодействует с для создания отображения [отображение
  2. В стадии нахождения «отвязки», получает отображение [отображение и создает 2 строки «отвязки» и .

является успешной, если в стадии открытия принимает 2 строки «отвязки» и .

TemplateDifinitionIcon.svg Определение «Определение 5 (q-связывание в пределах времени ). »
Схема привязки является -связывающей в пределах времени , если в связывающей игре для каждой пары времени , вероятность успеха не более . Можно сказать, что -связывающая, если -связывающая в пределах времени для каждой фиксированной и достаточно большого параметра безопасности .
TemplateDifinitionIcon.svg Определение «Определение 6 (безопасность схем привязок).  »
Схема привязки является -безопасной (в пределах времени ), если – p-скрывающая и -связывающая (в пределах времени ). Com безопасна, если является (, )-безопасной для каждой фиксированной и достаточно большого параметра безопасности .

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

TemplateDifinitionIcon.svg Определение «Теорема 1. »
Пусть будут константами и . Предположим, что существует -безопасная схема привязки . Тогда, для каждых , где является параметром безопасности, существуют безопасные схемы привязок к -битным строкам, которые делают только запросов черного ящика к .

ЭФФЕКТИВНОСТЬ УСИЛЕНИЯ БЕЗОПАСНОТИ ДЛЯ СХЕМ ПРИВЯЗОК.

Эффективное усиление безопасности при известных параметрах безопасности.

Усиление безопасности для Схем Привязок к Строкам.

Соединяя все воедино.

Мы готовы представить формальное описание нашего эффективного усиления безопасности для схем привязок (см. Приложение 5) и доказать Теорему 1.

Приложение 5

Финальная Конструкция.

-Вход. -безопасная схема привязки к биту , у которой
-Выход. Безопасная схема привязки к строке , у которой .
  1. Применяются поочередно преобразования Halevi и Rabin для получения -безопасной схемы привязки к биту , , достаточно малы.
  2. Применяется наше преобразование для получения -безопасной схемы привязки к -битной строке , где , а – некоторая константа.
  3. Пусть – произвольно выбранная функция .Применяется для получения -безопасной схемы привязки к -битной строке .
  4. Применяется для получения безопасной схемы привязки к -битной строке .
Эффективное усиление безопасности схем привязок

Доказательство (Теоремы 1). То, что является безопасной схемой привязки к строке следует напрямую из Теоремы 2, Лемм 4,5,6. делает запросов черного ящика к , делает запросов к , запросов к и, наконец, делает запросов к . Общее количество запросов черного ящика, которое делает к равно , что и было необходимо.

БЛАГОДРАНОСТИ

Мы благодарим Salil Vadhan за его комментарии на протяжении всего времени, в течении которого велась эта работа. Также, мы благодарим Anna Lysyanskaya и Evgeniy Dodis за предоставление информации.

СНОСКИ

[BIN97] Bellare, M., Impagliazzo, R., Naor, M.: Does parallel repetition lower the errorin computationally sound protocols? In: FOCS, pp. 374–383 (1997)
[CHS05] Canetti, R., Halevi, S., Steiner, M.: Hardness amplification of weakly verifiable puzzles. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 17–33.Springer, Heidelberg (2005)
[DIJK09] Dodis, Y., Impagliazzo, R., Jaiswal, R., Kabanets, V.: Security amplification for interactivecryptographic primitives. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 128–145. Springer, Heidelberg (2009)
[DKS99] Damgard, I., Kilian, J., Salvail, L.: On the (im)possibility of basing oblivious

transfer and bit commitment on weakened security assumptions. In: Stern, J.(ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 56–73. Springer, Heidelberg (1999)

[DNR04] Dwork, C., Naor, M., Reingold, O.: Immunizing encryption schemes from decryption errors. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 342–360. Springer, Heidelberg (2004)
[Gol01] Goldreich, O.: Foundations of Cryptography. Basic tools. Cambridge University Press, Cambridge (2001)
[HR05] Holenstein, T., Renner, R.: One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 478–493. Springer, Heidelberg (2005)
[HR08] Halevi, S., Rabin, T.: Degradation and amplification of computational hardness.In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 626–643. Springer,Heidelberg (2008)
[HS10] Holenstein, T., Schoenebeck,G.: General hardness amplification of predicates and puzzles. CoRR, abs/1002.3534 (2010)
[IJK07] Impagliazzo, R., Jaiswal, R., Kabanets, V.: Chernoff-type direct product theorems.In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 500–516.Springer, Heidelberg (2007)
[Jut10] Jutla, C.S.: Almost optimal bounds for direct product threshold theorem. In:Micciancio, D. (ed.) Theory of Cryptography. LNCS, vol. 5978, pp. 37–51.Springer, Heidelberg (2010)
[MT09] Maurer, U., Tessaro, S.: Computational indistinguishability amplification: Tight product theorems for system composition. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 350–368. Springer, Heidelberg (2009)
[PW07] Pietrzak, K.,WikstrЁom, D.: Parallel repetition of computationally sound protocols revisited. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 86–102. Springer, Heidelberg (2007)
[Val84] Valiant, L.G.: Short monotone formulae for the majority function. J. Algorithms 5(3), 363–366 (1984)
[Wul07] Wullschleger, J.: Oblivious-transfer amplification. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 555–572. Springer, Heidelberg (2007)
[Yao82] Yao, A.C.-C.: Theory and applications of trapdoor functions (extended abstract).In: FOCS, pp. 80–91 (1982)

Контакты авторов материала

  1. School of Engineering & Applied Sciences, Harvard University, Cambridge MA, USA, E-mail: [1]
  2. Department of Computer Science, Brown University, Providence RI, USA, E-mail: [2]
  3. Institute of Information Science, Academia Sinica, Taipei, Taiwan, E-mail: [3]
  4. Institute of Information Science, Academia Sinica, Taipei, Taiwan, E-mail: [4]