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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 12:05, 30 октября 2015.
Псевдослучайные ранцы и типовая сложность изучения ошибок и их поиск сокращенного решения
Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions.png
Авторы Abhi Shelat[@: 1] and
Petros Mol[@: 2]
Опубликован 2011 г.
Сайт Department of Computer Science
Перевели Vladislav Yushkov
Год перевода 2015 г.
Скачать оригинал
Аннотация. Мы изучаем псевдохаотичность ограниченных функций ранца по произвольным конечным абелевым группам. Предыдущие работы рассматривают только определенные семьи конечных абелевых групп и 0-1 коэффициентов. Главный технический вклад нашей работы - новая, общая теорема, которая обеспечивает достаточные условия, при которых псевдохаотичность ограниченных функций ранца следует непосредственно от их одностороннего. Наши результаты обобщают и существенно расширяют предыдущую работу Impagliazzo и Naor (J. Криптология 1996).
Как применение новой теоремы, мы рассматриваем типовой поиск сокращенного решения с проблемами обучения с ошибками (LWE),введенный (Regev, STOC 2005) и широко используемый в основанном на решетке криптографии. Конкретно мы показываем что, для широкого диапазона параметров, образцы LWE могут быть доказаны неотличимыми от случайного только в соответствии с гипотезой, которые ищут, LWE - односторонняя функция для того же самого числа образцов.
Ключевые слова: LWE, вероятность, Гауссово распределение.

Введение

Проблема изучения ошибок, введенная Регевым в [1], проблема восстановления секретного n-мерного вектора целого числа , учитывая коллекцию встревоженных случайных уравнений , где выбран однородно наугад и для некоторого маленького, беспорядочно выбранного остаточного члена . В последние годы LWE использовался, чтобы существенно расшириться, объем решетки базировал криптографию, приводя к решениям многих важных шифровальных задач, включая шифрование открытого ключа, безопасного против пассивного [1][2][3] и активного нападения [4][5] (иерархическая) идентичность базировала шифрование [6][7][8][9] цифровые подписи [6][7] забывающие протоколы передачи [3], несколько форм утечки эластичного шифрования [10][11] [12][13], гомоморфное шифрование [14] и больше.

Универсальность проблемы LWE в строительстве множества крипто-графических приложений связано в значительной части своих псевдослучайных свойств: как доказано в [1], если восстановление (с высокой[прим. 1] вероятностью 1) секретных S из образцов () вычислить трудно, то это также трудно выделить образцы LWE () из равномерно случайных чисел (), где выбираются равномерно и независимо наугад. Другими словами, любое эффективное различие (между LWE и равномерных распределений) могут быть превращены в инвертор, который восстанавливает секретные S, только с полиномиальным замедлением.

На теоретической стороне криптография, основанная на LWE, поддержана глубоко худший случай/связи среднего случая [1][5], показывая, что любой алгоритм, который решает LWE (в среднем), может быть эффективно преобразован в (квант) алгоритм, чтобы решить (худший случай) самые твердые случаи нескольких известных проблем приближения решетки, которые, как полагают, тяжелы, включая приближение минимального расстояния решетки в пределах факторов, которые растут многочленным образом в измерении и связанных проблемах [15]. Это должно быть отмечено, что, в то время как такие доказательства безопасности, основанной на предположениях решетки худшего случая, обеспечивают твердое теоретическое оправдание за распределения вероятности, используемые в криптографии LWE, они едва полезны на практике: чтобы получить значащие оценки на твердости ломки криптографии LWE, это обычно более полезно и соответствующе предугадать твердость среднего случая решения LWE и использования что это как отправная точка. Фактически, вся недавняя работа, нацеленная на определение соответствующих ключевых размеров и параметров безопасности [16][17][18], следует за этим подходом и исследует экспериментально конкретную твердость решения LWE в среднем.

В свете, которого, LWE лучше всего сформулирована как проблема инвертирования одного - путем рандомной функции (внесенный в указатель случайной матрицы , где m - число образцов), который наносит на карту тайну s и ошибочный вектор к . Поиск сокращенного решения [1] такая, что, если рандомная функция LWE односторонняя, то это - также хороший псевдослучайный генератор. Однако, сокращение [1] так или иначе скрывает очень важную деталь: ценность m, для которого функция, как предполагается, односторонняя, намного выше (все еще многочленным образом связанный) к ценности m, для которого продукция функции псевдослучайна. В то время как теоретические результаты, основанные на проблемах решетки худшего случая, довольно нечувствительны к ценности m (т.е., число образцов, используемых в случае LWE), это число становится более важной и релевантной, рассматривая конкретные нападения на твердость среднего случая LWE.

