Дальнейший обзор Оптимистичных протоколов доверенного обмена в многопользовательской системе

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 10:08, 24 декабря 2015.
Further Observations on Optimistic Fair Exchange Protocols in the Multi-user Setting
Multi-query Computationally-Private Information Retrieval with Constant Communication Rate.PNG
Авторы Jens Groth[@: 1],
Aggelos Kiayias[@: 2],
Helger Lipmaa[@: 3][@: 4]
Опубликован 2010 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Содержание

Аннотация

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

Введение

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

Оптимистический доверенный обмен(также известный как доверенный обмен оффлайн) был предложен Асоканом и др. [1] Протокол оптимистического доверенного обмена также нуждается в наличие третьей стороны называемой «арбитром», которой нет необходимости всё время быть онлайн. Вместо этого вступает только когда что-либо идёт не так (например, один из участников пытается воспользоваться ошибкой вызванной у другого). В протоколе оптимистического доверенного обмена участвуют три стороны, а именно, подписывающий, проверяющий и арбитр. Подписывающий (скажем, Алиса) сперва передаёт проверяемую «частичную подпись» проверяющему (скажем, Бобу). Боб проверяет корректность и заполняет соответствующие значения если корректна. После этого, Алиса отправляет Бобу «целую подпись» для завершения транзакции. Т.о. если не возникло никаких проблем, арбитр не принимает участия в обмене. Однако, если Боб не получил полную подпись от Алисы, он может отправить (и доказательство заполнения его соответствующих значений) арбитру, который преобразует в для Боба.

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

Предыдущие работы

Доверенный обмен изучался интенсивно с момента его определения в качестве фундаментальной задачи для безопасности электронных транзакций и цифрового управления правами. Известно, что оптимистический доверенный обмен можно построить (в общем виде) используя конструкцию «двух подписей» [4], проверяемую зашифрованную подпись [[5],[6],[7],[8],[9],[10],[11]], и последовательную двухстороннюю подпись (впервые предложенную Парком и др. [12], и затем пересмотренную заново Додисом и Рейзином [4]), OR-доказательства [3], стандартную подпись и кольцевую подпись [13]. Далее представим вам краткий обзор некоторых результатов, которые имеют прямое отношение к нашей работе.

Оптимистический доверенный обмен в однопользовательском варианте

В протоколе оптимистического доверенного обмена будет всего три стороны, подписывающий(щие), проверяющий(щие) и арбитр(ы). Большинство работе по оптимистическому доверенному обмену рассматривались только в однопользовательском варианте, а именно там был только один подписывающий. Первая безопасная модель оптимистического доверенного обмена была представлена в [[5],[6]]. Додис и Рейзин [4] определили более общую и унифицированную модель для не интерактивного оптимистического доверенного обмена, с помощью представления нового криптографического примитива названного проверяемая связанная подпись. В [4] безопасность схемы проверяемой связанной подписи (эквивалентной протоколу оптимистического доверенного обмена) для однопользовательского варианта состояла из трёх аспектов: безопасность от сторонних действий подписывающего, безопасность от сторонних действий проверяющего и безопасность от сторонних действий арбитра. Т.к. арбитр не полностью доверенный, предполагается, что он полудоверенный в том смысле, что арбитр не вступает в сговор ни с подписывающим ни с проверяющим. В дальнейшей части работы если утверждается, что протокол оптимистического доверенного обмена является безопасным в однопользовательском варианте то это означает, что он является таковым как определено в [4]. Отметим, что их определение не включает в себя все понятия оптимистического доверенного обмена (например, злоупотребление свободой действий [14], безотказность [[15],[16]], своевременное завершение работы [[5],[6]] и неоднозначность подписывающего [17]), но это никак не повлияет на то, что мы реализуем посредством него в нашей работе. Додис и Рейзин [4] представили автономную, но с управляемой настройкой, схему проверяемой связанной подписи для промежуточной задачи Диффи-Хеллмана. Конструкции автономной проверяемой связанной подписи с управляемой настройкой представлены в [[18],[2]].

Оптимистический доверенный обмен в многопользовательском варианте

Недавно безопасность не интерактивного оптимистического доверенного обмена в многопользовательском варианте была независимо исследована в [3] и [19]. Оптимистический доверенный обмен в многопользовательском варианте соответствует сценарию, где два или более подписывающий в системе, но значениями обмениваются по прежнему всего два участника. Это отличается от многопользовательского обмена, который рассматривает обмен трёх или более участник.

