Обучение с ошибками - Learning with errors

Обучение с ошибками ( LWE ) - это вычислительная проблема вывода линейной -арной функции над конечным кольцом из заданных выборок, некоторые из которых могут быть ошибочными. Предполагается, что проблему LWE трудно решить, и поэтому она может быть полезна в криптографии . ${\ displaystyle n}$${\ displaystyle f}$${\ Displaystyle у_ {я} = е (\ mathbf {х} _ {я})}$

Точнее, проблема LWE определяется следующим образом. Позвольте обозначить кольцо целых чисел по модулю и обозначить множество - векторов над . Существует некоторая неизвестная линейная функция , и входом в задачу LWE является выборка пар , где и , так что с большой вероятностью . Кроме того, отклонение от равенства соответствует некоторой известной модели шума. Проблема требует отыскания функции или ее близкого приближения с большой вероятностью. ${\ displaystyle \ mathbb {Z} _ {q}}$ ${\ displaystyle q}$${\ displaystyle \ mathbb {Z} _ {q} ^ {n}}$${\ displaystyle n}$${\ displaystyle \ mathbb {Z} _ {q}}$${\ displaystyle f: \ mathbb {Z} _ {q} ^ {n} \ rightarrow \ mathbb {Z} _ {q}}$${\ displaystyle (\ mathbf {x}, y)}$${\ displaystyle \ mathbf {x} \ in \ mathbb {Z} _ {q} ^ {n}}$${\ displaystyle y \ in \ mathbb {Z} _ {q}}$${\ Displaystyle у = е (\ mathbf {х})}$${\ displaystyle f}$

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

Определение

Обозначим в аддитивной группе по модулю чисел один . Позвольте быть фиксированным вектором. Позвольте быть фиксированным распределением вероятностей над . Обозначим распределение на, полученное следующим образом. ${\ Displaystyle \ mathbb {T} = \ mathbb {R} / \ mathbb {Z}}$${\ displaystyle \ mathbf {s} \ in \ mathbb {Z} _ {q} ^ {n}}$${\ displaystyle \ phi}$${\ Displaystyle \ mathbb {T}}$${\ Displaystyle А _ {\ mathbf {s}, \ phi}}$${\ Displaystyle \ mathbb {Z} _ {д} ^ {п} \ раз \ mathbb {T}}$

1. Выберите вектор из равномерного распределения , ${\ displaystyle \ mathbf {a} \ in \ mathbb {Z} _ {q} ^ {n}}$${\ displaystyle \ mathbf {a} \ in \ mathbb {Z} _ {q} ^ {n}}$
2. Выберите номер из раздачи , ${\ Displaystyle е \ в \ mathbb {T}}$${\ displaystyle \ phi}$
3. Вычислите , где - стандартный внутренний продукт в , деление выполняется в области вещественных чисел (или, более формально, это «деление на » является обозначением для отображения гомоморфизма групп в ), и последнее добавление находится в . ${\ displaystyle t = \ langle \ mathbf {a}, \ mathbf {s} \ rangle / q + e}$${\ displaystyle \ textstyle \ langle \ mathbf {a}, \ mathbf {s} \ rangle = \ sum _ {i = 1} ^ {n} a_ {i} s_ {i}}$${\ displaystyle \ mathbb {Z} _ {q} ^ {n}}$${\ displaystyle q}$${\ Displaystyle \ mathbb {Z} _ {q} \ longrightarrow \ mathbb {T}}$${\ displaystyle 1 \ in \ mathbb {Z} _ {q}}$${\ Displaystyle 1 / д + \ mathbb {Z} \ in \ mathbb {T}}$${\ Displaystyle \ mathbb {T}}$
4. Выведите пару . ${\ Displaystyle (\ mathbf {а}, т)}$

Проблема обучения с ошибками состоит в том , чтобы найти , имея доступ к полиномиально большому количеству выборок из . ${\ displaystyle \ mathrm {LWE} _ {q, \ phi}}$${\ displaystyle \ mathbf {s} \ in \ mathbb {Z} _ {q} ^ {n}}$${\ Displaystyle А _ {\ mathbf {s}, \ phi}}$

