Подписи замены и проверяемое шифрование

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:53, 27 сентября 2015.
Commuting Signatures and Verifiable Encryption
EC2011 2.PNG
Авторы Georg Fuchsbauer[@: 1]
Опубликован 2011 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

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

Введение

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

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

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

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

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

Анонимные учётные данные нацелены на обеспечение функциональности схожей с сертификатами но без раскрытия информации об идентификаторе пользователя при получении или раскрытии учётных данных. Однако, до недавнего времени связь между делегируемостью и анонимностью прослеживалась неявно. Чейс и Лизианская[1] показали теоретическое существование делегируемых анонимных учётных данных, но их размер был экспоненциальным для числа делегатов. Обойти это сумели Беленский и др. (BCCKLS) в [2], представив новый метод использования не интерактивной системы доказательства нулевого разглашения (NIZK)[3] с рандомизируемыми доказательствами: кто угодно может преобразовать такое доказательство в новое доказательство аналогичного характера при этом оно не будет связано с оригиналом. Учётные данных по сути это доказательство знания цепочки сертификата, которая может быть рандомизирована перед процессом делегации или её раскрытием, что гарантирует анонимность и несвязываемость.

В их модели каждый пользователь обладает секретным ключом который можно использовать для получения нескольких несвязанных между собой псевдонимов Nym. Пользователь А может представляться для пользователя О как , а для B как . Для заданных учётных данных имеющихся у O относительно , A может преобразовать их в учетные данные от O для и показать их B. Более того, A может делегировать учётные данные пользователю C, известному A как . C, в свою очередь, может показать учётные данные от O для пользователю D (без раскрытия и ), или повторно их делегировать. Делегирование сохраняет анонимность и в таком случае делегат и делегируемый не получают какой-либо информации об их соответствующих псевдонимах. Это формализуется требованием существования такого симулятора, который бы мог сопоставлять псевдонимы и учётные данные без наличия знания об их секретных значениях.

Как утверждается в [2] делегирование – это довольно сложный и интерактивный процесс, что нельзя сказать об его аналоге с не анонимными учётными данными, где достаточно знать открытый ключ пользователя для того, чтобы сопоставить делегирование и его учётные данные. Этот недостаток обходится с помощью утверждения о том, что наличествует не интерактивное делегирование: для заданного псевдонима Nym, делегат может задавать готовые учётные данные для обладателя Nym без какой-либо дополнительной итерации. Отметим, что протокол не интерактивного делегирования включает в себя по определению безопасность от одновременных атак, при которых злоумышленник может одновременно запускать протоколы для делегирования и делегируя тем самым учётные данные доверенных пользователей. Этот случай не рассмотрен в BCCKLS модели.

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

Для согласованности с методологией Грота-Сахая[4], мы также будем говорить привязка вместо шифрования, т.к. привязки к групповым элементам, которые мы будем использовать, являются извлекаемыми, т.е. можно восстановить взаимосвязанное значение (и т.о. «расшифровать») используя ключ извлечения. Извлекаемая привязка к подписи наряду с доказательством корректности является доказательством знания подписи (PoK), и в тоже время проверяемой зашифрованной подписью (VES) ([5], [6].

Обозначим привязку к подписям за Com, к сообщениям - , а доказательство корректности - . Доказательство для взаимосвязанной подписи обозначим за , а для соответствующего сообщения - . Если оба из них взаимосвязаны, записываем это как , а если и ключ привязки тоже связан с ними, то - » для подписи «» для vk). Помимо возможности доказательства корректности взаимосвязанных значений, схема подписи замены обладает следующей функциональностью, ни один пункт которой не требует знания ключа извлечения: . Для заданной привязки к сообщению М и ключа подписи , выполняет привязку к подписи на М при , а доказательство содержащееся в будет корректной подписью элементов .

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

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

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

Рисунок 1. Диаграмма представления системы подписей привязки и проверяемого шифрования

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

