Регева Исследование LWE содержит набросок доказательства.
Алгоритмы. Одним из наивных способов решения LWE является алгоритм максимального правдоподобия. Предположим для простоты, что $q$ является полиномиальным и что распределение ошибок является нормальным, как указано выше. Тогда нетрудно доказать, что примерно через $ О (п) $ уравнения, единственное назначение $s$ который «приблизительно удовлетворяет» уравнениям, является правильным. Это можно показать с помощью стандартного рассуждения, основанного на границе Чернова и границе объединения по всем $s\in\mathbb{Z}_q^n$. Это приводит к алгоритму, который использует только $ О (п) $ образцы и работает во времени $2^{O(n \log n)}$. Как следствие, мы получаем, что LWE является «хорошо определенным» в том смысле, что с высокой вероятностью решение $s$ уникален, если предположить, что количество уравнений равно $\Омега(n)$.
Также может быть полезно рассматривать LWE с другой точки зрения, а именно как диапазон параметров для SIS, где он априори неясно, должно ли существовать решение или нет, поэтому его «сажают». Видеть эти заметки для некоторой перспективы в этом направлении.
Обратите внимание, что для стандартной SIS многие решения существуют с высокой вероятностью, поэтому «LWE = Decisional SIS (в некотором диапазоне параметров)» легко запутаться, если не быть осторожным, см., например этот вопрос.
