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

Сетевое кодирование предоставляет возможность увеличить пропускную способность и улучшить устойчивость сети без какого-либо централизованного управления. К сожалению, оно очень восприимчиво к атакам, в которых вредоносные узлы изменяют данные. Благодаря тому, как пакеты распространяются в сети, единственный неправильный пакет данных может сделать недействительными все дальнейшие данные. Злоумышленник может повредить пакет, даже если он зашифрован: для этого ему нужно подделать подпись, либо найти коллизии используемой хеш-функции. Денис Чарльз, Камал Джаин и Кристин Лаутер разработали новую схему гомоморфного шифрования, позволяющую предотвратить такие атаки. Использование гомоморфной подписи позволяет узлам подписывать любую линейную комбинацию входящих пакетов. В этой схеме узел не может подписать линейную комбинацию пакетов,не раскрывая, какая линейная комбинация использовалась. Кроме того, схема подписи защищена в соответствии с предположениями о сложности вычисления дискретного логарифма и сложности решения задачи Диффи-Хеллмана.

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

Пусть $G=(V,E)$ ориентированный граф, состоящий из множества $V$, элементы которого называются вершинами, и множества $E$ упорядоченных пар вершин $u,v\in V$, именуемых направленными рёбрами или дугами. Задача источника $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}$. Перед первой $1$ в векторе $v_{i}$ находится $(i-1)$ нулей. Без потери общности можно считать, что векторы $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}$.

История

Крон, Фридман и Мэзиэс в 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$ должна быть передана всем узлам сети через отдельный защищенный канал.

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

1. Реализуют аутентификацию в дополнение к выявлению подмены пакетов.
2. Нет необходимости в передаче хеш-сумм по защищенному каналу.
3. Открытая информация не изменяется для последующей передачи файлов.

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

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

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

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

Пусть $\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\}$

образует абелеву группу.

Вейль-спаривание

Вейль-спариванием является билинейное отображение, сопоставляющее двум точкам подгруппы $m$-кручения точек эллиптической кривой $E$ корень степени $m$ в конечном поле. Пусть $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_{m}:E[m]*E[m]\rightarrow \mu _{m}(\mathbb {F} _{q})$ обладает свойствами:

1. (Билинейность) $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)$.
2. (Невырожденность) $e_{m}(P,Q)=1$ for all P implies that $Q=O$.
3. (Тождественность) $e_{m}(P,P)=1$.

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

Пусть $p$ простое число и $q$ степень другого простого числа: $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$ бит, и это дополнительные расходы на передачу.

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

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

Если даны $(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}).$

Если $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-v\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$). Вполне возможно, что полученное уравнение не будет содержать неизвестную величину. Тем не менее, это происходит с очень маленькой вероятностью. Предположим, что алгоритм поиска коллизий дал нам

$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$. Рассмотрим $b_{i}$, где $2\leq i\leq r$, не равные нулю одновременно. Какова вероятность, что выбранные $r_{i}$ удовлетворяют условию $\sum _{2\leq i\leq r}(b_{i}r_{i})=0$? Она равна $1 \over p$ . Таким образом, с большой долей вероятности придется решать дискретный логарифм $Q$.

Мы показали, что сложно найти коллизии хеш-функции в данной схеме. Другой способ нарушить работу системы – подделать подпись. Эта схема подписи является версией схемы BLS (Boneh – Lynn - Shacham). Подделать подпись, по крайней мере так же сложно, как решить вычислительную проблему Диффи-Хелмана. Единственный известный способ решить эту проблему на эллиптических кривых – вычислить дискретный логарифм. Таким образом, подделать подпись так же сложно, как вычислить дискретный логарифм.

См. также

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

Литература

• Joseph H. Silverman. The Arithmetic of Elliptic Curves. — N. Y.: Springer, 2009. — P. 51-52,92-94. — 408 p. — ISBN 978-0-387-09493-9.
• R. Gennaro, J. Katz, H. Krawczyk,T. Rabin. Secure Network Coding Over the Integers. — 2011. — P. 19.
• D. Charles, K. Jain,K. Lauter. SIGNATURES FOR NETWORK CODING. — 2006. — P. 7.
• M. Krohn, M. Freedman,D. Mazieres. On-the-Fly Verification of Rateless Erasure Codes for Efficient Content Distribution. — 2004. — P. 15.
• D. Boneh, B. Lynn,H. Shacham. Short Signatures from the Weil Pairing. — 2001. — P. 24.

Ссылки

• Comprehensive View of a Live Network Coding P2P System
• Signatures for Network Coding(presentation) CISS 2006, Princeton
• University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra