是否有可能在通信复杂度小于发送方全部输入的情况下构造一个1-out-N OT？

Question

我见过的用于l-bit字符串的1输出-bit OT的构造具有与nl成正比的通信复杂性。我想知道，在活动安全性和传输小于O(nl)位的情况下(这里我忽略了O-notation中的安全参数)是否有可能做到这一点？对我来说，重要的是让它比仅仅把发送者的输入转移到接收者更便宜。

是否有一些固有的限制不允许这种OT传输比发送者的输入少的位数？有任何沟通下限吗？

Answer 1

假设发送方有字符串x_1, \ldots, x_n，每个字符串的长度为\ell。接收方可以选择y \in \{1, \ldots, n\}，并希望学习(仅) x_y。该议定书可按以下方式进行：

• 接收机为对称密钥全同态加密方案生成密钥k .
• 接收器发送c = \textsf{Enc}(k,y)。
• 发送者想象函数y \mapsto x_y的布尔电路D13 --这个电路有内置的所有x_i值。
• 发送方使用同态计算特性来本地计算c' = \textsf{Enc}(k,f(y))。
• 发送者发送c'。
• 接收器解密以获得f(y) = x_y。

只发送两个密文(每个加密一个\ell-bit字符串)，因此对于合适的FHE方案，这可能会花费O(\kappa)+2\ell比特。注意:您需要一个电路私有的加密方案--也就是说，c'不应该透露比f(y)更多的信息，甚至对密钥持有者也是如此。

该协议对半诚实的对手是安全的，但也有方法将其扩展到恶意安全。

Answer 2

为了补充Mikero的回答：

• 如果您希望在选定的输入位上使用1输出N OT，那么获取o(N)通信的已知方法将建立在次线性私有信息检索工作的基础上。大多数解决方案都依赖于全同态加密，就像Mikero的回答一样。然而，在其他密码假设下，也存在各种不同的构造，例如DCR (通过Damg Jurik密码系统)或DDH和QR (使用陷门哈希函数)。
• 如果您想要1-out-N伪随机OT (即N发送方输入是某些伪随机函数的输出)，那么在LPN假设的变体下有可供选择的、更有效的解决方案，例如这项工作。
• 具有次线性通信的知识零知识证明在证人规模上存在许多构造。如果您希望它们是非交互式的，则需要强大的假设(随机预言模型，或SNARG)，但如果您对交互很好，则它们存在于简单的假设中，如存在抗碰撞散列函数(例如，这里)。您可以使用任何这样的证明系统，以一种通用的方式将半诚实的OT (例如Mikero的答案中的一个)转换为一个具有主动安全性的方案。
• 如果您只想使用小于数据库大小的通信进行1-out-N，那么在一般假设下，这是可能的(尽管通信量会稍微少一点)：陷阱排列的存在(请参阅这里)。对于主动安全，您将需要CRHFs在此之上。