Hey Jacob, Thanks again for your recommendations. I was wondering if you could tell me how, in the simple DH-based OT protocol you mentioned to me, how do Alice and Bob agree on which generator of the group Z to use? Is this something that can be determined publicly or must it be negotiated in secret ahead of time?
Thanks for your help! Joe On Mon, Sep 12, 2016 at 1:21 PM, Jacob Wilder < [email protected]> 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" <[email protected]> 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 <[email protected]> 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 > > > > > > >
