Несвязываемость одноразовых подписей

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:28, 30 октября 2015.
Unlinkability of Sanitizable Signatures
Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA.png
Авторы Christina Brzuska, Marc Fischlin, Anja Lehmann,
and Dominique Schroder [@: 1]
Опубликован 2010 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. В подписях с удалением секретной информации наличествует назначенный участник, называемый удаляющим секретную информацию, для модифицирования частей подписанных данных такого, что неизменные части можно всё ещё проверить относительно изначального подписывающего. Атениес и др. (ES-ORICS 2005) исследовали пять свойств безопасности для таких схем подписи: стойкость, неизменность, конфиденциальность, прозрачность и подотчётность. Эти термины были сформулированы в недавней работе Бзуски и др. (РКС 2009), в которой также расписаны отношения между этими свойствами безопасности. Кроме того, они доказали, что модифицированная схема Атениес и др. безопасна согласно этим понятиям.
Здесь обсуждается, что желательно ещё ввести шестое свойство для схем подписей с удалением секретной информации: несвязываемость. В основном, это свойство определяет возможность связывания пар сообщение-подпись с удалённой секретной информацией для одного документа, т.о. позволяя вывести комбинированную информацию об исходном документе. Мы показали, что это понятие реализует конфиденциальность, невозможность восстановления исходных данных частей с удалением секретной информации, но не реализуется ни одним из остальных пяти понятий. Также определяется схема основанная на групповой подписи удовлетворяющая всем пяти свойствам.

Введение

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

Атением и др. [1] рассмотрели применимость схем с удалением секретной информации для анонимности медицинских данных, заменив аутентификацию в медиа потоках или преобразовав достоверную информацию о потоках. Они выявили пять необходимых свойств безопасности для схем подписей с удалением секретной информации. Вот эти свойства:

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

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

Конфиденциальность. Предотвращение восстановления злоумышленником исходных данных о частях сообщения с удалением секретной информации.

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

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

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

Несвязываемость. Здесь мы обсудим, что дополнительное свойство может оказаться полезным в некоторых случаях. Назовём это свойство несвязываемостью и покажем причину его использования следующим примером (см. также Рис. 1): Предположим, что имеется подписанные медицинские записи и в тоже время данные являются анонимными посредством удаления личной информации пациентов такой, как имена, адреса и др. Помимо этого, удаляется действительная информация о медицинском лечении и остаётся только личная информация. Т.о. нельзя связать эти данные посредством подписей и поэтому восстановить полностью записи. Однако, предыдущие схемы такие, как схема Бзуски и др. [5], и, например, одна из [6][7][8] фактически подвержены таким атакам. Они обычно основываются на изменчивых хэш функциях, которые остаются неизменными для шага удаления секретной информации и т.о. позволяют выявить две подписи с удалённой секретной информацией полученные из одинаковой подписи посредством хэш значения. Других конструкции такие как [3] даже применяются вместе с явной идентификацией документов, позволяющей просто связать сообщения с удалённой секретной информацией.

Рисунок 1. Задача взаимосвязи.

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

Схема. Теперь представим конструкцию схемы подписи с удалением секретно информации обладающую всеми шестью свойствами, включая несвязываемость. Идея фундаментально отличается от предыдущих подходов, которые обычно основывались на изменчивых хэш функциях. В нашем случае подписывающий сперва подписывает фиксированную часть при помощи обычной схемы подписи. Для модифицированной части подписывающий и удаляющий секретные данные используют групповую схему подписи [9], т.е. схему подписи, которая позволяет подписывать анонимно от имени группы но так, чтобы главный участник группы смог выполнить идентификацию пользователя, который подписывал сообщение [10]. В нашем случае группа состоит только из подписывающего и удаляющего секретные данные, и подписывающий выступает в роли главного участника группы. Если удаляющий секретные данные потом изменяет (некоторые) модифицированные части сообщения он может создать новую группу подписи и заменить группе подписи подписывающего.

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

