Просмотр исходного текста страницы Опознавательные составные схемы и схемы с многими подписями основанные на RSA

{{Карточка переведённых статей
|name      = IBMS RSA
|screenshot   = [[Файл:Multi-query Computationally-Private Information Retrieval with Constant Communication Rate.PNG|120px]]
|author    = Ali Bagherzandi<ref group="@:">Department of Computer Science, University of California, Irvine [mailto:zandi@ics.uci.edu zandi@ics.uci.edu]</ref>, <br> and Stanislaw Jarecki<ref group="@:">Department of Computer Science, University of California, Irvine [mailto:stasio@ics.uci.edu stasio@ics.uci.edu]</ref>
|released   = 2010 г.
|license = ?
|website = ?
|status = ?
|transauthor = [[Коллектив проекта|коллектив проекта «Gir»]]
|translation = 2011 г.
|download = [http://gir.openrise.org/data/ksbp_data/pdf/PKC/480-498%20Identity-Based%20Aggregate%20and%20Multi-Signature%20Schemes%20Based%20on%20RSA.pdf оригинал] 
}}
__NUMBEREDHEADINGS__
__TOC__

::'''Аннотация'''. Предлагается новые схемы с идентификационной множественной подписью (IBMS) и совокупной подписью (IBAS), безопасные при RSA предположении. Наши схемы уменьшают циклическую сложность предыдущих RSA-подобных IBMS схем Беллара и Невена <ref name='[BN07]'>Bellare, M., Neven, G.: Identity-based multi-signatures from rsa. In: Abe, M. (ed.) CT-RSA 2007. LNCS, vol. 4377, pp. 145–162. Springer, Heidelberg
(2006)</ref> от 3 до 3 циклов. Как ни странно, но это улучшение реализуется виртуально без каких-либо затрат, т.к. вычислительная эффективность и точная безопасность новой схемы практически идентичны схеме из <ref name='[BN07]'></ref>. Данная новая схема определена с помощью независимого технического устройства, класса доказательств нулевого разглашения знания прообразов однонаправленных функций, которые можно напрямую смоделировать, реализующего параллелизм и хорошую точную безопасность, а также  совокупность, предусматривающую множество параллельных случаев для данных доказательств при коротких мульти/совокупных подписей.

== Введение ==

Протокол множественной подписи позволяет группе участников подписывать одно и то же сообщение с помощью обобщённой короткой строки, называемой мультиподписью, которую можно проверить для набора открытых ключей этих участников. Совокупная подпись это обобщение этого понятия до случая, где каждый участник подписывает потенциально разные сообщения. Такие схемы уменьшают пропускную способность необходимую для передачи подписей, место необходимое для их хранения, и время необходимое для их проверки, от линейного значения числа соподписчиков до константы. Уменьшение пропускной способности особенно важно для устройств с малым потреблением энергии, таких как RFID чипы и сенсоры, которые связаны по энергоёмкому проводному каналу, где передача данных требует в разы больше энергии, чем выполнение арифметических операций (см. пример в <ref name='[BA03]'>Barr, K., Asanovic, K.: Energy aware lossless data compression. In:MobiSys (2003)</ref>). Стандартные мульти-/совокупные подписи уменьшают место занимаемое <math>n ~ \, \! </math> подписями от <math>O (n) ~ \, \! </math> до <math>O(1) ~ \, \! </math>, но проверкам всё ещё необходимы открытые ключи <math>n ~ \, \! </math> подписывающих. Поэтому в приложениях пропускная способность выступает в роли слабого звена протокола будет не лишним рассмотреть идентификационные мульти-/совокупные подписи, где проверяющим необходимы только уникальные идентификаторы подписывающих, например, 32-битный адрес, вместо открытых ключей.

'''Идентификационные (Мульти-/совокупные) подписи.''' Идентификационная криптография<ref name='[Sha84]'>Shamir, A.: Identity-based cryptosystems and signature schemes. In:Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985)</ref> упрощает реализацию открытого ключа с помощью замены открытых ключей пользователей на их идентификатор, например, имя, электронную почту или IP адрес. В идентификационной схеме доверенный участник, Генератор Секретного ключа (PKG), генерирует секретный ключ соответствующий каждому идентификатору пользователя, а подписанные сообщения используя такие ключи можно проверить при помощи идентификатора подписывающего а также главного открытого ключа PKG. В случае идентификационных мульти-/совокупных подписей, если все подписывающие получили секретные ключи посредством одного и того же PFG, то проверяющему необходимо только наличие главного открытого ключа PKG и идентификаторов всех подписывающих. Отметим, что во многих приложениях идентификаторы подписывающих часто включены в протокол сообщений, например, имя пользователя или IP адрес в заголовках пакета, и в таком случае идентификационные мульти-/совокупные подписи добавит постоянное значение пропускной способности для сообщений не прошедших проверку подлинности.

'''Текущее положение дел по данному вопросу'''. Стандартные подписи реализуют идентификационные подписи посредством «сертификационного образца», например, <ref name='[GHK06]'>Galindo, D., Herranz, J., Kiltz, E.: On the generic construction of identitybased signatures with additional properties. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 178–193. Springer, Heidelberg (2006)</ref>, т.е. с помощью простого присоединения открытого ключа подписывающего и сертификата для каждой подписи. Однако, не ясно как применить данную идею для преобразования стандартных мульти/совокупных подписей, например <ref name='[BN06]'>Bellare, M., Neven, G.: Mult-signatures in the plain public-key model and a general forking lemma. In: Conference on Computer and Communications Security, CCS 2006, pp. 390–399 (2006)</ref><ref name='[BCJ08]'>Bagherzandi, A., Cheon, J.H., Jarecki, S.: Multisignatures secure under the discrete logarithm assumption and a generalized forking lemma. In: ACM Conference on Computer and Communications Security, pp. 449–458 (2008)</ref> в идентификационные, потому что не понятно как сгенерировать <math>n ~ \, \! </math> отдельных открытых ключей и сертификатов, даже если подписываются одним и тем же СА. (Стандартные совокупные подписи используются для исключения лишних СА подписей на сертификаты, но это не исключает в свою очередь тоже самое для открытых ключей.)

Первыми эффективными IBAS/IBMS схемами разработанными с нуля были схемы предложенные Гентри и Рамзаном <ref name='[GR06]'>Gentry, C., Ramzan, Z.: Identity-based aggregate signatures. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 257–273. Springer, Heidelberg (2006)</ref>. Их схемы применяли группу с билинейным отображением, на котором основывалась их безопасность, в стандартной модели случайного оракула (ROM), для конкретной стойкости GapDH задачи, где схемы не интерактивны, и для обоих процессов как подписания так и проверки время определяется О(1) возведениями в степень и билинейными операциями отображения. Однако, IBAS схема <ref name='[GR06]'>Gentry, C., Ramzan, Z.: Identity-based aggregate signatures. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 257–273. Springer, Heidelberg (2006)</ref> требует от соподписчиков разделять некоторый символ для каждого набора подписей которые они хотят объединить, а также  каждый соподписчик должен быть уверен что этот символ не использовался ранее в подписании других сообщений, из чего следует, что в некоторых приложениях этой схеме нужен будет дополнительный связующий цикл для того, чтобы участники согласовали новой символ. В последующей работе Болдырёва и др. <ref name='[BGOY10]'>Boldyreva, A., Gentry, C., O’Neill, A., Yum, D.H.: Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing. Cryptology ePrint Archive, Report 2007/438, Revised 21/02/2010 (2010)</ref> (корректирую предыдущую свою работу) представили IBAS схему, которой не требуется эти уникальные символы, но в свою очередь необходим последовательный связующий шаблон, а также она теперь основывается на более сложном предположении билинейного отображения. Отметим, что т.к. последовательная взаимосвязь хорошо изучена для некоторых приложений, например безопасного открытия маршрута <ref name='[KT05]'>Kim, J., Tsudik, G.: Srdp: Securing route discovery in dsr. In: MobiQuitous, pp. 247–260 (2005)</ref>, она вводит дополнительные затраты для взаимосвязи участников, например при вещательном канале или древовидной топологии.

