How to correct errors in multi-server PIR
K Kurosawa - International Conference on the Theory and …, 2019 - Springer
International Conference on the Theory and Application of Cryptology and …, 2019•Springer
Suppose that there exist a user and ℓ servers S_1, ..., S_ ℓ. Each server S_j holds a copy of
a database x=(x_1, ..., x_n) ∈ {0, 1\}^ n, and the user holds a secret index i_0 ∈ {1, ..., n\}. A
b error correcting ℓ server PIR (Private Information Retrieval) scheme allows a user to
retrieve x_ i_0 correctly even if and b or less servers return false answers while each server
learns no information on i_0 in the information theoretic sense. Although there exists such a
scheme with the total communication cost O (n^ 1/(2k-1) * k ℓ ℓ) where k= ℓ-2b, the decoding …
a database x=(x_1, ..., x_n) ∈ {0, 1\}^ n, and the user holds a secret index i_0 ∈ {1, ..., n\}. A
b error correcting ℓ server PIR (Private Information Retrieval) scheme allows a user to
retrieve x_ i_0 correctly even if and b or less servers return false answers while each server
learns no information on i_0 in the information theoretic sense. Although there exists such a
scheme with the total communication cost O (n^ 1/(2k-1) * k ℓ ℓ) where k= ℓ-2b, the decoding …
Abstract
Suppose that there exist a user and servers . Each server holds a copy of a database , and the user holds a secret index . A b error correcting server PIR (Private Information Retrieval) scheme allows a user to retrieve correctly even if and b or less servers return false answers while each server learns no information on in the information theoretic sense. Although there exists such a scheme with the total communication cost where , the decoding algorithm is very inefficient.
In this paper, we show an efficient decoding algorithm for this b error correcting server PIR scheme. It runs in time .
Springer
Showing the best result for this search. See all results