报名 | 北京密码学日
北京密码学日是密码学领域的单日研讨会，将于2024年6月15日在北京大学举办，由北京大学前沿计算研究中心刘天任老师组织，以特邀报告的方式，邀请国内外专家介绍在密码学领域的前沿进展。
互动报名
↑↑扫小程序码报名↑↑
密码学日上午内容线上进行，下午内容线下进行。报名成功的观众将于6月14日收到通知邮件，含上午报告在线会议链接。
报告信息
以报告时间排序
1. Improving Garbled Circuits with Switch Systems
Abstract
Secure multiparty computation (MPC) is a subfield of cryptography that allows two or more mutually untrusting parties to securely run programs on their joint private inputs. One of the main techniques for achieving MPC is Yao's Garbled Circuit (GC). Roughly speaking, GC allows one party — the garbler — to "garble" a program such that a second party — the evaluator — can run that garbled program on an encrypted input. Since all data is encrypted, the evaluator learns nothing beyond the program output, achieving the privacy requirement.
Since the 1980s, the community has known simple and reasonably efficient techniques for garbling any program, so long as that program is represented as a Boolean circuit. While any (bounded) program can be compiled to a Boolean circuit, many programs compile to large circuits, leading to high cryptographic cost. It is thus interesting to consider garbling other program representations, such as RAM programs and arithmetic circuits.
In this talk, I will explain recent advances in GC that extend garbling to other program representations. My focus will be a recently-introduced model of computation called the switch system model. The switch system model is reasonably simple, straightforward to garble, and captures many recent advances in GC. I will sketch how the switch system model enables significant improvements in the garbling of RAM programs and arithmetic circuits, and how this model unifies many recent advances in GC.
Biography
David Heath is an assistant professor at University of Illinois Urbana-Champaign's department of computer science. His work focuses on secure multiparty computation and zero knowledge proofs, and the emphasis of his research is on improving the asymptotic and concrete efficiency of these techniques.
2. Cryptography from Learning Parity with Noise
Abstract
Learning parity with noise (LPN) is a computational hard problem that has been well studied in learning theory, coding theory and cryptography since the early 90's. Despsite its simplificity, standard LPN assumptions did not seem to imply anything beyond Minicrypt. In this talk, we show that LPN with sufficient subexponential hardness implies public-key cryptography, oblivious transfers and collision resistant hash functions. Falsifying the hardness assumptions would imply significant improvement over the current state-of-the-art LPN solver, namely, the BKW algorithm. We also discuss how to do time space tradeoffs for BKW.
Biography
Yu Yu is currently a professor at Shanghai Jiao Tong University. He obtained his BSc from Fudan University in 2003, and then his PhD from Nanyang Technological University in 2007. He worked as a researcher at the ICT security lab at T-Systems Singapore from 2006 to 2008, and as a postdoctoral researcher at the UCL Crypto Group during 2008-2010. After returned to China, he was employed by East China Normal University (2011-2012) and Tsinghua University (2012-2014).
3. A Direct PRF Construction from Kolmogorov Complexity
Abstract
While classic results in the 1980s establish that one-way functions (OWFs) imply the existence of pseudorandom generators (PRGs) which in turn imply pseudorandom functions (PRFs), the constructions (most notably the one from OWFs to PRGs) is complicated and inefficient.
Consequently, researchers have developed alternative direct constructions of PRFs from various different concrete hardness assumptions. In this work, we continue this thread of work and demonstrate the first direct constructions of PRFs from average-case hardness of the time-bounded Kolmogorov complexity problem MK^t P[s], where given a threshold, s(·) , and a polynomial time-bound, t(·) , MK^t P[s] denotes the language consisting of strings x with t-bounded Kolmogorov complexity, K^t (x) , bounded by s(|x|).
In more detail, we demonstrate a direct PRF construction with quasi-polynomial security from mild average-case of hardness of MK^t P[2^(O√logn)] w.r.t the uniform distribution. We note that by earlier results, this assumption is known to be equivalent to the existence of quasi-polynomially secure OWFs; as such, our results yield the first direct (quasi-polynomially secure) PRF constructions from a natural hardness assumption that also is known to be implied by (quasi-polynomially secure) PRFs.
Perhaps surprisingly, we show how to make use of the Nisan-Wigderson PRG construction to get a cryptographic, as opposed to a complexity-theoretic, PRG.
Biography
Yanyi Liu is a PhD student at Cornell Tech, advised by Rafael Pass and Elaine Shi.
4. Achieving Asynchronous MPC with Linear Communication and Optimal Resilience
Abstract
Secure multiparty computation (MPC) allows a set of n parties to jointly compute a function over their private inputs. The seminal works of Ben-Or, Canetti and Goldreich [STOC '93] and Ben-Or, Kelmer and Rabin [PODC '94] settled the feasibility of MPC over asynchronous networks. Despite the significant line of work devoted to improving the communication complexity, current protocols with information-theoretic security and optimal resilience t＜n/3 communicate Ω(n^4 C) field elements for a circuit with C multiplication gates. In contrast, synchronous MPC protocols with Ω(nC) communication have long been known.
In this talk, I will introduce our recent progress that gives the first information-theoretic AMPC with communication complexity O(nC) field elements. Our construction is obtained from the following two results:
- We first build an asynchronous complete secret-sharing (ACSS) protocol with linear communication complexity. ACSS allows a dealer to share a batch of Shamir sharings such that all parties eventually receive their shares. ACSS is an important building block in AMPC. We improve the previously best-known result by Choudhury and Patra [J. Cryptol '23], which requires O(n^3) elements per sharing, by a factor of n^2.
- We then provide a novel MPC protocol that makes black-box use of ACSS, where the cost per multiplication reduces to the cost of distributing a constant number of sharings via ACSS, improving a linear factor over the state of the art by Choudhury and Patra [IEEE Trans. Inf. Theory '17].
Biography
Yifan Song is an assistant professor at Tsinghua University. He received the Ph.D. degree from Carnegie Mellon University in 2022, advised by Prof. Vipul Goyal. Before that, he received the Bachelor degree from Yao Class at Tsinghua University in 2017.
Yifan Song is generally interested in theoretical Cryptography and has a special focus on secure multiparty computation. He has published more than 10 papers in the top conferences of Cryptography. He was a committee member of Eurocrypt 2023 and PKC 2024, and served as an external reviewer for many top conferences in Cryptography.
活动组织
刘天任
北京大学前沿计算研究中心助理教授
研究方向：密码学
关于中心
北京大学前沿计算研究中心（Center on Frontiers of Computing Studies, Peking University）成立于2017年12月，是北京大学新体制科研机构，由图灵奖获得者、中国政府“友谊奖”获得者、中国科学院外籍院士、北京大学访问讲席教授John Hopcroft和中国工程院院士、北京大学博雅讲席教授高文担任联合主任。
中心立足国际计算机学科前沿，与世界顶尖高校及科研机构建立密切的交流与合作关系，在计算理论如博弈论、信息论、量子信息与密码学，前沿计算方法如具身计算与人工智能，以及计算与机器人、经济、艺术和体育等多个领域的交叉方向展开前沿探索，创立具有国际一流影响力的计算科学研究中心；形成跨领域、交叉融合的计算应用支撑中心。
中心创建宽松自由的国际化学术环境，助力青年教师成长为计算机领域世界一流的学者；并以“图灵人才培养计划”为代表，建立国际先进的计算科学及相关交叉学科人才培养机制，为国家新时代科技发展和产业革新培养引领未来的卓越人才。