Без использования линейных отображений, Беллар и Невен <ref name='[BN07]'></ref> определили схему IMBS, которая основывается на RSA предположении в ROM. Их схема также обладает быстрой генерацией мультиподписей и проверкой, требующей О(1) возведение в степень, но она выполняется за 3 цикла итераций. Отметим, что любая 3-цикловая IBMS реализует 4-цикловую IBAS если все соподписчики сообщений будут передающими, а схема IBM выполняется при их взаимосвязи. (Более того, в IBMS схеме <ref name='[BN07]'></ref> это передача может дополнять первый цикл протокола, для заданной 3-цикловой IBAS схемы.) Однако, такая передача всех сообщений всем соподписчикам подразумевает использование пропускной способности, которая бы не потребовалась в противном случае, и т.о. уходя от обобщённого представления было бы интересно изучить IBAS схемы, которым не требуется такая передача.  (В качестве локального замечания хотелось бы отметить, что 3-цикловую IBMS схему <ref name='[BN07]'></ref> можно преобразовать в 3-цикловую IBAS схему без таких передач, например, используя идеи схожие для нашей IBAS схемы <ref name='[BJ10]'>Bagherzandi, A., Jarecki, S.: Identity-based aggregate and multi-signature schemes based on RSA (full version) (2010)</ref>.)

{|border="0" align="center" 
|-
|
{| class="wikitable" width="700px"
|+ Таблица №1
|-
! IBAS/IMBS Схемы
! Соответствующая задача (1)
! Упрощения (2)
! Число циклов
! Время проверки (3)
! Время подписания (3)
! Длинна подписи (4)
|-
| <br>
| <br>
| <br>
| <br>
| <br>
| <br>
| <br>
|-
|}
|}

'''Таблица №1'''. 
:*(1) Все схемы задают доказательство безопасности только в ROM модели; 
:*(2) IBAS схема <ref name='[GR06]'></ref> предполагает, что участники разделяют уникальный и общий символ для каждого выполнения IBAS схемы. Это требование можно избежать за счёт затрат на дополнительный цикл итерации, т.к. схеме <ref name='[BGOY10]'></ref> требуется последовательная совокупность; 
:*(3) Время подписания оценивается для каждого участника. Для обоих случаев затрат на подписание и проверку, <math>P ~ \, \! </math> есть затрата на одну парную операцию, а М есть затрата на скалярное умножение на эллиптической кривой, и <math>E ~ \, \! </math> это затрата на (мульти-) возведение в степень в   (с примерно 80-битными экспонентами); 
:*(4) Длинна подписи оценивается в битах, где <math>k ~ \, \! </math> это параметр безопасности, <math>n ~ \, \! </math> это модель RSA, <math>l ~ \, \! </math> верхняя граница количества участников,   и   - две группы точек эллиптической кривой с ассиметричным билинейным отображением, <math>G ~ \, \! </math> это группа точек эллиптической кривой с симметрическим отображением, а |A| определяет размер в битах представления элементов в группе <math>A ~ \, \! </math>. Типичные значения для этих параметров будут <math>k = 160 ~ \, \! </math>, <math>|G_1| = 160 ~ \, \! </math>, <math>|G| = 512 ~ \, \! </math>, <math>\log l = 20 ~ \, \! </math>, и <math>|Z^*_n| = 1024 ~ \, \! </math> либо <math>2048 ~ \, \! </math>

'''Наш вклад'''. Мы предлагаем IBMS и IBAS схемы безопасные при RSA предположении в ROM которым необходимы только два цикла взаимосвязи. Это выявляет альтернативы для IBAS/IMBS схем основанных на билинейном отображении в особенности в приложениях, в действительности выполняются за два связующих цикла, таких как открытие аутентифицированного маршрута либо объединение вещаемых подтверждений. Т.к. операции билинейного отображения более ресурсоёмки чем RSA возведение в степень, наши вычислительные затраты будут немного меньше для подписания и значительно меньше для проверки, по сравнению с примером из [GR06], хотя в то же время наши подписи будут длиннее. Обобщение этих сравнений показано на рисунке 1.

'''Дальнейшая соответствующая работа.''' Грегори Невен представил два примитива, последовательные совокупные подписанные данные и мульти-подписанные данные, относящиеся к совокупным подписям и мультиподписям соответственно, целью которых было представить минимальную общую пропускную способность получаемую посредством подписей и сообщений участвующих в передаче аутентифицированных данных исходящих из нескольких источников <ref name='[Nev08]'>Neven, G.: Efficient sequential aggregate signed data. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 52–69. Springer, Heidelberg (2008)</ref>. Его конструкции использовали методы восстановления сообщения для сжатия бит сообщения в (мульти/совокупную) подпись. Сравнивая его работу с нашей, отметим, что: 
:*(1) его схемы поддерживают только последовательную совокупность при подписании различных сообщений; 
:*(2) пропускная способность сохраняющихся значений зависит от размеров сообщения (для малых сообщений пропускная способность может быть хуже чем для стандартных подписей); 
:*(3) эти схемы не принимают во внимание излишние затраты в связи с применением открытых ключей, из-за которых возникает вопрос можно ли в последствии уменьшить общее значение для пропускной способности относительно подписей и сообщений, возможно при помощи методов восстановления сообщения, с идентификационные мульти-/совокупные подписи. В другой соответствующей работе Херранза и Галиндо и др.<ref name='[Her06]'>Herranz, J.: Deterministic identity-based signatures for partial aggregation. Comput. J. 49(3), 322–330 (2006)</ref><ref name='[GHK06]'></ref> показываются идентификационные подписи, которые могут быть совмещены если они были исходными для одного и того же подписывающего.

'''План работы.''' Раздел 2 содержит техническую оценку нашей конструкции. В Разделе 3 мы определяем IBMS схемы. (Формальное определение схем IBAS мы не даём в силу его наличия в <ref name='[BJ10]'></ref>.) В Разделе 4 показана разработка наших приспособлений, а именно, представлены структурированные доказательства (ZK) нулевого разглашения и <math>\Sigma ~ \, \! </math> - эквивалентные привязки а также показано, что <math>\Sigma ~ \, \! </math> - эквивалентные привязки достаточны для компиляции класса <math>\Sigma ~ \, \! </math> - протоколов, который включает в себя RSA-подобный идентификационный протокол, доказательство знания е-ого корня, для прямолинейного симулируемого структурированного ZK. В Разделе 5 показаны гомоморфные <math>\Sigma ~ \, \! </math> - эквивалентные привязки безопасные при RSA. Из результатов Раздела 4 реализуется совокупное структурированное ZK доказательство знания <math>e ~ \, \! </math>-ого корня, что приводит к получению конструкции IBMS схемы, описанной в Разделе 6, и IBAS схеме отмеченной в Разделе 7.

