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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:34, 30 октября 2015.
Chosen-Ciphertext Security from Slightly Lossy Trapdoor Functions
Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA.png
Авторы Petros Mol [@: 1]
Scott Yilek [@: 2]
Опубликован 2010 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__


Аннотация. Функции теряющие информацию о лазейке (LTDF), представленные Пикертом и Уотерсом (STOC 2008) были довольно полезными для создания многих криптографических примитивов. В частности, с помощью LTDF, которая теряет части всех её входных бит, возможно получить ССА безопасность путём представления LTDF как чёрного ящика. К сожалению, не все кандидаты LTDF достигают такого высокого уровня стойкости от потери информации. В данной работе был значительно снижена стойкость к потери информации необходимая для достижения ССА безопасности, и показано, что LTDF теряет только конкретную часть простого бита и её можно использовать в качестве чёрного ящика для создания ССА-безопасной РКЕ. Для того, чтобы показать наш результат, мы взяли за основу недавно полученый результат Росена и Сегева (ТСС 2009), который выявляет как достичь ССА безопасность для функций произведения которых будут однонаправленными при определённых типах взаимосвязанных входных значений. В заключении, даётся пример построения TDF с незначительной потерей основанной на предположении о том, что получение произведения двух простых значений из произведения трёх простых значений является трудной задачей.

Введение

Функции теряющие информацию о лазейке (LTDF) недавно представленные Пикертом и Уотерсом, являются доказано полезным способом как для задания новой конструкции традиционных криптографических примитивов так и для построения новых примитивов. В действительности, Пикерт и Уотерс использовали LTDF для создания однонаправленных инъективных функций с лазейкой, хэш функций стойких к коллизиям, СРА и ССА-безопасного шифрования, и др. LTDF использовались для создания детерминистических РКЕ схем безопасности в стандартной модели [3], а также РКЕ схем безопасности при выборочных открытых атаках [1].

Проще говоря, LTDF это инъективная функция с лазейкой при описании функции как (вычислительно) неразличимой по признакам от описания другой функции, которая статистически теряет информацию о своих входных значениях. Другими словами, функция будет не инъективной, при том что некоторые изображения будут потенциально иметь много прообразов. Говорим, что LTDF (вычислительно) теряет 1 бит, если эффективная размерность неотличимой по признакам функции будет не более - части размерности её области определения. LTDF позволяет просто и легко доказать методику: при доверительном выполнении протокола используем инъективную функцию для получения корректной функциональности, тогда как в доказательстве «задачи» заданной злоумышленнику воспользуемся функцией с потерями. Затем применим статистический аргумент для завершения доказательства.

Используя LTDF и данное доказательство, Пикерт и Уотерс показали, что LTDF с размером входа в виде полинома (где это параметр безопасности), и которая теряет бит является однонаправленной. Это легко заметить т.к. инвертер задан , где это неразличимая по признакам функция с потерями, то будет в среднем возможных прообразов; т.о. злоумышленник сможет вывести корректное значения только с пренебрежимо малой вероятностью. Применяя известный результат, эти однонаправленные TDF непосредственно дают СРА безопасность шифрования путём обобщен ключевых утверждений [7]. К тому же, Пикерт и Уотерс помимо этого показали, что LTDF опускает простые ключевые функции, что приводит к получению эффективных многоразрядных схем шифрования.

Для достижения ССА безопасности при LTDF, Пикерт и Уотерс затем показали, что любую LTDF с достаточным количеством теряемой информации можно использовать для построения all-but-one (исключительной) функции с лазейкой (АВО), которую затем можно использовать для получения ССА безопасности. Под «достаточной» количеством теряемой информации понимается наличие практического большинства входных битов, которые сложно выявить. Пикерт и Уотерс получили достаточное количество теряемой информации из DDH-подобной схемы, однако, их схема основанная на решётке теряет только конкретную часть входных бит, что будет недостаточным для общей схемы. Т.о. для оплучения ССА безопасности из предположений основанных на решётке, необходимо задать конкретную конструкцию АВО.