Заметим, что реальной конструкции необходима хорошая реализация вышеуказанной идеи для получения схемы подписи с удалением секретной информации удовлетворяющей всем необходимым свойствам безопасности. Это в частности правда т.к. предложенные групповые схемы подписи как [10][11][12][13][14][15] определены с различными ухищрениями относительно безопасности и установленных предположений. В данной версии мы т.о. покажем простой но не обязательно необходимый на практике подход реализации нашей идеи для схемы безопасности с удалением секретной информации, например, следуя определениям из [5] мы не используем тот факт, что открытые ключи подписывающего и удаляющего секретные данные регистрируются, хотя это более благоприятно при реализации на практике. В полной версии данной работы обсуждаются дальнейшие варианты, например, с несколькими удаляющими секретные данные, или с использованием кольцевой схемы подписи вместо групповой схемы подписи, т.о. снижая требование по подотчётности для описываемой схемы с удалением секретной информации.

Наше решение показывает, что в общем случае, подписи с удалением секретных данных можно построить из групповых подписей, т.о. обеспечивая возможность применения нового приложения для более поздних примитивов. Это также непосредственно даёт реализацию результата для подписей с удалением секретных данных: т.к. работа Беллара и др. [10] по групповым подписям доказывает, что их можно определить исходя из IND-CCA безопасного шифрования, не интерактивных доказательств нулевого разглашения, известного всем участникам существования лазейки в перестановках, и следовательно, можно также создать безопасные подписи с удалением секретных данных из лазейки перестановок.

План данной работы. В Разделе 2 представлено понятие схем с удалением секретных данных и свойства безопасности из [1][5]. В Разделе 3 обсуждается понятие несвязываемости и её отношение к другим свойствам безопасности. В Разделе 4 показывается наша конструкция безопасной схемы с удалением секретных данных основанная на групповых подписях.

Начальные данные и определения

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

Подписи с удалением секретных данных

В схеме подписи с удалением секретных данных как и у подписывающего так и у удаляющего секретную информацию находится пара ключа такая, что подписывающий может подписать сообщения с помощью его секретного ключа и «прикрепить» описание допустимого преобразования , которое позволено удаляющему секретную информацию Удаляющий секретную информацию может затем изменить это сообщение согласно некоторой модификации и преобразовать подпись используя его секретный ключ . Для того, чтобы урегулировать разночтения между исходной парой сообщение-подпись алгоритм Proof позволяет подписывающему выполнить доказательство из предыдущих подписанных сообщений, подпись которых была создана удаляющим секретную информацию. Это доказательство может затем быть определено с помощью Judge алгоритма (которому необходимо только выявить корректность исходной пары сообщение-подпись; для некорректных пар решения алгоритма будут в общем случае нереализуемы).

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

Для простоты обозначения пусть будет эффективным детерминистическим алгоритмом, который равномерно распределён по и в котором отображается m в неизменную часть сообщения , например, для блочно разбитых сообщений будет набором всех блоков не присутствующих в . Для исключения тривиальных примеров установим, что допустимые преобразования оставляют фиксированную часть сообщения без изменений, т.е. для всех и всех с . Аналогично, во избежание наличия у пустого выхода, также потребуем, чтобы фиксированная часть была «максимальной» для заданного , т.е. для с

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

Следующее определение взято из [5]:

TemplateDifinitionIcon.svg Определение «Определение 1»
(Схема подписи с удалением секретных данных). Схема подписи с удалением секретных данных SanSig состоит из семи эффективных алгоритмов ( ) таких, как:

Генерация ключа. Будет два алгоритма генерации ключа, один для подписывающего другой для удаляющего секретную информацию. Оба создают пару ключей, секретный ключ и соответствующий открытый ключ:

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

Полагаем, что восстановима из любой подписи

