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

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

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

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

$y(e)=\underset{f:\mathrm{o}\mathrm{u}\mathrm{t}(f)=v}{\sum <!--\; \sum \; -->}(m_e(f)y(f))$$y(e)=\sum _{f:\mathrm {out} (f)=v}(m_{e}(f)y(f))$ 

где $m_e(f)\in <!--\; \in \; -->{\mathbb{F}}_p$$m_{e}(f)\in \mathbb {F} _{p}$ . Мы считаем, что источник является конечной вершиной $k$$k$  дуг, передающих $k$$k$  векторов $w_i$$w_{i}$ . По индукции, пусть вектор $y(e)$$y(e)$  какой-либо дуги является линейной комбинацией $y(e)=\underset{1\le <!--\; \le \; -->i\le <!--\; \le \; -->k}{\sum <!--\; \sum \; -->}(g_i(e)v_i)$$y(e)=\sum _{1\leq i\leq k}(g_{i}(e)v_{i})$  и является вектором в $V$$V$ . Тогда k-мерный вектор $g(e)=(g_1(e),\dots <!--\; \dots \; -->,g_k(e))$$g(e)=(g_{1}(e),\ldots ,g_{k}(e))$  это просто k первых координат вектора $y(e)$$y(e)$ . Назовем матрицу, строками которой являются векторы $g(e_1),\dots <!--\; \dots \; -->,g(e_k)$$g(e_{1}),\ldots ,g(e_{k})$ , где $e_i$$e_{i}$  рёбра, входящие в вершину $t\in <!--\; \in \; -->T$$t\in T$ , глобальной матрицей кодирования для $t$$t$  и обозначим её $G_t$$G_{t}$ . На практике векторы кодирования выбираются случайно, поэтому матрица $G_t$$G_{t}$  с высокой вероятностью обратима. Таким образом, любой приёмник, получивший $y_1,\dots <!--\; \dots \; -->,y_k$$y_{1},\ldots ,y_{k}$ , может найти $w_1,\dots <!--\; \dots \; -->,w_k$$w_{1},\ldots ,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]$${\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^{\prime }$$y_{i}'$  векторы, образованные удалением первых $k$$k$  координат вектора $y_i$$y_{i}$ .

ДекодированиеПравить

Каждый приёмник $t\in <!--\; \in \; -->T$$t\in T$ , получает $k$$k$  векторов $y_1,\dots <!--\; \dots \; -->,y_k$$y_{1},\ldots ,y_{k}$ , являющихся случайными линейными комбинациями векторов $v_i$$v_{i}$ . В самом деле, если

$y_i=({\mathrm{\alpha <!--\; \alpha \; -->}}_{i_1},\dots <!--\; \dots \; -->,{\mathrm{\alpha <!--\; \alpha \; -->}}_{i_k},a_{i_1},\dots <!--\; \dots \; -->,a_{i_d})$$y_{i}=(\alpha _{i_{1}},\ldots ,\alpha _{i_{k}},a_{i_{1}},\ldots ,a_{i_{d}})$ 

тогда

$y_i=\underset{1\le <!--\; \le \; -->j\le <!--\; \le \; -->k}{\sum <!--\; \sum \; -->}({\mathrm{\alpha <!--\; \alpha \; -->}}_{ij}{v}_j).$$y_{i}=\sum _{1\leq j\leq k}(\alpha _{ij}v_{j}).$ 

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

ИсторияПравить

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

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

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

$y=\underset{1\le <!--\; \le \; -->i\le <!--\; \le \; -->k}{\sum <!--\; \sum \; -->}({\mathrm{\alpha <!--\; \alpha \; -->}}_i{v}_i)$$y=\sum _{1\leq i\leq k}(\alpha _{i}v_{i})$ 

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

$H(y)=\underset{1\le <!--\; \le \; -->i\le <!--\; \le \; -->k}{\sum <!--\; \sum \; -->}({\mathrm{\alpha <!--\; \alpha \; -->}}_{i}H(v_i))$$H(y)=\sum _{1\leq i\leq k}(\alpha _{i}H(v_{i}))$ 

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

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

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

Схема подписиПравить

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

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

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

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

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

где $a,b\in <!--\; \in \; -->{\mathbb{F}}_q$$a,b\in \mathbb {F} _{q}$  такие, что $4a^3+27b^2\ne 0$$4a^{3}+27b^{2}\not =0$ 

Пусть $K\supseteq <!--\; \supseteq \; -->{\mathbb{F}}_q$$K\supseteq \mathbb {F} _{q}$ , тогда

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

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

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

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

Вейль-спаривание $e_m:E[m]\ast <!--\; \ast \; -->E[m]\to <!--\; \to \; -->{\mathrm{\mu <!--\; \mu \; -->}}_m({\mathbb{F}}_q)$$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)$$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$$e_{m}(P,Q)=1$  for all P implies that $Q=O$$Q=O$ .
3. (Тождественность) $e_m(P,P)=1$$e_{m}(P,P)=1$ .

Гомоморфные подписиПравить