В [3], Додис, Ли и Ям выявили, что в однопользовательском варианте безопасность оптимистического доверенного обмена не гарантирует безопасность в многопользовательском варианте. Они представили простой контрпример, который был безопасным в однопользовательском варианте, но небезопасным в многопользовательском варианте. Додис, Ли и Ям определили модель безопасности в многопользовательском варианте оптимистического доверенного обмена и показали обобщённую конструкцию со свободной настройкой оптимистического доверенного обмена безопасного в многопользовательском варианте [3]. Безопасность их конструкции основывалась на однонаправленных функциях в модели случайного оракула и лазейке однонаправленных перестановок в стандартной модели. Анализ из [3] показал, что два известных метода оптимистического доверенного обмена (а именно, конструкции основанные на проверяемой связанной подписи и последовательных двухсторонних подписях) остаются безопасными в многопользовательском варианте если соответствующие примитивы удовлетворяют некоторым понятиям безопасности. Независимо, Зу, Сусило и Му [19] также продемонстрировали схему проверяемой связанной подписи которая безопасна в модели определённой в [4], но небезопасна в многопользовательском варианте. Они определили понятия безопасности проверяемой связанной подписи в многопользовательском варианте и предложили конкретную конструкцию многопользовательской безопасной автономной проверяемой связанной подписи со свободной настройкой [19]. Не интерактивная версия их схемы использует методику Фиата-Шамира и требует наличия хэш функции, которая рассматривается как случайный оракул при анализе безопасности. Согласно [3], многопользовательские безопасные автономные протоколы оптимистического доверенного обмена со свободной настройкой без случайных оракулов можно построить из схем проверяемой связанной подписи без случайных оракулов [[9],[10],[11]].

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

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

Хуанг и др. [[13]] представили другую обобщённую конструкцию для оптимистического доверенного обмена. Их конструкция приводит к эффективным протоколам оптимистического доверенного обмена со свободной настройкой безопасным в стандартной модели и модели выбранного ключа. Сравнительно недавно, был показан первый эффективный неопределённый протокол оптимистического доверенного обмена [17]. Этот новый протокол реализовывался с доказанной безопасностью в многопользовательском варианте и модели выбранного ключа без использования предположения случайного оракула. Без всякого сомнения более приемлемо если криптографические протоколы можно сделат доказуемо безопасными в модели выбранного ключа. Однако, в данной работе, безопасность оптимистического доверенного обмена рассматривается в модели сертифицированного ключа (как определено в [3]), т.к. модель сертифицированного ключа приемлема и широко используется в исследовательских работах по криптографии с открытым ключом. В дальнейшем, если мы говорим, что протокол оптимистического доверенного обмена является многопользовательским безопасным, это значит что данный протокол является безопасным в многопользовательском варианте как это определено в [3] (где рассматривается модель сертифицированного ключа).

Мотивация

Данное исследование оптимистического доверенного обмена показало, что:

  • Однопользовательская безопасность оптимистического доверенного обмена не гарантирует многопользовательскую безопасность [[3],[19]].
  • Не все однопользовательские безопасные протоколы оптимистического доверенного обмена будут небезопасны в многопользовательском варианте [3]. Некоторые однопользовательские безопасные протоколы доказуемо безопасны в многопользовательском варианте [3].

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

Наш вклад

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

  1. В разделе 3, представлено и определено свойство оптимистического доверенного обмена, которое мы называем стойким решением неопределённости. Если вкратце, то протокол оптимистического доверенного обмена обладает свойством стойкого решения неопределённости есть он может преобразовать частичную подпись в полную подпись используя секретный ключ подписывающего или секретный ключ арбитра; отметим, что для такой заданной пары , невозможно сказать какой именно ключ участвует в преобразовании. Т.к. существуют некоторые протоколы оптимистического доверенного обмена удовлетворяющие стойкому решению неопределённости, впервые это понятие может быть связанно и формально определено.
  2. Для протокола оптимистического доверенного обмена со стойким решением неопределённости, доказано, что его безопасность в однопользовательском варианте сохраняется в многопользовательском варианте. Точнее говоря, мы показали, что: (1) безопасность от действий подписывающего и безопасность от действий проверяющего в однопользовательском варианте сохраняются в многопользовательском варианте для протоколов оптимистического доверенного обмена со стойким решением неопределённости, и (2) безопасность от действий арбитра в однопользовательском варианте сохраняется в многопользовательском варианте (для протоколов оптимистического доверенного обмена с и без стойкого решения неопределённости).

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

3. В Разделе 4 показывается новая конструкция оптимистического доверенного обмена со стойким решением неопределённости. Наша конструкция является вариантом протокола оптимистического доверенного обмена для схемы проверяемой связанной подписи предложенной в [9]. Протокол в [9] обладает несколькими требуемыми свойствами, например, он со свободной настройкой, автономный и многопользовательской безопасностью без использования случайных оракулов при вычислительном предположении Диффи-Хеллмана. Наш протокол обладает теми же свойствами и является более эффективным в плане генерации, передачи и проверки частичных подписей. Это однако достигается за счёт затрат на больший раз.

Определения оптимистического доверенного обмена в многопользовательском варианте

Этот раздел посвящён синтаксису и определениям безопасности оптимистического доверенного обмена в многопользовательском варианте [3].

