Constant-Rate Oblivious Transfer from Noisy Channels
Constant-Rate Oblivious Transfer from Noisy Channels
复制标题
来自噪声通道的恒定速率不经意传输
DOI：
10.1007/978-3-642-22792-9_38
复制
发表时间：
2011
影响因子：
2.5
通讯作者：
Jürg Wullschleger
中科院分区：
文献类型：
--
作者：
Yuval Ishai;E. Kushilevitz;R. Ostrovsky;M. Prabhakaran;A. Sahai;Jürg Wullschleger
二进制对称信道（BSC）是一种有噪声的通信信道，它以某个固定的错误概率0 < p < 1/2独立地翻转每个比特。Crepeau和Kilian（FOCS 1988）表明，不经意传输，因此一般安全的两方计算，可以无条件地实现通过BSC通信。在提高这一结构的效率和通用性方面，已经进行了一系列的工作。然而，实现针对恶意方的安全性的所有已知构造都要求各方针对实现的不经意传输（更准确地说，（2/1）- bit-OT）的每个实例在信道上传送poly（k）比特，其中k是统计安全参数。实现恒定（正）速率的问题仍然悬而未决，即使是在实现长字符串的单次不经意传输的更容易的情况下。
我们解决这个问题的肯定，通过展示如何实现n个独立的不经意传输的情况下，与统计错误，消失与n，通过通信只是O（n）位在BSC。作为一个推论，任何大小为s的布尔电路都可以通过BSC上的O（s）+poly（k）位通信的两方安全地评估，从而改善了以前构造的O（s）-poly（k）复杂度。
A binary symmetric channel (BSC) is a noisy communication channel that flips each bit independently with some fixed error probability 0 < p < 1/2. Crepeau and Kilian (FOCS 1988) showed that oblivious transfer, and hence general secure two-party computation, can be unconditionally realized by communicating over a BSC. There has been a long line of works on improving the efficiency and generality of this construction. However, all known constructions that achieve security against malicious parties require the parties to communicate poly(k) bits over the channel for each instance of oblivious transfer (more precisely, (2/1)- bit-OT) being realized, where k is a statistical security parameter. The question of achieving a constant (positive) rate was left open, even in the easier case of realizing a single oblivious transfer of a long string.
We settle this question in the affirmative by showing how to realize n independent instances of oblivious transfer, with statistical error that vanishes with n, by communicating just O(n) bits over a BSC. As a corollary, any boolean circuit of size s can be securely evaluated by two parties with O(s)+poly(k) bits of communication over a BSC, improving over the O(s) ċ poly(k) complexity of previous constructions.