Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




13.02.2021


07.02.2021


24.01.2021


24.01.2021


24.01.2021





Яндекс.Метрика
         » » BLS

BLS

05.02.2021

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

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

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

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

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

  • Невырожденность: e(g, g) ≠ 1
  • Билинейность: e(ga, gb) = e(g, g)ab, где a, b ∈ Z
  • Наиболее распространенными в криптографии являются функции спаривания Тейта, Вейля и оптимальное спаривание Эйта.. Последнее считается наиболее эффективным, и чаще всего используется в практике.

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

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

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

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

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

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

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

  • Посчитаем d1 = e(PK, H)
  • С другой стороны, вычислим d2 = e(g, S) = e(g, HSK) = e(gSK, H)
  • Сравним 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(Pub, 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’, Pub’) = (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 подписи.

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