Private information retrieval protocol

A new computationally efficient private information retrieval protocol is proposed. It is based on coset properties of Galois groups of the field $\mathrm{GF}(q)$ finite extensions. The proposed protocol has communication complexity slightly worse than the best known schemes based on locally decodable codes and it may be constructed for any system parameters (as opposed to codes). In comparison with similar solutions based on polynomials the computational complexity of our method is smaller which is important especially for servers processing multiple requests from multiple users.