Кроме того, для проверяемых зашифрованных подписей, подписей привязки применяют подписи в слепую, а также CL подписи [7] и Р-подписи [8], которые в свою очередь являются блоками построения для протоколов обеспечивающих конфиденциальность. Они позволяют пользователю получать подпись на взаимосвязанное значение от подписывающего с помощью выполнения соответствующего протокола. Пользователь может затем доказать знание подписи, что будет являться проверкой для заданной привязки. обеспечивает не интерактивное взаимодействие, которое напрямую даёт пользователю (рандомизируемое) доказательство знания такой подписи (см. полную версию [9]).

Примеры подписей привязки. Подписи в слепую [10], [11] позволяют пользователю получить подпись для сообщения в том виде, в котором подписывающий не может проследить результирующий путь для пары сообщение/подпись. В [12], [13] авторы показывают эффективную реализацию с циклически оптимальным выходом [14], где после отправки информации к подписывающему, пользователь незамедлительно получает подпись в слепую в качестве ответа подписывающего. В такой схеме, пользователь рандомизирует сообщение, и дополняет его доказательством свидетельства о неразличимости по признакам (WI) о том, что привязки содержат корректные значения.

Пользователь отправляет эти значения подписывающему, который в свою очередь не получает никакой дополнительной информации о сообщении. Подписывающий реализует процедуру «предварительной подписи», которую пользователь, при известных ему значениях используемых для рандомизации сообщения, может преобразовать в подпись для своего сообщения. В действительности подпись в слепую будет в таком случае WI доказательством знания (РоК) этой подписи, что предотвращает ситуацию, при которой подписывающий получает информацию о процедуре подписи. Это РоК связано с привязками Грота-Сахая (GS) и доказательствами [4] для парных произведений уравнений (РРЕ), а сообщение в таком случае содержит пары групповых элементов.

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

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

Примеры делегируемых анонимных учётных данных. Беленски и др.[2] показали, что доказательства Грота-Сахая (GS) можно рандомизировать и совместить их с схемой аутентификации для секретных ключей при построении делегирования учётных данных. Псевдоним Nym есть привязка к секретному ключу пользователя, а учётные данные это доказательство знания цепочки аутентификации. Для делегирования либо получения выходных данных, пользователи совместно вычисляют РоК аутентификатора содержащихся данных относительно пользовательского псевдонима. В случае делегирования, первичный пользователь раскрывает свои собственные учётные данные, после их рандомизации. Их схема аутентификации должна удовлетворять стойким понятиям безопасности (F-стойкость и сертификат безопасности) т.к. секретные ключи нельзя получить из привязок и злоумышленник в таком случае вынужден запрашивать аутентификацию как до так и после ключа, на который производилась атака.

Мы уходим от данных понятий и интерактивности делегирования с помощью более модульного подхода замены аутентификаторов на секретные ключи путём замены подписей на ключи проверки. Соответствующие подписи являются автоморфными [12], что означает совместимость Грота-Сахая и нахождение ключей проверки в пространстве сообщений – что и требуется для делегирования. Учётные данные в таком случае представляются в виде цепочки ключей проверки и сертификатов (без анонимности), которые задаются как привязки совместно с доказательствами корректности.

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

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

Т.о. на протокол передачи (делегирования) значительно более эффективный. В то время как в [2], начальный пользователь и пользователь выполняют сложный двухсторонний протокол использующий гомоморфное шифрование и интерактивные ZK доказательства, в нашем случае начальный пользователь просто отправляет РоК подпись. Обе схемы доказуемо безопасны при SXDH предположении и различных «скрытых» вариантах стойкого предположения Диффи-Хеллмана [15] (которые являются q-типными предположениями): BB-CDH и BBSDH, представленные в [2], для их схемы и ADH-SDH [13] для нашей (см. Раздел 4.1).

Автоморфные подписи совмещаются с GS доказательствами в [13] для построения прокси подписей (APS) [16]. Они также позволяют доказывать обладание какими-либо правами анонимно, но в таком случае анонимности не будет между делегатом и делегируемым пользователем. Если в нашей схеме учётных данных задаётся ключ извлечения с локальным авторством, и определяется алгоритм прокси подписания схожий с делегированием, но выводящий подпись привязки и для пустого сообщения, то необходимо использовать метод APS с взаимно анонимным делегированием.

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

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

