WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

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

Представленная^[1] Одедом Регев в 2005 году LWE оказалась удивительно универсальной основой для криптографических конструкций, в частности, для создания постквантовых криптографических алгоритмов^[1]^[2].

Определение

Зафиксируем параметр $n\geqslant 1$ , модуль $q\geqslant 2$ и распределение вероятности «ошибки» $\chi$ на ${Z}_{q}$ . Пусть $A_{\mathbf {s} ,\chi }$ — распределение вероятности на $\mathbb {Z} _{q}^{n}\times \mathbb {Z} _{q}$ , полученное выбором вектора $\mathbf {a} \in \mathbb {Z} _{q}^{n}$ равномерно случайно, выбором ошибки $\mathbf {e} \in \mathbb {Z} _{q}$ в соответствии с $\chi$ и полученным выражением $(\mathbf {a} ,\langle \mathbf {a} ,\mathbf {s} \rangle +e)$ , где $\textstyle \langle \mathbf {a} ,\mathbf {s} \rangle =\sum _{i=1}^{n}a_{i}s_{i}$ и сложение производится по модулю $q$ .

Говорят^[3], что алгоритм решает задачу $\mathrm {LWE} _{q,\chi }$ , если для любого $\mathbf {s} \in \mathbb {Z} _{q}^{n}$ , имея произвольное полиномиальное число независимых соотношений из $A_{\mathbf {s} ,\chi }$ он с высокой вероятностью выдаст $s$ .

История появления

Возникновение концепции LWE отслеживается в работах Миклоша Айтаи и Синтии Дворк^[4]. Они описали первую криптосистему на открытых ключах, использующую криптографию на решётках, и последующие её улучшения и модификации^[5]. LWE не была в явном виде представлена в этих работах, однако тщательное исследование конструкции Айтаи—Дворк, упрощённой в работе Регева^[6], показывает^[3], что идеи LWE неявно возникают в этой работе.

Стоит отметить, что ранние исследования в этой области^[4]^[6] опирались на недостаточно хорошо изученную задачу нахождения уникального кратчайшего вектора. Долгое время было непонятно, можно ли заменить её более стандартными задачами на решётках. Позднее Крис Пейкерт^[7] и Вадим Любашевский с Даниэле Миччанчо выяснили^[8], что задача нахождения уникального кратчайшего вектора на самом деле является эквивалентом стандартной задачи на решетках GapSVP, что привело к более ясной картине в данной области.

Пример задачи

Рассмотрим типичную задачу LWE^[3]: необходимо восстановить вектор $x\in \mathbb {Z} _{q}^{n}$ , имея последовательность приближенных линейных уравнений по x. Например:

{\begin{cases}14x_{1}+15x_{2}+15x_{3}+2x_{4}=8(mod17)\\13x_{1}+14x_{2}+14x_{3}+6x_{4}=16(mod17)\\\dots \\6x_{1}+7x_{2}+16x_{3}+2x_{4}=3(mod17),\\\end{cases}}

где каждое соотношение верно с некоторой маленькой дополнительной ошибкой, скажем, ± $1$ и наша цель восстановить $x$ (в данном примере $x=(0,13,9,11)$ ). Без ошибки найти $x$ было бы просто: например, за полиномиальное время, используя метод Гаусса. Учёт же ошибки делает задачу значительно более трудной, поскольку с каждой итерацией ошибка возрастает и в конечном итоге достигает неуправляемых значений^[3].

Криптографические приложения

Диапазон криптографических приложений LWE становится в последнее время достаточно широким. Кроме приведенного ниже примера криптосистемы, существуют и более эффективные схемы^[2]^[9]. Более того, использование Ring LWE может сделать систему реально применимой^[10].

Стоит особенно отметить, что LWE может использоваться как основа для создания криптографических схем, предоставляющих полностью гоморфное шифрование. Например, она использовалась в реализации открытой для общественного пользования библиотеки FHEW^[11].

Система на открытых ключах

Рассмотрим простой пример криптосистемы на открытых ключах, предложенной Регевом^[1]. Она опирается на сложность решения задачи LWE. Система описывается следующими числами: $n$ -секретный параметр, $m$ -размерность, $q$ -модуль и распределением вероятности $\chi \in \mathbb {Z} _{q}$ . Для гарантии безопасности и корректности системы следует выбрать следующие параметры:

$q\geq 2$ , простое число между $n^{2}$ и $2n^{2}$
$m=(1+\epsilon )(n+1)\log {q}$ для произвольной константы $\epsilon$
$\alpha (n)=1/{\sqrt {n}}\log ^{2}{n}$

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

