Zuzana Trubini and Martin Hirt receive TCC Test-of-Time Award 2020

Dr. Zuzana Trubini und Dr. Martin Hirt receive the prestigious TCC Test-of-Time Award for their 2008 paper titled "Perfectly-Secure MPC with Linear Communication Complexity".

Presentation, Event, November 18, 22.00 (CET) on YouTube

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.

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 November 18, 2020.

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.