сообщество !
Я ищу доказательство теоретической безопасности раскрытия секрета Шамиром. Я нашел несколько статей, в которых говорится, что это похоже на проблему остановки, что подразумевает, что не существует общего алгоритма для ее решения для всех возможных пар программа-ввод. Но я не понимаю, почему это означает шифрование SSS. Почему мы говорим, что можем рассчитать все возможные решения только для трехуровневой системы без возможности их проверки?
Я имею в виду, например, для $(к,п)$ мы можем построить $2^{Nк}$ различные полиномы ($N$ количество битов шифрования) перебором, затем строить $к$ доли с каждым многочленом, затем проверьте, приводят ли эти доли к правильному секрету с помощью интерполяции Лагранжа или исключения Гаусса. Таким образом, обладая достаточной вычислительной мощностью, мы должны рано или поздно раскрыть секрет.
Кроме того, я думаю, что эту грубую силу можно оптимизировать для $О(2^N)$ если мы рассматриваем только проверку постоянных полиномов, что означает перебор непосредственно на $2^N$ возможные значения, которые может принимать секрет.
Поэтому мне в основном интересно: почему этот сценарий невозможен? Где ошибка в моей мысли?
