Пороговые и извлекающие криптосистемы для хэш доказательств

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:59, 27 сентября 2015.
Threshold and Revocation Cryptosystems via Extractable Hash Proofs
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Hoeteck Wee[@: 1]
Опубликован 2010 г.
Сайт Department of Computer Science
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. Мы представляем новую объединяющую модель для построения неинтерактивного шифрования и схем подписей, а также расширение схем шифрования, в частности для ряда новых криптосистем, основанных на сложности факторизации, в том числе:
  • пороговая схема подписей (в моделе со случайными алгоритмами), которая поддерживает специальные группы (например, для независимого числа сторон) и реализуется для стандартных подписей Рабина;
  • пороговая схема шифрования, которая поддерживает специальные группы, в которых шифрование такое же как, в криптосистеме Блюма-Гольдвассера, и следовательно, более эффективная, чем реализации на RSA основе.
  • CCA-безопасные пороговые схемы шифрования в моделе со случайными алгоритмами;
  • расширенные схемы шифрования (точнее, аннулированные криптосистемы) который поддерживают специальные группы, чья сложность сравнима со схемами Наора-Пинкаса; кроме того, мы предлагаем вариант построения, который будет CCA-безопасным в моделе со случайным алгоритмом.
Наш подход опирается на новое понятие пороговых хэш доказательств. Оно может быть рассмотрено как обобщение хэш доказательства, которые будут особым видом неинтерактивных доказательств с нулевым разглашением.

Введение

Как говорится в старой поговорке: "Не кладите все яйца в одну корзину". Действительно, это один из основных принципов пороговой криптографии, который распределяет некоторые криптографические функционалы среди многих пользователей, таким образом, что: (1) любые стороны могут коллективно вычислить функционал; и (2) не одно подмножество из сторон может поставить под угрозу безопасность функционала. Двумя каноническими приложениями пороговой криптографии будут схемы шифрования открытых ключей и подписей, где функционалы отвечают за расшифровку и подписания, соответственно. Данный подход был инициирован в[1][2][3] , и к настоящему времени выполнен большой объем работы по пороговым схемам подписей[4][5][6][7][8][9][10][11][12] и пороговых схемам шифрования[13][14][15][11][16][17].

Если мы хотим работать исключительно с двусторонними схемами, то главные вопросы практического шифрования и пороговых схем подписей по существу будут решены. Пороговые схемы подписей Боне, Линна, Шахама[10] и пороговые схемы шифрования Бойена, Мэйя и Вотерса[17][16] не являются интерактивными (каждая сторона локально вычисляет долю подписи/шифровки без какого-либо взаимодействия с другими сторонами), что гарантирует устойчивость к вредоносным сторонам (при проверке ключа, каждая сторона может проверить, чтобы доли подписи/шифровки были правильно сформированы) и хорошо подходит для использования в специальных группах, таких как MANET ("мобильные одноранговые сети", которые имеются во многих беспроводных или военных применениях). Последнее требование, сформулированное в недавней работе Дженнаро и соавт.[12], означает, что криптографический протокол поддерживает пространства экспоненциальных размеров и не имеет какой-либо зависимости от общего количества сторон.

Учитывая, что основной принцип пороговой криптография пытается избежать наличие какой-либо точки ошибки, было бы весьма странно, конечно, строить всю пороговую криптографию на парных и дискретно-логарифмических предположениях. Подходящим классом альтернативных предположений будет тот, который связан с факторизацией, где многие проблемы остаются открытыми. У нас практически все схемы основаны на RSA предположении, единственным исключением является схема Каца и Юнга[11], которая не поддерживает специальные группы. Мы также не знаем ничего о пороговых схемах шифрования на основе факторизации, которые поддерживали бы специальные группы. В частности, мы не знаем практических пороговых CCA-безопасных схем шифрования, основанных на факторизации, даже в моделе со случайным алгоритмом; это проблема осталась открытой в работе[13]. Кроме того, очень мало известно криптосистемах отзыва, несвязанных с пороговыми криптосистемами. Это особый вид схем передачи шифрования[18], где отправитель передает зашифрованное сообщения, созданные таким образом, что все, за исключением небольшой части, получатели могут расшифровать сообщение.

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

  • Пороговая схема подписей (в моделе со случайными алгоритмами), которая поддерживает специальные группы и реализуется для стандартных подписей Рабина; (а именно, конечным результатом работы протокола будет подпись Рабина, и любой может проверить ее, как если бы она была создана централизованным автором);
  • Пороговая схема шифрования (в стандартной моделе), которая поддерживает специальные группы, в которых шифрование такое же как, в криптосистеме Блюма-Гольдвассера, и следовательно, более эффективная, чем реализации на RSA основе.
  • CCA-безопасные пороговые схемы шифрования (в моделе со случайными алгоритмами) вычислительные и коммуникационные сложности сложности для которых примерно равны пороговой схеме Шоапа[6] и шифрованию Хофхайнца-Килтца[19].
  • Криптосистемы с отзывом (в стандартной модели), которые также поддерживают специальные группы, сложность которых сравнима со схемами Наора-Пинкаса[20], причем мы предлагаем вариант построения, который CCA-безопасен в моделе со случайными алгоритмами.
