Дальнейшее создание корелляционно-устойчивых односторонних функций с потерями

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:36, 30 октября 2015.
More Constructions of Lossy and Correlation-Secure Trapdoor Functions
More Constructions of Lossy and Correlation-Secure Trapdoor Functions.PNG
Авторы David Mandell Freeman[@: 1],
AOded Goldreich
Gil Segev[@: 2],
Eike Kiltz[@: 3],
Alon Rosen[@: 4]
Опубликован 2010 г.
Сайт Homepage of David Mandell Freeman
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. Мы предлагаем новые улучшенные реализации функций с лазейкой и потерей информации (Пикерт и Уотерса STOC’08), и функции защищённые от корреляции с лазейкой (Росена и Сегева, ТСС’09). Наши схемы расширяют множество теоретико-числовых предположений, на которых данные примитивы основываются, и выявляем следующее:
  • Функции с лазейкой и потерей данных при предположении о квадратичной остаточности. Наша конструкция основывается на модульном возведении в квадрат, тогда как предыдущие её аналоги такие как схемы основывались на заметно стойких предположениях, и т.о. получается, что мы представляем первую конструкцию которая основывается исключительно на предположении о квадратичной остаточности.
  • функции с лазейкой и потерей данных основываются на составном предположении о квадратичной остаточности. Наша конструкция реализует в действительности любое количество потери данных, где в то же время функции являются более эффективными, чем в матричном подходе Пикерта и Уотерса.
  • функции с лазейкой и потерей данных основываются на d-линейном предположении. Наша конструкция не только упрощает DDH-подобную схему Пикерта-Уотерса, но и позволяет обобщить целое семейство d-линейных предположений без потери эффективности.
  • функции с лазейкой защищённые от корреляции основываются на стойком синдроме декодирования.
Ключевые слова: шифрование с открытым ключом, функции с лазейкой и потерей данных, функции с лазейкой защищённые от корреляции.

Введение

В данной работе, рассматриваются новые конструкции функции с лазейкой и потерей данных и функции с лазейкой защищённые от корреляции. Эти примитивы являются более стойкими вариантами классического понятия функций с лазейкой, и представлены с целью реализации простой конструкции и конструкции в виде чёрного ящика схем шифрования с открытым ключом, которые защищены от атак на выбранный шифртекст. На высоком уровне они определяются следующим образом:

  • Функции с лазейкой и потерей данных [1]: Набор функции с лазейкой и потерей данных содержит два семейства функций. Функции в первом семействе являются инъективными и для них можно эффективно использовать лазейку. Функции во втором семействе являются функциями «с потерей данных», означающей, что размер из изображения значительно меньше чем размер их области определения. Единственным вычислительным условием будет то, что описание случайно выбранной функции из семейства инъективных функций вычислительно неразличимо по признакам от описания случайно выбранной функции из семейства функций с потерей данных.
  • Функции с лазейкой защищённые от корреляции [2]: Классическое понятие однонаправленных функций требует чтобы функция была эффективно вычислима, но сложно инвертируема для заданного изображения равномерно выбранного входа. Защита от корреляции обобщает требование однонаправленности с помощью рассмотрения -зависимых произведений функций и любого специального входного распределения, при этом равномерное распределение не требуется. Для заданного набора функций и распределения над -зависимыми входами, говорят, что безопасна при -корреляции входов если функция однонаправлена, где будут независимо выбираться из и получаются из .

Функции с лазейкой и потерей данных рассматривались и Пикертом с Уотерсом [1], которые показали, что они реализуют фундаментальные криптографические примитивы, такие как функции с лазейкой, хэш функции стойкие к коллизиям, переход с забыванием, и ССА-безопасное шифрование с открытым ключом. Кроме того, функции с лазейкой и потерей данных уже использовались в ряде других приложений, включая детерминистическое шифрование с открытым ключом [3], ОАЕР-подобное шифрование с открытым ключом [4], «ограниченное» шифрование с открытым ключом для защиты от плохих случайных значений [5], безопасное при селективных открытых атаках [6], и эффективные не интерактивные строковые привязки [7].

Понятие корреляционной безопасности было предложено Росеном и Сегевым [2], которые показали, что любой набор инъективных функций с лазейкой однонаправлен при действительном распределении входа и его можно использовать для построения ССА-безопасной схемы шифрования с открытым ключом. Они показали, что любой набор функции с лазейкой и потерей данных, при значительной потере данных также будет корреляционно безопасным. Этот результат недавно был повторно получен Молом и Ялеком [8], которые выявили, что даже допустима даже потеря любой полиномиальной части простого бита.

Эти приложения сподвигли нас к анализу новых конструкций функции с лазейкой и потерей данных и функции с лазейкой защищённые от корреляции. Такие конструкции позволяют нам расширить базис при котором можно получить вышеуказанные криптографические задачи в простом и модульном виде.

