Asiacrypt 2021
Probabilistic Reasoning in Cryptography and Machine Learning
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.
Andrew Chi-Chih Yao is Dean of the Institute for Interdisciplinary Information Sciences (IIIS) at Tsinghua University. His research interests include algorithms, cryptography, quantum computing, auction theory and artificial intelligence. Professor Yao is recipient of the Turing Award in 2000 and the Kyoto Prize in Advanced Technology in 2021. He is member of the Chinese Academy of Sciences, and foreign member of the US National Academy of Sciences.
You can see more information about past IACR Distinguished Lectures here.
Cryptography For a Secure, Privacy-Respecting and Fair Society: What More Can We Do?
Cryptographic protocols such as electronic voting schemes, auction schemes, lottery schemes and many others, are designed to bring more security, privacy and fairness to society. In this talk, I will discuss some further steps we could take towards achieving this goal using our expertise in cryptography, together with lessons I learned along my ongoing journey.
Professor Kazue Sako studies cryptographic protocols that enhance privacy and fairness, such as electronic voting protocols, anonymous authentication schemes, and digital lottery systems. Before joining Waseda University in 2020, she worked in a research laboratory at NEC where she engaged in designing and developing many real world products using cryptography. She served as Program Chair or Co-Chair for Asiacrypt, CT-RSA, FC, PKC, ESORICS, ACNS and AsiaCCS, and is currently a member of the RWC Steering Committee. She was the 26th president of Japan Society for Industrial and Applied Mathematics. She serves as expert in ISO/IEC JTC1 SC27 WG5 (Identity and Privacy) where she edited two international standards on anonymous authentication, and is part of several committees within the Japanese government, including the Science Council of Japan, the Financial System Council and the Evaluation Committee for Innovative Business Activities. She is the Vice-Chair of MyDataJapan and a former trustee of the Sovrin Foundation.
Professor Sako received her Ph.D from Kyoto University.
Learning Parity with Noise: Constructions, Reductions, and Analyses
In this talk, I will introduce my recent works on the learning parity with noise (LPN) problem. In particular, we consider the LPN problem under the constant rate noise regime. First, we show how to construct public-key encryptions and collision-resistant hash functions from the LPN assumption with sufficient hardness. Second, we discuss whether such (average-case) hardness can be reducible from its worst-case analog, i.e., the promise-NCP problem (on specific codes). Finally, we study the asymptotic hardness of LPN by reviewing the BKW algorithm. We introduce ways to optimize the BKW with fine-grained trade-offs between time, space, and sample complexities without heuristics.
Yu Yu is a professor at Shanghai Jiao Tong University. He obtained his BSc from Fudan University in 2003, and then his Ph.D. from Nanyang Technological University in 2006. Yu was a postdoctoral researcher at the UCL Crypto Group during 2008-2010. After returning to China, he worked at East China Normal University (2011- 2012) and Tsinghua University (2012-2013). His research interests include side-channel analysis and countermeasures, efficient constructions of pseudorandom objects, and learning parity with noise. He is a member of the Asiacrypt Steering Committee and has served on the program committee of Asiacrypt, Eurocrypt, Crypto, CHES, PKC, and TCC.