Например, недавние алгоритмические результаты [19], показывют это, когда ошибки будут достаточно маленькими, проблема LWE может быть решена в подпоказательном (или даже полиномиальном) времени, обеспечив достаточно большое (но все еще многочленное) число образцов доступности. Поэтому, для определенных диапазонов параметров, число доступных образцов может оказать значительное влияние на вычислительную твердость проблемы LWE. Аналогично, некоторые нападения решетки выполняют лучше на практике, когда дали многие (как правило ) образцы [16]. Однако, основанные на LWE схемы шифрования (например, см. [17]), как правило, выставляют только небольшое количество образцов (скажем, сопоставимый с измерением n тайны s LWE) во время ключевого поколения и шифрования. Фиксация числа доступных образцов к маленькой стоимости может значительно уменьшить эффективность конкретных нападений и увеличить нашу уверенность в безопасности схем.

Нужно также отметить, что, когда число доступных образцов выше определенного порога, можно эффективно произвести произвольное число дополнительных образцов [6][11][20], но за счет увеличения величины ошибок. Так, наверняка другие диапазоны параметров воздействие увеличения числа из образцов может не быть столь же важным как в [19]. Однако, даже в таких ситуациях, используя большое количество образцов прибывает в цену понижения качества образцов, которые могут отрицательно повлиять на конкретную безопасность и исполнение основанных на LWE шифровальных функций.

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

Вклады и заявления. Пусть является конечной абелевой группой, и последовательность элементов группы выбранных случайно наугад. Элементы группы g определяют функцию ранца , который отображает вектор к элементу группы . Если входной х ограничен векторами с маленькими записями, то для большого разнообразия групп предугадано, чтобы быть односторонней семьей функции, т.е., семьей функций, которые трудно инвертировать в среднем, когда ключ g выбран однородно наугад. Например, если входной х ограничен набором двоичных векторов, обращение является знаменитой проблемой подмножества сумм, которая предположена, что это трудно решить, в среднем, и была тщательно изучена в криптографии. В классической работе [21], Impagliazzo и Naor показали, что для некоторых конкретных, но представительных, выбор группы G, если функция суммы подмножества односторонняя, то это также псевдослучайный генератор, т.е., в вычислительном отношении трудно различить из равномерно случайного элемента в , когда , выбираются случайно наугад. Мы обобщим результаты [21] в двух отношениях:

- Мы рассматриваем функции по произвольным группам G. Только группы формы считали в [21], и для двух определенных (но представитель) выбор (главными и власть 2).
- Мы рассматриваем входные коэффициенты , которые берут ценности от набора (или ) для любого (многочленным образом ограниченный) s. Кроме того, мы рассматриваем произвольные входные распределения. В отличие от этого, результаты в [21] держатся для входов x распределенный однородно с коэффициентами в .

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

1. - односторонняя семейная функции относительно входного распределения , и
2. Определенные свернутые версии (где и ключ и продукция спроектированы на группу фактора для некоторого ,), имеют псевдослучайную продукцию.

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

- Группы, порядок которых содержит только большие главные факторы, больше, чем максимальное значение входных коэффициентов. Циклические группы с простого порядка и векторных групп для простого попадают в эту категорию. Этот результат обобщает тех в [21] от однородного двоичного входа до произвольных входных распределений.
- Распределение, что при складывании (по модулю небольших делителей порядка ,)поддерживает высокую энтропию относительно размера группы фактора . (См. Теорема 6.) Группы форм и однородное входное распределение для некоторых удовлетворяет это требование. Этот набор параметра является очень привлекательным выбором на практике, так как оба групповых операций и выборки входного особенно эффективно и просто в реализации.

Используя двойственность между LWE и задаче о ранце [22] [23], мы получаем образец поиска сокращенного решения для нескольких интересных вариантов в модуль и входным распределением, которые включают (среди прочих):

- и любое ошибочное распределение. Это непосредственно доказывает псевдохаотичность известного изучения вопросов равенства с шумом (LPN) проблем, как уже установлено в [24][25], но таким образом, сохраняя образец.
- Начальный и любое полиномиальное ограничение распределения ошибок.
- Начальный модуль мощности для , достаточно большое так, чтобы ошибочное распределение было сосредоточено более .
- для маленького главного p и однородного ошибочного распределения по .