Наш вклад

Мы предлагаем новые и улучшенные схемы функции с лазейкой и потерей данных и функции с лазейкой защищённые от корреляции основанные на хорошо реализуемых теоретико-числовых предположений (некоторые из которых не были известны прежде в качестве применения каких либо примитивов). При непосредственной реализации результатов [1][2][8], мы получили ССА-безопасные схемы шифрования с открытым ключом основанные на этих предположениях. Конкретно, были представлены следующие конструкции:

  1. Перестановки с лазейкой и потерями данных основанные на предположении о квадратичной остаточности. Наша конструкция основывается на функции модульного возведения в квадрат Рабина и единственном предположении о квадратичной остаточности. Точнее говоря, функция определена как , где есть RSA модули и функция индексированная с помощью двух открытых элементов ,решающих две независимые цели. Первая, это расширение функции модульного возведения в квадрат до перестановки . Вторая, это определение, что теряет информацию о подписи тогда и только тогда, когда s есть квадратичная остаточность. Поэтому, по предположению о квадратичной остаточности f имеет один бит потери. Отметим, что хоть функция с одним битом потери (или, говоря более общими словами, только с пренебрежимо малым количеством теряемой информации) не обязательно будет (стойкой) однонаправленной функцией, тем не менее её можно использовать как блок построения для создания даже ССА-безопасной схемы шифрования с открытым ключом (см. [1][2]).
  2. Функции с лазейкой и потерей данных основанные на предположении о составной остаточности. Наша конструкция основывается на схема шифрования Дамгарда-Джурика [9] с дополнениями Дамгарда и Нельсона[10] [11]. Схема Дамгарда-Джурика основывается на вычислениях в группе , где есть RSA модуль и есть целое значение (она включает в себя схему шифрования Пайлера [12] как частный случай при ). На высоком уровне, каждая функция описанная , где это открытый ключ для схемы шифрования, а с это либо шифрование (инъективный режим) либо шифрование (режим потери данных). Используя гомоморфные свойства схемы шифрования, для заданного шифртекста и элемента , возможно вычислить либо шифрование в инъективном режиме, либо шифрование в режиме потери данных. Отметим, что эта конструкция была недавно и независимо представлена Болдыревой и др. [3]. Также задаётся «all-but-one» версия данной схемы.
  3. Функции с лазейкой и потерей данных основанные на d-линейном предположении. Наша конструкция упрощает и обобщает DDH-подобную конструкцию Пикерта и Уотреса [1]. (Напомним, что DDH является 1-линейным предположением.) Пусть будет конечной группой порядка и выбранной матрицы над , которая обладает либо рангом (режим потери данных) либо рангом (инъективный режим). Мы «шифруем» как матрицу , где есть генератор . Если есть бинарный вектор длины , тогда для заданной можно эффективной оценить функцию . Если имеет ранг n, тогда для заданного можно эффективно инвертировать для изображения . С другой стороны, если имеет ранг и , тогда будет с потерями. -линейное предположение реализует то, что режимы потери данных и инъекции нельзя эффективно различить по признакам. Мы также даём «all-but-one» версию функции основанной на DDH предположении.
  4. Функции с лазейкой защищённые от корреляции основанные на стойкости синдрома декодирования. Наша конструкция основывается на системе шифрования Нидерейтера использующей кодирование [13] которая сама по себе представляется удвоением системы шифрования МакЭллис [14]. Наша функция с лазейкой определяется как , где есть бинарная матрица (некоторого распределения, которое позволяет осуществить использование лазейки) а есть битовая строка с малым весом Хемминга. Показывается, что корреляционная безопасность функции непосредственно реализуется с помощью результата Фичера и Стерна [15] для псевдослучайности функции f. Интересно, что соответствующая функция с лазейкой МакЭллис (которую можно рассматривать как удвоенную функцию Нидерейтера) не будет корреляционно безопасной. Однако, есть возможность расширить понятие корреляционной безопасности с помощью выявления непосредственной конструкции ССА-безопасной схемы шифрования из функции с лазейкой МакЭллис. Это было недавно продемонстрировано Доусли и др. [16] (который предложил первую схему шифрования основанную на кодировании, которая была ССА-безопасной в стандартной модели) а также для соответствующего выбора решётки независимо показано Пикертом [17], Голдвассером и Вайкунтанатаном [18]. Наш вклад по данному вопросу показал, что функция Нидерейтера реализует простую конструкцию функции с лазейкой и потерей данных и функции с лазейкой защищённые от корреляции основанных на одинаковых с [16] предположениях о безопасности. Результирующая ССА-безопасная схема шифрования будет эффективной как и любая из [16].

