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

Сетевое кодирование Пусть ориентированный граф, состоящий из множества , элементы которого называются вершинами, и множества упорядоченных пар вершин , именуемых направленными рёбрами или дугами. Задача источника – отправить файл множеству вершин . Выбирается векторное пространство (скажем, размерности ), где простое, и данные, являющиеся множеством векторов . Источник создаёт расширенные векторы ,определенные следующим образом , где -я координата вектора . Перед первой в векторе находится нулей. Без потери общности можно считать, что векторы линейно независимы. Обозначим линейное подпространство (из ), натянутое на эти векторы, буквой . Каждая исходящая дуга вычисляет линейную комбинацию векторов, входящих в начальную вершину дуги . То есть

где . Мы считаем, что источник является конечной вершиной дуг, передающих векторов . По индукции, пусть вектор какой-либо дуги является линейной комбинацией и является вектором в . Тогда k-мерный вектор это просто k первых координат вектора . Назовем матрицу, строками которой являются векторы , где рёбра, входящие в вершину , глобальной матрицей кодирования для и обозначим её . На практике векторы кодирования выбираются случайно, поэтому матрица с высокой вероятностью обратима. Таким образом, любой приёмник, получивший , может найти , решив

где векторы, образованные удалением первых координат вектора .

Декодирование Каждый приёмник , получает векторов , являющихся случайными линейными комбинациями векторов . В самом деле, если

тогда

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

История Крон, Фридман и Мэзиэс в 2004 году предложили теорию: если у нас есть хеш-функция такая, что: стойка к коллизиям – сложно найти и такие, что ; является гомоморфизмом – .

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

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

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

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

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

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

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

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

где такие, что

Пусть , тогда

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

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

Вейль-спаривание обладает свойствами:

(Билинейность) . (Невырожденность) for all P implies that . (Тождественность) .

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

Пусть простое число и степень другого простого числа: . Пусть векторное пространство размерности и эллиптическая кривая такая, что . Определим следующим образом: . Эта функция гомоморфизм в .

Сервер выбирает секретно в и публикует точку , являющуюся элементом -кручения, такую, что и публикует , где . Подписью вектора является

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

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

Даны и подпись . Для проверки подлинности требуется проверить равенство

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

Настройка системы Сервер вычисляет для каждого . Передаёт . На каждом ребре при вычислении

также вычисляется

на эллиптической кривой .

Подписью является точка на эллиптической кривой с координатами в . Таким образом, размер подписи бит, и это дополнительные расходы на передачу.

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

Если даны точки в , найдём и

такие, что и

Если , тогда мы получаем . То есть . и . Допустим, что , тогда , но точка порядка (простое число), таким образом . Другими словами в . Это противоречит предположению о том, что и различные пары в . Таким образом , где обратный элемент берётся по модулю .

Если , мы можем взять и как раньше и установить для (в этом случае доказательство аналогично ), или мы можем взять и , где выбираются случайным образом из . Получаем одно уравнение с одним неизвестным (дискретный логарифм ). Вполне возможно, что полученное уравнение не будет содержать неизвестную величину. Тем не менее, это происходит с очень маленькой вероятностью. Предположим, что алгоритм поиска коллизий дал нам

До тех пор, пока , нужно решать дискретный логарифм . Рассмотрим , где , не равные нулю одновременно. Какова вероятность, что выбранные удовлетворяют условию ? Она равна . Таким образом, с большой долей вероятности придется решать дискретный логарифм .

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

См. также Сетевое кодирование Гомоморфное шифрование Эллиптическая криптография Протокол Диффи — Хеллмана на эллиптических кривых 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

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