После опубликования исходной работы было предложено много аналогов построения LTDF. Розен и Сегев [20] и Болдырева, Фехн и О’Нилл [3] расписали схему основанную на предположении о выборочном составном вычитании (DCR), в то время как Килтз, О’Нилл, и Смит [9] показали, что RSA перестановка с лазейкой будет с потерями по предположению о пи-сокрытие [4]. Т.к. DCR-подобная LTDF имеет достаточное значение теряемой информации для построения АВО и получения ССА безопасности, RSA теряет только определённую часть (меньше половины) входных битов и т.о. не может использоваться для построения АВО при помощи общей схемы.

Связанные с этой работы. Розен и Сегев [21] недавно обобщили АВО метод для получения ССА безопасности с помощью задания достаточного, строгого предположения для соответствующей TDF. Они назвали это нововведение однонаправленностью при связанных произведениях. Хорошо известно, что для полиномиально ограниченной , получение конкретных функций независимо от семейства однонаправленных функций, а их реализации для независимых равномерных входов опять же приводят к однонаправленной функции, и даже усиливает однонаправленность. Розен и Сегев выявили случай, когда входы не должны быть обязательно независимые и равномерные, но вместо этого они должны быть связаны каким-либо способом. Они показали, как получить ССА безопасность для семейства функций, которые однонаправелнные относительно определённых распределений при связанных входах. В действительности, распределения, которые они использовали, обладали таким свойством, что для заданных любых входных значений общий входной вектор можно воссоздать. (Назовёт такие распределения восстановимым -подмножеством; см. Раздел 3 для более детального ознакомления.) Такое распределение будет простейшим при , что Розен и Сегев назвали распределением с w-повторением. В данном случае, независимо полученные функции будут применимы к одному и тому же входному значению.

Конечно же это определение полезно только если существует TDF, однонаправленная при таких взаимосвязях. Розен и Сегев показали, что LTDF с достаточным значением теряемой информации удовлетворяет данным требованиям. Требующееся значение потери информации будет в данном случае примерно равно значению необходимому Пикерту и Уотерсу для преобразования LTDF в АВО. Это значение будет задаваться чем то большим, а не какой либо постоянной функцией входных бит, что исключает некоторые LTDF.

Наш результат. Мы расширили результаты [15] и [21] и показали, что только определённая часть теряемого простого бита от потерь необходима для построения IND-CCA безопасного шифрования. Наши результаты снижают требуемое значение теряемой информации от –части всех входных бит до всего лишь 1/poly части одного бита. Это решает задачу из (наиболее поздняя версия [14]) [15] и к тому же в дальнейшем выполняет реализуемость обобщения связанного произведения Розена и Сегева. Наш результат также непосредственно означает, что LTDF конструкцию основанную на RSA функции из [9] и конструкцию основанную на решётке из [15] можно теперь использовать в качестве чёрного ящика для получения ССА безопасности.

Для выявления нашего результата, сперва докажем соответствующую теорему ограничивающую значение потери информации требующееся LTDF для того, чтобы определить, что -зависимые произведения будут однонаправленными относительно распределения связанного входа с минимальной энтропией . Затем покажем, что если применим кодировку коррекции ошибок в конструкции Розена-Сегева с кодировками Рида-Соломона и выберем параметры должным образом, то можно будет использовать распределение связанных входов с достаточной минимальной энтропией , что будет необходимо только чтобы LTDF терял около 2 бит. Т.к. легко получить количественную характеристику теряемой информации, то можно выявить LTDF которая теряет 2 бита для любой LTDF, которая теряет только определённую часть бита.

Т.к. мы значительно снизили количество потери информации необходимой для ССА безопасности, надеемся, что будет возможным получение ССА безопасности применимо к LTDF при более общем наборе предположений. С этой целью, мы даём пример построения TDF с незначительной потерей информации используя предположение из которого следует, что не ясно то, как построить LTDF с значительно большим количеством теряемой информации. Наша LTDF основывается на модульном возведении в квадрат и теряет определённую часть одного бита при предположении о том, что сложно различить по признакам произведение двух простых значений из произведения трёх простых значений [2]. Наши результаты описанные выше непосредственно дают ССА безопасность при данном предположении. Интересно, что Фриман, Голррейх, Килтз, Розен, и Сегев [6] независимо описали то, что LTDF теряет один бит информации при предположении о квадратичном вычитании. Наш результат позволил им получить ССА безопасность для TDF с незначительной потерей данных реализуемой как чёрный ящик.