Синтаксис оптимистического доверенного обмена

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

  • . Арбитр устанавливает алгоритм принимающий в качестве входа параметр и выводящий секретный переменный ключ и открытый частичный ключ проверки .
  • . Пользователь устанавливает алгоритм принимающий в качестве входа и (опционально) , и выдающий на выходе частный ключ подписи и открытый ключ проверки .
  • и . Они аналогичны алгоритмам подписания и проверки в исходной схеме цифровой подписи.
    • Алгоритм подписания выполняемый подписывающий , принимает на входе и выводит подпись для сообщения m. В протоколах доверенного обмена подписи генерируемые называются полными подписями.
    • Алгоритм проверки , выполняемый проверяющим, принимает на входе и возвращает или . Подпись является корректной полной подписью m при если .
  • и . Существуют алгоритмы частичной подписи и проверки, где вместе с (который впоследствии будет определён) функционально эквивалентны .
    • Алгоритм частичного подписания выполняемый подписывающий , принимает на входе и выдаёт подпись ’ для m. Разделение по признакам этих полученных с помощью подписей обобщённых называют частичной подписью.
    • Алгоритм частичной проверки, выполняемый проверяющим, принимает на входе и возвращает или . Подпись ’ будет корректной частичной подписью m при если .
  • . Разрешающий алгоритм принимает на входе корректную частичную подпись ’ для m при и секретный переменный ключ ASK , и выдаёт подпись . Этот алгоритм выполняется арбитром для участника , который не получил полную подпись от , но оперирует корректной частичной подписью и доказательством, что он/она заполнил(а) соответствующие значения .

Корректность. Если каждая подпись генерируется соответственно протокольной спецификации, то должны быть пройдены соответствующие алгоритмы проверки. А именно,

Стойкое решение неопределённости [[3],[4],[13],[15],[19]]. Любая «разрешимая» подпись является (хотя бы вычислительно) неразличимой по признакам от «действительной подписи» .

Безопасность оптимистического доверенного обмена. Интуитивно понятно, что доверенность обмена требует от двух участников доверенного обмена их результатами т.о., чтобы ни один из них не получил лишнего значения другого участника. Это требование включает в себя безопасность от действий подписывающего (s), безопасность от действий проверяющего (s) и безопасность от действий арбитра, которые определяются с помощью игры между злоумышленником и управляющим. В процессе игры, управляющий компонует три изначально пустых списка: (1) PK-список содержащий открытые ключи создаваемые пользователями; (2) PartialSign-список содержащий запросы для частичной подписи осуществляемые злоумышленником; и (3) Resolve-список содержащий решающие запросы сделанные злоумышленником.

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

Безопасность от действий подписывающего(щих)

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

  • Установка. Управляющий генерирует параметр Param и ключевую пару арбитра выполняя . Злоумышленнику дан и .
  • Запросы. Выполняя всё адаптивно, реализует следующие запросы.
  1. Создание запросов пользователя. Для того, чтобы принудить управляющего принять (т.е. добавить в РК-список), необходимо доказать его знание законного ключа . Это можно осуществить с помощью оперирования злоумышленником над секретным ключом, представленного в [9], либо генерации доказательства знания [4] данного секретного ключа.
  2. Решающие запросы. Для решающего запроса удовлетворяющего управляющий сперва просматривает РК-список. Если PK PK-списку, символ ошибки « T » будет возвращён злоумышленнику. В противном случае, управляющий добавляет (m, PK) в Resolve-список (если этой пары там нет) и соотносит его с выходом
  • Выход. Получаем, что выводит тройку и выигрывает в игре если PK-списку, и

Пусть будет вероятностью того, что выигрывает данную вышеуказанную игру, реализуемой для алгоритма подбрасывания монетки и управляющим. Говорится, что злоумышленник -взламывает безопасность подписывающего(щих) если за время t, делает не более запросов создаваемых пользователем, решающих запросов а будет не менее е.

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

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

Безопасность от действий проверяющего(щих)

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

Первое требование выполняется путём безопасности от действий арбитра, а именно, даже арбитр не может реализовать эту атаку. Это будет кратно определено в Разделе 2.4. Второе требование определяется так как показано ниже.

  • Установка. Управляющий генерирует параметр Param и ключевую пару арбитра выполняя . Управляющий также генерирует ключевую пару выполняя , и добавляет в РК-список. Злоумышленнику даются и Param.
  • Запросы. Выполняя всё адаптивно, реализует все запросы из раздела 2.2 запросы частичной подписи определённые ниже. Запросы частичной подписи. На запрос частичной подписи управляющий отвечает . После чего, добавляется в PartilSign-список.
  • Выход: В выводит пару и выигрывает игру если Resolve-списку и

Пусть будет вероятностью того, что выигрывает данную вышеуказанную игру, реализуемой для алгоритма подбрасывания монетки и управляющим. Говорится, что злоумышленник -взламывает безопасность проверяющего(щих) если за время t, делает не более запросов создаваемых пользователем, запросов частичной подписи решающих запросов а будет не менее е.