Схожие работы

Большинство известных конструкций и приложений функции с лазейкой и потерей данных и функции с лазейкой защищённые от корреляции уже указывались выше; здесь мы рассмотрим ещё несколько. Кроме конструкции основанной на DDH, Пикерт и Уотерс [1] также представили конструкцию функции с лазейкой и потерей данных основанных на задачах с наихудшим случаем стойкости решёток. Данная конструкция не удовлетворяет такому же количестве потери информации как в DDH-подобной схеме, всё равно допустима для реализации ССА-безопасной схемы шифрования с открытым ключом. Задачи наихудшего случая стойкости решёток также использовались Пикертом [17] и Голдвассером и Вайкунтанатаном [18] для построения ССА-безопасной схемы шифрования использующей действительное обобщение корреляционно безопасных функций с лазейкой.

Килтз и др. [4] показали, что RSA перестановка с лазейкой теряет данные при предположении о -сокрытие Качина и др. [19]. (Конкретно говоря, оно теряет бит информации, где является открытой RSA экспонентой.) Более того, они предложили предположения стойкости при нескольких простых значениях для которых у RSA будет значительная потеря данных.

В недавней и независимой работе Мол и Ялек [8] предложили функции с лазейкой и потерей данных основанные на функциях модульного возведения в квадрат. Хотя эта конструкция и соотносима с нашей, её безопасность основывается на более стойком предположении, что два простых случайных RSA модуля неразличимы по признакам от трёх простых случайных RSA модулей. В другой недавней и независимой работе Хеменвей и Островский [20] обобщили понятие Пикерта и Уотерса [1] обосновав его теперь для любых систем гомоморфного хэшированного доказательства, где изначально обобщение систем хэшированного доказательства бралось из работы Крамера и Соупа [21]. Хеменвей и Островский т.о. показали, что системы гомоморфного хэшированного доказательства можно построить основываясь на либо предположении о квадратичной остаточности либо на предположении о составной остаточности. Их подход значительно отличается от нашего, в следствии чего результирующие конструкции несравнимы по компромиссу между эффективностью и количеством потерянных данных.

План работы

Оставшаяся часть работы организована следующим образом. В Разделе 2 мы напомним читателю определения функции с лазейкой и потерей данных и функции с лазейкой защищённые от корреляции. В разделе 3, 4 и 5 представим наши конструкции основанные на предположении о квадратичной остаточности, -линейном предположении, и стойкости синдрома декодирования, соответственно. В силу нехватки места конструкция основанная на предположении о составной остаточности дана в полной версии этой работы [22].

Начальные обозначения и определения

Функции с лазейкой и потерей данных

Набор функции с лазейкой и потерей данных содержит два семейства функций. Функции первого семейства инъективны и могут быть эффективно инвертированы используя лазейку. Функции второго семейства будут с «потерей данных», которая означает, что размер их изображения значительно меньше, чем размер их области определения. Единственным вычислительным требованием будет вычислительная неразличимость по признакам распределения случайно выбранной функции из семейства инъективных функций от распределения случайно выбранной функции из семейства функций с потерями данных.

TemplateDifinitionIcon.svg Определение «Определение - Определение 1»
Функции с лазейкой и потерей данных - Набор функций с -потерей данных будет 4-кортежом вероятностных полиномиально сложных алгоритмов таких, что:
  1. Получение функции с потерей данных: выводит индекс функции .
  2. Получение инъективных функций: выводит пару . (Здесь есть индекс функции, а - лазейка.)
  3. Оценка инъективных функций: Для каждого индекса функции представленной , алгоритм вычисляет функцию , изображение которой будет размером не более .
  4. Оценка инъективных функций: Для каждой пары ,полученной , алгоритм вычисляет инъективную функцию .
  5. Инверсия инъективных функций: Для каждой пары ,полученной и каждого , имеем
  6. Безопасность: Два ансамбля и вычислительно неразличимы по признакам.

Отметим, что может быть функцией . Также заметим, что мы не конкретизируем выход для входов не из изображения .

Набор all-but-one функции с лазейкой и потерей данных является более общим примитивом. Такой набор связывается с множеством , каждый элемент которого соотносится в виде ответвления. (Если то получим предыдущее понятие функции с лазейкой и потерей данных.) Полученный алгоритм для данного набора принимает дополнительный параметр и выводит определение функции с лазейкой и набор ответвлений . Функция обладает таким свойством, что для любого ответвления функция инъективна (и может быть инвертирована при помощи ), а функция будет с потерей данных. Более того, определение скрывает (в плане вычислений) набор ответвлений с потерей данных .

