Information-theoretic cryptography with minimal interaction (Tianren Liu)
Abstract
Information-theoretic cryptography deals with problems of secure communication and computation against computationally unbounded adversaries. Unlike much of cryptography that relies on unproven computational assumptions, information-theoretic cryptography provides absolute security guarantee without any computational assumption. This talk will mention many information-theoretic cryptography on secure computation, and will mainly focus on the *secret sharing* problem.
Secret sharing is widely used in secure computation, either with computational security or information-theoretic security. A secret scheme for a group of parties is associated to a policy specifying which subsets of parties are authorized. It allows a secret to be distributed among the group of parties, such that any authorized subset of parties can jointly recover the secret, and any unauthorized subset of parties jointly learn nothing about the secret. One of the major long-standing questions in information-theoretic cryptography is to understand the minimum size of the shares in a secret-sharing scheme for arbitrary monotone functions. There is an exponential gap between lower and upper bounds for secret sharing. The best known upper bound is 2^{n-o(n)}, while the best lower bound is n^2/log(n).
In a sequence of joint works with Vinod Vaikuntanathan and Hoeteck Wee, we improve this more-than-30-year-old upper bound by constructing secret sharing scheme for general monotone functions whose share size is 2^{0.994n}. As intermediate results, we reveal surprising connections between secret sharing and a few other problems in information-theoretic cryptography.
Time
2021-1-29 14:00 ~ 15:00
Speaker
Tianren Liu, University of Washington
Room
Zoom ID:97074603527，Password：123456
