[messaging] PIR (in Pynchon Gate)

[Robert Ransom]

On 3/23/14, Brian Warner <warner at lothar.com> wrote:
> There were also a bunch of fiddly bits involving how to scale the
> slot/ring/window sizes, how to deal with overload (recipients could send
> anonymous messages back to the collator to release the next batch of
> messages), how to detect byzantine distributors (and complain about them
> safely),

The most obvious way to identify a malicious distributor is to use a
GF(2)-linear single-server CPIR scheme to retrieve a GF(2)-linear hash
(in the ‘universal hash function’ sense) of each of the responses it
should have received, from each of several distributors.  The hash
function can be implemented using polynomial evaluation over a
reasonably large binary field; the CPIR scheme will have to be
code-based, and will probably be horribly inefficient, so malicious
distributors must be punished harshly.

It's likely that some clients would be better off downloading the
entire dataset than uploading the many requests needed for code-based
CPIR.


Once a client has identified which response was malicious, it can
publish its request and the distributor's signature on the bogus
response in order to incriminate the distributor.


Robert Ransom