Более конкретное рассмотрение. Для понимания зачем TDF с незначительной потерей данных необходима для построения различных криптографических примитивов давайте сперва сфокусируемся на построении СРА-безопасного шифрования. Для простоты, скажем, что имеется семейство LTDF с областью определения , и которая (вычислительно) теряет 1 бит. Теперь рассмотрим новое семейство LTDF которое будет просто -зависимым произведением для , где это параметр безопасности. Это означает, что для выявления функции из произведения семейства мы независимо получаем функций из ; область определения произведения семейства будет . Легко увидеть, что такое семейство вычислительно теряет бит и, применяя результат [15], и т.о. однонаправлено. Применив обобщение ключевых утверждений, это приводит к получению СРА-безопасной схемы шифрования.

Схема шифрования Розена-Сегева будет такой же, за исключением одного важного отличия заключающегося в том, что распределение входных значений функции выбирающееся из семейства произведения не будет больше равномерным над , а вместо этого будет взаимосвязанным (напомним, что мы назвали его восстановимым -подмножеством). Это поможет реализовать возможность ответов на запросы расшифровки в доказательстве. Розен и Сегев рассмотрели случай , который означает, что каждая из w функций участвующих в формировании функции произведения реализуется для одинаковых входных значений. Если из этих функции каждая не значительно теряют информацию, то общее количество теряемой информации будет слишком большим. Мы показали, что выбирая соответствующую кодировку корректирующую ошибки в RS схеме и устанавливая параметры должным образом, можно задать в больше мере зависимое от w и т.о. получить достаточную энтропию для распределения входных значений, чтобы определить однонаправленность и получить ССа безопасность при использовании только TDF с незначительной потерей данных для w-зависимых функций произведения.

Вопросы оставленные на обсуждение. Интересным вопросом будет можно ли получить ССА-безопасность основанную на других предположениях стойкости. К примеру, возможно ли построение функций с лазейкой теряющих незначительное количество данных из предположений о стойкости для которых пока не известны способы достижения ССА безопасности? Другой насущный вопрос – это есть ли LTDF с малым количеством теряемой информации достаточным для построения других примитивов таких как хэш функции стойкие от коллизий. И в заключении, остаётся узнать есть ли другие направления в разработке методик для реализации объёма потери информации, т.е. увеличив тем самым её размерность до входных значений.

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

Обозначения. В данной работе, обозначает параметр безопасности. Для случайной переменной , пусть обозначает выбор значения равномерно распределённого случайным образом (распределение) для и присваиваем его . Говорим, что функция пренебрежимо мала, если и значительна если . Пусть обозначает переменную пренебрежимо малую функцию, а полиномиально ограниченную функцию и обозначает переменную значимую функцию.

Задание вероятности. Пусть будут двумя (дискретными) случайными переменными распределёнными над счётным набором относительно и соответственно. Статистическое расстояние между и (или между относительно и ) определяется как

Для двух случайных переменных ансамбли и индексируются параметром (безопасности) , и говорится, что , статистически неразличимы по признакам (обозначатся ), если Кроме того,, вычислительно неразличимы (обозначается ) если

для любого РРТ алгоритма (где вероятность берётся для характеристики случайности и случайных значений ,).

Для случайной переменной принимающей значения из области определения , определим минимальную энтропию как

.

где обозначает предсказуемость случайной переменной .

Другим полезным обозначением энтропии будет средняя минимальная энтропия (определённая в [5]) случайной переменной (заданной ), которая определяется как показано ниже:

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

TemplateLemmaIcon.svg Лемма «Лемма 1 (Лемма 2.2b [1]). »
Пусть есть случайные переменные такие, что принимает максимум значений. Тогда

В частности, если независим от , то .


Функции с лазейкой. Набор инъективных функций с лазейкой будет кортежем РТ алгоритмов таких, что (вероятностный) алгоритм выходных пар состоит из функциональных индексов и соответствующей лазейки . Детерминистический алгоритм , для входного индекса функции и выводит . Алгоритм для заданной лазейки , вычисляет инверсию функции . Рассмотрим набор инъективных функций с лазейкой с областью определения и пусть будет распределением над . Говорим, что будет однонаправленной относительно , если для всех РРТ злоумышленников и любого полинома следует, что для всех удовлетворительно больших