Таблица 1. Резюме для пороговых PKE схем
Источники Предложение Безопасность Спец. функции
[4], [8] RSA CPA NO
[21], [15] DCR CPA, CCA (RO) NO
[11], [15] QR CPA, CCA (RO) NO
[11] факторизация CPA NO
наша работа факторизация CPA YES
наша работа факторизация CCA (RO) NO

Мы приводим таблицу 1 для сравнения с предыдущими пороговыми криптосистемами на основе факторизации. Здесь же отметим, что наш подход также охватывает многие из вышеупомянутых пороговых криптосистем и систем в отзывом, основанные на парах и дискретно-логарифмическом предположении[10][17][20] (см. таблицу 2).

Обзор нашего построения

Мы продолжим, чтобы дать обзор нашей системы и построения.

Пороговые расширенные хэш доказательства. Введем понятие пороговой хэш-системы доказательств, которая обобщает наши недавние работы[22]. Неформально, эти хэш-системы доказательств похожи на универсальные доказательства Крамера-Шоапа[23] в том, что они представляют из себя особый вид неинтерактивного доказательства с нулевым разглашением[24], за исключением того, что мы заменяем требование устойчивости "доказательством знания"[25][26]. В частности, доказательства определяются множеством функций , проиндексированных открытым ключом HK и принимающих два входа, маркер и исполнение . Мы будем требовать, чтобы была эффективно вычислима либо для заданных перестановок образца u, либо для секретного ключа соответствующего маркера. Кроме того, множество функций параметризуется "пороговым" значением , которое играет следующую роль:

  • - извлекаемость: для заданного доказательства исполнения и для различных маркеров, мы можем эффективно "извлекает" свидетеля s для исполнения (это в основном имеет смысл, когда вычисление свидетеля для заданного исполнения представляется сложным);
  • -моделируемость: с другой стороны, любые доказательства не обнаруживают "полезной" информации о свидетеле, то есть существует симулятор, который может эффективно сгенерировать доказательства для различных маркеров исполнения , не зная ничего о свидетеле. Формальные требования сильнее в том, что симулятор может генерировать случайные ключи HK вместе с секретными ключами для любых различных маркеров.

Отметим здесь, что случай для соответствует "все, кроме одного" извлекаемому хэш доказательству из[22]; то есть пороговое извлекаемое доказательство можно рассматривать как "все, кроме " аналог хэш доказательств.

От Хэш доказательств к криптосистемам. С неформальной точки зрения к пороговым извлекаемым хэш доказательствам мы можем сказать, каким образом мы выводим пороги и криптосистемы с отзывом (см. рисунок 3 для параметров). Отметим здесь, что мы работаем в моделе с доверенным дилером, который генерирует ключи HK и передает каждая стороне идентификаторы ID с секретным ключом, соответствующем ID маркерам. Это хорошо подходит для специальных динамических сетей, где любой пользователь может подключиться к сети в любое время и зарегистрироваться у доверенного дилера, чтобы получить секретный ключ; однако в этой работе, мы говорим только об условиях, когда порог зафиксирован раз и навсегда.

  • пороговое шифрование: Для шифрования бита мы генерируем случайную пару исполнение-свидетель , маскируем бит с использованием бита из , а также публикуем вместе с замаскированным битом. Долей шифровки для ID маркера стороны будет просто доказательство . Функциональные требования следуют из - извлекаемости – любой может провести расшифровку при получении доли от любой из сторон, более того, - моделируемость предотвращает сообщения от расшифровки сговорившимися сторонами.
  • пороговые подписи: Подписью для сообщения будет свидетель s для исполнения , где является хэш-функцией, смоделированной как случайный алгоритм (для "полного хэш домена"). Долей подписи для ID пользователя снова будет доказательство  ; функционалы и безопасность здесь в точности такая же, что для порогового шифрования.
  • криптосистемы с отзывом: Мы хотим зашифровать сообщение таким образом, что любая из сторон за пределами названного набора из пользователей может осуществить расшифровку. (Чтобы отозвать меньше, чем пользователей, мы можем просто добавить "пустые" идентификаторы). Опять же, чтобы зашифровать бит, мы генерируем случайную пару , маскируем бит с использованием бита из , а также публикуем вместе с замаскированным битом и доказательствами . Любая сторона вне названного множества может вычислить доказательство, с использованием секретного ключа для маркера ID, а затем получить для расшифровки.

Мы также покажем, как реализовать надежность для подписей, следуя[8], и CCA безопасность для порогового шифрования и схем с отзывом (в рамках модели со случайными алгоритмами). Наши методы для достижения CCA безопасности следуют парадигме с "всех, кроме одного извлекаемого хэш доказательства" из[22][27][19], в то время, как большинство предыдущих построений[14][28][15] полагались на парадигмы Крамера-Шоапа[29][23] или Хаопа-Юнга[30], которые ограничены, по своей сути, в принятии решений.