== Техническая оценка ==

Наша IBAS/IBMS схема будет вариацией подписи Гуиллоу-Куискватера для нескольких доказывающих. ID-подобная версия GQ подписи будет не интерактивным доказательством нулевого разглашения (NIZK) знания (PK) е-ого корня по модулю n (в ROM). Пусть <math>y = H (ID) ~ \, \! </math> будет элементом из <math>Z^*_n ~ \, \! </math> и пусть <math> x ~ \, \! </math> это е-ый корень <math>y ~ \, \! </math>, секретный ключ соответствующий идентификатору ID. (Такой секретный ключ можно вычислить PKG которому известна факторизация <math>n  ~ \, \! </math>.) Для подписания сообщения m, подписывающий с идентификатором ID следует ROM-подобному NIZK KP е-ого корня <math>y ~ \, \! </math>: Он вычисляет первое сообщение доказательства <math>a=k^e ~ \, \! </math> для случайного <math>k ~ \, \! </math> в <math>Z^*_n ~ \, \! </math>, и получает с запрашивая <math>(m,a) ~ \, \! </math> у хэш функции (определённой как случайный оракул) и вычисляет ответ <math>z ~ \, \! </math> на этот запрос <math> z=kx^e~ \, \! </math>. Подписью будет <math>(a, z) ~ \, \! </math>  проверяемое с помощью выявления будет ли <math> z^e=ay^e ~ \, \! </math>.  для <math>c=H(m,a) ~ \, \! </math>. Согласно гомоморфному свойству возведения в степень можно попробовать получить IBAS/IBMS схему с помощью объединения таких ROM-подобный NIZK ZK е-ых корней выводимых несколькими соподписчиками. К примеру, рассмотрим 2-циклический протокол построенный в соответствии с DL-подобной схемой мультиподписи <ref name='[MOR01]'>Micali, S., Ohta, K., Reyzin, L.: Accountable-subgroup multisignatures. In: ACM Conference on Computer and Communications Security, CCS 2001 (October 2001)</ref>: В первом цикле каждый участник  передаёт своё первое сообщение  . Все участники получают общее значение с запрашивая хэш функцию для входа включающего <math> a=\prod a_i ~ \, \! </math> и подписываемого сообщения. Наконец, каждый участник отправляет свой ответ <math>z_i ~ \, \! </math> на этот запрос. Мультиподписью будет <math>(a,z) ~ \, \! </math>  где <math>z=\prod z_i ~ \, \! </math>. Отметим, что если <math> z^e_i=a_i y^e_i ~ \, \! </math> для каждого <math> i ~ \, \! </math> то  <math> (a, z) ~ \, \! </math> удовлетворяет оценку проверки <math> z^e = a \left ( \prod \right )^e ~ \, \! </math> где <math> y_i = H(I D_i) ~ \, \! </math>. Адаптация доказательства безопасности <ref name='[MOR01]'></ref> выявит доказательство для данной схемы, но результирующий аргумент безопасности будет иметь некоторые ограничения: 
:* (1) Упрощение будет только для задачи ожидаемой стойкости RSA; 
:* (2) мы сталкиваемся с существенным уменьшением безопасности в связи с широким использованием обратных преобразований; 
:* (3) В следствии этого расширение не применимо к нескольким выполнениям данной схемы.

Для объяснения того как мы преодолеваем эти ограничения нам нужно сперва объяснить, почему они появляются в вышеуказанной схеме. Симулятор для NIZK PK е-ого корня выбирает случайное значение с и случайное <math>z  ~ \, \! </math> в <math>Z^*_n ~ \, \! </math>, вычисляет первое сообщение как <math>a=z^e y^{-e} ~ \, \! </math> и определяет хаш от <math>(a,m) ~ \, \! </math> как с т.к. оно влияет на хэш функцию <math>H  ~ \, \! </math>. Отметим, что т.к. злоумышленник не обладает информацией о а, будет только пренебрежимо малый шанс того, что он запросит Н для такого же <math>(a, m)  ~ \, \! </math> перед тем как симулятор выявит определение его значения с, и следовательно, симулятор заканчивает работу успешно с преобладающей вероятностью. Фундаментальное различие между данной симуляцией и симуляцией для совокупного доказательства в вышеуказанной схеме будет в том, что совокупное доказательство не реализует для соподписчиков выбор вносимых ими значений <math>a_i  ~ \, \! </math> для базиса <math>a_i  ~ \, \! </math> передаваемого доверенными соподписчиками. Следовательно, симулятор может только выдвигать предположение о результирующем а значении с вероятностью <math>1/q_h ~ \, \! </math> где <math>q_h ~ \, \! </math> это число хэш запросов производимых злоумышленником. Это расширяет процедуру симуляции, в которой пересматривается ожидаемое значение злоумышленником <math>q_h  ~ \, \! </math> раз для каждого случая подписи, что вызывает в свою очередь ограничения отмеченные выше: сокращение ожидаемой стойкости, сокращение безопасности, и не существование аргумента для безопасности одновременных примеров протокола.

Беллар и Невен <ref name='[BN07]'></ref> показали, как преодолеть эти трудности в ROM модели с помощью добавления дополнительного вычислительного цикла а котором каждый участник сперва связывает своё вносимое значение <math>a_i  ~ \, \! </math>  с помощью передачи Хэш <math>H(a_i) ~ \, \! </math> . Контролируя хэш функцию <math>H   ~ \, \! </math> симулятор может узнать связанное значение <math>a_i  ~ \, \! </math> в качестве злоумышленника и затем решить разрешить всё для части доверенных участников которым было передано <math>a_i  ~ \, \! </math> . Таким способом данный симулятор работает без повторного рассмотрения значений с преобладающей вероятностью, аналогично симуляции NIZK указанной выше. Основной методикой, которой мы пользуемся в данной работе является выявление получения такой прямолинейной симуляции не использующей дополнительного связующего цикла, т.е. симуляцию только с двумя циклами итерации. Наша методика будет вариантом HVKZ-в-ZK компиляции Дамгарда [Dam00] строит прямолинейное симулируемое доказательство нулевого разглашения из любого <math>\Sigma  ~ \, \! </math> -протокола используя эквивалентную схему привязки, но в нашем случае которая представляется немного другим образом: В схеме Дамгарда подписывающий связывает своё значение <math>a_i  ~ \, \! </math>  используя схему эквивалентной привязки, и симулятор, который для любого с может раскрыть эту привязку и выявить значение <math>a_i = z^e_i y^{-e}_i  ~ \, \! </math> необходимое для проверки доказательства (где ответ <math>z_i  ~ \, \! </math>  выбирается случайным образом, чтобы соответствовать ответному распределению в действительном доказательстве). Однако, для создания IBMS/IBAS схемы с помощью совокупности таких доказательств нам необходимо, чтобы эта схема привязки была мультипликативно гомоморфна и насколько нам известно, пока ещё не существует такой эффективной схемы привязки которая обладала бы как свойством неопределённости так и мультипликативной гомоморфности. Вместо этого, покажем схему привязки которая будет мультипликативно гомоморфна над <math>Z^*_n  ~ \, \! </math> и удовлетворяет упрощённой неопределённости, которую мы назовём <math>\Sigma  ~ \, \! </math> -неопределённость, и которая удовлетворяет соответственной симуляции <math>\Sigma  ~ \, \! </math> -протокола указанного выше. К примеру, <math>\Sigma ~ \, \! </math> -неопределённая привязка для отношения <math>R =\begin{Bmatrix} (x,y)|y=x^e \end{Bmatrix}  ~ \, \! </math>  реализуется для неопределённости привязок к сообщениям вида <math>z^e y^{-e} ~ \, \! </math> для любых <math>z ~ \, \! </math> и <math>c ~ \, \! </math>, и т.о. это будет в точности вид сообщения а, которое требуется вышеуказанному симулятору для доказательства.