где и

Говорим, что будет с –потерей данных, если существует РРТ алгоритм , который для параметра безопасности выводит и такие, что

  • Первые выходные значения и вычислительно неразличимы по признакам.
  • Для любого выводимого , отображение будет иметь размерность не более. Мы называем значением потери данных.

Иногда мы будем называть TDF функцию с лазейкой теряющую незначительное количество данных (LTDF).

Шифрование с открытым ключом. Схема шифрования с открытым ключом будет тремя РРТ алгоритмами. Алгоритм генерации ключа , для выходного параметра безопасности , выводит пару ключей . Алгоритм шифрования получает на входе открытый ключ и сообщение (для некоторого пространства сообщений ) и выводит шифртекст . Алгоритм расшифровки на входе имеет секретный ключ и шифртекст , и выводит сообщение либо (отказ). Требуется чтобы где вероятность берётся для случайностей и

Сильное определение безопасности для криптосистемы с открытым ключом рассматриваемое в данной работе заключается в неразличимости по признакам шифртекста для заданной атаке на шифртекст (IND-CCA) [13,17]. Определим IND-CCA безопасность как игру между злоумышленником и окружением следующим образом. Окружение выполняет для получения пары ключей и вычисляет бит . Это даёт для . выводит пару сообщений с . Окружение возвращает соответствующий шифртекст к . Кроме этого, в течении всей игры у злоумышленника есть доступ к оракулу расшифровки Dec т.е. входу и выхожу Одно ограничение которое накладывается на злоумышленника это то, что он не может запрашивать конкретный шифртекст у оракула расшифровки, т.к. это приведет к тривиальной победе. В конце игры злоумышленник возвращает предполагаемый бит . Определим IND-CCA преимущество злоумышленника как

Говорится что будет ССА-безопасной, если пренебрежимо мала при для всех РРТ злоумышленников .

Кодировки коррекции ошибок. Мы используем кодировки коррекции ошибок для построения ССА безопасной схемы. В данном разделе мы рассмотрим некоторые базовые определения и утверждения из теории кодирования. Ограничимся только материалом необходимым для доказательства безопасности нашей ССА конструкции. Для детального рассмотрения данного вопроса просим читателя обратиться к [10].

Пусть есть множество символов (алфавит) с . Для двух строк расстояние Хемминга определяется как число координат, где отличается от . Предположим теперь что кодируемое отображение будет Код будет простым изображением такого отображения (т.е. ), с Минимальное расстояние для кода определяется как

Используем для обозначения кода с длинной блока , длиной сообщения минимальным расстоянием и размером алфавита

Для ССА схемы необходима кодировка, слова которой будут «настолько далеки» насколько это возможно. В частности, для фиксированного , нужна кодировка которая максимизирует при условии, что полиномиален в . С помощью границы Синглетона [23] для любого кода и размера алфавита, которые непосредственно дают верхнюю границу для Коды удовлетворяющие границе Синглетона называются Максимально разделяемыми по расстоянию (MDS) кодами.

Коды Рида-Соломона. Коды Рида-Соломона (представленные в [18]) являются частным примером MDS. Опишем (определим) конструкцию семейства асимптотических кодов Рида-Соломона. Пусть обозначает код Рида-Соломона (или более точно – семейство RS кодов) с сообщением длинной , длинной блока и размером алфавита . Схема работает следующим образом:

  • Генерация: Выбирается поле (для удобства мы используем как соответствующее поле, где наименьшее простое значение, такое что ). Также выберем различных элементов (точки оценки).
  • Кодировка: Пусть есть сообщение и пусть будет соответствующим полиномом. Кодировка сообщения определяется как

где оценка производится над .

TemplateLemmaIcon.svg Лемма « Лемма 2 »
Код Рида-Соломона имеет минимальное расстояние .Также длинна кода и временная сложность кодировки будут полиномаильны в


Произведения и связанные входные значения

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

Произведения и предположение о потере данных

Сперва определим -зависимое произведение набора функций

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

Мы используем следующую лемму в дальнейшей части нашей работы. В ней утверждается, что w-зависимые произведения (для ) реализуют абсолютное количество потери информации.

TemplateLemmaIcon.svg Лемма «Лемма 3 (предположение о потере информации).»
Пусть это параметр безопасности. Для любого семейства TDF с пространством сообщений , если будет с потерей, тогда –зависимое произведение семейства (определённое выше) строящееся из будет с –потерей для всех .


Доказательство. Сперва, если существует эффективный алгоритм генерации ключа с потерями , который выводит неразличимые по признакам функции взятые из G, тогда с помощью гибридного аргумента следует, что , которая выполняет G независимо w раз для получения и вывода (s,t), где и выводит неразличимые по признакам ключи из .

Далее т.к. каждый выводится G отображением имеет размерность не более , то для каждого s выводимого отображение будет иметь размерность не более Ч.т.д.

Непосредственное применение Леммы 3 заключается в том, что -LTDF использует однонаправленные функции с лазейкой и CPA-безопасное шифрование (доказательства этих утверждений довольно элементарны и в силу этого опускаются). Мы упростили это утверждение в виде следствия для полноты.

TemplateLemmaIcon.svg Лемма « Следствие 1.»
Пусть есть полином. Тогда -LTDF использует однонаправленные функции с лазейкой и CPA-безопасные схемы шифрования.


Подмножество восстанавливаемых распределений

Т.к. хорошо известно, что если F однонаправленная относительно равномерного распределения на , то произведение будет однонаправленным относительно распределения над , нужно рассматривать безопасность произведений когда входы взаимосвязаны и не обязательно равномерно распределены. Нужно рассмотреть распределения которые мы назвали восстанавливаемым (d,w)-подмножеством.

TemplateDifinitionIcon.svg Определение «Определение 2 (восстанавливаемое распределение (d,w)-подмножества (SRD)).»
Пусть такие, что , то будет областью определения а распределением с . Говорим, что есть восстанавливаемое (d,w)-подмножество (и обозначаем его ) если каждый w-кортеж будет полностью и однозначно восстановим из любого подмножества различных элементов кортежа.

Легко заметить, что частный случай где d = 1 и даёт равномерное w-повторимое распределение используемое в упрощённой конструкции ССА безопасных криптосистемах из [21]. Для нашей ССА-схемы, нужно выбрать значение d меньше чем w (это необходимо для наиболее лучшей симуляции оракула расшифровки), но наиболее близко к w насколько это возможно для того, чтобы минимизировать требуемую потерю данных TDF (чем ближе к 1 значение d/w, тем меньшая потеря данных будет у нас в ССА схеме). Отметим, что SRD обозначение схоже с другим известным обозначением в теории кодирования и криптографии; их сравнения и различия показаны в [11].

Получение полиномаильной интерполяции. Используем полиномиальную интерполяцию как способ эффективного получения для любого значения d,w. Схема будет идентичной той, что используется Шамиром [22] для (d,w)-пороговой схемы разделения секрета. На входе будет простое Q (с ) и целые d,w а полученный алгоритм выбирает независимо d значений распределённых равномерно случайными образом из (это соответствует d коэффициентам полинома степени (d – 1)). Этот алгоритм затем просто выводит где оценка реализуется в и представлен с помощью бинарных строк длинной не более Следующая лемма (доказанная в [11]) утверждает, что выходное распределение получения полиномиальной интерполяции будет восстанавливаемым распределением (d,s)-подмножества с достаточной энтропией.

TemplateLemmaIcon.svg Лемма «Лемма 4.»
Пусть Тогда вышеуказанный алгоритм будет алгоритмом получения для . К тому же минимальная энтропия распределения будет


ССА безопасность для функций с малой потерей данных

В данном разделе доказывается наш основной результат: TDF с потерей, которая теряет значительную часть бита реализует ССА-безопасное шифрование. Начнём с описания схемы шифрования Розена и Сегева [21], которая показывает, что ССА безопасность реализуется с помощью (однонаправленных) безопасных инъективных функций с лазейкой для некоторых связанных произведений. Затем покажем, что TDF с (n,2)-потерей используется для инъективной функции с лазейкой безопасной для некоторых связанных произведений. Завершим доказательство с помощью того, что TDF с (n,2)-потерей можно создать в виде чёрного ящика из LTDF которая теряет части простого бита (это видно по аргументу предположения о потери данных). Для простоты, мы опишем схему шифрования простого бита. Согласно недавно полученному результату [12], это явно реализует существование многоразрядных ССА-безопасных схем. Отметим, однако, что одноразрядную схему шифрования можно получить напрямую с помощью простой замены ключевых предикатов h на универсальную хэш функцию, как в РКЕ схемах из [15].

