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 — атака (атака на криптосистемы с эллиптическими кривыми), направленная на снижение безопасности системы, путем воздействия на функцию спаривания.

См. также

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

Примечания

Литература

Ссылки