Multi-party computation (MPC) seems to be the most popular topic at this year's Crypto, and this morning began with the first of three sessions on MPC that are happening during the week.
This session, "New directions in MPC", covered some lesser-known theoretical aspects of secure computation.
The first talk dealt with the concept of fairness. A protocol is fair if an adversary who learns the output of the function cannot prevent the other parties from receiving the same output, by aborting the protocol, for instance. This is naturally a highly desirable property for secure computation, but even when it comes to the most basic protocols, our understanding of fairness is lacking. For example, it is impossible to construct a fair protocol for the coin flipping functionality, where two parties jointly generate a random bit. The talk gave some new results here, such as showing that coin flipping is impossible, even given a protocol that fairly computes random-OT, using a nice application of spectral graph theory.
Later in the morning, topics moved to leakage resilience and then symmetric encryption, which was (perhaps surprisingly) my favourite session of the day, dealing with topics related to cloud security and format-preserving encryption. The last few years have seen a massive surge of interest in techniques for computing on encrypted data and their application to cloud security. Whilst FHE as a concept is very nice and general, it is currently quite impractical, particularly for the oft-touted application of encrypted database search, since it requires computation at least linear in the database size. An alternative for this application is symmetric searchable encryption, explained Hugo Krawczyk.
Their scheme allows efficient, arbitrary boolean queries on keywords, with both the queries and database remaining semantically secure against the cloud. Most impressively, it has been tested on 10TB databases with 100 million records and over 100 billion indexed record-keyword pairs. The key improvement over previous work is efficient support for conjunctions (multiple keywords), which run in time proportional to the least frequent search term, whereas previous schemes allowing this were linear in the entire database size. However, information is still leaked on the access pattern through repeated results and queries, which seems a difficult problem to efficiently overcome.
Another highlight of the symmetric crypto session was Scott Yilek's talk on fully secure small domain encryption. This is applicable to format-preserving encryption, in which a ciphertext 'looks like' a plaintext. So for instance, an encrypted credit card number still looks like a credit number, which is very important for companies upgrading legacy systems to support encryption. The difficulty here is constructing a block cipher for arbitrary small domains, e.g. {0,1}^20 or {0, ..., 9}^16.
Scott's talk was very well presented (I highly recommend checking out the video if you missed it), with diagrams of playing cards for a simple recursive shuffling algorithm used to build a new primitive called a pseudo-random separator (PRS). To build a fully secure PRP there is the 'icicle' construction, which chains together several PRSs, illustrated by a diagram resembling icicles hanging from a sloped ceiling. The construction improves by a log(n) factor on previous fully secure schemes, but other schemes that are not fully secure are still more efficient.
The first talk dealt with the concept of fairness. A protocol is fair if an adversary who learns the output of the function cannot prevent the other parties from receiving the same output, by aborting the protocol, for instance. This is naturally a highly desirable property for secure computation, but even when it comes to the most basic protocols, our understanding of fairness is lacking. For example, it is impossible to construct a fair protocol for the coin flipping functionality, where two parties jointly generate a random bit. The talk gave some new results here, such as showing that coin flipping is impossible, even given a protocol that fairly computes random-OT, using a nice application of spectral graph theory.
Later in the morning, topics moved to leakage resilience and then symmetric encryption, which was (perhaps surprisingly) my favourite session of the day, dealing with topics related to cloud security and format-preserving encryption. The last few years have seen a massive surge of interest in techniques for computing on encrypted data and their application to cloud security. Whilst FHE as a concept is very nice and general, it is currently quite impractical, particularly for the oft-touted application of encrypted database search, since it requires computation at least linear in the database size. An alternative for this application is symmetric searchable encryption, explained Hugo Krawczyk.
Their scheme allows efficient, arbitrary boolean queries on keywords, with both the queries and database remaining semantically secure against the cloud. Most impressively, it has been tested on 10TB databases with 100 million records and over 100 billion indexed record-keyword pairs. The key improvement over previous work is efficient support for conjunctions (multiple keywords), which run in time proportional to the least frequent search term, whereas previous schemes allowing this were linear in the entire database size. However, information is still leaked on the access pattern through repeated results and queries, which seems a difficult problem to efficiently overcome.
Another highlight of the symmetric crypto session was Scott Yilek's talk on fully secure small domain encryption. This is applicable to format-preserving encryption, in which a ciphertext 'looks like' a plaintext. So for instance, an encrypted credit card number still looks like a credit number, which is very important for companies upgrading legacy systems to support encryption. The difficulty here is constructing a block cipher for arbitrary small domains, e.g. {0,1}^20 or {0, ..., 9}^16.
Scott's talk was very well presented (I highly recommend checking out the video if you missed it), with diagrams of playing cards for a simple recursive shuffling algorithm used to build a new primitive called a pseudo-random separator (PRS). To build a fully secure PRP there is the 'icicle' construction, which chains together several PRSs, illustrated by a diagram resembling icicles hanging from a sloped ceiling. The construction improves by a log(n) factor on previous fully secure schemes, but other schemes that are not fully secure are still more efficient.
No comments:
Post a Comment