TemplateDifinitionIcon.svg Определение «Определение 2 - Безопасность от действий проверяющего(щих)»
Протокол оптимистического доверенного обмена будет -безопасным от действий подписывающего(щих) если нет такого злоумышленника который взломает его.

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

Безопасность от действий арбитра(ов)

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

Безопасность от действий арбитра требует, чтобы арбитр, без частичной подписи сообщения m, не смог бы получить корректную полную подпись сообщения m. Это понятие определяется следующим образом.

  • Установка. Управляющий генерирует параметр Param , который даётся злоумышленнику .
  • Выход-1. генерирует открытый ключ арбитра ARK и отправляет его управляющему. В ответ, управляющий генерирует ключевую пару выполняя и добавляет в РК-список. Злоумышленнику дан .
  • Запросы. Выполняя всё адаптивно, реализует запросы создаваемые пользователем (определённые в разделе 2.2) и запросы частичной подписи (определённые в разделе 2.3).
  • Выход-2. выводит пару и выигрывает игру если PartialSign-списку и .

Пусть будет вероятностью того, что выигрывает данную вышеуказанную игру, реализуемой для алгоритма подбрасывания монетки и управляющим. Говорится, что злоумышленник -взламывает безопасность арбитра(ов) если за время t, делает не более запросов создаваемых пользователем, запросов частичной подписи а будет не менее е.

Замечание 1. В данной игре злоумышленник должен сперва сгенерировать открытый ключ арбитра APK перед получением или сделать другие запросы. Это повлияет на определение оптимистического доверенного обмена в том плане, что APK может быть входом алгоритма и Psig. Для конкретных протоколов где этим алгоритмам не требуется АРК в качестве входа, злоумышленник получает и/или реализует запросы частичной подписи перед генерацией АРК.

TemplateDifinitionIcon.svg Определение «Определение 3- Безопасность от действий арбитра»
Протокол оптимистического доверенного обмена будет -безопасным от действий арбитра(ов) если нет такого злоумышленника , который взломает его.

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

TemplateTheoremIcon.svg Теорема Теорема 1.
Протокол оптимистического доверенного обмена будет -безопасным от действий арбитра в многопользовательском варианте если он -безопасен от действий арбитра в однопользовательском варианте. Здесь обозначает время до ответа на один запрос создаваемый пользователем.
Доказательство
Доказательство. Обозначим за злоумышленника в однопользовательском варианте и в многопользовательском варианте. Теперь покажем, как преобразовать реализуемый в реализуемый . Сперва получает от управляющего в однопользовательском варианте.
  • Установка. даётся .
  • Выход-1. Пусть APK будет открытым ключом арбитра создаваемым в многопользовательском варианте. APK отправляют управляющему в однопользовательском варианте. использует для генерации доказательства знания, а именно выступает в роли основы для доказательства что все следующие сообщения будут от управляющего к (или наоборот). В конце данной фазы, будет дан открытый ключ , который соответствует полученному открытому ключу в многопользовательском варианте.
  • Запросы. Мы показали, как может корректно отвечать на запросы .
  1. Запросы создаваемые пользователем. Для запроса создаваемого пользователем добавляет в РК-список если может генерировать доказательство знания законного секретного ключа.
  2. Запросы частичной подписи. Для запроса частичной подписи , предоставляет его своему управляющему и отправляет его ответ .
  • Выход-2. выводит пару . устанавливает в качестве его собственного выхода в однопользовательском варианте.

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

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

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


В Разделе 3 показываются условия при который безопасность подписывающий и проверяющий в однопользовательском варианте будут сохраняться в многопользовательском варианте.

Стойкое решение неопределённости

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

Оптимистический доверенный обмен для последовательного двухстороннего множественного подписания

Схемы с несколькими подписями позволяют любой подгруппе пользователей совместно подписывать документ так, чтобы проверяющий был уведомлён, что каждый пользователь подгруппы участвовал в подписании. Для построения протокола оптимистического доверенного обмена, можно использовать простой тип множественной подписи, который называют последовательной двухсторонней множественной подписью. В данной конструкции подписывающий сперва генерирует ключевые пары и (АРК,ASK), где отправляется арбитру по защищённому каналу. Секретный ключ подписывающего SK является парой , а секретный ключ арбитра будет ASK. Частичная подпись сообщения m будет обычной подписью генерируемой при помощи sk, а полная подпись будет мультиподписью генерируемой при помощи и ASK. Для заданной корректной частичной подписи, оба арбитр и подписывающий могут преобразовать её в полную подпись используя ASK. Т.о. виртуально невозможно сказать кто (подписывающий или арбитр) преобразовал каждую из частей подписи в полной подписи. Это естественное требование для оптимистического доверенного обмена со стойким решением неопределённости, который формально определён следующим образом.

