Гомоморфные подписи для сетевого кодирования - Homomorphic signatures for network coding

Сетевое кодирование было показано, что оптимально использовать пропускная способность в сети, максимизируя информационный поток, но эта схема по своей природе очень уязвима для атак загрязнения со стороны злонамеренных узлов в сети. Узел, вводящий мусор, может быстро повлиять на многие получатели. Загрязнение сетевые пакеты распространяется быстро, так как выход (даже) честного узла поврежден, если поврежден хотя бы один из входящих пакетов. Злоумышленник может легко повредить пакет, даже если он зашифрован, путем подделки подписи или создания коллизии под хэш-функция. Это даст злоумышленнику доступ к пакетам и возможность их повредить. Денис Чарльз, Камаль Джайн и Кристин Лаутер разработали новый гомоморфное шифрование схема подписи для использования с сетевым кодированием для предотвращения атак загрязнения.^[1] Гомоморфность подписей позволяет узлам подписывать любую линейную комбинацию входящих пакетов, не связываясь с органом подписи. В этой схеме для узла вычислительно невозможно подписать линейную комбинацию пакетов, не раскрывая, что линейная комбинация использовался при генерации пакета. Кроме того, мы можем доказать, что схема подписи безопасна при хорошо известных криптографический предположения о твердости дискретный логарифм проблема и вычислительная Эллиптическая кривая Диффи – Хеллмана.

Сетевое кодирование

Позволять ${ Displaystyle G = (V, E)}$ быть ориентированный граф куда ${ displaystyle V}$ - множество, элементы которого называются вершинами или узлы, и ${ displaystyle E}$ это набор заказанные пары вершин, называемых дугами, направленными ребрами или стрелками. Источник ${ displaystyle s in V}$ хочет передать файл ${ displaystyle D}$ к набору ${ Displaystyle T substeq V}$ вершин. Один выбирает векторное пространство ${ Displaystyle W / mathbb {F} _ {p}}$ (скажем о размере ${ displaystyle d}$ ), куда ${ displaystyle p}$ является простым и рассматривает данные, которые должны быть переданы, как набор векторов ${ displaystyle w_ {1}, ldots, w_ {k} in W}$ . Затем источник создает дополненные векторы ${ displaystyle v_ {1}, ldots, v_ {k}}$ установив ${ Displaystyle v_ {я} = (0, ldots, 0,1, ldots, 0, w_ {i_ {1}}, ldots, w {i_ {d}})}$ куда ${ displaystyle w_ {i_ {j}}}$ это ${ displaystyle j}$ -я координата вектора ${ displaystyle w_ {i}}$ . Есть ${ Displaystyle (я-1)}$ нули перед первой "1" появляется в ${ displaystyle v_ {i}}$ . Без ограничения общности можно считать, что векторы ${ displaystyle v_ {i}}$ находятся линейно независимый. Обозначим линейное подпространство (из ${ Displaystyle mathbb {F} _ {p} ^ {k + d}}$ ), натянутые на эти векторы ${ displaystyle V}$ . Каждый исходящий край ${ displaystyle e in E}$ вычисляет линейную комбинацию, ${ Displaystyle у (е)}$ , векторов, входящих в вершину ${ Displaystyle v = в (е)}$ откуда начинается край, т. е.

{ displaystyle y (e) = sum _ {f: mathrm {out} (f) = v} (m_ {e} (f) y (f))}