Идея использования привязок с аналогично упрощённой неопределённостью появилась в<ref name='[BCJ08]'></ref>, где она использовалась для построения прямолинейного симулируемого и совокупного доказательства DL знания и DL-подобной схемы мультиподписи. Однако, понятие неопределённости (и данной конструкции)<ref name='[BCJ08]'></ref> реализуется только для прямолинейных доказательств нулевого разглашения. Интуитивно понятно, что этого достаточно для безопасности мультиподписей т.к. при реализации мультиподписи злоумышленник без потери общности взламывает всех участников за исключением одного, т.о. симулятору необходимо включить свою задачу для получения только одного открытого ключа, и смоделировать протокол мультиподписи для оставшейся части участников исключая этого одного. Используя данный вид неопределённости в аргументе безопасности для идентификационных схем будет проявляться сокращение безопасности относительно фактора <math>q_H ~ \, \! </math>, числа запросов хэш функций, в связи с тем, что симулятору нужно будет предполагать значение простой идентификации при котором его значение инкапсулируется. Здесь мы определим более общее понятие <math>\Sigma ~ \, \! </math>-неопределённости которое позволит применимо для прямолинейных симулируемый «структурированных» доказательств нулевого разглашения в CRS модели: Для структурированных доказательств нулевого разглашения, обобщённых в данной работе, симулятор моделирует любое заключение из соответствующего класса, отличному от простого утверждения в ZK и любого примера в (стандартной) ZK. Это будет класс примеров, которые в частности полезны для выявления сокращения безопасности у IBMS/IBAS схемы основанной на <math>\Sigma ~ \, \! </math>-протоколе для доказательства знания прообраза функции <math>f(x)=x^e ~ \, \! </math> являющегося примером вида <math>y = \dot{y} f(\delta) ~ \, \! </math>, где <math> \dot{y} ~ \, \! </math> это значение выводимое симулятором. В таком виде симулятор может вставлять своё значение в любое количество идентификаторов, выбирая случайное   для каждого идентификатора, до тех пор пока не будут смоделированы доказательства выполнимые оставшейся частью участников относительно общего их числа параллельно. Т.о. наш основной технический метод будет разбит на 2 части: Во-первых, обобщается понятие <math>\Sigma ~ \, \! </math>-неопределённости и применяется в выполнении <math>\Sigma ~ \, \! </math>-протоколов при прямолинейного симулируемого структурированного ZKPK (Раздел 4). Во-сторых, мы строим мультипликативно гомоморфную и  -неопределённую схему привязки основанную на RSA задаче (Раздел 5). Вместе эти две части составляют реализацию IMBS и IBAS схем представленных в данной работе (Раздел 6 и Раздел 7).

== Идентификационные мульти/совокупные схемы подписи ==

Выявим понятие идентификационной схемы мультиподписи (IBMS) построенной на определениях заданных в <ref name='[MOR01]'></ref><ref name='[BN06]'></ref><ref name='[GR06]'></ref><ref name='[BN07]'></ref>. (В связи с экономией места расширенные определения схем IBAS представлены в полной версии данной работы.) Наше понятие будет более гибкое чем <ref name='[MOR01]'></ref><ref name='[BN06]'></ref><ref name='[BN07]'></ref> потому что нам не требуется набор идентификаторов участников в виде входа для мульти/совокупного протокола подписи. Распределённые участники должны знать о выполнении протокола другим участником, но в таком случае необходимо лишь корректное задание связности, а их индексы не требуются для входа криптографического протокола. Эти схемы безопасны при данной предложенной гибкости для приложений мульти/совокупных подписей потому что в какое-либо время подписывающий оперирует только подписываемым сообщением и не принимает во внимание идентификаторы соподписчиков. В противном случае список соподписчиков всегда будет сопоставим с подписываемым сообщением.

'''Синтаксис IBMS схемы'''. Определим идентификационную мультиподпись как <math>IBMS= (Setup, KeyDer, MSign, Vrfy)~ \, \! </math>, где <math>Setup, KeyDer~ \, \! </math> и <math>Vrfy~ \, \! </math> будут вероятностными полиномиально сложными алгоритмами, а <math>MSign~ \, \! </math> будет распределённым протоколом выполняемым множеством участников.
:* <math>(mpk, msk) \longleftarrow Setup (1^k) ~ \, \! </math> выполняется доверенным участником, при входном параметре безопасности <math>k ~ \, \! </math>, генерируется главный открытый ключ <math>mpk ~ \, \! </math> и соответствующий главный секретный ключ <math>msk ~ \, \! </math>.
:* <math>sk_{Id} \longleftarrow KeyDer (msk, Id) ~ \, \! </math> выполняется доверенным участником, при входном главном секретном ключе <math>msk ~ \, \! </math> и идентификаторе <math>Id \in \begin{Bmatrix} 0, 1 \end{Bmatrix}^* ~ \, \! </math> определяющем секретный ключ <math>sk_{Id} ~ \, \! </math>  для пользователя с идентификатором ID.
:* <math> MSign ~ \, \! </math> это протокол мультиподписи выполняемый группой участников которые хотят подписать некоторое сообщение m. Участник с идентификатором ID выполняет этот протокол для открытого входного mpk и сообщения m, и секретного входа <math>sk_{Id} ~ \, \! </math>, который является его собственным секретным ключом. Локальный выход протокола для каждого участника будет мультиподписью обозначенной как  .
:* <math>\begin{Bmatrix} 0, 1 \end{Bmatrix} \longleftarrow Vrfy (mpk, m, IdSet, \sigma) ~ \, \! </math> проверяет будет ли   корректной мультиподписью сообщения <math> m ~ \, \! </math>  для оставшегося набора идентификаторов <math> IDSet ~ \, \! </math>.

В модели случайного оракула (ROM), <math> KeyDer, MSign ~ \, \! </math> и <math> Vrfy ~ \, \! </math> процедуры дополнительно имеют доступ к случайному оракулу <math>H(\cdot) : \left \{ 0,1 \right \} \longrightarrow D ~ \, \! </math>, где <math>D ~ \, \! </math> зависит от схемы. Этот набор процедур должен удовлетворять следующим свойствам полноты: Для любого целого <math>n ~ \, \! </math>, любого сообщения <math>m ~ \, \! </math>, и любого <math>(mpk, msk) ~ \, \! </math>  выводится <math>Setup(1^k) ~ \, \! </math>, если для <math>i= 1 ... n ~ \, \! </math>, получается <math>sk_{Id} \longleftarrow KeyDer(msk, Id_i) ~ \, \! </math> и корректно выполняется MSign для входа m используя секретные ключи <math>sk_{Id} ~ \, \! </math>, тогда предполагается что все сообщения проходят между участниками, каждый участник выводит одинаковую строку <math>\sigma ~ \, \! </math> которая удовлетворяет <math>Vrfy (mpk, m, \begin{Bmatrix} Id_1, ..., Id_n \end{Bmatrix}, \sigma) ~ \, \! </math>