Наше определение является чуть более общим, чем Пикерта и Уотерса [1], которое позволяет наличествовать только одному ответвлению с потерей данных (т.е. ). В нашем же случае можно иметь несколько ответвлений с потерей данных (отличных от ) и требуется чтобы для заданного определения функции и соответствующего было вычислительно невозможно найти другое ответвление с потерей. Доказательство безопасности ССА-безопасной схемы шифрования с открытым ключом Пикерта и Уотерса [1][Раздел 4.3] можно легко адаптировать к нашему обобщению. (С этого момента в работе не рассматриваются другие приложения all-but-one функции с лазейкой и потерей данных).

TemplateDifinitionIcon.svg Определение «Определение - Определение 2»
All-but-one функции с лазейкой и потерей данных - Набор -all-but-one функции с лазейкой и потерей данных будет 4-кортежем вероятностных полиномиально сложных алгоритмов таких что:
  1. Получение ответвления: выводит значение .
  2. Получение функции: Для каждого значения получаемого , алгоритм выводит тройку содержащую индекс функции , лазейку , и набор ответвлений с потерей данных c
  3. Оценка функций с потерей данных: Для каждого значения получаемого и каждого получаемого , алгоритм вычисляет функцию , изображение которой будет рамером не более .
  4. Оценка инъективных функций: Для любого b* и b получаемого и для каждого получаемого , если , то алгоритм вычисляет инъективную функцию .
  5. Инверсия инъективных функций: Для любого b* и b получаемого и для каждого получаемого , если тогда имеем
  6. Безопасность: Для любых двух последовательностей таких, что и будут конкретными значениями в изображении , два ансамбля и будут вычислительно неразличимы по признакам.
  7. Сокрытие ответвлений с потерей данных: Любой вероятностный полиномиально сложный алгоритм , получающий на входе , где и имеют пренебрежимо малую вероятность вывода элемента (где вероятность берётся для случайных значений ).

Функции с лазейкой защищённые от корреляции

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

TemplateDifinitionIcon.svg Определение «Определение - Определение 3»
k-зависимое произведение - Пусть будет набором эффективно вычислимых функций. Для любого целого k, определим k-зависимое произведение следующим образом:
  • Алгоритм генерации ключа для входа реализует k независимых случая и выводит . Т.е. функция получается из путём независимого выявления k функций из .
  • Алгоритм оценки для входа реализует F для оценки каждой функции на . Т.е.,

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

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

Определение 4 Oднонаправленность для корреляционных входов - пусть есть набор с областью определения и пусть С будет распределением, где распределено над для некоторого целого k = k (n).Говорим, что является однонаправленным для С-корреляционных входов, если будет однонаправленным относительно входного распределения С.}}

Для частного случая это распределение будет равномерным -повторимым распределением (т.е. выявляет равномерно случайных вход и выводит копий ), и говорится, что является однонаправленным для -корреляционных входов. Росен и Сегев [2] показали, что набор функций с лазейкой и (n, l)-потерей данных можно использовать в построении набора , который является однонаправленным для -корреляционных входов при любом .

Конструкция основанная на предположении о квадратичной остаточности

Наша конструкция основывается на функции модульного возведения в квадрат , где для простых чисел (т.е. целых значений Блюма). Это 4-в-1 отображение на , и т.о. конструкция будет получаться с помощью использования дополнительной информации на выходе, которая уменьшит число прообразов до 2 (это для функций с потерями) или 1 (это для инъективных функций) посредством вычислительной неразличимости по признакам. Хотя этот результат будет для одного бита потери где функции определены над , все функции с лазейкой и потерей данных в наборе требуют общей для всех области определения (т.е., область определения должна зависеть только от параметра безопасности). Это сложность преодолевается простым расширением области определения, что приводит к потере бит.

Для любого нечётного положительного целого , обозначим за символ Якоби по модулю N. Определим функции следующим образом:

Определим и на с помощью представления элементов целыми числами от до .

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

и

В частности, 4 квадратных корня примут значения

Конструкция. Определим 4-кортеж (из определения 2.1) следующим образом:

  1. Получение функции с потерей данных: Для входа алгоритм выбирает -битный модуль , где есть -битные простые числа. Затем он выбирает случайное такое, что , и случайное такое, что , где будет квадратичной остаточностью. Индекс функции будет .
  2. Получение инъективной функции: Для входа алгоритм выбирает -битный модуль , где есть -битные простые числа. Затем он выбирает случайное такое, что , и случайное такое, что , где не будет квадратичной остаточностью. Индекс функции будет , а лазейка - .
  3. Оценка: Для заданного индекса функции и алгоритм выражает как целое значение в наборе и выводит
  4. Инверсия: Для заданного определения инъективной функции и лазейки , а также алгоритм получает следующим образом. Если , то алгоритм выводит . В противном случае:
