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

[[Сетевое кодирование]] предоставляет возможность увеличить [[Пропускная способность|пропускную способность]] и улучшить устойчивость сети без какого-либо централизованного управления. К сожалению, оно очень восприимчиво к атакам, в которых вредоносные узлы изменяют данные. Благодаря тому, как [[Пакет (сетевые технологии)|пакеты]] распространяются в сети, единственный неправильный пакет данных может сделать недействительными все дальнейшие данные.{{sfn|R. Gennaro, J. Katz, H. Krawczyk,T. Rabin|2011|p = 1}} Злоумышленник может повредить пакет, даже если он зашифрован: для этого ему нужно подделать [[Электронная подпись|подпись]], либо найти [[Коллизия хеш-функции|коллизии]] используемой [[Хеширование|хеш-функции]].{{sfn|D. Charles, K. Jain,K. Lauter|2006|p = 3}} Денис Чарльз, Камал Джаин и Кристин Лаутер разработали новую схему [[Гомоморфное шифрование|гомоморфного шифрования]], позволяющую предотвратить такие атаки.{{sfn|D. Charles, K. Jain,K. Lauter|2006}} Использование гомоморфной подписи позволяет узлам подписывать любую линейную комбинацию входящих пакетов. В этой схеме узел не может подписать [[Линейная комбинация|линейную комбинацию]] пакетов,не раскрывая, какая линейная комбинация использовалась. Кроме того, схема подписи защищена в соответствии с предположениями о сложности вычисления [[Дискретное логарифмирование|дискретного логарифма]] и сложности решения задачи [[Протокол Диффи — Хеллмана|Диффи-Хеллмана]].{{sfn|D. Charles, K. Jain,K. Lauter|2006|p = 1}}

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

: <math>y(e) = \sum_{f:\mathrm{out}(f)=v}(m_e(f)y(f))</math>

где <math>m_e(f) \in \mathbb{F}_p</math>. Мы считаем, что источник является конечной вершиной <math>k</math> дуг, передающих <math>k</math> векторов <math>w_i</math>. По [[Математическая индукция|индукции]], пусть вектор <math>y(e)</math> какой-либо дуги является линейной комбинацией <math>y(e) = \sum_{1 \le i \le k}(g_i(e)v_i)</math> и является вектором в <math>V</math>. Тогда ''k''-мерный вектор <math>g(e) = (g_1(e), \ldots , g_k(e))</math> это просто ''k'' первых координат вектора <math>y(e)</math>. Назовем [[Матрица (математика)|матрицу]], строками которой являются векторы <math>g(e_1), \ldots , g(e_k)</math>, где <math>e_i</math> рёбра, входящие в вершину <math>t \in T</math>, ''глобальной матрицей кодирования'' ''для'' <math>t</math> и обозначим её <math>G_t</math>. На практике векторы кодирования выбираются случайно, поэтому матрица <math>G_t</math> с высокой вероятностью [[Обратная матрица|обратима]]. Таким образом, любой приёмник, получивший <math>y_1, \ldots , y_k</math>, может найти <math>w_1,\ldots ,w_k</math>, решив
: <math>\begin{bmatrix} y'\\ y_2' \\  \vdots \\ y_k' \end{bmatrix} = G_t \begin{bmatrix} w_1\\ w_2 \\ \vdots \\ w_k \end{bmatrix}</math>

где <math>y_i'</math> векторы, образованные удалением первых <math>k</math> координат вектора <math>y_i</math>.{{sfn|D. Charles, K. Jain,K. Lauter|2006|p = 2}}

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

: <math>y_i = (\alpha_{i_1}, \ldots , \alpha_{i_k}, a_{i_1}, \ldots , a_{i_d})</math>

тогда

: <math>y_i = \sum_{1 \le j \le k}(\alpha_{ij}v_j).</math>

Таким образом, мы можем с высокой [[вероятность]]ю обратить линейной преобразование и найти <math>v_i</math>.{{sfn|D. Charles, K. Jain,K. Lauter|2006|p = 2}}

== История ==
Крон, Фридман и Мэзиэс в 2004 году предложили теорию{{sfn|M. Krohn, M. Freedman,D. Mazieres|2004}}: если у нас есть хеш-функция <math>H : V \longrightarrow G</math> такая, что:
* <math>H</math> стойка к коллизиям – сложно найти <math>x</math> и <math>y</math> такие, что <math>H(x) = H(y)</math>;
* <math>H</math> является [[гомоморфизм]]ом – <math>H(x+y) = H(x) + H(y)</math>.

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

: <math>y =   \sum_{1 \leq i\leq k} (\alpha_iv_i)</math>

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

: <math>H(y) =    \sum_{1 \leq i\leq k} (\alpha_iH(v_i))</math>

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

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