'''Понятие безопасности для IBMS схемы'''. Мы моделируем безопасность в виде существующей стойкости при адаптивно выбираемом сообщении и адаптивно выбираемой идентификационной атаки: Злоумышленник участвующий в игре, в которой он запрашивает количество дифференцированных ключей и запросов подписи. При запросе дифференцированного ключа злоумышленник взламывает участника путём выявления его идентификатора Id для оракула дифференциации ключа и получает его секретный ключ <math>sk_{Id} ~ \, \! </math>. При запросе подписи злоумышленник выявляет сообщение m и идентификатор <math>Id ~ \, \! </math> которыми он хочет оперировать; а оракул подписания выполняет <math>MSign ~ \, \! </math> протокол относительно сообщения <math>m ~ \, \! </math> для оставшихся <math>Id ~ \, \! </math>. Злоумышленник побеждает в игре если он в действительности выводит сообщение m, мультиподпись  <math> \sigma ~ \, \! </math>, и набор идентификаторов <math>IdSet ~ \, \! </math> такой, что <math>Vrfy (mpk, m, IdSet, \sigma) =1 ~ \, \! </math> и существует идентификатор <math>Id ~ \, \! </math> такой, что злоумышленник никогда не сможет запросить оракул дифференциации ключа для <math>Id ~ \, \! </math> и оракул подписания для <math>(m, Id) ~ \, \! </math>. Более формально определим преимущество злоумышленника <math>A ~ \, \! </math>для <math>IBMS = (Setup, KeyDer, MSign, Vrfy) ~ \, \! </math> как вероятность что эксперимент <math> Exp^{uu-cma}_{IBMS} (A) ~ \, \! </math> описанный в Рис. 2 выведет 1, т.е.


<center><math>Adv^{uu-cma}_{IBMS} (A) = Pr [Exp^{uu-cma}_{IBMS} (A) = 1] ~ \, \! </math></center>


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

Назовём IBMS схему <math>(t, \epsilon, n, q_K, q_S) ~ \, \! </math> - безопасной если <math>Adv^{uu-cma}_{IBMS} (A) \ge \epsilon ~ \, \! </math> для любого злоумышленника <math>A ~ \, \! </math>, который выполняет всё за время не больше <math>t ~ \, \! </math>, и делает не более <math>q_s ~ \, \! </math> запросов дифференциации ключа, а также не более запросов подписи, и производит взлом не более чем <math>n ~ \, \! </math>оставшейся части участников. В модели случайного оракула мы расширяем это понятие до <math>(t, \epsilon, n, q_K, q_S, q_H) ~ \, \! </math> - безопасности, где <math>A ~ \, \! </math>аддитивно упрощается до не более <math>q_H ~ \, \! </math> хэш запросов и вероятность в эксперименте если <math>Adv^{uu-cma}_{IBMS} (A) ~ \, \! </math> также получается для случайного выбора хэш функции.

{{Пример| Эксперимент <math>Exp^{uu-cma}_{IBMS} (A) ~ \, \! </math>|
* <math>(mpk, msk) \longleftarrow Setup(1^k); MldLst \longleftarrow \empty ; CldLst \longleftarrow \empty ~ \, \! </math>
* Выполняется <math> А(mpk) ~ \, \! </math>, <math>A ~ \, \! </math> оперирует дифференциацией ключа и запросами подписи следующим образом:
* Для запроса дифференциации ключа и идентификатора <math>Id ~ \, \! </math>, добавляем <math>Id ~ \, \! </math> в <math>CldLst ~ \, \! </math>, выполняем <math>KeyDer ~ \, \! </math> для входного <math>(msk, Id) ~ \, \! </math>  и возвращаем <math>sk_{Id} ~ \, \! </math> к <math>А ~ \, \! </math>.
* При запросе подписания для пары <math>(m, Id) ~ \, \! </math>, добавляем <math>(m, Id) ~ \, \! </math>  к <math>MldList ~ \, \! </math>, выполняем <math>MSign ~ \, \! </math> протокол для оставшейся части идентификаторов <math>Id ~ \, \! </math> при сообщении <math>m ~ \, \! </math> отправляя сообщения от и к <math>A ~ \, \! </math>.
* Когда <math>A ~ \, \! </math> останавливается выводим его парные значения в виде <math>(m, IdSet, \sigma) ~ \, \! </math>.
* Если <math>(Vrfy(mpk, m, IdSet, \sigma)=1) \land (\exists Id \in IdSet) ~ \, \! </math> такой, что <math>(Id \notin CldLst) \land ((m, Id) \notin MldLst) ~ \, \! </math> то возвращаем 1, в противном случае возвращаем 0.
}}

Рис. 2. Атака на выбранное сообщение для Идентификационной схемы мультиподписи

== <math> \Sigma </math> - неопределённые привязки и структурированное нулевое разглашение ==

Гомоморфные  <math> \Sigma </math> - протоколы. <math> \Sigma       ~ \, \! </math> -протокол,понятие представлено Крамером, Дамгардом и Шенмакерсом [CDS94], будет трехступенчатой системой доказательства с определённым доверенным верификатором нулевого разглашения (HVZK) и свойствами стойкости. Пусть <math>  R=\{ (x,y) \}     ~ \, \! </math>  будет отношение принадлежность которого можно проверить за оплиномиальное время. Рассмотрим частный случай, где X и Y будут алгебраическими группами (для общей простоты используем мультипликативные понятия для обоих), а  <math>   R=\{ (x,f(x)) | x \in X \}    ~ \, \! </math>, где <math>    f : X \rightarrow Y   ~ \, \! </math>  есть гомоморфная однонаправленная функция. Рассмотрим доказательство знания системы для отношения <math>    R   ~ \, \! </math>, что мы назовём гомоморфным  <math>    \Sigma   ~ \, \! </math>-протоколом (для R): доказывающий при входе <math>    x \in X   ~ \, \! </math>  отправляет <math>     a= f(k)  ~ \, \! </math>, где  <math>  k^r \leftarrow X     ~ \, \! </math>. Проверяющий для входа <math>    y \in Y   ~ \, \! </math>  создаёт значение с в виде случайной k-битовой строки, а доказывающий отвечает на это  <math>   z=kx^c    ~ \, \! </math>. Проверяющий принимает его тогда и только тогда когда  <math>    f(z)=ay^c   ~ \, \! </math>. Это является видом некоторых  <math>    \Sigma   ~ \, \! </math>-протоколов для известных гомоморфных однонаправленных функций, например, идентификационная схема Гуиллоу-Куискуатера [GQ88] для степенной функции <math>  f_{e,n}(x)=x^e  mod n   ~ \, \! </math>  и схема Шнорра [Sch89] для экспоненциальной функции  <math>    f_{g,p}(x)=g^x mod p  ~ \, \! </math>. Особенное свойство HVZK  <math>   \Sigma    ~ \, \! </math>-протокола указывает, что существует эффективный симулятор, который для входа y вычисляет пару <math>   (a,z)    ~ \, \! </math> для любого с с распределением совпадающим с распределением доказывающего. Специальное свойство стойкости определяет, что существует эффективный экстрактор, который вычисляет свидетельство x такое, что <math>    (x,y) \in R   ~ \, \! </math>  для любого у из любой пары допустимых взаимодействий <math>    (a,c,z)   ~ \, \! </math> и <math>    (a,c',z')    ~ \, \! </math> таких, что  <math>     c \neq c'  ~ \, \! </math>.