a)Находим вычисляя (отметим, что . Пусть .
b)Найдём с помощью проверки является ли квадратичной остаточностью по модулю (отметим, что тогда и только тогда, когда ею не является). Пусть .
c)Найдём все квадратичные корни в , и выведем тот, которые согласуется с обоими и . (Используем Факт 3.1 если , и заметим, что если , то имеет два квадратичных отрицательных корня.)

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

TemplateTheoremIcon.svg Теорема Теорема 1

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

Доказательство
Сперва, что следует их корректности алгоритма инверсии, выводит перестановки для множества . Затем, утверждается, что выводит функции, которые являются 2-в-1 для множества . Предположим . Т.к. s является квадратичной остаточностью, Факт 3.1 выявляет, что каждый будет удовлетворяющим


Тогда для каждого имеем и . Т.о. каждый элемент в множестве имеет не менее двух прообразов в , и т.к. это множество имеет число элементов половины , получаем, что будет 2-в-1 на . Аналогично показываем, что каждый квадрат в группе имеет два прообраза в и тоже самое для . Т.к. , функция будет 2-в-1 для всего множества.

Т.к. является -битным модулем (т.е. ), функции с потерей данных будут 2-в-1 как минимум для половины области определения, что реализует размер их изображения не более . Кроме того, описания функций с потерей данных и инъективных функций отличаются не только для s элемента, который является случайным элементом подгруппы с символом Якоби 1, который является квадратичной остаточностью в случае с потерей данных и не является ею в инъективном случае. Поэтому, предположение о квадратичной остаточности реализует то, что функции с потерей данных будут вычислительно неразличимы от инъективных функций.

Что и требовалось доказать.


Конструкция основанная на d-линейном предположении

-линейное предположение [23] [24] является обобщением решающего предположения Диффи-Хеллмана, которое выполняется даже в группах с эффективно вычислимым -линейным отображением. 1-линейное предположение будет DDH, тогда как 2-линейное предположение будет решающим линейным предположением известным из [25]. Предположение будет задаваться следующим образом:

TemplateDifinitionIcon.svg Определение «Определение - Определение 5»
Пусть будет целым, и пусть будет конечной циклической группой порядка . Говорят, что -линейное предположение выполняется в если распределения

будут вычислительно неразличимы по признакам.

Для любого -линейное предположение реализует -линейное предположение [23][Лемма 3].

Пикерт и Уотерс [1][Раздел 5] показывают функции с потерей данных и all-but-one функции с лазейкой и потерей данных основанные на DDH предположении. В конструкции Пикерта-Уотерса, индексной функцией будет шифрование Эль Гамаля матрицы , которая либо является нулевой матрицей (в режиме потери данных) либо идентификационной матрицей (в инъективном режиме) использующей конечную циклическую группу порядка . DDH предположение в реализует то, что эти два шифрования нельзя различить по признакам. Конструкцию можно обобщить до d-линейных предположений используя обобщение шифрования Эль Гамаля, но такие схемы будут уже менее эффективны т.к. оно основывается на -линейном предположении определяющем групповой элемент для каждого шифртекста (см. пример в [24]).

Наша конструкция основывается на следующем основном понятие из линейной алгебры: если есть матрица над конечным полем и есть длина -векторного столбца, то отображение имеет изображение размером . Если сократим область определения до бинарных вектором (т.е. тех у которых выходы будут представляться в ), то функция будет инъективной когда , а её инверсию можно вычислить путём . Если с другой стороны, имеем , тогда не будет инъективной даже когда область определения сокращена до бинарных вектором, т.к. изображение в таком случае содержит подгруппу размером не менее .

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

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

.

Аналогично для заданной матрицы и векторного столюца определим как

Для этих определений получается

Конструкция. Для любого положительного целого и любого действительного числа , определим 4-кортеж (см. Определение 2.1) следующим образом:

  1. Получение функции с потерей данных: Для входа , алгоритм выбирает случайное -битное простое , группу порядка , и генератор для . Затем он выбирает матрицу и вычисляет . Индексная функция будет .
  2. Получение инъективной функции: Для входа , алгоритм выбирает случайное -битное простое , группу порядка , и генератор для . Затем он выбирает матрицу и . Индексная функция будет , а лазейка .
  3. Оценка: Для заданной индексной функции и представим как бинарный векторный столбец . Алгоритм вычисляет функцию .
  4. Инверсия: Для заданной индексной функции , лазейки и вектора , определяем следующим образом:
a)Вычисляем ;
b)Пусть для ;
c)Выводим .


TemplateTheoremIcon.svg Теорема Теорема 2

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

