Zuzana Trubini and Martin Hirt receive TCC Test-of-Time Award
Dr. Zuzana Trubini and Dr. Martin Hirt receive the prestigious TCC Test-of-Time Award for their 2008 paper titled "Perfectly-Secure MPC with Linear Communication Complexity".
The award committee recognises the paper for introducing hyper-invertible matrices to perfectly secure multiparty computation, thus enabling significant efficiency improvements and, eventually, constructions with minimal communication complexity.
The award-winning paper:
A hyper-invertible matrix is a matrix whose every non-trivial square sub-matrix is invertible. Any m-by-n matrix induces a (linear) mapping from n input values to m output values; if the matrix is hyper-invertible, then the mapping has the property that from any n values (some inputs and some outputs), the remaining m values (some inputs and some outputs) can be computed.
Hyper-invertible matrices have various applications, in cryptography and beyond. For example, consider n random values, and an adversary who can manipulate t of them. Without knowing which are the manipulated values, is it possible to extract n-t values that are random and unknown to the adversary? The answer is yes, by applying a hyper-invertible (n-t)-by-n matrix to the n values. One can show that the n-t output values are uniformly distributed, statistically independent from the manipulated values.
Another application is to check the degree of polynomials. Consider a set of n polynomials of degree at most d, but again, an adversary can manipulate up to t of the polynomials and increase their degree. Such a manipulation can be detected by applying a hyper-invertible n-by-n matrix to the polynomials and checking the degree of arbitrary t of the output polynomials.
The awarded paper introduces hyper-invertible matrices and shows how they can be used to construct perfectly-secure multiparty computation at linear costs; i.e., for each multiplication, every participant has to communicate only a constant number of values.
Zuzana Trubini and Martin Hirt will receive the TCC Test-of-Time Award this upcoming November.
About Dr. Zuzana Trubini:
Zuzana Trubini studied mathematics at ETH Zurich and pursued a doctoral degree in the research group of Prof. Ueli Maurer. In her research, she focused on cryptographic protocols and multi-party computation in synchronous and asynchronous networks. Her results were published at renowned international conferences like TCC, Asiacrypt and PODC. She currently works at cnlab security AG as security analyst.
About Dr. Martin Hirt:
Martin Hirt holds a Master's degree in computer science and a doctoral degree in cryptography, both from ETH Zurich. The latter he obtained in 2001. His research focuses on cryptographic protocols, efficiency improvements, asynchronous networks, generalized adversary models and electronic voting. Martin's work was published at various prestigious conferences, such as TCC, Crypto and Eurocrypt. Currently, Martin is working as a senior research assistant and lecturer at the Institute of Theoretical Computer Science at ETH Zurich.
The Theory of Cryptography Conference (TCC)
The TCC Test-of-Time Award recognizes outstanding papers, published in TCC at least eight years ago, making a significant contribution to the theory of cryptography, preferably with influence also in other areas of cryptography, theory, and beyond. The award is given annually during the TCC conference. external page Read more