О соотношениях между атаками на симметричные шифры, гомоморфные над кольцом вычетов

Аннотация

Работа посвящена изучению криптостойкости симметричных гомоморфных шифров над кольцами вычетов. Основной задачей является выяснить, возможно ли установить эквивалентность между атакой только по шифртекстам (АТШ) и атакой по известным открытым текстам (АИОТ) для таких шифров. Для этого вводится понятие сводимости между атаками и дается достаточное условие сводимости от АТШ к АИОТ. Основная идея заключается в том, что для доказательства сводимости от АТШ к АИОТ необходимо найти функцию над кольцом вычетов, которая является эффективно вычислимой и имеет небольшой размер образа по сравнению с размером всего кольца вычетов. Исследование наличия сводимости интересно тем, что оно может позволить лучше понять уровень криптостойкости существующих симметричных гомоморфных криптосистем (ГК). Поскольку для большинства из них в литературе уже установлена уязвимость к АИОТ, то доказательство существования сводимости может показать, что эти криптосистемы нестойки даже к АТШ, а следовательно, совсем нестойки и непригодны для применения. Приводится пример сводимости АТШ к АИОТ для случая, когда кольцо вычетов является простым полем. На основе этого примера описывается эффективная АТШ на одну симметричную ГК в случае кольца вычетов небольшого размера. Также отдельно рассматривается случай, когда кольцо вычетов для ГК строится по трудно- факторизуемому модулю п. Для таких п на данный момент не известен эффективный алгоритм построения эффективно вычислимых функций с «небольшим» образом. Ввиду этого дальнейшая работа по криптоанализу существующих симметричных ГК будет направлена на изучение свойств функций над кольцами вычетов по труднофакторизуемым модулям.