'''Структурированное нулевое разглашение.''' Многозадачное нулевое разглашение в общей модели связующей строки требует наличия двухэтапного вероятностного полиномиально сложного симулятора такого, что (1) будет первым этапом для заданных параметров безопасности; (2) на втором этапе, для заданного определение и лазейки, симулятор выводит смоделированное доказательство для заданного утверждения. Для однозадачного ZK симулятор знает изначальное определение и может установить CRS строку в виде функции от частных значений. Структурированное доказательство нулевого разглашения для отношения R представленного выше будет понятием: Симулятору дано «исходное определение»  <math>   y \in Y    ~ \, \! </math> до установления им строки СRS, и затем он моделирует доказательство для определения <math>   y=y \cdot f(\delta)    ~ \, \! </math>  для любого  <math>     \delta \in X  ~ \, \! </math>. Здесь формальное определение будет:

'''Определение 1.''' Пусть <math> X, Y       ~ \, \! </math> будут алгебраическими группами и <math>  f : X \rightarrow Y     ~ \, \! </math>  будет сюръективной гомоморфной однонаправленной функцией, все значения индексируются с помощью открытого параметра par. Пусть  <math>    \Pi = (G,P,V)   ~ \, \! </math>  будет доказательством системы в CRS модели для отношения    где   это алгоритм, который выводит общую связующую строку. Говорим, что П будет прямолинейным структурированным нулевым разглашением если существуют эффективные алгоритмы   такие, что   для входа par и исходного примера   выводит CRS строку   и лазейку td, а т.к.   для входа td и «свидетельства»   выводит  моделируемое доказательство   для случая  , а для    таких, что   выполняются следующие два свойства:
1.	Статистическая разность между двумя следующими распределениями будет не более е:
2.	для   проверяющего   и   следующие два распределения идентичны:

'''Схемы привязки.''' Схема привязки С в CRS модели состоит из вероятностный полиномиально сложных алгоритмов   и   для входа в виде параметра безопасности k, генерирует открытые параметры cpar, которые также определяют пространство привязки сообщения   генерирует ключ привязки   генерирует привязку С и определение обратного её значения D для сообщения  , и наконец,   определяет является ли D корректным для привязки С сообщения m. Схема привязки должны удовлетворять том, что если    и  , тогда  1. Нише мы определим статистическое сокрытие и вычислительное задание свойств привязок, потому что есть различные вариации для который наша схема удовлетворительна.

е-Сокрытие: Для всех   и  , существует менее чем е статистическая разница между распределением выхода С посредством   и распределением  выхода С посредством   Схема привязки в таком случае будет полностью скрываема если е = 0.

(t,e)-Задание: Для любого алгоритма А оперирующего за полиномиальное время t и любого cpar выводим с помощью  , вероятность   и   будет не более чем е, где  выводятся А для входа К и   для вероятности при подбрасывании монеток CKG и А.

Понятие: В данной работе мы имеем дело только со схемами привязки в которых привязкой является детерминистическая функция от сообщения и его значения получаемого при обратном вычислении привязки. Поэтому мы полагаем, что существует пространство обозначенное как R и Com процедура выбирающая обратное значение привязки   и вычисляющая привязку С представленную в виде детерминистической функции от m и D.

'''неопределённые привязки.''' Схема привязки является неопределённой,  если существует эффективный симулятор, который генерирует ключ привязки К, неразличимый по признакам от реального ключа, вместе с лазейкой td. Лазейка позволяет симулятору создавать ложные привязки неразличимые по признакам от действительных, а затем вычислять обратное значение их привязки для любого сообщения. Используя неопределённые привязки, можно выполнить  -протокол для многовариантной системы ZK доказательства с помощью прямолинейной симуляции [Dam00]. Здесь определяется более упрощённый вид неопределённости называемый  -неопределённостью и показывается, что од достаточен для выполнения  -протоколов для структурированных ZK доказательств с прямолинейной симуляцией. Выявляется, что структурированной ZK достаточно для нашего приложения ZK доказательств для мульти/совокупных подписей и при этом многовариантное ZK не требуется. Более того, прямолинейная симуляционность данной системы позволяет получить мульти/совокупные схемы с параллелизмом, и более лучшей точной безопасностью а также улучшенной циклической сложностью.

'''Определение 2.''' Пусть Х и Y будут алгебраическими группами и   будет гомоморфной однонаправленной функцией, все значения индексируются с помощью открытого параметра par. Говорим, что схема привязки е- -не определена для f если существуют вероятностные полиномиально сложные алгоритмы   и  , где    и   такие, что для любого cpar выводимого   и любого   выполняются следующие два свойства:
1.	Статистическая разность между двумя распределениями К выводимого   и К выводимого   будет не более е
2.	Для всех   и  , если   выводится   и   будет получать на выходе при  , что   различим по признакам от случайного распределения R и  

Интуитивно понятно, определение 2 утверждает, что неопределённая  процедура для заданных   может определять фальшивые привязки сообщения вида   для некоторого z. Это полезно при прямолинейной симуляции доказательства знания для отношения   К примеру, пусть  , где  . Рассмотрим HVZK симулятор  -протокола для доказательства знания е-ого корня: Этот симулятор выбирает случайные с и z и вычисляет первое сообщение доказывающего  . Ниже мы покажем выполнение Дамгарда [Dam00] (см. Рис. 3 ниже) преобразовывающее такой  -протокол в структурированное нулевое разглашение используя только заданные  -неопределённые привязки, т.к. симулятор может вывести ложную привязку и затем выявить какой именно симулятор  -протокола будет иметь на выходе аналог первого сообщения доказывающего т.е.  . Определение 2 подразумевает по собой то, что ложная привязка может быть выявлена для   для любого   и с. Следовательно структурированный симулятор нулевого разглашения может использовать это свойство для моделирования доказательства любого значения  , где   устанавливается до создания симулятором строки CRS (см. теорему 1).

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

Рис. 3. Прямолинейное симулируемое структурированное ZKPK прообраза f

'''Гомоморфные привязки.''' Назовём схему привязки мультипликативно гомоморфной если существуют эффективно вычисляемые операции   и   такие, что   и  , тогда   для   и  . Согласно этому схема привязки будет l-сокращённой мультипликативно гомоморфной если гомоморфная операция реализует не только l пар привязка – обратное значение привязки генерируемых процедурой Com. Наша конструкция будет l-сокращённой мультипликативно гомоморфной.

Структурированное нулевое разглашение для гомоморфного  -протокола. На Рис. 3 показана конструкция прямолинейного симулируемого структурированного доказательства нулевого разглашения знания системы, в CRS модели, для гомоморфного  -протокола и  -неопределённой привязки. Она идентична конструкции компилятора Дамгарда для  -протокола при ZKPK доказательстве [Dam00]. Ниже мы покажем, что используя только  -неопределённых привязок будет реализовываться то же самое структурированное доказательство нулевого разглашения для заданного гомоморфного  -протокола. Как в [Dam00] результирующий протокол будет аргументом знания, субъективным по свойству задания схемы привязки.

'''Теорема 1.''' Пусть Х и Y будут алгебраическими группами и   будет гомоморфной однонаправленной функцией, С это  -неопределённая привязка над пространством сообщений  . Тогда протокол на рис. 3 будет прямолинейным симулируемым структурированным доказательством нулевого разглашения знания прообраза f в CRS модели.

