A serious look at game playing

OU researchers have found a potential flaw in one of the methods proposed for

The use of alphanumeric codes or passwords to protect information and resources is a classic method of security protection. In a secret sharing scheme, different elements of a code or password are shared between different individuals in such a way that all the individuals are required to contribute their ‘shares’ before the complete code can be recovered.

Various construction methods have been proposed for secret sharing schemes, many of which are based on mathematics – and in particular minimal defining sets. The received wisdom around such sets suggests that if one of the shares is missing, finding the key is impossible. However, in a recent breakthrough Professors Mike Grannell and Terry Griggs of the OU’s Mathematics Department, working with Anne Street from the University of Queensland, have found that in some instances it is possible to use the shares already in place to determine the identity of the missing one – which could mean that bank safes are not as secure as they seem.

A Sudoku puzzle is a good illustration of the mathematics involved. It is an example of a combinatorial design – it has entries (the numbers from 1 to 9) and a structure (a 9X9 square split into nine 3X3 sub-squares, with rules for completion). When you try a Sudoku puzzle, you hope that, within the rules, there is a unique completion. In mathematical terminology, we require that the entries given at the start form a defining set. A defining set is said to be minimal if the removal of any one of its entries leaves a puzzle with more than one completion. To see the connection with secret sharing, take a Sudoku puzzle whose starting entries form a minimal defining set. Give each entry (value and position) to a different person. Together, these people can re-create the puzzle. But if any one of them is missing or refuses to co-operate, it would appear that the original puzzle cannot, with certainty, be re-created.

The OU research team has proved that this is not necessarily true and has demonstrated that once given the identity of a subset, together with the knowledge that it is part of a minimal defining set, it is sometimes possible to re-create the original design and even to determine the missing entries from the minimal defining set.

Back to top