Last week I was in Aarhus, Denmark for the workshop on the Theory and Practice of MPC. It was a really great week with all the MPC people, thanks largely to the excellent programme covering a wide range of areas (and of course the rump session featuring Marcel's Eurovision-worthy MPC song). In this post I'll briefly describe two of the talks that captured my attention the most: a practical talk by Benny Pinkas on Private Set Intersection, and a theoretical result presented by Yuval Ishai on a promising new approach to obtaining actively secure MPC protocols.
Private Set Intersection (Benny Pinkas)
The problem of private set intersection (PSI) is simple: two parties each hold a set of items, and one or both of them wish to learn the intersection of the sets without revealing anything else. Benny spent most of the talk giving an overview of pretty much every possible method of doing PSI, including a couple of new or improved techniques, and then presented timings for implementations of all the protocols, running on the same platform in the same conditions. This kind of rigour is (sadly) rarely found in applied MPC papers and it was really cool to see this being done.
The simplest PSI protocol is based on DDH and apparently dates back to the 80s. Both parties simply hash their items and raise them to the power of a secret exponent. Then they do a Diffie-Hellman-style exchange and compute the hashes raised to the product of the two exponents, which allows them to determine any matches. This very simple method needs 2N exponentiations for N items, but can be made pretty efficient using ECC and still performs surprisingly well.
Benny went on to describe a method based on oblivious polynomial evaluation, a generic circuit-based approach using oblivious shuffling and sorting networks, and a recent, efficient construction from CCS last year that uses a bloom filter and OT. Noting that with OT extensions, the OT primitive is now much more efficient than public key techniques, so they redesigned the bloom filter protocol to allow for OT extensions and finally gave a new method based solely on OT and hashing. This new method was the fastest, computing an intersection of 2^18 items in just 14s, with 76MB of communication. However if communication is a bottleneck then the classic DDH approach still wins, with only 26MB.
Active security in MPC (Yuval Ishai)
Traditional approaches to getting active security in MPC take a passively secure protocol and modify it in some way to ensure that the adversary will always follow the protocol and cannot cheat, often using zero knowledge proofs or cut-and-choose, which are fairly expensive tools. One notable exception to this is the IPS compiler, which is a general technique for building an actively secure protocol from several passive protocols with only constant overhead, but is still too expensive for practical usage right now.
Yuval presented a new method of obtaining active security, based on the idea of creating tamper-resistant circuits that are secure against arbitrary additive manipulation of wire values. He described a clever solution that encodes inputs in a way that additive attacks can be detected, based on similar encodings to MACs used in the BDOZ and SPDZ MPC protocols. These encodings contain a random verification value, which grows quadratically with every multiplication in the circuit; to avoid this growth, they have a special gadget after every gate that ensures the output degree does not increase.
The talk was theoretical, and it will probably take some work to make these circuit conversion techniques truly practical, but this would have exciting implications for the efficiency of actively secure protocols, such as:
- Active security by simply running a passive secure protocol (e.g. GMW) over the modified, additively secure circuit
- Actively secure MPC using untrusted preprocessing (generated from a passive protocol)
No comments:
Post a Comment