BLS

BLS подпись (Boneh-Lynn-Shacham) — это электронная подпись, опирающаяся на кривые, удобные для спаривания, и поддерживающая неинтерактивные свойства агрегации. То есть, для группы подписей (σ₁, …, σ_n), можно составить короткую подпись σ, которая аутентифицирует всю коллекцию подписей. Схема подписи проста, эффективна и может быть использована в разнообразных сетевых протоколах и системах для сжатия подписей или цепочки сертификатов. Так как вычислительная задача Диффи-Хеллмана является неразрешимой, безопасность схемы доказана.

Хэширование в кривую

Так как BLS подпись работает с эллиптическими кривыми, необходимо модифицировать стандартные функции хеширования так, чтобы на выходе получалось не число, а координаты точки. За основу возьмём стандартную функцию хэширования, но результатом её работы будем считать не конечное число, а x-координату точки. Каждому найденному x может соответствовать ноль или два значения y, то есть не для каждого x существует валидный y. Поэтому будем хэшировать (msg || i), пока не получим корректный результат, где || — функция конкатенации, а i — неотрицательное число. Остаётся только определить закон выбора одной из полученных точек (например, будет точка с наибольшим значением y).

Спаривание кривых

Для создания подписи необходима функция, которая будет сопоставлять двум точкам кривой некоторое число. Введём абстрактное определение спаривания. Пусть G, G_T — циклические группы простого порядка r, порожденные элементом g. Спариванием называется эффективно вычислимая функция e : G₁ × G₂ → G_T , для которой выполняются следующие свойства:

1. Невырожденность: e(g, g) ≠ 1
2. Билинейность: e(g^a, g^b) = e(g, g)^ab, где a, b ∈ Z

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

Если для циклической группы определена функция спаривания, то для этой группы неразрешимы вычислительная задача Диффи-Хеллмана и задача дискретного логарифма, но существует эффективное решение задачи принятия решения Диффи-Хеллмана. Такие группы называют группами Диффи-Хеллмана и подразумевают схему подписи, называемую подпись Боне — Линна — Шахама.

Схема BLS подписи

Пусть G — группа Диффи-Хеллмана простого порядка r, где g ∈ G — порождающий элемент группы, m — заданное сообщение.

Генерация ключей

Закрытым ключом SK является случайное целое число, выбранное из интервала [0, r-1]. Открытым ключом назовем PK = g^SK

Cоздание подписи

1. Хэшируем сообщение в кривую H = Hashing(m), где H — точка на кривой
2. Вычисляем S = H^SK
3. Подписью документа является точка S.

Проверка подписи

1. Посчитаем d1 = e(PK, H)
2. С другой стороны, вычислим d2 = e(g, S) = e(g, H^SK) = e(g^SK, H)
3. Сравним d1 и d2: если они совпадают — подпись верна.

Агрегирование подписей

Предположим, что мы имеем группу подписей, которая содержит n пар (S_i, PK_i), где i = [0,n]. Агрегированной подписью системы назовем сумму S_i по i. Чтобы подтвердить подпись необходимо проверить равенство e(g, S) = e(PK₁, H₁) ⋅ e(PK₂, H₂) ⋅ … ⋅ e(PK_n, H_n).

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

Выполним проверку (g, S) = e(g, S₁ + S₂ + …+ S_n) = e(g, S₁)⋅ e(g, S₂) ⋅ … ⋅ e(g, S_n) = e(g, H₁^PK₁) ⋅ … ⋅ e(g, H_n^PK_n) = e(g^PK₁, H₁) ⋅ … ⋅ e(g^PK_n, H_n) = e(SK₁, H₁) ⋅ e(SK₂, H₂)⋅…⋅e(SK_n, H_n)

Мультиподпись подгруппы

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

Мультиподпись типа n-из-n

Самым простым способом комбинирования является сложение. Поэтому подписью назовём S = S₁ + S₂ + … + S_n, а ключом PK = PK₁ + PK₂ + … + PK_n. Для этого случая легко доказывается корректность выбранных значений: e(g, S) = e(P, H)

e(g, S) = e(g, S₁ + S₂ + … + S_n) = e(g, H^{SK₁ + SK₂ + … + SK_n}) = e(g^{SK₁ + SK₂ + … + SK_n}, H) = e(PK₁ + PK₂ + … + PK_n, H) = e(PK, H)

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

S = a₁×S₁ + a₂×S₂ + … + a_n×S_n

PK = a₁×PK₁ + a₂×PK₂ + … + a_n×PK_n

Здесь коэффициенты подписей и ключей вычисляются c помощью хэширующей функции, и учитывают все публичные ключи PK_n: a_i = hash(PK_i, {PK₁,PK₂, …, PK_n}), hash — обычная хэширующая функция, результатом работы которой является число.

