ICMC18: Keynote: Challenges in Implementing Usable Advanced Crypto

OS Crypto Track Keynote: Challenges in Implementing Usable Advanced Crypto (S22a) Shai Halevi, Principal Research Staff Member, IBM T. J. Watson Research Center

Advanced crypto goes beyond cryptography - includes proofs and things that complement use. We need it to be fast enough to be useful.

Your privacy is for sale - we give up privacy for services (directions, discounts on groceries, restaurant recommendations), we give up health data to look up personal medical solutions.

Data abuse is the new normal - the entire IT industry is making It easier to abuse. Larger collections of data, better ways to process them. It will get worse! If there opportunity is there to abuse, it will be abused.

Advanced cryptography promises blindfold computation - the ability to process data without ever seeing it - getting personalized services without giving access to your private information. Useful more traditional uses as well, like key management, but that's not the focus of this talk.

Zero knowledge proofs have been around for a long time (mid 80s?), are the concept that I have a secret that I don't want to tell you, but I can convince you of properties of my secret which should be enough to prove my secret.

You can use this for grocery history - I can prove that I bought 10 gallons of milk this month, so I can get a coupon, without revealing everything else that I bought.

The next concept is secure multi-party computation. We all have our individual secrets. We can compute a function of these secrets w/out revealing them to each other (or anyone else!). Has been around since the 1980s.

You could use this with medical data to determine the effectiveness of some treatment.  Data for different patients are held at each clinic, but the effectiveness can be shared.

The other concept is homomorphic encryption. Data can be processed in encrypted form and the result is also encrypted - but inside is the result of the function. Has been described in papers going back to 2009.

I could encrypt my location and send it to Yelp, Yelp computes an encrypted table lookup and gives me ads for nearby coffee shops. I could then get back encrypted results and then get coffee. :-)

Improving performance has been a major research topic for the last 30 years - we've made progress, but it will take a lot of very knowledgeable engineers to implement it.

Digital currencies  need to prove that you have sufficient unspent coins on the ledger, constructing the proof in less than 1 min and verify in a few microseconds - this needed the performance improvements to get it to perform that well.

You can use these encryption techniques and the speed improvements to find similar patients in a database in less than 30 seconds, or compute private set intersections.

By speeding up homomorphic encryption, you can compute the similarity of two 1M-marker sequences in minutes, or inference of simple neural-nets on encrypted data. 

But - all of these are complex, so not generally available.

There are a lot of software libraries that implement ZKP / MPC / FHE - most are open source, but it's very hard to compare the, decide which to use for what.  They have different computation models,performance profiles, security guarantees and there are hardly an accepted benchmarks.

Distributed computing is already very complex by itself. Adding advanced cryptography into it makes it that much more complicated (needs oblivious computation). Good performance needs extreme optimization - straightforward implementation will be terribly non performant. You need to be familiar with the techniques to optimize for what you're trying to do.

Communication between parties is the bottleneck in many protocols for secure multi-party computation. To optimize, many libraries work with sockets - they expect to be "in charge" of IP-address:port.  Retrofitting existing libraries is also very complicated.

How can you tame the complexity? You need frameworks and compiler support, tool boxes for common tasks and to shift our focus to usability.

We need to engage cryptographers and system builders to make this happen.