The Chinese University of Hong Kong
Department of Computer Science and Engineering

Regular Department Seminar Series

Title: On the complexity and efficiency of secret sharing schemes
Date: November 17, 2017 (Friday)
Time: 4:00 p.m. - 5:00 p.m.
Venue: Room 121, 1/F, Ho Sin-hang Engineering Building,
The Chinese University of Hong Kong,
Shatin, N.T.
Speaker: Prof. Andrej Bogdanov
Associate Professor
Department of Computer Science and Engineering
The Chinese University of Hong Kong



A secret sharing scheme is a mechanism for dividing up a secret among several parties so that unqualified subsets of the parties do not learn any information about the secret, while qualified subsets can recover the secret. Such schemes were introduced by Shamir and Blakley in 1979 and have become an indispensable component in the architecture of secure communication and computation protocols.

This talk will address the following foundational aspects of secret sharing and reconstruction:

  1. Most secret sharing schemes are based on codes or polynomials. Is the use of linear algebra a necessity in this context or merely a convenience? What are "non-algebraic" schemes good for? What happens if they don't exist?
  2. In known secret sharing schemes, the shares are sometimes substantially larger than the secret. Is this loss in information efficiency a necessary price to pay for security?

Our methods (from joint works with Siyao Guo, Yuval Ishai, Ilan Komargodski, Emanuele Viola, and Christopher Williamson) highlight connections between secret sharing, approximation theory, and game theory.



Andrej Bogdanov is associate professor of Computer Science and associate director of the Institute of Theoretical Computer Science and Communications at the Chinese University of Hong Kong. He obtained his B.Sc. and M.Eng. degrees from MIT and his Ph.D. from UC Berkeley. He has worked as a postdoctoral researcher at the Institute for Advanced Study in Princeton, at DIMACS (Rutgers University), and at ITCS (Tsinghua University), and as a visiting professor at the Tokyo Institute of Technology and at the Simons Institute for the Theory of Computing. His current research interests are in cryptography and the use of randomness in computation.


Enquiries: Mr. Calvin Tsang at tel. 3943 8440

For more information, please refer to