Мы вкратце опишем определения и требования по безопасности для соответствующих примитив взятые из литературы (для более детального описания обратитесь к полной версии данной работы [9]).

Привязки. Мы будем использовать схему рандомизационной извлекаемой привязки Com которая состоит из алгоритмов , , , , и . За мы обозначим пространство «взаимосвязанных» значений, за - пространство случайных значений, и за - пространство привязок. На входе принимается параметр безопасности , и выводят ключ привязки , а выводит , где это распределение выходного значения ; назовём ключом извлечения. Для входных данных , сообщения и случайного значения , Com выводит привязки .

Такая схема будет полностью скрываемой, т.е. для любого и любого существует только одно согласно тому, что для некоторого . Если тогда извлекает это значение М из с. Ключи, выводимые , вычислительно неразличимы по признакам от их аналогов, выводимых , и генерируют полное сокрытие привязок: для любого , и существует такое, что . И ещё, мы получаем, что ; т.о. рандомизирует привязки.

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

Рандомизационная система доказательства свидетельства неразличимости по признакам Доказательства для схемы привязки Com класса уравнений, содержащих алгоритмы и . На входе имеем , уравнение , значения , удовлетворяющие Е и выводит доказательство для значений На входе и выводит 0 или 1, выявляя принятие или отказ относительно . Каждое доказательство генерируемое для привязок к значениям удовлетворяющим уравнению проверяется . Для заданных доказательства для и Е, а также , алгоритм выводит доказательство для рандомизационных значений ; в частности, распределён как .

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

Подписи. Схема подписи Sig состоит из следующих алгоритмов: принимает в качестве входа параметр безопасности и выводит параметры pp, которые определяют пространство сообщений . При входе рр, выводит пару проверки и ключ подписи. Для выводит подпись , которая проверяется . Если и , то для всех . Сильная стойкость означает, что для заданного vk и оракула, который запрашивает сообщение и возвращает на , невозможно получить на выходе пару , т.к. и для всех i.

Необходимо, чтобы Sig был взаимозаменяем с Com и Proof: сообщения, ключи проверки и подписи состоящие из значений в (пространство значений Com) и проверка предиката подписи были конъюнкцией уравнений из (класс уравнений Proof). Отметим, что из заменяемой тройки (Com, Sig, Proof) можно легко построить проверяемую схему с зашифрованной подписью; см. [9].

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

Подписи замены и проверяемое шифрование

Подписи замены расширяют схему привязки Com, связывают систему Proof и схему подписи замены Sig следующей функциональностью: это схема привязки с аналогичными Com ключами и пространством сообщений таким же как в Sig. SigCom принимает привязку и подписывает ключ, а также выполняет привязку подписи для заменяемого сообщения и доказательство корректности. SmSigCom моделирует SigCom и задаёт подпись вместо ключа подписи. Кроме этого, алгоритмы AdC и AdD адаптируют доказательства при привязке (обратном процессе) к подписи (с индексов S), сообщению (индекс М) либо ключу проверки (индекс К).

TemplateDifinitionIcon.svg Определение «Определение 1»
Система заменяемых подписей и проверяемого шифрования состоит из извлекаемой схемы привязки с пространством значений пространством случайных значений системой рандомизационного доказательства WI для Com, совместимой схемы подписи и следующих алгоритмов. Пусть и .

. На входе принимает рр, сообщение и , алгоритм выводит привязку С в , пространство привязок. принимает на входе рр, С и и выводит рандомизированную привязку С’. Для входного значения еk выводится С , а - значение привязки М. Необходимо чтобы была схемой привязки как определено в Разделе 2 и взаимо заменяема с Proof, т.е. Prove и RdProof принимают входные значения от а Verify - привязки.

. Если , тогда алгоритм выводит , который распределён как , где М и такие, что .

. Если , тогда алгоритм выводит , который распределён как , где М и такие, что .

. Если , тогда алгоритм выводит , который распределён как , где и такие, что .

. Если , то алгоритм выводит , который распределён как , где и такие, что .

. Если , алгоритм выводит , который распределён как , где , , и такие, что и .

. Если , алгоритм выводит , который распределён как , где , , и такие, что и .

