Можно ли построить OT 1 из N со сложностью связи меньше, чем весь ввод отправителя?

Конструкции 1-из-$n$ ОТ для $л$-битовые строки, которые я видел, имели сложность связи, пропорциональную $нл$. Интересно, а можно ли сделать ОТ с активной безопасностью и передать меньше чем $O(нл)$ бит (я игнорирую параметр безопасности в $О$-обозначение здесь)? Для меня важной частью здесь является то, что это дешевле, чем просто передача ввода отправителя получателю.

Есть ли какое-то неотъемлемое ограничение, которое не позволяет этому типу OT передавать меньше битов, чем ввод отправителя? Существуют ли какие-либо коммуникационные нижние границы для этого?

Предположим, что у отправителя есть строки $x_1, \ldots, x_n$, каждая длины $\ell$. У получателя есть выбор $y \in \{1, \ldots, n\}$ и хочет учиться (только) $x_y$. Протокол может действовать следующим образом:

• Получатель генерирует ключ $к$ для полностью гомоморфной схемы шифрования с симметричным ключом.
• Получатель отправляет $c = \textsf{Enc}(k,y)$.
• Отправитель воображает логическую схему $f$ для функции $y \mapsto x_y$ - эта схема имеет все $x_i$ встроенные ценности.
• Отправитель использует функцию гомоморфной оценки для локального вычисления $c' = \textsf{Enc}(k,f(y))$.
• Отправитель отправляет $с'$.
• Получатель расшифровывает, чтобы получить $f(y) = x_y$.

Только два шифротекста (каждый из которых шифрует $\ell$-битовая строка) отправляются, так что это может стоить $O(\каппа)+2\ell$ биты для подходящей схемы FHE. Примечание: вам нужна схема шифрования, которая является закрытой для канала, т.е. $с'$ должен раскрывать не более $ф(у)$, даже к ключнице.

Этот протокол защищен от получестных злоумышленников, но есть способы распространить его и на злонамеренные средства защиты.

Чтобы дополнить ответ Микеро:

• Если вы хотите 1-из-$N$ OT на выбранных входных битах, известные способы получения $о(Н)$ коммуникации строятся на работе по сублинейному поиску частной информации. Большинство решений основано на полностью гомоморфное шифрование, как в ответе Микеро. Однако существуют также различные альтернативные конструкции при других криптографических предположениях, таких как ДКР (через криптосистему DamgÃ¥rd-Jurik), или ДДХ и QR (используя хеш-функции с лазейкой).
• Если вы хотите 1-из-$N$ псевдослучайный ОТ (т.е. $N$ входные данные отправителя являются выходными данными некоторой псевдослучайной функции), то существуют альтернативные, более эффективные решения при вариантах предположения LPN, см., например, эта работа.
• Существует (много) конструкций доказательств знания с нулевым разглашением с сублинейной связью в размере свидетеля. Если вы хотите, чтобы они были неинтерактивными, вам нужны сильные предположения (модель случайного оракула или SNARG), но если вы согласны с взаимодействиями, они существуют из таких простых предположений, как существование устойчивых к коллизиям хэш-функций (например, здесь). Вы можете использовать любую такую ​​систему доказательств в общем виде, чтобы преобразовать получестную OT (такую, как в ответе Микеро) в схему с активной безопасностью.
• Если вы хотите сделать только 1-из-$N$ со связью меньше, чем размер базы данных, это, как известно, возможно (хотя связь будет только немного меньше) при общих предположениях: существование перестановок с лазейками (см. здесь). Кроме того, для активной безопасности вам понадобятся CRHF.