Для каждого обозначим одномерным гауссианом с нулевым средним и дисперсией , то есть функция плотности - это где , и пусть будет распределением по, полученным с учетом модуля один. Версия LWE, рассматриваемая в большинстве результатов, будет ${\ displaystyle \ alpha> 0}$${\ displaystyle D _ {\ alpha}}$${\ Displaystyle \ альфа ^ {2} / (2 \ пи)}$${\ Displaystyle D _ {\ альфа} (х) = \ ро _ {\ альфа} (х) / \ альфа}$${\ Displaystyle \ ро _ {\ альфа} (х) = е ^ {- \ пи (| х | / \ альфа) ^ {2}}}$${\ displaystyle \ Psi _ {\ alpha}}$${\ Displaystyle \ mathbb {T}}$${\ displaystyle D _ {\ alpha}}$${\ displaystyle \ mathrm {LWE} _ {q, \ Psi _ {\ alpha}}}$

Версия решения

LWE проблема , описанная выше , является поиск версия этой проблемы. В версии решения ( DLWE ) цель состоит в том, чтобы различать зашумленные внутренние продукты и равномерно случайные выборки из (практически, некоторой дискретной версии этого). Регев показал, что варианты решения и поиска эквивалентны, когда есть простое число, ограниченное некоторым многочленом от . ${\ Displaystyle \ mathbb {Z} _ {д} ^ {п} \ раз \ mathbb {T}}$${\ displaystyle q}$${\ displaystyle n}$

Решающее решение, предполагающее поиск

Интуитивно понятно, что если у нас есть процедура для задачи поиска, вариант решения может быть легко решен: просто передайте входные образцы для задачи решения решающей программе для задачи поиска. Обозначим данные образцы значком . Если решатель возвращает кандидата , для всех , рассчитайте . Если выборки взяты из распределения LWE, то результаты этого расчета будут распределены согласно , но если выборки являются равномерно случайными, эти количества также будут распределены равномерно. ${\ displaystyle \ {(\ mathbf {a} _ {i}, \ mathbf {b} _ {i}) \} \ subset \ mathbb {Z} _ {q} ^ {n} \ times \ mathbb {T} }$${\ displaystyle \ mathbf {s}}$${\ displaystyle i}$${\ displaystyle \ {\ langle \ mathbf {a} _ {i}, \ mathbf {s} \ rangle - \ mathbf {b} _ {i} \}}$${\ displaystyle \ chi}$

Решение поиска, предполагающее решение

Для другого направления, при наличии решателя для проблемы решения, поисковая версия может быть решена следующим образом: Восстановление по одной координате за раз. Чтобы получить первую координату, сделайте предположение и выполните следующие действия. Выберите число равномерно наугад. Преобразуйте данные образцы следующим образом. Рассчитайте . Отправьте преобразованные образцы в решающую программу. ${\ displaystyle \ mathbf {s}}$${\ displaystyle \ mathbf {s} _ {1}}$${\ displaystyle k \ in Z_ {q}}$${\ displaystyle r \ in \ mathbb {Z} _ {q}}$${\ displaystyle \ {(\ mathbf {a} _ {i}, \ mathbf {b} _ {i}) \} \ subset \ mathbb {Z} _ {q} ^ {n} \ times \ mathbb {T} }$${\ displaystyle \ {(\ mathbf {a} _ {i} + (r, 0, \ ldots, 0), \ mathbf {b} _ {i} + (rk) / q) \}}$

Если предположение было правильным, преобразование переводит распределение в себя, а в противном случае, поскольку оно простое, оно переводит его в равномерное распределение. Таким образом, учитывая полиномиальный решатель для проблемы решения, которая ошибается с очень малой вероятностью, поскольку ограничена некоторым полиномом от , требуется только полиномиальное время, чтобы угадать все возможные значения для и использовать решатель, чтобы увидеть, какое из них правильное. ${\ displaystyle k}$${\ Displaystyle А _ {\ mathbf {s}, \ chi}}$${\ displaystyle q}$${\ displaystyle q}$${\ displaystyle n}$${\ displaystyle k}$

После получения проделываем аналогичную процедуру для друг друга координаты . А именно, мы преобразуем наши образцы таким же образом и преобразуем наши образцы, вычисляя , где находится в координате. ${\ displaystyle \ mathbf {s} _ {1}}$${\ displaystyle \ mathbf {s} _ {j}}$${\ displaystyle \ mathbf {b} _ {i}}$${\ Displaystyle \ mathbf {а} _ {я}}$${\ displaystyle \ mathbf {a} _ {i} + (0, \ ldots, r, \ ldots, 0)}$${\ displaystyle r}$${\ displaystyle j ^ {\ text {th}}}$