куда ${ displaystyle m_ {e} (е) in mathbb {F} _ {p}}$ . Мы рассматриваем источник как имеющий ${ displaystyle k}$ входные края, несущие ${ displaystyle k}$ векторов ${ displaystyle w_ {i}}$ . К индукция, то вектор ${ Displaystyle у (е)}$ на любом ребре - линейная комбинация ${ Displaystyle у (е) = сумма _ {1 Leq я Leq k} (g_ {я} (е) v_ {я})}$ и является вектором в ${ displaystyle V}$ . K-мерный вектор ${ displaystyle g (e) = (g_ {1} (e), ldots, g_ {k} (e))}$ просто первый k координаты вектора ${ Displaystyle у (е)}$ . Мы называем матрица чьи строки являются векторами ${ Displaystyle г (е_ {1}), ldots, г (е_ {к})}$ , куда ${ displaystyle e_ {i}}$ входящие ребра для вершины ${ displaystyle t in T}$ , глобальная матрица кодирования для ${ displaystyle t}$ и обозначим его как ${ displaystyle G_ {t}}$ . На практике векторы кодирования выбираются случайным образом, поэтому матрица ${ displaystyle G_ {t}}$ обратима с большой вероятностью. Таким образом, любой получатель, получив ${ displaystyle y_ {1}, ldots, y_ {k}}$ могу найти ${ displaystyle w_ {1}, ldots, w_ {k}}$ путем решения