Доказательство
Сперва отметим, что в случае потери данных, когда будет ранга , изображение содержится в подгруппе размером . Условие гарантирует , т.о. когда будет ранга функция станет инъективной. Легко проверить что инверсия алгоритма выполняется корректно для инъективных функций. Наконец, по [20, Лемма А.1], d-линейное предположение реализует то, что матрица , когда будет рангом , является вычислительно неразличимой по признакам от матрица , когда будет рангом . Что и требовалось доказать.


Отметим, что безопасность системы оценивается по размеру бита , т.е. . К тому же, заметим, что дискретные логарифмы на шаге инверсии можно рассчитать эффективно, когда выступает в виде бинарного вектора. (Здесь будет преимущество в том, что выход не определяется входами не для изображения .)

Теперь опишем расширение системы до all-but-one функций с потерей данных, для случая, когда параметр в вышеуказанной конструкции будет равен . Пусть обозначает идентификационную матрицу. Для любого действительного определим 4-кортеж (см. Определение 2) следующим образом:

  1. Получение ответвления: Для входа , алгоритм выводит равномерно распределённое .
  2. Получение функции: Для входа , алгоритм выбирает случайное -битное простое , группу порядка , и генератор для . Затем он выбирает матрицу . Пусть и . Индексная функция будет , а лазейка , а множество ответвлений с потерей данных .
  3. Оценка: Для заданной индексной функции , ответвления , и входа , мы представляем в виде бинарного векторного столбца . Алгоритм вычисляет функцию , где обозначает покомпонентное произведение элементов .
  4. Инверсия: Для заданной индексной функции , лазейки , ответвления , и вектора , определяем следующим образом:
a)Если не инвертируемо, выводим \perp.
b)Вычисляем ;
c)Пусть для ;
d)Выводим .
TemplateTheoremIcon.svg Теорема Теорема 3

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

Доказательство
Сперва отметим, что если будет матрица ранга вычисляемая с помощью , то действует теорема 2.
.

Теперь проверим каждое свойство Определения 2. Свойства и неизменны. Для проверки свойства , отметим, что Теерема 2 реализует . Т.к. имеет ранг , изображение содержится в подгруппе размером . Для проверки свойства , заметим, что условие гарантирует , т.о. когда инвертируемо функция будет инъективной. Условие неинвертируемости эквивалентно тому, что будет собственным значением . Т.к. имеет ранг , его собственными значениями будут и . Т.о. будет собственным значением тогда и только тогда, когда , а инъективна для всех . Легко проверить, что алгоритм инверсии выполняется корректно при , т.о. выполняется свойство .

Свойства и следуют из DDH предположения для . Покажем свойство построив последовательность игр:

: Это игра с действительной безопасностью. Злоумышленник задаёт и для и и выводит . Злоумышленник побеждает если .

: То же самое что и в , исключением будет для полноранговой матрицы .

: То же самое что и в , исключением будет для некоторой равномерной матрицы .

: То же самое что и в , исключением будет .

Т.к. будет независима от , преимущество любого злоумышленника реализующего будет нулевым. Теперь покажем, что если DDH предположение выполняется для , то для не полиномиально сложный злоумышленник может различить по признакам от с пренебрежимо малым преимуществом.

: Любой алгоритм который различает по признакам от можно использовать для различения по признакам распределений и . По [26], любой алгоритм, который различает по признакам эти распределения может решать задачу DDH в .

: Т.к. отношением полноранговых матриц ко всем матрицам в будет , даже злоумышленник без ограничений сможет различить по признакам от с вероятностью не более .

: Т.к. матрица будет равномерной в , то матрица будет также равномерной в , т.о. и будут идентичны.

Заключим, что для любого не полиномиально сложный злоумышленник может выиграть с пренебрежимо малым преимуществом.

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

Пусть будет дискретным логарифмом для . Для любого вычисляем матрицу и предоставляем злоумышленнику . Если злоумышленник выводит с то можно вычислить т.к. это единственное ненулевое собственное значение . Если есть -ая диагональ , это даёт нам уравнение (4)

.

Т.к. с вероятностью , можно его решить для всегда кроме случая с пренебрежимо малой вероятностью.

Что и требовалось доказать.


Если мы выбираем любое целое и повторим вышеуказанную конструкцию с -битным простым и матрицей ранга , тогда получаем all-but-one функцию с лазейкой и потерей данных при -линейном предположении. В действительности, доказательства свойств довольно просты. Однако, вышеуказанное доказательство свойства нельзя обобщить. В частности, обобщением будет , который можно записать как для некоторых (известных) . Когда элемент независим от , т.о. можно заключить, что он будет ненулевым с высокой вероятностью; однако, когда такого не будет. Т.о. вопрос завершения доказательства для остаётся открытым.

Корреляционная безопасность входного значения при синдроме декодирования