Секретный ключ: Секретный ключ это $\mathbf {s} \in \mathbb {Z} _{q}^{n}$ выбранный произвольно.
Открытый ключ: Выберем $m$ векторов $a_{1},\ldots ,a_{m}\in \mathbb {Z} _{q}^{n}$ произвольно и независимо. Выберем допустимые ошибки $e_{1},\ldots ,e_{m}\in \mathbb {Z} _{q}$ независимо в соответствии с распределением $\chi$ . Открытый ключ состоит из $(a_{i},b_{i}=\langle a_{i},\mathbf {s} \rangle /q+e_{i})_{i=1}^{m}$
Шифрование: Шифрование бита $x\in \{0,1\}$ производится так: выбирается случайное подмножество $S$ из $[m]$ и определяется шифр $Enc(x)$ как $(\sum _{i\in S}a_{i},x/2+\sum _{i\in S}b_{i})$
Расшифрование: Расшифровка $(a,b)$ это $0$ в случае если $b-\langle a,\mathbf {s} \rangle /q$ ближе к $0$ , чем ${\frac {1}{2}}$ , и $1$ в противном случае.

В своих работах^[1]^[3] Одед Регев доказал корректность и защищенность данной криптосистемы при соответствующем выборе параметров.

Примечания

1 2 3 4 Oded Regev «On lattices, learning with errors, random linear codes, and cryptography», in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84-93, http://portal.acm.org/citation.cfm?id=1060590.1060603.
1 2 D. Micciancio and O. Regev. Lattice-based cryptography. In D. J.Bernstein and J. Buch-mann, editors,Post-quantum Cryprography. Springer, 2008
1 2 3 4 5 Oded Regev, «The Learning with Errors Problem» http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf
1 2 M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In Proc. 29th Annual ACM Symp. on Theory of Computing (STOC), pages 284—293. 1997
↑ M. Ajtai and C. Dwork. The first and fourth public-key cryptosystems with worst-case/average-case equivalence, 2007. Available from ECCC at http://www.uni-trier.de/eccc/
1 2 O. Regev. New lattice-based cryptographic constructions. Journal of the ACM, 51(6):899-942, 2004. Preliminary version in STOC’03
↑ C. Peikert. Public-key cryptosystems from the worst-case shortest vector problem. In Proc. 41st ACM Symp. on Theory of Computing (STOC), pages 333—342. 2009
↑ V. Lyubashevsky and D. Micciancio. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In CRYPTO, pages 577—594. 2009.
↑ C. Peikert, V. Vaikuntanathan, and B. Waters. A framework for efficient and compos-able oblivious transfer. In CRYPTO, pages 554—571. 2008
↑ V. Lyubashevsky, C. Peikert, and O. Regev. On ideal lattices and learning with errors over rings. In EUROCRYPT. 2010.
↑ Leo Ducas. FHEW: A Fully Homomorphic Encryption library (неопр.). Проверено 31 декабря 2014.

Литература

Post-Quantum Cryptography. — Springer, 2008. — P. 245. — ISBN 978-3540887010.
Peikert, Chris. Lattice Cryptography for the Internet. — Springer International Publishing, 2014-10-01. — P. 197–219. — ISBN 978-3-319-11658-7.
Chen, Yuanmi; Phong Q., Nguyen. BKZ 2.0: Better Lattice Security Estimates. — Springer Berlin Heidelberg, 2011. — P. 1-20.

См. также

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2025
WikiSort.ru - проект по пересортировке и дополнению контента Википедии

[regev05-1] 1 2 3 4 Oded Regev «On lattices, learning with errors, random linear codes, and cryptography», in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84-93, http://portal.acm.org/citation.cfm?id=1060590.1060603.

[MR08-2] 1 2 D. Micciancio and O. Regev. Lattice-based cryptography. In D. J.Bernstein and J. Buch-mann, editors,Post-quantum Cryprography. Springer, 2008

[regev-3] 1 2 3 4 5 Oded Regev, «The Learning with Errors Problem» http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf

[AD97-4] 1 2 M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In Proc. 29th Annual ACM Symp. on Theory of Computing (STOC), pages 284—293. 1997

[AD07-5] M. Ajtai and C. Dwork. The first and fourth public-key cryptosystems with worst-case/average-case equivalence, 2007. Available from ECCC at http://www.uni-trier.de/eccc/

[Reg03-6] 1 2 O. Regev. New lattice-based cryptographic constructions. Journal of the ACM, 51(6):899-942, 2004. Preliminary version in STOC’03

[Pei09a-7] C. Peikert. Public-key cryptosystems from the worst-case shortest vector problem. In Proc. 41st ACM Symp. on Theory of Computing (STOC), pages 333—342. 2009

[LM09-8] V. Lyubashevsky and D. Micciancio. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In CRYPTO, pages 577—594. 2009.

[PVW08-9] C. Peikert, V. Vaikuntanathan, and B. Waters. A framework for efficient and compos-able oblivious transfer. In CRYPTO, pages 554—571. 2008

[LPR10-10] V. Lyubashevsky, C. Peikert, and O. Regev. On ideal lattices and learning with errors over rings. In EUROCRYPT. 2010.

[FHEW-11] Leo Ducas. FHEW: A Fully Homomorphic Encryption library (неопр.). Проверено 31 декабря 2014.