Доказательство. Прямолинейный симулятор   для структурированного доказательства нулевого разглашения ведёт себя следующим образом: На первой фазе задаётся cpar и   выполняется   для получения (td,K) и устанавливается общая связующая строка   в виде К. На второй фазе, для заданного td и свидетельства   выполняется   для получения ложной привязки   и st а затем   отправляется проверяющему. При получении значения с от проверяющего   выполняет   для получения ответа z и ложной привязки  . Согласно свойству  -неопределённости (определение 2) из этого всего следует, что S удовлетворяет условиям определения 4.

==	Совокупное доказательство нулевого разглашения знания е-ого корня==

'''Безопасное RSA предположение.''' Т.к. наша конструкция основывается на двух соответственных связанных вариациях RSA криптосистем, который разделяют некоторый RSA модель n, но используют две различные открытые экспоненты е и е’, то для нас будет удобным использование следующих понятий для обобщения RSA примеров: Назовём алгоритм   безопасным RSA генератором если для входного параметра безопасности k и простого е таких, что   генерирует пару (n,d), где (1)   и p, q, p’ и q’ будут простыми числами, такими, что   и   и (2)  . Для дальнейшего использования мы определим  . Преимущество алгоритма А во взломе RSA(e) задачи будет определяться как (1)

Говорим, что алгоритм А (t,e)-взламывает RSA(e) задачу для параметра безопасности k, если А выполняет вычисления за время не более t и  . Говорим, что RSA(e) задача является (t,e)-стойкой (для параметра безопасности k) если нету такого алгоритма А, который (t,e)-взламывает её. Отметим, что требование   это просто нижняя границы которую мы представили для предоставления любому участнику выбор «второй» открытой экспоненты е’ такой, что   и   где l это максимальное число участников в любом простом примере схемы мультиподписи.


===	RSA-подобная мультипликативно гомоморфная  -неопределённая привязка===

Пусть е и е’ будут двумя простыми числами такими, что   и   для некоторого целого l и пусть (n,d) будет выходом  . Это предполагает, что оба примера (n,e) и (n,e’) являются безопасными RSA примерами. Опишем схему эффективной привязки, которая вычислительно задана для RSA(e’) предположения, обладает l-сокращённым мультипликативным гомоморфным свойством для пространства сообщений  , и является  -неопределённой для  . В действительности, эта привязка будет статистически сокрыта только для сообщений выбираемых из специфического подмножества пространства сообщений, но в нашем приложении эта схема привязки будет с прямолинейным и вычислимым ZKPK е-ого корня, и нет необходимости в стандартном свойстве сокрытия, в то время как свойство  -неопределённости для вышеуказанной функции выполняется.

* Выбираем простые числа е и е’ такие, что   и  . Выполняем   для входа (k,e) чтобы получить (n,d). Устанавливаем  .
* Выбираем   и устанавливаем  . Отметим, что легко получить случайный элемент в   путём возведения в квадрат случайного элемента в  .
* Выбираем   и устанавливаем   и  . (следовательно пространством обратных значений привязки будет  .)
* Принимается тогда и только тогда, когда   и  
* Выбираем   и устанавливаем   и  
* Выбираем   и возвращаем  , где   и st = s.
* Вычисляем   и    (над целыми числами) и возвращаем (r,z), где  .

'''Статистическое сокрытие.''' Эта схема привязки будет е-сокрытой для сообщений выбираемых из   где 	  и h определён ключом привязки. Для определения этого, отметим, что максимальная статистическая разница между распределениями привязок для   случается когда они определены как i = 0 и i = ee’/2, соответственно. Т.о. распределениями данных привязок будут   соответственно, которые обладают статистической разностью равной е.

'''Вычислительное задание.''' Данная схема привязки (t,e)-задана если RSA(e’) задача является (t,e)-стойкой. В действительности для заданного значения (n, e’ ,h) можно использовать злоумышленника для задания чтобы найти е’-ый корень h. Упрощение выполняет задание злоумышленника на получение   таких, что   и  . Т.к.   следует, что  . Теперь т.к.  , тогда   и используем расширенный алгоритм Эвклида чтобы вычислить   такие, что   Т.о.   и е’-ый корень h можно вычислить как  

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

'''<math> \Sigma </math>-неопределённость.''' Эта схема привязки является  - -неопределённой для функции (семейства)   Сперва отметим, что для каждого   выхода   и каждого   таких, что   является генератором  , распределения сгенерированных ключей с помощью   и   будут состоять из не более   частей, потому что   выбирает ключ h в виде случайного элемента в   тогда как   выбирает   для е’ т.о. чтобы   и   выбирался случайным образом из  . Боле того статистическая разница между   и   будет равна  . Затем, если   есть генератор  , то для каждого  , каждого   и каждого  , согласно кодировке   и  удовлетворяют   и  , поэтому для   мы имеем  , и следовательно  . Более того распределение обратных значений привязки в неопределённом процессе, т.е.  , будет идентичным равномерному распределению над  .

'''Следствие 1.''' Рассмотрим простое число   и пусть n будет безопасным RSA модулем выводящимся   при входном значении е и секретном параметре k. Рассмотрим выполнение показанное на рис. 3 и пусть функция (семейство) f будет   таким, что   и пусть выполнение примера схемы привязки будет взято из данного раздела. Тогда из Теоремы 1 следует, что результирующая схема будет прямолинейным структурированным доказательством нулевого разглашения знания e-ого корня.

==	Идентификационные схемы мультиподписи основанные на RSA==

Опишем нашу IBMS схему основанную на RSA предположении. Данная схема выполняется за два вычислительных цикла, требующих два двойных возведения в степень для каждого участника при подписании и одно тройное возведение в степень при проверке. Схема основывается на GQ ID-подобном идентификационном протоколе [GQ88], который является  -протоколом для доказательства знания е-ого корня. Каждый участник просто выполняет совокупное доказательство нулевого разглашения е-ого корня своей (хэшированной) идентификационной строки, используя прямолинейное симулируемое совокупное ZKPK е-ого корня описанное в Разделе 5. Рисунок 4 содержит   и   алгоритмы для данной IBMS схемы.

'''Замечание по поводу длины мультиподписи.''' На Рис. 4 конечной мольтиподписью является кортеж (z,C,D), где   и   выступаю в роли пар привязка – её обратное значение для сообщения  . Однако, эта привязка может быть вычислена посредством детерминистической функции привязываемого сообщения а и её обратного значения. Поэтому С можно рассчитать для заданно (z,C,D) и следовательно можно использовать (z,C,D) в качестве конечной мультиподписи, которая уменьшает размер мультиподписи до  

'''Теорема 2.''' Если RSA(e) и RSA(e’) задачи являются (t’,e’)-стойкими, и IBMS схема на рис. 4 определяется с помощью схемы привязки из раздела 5, которая  -заданная и  -неопределенная для функции  , то результирующая схема IBMS будет  -защищена в модели случайного оракула, где и   это время одного возведения в степень в  .

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


# Пусть l будет максимальным числом участников в IBMS схеме. Выберем простые числа е и e’ такие, что   и   Выполним   для входа (k, e) чтобы получить (n, d). Отметим. что   потому что   где   Выполним   для получения ключа привязки К. Установим   и msk = d. Предположим, что   и   это случайные оракулы такие, что каждый другой алгоритм в протоколе имеет доступ к ним.
# PKG вычисляет  , выявляется секретный ключ пользователя с идентификатором Id как   и отправляется обратно ему через безопасный и аутентифицированный канал.
#	MSig: Пусть Р будет множеством участников в протоколе. Каждый участник определяет Р после первого шага MSig. Участник с идентификатором   для входа   выполняет следующие шаги:
##	Выбирает  ; Устанавливает   и предоставляет  
##	При получении  , Устанавливает   и  ; Устанавливает  ; Вычисляет   и передаёт  
##	Выводит мультиподпись  , где   и  
# Компонует пары   как   и mpk как  ; Устанавливает  ;  ; Если  , то accept, в противном случае reject.

