报名 | 北京密码学日
关键词：密码学
北京密码学日
about Cryptography Day
北京密码学日是密码学领域的单日研讨会，将于2024年6月15日在北京大学举办，由北京大学前沿计算研究中心刘天任老师组织，以特邀报告的方式，邀请国内外专家介绍在密码学领域的前沿进展。
会议日程
Agenda
Time | Content |
10:30-11:30 | Improving Garbled Circuits with Switch Systems David Heath, UIUC |
11:30-13:00 | Lunch Break |
13:00-14:00 | Cryptography from Learning Parity with Noise Yu Yu, SJTU |
14:00-14:20 | Coffee Break |
14:20-15:20 | A Direct PRF Construction from Kolmogorov Complexity Yanyi Liu, Cornell Tech |
15:20-15:40 | Coffee Break |
15:40-16:40 | Achieving Asynchronous MPC with Linear Communication and Optimal Resilience Yifan Song, THU |
互动报名
Registration
↑↑扫小程序码报名↑↑
密码学日上午内容线上进行，下午内容线下进行。
报名成功的观众将于6月14日收到通知邮件，含上午报告在线会议链接。
报告信息
以报告时间排序
Improving Garbled Circuits with Switch Systems
David Heath, University of Illinois Urbana-Champaign
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
University of Illinois Urbana-Champaign
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.
Cryptography from Learning Parity with Noise
Yu Yu, Shanghai Jiao Tong University
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
Shanghai Jiao Tong University
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).
A Direct PRF Construction from Kolmogorov Complexity
Yanyi Liu, Cornell Tech
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 , where given a threshold, , and a polynomial time-bound, , denotes the language consisting of strings with -bounded Kolmogorov complexity, , bounded by .
In more detail, we demonstrate a direct PRF construction with quasi-polynomial security from mild average-case of hardness of 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
Cornell Tech
Yanyi Liu is a PhD student at Cornell Tech, advised by Rafael Pass and Elaine Shi.
Achieving Asynchronous MPC with Linear Communication and Optimal Resilience
Yifan Song, Tsinghua University
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 communicate field elements for a circuit with multiplication gates. In contrast, synchronous MPC protocols with communication have long been known.
In this talk, I will introduce our recent progress that gives the first information-theoretic AMPC with communication complexity 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 elements per sharing, by a factor of .
- 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
Tsinghua University
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.
活动组织
Organizer
刘天任
北京大学前沿计算研究中心助理教授
研究方向：密码学
CFCS近期动态
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点“阅读原文”转报名链接