Andrew Chi-Chih Yao to deliver 2021 IACR Distinguished Lecture

Title: Probabilistic Reasoning in Cryptography and Machine Learning

Asiacrypt 2021

Abstract: Distributed protocols occupy a key position in cryptography as well as in machine learning. Yet their analysis, especially in the probabilistic setting, can be quite involved. Simple statements regarding a protocol’s behavior often take sophisticated analysis to affirm. In this talk we present several new results along this line in cryptography and machine learning.

The first result concerns information complexity which specifies, for a given task, the amount of information that any protocol must leak. We determine the information complexity for a natural problem, using information theory to show why certain loss of privacy in inputs is inevitable.

The second result concerns machine learning. Traditional algorithms are designed to solve a specific problem with performance guarantees. The rise of powerful machine learning algorithms (ML) is a paradigm shift. Yet to show what problems can be solved by ML can be challenging; even seemingly obvious conjectures are often hard to establish rigorously. In this talk we give a proof for some cases where ML is known to demonstrate poor performance experimentally.