Удаление секретной информации. Алгоритм Sanit принимает сообщение , подпись , открытый ключ подписывающего и секретный ключ удаляющего секретную информацию. Он преобразовывает сообщение согласно предписанию модификации и определяет новую подпись для модифицированного сообщения. Затем Sanit выводит и (либо возможно в случае ошибки).

Проверка. Алгоритм Verify выводит бит проверяющий корректность подписи для сообщения относительно открытых ключей и

Доказательство. Алгоритм Proof принимает на входе секретный подписывающий ключ , сообщение и подпись в качестве набора (полиномиально достаточных) дополнительных пар сообщение-подпись и открытого ключа Он выводит строку  :

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

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

Безопасность подписей с удалением секретных данных

Здесь мы напомним вам обозначения для подписей с удалением секретных данных заданной Бзуской и др. [5]. Отметим, что в [5] они показали, что подотчётность подписывающего и удаляющего секретную информацию вместе реализует стойкость, а прозрачность реализует конфиденциальность. Следовательно, в принципе этого достаточно для того, чтобы показать неизменность, подотчётность и прозрачность. Поэтому опустим общие определения стойкости и конфиденциальности здесь, а если читателю они интересны то ему следует обратиться к полной версии данной работы.

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

{Определение|Определение 2 (Неизменность).| Схема подписи с удалением секретных данных SanSig будет неизменной если для каждого эффективного алгоритма А вероятность того, что следующий пример вернёт 1 пренебрежимо мала (как функция от n).}}

TemplateExampleIcon.svg Пример Пример Неизменность
Immutabibillity Signature.png


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

В игре с подотчётностью удаляющего секретную информацию пусть будет эффективным злоумышленником играющим роль злоумышленника удаляющего секретную информацию. Злоумышленник имеет доступ к Sign и Proof оракулам. Его задачей будет вывести корректную пару сообщение-подпись вместе с ключом (с отличными от пар ( ) в предыдущем запросе Sign оракула) таким, что доказательство предложенное подписывающим посредством Proof приводит к решению «Sig», т.е. что подпись была создана подписывающим.

TemplateDifinitionIcon.svg Определение «Определение 3 (Подотчётность удаляющего секретную информацию).»
Схема подписи с удалением секретных данных SanSig называется подотчётной удаляющего секретную информацию если для любого эффективного вероятность того, что следующий пример возвращает 1 пренебрежимо мала (как функция от n).
TemplateExampleIcon.svg Пример Пример Сан-Подотчетность
San-Accountability Signature.png


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

TemplateDifinitionIcon.svg Определение «Определение 4 (Подотчётность подписывающего).»
Схема подписи с удалением секретных данных SanSig называется подотчётным подписывающим если для любого эффективного вероятность того, что следующий пример возвратит 1 пренебрежимо мала (как функция от n).
TemplateExampleIcon.svg Пример Пример Sig-Подотчетность
Sig-Accountability Signature.png


Прозрачность. Определим прозрачность с помощью следующей игры злоумышленника. Рассмотрим злоумышленника А с доступом к Sign, Sanit и Proof оракулам с которыми злоумышленник может создать подписи для сообщений (с удалением секретных данных) и изучить доказательства. Кроме того, А получает доступ к Sanit/Sign ящику, который содержит секретный случайный бит и который, для входящего сообщения m, будет модификационной информацией MOD и определением ADM.

  • для b = 0 выполняем алгоритм подписывающего по созданию затем выполняем алгоритм удаляющего секретную информацию и возвращаем сообщение с удалением секретных данных m’ с новой подписью , и
  • для b = 1 будет всё также как и для b = 0, но ещё подписываем m’ с помощью алгоритма подписания для создания подписи и возвращаем пару (m’, ).

Злоумышленник А в действительности выводит а, как предположение для b. Подпись с удалением секретных данных теперь будет прозрачной если для всех элементов эффективных алгоритмов А вероятность для верного предположения a = b в вышеуказанной игре будет пренебрежимо близка к ½. Ниже определим упрощённую версю называемую прозрачностью с упрощённым доказательством и обсудим её идею после определения.