Наша конструкция основывается на системе шифрования Нидерреитера использующей кодирование [13], которая в свою очередь является двойной системой шифрования МакЭллис [14].

Пусть и будут двумя функциями с параметром безопасности . Установим область определения в качестве области определения для всех -битных строк с весом Хемминга . Отметим, что будет выявляться эффективно (см. пример в [15]). Функция Нидерреитера с лазейкой определяется следующим образом:

  • Генерация ключа: Для входа алгоритм выбирает невырожденную бинарную матрицу , -линейный бинарный код Гоппа производящий корректировку до ошибок , и матрице перестановок . Он устанавливает , что в свою очередь будет матрицей . Описанием функции будет , а лазейкой .
  • Оценка: Для заданного определения функции и с весом Хемминга , алгоритм вычисляет функцию .
  • Инверсия: Для заданной лазейки и , алгоритм вычисляет , применяет алгоритм синдрома декодирования для чтобы восстановить , и вычислить .

Для функции Нидерреитера с лазейкой можно доказать однонаправленность посредством неразличимости по признакам и предположении о синдроме декодирования, которые индексируются параметрами и .

Предположение о неразличимости по признакам. Бинарная матрица выводимая будет вычислительно неразличима по признакам от равномерной матрицы той же размерности.

Предположение о синдроме декодирования. Набор функций определённых как для равномерной бинарной матрицы будет однонаправленным на области определения .

Выбирая вес , близкий к границе Гилберта-Варшамова получаем примеры трудно решаемые относительно задачи синдрома декодирования. Граница Гиблерта-Варшимова для линейного кода с задаётся с помощью уравнения , где . В силу этого предположим, что предположение о синдроме декодирования выполняется для всех , удовлетворяющих [15]. Отметим, что однонаправленность также реализует то, что мощность будет супер-полиномиальна в .

Следующая теорема доказана в [15].

TemplateTheoremIcon.svg Теорема Теорема 4

Если предположение о синдроме декодирования выполняется для и , тогда ансамбли и будут вычислительно неразличимы по признакам .

Доказательство
Эта теорема реализует то, что функция Нидерреитера с лазейкой будет однонаправленной для -корреляционных входов.


TemplateTheoremIcon.svg Теорема Теорема 5

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

Доказательство
Зададим вероятностного полиномиально сложного злоумышленника , который участвует в игре безопасности для случая однонаправленности при k-корреляционных входах. Определим

,
где и . Теперь заменим все матрицы на равномерные матрицы той же размерности. С помощью предположения о неразличимости по признакам и гибридного аргумента, получаем, что

Для определим матрицу с помощью объединения столбцов матриц . Тогда распределения (U_1,...,U_k,U_1(x),...,U_k(x)) и будут идентичны. Т.к. мы можем применив Теорему 5.1 получить

где будет равномерной битовой строкой в . Отметим, что подразумевает, что пренебрежимо мал. Что и требовалось доказать.


Заметим, что вышеуказанное доказательство выявляет, что функция Нидерреитера с лазейкой линейно имеет много исходных битов, которые значительно повышают эффективность ССА-безопасной схемы шифрования полученной путём использования конструкции из [2].

Благодарности