Одной из таких функций является конкатенация публичного ключа подписанта и всего множества публичных ключей, используемых для подписи: a_i = hash(P_i || P₁ || P₂ || P₃). Для усложнённой схемы действительно то же уравнение для верификации (логика доказательства не меняется, несмотря на дополнительные коэффициенты a_i).

Мультиподпись типа k-из-n

Часто мультиподписи n-из-n, предпочитают k-из-n. Так как в этом случае при потере одного или нескольких ключей возможна корректная работа системы. Для BLS подписи агрегирование ключей работает и в таком сценарии.

Приведем пример построения схемы мультиподписи k-из-n с помощью ключей(k < n), хранящихся на n разных устройствах.

Каждое из устройств имеет номер подписанта i = 1,2, …, n, определяющий порядковый номер во множестве, приватный ключ SK_i и публичный ключ PK_i = g^SK_i.

Рассчитаем агрегированный публичный ключ PK = a₁×PK₁ + a₂×PK₂ + … + a_n×PK_n, где a_i = hash(PK_i, {PK₁,PK₂, …, PK_n}).

Получим ключ участия MK_i от каждого устройства, который подтвердит, что номер i входит в PK. Каждый ключ участия должен быть сохранён на соответствующем устройстве.

MK_i = H(PK, i)^a₁⋅SK₁ + H(PK, i)^a₂⋅SK₂ + … + H(PK, i)^a_n⋅SK_n

Каждый ключ участия — это действенная подпись n-из-n сообщения H(PK,i). Следовательно, для каждого MK_i выполняется: e(g, MK_i)=e(PK, H(PK,i))

Предположим, что мы хотим подписать сообщение только ключами SK₁, SK₂, …, SK_k. Генерируем m подписей S₁, S₂, …, S_k:

S₁ = H(PK, m)^SK₁ + MK₁

S₂ = H(PK, m)^SK₂ + MK₂

…

S_k = H(PK, m)^SK_k + MK_k

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

(S’, PK’) = (S₁ + S₂ + … + S_k, PK₁ + PK₂ + …+ PK_k)

Ключ PK’ и подпись S’ отличны от пары PK, S. Первые зависят только от подмножества подписантов, в то время как вторые определяются всеми парами начальной системы.

Для верификации полученной подписи k-из-n, проверим условие:

e(g, S’) = e(PK’, H(PK, m))⋅e(PK, H(PK, 1)+H(PK, 2)+ … + H(PK, k))

Так как ключи участия MK₁, MK₂, … MK_k — это действительные подписи для сообщений H(PK, 1), H(PK, 2) … H(PK, k), подписанных агрегированным ключом PK, поэтому:

e(g, S’) = e(g, S₁ + S₂ + … + S_n) = e(g, H(PK, m)^SK₁ + H(PK, m)^SK₂ + … + H(PK, m)^SK_k + MK₁ + MK₂ + … + MK_k) = e(g, H(PK, m)^SK₁+ H(PK, m)^SK₂ + … H(PK, m)^SK_k) ⋅ e(g, MK₁ + MK₂ + … + MK_k) = e(g^SK₁ + g^SK₂ + … + g^SK_k, H(PK, m)) ⋅ e(PK, H(PK, 1) + H(PK, 2) + … + H(PK, k)) = e(PK’, H(PK, m)) ⋅ e(PK, H(PK, 1) + H(PK, 2) + … + H(PK, k))

Аналогичная схема применима для любых значений k и n. А вместо 1, 2, … k могут быть выбраны любые неповторяющиеся k подписантов с номерами, принадлежащими промежутку [1, n].

Недостатки

Основным недостатком данного типа подписей является процесс спаривания.

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

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

См. также

• Протокол Диффи — Хеллмана на эллиптических кривых
• Эллиптическая криптография

Литература

• Dan Boneh, Craig Gentry, Ben Lynn, Hovav Shacham Aggregate and Verifiably Encrypted Signatures from Bilinear Maps // cryptology. — 2003. — C. 416—432.
• T. Okamoto and D. Pointcheval. The gap-problems: A new class of problems for the security of cryptographic schemes. In Public Key Cryptography. — 2001 — С. 104—118.
• О. Н. Василенко, «О вычислении спариваний Вейля и Тейта», Тр. по дискр. матем., 10, Физматлит, М., 2007
• Dan Boneh, Alice Silverberg Applications of Multilinear Forms to Cryptography // Contemporary Mathematics. — 2003. — C. 71 — 90.

Ссылки

• BLS signatures: better than Schnorr
• What is the BLS signature scheme?