. Если , тогда алгоритм выводит привязку к подписи и доказательство корректности , которые распределены как

,

где М и такие, что .

. Положим . Если тогда алгоритм выводит , которые распределены как

,

где М и такие, что .

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

Определение 1 означает, что выполнение SigCom на привязке к М аналогично (идентичное распределение выхода) выполнению на на и на ; либо выполнение на М и для и затем на , а также и т.д. Это означает, что элементы диаграммы на Рис. 1 взаимозаменяемы.

позволяет нам доказать следующее свойство стойкости: Рассмотрим злоумышленника, которому дано для и доступ к оракулу на входе которого , а его возвращаемое значение - . Тогда он не может получить выходные данные корректной тройки такие, что связанная пара сообщение/подпись отличалась от любой пары из запросов оракула. Заменяемые подписи более того содержат в себе циклически оптимальную схему подписи в слепую: Пользователь отправляет привязку к сообщению подписывающему, который выполняет SigCom для получения . Пользователь вычисляет доказательство для и М через и выводит в виде подписи в слепую (см. [9]).

Примеры построения блоков схемы

Билинейные группы и предположения

Билинейная группа - это кортеж , где и - это циклические группы простого порядка р; и генерируют и , соответственно; а - это эффективное невырожденное билинейное отображение: , а генерирует .

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

Предположение 1 (SXDH). Симметрическое предположение Диффи-Хеллмана для утверждает, что для заданного случайных сложно решить, будет ли или случайным значением; то же самое для заданного случайных сложно решить, будет ли или случайным значением.

q-Ассиметрическое удвоенно сокрытое стойкое предположение Диффи-Хеллмана (ADH-SDH) было представлено в [13] и доказано, что оно сохраняется в общей групповой модели для любого типа пар. В [19] было показано q-SDH предположение [15], где для заданного и наборов для случайного значения , сложно вычислить новый набор такого же вида. Аналогично q-HSDH [20], ADH-SDH утверждает, что если и заданы в сокрытом виде , то невозможно вычислить другой подобный кортеж

Предположение 2 (q-ADH-SDH). Для случайно выбранных и , заданного и для ,

получить на выходе с для всех i является трудной задачей.

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

Предположение 3 (AWF-CDH). Для заданных генераторов и , а также для получить на выходе с является трудной задачей.

Доказательства Грота-Сахая и Автоморфные подписи

Привязки. Мы продемонстрируем это на примере Com, определённом в разделе 2, с помощью схемы привязки основанной на SXDH из [4]. Setup, на входе имеющий , выводит ключ привязки . Значение и пространство случайных значений определяются как и . принимает случайное значение и элемент ; привязки к -элементам будут в , а привязки к -элементам в . Получаем , где «» обозначает покомпонентное умножение; привязки т.о. гомоморфны.

возвращает , который для будет равен . ExSetup выстраивает ck как и в Setup и в качестве дополнительного выходного значения он использует случайное значение в виде ek, а выводит значение привязки. WlSetup вычисляет ключ привязки т.е. неразличимое значение по признакам от выхода Setup при SXDH предположении. Привязки над независимы от этого значения привязки.

Доказательства для значений привязки. Для того чтобы продемонстрировать Proof для Com, используем систему доказательств из [4], которая показана в рандомизационном виде в [2]. Класс уравнений для нашей системы доказательств будет называться класс уравнений парных произведений (PPE). РРЕ для неизвестных и выглядит как уравнение вида

определённого для , при и . Воспользуемся [4] и [9] для описания реализаций следующим образом: Prove, который выбирает частное случайное значение и выводит ; , который адаптирует доказательство при новой привязке и выводимой с помощью и ; и .

Подписи. Рассмотрим Sig с точки зрения автоморфной схемы подписи представленной в [13]. По совместимости понятно, что компоненты подписи находятся в пространстве для значений привязки , а проверочные уравнения будут уравнениями парных произведений, и т.о. в . Более того, ключи проверки лежат в пространстве сообщений, набор пар Диффи-Хеллмана. При q-ADH-SDH и AWF-CDH, Sig будет значительно стойче от злоумышленников выполняющих до q – 1 адаптивных запроса на выбранные сообщения, как показано в [12].