# Реализуют [[Аутентификация|аутентификацию]] в дополнение к выявлению подмены пакетов.
# Нет необходимости в передаче [[Хеш-сумма|хеш-сумм]] по защищенному каналу.
# Открытая информация не изменяется для последующей передачи файлов.{{sfn|D. Charles, K. Jain,K. Lauter|2006|p = 1}}

==Схема подписи==
Гомоморфное свойство подписей позволяет узлам подписывать какую-либо линейную комбинацию входящих пакетов, не используя схему подписи.{{sfn|D. Charles, K. Jain,K. Lauter|2006|p = 1}}

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

Пусть <math>\mathbb{F}_q</math> конечное поле такое, что <math>q</math> не является степенью 2 или 3. Тогда эллиптическая кривая <math>E</math> над <math>\mathbb{F}_q</math> является кривой, задающейся уравнением вида
: <math> y^2 = x^3 + ax + b, \, </math>

где <math>a, b  \in   \mathbb{F}_q</math> такие, что <math>4a^3 + 27b^2 \not= 0</math>

Пусть <math>K \supseteq \mathbb{F}_q</math>, тогда

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

образует [[Абелева группа|абелеву группу]].{{sfn|Silverman|2009|pp=51-52}}

===Вейль-спаривание=== 
Вейль-спариванием является [[билинейное отображение]], сопоставляющее двум точкам подгруппы <math>m</math>-[[Кручение (алгебра)|кручения]] точек эллиптической кривой <math>E</math> корень степени <math>m</math> в конечном поле.{{sfn|Silverman|2009|pp=92-94}} Пусть <math>E/\mathbb{F}_q</math> эллиптическая кривая и пусть <math>\mathbb{\bar{F}}_q</math> [[Замыкание (алгебра)|алгебраическое замыкание]] <math>\mathbb{F}_q</math>. Если <math>m</math> целое и взаимно-простое с [[Характеристика кольца|характеристикой поля]] <math>\mathbb{F}_q</math>, тогда группа элементов <math>m</math>-кручения <math>E[m] = {P \in  E(\mathbb{\bar {F}}_q) : mP = O}</math>.

Вейль-спаривание <math>e_m : E[m] * E[m] \rightarrow \mu_m(\mathbb{F}_q)</math> обладает свойствами{{sfn|D. Charles, K. Jain,K. Lauter|2006|p = 2}}:

#([[Билинейное отображение|Билинейность]]) <math>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)</math>.
#(Невырожденность) <math>e_m(P,Q) = 1</math> for all ''P'' implies that <math>Q = O</math>.
#(Тождественность) <math>e_m(P, P) = 1</math>.

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

Пусть <math>p</math> простое число и <math>q</math> степень другого простого числа: <math>p<<q</math>. Пусть <math>V/\mathbb{F}_p</math> векторное пространство размерности <math>D</math> и <math>E/\mathbb{F}_q</math> эллиптическая кривая такая, что <math>P_1, \ldots , P_D  \in   E[p]</math>.
Определим <math>h : V \longrightarrow E[p]</math> следующим образом:
<math>h(u_1, \ldots , u_D) =   \sum_{1 \leq i\leq D} (u_iP_i)</math>.
Эта функция <math>h</math> гомоморфизм <math>V</math> в <math>E[p]</math>.

Сервер выбирает секретно <math>s_1, \ldots , s_D</math> в <math>\mathbb{F}_p</math> и публикует точку <math>Q</math>, являющуюся элементом <math>p</math>-кручения, такую, что <math>e_p(P_i,Q) \not=  1</math> и публикует  <math>(P_i, s_iQ)</math>, где <math>1 \leq i \leq D</math>.{{sfn|D. Charles, K. Jain,K. Lauter|2006|p = 2}}
Подписью вектора <math>v = u_1, \ldots , u_D</math> является 
<math>\sigma(v) =   \sum_{1 \leq i\leq D} (u_is_iP_i)</math>

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

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

Даны <math>v = u_1, \ldots , u_D</math> и подпись <math>\sigma</math>. Для проверки подлинности требуется проверить равенство{{sfn|D. Charles, K. Jain,K. Lauter|2006|p = 3}}

: <math>
\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_iQ)
\end{align}
</math>

[[Верификация]] использует билинейность Вейль-спаривания.{{sfn|D. Charles, K. Jain,K. Lauter|2006|p = 1}}

==Настройка системы==
Сервер вычисляет{{sfn|D. Charles, K. Jain,K. Lauter|2006|p = 3}} <math>\sigma(v_i)</math> для каждого <math>1 \leq i \leq k</math>. Передаёт <math>v_i, \sigma(v_i)</math>.
На каждом ребре <math>e</math> при вычислении
<math>y(e) =  \sum_{f \in E:\mathrm{out}(f)=\mathrm{in}(e)} (m_e(f)y(f))</math>
также вычисляется
<math>\sigma(y(e)) =  \sum_{f \in E:\mathrm{out}(f)=\mathrm{in}(e)} (m_e(f)\sigma(y(f)))</math>
на эллиптической кривой <math>E</math>.