Схема Розена-Сегева

Вспомним криптосистему из [21]. Пусть есть набор инъективных функций с лазейкой, есть входное распределение такое, что любой выводимый можно воссоздать для заданного любого размера d < w подмножества x. Пусть также будет предикатом, есть функция РТ шифрования для исправляющего ошибки кода с расстоянием d а есть единовременная схема подписи, верификационные ключи которой являются элементами из Схема RS шифрования работает следующим образом:

Генерация ключа: На входе будет параметр безопасности , для каждого и каждого , выполняется , генерация ключа для семейства инъективных функций с лазейкой. Возвращается пара (pk,sk) где

Шифрование: На входе открытый ключ pk и однобитовое сообщение m, выполняется для генерации (VK,SK) и получения из Применяем кодировку исправления ошибок к VK для получения Тогда выводится

где VK будет тем, что указан выше и

Расшифровка: На входе секретный ключ sk и шифртекст , проверяется эквивалентен ли единице. Если нет – выводится В противном случае, вычисляется и выбирается d различных индексов Используется лазейка для вычисления

Используем эти для воссоздания полного вектора Если для всех выводим и в противном случае выводим Розен и Сегев доказали следующую теорему:

TemplateTheoremIcon.svg Теорема Теорема 1 (Теорема 5.1 в [19]).
Если П есть одноразовая стойкая схема подписи, безопасная при связанном произведении, и h есть клюевй предикат для относительно , тогда вышеуказанная РКЕ схема будет IND-CCA безопасной.
Доказательство
Без доказательства


Наш результат

В данном разделе мы покажем следующий результат

TemplateTheoremIcon.svg Теорема Теорема 2 (основная теорема).
ССА-безопасные схема можно построить в виде чёрного ящика из LTDF которые теряют бит.
Доказательство
Доказательство разбивается на 2 шага. На первом шаге (Лемма 5) покажем, что TDF с потерей данных расширяют семейства инъективных функций с лазейкой безопасных при распределении связанного произведения с достаточно большой энтропией. Более того, чем больше энтропии имеет соответствующее распределение, тем меньше потери данных будет и наших LTDF. На втором и завершающем шаге (Лемма 6) покажем, что выбирая соответствующее кодирование исправления ошибок и связанное входное распределение с большой энтропией в схеме Розена-Сегева, можно получить однонаправленность для соответствующих связанных произведений (и следовательно ССА-безопасность) начиная от TDF с потерей данных при минимальных требованиях к этой потере. Говоря более определённо, используя равномерную (которая имеет большую энтропию, см. Лемму 4) в качестве нашего соответствующего распределения и кодировку Рида-Соломона для ЕСС, покажем, что TDF с (n,2)-потерей достаточно для ССА-безопасного шифрования. Затем мы выведем теорему 2 анализируя то, что TDF с (n,2)-потерей можно создать с помощью функций с -потерей (где ) (см. Лемму 3).


TemplateLemmaIcon.svg Лемма « Лемма 5.»
Пусть есть набор функций с лазейкой и (n,l)-потерей данных и пусть есть её w-зависимой произведение для Пусть будет входным распределением с минимальной энтропией . Тогда будет безопасной при связанных произведениях когда


Доказательство. Доказательство схоже с доказательством из [15]. Предположим наоборот, что существует инвертор , который выполняет инвертировании с вероятностью для некоторого полинома р. Создадим злоумышленника, который может отличить по признакам ключи потери данных и настоящие ключи. В силу стандартного гибридного аргумента, достаточно показать, что существует злоумышленник , который может различить по признакам с не пренебрежимо малой вероятностью случай где заданы ключей потерь (генерируемых ) от случая где задаются реальных ключей (генерируемых G). Злоумышленник для входных ключей получает из и выполняет инверсию Если, однако, s берётся из , то вероятность успеха для I будет не более

Для ограничения этой вероятности используем Лемму 1 и увидим, что