Эти результаты включают в категорию (см. ниже), несколько предыдущих результатов псевдохаотичности для LWE [1][11] и LPN [25], но с важным различием. В то время как доказательства в [1][11][25] требуют это LWE (соотв. LPN), трудно решить для очень большого количества примеров, наши сокращения - типовой пример: псевдохаотичность LWE (соотв. LPN), держится, если та же самая проблема односторонняя для того же самого числа примеров. Мы отмечаем, что предыдущие результаты часто выражаются как поиск сокращенного решения с высокой вероятностью, к решению проблемы решения LWE с незначительным преимуществом, объединяя увеличение вероятности сокращения и успеха поиска сокращенного решения в единственное заявление. В отличие от этого, наше сокращение показывает, как решить проблему поиск сокращенного решения с незначительной вероятностью. Наши результаты включают в категорию предыдущую работу в том смысле, что проблема поиска сокращенного решения может быть решена с высокой вероятностью первым призывом нашего сокращения и затем усилением вероятности успеха, используя стандартные методы повторения. Конечно, любое такое увеличение вероятности успеха естественно несло бы стоимость более высокой типовой сложности. Мы отмечаем, что тщательное изучение худшего случая к сокращениям среднего случая для LWE [1][5] показывает, что эти сокращения непосредственно поддерживают догадку, что LWE - сильная односторонняя функция. Как уже обсуждено, худший случай к сокращениям среднего случая не обеспечивают количественно интересные результаты и лучше всего используются в качестве качественных аргументов, чтобы поддержать догадку, что определенные проблемы в вычислительном отношении трудны в среднем. Под стандартной догадкой, которые ищут LWE, сильная односторонняя функция, результаты в этой газете предлагают довольно трудное, и типовое доказательство сохранения, что LWE - также хороший псевдослучайный генератор, который может эффективно использоваться для строительства многих, другая решетка базировала открытый ключ шифровальных примитивов. В отличие от этого, не известно, как использовать в своих интересах сильный односторонний из LWE в пределах предыдущих поисков сокращенного решения, приводящих к главному ухудшению параметров. Конечно, если мы изменим предположение сложности, и как отправная точка мы используем твердость худшего случая проблем решетки или предположения, что LWE - только слабая односторонняя функция, то тогда наше сокращение также обязательно подвергнется большому фотографическому увеличению в типовой сложности посредством увеличения и приведет к количественно неинтересным результатам.

Прелиминарии

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

Вероятность

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

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

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

(1)

получают с помощью выбора функции наугад и оценки его в случайном входе. Семейной функцией называют - однородный, если нет никакого (вероятностного) алгоритма работает хорошо в большей части , таким образом, что . В этой статье удобно использовать связанное понятие “необратимой функции”. </math>A(t,\epsilon)</math>, - инвертор для семьи функции является (вероятностным) алгоритмом хорошо работающей в большей части , таким образом что </math>Pr \left \{x = y | f \larr \mathcal U(F), x \larr \mathcal X, y \larr \mathcal I (f, f(x))\right \} \ge \epsilon</math>. Если также существует , - инвертор для семейной функций , то мы говорим, что есть , - обратимый. Семейная функция, таким образом, что нет никакого , - инвертор, называют ,- необратимым. В этой статье мы имеем дело с семейной функцией , которые являются (почти) инъективным, т.е. с подавляющей вероятностью по и , там не существует никакой такой что . Когда дело обстоит так, тогда односторонний и необратимость - эквивалентные понятия. - псевдорандомная семейность генератора семейной функции таким образом, что связанное распределение (1) </math>(t,\epsilon)</math>- псевдорандомное, т.е., это , - неотличимо от равномерного распределения .

Асимптотика. Мы используем n в качестве (безопасность) параметра, который управляет всеми другими параметрами. Если не указано иное, любой другой параметр (говорят m) будет многочленным образом связан с n. Мы используем стандартное асимптотическое примечание , и т.д. Мы пишем для набора незначительных функций и для набора многочленным образом ограниченных функций. В асимптотическом вычислительном урегулировании сложности каждый часто рассматривает ансамбли вероятности, т.е., последовательности распределений вероятности возможны различными наборами . Два ансамбля распределений и статистически близки (обозначим ), если и - закрываются для некоторой незначительной функции . Ансамбли и в вычислительном отношении неразличимы (обозначим ), если и - неразличимы для и какой-либо под однородной последовательностью отличительных признаков. Определения для семей функции также расширены очевидным способом функционировать семейные ансамбли в асимптотическом урегулировании, беря и и рассматривая однородные последовательности различения алгоритмов. В частности, семейный ансамбль функции является односторонним, если есть - один путь к и какой-либо . Это псевдослучайно, если связанное (асимптотическое) распределение (1)есть- псевдорандомное, т.е., это - неотличимо от равномерного распределения .

Дискретная гауссовских распределений. Гауссово распределение играет центральную роль в обучении с ошибками (LWE) проблем. Для каждого образца , распределение из которого обращается, это нормальное распределение над целыми числами. Ниже мы сосредоточены главным образом на дискретном распределении Гаусса и обеспечиваем границы на ее вероятностном столкновении. Эти границы используются в налаживании поиска сокращенного решения для изучении проблем. Аналогичные оценки могут быть установлены для дискретизации Гаусса (определены в [1]).

Гаусса функция на с параметром и центром с определяется как . Дискретная распределение Гаусса над счетным множеством S определяется как