Пайкерт показал, что это сокращение с небольшой модификацией работает для любого, который является произведением различных малых (полиномиальных от ) простых чисел. Основная идея состоит в том , чтобы для каждого из них угадать и проверить, конгруэнтно ли оно , а затем использовать китайскую теорему об остатках для восстановления . ${\ displaystyle q}$${\ displaystyle n}$${\ displaystyle q = q_ {1} q_ {2} \ cdots q_ {t}}$${\ displaystyle q _ {\ ell}}$${\ displaystyle \ mathbf {s} _ {j}}$${\ displaystyle 0 \ mod q _ {\ ell}}$${\ displaystyle \ mathbf {s} _ {j}}$

Средняя твердость корпуса

Регев показал случайную собственную восстанавливаемость из LWE и DLWE задач для произвольных и . Учитывая образцы из , легко увидеть, что это образцы из . ${\ displaystyle q}$${\ displaystyle \ chi}$${\ Displaystyle \ {(\ mathbf {а} _ {я}, \ mathbf {б} _ {я}) \}}$${\ Displaystyle А _ {\ mathbf {s}, \ chi}}$${\ displaystyle \ {(\ mathbf {a} _ {i}, \ mathbf {b} _ {i} + \ langle \ mathbf {a} _ {i}, \ mathbf {t} \ rangle) / q \} }$${\ Displaystyle А _ {\ mathbf {s} + \ mathbf {t}, \ chi}}$