Анализ пороговых извлекающих хэш доказательств. Начнем с неформального описания нашего подхода для построения пороговых извлекающих хэш доказательств. Подход обобщает прямые построения «все, кроме одного» извлекающих хэш доказательств в[22] и предоставляет другую точку зрения на теже построения. Основная идея заключается в использовании алгоритма Шамира в экспоненте. Более точно, мы берем многочлен , случайной степени при ограничении, что это такая специальная величина, что . Основной секретный ключ задается многочленом , а открытый ключ HK образуется из некоторых коэффициентов для . Секретный ключ, соответствующий маркеру TAG задается как и . Вычисление для заданных бросков монеты генерирует соответствующие исполнения для оценки в экспоненте. Учитывая хэш доказательства для u и соответствующие маркеры, мы можем восстановить с помощью лагранжевого приближения для экспоненты.

Таблица 2. Описание старых и нынешнего построений CDH/DDH, BDDH и факторизации.
примитивы CDH/DDH BDDH факторизация
пороговые PKE схемы общеприняты общеприняты новые
пороговые подписи [5] (RO) [10] новые (RO)
передающие PKE схемы [20] [20] новые
CCA пороговые PKE схемы [13], [15] (RO) [17], [16] новые (RO)
CCA передающие PKE схемы [28] новые новые (RO)
Для большинства примитивов и предположений, наше построение совпадает и расширяет существующие. Мы подчеркиваем два случая, где существующие работы достигают лучших результатов, чем наша. Отметим, что схема[28] достигает только слабой CCA безопасности.
Таблица 3. Сложность нашей и других схем, если судить по числу групповых элементов.
примитивы откр. ключ секр. ключ шифротекст\подпись шифротекст\доля подписи
пороговые PKE схемы
пороговые подписи
передающие PKE схемы
CCA пороговые PKE схемы
CCA передающие PKE схемы
Для передающих PKE схем обозначает пороговый отзыв. Здесь, секретный ключ относится к пользовательскому/серверному секретному ключу, секретный ключ дилера имеет размер .

Это просто для дискретно-логарифмического случая, так как мы знаем порядок групп. Создание смоделированных доказательств или секретных ключей для любых различных тегов очень легко, так как оценка функции в любом месте будет случайной; основные технические ложности связаны с тем, чтобы смоделировать последовательность ключей HK (хотя это опять таки не сложно для дискретно-логарифмического случая). Построение с факторизацией основывается на односторонних перестановках Рабина. Мы начинается с простого наблюдения, что мы можем вычислить квадратный корень для u при возведении в степень секретного значения . Здесь мы используем разделение секрета по множеству , тогда как предыдущие схемы[11] применяли разделение секрета к факторизации модуля N. Для того, чтобы выполнить лагранжеву интерполяцию для множества неизвестного порядка, мы будем опираться на идеи, разработанные для RSA схем[6][12] и для криптосистем из[19]. Неформально, мы задаем как . При заданном хэш доказательстве , соответствующем различным маркерам, мы можем восстановить , где D обозначает целое число, используемое для "очистки знаменателя" в дробных лагранжевых коэффициентах, и зависящее от маркеров, используемых в доказательствах. В целях поддержание неизменности пространства экспоненциального размера, мы задаем границу для степени в 2, что приводит для к значению , согласно[12]. Учитывая как u , так и , мы можем восстановить , используя алгоритм Шамира[31].

В нашем построении мы "работаем" с коэффициентами для , а не оцениваем в HK, рассчитывая для заданных бросков монеты и не требуя интерполяций; это первый раз, когда данное свойство используется для RSA/факторизованных схем и имеет значение для обработки в специальных сетях.

О структурных исполнениях. Заглядывая вперед, мы планируем изучить решетчатые исполнения пороговых извлекающих хэш доказательств, распространяя результаты и идеи в[32][33]. Одной из возможных отправных точек является следующее построение: , где и для . Исполнение будет возмущенным узлом решетки , где и задает . Из-за взаимодействия лагранжевых коэффициентов и векторов шума, мы должны будем работать с размерами полей и факторами приближений гораздо большими, чем (см. [33]). Однако, согласно предположению о экспоненциальной сложности для решетчатых задач, мы могли бы все еще потенциально получать осмысленные результаты для таких параметров при .

Предварительные сведения и определения

Механизм открытия ключа (KEM) (Gen, Enc, Dec) с пространством ключей состоит из трех полиномиальный алгоритмов. Через алгоритм генерации ключей создаются открытые/секретные ключи для параметра безопасности ; через вероятностный алгоритм создается равномерное распределение симметричного ключа вместе с шифротекстом ; через обладатель секретного ключа расшифровывает шифротекст , чтобы вернуть ключ , который является элементом из , или специальный символ . Для надежности, мы требуем, чтобы для всех и всех , мы имели .

Бинарные отношения для задач поиска

Зафиксируем множество (бинарных) отношений , проиндексированных открытым параметром . Мы требуем, чтобы был эффективно отбираем для заданного параметра безопасности , и предпологаем, что все алгоритмы имеют как часть своего входа. Мы опускаем отныне всякий раз, когда контекст понятен. Мы также будем требовать, чтобы был эффективно отбираем, где алгоритм отбора обозначается как . Отношение соответствует сложной проблеме поиска, то есть, при заданном , трудно найти такие , что . Формально, мы говорим, что двоичные отношения является односторонними, если:

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

