[messaging] PIR (in Pynchon Gate)

[Stefan Birgmeier]

On 25/03/14 03:48, Robert Ransom wrote:
> 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
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging
>
Not sure how far people are aware of this paper 
https://cs.uwaterloo.ca/~iang/pubs/orpir-usenix.pdf (by Casey Devet, Ian 
Goldberg, who seems to be in this conversation anyway, and Nadia 
Heninger) which attempts to tackle all the problems (Byzantine 
robustness, privacy, efficiency) and appears to do a good job at it, 
too. The paper can be conveniently "watched" there 
https://www.usenix.org/conference/usenixsecurity12/technical-sessions/presentation/devet 
in form of a presentation.
Just wanted to point it out.

Stefan