Key Search

The naked PIR protocol only can specify the position of the database elements stored on the database. Thus if you are not sure about the position number of the data, you cannot retrieve the data in one query.

However if the database elements are sorted according to the some key set, you can execute a binary or interpolation search to the database with multiple requests to achieve key search essentially.

This enables you to do a key search for the database.

The worst number of queries sent to the server is log2(n), but if you utilize interpolation search the number of queries are much shorter than the worst case for almost all real-world dataset.

We recommend interpolation search but the server may learn some knowledge from the number of requests sent to the server. In that case you can switch to binary search which has constant number of requests sent to the server. The latter case has perfect privacy by sacrificing efficiency, whereas the former case also will not leak big knowledge about the query and has more efficiency. We recommend interpolation search if you are not perfectionist.