Мы благодарим Ивана Дамгарда и Криса Пикерта за их полезные советы. Исследования Давида Манделла Фримана проводились для CWI в Университете Леидена, Нидерланды, и осуществлялись при поддержке Национального Научного фонда Международного исследовательского отделения, с дополнительной поддержкой со стороны отдела многопрофильной деятельности в NSF Управлении по математическим и физическим наукам. Одед Голдрейх частично осуществлял свою работу при поддержке Израильского научного фонда (грант # 1041/08). Ик Килтз проводил исследования при поддержке исследовательской программы Сентинеля. Сентинель финансируется Технологическим фондом STW, Организации Нидерланд для научных исследований (NWO), и Датским министерством по экономическим вопросам. Алон Росен частично осуществлял свою работу при поддержке Израильского научного фонда (гранд № 334/08). Гил Сегев осуществлял свою работу при поддержке программы стипендии Адамса Израильской Академии Гуманитарных и Технических наук.

Контакты авторов материала

  1. Stanford University, USA, E-mail: [1]
  2. Weizmann Institute of Science, Rehovot 76100, Israel , E-mail: [2]
  3. CWI, Netherlands , E-mail: [3]
  4. Efi Arazi School of Computer Science, Herzliya Interdisciplinary Center (IDC),Herzliya 46150, Israel, E-mail: [4]

Литература

  1. 1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: 40th ACM Symposium on Theory of Computing, pp. 187–196 (2008)
  2. 2,0 2,1 2,2 2,3 2,4 2,5 Rosen, A., Segev, G.: Chosen-ciphertext security via correlated products. In: Reingold,O. (ed.) Theory of Cryptography. LNCS, vol. 5444, pp. 419–436. Springer,Heidelberg (2009)
  3. 3,0 3,1 Boldyreva, A., Fehr, S., O’Neill, A.: On notions of security for deterministic encryption,and efficient constructions without random oracles. In: Wagner, D. (ed.)CRYPTO 2008. LNCS, vol. 5157, pp. 335–359. Springer, Heidelberg (2008)
  4. 4,0 4,1 Kiltz, E., O’Neill, A., Smith, A.: Lossiness of RSA and the instantiability of OAEP. Manuscript (2009)
  5. Bellare, M., Brakerski, Z., Naor, M., Ristenpart, T., Segev, G., Shacham, H.,Yilek, S.: Hedged public-key encryption: How to protect against bad randomness.In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 232–249. Springer,Heidelberg (2009)294 D.M. Freeman et al.
  6. Bellare, M., Hofheinz, D., Yilek, S.: Possibility and impossibility results for encryption and commitment secure under selective opening. In: Joux, A. (ed.)EUROCRYPT 2009. LNCS, vol. 5479, pp. 1–35. Springer, Heidelberg (2009)
  7. Nishimaki, R., Fujisaki, E., Tanaka, K.: Efficient non-interactive universally composable string-commitment schemes. In: Pieprzyk, J., Zhang, F. (eds.) ProvSec 2009. LNCS, vol. 5848, pp. 3–18. Springer, Heidelberg (2009)
  8. 8,0 8,1 8,2 Mol, P., Yilek, S.: Chosen-ciphertext security from slightly lossy trapdoor functions. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 296–311.Springer, Heidelberg (2010)
  9. Damg˚ard, I., Jurik, M.: A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001)
  10. Damg˚ard, I., Nielsen, J.B.: Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 581–596. Springer, Heidelberg (2002)
  11. Damg˚ard, I., Nielsen, J.B.: Universally composable efficient multiparty computation from threshold homomorphic encryption. In: Boneh, D. (ed.) CRYPTO 2003.LNCS, vol. 2729, pp. 247–264. Springer, Heidelberg (2003)
  12. DPaillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)
  13. 13,0 13,1 Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory [Problemy Upravlenija i Teorii Informacii]15, 159–166 (1986)
  14. 14,0 14,1 McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep., Jet Prop. Lab., 114–116 (January 1978)
  15. 15,0 15,1 15,2 15,3 Fischer, J.-B., Stern, J.: An efficient pseudo-random generator provably as secure as syndrome decoding. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070,pp. 245–255. Springer, Heidelberg (1996)
  16. 16,0 16,1 16,2 Dowsley, R., M¨uller-Quade, J., Nascimento, A.C.A.: A CCA2 secure public key encryption scheme based on the McEliece assumptions in the standard model. In: Fischlin, M. (ed.) RSA Conference 2009. LNCS, vol. 5473, pp. 240–251. Springer, Heidelberg (2009)
  17. 17,0 17,1 Peikert, C.: Public-key cryptosystems from the worst-case shortest vector
  18. 18,0 18,1 Goldwasser, S., Vaikuntanathan, V.: New constructions of correlation-secure trapdoor functions and CCA-secure encryption schemes. Manuscript (2008)
  19. Bellare, M., Hofheinz, D., Yilek, S.: Possibility and impossibility results for encryption and commitment secure under selective opening. In: Joux, A. (ed.)EUROCRYPT 2009. LNCS, vol. 5479, pp. 1–35. Springer, Heidelberg (2009)
  20. Hemenway, B., Ostrovsky, R.: Lossy trapdoor functions from smooth homomorphic hash proof systems. Electronic Colloquium on Computational Complexity, Report TR09-127 (2009)
  21. Cramer, R., Shoup, V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 45–64. Springer, Heidelberg (2002)
  22. Freeman, D.M., Goldreich, O., Kiltz, E., Rosen, A., Segev, G.: More constructions of lossy and correlation-secure trapdoor functions. Cryptology ePrint Archive, Report 2009/590 (2009),
  23. 23,0 23,1 Hofheinz, D., Kiltz, E.: Secure hybrid encryption from weakened key encapsulation.In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 553–571. Springer,Heidelberg (2007)
  24. 24,0 24,1 Shacham, H.: A Cramer-Shoup encryption scheme from the Linear assumption and from progressively weaker Linear variants. Cryptology ePrint Archive, Report 2007/074 (2007)
  25. Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.)CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004)
  26. Boneh, D., Halevi, S., Hamburg,M., Ostrovsky, R.: Circular-secure encryption from decision Diffie-Hellman. In: Wagner, D. (ed.) CRYPTO 2008.LNCS,vol.5157,pp. 108–125. Springer, Heidelberg (2008)