TemplateDifinitionIcon.svg Определение « Определение 5 (Прозрачность (с упрощённым доказательством)).»
Схема подписи с удалением секретных данных SanSig будет прозрачной (с упрощённым доказательством) если для любого эффективного алгоритма А вероятность того, что следующий пример возвратит 1 пренебрежимо близка к ½.
TemplateExampleIcon.svg Пример Пример Прозрачность
Transparency Signature.png


Исходное определение Бзуски и др. [3] не рассматривало случай с упрощённым доказательством. Без этого допущения, однако, получение прозрачности на первый взгляд выглядит невозможным потому что злоумышленник может всегда представить повторения Sanit/Sign оракула для Proof оракула и т.о. восстановить секретный бит b. Однако, в их конструкции Proof алгоритм осуществляет поиск в списке предыдущих подписанных сообщений и отвечает только если находит совпадение, что позволяет реализовать прозрачность без данного допущения. Но, любое решение (как то, что представлено здесь) где Proof алгоритм будет с «пустым списком» может достигать прозрачность только для версии с упрощённым доказательством. Отметим, что Proof алгоритмы не используют набору предыдущих сообщений, что предпочтительно с точки зрения эффективности, конечно.

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

Несвязываемость

В данном разделе определяется несвязываемость в общем виде и обсуждается её отношение относительно других понятий безопасности.

Определение

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

Формально, используется подход основанный на играх для определения несвязываемости, также как и для других понятий безопасности из [5]. Злоумышленнику дан доступ к подписывающему оракулу и оракулу удаления секретных данных (и доказательство оракула для этого шага зависит от секретного ключа подписывающего и может терять значимую информацию). Злоумышленник также может запросить оракул LoRSanit, который инициализирован секретным случайным битов b. В каждом из многочисленных запросов LoRSanit злоумышленник рассматривает пару кортежей, каждый состоящий из сообщения, модификации и корректной подписи, таких, что восстановимое описание допустимых преобразований будет идентично в обоих случаях (т.к. полагается, что ADM восстановим из подписи определяющей различные описания ADM и что позволит реализовать тривиальную атаку; т.о. необходим случай, когда только одна подпись будет корректной). В зависимости от бита b, злоумышленник получает пару сообщение-подпись с удалением секретных данных либо для левой либо для правой пары входных значений. Злоумышленник должен действительно предсказать бит b значительно лучше чем по вероятности предположения .

TemplateDifinitionIcon.svg Определение « Определение 6 (Несвязываемость).»
Схема подписи с удалением секретных данных SanSig будет непривязываема если для любого эффективного алгоритма А вероятность того, что следующий пример возвратит пренебрежимо близка к .
Unlinkability Signature.png

Визуальное объяснение изображено на Рисунке 2. Отметим, что вышеуказанное определение дано для надёжного примера содержащего несколько шагов удаления секретной информации в LoRSanit оракуле. Т.е., злоумышленнику позволено в вышеуказанном примере получать «модифицированные цепочки» переменной длины и такие, что из двух исходных документов постепенно удаляется секретная информация получаемая в результирующих документах. Т.о. предсказание является трудной задачей, т.к. такие цепочки можно потенциально симулировать с помощью вызова оракула удаления секретной информации для первых преобразований вручную, перед входом в конечный шаг удаления секретной информации для LoRSanit оракула.

Рисунок 2. Несвязываемость. А выигрывает если выводит a = b..

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

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

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

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

TemplateLemmaIcon.svg Лемма «Предположение 1 (Независимость несвязываемости).»
Предположим, что существует схема подписи с удалением секретных данных (согласуемая с одним или более свойствам стойкости, неизменности, конфиденциальности, прозрачности (с упрощённым доказательством), подотчётности подписывающего и подотчётности удаляющего секретную информацию). Тогда существует схема подписи с удалением секретных данных, которая не будет обладать несвязываемостью, но будет соответствовать другим свойствам безопасности.


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

