کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429845 | 687693 | 2012 | 16 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Communication-efficient distributed oblivious transfer Communication-efficient distributed oblivious transfer](/preview/png/429845.png)
Distributed oblivious transfer (DOT) was introduced by Naor and Pinkas (2000) [31], and then generalized to (k,ℓ)(k,ℓ)-DOT-(n1) by Blundo et al. (2007) [8] and Nikov et al. (2002) [34]. In the generalized setting, a (k,ℓ)(k,ℓ)-DOT-(n1) allows a sender to communicate one of n secrets to a receiver with the help of ℓ servers. Specifically, the transfer task of the sender is distributed among ℓ servers and the receiver interacts with k out of the ℓ servers in order to retrieve the secret he is interested in. The DOT protocols we consider in this work are information-theoretically secure. The known (k,ℓ)(k,ℓ)-DOT-(n1) protocols require linear (in n ) communication complexity between the receiver and servers. In this paper, we construct (k,ℓ)(k,ℓ)-DOT-(n1) protocols which only require sublinear (in n) communication complexity between the receiver and servers. Our constructions are based on information-theoretic private information retrieval . In particular, we obtain both a specific reduction from (k,ℓ)(k,ℓ)-DOT-(n1) to polynomial interpolation-based information-theoretic private information retrieval and a general reduction from (k,ℓ)(k,ℓ)-DOT-(n1) to any information-theoretic private information retrieval. The specific reduction yields (t,τ)(t,τ)-private (k,ℓ)(k,ℓ)-DOT-(n1) protocols of communication complexity O(n1/⌊(k−τ−1)/t⌋)O(n1/⌊(k−τ−1)/t⌋) between a semi-honest receiver and servers for any integers t and τ such that 1⩽t⩽k−11⩽t⩽k−1 and 0⩽τ⩽k−1−t0⩽τ⩽k−1−t. The general reduction yields (t,τ)(t,τ)-private (k,ℓ)(k,ℓ)-DOT-(n1) protocols which are as communication-efficient as the underlying private information retrieval protocols for any integers t and τ such that 1⩽t⩽k−21⩽t⩽k−2 and 0⩽τ⩽k−1−t0⩽τ⩽k−1−t.
► We propose a specific reduction from DOT to polynomial interpolation-based PIR.
► We propose a general reduction from DOT to any PIR.
► The DOTs we obtained are of sublinear communication complexity.
► The specific reduction captures all DOTs in the previous work.
► The general reduction relates DOTs to LDCs.
Journal: Journal of Computer and System Sciences - Volume 78, Issue 4, July 2012, Pages 1142–1157