Рис. 4. Идентификационная схема мультиподписи основанная на RSA

Аддитивно   отвечает на хэш запросы злоумышленника и выполняет дополнительный расчёт конечных значений с помощью процедур SimHash и   из Рис. 5. Симулятор   с другой стороны, принимает в качестве входа RSA значение   и набор   где   будет в   и выполняются следующие процедуры   и  , детально показанные на Рис. 5, при инициализации, ответе на решающий ключ, подписании и хэш запросах а также конечном расчёте, соответственно. Интуитивно понятно, что симулятор   использует методику Корона [Cor00] для включения RSA значения в хэш функции ID участника с некоторой необъективной вероятностью   подразумевающей, что злоумышленник будет основываться на ID участника для которого значение RSA в действительности было инкапсулировано. Т.о.   выполняет запросы на подписание от идентификатора Id прямо как в реальном протоколе использующем процедуру MSig, но если значение RSA не вводилось в хэш Id, то в противном случае   использует прямолинейную структурированную имуляцию нулевого разглашения для доказательства знания е-ого корны (см. следствие 1) при моделировании протокола подписания от лица идентификатора Id. Оба и   и  , после получения корректного значения от F, выполняют заключительный этап в котором подделанная мультиподпись возвращается вместе с индексом хэш ответа на котором они основывали своё взаимодействие. А именно,   и   возвращают   такое, что   и существует хотя бы один не взломанный Id такой, что (m, Id) никогда не запрашивался для подписания. Симуляторы   и   определяют пустые таблицы   и   для моделирования хэш функций   и   соответственно т используют множество   для ответа на  запросы хэш функций для  , которая позволяет использовать порождающую Лемму (сформулированную в [BN06,BCJ08]).
	
Теперь для   пусть   будет ограничена снизу вероятностью того, что   сгенерирует «полезный» выход, т.е. выход отличный от   Это происходит, когда   прерывает выполнение запросов решающего ключа или заключительной процедуры. Поэтому  . Эта функция достигает своего максимума при   Подставляя это значение   получим

Для  , рассмотрим  -порождающий алгоритм связанный с  . Успешное событие для   обозначим за   и определим, как то, что алгоритм   вывел два кортежа   и   таких, что   где j будет индексом хэш ответов на которых основывается поддельная мультиподпись. Т.к. алгоритм случайного подбрасывания монетки   и данные хэш функции отвечают аналогичным образом на предыдущий j-ый запрос алгоритма   в первом и втором выполнении протокола, то все вычисления и взаимосвязи в частности запросы представленные хэш функции   перед j-ым запросом должны быть такими же. Т.о. появление   привело к   и   Отметим, что   также приводит к   Это из-за того что  ,   а значения для   для всех   будут зафиксированы перед выявлением значения. Успешное завершение события   можно разбить на два случая (1) событие   при котором происходит   и   (2) событие  при котором происходит   и   Очевидно, что   и следовательно,  . С другой стороны, согласно порождающей лемме,   можно ограничить снизу с помощью  , вероятности успеха симулятора   (2):

Если   равномерно распределён в  , то оценка F при взаимодействии с   будет идентичной реальному выполнению протокола. Что касается  , то т.к. С является  -неопределённым, по линейной конструктивной симулируемости ZKPK е-ого элемента, первично распределения и ключи привязки в симуляции и в реальном протоколе отличны не более чем на   и вторично, распределение кортежей    генерируется для каждой подписи при взаимодействии между F и   с идентичными распределениям одинаковых переменных для реального выполнения. Т.о. т.к. наша симуляция прямолинейна, то общее расстояние между оценкой F при взаимодействии с   и для реального случая будет не более  . Это приводит к тому, что в частности,   и  . Т.о.   и  . Т.о. уравнение (2) становиться (3):

Выбираем простое е’ где   и выполняем   для получения  , устанавливаем mpk как   и выполняем F для входного значения mpk;

Запрашиваем у   Id и анализируем   для получения  . Если b = 0, возвращаем  , в противном случае прекращаем симуляцию с выводом ошибки  

Запрашиваем у   Id и анализируем   для получения  . Если b = 0, то выполняем  ; в противном случае:

Если Id в предыдущих запросах не участвовал, выбираем   равномерно случайный из  , подбрасываем необъективную монетку b, т.о. чтобы b = 0 с вероятностью  , а b = 1 с вероятностью   Если b = 0, устанавливаем   в противном случае устанавливаем   Сохраняем (b, y,  ) для  . Возвращаем  .

Если   есть i-ый отличный от предыдущего запрос F для  , то запрашиваем   для каждого   и устанавливаем  ; Возвращаем  

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

Рис. 5. Процедуры   и  , которые используют   и   и процедуры   и  , которые использует  

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

Теперь т.к.  , поэтому   и можно легко вычислить e-ый корень   используя расширенный алгоритм Эвклида.
	
Если   происходит, то R сразу преобразует это в атаку на заданное свойство схемы привязки С с помощью возвращения   Чтобы увидеть это, отметим, что т.к. утверждались раннее   и т.к.   произошло, то т.о.   и согласно корректности подложных подписей получаем   Более того ключ привязки К выводимый   при взаимодействии  . Т.о.   и   и следовательно уравнение (3) становиться (5)

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

==	Идентификационная совокупная схема подписи==

Конструкцию из предыдущего раздела можно легко преобразовать для получения 2-циклической идентификационной совокупной схемы подписи (IBAS) доказуемо безопасной при RSA предположении. Для этого, необходимо модифицировать алгоритм проверки до такого, который бы поддерживал случай, когда различные проверочные значения получались на шаге 4.2 протокола с помощью запросов посылаемых   для различных сообщений. Точнее говоря, результирующая IBAS схема будет в точности такой же как схема описанная на Рисунке 4 за исключением того, что её алгоритм проверки будет следующим: Компонуем парные значения   как   и mpk как  ; Вычисляем  , где   это выход   при входе   и проверяем будет ли  
	
Доказательство безопасности данной IBAS схемы схоже с доказательством заданным в предыдущем разделе. А именно, упрощение реализует выполнение двух симуляторов; в одном симуляторе инкапсулируется проверочное значение в ключ привязки а в другом – в хэш функции ID. Поэтому с большой вероятностью, если происходит подделка подписи процедура сокращения приводит либо к реализации атаки на заданное свойство схемы привязки (событие   в прошлом доказательстве) либо к нахождению е-ого корня проверочного значения (событие   в предыдущем доказательстве). Доказательство безопасности IBAS схемы аналогично доказательству безопасности IBMS схемы описанное в предыдущем разделе. Самой важной отличительной чертой данного доказательства будет замена следующим уравнением уравнения (4) из предыдущего доказательства при нахождении е-ого корня:

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

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

{{примечания|group=@:}}

== Примечание ==

{{примечания|group=прим.}}

== Литература ==

{{примечания}}

[[Категория:Public Key Cryptography 2010]]
[[en:Identity-Based Aggregate and Multi-Signature Schemes Based on RSA]]