{ displaystyle { begin {bmatrix} y ' y_ {2}' vdots y_ {k} ' end {bmatrix}} = G_ {t} { begin {bmatrix} w_ {1} w_ {2} vdots w_ {k} end {bmatrix}}}

где ${ displaystyle y_ {i} '}$ - векторы, образованные удалением первого ${ displaystyle k}$ координаты вектора ${ displaystyle y_ {i}}$ .

Расшифровка на приемнике

Каждый приемник, ${ displaystyle t in T}$ , получает ${ displaystyle k}$ векторов ${ displaystyle y_ {1}, ldots, y_ {k}}$ которые представляют собой случайные линейные комбинации ${ displaystyle v_ {i}}$ S. На самом деле, если

{ displaystyle y_ {i} = ( alpha _ {i_ {1}}, ldots, alpha _ {i_ {k}}, a_ {i_ {1}}, ldots, a_ {i_ {d}} )}

тогда

{ displaystyle y_ {i} = sum _ {1 leq j leq k} ( alpha _ {ij} v_ {j}).}

Таким образом, мы можем инвертировать линейное преобразование, чтобы найти ${ displaystyle v_ {i}}$ С высоким вероятность.

История

Крон, Фридман и Мазьер предложили теорию^[2] в 2004 году, если у нас есть хеш-функция ${ displaystyle H: V longrightarrow G}$ такой, что:

${ displaystyle H}$ является стойкий к столкновениям - трудно найти ${ displaystyle x}$ и ${ displaystyle y}$ такой, что ${ Displaystyle Н (х) = Н (у)}$ ;
${ displaystyle H}$ это гомоморфизм – ${ Displaystyle Н (Икс + Y) = Н (Икс) + Н (Y)}$ .

Тогда сервер сможет безопасно распространять ${ displaystyle H (v_ {i})}$ каждому получателю и проверить,

{ Displaystyle у = сумма _ {1 Leq я Leq k} ( альфа _ {я} v_ {я})}

мы можем проверить, есть ли

{ Displaystyle Н (Y) = сумма _ {1 Leq я Leq k} ( альфа _ {я} Н (v_ {i}))}

Проблема с этим методом заключается в том, что серверу необходимо передавать защищенную информацию каждому из получателей. Хеш-функции ${ displaystyle H}$ необходимо передать на все узлы в сети через отдельный защищенный канал. ${ displaystyle H}$ требует больших затрат на вычисление и безопасную передачу ${ displaystyle H}$ тоже не экономично.

Преимущества гомоморфных подписей

Устанавливает аутентификацию в дополнение к обнаружению загрязнения.
Нет необходимости распространять безопасные хеш-дайджесты.
Обычно будет достаточно меньшей битовой длины. Подписи длиной 180 бит имеют такую же безопасность, как и 1024-битные подписи RSA.
Публичная информация не меняется для последующей передачи файлов.

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

Гомоморфность подписей позволяет узлам подписывать любую линейную комбинацию входящих пакетов, не связываясь с органом подписи.

Криптография на эллиптических кривых над конечным полем

Криптография на эллиптических кривых над конечным полем - это подход к криптография с открытым ключом основанный на алгебраической структуре эллиптические кривые над конечные поля.

Позволять ${ displaystyle mathbb {F} _ {q}}$ - конечное поле такое, что ${ displaystyle q}$ не является степенью 2 или 3. Тогда эллиптическая кривая ${ displaystyle E}$ над ${ displaystyle mathbb {F} _ {q}}$ кривая, заданная уравнением вида

{ displaystyle y ^ {2} = x ^ {3} + ax + b, ,}

куда ${ displaystyle a, b in mathbb {F} _ {q}}$ такой, что ${ displaystyle 4a ^ {3} + 27b ^ {2} not = 0}$

Позволять ${ Displaystyle К supseteq mathbb {F} _ {q}}$ , тогда,

{ displaystyle E (K) = {(x, y) | y ^ {2} = x ^ {3} + ax + b } bigcup {O }}

образует абелева группа с O как личность. В групповые операции может выполняться эффективно.

Спаривание Вейля

Спаривание Вейля это конструкция корни единства с помощью функций на эллиптическая кривая ${ displaystyle E}$ , таким образом, чтобы создать спаривание (билинейная форма хотя с мультипликативная запись ) на торсионная подгруппа из ${ displaystyle E}$ . Позволять ${ Displaystyle E / mathbb {F} _ {q}}$ - эллиптическая кривая и пусть ${ displaystyle mathbb { bar {F}} _ {q}}$ быть алгебраическим замыканием ${ displaystyle mathbb {F} _ {q}}$ . Если ${ displaystyle m}$ является целым числом, взаимно простым с характеристикой поля ${ displaystyle mathbb {F} _ {q}}$ , то группа ${ displaystyle m}$ -точки кручения, ${ displaystyle E [m] = {P in E ( mathbb { bar {F}} _ {q}): mP = O}}$ .

Если ${ Displaystyle E / mathbb {F} _ {q}}$ эллиптическая кривая и ${ Displaystyle НОД (т, д) = 1}$ тогда

{ Displaystyle E [м] cong ( mathbb {Z} / m mathbb {Z}) * ( mathbb {Z} / m mathbb {Z})}

Есть карта ${ displaystyle e_ {m}: E [m] * E [m] rightarrow mu _ {m} ( mathbb {F} _ {q})}$ такой, что:

(Билинейный) ${ displaystyle e_ {m} (P + R, Q) = e_ {m} (P, Q) e_ {m} (R, Q) { text {and}} e_ {m} (P, Q + R ) = e_ {m} (P, Q) e_ {m} (P, R)}$ .
(Невырожденный) ${ displaystyle e_ {m} (P, Q) = 1}$ для всех п подразумевает, что ${ displaystyle Q = O}$ .
(Чередование) ${ displaystyle e_ {m} (P, P) = 1}$ .

Также, ${ displaystyle e_ {m}}$ можно вычислить эффективно.^[3]

Гомоморфные подписи

Позволять ${ displaystyle p}$ быть первым и ${ displaystyle q}$ основная сила. Позволять ${ Displaystyle V / mathbb {F} _ {p}}$ быть векторным пространством размерности ${ displaystyle D}$ и ${ Displaystyle E / mathbb {F} _ {q}}$ - эллиптическая кривая такая, что ${ Displaystyle P_ {1}, ldots, P_ {D} in E [p]}$ .Определять ${ displaystyle h: V longrightarrow E [p]}$ следующее: ${ Displaystyle ч (и_ {1}, ldots, и_ {D}) = сумма _ {1 leq я leq D} (и_ {i} P_ {i})}$ .Функция ${ displaystyle h}$ - произвольный гомоморфизм из ${ displaystyle V}$ к ${ displaystyle E [p]}$ .

Сервер выбирает ${ Displaystyle s_ {1}, ldots, s_ {D}}$ тайно в ${ displaystyle mathbb {F} _ {p}}$ и публикует точку ${ displaystyle Q}$ p-кручения такое, что ${ displaystyle e_ {p} (P_ {i}, Q) not = 1}$ а также издает ${ displaystyle (P_ {i}, s_ {i} Q)}$ за ${ Displaystyle 1 Leq я Leq D}$ .Подпись вектора ${ displaystyle v = u_ {1}, ldots, u_ {D}}$ является ${ Displaystyle sigma (v) = сумма _ {1 Leq я Leq D} (u_ {i} s_ {i} P_ {i})}$ Примечание: эта сигнатура гомоморфна, поскольку вычисление h является гомоморфизмом.

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

Данный ${ displaystyle v = u_ {1}, ldots, u_ {D}}$ и его подпись ${ displaystyle sigma}$ , подтвердите это

{ displaystyle { begin {align} e_ {p} ( sigma, Q) & = e_ {p} left ( sum _ {1 leq i leq D} (u_ {i} s_ {i} P_ {i}), Q right) & = prod _ {i} e_ {p} (u_ {i} s_ {i} P_ {i}, Q) & = prod _ {i} e_ {p} (u_ {i} P_ {i}, s_ {i} Q) end {выровнено}}}

Проверка критически использует билинейность спаривания Вейля.

Настройка системы

Сервер вычисляет ${ displaystyle sigma (v_ {i})}$ для каждого ${ Displaystyle 1 Leq я Leq k}$ . Передает ${ displaystyle v_ {i}, sigma (v_ {i})}$ .На каждом краю ${ displaystyle e}$ при вычислении ${ displaystyle y (e) = sum _ {е in E: mathrm {out} (f) = mathrm {in} (e)} (m_ {e} (f) y (f))}$ также вычислить ${ displaystyle sigma (y (e)) = sum _ {f in E: mathrm {out} (f) = mathrm {in} (e)} (m_ {e} (f) sigma ( y (f)))}$ на эллиптической кривой ${ displaystyle E}$ .

Подпись - это точка на эллиптической кривой с координатами в ${ displaystyle mathbb {F} _ {q}}$ . Таким образом, размер подписи ${ displaystyle 2 log q}$ бит (что является постоянным временем ${ displaystyle log (p)}$ бит, в зависимости от относительного размера ${ displaystyle p}$ и ${ displaystyle q}$ ), и это накладные расходы передачи. Вычисление подписи ${ displaystyle h (e)}$ в каждой вершине требуется ${ displaystyle O (d_ {in} log p log ^ {1+ epsilon} q)}$ битовые операции, где ${ displaystyle d_ {in}}$ внутренняя степень вершины ${ Displaystyle в (е)}$ . Для проверки подписи требуется ${ Displaystyle О ((д + к) журнал ^ {2+ эпсилон} д)}$ битовые операции.

Доказательство безопасности

Злоумышленник может вызвать коллизию под хеш-функцией.

Если дано ${ displaystyle (P_ {1}, ldots, P_ {r})}$ указывает в ${ displaystyle E [p]}$ найти ${ displaystyle a = (a_ {1}, ldots, a_ {r}) in mathbb {F} _ {p} ^ {r}}$ и ${ displaystyle b = (b_ {1}, ldots, b_ {r}) in mathbb {F} _ {p} ^ {r}}$

такой, что ${ displaystyle a not = b}$ и

{ displaystyle sum _ {1 leq i leq r} (a_ {i} P_ {i}) = sum _ {1 leq j leq r} (b_ {j} P_ {j}).}

Утверждение: есть полиномиальное сокращение времени от дискретного журнала на циклическая группа порядка ${ displaystyle p}$ на эллиптических кривых к Hash-Collision.

Если ${ displaystyle r = 2}$ , то получаем ${ Displaystyle xP + yQ = uP + vQ}$ . Таким образом ${ Displaystyle (х-и) п + (у-v) Q = 0}$ .Мы утверждаем, что ${ Displaystyle х not = и}$ и ${ Displaystyle у not = v}$ . Предположим, что ${ displaystyle x = u}$ , тогда у нас было бы ${ displaystyle (y-v) Q = 0}$ , но ${ displaystyle Q}$ это по порядку ведения заседания ${ displaystyle p}$ (простое число) таким образом ${ Displaystyle у-и эквив 0 { bmod {p}}}$ . Другими словами ${ displaystyle y = v}$ в ${ displaystyle mathbb {F} _ {p}}$ . Это противоречит предположению, что ${ Displaystyle (х, у)}$ и ${ Displaystyle (и, v)}$ различные пары в ${ displaystyle mathbb {F} _ {2}}$ . Таким образом, мы имеем ${ Displaystyle Q = - (х-и) (у-v) ^ {- 1} P}$ , где обратная величина берется по модулю ${ displaystyle p}$ .

Если у нас r> 2, мы можем сделать одно из двух. Либо мы можем взять ${ displaystyle P_ {1} = P}$ и ${ displaystyle P_ {2} = Q}$ как прежде и установить ${ displaystyle P_ {i} = O}$ за ${ displaystyle i}$ > 2 (в этом случае доказательство сводится к случаю, когда ${ displaystyle r = 2}$ ), или мы можем взять ${ displaystyle P_ {1} = r_ {1} P}$ и ${ displaystyle P_ {i} = r_ {i} Q}$ куда ${ displaystyle r_ {i}}$ выбираются случайным образом из ${ displaystyle mathbb {F} _ {p}}$ . Мы получаем одно уравнение с одной неизвестной (дискретный журнал ${ displaystyle Q}$ ). Вполне возможно, что полученное уравнение не включает неизвестное. Однако это происходит с очень малой вероятностью, как мы рассуждаем дальше. Предположим, алгоритм Hash-Collision дал нам, что

{ displaystyle ar_ {1} P + sum _ {2 leq i leq r} (b_ {i} r_ {i} Q) = 0.}

Тогда пока ${ displaystyle sum _ {2 leq i leq r} b_ {i} r_ {i} not Equiv 0 { bmod {p}}}$ , мы можем найти дискретный журнал Q. Но ${ displaystyle r_ {i}}$ Оракулу неизвестны для Hash-Collision, поэтому мы можем поменять местами порядок, в котором происходит этот процесс. Другими словами, учитывая ${ displaystyle b_ {i}}$ , за ${ Displaystyle 2 Leq я Leq г}$ , не все равны нулю, какова вероятность того, что ${ displaystyle r_ {i}}$ Мы выбрали удовлетворение ${ Displaystyle сумма _ {2 leq я leq r} (b_ {i} r_ {i}) = 0}$ ? Ясно, что последняя вероятность равна ${ displaystyle 1 over p}$ . Таким образом, с большой вероятностью мы сможем найти дискретный логарифм ${ displaystyle Q}$ .

Мы показали, что создавать хеш-коллизии в этой схеме сложно. Другой метод, с помощью которого злоумышленник может помешать нашей системе, - это подделка подписи. Эта схема для подписи по сути является версией схемы подписи Boneh-Lynn-Shacham с использованием агрегированной подписи.^[4] Здесь показано, что подделка подписи не менее сложна, чем решение эллиптическая кривая Диффи – Хеллмана проблема. Единственный известный способ решить эту проблему на эллиптических кривых - это вычисление дискретных журналов. Таким образом, подделка подписи не менее сложна, чем решение вычислительного ко-Диффи – Хеллмана на эллиптических кривых, и, вероятно, так же сложно, как вычисление дискретных журналов.

Смотрите также

внешняя ссылка

[1] «Подписи для сетевого кодирования». 2006 г. CiteSeerX 10.1.1.60.4738. Цитировать журнал требует | журнал = (помощь)

[2] ttps://www.cs.princeton.edu/~mfreed/docs/authcodes-sp04.pdf

[3] Эйзентрегер, Кирстен; Лаутер, Кристин; Монтгомери, Питер Л. (2004). «Улучшенные пары Вейля и Тейта для эллиптических и гиперэллиптических кривых»: 169–183. arXiv:математика / 0311391. Bibcode:2003математика ..... 11391E. CiteSeerX 10.1.1.88.8848. Цитировать журнал требует | журнал = (помощь)

[4] ttp://cseweb.ucsd.edu/~hovav/dist/sigs.pdf

[1]

[2]

[3]

[4]