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

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

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

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

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

Каждый приёмник <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

История

Крон, Фридман и Мэзиэс в 2004 году предложили теориюШаблон:Sfn: если у нас есть хеш-функция <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

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

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

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

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

Пусть <math>\mathbb{F}_q</math> конечное поле такое, что <math>q</math> не является степенью 2 или 3. Тогда эллиптическая кривая <math>E</math> над <math>\mathbb{F}_q</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

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

Вейль-спариванием является билинейное отображение, сопоставляющее двум точкам подгруппы <math>m</math>-кручения точек эллиптической кривой <math>E</math> корень степени <math>m</math> в конечном поле.Шаблон:Sfn Пусть <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:

(Билинейность) <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 Подписью вектора <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

<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

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

Сервер вычисляетШаблон:Sfn <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 <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>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>\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

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

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.