Пусть $p$$p$  простое число и $q$$q$  степень другого простого числа: $p<<q$ . Пусть $V/{\mathbb{F}}_p$$V/\mathbb {F} _{p}$  векторное пространство размерности $D$$D$  и $E/{\mathbb{F}}_q$$E/\mathbb {F} _{q}$  эллиптическая кривая такая, что $P_1,\dots <!--\; \dots \; -->,P_D\in <!--\; \in \; -->E[p]$$P_{1},\ldots ,P_{D}\in E[p]$ . Определим $h:V⟶<!--\; ⟶\; -->E[p]$$h:V\longrightarrow E[p]$  следующим образом: $h(u_1,\dots <!--\; \dots \; -->,u_D)=\underset{1\le <!--\; \le \; -->i\le <!--\; \le \; -->D}{\sum <!--\; \sum \; -->}(u_i{P}_i)$$h(u_{1},\ldots ,u_{D})=\sum _{1\leq i\leq D}(u_{i}P_{i})$ . Эта функция $h$$h$  гомоморфизм $V$$V$  в $E[p]$$E[p]$ .

Сервер выбирает секретно $s_1,\dots <!--\; \dots \; -->,s_D$$s_{1},\ldots ,s_{D}$  в ${\mathbb{F}}_p$$\mathbb {F} _{p}$  и публикует точку $Q$$Q$ , являющуюся элементом $p$$p$ -кручения, такую, что $e_p(P_i,Q)\ne 1$$e_{p}(P_{i},Q)\not =1$  и публикует $(P_i,s_{i}Q)$$(P_{i},s_{i}Q)$ , где $1\le <!--\; \le \; -->i\le <!--\; \le \; -->D$$1\leq i\leq D$ . Подписью вектора $v=u_1,\dots <!--\; \dots \; -->,u_D$$v=u_{1},\ldots ,u_{D}$  является $\mathrm{\sigma <!--\; \sigma \; -->}(v)=\underset{1\le <!--\; \le \; -->i\le <!--\; \le \; -->D}{\sum <!--\; \sum \; -->}(u_i{s}_i{P}_i)$$\sigma (v)=\sum _{1\leq i\leq D}(u_{i}s_{i}P_{i})$ 

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

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

Даны $v=u_1,\dots <!--\; \dots \; -->,u_D$$v=u_{1},\ldots ,u_{D}$  и подпись $\mathrm{\sigma <!--\; \sigma \; -->}$$\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}}$ 

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

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

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

Подписью является точка на эллиптической кривой с координатами в ${\mathbb{F}}_q$$\mathbb {F} _{q}$ . Таким образом, размер подписи $2\log <!--\; \; -->q$$2\log q$  бит, и это дополнительные расходы на передачу.

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

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

Если даны $(P_1,\dots <!--\; \dots \; -->,P_r)$$(P_{1},\ldots ,P_{r})$  точки в $E[p]$$E[p]$ , найдём $a=(a_1,\dots <!--\; \dots \; -->,a_r)\in <!--\; \in \; -->{\mathbb{F}}_p^r$$a=(a_{1},\ldots ,a_{r})\in \mathbb {F} _{p}^{r}$  и $b=(b_1,\dots <!--\; \dots \; -->,b_r)\in <!--\; \in \; -->{\mathbb{F}}_p^r$$b=(b_{1},\ldots ,b_{r})\in \mathbb {F} _{p}^{r}$ 

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

$\underset{1\le <!--\; \le \; -->i\le <!--\; \le \; -->r}{\sum <!--\; \sum \; -->}(a_i{P}_i)=\underset{1\le <!--\; \le \; -->j\le <!--\; \le \; -->r}{\sum <!--\; \sum \; -->}(b_j{P}_j).$$\sum _{1\leq i\leq r}(a_{i}P_{i})=\sum _{1\leq j\leq r}(b_{j}P_{j}).$ 

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

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

$a{r}_{1}P+\underset{2\le <!--\; \le \; -->i\le <!--\; \le \; -->r}{\sum <!--\; \sum \; -->}(b_i{r}_{i}Q)=0.$$ar_{1}P+\sum _{2\leq i\leq r}(b_{i}r_{i}Q)=0.$ 

До тех пор, пока $\underset{2\le <!--\; \le \; -->i\le <!--\; \le \; -->r}{\sum <!--\; \sum \; -->}{b}_i{r}_i\not\equiv 0modp$$\sum _{2\leq i\leq r}b_{i}r_{i}\not \equiv 0{\bmod {p}}$ , нужно решать дискретный логарифм $Q$$Q$ . Рассмотрим $b_i$$b_{i}$ , где $2\le <!--\; \le \; -->i\le <!--\; \le \; -->r$$2\leq i\leq r$ , не равные нулю одновременно. Какова вероятность, что выбранные $r_i$$r_{i}$  удовлетворяют условию $\underset{2\le <!--\; \le \; -->i\le <!--\; \le \; -->r}{\sum <!--\; \sum \; -->}(b_i{r}_i)=0$$\sum _{2\leq i\leq r}(b_{i}r_{i})=0$ ? Она равна $\frac{1}{p}$$1 \over p$  . Таким образом, с большой долей вероятности придется решать дискретный логарифм $Q$$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