Eurocrypt 2023
Indistinguishable Predictions and Multi-Group Fair Learning
Prediction algorithms assign numbers to individuals that are popularly understood as individual "probabilities"---what is the probability that an applicant will repay a loan? Automated predictions increasingly form the basis for life-altering decisions, and this raises a host of concerns. Concerns about the fairness of the resulting predictions are particularly alarming: for example, the predictor might perform poorly on a protected minority group. We survey recent developments in formalizing and addressing such concerns.
Inspired by the theory of computational indistinguishability, the recently proposed notion of Outcome Indistinguishability (OI) [Dwork et al., STOC 2021] requires that the predicted distribution of outcomes cannot be distinguished from the real-world distribution. Outcome Indistinguishability is a strong requirement for obtaining meaningful predictions. Happily, it can be obtained: techniques from the algorithmic fairness literature [Hebert-Johnson et al., ICML 2018] yield algorithms for learning OI predictors from real-world outcome data.
Returning to the motivation of addressing fairness concerns, Outcome Indistinguishability can be used to provide robust and general guarantees for protected demographic groups [Rothblum and Yona, ICML 2021]. This gives algorithms that can learn a single predictor that "performs well" for every group in a given rich collection G of overlapping subgroups. Performance is measured using a loss function, which can be quite general and can itself incorporate fairness concerns.
Guy Rothblum is a researcher at Apple and an Associate Professor of Computer Science and Applied Mathematics (on leave) at the Weizmann Institute of Science. He has wide interests in theoretical computer science, with a focus on cryptography, complexity theory, and societal concerns in algorithms and data analysis. He is the recipient of the 2018 Morris L. Levinson Prize in Mathematics, and the 2020 Blavatnik Award for Young Scientists in Israel in Physical Sciences & Engineering.
Musings on the not-so-distant past and future of lattice cryptography
Barring serious breakthroughs in cryptanalysis, the recent NIST selection of lattice cryptography as its primary quantum-safe standard ensures that lattices will play an important role in securing future communication. The new CNSA 2.0 guidelines dictating that all US government infrastructure must be quantum-safe by the early 2030’s means that this future will come earlier than many expected. But this real-world applicability of lattices is only the beginning. The simultaneous rise of digital currency and advanced cryptographic privacy applications means that there is a good chance that lattice-based schemes will contribute there as well.
In this talk, I will give a (non-technical) discussion of what happened during the NIST standardization process and how we can do even better in ensuring that the next generation of advanced cryptographic primitives gets into real world applications as soon as possible. I will describe some ideas that go into current lattice-based zero knowledge proofs (which are the cornerstone of a lot of privacy-based crypto) and will discuss what’s needed to push the field even further towards practical applications.
Vadim Lyubashevsky is a principal research scientist in the cryptography group at IBM Research Europe in Zurich. Vadim received his Ph.D. in 2008 from UCSD, after which he spent two years as a post-doc at Tel-Aviv University. Prior to joining IBM, he was a researcher at Inria in Paris, France from 2010 - 2015. Vadim’s main area of research is quantum-safe cryptography based on the hardness of lattice problems. In particular, he has done extensive foundational work on constructions of efficient cryptographic primitives, including encryption, digital signatures, and zero-knowledge proofs. A lot of his designs have been used as blueprints for submissions, by many various groups, to the recently-completed NIST post-quantum standardization process. He is part of the consortium of both schemes (CRYSTALS-Kyber and CRYSTALS Dilithium) which were chosen as the primary standards.