Re: Private Information Retrieval (PIR) as a C/C++ Aggregate Extension

Yes, that is accurate. You can think of PIR as an aggregator.

The amount of data per query is already limited. In fact, the naive implementation of Information Theoretic PIR requires the transmission of the entire database. MuchPIR implementation makes use of the already optimized query/response presented in [1]. As for protection of the database per copy: anyone who already has access to your database can copy it if they so wish so. PIR's threat model revolves around keeping data query/result private even when everything beyond your private zone is untrusted. Data copy is not a concern.

There is one configuration in which the query can be reduced to about 1 MB in size. Comes at a cost somewhere else though. There is an optimization that reduces the query size by more than half, but that is not available in the demo. The query result however is fixed in size, per configuration, up to compression.

Yes, our particular implementation does lend itself to other uses falling under Differential Privacy. In fact, we have already worked out the technical details for several such use cases: retrieval on keyword match, or ID match, sum aggregator, and string search. The most remarkable part of string search is that searches can be done with using wildcards as well, though the returned data will be how many hits occurred. The size of the string to be searched remains very small, but we are working to improve every aspect of MuchPIR and the technology we are building on top of it.

MucPIR Team

[1] https://eprint.iacr.org/2017/1142.pdf

Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐

On Sunday, September 12th, 2021 at 1:00 PM, Andrey Borodin <x4mmm(at)yandex-team(dot)ru> wrote:

> Hi!
>
> > 12 сент. 2021 г., в 18:02, Private Information Retrieval(PIR) postgresql-pir(at)pm(dot)me написал(а):
> >
> > I've created a Postgresql C/C++ Aggregate Extension implementing Private Information Retrieval (PIR) using Homomorphic Encryption. The open sourced version can be found here: https://github.com/ReverseControl/MuchPIR .
> >
> > In essence, with PIR we can retrieve data from any row in a table without revealing to the server doing the search which row data was retrieved, or whether the data was found at all.
> >
> > I am seeking feedback from the postgres community on this extension. Is it something of interest? Is it something anyone would like to contribute to and make better? Is there similar work already publicly available? Any reference would be greatly appreciated.
>
> PIR seem to be interesting functionality.
>
> As far as I understand in terms of a database PIR is special kind of an aggregator, which extracts some part of data unknown to server.
>
> One question came to my mind. Can we limit the amount of extracted data? It makes sense to protect the database from copy.
>
> Also you may be interested in differential privacy data exploration [0,1]. This is a kind of data aggregation which protects data from deducing single row by means of aggregation. Implementation could be resemblant to MuchPIR.
>
> Thanks!
>
> Best regards, Andrey Borodin.
>
> [0] https://en.wikipedia.org/wiki/Differential_privacy
>
> [1] https://cs.uwaterloo.ca/~ilyas/papers/GeSIGMOD2019.pdf