Определение стойкого решения неопределённости

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

  • . Этот алгоритм принимает на входе секретный ключ подписывающего , (опционально) открытый ключ арбитра АРК, сообщение m и его корректную частичную подпись . Выводит полную подпись подписывающего для m.

В тривиальном случае, каждый протокол оптимистического доверенного обмена имеет алгоритм . Нашей целью здесь является определение не тривиального и сравнение его с решающим алгоритмом Res. Напомним, что со знанием ASK, можно также преобразовать частичную подпись в полную используя Res. Это делает актуальным следующий вопрос: Для заданной корректной частичной подписи , в чём будет заключатся разница между полными подписями получаемыми через и Ответ на данный вопрос заключается в стойком решение неопределённости.

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

В протоколе оптимистического доверенного обмена определённом как в Разделе 2, пусть (АРК,ASK) будут любой парой в , и пусть будут любой парой в . Для любой пары удовлетворяющей определим

 : вероятность распределения полной подписи предложенной

 : вероятность распределения полной подписи предложенной


TemplateDifinitionIcon.svg Определение «Определение 4 - Стойкое решение неопределённости»
Говорят, что протокол оптимистического доверенного обмена удовлетворяет стойкому решению неопределённости если существует алгоритм Convert определённый выше такой, что будет идентична .

Стойкое решение неопределённости и решение неопределённости: краткое сравнение. Протокол оптимистического доверенного обмена со стойким решением неопределённости удовлетворяет решению неопределённости если определяется как , а именно подписывающий сперва генерирует частичную подпись, а затем преобразовывает её в полную используя . В данном случае, действительные подписи (генерируемые) будут неразличимы по признакам от повторно вычисляемых подписей (генерируемых ). Однако, из решения неопределенности не следует стойкое решение неопределённости, которой требуется чтобы можно было использовать секретный ключ подписывающего для преобразования частичной подписи в полную и при этом чтобы данное преобразование было неразличимо по признакам от того, которое использует секретный ключ арбитра.

Протоколы оптимистического доверенного обмена с/без стойкого решения неопределённости

Очевидно, что общие конструкции оптимистического доверенного обмена при последовательной двухсторонней мультиподписи [4] (отмеченной в начале Раздела 3) обладают свойством стойкого решения неопределённости по определению Convert = Res. Ниже показаны некоторые другие конкретные примеры оптимистического доверенного обмена с/без стойкого решения неопределённости.

Оптимистический доверенный обмен при проверяемой связанной подписи

Пусть есть протоколы оптимистического доверенного обмена построенные для проверяемой связанной подписи. Если алгоритм будет детерминистическим (например, схема проверяемой связанной подписи в [8]), то обладает свойством стойкого решения неопределённости. Для любой корректной частичной подписи m, будет только один выход алгоритма , а именно уникальная полная подпись . По определению , и будут идентичны а протоколы будут удовлетворять стойкому решению неопределённости. с вероятностным алгоритмом могут также обладать свойством стойкого решения неопределённости. Одним из примеров может служить протокол оптимистического доверенного обмена для схемы проверяемой связанной подписи предложенный в [9]. В [9], алгоритм является алгоритмом подписания подписи [20] , а частичная подпись является шифрованием полной подписи использующим . После расширения из , арбитр рандомизирует т.о., что выходом будет полная подпись равномерно распределённая в пространстве полной подписи. Это выявляет распределение полных подписей производимых Res таким же как для полных подписей генерируемых .

Конкретный пример обобщённой конструкции в [13]

Обобщённая конструкция оптимистического доверенного обмена в [13] основывается на стандартной схеме подписи и схеме кольцевой подписи, которые можно построить эффективно без использования случайных оракулов. В даном протоколе, подписывающий и арбитр сперва генерируют их собственные пары ключей. Полная подпись сообщения m будет парой , где - это стандартная подпись подписывающего сообщения m, а кольцевая подпись m и . Либо у подписывающего либо у арбитра будет возможность сгенерировать . Эта конструкция удовлетворяет стойкому решению неопределённости если распределение кольцевых подписей генерируемых подписывающим будет таким же как распределение кольцевых подписей генерируемых арбитром.

Конкретный протокол без стойкого решения неопределённости

Одним из примеров протоколов оптимистического доверенного обмена без стойкого решения неопределённости будет однопользовательский безопасный и многопользовательский небезопасный протокол оптимистического доверенного обмена представленный в [3]. В данном протоколе, полная подпись сообщения m будет , где есть стандартная подпись подписывающего для ,а f это однонаправленная перестановка с лазейкой. Частичная подпись будет определяться как Для преобразования в полную подпись, арбитр использует его/её секретный ключ для вычисления и получения полной подписи . Для заданного сообщения m и его полной подписи трудно сказать был ли определён с помощью непосредственно или сперва сгенерирован а затем . Т.о. как показано в [3], свойство «решения неопределённости» удовлетворяется. С другой стороны, этот протокол не обладает стойким решением неопределённости т.к. f является однонаправленной перестановкой с лазейкой. Предположим, в противном случае, что существует алгоритм такой, что для частичной подписи , вывод имеет ту же вероятность распределения что и . Отметим, что для , будет выводить пару такую, что y = f(r). Из этого следует, что должен также выводить удовлетворяющую y = f(r) если протокол обладает стойким решением неопределённости. Это нарушает однонаправленность f, а именно, для заданного y, существует алгоритм Convert который может находить такое, что без использования лазейки .

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