Здесь мы интересуемся векторами распределяются в соответствии с . В этом случае, каждая координата от тождественно и независимо распределяются в соответствии с 1-гауссовского . Для нашего поиска сокращенного решения и изучения ошибок с дискретным распределением Гаусса, мы должны рассмотреть сложенное (1-мерное) распределение . Следующая лемма ограничивает вероятность столкновения этого распределения.

Лемма 1. Для любого и , Мы получаем . Кроме того, если , Иначе .

Группы и семейные функции ранца

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

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

Лемма 2. Для любой группы и целого векторa . В частности,

Ранцевые семьи. Для любой группы и входной распределительной над , семейные ранцы являются семейной функцией с входной распределительной и набором функций проиндексированы и определяем, как . Мы будем часто использовать вместо , чтобы описать членскую функцию, с . Когда ясны из контекста, мы просто напишем . Мы часто рассматриваем свернутые ранцевые семьи над фактор-группой . Для краткости при и ясно из контекста, мы будем писать вместо к . Cледующая лемма показывает, что распределение , связанный со свернутой семейной функцией ранца, которая тесно связана с распределением

(2)

Лемма 3. Для любого семейного ранца и , . Кроме того, псевдослучайное, если и только если является псевдослучайной. Для группы , что сжимает свой вклад, Лемма 4 дает верхнюю границу на статистическом расстоянии между и , обобщая остаточную хэш Лемму [26], к (не обязательно) универсальной семейной функций ранца к на произвольные группы.

Лемма 4 (LHL, обобщенное). Для любой конечной абелевой группы и целого ,

(3)

где является показателем и перебегает все делители .

Анализ Фурье и изучение

Анализ Фурье широко используется в теории обучения, особенно в контексте функций обучения, определенные над булевой гиперкуба (см. [27][28][29] для некоторых примеров). В криптографии, два примечательных примера являются Кушилевитц-Мансура [27] формулировка доказательства Голдрейх-Левина [30] злостный предикат для любой односторонней функции и доказательства злостных предикатов для нескольких теоретико-числовых одноходовых функций по Акавию, Голдвассера и Сафра [31].

Ниже мы рассмотрим некоторые основные факты из анализа Фурье, сфокусированном на дискретном преобразованим Фурье над конечной абелевой группой. Мы ограничимся презентацией на то, что необходимо, и отсылаем заинтересованного читателя к [32][33] для более подробной информации.

Основы Фурье. Пусть конечная абелева группа и функции из в комплексные числа. Скалярное произведение и определяется как

?

где сопряженное . - норма и - норма определяются как

и

Набор символов (обозначается как ) есть множество всех гомоморфизмов из в комплексных числах единичной величины , а именно:

При векторная группа, т.е. и , то символ определяется как .

Преобразование Фурье. Преобразование Фурье функции есть функция определяется как . Преобразование Фурье измеряет корреляцию с символом в </math>H</math>.

Энергия коэффициента Фурье определяется как квадрат его стандартна , а полная энергия определяется как . Идентичность замкнутости говорит, что .

Изучение тяжелых коэффициентов Фурье. Возьмем и , где является конечной абелевой группой. После обозначения и терминологию из [32], мы говорим, что это - значительная (или -полный) коэффициент Фурье , если JBH Набор - Коэффициенты Фурье значительнo обозначается полным есть . Следующая теорема дает условия для обучения полных коэффициентов функций Фурье, определенных над произвольным конечных групп и будет использоваться в доказательстве основного результата.

Теорема 1.(Значительное преобразование Фурье, [32][теорема 3.3]) Там существует вероятностный алгоритм (SFT), что на входе установлен порог и дает доступ к запросу функции возвращает все Коэффициенты Фурье полные за время с вероятностью[прим. 2] по крайней мере, 2/3.

Псевдослучайность ранцевой функций

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


Теорема 2 (Основная). Пусть является распределением по для некоторых и конечная абелева группа. Если является односторонним и является псевдослучайной для всех то является псевдослучайной.

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

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

.

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

Доказательство теоремы 2 делится на два этапа. На первом этапе (лемма 5) показывает, что определенная (нетривиальная) предиктором подразумевает нетривиальный инвертор для . Этот шаг использует анализ Фурье и справедливо для любой семейной функций (и не только для ) с домен . На втором этапе (предложение 2), мы докажем, что если существует различающая для , но не различающая для для малых , то существует предсказатель для / Этот шаг является специфическим для семейного ранца и зависит как от основной группы и распределения . два шага в сочетании Теорема выход 2. Разделы 3.1 и 3.2 посвящены кажду этапу сокращения.

От предсказуемости до обратимости

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

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

Доказательство (Эскиз). Мы используем анализ Фурье и алгоритма из теоремы 1. Пусть будет - предиктором , который работает за время . Грубо говоря, инвертор на входе для некоторых , имитирует выполнение для того, чтобы найти . Для любого запроса выдается , вызывает на соответствующий вход и отправляет обратно результат . Получается, что, если предиктор есть - смещение в течение некоторого , достаточно большое, а затем имитирует для (детерминированную) функцию , который сильно коррелирует с характером , то есть, функции предоставляют доступ к (через ) таковой, что "достаточно тяжелый"[прим. 3], и поэтому будет включать в список, который это возвращает.