Для отношений, где для заданного u вычисление s представляется сложным, мы можем применить генератор с одно битовым выходом через бит Голдрейха-Левина [34] (со случайностью в ). Во многих случаях, как мы увидим в ближайшее время, можно получить линейное число битов либо за счет применения односторонних перестановок, либо опираясь на предположение о принятии решений.

Пороговые извлекающие хэш доказательства

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

  • (Генерация ключей). Алгоритмов создания генерирует открытые ключи и основной секретный ключ . Учитывая маркеры , алгоритм создания долей вычисляет связанный ключ .
  • (Открытая оценка). Для всех , и выполняется .
  • (Индивидуальные оценки). Для всех , , выполняется
  • (-извлечение). Для всех , , и различных маркеров выполняется
Отметим здесь, что также получает в качестве входа маркеры (опускаем эту часть для простоты обозначений), но не требует в качестве входа .
  • (-моделирование). Для всех , и всех распределения для в следующие экспериментах статистически неразличимы:
  • в первом это полученные при генерации ключей величины и для ;
  • во втором это значения, полученные от

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

Пороговые схемы шифрования

Мы определим пороговую модель (из которой мы можем легко построить пороговое схему шифрования):

  • (этап разделения). Алгоритм генерирует открытый ключ и основной секретный ключ . При заданных идентификаторах , алгоритм создания долей вычисляет ключ .
  • (шифровка). Алгоритм генерирует , а именно случайный ключ вместе с шифротекстом .
  • (расшифровка). Алгоритм расшифровки принимает идентификатор , и вычисляет долю расшифровки этого идентификатора, используя секретный ключ . Более того, существует объединяющий алгоритм, который принимает любые доли расшифровки и выводит .

Семантическая безопасность. Мы определим алгоритм как :

Здесь обозначает алгоритм, который для заданного вычисляет шифротекст , используя , и возвращает вместе с . Это учитывает тот факт, что противник может получить долю расшифровки для известных сообщений, а также учитывает понятие безопасности, используемое в[35], и применяет его к безопасному голосованию. В CCA случае мы предоставляем алгоритм доступ к , с тем ограничением, что допускается только запрашивать для шифротекстов, отличных от шифротекста . Пороговая схема шифрования называется неотличимой для выбранной атаки на текст (IND-CPA), если для всех противников значение является пренебрежимой функцией в .

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

TemplateTheoremIcon.svg Теорема Теорема 1
Если является односторонним отношение, допускающим пороговое извлекающее хэш доказательство, то пороговая KEM модель, показанная на рисунке 4 будет IND-CPA безопасной.
Доказательство
Для заданного PPT противника , нарушающего пороговую схему шифрования, мы создаем , нарушающего псевдослучайность следующим образом: для входа (см. таблицу №4):
  • запускается
  • запускается , чтобы получить .
  • выводится , моделируется с использованием .

Легко отметить, что .

Таблица 4. Пороговая схема шифрования для порогового хэш доказательства
Пороговые PKE схемы
Этап разделения долей Для входного параметра безопасности и порога , дилер генерирует , запускает и задает вместо . Пользователю с идентификатором дается доля .
Шифровка : отбирается , и возвращается .
Расшифровка Для входного шифротекста , пользователь вычисляет долю расшифровки . Учитывая доли расшифровки алгоритм объединения вычисляет и возвращает .

Пороговые схемы подписей

Пороговая схема подписей проводится в два этапа:

  • (Этап разделения долей). Алгоритм генерирует проверку и основной секретный ключ . Учитывая идентификатор , алгоритм разделения долей вычисляет связанный ключ .
  • (Фаза вычисления подписей). Алгоритм вычисления подписей принимает идентификатор и сообщение, далее он вычисляет доли подписей для этого идентификатора с помощью своего секретного ключа . Кроме того, существует объединяющий алгоритм, который принимает доли подписей и выводит фактическую подпись .

Неподдельность. Мы определяем значение как:

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

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

Таблица 5. Пороговые подписи для пороговых хэш доказательств
Пороговая схема подписей
Этап разделения долей Для входного параметра безопасности и порога , дилер генерирует , запускается и задается вместо . Пользователю с идентификатором передается доля .
Этап вычисления подписей Для входного сообщения , вычисляется и публикуется фрагмент подписи . Для заданных подписей c фрагментами , подпись задается как .
Проверка подписей Для входного ключа , сообщения и подписи , проверка, если .
TemplateTheoremIcon.svg Теорема Теорема 2
Если является односторонним отношением, допускающим пороговые извлекающие хэш доказательства, тогда пороговая подпись, показанная на рисунке 5 экзистенциально неподдельна в моделе со случайными алгоритмами. Более того, если хэш доказательство открыто проверяемо, тогда схемы подписей являются надежными.
Доказательство
Для заданного противника , нападающего на пороговую схему подписей, мы создаем , разрушающего односторонность для следующим образом: для входа :
  • Запускается
  • Запускается чтобы получить
  • Выводится

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

Схемы с отзывом

