Почему RLWE сложен или даже имеет решение?

Я думал о том, почему и как проблема RLWE вообще сложна. Я знаю, что это сложно, потому что ее можно свести к задаче о кратчайших векторах, но я думаю о том, как она вообще имеет решение.

Проблема в основном:

$а_{я}(х)$ быть набором случайных, но известных полиномов из $F_q [ х ] / Φ ( х )$ с коэффициентами от всех $F_q$.

$e_i ( х ) $ быть набором малых случайных и неизвестных полиномов, относительных до предела $b$ на ринге $F_q[x]/Φ(x)$.

$с(х)$ быть малым неизвестным полиномом относительно границы $b$ в звенеть $F_q[x]/Φ(x)$.

$b_i ( x ) = ( a_i ( x ) â s ( x ) ) + e_i ( x )$

Задача RLWE состоит в нахождении полинома $s$ данный $b$ и $а$. Но как я узнаю, что нашел его, если ошибка $е$ может быть что угодно? Например, я мог бы выбрать умеренное $s$ чтобы результат был близок к $b$ и придумать любой $е$ такой, что $b = a.s + e$. С $е$ случайно и неизвестно, это может быть что угодно. У меня даже нет способа проверить, что я нашел правильный, потому что я не знаю $е$.

Есть два ключевых момента, о которых вы упоминаете (один из них упоминается Пончо в комментариях --- я повторяю здесь для наглядности).

1. Ошибки RLWE $e_i(x)$ находятся небольшой, и
2. секрет $с(х)$ является последовательный по всем образцам.

Это дает довольно простой способ убедиться, что вы восстановили правильный $с(х)$ --- разделите набор сэмплов пополам, восстановите $с(х)$ из половины образцов, и убедитесь, что те же $с(х)$ таков, что $a(x)s(x)\приблизительно b(x)$ (до «небольшой» ошибки) на другой половине выборок. На всех образцах вы должны убедиться, что восстановленный $e(x) = b(x)-a(x)s(x)$ маленький. Я считаю, что эта техника известна как перекрестная проверка в статистике, но как бы он ни назывался, он и здесь прекрасно работает.

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