Подписью является точка на эллиптической кривой с координатами в <math>\mathbb{F}_q</math>. Таким образом, размер подписи{{sfn|D. Charles, K. Jain,K. Lauter|2006|p = 3}} <math>2 \log q</math> бит, и это дополнительные расходы на передачу.

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

Если даны <math>(P_1, \ldots , P_r)</math> точки в <math>E[p]</math>, найдём
<math>a = (a_1, \ldots , a_r)  \in  \mathbb{F}_p^r</math> и <math>b = (b_1, \ldots , b_r)  \in  \mathbb{F}_p^r</math>

такие, что <math>a \not= b</math> и

: <math>\sum_{1 \leq i \leq r} (a_iP_i) = \sum_{1 \leq j \leq r} (b_jP_j).</math>

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

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

: <math>ar_1P + \sum_{2 \leq i \leq r}(b_ir_iQ) = 0.</math>

До тех пор, пока  <math>\sum_{2 \leq i \leq r} b_ir_i \not\equiv 0 \bmod p</math>, нужно решать дискретный логарифм <math>Q</math>. Рассмотрим <math>b_i</math>, где <math>2 \leq i \leq r</math>, не равные нулю одновременно. Какова вероятность, что выбранные <math>r_i</math> удовлетворяют условию  <math>\sum_{2 \leq i \leq r} (b_ir_i) = 0</math>? Она равна  <math>1 \over p</math> . Таким образом, с большой долей вероятности придется решать дискретный логарифм <math>Q</math>.{{sfn|D. Charles, K. Jain,K. Lauter|2006|pp = 3-4}}

Мы показали, что сложно найти коллизии хеш-функции в данной схеме. Другой способ нарушить работу системы – подделать подпись. Эта схема подписи является версией  схемы  BLS (Boneh – Lynn - Shacham). Подделать подпись, по крайней мере так же сложно, как решить вычислительную проблему Диффи-Хелмана.{{sfn|D. Boneh, B. Lynn,H. Shacham|2001}} Единственный известный способ решить эту проблему на эллиптических кривых – вычислить дискретный логарифм. Таким образом, подделать подпись так же сложно, как вычислить дискретный логарифм.{{sfn|D. Charles, K. Jain,K. Lauter|2006|p = 4}}

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

== Примечания ==
{{примечания}}

== Литература ==
* {{книга
|подзаголовок
|заглавие=The Arithmetic of Elliptic Curves
|оригинал=
|ссылка=https://archive.org/details/arithmeticellipt00silv
|автор= Joseph H. Silverman
|год=2009
|место=N. Y.
|издательство=Springer
|pages=[https://archive.org/details/arithmeticellipt00silv/page/n68 51]-52,92-94
|allpages=408
|isbn= 978-0-387-09493-9
|ref= Silverman
}}
* {{статья
  |автор          =  R. Gennaro, J. Katz, H. Krawczyk,T. Rabin
  |заглавие       = Secure Network Coding Over the Integers
  |ссылка         = http://www.iacr.org/archive/pkc2010/60560142/60560142.pdf
  |год            = 2011
  |pages         = 19
  |ref            = R. Gennaro, J. Katz, H. Krawczyk,T. Rabin
}}
* {{статья
  |автор          =  D. Charles, K. Jain,K. Lauter
  |заглавие       = SIGNATURES FOR NETWORK CODING
  |ссылка         = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.4738&rep=rep1&type=pdf
  |год            = 2006
  |pages         = 7
  |ref            = D. Charles, K. Jain,K. Lauter
}}
* {{статья
  |автор          =  M. Krohn, M. Freedman,D. Mazieres
  |заглавие       = On-the-Fly Verification of Rateless Erasure Codes for Efficient Content Distribution
  |ссылка         = http://www.scs.stanford.edu/~dm/home/papers/krohn:authcodes.pdf
  |год            = 2004
  |pages         = 15
  |ref            = M. Krohn, M. Freedman,D. Mazieres
}}
* {{статья
  |автор          =   D. Boneh, B. Lynn,H. Shacham
  |заглавие       = Short Signatures from the Weil Pairing
  |ссылка         = http://cseweb.ucsd.edu/~hovav/dist/sigs.pdf
  |год            = 2001
  |pages         = 24
  |ref            = D. Boneh, B. Lynn,H. Shacham
}}

== Ссылки ==
* [http://research.microsoft.com/pubs/69452/imc06.pdf Comprehensive View of a Live Network Coding P2P System]
* [http://research.microsoft.com/en-us/um/people/klauter/CISS_06.pdf Signatures for Network Coding(presentation) CISS 2006, Princeton]
* [https://web.archive.org/web/20110606191907/http://www.cse.buffalo.edu/~atri/courses/coding-theory/fall07.html University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra]

[[Категория:Теория кодирования]]
[[Категория:Информационная безопасность]]