От различимости до предсказуемости

Теперь продолжаем доказывать, что при определенных условиях, различающая для с заметным преимуществом отличительного подразумевает предсказатель для с заметным уклоном. На высоком уровне, предсказатель работает следующим образом: на входе модуля Функция и , она сначала делает предположение для внутреннего продукта ; это тогда использует то предположение, чтобы изменить случай ранца , и, наконец, вызывает различающая на модифицированной инстанции . В заключение, выход используется для того, чтобы определить, было ли правильным или нет первоначальная догадка. Тот же метод был использован Impagliazzo и Naor в [21]. Тем не менее, в условиях рассматриваемой в [21] подмножества-суммы в течении циклической группы простого порядка [прим. 4] - снижение довольно просто: если догадка для верна, то модифицированный экземпляр ранца , распределяется в соответствии с , в то время как, если догадка неверна, распределение является (статистически близко к) равномернымю Таким образом, различающая с заметным преимуществом предполагает почти немедленно 2-предикатора с заметным уклоном.

При рассмотрении общих (не обязательно) циклически абелевых групп с возможным композитным ордером и распределением с , нескольких технических трудностей. В отличие от [21], если догадка для такова, то распределение может быть статистически далеко не однородным. На самом деле, могут быть распределены в соответствии с для любого делителя группового показателя . В зависимости от порядка и структуры основного группы, и распределений выходных в различающей на различных вспомогательных распределениях , технические детали сокращения существенно отличаются. В разминке мы сначала сформулируем слабую форму нашей основной теоремы.

Утверждение 1. Если является - различимый от случайного для некоторых примечательных , но является псевдослучайной для всех , то есть - ограниченная полиномиально , так что является - предсказуемый. Даже если утверждение 1 уже дает поиск сокращенного решения некоторых интересных семейств , это не достаточно сильно, чтобы установить теорему 2 в полной общности. Это достигается в утверждении 2. Теорема 2, то непосредственно следует, если сочетать утверждение 2 и Лемму 5.

Утверждение 2. Если является -различимый от случайного для некоторых примечательных , но является псевдослучайной для всех , то существует полиномиальная ограниченность и полином[прим. 5] такой, что есть - предсказуемый.

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

По предположению, существует различающая и полином , так что и . Если , то доказательство непосредственно вытекает из утверждения 1. Иначе, существует с (заметим, что, так как оба и полиномиально ограничена в , так ) и полином такой, что . Пусть наименьший делитель , такие что [прим. 6] (в частности, это означает, что для всех ). С и , она должна быть такая, что . Рассмотрим теперь предсказатель , показанный в алгоритме 1 ( пытается угадать внутренний продукт ).

input: //

output: guess

  1. Pick ;
  2. Pick ;
  3. ;
  4. Run on input ;
  5. if returns 1 then
  6. guess ;
  7. else
  8. guess ;
  9. end
  10. return guess
Алгоритм 1: Предсказатель для сильного сокращения (предложение 2)

Это может быть проверено, что если предположение для (строка 1) является правильным, то распределение вход (строка 4) в точности . В противном случае распределение вход является для некоторого с . Остается только вычислить смещение . Во-первых, что это

(4)

Обуславливая на выходе и потом делаем некоторые расчеты, мы получим который означает это Используя это и тот факт, что мы получаем, что (5)

Далее, мы связали . Определяем и пусть[прим. 7] . Явно . Так

где в последнем неравенстве мы использовали тот факт, что для всех делителей из , Заменяем обратно в (5), мы, наконец, получим

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

Последствия и приложения

Теорема 2 дает четкие критерии для проверки, если семейный ранец является псевдослучайным. Для группы и входной распределительной , нужно только, чтобы проверить, является ли свернутой семей псевдослучайной. Как выясняется, для многих выборочных , свернутых ранцевых функции сжимает свой вклад и карту для распределения, статистически близка к равномерной над . Более конкретно, , и является псевдослучайных в сильном статистическом смысле. Ниже мы приводим некоторые типичные примеры упором на те, которые наиболее интересны в приложениях.

Конкретные группы и входные распределения

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

Следствие 1. Пусть наименьшее простое фактор и таково, что . Если является односторонним, то это также псевдослучайное.

Следствие 1 уже очень сильное. Например, в стандартной задаче подмножество сумма у нас есть для любого простого . Таким образом, следствие 1 значительно обобщает результаты из [21] и [34]. Более конкретно, оно утверждает, что любая ранец семьи с является псевдослучайной, если она является односторонней, для любой абелевой группы . Другие интересные группы Следствие 1 непосредственно применимы к включают группы с простого порядка, векторных групп для простого и вообще группы , где простое число, .

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

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

