Introduction
For non-engineers
Math behind PIRs in 5min
The server sorts database elements in some way to coordinate a dataset. The client will send a query with an encrypted position of the elements and the server replies an encrypted data with the correct data.
The client sends an array of encrypted messages with zero or one. There is single "one" encrypted message which select the database elements to fetch. Since all messages are encrypted with client's private key, the server cannot distinguish which messages are zero or one.
The server will compute a multiplication with the data and encrypted messages, and then adds them up to compose an encrypted payload and send back to the client.
The client then decrypts the encrypted reply to retrieve the needed data.
Multi-dimensional case
We intentionally limited ourselves to the one-dimensional case above, but in our implementation we use multi-dimensional PIR. For multi-dimensional PIR, the server arranges the database elements in a multi-dimensional cube (for 2d: squre, for 3d: cube, for 4d+: hypercube) and the client's query will be an array of arrays of encrypted messages. The reply will be an encrypted message with some another encrypted message of some another encrypted message... (repeated for the dimension used).
This looks too complicated but it is required for shorter reply. There are some trade-offs between the reply size and the computation time, the dimension is usually selected as two or three.
Last updated