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

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

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

Пусть $G=(V,E)$ ориентированный граф, состоящий из множества $V$, элементы которого называются вершинами, и множества $E$ упорядоченных пар вершин $u,v\in V$, именуемых направленными рёбрами или дугами. Задача источника $s\in V$ – отправить файл $D$ множеству вершин $T\subseteq V$. Выбирается векторное пространство $W/{𝔽}_p$ (скажем, размерности $d$), где $p$ простое, и данные, являющиеся множеством векторов $w_1,\dots ,w_k\in W$. Источник создаёт расширенные векторы $v_1,\dots ,v_k$,определенные следующим образом $v_i=(0,\dots ,0,1,\dots ,0,w_{i_1},\dots ,w_{i_d})$, где $w_{i_j}$ $j$-я координата вектора $w_i$. Перед первой $1$ в векторе $v_i$ находится $(i-1)$ нулей. Без потери общности можно считать, что векторы $v_i$ линейно независимы. Обозначим линейное подпространство (из ${𝔽}_p^{k+d}$ ), натянутое на эти векторы, буквой $V$. Каждая исходящая дуга $e\in E$ вычисляет линейную комбинацию $y(e)$ векторов, входящих в начальную вершину дуги $v=in(e)$. То есть

$y(e)=\sum _{f:\mathrm{o}\mathrm{u}\mathrm{t}(f)=v}(m_e(f)y(f))$

где $m_e(f)\in {𝔽}_p$. Мы считаем, что источник является конечной вершиной $k$ дуг, передающих $k$ векторов $w_i$. По индукции, пусть вектор $y(e)$ какой-либо дуги является линейной комбинацией $y(e)=\sum _{1\le i\le k}(g_i(e)v_i)$ и является вектором в $V$. Тогда k-мерный вектор $g(e)=(g_1(e),\dots ,g_k(e))$ это просто k первых координат вектора $y(e)$. Назовем матрицу, строками которой являются векторы $g(e_1),\dots ,g(e_k)$, где $e_i$ рёбра, входящие в вершину $t\in T$, глобальной матрицей кодирования для $t$ и обозначим её $G_t$. На практике векторы кодирования выбираются случайно, поэтому матрица $G_t$ с высокой вероятностью обратима. Таким образом, любой приёмник, получивший $y_1,\dots ,y_k$, может найти $w_1,\dots ,w_k$, решив

$\left[\begin{array}{c}{y}^{\prime }\\ {y_2}^{\prime }\\ ⋮\\ {y_k}^{\prime }\end{array}\right]=G_t\left[\begin{array}{c}{w}_1\\ w_2\\ ⋮\\ w_k\end{array}\right]$

где ${y_i}^{\prime }$ векторы, образованные удалением первых $k$ координат вектора $y_i$.Шаблон:Sfn

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

Каждый приёмник $t\in T$, получает $k$ векторов $y_1,\dots ,y_k$, являющихся случайными линейными комбинациями векторов $v_i$. В самом деле, если

$y_i=({\alpha }_{i_1},\dots ,{\alpha }_{i_k},a_{i_1},\dots ,a_{i_d})$

тогда

$y_i=\sum _{1\le j\le k}({\alpha }_{ij}{v}_j).$

Таким образом, мы можем с высокой вероятностью обратить линейной преобразование и найти $v_i$.Шаблон:Sfn

История

Крон, Фридман и Мэзиэс в 2004 году предложили теориюШаблон:Sfn: если у нас есть хеш-функция $H:V⟶G$ такая, что:

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

Тогда сервер может отправить $H(v_i)$ каждому приёмнику. Если

$y=\sum _{1\le i\le k}({\alpha }_i{v}_i)$

мы можем проверить равенство

$H(y)=\sum _{1\le i\le k}({\alpha }_{i}H(v_i))$

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

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

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

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

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

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

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

Пусть ${𝔽}_q$ конечное поле такое, что $q$ не является степенью 2 или 3. Тогда эллиптическая кривая $E$ над ${𝔽}_q$ является кривой, задающейся уравнением вида

$y^2=x^3+ax+b,$

где $a,b\in {𝔽}_q$ такие, что $4a^3+27b^2=0$

Пусть $K\supseteq {𝔽}_q$, тогда

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

образует абелеву группу.Шаблон:Sfn

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

Вейль-спариванием является билинейное отображение, сопоставляющее двум точкам подгруппы $m$-кручения точек эллиптической кривой $E$ корень степени $m$ в конечном поле.Шаблон:Sfn Пусть $E/{𝔽}_q$ эллиптическая кривая и пусть ${\overline{𝔽}}_q$ алгебраическое замыкание ${𝔽}_q$. Если $m$ целое и взаимно-простое с характеристикой поля ${𝔽}_q$, тогда группа элементов $m$-кручения $E[m]=P\in E({\overline{𝔽}}_q):mP=O$.

