PIR reading list

[Tim Ellison <t....@gmail.com>]

Could folks recommend some reading material to help me become more
familiar with the principles behind Pirk's PIR?

Many of the publications I have found on-line are academic reviews
(information theoretic vs. computational PIR, trading off communication
and processing complexity, etc), or deep mathematical proofs of
efficient algorithms (I'm looking at you Wideskies ;-)

I'm prepared to take on trust that the maths can be proven, but I'm
looking for a bit more than "you send an encrypted query, and we send
you an encrypted result".  I'm looking for the next level of detail.

How do you recommend I learn more about what is happening between the
various players in Pirk's PIR system?

Regards,
Tim

Re: PIR reading list

[Suneel Marthi <sm...@apache.org>]

On Tue, Aug 9, 2016 at 6:02 PM, Ellison Anne Williams <
eawilliamspirk@gmail.com> wrote:

> Hi Tim,
>
> Disclaimer: As a pure mathematician by training, I'm bent towards the
> theoretic mathematical explanations of PIR. :)
>
> PIR has 'historically' (it's only 20 yrs or so old) been a theoretic
> discipline which is why you see a theoretic/academic treatment in the
> literature. The aim of Pirk is to change this -- to move PIR from the
> purely theoretic and into the practical and scalable.
>
> The Wideskies paper and it's citations are good starting places for
> understanding the first base algorithm of Pirk and they do go into all of
> the detail. The original Paillier paper is also linked from the website and
> it contains some beautiful proofs regarding the hows-and-whys of the
> crypto.
>
> A good basis in abstract algebra (and a cursory bit of number theory) is
> necessary to really understand why things work they way that they do here
> -- my favorite algebra book is 'Algebra' by Micheal Artin.
>
> I am working on some slides in which I will explain the Wideskies algorithm
> (and some PIR primitives) at a high level, but, honestly, without diving
> deeply into the mathematics, folks will mostly have to press the 'I
> Believe' button... If we are in the same room at some point, I am happy to
> try and walk you through the math.
>

We could probably plan for a PIR-101 google hangout sometime. Barring Tim
(who's in UK), the rest of us I suppose are located in the Washington DC
metro.


>
> Anyone else want to weigh in here?
>
> Thanks!
>
> Ellison Anne
>
>
>
> On Tue, Aug 9, 2016 at 10:45 AM, Tim Ellison <t....@gmail.com>
> wrote:
>
> > Could folks recommend some reading material to help me become more
> > familiar with the principles behind Pirk's PIR?
> >
> > Many of the publications I have found on-line are academic reviews
> > (information theoretic vs. computational PIR, trading off communication
> > and processing complexity, etc), or deep mathematical proofs of
> > efficient algorithms (I'm looking at you Wideskies ;-)
> >
> > I'm prepared to take on trust that the maths can be proven, but I'm
> > looking for a bit more than "you send an encrypted query, and we send
> > you an encrypted result".  I'm looking for the next level of detail.
> >
> > How do you recommend I learn more about what is happening between the
> > various players in Pirk's PIR system?
> >
> > Regards,
> > Tim
> >
>

Re: PIR reading list

[Joseph Kovba <jk...@gmail.com>]

Not having EA's background in mathematics but having taken a crypto course
with some of the cursory number theory she eluded to,  I find the guide
below useful because it lays out the minimum amount of number
theory/algebra needed to understand Pallier encryption up front before
using the concepts to prove why it works mathematically.  As you requested,
I think this paper lies somewhere between the deep mathematical theory and
the seemingly magical "you send an encrypted query, and we send
you an encrypted result".

Ellison Anne, if you'd like some help coming up with the "Dummies' Guide to
PIR", that's something I'd love to help you develop!

Here is the link:

http://www2.cs.uni-paderborn.de/cs/ag-bloemer/lehre/proseminar_WS2005/material/Volkhausen_Ausarbeitung.pdf?PHPSESSID=edd79a27cb022cfa749b4a2baa7ea6f0

Take care!

On Tue, Aug 9, 2016 at 6:02 PM, Ellison Anne Williams <
eawilliamspirk@gmail.com> wrote:

> Hi Tim,
>
> Disclaimer: As a pure mathematician by training, I'm bent towards the
> theoretic mathematical explanations of PIR. :)
>
> PIR has 'historically' (it's only 20 yrs or so old) been a theoretic
> discipline which is why you see a theoretic/academic treatment in the
> literature. The aim of Pirk is to change this -- to move PIR from the
> purely theoretic and into the practical and scalable.
>
> The Wideskies paper and it's citations are good starting places for
> understanding the first base algorithm of Pirk and they do go into all of
> the detail. The original Paillier paper is also linked from the website and
> it contains some beautiful proofs regarding the hows-and-whys of the
> crypto.
>
> A good basis in abstract algebra (and a cursory bit of number theory) is
> necessary to really understand why things work they way that they do here
> -- my favorite algebra book is 'Algebra' by Micheal Artin.
>
> I am working on some slides in which I will explain the Wideskies algorithm
> (and some PIR primitives) at a high level, but, honestly, without diving
> deeply into the mathematics, folks will mostly have to press the 'I
> Believe' button... If we are in the same room at some point, I am happy to
> try and walk you through the math.
>
> Anyone else want to weigh in here?
>
> Thanks!
>
> Ellison Anne
>
>
>
> On Tue, Aug 9, 2016 at 10:45 AM, Tim Ellison <t....@gmail.com>
> wrote:
>
> > Could folks recommend some reading material to help me become more
> > familiar with the principles behind Pirk's PIR?
> >
> > Many of the publications I have found on-line are academic reviews
> > (information theoretic vs. computational PIR, trading off communication
> > and processing complexity, etc), or deep mathematical proofs of
> > efficient algorithms (I'm looking at you Wideskies ;-)
> >
> > I'm prepared to take on trust that the maths can be proven, but I'm
> > looking for a bit more than "you send an encrypted query, and we send
> > you an encrypted result".  I'm looking for the next level of detail.
> >
> > How do you recommend I learn more about what is happening between the
> > various players in Pirk's PIR system?
> >
> > Regards,
> > Tim
> >
>

Re: PIR reading list

[Ellison Anne Williams <ea...@gmail.com>]

Hi Tim,

Disclaimer: As a pure mathematician by training, I'm bent towards the
theoretic mathematical explanations of PIR. :)

PIR has 'historically' (it's only 20 yrs or so old) been a theoretic
discipline which is why you see a theoretic/academic treatment in the
literature. The aim of Pirk is to change this -- to move PIR from the
purely theoretic and into the practical and scalable.

The Wideskies paper and it's citations are good starting places for
understanding the first base algorithm of Pirk and they do go into all of
the detail. The original Paillier paper is also linked from the website and
it contains some beautiful proofs regarding the hows-and-whys of the
crypto.

A good basis in abstract algebra (and a cursory bit of number theory) is
necessary to really understand why things work they way that they do here
-- my favorite algebra book is 'Algebra' by Micheal Artin.

I am working on some slides in which I will explain the Wideskies algorithm
(and some PIR primitives) at a high level, but, honestly, without diving
deeply into the mathematics, folks will mostly have to press the 'I
Believe' button... If we are in the same room at some point, I am happy to
try and walk you through the math.

Anyone else want to weigh in here?

Thanks!

Ellison Anne



On Tue, Aug 9, 2016 at 10:45 AM, Tim Ellison <t....@gmail.com> wrote:

> Could folks recommend some reading material to help me become more
> familiar with the principles behind Pirk's PIR?
>
> Many of the publications I have found on-line are academic reviews
> (information theoretic vs. computational PIR, trading off communication
> and processing complexity, etc), or deep mathematical proofs of
> efficient algorithms (I'm looking at you Wideskies ;-)
>
> I'm prepared to take on trust that the maths can be proven, but I'm
> looking for a bit more than "you send an encrypted query, and we send
> you an encrypted result".  I'm looking for the next level of detail.
>
> How do you recommend I learn more about what is happening between the
> various players in Pirk's PIR system?
>
> Regards,
> Tim
>