Мы определяем схему с отзывом:

  • (Этап разделения долей). Алгоритм генерирует открытые ключи и основной секретный ключ . Учитывая идентификаторы , алгоритм генерации долей вычисляет связанные ключи .
  • (Шифровка). Алгоритм Enc принимает и множество отозванных пользователей , создает , а именно случайный ключ вместе с зашифрованным текстом .
  • (Расшифровка). Алгоритм принимает для всех и выводит .

Семантическая безопасность. Мы определяем значение как:

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

TemplateTheoremIcon.svg Теорема Теорема 2
Если является односторонним отношением, допускающим пороговые извлекающие хэш доказательства, то передача , показанная на рисунке 6, будет ), безопасной.
Доказательство
Для противника , прерывающего передачу, мы создаем , нарушающего псевдослучайность следующим образом: для входа :
  • запускается
  • запускается , чтобы получить
  • задается .
  • выводится .

Легко увидеть, что .

Реализация для Диффи-Хелмановского отношения

Мы считаем, что множество групп простого порядка допускает билинейные отметки. Секретным параметром будет и открытый параметр имеет вид для случайных и . Мы рассматриваем Диффи – Хелмановское отношение

Отметим, что эффективно проверяемо путем вычисления создания пар. Связанный алгоритм выборки выбираем и выводим .

Таблица 6. Cхема с отзывом для пороговых хэш доказательств
PKE схемы с отзывом
Этап создания долей Для входного параметра безопасности и порогового отзыва , дилер генерирует , запускает и устанавливает открытый ключ как . Пользователь с идентификатором задает ключ .
Расшифровка Для того, чтобы отозвать пользователей , алгоритм отбирает , вычисляет для и возвращает .
Зашифровка Любой пользовательский идентификатор в отозванном множестве расшифровывает шифротекст следующим образом: вычисляется и выводится .

Жесткие биты. Далее, мы объясняем как получить жесткие биты для под разными предположениями.

  • CDH предположение[36] утверждает, что вычисление для трудно; здесь мы можем выделить отдельный бит , используя .
  • Билинейное предположение [7] утверждает, что будет псевдослучайно для , где являются случайными элементами билинейной группы. Под предположением, мы можем извлекать линейные значения битов из с помощью:
где теперь задается как . Кроме того, мы можем повысить эффективность за счет предварительного вычисления пар и задания в качестве и вычисления . Это построение естественно продолжается до предположения[37].

Пороговая схема доказательств. Зафиксируем параметры  ; что также фиксирует группы простых чисел порядка . Пространства маркеров задается как .

  • (Генерация ключей). Выбирается и задается множество .
  • задается (PP, SP, 1t) и возвращается и
  • возвращает .
  • (Открытая/секретная оценка). задается через , где .
  • возвращает .
  • возвращает .
  • ( - извлечения). Учитывая , мы имеем , и кроме того, мы можем записать , где являются лагранжевыми коэффициентами, которые могут быть эффективно вычисленными для заданных . Это означает, что .
  • возвращает .
  • ( моделирование). Выбирается . Это однозначно определяет такую степень для многочлена , что для всех . Более того, задаются решением следующей линейной системы:
В частности, каждый из может быть записан в виде линейной комбинации (где коэффициенты эффективно вычислимы для заданных ) и поэтому каждый из может быть записан в виде произведения в соответствующих степенях.
  • возвращает , вычисленные как описано выше и .

Замечание 1. Вместо того, чтобы задавать , можно также установить . Открытые оценки и -моделирование затем осуществляется через лагранжевы интерполяции в экспоненте.

Открытая проверяемость. Для заданных проверяется, чтобы соответствовало проверке в качестве действительного набора. Учитывая и , мы можем вычислить , используя . Это приводит к открытой проверяемости в билинейных группах. Для общих групп, которые не допускают подобных пар, мы можем реализовать открытую проверяемость в моделе со случайными алгоритмами [[13], раздел 4.3] (также [8]). То есть, мы добавляем к такие неинтерактивные доказательства с нулевым разглашением, что является действительным набором. Такие доказательства получаются путем применения эвристического -протокола Шамира для действительных наборов [38]; обоснованность алгоритма проверки непосредственно следует из обоснованности -протокола. Обработка открытых и секретных оценок требует большей осторожности, и мы действуем по-разному в зависимости от приложения:

  • в применении к пороговым криптосистемам, мы создаем такое исполнение протокола Чаума-Педерсена, что существует эффективное доказательство для заданной в качестве свидетеля. Это гарантирует эффективность секретных оценок. Для открытых оценок, мы полагаемся на моделирование с нулевым разглашением, которое, в свою очередь, требует наличия случайных алгоритмов. Это не является проблемой, так как мы полагаться только на открытые оценки в доказательствах безопасности.
  • при работе с отзывающими криптосистемами, мы создаем такой протокол Чаума-Педерсена, что существует эффективное доказательство для в качестве свидетеля. Это гарантирует эффективную открытую оценку. Для частных оценок, мы полагаемся на моделирование с нулевым разглашением, что опять-таки требует случайных алгоритмов. Это не проблема, поскольку в алгоритме расшифровки, игнорирует неинтерактивные доказательства с нулевым разглашением.

Реализации для сложной факторизации

