Re: Secure Multi-party Computation

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

Hey team,

To take things down a more algorithmic path...

I've gotten through some of the basic papers on different PIR techniques as
well as some of the multi-set theory papers as well.  Before beginning
development, would anyone mind joining me in thinking some more about which
MPC algorithm might be the best in terms of Pirk's future MPC goals?  I've
got about 6.5-7 weeks left of my independent work period and I'd love to
start getting some code down.

Of course any help is appreciated.

Thanks guys,

Joe

On Thu, Sep 15, 2016 at 10:08 PM, Jacob Wilder <
jacobwilder.opensource@gmail.com> wrote:

> Joe (and for observers who aren’t reading all the papers),
> With the Microsoft paper it’s very important to note that it is a
> three-party protocol involving a trusted third party. Rather than rewrite
> an explanation I’ll cite the one from Pinkas, Schneider and Zohner ’14 on
> page 2 (they cite that Microsoft paper as [35]):
>
> > *Third Party-Based PSI* Several PSI protocols have
> > been proposed that utilize additional parties, e.g., [4].
> > …
> > Several efficient server-aided protocol for PSI were presented
> > and benchmarked in [35]. For their PSI protocol
> > with a semi-honest server, the authors report a runtime
> > of 1.7 s for server-aided PSI on one million elements using
> > 20 threads between cloud instances in the US east
> > - and west coast and 10 MB of communicated data. In
> > comparison, our fastest PSI protocol without a server requires
> > 4.9 s for 218 elements using four threads and sends
> > 78 MB (cf. Tab. 1 and Tab. 8). Note that this comparison
> > is sketchy and is only meant to demonstrate that using
> > a third party can increase performance. In our work we
> > focus on PSI protocols without a third party.
>
>
> On 9/15/16, 21:18, "Joseph Kovba" <jk...@gmail.com> wrote:
>
>     Jacob/Ellison Anne,
>
>     I'm currently looking (agonizing) over some papers on the foundations
> of
>     sMPC and at PSI in particular.  Within a week I hope to be able to
> discuss
>     it further with you and anyone else who might be interested.
>
>     In the meantime I did find that Microsoft is working on scalable PSI
> though
>     I have not read the paper, yet:
>     https://www.microsoft.com/en-us/research/publication/
> scaling-private-set-intersection-to-billion-element-sets/
>
>     Thanks for all of your helpful suggestions!
>
>     Take care,
>
>     Joe
>
>     On Mon, Sep 12, 2016 at 1:21 PM, Jacob Wilder <
>     jacobwilder.opensource@gmail.com> wrote:
>
>     > Continuing in the Private Set Intersection direction that Ellison
> Anne
>     > mentioned: I’ve been researching and thinking about what would look
> like a
>     > good way to implement Private Set Intersection in Pirk. I’ve found
> the 2014
>     > USENIX Security paper ‘Faster Private Set Intersection Based on OT
>     > Extension’ by Pinkas, Schneider and Zohner very useful. They present
>     > improvements to Oblivious Transport based PSI using hashing. Then
> they also
>     > perform a survey *with benchmarking* of all the different schemes
> they
>     > found.
>     > [ conference version with video https://www.usenix.org/
>     > conference/usenixsecurity14/technical-sessions/presentation/pinkas ]
>     > [ full version https://eprint.iacr.org/2014/447 ]
>     >
>     > In their conference presentation (slides 14-17) they include a nice
> graph
>     > with their performance measurements:
>     > https://www.usenix.org/sites/default/files/conference/
>     > protected-files/sec14_slides_pinkas.pdf#page=14
>     >
>     > The conclusions for Pirk from that graph as I see them:
>     >  - Elliptic Curve Diffie-Hellman based Private Set Intersection
> based on
>     > C. Meadows’s 1986 paper is the PSI algorithm with the lowest network
> traffic
>     >  - The authors’ OT with hashing is not terrible in the network
> traffic
>     > ranking but is the best in terms of low compute complexity
>     >  - Circuit-based sMPC should only be used for something more
> complicated
>     > than PSI due to higher costs in compute and substantially higher
> costs in
>     > communication
>     >
>     > A year later (at USENIX Security 2015) the same authors ( + Segev )
>     > released another optimization to their OT algorithm:
>     > [ https://www.usenix.org/conference/usenixsecurity15/
> technical-sessions/
>     > presentation/pinkas ]
>     > They also released the code from their survey:
> http://encrypto.de/PSI
>     >
>     > My personal opinion is that if we were to implement PSI we should
> start
>     > with the ECDH approach. Diffie-Hellman based protocols are well
> known and
>     > the security is widely understood.
>     >
>     > If an implementation of the ECDH version of PSI is added to Pirk I’d
> like
>     > to see us support different curves. Right now my personal wish list
> is
>     > P-256, P-384, Curve25519, and Curve448.
>     >
>     >
>     > I also think the OT algorithm is pretty interesting and would be
> worth
>     > implementing because it has different performance characteristics.
> It would
>     > be great in situations where network bandwidth is substantially
> cheaper (or
>     > faster) than the compute available. I have less to say about it
> because I
>     > know less about the crypto.
>     >
>     > I do think it’s important to note that OT is quantum machine
> resistant
>     > while Finite Field/Classical and Elliptic Curve Diffie-Hellman are
> not.
>     >
>     >
>     >
>     > On 9/8/16, 08:02, "Ellison Anne Williams" <ea...@apache.org>
> wrote:
>     >
>     >     Hi Joe,
>     >
>     >     So happy to see the interest and movement with sMPC!
>     >
>     >     Let's use the dev list to discuss the algorithms that you would
> like to
>     >     implement. Once the algorithms that make sense are determined
> (some are
>     >     more scalable than others), let's discuss the best way to
> integrate
>     > them
>     >     into Pirk.
>     >
>     >     One direction that may make the most sense for MPC is Private Set
>     >     Intersection. A few of us have been doing some research into the
>     > subject
>     >     lately as a possible next algorithmic step for Pirk. If you are
>     > interested
>     >     in private set intersection, let's discuss the research and
> bounce some
>     >     ideas around.
>     >
>     >     (cc'ing David Zaret as he is a previous colleague and may want
> to jump
>     > into
>     >     the conversation)
>     >
>     >     Thanks!
>     >
>     >     Ellison Anne
>     >
>     >     On Thu, Sep 8, 2016 at 7:40 AM, Joseph Kovba <jk...@gmail.com>
> wrote:
>     >
>     >     > Good morning,
>     >     >
>     >     > I'm currently enrolled in an independent work project at
> JHUAPL as
>     > part of
>     >     > a degree program.  My professor (David Zaret of JHU APL) is
>     > interested in
>     >     > PIR and MPC and I'd like to make that my topic for the
> semester.  I
>     > saw
>     >     > that secure MPC is on the Pirk roadmap and I'm looking for
> guidance
>     > on how
>     >     > to get started.  Do I need permission to begin working on a
> larger
>     >     > component, design guidance, etc?  Or, perhaps it's reasonable
> to
>     > take on
>     >     > unilaterally for the next 11-12 weeks and come back with a
>     > reasonable first
>     >     > attempt?
>     >     >
>     >     > I'm open to whichever method best serves the Pirk community
> and would
>     >     > appreciate any help or guidance you may have.
>     >     >
>     >     > Thanks, take care!
>     >     >
>     >     > Joe
>     >     >
>     >
>     >
>     >
>     >
>     >
>
>
>
>