Почему мы предполагаем, что f полиномиальная функция или полиномиальная по времени? Какая интуиция стоит за этим?
Я надеюсь, вы уже знакомы с тем, почему мы используем полиномиальное время в качестве основы практически для всей криптографии (см. комментарии Келалаки). Короче говоря, существует бесчисленное множество причин, по которым мы считаем, что это достаточно надежная модель для того, что мы интуитивно называем «эффективными вычислениями».Здесь, в контексте MPC, все то же самое: мы хотим иметь возможность сосредоточиться на вычислениях, которые эффективно выполнять.
это ограничивает типы функций, которые мы можем воспроизвести с помощью протоколов, не так ли? Почему мы предполагаем, что это единственное семейство функций, которые могут имитировать протоколы? Ограничивает ли это семейство функций задачу также полиномиальными функциями? Может ли это предположение
Я не знаком с точными формулировками в этих статьях, но, как правило, всякий раз, когда вы ссылаетесь на функции с неограниченным вводом/выводом, вы действительно рассматриваете их, которые все еще вычислимы за полиномиальное время относительно длины ввода. Опять же, это потому, что мы моделируем участников протокола как машины с полиномиальным временем, и мы хотели бы, чтобы они могли завершить вычисления.
Кроме того, существуют понятия безопасности, основанные на предположении, что злоумышленник ограничен вычислительными возможностями. Например, есть протоколы, безопасность которых зависит от неспособности злоумышленника разложить на множители большие числа. Это возможно, конечно, при наличии достаточного времени вычислений, чтобы перепробовать все возможные простые множители, но противник с полиномиальным временем не может этого сделать.
Однако есть и другие понятия в контексте безопасных многосторонних вычислений, когда мы действительно можем терпеть противников, работающих за суперполиномиальное время. Протоколы с Отлично и статистический безопасности (которые получают общий термин теоретико-информационная безопасность) спроектированы таким образом, что ни один злоумышленник, независимо от количества вычислительных ресурсов или времени работы, не может нарушить безопасность протокола.
Учитывая это, в принципе, мы могли бы позволить всем сторонам (не только противнику) работать за сверхполиномиальное время, но тогда возникает вопрос, что на самом деле получается при этом. По сути, я не могу думать о значимых неполиномиальных функциях, которые мы хотели бы вычислить.
