С. М. ГОНЧАРОВ
Дальневосточный государственный университет, Владивосток
Мультиподпись на основе к-мультилинейных отображений
В [1] Боне, Линн и Шачам предложили новую схему подписи, использующую группы, в которых решающая проблема Диффи-Хэллмана – легка, а вычислительная проблема Диффи-Хэллмана – сложна. Следуя [1], мы будем обозначать такие группы - GDH-группы. А. Болдырева в [2] предложила схему мультиподписи для GDH-групп и показала ее безопасность. Нами будут использованы некоторые понятия и факты из [2].
Пусть G - GDH-группа простого порядка q и пусть g будет генератором G. Как и в большинстве схем, основанных на проблеме дискретного логарифмирования, секретный ключ GDH-подписи есть случайный элемент x
, а открытый ключ есть y= gx. Чтобы подписать сообщение М {0,1}*, подписывающий, который знает секретный ключ x, вычисляет подпись H(M)x , где H – хеш-функция, отображающая произвольные строки элементов G\{1} (1 обозначает нейтральный элемент группы G). Для верификации подписи проверяющий просто проверяет: является ли (g, y, H(M), σ) в действительности кортежем Диффи-Хэллмана.
Боне и соавторы [1] доказали, что схема GDH-подписи безопасна по отношению к подделке подписи при атаке с выбранным сообщением в условиях модели случайного оракула в предположении, что рассматриваемая группа – GDH-группа.
Схема мультиподписи состоит из тройки алгоритмов (MK, MS, MV).
• MK: Алгоритм генерации ключа. Каждый участник Ui использует этот алгоритм для получения открытого ключа pki=(p, g,H, yi) и секретного ключа ski=xi , где yi= gxi.
• MS: Каждый участник Ui c секретным ключом ski=xi , который желает участвовать в мультиподписи, берет сообщение М, вычисляет и широковещательно рассылает σi=H(M)xi участникам мультиподписи. Пусть L={Ui1,…,Uil} – подгруппа, участвующая в мультиподписи. Пусть J={i1,…,il} обозначает набор индексов таких пользователей. Формирующий подпись (его роль может выполнять любой из подписывающих), который знает подпись каждого из подписывающих, вычисляет σ= ∏ jJ (σi) и выдает T=(M, L, σ).
• MV: Проверяющий берет T=(M, L, σ) и открытые ключи подписавших из L: (pki1,…,pkil ), где pkij = 
для каждого ijJ. Затем вычисляет
pkL = ∏ jJ (pki) = ∏ jJ (
) и выдает на выход VDDH(g, pkL, H(M), σ).
(VDDH – алгоритм решения DDH-проблемы.)
В [2] доказан следующий факт, касающийся безопасности схемы мультиподписи в GDH-группе:
Факт 1. Пусть G - GDH-группа. Тогда схема GDH-мультиподписи является безопасной схемой мультиподписи в модели случайного оракула.
Вариант мультиподписи на базе мультилинейных отображений.
Напомним две базовые проблемы.
CDH-проблема. Для заданных α, αa, βG1 вычислить βa.
DDH-проблема. Для заданных α, αa, β, βb G1 определить справедливо ли равенство a=b («да» на выходе алгоритма) или нет («нет» на выходе).
Покажем, что эффективно вычисляемое k-мультилинейное отображение e предоставляет алгоритм для решения DDH-проблемы.
Утверждение Если существует k-мультилинейное отображение e: 
, то для кортежа (α, αa, β, βb) имеем:
a=b modq 
e(β, αa, g,..., g)= e(βb, α, g,..., g), где q - порядок группы G1,
g - генератор группы G1.
Доказательство: В прямую сторону.
a=b modq 
e(β, αa, g,..., g)= e(β, α, g,..., g) a= e(β, α, g,..., g)b= e(βb, α, g,..., g)
В обратную сторону.
Пусть e(β, αa, g,..., g)= e(βb, α, g,..., g). Так как g - генератор группы G, то существуют x1, x2 , такие, что α= g x1 и β = g x2.
e(β, αa, g,..., g)= e(g x2, g x1a, g,..., g)= e(g, g, g,..., g) x2 x1a
e(βb, α, g,..., g) )= e(g x2 b, g x1, g,..., g) = e(g, g, g,..., g) x2 x1b
Из определения мультилинейного отображения следует, если gG1 является генератором G1 , тогда e (g,..., g) - генератор G2. Так как
e(g, g, g,..., g) - генератор G2, из равенства
e(g, g, g,..., g) x2 x1a= e(g, g, g,..., g) x2 x1b следует x2x1a= x2x1b modq.
Так как x1, x2 , а q – простое, отсюда следует a=b modq.
Утверждение доказано.
Следствие 1 Если существует k-мультилинейное отображение e: , то DDH-проблема в G1 - легка.
Следствие 2 Если существует k-мультилинейное отображение e: , то G1 - GDH-группа.
Таким образом, можно построить безопасную схему мультиподписи с использованием k-мультилинейных отображений. При этом схема мультиподписи на основе k-мультилинейных отображений совпадает с описанной выше схемой. Алгоритм VDDH сводится к проверке равенства e(H(M), pkL, g,..., g)= e(σ, g, g,..., g), посредством вычисления k-мультилинейных отображений (в случае выполнения равенства – на выходе 1, в противном случае – на выходе 0).
Список литературы
1. D. Boneh and B. Lynn and H. Shacham. Short signatures from the Weil pairing, Advances in Cryptology ASIACRYPT 2001, LNCS Vol. 2248, C. Boyd ed., Springer-Verlag, 2001.
2. A. Boldyreva. Efficient Threshold signature, multisignature and blind signature schemes based on the gap-Diffie-Hellman-group signature scheme. Proceedings of PKC 2003, volume 2567 of LNCS, pages 31-46. Springer-Verlag, 2003.
