Разделение секрета – многочлены над конечными полями, комбинаторика, коды и матроиды

Доклад будет посвящен некоторым математическим задачам, возникающим при изучении так называемого разделения секрета. Саму задачу можно сформулировать так: надо «разделить» секрет между $n$ участниками таким образом, что разрешенные коалиции участников могли бы найти секрет, а любые неразрешенные не знали о секрете ничего «дополнительного», т.е. кроме априорных сведений. Самый популярный и изученный пример – пороговые схемы, т.е. разрешенные коалиции это все коалиции из $t$ или более участников, и никакие больше. Эта задача связана, в частности, со следующей гипотезой, известной в комбинаторике, теории кодирования и даже алгебраической геометрии – пусть множество из $n$ $r$-мерных векторов над конечным полем из $q$ элементов таково, что любые $r$ из них линейно независимы. Тогда $n<q+2$ (два исключения в характеристике $2$). Гипотеза недавно доказана для простых полей.
А еще мы обсудим задачу о построении семейств $k$-мерных подпространств в $n$-мерном пространстве со свойством «все или ничего», то есть линейная оболочка любого множества этих подпространств пересекается с фиксированным $k$-мерным подпространством либо по вектору $0$, либо содержит это фиксированное подпространство целиком. А отсюда уже рукой подать до матроидов!