TemplateLemmaIcon.svg Лемма «Предположение 2 (Несвязываемость реализует конфиденциальность).»
Любая несвязываемая схема подписи с удалением секретных данных будет также конфиденциальна.


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

TemplateLemmaIcon.svg Лемма «Предположение 3 (Независимость других свойств).»
Предположим , что существует схема подписи с удалением секретных данных которая обладает стойкостью, неизменностью, конфиденциальностью, прозрачностью (с упрощённым доказательсвом), подотчётностью подписывающего и удаляющего, а также несвязываемостью. Тогда для любых других свойств стойкости, неизменности, конфиденциальности, прозрачности (с упрощённым доказательством), подотчётности подписывающего и подотчётности удаляющего, существует схема подписи с удалением секретных данных согласуемая со всеми свойствами за исключением того, которое будет под вопросом.


Доказательство. Факт того, что несвязываемость не следует ни из одного свойства уже был показан в Предположении 1. Для других свойств отметим, что контрпримеры из [5], которые независимо от других свойств неизменны, прозрачны, подотчётны также несвязываемы в каждом случае (и также выполняется для упрощённого доказательства прозрачности).

Конструкции основанные на групповых подписях

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

Групповые подписи

Групповые подписи, представленные Чаумом и Хейстом [9], позволяют нескольким пользователям подписывать от имени группы так, что сторонние лица не смогут различить по признакам разные подписи (анонимность), но главный участник группы может проверить идентификацию подписывающего (трассерируемость). Мы следуем общей методике Беллара и др. [10], но с добавлением не обобщённого требования [16], что даже главный участник группы не может подписывать от имени пользователей. Напомним, что это необходимо для подотчётности в нашей схеме подписи с удалением секретных данных, где подписывающий выступает в роли главного участника группы и не должен обладать возможностью реализации отказа для удаляющего секретные данные.

Вкратце напомним, что представляют из себя групповые схемы подписи и их свойства безопасности. Для развёрнутых определений обращайтесь к полной версии данной работы и [10]. Групповая схема подписи состоит из 6 эффективный алгоритмов где

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

Существует три свойства безопасности для групповых подписей [10][11]:

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

TemplateDifinitionIcon.svg Определение « Определение 7 (Безопасная групповая подпись).»
Назовём схему групповой подписи безопасной, если она анонимна и не ограничена.

Отметим, что мы специально приспособили определения групповой подписи для наших целей добавив неограниченность, и сделав синтаксическую установку сессии схемы свободной и приемлемой безопасной моделью учитывающей некоторые технические нюансы рассмотренные в полной версии данной работы. Относительно конкретизации отметим, что (обобщённая) конструкция Беллара и др. [10] удовлетворяет нашему добавочному определению. Что касается более эффективных групповых схем подписи, то можно реализовать нашу схему подписи с удалением секретных данных с другими групповыми схемами подписи такими как [12][13][14][15]. Но всё же этим групповым схемам подписи требуется дополнительные начальные предположения такие как доверенный участник генерирующий общие параметры или интерактивная регистрация пользователей. Наша схема подписи с удалением секретных данных т.о. соответствует этим характеристикам (напомним, что на практике регистрация ключей подписывающего и удаляющего секретную информацию будет, например, необходима для определения значимой подотчётности).

Схема

В данном разделе показывается, что новое требование по безопасности в виде несвязываемости можно получить совместно с пятью установленными свойствами безопасности обобщая [5]. Напомним, что подписывается полное сообщение, включая модифицированные части, при помощи схемы групповой подписи, и – для того, чтобы избежать незаданных изменений – подписывающий также подписывает фиксированную часть с помощью регулярной схемы. Это нужно принять во внимание, т.к. если взять переменную схему подписи, то подпись может выступать в роли уникального идентификатора, даже для сообщений с идентичной фиксированной частью. Т.о. несвязываемость будет нарушена.

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

