В этом ответе я сосредоточусь на получестной безопасности. Вы можете разделить соответствующие протоколы PSI на две категории:
В на основе Диффи-Хеллмана протоколы (созданные в Губерман-Франклин-Хогг), стороны должны вычислить несколько возведений в степень для каждого элемента в своих наборах.
В Oblivious-перевод на основе протоколы (ведущими в данном случае будут ККРТ и Чейз-Мяо), стороны сначала выполняют несколько сотен базовых OT (каждая требует нескольких возведений в степень), независимо от размера их наборов PSI. Все, что появляется позже в протоколе, использует только гораздо более эффективные операции с симметричным ключом, такие как вызовы AES/SHA.
Подход Диффи-Хеллмана неизменно имеет меньшие затраты на связь, независимо от того, насколько велики наборы PSI. А когда наборы PSI малы, время выполнения нескольких возведений в степень для каждого элемента меньше, чем время выполнения «базовых OT» других протоколов. В общем, Diffie-Hellman PSI для небольших наборов отличное практическое правило.
Но насколько мал мал? Вы упоминаете наборы, содержащие около 1000 предметов. С наборами такого размера уже не совсем ясно, какой протокол лучше. В экспериментах, которые мы проводили в нашей исследовательской группе, отсечка (когда протоколы на основе OT становятся быстрее) составляет чуть менее 500 элементов в очень быстрых сетях и чуть более 1000 элементов в очень медленных сетях.Но даже в быстрых сетях разница в производительности для этого приложения не зацикливается: мы говорим о 0,35 против 0,25 секунды для выполнения PSI.
В итоге, Я бы рекомендовал реализовать протокол Diffie-Hellman PSI. Губермана-Франклина-Хогга, поскольку (1) время работы достаточно близко к минимальному; (2) связь самая низкая; (3) простота протокола облегчает его реализацию.
Изменить декабрь 2021 г.: Недавно мы опубликовали улучшение протокола Губермана-Франклина-Хогга для PSI на малых наборах. Он быстрее, использует меньше средств связи и имеет более сильную (вредоносную) защиту. Это будет моя последняя рекомендация.
Чтобы ответить на ваш вопрос о многопартийном PSI: теперь довольно легко преобразовать большинство двухсторонних протоколов PSI в многосторонние.
Большинство протоколов PSI построены на основе базового забывчивого PRF (в Diffie-Hellman PSI забывчивый PRF является $x \mapsto H(x)^k$ куда $Ч$ случайный оракул). В КМПРТ мы показали, как построить многопартийную PSI из двухпартийной OPRF. Одна из конструкций защищена от полудобросовестных противников, а другая имеет свойство безопасности с более мелким шрифтом. В бумага который появится на Crypto 2021, мы показываем, что эта вторая конструкция действительно защищена от злоумышленников.
В целом, многосторонняя PSI, по сути, предполагает, что каждая сторона проводит модифицированную двухстороннюю PSI с одной центральной стороной (той, которая получает выходные данные).