Безопасные протоколы оптимистического доверенного обмена со стойким решением неопределённости

TemplateTheoremIcon.svg Теорема Теорема 1.
Показывает, что безопасность арбитра в однопользовательском варианте сохраняется в многопользовательском варианте. В этом разделе рассматриваются другие два понятия безопасности, и доказывается, что:
  1. Для протоколов оптимистического доверенного обмена со стойким решением неопределённости безопасность подписывающего в однопользовательском варианте сохраняется и в многопользовательском варианте (Теорема 2).
  2. Для протоколов оптимистического доверенного обмена со стойким решением неопределённости, безопасность проверяющего в однопользовательском варианте сохраняется в многопользовательском варианте (Теорема 3).
Доказательство
Без доказательства


TemplateTheoremIcon.svg Теорема Теорема 2.
Протокол оптимистического доверенного обмена со стойким решением неопределённости будет -безопасным для подписывающего в многопользовательском варианте, если он будет -безопасным для подписывающего в однопользовательском варианте. Здесь есть время зависящее от корректности доказательства знания, а - время зависящее от алгоритма в протоколе.
Доказательство
Доказательство. Обозначим за злоумышленника в однопользовательском варианте и за в многопользовательском варианте. В доказательстве используем стандартный метод показывая что для протокола оптимистического доверенного обмена со стойким решением неопределённости реализуемая может быть преобразована в реализуемую . Сперва дадим высокоуровневое описание доказательства.

выступает в роли управляющего для в доказательстве и отвечает на все запросы. устанавливает управляющий открытый ключ для в качестве его собственного управляющего открытого ключа, а выход - как свой собственный. Сложной частью доказательства будет определение того, как может корректно отвечать на решающие запросы от . Для решающих запросов отнесённых к может использовать управляющего для генерации корректных ответов. Однако, это не достижимо для решающих запросов при других открытых ключах. К счастью, на такие запросы можно корректно ответить с помощью если протокол оптимистического доверенного обмена обладает стойким решением неопределённости. Для решающего запроса может преобразовать до полной подписи используя алгоритм Convert и секретный ключ . Согласно Опр. 4, это симулирует действительную игру между и управляющим в многопользовательском варианте. Секретный ключ можно выявить с помощью относительно корректности доказательства знания необходимого на этапе создания пользовательских запросов.

Детальное доказательство показано в полной версии данной работы.


TemplateTheoremIcon.svg Теорема Теорема 3.
Протокол оптимистического доверенного обмена со стойким решением неопределённости является стойким против проверки при многопользовательских настройках, если он безопасен при проверке однопользовательских настроек. Здесь в то же время зависит от правильности знания и в то же время зависит от алгоритма в протоколе
Доказательство
Детали доказательства в полной версии статьи

Замечание 2. Наш анализ только показывает, что стойкое решение неопределённости является достаточным условием для однопользовательсной безопасности в протоколе обмена и остается безопасным при многопользовательских настройках. Это не необходимое требование для многопользователского протокола оптимистического доверенного обмена

Новый протокол оптимистического доверенного обмена со стойким решением неопределённости

В данном разделе представлен новый протокол оптимистического доверенного обмена со стойким решением неопределённости. Данный протокол основывается на подписи Уотерса [20] для билинейного отображения. Определения билинейного отображения и вычислительного предположения Диффи-Хеллмана можно найти в [20]

Предлагаемый протокол

Пусть будут билинейными группами простого порядка , и пусть будет генератором . обозначает билинейное отображение . Пусть n будет битовой длинной строки подписываемого сообщения. Для элемента m в , пусть будет множеством всех i для которых i-ый бит будет 1. Параметр Param будет .

  • . Для заданного , арбитр выбирает случайное число и вычисляет . Открытый ключ арбитра будет , а секретный ключ ASK будет .
  • . Для заданного , этот алгоритм выводит секретный подписывающий ключ и открытый ключ проверки , где
  1. и случайно выбираются в
  2. и , и
  3. есть вектор состоящий из элементов Все эти элементы будут случайно выбираться в .

