Mathematical Sciences Colloquium - "Some recent results on all-or-nothing transforms, or “All or nothing at all”" by Doug Stinson (University of Waterloo), Stratton Hall 203

Friday, October 27, 2017
11:00 am to 11:50 am


Floor/Room #: 


Doug Stinson
University of Waterloo

Some recent results on all-or-nothing transforms, or “All or nothing at all”

ABSTRACT:  A (t,s,v)-all-or-nothing transform (AONT) is a bijective mapping defined on s-tuples over an alphabet of size v, which satisfies the condition that the values of any t input co-ordinates are completely undetermined, given the values of any s−t output co-ordinates. The main question I address in this talk is: for which choices of parameters does a (t,s,v)-AONT exist?

AONT were introduced by Ron Rivest in 1997 in the special case t=1, motivated by an application to encryption using block ciphers. This case is now well understood.

In this talk, I will discuss recent work which concerns various necessary as well as sufficient conditions for existence of these objects, mainly in the next case, t=2. I will also show some connections between AONT and other structures of combinatorial and cryptographic interest, such as orthogonal arrays and resilient functions.

A rich variety of mathematical techniques have turned out to be useful in this investigation, including coding theory, linear algebra, cyclotomy, design theory, quadratic programming, and the probabilistic method.