Я думаю, что есть путаница с терминологией «безопасное вычисление от совместного использования секрета». Позвольте мне попытаться уточнить.
Есть две основные настройки для безопасных вычислений: настройка честного большинства (из $n$ партии, максимум $(n-1)/2$ нечестны) и установка нечестного большинства (до $n-1$ стороны могут быть нечестными). У этих двух настроек есть очень важное различие: первая может быть достигнута без каких-либо вычислительных предположений, поскольку она может быть защищена даже от недобросовестных сторон с неограниченной вычислительной мощностью. С другой стороны, второй «платит» своей более сильной устойчивостью к коррупции, обязательно требуя вычислительных предположений (протокол MPC с нечестным большинством не может быть защищен от вычислительно неограниченных сторон).
Здесь вы говорите о безопасном сравнении и цитируете мою статью, поэтому я предполагаю, что вы говорите о безопасных двухсторонних вычислениях. Конечно, двухстороннее вычисление относится ко второй категории: у вас не может быть честного большинства среди двух игроков (если только все не будут честными, и в этом случае защищать нечего). Это означает, что вы должен использовать расчетное предположение.
Обмен секретами нет вычислительное предположение. Разделение секретов существует безоговорочно: например, разделение секретов Шамира — это просто полиномиальная интерполяция. Поэтому доказуемо невозможно создать безопасный двухсторонний протокол вычислений для сравнения, используя только совместное использование секрета. Все протоколы должен полагаться на вычислительное предположение, которое может быть гомоморфным шифрованием, забывчивой передачей или чем-то еще.
Я думаю, что источник путаницы, вероятно, происходит из общей терминологии в MPC: многие люди используют терминологию «MPC, основанный на совместном использовании секретов», даже в условиях нечестного большинства. Но эта терминология просто означает, что методы совместного использования секретов использовал в протоколе, обычно аналогично протоколу GMW. Однако это не означает, что протокол использует исключительно совместное использование секрета, поскольку это невозможно. Как правило, когда мы говорим «MPC на основе совместного использования секрета», мы имеем в виду протокол MPC, который на самом деле использует методы совместного использования секрета и передачу без ведома.
Итак, «методы, основанные на совместном использовании секрета» для безопасного сравнения, точно так же, как и в моей статье, — это методы, использующие забывчивую передачу в качестве вычислительного предположения. Если вы посмотрите на мою статью в разделе 1.5, я также сравнил свой протокол с «общим 2PC, примененным к [GSV07]». Здесь «универсальный 2PC» относится к стандартному 2PC в стиле GMW, который часто называют «MPC на основе совместного использования секретов». Протокол в стиле GMW требует логического представления схемы целевой функции; именно поэтому я сказал «применительно к [GSV07]», который обеспечивает именно такую схему. Следовательно, я сравниваю свою работу с тем, что часто называют «секретным обменом MPC», но я просто не использовал терминологию, которая, кажется, является источником вашей путаницы.