Фиксируем целое число для безопасных простых чисел (такое, что и для простых , ). Следуя [39], мы работаем c группой квадратичных вычетов, заданой фактором . . является группой порядка и эффективно узнаваемой (по проверке того, что символом Якоби будет ). Кроме того, отображение является перестановкой для . Также, при условии, что факторизация сложна в среднем, и, что безопасные простые числа уплотнены, множество перестановок (проиндексированных по ), действующих на группы , является односторонним. В наших построениях, открытый параметра состоит из , где является случайным -битным целым и выбирается равномерно из от . Мы будем в дальнейшем считать, что это генератор для , который реализуется с вероятностью . Для подписей, мы рассмотрим соотношение

Для шифрования, рассмотрим соотношение:

Здесь мы сосредоточимся на последнем соотношении. Связанный алгоритм выбирает случайное и выводит . Обратим внимание, что выходное распределение является статистически близким к равномерному для всякий раз, когда является генератором. Использовуя Блюм-Блюм-Шуб (BBS) псевдослучайный генератор[40], мы можем извлекать k биты из s, которые будут псевдослучайными, даже при u,а именно:


Основная идея. Следующее утверждение показывает, что мы можем сделать разделение секрета по Шамиру для составных модулей: Утверждение (подразумевается в [40]). Зафиксируем два простых числа . Для любого и различных значений в , отметка где определяет превращение в .


Доказательство (краткое). Инъективность для следует из того, что любой многочлен степени для , равен нулю при ; различные значения должны быть тождественны по модулю и и равны по модулю (по китайской теореме об остатках). Сюръективность следует из Лагранжевого приближения (так как все парные разности взаимны с ).


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

  • (Генерация ключей). Выбираем и задаем . Кроме того, выбираем .
  • возвращает и
  • возвращает
  • (Открытая/Частная оценка). Для задается через , где
  • возвращает .
  • возвращает .
  • ((t+1)-извлечение). Для заданных мы можем эффективно вычислять такие дробные коэффициенты лагранжа ,что , . Кроме того, мы можем вычислить
Мы делаем следующие выводы: (1) будут все целые числа, такие, что мы можем вычислить (2) пусть будет наибольшей степенью для 2, которая делит , и мы имеем (так как ) и (3) для заданных и , мы можем эффективно восстановить с использованием алгоритма Шамира [39], так как .
  • возвращается , как рассчитано выше.
  • (t-моделирование). Выбираем , что статистически близко к . Этот выбор однозначно определяет степень такого многочлена , что Кроме того, берутся из решений для следующей системы:
Пусть (определитель матрицы Вандермонда слева). Затем, мы можем эффективно вычислить целые числа (с учетом и ) без вычисления модульной инверсии.
  • выбирает и возвращает и

Открытая проверяемость. Следуя [[8], раздел 4], достаточно будет построить -протокол для -множеств в , который выглядит как . Честный отправитель имеет свидетеля так, что принимает и посылает . Задача для относится к варианту . Анализ полностью аналогичен работе [28].

Избирательная безопасность шифротекста

CCA передача

В этом разделе мы построим отзывающие схемы, защищенные от CCA атак.

Открытая проверка, подписи и случайные алгоритмы. Как уже говорилось, строительство также требует открытой проверяемости и одноразовой схемы подписей. Для факторизованного исполнения Диффи-Хеллмана в общих группах, мы полагаемся на случайный алгоритм, чтобы провести открытые проверки, таким образом мы можем также полагаться на случайный алгоритм для построения эффективной схемы подписей. Для Диффи-Хеллмана в билинейных группах (которые удовлетворяют открытой проверяемости без случайных алгоритмов), мы можем избежать использования сигнатур и вместо этого использовать TC – шифротекст, заданный , где и , и, таким образом, мы получаем эффективное построение без случайных алгоритмов.

Таблица 7. CCA-безопасная схема с отзывом для порогового хэш доказательства
PKE схемы с отзывом
Этап распределения долей Для входного параметра безопасности порогового отзыва , дилер генерирует , запускает и устанавливает открытый ключ как . Пользователю с идентификатором передается ключ
дается ключ .
Шифровка Для того чтобы извлечь пользователей , примяется :
  1. генерируется проверка для односторонней схемы подписей;
  2. отбирается  ;
  3. вычисляется и для  ;
  4. вычисляется подпись для ;
  5. выводится .
Расшифровка Любой пользователь не из отобранного множества может расшифровать шифротекст следующим образом:
  1. проверяются доказательства и подпись σ; выводится ⊥, если одна из проверок не выполняется;
  2. вычисляется и выводится .
TemplateTheoremIcon.svg Теорема Теорема 4
Если является односторонним отношением, допускающим пороговое извлекающие хэш доказательства с открытой провераяемостью, тогда приведенная выше схема будет безопасной.
Доказательство
Мы записываем , чтобы обозначить задачи шифротекста и ключи, выбранные в эксперименте, и мы задаем для обозначения ключа проверки, используемого при расчете . Мы работаем, как для последовательности игр. Мы начинаем с игры 0 (Game 0), где претендент действует как в стандартной игре (то есть отвечает за реальный ключ и является случайным ключом) и заканчиваем игрой, в которой выбираются случайно и равномерно. Затем, мы покажем, что все игры неотличимы в предположении, что псевдослучайна, даже при заданном .