Все эти элементы будут случайно выбираться в

  • Sig. Для заданного сообщения m, подписывающий использует секретный ключ для генерации подписи Уотерса , где и r является случайным числом из .
  • Ver. Для заданной пары сообщение-подпись и math> U_i\,\! </math -го открытого ключа <> , данный алгоритм выводит если . В противном случае алгоритм выводит .
  • Psig. Для заданного сообщения m и открытого ключа арбитра W, подписывающий сперва выполняет Sig для получения полной подписи . А затем, вычисляет и. Частичная подпись будет
  • PVer. Для заданной пары , -го открытого ключа и открытого ключа арбитра АРК (который будет W) компонуем как . Данный алгоритм выводит если . В противном случае он выводит .
  • Res. Для заданной корректной частичной подписи сообщения m при открытом ключе , арбитр сперва компонует как После этого арбитр использует секретный ключ w для вычисления и Затем арбитр выбирает случайное число math> r' \nable \mathbb{Z}_p \,\! </math> и вычисляет и . Выходом алгоритма Res будет.

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

Можно найти такой алгоритм Convert, который будет аналогом Sig, таким, что для заданной любой частичной подписи , выход Convert будет неразличим по признакам от выхода Res, а также оба будут равномерно распределены в пространстве корректной подписи для подписи Уотерса. Т.о. предложенный протокол также удовлетворяет решению неопределённости.

Следующая теорема показывает, что протокол безопасен в многопользовательском варианте.

TemplateTheoremIcon.svg Теорема Теорема 4.
Предложенный протокол будет многопользовательским и безопасным при вычислительном предположении Диффи-Хеллмана.
Доказательство
Детальное доказательство показано в полной версии данной работы.


Сравнение предыдущих протоколов

В Таблице 1 сравниваются известные протоколы оптимистического доверенного обмена, обладающие одинаковыми свойствами вместе с вновь предложенным (а именно, не интерактивность, свободная установка, автономность, и многопользовательская безопасность без использования случайных оракулов). Сравнения сделаны для следующих аспектов: (1) соответствующее предположение сложности, (2) размер частичной подписи и полной подписи, и (3) вычислительные затраты на подписание и проверку частичных и полных подписей. Мы рассматриваем затраты на подписание и проверку частичных подписей т.к. подписывающий должен сгенерировать частичную подпись при каждом обмене, которая будет проверена проверяющим и может быть также проверена арбитром.

Таблица 1. Многопользовательские безопасные автономные протоколы оптимистического доверенного обмена со свободной настройкой без случайных оракулов

Наш протокол [9] [10] [11]
Предположение сложности CDH CDH CT-CDH SDH
Полная подпись Уотерса [20] Уотерса [20] Уотерса [20] ВВ [21]
Размер подписи <
Затраты на подписание
Затраты на проверку 2ВМ + 1ВМ 3ВМ 2ВМ + 1ВМ 2ВМ + 4ВМ

Обозначения:

CDH: вычислительное предположение Диффи-Хеллмана

CT-CDH: предположение Диффи-Хеллмана о выбранном значении [22]

SDH: стойкое предположение Диффи-Хеллмана

 : длина бит элемента в ,  : длина бит элемента в

 : вычислительные затраты генерации одной подписи Уотерса [20]

 : вычислительные затраты генерации одной ВВ подписи [21]

 : возведение в степень в ,  : предварительно вычисляемое возведение в степень в

BM: билинейное отображение, ВМ: предварительно вычисляемое билинейное отображение.

Поэтому эффективность подписания и проверки частичных подписей не мене важна, чем для полных. В Таблице 1, наиболее эффективным является протокол построенный из схемы проверяемой связанной подписи в [11], предположение о безопасности которого является стойким предположением Диффи-Хеллмана (SDH). Остальные три протокола основываются на подписи Уотерса, но безопасность протокола [10] можно записать и для стойкого предположения: предположение Диффи-Хеллмана о выбранном значении (CT-CDH). Наш протокол и протокол из [9] разработаны однотипно. При сравнении с [9] наш протокол имеет меньший размер частичной подписи и более эффективен в подписании и проверке подписей. Это достигается за счёт больших затрат на размер ключа (при помощи ещё одной пары в ).

Заключение

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

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

  1. University College London, UK, E-mail: j.groth@ucl.ac.uk
  2. Department of Informatics, University of Athens, Greece , E-mail: aggelos@di.uoa.gr
  3. Cybernetica AS, Estonia, E-mail: lipmaa@research.cyber.ee
  4. Tallinn University, Estonia

Примечание

