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.