Лемма 6. Если есть одностороннее, и . для всех с , то также есть псевдослучайное.

Ниже мы представляем 2 природных семейства распределений, которые имеют небольшую вероятность столкновения, когда он "свернут" над небольшим . Поиск сокращенного решения за принятием решений, соответствующих семейных ранцев непосредственно следуют из леммы 6 и оценок на вероятность столкновения двух распределений Леммы 7 и 8 предоставляют формальные заявления.

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

Лемма 7. Если есть одностороннее и равномерно сложены относительно для ), то это тоже псевдослучайное.

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

Лемма 8. Пусть параметр Гаусса с [прим. 8] . Если является односторонним, то он также псевдослучайный при условии, что либо простое или составное и существует функция такая, что все делители из лежат вне интервала .

Применение к изучению ошибок

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

.

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

Мы заинтересованы в сокращении из LWE, чтобы DLWE, которые сохраняют все параметры , включая число образцов . Сохраняющие образец сокращения более естественно описаны, используя матричное примечание для проблемы LWE. Учитывая коллекцию образцов LWE , мы можем объединить их в матрице , имеющий векторы как строки, а вектор-столбец с записями равняется . То есть, , где . В этих обозначениях, мы хотим доказать, что любой алгоритм, который отличает от . Может быть использован для восстановления секретнго . Заметьте, что, как только секретное была восстановлено, можно также возвратить ошибочный вектор . Так, мы можем эквивалентно определить LWE как проблему восстановления и . Это - точно проблема инвертирования следующей семейной функции.

Определение 2. Пусть и как определено выше. LWE есть семейная функция , где , и есть множество функций , проиндексированных и определяется как .

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

Лемма 9. Для любых[прим. 9] и , существует многочлен сокращения времени от проблемы обращения с вероятностью , к проблеме обращения с вероятностью .

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

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

Лемма 10. Для любого и , есть полиномиальное сокращение времени от проблемы разграничения от униформы с преимуществом к проблеме различения from uniform with advantage .

Доказательство (Набросок доказательства). Снижение изменяет шаги, предпринятые для преобразования LWE в рюкзаке. Начнем с пары . Как и прежде, мы можем предположить, что столбцы генерируют . Далее, используя линейную алгебру, мы вычисляем матрицу . Столбцы, которой порождают множество векторов такое, что . Как и прежде, мы можем выбирать правой частью умножая ее на случайую унимодулярную матрицу получим . Мы также наносим на карту к , где и является случайным решением уравнения . Это может быть проверено, что это преобразование отображает распределение ранцa к распределению LWE (с равномерно случайным ), когда и выбраны наугад, подвергающиеся ограничению, что они неисключительны. Преобразование также отображает равномерное распределение на (статистически близко к) равномерном распределении.

ИСО: От поискa до решения

Образец сохраняющих поиска сокращенного решения принятия решений для изучения ошибок сразу получается объединения сокращений из леммы 9 и леммы 10 с результатами раздела 3 на . Как и в случае ранца, сокращения не держатся безоговорочно; скорее, они справедливы для конкретных, но очень широких модулей и ошибок распределения . Ниже мы приводим общее заявление для поиска сокращенного решения принятия параметризованных и . После предоставления заявления мы обеспечиваем определенные экземпляры ошибок и модуля для которого держится заявление. Повсюду, мы принимаем это .

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

Следующие "назначения" обеспечивают примеры и , это делает вышеупомянутое заявление верным.

Первоначальный для постоянной и . Поиск сокращенного решения соответствующей ограниченной проблемы ранца следует непосредственно от Cледствия 1. Установка и как указано выше, является типичным для конкретизации криптографических приложений, основанных на LWE.
для начала , и для "достаточно узкого" стандартного отклонения (более конкретно, необходимо, чтобы ) Опять же, поиск сокращенного решения ограниченной проблемы ранца происходит от Cледствия 1. Заметим, что этот случай дает пример, сохраняющих версию поиска для уменьшения решения, доказанная в [11].
, с для некоторых . Псевдослучайность экземпляра ранца непосредственно вытекает из Леммы 7. Поиск сокращенного решения для изучения ошибок с таким шумовым распределением, кажется, новый; нет таких (даже "не типовое сохранение") ранее не появился в литературе.

Открытые проблемы