Game 1: устранение столкновений. Мы заменяем механизм на , который выводит для таких входов , , но в противном случае работает . Мы показываем, что Game 0 и 1 являются вычислительно неразличимыми, когда и согласуются со всеми входами. Это легко следует из безопасности односторонней подписи.

Game 2: Раскрытие с . Мы модифицируем эксперимент из Game 1, генерируем ключи, используя , и мы заменяем на  :

Для входных  :
  • Если , возвращается .
  • Если или любая из не выполняется, возвращается .
  • Вычисляется и выводится .

Здесь мы используем тот факт, что в и мы исполняем для действительных доказательств и, следовательно, выводится правильный свидетель .

Game 3: Раскрытие с . Мы вычисляем все доказательства в , используя вместо и подписываемся, используя секретный ключ, соответствующий .

Game 4: Замещение . Мы генерируем наугад из вместо использования (Напомним, что ). В Game 3, мы никогда не используем знания о свидетеле или случайности , связанной с . Как следует из псевдослучайности , Game 3 и 4 вычислительно неразличимы. В частности, мы можем превратить любого противника для Game 3 и 4 в противника и . Отметим в заключение, что в Game 4, и одинаково распределены, так что вероятность в точности равна ½.

Пороговые CCA схемы

В этом разделе мы построим пороговую схему шифрования, безопасную для CCA атак. Основная техническая трудность заключается в следующем: симулятор знает и должен смочь вычислить для любых . Это делается для моделирования и доли дешифрования некоторых пользователей . Чтобы справиться с этим, мы изменили нашу основную пороговую схему шифрования в трех направлениях:

  • Первая модификация заключается в добавлении к шифротекстам, содержащим исполнение u, открыто проверяемого, порогового, извлекающего хэш доказательства, или, «все, кроме одного» извлекающего хэш доказательства, в терминологии [22], для отношения . Для этого мы должны обратиться к парам или моделе со случайными алгоритмами. (Подобные вопросы возникают и в предыдущих дискретно логарифмических схемах, основанных не на парах). Таким образом, симулятор будет иметь возможность восстановить значений для любого правильно сформированного шифротекста.
  • Далее, с помощью интерполяций, мы можем восстановить , где это фактор, использованный, чтобы убрать дробные лагранжевы коэффициенты. В дискретно логарифмическом случае мы можем вычислить и таким образом восстановить . В факторизующем исполнении мы заменим хэш-функцию на  ; мы можем поддерживать только фиксированное пространство идентичности, так как нам необходимо вычислить заранее. Точно так же мы должны изменить так, чтобы он вычислял с помощью лагранжевых приближений, а для и через алгоритм Шамира.
  • Наконец, мы изменяем , так что он будет выводить только долю расшифровки, если пороговые хэш доказательства работают должным образом.

Детали приводяться в полной версии данной статьи.

Благодарности

Я хотел бы поблагодарить Дэна Боне, Марио Сегеди и Моти Юнга за полезные дискуссии. Я также очень благодарен анонимным рецензентам за подробную и конструктивную обратную связь. Взгляды и выводы, содержащиеся в настоящем документе принадлежат автору и применяются для нужд научно-исследовательской лаборатории правительства и армии США, Министерства обороны Великобритании и правительства Великобритании.

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

  1. Queens College, CUNY, E-mail: hoeteck@cs.qc.cuny.edu

Примечание