Принимая во внимание (1), получаем, что

где в последнем неравенстве мы используем ограничение для l. Из этого следует, что вероятность реализации I в случае когда заданы ключи потери будет ограничена сверху Поэтому, для такого выбора l инвертор имеет пренебрежимо малую вероятность успеха и т.о. может отличить по признакам ключи из G и ключи из что вытекает в противоречие. Ч.т.д.

TemplateLemmaIcon.svg Лемма « Лемма 6.»
ССА-безопасные схемы можно построить в виде чёрного ящика из TDF с (n,2)-потерей данных.


Доказательство. Пусть Пусть также есть кодировка Рида-Соломона с (для некоторой константы е с ), для некоторой константы c > 1 + e, q наименьшего простого значения такого, что и расстояния d = w – k + 1. Пусть также есть распределение полученное с помощью полиномиальной интерполяции (см. Раздел 3.2) для некоторого простого значения Q такого, что Пусть наконец есть набор функций с лазейкой и (n,2)-потерей данных и есть его w-зависимое произведение. В силу схемы (Лемма 4, Раздел 3.2) имеет минимальную энтропию и может быть получен за время К тому же по свойствам кода Рида-Соломона имеем

и следовательно

Поэтому получаем, что

для некоторой –функции. Применяя Лемму 5, получаем, что безопасна при вышеупомянутом связанном произведении. Пусть h есть ключевой предикат для w-зависимого произведения (относительно ). Применяя конструкцию Розена-Сегева вместе с Теоремой 1 из Раздела 4.1, заключаем, что TDF с (n,2)-потерей данных реализует ССА-безопасность (в плане использование её как чёрного ящика). Ч.т.д.

Конкретная схема TDF с незначительной потерей данных

Основная идея. В данном разделе мы покажем построение LTDF которая теряет ¼ бита. На высоком уровне, наша конструкция работает следующем образом: основным компонентом является функция с лазейкой g (лазейка t), которая статистически теряет l бит ( и l = 0 соответственно для инъективной функции с лазейкой). Пусть также будет детерминистической функцией такой, что (по некоторому вычислительному предположению СА) и теряет бит (т.е. для некоторого ). Рассмотрим теперь функцию h такую, что ||h(x)|| = l (где обозначает размерность в битах) и (g (x), h(x)) равномерно распределены для отображения x (что можно эффективно получить для заданного t) для всех входов х. Данные распределения инъективной функции с лазейкой и функции с потерей данных будут s = (g, h) и соответственно. Не сложно заметить, что соответствует функции с -потерей данных. В действительности Наконец, неразличимость по признакам для и g означает что

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

Предположение о стойкости. Рассмотрим следующие два распределения (где ).

различные простые значения различные простые значения

где ||N|| обозначает размер в битах N и ||N|| = n определяет то, что наиболее значимым битом N будет 1.

TemplateDifinitionIcon.svg Определение « Предположение 1 (2v3Primes).»
Для любого РРТ алгоритма и любого полинома где вероятность берётся для случайности получения N и внутренней случайности .

Это предположение (в немного другом виде) было дано в [2] под названием 2OR3A.

Схема. Для нашей функции g используем квадратичный модульное произведение N двух больших (сбалансированных) простых p и q. Эта функция будет базисом для криптосистемы Рабина [16]. Определим семейство инъективных функций с лазейкой следующим образом:

с и pq имеет размер в битах n + 1. Т.е. Возвращаем (s,t) где s = N и t = (p,q).


с и pq имеет размер в битах n + 1. Т.е. Возвращаем (s,-) где s = N.

F(s,x): анализируем s как N. Для входа вычисляем Определяем если x > N/2 и в противном случае и если и в противном случае где есть символ Якоби x по модулю N. Возвращаем

анализируем t как (p,q) и y’ как Вычисляем квадратные корни y используя p и q. Вычисляем также и для всех и выводим (уникальный) такой, что и

Отметим, что если даже модуль N будет размером n + 1 бит (т.е. ), областью определения функции будет

TemplateTheoremIcon.svg Теорема Теорема 3.
F указанный выше есть семейство функций с лазейкой и (n,1/4)-потерей данных по 2v3Primes предположению.
Доказательство
{{{3}}}


Слова благодарности