Наша работа оставляет много интересных открытых вопросов. Для начала, образец с сохранением поиска сокращенного решения для изучения ошибок с ограничением шума, считается в этом работа, кажется, не распространяется на неограниченной власти шума, то есть когда каждый коэффициент ошибки вектора LWE взята из набора с суперполиномиальным размера. Отметим, что такой поиск сокращенного решения известны [28], но не попробовав сохранение. Эти сокращения полагаются в большой степени на китайское напоминание теоремы обращения (CRT): используя совершенную [прим. 10] различающую, они сначала изучают секретный модуль с подавляющей вероятностью успеха для каждого полиномиального ограниченного главного фактора модуля ; они затем используют CRT, чтобы восстановить всю тайну. В образце сохранения сокращений, где лишь несовершенной различающей может быть предоставлена по имеющеимся количеству образцов, изучив секретный модуль может быть выполнено в намного более свободном, расшифровывающем смысле списка: секретный модуль включен в соответствующие списки , но среди многих других возможных элементов. И единственный способ проверить, какой из элементов списка соответствует тайне модуля , кажется, формируя сначала всю тайну, используя CRT и затем подтверждаем, что результат - тайна LWE. Таким образом нужно решить супермногочленным образом много случаев CRT прежде, чем возвратить правильное значение тайны. Было бы хорошо расширить расшифровывающий список подходов, чтобы работать даже в этом случае.

В качестве дополнительной мотивации, отметим, что наши образцы продления сохранении сокращения в обстановке неограниченной ошибки, скорее всего, будет иметь последствия для поиска на решение эквивалентности недавно представила кольцо LWE (R-LWE) проблемы [35]. R-LWE является алгебраической вариант LWE, что приводит к намного более эффективными, чем стандартные конструкции LWE то же время наслаждаться сильные гарантии безопасности. Многое, как LWE с неограниченной шума, существующего в этой категории сокращений решения [35] разложить секрет (который является элементом из кольца R) по модулю ци, где Ци простой идеал факторов.

Наша работа также подчеркивает важность понимания твердости LWE при различных распределениях шума. Текущие доказательства твердости для поиска LWE [1] на основе наихудших проблем решетки полагаются на шум следующим распределением Гаусса. Могут ли результаты твердости решетки, основанные на поиске LWE быть продлены до распределения шума кроме Гауссовской? Можем ли мы показать подобную решетку на основе результатов твердости, если шум равномерно распределен по случайному модулю ? Последнем случай очень привлекателен с практической точки зрения, так как арифметика по модулю 2 и отбора проб из равномерных распределений могут быть реализованы очень эффективно.

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

  1. Engineering University of California, San Diego, E-mail: daniele@cs.ucsd.edu
  2. Engineering University of California, San Diego, E-mail: pmol@cs.ucsd.edu

Примечание

  1. Из-за собственной сводимости свойств задачи LWE, здесь "высоким" может быть истолковано в различных формах, начиная от "незначительного" до "очень близкго к 1".
  2. Вероятность успеха берется по внутренней случайности алгоритма только, и может быть усиленa с помощью стандартных методов повторения. Тем не менее, это не требуется в нашем контексте, так для простоты мы фиксируем вероятность успеха до 2/3.
  3. В контексте полиномиальных сокращений время "достаточно высокое" и "достаточно тяжелое" следует интерпретировать так заметно в параметре безопасности.
  4. [18] также рассматривает циклические группы с питания от 2-порядка, но это делает их анализ лишь немного сложнее.
  5. Мы только заботимся о преимущественном прогнозировании быть заметным и не стремиться оптимизировать его как функцию отличительного преимущества. Мы просто упоминаем, что вероятность успеха предиктора является .
  6. такой всегда существует. Действительно сама удовлетворяет этому условию и является делителем.
  7. Это обобщенная Функция Эйлера.
  8. В типичных экземплярах, для некоторой постоянной .
  9. Необходимое условие есть стандартное предположение в контексте LWE,где, как правило, .
  10. Под совершенным, здесь мы имеем в виду различающую с преимуществом почти 1. Получение идеальной различающей из несовершенного (только одна с незначительным преимуществом) является главной причиной увеличения чисел в образце, которые потребляет сокращение.

