Гомоморфные подписи для сетевого кодирования

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

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

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

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

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

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

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

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

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

Декодирование на ресивере

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

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

затем

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

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

История

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

$H$ устойчив к столкновениям – его трудно найти $x$ и $y$ такой, что $H(x)=H(y)$ ;
$H$ является гомоморфизмом – $H(x+y)=H(x)+H(y)$ .

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

y=\sum _{1\leq i\leq k}(\alpha _{i}v_{i})

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

H(y)=\sum _{1\leq i\leq k}(\alpha _{i}H(v_{i}))

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

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

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

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

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

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

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

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

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

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

Позволять $K\supseteq \mathbb {F} _{q}$ , затем,

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

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

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

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

Если $E/\mathbb {F} _{q}$ представляет собой эллиптическую кривую и $\gcd(m,q)=1$ затем

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

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

(Билинейный) $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)$ .
(Невырожденный) $e_{m}(P,Q)=1$ для всех P следует, что $Q=O$ .
(поочередно) $e_{m}(P,P)=1$ .

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

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

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

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

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

Данный $v=u_{1},\ldots ,u_{D}$ и его подпись $\sigma$ , убедитесь, что

{\begin{aligned}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{aligned}}

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

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

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

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

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

Злоумышленник может произвести коллизию с помощью хэш-функции.

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

такой, что $a\not =b$ и

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

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

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

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

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

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

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

См. также

Ссылки

^ «Сигнатуры для сетевого кодирования» . 2006. CiteSeerX 10.1.1.60.4738 . Архивировано из оригинала 20 ноября 2021 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Крон, Максвелл Н.; Фридман, Майкл Дж; Мазьер, Давид (2004). «Мгновенная проверка кодов стирания без скорости для эффективного распространения контента» (PDF) . Симпозиум IEEE по безопасности и конфиденциальности, 2004 г. Материалы. 2004 . Беркли, Калифорния, США. стр. 226–240. дои : 10.1109/SECPRI.2004.1301326 . ISBN 0-7695-2136-3 . ISSN 1081-6011 . S2CID 6976686 . Проверено 17 ноября 2022 г. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Эйзентрегер, Кирстен; Лаутер, Кристин; Монтгомери, Питер Л. (2004). «Улучшенные пары Вейля и Тейта для эллиптических и гиперэллиптических кривых» : 169–183. arXiv : math/0311391 . Бибкод : 2003math.....11391E . CiteSeerX 10.1.1.88.8848 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Боне, Дэн; Линн, Бен; Шахам, Ховав (2001). «Краткие подписи пары Вейля» (PDF) . Достижения в криптологии — ASIACRYPT 2001 . Конспекты лекций по информатике. Том. 2248. стр. 514–532. дои : 10.1007/3-540-45682-1_30 . ISBN 978-3-540-45682-7 . Проверено 17 ноября 2022 г.

Внешние ссылки

[1] «Сигнатуры для сетевого кодирования» . 2006. CiteSeerX 10.1.1.60.4738 . Архивировано из оригинала 20 ноября 2021 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[2] Крон, Максвелл Н.; Фридман, Майкл Дж; Мазьер, Давид (2004). «Мгновенная проверка кодов стирания без скорости для эффективного распространения контента» (PDF) . Симпозиум IEEE по безопасности и конфиденциальности, 2004 г. Материалы. 2004 . Беркли, Калифорния, США. стр. 226–240. дои : 10.1109/SECPRI.2004.1301326 . ISBN 0-7695-2136-3 . ISSN 1081-6011 . S2CID 6976686 . Проверено 17 ноября 2022 г. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

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

[4] Боне, Дэн; Линн, Бен; Шахам, Ховав (2001). «Краткие подписи пары Вейля» (PDF) . Достижения в криптологии — ASIACRYPT 2001 . Конспекты лекций по информатике. Том. 2248. стр. 514–532. дои : 10.1007/3-540-45682-1_30 . ISBN 978-3-540-45682-7 . Проверено 17 ноября 2022 г.

[1]

[2]

[3]

[4]