За формальным определением мощных стойких схем подписи обратитесь к [18]. Нам необходимо это понятие стойкости для определения несвязываемости. Примерами схем подписи в которых реализовано это мощное понятие служат [19][20] [21] [22] [16]. Более того, возможно получить очень стойкую схему подписи из любой стойкой схемы подписи применив преобразование Беллара и Соупа [23]. Применив преобразование [17] можно также сделать такие схемы детерминистическими.

Напомним, что основополагающая идея нашей схемы заключается в том, что для каждой подписи подписывающий использует ключ главного участника группы, создаёт сертифицированный ключ пользователя для подписания модифицируемых частей, и сертифицирует открытый ключ удаляющего секретные данные выступающего в качестве члена группы выполняющего преобразования. Но т.к. наше определение подписей с удалением секретных данных основывается на свободных решениях, подписывающий формально не может сохранять ключ главного участника группы для данного удаляющего секретную информацию и нужно создавать новый для каждого запроса. Это обходится следующим образом: пусть подписывающий для каждого запроса подписи, включая открытый ключ удаляющего секретную информацию , создаёт ключи главного участника группы с помощью соответствующих групповых алгоритмов подписи, ну а случайность этих алгоритмов обеспечивается реализацией псевдослучайной функции (см. [24] для определения псевдослучайных функций). Поэтому мы не буреем (практически) независимые ключи для различных удаляющих секретную информацию, а используем составные параметры для каждого удаляющего секретную информацию. По той же причине, также применяется сертификат группового членства удаляющего секретную информацию в подписи, хотя он итак задан непосредственно для удаляющего секретную информацию. В качестве побочного эффекта, т.к. открытый ключ главного участника связан с удаляющим секретную информацию, также необходимо использовать только на групповые подписи со статическими объединениями.

TemplateExampleIcon.svg Пример Конструкция 1 (Схема подписи с удалением секретных данных)
Sanitizable Signature Scheme.png


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

Текст заголовка

Доказательство безопасности

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

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


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

Стойкость соответствующей регулярной схемы подписи реализует неизменность: Если удаляющий секретную информацию изменит допустимые части сообщения, то ему всё равно будет невозможно взломать подпись для фиксированной части. Несвязываемость выполняется т.к. удаляющий секретную информацию создаёт новую групповую подпись при удалении секретных данных. Более того, подпись регулярной схемы остаётся без изменений, и идентична для разных документов с одинаковой фиксированной частью т.к. используется детерминистическая схема. Формальное доказательство представлено в полной версии данной работы.

Слова благодарности