Мы хотели бы поблагодарить Михира Беллара, Рассела Импаглиазо, Ика Килтза, Даниэля Миккианчио, Криса Пикерта, Гила Сегева, и Брента Уотерса за их полезные заключения по данной работе. Скотту Елеку был предоставлен NSF грант CNS-0831536 и CNS-0627779. Петросу Молу был предоставлен NSF грант CNS-0716790 и CNS-0634909.

Справочная литература

  1. 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)
  2. Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications(extended abstract). In: STOC, pp. 103–112. ACM, New York (1988)
  3. 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. Cachin, C., Micali, S., Stadler, M.: Computationally Private Information Retrieval with Polylogarithmic Communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999)
  5. Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM J. Comput. 38(1), 97–139 (2008); Cachin, C., Camenisch, J.L. (eds.): EUROCRYPT 2004. LNCS, vol. 3027, pp. 523–540. Springer, Heidelberg (2004)
  6. Freeman, D., Goldreich, O., Kiltz, E., Rosen, A., Segev, G.: Number-theoretic constructions of lossy and correlation-secure trapdoor functions. In: PKC 2010. Springer, Heidelberg (to appear, 2010)
  7. Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing – STOC 1989, pp. 25–32. ACM, New York (1989) Chosen-Ciphertext Security from Slightly Lossy Trapdoor Functions 311
  8. Hofheinz, D., Kiltz, E.: Practical Chosen Ciphertext Secure Encryption from Factoring. In: Joux, A. (ed.) EUROCRYPT 2009, vol. 5479, pp. 313–332. Springer, Heidelberg (2009)
  9. Kiltz, E., O’Neill, A., Smith, A.: Lossiness of RSA and the Chosen-Ciphertext Security of OAEP without Random Oracles (2009) (manuscript)
  10. Macwilliams, F., Sloane, N.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (January 1983)
  11. Mol, P., Yilek, S.: Chosen-Ciphertext Security from Slightly Lossy Trapdoor Functions. Cryptology ePrint Archive, Report 2009/524 (2009), http://eprint.iacr.org/
  12. Myers, S., Shelat, A.: Bit Encryption Is Complete. In: FOCS, pp. 607–616. IEEE Computer Society, Los Alamitos (2009)
  13. Naor, M., Yung, M.: Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. In: STOC, pp. 427–437. ACM, New York (1990)
  14. Peikert, C.,Waters, B.: Lossy Trapdoor Functions and Their Applications (October 5, 2009), Latest Version availbale at http://www.cc.gatech.edu~cpeikert/
  15. Peikert, C., Waters, B.: Lossy Trapdoor Functions and Their Applications. In: STOC 2008, pp. 187–196. ACM, New York (2008)
  16. Rabin, M.O.: Digitalized Signatures and Public-Key Functions as Intractable as Factorization. Technical report, Massachusetts Institute of Technology (1979)
  17. Rackoff, C., Simon, D.R.: Non-interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 433–444. Springer, Heidelberg (1991)
  18. Reed, I.S., Solomon, G.: Polynomial Codes Over Certain Finite Fields. SIAM J. Comput. 8(2), 300–304 (1960)
  19. Rosen, A., Segev, G.: Chosen-Ciphertext Security via Correlated Products. IACR ePrint Archive, Report 2008/116
  20. Rosen, A., Segev, G.: Efficient lossy trapdoor functions based on the composite residuosity assumption. IACR ePrint Archive, Report 2008/134
  21. Rosen, A., Segev, G.: Chosen-Ciphertext Security via Correlated Products. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 419–436. Springer, Heidelberg (2009)
  22. Shamir, A.: How to Share a Secret. Commun. ACM 22(11), 612–613 (1979)
  23. Singleton, R.C.: Maximum Distance q-nary Codes. IEEE Transactions on Information Theory 10, 116–118 (1964)

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

  1. Department of Computer Science & Engineering University of California, San Diego E-mail: [1]
  2. Department of Computer Science & Engineering University of California, San Diego E-mail: [2]

Литература

  1. Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM J. Comput. 38(1), 97–139 (2008); Cachin, C., Camenisch, J.L. (eds.): EUROCRYPT 2004. LNCS, vol. 3027, pp. 523–540. Springer, Heidelberg (2004)