Схема 1 (Sig). имеет на входе билинейную группу и выводит случайные генераторы . Пространство сообщений будет .

выбирает и выводит и

Sign имеет на входе секретный ключ x и сообщение . Он выбирает и выводит

Ver на входе получает ключ проверки , сообщение и подпись и выводит 1 тогда и только тогда, когда выполняются следующие уравнения:

При SXDH и ADH-SDH, Com, Proof и Sig являются частными случаями примитив определённых в Разделе 2. Отметим, что если бы мы основывались на GS доказательствах для DLIN вместо SXDH, то безопасность наших схем следовала из DLIN, ADH-SDH и AWF-CDH, все из которых можно выполнить для билинейных групп каждого типа (1, 2 и 3) как следует из [21].

Дополнительные свойства доказательств Грота-Сахая

Определим четыре свойства доказательств Грота-Сахая (GS) которые позволят нам определить подписи замены. Для полных выкладок доказательств и дальнейших результатов обращайтесь в [9]. Сперва отметим, что доказательства независимы от правой части уравнения, и если уравнение не содержит пар двух переменных, т.е. для всех i, j в , то они будут даже независимы от значений привязки.

TemplateLemmaIcon.svg Лемма «Лемма 1»
Для любого уравнения выход не зависит от .


TemplateLemmaIcon.svg Лемма «Лемма 2»
Доказательства для уравнений при для всех i, j зависят только от случайных значений в привязках.


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

и доказательством для привязок от Е и доказательством для привязок от Е’, и тогда есть доказательство привязок и уравнения Е’’, определённого как (для переменной ).

TemplateLemmaIcon.svg Лемма «Лемма 3»
Для Е, E’, E’’, указанных выше, если и , то тогда выполняются следующее уравнение:
.


Для заданного доказательства уравнения можно осуществить привязку к его константам и адаптировать данное доказательство. Рассмотрим как в и доказательство для Е и привязок . Тогда будет также доказательством для , определяемым как

и привязок . Т.о. получаем следующее:

TemplateLemmaIcon.svg Лемма «Лемма 4»
Пусть и для всех i, j. Тогда будет содержать в себе доказательство распределения в виде . Аналогичный результат будет для привязки к константе .


Примеры заменяемых подписей

Здесь мы объясним как реализовать заменяемые подписи; из-за экономии места за более детальным анализом и доказательствами обращайтесь в [9]. В [12], [13], схема подписи в слепую строится из схемы Sig (Схема 1) следующим образом. Для заданных параметров и сообщения пользователь выбирает случайное значение и «скрывает» первую компоненту сообщения фактором . Затем он отправляет следующее подписывающему: , привязки и к и , соответственно; доказательства и , доказывающие, что и скорректированные относительно U. С помощью

доказывает , доказывает , а - , которое утверждает, что .

Подписывающий отвечает начиная с «предварительной подписи» на U, определённой в ниже, которую пользователь преобразовывает в подпись и выводит GS доказательство её значения. Теперь для преобразования этого в заменяемую подпись рассмотрим две ключевые особенности.

  1. Значения , которые пользователь отправляет подписывающему можно рассматривать как привязку к сообщению (M, N), которое извлекаемо и рандомизируемо, и которое идеально скрывает сообщение при значениях получаемых для ключа .
  2. Т.к. Com гомоморфен, значения , содержащиеся в привязке С к (M, N), могут быть использованы подписывающим для вычисления привязок к действительной подписи. Более того, ниже мы покажем, как и можно использовать для получения доказательства корректности по Леммам 1, 2, 3 и 4.

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

Привязки к сообщениям. Для задания определим привязку к сообщению как С, указанную выше. Для параметров пространство корректных привязок т.о. будет определяться как:

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

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

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

Т.к. , получаем , что является первым компонентом подписи на (M, N) с случайным значением r + t. Зная t, пользователь может выполнить действительное подписание для (M, N), исходя из предварительной подписи при помощи установки и . тогда будет подписью для (M, N) со случайным значением (c, r + t).

для входа устанавливает и возвращает