Мы хотели бы поблагодарить анонимных авторов за их полезные комментарии. Работа Марка Фичлина, Ани Леман и Доминика Шрёдера осуществлялась при поддержке Программы Эми Нотер Fi 940/2-1 Исследовательского Фонда Германии (DGF). Эта работа также осуществлялась при поддержке CASED (http://www.cased.de).

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

  1. Darmstadt University of Technology, Germany E-mail: [1]

Литература

  1. 1,0 1,1 1,2 1,3 Ateniese, G., Chou, D.H., de Medeiros, B., Tsudik, G.: Sanitizable Signatures. In:di Vimercati, S.D.C., Syverson, P.F., Gollmann, D. (eds.) ESORICS 2005. LNCS,vol. 3679, pp. 159–177. Springer, Heidelberg (2005)
  2. Steinfeld, R., Bull, L., Zheng, Y.: Content Extraction Signatures. In: Kim, K.-c. (ed.) ICISC 2001. LNCS, vol. 2288, pp. 285–304. Springer, Heidelberg (2002)
  3. 3,0 3,1 Miyazaki, K., Susaki, S., Iwamura, M., Matsumoto, T., Sasaki, R., Yoshiura, H.: Digital documents sanitizing problem. Technical Report ISEC2003-20. IEICE (2003)
  4. Johnson, R., Molnar, D., Song, D.X., Wagner, D.: Homomorphic Signature Schemes. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 244–262. Springer, Heidelberg (2002)
  5. 5,00 5,01 5,02 5,03 5,04 5,05 5,06 5,07 5,08 5,09 5,10 Brzuska, C., Fischlin, M., Freudenreich, T., Lehmann, A., Page, M., Schelbert, J.,Schroeder, D., Volk, F.: Security of Sanitizable Signatures Revisited. In: Jarecki, S.,Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 317–336. Springer, Heidelberg (2009) 460 C. Brzuska et al.
  6. Klonowski, M., Lauks, A.: Extended Sanitizable Signatures. In: Rhee, M.S., Lee, B. (eds.) ICISC 2006. LNCS, vol. 4296, pp. 343–355. Springer, Heidelberg (2006) Unlinkability of Sanitizable Signatures 461
  7. Canard, S., Laguillaumie, F., Milhau, M.: Trapdoor Sanitizable Signatures and Their Application to Content Protection. In: Bellovin, S.M., Gennaro, R., Keromytis, A.D., Yung, M. (eds.) ACNS 2008. LNCS, vol. 5037, pp. 258–276. Springer, Heidelberg (2008)
  8. Canard, S., Jambert, A.: On Extended Sanitizable Signature Schemes. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 179–194. Springer, Heidelberg (2010)
  9. 9,0 9,1 Chaum, D., van Heyst, E.: Group Signatures. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 241–246. Springer, Heidelberg (1991)
  10. 10,0 10,1 10,2 10,3 10,4 10,5 10,6 Bellare, M., Micciancio, D., Warinschi, B.: Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 614–629. Springer, Heidelberg (2003)
  11. 11,0 11,1 Bellare, M., Shi, H., Zhang, C.: Foundations of Group Signatures: The Case of Dynamic Groups. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 136–153. Springer, Heidelberg (2005)
  12. 12,0 12,1 Kiayias, A., Yung, M.: Group Signatures with Efficient Concurrent Join. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 198–214. Springer, Heidelberg (2005)
  13. 13,0 13,1 Delerabl.ee, C., Pointcheval, D.: Dynamic Fully Anonymous Short Group Signatures. In: Nguyˆen, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 193–210. Springer, Heidelberg (2006)
  14. 14,0 14,1 Groth, J.: Simulation-Sound NIZK Proofs for a Practical Language and Constant Size Group Signatures. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 444–459. Springer, Heidelberg (2006)
  15. 15,0 15,1 Groth, J.: Fully Anonymous Group Signatures Without Random Oracles. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 164–180. Springer, Heidelberg (2007)
  16. 16,0 16,1 Boneh, D., Shen, E., Waters, B.: Strongly Unforgeable Signatures Based on Computational Diffie-Hellman. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 229–240. Springer, Heidelberg (2006)
  17. 17,0 17,1 Goldreich, O.: Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 104–110.Springer, Heidelberg (1987)
  18. Goldreich, O.: The Foundations of Cryptography, vol. 2. Cambridge University Press, Cambridge (2004)
  19. Bellare, M., Rogaway, P.: The Exact Security of Digital Signatures - How to Sign with RSA and Rabin. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 399–416. Springer, Heidelberg (1996)
  20. Coron, J.-S.: On the Exact Security of Full Domain Hash. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 229–235. Springer, Heidelberg (2000)
  21. Boneh, D., Lynn, B., Shacham, H.: Short Signatures from theWeil Pairing. Journal of Cryptology 17(4), 297–319 (2004)
  22. 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)
  23. Bellare, M., Shoup, S.: Two-Tier Signatures, Strongly Unforgeable Signatures, and Fiat-Shamir Without Random Oracles. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 201–216. Springer, Heidelberg (2007)
  24. Goldreich, O.: The Foundations of Cryptography, vol. 1. Cambridge University Press, Cambridge (2001)