Итак, предположим , что существует некоторое множество такое , что и для распределений с , DLWE было легко. ${\ displaystyle {\ mathcal {S}} \ subset \ mathbb {Z} _ {q} ^ {n}}$${\ displaystyle | {\ mathcal {S}} | / | \ mathbb {Z} _ {q} ^ {n} | = 1 / \ OperatorName {poly} (n)}$${\ Displaystyle А _ {\ mathbf {s} ', \ chi}}$${\ Displaystyle \ mathbf {s} '\ leftarrow {\ mathcal {S}}}$

Тогда был бы какой-нибудь отличитель , который по выборкам мог бы сказать, являются ли они равномерно случайными или от них . Если нам нужно отличить равномерно случайные выборки из , где выбирается равномерно случайным образом из , мы могли бы просто попробовать разные значения, выбранные равномерно случайным образом из , вычислить и передать эти выборки в . Поскольку включает большую фракцию , с высокой вероятностью, если мы выберем полиномиальное число значений , мы найдем один такой , что и будет успешно различать образцы. ${\ displaystyle {\ mathcal {A}}}$${\ Displaystyle \ {(\ mathbf {а} _ {я}, \ mathbf {б} _ {я}) \}}$${\ Displaystyle А _ {\ mathbf {s} ', \ chi}}$${\ Displaystyle А _ {\ mathbf {s}, \ chi}}$${\ displaystyle \ mathbf {s}}$${\ displaystyle \ mathbb {Z} _ {q} ^ {n}}$${\ displaystyle \ mathbf {t}}$${\ displaystyle \ mathbb {Z} _ {q} ^ {n}}$${\ displaystyle \ {(\ mathbf {a} _ {i}, \ mathbf {b} _ {i} + \ langle \ mathbf {a} _ {i}, \ mathbf {t} \ rangle) / q \} }$${\ displaystyle {\ mathcal {A}}}$${\ Displaystyle {\ mathcal {S}}}$${\ displaystyle \ mathbb {Z} _ {q} ^ {n}}$${\ displaystyle \ mathbf {t}}$${\ displaystyle \ mathbf {s} + \ mathbf {t} \ in {\ mathcal {S}}}$${\ displaystyle {\ mathcal {A}}}$

Таким образом, таких не может быть, а это означает, что LWE и DLWE (с точностью до полиномиального множителя) столь же сложны в среднем случае, как и в худшем случае. ${\ Displaystyle {\ mathcal {S}}}$

Результаты твердости

Результат Регева

Для n- мерной решетки пусть параметр сглаживания обозначает наименьший такой, что где является двойным к и расширяется до множеств путем суммирования значений функций на каждом элементе в множестве. Обозначим через дискретное гауссово распределение по ширине для решетки и вещественного . Вероятность каждого пропорциональна . ${\ displaystyle L}$ ${\ displaystyle \ eta _ {\ varepsilon} (L)}$${\ displaystyle s}$${\ Displaystyle \ rho _ {1 / s} (L ^ {*} \ setminus \ {\ mathbf {0} \}) \ leq \ varepsilon}$${\ Displaystyle L ^ {*}}$${\ displaystyle L}$${\ Displaystyle \ ро _ {\ альфа} (х) = е ^ {- \ пи (| х | / \ альфа) ^ {2}}}$${\ displaystyle D_ {L, r}}$${\ displaystyle L}$${\ displaystyle r}$${\ displaystyle L}$${\ displaystyle r> 0}$${\ displaystyle x \ in L}$${\ displaystyle \ rho _ {r} (х)}$

Задача дискретной гауссовой выборки (DGS) определяется следующим образом: экземпляр задается -мерной решеткой и числом . Цель состоит в том, чтобы вывести образец из . Регев показывает, что для любой функции существует сокращение от до . ${\ displaystyle DGS _ {\ phi}}$${\ displaystyle n}$${\ displaystyle L}$${\ Displaystyle г \ geq \ фи (L)}$${\ displaystyle D_ {L, r}}$${\ displaystyle \ operatorname {GapSVP} _ {100 {\ sqrt {n}} \ gamma (n)}}$${\ displaystyle DGS _ {{\ sqrt {n}} \ gamma (n) / \ lambda (L ^ {*})}}$${\ Displaystyle \ гамма (п)}$

Затем Регев показывает, что существует эффективный квантовый алгоритм для данного доступа к оракулу для целых и таких, что . Это подразумевает твердость для LWE. Хотя доказательство этого утверждения работает для любого , для создания криптосистемы он должен быть полиномиальным от . ${\ Displaystyle DGS _ {{\ sqrt {2n}} \ eta _ {\ varepsilon} (L) / \ alpha}}$${\ displaystyle \ mathrm {LWE} _ {q, \ Psi _ {\ alpha}}}$${\ displaystyle q}$${\ Displaystyle \ альфа \ в (0,1)}$${\ displaystyle \ alpha q> 2 {\ sqrt {n}}}$${\ displaystyle q}$${\ displaystyle q}$${\ displaystyle n}$

Результат Пайкерта

Peikert доказывает , что существует вероятностное полиномиальное сокращение времени от задачи в худшем случае к решению с использованием образцов для параметров , , и . ${\ displaystyle \ operatorname {GapSVP} _ {\ zeta, \ gamma}}$${\ displaystyle \ mathrm {LWE} _ {q, \ Psi _ {\ alpha}}}$${\ Displaystyle \ OperatorName {поли} (п)}$${\ Displaystyle \ альфа \ в (0,1)}$${\ Displaystyle \ гамма (п) \ geq п / (\ альфа {\ sqrt {\ лог п}})}$${\ Displaystyle \ дзета (п) \ geq \ гамма (п)}$${\ displaystyle q \ geq (\ zeta / {\ sqrt {n}}) \ omega {\ sqrt {\ log n}})}$

Использование в криптографии

Проблема LWE служит универсальной задачей, используемой при построении нескольких криптосистем. В 2005 году Регев показал, что решающая версия LWE жестко предполагает квантовую трудность решеточных задач ( как указано выше) и с ). В 2009 году Пайкерт доказал аналогичный результат, предполагая только классическую трудность родственной задачи . Недостатком результата Пайкерта является то, что он основан на нестандартной версии более простой (по сравнению с SIVP) проблемы GapSVP. ${\ Displaystyle \ mathrm {GapSVP} _ {\ gamma}}$${\ displaystyle \ gamma}$${\ displaystyle \ mathrm {SIVP} _ {t}}$${\ Displaystyle т = О (п / \ альфа)}$${\ Displaystyle \ mathrm {GapSVP} _ {\ zeta, \ gamma}}$

Криптосистема с открытым ключом

Регев предложил криптосистему с открытым ключом, основанную на сложности проблемы LWE . Криптосистема, а также доказательства безопасности и корректности полностью классические. Система характеризуется вероятностным распределением на . Установка параметров, используемых в доказательствах правильности и безопасности, является ${\ displaystyle m, q}$${\ displaystyle \ chi}$${\ Displaystyle \ mathbb {T}}$

• ${\ displaystyle q \ geq 2}$ , обычно простое число от до . ${\ Displaystyle п ^ {2}}$${\ displaystyle 2n ^ {2}}$
• ${\ Displaystyle м = (1+ \ varepsilon) (п + 1) \ журнал q}$ для произвольной постоянной ${\ Displaystyle \ varepsilon}$
• ${\ Displaystyle \ чи = \ пси _ {\ альфа (п)}}$ для , где - распределение вероятностей, полученное путем выборки нормальной переменной со средним и стандартным вариациями и уменьшения результата по модулю . ${\ Displaystyle \ альфа (п) \ в о (1 / {\ sqrt {n}} \ журнал п)}$${\ displaystyle \ Psi _ {\ beta}}$${\ displaystyle 0}$${\ displaystyle {\ frac {\ beta} {\ sqrt {2 \ pi}}}}$${\ displaystyle 1}$

Затем криптосистема определяется следующим образом:

• Закрытый ключ : закрытый ключ выбирается случайным образом. ${\ displaystyle \ mathbf {s} \ in \ mathbb {Z} _ {q} ^ {n}}$
• Открытый ключ : выбирайте векторы равномерно и независимо. Смещения ошибок выбираются независимо в соответствии с . Открытый ключ состоит из ${\ displaystyle m}$${\ displaystyle \ mathbf {a} _ {1}, \ ldots, \ mathbf {a} _ {m} \ in \ mathbb {Z} _ {q} ^ {n}}$${\ displaystyle e_ {1}, \ ldots, e_ {m} \ in \ mathbb {T}}$${\ displaystyle \ chi}$${\ displaystyle (\ mathbf {a} _ {i}, b_ {i} = \ langle \ mathbf {a} _ {i}, \ mathbf {s} \ rangle / q + e_ {i}) _ {i = 1} ^ {m}}$
• Шифрование : Шифрование бита осуществляется путем выбора случайного подмножества из , а затем определение , как ${\ Displaystyle х \ в \ {0,1 \}}$${\ displaystyle S}$${\ Displaystyle [м]}$${\ displaystyle \ operatorname {Enc} (x)}$

${\ displaystyle \ left (\ sum _ {i \ in S} \ mathbf {a} _ {i}, {\ frac {x} {2}} + \ sum _ {i \ in S} b_ {i} \ верно)}$

• Дешифрирование : дешифрования является , если ближе к чем , и в противном случае. ${\ Displaystyle (\ mathbf {а}, б)}$${\ displaystyle 0}$${\ displaystyle b- \ langle \ mathbf {a}, \ mathbf {s} \ rangle / q}$${\ displaystyle 0}$${\ displaystyle {\ frac {1} {2}}}$${\ displaystyle 1}$

Доказательство правильности следует из выбора параметров и некоторого вероятностного анализа. Доказательство безопасности сводится к версии решения LWE : алгоритм для различения шифров (с указанными выше параметрами) и может использоваться для различения и равномерного распределения по ${\ displaystyle 0}$${\ displaystyle 1}$${\ displaystyle A_ {s, \ chi}}$${\ Displaystyle \ mathbb {Z} _ {д} ^ {п} \ раз \ mathbb {T}}$

CCA-безопасная криптосистема

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

Обмен ключами

Идея использования LWE и Ring LWE для обмена ключами была предложена и подана в Университет Цинциннати в 2011 году Джинтаем Дингом. Идея исходит из ассоциативности умножения матриц, а ошибки используются для обеспечения безопасности. Статья появилась в 2012 году после подачи предварительной заявки на патент в 2012 году.

Безопасность протокола подтверждена твердостью решения проблемы LWE. В 2014 году Пайкерт представил схему передачи ключей, следуя той же базовой идее Динга, где также используется новая идея отправки дополнительного 1-битного сигнала для округления в конструкции Динга. Реализация «новой надежды», выбранная для постквантового эксперимента Google, использует схему Пайкерта с вариациями в распределении ошибок.

Смотрите также

• Постквантовая криптография
• Криптография на основе решеток
• Кольцевое обучение с ошибками обмен ключами
• Задача короткого целочисленного решения (SIS)

Рекомендации