Вейль-спаривание $e_m:E[m]*E[m]\to {\mu }_m({𝔽}_q)$ обладает свойствамиШаблон:Sfn:

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/{𝔽}_p$ векторное пространство размерности $D$ и $E/{𝔽}_q$ эллиптическая кривая такая, что $P_1,\dots ,P_D\in E[p]$. Определим $h:V⟶E[p]$ следующим образом: $h(u_1,\dots ,u_D)=\sum _{1\le i\le D}(u_i{P}_i)$. Эта функция $h$ гомоморфизм $V$ в $E[p]$.

Сервер выбирает секретно $s_1,\dots ,s_D$ в ${𝔽}_p$ и публикует точку $Q$, являющуюся элементом $p$-кручения, такую, что $e_p(P_i,Q)=1$ и публикует $(P_i,s_{i}Q)$, где $1\le i\le D$.Шаблон:Sfn Подписью вектора $v=u_1,\dots ,u_D$ является $\sigma (v)=\sum _{1\le i\le D}(u_i{s}_i{P}_i)$

Замечание: эта подпись гомоморфна,поскольку $h$ гомоморфизм.

Проверка подлинности подписи

Даны $v=u_1,\dots ,u_D$ и подпись $\sigma$. Для проверки подлинности требуется проверить равенствоШаблон:Sfn

$\begin{array}{cc}{e}_p(\sigma ,Q)& =e_p(\sum _{1\le i\le D}(u_i{s}_i{P}_i),Q)\\ & =\prod _i{e}_p(u_i{s}_i{P}_i,Q)\\ & =\prod _i{e}_p(u_i{P}_i,s_{i}Q)\end{array}$

Верификация использует билинейность Вейль-спаривания.Шаблон:Sfn

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

Сервер вычисляетШаблон:Sfn $\sigma (v_i)$ для каждого $1\le i\le k$. Передаёт $v_i,\sigma (v_i)$. На каждом ребре $e$ при вычислении $y(e)=\sum _{f\in E:\mathrm{o}\mathrm{u}\mathrm{t}(f)=\mathrm{i}\mathrm{n}(e)}(m_e(f)y(f))$ также вычисляется $\sigma (y(e))=\sum _{f\in E:\mathrm{o}\mathrm{u}\mathrm{t}(f)=\mathrm{i}\mathrm{n}(e)}(m_e(f)\sigma (y(f)))$ на эллиптической кривой $E$.

Подписью является точка на эллиптической кривой с координатами в ${𝔽}_q$. Таким образом, размер подписиШаблон:Sfn $2\log q$ бит, и это дополнительные расходы на передачу.

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

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

Если даны $(P_1,\dots ,P_r)$ точки в $E[p]$, найдём $a=(a_1,\dots ,a_r)\in {𝔽}_p^r$ и $b=(b_1,\dots ,b_r)\in {𝔽}_p^r$

такие, что $a=b$ и

$\sum _{1\le i\le r}(a_i{P}_i)=\sum _{1\le j\le r}(b_j{P}_j).$

Если $r=2$, тогда мы получаем $xP+yQ=uP+vQ$. То есть $(x-u)P+(y-v)Q=0$. $x=u$ и $y=v$. Допустим, что $x=u$, тогда $(y-v)Q=0$, но $Q$ точка порядка $p$ (простое число), таким образом $y-v\equiv 0modp$. Другими словами $y=v$ в ${𝔽}_p$. Это противоречит предположению о том, что $(x,y)$ и $(u,v)$ различные пары в ${𝔽}_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$ выбираются случайным образом из ${𝔽}_p$. Получаем одно уравнение с одним неизвестным (дискретный логарифм $Q$). Вполне возможно, что полученное уравнение не будет содержать неизвестную величину. Тем не менее, это происходит с очень маленькой вероятностью. Предположим, что алгоритм поиска коллизий дал нам

$a{r}_{1}P+\sum _{2\le i\le r}(b_i{r}_{i}Q)=0.$

До тех пор, пока $\sum _{2\le i\le r}{b}_i{r}_i\equiv ̸0modp$, нужно решать дискретный логарифм $Q$. Рассмотрим $b_i$, где $2\le i\le r$, не равные нулю одновременно. Какова вероятность, что выбранные $r_i$ удовлетворяют условию $\sum _{2\le i\le r}(b_i{r}_i)=0$? Она равна $\frac{1}{p}$ . Таким образом, с большой долей вероятности придется решать дискретный логарифм $Q$.Шаблон:Sfn

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья

Ссылки

• 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