Литература

  1. Desmedt, Y.: Society and group oriented cryptography: A new concept. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 120–127. Springer, Heidelberg (1988)
  2. Desmedt, Y., Frankel, Y.: Threshold cryptosystems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 307–315. Springer, Heidelberg (1990)
  3. Desmedt, Y., Frankel, Y.: Shared generation of authenticators and signatures (extended abstract). In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 457–469. Springer, Heidelberg (1992)
  4. 4,0 4,1 De Santis, A., Desmedt, Y., Frankel, Y., Yung, M.: How to share a function securely. In: STOC, pp. 522–533 (1994)
  5. 5,0 5,1 Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Robust threshold DSS signatures. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 354–371. Springer, Heidelberg (1996)
  6. 6,0 6,1 6,2 Shoup, V.: Practical threshold signatures. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 207–220. Springer, Heidelberg (2000)
  7. Frankel, Y., Gemmell, P., Yung, M.: Witness-based cryptographic program checking and robust function sharing. In: STOC, pp. 499–508 (1996)
  8. 8,0 8,1 8,2 8,3 8,4 Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Robust and efficient sharing of RSA functions. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 157–172. Springer, Heidelberg (1996)
  9. Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Secure distributed key generation for discrete-log based cryptosystems. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 295–310. Springer, Heidelberg (1999)
  10. 10,0 10,1 10,2 10,3 Boneh, D., Lynn, B., Shacham, H.: Short signatures from the weil pairing. J. Cryptology 17(4), 297–319 (2004)
  11. 11,0 11,1 11,2 11,3 11,4 11,5 Katz, J., Yung, M.: Threshold cryptosystems based on factoring. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 192–205. Springer, Heidelberg (2002)
  12. 12,0 12,1 12,2 12,3 Gennaro, R., Halevi, S., Krawczyk, H., Rabin, T.: Threshold RSA for dynamic and ad-hoc groups. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 88–107. Springer, Heidelberg (2008)
  13. 13,0 13,1 13,2 13,3 Shoup,V.,Gennaro,R.:Securingthresholdcryptosystemsagainstchosenciphertextattack. J. Cryptology 15(2), 75–96 (2002)
  14. 14,0 14,1 Canetti, R., Goldwasser, S.: An efficient threshold public key cryptosystem secure against adaptive chosen ciphertext attack. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 90–106. Springer, Heidelberg (1999)
  15. 15,0 15,1 15,2 15,3 15,4 Fouque, P.-A., Pointcheval, D.: Threshold cryptosystems secure against chosen-ciphertext attacks. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 351–368. Springer, Heidelberg (2001)
  16. 16,0 16,1 16,2 Boneh,D.,Boyen,X.,Halevi,S.:Chosenciphertextsecurepublickeythresholdencryption without random oracles. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 226– 243. Springer, Heidelberg (2006)
  17. 17,0 17,1 17,2 17,3 Boyen, X., Mei, Q., Waters, B.: Direct chosen ciphertext security from identity-based techniques. In: ACM CCS, pp. 320–329 (2005)
  18. Fiat, A., Naor, M.: Broadcast encryption. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 480–491. Springer, Heidelberg (1994)
  19. 19,0 19,1 19,2 Hofheinz, D., Kiltz, E.: Practical chosen ciphertext secure encryption from factoring. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 313–332. Springer, Heidelberg (2009)
  20. 20,0 20,1 20,2 20,3 Naor, M., Pinkas, B.: Efficient trace and revoke schemes. In: Frankel, Y. (ed.) FC 2000. LNCS, vol. 1962, pp. 1–20. Springer, Heidelberg (2001)
  21. Fouque,P.-A.,Poupard,G.,Stern,J.:Sharingdecryptioninthecontextofvotingorlotteries. In: Frankel, Y. (ed.) FC 2000. LNCS, vol. 1962, pp. 90–104. Springer, Heidelberg (2001)
  22. 22,0 22,1 22,2 22,3 22,4 Wee,H.:Efficientchosen-ciphertextsecurityviaextractablehashproofs.In:Rabin,T.(ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 314–332. Springer, Heidelberg (2010)
  23. 23,0 23,1 Cramer, R., Shoup, V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 45–64. Springer, Heidelberg (2002)
  24. Blum,M.,Feldman,P.,Micali,S.:Non-interactivezero-knowledgeanditsapplications.In: STOC, pp. 103–112 (1988)
  25. Rackoff, C., Simon, D.R.: Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 433–444. Springer, Heidelberg (1992)
  26. De Santis, A., Persiano, G.: Zero-knowledge proofs of knowledge without interaction. In: FOCS, pp. 427–436 (1992)
  27. Canetti,R.,Halevi,S.,Katz,J.:Chosen-ciphertextsecurityfromidentity-basedencryption. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 207–222. Springer, Heidelberg (2004)
  28. 28,0 28,1 28,2 Dodis, Y., Fazio, N.: Public key trace and revoke scheme secure against adaptive chosen ciphertext attack. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 100–115. Springer, Heidelberg (2002)
  29. Cramer,R.,Shoup,V.:Apracticalpublickeycryptosystemprovablysecureagainstadaptive chosen ciphertext attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 13– 25. Springer, Heidelberg (1998)
  30. Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: STOC, pp. 427–437 (1990)
  31. Shamir, A.: On the generation of cryptographically strong pseudorandom sequences. ACM Trans. Comput. Syst. 1(1), 38–44 (1983)
  32. Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 553–572. Springer, Heidelberg (2010)
  33. 33,0 33,1 Bendlin, R., Damga ̊rd, I.: Threshold decryption and zero-knowledge proofs for lattice- based cryptosystems. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 201–218. Springer, Heidelberg (2010)
  34. Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: STOC, pp. 25–32 (1989)
  35. Damga ̊rd,I.,Jurik,M.:Ageneralisation,asimplificationandsomeapplicationsofPaillier’s probabilistic public-key system. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119– 136. Springer, Heidelberg (2001)
  36. Abdalla, M., Bellare, M., Rogaway, P.: The oracle diffie-hellman assumptions and an analysis of DHIES. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 143–158. Springer, Heidelberg (2001)
  37. Kiltz, E.: Chosen-ciphertext secure key-encapsulation based on gap hashed diffie-hellman. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 282–297. Springer, Heidelberg (2007)
  38. Chaum, D., Pedersen, T.P.: Wallet databases with observers. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 89–105. Springer, Heidelberg (1993)
  39. Hofheinz,D.,Kiltz,E.:Thegroupofsignedquadraticresiduesandapplications.In:Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 637–653. Springer, Heidelberg (2009)
  40. Blum, L., Blum, M., Shub, M.: Comparison of two pseudo-random number generators. In: CRYPTO 1982, pp. 61–78 (1982)