Литература

  1. 1,00 1,01 1,02 1,03 1,04 1,05 1,06 1,07 1,08 1,09 1,10 Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of ACM, 56(6):34, September 2009. Preliminary version in STOC 2005.
  2. Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa. Multi-bit Cryptosystems Based on Lattice Problems. In Public Key Cryptography, pages 315-329, 2007.
  3. 3,0 3,1 Chris Peikert, Vinod Vaikuntanathan, and Brent Waters. A Framework for Efficient and Composable Oblivious Transfer. In CRYPTO, pages 554-571, Berlin, Heidelberg, 2008. Springer-Verlag.
  4. Chris Peikert and BrentWaters. Lossy Trapdoor Functions and Their Applications. In STOC, pages 187-196, New York, NY, USA, 2008. ACM.
  5. 5,0 5,1 5,2 Chris Peikert. Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem. In STOC, pages 333-342, New York, NY, USA, 2009. ACM.
  6. 6,0 6,1 6,2 Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for Hard Lattices and New Cryptographic Constructions. In STOC, pages 197-206, New York, NY, USA, 2008. ACM.
  7. 7,0 7,1 David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. Bonsai Trees, or How to Delegate a Lattice Basis. In EUROCRYPT, pages 523-552, 2010.
  8. Shweta Agrawal, Dan Boneh, and Xavier Boyen. Efficient Lattice (H)IBE in the Standard Model. In EUROCRYPT, pages 553-572, 2010.
  9. Shweta Agrawal, Dan Boneh, and Xavier Boyen. Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE. In CRYPTO, pages 98-115,2010.
  10. Adi Akavia, Shafi Goldwasser, and Vinod Vaikuntanathan. Simultaneous Hardcore Bits and Cryptography against Memory Attacks. In TCC, pages 474-495, 2009.
  11. 11,0 11,1 11,2 11,3 11,4 Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. In CRYPTO, pages 595-618, 2009.
  12. Yevgeniy Dodis, Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan. Public-Key Encryption Schemes with Auxiliary Inputs. In TCC, pages 361-381, 2010.
  13. Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan. Robustness of the Learning with Errors Assumption. In ICS, 2010.
  14. Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. A Simple BGN-Type Cryptosystem from LWE. In EUROCRYPT, pages 506-522, 2010.
  15. Vadim Lyubashevsky and Daniele Micciancio. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In CRYPTO, pages 577-594, 2009.
  16. 16,0 16,1 Daniele Micciancio and Oded Regev. Lattice-Based Cryptography. In Post Quantum Cryptography, pages 147-191. Springer Publishing Company, 2009.
  17. 17,0 17,1 Richard Lindner and Chris Peikert. Better Key Sizes (and Attacks) for LWE-Based Encryption. In CT-RSA, pages 319-339, 2011.
  18. Markus Ruckert and Michael Schneider. Estimating the Security of Lattice-based Cryptosystems. Technical Report 2010/137, IACR ePrint archive, 2010.
  19. 19,0 19,1 Sanjeev Arora and Rong Ge. New algorithms for learning in presence of errors. In ICALP, 2011. Available at http://www.eccc.uni-trier.de/report/2010/066/.
  20. Oded Regev. The Learning with Errors Problem (Invited Survey). In IEEE Conference on Computational Complexity, pages 191-204, 2010.
  21. 21,0 21,1 21,2 21,3 21,4 21,5 21,6 21,7 21,8 Russell Impagliazzo and Moni Naor. Efficient Cryptographic Schemes Provably asSecure as Subset Sum. J. Cryptology, 9(4):199-216, 1996.
  22. Damien Stehle, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. Efficient Public Key Encryption Based on Ideal Lattices. In ASIACRYPT, pages 617-635, 2009.
  23. Daniele Micciancio. Duality in Lattice Based Cryptography. In Public Key Cryptography, 2010. Invited Talk.
  24. Avrim Blum, Merrick L. Furst, Michael J. Kearns, and Richard J. Lipton. Cryptographic Primitives Based on Hard Learning Problems. In CRYPTO, pages 278-291, 1993.
  25. 25,0 25,1 25,2 Jonathan Katz, Ji Sun Shin, and Adam Smith. Parallel and Concurrent Security of the HB and HB+ Protocols. J. Cryptology, 23(3):402-421, 2010.
  26. R. Impagliazzo and D. Zuckerman. How to Recycle Random Bits. In FOCS, pages 248-253, Washington, DC, USA, 1989. IEEE Computer Society.
  27. 27,0 27,1 Eyal Kushilevitz and Yishay Mansour. Learning Decision Trees Using the Fourier Sprectrum. In STOC, pages 455-464, 1991.
  28. Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, YishayMansour, and Steven Rudich. Weakly Learning DNF and Characterizing Statistical Query Learning using Fourier Analysis. In STOC, pages 253-262, 1994.
  29. Elchanan Mossel, Ryan O'Donnell, and Rocco A. Servedio. Learning Juntas. In STOC, pages 206-212, 2003.
  30. Oded Goldreich and Leonid A. Levin. A Hard-Core Predicate for All One-Way Functions. In STOC, pages 25-32, 1989.
  31. Adi Akavia, Shafi Goldwasser, and Shmuel Safra. Proving Hard-Core Predicates Using List Decoding. In FOCS, pages 146-157, 2003.
  32. 32,0 32,1 32,2 Adi Akavia. Learning Noisy Characters, Multiplication Codes and Hardcore Predicates. PhD thesis, MIT, February 2008.
  33. Daniel Stefankovic. Fourier Transform in Computer Science. Master's thesis, University of Chicago, October 2000.
  34. Jean-Bernard Fischer and Jacques Stern. An efficient pseudo-random generator provably as secure as syndrome decoding. In EUROCRYPT, pages 245-255, 1996.
  35. 35,0 35,1 Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On Ideal Lattices and Learning with Errors over Rings. In EUROCRYPT, pages 1-23, 2010.