Литература

  1. Asokan, N., Schunter, M., Waidner, M.: Optimistic protocols for fair exchange.In: Proceedings of the 4th ACM conference on Computer and Communications.Security, pp. 7–17. ACM Press, New York (1997)
  2. 2,0 2,1 2,2 Zhu, H., Bao, F.: Stand-alone and setup-free verifiably committed signatures. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 159–173. Springer, Heidelberg (2006)
  3. 3,00 3,01 3,02 3,03 3,04 3,05 3,06 3,07 3,08 3,09 3,10 3,11 3,12 3,13 3,14 3,15 3,16 Dodis, Y., Lee, P.J., Yum, D.H.: Optimistic fair exchange in a multi-user setting. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 118–133. Springer, Heidelberg (2007)
  4. 4,0 4,1 4,2 4,3 4,4 4,5 4,6 4,7 4,8 4,9 Dodis, Y., Reyzin, L.: Breaking and repairing optimistic fair exchange from PODC 2003. In: Proceedings of the 3rd ACM Workshop on Digital Rights Management, pp. 47–54. ACM, New York (2003)
  5. 5,0 5,1 5,2 Asokan, N., Shoup, V., Waidner, M.: Optimistic fair exchange of digital signatures (Extended abstract). In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403,pp. 591–606. Springer, Heidelberg (1998)
  6. 6,0 6,1 6,2 Asokan, N., Shoup, V., Waidner, M.: Optimistic fair exchange of digital signatures.IEEE Journal on Selected Areas in Communication 18(4), 593–610 (2000)
  7. Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS,vol. 2656, pp. 416–432. Springer, Heidelberg (2003)
  8. Camenisch, J., Damg˚ard, I.: Verifiable encryption, group encryption, and their applications to separable group signatures and signature sharing schemes. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 331–345. Springer, Heidelberg (2000)
  9. 9,0 9,1 9,2 9,3 9,4 9,5 9,6 9,7 9,8 9,9 Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., Waters, B.: Sequential aggregate signatures and multisignatures without random oracles. In: Vaudenay, S. (ed.)EUROCRYPT 2006. LNCS, vol. 4004, pp. 465–485. Springer, Heidelberg (2006)
  10. 10,0 10,1 10,2 10,3 Zhang, J., Mao, J.: A novel verifiably encrypted signature scheme without random oracle. In: Dawson, E., Wong, D.S. (eds.) ISPEC 2007. LNCS, vol. 4464, pp. 65–78. Springer, Heidelberg (2007)
  11. 11,0 11,1 11,2 11,3 R.uckert, M., Schr.oder, D.: Security of verifiably encrypted signatures and a construction without random oracles. In: Shacham, H. (ed.) Pairing 2009. LNCS, vol. 5671, pp. 17–34. Springer, Heidelberg (2009)
  12. Park, J.M., Chong, E.K.P., Siegel, H.J.: Constructing fair-exchange protocols for E-commerce via distributed computation of RSA signatures. In: Proceedings of the twenty-second annual symposium on Principles of distributed computing, pp. 172–181. ACM, New York (2003)
  13. 13,0 13,1 13,2 13,3 13,4 13,5 13,6 Huang, Q., Yang, G.,Wong, D.S., Susilo, W.: Optimistic fair exchange secure in the multi-user setting and chosen-key model without random oracles. In: Malkin, T.G.(ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 106–120. Springer, Heidelberg (2008)
  14. Garay, J.A., Jakobsson, M., MacKenzie, P.: Abuse-free optimistic contract signing. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 449–466. Springer, Heidelberg (1999)
  15. 15,0 15,1 Markowitch, O., Kremer, S.: An optimistic non-repudiation protocol with transparent trusted third party. In: Davida, G.I., Frankel, Y. (eds.) ISC 2001. LNCS,vol. 2200, pp. 363–378. Springer, Heidelberg (2001) Further Observations on OFE Protocols in the Multi-user Setting 141
  16. Zhou, J., Gollmann, D.: A fair non-repudiation protocol. In: Proceedings of the 1996 IEEE Symposium on Security and Privacy,Washington DC, pp. 55–61. IEEE, Los Alamitos (1996)
  17. 17,0 17,1 17,2 Huang, Q., Yang, G., Wong, D.S., Susilo, W.: Ambiguous optimistic fair exchange. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 74–89. Springer, Heidelberg (2008)
  18. Zhu, H., Bao, F.: More on stand-alone and setup-free verifiably committed signatures. In: Batten, L.M., Safavi-Naini, R. (eds.) ACISP 2006. LNCS, vol. 4058, pp. 148–158. Springer, Heidelberg (2006)
  19. 19,0 19,1 19,2 19,3 19,4 Zhu, H., Susilo, W., Mu, Y.: Multi-party stand-alone and setup-free verifiably committed signatures. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 134–149. Springer, Heidelberg (2007)
  20. 20,0 20,1 20,2 20,3 20,4 20,5 20,6 Waters, B.: Efficient identity-based encryption without random oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005)
  21. 21,0 21,1 Boneh, D., Boyen, X.: Short signatures without random oracles. In: Cachin, C.,Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56–73. Springer,Heidelberg (2004)
  22. Boldyreva, A.: Threshold signatures, multisignatures and blind signatures based on the Gap-Diffie-Hellman-Group signature scheme. In: Desmedt, Y.G. (ed.)PKC 2003. LNCS, vol. 2567, pp. 31–46. Springer, Heidelberg (2002)