|
BLSBLS подпись (Boneh-Lynn-Shacham) — это электронная подпись, опирающаяся на кривые, удобные для спаривания, и поддерживающая неинтерактивные свойства агрегации. То есть, для группы подписей (σ1, …, σn), можно составить короткую подпись σ, которая аутентифицирует всю коллекцию подписей. Схема подписи проста, эффективна и может быть использована в разнообразных сетевых протоколах и системах для сжатия подписей или цепочки сертификатов. Так как вычислительная задача Диффи-Хеллмана является неразрешимой, безопасность схемы доказана. Хэширование в кривуюТак как BLS подпись работает с эллиптическими кривыми, необходимо модифицировать стандартные функции хеширования так, чтобы на выходе получалось не число, а координаты точки[1]. За основу возьмём стандартную функцию хэширования, но результатом её работы будем считать не конечное число, а x-координату точки. Каждому найденному x может соответствовать ноль или два значения y, то есть не для каждого x существует валидный y. Поэтому будем хэшировать (msg || i), пока не получим корректный результат, где || — функция конкатенации, а i — неотрицательное число. Остаётся только определить закон выбора одной из полученных точек (например, будет точка с наибольшим значением y). Спаривание кривыхДля создания подписи необходима функция, которая будет сопоставлять двум точкам кривой некоторое число. Введём абстрактное определение спаривания. Пусть G, GT — циклические группы простого порядка r, порожденные элементом g. Спариванием называется эффективно вычислимая функция e : G1 × G2 → GT , для которой выполняются следующие свойства:
Наиболее распространенными в криптографии являются функции спаривания Тейта, Вейля и оптимальное спаривание Эйта[2]. Последнее считается наиболее эффективным, и чаще всего используется в практике. Если для циклической группы определена функция спаривания, то для этой группы неразрешимы вычислительная задача Диффи-Хеллмана и задача дискретного логарифма, но существует эффективное решение задачи принятия решения Диффи-Хеллмана. Такие группы называют группами Диффи-Хеллмана[3] и подразумевают схему подписи, называемую подпись Боне — Линна — Шахама. Схема BLS подписиПусть G — группа Диффи-Хеллмана простого порядка r, где g ∈ G — порождающий элемент группы, m — заданное сообщение. Генерация ключейЗакрытым ключом SK является случайное целое число, выбранное из интервала [0, r-1]. Открытым ключом назовем PK = gSK Cоздание подписи
Проверка подписи
Агрегирование подписейПредположим, что мы имеем группу подписей, которая содержит 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 — атака (атака на криптосистемы с эллиптическими кривыми), направленная на снижение безопасности системы, путем воздействия на функцию спаривания. См. такжеПримечания
Литература
Ссылки |