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

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 the n values to a hyper-invertible (n-t)-by-n matrix. 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 the polynomials to a hyper-invertible n-by-n matrix 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, PODC, amongst others. 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 Institue of Theoretical Computer Science at ETH Zurich.