BLS

Перейти к навигацииПерейти к поиску

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предположим, что мы имеем группу подписей, которая содержит n пар (Si, PKi), где i = [0,n]. Агрегированной подписью системы назовем сумму Si по i. Чтобы подтвердить подпись необходимо проверить равенство e(g, S) = e(PK1, H1) ⋅ e(PK2, H2) ⋅ … ⋅ e(PKn, Hn).

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

Выполним проверку (g, S) = e(g, S1 + S2 + …+ Sn) = e(g, S1)⋅ e(g, S2) ⋅ … ⋅ e(g, Sn) = e(g, H1PK1) ⋅ … ⋅ e(g, HnPKn) = e(gPK1, H1) ⋅ … ⋅ e(gPKn, Hn) = e(SK1, H1) ⋅ e(SK2, H2)⋅…⋅e(SKn, Hn)

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

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

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

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

e(g, S) = e(g, S1 + S2 + … + Sn) = e(g, HSK1 + SK2 + … + SKn) = e(gSK1 + SK2 + … + SKn, H) = e(PK1 + PK2 + … + PKn, H) = e(PK, H)

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

S = a1×S1 + a2×S2 + … + an×Sn

PK = a1×PK1 + a2×PK2 + … + an×PKn

Здесь коэффициенты подписей и ключей вычисляются c помощью хэширующей функции, и учитывают все публичные ключи PKn: ai = hash(PKi, {PK1,PK2, …, PKn}), hash — обычная хэширующая функция, результатом работы которой является число.

Одной из таких функций является конкатенация публичного ключа подписанта и всего множества публичных ключей, используемых для подписи: ai = hash(Pi || P1 || P2 || P3). Для усложнённой схемы действительно то же уравнение для верификации (логика доказательства не меняется, несмотря на дополнительные коэффициенты ai).

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

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

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

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

Рассчитаем агрегированный публичный ключ PK = a1×PK1 + a2×PK2 + … + an×PKn, где ai = hash(PKi, {PK1,PK2, …, PKn}).

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

MKi = H(PK, i)a1⋅SK1 + H(PK, i)a2⋅SK2 + … + H(PK, i)an⋅SKn

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

Предположим, что мы хотим подписать сообщение только ключами SK1, SK2, …, SKk. Генерируем m подписей S1, S2, …, Sk:

S1 = H(PK, m)SK1 + MK1

S2 = H(PK, m)SK2 + MK2

…

Sk = H(PK, m)SKk + MKk

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

(S’, PK’) = (S1 + S2 + … + Sk, PK1 + PK2 + …+ PKk)

Ключ 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))

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

e(g, S’) = e(g, S1 + S2 + … + Sn) = e(g, H(PK, m)SK1 + H(PK, m)SK2 + … + H(PK, m)SKk + MK1 + MK2 + … + MKk) = e(g, H(PK, m)SK1+ H(PK, m)SK2 + … H(PK, m)SKk) ⋅ e(g, MK1 + MK2 + … + MKk) = e(gSK1 + gSK2 + … + gSKk, 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 подписи.

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

См. также

Примечания

  1. ↑ Pierre-Alain Fouque, Mehdi Tibouchi Indifferentiable Hashing to Barreto-Naehrig Curves// LATINCRYPT. — 2012. — C. 1 — 17. Дата обращения: 13 декабря 2019. Архивировано 13 декабря 2019 года.
  2. ↑ Ben Lynn On the Implementation of Pairing-based Cryptosystems // Stanford University. — 2007. — C. 31 — 36. Дата обращения: 13 декабря 2019. Архивировано 13 декабря 2019 года.
  3. ↑ Dan Boneh, Ben Lynn, and Hovav Shacham Short Signatures from the Weil Pairing // cryptology. — 2004. — C. 298—300. Дата обращения: 13 декабря 2019. Архивировано 11 июля 2020 года.
  4. ↑ Ben Lynn On the Implementation of Pairing-based Cryptosystems // Stanford University. — 2007. — C. 50 — 68. Дата обращения: 13 декабря 2019. Архивировано 13 декабря 2019 года.

Литература

Ссылки