имеет на входе pp, C и и возвращает С’. Он заменяет t на t + t’, устанавливая , и . Затем заменяет оставшиеся случайные значения на , устанавливая

выводит

. Группирует попарно С как и sk как x. Если и корректны, то тогда выбирает и и вычисляет следующие значения:

Возвращает

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

Подписывающий затем выбирает и выполняет расчёт оставшихся привязок:

Данный вектор т.о. является привязкой к подписи на (M, N). Остаётся выявить доказательства и для 3 уравнений в – без знания случайных значений и привязок и ! Это можно сделать с помощью следующего:

  1. Уравнение в действительности будет из . Т.к. по и имеют одни и те же случайные значения а и - , и т.к. по Лемме 2 доказательства для являются независимыми от значений привязки, также будет доказательством для и ; т.о. устанавливаем, что .
  2. Леммы 1 и 2 утверждают, что доказательства для (Уравнение ) зависят только от случайных значений привязок. Т.к. и имеют одинаковые случайные значения, будет доказательством не только для , но и также для
(для переменной ) и . Более того, подписывающий, зная A, D, и , может найти доказательство для
(для любого ). Т.к. данное произведение в левой части и в левой части из , то по Лемме 3 будет доказательством для .

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

Пример SmSigCom. Этот алгоритм схож с , но здесь вместо подписания ключа sk идёт задание подписи и ключа извлечения. Он выполняется так же, как и но начинается при этом с непосредственного подписания вместо выполнения процедуры предварительного подписания: выбираем и устанавливаем и , как показано в ; используем ek для извлечения Р и Q из С и установки а также . Теперь и можно вычислить как и в .

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

С и , определёнными в , можно записать это в следующем виде:

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

Т.к. данное произведение левой части и есть левая часть , то по Лемме 3 получаем , что приводит нас к преобразованию доказательств для уравнения и в доказательства для и его сокращённых интерпретаций, и т.о. реализуя наши 4 алгоритма. Отметим, что когда доказательство расширяется новым, оно становиться неравномерно распределённым: по Лемме 3, если Z есть начальное случайное значение доказательства и Z’ есть новое доказательство относительно данного случайного значения, то произведение доказательств будет Z + Z’. Однако, при повторном использовании доказательства его сперва необходимо рандомизировать.

. Доказательство для устанавливает, что

для и , определённых в . Затем он возвращает .

. Данное доказательство будет вида . Алгоритм устанавливает и возвращает (где "" обозначает покомпонентное деление, т.е. умножение каждого компонента на инверсный компонент ).

\mbox{AdC}_{\mathcal{M}}(pp, vk, ((M, N), (t, \mu, \nu, \rho, \sigma)), (c_A, c_B, c_D, c_R, c_S), \tilde{\pi}). Доказательство будет вида . Алгоритм возвращает с

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

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

и и из . Для заданной привязки С к сообщению, привязки к подписи, (X, Y) и доказательству корректности, по Лемме 4 компоненту можно адаптировать к виду для , установив

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

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

TemplateLemmaIcon.svg Лемма «Теорема 1»
По ADH-SDH и SXDH предположению, есть система подписей привязки и проверяемого шифрования, заданного в Определении 1.


Неинтерактивные делегируемые анонимные учётные данные

BCCKLS модель

Функциональность. Кратко опишем модель делегирования учётных данных определённую в [2]. Данная система параметров устанавливается доверенным участником. Каждый пользователь генерирует секретный ключ sk, при помощи которого он может использовать псевдоним . Любой пользователь может стать обладателем соответствующих учётных данных при помощи передачи псевдонима в качестве открытого ключа. Для вывода или делегирования учётных данных, начальный пользователь или простой пользователь выполняют протокол в конце которого пользователю будут представлены учётные данные. Их обладатель может задать доказательство на право обладания учётными данными для любого своего псевдонима, что в свою очередь доказывает факт взаимосвязи псевдонима и учётных данных по открытому ключу .

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

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

Вывод и делегирование выполняется через , который на входе принимает секретный ключ пользователя , псевдоним и соответствующую , уровнь-L учётных данных cred для вывода изначальных при